🥮 mooncakes.io

    xor16filter

    Xor16 filter: 16-bit binary fuse filter with paper-accuracy fingerprints.

    Download zip
    Version
    0.1.2
    License
    Apache-2.0
    Repository
    Last updated
    1 hour ago
    Downloads
    20

    No dependencies

    #xor16filter

    Xor16 binary fuse filter with 16-bit fingerprints.

    moon test

    #Provenance & License

    • 出处：Xor16 Filter: arXiv:1912.08258 — 详见 EXTRACTION.md
    • 独立实现声明与判据来源详见同目录 EXTRACTION.md；许可证随仓库根 LICENSE（MIT）。

    Xor16

    source
    pub(all) struct Xor16 {
      seed : UInt64
      block_length : Int
      fingerprints : FixedArray[UInt64]
    }

    Xor16 filter (arXiv:1912.08258). Fingerprints are 16-bit values stored (unpacked) as UInt64 slots. Faithful to FastFilter/xor_singleheader xorfilter.h semantics; see BLUEPRINT.md for documented deviations.

    Xor16::contains

    source
    fn Xor16::contains(self : Xor16, key : UInt64) -> Bool

    Membership query: always true for keys used at build time; false-positive rate ~0.3905 / 2^16 for other keys.

    build

    source
    fn build(keys : Array[UInt64]) -> Result[Xor16, String]

    Build an xor16 filter from distinct 64-bit keys. Retries with fresh splitmix64 seeds up to 100 times; fails if the hypergraph is not peelable (typically caused by duplicate keys).

    low32

    source
    fn low32(h : UInt64) -> UInt64

    Low 32 bits as a stand-in for (uint32_t) truncation.

    murmur64

    source
    fn murmur64(h : UInt64) -> UInt64

    Murmur3 finalizer: scrambles a 64-bit value. Reference: xorfilter.h xor_murmur64.

    reduce

    source
    fn reduce(hash : UInt64, n : Int) -> Int

    Fast modulo reduction: (hash * n) >> 32, result in 0..<n. hash must already be a 32-bit value (see low32). Reference: xor_reduce.

    rotl64

    source
    fn rotl64(n : UInt64, c : Int) -> UInt64

    Rotate-left for 64-bit values. c must be in 1..=63.

    splitmix64_next

    source
    fn splitmix64_next(seed : 
    Ref    [UInt64]) -> UInt64

    splitmix64 PRNG step, state kept in a Ref. Used for seeds and test data.

    Source Files