fuzz_set_alloc_callbacks: 31| 865|{ 32| 865| ndpi_set_memory_alloction_functions(malloc_wrapper, 33| 865| free_wrapper, 34| 865| calloc_wrapper, 35| 865| realloc_wrapper, 36| | /* Aligned allocations are used only by croaring, 37| | but no during fuzzing. So no point to set 38| | these two wrappers here */ 39| 865| NULL, NULL, 40| 865| malloc_wrapper, 41| 865| free_wrapper); 42| 865|} fuzz_set_alloc_seed: 44| 865|{ 45| 865| mem_alloc_state = seed; 46| 865|} fuzz_set_alloc_callbacks_and_seed: 48| 865|{ 49| 865| fuzz_set_alloc_callbacks(); 50| 865| fuzz_set_alloc_seed(seed); 51| 865|} fuzz_common_code.c:malloc_wrapper: 17| 5.49k|static void *malloc_wrapper(size_t size) { 18| 5.49k| return (fastrand () % 16) ? malloc (size) : NULL; ------------------ | Branch (18:10): [True: 5.07k, False: 415] ------------------ 19| 5.49k|} fuzz_common_code.c:fastrand: 11| 18.2k|{ 12| 18.2k| if(!mem_alloc_state) return 1; /* No failures */ ------------------ | Branch (12:6): [True: 0, False: 18.2k] ------------------ 13| 18.2k| mem_alloc_state = (214013 * mem_alloc_state + 2531011); 14| 18.2k| return (mem_alloc_state >> 16) & 0x7FFF; 15| 18.2k|} fuzz_common_code.c:free_wrapper: 20| 12.6k|static void free_wrapper(void *freeable) { 21| 12.6k| free(freeable); 22| 12.6k|} fuzz_common_code.c:calloc_wrapper: 23| 7.12k|static void *calloc_wrapper(size_t nmemb, size_t size) { 24| 7.12k| return (fastrand () % 16) ? calloc (nmemb, size) : NULL; ------------------ | Branch (24:10): [True: 6.60k, False: 525] ------------------ 25| 7.12k|} fuzz_common_code.c:realloc_wrapper: 26| 5.59k|static void *realloc_wrapper(void *ptr, size_t size) { 27| 5.59k| return (fastrand () % 16) ? realloc (ptr, size) : NULL; ------------------ | Branch (27:10): [True: 5.22k, False: 376] ------------------ 28| 5.59k|} LLVMFuzzerTestOneInput: 7| 865|extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { 8| 865| FuzzedDataProvider fuzzed_data(data, size); 9| 865| u_int16_t i, num_iteration, is_added = 0; 10| 865| ndpi_bitmap64_fuse *b; 11| 865| bool rc; 12| 865| u_int64_t value, value_added; 13| | 14| | /* To allow memory allocation failures */ 15| 865| fuzz_set_alloc_callbacks_and_seed(size); 16| | 17| 865| b = ndpi_bitmap64_fuse_alloc(); 18| | 19| 865| if(fuzzed_data.ConsumeBool()) ------------------ | Branch (19:6): [True: 492, False: 373] ------------------ 20| 492| ndpi_bitmap64_fuse_compress(b); 21| | 22| 865| num_iteration = fuzzed_data.ConsumeIntegral(); 23| 22.5M| for (i = 0; i < num_iteration; i++) { ------------------ | Branch (23:15): [True: 22.5M, False: 865] ------------------ 24| 22.5M| value = fuzzed_data.ConsumeIntegral(); 25| | 26| 22.5M| rc = ndpi_bitmap64_fuse_set(b, value); 27| | /* Keep one random entry really added */ 28| 22.5M| if (rc == true && is_added == 0 && fuzzed_data.ConsumeBool()) { ------------------ | Branch (28:9): [True: 21.7M, False: 787k] | Branch (28:23): [True: 7.43M, False: 14.3M] | Branch (28:40): [True: 449, False: 7.43M] ------------------ 29| 449| value_added = value; 30| 449| is_added = 1; 31| 449| } 32| 22.5M| } 33| | 34| 865| if(fuzzed_data.ConsumeBool()) ------------------ | Branch (34:6): [True: 73, False: 792] ------------------ 35| 73| ndpi_bitmap64_fuse_compress(b); 36| | 37| | /* "Random" search */ 38| 865| num_iteration = fuzzed_data.ConsumeIntegral(); 39| 21.2k| for (i = 0; i < num_iteration; i++) { ------------------ | Branch (39:15): [True: 20.4k, False: 865] ------------------ 40| 20.4k| value = fuzzed_data.ConsumeIntegral(); 41| | 42| 20.4k| ndpi_bitmap64_fuse_isset(b, value); 43| 20.4k| } 44| | /* Search of an added entry */ 45| 865| if (is_added) { ------------------ | Branch (45:7): [True: 449, False: 416] ------------------ 46| 449| ndpi_bitmap64_fuse_isset(b, value_added); 47| 449| } 48| | 49| 865| ndpi_bitmap64_fuse_size(b); 50| | 51| 865| ndpi_bitmap64_fuse_free(b); 52| | 53| 865| return 0; 54| 865|} ndpi_bitmap64_fuse_alloc: 46| 865|ndpi_bitmap64_fuse* ndpi_bitmap64_fuse_alloc() { 47| 865| ndpi_bitmap64_fuse_t *rc = (ndpi_bitmap64_fuse_t*)ndpi_malloc(sizeof(ndpi_bitmap64_fuse_t)); 48| | 49| 865| if(!rc) return(rc); ------------------ | Branch (49:6): [True: 25, False: 840] ------------------ 50| | 51| 840| rc->num_allocated_entries = NDPI_BITMAP64_FUSE_REALLOC_SIZE, rc->num_used_entries = 0; ------------------ | | 33| 840|#define NDPI_BITMAP64_FUSE_REALLOC_SIZE 4096 ------------------ 52| 840| if((rc->entries = (u_int64_t*)ndpi_calloc(rc->num_allocated_entries, sizeof(u_int64_t))) == NULL) { ------------------ | Branch (52:6): [True: 28, False: 812] ------------------ 53| 28| ndpi_free(rc); 54| 28| return(NULL); 55| 28| } 56| | 57| 812| rc->is_compressed = false; 58| | 59| 812| return((ndpi_bitmap64_fuse*)rc); 60| 840|} ndpi_bitmap64_fuse_compress: 75| 1.69k|bool ndpi_bitmap64_fuse_compress(ndpi_bitmap64_fuse *_b) { 76| 1.69k| ndpi_bitmap64_fuse_t *b = (ndpi_bitmap64_fuse_t*)_b; 77| 1.69k| u_int32_t i; 78| | 79| 1.69k| if(!b) ------------------ | Branch (79:6): [True: 32, False: 1.66k] ------------------ 80| 32| return(false); 81| | 82| 1.66k| if(b->is_compressed) ------------------ | Branch (82:6): [True: 7, False: 1.65k] ------------------ 83| 7| return(true); 84| | 85| 1.65k| if(b->num_used_entries > 0) { ------------------ | Branch (85:6): [True: 1.04k, False: 616] ------------------ 86| 1.04k| if(b->num_used_entries > 1) ------------------ | Branch (86:8): [True: 978, False: 64] ------------------ 87| 978| qsort(b->entries, b->num_used_entries, 88| 978| sizeof(u_int64_t), 89| 978| ndpi_bitmap64_fuse_entry_compare); 90| | 91| | /* Now remove duplicates */ 92| 1.04k| u_int64_t old_value = b->entries[0], new_len = 1; 93| | 94| 22.7M| for(i=1; inum_used_entries; i++) { ------------------ | Branch (94:14): [True: 22.7M, False: 1.04k] ------------------ 95| 22.7M| if(b->entries[i] != old_value) { ------------------ | Branch (95:10): [True: 2.51M, False: 20.2M] ------------------ 96| 2.51M| if(new_len != i) ------------------ | Branch (96:5): [True: 1.36M, False: 1.14M] ------------------ 97| 1.36M| memcpy(&b->entries[new_len], &b->entries[i], sizeof(u_int64_t)); 98| | 99| 2.51M| old_value = b->entries[i]; 100| 2.51M| new_len++; 101| 20.2M| } else { 102| |#ifdef PRINT_DUPLICATED_HASHS 103| | printf("Skipping duplicate hash %lluu [id: %u/%u]\n", 104| | b->entries[i].value, i, b->num_used_entries); 105| |#endif 106| 20.2M| } 107| 22.7M| } 108| | 109| 1.04k| b->num_used_entries = b->num_allocated_entries = new_len; 110| 1.04k| } 111| | 112| 1.65k| if(binary_fuse16_allocate(b->num_used_entries, &b->bitmap)) { ------------------ | Branch (112:6): [True: 1.54k, False: 115] ------------------ 113| 1.54k| if(binary_fuse16_populate(b->entries, b->num_used_entries, &b->bitmap)) { ------------------ | Branch (113:8): [True: 941, False: 602] ------------------ 114| 941| ndpi_free(b->entries), b->num_used_entries = b->num_allocated_entries = 0; 115| 941| b->entries = NULL; 116| 941| } else { 117| 602| binary_fuse16_free(&b->bitmap); 118| 602| return(false); 119| 602| } 120| 1.54k| } else { 121| 115| return(false); 122| 115| } 123| | 124| 941| b->is_compressed = true; 125| | 126| | return(true); 127| 1.65k|} ndpi_bitmap64_fuse_set: 131| 22.5M|bool ndpi_bitmap64_fuse_set(ndpi_bitmap64_fuse *_b, u_int64_t value) { 132| 22.5M| ndpi_bitmap64_fuse_t *b = (ndpi_bitmap64_fuse_t*)_b; 133| | 134| 22.5M| if(!b) ------------------ | Branch (134:6): [True: 787k, False: 21.7M] ------------------ 135| 787k| return(false); 136| | 137| 21.7M| if(b->is_compressed) { ------------------ | Branch (137:6): [True: 232, False: 21.7M] ------------------ 138| | /* 139| | We need to discard the filter and start over as this 140| | datastructure is immutable 141| | */ 142| | 143| 232| binary_fuse16_free(&b->bitmap); 144| | /* No need to call b->is_compressed = false; as it will be set below */ 145| 232| } 146| | 147| 21.7M| if(b->num_used_entries >= b->num_allocated_entries) { ------------------ | Branch (147:6): [True: 5.59k, False: 21.7M] ------------------ 148| 5.59k| u_int64_t *rc; 149| 5.59k| u_int32_t new_len = b->num_allocated_entries + NDPI_BITMAP64_FUSE_REALLOC_SIZE; ------------------ | | 33| 5.59k|#define NDPI_BITMAP64_FUSE_REALLOC_SIZE 4096 ------------------ 150| | 151| 5.59k| rc = (u_int64_t*)ndpi_realloc(b->entries, 152| 5.59k| sizeof(u_int64_t)*new_len); 153| 5.59k| if(rc == NULL) { ------------------ | Branch (153:8): [True: 376, False: 5.22k] ------------------ 154| 376| b->is_compressed = false; 155| 376| return(false); 156| 376| } 157| | 158| 5.22k| b->entries = rc, b->num_allocated_entries = new_len; 159| 5.22k| } 160| | 161| 21.7M| b->entries[b->num_used_entries] = value; 162| 21.7M| b->num_used_entries++, b->is_compressed = false; 163| | 164| | return(true); 165| 21.7M|} ndpi_bitmap64_fuse_isset: 169| 20.8k|bool ndpi_bitmap64_fuse_isset(ndpi_bitmap64_fuse *_b, u_int64_t value) { 170| 20.8k| ndpi_bitmap64_fuse_t *b = (ndpi_bitmap64_fuse_t*)_b; 171| | 172| 20.8k| if(!b) ------------------ | Branch (172:6): [True: 1.66k, False: 19.2k] ------------------ 173| 1.66k| return(false); 174| | 175| 19.2k| if(!b->is_compressed) { ------------------ | Branch (175:6): [True: 709, False: 18.4k] ------------------ 176| 709| if(!ndpi_bitmap64_fuse_compress(b)) ------------------ | Branch (176:8): [True: 368, False: 341] ------------------ 177| 368| return(false); /* Compresssion failed */ 178| 709| } 179| | 180| 18.8k| return(binary_fuse16_contain(value, &b->bitmap)); 181| 19.2k|} ndpi_bitmap64_fuse_free: 185| 865|void ndpi_bitmap64_fuse_free(ndpi_bitmap64_fuse *_b) { 186| 865| ndpi_bitmap64_fuse_t *b = (ndpi_bitmap64_fuse_t*)_b; 187| | 188| 865| if(!b) ------------------ | Branch (188:6): [True: 53, False: 812] ------------------ 189| 53| return; 190| | 191| 812| if(b->entries) ndpi_free(b->entries); ------------------ | Branch (191:6): [True: 103, False: 709] ------------------ 192| | 193| 812| if(b->is_compressed) ------------------ | Branch (193:6): [True: 709, False: 103] ------------------ 194| 709| binary_fuse16_free(&b->bitmap); 195| | 196| 812| ndpi_free(b); 197| 812|} ndpi_bitmap64_fuse_size: 201| 865|u_int32_t ndpi_bitmap64_fuse_size(ndpi_bitmap64_fuse *_b) { 202| 865| ndpi_bitmap64_fuse_t *b = (ndpi_bitmap64_fuse_t*)_b; 203| | 204| 865| if(!b) return(0); ------------------ | Branch (204:6): [True: 53, False: 812] ------------------ 205| | 206| 812| if(!b->is_compressed) { ------------------ | Branch (206:6): [True: 423, False: 389] ------------------ 207| 423| if(!ndpi_bitmap64_fuse_compress(b)) ------------------ | Branch (207:8): [True: 103, False: 320] ------------------ 208| 103| return(0); /* Compresssion failed */ 209| 423| } 210| | 211| 709| return(sizeof(ndpi_bitmap64_fuse) + binary_fuse16_size_in_bytes(&b->bitmap)); 212| 812|} ndpi_bitmap64_fuse.c:ndpi_bitmap64_fuse_entry_compare: 64| 203M|static int ndpi_bitmap64_fuse_entry_compare(const void *_a, const void *_b) { 65| 203M| u_int64_t *a = (u_int64_t*)_a, *b = (u_int64_t*)_b; 66| | 67| 203M| if(*a < *b) return -1; ------------------ | Branch (67:6): [True: 18.1M, False: 185M] ------------------ 68| 185M| else if(*a > *b) return 1; ------------------ | Branch (68:11): [True: 31.9M, False: 153M] ------------------ 69| 153M| else return 0; 70| 203M|} ndpi_set_memory_alloction_functions: 52| 865| void (*__ndpi_flow_free)(void *ptr)) { 53| | 54| | /* We can't log here */ 55| | 56| 865| if(__ndpi_malloc && __ndpi_free && ------------------ | Branch (56:6): [True: 865, False: 0] | Branch (56:23): [True: 865, False: 0] ------------------ 57| 865| __ndpi_calloc && __ndpi_realloc) { ------------------ | Branch (57:6): [True: 865, False: 0] | Branch (57:23): [True: 865, False: 0] ------------------ 58| 865| _ndpi_malloc = __ndpi_malloc; 59| 865| _ndpi_free = __ndpi_free; 60| 865| _ndpi_calloc = __ndpi_calloc; 61| 865| _ndpi_realloc = __ndpi_realloc; 62| 865| } 63| 865| if(__ndpi_aligned_malloc && __ndpi_aligned_free) { ------------------ | Branch (63:6): [True: 0, False: 865] | Branch (63:31): [True: 0, False: 0] ------------------ 64| 0| _ndpi_aligned_malloc = __ndpi_aligned_malloc; 65| 0| _ndpi_aligned_free = __ndpi_aligned_free; 66| 0| } 67| 865| if(__ndpi_flow_malloc && __ndpi_flow_free) { ------------------ | Branch (67:6): [True: 865, False: 0] | Branch (67:28): [True: 865, False: 0] ------------------ 68| 865| _ndpi_flow_malloc = __ndpi_flow_malloc; 69| 865| _ndpi_flow_free = __ndpi_flow_free; 70| 865| } 71| 865|} ndpi_malloc: 81| 5.49k|void *ndpi_malloc(size_t size) { 82| 5.49k| __sync_fetch_and_add(&ndpi_tot_allocated_memory, size); 83| 5.49k| return(_ndpi_malloc ? _ndpi_malloc(size) : malloc(size)); ------------------ | Branch (83:10): [True: 5.49k, False: 0] ------------------ 84| 5.49k|} ndpi_calloc: 88| 7.12k|void *ndpi_calloc(size_t nmemb, size_t size) { 89| 7.12k| __sync_fetch_and_add(&ndpi_tot_allocated_memory, nmemb * size); 90| 7.12k| return(_ndpi_calloc ? _ndpi_calloc(nmemb, size) : calloc(nmemb, size)); ------------------ | Branch (90:10): [True: 7.12k, False: 0] ------------------ 91| 7.12k|} ndpi_free: 95| 12.6k|void ndpi_free(void *ptr) { 96| 12.6k| _ndpi_free ? _ndpi_free(ptr) : free(ptr); ------------------ | Branch (96:3): [True: 12.6k, False: 0] ------------------ 97| 12.6k|} ndpi_realloc: 101| 5.59k|void *ndpi_realloc(void *ptr, size_t size) { 102| 5.59k| __sync_fetch_and_add(&ndpi_tot_allocated_memory, size); 103| 5.59k| return(_ndpi_realloc ? _ndpi_realloc(ptr, size) : realloc(ptr, size)); ------------------ | Branch (103:10): [True: 5.59k, False: 0] ------------------ 104| 5.59k|} ndpi_bitmap64_fuse.c:binary_fuse16_allocate: 502| 1.65k| binary_fuse16_t *filter) { 503| 1.65k| uint32_t arity = 3; 504| 1.65k| filter->SegmentLength = size == 0 ? 4 : binary_fuse_calculate_segment_length(arity, size); ------------------ | Branch (504:27): [True: 616, False: 1.04k] ------------------ 505| 1.65k| if (filter->SegmentLength > 262144) { ------------------ | Branch (505:7): [True: 0, False: 1.65k] ------------------ 506| 0| filter->SegmentLength = 262144; 507| 0| } 508| 1.65k| filter->SegmentLengthMask = filter->SegmentLength - 1; 509| 1.65k| double sizeFactor = size <= 1 ? 0 : binary_fuse_calculate_size_factor(arity, size); ------------------ | Branch (509:23): [True: 684, False: 974] ------------------ 510| 1.65k| uint32_t capacity = (uint32_t)(round((double)size * sizeFactor)); 511| 1.65k| uint32_t initSegmentCount = 512| 1.65k| (capacity + filter->SegmentLength - 1) / filter->SegmentLength - 513| 1.65k| (arity - 1); 514| 1.65k| filter->ArrayLength = (initSegmentCount + arity - 1) * filter->SegmentLength; 515| 1.65k| filter->SegmentCount = 516| 1.65k| (filter->ArrayLength + filter->SegmentLength - 1) / filter->SegmentLength; 517| 1.65k| if (filter->SegmentCount <= arity - 1) { ------------------ | Branch (517:7): [True: 997, False: 661] ------------------ 518| 997| filter->SegmentCount = 1; 519| 997| } else { 520| 661| filter->SegmentCount = filter->SegmentCount - (arity - 1); 521| 661| } 522| 1.65k| filter->ArrayLength = 523| 1.65k| (filter->SegmentCount + arity - 1) * filter->SegmentLength; 524| 1.65k| filter->SegmentCountLength = filter->SegmentCount * filter->SegmentLength; 525| 1.65k| filter->Fingerprints = (uint16_t*)ndpi_calloc(filter->ArrayLength, sizeof(uint16_t)); 526| | return filter->Fingerprints != NULL; 527| 1.65k|} ndpi_bitmap64_fuse.c:binary_fuse_calculate_segment_length: 178| 1.04k| uint32_t size) { 179| | // These parameters are very sensitive. Replacing 'floor' by 'round' can 180| | // substantially affect the construction time. 181| 1.04k| if (arity == 3) { ------------------ | Branch (181:7): [True: 1.04k, False: 0] ------------------ 182| 1.04k| return ((uint32_t)1) << (int)(floor(log((double)(size)) / log(3.33) + 2.25)); 183| 1.04k| } else if (arity == 4) { ------------------ | Branch (183:14): [True: 0, False: 0] ------------------ 184| 0| return ((uint32_t)1) << (int)(floor(log((double)(size)) / log(2.91) - 0.5)); 185| 0| } else { 186| 0| return 65536; 187| 0| } 188| 1.04k|} ndpi_bitmap64_fuse.c:binary_fuse_calculate_size_factor: 198| 974| uint32_t size) { 199| 974| if (arity == 3) { ------------------ | Branch (199:7): [True: 974, False: 0] ------------------ 200| 974| return binary_fuse_max(1.125, 0.875 + 0.25 * log(1000000.0) / log((double)size)); 201| 974| } else if (arity == 4) { ------------------ | Branch (201:14): [True: 0, False: 0] ------------------ 202| 0| return binary_fuse_max(1.075, 0.77 + 0.305 * log(600000.0) / log((double)size)); 203| 0| } else { 204| 0| return 2.0; 205| 0| } 206| 974|} ndpi_bitmap64_fuse.c:binary_fuse_max: 190| 974|static inline double binary_fuse_max(double a, double b) { 191| 974| if (a < b) { ------------------ | Branch (191:7): [True: 974, False: 0] ------------------ 192| 974| return b; 193| 974| } 194| 0| return a; 195| 974|} ndpi_bitmap64_fuse.c:binary_fuse16_populate: 553| 1.54k| binary_fuse16_t *filter) { 554| 1.54k| uint64_t rng_counter = 0x726b2b9d438b9d4d; 555| 1.54k| filter->Seed = binary_fuse_rng_splitmix64(&rng_counter); 556| 1.54k| uint64_t *reverseOrder = (uint64_t *)ndpi_calloc((size + 1), sizeof(uint64_t)); 557| 1.54k| uint32_t capacity = filter->ArrayLength; 558| 1.54k| uint32_t *alone = (uint32_t *)ndpi_malloc(capacity * sizeof(uint32_t)); 559| 1.54k| uint8_t *t2count = (uint8_t *)ndpi_calloc(capacity, sizeof(uint8_t)); 560| 1.54k| uint8_t *reverseH = (uint8_t *)ndpi_malloc(size * sizeof(uint8_t)); 561| 1.54k| uint64_t *t2hash = (uint64_t *)ndpi_calloc(capacity, sizeof(uint64_t)); 562| | 563| 1.54k| uint32_t blockBits = 1; 564| 2.30k| while (((uint32_t)1 << blockBits) < filter->SegmentCount) { ------------------ | Branch (564:10): [True: 760, False: 1.54k] ------------------ 565| 760| blockBits += 1; 566| 760| } 567| 1.54k| uint32_t block = ((uint32_t)1 << blockBits); 568| 1.54k| uint32_t *startPos = (uint32_t *)ndpi_malloc((1 << blockBits) * sizeof(uint32_t)); 569| 1.54k| uint32_t h012[5]; 570| | 571| 1.54k| if ((alone == NULL) || (t2count == NULL) || (reverseH == NULL) || ------------------ | Branch (571:7): [True: 95, False: 1.44k] | Branch (571:26): [True: 132, False: 1.31k] | Branch (571:47): [True: 95, False: 1.22k] ------------------ 572| 1.22k| (t2hash == NULL) || (reverseOrder == NULL) || (startPos == NULL)) { ------------------ | Branch (572:7): [True: 81, False: 1.14k] | Branch (572:27): [True: 97, False: 1.04k] | Branch (572:53): [True: 102, False: 941] ------------------ 573| 602| ndpi_free(alone); 574| 602| ndpi_free(t2count); 575| 602| ndpi_free(reverseH); 576| 602| ndpi_free(t2hash); 577| 602| ndpi_free(reverseOrder); 578| 602| ndpi_free(startPos); 579| 602| return false; 580| 602| } 581| 941| reverseOrder[size] = 1; 582| 941| int loop; 583| 2.22k| for (loop = 0; true; ++loop) { ------------------ | Branch (583:18): [True: 2.22k, Folded] ------------------ 584| 2.22k| if (loop + 1 > XOR_MAX_ITERATIONS) { ------------------ | | 13| 2.22k| 100 // probability of success should always be > 0.5 so 100 iterations is ------------------ | Branch (584:9): [True: 2, False: 2.22k] ------------------ 585| | // The probability of this happening is lower than the 586| | // the cosmic-ray probability (i.e., a cosmic ray corrupts your system), 587| | // but if it happens, we just fill the fingerprint with ones which 588| | // will flag all possible keys as 'possible', ensuring a correct result. 589| 2| memset(filter->Fingerprints, ~0, filter->ArrayLength * sizeof(uint16_t)); 590| 2| ndpi_free(alone); 591| 2| ndpi_free(t2count); 592| 2| ndpi_free(reverseH); 593| 2| ndpi_free(t2hash); 594| 2| ndpi_free(reverseOrder); 595| 2| ndpi_free(startPos); 596| 2| return true; 597| 2| } 598| | 599| 2.22k| uint32_t i; 600| 21.4k| for (i = 0; i < block; i++) { ------------------ | Branch (600:17): [True: 19.2k, False: 2.22k] ------------------ 601| | // important : i * size would overflow as a 32-bit number in some 602| | // cases. 603| 19.2k| startPos[i] = ((uint64_t)i * size) >> blockBits; 604| 19.2k| } 605| | 606| 2.22k| uint64_t maskblock = block - 1; 607| 10.9M| for (i = 0; i < size; i++) { ------------------ | Branch (607:17): [True: 10.9M, False: 2.22k] ------------------ 608| 10.9M| uint64_t hash = binary_fuse_murmur64(keys[i] + filter->Seed); 609| 10.9M| uint64_t segment_index = hash >> (64 - blockBits); 610| 11.7M| while (reverseOrder[startPos[segment_index]] != 0) { ------------------ | Branch (610:14): [True: 842k, False: 10.9M] ------------------ 611| 842k| segment_index++; 612| 842k| segment_index &= maskblock; 613| 842k| } 614| 10.9M| reverseOrder[startPos[segment_index]] = hash; 615| 10.9M| startPos[segment_index]++; 616| 10.9M| } 617| 2.22k| int error = 0; 618| 2.22k| uint32_t duplicates = 0; 619| 10.9M| for (i = 0; i < size; i++) { ------------------ | Branch (619:17): [True: 10.9M, False: 2.22k] ------------------ 620| 10.9M| uint64_t hash = reverseOrder[i]; 621| 10.9M| uint32_t h0 = binary_fuse16_hash(0, hash, filter); 622| 10.9M| t2count[h0] += 4; 623| 10.9M| t2hash[h0] ^= hash; 624| 10.9M| uint32_t h1= binary_fuse16_hash(1, hash, filter); 625| 10.9M| t2count[h1] += 4; 626| 10.9M| t2count[h1] ^= 1; 627| 10.9M| t2hash[h1] ^= hash; 628| 10.9M| uint32_t h2 = binary_fuse16_hash(2, hash, filter); 629| 10.9M| t2count[h2] += 4; 630| 10.9M| t2hash[h2] ^= hash; 631| 10.9M| t2count[h2] ^= 2; 632| 10.9M| if ((t2hash[h0] & t2hash[h1] & t2hash[h2]) == 0) { ------------------ | Branch (632:11): [True: 2.43k, False: 10.9M] ------------------ 633| 2.43k| if (((t2hash[h0] == 0) && (t2count[h0] == 8)) ------------------ | Branch (633:16): [True: 0, False: 2.43k] | Branch (633:37): [True: 0, False: 0] ------------------ 634| 2.43k| || ((t2hash[h1] == 0) && (t2count[h1] == 8)) ------------------ | Branch (634:16): [True: 0, False: 2.43k] | Branch (634:37): [True: 0, False: 0] ------------------ 635| 2.43k| || ((t2hash[h2] == 0) && (t2count[h2] == 8))) { ------------------ | Branch (635:16): [True: 0, False: 2.43k] | Branch (635:37): [True: 0, False: 0] ------------------ 636| 0| duplicates += 1; 637| 0| t2count[h0] -= 4; 638| 0| t2hash[h0] ^= hash; 639| 0| t2count[h1] -= 4; 640| 0| t2count[h1] ^= 1; 641| 0| t2hash[h1] ^= hash; 642| 0| t2count[h2] -= 4; 643| 0| t2count[h2] ^= 2; 644| 0| t2hash[h2] ^= hash; 645| 0| } 646| 2.43k| } 647| 10.9M| error = (t2count[h0] < 4) ? 1 : error; ------------------ | Branch (647:15): [True: 0, False: 10.9M] ------------------ 648| 10.9M| error = (t2count[h1] < 4) ? 1 : error; ------------------ | Branch (648:15): [True: 0, False: 10.9M] ------------------ 649| 10.9M| error = (t2count[h2] < 4) ? 1 : error; ------------------ | Branch (649:15): [True: 0, False: 10.9M] ------------------ 650| 10.9M| } 651| 2.22k| if(error) { ------------------ | Branch (651:8): [True: 0, False: 2.22k] ------------------ 652| 0| memset(reverseOrder, 0, sizeof(uint64_t) * size); 653| 0| memset(t2count, 0, sizeof(uint8_t) * capacity); 654| 0| memset(t2hash, 0, sizeof(uint64_t) * capacity); 655| 0| filter->Seed = binary_fuse_rng_splitmix64(&rng_counter); 656| 0| continue; 657| 0| } 658| | 659| | // End of key addition 660| 2.22k| uint32_t Qsize = 0; 661| | // Add sets with one key to the queue. 662| 13.7M| for (i = 0; i < capacity; i++) { ------------------ | Branch (662:17): [True: 13.7M, False: 2.22k] ------------------ 663| 13.7M| alone[Qsize] = i; 664| 13.7M| Qsize += ((t2count[i] >> 2) == 1) ? 1 : 0; ------------------ | Branch (664:16): [True: 2.98M, False: 10.7M] ------------------ 665| 13.7M| } 666| 2.22k| uint32_t stacksize = 0; 667| 8.09M| while (Qsize > 0) { ------------------ | Branch (667:12): [True: 8.09M, False: 2.22k] ------------------ 668| 8.09M| Qsize--; 669| 8.09M| uint32_t index = alone[Qsize]; 670| 8.09M| if ((t2count[index] >> 2) == 1) { ------------------ | Branch (670:11): [True: 7.35M, False: 743k] ------------------ 671| 7.35M| uint64_t hash = t2hash[index]; 672| | 673| | //h012[0] = binary_fuse16_hash(0, hash, filter); 674| 7.35M| h012[1] = binary_fuse16_hash(1, hash, filter); 675| 7.35M| h012[2] = binary_fuse16_hash(2, hash, filter); 676| 7.35M| h012[3] = binary_fuse16_hash(0, hash, filter); // == h012[0]; 677| 7.35M| h012[4] = h012[1]; 678| 7.35M| uint8_t found = t2count[index] & 3; 679| 7.35M| reverseH[stacksize] = found; 680| 7.35M| reverseOrder[stacksize] = hash; 681| 7.35M| stacksize++; 682| 7.35M| uint32_t other_index1 = h012[found + 1]; 683| 7.35M| alone[Qsize] = other_index1; 684| 7.35M| Qsize += ((t2count[other_index1] >> 2) == 2 ? 1 : 0); ------------------ | Branch (684:19): [True: 2.55M, False: 4.79M] ------------------ 685| | 686| 7.35M| t2count[other_index1] -= 4; 687| 7.35M| t2count[other_index1] ^= binary_fuse_mod3(found + 1); 688| 7.35M| t2hash[other_index1] ^= hash; 689| | 690| 7.35M| uint32_t other_index2 = h012[found + 2]; 691| 7.35M| alone[Qsize] = other_index2; 692| 7.35M| Qsize += ((t2count[other_index2] >> 2) == 2 ? 1 : 0); ------------------ | Branch (692:19): [True: 2.55M, False: 4.79M] ------------------ 693| 7.35M| t2count[other_index2] -= 4; 694| 7.35M| t2count[other_index2] ^= binary_fuse_mod3(found + 2); 695| 7.35M| t2hash[other_index2] ^= hash; 696| 7.35M| } 697| 8.09M| } 698| 2.22k| if (stacksize + duplicates == size) { ------------------ | Branch (698:9): [True: 939, False: 1.28k] ------------------ 699| | // success 700| 939| size = stacksize; 701| 939| break; 702| 939| } 703| 1.28k| memset(reverseOrder, 0, sizeof(uint64_t) * size); 704| 1.28k| memset(t2count, 0, sizeof(uint8_t) * capacity); 705| 1.28k| memset(t2hash, 0, sizeof(uint64_t) * capacity); 706| 1.28k| filter->Seed = binary_fuse_rng_splitmix64(&rng_counter); 707| 1.28k| } 708| | 709| 939| uint32_t i; 710| 1.49M| for ( i = size - 1; i < size; i--) { ------------------ | Branch (710:23): [True: 1.49M, False: 939] ------------------ 711| | // the hash of the key we insert next 712| 1.49M| uint64_t hash = reverseOrder[i]; 713| 1.49M| uint16_t xor2 = binary_fuse16_fingerprint(hash); 714| 1.49M| uint8_t found = reverseH[i]; 715| 1.49M| h012[0] = binary_fuse16_hash(0, hash, filter); 716| 1.49M| h012[1] = binary_fuse16_hash(1, hash, filter); 717| 1.49M| h012[2] = binary_fuse16_hash(2, hash, filter); 718| 1.49M| h012[3] = h012[0]; 719| 1.49M| h012[4] = h012[1]; 720| 1.49M| filter->Fingerprints[h012[found]] = xor2 ^ 721| 1.49M| filter->Fingerprints[h012[found + 1]] ^ 722| 1.49M| filter->Fingerprints[h012[found + 2]]; 723| 1.49M| } 724| 939| ndpi_free(alone); 725| 939| ndpi_free(t2count); 726| 939| ndpi_free(reverseH); 727| 939| ndpi_free(t2hash); 728| 939| ndpi_free(reverseOrder); 729| 939| ndpi_free(startPos); 730| | return true; 731| 941|} ndpi_bitmap64_fuse.c:binary_fuse_rng_splitmix64: 51| 2.83k|static inline uint64_t binary_fuse_rng_splitmix64(uint64_t *seed) { 52| 2.83k| uint64_t z = (*seed += UINT64_C(0x9E3779B97F4A7C15)); 53| 2.83k| z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9); 54| | z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB); 55| 2.83k| return z ^ (z >> 31); 56| 2.83k|} ndpi_bitmap64_fuse.c:binary_fuse_murmur64: 20| 10.9M|static inline uint64_t binary_fuse_murmur64(uint64_t h) { 21| 10.9M| h ^= h >> 33; 22| 10.9M| h *= UINT64_C(0xff51afd7ed558ccd); 23| 10.9M| h ^= h >> 33; 24| | h *= UINT64_C(0xc4ceb9fe1a85ec53); 25| 10.9M| h ^= h >> 33; 26| 10.9M| return h; 27| 10.9M|} ndpi_bitmap64_fuse.c:binary_fuse16_hash: 476| 59.2M| const binary_fuse16_t *filter) { 477| 59.2M| uint64_t h = binary_fuse_mulhi(hash, filter->SegmentCountLength); 478| 59.2M| h += (uint64_t)index * filter->SegmentLength; 479| | // keep the lower 36 bits 480| 59.2M| uint64_t hh = hash & ((1ULL << 36) - 1); 481| | // index 0: right shift by 36; index 1: right shift by 18; index 2: no shift 482| 59.2M| h ^= (size_t)((hh >> (36 - 18 * index)) & filter->SegmentLengthMask); 483| 59.2M| return h; 484| 59.2M|} ndpi_bitmap64_fuse.c:binary_fuse_mulhi: 71| 59.2M|static inline uint64_t binary_fuse_mulhi(uint64_t a, uint64_t b) { 72| 59.2M| return ((__uint128_t)a * b) >> 64; 73| 59.2M|} ndpi_bitmap64_fuse.c:binary_fuse_mod3: 256| 14.7M|static inline uint8_t binary_fuse_mod3(uint8_t x) { 257| 14.7M| return x > 2 ? x - 3 : x; ------------------ | Branch (257:12): [True: 8.30M, False: 6.40M] ------------------ 258| 14.7M|} ndpi_bitmap64_fuse.c:binary_fuse16_fingerprint: 460| 1.51M|static inline uint64_t binary_fuse16_fingerprint(uint64_t hash) { 461| 1.51M| return hash ^ (hash >> 32); 462| 1.51M|} ndpi_bitmap64_fuse.c:binary_fuse16_free: 535| 1.54k|static inline void binary_fuse16_free(binary_fuse16_t *filter) { 536| 1.54k| ndpi_free(filter->Fingerprints); 537| | filter->Fingerprints = NULL; 538| 1.54k| filter->Seed = 0; 539| 1.54k| filter->SegmentLength = 0; 540| 1.54k| filter->SegmentLengthMask = 0; 541| 1.54k| filter->SegmentCount = 0; 542| 1.54k| filter->SegmentCountLength = 0; 543| 1.54k| filter->ArrayLength = 0; 544| 1.54k|} ndpi_bitmap64_fuse.c:binary_fuse16_contain: 488| 18.8k| const binary_fuse16_t *filter) { 489| 18.8k| uint64_t hash = binary_fuse_mix_split(key, filter->Seed); 490| 18.8k| uint16_t f = binary_fuse16_fingerprint(hash); 491| 18.8k| binary_hashes_t hashes = binary_fuse16_hash_batch(hash, filter); 492| 18.8k| f ^= filter->Fingerprints[hashes.h0] ^ filter->Fingerprints[hashes.h1] ^ 493| 18.8k| filter->Fingerprints[hashes.h2]; 494| 18.8k| return f == 0; 495| 18.8k|} ndpi_bitmap64_fuse.c:binary_fuse_mix_split: 28| 18.8k|static inline uint64_t binary_fuse_mix_split(uint64_t key, uint64_t seed) { 29| 18.8k| return binary_fuse_murmur64(key + seed); 30| 18.8k|} ndpi_bitmap64_fuse.c:binary_fuse16_hash_batch: 465| 18.8k| const binary_fuse16_t *filter) { 466| 18.8k| uint64_t hi = binary_fuse_mulhi(hash, filter->SegmentCountLength); 467| 18.8k| binary_hashes_t ans; 468| 18.8k| ans.h0 = (uint32_t)hi; 469| 18.8k| ans.h1 = ans.h0 + filter->SegmentLength; 470| 18.8k| ans.h2 = ans.h1 + filter->SegmentLength; 471| 18.8k| ans.h1 ^= (uint32_t)(hash >> 18) & filter->SegmentLengthMask; 472| 18.8k| ans.h2 ^= (uint32_t)(hash)&filter->SegmentLengthMask; 473| 18.8k| return ans; 474| 18.8k|} ndpi_bitmap64_fuse.c:binary_fuse16_size_in_bytes: 530| 709|static inline size_t binary_fuse16_size_in_bytes(const binary_fuse16_t *filter) { 531| 709| return filter->ArrayLength * sizeof(uint16_t) + sizeof(binary_fuse16_t); 532| 709|}