Skip to content

Commit 4d2f7ee

Browse files
lemirelemire
authored
Merge pull request #47 from igor-sokolov/sis/add-serialize-deserialize-methods
Add serialize deserialize methods to XorBinaryFuse16
2 parents bc4d79b + bb124f6 commit 4d2f7ee

8 files changed

Lines changed: 596 additions & 20 deletions

File tree

‎fastfilter/src/main/java/org/fastfilter/Filter.java‎

Lines changed: 21 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package org.fastfilter;
22

3+
import java.nio.ByteBuffer;
4+
35
/**
46
* An approximate membership filter.
57
*/
@@ -14,7 +16,7 @@ public interface Filter {
1416
boolean mayContain(long key);
1517

1618
/**
17-
* Get the number of bits in thhe filter.
19+
* Get the number of bits in the filter.
1820
*
1921
* @return the number of bits
2022
*/
@@ -65,4 +67,22 @@ default long cardinality() {
6567
return -1;
6668
}
6769

70+
/**
71+
* Get the serialized size of the filter.
72+
*
73+
* @return the size in bytes
74+
*/
75+
default int getSerializedSize() {
76+
return -1;
77+
}
78+
79+
/**
80+
* Serializes the filter state into the provided {@code ByteBuffer}.
81+
*
82+
* @param buffer the byte buffer where the serialized state of the filter will be written
83+
* @throws UnsupportedOperationException if the operation is not supported by the filter implementation
84+
*/
85+
default void serialize(ByteBuffer buffer) {
86+
throw new UnsupportedOperationException();
87+
}
6888
}

‎fastfilter/src/main/java/org/fastfilter/utils/Hash.java‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,6 @@
33
import java.util.Random;
44

55
public class Hash {
6-
76
private static Random random = new Random();
87

98
public static void setSeed(long seed) {

‎fastfilter/src/main/java/org/fastfilter/xor/Xor16.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package org.fastfilter.xor;
22

3+
import java.nio.ByteBuffer;
4+
35
import org.fastfilter.Filter;
46
import org.fastfilter.utils.Hash;
57

@@ -143,4 +145,55 @@ private int fingerprint(long hash) {
143145
return (int) (hash & ((1 << BITS_PER_FINGERPRINT) - 1));
144146
}
145147

148+
private Xor16(int blockLength, int bitCount, long seed, short[] fingerprints) {
149+
this.blockLength = blockLength;
150+
this.bitCount = bitCount;
151+
this.seed = seed;
152+
this.fingerprints = fingerprints;
153+
}
154+
155+
@Override
156+
public int getSerializedSize() {
157+
return Integer.BYTES + Long.BYTES + Integer.BYTES + fingerprints.length * Short.BYTES;
158+
}
159+
160+
@Override
161+
public void serialize(ByteBuffer buffer) {
162+
if (buffer.remaining() < getSerializedSize()) {
163+
throw new IllegalArgumentException("Buffer too small");
164+
}
165+
166+
buffer.putInt(blockLength);
167+
buffer.putLong(seed);
168+
buffer.putInt(fingerprints.length);
169+
for (final short fp : fingerprints) {
170+
buffer.putShort(fp);
171+
}
172+
}
173+
174+
public static Xor16 deserialize(ByteBuffer buffer) {
175+
// Check minimum size for header (1 int + 1 long + 1 int for length)
176+
if (buffer.remaining() < Integer.BYTES + Long.BYTES + Integer.BYTES) {
177+
throw new IllegalArgumentException("Buffer too small");
178+
}
179+
180+
final int blockLength = buffer.getInt();
181+
final long seed = buffer.getLong();
182+
183+
final int len = buffer.getInt();
184+
185+
// Check if buffer has enough bytes for all fingerprints
186+
if (buffer.remaining() < len * Short.BYTES) {
187+
throw new IllegalArgumentException("Buffer too small");
188+
}
189+
190+
final short[] fingerprints = new short[len];
191+
for (int i = 0; i < len; i++) {
192+
fingerprints[i] = buffer.getShort();
193+
}
194+
195+
final int bitCount = len * BITS_PER_FINGERPRINT;
196+
197+
return new Xor16(blockLength, bitCount, seed, fingerprints);
198+
}
146199
}

‎fastfilter/src/main/java/org/fastfilter/xor/Xor8.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
package org.fastfilter.xor;
22

33
import java.io.*;
4+
import java.nio.ByteBuffer;
45

56
import org.fastfilter.Filter;
67
import org.fastfilter.utils.Hash;
@@ -187,4 +188,51 @@ public Xor8(InputStream in) {
187188
}
188189
}
189190

