1 /*
2 * Copyright (C) 2023 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 #include "location/lbs/contexthub/nanoapps/nearby/bloom_filter.h"
18
19 #include <cstring>
20
21 #include "location/lbs/contexthub/nanoapps/nearby/crypto/sha2.h"
22
23 namespace nearby {
24
BSWAP32(uint32_t value)25 inline static uint32_t BSWAP32(uint32_t value) {
26 #if defined(__clang__) || \
27 (defined(__GNUC__) && \
28 ((__GNUC__ == 4 && __GNUC_MINOR__ >= 8) || __GNUC__ >= 5))
29 return __builtin_bswap32(value);
30 #else
31 uint32_t Byte0 = value & 0x000000FF;
32 uint32_t Byte1 = value & 0x0000FF00;
33 uint32_t Byte2 = value & 0x00FF0000;
34 uint32_t Byte3 = value & 0xFF000000;
35 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
36 #endif
37 }
38
BloomFilter(const uint8_t filter[],size_t size)39 BloomFilter::BloomFilter(const uint8_t filter[], size_t size)
40 : filter_bit_size_(Init(filter, size) * 8) {}
41
Init(const uint8_t filter[],size_t size)42 size_t BloomFilter::Init(const uint8_t filter[], size_t size) {
43 size_t minFilterSize =
44 (kMaxBloomFilterByteSize > size) ? size : kMaxBloomFilterByteSize;
45 memcpy(filter_, filter, minFilterSize);
46 return minFilterSize;
47 }
48
MayContain(const uint8_t key[],size_t size)49 bool BloomFilter::MayContain(const uint8_t key[], size_t size) {
50 uint32_t hash[SHA2_HASH_WORDS];
51 sha256(key, static_cast<uint32_t>(size), hash, sizeof(hash));
52
53 for (size_t i = 0; i < SHA2_HASH_WORDS; i++) {
54 hash[i] = BSWAP32(hash[i]);
55 uint32_t bitPos = hash[i] % (filter_bit_size_);
56 if (!(filter_[bitPos / 8] & (1 << (bitPos % 8)))) {
57 return false;
58 }
59 }
60 return true;
61 }
62
63 } // namespace nearby
64