Class KeySelector

  extended by org.xlattice.crypto.filters.KeySelector

public class KeySelector
extends java.lang.Object

Given a key, populates arrays determining word and bit offsets into a Bloom filter.

Jim Dixon and are BSD licensed from the xlattice app - minor tweaks by jrandom, exposing unsynchronized access and allowing larger M and K. changes released into the public domain.

Nested Class Summary
static interface KeySelector.BitSelector
 class KeySelector.GenericBitSelector
          Extracts the k bit offsets from a key, suitable for general values of m and k.
 class KeySelector.GenericWordSelector
          Extracts the k word offsets from a key.
static interface KeySelector.WordSelector
Field Summary
static int[] MASK
          AND with byte to zero out index-many bits
static int TWO_UP_15
static int[] UNMASK
          AND with byte to expose index-many bits
Constructor Summary
KeySelector(int m, int k, int[] bitOffset, int[] wordOffset)
          Creates a key selector for a Bloom filter.
Method Summary
(package private)  java.lang.String btoh(byte b)
 void getOffsets(byte[] key)
          Given a key, populate the word and bit offset arrays, each of which has k elements.
 void getOffsets(byte[] key, int off, int len)
(package private)  java.lang.String itoh(int i)
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail


public static final int[] UNMASK
AND with byte to expose index-many bits


public static final int[] MASK
AND with byte to zero out index-many bits


public static final int TWO_UP_15
See Also:
Constant Field Values
Constructor Detail


public KeySelector(int m,
                   int k,
                   int[] bitOffset,
                   int[] wordOffset)
Creates a key selector for a Bloom filter. When a key is presented to the getOffsets() method, the k 'hash function' values are extracted and used to populate bitOffset and wordOffset arrays which specify the k flags to be set or examined in the filter.

m - size of the filter as a power of 2
k - number of 'hash functions'
bitOffset - array of k bit offsets (offset of flag bit in word)
wordOffset - array of k word offsets (offset of word flag is in) Note that if k and m are too big, the GenericWordSelector blows up - The max for 32-byte keys is m=23 and k=11. The precise restriction appears to be: ((5k + (k-1)(m-5)) / 8) + 2 < keySizeInBytes It isn't clear how to fix this.
Method Detail


public void getOffsets(byte[] key)
Given a key, populate the word and bit offset arrays, each of which has k elements.

key - cryptographic key used in populating the arrays


public void getOffsets(byte[] key,
                       int off,
                       int len)


java.lang.String itoh(int i)


java.lang.String btoh(byte b)