This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new c2dda05 feat(xor): add immutable filters with portable serialization
(#309)
c2dda05 is described below
commit c2dda055bd416cd67109db31ecd8f2ceacc7348a
Author: tison <[email protected]>
AuthorDate: Fri Oct 30 16:57:29 2026 +0800
feat(xor): add immutable filters with portable serialization (#309)
---
CHANGELOG.md | 4 +
CONTRIBUTING.md | 2 +
Cargo.lock | 8 +
README.md | 3 +-
benchmarks/Cargo.toml | 2 +
benchmarks/main.rs | 1 +
benchmarks/xor/build.rs | 132 ++++
benchmarks/xor/matched_build.rs | 116 +++
benchmarks/{main.rs => xor/mod.rs} | 33 +-
benchmarks/xor/query.rs | 193 +++++
datasketches/Cargo.toml | 1 +
datasketches/src/codec/family.rs | 9 +
datasketches/src/codec/mod.rs | 2 +
datasketches/src/hash/mod.rs | 7 +-
datasketches/src/lib.rs | 5 +-
datasketches/src/xor/filter.rs | 805 +++++++++++++++++++++
datasketches/src/xor/mod.rs | 80 ++
datasketches/src/xor/serialization.rs | 243 +++++++
tests-integration/Cargo.toml | 2 +
tests-integration/tests/serde_tests.rs | 3 +
tests-integration/tests/serde_tests/xor.rs | 341 +++++++++
tests-integration/tests/xor_test/filter.rs | 162 +++++
.../tests/xor_test}/main.rs | 21 +-
tests-integration/tests/xor_test/parts.rs | 244 +++++++
24 files changed, 2378 insertions(+), 41 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 8e563c5..376478f 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -4,6 +4,10 @@ All significant changes to this project will be documented in
this file.
## Unreleased
+### New features
+
+* Add immutable `XorFilter` and `XorFilterBuilder` behind the `xor` feature,
with 8-, 16-, and 32-bit fingerprints, consuming builder configuration with
complete-input construction and bounded seeded retries, optional cardinality
metadata for imported filters, standard serialization for all three widths
(Java-compatible for 8/16-bit filters), and raw parts for application-defined
storage.
+
### Improvements
* `KllSketch::rank` is faster for repeated queries on compacted sketches.
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index c02d8d1..2798be7 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -168,6 +168,8 @@ cargo x prepare-testdata java
If no language is specified, all languages are prepared. These directories are
not stored in Git. Run the command before the first test run and again whenever
the pinned TCK revision changes. It requires network access and replaces the
selected generated directories.
+The pinned TCK revision does not yet contain XOR filter snapshots. Until it
does, `serde_tests/xor.rs` retains small hexadecimal fixtures generated from
the merged Java implementation, with the source revision and inputs documented
alongside them. Keep these separate from the synchronized `*_generated_files`
directories; replace them with TCK fixtures when available.
+
## Code of Conduct
We expect all community members to follow our [Code of
Conduct](https://www.apache.org/foundation/policies/conduct.html).
diff --git a/Cargo.lock b/Cargo.lock
index 81862f6..2421b06 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -86,6 +86,7 @@ dependencies = [
"datasketches",
"divan",
"rand",
+ "xorf",
]
[[package]]
@@ -782,6 +783,7 @@ dependencies = [
"googletest",
"insta",
"quickcheck",
+ "xorf",
]
[[package]]
@@ -1003,6 +1005,12 @@ dependencies = [
"which",
]
+[[package]]
+name = "xorf"
+version = "0.13.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0f13846c9009c0e550697ddde851e934b5dfafbce757a5ef5edfdb27ea20803e"
+
[[package]]
name = "zeroize"
version = "1.9.0"
diff --git a/README.md b/README.md
index 7ec87ca..37a86a3 100644
--- a/README.md
+++ b/README.md
@@ -75,6 +75,7 @@ Enable multiple algorithms by listing their features
together, such as `features
| `tdigest` | `TDigestMut`, `TDigest` | Quantile and rank
estimation, with high accuracy near distribution tails.
|
| `theta` | `ThetaSketch` and set operations | Distinct counts, set
expressions, and Jaccard similarity. |
| `tuple` | `TupleSketch` and set operations | Theta-style keys
with user-defined summaries attached to retained entries.
|
+| `xor` | `XorFilter`, `XorFilterBuilder` | Immutable
probabilistic membership with 8-, 16-, or 32-bit fingerprints.
|
See the [API documentation](https://docs.rs/datasketches) for configuration,
accuracy guarantees, serialization, and examples for each algorithm. Runnable
end-to-end scenarios live in [`datasketches/examples`](datasketches/examples).
@@ -82,7 +83,7 @@ See the [API documentation](https://docs.rs/datasketches) for
configuration, acc
The minimum supported Rust version is 1.86.0. The crate currently supports
little-endian targets only.
-Supported serialization formats are tested with fixtures produced by Apache
DataSketches Java, C++, and Go through the [DataSketches
TCK](https://github.com/apache/datasketches-tck).
+Supported serialization formats are tested with fixtures produced by Apache
DataSketches Java, C++, and Go through the [DataSketches
TCK](https://github.com/apache/datasketches-tck). XOR additionally uses
fixtures generated from the merged Java implementation until TCK snapshots are
available. Its standard format supports 8-, 16-, and 32-bit fingerprints;
32-bit images require a reader that supports that width. Formats without an
item count use the raw-parts API.
Serialization compatibility does not imply that an ordinary Rust `Hash`
implementation produces the same update bytes across languages. When sketches
must represent the same inputs across implementations, use
`hash::value::{raw_bytes, canonical_float, sign_extend, natural_extend}` (and
the constructors within those modules) to select matching input encodings. When
interoperating with an implementation that skips empty strings, skip them
before updating here as well.
diff --git a/benchmarks/Cargo.toml b/benchmarks/Cargo.toml
index 25af32a..49c3b9b 100644
--- a/benchmarks/Cargo.toml
+++ b/benchmarks/Cargo.toml
@@ -23,6 +23,7 @@ edition.workspace = true
rust-version.workspace = true
[dev-dependencies]
+xorf = { version = "=0.13.0", default-features = false }
datasketches = { workspace = true, features = [
"bloom",
"countmin",
@@ -34,6 +35,7 @@ datasketches = { workspace = true, features = [
"tdigest",
"theta",
"tuple",
+ "xor",
] }
divan = { workspace = true }
rand = { workspace = true }
diff --git a/benchmarks/main.rs b/benchmarks/main.rs
index ee28803..202f8e0 100644
--- a/benchmarks/main.rs
+++ b/benchmarks/main.rs
@@ -31,6 +31,7 @@ mod req;
mod tdigest;
mod theta;
mod tuple;
+mod xor;
fn main() {
divan::main();
diff --git a/benchmarks/xor/build.rs b/benchmarks/xor/build.rs
new file mode 100644
index 0000000..153c063
--- /dev/null
+++ b/benchmarks/xor/build.rs
@@ -0,0 +1,132 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use datasketches::xor::XorFilterBuilder;
+use datasketches::xor::XorFilterType;
+use divan::Bencher;
+use divan::black_box;
+use divan::counter::ItemsCount;
+
+use crate::xor::hashes;
+
+#[divan::bench(args = [1_000, 16_384, 49_999, 50_000, 50_001, 100_000])]
+fn datasketches_distinct_8(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor8)
+ .build_from_distinct_hashes(&keys)
+ .unwrap(),
+ )
+ });
+}
+
+#[divan::bench(args = [1_000, 16_384, 49_999, 50_000, 50_001, 100_000])]
+fn datasketches_deduplicate_8(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor8)
+ .build_from_hashes(keys.iter().copied())
+ .unwrap(),
+ )
+ });
+}
+
+#[divan::bench(args = [1_000, 16_384, 49_999, 50_000, 50_001, 100_000])]
+fn xorf_8(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(||
black_box(xorf::Xor8::from_iterator(keys.iter().copied())));
+}
+
+#[divan::bench(args = [1_000, 16_384, 49_999, 50_000, 50_001, 100_000])]
+fn datasketches_distinct_16(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor16)
+ .build_from_distinct_hashes(&keys)
+ .unwrap(),
+ )
+ });
+}
+
+#[divan::bench(args = [1_000, 16_384, 49_999, 50_000, 50_001, 100_000])]
+fn datasketches_deduplicate_16(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor16)
+ .build_from_hashes(keys.iter().copied())
+ .unwrap(),
+ )
+ });
+}
+
+#[divan::bench(args = [1_000, 16_384, 49_999, 50_000, 50_001, 100_000])]
+fn xorf_16(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(||
black_box(xorf::Xor16::from_iterator(keys.iter().copied())));
+}
+
+#[divan::bench(args = [1_000, 16_384, 49_999, 50_000, 50_001, 100_000])]
+fn datasketches_distinct_32(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor32)
+ .build_from_distinct_hashes(&keys)
+ .unwrap(),
+ )
+ });
+}
+
+#[divan::bench(args = [1_000, 16_384, 49_999, 50_000, 50_001, 100_000])]
+fn datasketches_deduplicate_32(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor32)
+ .build_from_hashes(keys.iter().copied())
+ .unwrap(),
+ )
+ });
+}
+
+#[divan::bench(args = [1_000, 16_384, 49_999, 50_000, 50_001, 100_000])]
+fn xorf_32(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(||
black_box(xorf::Xor32::from_iterator(keys.iter().copied())));
+}
diff --git a/benchmarks/xor/matched_build.rs b/benchmarks/xor/matched_build.rs
new file mode 100644
index 0000000..fe1ad4d
--- /dev/null
+++ b/benchmarks/xor/matched_build.rs
@@ -0,0 +1,116 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use datasketches::xor::XorFilterBuilder;
+use datasketches::xor::XorFilterType;
+use divan::Bencher;
+use divan::black_box;
+use divan::counter::ItemsCount;
+
+use crate::xor::hashes_with_offset;
+
+// xorf 0.13 starts SplitMix at 1. Both builders use the same seed sequence;
+// equal winning seeds therefore imply equal attempt counts. The offset 917504
+// case exercises a second attempt; every case verifies equal winning seeds.
+fn verify_seed(keys: &[u64], kind: XorFilterType) {
+ let filter = XorFilterBuilder::new(kind)
+ .seed(1)
+ .build_from_distinct_hashes(keys)
+ .unwrap();
+ assert_eq!(filter.seed(), xorf::Xor8::from(keys).seed);
+}
+
+#[divan::bench(args = [(1_000, 0), (16_384, 0), (16_384, 917_504), (49_999,
0), (50_000, 0), (50_001, 0), (100_000, 0), (8_000_000, 0)])]
+fn datasketches_8(bencher: Bencher, case: (usize, u64)) {
+ let (cardinality, offset) = case;
+ let keys = hashes_with_offset(cardinality, offset);
+ verify_seed(&keys, XorFilterType::Xor8);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor8)
+ .seed(1)
+ .build_from_distinct_hashes(&keys)
+ .unwrap(),
+ )
+ });
+}
+
+#[divan::bench(args = [(1_000, 0), (16_384, 0), (16_384, 917_504), (49_999,
0), (50_000, 0), (50_001, 0), (100_000, 0), (8_000_000, 0)])]
+fn xorf_8(bencher: Bencher, case: (usize, u64)) {
+ let (cardinality, offset) = case;
+ let keys = hashes_with_offset(cardinality, offset);
+ verify_seed(&keys, XorFilterType::Xor8);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(||
black_box(xorf::Xor8::from_iterator(keys.iter().copied())));
+}
+
+#[divan::bench(args = [(1_000, 0), (16_384, 0), (16_384, 917_504), (49_999,
0), (50_000, 0), (50_001, 0), (100_000, 0), (8_000_000, 0)])]
+fn datasketches_16(bencher: Bencher, case: (usize, u64)) {
+ let (cardinality, offset) = case;
+ let keys = hashes_with_offset(cardinality, offset);
+ verify_seed(&keys, XorFilterType::Xor16);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor16)
+ .seed(1)
+ .build_from_distinct_hashes(&keys)
+ .unwrap(),
+ )
+ });
+}
+
+#[divan::bench(args = [(1_000, 0), (16_384, 0), (16_384, 917_504), (49_999,
0), (50_000, 0), (50_001, 0), (100_000, 0), (8_000_000, 0)])]
+fn xorf_16(bencher: Bencher, case: (usize, u64)) {
+ let (cardinality, offset) = case;
+ let keys = hashes_with_offset(cardinality, offset);
+ verify_seed(&keys, XorFilterType::Xor16);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(||
black_box(xorf::Xor16::from_iterator(keys.iter().copied())));
+}
+
+#[divan::bench(args = [(1_000, 0), (16_384, 0), (16_384, 917_504), (49_999,
0), (50_000, 0), (50_001, 0), (100_000, 0), (8_000_000, 0)])]
+fn datasketches_32(bencher: Bencher, case: (usize, u64)) {
+ let (cardinality, offset) = case;
+ let keys = hashes_with_offset(cardinality, offset);
+ verify_seed(&keys, XorFilterType::Xor32);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor32)
+ .seed(1)
+ .build_from_distinct_hashes(&keys)
+ .unwrap(),
+ )
+ });
+}
+
+#[divan::bench(args = [(1_000, 0), (16_384, 0), (16_384, 917_504), (49_999,
0), (50_000, 0), (50_001, 0), (100_000, 0), (8_000_000, 0)])]
+fn xorf_32(bencher: Bencher, case: (usize, u64)) {
+ let (cardinality, offset) = case;
+ let keys = hashes_with_offset(cardinality, offset);
+ verify_seed(&keys, XorFilterType::Xor32);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(||
black_box(xorf::Xor32::from_iterator(keys.iter().copied())));
+}
diff --git a/benchmarks/main.rs b/benchmarks/xor/mod.rs
similarity index 58%
copy from benchmarks/main.rs
copy to benchmarks/xor/mod.rs
index ee28803..cf9fbfc 100644
--- a/benchmarks/main.rs
+++ b/benchmarks/xor/mod.rs
@@ -15,23 +15,22 @@
// specific language governing permissions and limitations
// under the License.
-use divan::AllocProfiler;
+mod build;
+mod matched_build;
+mod query;
-#[global_allocator]
-static ALLOC: AllocProfiler = AllocProfiler::system();
-
-mod bloom;
-mod countmin;
-mod cpc;
-mod frequencies;
-mod hash_inputs;
-mod hll;
-mod kll;
-mod req;
-mod tdigest;
-mod theta;
-mod tuple;
+// SplitMix is a permutation, so these pseudorandom precomputed hashes are
distinct.
+fn hashes(count: usize) -> Vec<u64> {
+ hashes_with_offset(count, 0)
+}
-fn main() {
- divan::main();
+fn hashes_with_offset(count: usize, offset: u64) -> Vec<u64> {
+ (offset..offset + count as u64)
+ .map(|i| {
+ let mut z = i.wrapping_add(0x9e3779b97f4a7c15);
+ z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
+ z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
+ z ^ (z >> 31)
+ })
+ .collect()
}
diff --git a/benchmarks/xor/query.rs b/benchmarks/xor/query.rs
new file mode 100644
index 0000000..af31987
--- /dev/null
+++ b/benchmarks/xor/query.rs
@@ -0,0 +1,193 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use datasketches::xor::XorFilterBuilder;
+use datasketches::xor::XorFilterType;
+use divan::Bencher;
+use divan::black_box;
+use divan::counter::ItemsCount;
+use xorf::Filter as _;
+
+use crate::xor::hashes;
+
+#[divan::bench(args = [16_384, 50_000])]
+fn datasketches_8_present(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = XorFilterBuilder::new(XorFilterType::Xor8)
+ .build_from_distinct_hashes(&keys[..cardinality])
+ .unwrap();
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[..cardinality] {
+ black_box(filter.contains_hash(black_box(*key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn datasketches_8_absent(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = XorFilterBuilder::new(XorFilterType::Xor8)
+ .build_from_distinct_hashes(&keys[..cardinality])
+ .unwrap();
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[cardinality..] {
+ black_box(filter.contains_hash(black_box(*key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn xorf_8_present(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = xorf::Xor8::from(&keys[..cardinality]);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[..cardinality] {
+ black_box(filter.contains(black_box(key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn xorf_8_absent(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = xorf::Xor8::from(&keys[..cardinality]);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[cardinality..] {
+ black_box(filter.contains(black_box(key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn datasketches_16_present(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = XorFilterBuilder::new(XorFilterType::Xor16)
+ .build_from_distinct_hashes(&keys[..cardinality])
+ .unwrap();
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[..cardinality] {
+ black_box(filter.contains_hash(black_box(*key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn datasketches_16_absent(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = XorFilterBuilder::new(XorFilterType::Xor16)
+ .build_from_distinct_hashes(&keys[..cardinality])
+ .unwrap();
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[cardinality..] {
+ black_box(filter.contains_hash(black_box(*key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn xorf_16_present(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = xorf::Xor16::from(&keys[..cardinality]);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[..cardinality] {
+ black_box(filter.contains(black_box(key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn xorf_16_absent(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = xorf::Xor16::from(&keys[..cardinality]);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[cardinality..] {
+ black_box(filter.contains(black_box(key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn datasketches_32_present(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = XorFilterBuilder::new(XorFilterType::Xor32)
+ .build_from_distinct_hashes(&keys[..cardinality])
+ .unwrap();
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[..cardinality] {
+ black_box(filter.contains_hash(black_box(*key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn datasketches_32_absent(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = XorFilterBuilder::new(XorFilterType::Xor32)
+ .build_from_distinct_hashes(&keys[..cardinality])
+ .unwrap();
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[cardinality..] {
+ black_box(filter.contains_hash(black_box(*key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn xorf_32_present(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = xorf::Xor32::from(&keys[..cardinality]);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[..cardinality] {
+ black_box(filter.contains(black_box(key)));
+ }
+ });
+}
+
+#[divan::bench(args = [16_384, 50_000])]
+fn xorf_32_absent(bencher: Bencher, cardinality: usize) {
+ let keys = hashes(cardinality * 2);
+ let filter = xorf::Xor32::from(&keys[..cardinality]);
+ bencher
+ .counter(ItemsCount::new(cardinality))
+ .bench_local(|| {
+ for key in &keys[cardinality..] {
+ black_box(filter.contains(black_box(key)));
+ }
+ });
+}
diff --git a/datasketches/Cargo.toml b/datasketches/Cargo.toml
index 2c931fc..adbbb84 100644
--- a/datasketches/Cargo.toml
+++ b/datasketches/Cargo.toml
@@ -48,6 +48,7 @@ req = []
tdigest = []
theta = []
tuple = []
+xor = []
[[example]]
name = "bloom_difference"
diff --git a/datasketches/src/codec/family.rs b/datasketches/src/codec/family.rs
index 734d529..06a8f3d 100644
--- a/datasketches/src/codec/family.rs
+++ b/datasketches/src/codec/family.rs
@@ -124,6 +124,15 @@ impl Family {
min_pre_longs: 3,
max_pre_longs: 4,
};
+
+ /// Immutable XOR Filter.
+ #[cfg(feature = "xor")]
+ pub const XORFILTER: Family = Family {
+ id: 22,
+ name: "XORFILTER",
+ min_pre_longs: 3,
+ max_pre_longs: 3,
+ };
}
impl Family {
diff --git a/datasketches/src/codec/mod.rs b/datasketches/src/codec/mod.rs
index d6b6a06..7c50da3 100644
--- a/datasketches/src/codec/mod.rs
+++ b/datasketches/src/codec/mod.rs
@@ -33,6 +33,7 @@ pub use self::encode::SketchBytes;
feature = "tdigest",
feature = "theta",
feature = "tuple",
+ feature = "xor",
))]
#[allow(dead_code)] // some utilities are only used for certain sketches
pub(crate) mod assert;
@@ -48,5 +49,6 @@ pub(crate) mod assert;
feature = "tdigest",
feature = "theta",
feature = "tuple",
+ feature = "xor",
))]
pub(crate) mod family;
diff --git a/datasketches/src/hash/mod.rs b/datasketches/src/hash/mod.rs
index 2084902..f2dde4f 100644
--- a/datasketches/src/hash/mod.rs
+++ b/datasketches/src/hash/mod.rs
@@ -38,9 +38,9 @@ mod murmurhash;
))]
pub(crate) use self::murmurhash::*;
-#[cfg(feature = "bloom")]
+#[cfg(any(feature = "bloom", feature = "xor"))]
mod xxhash;
-#[cfg(feature = "bloom")]
+#[cfg(any(feature = "bloom", feature = "xor"))]
pub(crate) use self::xxhash::*;
#[cfg(any(
@@ -82,7 +82,7 @@ pub(crate) use self::seed::*;
))]
pub(crate) const DEFAULT_UPDATE_SEED: u64 = 9001;
-#[cfg(feature = "bloom")]
+#[cfg(any(feature = "bloom", feature = "xor"))]
#[inline(always)]
fn read_u32_le(bytes: &[u8]) -> u32 {
u32::from_le_bytes(bytes.try_into().expect("four-byte hash input"))
@@ -96,6 +96,7 @@ fn read_u32_le(bytes: &[u8]) -> u32 {
feature = "hll",
feature = "theta",
feature = "tuple",
+ feature = "xor",
))]
#[inline(always)]
fn read_u64_le(bytes: &[u8]) -> u64 {
diff --git a/datasketches/src/lib.rs b/datasketches/src/lib.rs
index 813a841..18cd2bc 100644
--- a/datasketches/src/lib.rs
+++ b/datasketches/src/lib.rs
@@ -33,7 +33,7 @@
//!
//! ## Choosing a sketch
//!
-//! * Use `bloom` for probabilistic membership queries.
+//! * Use `bloom` for incremental probabilistic membership queries or `xor`
for immutable sets.
//! * Use `countmin` for point-frequency estimates and `frequencies` for
discovering heavy hitters.
//! * Use `hll` for fast distinct counts, `cpc` for compact serialized
distinct counts, or `theta`
//! when set operations are required.
@@ -92,6 +92,9 @@ pub use self::thetafamily::theta;
#[cfg(feature = "tuple")]
pub use self::thetafamily::tuple;
+#[cfg(feature = "xor")]
+pub mod xor;
+
// common modules
pub mod codec;
pub mod common;
diff --git a/datasketches/src/xor/filter.rs b/datasketches/src/xor/filter.rs
new file mode 100644
index 0000000..0762b40
--- /dev/null
+++ b/datasketches/src/xor/filter.rs
@@ -0,0 +1,805 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::hash::Hash;
+use std::hash::Hasher;
+use std::ops::BitXor;
+
+use crate::error::Error;
+use crate::hash::XxHash64;
+
+const NUM_HASHES: u8 = 3;
+const HASH_SEED: u64 = 0;
+const DEFAULT_CONSTRUCTION_SEED: u64 = 0;
+const LOAD_FACTOR: f64 = 1.23;
+const CAPACITY_OFFSET: u64 = 32;
+const MAX_CONSTRUCTION_ATTEMPTS: usize = 100;
+
+const MURMUR_C1: u64 = 0xff51_afd7_ed55_8ccd;
+const MURMUR_C2: u64 = 0xc4ce_b9fe_1a85_ec53;
+
+const SPLITMIX_GAMMA: u64 = 0x9e37_79b9_7f4a_7c15;
+const SPLITMIX_MUL1: u64 = 0xbf58_476d_1ce4_e5b9;
+const SPLITMIX_MUL2: u64 = 0x94d0_49bb_1331_11eb;
+
+/// Fingerprint representation used by an [`XorFilter`].
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub enum XorFilterType {
+ /// Uses 8-bit fingerprints and has an expected false-positive probability
of about `1 / 256`.
+ Xor8,
+ /// Uses 16-bit fingerprints and has an expected false-positive
probability of about
+ /// `1 / 65_536`.
+ Xor16,
+ /// Uses 32-bit fingerprints and has an expected false-positive
probability of about `2^-32`.
+ Xor32,
+}
+
+impl XorFilterType {
+ /// Returns the number of bits in each fingerprint.
+ pub const fn bits_per_fingerprint(self) -> u8 {
+ match self {
+ Self::Xor8 => 8,
+ Self::Xor16 => 16,
+ Self::Xor32 => 32,
+ }
+ }
+
+ pub(crate) const fn bytes_per_fingerprint(self) -> usize {
+ (self.bits_per_fingerprint() / 8) as usize
+ }
+}
+
+/// Owned fingerprint slots for importing and exporting an application-defined
format.
+///
+/// Slots are ordered as three consecutive, equally sized segments.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum XorFingerprints {
+ /// 8-bit fingerprint slots.
+ Xor8(Box<[u8]>),
+ /// 16-bit fingerprint slots.
+ Xor16(Box<[u16]>),
+ /// 32-bit fingerprint slots.
+ Xor32(Box<[u32]>),
+}
+
+impl XorFingerprints {
+ fn len(&self) -> usize {
+ match self {
+ Self::Xor8(values) => values.len(),
+ Self::Xor16(values) => values.len(),
+ Self::Xor32(values) => values.len(),
+ }
+ }
+
+ pub(crate) fn byte_len(&self) -> usize {
+ match self {
+ Self::Xor8(values) => size_of_val::<[u8]>(values),
+ Self::Xor16(values) => size_of_val::<[u16]>(values),
+ Self::Xor32(values) => size_of_val::<[u32]>(values),
+ }
+ }
+}
+
+/// Raw state of an [`XorFilter`] for application-defined storage.
+///
+/// Created by [`XorFilter::into_parts`] or [`XorFilterParts::new`], and
consumed by
+/// [`XorFilter::from_parts`], which validates the layout.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct XorFilterParts {
+ seed: u64,
+ segment_length: usize,
+ fingerprints: XorFingerprints,
+ num_items: Option<usize>,
+}
+
+impl XorFilterParts {
+ /// Creates parts from a construction seed, segment length, and
fingerprint slots.
+ ///
+ /// The item count is unknown unless set with
[`with_num_items`](Self::with_num_items).
+ pub fn new(seed: u64, segment_length: usize, fingerprints:
XorFingerprints) -> Self {
+ Self {
+ seed,
+ segment_length,
+ fingerprints,
+ num_items: None,
+ }
+ }
+
+ /// Records the number of distinct hashes in the original input set.
+ ///
+ /// Standard serialization and emptiness checks require a known item count.
+ pub fn with_num_items(mut self, num_items: usize) -> Self {
+ self.num_items = Some(num_items);
+ self
+ }
+
+ /// Returns the construction seed.
+ pub fn seed(&self) -> u64 {
+ self.seed
+ }
+
+ /// Returns the number of fingerprint slots in each of the three segments.
+ pub fn segment_length(&self) -> usize {
+ self.segment_length
+ }
+
+ /// Returns the fingerprint slots.
+ pub fn fingerprints(&self) -> &XorFingerprints {
+ &self.fingerprints
+ }
+
+ /// Returns the number of distinct input hashes, or `None` if unknown.
+ pub fn num_items(&self) -> Option<usize> {
+ self.num_items
+ }
+
+ /// Returns the fingerprint slots without copying.
+ pub fn into_fingerprints(self) -> XorFingerprints {
+ self.fingerprints
+ }
+}
+
+/// An immutable xor filter for probabilistic set membership.
+///
+/// A query that returns `false` proves that the item was not in the input
set. A query that returns
+/// `true` may be a false positive, with probability determined by
[`XorFilterType`]. A filter
+/// known to be empty always returns `false`. Values cannot
+/// be added after construction; rebuild the filter when the set changes.
+///
+/// Ordinary values passed to [`contains`](Self::contains) are reduced to
64-bit hashes with
+/// xxHash64 and seed `0`. Use [`contains_hash`](Self::contains_hash) only
with the same hashes that
+/// were supplied to [`XorFilterBuilder::build_from_hashes`] or
+/// [`XorFilterBuilder::build_from_distinct_hashes`].
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct XorFilter {
+ pub(crate) segment_length: usize,
+ pub(crate) num_items: Option<usize>,
+ pub(crate) seed: u64,
+ pub(crate) fingerprints: XorFingerprints,
+}
+
+impl XorFilter {
+ /// Imports raw parts without requiring a DataSketches serialization
header.
+ ///
+ /// The caller must preserve the original construction seed and
fingerprint order, and query
+ /// with the original input hashes. A supplied item count must describe
the original set.
+ /// A valid layout alone cannot establish these invariants.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error unless the segment length is positive, the payload
has exactly three
+ /// segments, and a supplied item count fits the capacity. Segment lengths
above `u32::MAX`
+ /// are rejected because the index reduction uses 32-bit hash words.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::xor::XorFilter;
+ /// use datasketches::xor::XorFilterBuilder;
+ /// use datasketches::xor::XorFilterParts;
+ /// use datasketches::xor::XorFilterType;
+ ///
+ /// let filter =
XorFilterBuilder::new(XorFilterType::Xor8).build_from_hashes([10, 20, 30])?;
+ /// let parts = filter.into_parts();
+ /// // A storage format that does not record the item count keeps only
these fields.
+ /// let parts = XorFilterParts::new(
+ /// parts.seed(),
+ /// parts.segment_length(),
+ /// parts.into_fingerprints(),
+ /// );
+ /// let imported = XorFilter::from_parts(parts)?;
+ /// assert!(imported.contains_hash(20));
+ /// assert_eq!(imported.num_items(), None);
+ /// # Ok::<(), datasketches::error::Error>(())
+ /// ```
+ pub fn from_parts(parts: XorFilterParts) -> Result<Self, Error> {
+ let XorFilterParts {
+ seed,
+ segment_length,
+ fingerprints,
+ num_items,
+ } = parts;
+ if segment_length == 0
+ || segment_length > u32::MAX as usize
+ || segment_length.checked_mul(3) != Some(fingerprints.len())
+ {
+ return Err(Error::invalid_argument(
+ "invalid xor filter segment or payload length",
+ ));
+ }
+ if num_items.is_some_and(|count| count > fingerprints.len()) {
+ return Err(Error::invalid_argument(
+ "item count exceeds xor filter capacity",
+ ));
+ }
+ Ok(Self {
+ segment_length,
+ num_items,
+ seed,
+ fingerprints,
+ })
+ }
+
+ /// Returns the number of fingerprint slots in each of the three segments.
+ pub fn segment_length(&self) -> usize {
+ self.segment_length
+ }
+
+ /// Returns the fingerprint slots for application-defined serialization.
+ pub fn fingerprints(&self) -> &XorFingerprints {
+ &self.fingerprints
+ }
+
+ /// Converts the filter into raw parts without copying the fingerprint
slots.
+ pub fn into_parts(self) -> XorFilterParts {
+ XorFilterParts {
+ seed: self.seed,
+ segment_length: self.segment_length,
+ fingerprints: self.fingerprints,
+ num_items: self.num_items,
+ }
+ }
+
+ /// Returns `true` if an item is possibly in the input set.
+ ///
+ /// A `false` result means the item was definitely absent; a `true` result
may be a false
+ /// positive.
+ #[inline]
+ pub fn contains<T: Hash + ?Sized>(&self, item: &T) -> bool {
+ self.contains_hash(hash_item(item))
+ }
+
+ /// Returns `true` if a precomputed 64-bit hash is possibly in the input
set.
+ ///
+ /// This method bypasses xxHash64. The caller must use the same hash value
during construction
+ /// and queries; mixing raw values with precomputed hashes can introduce
false negatives.
+ #[inline]
+ pub fn contains_hash(&self, hash: u64) -> bool {
+ if self.num_items == Some(0) {
+ return false;
+ }
+ let mixed = mix(hash, self.seed);
+ let [h0, h1, h2] = indexes(mixed, self.segment_length);
+
+ match &self.fingerprints {
+ XorFingerprints::Xor8(fingerprints) => {
+ fingerprint(mixed) as u8 == fingerprints[h0] ^
fingerprints[h1] ^ fingerprints[h2]
+ }
+ XorFingerprints::Xor16(fingerprints) => {
+ fingerprint(mixed) as u16 == fingerprints[h0] ^
fingerprints[h1] ^ fingerprints[h2]
+ }
+ XorFingerprints::Xor32(fingerprints) => {
+ fingerprint(mixed) as u32 == fingerprints[h0] ^
fingerprints[h1] ^ fingerprints[h2]
+ }
+ }
+ }
+
+ /// Returns whether the input set was empty, or `None` if imported without
an item count.
+ ///
+ /// Fingerprint contents cannot reliably establish whether the original
set was empty.
+ pub fn is_empty(&self) -> Option<bool> {
+ self.num_items.map(|count| count == 0)
+ }
+
+ /// Returns the number of distinct input hashes, or `None` if imported
without a count.
+ pub fn num_items(&self) -> Option<usize> {
+ self.num_items
+ }
+
+ /// Returns the fingerprint representation.
+ pub fn filter_type(&self) -> XorFilterType {
+ match &self.fingerprints {
+ XorFingerprints::Xor8(_) => XorFilterType::Xor8,
+ XorFingerprints::Xor16(_) => XorFilterType::Xor16,
+ XorFingerprints::Xor32(_) => XorFilterType::Xor32,
+ }
+ }
+
+ /// Returns the number of bits in each fingerprint.
+ pub fn bits_per_fingerprint(&self) -> u8 {
+ self.filter_type().bits_per_fingerprint()
+ }
+
+ /// Returns the number of hash locations used by non-empty filter queries.
+ pub fn num_hashes(&self) -> u8 {
+ NUM_HASHES
+ }
+
+ /// Returns the number of fingerprint slots in the filter.
+ pub fn capacity(&self) -> usize {
+ self.fingerprints.len()
+ }
+
+ /// Returns the construction seed stored with the filter.
+ pub fn seed(&self) -> u64 {
+ self.seed
+ }
+
+ /// Returns the number of fingerprint bits allocated per distinct input
hash.
+ ///
+ /// Returns `None` for an unknown item count and `Some(0.0)` for an empty
filter. For
+ /// sufficiently large inputs the value approaches `9.84` for
[`XorFilterType::Xor8`],
+ /// `19.68` for [`XorFilterType::Xor16`], and `39.36` for
[`XorFilterType::Xor32`].
+ pub fn bits_per_item(&self) -> Option<f64> {
+ self.num_items.map(|count| {
+ if count == 0 {
+ 0.0
+ } else {
+ self.capacity() as f64 *
f64::from(self.bits_per_fingerprint()) / count as f64
+ }
+ })
+ }
+
+ /// Returns the estimated in-memory size of the filter in bytes.
+ pub fn estimated_size(&self) -> usize {
+ size_of::<Self>() + self.fingerprints.byte_len()
+ }
+
+ fn build(
+ keys: &[u64],
+ filter_type: XorFilterType,
+ base_seed: u64,
+ max_attempts: usize,
+ ) -> Result<Self, Error> {
+ debug_assert!(max_attempts > 0);
+ let num_items = keys.len();
+ let capacity = compute_capacity(num_items)?;
+ let segment_length = capacity / usize::from(NUM_HASHES);
+ let mut xor_mask = vec![0_u64; capacity];
+ let mut count = vec![0_u32; capacity];
+ let mut queue = vec![0_u32; capacity];
+ let mut stack_hash = vec![0_u64; num_items];
+ let mut stack_index = vec![0_u32; num_items];
+
+ let mut rng_state = base_seed;
+ let mut construction_seed = 0;
+ let mut stack_size = 0;
+ for attempt in 0..max_attempts {
+ if attempt != 0 {
+ xor_mask.fill(0);
+ count.fill(0);
+ }
+ rng_state = rng_state.wrapping_add(SPLITMIX_GAMMA);
+ construction_seed = splitmix64(rng_state);
+ stack_size = map(
+ keys,
+ construction_seed,
+ segment_length,
+ &mut xor_mask,
+ &mut count,
+ &mut queue,
+ &mut stack_hash,
+ &mut stack_index,
+ );
+ if stack_size == num_items {
+ break;
+ }
+ // For a fixed seed, mixing is a bijection, so two remaining
hashes that cancel
+ // out are the same input hash. Reseeding cannot separate
duplicates.
+ if count.iter().zip(&xor_mask).any(|(&c, &m)| c == 2 && m == 0) {
+ return Err(
+ Error::invalid_argument("xor filter input contains
duplicate hashes")
+ .with_context("num_items", num_items),
+ );
+ }
+ }
+
+ if stack_size != num_items {
+ return Err(Error::invalid_argument(format!(
+ "xor filter construction failed after {max_attempts} attempts"
+ ))
+ .with_context("num_items", num_items));
+ }
+
+ let fingerprints = match filter_type {
+ XorFilterType::Xor8 => {
+ let mut values = vec![0_u8; capacity].into_boxed_slice();
+ assign_fingerprints(
+ &mut values,
+ segment_length,
+ &stack_hash[..stack_size],
+ &stack_index[..stack_size],
+ |hash| fingerprint(hash) as u8,
+ );
+ XorFingerprints::Xor8(values)
+ }
+ XorFilterType::Xor16 => {
+ let mut values = vec![0_u16; capacity].into_boxed_slice();
+ assign_fingerprints(
+ &mut values,
+ segment_length,
+ &stack_hash[..stack_size],
+ &stack_index[..stack_size],
+ |hash| fingerprint(hash) as u16,
+ );
+ XorFingerprints::Xor16(values)
+ }
+ XorFilterType::Xor32 => {
+ let mut values = vec![0_u32; capacity].into_boxed_slice();
+ assign_fingerprints(
+ &mut values,
+ segment_length,
+ &stack_hash[..stack_size],
+ &stack_index[..stack_size],
+ |hash| fingerprint(hash) as u32,
+ );
+ XorFingerprints::Xor32(values)
+ }
+ };
+
+ Ok(Self {
+ segment_length,
+ num_items: Some(num_items),
+ seed: construction_seed,
+ fingerprints,
+ })
+ }
+}
+
+/// Builder for configuring and creating an immutable [`XorFilter`].
+///
+/// Stores only the fingerprint type and construction seed. Each build
consumes the configuration
+/// and takes the complete input set. Ordinary values and precomputed hashes
are deduplicated in
+/// temporary storage; already-distinct hashes can be borrowed without copying
or sorting.
+#[derive(Debug, Clone)]
+pub struct XorFilterBuilder {
+ filter_type: XorFilterType,
+ seed: u64,
+}
+
+impl XorFilterBuilder {
+ /// Creates a builder for the requested fingerprint representation.
+ ///
+ /// The default base construction seed is `0`.
+ pub fn new(filter_type: XorFilterType) -> Self {
+ Self {
+ filter_type,
+ seed: DEFAULT_CONSTRUCTION_SEED,
+ }
+ }
+
+ /// Sets the base seed used to derive construction attempts.
+ ///
+ /// A fixed seed makes construction deterministic for a given set of
hashes. The filter stores
+ /// the successful derived seed, which is returned by [`XorFilter::seed`].
+ pub fn seed(mut self, seed: u64) -> Self {
+ self.seed = seed;
+ self
+ }
+
+ /// Builds a filter from values hashed by xxHash64 with seed `0`.
+ ///
+ /// Duplicate hashes are removed before construction. The input is
consumed as an iterator;
+ /// pass borrowed values to retain them for a later build, including after
an error.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error under the same conditions as
+ /// [`build_from_hashes`](Self::build_from_hashes).
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::xor::XorFilterBuilder;
+ /// use datasketches::xor::XorFilterType;
+ ///
+ /// let filter = XorFilterBuilder::new(XorFilterType::Xor8)
+ /// .seed(42)
+ /// .build(["apple", "banana"])?;
+ /// assert!(filter.contains("apple"));
+ /// # Ok::<(), datasketches::error::Error>(())
+ /// ```
+ pub fn build<T: Hash>(self, items: impl IntoIterator<Item = T>) ->
Result<XorFilter, Error> {
+ self.build_from_hashes(items.into_iter().map(|item| hash_item(&item)))
+ }
+
+ /// Builds a filter from precomputed 64-bit hashes, removing duplicates.
+ ///
+ /// This method bypasses xxHash64. Query the resulting filter with
+ /// [`XorFilter::contains_hash`] using hashes from the same source.
Temporary input storage is
+ /// released on success or failure. Pass `hashes.iter().copied()` to
retain the original input
+ /// for a later build, including after an error.
+ ///
+ /// # Errors
+ ///
+ /// Returns [`InvalidArgument`](crate::error::ErrorKind::InvalidArgument)
if the fingerprint
+ /// slot count exceeds `u32::MAX` or a scratch allocation would exceed
`isize::MAX` bytes,
+ /// or if no peelable construction is found within 100 attempts. Valid
input can also
+ /// exhaust the construction attempts. A successful build may still exceed
the limits of
+ /// [`XorFilter::serialize`].
+ pub fn build_from_hashes(
+ self,
+ hashes: impl IntoIterator<Item = u64>,
+ ) -> Result<XorFilter, Error> {
+ let mut hashes: Vec<_> = hashes.into_iter().collect();
+ hashes.sort_unstable();
+ hashes.dedup();
+ self.build_from_distinct_hashes(&hashes)
+ }
+
+ /// Builds a filter from distinct precomputed hashes without copying or
sorting them.
+ ///
+ /// Borrows the input without modifying it, so the same slice can be
retried with another
+ /// construction seed after an error. Changing the seed does not guarantee
success.
+ /// Input order does not affect the result.
+ ///
+ /// # Errors
+ ///
+ /// Returns [`InvalidArgument`](crate::error::ErrorKind::InvalidArgument)
under the size limits
+ /// described by [`build_from_hashes`](Self::build_from_hashes), or if no
peelable
+ /// construction is found within 100 attempts, even for valid input.
Duplicate hashes
+ /// prevent peeling; a failed attempt usually exposes them and stops
construction early,
+ /// but detection is not guaranteed. Use
[`build_from_hashes`](Self::build_from_hashes) to
+ /// remove duplicates.
+ pub fn build_from_distinct_hashes(self, hashes: &[u64]) ->
Result<XorFilter, Error> {
+ self.build_with_attempts(hashes, MAX_CONSTRUCTION_ATTEMPTS)
+ }
+
+ // A private attempt bound makes exhaustion and recovery deterministic in
unit tests.
+ fn build_with_attempts(self, hashes: &[u64], max_attempts: usize) ->
Result<XorFilter, Error> {
+ XorFilter::build(hashes, self.filter_type, self.seed, max_attempts)
+ }
+}
+
+fn hash_item<T: Hash + ?Sized>(item: &T) -> u64 {
+ let mut hasher = XxHash64::with_seed(HASH_SEED);
+ item.hash(&mut hasher);
+ hasher.finish()
+}
+
+fn compute_capacity(num_items: usize) -> Result<usize, Error> {
+ if num_items > u32::MAX as usize {
+ return Err(Error::invalid_argument(format!(
+ "xor filter item count exceeds construction limit: {num_items}"
+ )));
+ }
+
+ let scaled = (LOAD_FACTOR * num_items as f64) as u64;
+ let capacity = CAPACITY_OFFSET + scaled;
+ let capacity = capacity / u64::from(NUM_HASHES) * u64::from(NUM_HASHES);
+ if capacity > u32::MAX as u64 || capacity > (isize::MAX as u64 /
size_of::<u64>() as u64) {
+ return Err(Error::invalid_argument(format!(
+ "xor filter capacity exceeds construction limit: {capacity}"
+ )));
+ }
+ Ok(capacity as usize)
+}
+
+fn map(
+ keys: &[u64],
+ seed: u64,
+ segment_length: usize,
+ xor_mask: &mut [u64],
+ count: &mut [u32],
+ queue: &mut [u32],
+ stack_hash: &mut [u64],
+ stack_index: &mut [u32],
+) -> usize {
+ // Separate queues keep each drain within one segment and make the two
neighbor
+ // segments statically known. Scratch space remains one slot per
fingerprint.
+ let mut masks = split_segments(xor_mask, segment_length);
+ let mut counts = split_segments(count, segment_length);
+ let mut queues = split_segments(queue, segment_length);
+ // Reuse the peel stack for mixed hashes while mapping one segment at a
time.
+ // This bounds the random-access working set without allocating another
buffer.
+ for (&key, hash) in keys.iter().zip(stack_hash.iter_mut()) {
+ *hash = mix(key, seed);
+ }
+ for block in 0..3 {
+ for &hash in stack_hash.iter() {
+ let index = reduce(hash.rotate_left(block as u32 * 21) as u32,
segment_length);
+ masks[block][index] ^= hash;
+ counts[block][index] += 1;
+ }
+ }
+ let mut queue_sizes = [0; 3];
+ for block in 0..3 {
+ for (index, &value) in counts[block].iter().enumerate() {
+ // Avoid a poorly predicted singleton branch. Before this write,
the number
+ // retained cannot exceed the current scan index, so the queue has
room.
+ queues[block][queue_sizes[block]] = index as u32;
+ queue_sizes[block] += usize::from(value == 1);
+ }
+ }
+ let mut stack_size = 0;
+ while queue_sizes != [0; 3] {
+ peel_block::<0>(
+ &mut masks,
+ &mut counts,
+ &mut queues,
+ &mut queue_sizes,
+ segment_length,
+ stack_hash,
+ stack_index,
+ &mut stack_size,
+ );
+ peel_block::<1>(
+ &mut masks,
+ &mut counts,
+ &mut queues,
+ &mut queue_sizes,
+ segment_length,
+ stack_hash,
+ stack_index,
+ &mut stack_size,
+ );
+ peel_block::<2>(
+ &mut masks,
+ &mut counts,
+ &mut queues,
+ &mut queue_sizes,
+ segment_length,
+ stack_hash,
+ stack_index,
+ &mut stack_size,
+ );
+ }
+ stack_size
+}
+
+fn split_segments<T>(values: &mut [T], segment_length: usize) -> [&mut [T]; 3]
{
+ let (first, rest) = values.split_at_mut(segment_length);
+ let (second, third) = rest.split_at_mut(segment_length);
+ [first, second, third]
+}
+
+#[inline]
+fn peel_block<const BLOCK: usize>(
+ masks: &mut [&mut [u64]; 3],
+ counts: &mut [&mut [u32]; 3],
+ queues: &mut [&mut [u32]; 3],
+ queue_sizes: &mut [usize; 3],
+ segment_length: usize,
+ stack_hash: &mut [u64],
+ stack_index: &mut [u32],
+ stack_size: &mut usize,
+) {
+ while queue_sizes[BLOCK] > 0 {
+ queue_sizes[BLOCK] -= 1;
+ let index = queues[BLOCK][queue_sizes[BLOCK]] as usize;
+ if counts[BLOCK][index] == 0 {
+ continue;
+ }
+ let hash = masks[BLOCK][index];
+ stack_hash[*stack_size] = hash;
+ stack_index[*stack_size] = (index + BLOCK * segment_length) as u32;
+ *stack_size += 1;
+ // The owned slot has no other live edge and is queued at most once.
Only
+ // the other two slots need updating; stale entries there are skipped
above.
+ for other in [(BLOCK + 1) % 3, (BLOCK + 2) % 3] {
+ let index = reduce(hash.rotate_left(other as u32 * 21) as u32,
segment_length);
+ masks[other][index] ^= hash;
+ counts[other][index] -= 1;
+ if counts[other][index] == 1 {
+ queues[other][queue_sizes[other]] = index as u32;
+ queue_sizes[other] += 1;
+ }
+ }
+ }
+}
+
+fn assign_fingerprints<T: Copy + BitXor<Output = T>>(
+ fingerprints: &mut [T],
+ segment_length: usize,
+ stack_hash: &[u64],
+ stack_index: &[u32],
+ fingerprint_of: impl Fn(u64) -> T,
+) {
+ for (&hash, &index) in stack_hash.iter().zip(stack_index).rev() {
+ let index = index as usize;
+ let [h0, h1, h2] = indexes(hash, segment_length);
+ fingerprints[index] =
+ fingerprint_of(hash) ^ fingerprints[h0] ^ fingerprints[h1] ^
fingerprints[h2];
+ }
+}
+
+#[inline]
+fn indexes(hash: u64, segment_length: usize) -> [usize; 3] {
+ [
+ reduce(hash as u32, segment_length),
+ reduce(hash.rotate_left(21) as u32, segment_length) + segment_length,
+ reduce(hash.rotate_left(42) as u32, segment_length) + 2 *
segment_length,
+ ]
+}
+
+#[inline]
+fn reduce(hash: u32, range: usize) -> usize {
+ ((u64::from(hash) * range as u64) >> 32) as usize
+}
+
+#[inline]
+fn fingerprint(hash: u64) -> u64 {
+ hash ^ (hash >> 32)
+}
+
+#[inline]
+fn mix(key: u64, seed: u64) -> u64 {
+ let mut hash = key.wrapping_add(seed);
+ hash ^= hash >> 33;
+ hash = hash.wrapping_mul(MURMUR_C1);
+ hash ^= hash >> 33;
+ hash = hash.wrapping_mul(MURMUR_C2);
+ hash ^ (hash >> 33)
+}
+
+fn splitmix64(state: u64) -> u64 {
+ let mut value = state;
+ value = (value ^ (value >> 30)).wrapping_mul(SPLITMIX_MUL1);
+ value = (value ^ (value >> 27)).wrapping_mul(SPLITMIX_MUL2);
+ value ^ (value >> 31)
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use crate::error::ErrorKind;
+
+ #[test]
+ fn oversized_input_is_rejected_before_allocating() {
+ for count in [usize::MAX, u32::MAX as usize] {
+ assert_eq!(
+ compute_capacity(count).unwrap_err().kind(),
+ ErrorKind::InvalidArgument
+ );
+ }
+ }
+
+ #[test]
+ fn borrowed_input_survives_exhaustion_and_can_retry() {
+ // This synthetic set fails its first peeling attempt with base seed 1.
+ // Limiting the private engine to one attempt exercises the public
build failure path
+ // without relying on a rare failure across all 100 production
attempts.
+ let keys: Vec<_> = (917_504..917_504 + 16_384u64)
+ .map(|i| splitmix64(i.wrapping_add(SPLITMIX_GAMMA)))
+ .collect();
+ for kind in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let original = keys.clone();
+ let error = XorFilterBuilder::new(kind)
+ .seed(1)
+ .build_with_attempts(&keys, 1)
+ .unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidArgument);
+ assert_eq!(keys, original);
+
+ let builder =
XorFilterBuilder::new(kind).seed(1_u64.wrapping_add(SPLITMIX_GAMMA));
+ let filter =
builder.clone().build_from_distinct_hashes(&keys).unwrap();
+ assert_eq!(filter.num_items(), Some(keys.len()));
+ for &key in &keys {
+ assert!(filter.contains_hash(key));
+ }
+ // A failed peel overwrites the mixed hashes in the scratch stack.
An automatic
+ // retry must remap the original input before attempting the next
seed.
+ assert_eq!(
+ XorFilterBuilder::new(kind)
+ .seed(1)
+ .build_from_distinct_hashes(&keys)
+ .unwrap(),
+ filter,
+ );
+ assert_eq!(
+ builder
+
.build_from_hashes(keys.iter().copied().chain(keys.iter().copied()))
+ .unwrap(),
+ filter,
+ );
+ }
+ }
+}
diff --git a/datasketches/src/xor/mod.rs b/datasketches/src/xor/mod.rs
new file mode 100644
index 0000000..796db5f
--- /dev/null
+++ b/datasketches/src/xor/mod.rs
@@ -0,0 +1,80 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! Xor filters for immutable probabilistic set membership.
+//!
+//! An xor filter is built from the complete input set and cannot be updated
afterward. Compared
+//! with a Bloom filter at the same false-positive probability, it generally
needs less space and
+//! performs exactly three fingerprint reads per query. Construction needs
temporary space linear
+//! in the number of distinct hashes.
+//!
+//! The [`XorFilterBuilder`] hashes ordinary Rust values with xxHash64. Call
+//! [`XorFilterBuilder::build_from_hashes`] or
[`XorFilterBuilder::build_from_distinct_hashes`]
+//! when hashes have already been computed and must not be hashed again.
+//!
+//! # Cross-language hashing
+//!
+//! Standard serialization supports 8-, 16-, and 32-bit fingerprints using
family `22`, version `1`.
+//! Interoperability requires the reader to support the encoded fingerprint
width. The 8- and
+//! 16-bit images match Java's format; 32-bit images extend the same layout
with little-endian
+//! `u32` slots and cannot be read by implementations limited to 8/16 bits.
+//! Construction may choose a different valid fingerprint array from another
implementation;
+//! byte-for-byte equality of independently constructed filters is not
guaranteed. Rust's
+//! [`Hash`](std::hash::Hash) implementations do not always encode values like
other languages. Use
+//! the strategies in [`crate::hash::value`] when the input hashes must match
another DataSketches
+//! implementation. A filter built through the precomputed-hash APIs remains
portable only when
+//! every reader uses the same external hash function.
+//!
+//! Java hashes integer scalars as 64-bit little-endian values and strings as
UTF-8 bytes with
+//! xxHash64 seed `0`. Use `u64`/`i64` and [`crate::hash::value::raw_bytes`]
accordingly. Java
+//! skips empty strings; callers must do so explicitly here. External hashes
(for example XXH3)
+//! must use the precomputed-hash APIs throughout; Java's typed query API will
not match them.
+//!
+//! # Application-defined storage
+//!
+//! [`XorFilter::into_parts`] and [`XorFilter::from_parts`] exchange
[`XorFilterParts`], which
+//! preserve the construction seed, segment length, and typed fingerprint
slots without adding
+//! metadata to an existing disk format. Imported parts may omit the item
count. Filters with a
+//! known zero item count always reject queries; imported parts with an
unknown count retain the
+//! ordinary fingerprint comparison, including possible false positives.
+//!
+//! # Examples
+//!
+//! ```
+//! use datasketches::xor::XorFilterBuilder;
+//! use datasketches::xor::XorFilterType;
+//!
+//! let filter = XorFilterBuilder::new(XorFilterType::Xor8)
+//! .build(["apple", "banana"])
+//! .unwrap();
+//!
+//! assert!(filter.contains(&"apple"));
+//! ```
+//!
+//! # References
+//!
+//! * Graf and Lemire, "Xor Filters: Faster and Smaller Than Bloom and Cuckoo
Filters," ACM Journal
+//! of Experimental Algorithmics 25 (2020).
+
+mod filter;
+mod serialization;
+
+pub use self::filter::XorFilter;
+pub use self::filter::XorFilterBuilder;
+pub use self::filter::XorFilterParts;
+pub use self::filter::XorFilterType;
+pub use self::filter::XorFingerprints;
diff --git a/datasketches/src/xor/serialization.rs
b/datasketches/src/xor/serialization.rs
new file mode 100644
index 0000000..6cb3e1c
--- /dev/null
+++ b/datasketches/src/xor/serialization.rs
@@ -0,0 +1,243 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::codec::SketchBytes;
+use crate::codec::SketchSlice;
+use crate::codec::assert::ensure_preamble_longs_in_range;
+use crate::codec::assert::ensure_serial_version_is;
+use crate::codec::assert::insufficient_data;
+use crate::codec::family::Family;
+use crate::error::Error;
+use crate::xor::filter::XorFilter;
+use crate::xor::filter::XorFilterType;
+use crate::xor::filter::XorFingerprints;
+
+const SERIAL_VERSION: u8 = 1;
+const NUM_HASHES: u8 = 3;
+const PREAMBLE_BYTES: usize = 3 * size_of::<u64>();
+
+impl XorFilter {
+ /// Serializes the filter using DataSketches family `22`, version `1`.
+ ///
+ /// Supports 8-, 16-, and 32-bit fingerprints, recorded in the header's
fingerprint width
+ /// field. Reserved fields are written as zero; integers and fingerprints
are little-endian.
+ /// The 8- and 16-bit images are compatible with Java when input hashing
agrees. Readers
+ /// must support the encoded fingerprint width; implementations limited to
8/16 bits cannot
+ /// read 32-bit images.
+ ///
+ /// # Errors
+ ///
+ /// Returns [`InvalidArgument`](crate::error::ErrorKind::InvalidArgument)
for an unknown
+ /// item count, or an item count or segment length above `i32::MAX`.
+ /// The total number of slots must also fit `i32::MAX` so that Java can
index all three
+ /// segments; this is an additional interoperability limit, not a header
field. Construction
+ /// and raw parts allow larger capacities, so successful construction does
not guarantee
+ /// standard serialization. Use raw parts for other storage formats.
+ pub fn serialize(&self) -> Result<Vec<u8>, Error> {
+ let size = self.serialized_size()?;
+ let num_items = self
+ .num_items
+ .expect("serialized_size checked the item count");
+ let mut bytes = SketchBytes::with_capacity(size);
+
+ bytes.write_u8(Family::XORFILTER.min_pre_longs);
+ bytes.write_u8(SERIAL_VERSION);
+ bytes.write_u8(Family::XORFILTER.id);
+ bytes.write_u8(0); // flags
+ bytes.write_u8(self.bits_per_fingerprint());
+ bytes.write_u8(NUM_HASHES);
+ bytes.write_u16_le(0); // unused
+ bytes.write_u64_le(self.seed);
+ bytes.write_i32_le(self.segment_length as i32);
+ bytes.write_i32_le(num_items as i32);
+
+ match &self.fingerprints {
+ XorFingerprints::Xor8(fingerprints) => bytes.write(fingerprints),
+ XorFingerprints::Xor16(fingerprints) => {
+ for &fingerprint in fingerprints.iter() {
+ bytes.write_u16_le(fingerprint);
+ }
+ }
+ XorFingerprints::Xor32(fingerprints) => {
+ for &fingerprint in fingerprints.iter() {
+ bytes.write_u32_le(fingerprint);
+ }
+ }
+ }
+
+ Ok(bytes.into_bytes())
+ }
+
+ /// Deserializes an owned filter from bytes.
+ ///
+ /// Accepts 8-, 16-, and 32-bit images within the limits of
[`serialize`](Self::serialize).
+ /// Reserved fields and trailing bytes are ignored.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error if the image is truncated, belongs to another sketch
family or version, or
+ /// contains metadata that could make a membership query index outside the
fingerprint payload.
+ pub fn deserialize(bytes: &[u8]) -> Result<Self, Error> {
+ let mut cursor = SketchSlice::new(bytes);
+
+ let preamble_longs = cursor
+ .read_u8()
+ .map_err(insufficient_data("preamble_longs"))?;
+ let serial_version = cursor
+ .read_u8()
+ .map_err(insufficient_data("serial_version"))?;
+ let family_id =
cursor.read_u8().map_err(insufficient_data("family_id"))?;
+ let _flags = cursor.read_u8().map_err(insufficient_data("flags"))?;
+ let bits_per_fingerprint = cursor
+ .read_u8()
+ .map_err(insufficient_data("bits_per_fingerprint"))?;
+ let num_hashes =
cursor.read_u8().map_err(insufficient_data("num_hashes"))?;
+ let _unused =
cursor.read_u16_le().map_err(insufficient_data("unused"))?;
+
+ Family::XORFILTER.validate_id(family_id)?;
+ ensure_serial_version_is(SERIAL_VERSION, serial_version)?;
+ ensure_preamble_longs_in_range(
+ Family::XORFILTER.min_pre_longs..=Family::XORFILTER.max_pre_longs,
+ preamble_longs,
+ )?;
+ let filter_type = match bits_per_fingerprint {
+ 8 => XorFilterType::Xor8,
+ 16 => XorFilterType::Xor16,
+ 32 => XorFilterType::Xor32,
+ _ => {
+ return Err(Error::deserial(
+ "standard xor format requires 8-, 16-, or 32-bit
fingerprints",
+ ));
+ }
+ };
+ if num_hashes != NUM_HASHES {
+ return Err(Error::deserial(format!(
+ "invalid number of hashes: expected {NUM_HASHES}, got
{num_hashes}"
+ )));
+ }
+
+ let seed = cursor.read_u64_le().map_err(insufficient_data("seed"))?;
+ let segment_length = cursor
+ .read_i32_le()
+ .map_err(insufficient_data("segment_length"))?;
+ if segment_length <= 0 {
+ return Err(Error::deserial(format!(
+ "invalid segment length: expected a positive value, got
{segment_length}"
+ )));
+ }
+ let segment_length = segment_length as usize;
+
+ let num_items = cursor
+ .read_i32_le()
+ .map_err(insufficient_data("num_items"))?;
+ if num_items < 0 {
+ return Err(Error::deserial(format!(
+ "invalid item count: expected a non-negative value, got
{num_items}"
+ )));
+ }
+ let num_items = num_items as usize;
+
+ let capacity = segment_length
+ .checked_mul(usize::from(NUM_HASHES))
+ .ok_or_else(|| Error::deserial("xor filter capacity overflow"))?;
+ if capacity > i32::MAX as usize {
+ return Err(Error::deserial(format!(
+ "invalid xor filter capacity: maximum is {}, got {capacity}",
+ i32::MAX
+ )));
+ }
+ if num_items > capacity {
+ return Err(Error::deserial(format!(
+ "invalid item count: capacity is {capacity}, got {num_items}"
+ )));
+ }
+
+ let fingerprint_bytes = capacity
+ .checked_mul(filter_type.bytes_per_fingerprint())
+ .ok_or_else(|| Error::deserial("xor filter fingerprint size
overflow"))?;
+ if cursor.remaining().len() < fingerprint_bytes {
+ return Err(Error::insufficient_data_of(
+ "fingerprints",
+ format!(
+ "expected {fingerprint_bytes} bytes, got {}",
+ cursor.remaining().len()
+ ),
+ ));
+ }
+
+ let fingerprints = match filter_type {
+ XorFilterType::Xor8 => {
+ let mut values = vec![0_u8; capacity].into_boxed_slice();
+ cursor
+ .read_exact(&mut values)
+ .map_err(insufficient_data("fingerprints"))?;
+ XorFingerprints::Xor8(values)
+ }
+ XorFilterType::Xor16 => {
+ let mut values = Vec::with_capacity(capacity);
+ for _ in 0..capacity {
+ values.push(
+ cursor
+ .read_u16_le()
+ .map_err(insufficient_data("fingerprints"))?,
+ );
+ }
+ XorFingerprints::Xor16(values.into_boxed_slice())
+ }
+ XorFilterType::Xor32 => {
+ let mut values = Vec::with_capacity(capacity);
+ for _ in 0..capacity {
+ values.push(
+ cursor
+ .read_u32_le()
+ .map_err(insufficient_data("fingerprints"))?,
+ );
+ }
+ XorFingerprints::Xor32(values.into_boxed_slice())
+ }
+ };
+
+ Ok(Self {
+ segment_length,
+ num_items: Some(num_items),
+ seed,
+ fingerprints,
+ })
+ }
+
+ /// Returns the standard serialized size in bytes.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error under the same conditions as
[`serialize`](Self::serialize).
+ pub fn serialized_size(&self) -> Result<usize, Error> {
+ let count = self
+ .num_items
+ .ok_or_else(|| Error::invalid_argument("standard xor format
requires an item count"))?;
+ if count > i32::MAX as usize
+ || self.segment_length > i32::MAX as usize
+ || self.capacity() > i32::MAX as usize
+ {
+ return Err(Error::invalid_argument(
+ "xor filter exceeds standard format limits",
+ ));
+ }
+ PREAMBLE_BYTES
+ .checked_add(self.fingerprints.byte_len())
+ .ok_or_else(|| Error::invalid_argument("xor filter serialized size
overflow"))
+ }
+}
diff --git a/tests-integration/Cargo.toml b/tests-integration/Cargo.toml
index 79021d6..78d9eec 100644
--- a/tests-integration/Cargo.toml
+++ b/tests-integration/Cargo.toml
@@ -23,6 +23,7 @@ edition.workspace = true
rust-version.workspace = true
[dev-dependencies]
+xorf = { version = "=0.13.0", default-features = false }
datasketches = { workspace = true, features = [
"bloom",
"countmin",
@@ -34,6 +35,7 @@ datasketches = { workspace = true, features = [
"tdigest",
"theta",
"tuple",
+ "xor",
] }
googletest = { workspace = true }
insta = { workspace = true }
diff --git a/tests-integration/tests/serde_tests.rs
b/tests-integration/tests/serde_tests.rs
index bd72316..bfa66cf 100644
--- a/tests-integration/tests/serde_tests.rs
+++ b/tests-integration/tests/serde_tests.rs
@@ -71,3 +71,6 @@ mod theta;
#[path = "serde_tests/tuple.rs"]
mod tuple;
+
+#[path = "serde_tests/xor.rs"]
+mod xor;
diff --git a/tests-integration/tests/serde_tests/xor.rs
b/tests-integration/tests/serde_tests/xor.rs
new file mode 100644
index 0000000..e91fdde
--- /dev/null
+++ b/tests-integration/tests/serde_tests/xor.rs
@@ -0,0 +1,341 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use datasketches::error::ErrorKind;
+use datasketches::xor::XorFilter;
+use datasketches::xor::XorFilterBuilder;
+use datasketches::xor::XorFilterParts;
+use datasketches::xor::XorFilterType;
+use datasketches::xor::XorFingerprints;
+
+// Generated from datasketches-java commit
1034fb33b6e013334ff870f130b9c388cae5dfa9.
+// XorFilterBuilder.create([1, 2, 3, Long.MIN_VALUE], bits, 42).toByteArray().
+const JAVA_XOR8_IMAGE: &str = concat!(
+ "0301160008030000956eeb2f2632d7bd0c00000004000000",
+ "00000000000000000000c500000000000000000000000000dd000000040000000b000000"
+);
+const JAVA_XOR16_IMAGE: &str = concat!(
+ "0301160010030000",
+ "956eeb2f2632d7bd",
+ "0c00000004000000",
+ "0000000000000000",
+ "0000000000000000",
+ "00000000c5b60000",
+ "0000000000000000",
+ "0000000000000000",
+ "0000000000000000",
+ "dd6e000000000000",
+ "04e8000000000000",
+ "0b23000000000000",
+);
+
+#[test]
+fn java_images_round_trip_byte_for_byte() {
+ let values = [1_u64, 2, 3, 1_u64 << 63];
+
+ for (filter_type, image) in [
+ (XorFilterType::Xor8, JAVA_XOR8_IMAGE),
+ (XorFilterType::Xor16, JAVA_XOR16_IMAGE),
+ ] {
+ let expected = decode_hex(image);
+ let built = XorFilterBuilder::new(filter_type)
+ .seed(42)
+ .build(values)
+ .unwrap();
+
+ let restored = XorFilter::deserialize(&expected).unwrap();
+ assert_eq!(restored.serialize().unwrap(), expected);
+ // Peelability does not depend on peeling order, so both builders
select the same
+ // construction seed and layout. Fingerprint slots may still differ by
peeling order.
+ assert_eq!(
+ built.serialize().unwrap()[..24],
+ expected[..24],
+ "{filter_type:?} header differs from Java"
+ );
+ assert_eq!(restored.filter_type(), filter_type);
+ assert_eq!(restored.num_items(), Some(values.len()));
+ for value in values {
+ assert!(built.contains(&value));
+ assert!(
+ restored.contains(&value),
+ "{filter_type:?} image did not contain {value}"
+ );
+ }
+ }
+}
+
+#[test]
+fn serialization_round_trips_standard_fingerprint_types() {
+ for filter_type in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ for count in [0, 1, 10_000_u64] {
+ let original = XorFilterBuilder::new(filter_type)
+ .build_from_hashes(0..count)
+ .unwrap();
+ let bytes = original.serialize().unwrap();
+ assert_eq!(bytes.len(), original.serialized_size().unwrap());
+
+ let restored = XorFilter::deserialize(&bytes).unwrap();
+ assert_eq!(restored, original);
+ for hash in 0..count {
+ assert!(restored.contains_hash(hash));
+ }
+ if count == 0 {
+
assert!(!restored.contains_hash(restored.seed().wrapping_neg()));
+ }
+ }
+ }
+}
+
+#[test]
+fn every_truncated_image_is_rejected() {
+ for filter_type in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let bytes = XorFilterBuilder::new(filter_type)
+ .build_from_hashes(0..100_u64)
+ .unwrap()
+ .serialize()
+ .unwrap();
+ for end in 0..bytes.len() {
+ let error = XorFilter::deserialize(&bytes[..end]).unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidData, "length {end}");
+ }
+ assert!(XorFilter::deserialize(&bytes).is_ok());
+ }
+}
+
+#[test]
+fn invalid_preamble_fields_are_rejected() {
+ let valid = XorFilterBuilder::new(XorFilterType::Xor8)
+ .build_from_hashes(0..100_u64)
+ .unwrap()
+ .serialize()
+ .unwrap();
+
+ for (offset, value) in [
+ (0, 2),
+ (0, 4),
+ (1, 2),
+ (2, 21),
+ (4, 7),
+ (4, 24),
+ (4, 64),
+ (5, 4),
+ ] {
+ let mut corrupted = valid.clone();
+ corrupted[offset] = value;
+ let error = XorFilter::deserialize(&corrupted).unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidData, "offset {offset}");
+ }
+}
+
+#[test]
+fn unsafe_lengths_are_rejected_before_indexing() {
+ let valid = XorFilterBuilder::new(XorFilterType::Xor8)
+ .build_from_hashes(0..100_u64)
+ .unwrap()
+ .serialize()
+ .unwrap();
+
+ for segment_length in [0_i32, -1, i32::MAX] {
+ let mut corrupted = valid.clone();
+ corrupted[16..20].copy_from_slice(&segment_length.to_le_bytes());
+ assert_eq!(
+ XorFilter::deserialize(&corrupted).unwrap_err().kind(),
+ ErrorKind::InvalidData
+ );
+ }
+
+ for num_items in [-1_i32, i32::MAX] {
+ let mut corrupted = valid.clone();
+ corrupted[20..24].copy_from_slice(&num_items.to_le_bytes());
+ assert_eq!(
+ XorFilter::deserialize(&corrupted).unwrap_err().kind(),
+ ErrorKind::InvalidData
+ );
+ }
+}
+
+#[test]
+fn trailing_storage_is_ignored() {
+ for kind in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let original = XorFilterBuilder::new(kind)
+ .build_from_hashes(0..100_u64)
+ .unwrap();
+ let mut bytes = original.serialize().unwrap();
+ bytes.extend_from_slice(&[0xaa; 16]);
+
+ assert_eq!(XorFilter::deserialize(&bytes).unwrap(), original);
+ }
+}
+
+fn decode_hex(input: &str) -> Vec<u8> {
+ assert_eq!(input.len() % 2, 0);
+ input
+ .as_bytes()
+ .chunks_exact(2)
+ .map(|digits| {
+ let digits = std::str::from_utf8(digits).unwrap();
+ u8::from_str_radix(digits, 16).unwrap()
+ })
+ .collect()
+}
+
+#[test]
+fn java_utf8_and_raw_byte_inputs_match() {
+ use datasketches::hash::value::raw_bytes;
+ // The same merged Java implementation, using update(String) and
update(byte[]).
+ let images = [
+ (
+ XorFilterType::Xor8,
+
"0301160008030000956eeb2f2632d7bd0c0000000400000000000000000000000000000000df00000000000000000000cc0000003000000091000000",
+ ),
+ (
+ XorFilterType::Xor16,
+
"0301160010030000956eeb2f2632d7bd0c000000040000000000000000000000000000000000000000000000000000000000df500000000000000000000000000000000000000000ccb5000000000000301200000000000091b8000000000000",
+ ),
+ ];
+ for (kind, image) in images {
+ let built = XorFilterBuilder::new(kind)
+ .seed(42)
+ .build([
+ raw_bytes::from_slice(b"hello"),
+ raw_bytes::from_slice("数据🔎".as_bytes()),
+ raw_bytes::from_slice(&[]),
+ raw_bytes::from_slice(&[0, 1, 255]),
+ ])
+ .unwrap();
+ let expected = decode_hex(image);
+ let restored = XorFilter::deserialize(&expected).unwrap();
+ assert_eq!(restored.serialize().unwrap(), expected);
+ // Peelability does not depend on peeling order, so both builders
select the same
+ // construction seed and layout. Fingerprint slots may still differ by
peeling order.
+ assert_eq!(
+ built.serialize().unwrap()[..24],
+ expected[..24],
+ "{kind:?} header differs from Java"
+ );
+ for bytes in [b"hello".as_slice(), "数据🔎".as_bytes(), &[], &[0, 1,
255]] {
+ assert!(built.contains(&raw_bytes::from_slice(bytes)));
+ assert!(restored.contains(&raw_bytes::from_slice(bytes)));
+ }
+ }
+}
+
+#[test]
+fn xor32_image_preserves_full_width_little_endian_slots() {
+ // Hand-authored layout fixture, independent of the construction algorithm:
+ // family 22/version 1, width 32, three one-slot segments, one item.
+ let bytes = decode_hex(concat!(
+ "0301160020030000",
+ "efcdab8967452301",
+ "0100000001000000",
+ "67452301efcdab89ffffffff",
+ ));
+ let filter = XorFilter::from_parts(
+ XorFilterParts::new(
+ 0x0123_4567_89ab_cdef,
+ 1,
+ XorFingerprints::Xor32(vec![0x0123_4567, 0x89ab_cdef,
u32::MAX].into_boxed_slice()),
+ )
+ .with_num_items(1),
+ )
+ .unwrap();
+ assert_eq!(filter.serialized_size().unwrap(), bytes.len());
+ assert_eq!(filter.serialize().unwrap(), bytes);
+ assert_eq!(XorFilter::deserialize(&bytes).unwrap(), filter);
+}
+
+#[test]
+fn raw_parts_preserve_an_application_storage_layout() {
+ use datasketches::codec::SketchSlice;
+ // Synthetic storage fixtures with public xorf 0.13.0 payloads for [0, 1,
2, u64::MAX].
+ // This test-only envelope omits cardinality: magic, width:u8,
segment:u32, seed:u64,
+ // and little-endian slots. It is not a production storage format.
+ let images = [
+ concat!(
+
"54455354080c000000c15c0289ec2d0a91ad000000000000000000ca000000000000000000dc00300000000000000000",
+ "0000000000",
+ ),
+ concat!(
+
"54455354100c000000c15c0289ec2d0a91aded000000000000000000000000000000000000ca18000000000000000000",
+
"000000000000000000dcb9000030fc0000000000000000000000000000000000000000000000000000",
+ ),
+ concat!(
+
"54455354200c000000c15c0289ec2d0a91adedfc84000000000000000000000000000000000000000000000000000000",
+
"000000000000000000ca187b8e0000000000000000000000000000000000000000000000000000000000000000000000",
+
"00dcb969ee0000000030fcf3490000000000000000000000000000000000000000000000000000000000000000000000",
+ "0000000000000000000000000000000000",
+ ),
+ ];
+ for image in images {
+ let bytes = decode_hex(image);
+ let mut cursor = SketchSlice::new(&bytes);
+ assert_eq!(&bytes[..4], b"TEST");
+ let mut magic = [0; 4];
+ cursor.read_exact(&mut magic).unwrap();
+ let width = cursor.read_u8().unwrap();
+ let segment = cursor.read_u32_le().unwrap() as usize;
+ let seed = cursor.read_u64_le().unwrap();
+ let slots = cursor.remaining().len() / usize::from(width / 8);
+ let payload = match width {
+ 8 => XorFingerprints::Xor8(cursor.remaining().into()),
+ 16 => {
+ XorFingerprints::Xor16((0..slots).map(|_|
cursor.read_u16_le().unwrap()).collect())
+ }
+ 32 => {
+ XorFingerprints::Xor32((0..slots).map(|_|
cursor.read_u32_le().unwrap()).collect())
+ }
+ _ => unreachable!(),
+ };
+ let filter = XorFilter::from_parts(XorFilterParts::new(seed, segment,
payload)).unwrap();
+ for hash in [0, 1, 2, u64::MAX] {
+ assert!(filter.contains_hash(hash));
+ }
+ assert_eq!(filter.capacity(), slots);
+ assert_eq!(filter.num_items(), None);
+
+ let parts = filter.into_parts();
+ assert_eq!(parts.num_items(), None);
+ let (seed, segment) = (parts.seed(), parts.segment_length());
+ let payload = parts.into_fingerprints();
+ let mut encoded = b"TEST".to_vec();
+ encoded.push(width);
+ encoded.extend((segment as u32).to_le_bytes());
+ encoded.extend(seed.to_le_bytes());
+ match payload {
+ XorFingerprints::Xor8(values) =>
encoded.extend_from_slice(&values),
+ XorFingerprints::Xor16(values) => {
+ encoded.extend(values.iter().flat_map(|v| v.to_le_bytes()))
+ }
+ XorFingerprints::Xor32(values) => {
+ encoded.extend(values.iter().flat_map(|v| v.to_le_bytes()))
+ }
+ }
+ assert_eq!(encoded, bytes);
+ }
+}
diff --git a/tests-integration/tests/xor_test/filter.rs
b/tests-integration/tests/xor_test/filter.rs
new file mode 100644
index 0000000..bda1197
--- /dev/null
+++ b/tests-integration/tests/xor_test/filter.rs
@@ -0,0 +1,162 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use datasketches::xor::XorFilterBuilder;
+use datasketches::xor::XorFilterType;
+
+#[test]
+fn values_have_no_false_negatives() {
+ let filter = XorFilterBuilder::new(XorFilterType::Xor8)
+ .seed(8123)
+ .build(0..10_000_u64)
+ .unwrap();
+
+ for value in 0..10_000_u64 {
+ assert!(filter.contains(&value), "false negative for {value}");
+ }
+}
+
+#[test]
+fn precomputed_hashes_have_no_false_negatives() {
+ let hashes = (0..10_000_u64)
+ .map(|value| value.wrapping_mul(0x9e37_79b9_7f4a_7c15))
+ .collect::<Vec<_>>();
+
+ for filter_type in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let filter = XorFilterBuilder::new(filter_type)
+ .build_from_hashes(hashes.iter().copied())
+ .unwrap();
+ for &hash in &hashes {
+ assert!(filter.contains_hash(hash), "false negative for {hash}");
+ }
+ }
+}
+
+#[test]
+fn borrowed_values_can_be_reused() {
+ let values = vec!["datasketches".to_string(), "xor filter".to_string()];
+ let builder = XorFilterBuilder::new(XorFilterType::Xor16).seed(42);
+ let first = builder.clone().build(&values).unwrap();
+ let second = builder.build(&values).unwrap();
+ assert_eq!(first, second);
+ for value in &values {
+ assert!(first.contains(value));
+ }
+}
+
+#[test]
+fn duplicates_are_removed_before_construction() {
+ let filter = XorFilterBuilder::new(XorFilterType::Xor8)
+ .build_from_hashes([7, 7, 11, 11, 11])
+ .unwrap();
+ assert_eq!(filter.num_items(), Some(2));
+ assert!(filter.contains_hash(7));
+ assert!(filter.contains_hash(11));
+}
+
+#[test]
+fn construction_is_independent_of_input_order() {
+ let ascending = XorFilterBuilder::new(XorFilterType::Xor8).seed(424_242);
+ let descending = ascending.clone();
+
+ assert_eq!(
+ ascending
+ .build_from_hashes(0..50_000_u64)
+ .unwrap()
+ .serialize()
+ .unwrap(),
+ descending
+ .build_from_hashes((0..50_000_u64).rev())
+ .unwrap()
+ .serialize()
+ .unwrap()
+ );
+}
+
+#[test]
+fn metadata_describes_the_compact_payload() {
+ let filter = XorFilterBuilder::new(XorFilterType::Xor8)
+ .build_from_hashes(0..10_000_u64)
+ .unwrap();
+
+ assert_eq!(filter.is_empty(), Some(false));
+ assert_eq!(filter.num_items(), Some(10_000));
+ assert_eq!(filter.filter_type(), XorFilterType::Xor8);
+ assert_eq!(filter.bits_per_fingerprint(), 8);
+ assert_eq!(filter.num_hashes(), 3);
+ assert_eq!(filter.capacity() % 3, 0);
+ assert!((9.5..10.5).contains(&filter.bits_per_item().unwrap()));
+ assert!(filter.estimated_size() >= filter.capacity());
+ assert_eq!(filter.serialized_size().unwrap(), 24 + filter.capacity());
+}
+
+#[test]
+fn empty_filter_is_well_formed() {
+ let filter = XorFilterBuilder::new(XorFilterType::Xor16)
+ .build_from_hashes([])
+ .unwrap();
+
+ assert_eq!(filter.is_empty(), Some(true));
+ assert_eq!(filter.num_items(), Some(0));
+ assert_eq!(filter.capacity(), 30);
+ assert_eq!(filter.bits_per_item().unwrap(), 0.0);
+ assert_eq!(filter.serialized_size().unwrap(), 24 + 60);
+}
+
+#[test]
+fn false_positive_rates_follow_fingerprint_width() {
+ const NUM_ITEMS: u64 = 50_000;
+ const NUM_QUERIES: u64 = 100_000;
+
+ let xor8 = XorFilterBuilder::new(XorFilterType::Xor8)
+ .build_from_hashes(0..NUM_ITEMS)
+ .unwrap();
+ let xor16 = XorFilterBuilder::new(XorFilterType::Xor16)
+ .build_from_hashes(0..NUM_ITEMS)
+ .unwrap();
+ let xor32 = XorFilterBuilder::new(XorFilterType::Xor32)
+ .build_from_hashes(0..NUM_ITEMS)
+ .unwrap();
+
+ let false_positives8 = (NUM_ITEMS..NUM_ITEMS + NUM_QUERIES)
+ .filter(|&hash| xor8.contains_hash(hash))
+ .count();
+ let false_positives16 = (NUM_ITEMS..NUM_ITEMS + NUM_QUERIES)
+ .filter(|&hash| xor16.contains_hash(hash))
+ .count();
+ let false_positives32 = (NUM_ITEMS..NUM_ITEMS + NUM_QUERIES)
+ .filter(|&hash| xor32.contains_hash(hash))
+ .count();
+
+ assert!(
+ false_positives8 < 1_000,
+ "8-bit false-positive count was {false_positives8}"
+ );
+ assert!(
+ false_positives16 < 100,
+ "16-bit false-positive count was {false_positives16}"
+ );
+ assert!(
+ false_positives32 < 10,
+ "32-bit false-positive count was {false_positives32}"
+ );
+ assert!(false_positives16 < false_positives8);
+}
diff --git a/benchmarks/main.rs b/tests-integration/tests/xor_test/main.rs
similarity index 75%
copy from benchmarks/main.rs
copy to tests-integration/tests/xor_test/main.rs
index ee28803..656a505 100644
--- a/benchmarks/main.rs
+++ b/tests-integration/tests/xor_test/main.rs
@@ -15,23 +15,6 @@
// specific language governing permissions and limitations
// under the License.
-use divan::AllocProfiler;
+mod filter;
-#[global_allocator]
-static ALLOC: AllocProfiler = AllocProfiler::system();
-
-mod bloom;
-mod countmin;
-mod cpc;
-mod frequencies;
-mod hash_inputs;
-mod hll;
-mod kll;
-mod req;
-mod tdigest;
-mod theta;
-mod tuple;
-
-fn main() {
- divan::main();
-}
+mod parts;
diff --git a/tests-integration/tests/xor_test/parts.rs
b/tests-integration/tests/xor_test/parts.rs
new file mode 100644
index 0000000..61bf186
--- /dev/null
+++ b/tests-integration/tests/xor_test/parts.rs
@@ -0,0 +1,244 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use datasketches::error::ErrorKind;
+use datasketches::xor::XorFilter;
+use datasketches::xor::XorFilterBuilder;
+use datasketches::xor::XorFilterParts;
+use datasketches::xor::XorFilterType;
+use datasketches::xor::XorFingerprints;
+use xorf::Filter;
+
+#[test]
+fn raw_parts_interoperate_with_xorf_in_both_directions() {
+ let keys: Vec<_> = (0..16_384u64)
+ .map(|n| n.wrapping_mul(0x9e3779b97f4a7c15))
+ .collect();
+ for kind in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let (seed, segment, payload) = match kind {
+ XorFilterType::Xor8 => {
+ let f = xorf::Xor8::from(&keys);
+ (
+ f.seed,
+ f.block_length,
+ XorFingerprints::Xor8(f.fingerprints),
+ )
+ }
+ XorFilterType::Xor16 => {
+ let f = xorf::Xor16::from(&keys);
+ (
+ f.seed,
+ f.block_length,
+ XorFingerprints::Xor16(f.fingerprints),
+ )
+ }
+ XorFilterType::Xor32 => {
+ let f = xorf::Xor32::from(&keys);
+ (
+ f.seed,
+ f.block_length,
+ XorFingerprints::Xor32(f.fingerprints),
+ )
+ }
+ };
+ let imported = XorFilter::from_parts(XorFilterParts::new(seed,
segment, payload)).unwrap();
+ assert_eq!(imported.num_items(), None);
+ assert_eq!(imported.bits_per_item(), None);
+ assert_eq!(imported.is_empty(), None);
+ assert_eq!(
+ imported.serialize().unwrap_err().kind(),
+ ErrorKind::InvalidArgument
+ );
+ for &key in &keys {
+ assert!(imported.contains_hash(key));
+ }
+
+ let built = XorFilterBuilder::new(kind)
+ .build_from_distinct_hashes(&keys)
+ .unwrap();
+ let parts = built.clone().into_parts();
+ assert_eq!(parts.num_items(), Some(keys.len()));
+ let (seed, block_length) = (parts.seed(), parts.segment_length());
+ let payload = parts.into_fingerprints();
+ // Compare all answers, including false positives, after transferring
ownership.
+ let reference: Box<dyn Filter<u64>> = match payload {
+ XorFingerprints::Xor8(fingerprints) => Box::new(xorf::Xor8 {
+ seed,
+ block_length,
+ fingerprints,
+ }),
+ XorFingerprints::Xor16(fingerprints) => Box::new(xorf::Xor16 {
+ seed,
+ block_length,
+ fingerprints,
+ }),
+ XorFingerprints::Xor32(fingerprints) => Box::new(xorf::Xor32 {
+ seed,
+ block_length,
+ fingerprints,
+ }),
+ };
+ for key in keys.iter().copied().chain(0..100_000) {
+ assert_eq!(built.contains_hash(key), reference.contains(&key));
+ }
+ }
+}
+
+#[test]
+fn raw_parts_reject_invalid_layouts_and_counts() {
+ for (segment, length, count) in [
+ (0, 0, None),
+ (1, 2, None),
+ (1, 4, None),
+ (usize::MAX, 3, None),
+ (1, 3, Some(4)),
+ ] {
+ let mut parts =
+ XorFilterParts::new(0, segment, XorFingerprints::Xor8(vec![0;
length].into()));
+ if let Some(count) = count {
+ parts = parts.with_num_items(count);
+ }
+ assert_eq!(
+ XorFilter::from_parts(parts).unwrap_err().kind(),
+ ErrorKind::InvalidArgument
+ );
+ }
+}
+
+#[test]
+fn distinct_construction_is_bounded_and_does_not_deduplicate() {
+ for kind in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let error = XorFilterBuilder::new(kind)
+ .build_from_distinct_hashes(&[1, 2, 1])
+ .unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidArgument);
+ assert!(error.message().contains("duplicate hashes"));
+ for keys in [vec![], vec![0], vec![u64::MAX], vec![0, u64::MAX]] {
+ let f = XorFilterBuilder::new(kind)
+ .build_from_distinct_hashes(&keys)
+ .unwrap();
+ assert_eq!(f.num_items(), Some(keys.len()));
+ for key in keys {
+ assert!(f.contains_hash(key));
+ }
+ }
+ }
+}
+
+#[test]
+fn empty_filters_never_match_even_when_the_fingerprint_is_zero() {
+ for kind in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let f = XorFilterBuilder::new(kind).build_from_hashes([]).unwrap();
+ // This key mixes to zero under the filter's construction seed.
+ assert!(!f.contains_hash(f.seed().wrapping_neg()));
+ }
+}
+
+#[test]
+fn construction_recovers_after_an_unpeelable_first_attempt() {
+ // This distinct set needs two attempts with base seed 1. All fingerprint
widths
+ // share the peeling graph, so each must reset the failed attempt's
accumulators.
+ let keys: Vec<_> = (917_504..917_504 + 16_384u64)
+ .map(|i| {
+ let mut z = i.wrapping_add(0x9e3779b97f4a7c15);
+ z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
+ z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
+ z ^ (z >> 31)
+ })
+ .collect();
+ let first_seed = XorFilterBuilder::new(XorFilterType::Xor8)
+ .seed(1)
+ .build_from_distinct_hashes(&[])
+ .unwrap()
+ .seed();
+ let reference = xorf::Xor8::from(&keys);
+ assert_ne!(reference.seed, first_seed);
+ for kind in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let filter = XorFilterBuilder::new(kind)
+ .seed(1)
+ .build_from_distinct_hashes(&keys)
+ .unwrap();
+ assert_eq!(filter.seed(), reference.seed);
+ for &key in &keys {
+ assert!(filter.contains_hash(key));
+ }
+ let mut reversed = keys.clone();
+ reversed.reverse();
+ assert_eq!(
+ filter,
+ XorFilterBuilder::new(kind)
+ .seed(1)
+ .build_from_distinct_hashes(&reversed)
+ .unwrap()
+ );
+ }
+}
+
+#[test]
+fn unknown_count_does_not_infer_emptiness_from_zero_fingerprints() {
+ for kind in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let empty = XorFilterBuilder::new(kind).build_from_hashes([]).unwrap();
+ let zero_hash = empty.seed().wrapping_neg();
+ assert_eq!(empty.is_empty(), Some(true));
+ assert!(!empty.contains_hash(zero_hash));
+ let parts = empty.into_parts();
+ let unknown = XorFilter::from_parts(XorFilterParts::new(
+ parts.seed(),
+ parts.segment_length(),
+ parts.into_fingerprints(),
+ ))
+ .unwrap();
+ assert_eq!(unknown.is_empty(), None);
+ assert_eq!(unknown.num_items(), None);
+ assert_eq!(unknown.bits_per_item(), None);
+ // An omitted count must preserve the raw fingerprint comparison, even
for all-zero slots.
+ assert!(unknown.contains_hash(zero_hash));
+ assert_eq!(
+ unknown.serialized_size().unwrap_err().kind(),
+ ErrorKind::InvalidArgument
+ );
+ assert_eq!(
+ unknown.serialize().unwrap_err().kind(),
+ ErrorKind::InvalidArgument
+ );
+ let parts = unknown.into_parts();
+ assert_eq!(parts.num_items(), None);
+ let restored = XorFilter::from_parts(parts).unwrap();
+ assert_eq!(restored.is_empty(), None);
+ assert!(restored.contains_hash(zero_hash));
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]