191+
private Xor8(int size, long seed, byte[] fingerprints) {
192+
this.size = size;
193+
this.arrayLength = getArrayLength(size);
194+
this.bitCount = arrayLength * BITS_PER_FINGERPRINT;
195+
this.blockLength = arrayLength / HASHES;
196+
this.seed = seed;
197+
this.fingerprints = fingerprints;
198+
}
199+
200+
@Override
201+
public int getSerializedSize() {
202+
return Integer.BYTES + Long.BYTES + Integer.BYTES + fingerprints.length * Byte.BYTES;
203+
}
204+
205+
@Override
206+
public void serialize(ByteBuffer buffer) {
207+
if (buffer.remaining() < getSerializedSize()) {
208+
throw new IllegalArgumentException("Buffer too small");
209+
}
210+
211+
buffer.putInt(size);
212+
buffer.putLong(seed);
213+
buffer.putInt(fingerprints.length);
214+
buffer.put(fingerprints);
215+
}
216+
217+
public static Xor8 deserialize(ByteBuffer buffer) {
218+
// Check minimum size for header (1 int + 1 long + 1 int for length)
219+
if (buffer.remaining() < Integer.BYTES + Long.BYTES + Integer.BYTES) {
220+
throw new IllegalArgumentException("Buffer too small");
221+
}
222+
223+
final int size = buffer.getInt();
224+
final long seed = buffer.getLong();
225+
226+
final int len = buffer.getInt();
227+
228+
// Check if buffer has enough bytes for all fingerprints
229+
if (buffer.remaining() < len * Byte.BYTES) {
230+
throw new IllegalArgumentException("Buffer too small");
231+
}
232+
233+
final byte[] fingerprints = new byte[len];
234+
buffer.get(fingerprints);
235+
236+
return new Xor8(size, seed, fingerprints);
237+
}
190238
}

‎fastfilter/src/main/java/org/fastfilter/xor/XorBinaryFuse16.java‎

Lines changed: 62 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
package org.fastfilter.xor;
22

3+
import java.nio.ByteBuffer;
34
import java.util.Arrays;
4-
55
import org.fastfilter.Filter;
66
import org.fastfilter.utils.Hash;
77

@@ -20,19 +20,25 @@ public class XorBinaryFuse16 implements Filter {
2020
private final short[] fingerprints;
2121
private long seed;
2222

23-
public XorBinaryFuse16(int segmentCount, int segmentLength) {
23+
private XorBinaryFuse16(int segmentCount, int segmentLength, long seed, short[] fingerprints) {
2424
if (segmentLength < 0 || Integer.bitCount(segmentLength) != 1) {
2525
throw new IllegalArgumentException("Segment length needs to be a power of 2, is " + segmentLength);
2626
}
2727
if (segmentCount <= 0) {
2828
throw new IllegalArgumentException("Illegal segment count: " + segmentCount);
2929
}
30-
this.segmentLength = segmentLength;
30+
3131
this.segmentCount = segmentCount;
32-
this.segmentLengthMask = segmentLength - 1;
3332
this.segmentCountLength = segmentCount * segmentLength;
34-
this.arrayLength = (segmentCount + ARITY - 1) * segmentLength;
35-
this.fingerprints = new short[arrayLength];
33+
this.segmentLength = segmentLength;
34+
this.segmentLengthMask = segmentLength - 1;
35+
this.arrayLength = fingerprints.length;
36+
this.fingerprints = fingerprints;
37+
this.seed = seed;
38+
}
39+
40+
public XorBinaryFuse16(int segmentCount, int segmentLength) {
41+
this(segmentCount, segmentLength, 0L, new short[(segmentCount + ARITY - 1) * segmentLength]);
3642
}
3743

3844
public long getBitCount() {
@@ -204,9 +210,10 @@ private void addAll(long[] keys) {
204210
// It's better fail that either produce non-functional or incorrect filter.
205211
throw new IllegalArgumentException("could not construct filter");
206212
}
207-
// use a new random numbers
213+
// use a new random number
208214
seed = Hash.randomSeed();
209215
}
216+
210217
alone = null;
211218
t2count = null;
212219
t2hash = null;
@@ -258,4 +265,51 @@ private short fingerprint(long hash) {
258265
return (short) hash;
259266
}
260267

261-
}
268+
@Override
269+
public int getSerializedSize() {
270+
return 2 * Integer.BYTES + Long.BYTES + Integer.BYTES + fingerprints.length * Short.BYTES;
271+
}
272+
273+
@Override
274+
public void serialize(ByteBuffer buffer) {
275+
if (buffer.remaining() < getSerializedSize()) {
276+
throw new IllegalArgumentException("Buffer too small");
277+
}
278+
279+
buffer.putInt(segmentLength);
280+
buffer.putInt(segmentCountLength);
281+
buffer.putLong(seed);
282+
buffer.putInt(fingerprints.length);
283+
for (final short fp : fingerprints) {
284+
buffer.putShort(fp);
285+
}
286+
}
287+
288+
public static XorBinaryFuse16 deserialize(ByteBuffer buffer) {
289+
// Check minimum size for header (2 ints + 1 long + 1 int for length)
290+
if (buffer.remaining() < 2 * Integer.BYTES + Long.BYTES + Integer.BYTES) {
291+
throw new IllegalArgumentException("Buffer too small");
292+
}
293+
294+
final int segmentLength = buffer.getInt();
295+
final int segmentCountLength = buffer.getInt();
296+
final long seed = buffer.getLong();
297+
298+
final int len = buffer.getInt();
299+
300+
// Check if buffer has enough bytes for all fingerprints
301+
if (buffer.remaining() < len * Short.BYTES) {
302+
throw new IllegalArgumentException("Buffer too small");
303+
}
304+
305+
final short[] fingerprints = new short[len];
306+
for (int i = 0; i < len; i++) {
307+
fingerprints[i] = buffer.getShort();
308+
}
309+
310+
// Calculate segmentCount from segmentCountLength and segmentLength
311+
final int segmentCount = segmentCountLength / segmentLength;
312+
313+
return new XorBinaryFuse16(segmentCount, segmentLength, seed, fingerprints);
314+
}
315+
}

