1 /*
2 * This software is Copyright (c) 2015 Sayantan Datta <std2048 at gmail dot com>
3 * and it is hereby released to the general public under the following terms:
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted.
6 * Based on paper 'Perfect Spatial Hashing' by Lefebvre & Hoppe
7 */
8
9 #ifdef HAVE_OPENCL
10
11 #include <stdio.h>
12 #include <stdlib.h>
13 #include <string.h>
14 #include <sys/time.h>
15
16 #include "status.h"
17 #include "misc.h" // error()
18 #include "bt_twister.h"
19 #include "bt_hash_types.h"
20
21 #if _OPENMP > 201107
22 #define MAYBE_PARALLEL_FOR _Pragma("omp for")
23 #define MAYBE_ATOMIC_WRITE _Pragma("omp atomic write")
24 #define MAYBE_ATOMIC_CAPTURE _Pragma("omp atomic capture")
25 #else
26 #define MAYBE_PARALLEL_FOR _Pragma("omp single")
27 #define MAYBE_ATOMIC_WRITE
28 #define MAYBE_ATOMIC_CAPTURE
29 #endif
30
31 typedef struct {
32 /* List of indexes linked to offset_data_idx */
33 unsigned int *hash_location_list;
34 unsigned short collisions;
35 unsigned short iter;
36 unsigned int offset_table_idx;
37 } auxilliary_offset_data;
38
39 /* Interface pointers */
40 static unsigned int (*zero_check_ht)(unsigned int);
41 static void (*assign_ht)(unsigned int, unsigned int);
42 static void (*assign0_ht)(unsigned int);
43 static unsigned int (*calc_ht_idx)(unsigned int, unsigned int);
44 static unsigned int (*get_offset)(unsigned int, unsigned int);
45 static void (*allocate_ht)(unsigned int, unsigned int);
46 static int (*test_tables)(unsigned int, OFFSET_TABLE_WORD *, unsigned int, unsigned int, unsigned int, unsigned int);
47 static unsigned int (*remove_duplicates)(unsigned int, unsigned int, unsigned int);
48 static void *loaded_hashes;
49 static unsigned int hash_type;
50 static unsigned int binary_size_actual;
51
52 static unsigned int num_loaded_hashes;
53
54 unsigned int hash_table_size, shift64_ht_sz, shift128_ht_sz;
55
56 static OFFSET_TABLE_WORD *offset_table;
57 static unsigned int offset_table_size, shift64_ot_sz, shift128_ot_sz;
58 static auxilliary_offset_data *offset_data;
59
60 unsigned long long total_memory_in_bytes;
61
62 static unsigned int verbosity;
63
coprime_check(unsigned int m,unsigned int n)64 static unsigned int coprime_check(unsigned int m,unsigned int n)
65 {
66 unsigned int rem;
67
68 while (n != 0) {
69 rem = m % n;
70 m = n;
71 n = rem;
72 }
73 return m;
74 }
75
release_all_lists()76 static void release_all_lists()
77 {
78 unsigned int i;
79
80 for (i = 0; i < offset_table_size; i++)
81 bt_free((void **)&(offset_data[i].hash_location_list));
82 }
83
bt_malloc(void ** ptr,size_t size)84 int bt_malloc(void **ptr, size_t size)
85 {
86 *ptr = mem_alloc(size);
87 if (*ptr || !size)
88 return 0;
89 return 1;
90 }
91
bt_calloc(void ** ptr,size_t num,size_t size)92 int bt_calloc(void **ptr, size_t num, size_t size)
93 {
94 *ptr = mem_calloc(num, size);
95 if (*ptr || !num)
96 return 0;
97 return 1;
98 }
99
bt_memalign_alloc(void ** ptr,size_t alignment,size_t size)100 int bt_memalign_alloc(void **ptr, size_t alignment, size_t size)
101 {
102 *ptr = mem_alloc_align(size, alignment);
103 if (*ptr || !size)
104 return 0;
105 return 1;
106 }
107
bt_free(void ** ptr)108 void bt_free(void **ptr)
109 {
110 MEM_FREE(*ptr);
111 }
112
bt_error_fn(const char * str,char * file,int line)113 void bt_error_fn(const char *str, char *file, int line)
114 {
115 fprintf(stderr, "%s in file:%s, line:%d.\n", str, file, line);
116 error();
117 }
118
bt_warn_fn(const char * str,char * file,int line)119 void bt_warn_fn(const char *str, char *file, int line)
120 {
121 fprintf(stderr, "%s in file:%s, line:%d.\n", str, file, line);
122 }
123
modulo_op(void * hash,unsigned int N,uint64_t shift64,uint64_t shift128)124 static unsigned int modulo_op(void * hash, unsigned int N, uint64_t shift64, uint64_t shift128)
125 {
126 if (hash_type == 64)
127 return modulo64_31b(*(uint64_t *)hash, N);
128 else if (hash_type == 128)
129 return modulo128_31b(*(uint128_t *)hash, N, shift64);
130 else if (hash_type == 192)
131 return modulo192_31b(*(uint192_t *)hash, N, shift64, shift128);
132 else
133 fprintf(stderr, "modulo op error\n");
134 return 0;
135 }
136
137 /* Exploits the fact that sorting with a bucket is not essential. */
in_place_bucket_sort(unsigned int num_buckets)138 static void in_place_bucket_sort(unsigned int num_buckets)
139 {
140 unsigned int *histogram;
141 unsigned int *histogram_empty;
142 unsigned int *prefix_sum;
143 unsigned int i;
144
145 if (bt_calloc((void **)&histogram, num_buckets + 1, sizeof(unsigned int)))
146 bt_error("Failed to allocate memory: histogram.");
147 if (bt_calloc((void **)&histogram_empty, num_buckets + 1, sizeof(unsigned int)))
148 bt_error("Failed to allocate memory: histogram_empty.");
149 if (bt_calloc((void **)&prefix_sum, num_buckets + 10, sizeof(unsigned int)))
150 bt_error("Failed to allocate memory: prefix_sum.");
151
152 i = 0;
153 while (i < offset_table_size)
154 histogram[num_buckets - offset_data[i++].collisions]++;
155
156 for (i = 1; i <= num_buckets; i++)
157 prefix_sum[i] = prefix_sum[i - 1] + histogram[i - 1];
158
159 i = 0;
160 while (i < prefix_sum[num_buckets]) {
161 unsigned int histogram_index = num_buckets - offset_data[i].collisions;
162 if (i >= prefix_sum[histogram_index] &&
163 histogram_index < num_buckets &&
164 i < prefix_sum[histogram_index + 1]) {
165 histogram_empty[histogram_index]++;
166 i++;
167 }
168 else {
169 auxilliary_offset_data tmp;
170 unsigned int swap_index = prefix_sum[histogram_index] + histogram_empty[histogram_index];
171 histogram_empty[histogram_index]++;
172 tmp = offset_data[i];
173 offset_data[i] = offset_data[swap_index];
174 offset_data[swap_index] = tmp;
175 }
176 }
177
178 bt_free((void **)&histogram);
179 bt_free((void **)&histogram_empty);
180 bt_free((void **)&prefix_sum);
181 }
182
init_tables(unsigned int approx_offset_table_sz,unsigned int approx_hash_table_sz)183 static void init_tables(unsigned int approx_offset_table_sz, unsigned int approx_hash_table_sz)
184 {
185 unsigned int i, max_collisions, offset_data_idx;
186 uint64_t shift128;
187
188 if (verbosity > 1)
189 fprintf(stdout, "\nInitialing Tables...");
190
191 total_memory_in_bytes = 0;
192
193 approx_hash_table_sz |= 1;
194 /* Repeat until two sizes are coprimes */
195 while (coprime_check(approx_offset_table_sz, approx_hash_table_sz) != 1)
196 approx_offset_table_sz++;
197
198 offset_table_size = approx_offset_table_sz;
199 hash_table_size = approx_hash_table_sz;
200
201 if (hash_table_size > 0x7fffffff || offset_table_size > 0x7fffffff)
202 bt_error("Reduce the number of loaded hashes to < 0x7fffffff.");
203
204 shift64_ht_sz = (((1ULL << 63) % hash_table_size) * 2) % hash_table_size;
205 shift64_ot_sz = (((1ULL << 63) % offset_table_size) * 2) % offset_table_size;
206
207 shift128 = (uint64_t)shift64_ht_sz * shift64_ht_sz;
208 shift128_ht_sz = shift128 % hash_table_size;
209
210 shift128 = (uint64_t)shift64_ot_sz * shift64_ot_sz;
211 shift128_ot_sz = shift128 % offset_table_size;
212
213 if (bt_malloc((void **)&offset_table, offset_table_size * sizeof(OFFSET_TABLE_WORD)))
214 bt_error("Failed to allocate memory: offset_table.");
215 total_memory_in_bytes += offset_table_size * sizeof(OFFSET_TABLE_WORD);
216
217 if (bt_malloc((void **)&offset_data, offset_table_size * sizeof(auxilliary_offset_data)))
218 bt_error("Failed to allocate memory: offset_data.");
219 total_memory_in_bytes += offset_table_size * sizeof(auxilliary_offset_data);
220
221 max_collisions = 0;
222 #if _OPENMP
223 #pragma omp parallel private(i, offset_data_idx)
224 #endif
225 {
226 #if _OPENMP
227 #pragma omp for
228 #endif
229 for (i = 0; i < offset_table_size; i++) {
230 //memset(&offset_data[i], 0, sizeof(auxilliary_offset_data));
231 offset_data[i].offset_table_idx = 0;
232 offset_data[i].collisions = 0;
233 offset_data[i].hash_location_list = NULL;
234 offset_data[i].iter = 0;
235 offset_table[i] = 0;
236 }
237 #if _OPENMP
238 #pragma omp barrier
239 #endif
240 /* Build Auxiliary data structure for offset_table. */
241 #if _OPENMP
242 #pragma omp for
243 #endif
244 for (i = 0; i < num_loaded_hashes; i++) {
245 offset_data_idx = modulo_op(loaded_hashes + i * binary_size_actual, offset_table_size, shift64_ot_sz, shift128_ot_sz);
246 #if _OPENMP
247 #pragma omp atomic
248 #endif
249 offset_data[offset_data_idx].collisions++;
250 }
251 #if _OPENMP
252 #pragma omp barrier
253 #pragma omp single
254 #endif
255 for (i = 0; i < offset_table_size; i++)
256 if (offset_data[i].collisions) {
257 if (bt_malloc((void **)&offset_data[i].hash_location_list, offset_data[i].collisions * sizeof(unsigned int)))
258 bt_error("Failed to allocate memory: offset_data[i].hash_location_list.");
259 if (offset_data[i].collisions > max_collisions)
260 max_collisions = offset_data[i].collisions;
261 }
262 #if _OPENMP
263 #pragma omp barrier
264 MAYBE_PARALLEL_FOR
265 #endif
266 for (i = 0; i < num_loaded_hashes; i++) {
267 unsigned int iter;
268 offset_data_idx = modulo_op(loaded_hashes + i * binary_size_actual, offset_table_size, shift64_ot_sz, shift128_ot_sz);
269 #if _OPENMP
270 MAYBE_ATOMIC_WRITE
271 #endif
272 offset_data[offset_data_idx].offset_table_idx = offset_data_idx;
273 #if _OPENMP
274 MAYBE_ATOMIC_CAPTURE
275 #endif
276 iter = offset_data[offset_data_idx].iter++;
277 offset_data[offset_data_idx].hash_location_list[iter] = i;
278 }
279 #if _OPENMP
280 #pragma omp barrier
281 #endif
282 }
283 total_memory_in_bytes += num_loaded_hashes * sizeof(unsigned int);
284
285 //qsort((void *)offset_data, offset_table_size, sizeof(auxilliary_offset_data), qsort_compare);
286 in_place_bucket_sort(max_collisions);
287
288 if (verbosity > 1)
289 fprintf(stdout, "Done\n");
290
291 allocate_ht(num_loaded_hashes, verbosity);
292
293 if (verbosity > 2) {
294 fprintf(stdout, "Offset Table Size %Lf %% of Number of Loaded Hashes.\n", ((long double)offset_table_size / (long double)num_loaded_hashes) * 100.00);
295 fprintf(stdout, "Offset Table Size(in GBs):%Lf\n", ((long double)offset_table_size * sizeof(OFFSET_TABLE_WORD)) / ((long double)1024 * 1024 * 1024));
296 fprintf(stdout, "Offset Table Aux Data Size(in GBs):%Lf\n", ((long double)offset_table_size * sizeof(auxilliary_offset_data)) / ((long double)1024 * 1024 * 1024));
297 fprintf(stdout, "Offset Table Aux List Size(in GBs):%Lf\n", ((long double)num_loaded_hashes * sizeof(unsigned int)) / ((long double)1024 * 1024 * 1024));
298
299 for (i = 0; i < offset_table_size && offset_data[i].collisions; i++)
300 ;
301 fprintf(stdout, "Unused Slots in Offset Table:%Lf %%\n", 100.00 * (long double)(offset_table_size - i) / (long double)(offset_table_size));
302
303 fprintf(stdout, "Total Memory Use(in GBs):%Lf\n", ((long double)total_memory_in_bytes) / ((long double) 1024 * 1024 * 1024));
304 }
305 }
306
check_n_insert_into_hash_table(unsigned int offset,auxilliary_offset_data * ptr,unsigned int * hash_table_idxs,unsigned int * store_hash_modulo_table_sz)307 static unsigned int check_n_insert_into_hash_table(unsigned int offset, auxilliary_offset_data * ptr, unsigned int *hash_table_idxs, unsigned int *store_hash_modulo_table_sz)
308 {
309 unsigned int i;
310
311 i = 0;
312 while (i < ptr->collisions) {
313 hash_table_idxs[i] = store_hash_modulo_table_sz[i] + offset;
314 if (hash_table_idxs[i] >= hash_table_size)
315 hash_table_idxs[i] -= hash_table_size;
316 if (zero_check_ht(hash_table_idxs[i++]))
317 return 0;
318 }
319
320 i = 0;
321 while (i < ptr->collisions) {
322 if (zero_check_ht(hash_table_idxs[i])) {
323 unsigned int j = 0;
324 while (j < i)
325 assign0_ht(hash_table_idxs[j++]);
326 return 0;
327 }
328 assign_ht(hash_table_idxs[i], ptr->hash_location_list[i]);
329 i++;
330 }
331 return 1;
332 }
333
calc_hash_mdoulo_table_size(unsigned int * store,auxilliary_offset_data * ptr)334 static void calc_hash_mdoulo_table_size(unsigned int *store, auxilliary_offset_data * ptr) {
335 unsigned int i = 0;
336
337 while (i < ptr->collisions) {
338 store[i] = modulo_op(loaded_hashes + (ptr->hash_location_list[i]) * binary_size_actual, hash_table_size, shift64_ht_sz, shift128_ht_sz);
339 i++;
340 }
341 }
342
create_tables()343 static unsigned int create_tables()
344 {
345 unsigned int i;
346 unsigned int bitmap = ((1ULL << (sizeof(OFFSET_TABLE_WORD) * 8)) - 1) & 0xFFFFFFFF;
347 unsigned int limit = bitmap % hash_table_size + 1;
348 unsigned int hash_table_idx;
349 unsigned int *store_hash_modulo_table_sz;
350 unsigned int *hash_table_idxs;
351 #ifdef ENABLE_BACKTRACKING
352 OFFSET_TABLE_WORD last_offset;
353 unsigned int backtracking = 0;
354 #endif
355 unsigned int trigger;
356 long double done = 0;
357 struct timeval t;
358
359 if (bt_malloc((void **)&store_hash_modulo_table_sz, offset_data[0].collisions * sizeof(unsigned int)))
360 bt_error("Failed to allocate memory: store_hash_modulo_table_sz.");
361 if (bt_malloc((void **)&hash_table_idxs, offset_data[0].collisions * sizeof(unsigned int)))
362 bt_error("Failed to allocate memory: hash_table_idxs.");
363
364 gettimeofday(&t, NULL);
365
366 seedMT(t.tv_sec + t.tv_usec);
367
368 i = 0;
369 trigger = 0;
370
371 while (offset_data[i].collisions > 1) {
372 OFFSET_TABLE_WORD offset;
373 unsigned int num_iter;
374 unsigned int start_time;
375
376 done += offset_data[i].collisions;
377
378 calc_hash_mdoulo_table_size(store_hash_modulo_table_sz, &offset_data[i]);
379
380 offset = (OFFSET_TABLE_WORD)(randomMT() & bitmap) % hash_table_size;
381
382 #ifdef ENABLE_BACKTRACKING
383 if (backtracking) {
384 offset = (last_offset + 1) % hash_table_size;
385 backtracking = 0;
386 }
387 #endif
388 start_time = status_get_time();
389
390 num_iter = 0;
391 while (!check_n_insert_into_hash_table((unsigned int)offset, &offset_data[i], hash_table_idxs, store_hash_modulo_table_sz) && num_iter < limit) {
392 offset++;
393 if (offset >= hash_table_size) offset = 0;
394 num_iter++;
395 }
396
397 offset_table[offset_data[i].offset_table_idx] = offset;
398
399 if ((trigger & 0xffff) == 0) {
400 trigger = 0;
401 if (verbosity > 0) {
402 fprintf(stdout, "\rProgress:%Lf %%, Number of collisions:%u", done / (long double)num_loaded_hashes * 100.00, offset_data[i].collisions);
403 fflush(stdout);
404 }
405 }
406
407 if (status_get_time() >= start_time + 3) {
408 fprintf(stderr, "\nProgress is too slow!! trying next table size.\n");
409 bt_free((void **)&hash_table_idxs);
410 bt_free((void **)&store_hash_modulo_table_sz);
411 return 0;
412 }
413
414 trigger++;
415
416 if (num_iter == limit) {
417 #ifdef ENABLE_BACKTRACKING
418 if (num_loaded_hashes > 1000000) {
419 unsigned int j, backtrack_steps, iter;
420
421 done -= offset_data[i].collisions;
422 offset_table[offset_data[i].offset_table_idx] = 0;
423
424 backtrack_steps = 1;
425 j = 1;
426 while (j <= backtrack_steps && (int)(i - j) >= 0) {
427 last_offset = offset_table[offset_data[i - j].offset_table_idx];
428 iter = 0;
429 while (iter < offset_data[i - j].collisions) {
430 hash_table_idx =
431 calc_ht_idx(offset_data[i - j].hash_location_list[iter],
432 last_offset);
433 assign0_ht(hash_table_idx);
434 iter++;
435 }
436 offset_table[offset_data[i - j].offset_table_idx] = 0;
437 done -= offset_data[i - j].collisions;
438 j++;
439 }
440 i -= (j - 1);
441 backtracking = 1;
442 continue;
443 }
444 #endif
445 bt_free((void **)&hash_table_idxs);
446 bt_free((void **)&store_hash_modulo_table_sz);
447 return 0;
448 }
449
450 i++;
451 }
452
453 hash_table_idx = 0;
454 while (i < offset_table_size && offset_data[i].collisions > 0) {
455 done++;
456
457 while (hash_table_idx < hash_table_size) {
458 if (!zero_check_ht(hash_table_idx)) {
459 assign_ht(hash_table_idx, offset_data[i].hash_location_list[0]);
460 break;
461 }
462 hash_table_idx++;
463 }
464 offset_table[offset_data[i].offset_table_idx] = get_offset(hash_table_idx, offset_data[i].hash_location_list[0]);
465 if ((trigger & 0xffff) == 0) {
466 trigger = 0;
467 if (verbosity > 0) {
468 fprintf(stdout, "\rProgress:%Lf %%, Number of collisions:%u", done / (long double)num_loaded_hashes * 100.00, offset_data[i].collisions);
469 fflush(stdout);
470 }
471 }
472 trigger++;
473 i++;
474 }
475
476 bt_free((void **)&hash_table_idxs);
477 bt_free((void **)&store_hash_modulo_table_sz);
478
479 return 1;
480 }
481
next_prime(unsigned int num)482 static unsigned int next_prime(unsigned int num)
483 {
484 if (num == 1)
485 return 2;
486 else if (num == 2)
487 return 3;
488 else if (num == 3 || num == 4)
489 return 5;
490 else if (num == 5 || num == 6)
491 return 7;
492 else if (num >= 7 && num <= 9)
493 return 1;
494 /* else if (num == 11 || num == 12)
495 return 13;
496 else if (num >= 13 && num < 17)
497 return 17;
498 else if (num == 17 || num == 18)
499 return 19;
500 else if (num >= 19 && num < 23)
501 return 23;
502 else if (num >= 23 && num < 29)
503 return 29;
504 else if (num == 29 || num == 30 )
505 return 31;
506 else if (num >= 31 && num < 37)
507 return 37;
508 else if (num >= 37 && num < 41)
509 return 41;
510 else if (num == 41 || num == 42 )
511 return 43;
512 else if (num >= 43 && num < 47)
513 return 47;
514 else if (num >= 47 && num < 53)
515 return 53;
516 else if (num >= 53 && num < 59)
517 return 59;
518 else if (num == 59 || num == 60)
519 return 61;
520 else if (num >= 61 && num < 67)
521 return 67;
522 else if (num >= 67 && num < 71)
523 return 71;
524 else if (num == 71 || num == 72)
525 return 73;
526 else if (num >= 73 && num < 79)
527 return 79;
528 else if (num >= 79 && num < 83)
529 return 83;
530 else if (num >= 83 && num < 89)
531 return 89;
532 else if (num >= 89 && num < 97)
533 return 97;
534 else
535 return 1;*/
536 return 1;
537 }
538
create_perfect_hash_table(int htype,void * loaded_hashes_ptr,unsigned int num_ld_hashes,OFFSET_TABLE_WORD ** offset_table_ptr,unsigned int * offset_table_sz_ptr,unsigned int * hash_table_sz_ptr,unsigned int verb)539 unsigned int create_perfect_hash_table(int htype, void *loaded_hashes_ptr,
540 unsigned int num_ld_hashes,
541 OFFSET_TABLE_WORD **offset_table_ptr,
542 unsigned int *offset_table_sz_ptr,
543 unsigned int *hash_table_sz_ptr,
544 unsigned int verb)
545 {
546 long double multiplier_ht, multiplier_ot, inc_ht, inc_ot;
547 unsigned int approx_hash_table_sz, approx_offset_table_sz, i, dupe_remove_ht_sz;
548
549 total_memory_in_bytes = 0;
550
551 hash_type = htype;
552 loaded_hashes = loaded_hashes_ptr;
553 verbosity = verb;
554
555 if (hash_type == 64) {
556 zero_check_ht = zero_check_ht_64;
557 assign_ht = assign_ht_64;
558 assign0_ht = assign0_ht_64;
559 calc_ht_idx = calc_ht_idx_64;
560 get_offset = get_offset_64;
561 allocate_ht = allocate_ht_64;
562 test_tables = test_tables_64;
563 remove_duplicates = remove_duplicates_64;
564 loaded_hashes_64 = (uint64_t *)loaded_hashes;
565 binary_size_actual = 8;
566 if (verbosity > 1)
567 fprintf(stdout, "Using Hash type 64.\n");
568 }
569
570 else if (hash_type == 128) {
571 zero_check_ht = zero_check_ht_128;
572 assign_ht = assign_ht_128;
573 assign0_ht = assign0_ht_128;
574 calc_ht_idx = calc_ht_idx_128;
575 get_offset = get_offset_128;
576 allocate_ht = allocate_ht_128;
577 test_tables = test_tables_128;
578 remove_duplicates = remove_duplicates_128;
579 loaded_hashes_128 = (uint128_t *)loaded_hashes;
580 binary_size_actual = 16;
581 if (verbosity > 1)
582 fprintf(stdout, "Using Hash type 128.\n");
583 }
584
585 else if (hash_type == 192) {
586 zero_check_ht = zero_check_ht_192;
587 assign_ht = assign_ht_192;
588 assign0_ht = assign0_ht_192;
589 calc_ht_idx = calc_ht_idx_192;
590 get_offset = get_offset_192;
591 allocate_ht = allocate_ht_192;
592 test_tables = test_tables_192;
593 remove_duplicates = remove_duplicates_192;
594 loaded_hashes_192 = (uint192_t *)loaded_hashes;
595 binary_size_actual = 24;
596 if (verbosity > 1)
597 fprintf(stdout, "Using Hash type 192.\n");
598 }
599
600 inc_ht = 0.005;
601 inc_ot = 0.05;
602
603 if (num_ld_hashes <= 100) {
604 multiplier_ot = 1.501375173;
605 inc_ht = 0.05;
606 inc_ot = 0.5;
607 dupe_remove_ht_sz = 128;
608 }
609 else if (num_ld_hashes <= 1000) {
610 multiplier_ot = 1.101375173;
611 dupe_remove_ht_sz = 1024;
612 }
613 else if (num_ld_hashes <= 10000) {
614 multiplier_ot = 1.151375173;
615 dupe_remove_ht_sz = 16384;
616 }
617 else if (num_ld_hashes <= 100000) {
618 multiplier_ot = 1.20375173;
619 dupe_remove_ht_sz = 131072;
620 }
621 else if (num_ld_hashes <= 1000000) {
622 multiplier_ot = 1.25375173;
623 dupe_remove_ht_sz = 1048576;
624 }
625 else if (num_ld_hashes <= 10000000) {
626 multiplier_ot = 1.31375173;
627 dupe_remove_ht_sz = 16777216;
628 }
629 else if (num_ld_hashes <= 20000000) {
630 multiplier_ot = 1.35375173;
631 dupe_remove_ht_sz = 33554432;
632 }
633 else if (num_ld_hashes <= 50000000) {
634 multiplier_ot = 1.41375173;
635 dupe_remove_ht_sz = 67108864;
636 }
637 else if (num_ld_hashes <= 110000000) {
638 multiplier_ot = 1.51375173;
639 dupe_remove_ht_sz = 134217728;
640 }
641 else if (num_ld_hashes <= 200000000) {
642 multiplier_ot = 1.61375173;
643 dupe_remove_ht_sz = 134217728 * 2;
644 }
645 else {
646 multiplier_ot = 3.01375173;
647 dupe_remove_ht_sz = 134217728 * 4;
648 }
649 if (num_ld_hashes > 320294464)
650 fprintf(stderr, "This many number of hashes have never been tested before and might not succeed!!\n");
651
652 num_loaded_hashes = remove_duplicates(num_ld_hashes, dupe_remove_ht_sz, verbosity);
653 if (!num_loaded_hashes)
654 bt_error("Failed to remove duplicates.");
655
656 multiplier_ht = 1.001097317;
657
658 approx_offset_table_sz = (((long double)num_loaded_hashes / 4.0) * multiplier_ot + 10.00);
659 approx_hash_table_sz = ((long double)num_loaded_hashes * multiplier_ht);
660
661 i = 0;
662 do {
663 unsigned int temp;
664
665 init_tables(approx_offset_table_sz, approx_hash_table_sz);
666
667 if (create_tables()) {
668 if (verbosity > 0)
669 fprintf(stdout, "\n");
670 break;
671 }
672 if (verbosity > 0)
673 fprintf(stdout, "\n");
674 release_all_lists();
675 bt_free((void **)&offset_data);
676 bt_free((void **)&offset_table);
677 if (hash_type == 64)
678 bt_free((void **)&hash_table_64);
679 else if (hash_type == 128)
680 bt_free((void **)&hash_table_128);
681 else if (hash_type == 192)
682 bt_free((void **)&hash_table_192);
683
684 temp = next_prime(approx_offset_table_sz % 10);
685 approx_offset_table_sz /= 10;
686 approx_offset_table_sz *= 10;
687 approx_offset_table_sz += temp;
688
689 i++;
690
691 if (!(i % 5)) {
692 multiplier_ot += inc_ot;
693 multiplier_ht += inc_ht;
694 approx_offset_table_sz = (((long double)num_loaded_hashes / 4.0) * multiplier_ot + 10.00);
695 approx_hash_table_sz = ((long double)num_loaded_hashes * multiplier_ht);
696 }
697
698 } while(1);
699
700 release_all_lists();
701 bt_free((void **)&offset_data);
702
703 *offset_table_ptr = offset_table;
704 *hash_table_sz_ptr = hash_table_size;
705 *offset_table_sz_ptr = offset_table_size;
706
707 if (!test_tables(num_loaded_hashes, offset_table, offset_table_size, shift64_ot_sz, shift128_ot_sz, verbosity))
708 return 0;
709
710 return num_loaded_hashes;
711 }
712
713 /*static int qsort_compare(const void *p1, const void *p2)
714 {
715 auxilliary_offset_data *a = (auxilliary_offset_data *)p1;
716 auxilliary_offset_data *b = (auxilliary_offset_data *)p2;
717
718 if (a[0].collisions > b[0].collisions) return -1;
719 if (a[0].collisions == b[0].collisions) return 0;
720 return 1;
721 }*/
722
723 #endif
724