github-advanced-security[bot] commented on code in PR #740: URL: https://github.com/apache/datasketches-java/pull/740#discussion_r3569667033
########## src/main/java/org/apache/datasketches/filters/xorfilter/XorFilter.java: ########## @@ -0,0 +1,653 @@ +/* + * 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. + */ + +package org.apache.datasketches.filters.xorfilter; + +import static java.lang.foreign.ValueLayout.JAVA_BYTE; +import static java.lang.foreign.ValueLayout.JAVA_SHORT_UNALIGNED; +import static org.apache.datasketches.common.Util.LS; + +import java.lang.foreign.MemorySegment; +import java.nio.charset.StandardCharsets; +import java.util.Arrays; + +import org.apache.datasketches.common.Family; +import org.apache.datasketches.common.MemorySegmentStatus; +import org.apache.datasketches.common.SketchesArgumentException; +import org.apache.datasketches.common.SketchesStateException; +import org.apache.datasketches.common.positional.PositionalSegment; +import org.apache.datasketches.hash.XxHash; +import org.apache.datasketches.hash.XxHash64; + +/** + * A xor filter is an immutable data structure that can be used for probabilistic + * set membership, much like a Bloom filter but smaller and faster. + * + * <p>When querying a xor filter, there are no false negatives. Specifically: + * When querying an item that was presented to the filter when it was built, the filter will + * always indicate that the item is present. There is a chance of false positives, where + * querying an item that was never presented to the filter will indicate that the + * item has been seen. Consequently, any query should be interpreted as + * "might have seen."</p> + * + * <p>Unlike a Bloom filter, a xor filter is built once from the full set of items and cannot + * be updated afterwards. The filter stores a small fingerprint per item in an array whose + * size is about 1.23 times the number of distinct items, giving a false positive probability + * of approximately 1 / 2^bits, where bits is the configured fingerprint width (8 or 16). This + * is close to the information-theoretic lower bound and uses less memory than a Bloom filter + * for the same false positive probability.</p> + * + * <p>See the XorFilterBuilder class for methods to accumulate items and build a filter.</p> + * + * <p>This implementation uses xxHash64 to reduce items to 64-bit keys and follows the approach in + * Graf and Lemire, "Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters," + * ACM Journal of Experimental Algorithmics, 2020.</p> + */ +public final class XorFilter implements MemorySegmentStatus { + private static final int SER_VER = 1; + private static final int PREAMBLE_LONGS = 3; + private static final long PREAMBLE_SIZE_BYTES = (long) PREAMBLE_LONGS * Long.BYTES; + + // number of hash functions / segments used by the three-partite construction + static final int NUM_HASHES = 3; + // fixed seed used to reduce items to 64-bit keys, distinct from the construction seed + static final long HASH_SEED = 0L; + + private static final double LOAD_FACTOR = 1.23; + private static final int CAPACITY_OFFSET = 32; + private static final int MAX_ITERATIONS = 100; + + // MurmurHash3 64-bit finalizer constants (also used by the paper's Algorithm 5) + private static final long MURMUR_C1 = 0xff51afd7ed558ccdL; + private static final long MURMUR_C2 = 0xc4ceb9fe1a85ec53L; + + // splitmix64 constants, used to draw candidate construction seeds + private static final long SPLITMIX_GAMMA = 0x9e3779b97f4a7c15L; + private static final long SPLITMIX_MUL1 = 0xbf58476d1ce4e5b9L; + private static final long SPLITMIX_MUL2 = 0x94d049bb133111ebL; + + private final int bitsPerFingerprint_; // fingerprint width in bits, 8 or 16 + private final int segmentLength_; // number of fingerprint slots per hash segment + private final int numKeys_; // number of distinct keys used to build the filter + private final long seed_; // winning construction seed for the murmur mix + private final MemorySegment fpSeg_; // holds the raw fingerprint payload + private final MemorySegment wseg_; // used only when wrapping a serialized image + + /** + * Builds a xor filter from the provided distinct keys and a base construction seed. + * The keys must already be distinct; duplicates cause construction to fail. + * + * @param bitsPerFingerprint The fingerprint width in bits, either 8 or 16 + * @param seed A base seed used to draw candidate construction seeds + * @param keys An array of distinct 64-bit keys, using only the first numKeys entries + * @param numKeys The number of distinct keys to read from the keys array + */ + XorFilter(final int bitsPerFingerprint, final long seed, final long[] keys, final int numKeys) { + bitsPerFingerprint_ = bitsPerFingerprint; + numKeys_ = numKeys; + + final int capacity = computeCapacity(numKeys); + segmentLength_ = capacity / NUM_HASHES; + final int bytesPerFingerprint = bitsPerFingerprint >>> 3; + final long fingerprintBytes = (long) capacity * bytesPerFingerprint; + if (fingerprintBytes > Integer.MAX_VALUE) { + throw new SketchesArgumentException("Requested xor filter is too large to allocate: " + fingerprintBytes + + " fingerprint bytes exceeds " + Integer.MAX_VALUE); + } + fpSeg_ = MemorySegment.ofArray(new byte[(int) fingerprintBytes]); + wseg_ = null; + + // peeling accumulators, indexed by absolute slot in [0, capacity) + final long[] xorMask = new long[capacity]; + final int[] count = new int[capacity]; + final int[] queue = new int[capacity]; + final long[] stackHash = new long[numKeys]; + final int[] stackIndex = new int[numKeys]; + + long rngState = seed; + long buildSeed = 0L; + int stackSize = 0; + + // repeatedly map the keys onto the slots and peel until every key owns a unique slot, + // reseeding on the rare occasion that a two-core remains + for (int attempt = 0; attempt < MAX_ITERATIONS; ++attempt) { Review Comment: ## CodeQL / Useless comparison test Test is always true, because of [this condition](1). Test is always true, because of [this condition](2). [Show more details](https://github.com/apache/datasketches-java/security/code-scanning/963) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
