1// Copyright 2023 Google LLC 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15syntax = "proto3"; 16 17package google.firestore.v1; 18 19option csharp_namespace = "Google.Cloud.Firestore.V1"; 20option go_package = "cloud.google.com/go/firestore/apiv1/firestorepb;firestorepb"; 21option java_multiple_files = true; 22option java_outer_classname = "BloomFilterProto"; 23option java_package = "com.google.firestore.v1"; 24option objc_class_prefix = "GCFS"; 25option php_namespace = "Google\\Cloud\\Firestore\\V1"; 26option ruby_package = "Google::Cloud::Firestore::V1"; 27 28// A sequence of bits, encoded in a byte array. 29// 30// Each byte in the `bitmap` byte array stores 8 bits of the sequence. The only 31// exception is the last byte, which may store 8 _or fewer_ bits. The `padding` 32// defines the number of bits of the last byte to be ignored as "padding". The 33// values of these "padding" bits are unspecified and must be ignored. 34// 35// To retrieve the first bit, bit 0, calculate: `(bitmap[0] & 0x01) != 0`. 36// To retrieve the second bit, bit 1, calculate: `(bitmap[0] & 0x02) != 0`. 37// To retrieve the third bit, bit 2, calculate: `(bitmap[0] & 0x04) != 0`. 38// To retrieve the fourth bit, bit 3, calculate: `(bitmap[0] & 0x08) != 0`. 39// To retrieve bit n, calculate: `(bitmap[n / 8] & (0x01 << (n % 8))) != 0`. 40// 41// The "size" of a `BitSequence` (the number of bits it contains) is calculated 42// by this formula: `(bitmap.length * 8) - padding`. 43message BitSequence { 44 // The bytes that encode the bit sequence. 45 // May have a length of zero. 46 bytes bitmap = 1; 47 48 // The number of bits of the last byte in `bitmap` to ignore as "padding". 49 // If the length of `bitmap` is zero, then this value must be `0`. 50 // Otherwise, this value must be between 0 and 7, inclusive. 51 int32 padding = 2; 52} 53 54// A bloom filter (https://en.wikipedia.org/wiki/Bloom_filter). 55// 56// The bloom filter hashes the entries with MD5 and treats the resulting 128-bit 57// hash as 2 distinct 64-bit hash values, interpreted as unsigned integers 58// using 2's complement encoding. 59// 60// These two hash values, named `h1` and `h2`, are then used to compute the 61// `hash_count` hash values using the formula, starting at `i=0`: 62// 63// h(i) = h1 + (i * h2) 64// 65// These resulting values are then taken modulo the number of bits in the bloom 66// filter to get the bits of the bloom filter to test for the given entry. 67message BloomFilter { 68 // The bloom filter data. 69 BitSequence bits = 1; 70 71 // The number of hashes used by the algorithm. 72 int32 hash_count = 2; 73} 74