一：应用背景
快速查找海量字符串数组中查找是否包含某个字符串（密文），应用于实验室的分布式破译系统中。
二：实现主要思路
2.1 构造位图(bitMap)，位图的每个bit对应一条密文，即密文映射到位图某个bit上，采用特定的hash函数计算映射地址，位图的大小根据碰撞系数可变化。位图过小，那么越多的明文字符串就会映射到同一个bit上，从而导致查找性能下降。位图查找的时间复杂度为O(1)
2.2 二分查找实现密文字符串的精确查找，二分查找的时间复杂度为O(log(n))
GPU上的上千万条线程会同时暴力计算每一个候选明文，计算出来的密文会和给定的密文进行比较查找，查找过程如下：先通过位图查找该密文字符串是否可能在密文数组中(由于hash函数的碰撞性并不能保证一定性，所以才需要二分查找进行精确的查找)，如果通过位图查找，则进入二分查找阶段进行精确的查找。位图的目的是刷选掉绝大部分不符合的密文字符串，从而减少二分查找的次数，最终提高性能。
三：串行代码
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <malloc.h> #include <string.h> #include <assert.h> #include <sys/time.h> #define BITMAP_MIN 16 #define BITMAP_MAX 24 #include <iostream> using namespace std; void *mymalloc(size_t size); void *myrealloc(void *ptr, size_t oldsz, size_t add); void myfree (void *ptr); static uint32_t generate_bitmaps (const uint32_t digests_cnt, const uint32_t dgst_size, const uint32_t dgst_shifts, uint32_t *digests_buf_ptr, const uint32_t bitmap_mask, const uint32_t bitmap_size, uint32_t *bitmap_a, uint32_t *bitmap_b, uint32_t *bitmap_c, uint32_t *bitmap_d, const uint64_t collisions_max); static uint32_t check (const uint32_t digest[2], uint32_t *bitmap_s1_a, uint32_t *bitmap_s1_b, uint32_t *bitmap_s1_c, uint32_t *bitmap_s1_d, uint32_t *bitmap_s2_a, uint32_t *bitmap_s2_b, uint32_t *bitmap_s2_c, uint32_t *bitmap_s2_d, const uint32_t bitmap_mask, const uint32_t bitmap_shift1, const uint32_t bitmap_shift2); static int find_hash (const uint32_t digest[4], const uint32_t digests_cnt, uint32_t *digests_buf, uint32_t dgst_size); void low_ToBinary(char *in ,uint8_t *out ,int length) { if(strlen(in) != length) { printf("\n low_ToBinary error !! in_len: %d != %d\n",strlen(in),length); return; } for(int i = 0; i < length; i+=2) { unsigned char tmp = 0; if(in[i] >= 'a' && in[i] <= 'z') { tmp += in[i] - 'a' + 10; } else if(in[i] >= 'A' && in[i] <= 'Z') { tmp +=in[i] - 'A' + 10; } else if(in[i] >= '0' && in[i] <= '9') { tmp += in[i] - '0'; } tmp = tmp * 16; if(in[i+1] >= 'a' && in[i+1] <= 'z') { tmp += in[i+1] - 'a' + 10; } else if(in[i+1] >= 'A' && in[i+1] <= 'Z') { tmp +=in[i+1] - 'A' + 10; } else if(in[i+1] >= '0' && in[i+1] <= '9') { tmp += in[i+1] - '0'; } out[i/2] = tmp; } } int fgetl(FILE *fp, char *line_buf) { int line_len = 0; while(!feof(fp)) { const int c = fgetc(fp); if(c == EOF) break; line_buf[line_len] = (char) c; ++line_len; if(line_len == BUFSIZ) --line_len; if(c == '\n') break; } if(line_len == 0) return 0; if(line_buf[line_len - 1] == '\n') { --line_len; line_buf[line_len] = 0x00; } if(line_len == 0) return 0; if(line_buf[line_len - 1] == '\r') { --line_len; line_buf[line_len] = 0x00; } return line_len; } #define INCR_CIPHER 0x100 #define READBUFSIZE 0x100 void readCipherLibrary(const char *cipherLibraryPath, uint32_t *&digests_buf, uint32_t &digests_cnt, uint32_t &hashes_cnt, uint32_t &dgst_size) { assert(cipherLibraryPath != NULL); char readBuf[READBUFSIZE] = {0}; char readLineLen = 0; uint32_t cipher_avail = 0, cipher_cnt = 0; FILE *fp = NULL; if((fp = fopen(cipherLibraryPath, "rb")) == NULL) { printf("ERROR: Open %s failed!\n", cipherLibraryPath); exit(-1); } while(feof(fp) == 0) { memset(readBuf, 0, READBUFSIZE*sizeof(char)); readLineLen = fgetl(fp, readBuf); // printf("readBuf: %s\n", readBuf); if(readLineLen == 0) continue; dgst_size = readLineLen >> 3; if(cipher_avail == cipher_cnt) { if(cipher_avail == 0) { digests_buf = (uint32_t *) mymalloc (INCR_CIPHER * dgst_size * sizeof (uint32_t)); cipher_avail = INCR_CIPHER; }else { digests_buf = (uint32_t *) myrealloc (digests_buf, cipher_avail * dgst_size * sizeof (uint32_t), INCR_CIPHER * dgst_size * sizeof (uint32_t)); cipher_avail += INCR_CIPHER; } } uint8_t cipher[readLineLen]; uint32_t *cipherint = (uint32_t *)cipher; low_ToBinary(readBuf, cipher, readLineLen); for(int j = 0; j < dgst_size; ++j) { digests_buf[dgst_size*cipher_cnt+j] = cipherint[j]; // printf("digests_buf[%d]: %.8x\n", j, digests_buf[dgst_size*cipher_cnt+j]); } ++cipher_cnt; } hashes_cnt = digests_cnt = cipher_cnt; if(fclose(fp) == -1) { printf("ERROR: Close %s failed!\n", cipherLibraryPath); exit(-1); } } int cmp (const void *a, const void *b) { const uint32_t *a_uint32 = (uint32_t *)a; const uint32_t *b_uint32 = (uint32_t *)b; if (a_uint32[3] > b_uint32[3]) return ( 1); if (a_uint32[3] < b_uint32[3]) return (-1); if (a_uint32[2] > b_uint32[2]) return ( 1); if (a_uint32[2] < b_uint32[2]) return (-1); if (a_uint32[1] > b_uint32[1]) return ( 1); if (a_uint32[1] < b_uint32[1]) return (-1); if (a_uint32[0] > b_uint32[0]) return ( 1); if (a_uint32[0] < b_uint32[0]) return (-1); return (0); } int main(int argc, const char *argv[]) { /** * read cipher data **/ uint32_t *digests_buf; // 待匹配的密文库 uint32_t hashes_cnt; // 也是待匹配的密文数？ uint32_t digests_cnt; // 待匹配的密文数 uint32_t dgst_size; // 该算法的密文字数 const char *cipherLibraryPath = "./file/cipher_library.txt"; readCipherLibrary(cipherLibraryPath, digests_buf, digests_cnt, hashes_cnt, dgst_size); qsort(digests_buf, digests_cnt, dgst_size*sizeof(int), cmp); uint32_t digest_tp[dgst_size]; // 模拟计算结果 char *cipher_data = "02A3BE2CB049C2B81E22807AFA2E23F7"; low_ToBinary(cipher_data, (uint8_t *)digest_tp, dgst_size<<3); bool sorted_flag = true; for(int i = 1; i < digests_cnt; ++i) if(digests_buf[(i-1)*dgst_size+3] > digests_buf[(i+1)*dgst_size-1]) sorted_flag = false; if(sorted_flag) printf("Cipher lib is sorted!\n"); else printf("Cipher lib is unsorted!\n"); /** * generate bitmap tables **/ uint32_t bitmap_min = BITMAP_MIN; uint32_t bitmap_max = BITMAP_MAX; const uint32_t bitmap_shift1 = 5; const uint32_t bitmap_shift2 = 13; if (bitmap_max < bitmap_min) bitmap_max = bitmap_min; uint32_t *bitmap_s1_a = (uint32_t *) mymalloc ((1 << bitmap_max) * sizeof (uint32_t)); uint32_t *bitmap_s1_b = (uint32_t *) mymalloc ((1 << bitmap_max) * sizeof (uint32_t)); uint32_t *bitmap_s1_c = (uint32_t *) mymalloc ((1 << bitmap_max) * sizeof (uint32_t)); uint32_t *bitmap_s1_d = (uint32_t *) mymalloc ((1 << bitmap_max) * sizeof (uint32_t)); uint32_t *bitmap_s2_a = (uint32_t *) mymalloc ((1 << bitmap_max) * sizeof (uint32_t)); uint32_t *bitmap_s2_b = (uint32_t *) mymalloc ((1 << bitmap_max) * sizeof (uint32_t)); uint32_t *bitmap_s2_c = (uint32_t *) mymalloc ((1 << bitmap_max) * sizeof (uint32_t)); uint32_t *bitmap_s2_d = (uint32_t *) mymalloc ((1 << bitmap_max) * sizeof (uint32_t)); uint32_t bitmap_bits, bitmap_nums, bitmap_mask, bitmap_size; for (bitmap_bits = bitmap_min; bitmap_bits < bitmap_max; bitmap_bits++) { printf("Generating bitmap tables with %u bits...\n", bitmap_bits); bitmap_nums = 1 << bitmap_bits; bitmap_mask = bitmap_nums - 1; bitmap_size = bitmap_nums * sizeof (uint32_t); if ((hashes_cnt & bitmap_mask) == hashes_cnt){ cout<<"equal!"<<endl; break; } if (generate_bitmaps (digests_cnt, dgst_size, bitmap_shift1, digests_buf, bitmap_mask, bitmap_size, bitmap_s1_a, bitmap_s1_b, bitmap_s1_c, bitmap_s1_d, digests_cnt / 2) == 0x7fffffff){ cout<<"gen1"<<endl; continue;} if (generate_bitmaps (digests_cnt, dgst_size, bitmap_shift2, digests_buf, bitmap_mask, bitmap_size, bitmap_s2_a, bitmap_s2_b, bitmap_s2_c, bitmap_s2_d, digests_cnt / 2) == 0x7fffffff){ cout<<"gen2"<<endl;continue;} cout<<"gen3"<<endl; break; } bitmap_nums = 1 << bitmap_bits; bitmap_mask = bitmap_nums - 1; bitmap_size = bitmap_nums * sizeof (uint32_t); generate_bitmaps (digests_cnt, dgst_size, bitmap_shift1, digests_buf, bitmap_mask, bitmap_size, bitmap_s1_a, bitmap_s1_b, bitmap_s1_c, bitmap_s1_d, -1); generate_bitmaps (digests_cnt, dgst_size, bitmap_shift2, digests_buf, bitmap_mask, bitmap_size, bitmap_s2_a, bitmap_s2_b, bitmap_s2_c, bitmap_s2_d, -1); /** * match cipher **/ struct timeval tv_begin, tv_end; gettimeofday(&tv_begin, NULL); if (check (digest_tp, bitmap_s1_a, bitmap_s1_b, bitmap_s1_c, bitmap_s1_d, bitmap_s2_a, bitmap_s2_b, bitmap_s2_c, bitmap_s2_d, bitmap_mask, bitmap_shift1, bitmap_shift2)) { int hash_pos = find_hash (digest_tp, digests_cnt, digests_buf, dgst_size); if(hash_pos != -1) { printf("Find the cipher: "); for(int i = 0; i < dgst_size; ++i) printf("%.8x ", digests_buf[hash_pos*dgst_size+i]); printf("\n"); }else printf("Can't find the cipher!\n"); }else printf("Can't find the cipher!\n"); gettimeofday(&tv_end, NULL); // printf("Cost time: %f ms\n", (tv_end.tv_sec - tv_begin.tv_sec)*1000 + (tv_end.tv_usec - tv_begin.tv_usec)/1000); printf("Cost time: %f us\n", (tv_end.tv_sec - tv_begin.tv_sec)*1000000 + (tv_end.tv_usec - tv_begin.tv_usec)); myfree(bitmap_s1_a); myfree(bitmap_s1_b); myfree(bitmap_s1_c); myfree(bitmap_s1_d); myfree(bitmap_s2_a); myfree(bitmap_s2_b); myfree(bitmap_s2_c); myfree(bitmap_s2_d); myfree(digests_buf); return 0; } /************************** 内存管理接口 **************************/ #define MSG_ENOMEM "Insufficient memory available" // 申请空间 void *mymalloc(size_t size) { void *p = malloc (size); if (p == NULL) { printf("ERROR: %s", MSG_ENOMEM); exit(-1); } memset (p, 0, size); return (p); } void *myrealloc(void *ptr, size_t oldsz, size_t add) { void *p = realloc (ptr, oldsz + add); if (p == NULL) { printf ("ERROR: %s", MSG_ENOMEM); exit (-1); } memset ((char *) p + oldsz, 0, add); return (p); } // 释放空间 void myfree(void *ptr) { if (ptr == NULL) return; free (ptr); } /**************************** bitmap接口 **************************/ // 构造bitmap static uint32_t generate_bitmaps (const uint32_t digests_cnt, const uint32_t dgst_size, const uint32_t dgst_shifts, uint32_t *digests_buf_ptr, const uint32_t bitmap_mask, const uint32_t bitmap_size, uint32_t *bitmap_a, uint32_t *bitmap_b, uint32_t *bitmap_c, uint32_t *bitmap_d, const uint64_t collisions_max) { uint64_t collisions = 0; const uint32_t dgst_pos0 = 0; const uint32_t dgst_pos1 = 1; const uint32_t dgst_pos2 = 2; const uint32_t dgst_pos3 = 3; memset (bitmap_a, 0, bitmap_size); memset (bitmap_b, 0, bitmap_size); memset (bitmap_c, 0, bitmap_size); memset (bitmap_d, 0, bitmap_size); for (uint32_t i = 0; i < digests_cnt; ++i) { const uint32_t val0 = 1u << (digests_buf_ptr[dgst_pos0] & 0x1f); const uint32_t val1 = 1u << (digests_buf_ptr[dgst_pos1] & 0x1f); const uint32_t val2 = 1u << (digests_buf_ptr[dgst_pos2] & 0x1f); const uint32_t val3 = 1u << (digests_buf_ptr[dgst_pos3] & 0x1f); const uint32_t idx0 = (digests_buf_ptr[dgst_pos0] >> dgst_shifts) & bitmap_mask; const uint32_t idx1 = (digests_buf_ptr[dgst_pos1] >> dgst_shifts) & bitmap_mask; const uint32_t idx2 = (digests_buf_ptr[dgst_pos2] >> dgst_shifts) & bitmap_mask; const uint32_t idx3 = (digests_buf_ptr[dgst_pos3] >> dgst_shifts) & bitmap_mask; digests_buf_ptr += dgst_size; if (bitmap_a[idx0] & val0) ++collisions; if (bitmap_b[idx1] & val1) ++collisions; if (bitmap_c[idx2] & val2) ++collisions; if (bitmap_d[idx3] & val3) ++collisions; bitmap_a[idx0] |= val0; bitmap_b[idx1] |= val1; bitmap_c[idx2] |= val2; bitmap_d[idx3] |= val3; if (collisions >= collisions_max) return 0x7fffffff; } return collisions; } // bitmap查找 static uint32_t check_bitmap (uint32_t *bitmap, const uint32_t bitmap_mask, const uint32_t bitmap_shift, const uint32_t digest) { return (bitmap[(digest >> bitmap_shift) & bitmap_mask] & (1 << (digest & 0x1f))); } // 密文匹配的多bitmap查找 static uint32_t check (const uint32_t digest[4], uint32_t *bitmap_s1_a, uint32_t *bitmap_s1_b, uint32_t *bitmap_s1_c, uint32_t *bitmap_s1_d, uint32_t *bitmap_s2_a, uint32_t *bitmap_s2_b, uint32_t *bitmap_s2_c, uint32_t *bitmap_s2_d, const uint32_t bitmap_mask, const uint32_t bitmap_shift1, const uint32_t bitmap_shift2) { if (check_bitmap(bitmap_s1_a, bitmap_mask, bitmap_shift1, digest[0]) == 0) return (0); if (check_bitmap(bitmap_s1_b, bitmap_mask, bitmap_shift1, digest[1]) == 0) return (0); if (check_bitmap(bitmap_s1_c, bitmap_mask, bitmap_shift1, digest[2]) == 0) return (0); if (check_bitmap(bitmap_s1_d, bitmap_mask, bitmap_shift1, digest[3]) == 0) return (0); if (check_bitmap(bitmap_s2_a, bitmap_mask, bitmap_shift2, digest[0]) == 0) return (0); if (check_bitmap(bitmap_s2_b, bitmap_mask, bitmap_shift2, digest[1]) == 0) return (0); if (check_bitmap(bitmap_s2_c, bitmap_mask, bitmap_shift2, digest[2]) == 0) return (0); if (check_bitmap(bitmap_s2_d, bitmap_mask, bitmap_shift2, digest[3]) == 0) return (0); return (1); } /**************************** 密文匹配接口 **************************/ #define DGST_R0 0 #define DGST_R1 1 #define DGST_R2 2 #define DGST_R3 3 // 计算结果与正确密文的大小判断，共二分查找调用 static int hash_comp (const uint32_t d1[4], uint32_t *d2) { if (d1[3] > d2[DGST_R3]) return ( 1); if (d1[3] < d2[DGST_R3]) return (-1); if (d1[2] > d2[DGST_R2]) return ( 1); if (d1[2] < d2[DGST_R2]) return (-1); if (d1[1] > d2[DGST_R1]) return ( 1); if (d1[1] < d2[DGST_R1]) return (-1); if (d1[0] > d2[DGST_R0]) return ( 1); if (d1[0] < d2[DGST_R0]) return (-1); return (0); } // 二分查找接口 static int find_hash (const uint32_t digest[4], const uint32_t digests_cnt, uint32_t *digests_buf, uint32_t dgst_size) { for (uint32_t l = 0, r = digests_cnt; r; r >>= 1) { const uint32_t m = r >> 1; const uint32_t c = l + m; const int cmp = hash_comp (digest, digests_buf + c * dgst_size); if (cmp > 0) { l += m + 1; --r; } if (cmp == 0) return (c); } return (-1); }