‎fastfilter/src/main/java/org/fastfilter/xor/XorBinaryFuse32.java‎

Lines changed: 59 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
package org.fastfilter.xor;
22

3+
import java.nio.ByteBuffer;
34
import java.util.Arrays;
45

56
import org.fastfilter.Filter;
@@ -20,19 +21,25 @@ public class XorBinaryFuse32 implements Filter {
2021
private final int[] fingerprints;
2122
private long seed;
2223

23-
public XorBinaryFuse32(int segmentCount, int segmentLength) {
24+
private XorBinaryFuse32(int segmentCount, int segmentLength, long seed, int[] fingerprints) {
2425
if (segmentLength < 0 || Integer.bitCount(segmentLength) != 1) {
2526
throw new IllegalArgumentException("Segment length needs to be a power of 2, is " + segmentLength);
2627
}
2728
if (segmentCount <= 0) {
2829
throw new IllegalArgumentException("Illegal segment count: " + segmentCount);
2930
}
30-
this.segmentLength = segmentLength;
31+
3132
this.segmentCount = segmentCount;
32-
this.segmentLengthMask = segmentLength - 1;
3333
this.segmentCountLength = segmentCount * segmentLength;
34-
this.arrayLength = (segmentCount + ARITY - 1) * segmentLength;
35-
this.fingerprints = new int[arrayLength];
34+
this.segmentLength = segmentLength;
35+
this.segmentLengthMask = segmentLength - 1;
36+
this.arrayLength = fingerprints.length;
37+
this.fingerprints = fingerprints;
38+
this.seed = seed;
39+
}
40+
41+
public XorBinaryFuse32(int segmentCount, int segmentLength) {
42+
this(segmentCount, segmentLength, 0L, new int[(segmentCount + ARITY - 1) * segmentLength]);
3643
}
3744

3845
public long getBitCount() {
@@ -258,4 +265,51 @@ private int fingerprint(long hash) {
258265
return (int) (hash ^ (hash >>> 32));
259266
}
260267

268+
@Override
269+
public int getSerializedSize() {
270+
return 2 * Integer.BYTES + Long.BYTES + Integer.BYTES + fingerprints.length * Integer.BYTES;
271+
}
272+
273+
@Override
274+
public void serialize(ByteBuffer buffer) {
275+
if (buffer.remaining() < getSerializedSize()) {
276+
throw new IllegalArgumentException("Buffer too small");
277+
}
278+
279+
buffer.putInt(segmentLength);
280+
buffer.putInt(segmentCountLength);
281+
buffer.putLong(seed);
282+
buffer.putInt(fingerprints.length);
283+
for (final int fp : fingerprints) {
284+
buffer.putInt(fp);
285+
}
286+
}
287+
288+
public static XorBinaryFuse32 deserialize(ByteBuffer buffer) {
289+
// Check minimum size for header (2 ints + 1 long + 1 int for length)
290+
if (buffer.remaining() < 2 * Integer.BYTES + Long.BYTES + Integer.BYTES) {
291+
throw new IllegalArgumentException("Buffer too small");
292+
}
293+
294+
final int segmentLength = buffer.getInt();
295+
final int segmentCountLength = buffer.getInt();
296+
final long seed = buffer.getLong();
297+
298+
final int len = buffer.getInt();
299+
300+
// Check if buffer has enough bytes for all fingerprints
301+
if (buffer.remaining() < len * Integer.BYTES) {
302+
throw new IllegalArgumentException("Buffer too small");
303+
}
304+
305+
final int[] fingerprints = new int[len];
306+
for (int i = 0; i < len; i++) {
307+
fingerprints[i] = buffer.getInt();
308+
}
309+
310+
// Calculate segmentCount from segmentCountLength and segmentLength
311+
final int segmentCount = segmentCountLength / segmentLength;
312+
313+
return new XorBinaryFuse32(segmentCount, segmentLength, seed, fingerprints);
314+
}
261315
}

0 commit comments

Comments
 (0)