1 /* 2 * Copyright (C) 2022 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.server.nearby.common.bloomfilter; 18 19 import static java.nio.charset.StandardCharsets.UTF_8; 20 21 import com.google.common.primitives.UnsignedInts; 22 23 import java.nio.charset.Charset; 24 import java.util.Arrays; 25 import java.util.BitSet; 26 27 /** 28 * A bloom filter that gives access to the underlying BitSet. 29 */ 30 public class BloomFilter { 31 private static final Charset CHARSET = UTF_8; 32 33 /** 34 * Receives a value and converts it into an array of ints that will be converted to indexes for 35 * the filter. 36 */ 37 public interface Hasher { 38 /** 39 * Generate hash value. 40 */ getHashes(byte[] value)41 int[] getHashes(byte[] value); 42 } 43 44 // The backing data for this bloom filter. As additions are made, they're OR'd until it 45 // eventually reaches 0xFF. 46 private final BitSet mBits; 47 // The max length of bits. 48 private final int mBitLength; 49 // The hasher to use for converting a value into an array of hashes. 50 private final Hasher mHasher; 51 BloomFilter(byte[] bytes, Hasher hasher)52 public BloomFilter(byte[] bytes, Hasher hasher) { 53 this.mBits = BitSet.valueOf(bytes); 54 this.mBitLength = bytes.length * 8; 55 this.mHasher = hasher; 56 } 57 58 /** 59 * Return the bloom filter check bit set as byte array. 60 */ asBytes()61 public byte[] asBytes() { 62 // BitSet.toByteArray() truncates all the unset bits after the last set bit (eg. [0,0,1,0] 63 // becomes [0,0,1]) so we re-add those bytes if needed with Arrays.copy(). 64 byte[] b = mBits.toByteArray(); 65 if (b.length == mBitLength / 8) { 66 return b; 67 } 68 return Arrays.copyOf(b, mBitLength / 8); 69 } 70 71 /** 72 * Add string value to bloom filter hash. 73 */ add(String s)74 public void add(String s) { 75 add(s.getBytes(CHARSET)); 76 } 77 78 /** 79 * Adds value to bloom filter hash. 80 */ add(byte[] value)81 public void add(byte[] value) { 82 int[] hashes = mHasher.getHashes(value); 83 for (int hash : hashes) { 84 mBits.set(UnsignedInts.remainder(hash, mBitLength)); 85 } 86 } 87 88 /** 89 * Check if the string format has collision. 90 */ possiblyContains(String s)91 public boolean possiblyContains(String s) { 92 return possiblyContains(s.getBytes(CHARSET)); 93 } 94 95 /** 96 * Checks if value after hash will have collision. 97 */ possiblyContains(byte[] value)98 public boolean possiblyContains(byte[] value) { 99 int[] hashes = mHasher.getHashes(value); 100 for (int hash : hashes) { 101 if (!mBits.get(UnsignedInts.remainder(hash, mBitLength))) { 102 return false; 103 } 104 } 105 return true; 106 } 107 } 108 109