| 1 | #define DISABLE_SIGN_COMPARE_WARNINGS |
| 2 | |
| 3 | #include "git-compat-util.h" |
| 4 | #include "bloom.h" |
| 5 | #include "diff.h" |
| 6 | #include "diffcore.h" |
| 7 | #include "hashmap.h" |
| 8 | #include "commit-graph.h" |
| 9 | #include "commit.h" |
| 10 | #include "commit-slab.h" |
| 11 | #include "tree.h" |
| 12 | #include "tree-walk.h" |
| 13 | #include "config.h" |
| 14 | #include "repository.h" |
| 15 | |
| 16 | define_commit_slab(bloom_filter_slab, struct bloom_filter); |
| 17 | |
| 18 | static struct bloom_filter_slab bloom_filters; |
| 19 | |
| 20 | struct pathmap_hash_entry { |
| 21 | struct hashmap_entry entry; |
| 22 | const char path[FLEX_ARRAY]; |
| 23 | }; |
| 24 | |
| 25 | static uint32_t rotate_left(uint32_t value, int32_t count) |
| 26 | { |
| 27 | uint32_t mask = 8 * sizeof(uint32_t) - 1; |
| 28 | count &= mask; |
| 29 | return ((value << count) | (value >> ((-count) & mask))); |
| 30 | } |
| 31 | |
| 32 | static inline unsigned char get_bitmask(uint32_t pos) |
| 33 | { |
| 34 | return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1)); |
| 35 | } |
| 36 | |
| 37 | static int check_bloom_offset(struct commit_graph *g, uint32_t pos, |
| 38 | uint32_t offset) |
| 39 | { |
| 40 | /* |
| 41 | * Note that we allow offsets equal to the data size, which would set |
| 42 | * our pointers at one past the end of the chunk memory. This is |
| 43 | * necessary because the on-disk index points to the end of the |
| 44 | * entries (so we can compute size by comparing adjacent ones). And |
| 45 | * naturally the final entry's end is one-past-the-end of the chunk. |
| 46 | */ |
| 47 | if (offset <= g->chunk_bloom_data_size - BLOOMDATA_CHUNK_HEADER_SIZE) |
| 48 | return 0; |
| 49 | |
| 50 | warning("ignoring out-of-range offset (%"PRIuMAX") for changed-path" |
| 51 | " filter at pos %"PRIuMAX" of %s (chunk size: %"PRIuMAX")", |
| 52 | (uintmax_t)offset, (uintmax_t)pos, |
| 53 | g->filename, (uintmax_t)g->chunk_bloom_data_size); |
| 54 | return -1; |
| 55 | } |
| 56 | |
| 57 | int load_bloom_filter_from_graph(struct commit_graph *g, |
| 58 | struct bloom_filter *filter, |
| 59 | uint32_t graph_pos) |
| 60 | { |
| 61 | uint32_t lex_pos, start_index, end_index; |
| 62 | |
| 63 | while (graph_pos < g->num_commits_in_base) |
| 64 | g = g->base_graph; |
| 65 | |
| 66 | /* The commit graph commit 'c' lives in doesn't carry Bloom filters. */ |
| 67 | if (!g->chunk_bloom_indexes) |
| 68 | return 0; |
| 69 | |
| 70 | lex_pos = graph_pos - g->num_commits_in_base; |
| 71 | |
| 72 | end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos); |
| 73 | |
| 74 | if (lex_pos > 0) |
| 75 | start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1)); |
| 76 | else |
| 77 | start_index = 0; |
| 78 | |
| 79 | if (check_bloom_offset(g, lex_pos, end_index) < 0 || |
| 80 | check_bloom_offset(g, lex_pos - 1, start_index) < 0) |
| 81 | return 0; |
| 82 | |
| 83 | if (end_index < start_index) { |
| 84 | warning("ignoring decreasing changed-path index offsets" |
| 85 | " (%"PRIuMAX" > %"PRIuMAX") for positions" |
| 86 | " %"PRIuMAX" and %"PRIuMAX" of %s", |
| 87 | (uintmax_t)start_index, (uintmax_t)end_index, |
| 88 | (uintmax_t)(lex_pos-1), (uintmax_t)lex_pos, |
| 89 | g->filename); |
| 90 | return 0; |
| 91 | } |
| 92 | |
| 93 | filter->len = end_index - start_index; |
| 94 | filter->data = (unsigned char *)(g->chunk_bloom_data + |
| 95 | sizeof(unsigned char) * start_index + |
| 96 | BLOOMDATA_CHUNK_HEADER_SIZE); |
| 97 | filter->version = g->bloom_filter_settings->hash_version; |
| 98 | filter->to_free = NULL; |
| 99 | |
| 100 | return 1; |
| 101 | } |
| 102 | |
| 103 | /* |
| 104 | * Calculate the murmur3 32-bit hash value for the given data |
| 105 | * using the given seed. |
| 106 | * Produces a uniformly distributed hash value. |
| 107 | * Not considered to be cryptographically secure. |
| 108 | * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm |
| 109 | */ |
| 110 | static uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len) |
| 111 | { |
| 112 | const uint32_t c1 = 0xcc9e2d51; |
| 113 | const uint32_t c2 = 0x1b873593; |
| 114 | const uint32_t r1 = 15; |
| 115 | const uint32_t r2 = 13; |
| 116 | const uint32_t m = 5; |
| 117 | const uint32_t n = 0xe6546b64; |
| 118 | int i; |
| 119 | uint32_t k1 = 0; |
| 120 | const char *tail; |
| 121 | |
| 122 | int len4 = len / sizeof(uint32_t); |
| 123 | |
| 124 | uint32_t k; |
| 125 | for (i = 0; i < len4; i++) { |
| 126 | uint32_t byte1 = (uint32_t)(unsigned char)data[4*i]; |
| 127 | uint32_t byte2 = ((uint32_t)(unsigned char)data[4*i + 1]) << 8; |
| 128 | uint32_t byte3 = ((uint32_t)(unsigned char)data[4*i + 2]) << 16; |
| 129 | uint32_t byte4 = ((uint32_t)(unsigned char)data[4*i + 3]) << 24; |
| 130 | k = byte1 | byte2 | byte3 | byte4; |
| 131 | k *= c1; |
| 132 | k = rotate_left(k, r1); |
| 133 | k *= c2; |
| 134 | |
| 135 | seed ^= k; |
| 136 | seed = rotate_left(seed, r2) * m + n; |
| 137 | } |
| 138 | |
| 139 | tail = (data + len4 * sizeof(uint32_t)); |
| 140 | |
| 141 | switch (len & (sizeof(uint32_t) - 1)) { |
| 142 | case 3: |
| 143 | k1 ^= ((uint32_t)(unsigned char)tail[2]) << 16; |
| 144 | /*-fallthrough*/ |
| 145 | case 2: |
| 146 | k1 ^= ((uint32_t)(unsigned char)tail[1]) << 8; |
| 147 | /*-fallthrough*/ |
| 148 | case 1: |
| 149 | k1 ^= ((uint32_t)(unsigned char)tail[0]) << 0; |
| 150 | k1 *= c1; |
| 151 | k1 = rotate_left(k1, r1); |
| 152 | k1 *= c2; |
| 153 | seed ^= k1; |
| 154 | break; |
| 155 | } |
| 156 | |
| 157 | seed ^= (uint32_t)len; |
| 158 | seed ^= (seed >> 16); |
| 159 | seed *= 0x85ebca6b; |
| 160 | seed ^= (seed >> 13); |
| 161 | seed *= 0xc2b2ae35; |
| 162 | seed ^= (seed >> 16); |
| 163 | |
| 164 | return seed; |
| 165 | } |
| 166 | |
| 167 | static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len) |
| 168 | { |
| 169 | const uint32_t c1 = 0xcc9e2d51; |
| 170 | const uint32_t c2 = 0x1b873593; |
| 171 | const uint32_t r1 = 15; |
| 172 | const uint32_t r2 = 13; |
| 173 | const uint32_t m = 5; |
| 174 | const uint32_t n = 0xe6546b64; |
| 175 | int i; |
| 176 | uint32_t k1 = 0; |
| 177 | const char *tail; |
| 178 | |
| 179 | int len4 = len / sizeof(uint32_t); |
| 180 | |
| 181 | uint32_t k; |
| 182 | for (i = 0; i < len4; i++) { |
| 183 | uint32_t byte1 = (uint32_t)data[4*i]; |
| 184 | uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8; |
| 185 | uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16; |
| 186 | uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24; |
| 187 | k = byte1 | byte2 | byte3 | byte4; |
| 188 | k *= c1; |
| 189 | k = rotate_left(k, r1); |
| 190 | k *= c2; |
| 191 | |
| 192 | seed ^= k; |
| 193 | seed = rotate_left(seed, r2) * m + n; |
| 194 | } |
| 195 | |
| 196 | tail = (data + len4 * sizeof(uint32_t)); |
| 197 | |
| 198 | switch (len & (sizeof(uint32_t) - 1)) { |
| 199 | case 3: |
| 200 | k1 ^= ((uint32_t)tail[2]) << 16; |
| 201 | /*-fallthrough*/ |
| 202 | case 2: |
| 203 | k1 ^= ((uint32_t)tail[1]) << 8; |
| 204 | /*-fallthrough*/ |
| 205 | case 1: |
| 206 | k1 ^= ((uint32_t)tail[0]) << 0; |
| 207 | k1 *= c1; |
| 208 | k1 = rotate_left(k1, r1); |
| 209 | k1 *= c2; |
| 210 | seed ^= k1; |
| 211 | break; |
| 212 | } |
| 213 | |
| 214 | seed ^= (uint32_t)len; |
| 215 | seed ^= (seed >> 16); |
| 216 | seed *= 0x85ebca6b; |
| 217 | seed ^= (seed >> 13); |
| 218 | seed *= 0xc2b2ae35; |
| 219 | seed ^= (seed >> 16); |
| 220 | |
| 221 | return seed; |
| 222 | } |
| 223 | |
| 224 | void bloom_key_fill(struct bloom_key *key, const char *data, size_t len, |
| 225 | const struct bloom_filter_settings *settings) |
| 226 | { |
| 227 | int i; |
| 228 | const uint32_t seed0 = 0x293ae76f; |
| 229 | const uint32_t seed1 = 0x7e646e2c; |
| 230 | uint32_t hash0, hash1; |
| 231 | if (settings->hash_version == 2) { |
| 232 | hash0 = murmur3_seeded_v2(seed0, data, len); |
| 233 | hash1 = murmur3_seeded_v2(seed1, data, len); |
| 234 | } else { |
| 235 | hash0 = murmur3_seeded_v1(seed0, data, len); |
| 236 | hash1 = murmur3_seeded_v1(seed1, data, len); |
| 237 | } |
| 238 | |
| 239 | key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t)); |
| 240 | for (i = 0; i < settings->num_hashes; i++) |
| 241 | key->hashes[i] = hash0 + i * hash1; |
| 242 | } |
| 243 | |
| 244 | void bloom_key_clear(struct bloom_key *key) |
| 245 | { |
| 246 | FREE_AND_NULL(key->hashes); |
| 247 | } |
| 248 | |
| 249 | void add_key_to_filter(const struct bloom_key *key, |
| 250 | struct bloom_filter *filter, |
| 251 | const struct bloom_filter_settings *settings) |
| 252 | { |
| 253 | int i; |
| 254 | uint64_t mod = filter->len * BITS_PER_WORD; |
| 255 | |
| 256 | for (i = 0; i < settings->num_hashes; i++) { |
| 257 | uint64_t hash_mod = key->hashes[i] % mod; |
| 258 | uint64_t block_pos = hash_mod / BITS_PER_WORD; |
| 259 | |
| 260 | filter->data[block_pos] |= get_bitmask(hash_mod); |
| 261 | } |
| 262 | } |
| 263 | |
| 264 | void init_bloom_filters(void) |
| 265 | { |
| 266 | init_bloom_filter_slab(&bloom_filters); |
| 267 | } |
| 268 | |
| 269 | static void free_one_bloom_filter(struct bloom_filter *filter) |
| 270 | { |
| 271 | if (!filter) |
| 272 | return; |
| 273 | free(filter->to_free); |
| 274 | } |
| 275 | |
| 276 | void deinit_bloom_filters(void) |
| 277 | { |
| 278 | deep_clear_bloom_filter_slab(&bloom_filters, free_one_bloom_filter); |
| 279 | } |
| 280 | |
| 281 | struct bloom_keyvec *bloom_keyvec_new(const char *path, size_t len, |
| 282 | const struct bloom_filter_settings *settings) |
| 283 | { |
| 284 | struct bloom_keyvec *vec; |
| 285 | const char *p; |
| 286 | size_t sz; |
| 287 | size_t nr = 1; |
| 288 | |
| 289 | p = path; |
| 290 | while (*p) { |
| 291 | /* |
| 292 | * At this point, the path is normalized to use Unix-style |
| 293 | * path separators. This is required due to how the |
| 294 | * changed-path Bloom filters store the paths. |
| 295 | */ |
| 296 | if (*p == '/') |
| 297 | nr++; |
| 298 | p++; |
| 299 | } |
| 300 | |
| 301 | sz = sizeof(struct bloom_keyvec); |
| 302 | sz += nr * sizeof(struct bloom_key); |
| 303 | vec = (struct bloom_keyvec *)xcalloc(1, sz); |
| 304 | if (!vec) |
| 305 | return NULL; |
| 306 | vec->count = nr; |
| 307 | |
| 308 | bloom_key_fill(&vec->key[0], path, len, settings); |
| 309 | nr = 1; |
| 310 | p = path + len - 1; |
| 311 | while (p > path) { |
| 312 | if (*p == '/') { |
| 313 | bloom_key_fill(&vec->key[nr++], path, p - path, settings); |
| 314 | } |
| 315 | p--; |
| 316 | } |
| 317 | assert(nr == vec->count); |
| 318 | return vec; |
| 319 | } |
| 320 | |
| 321 | void bloom_keyvec_free(struct bloom_keyvec *vec) |
| 322 | { |
| 323 | if (!vec) |
| 324 | return; |
| 325 | for (size_t nr = 0; nr < vec->count; nr++) |
| 326 | bloom_key_clear(&vec->key[nr]); |
| 327 | free(vec); |
| 328 | } |
| 329 | |
| 330 | static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, |
| 331 | const struct hashmap_entry *eptr, |
| 332 | const struct hashmap_entry *entry_or_key, |
| 333 | const void *keydata UNUSED) |
| 334 | { |
| 335 | const struct pathmap_hash_entry *e1, *e2; |
| 336 | |
| 337 | e1 = container_of(eptr, const struct pathmap_hash_entry, entry); |
| 338 | e2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry); |
| 339 | |
| 340 | return strcmp(e1->path, e2->path); |
| 341 | } |
| 342 | |
| 343 | static void init_truncated_large_filter(struct bloom_filter *filter, |
| 344 | int version) |
| 345 | { |
| 346 | filter->data = filter->to_free = xmalloc(1); |
| 347 | filter->data[0] = 0xFF; |
| 348 | filter->len = 1; |
| 349 | filter->version = version; |
| 350 | } |
| 351 | |
| 352 | #define VISITED (1u<<21) |
| 353 | #define HIGH_BITS (1u<<22) |
| 354 | |
| 355 | static int has_entries_with_high_bit(struct repository *r, struct tree *t) |
| 356 | { |
| 357 | if (repo_parse_tree(r, t)) |
| 358 | return 1; |
| 359 | |
| 360 | if (!(t->object.flags & VISITED)) { |
| 361 | struct tree_desc desc; |
| 362 | struct name_entry entry; |
| 363 | |
| 364 | init_tree_desc(&desc, &t->object.oid, t->buffer, t->size); |
| 365 | while (tree_entry(&desc, &entry)) { |
| 366 | size_t i; |
| 367 | for (i = 0; i < entry.pathlen; i++) { |
| 368 | if (entry.path[i] & 0x80) { |
| 369 | t->object.flags |= HIGH_BITS; |
| 370 | goto done; |
| 371 | } |
| 372 | } |
| 373 | |
| 374 | if (S_ISDIR(entry.mode)) { |
| 375 | struct tree *sub = lookup_tree(r, &entry.oid); |
| 376 | if (sub && has_entries_with_high_bit(r, sub)) { |
| 377 | t->object.flags |= HIGH_BITS; |
| 378 | goto done; |
| 379 | } |
| 380 | } |
| 381 | |
| 382 | } |
| 383 | |
| 384 | done: |
| 385 | t->object.flags |= VISITED; |
| 386 | } |
| 387 | |
| 388 | return !!(t->object.flags & HIGH_BITS); |
| 389 | } |
| 390 | |
| 391 | static int commit_tree_has_high_bit_paths(struct repository *r, |
| 392 | struct commit *c) |
| 393 | { |
| 394 | struct tree *t; |
| 395 | if (repo_parse_commit(r, c)) |
| 396 | return 1; |
| 397 | t = repo_get_commit_tree(r, c); |
| 398 | if (!t) |
| 399 | return 1; |
| 400 | return has_entries_with_high_bit(r, t); |
| 401 | } |
| 402 | |
| 403 | static struct bloom_filter *upgrade_filter(struct repository *r, struct commit *c, |
| 404 | struct bloom_filter *filter, |
| 405 | int hash_version) |
| 406 | { |
| 407 | struct commit_list *p = c->parents; |
| 408 | if (commit_tree_has_high_bit_paths(r, c)) |
| 409 | return NULL; |
| 410 | |
| 411 | if (p && commit_tree_has_high_bit_paths(r, p->item)) |
| 412 | return NULL; |
| 413 | |
| 414 | filter->version = hash_version; |
| 415 | |
| 416 | return filter; |
| 417 | } |
| 418 | |
| 419 | struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c) |
| 420 | { |
| 421 | struct bloom_filter *filter; |
| 422 | int hash_version; |
| 423 | |
| 424 | filter = get_or_compute_bloom_filter(r, c, 0, NULL, NULL); |
| 425 | if (!filter) |
| 426 | return NULL; |
| 427 | |
| 428 | prepare_repo_settings(r); |
| 429 | hash_version = r->settings.commit_graph_changed_paths_version; |
| 430 | |
| 431 | if (!(hash_version == -1 || hash_version == filter->version)) |
| 432 | return NULL; /* unusable filter */ |
| 433 | return filter; |
| 434 | } |
| 435 | |
| 436 | struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, |
| 437 | struct commit *c, |
| 438 | int compute_if_not_present, |
| 439 | const struct bloom_filter_settings *settings, |
| 440 | enum bloom_filter_computed *computed) |
| 441 | { |
| 442 | struct bloom_filter *filter; |
| 443 | int i; |
| 444 | struct diff_options diffopt; |
| 445 | |
| 446 | if (computed) |
| 447 | *computed = BLOOM_NOT_COMPUTED; |
| 448 | |
| 449 | if (!bloom_filters.slab_size) |
| 450 | return NULL; |
| 451 | |
| 452 | filter = bloom_filter_slab_at(&bloom_filters, c); |
| 453 | |
| 454 | if (!filter->data) { |
| 455 | struct commit_graph *g; |
| 456 | uint32_t graph_pos; |
| 457 | |
| 458 | g = repo_find_commit_pos_in_graph(r, c, &graph_pos); |
| 459 | if (g) |
| 460 | load_bloom_filter_from_graph(g, filter, graph_pos); |
| 461 | } |
| 462 | |
| 463 | if (filter->data && filter->len) { |
| 464 | struct bloom_filter *upgrade; |
| 465 | if (!settings || settings->hash_version == filter->version) |
| 466 | return filter; |
| 467 | |
| 468 | /* version mismatch, see if we can upgrade */ |
| 469 | if (compute_if_not_present && |
| 470 | git_env_bool("GIT_TEST_UPGRADE_BLOOM_FILTERS", 1)) { |
| 471 | upgrade = upgrade_filter(r, c, filter, |
| 472 | settings->hash_version); |
| 473 | if (upgrade) { |
| 474 | if (computed) |
| 475 | *computed |= BLOOM_UPGRADED; |
| 476 | return upgrade; |
| 477 | } |
| 478 | } |
| 479 | } |
| 480 | if (!compute_if_not_present) |
| 481 | return NULL; |
| 482 | |
| 483 | repo_diff_setup(r, &diffopt); |
| 484 | diffopt.flags.recursive = 1; |
| 485 | diffopt.detect_rename = 0; |
| 486 | diffopt.max_changes = settings->max_changed_paths; |
| 487 | diff_setup_done(&diffopt); |
| 488 | |
| 489 | /* ensure commit is parsed so we have parent information */ |
| 490 | repo_parse_commit(r, c); |
| 491 | |
| 492 | if (c->parents) |
| 493 | diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt); |
| 494 | else |
| 495 | diff_tree_oid(NULL, &c->object.oid, "", &diffopt); |
| 496 | diffcore_std(&diffopt); |
| 497 | |
| 498 | if (diff_queued_diff.nr <= settings->max_changed_paths) { |
| 499 | struct hashmap pathmap = HASHMAP_INIT(pathmap_cmp, NULL); |
| 500 | struct pathmap_hash_entry *e; |
| 501 | struct hashmap_iter iter; |
| 502 | |
| 503 | for (i = 0; i < diff_queued_diff.nr; i++) { |
| 504 | char *path = diff_queued_diff.queue[i]->two->path; |
| 505 | |
| 506 | /* |
| 507 | * Add each leading directory of the changed file, i.e. for |
| 508 | * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so |
| 509 | * the Bloom filter could be used to speed up commands like |
| 510 | * 'git log dir/subdir', too. |
| 511 | * |
| 512 | * Note that directories are added without the trailing '/'. |
| 513 | */ |
| 514 | do { |
| 515 | char *last_slash = strrchr(path, '/'); |
| 516 | |
| 517 | FLEX_ALLOC_STR(e, path, path); |
| 518 | hashmap_entry_init(&e->entry, strhash(path)); |
| 519 | |
| 520 | if (!hashmap_get(&pathmap, &e->entry, NULL)) |
| 521 | hashmap_add(&pathmap, &e->entry); |
| 522 | else |
| 523 | free(e); |
| 524 | |
| 525 | if (!last_slash) |
| 526 | last_slash = path; |
| 527 | *last_slash = '\0'; |
| 528 | |
| 529 | } while (*path); |
| 530 | } |
| 531 | |
| 532 | if (hashmap_get_size(&pathmap) > settings->max_changed_paths) { |
| 533 | init_truncated_large_filter(filter, |
| 534 | settings->hash_version); |
| 535 | if (computed) |
| 536 | *computed |= BLOOM_TRUNC_LARGE; |
| 537 | goto cleanup; |
| 538 | } |
| 539 | |
| 540 | filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD; |
| 541 | filter->version = settings->hash_version; |
| 542 | if (!filter->len) { |
| 543 | if (computed) |
| 544 | *computed |= BLOOM_TRUNC_EMPTY; |
| 545 | filter->len = 1; |
| 546 | } |
| 547 | CALLOC_ARRAY(filter->data, filter->len); |
| 548 | filter->to_free = filter->data; |
| 549 | |
| 550 | hashmap_for_each_entry(&pathmap, &iter, e, entry) { |
| 551 | struct bloom_key key; |
| 552 | bloom_key_fill(&key, e->path, strlen(e->path), settings); |
| 553 | add_key_to_filter(&key, filter, settings); |
| 554 | bloom_key_clear(&key); |
| 555 | } |
| 556 | |
| 557 | cleanup: |
| 558 | hashmap_clear_and_free(&pathmap, struct pathmap_hash_entry, entry); |
| 559 | } else { |
| 560 | init_truncated_large_filter(filter, settings->hash_version); |
| 561 | |
| 562 | if (computed) |
| 563 | *computed |= BLOOM_TRUNC_LARGE; |
| 564 | } |
| 565 | |
| 566 | if (computed) |
| 567 | *computed |= BLOOM_COMPUTED; |
| 568 | |
| 569 | diff_queue_clear(&diff_queued_diff); |
| 570 | return filter; |
| 571 | } |
| 572 | |
| 573 | int bloom_filter_contains(const struct bloom_filter *filter, |
| 574 | const struct bloom_key *key, |
| 575 | const struct bloom_filter_settings *settings) |
| 576 | { |
| 577 | int i; |
| 578 | uint64_t mod = filter->len * BITS_PER_WORD; |
| 579 | |
| 580 | if (!mod) |
| 581 | return -1; |
| 582 | |
| 583 | for (i = 0; i < settings->num_hashes; i++) { |
| 584 | uint64_t hash_mod = key->hashes[i] % mod; |
| 585 | uint64_t block_pos = hash_mod / BITS_PER_WORD; |
| 586 | if (!(filter->data[block_pos] & get_bitmask(hash_mod))) |
| 587 | return 0; |
| 588 | } |
| 589 | |
| 590 | return 1; |
| 591 | } |
| 592 | |
| 593 | int bloom_filter_contains_vec(const struct bloom_filter *filter, |
| 594 | const struct bloom_keyvec *vec, |
| 595 | const struct bloom_filter_settings *settings) |
| 596 | { |
| 597 | int ret = 1; |
| 598 | |
| 599 | for (size_t nr = 0; ret > 0 && nr < vec->count; nr++) |
| 600 | ret = bloom_filter_contains(filter, &vec->key[nr], settings); |
| 601 | |
| 602 | return ret; |
| 603 | } |
| 604 | |
| 605 | uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len, |
| 606 | int version) |
| 607 | { |
| 608 | assert(version == 1 || version == 2); |
| 609 | |
| 610 | if (version == 2) |
| 611 | return murmur3_seeded_v2(seed, data, len); |
| 612 | else |
| 613 | return murmur3_seeded_v1(seed, data, len); |
| 614 | } |