Guest User

Perfect-hashing variant

a guest
Jul 29th, 2015
281
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <string.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4. #include <vector>
  5. #include <string>
  6. #include <algorithm>
  7. #include <smmintrin.h>
  8.  
  9. typedef unsigned int UINT32;
  10.  
  11. UINT32 GetIP(const char *p)
  12. {
  13.     UINT32 dwIP=0,dwIP_Part=0;
  14.     while(true)
  15.     {
  16.         if(p[0] == 0)
  17.         {
  18.             dwIP = (dwIP << 8) | dwIP_Part;
  19.             break;
  20.         }
  21.         if(p[0]=='.')
  22.         {      
  23.             dwIP = (dwIP << 8) | dwIP_Part;                    
  24.             dwIP_Part = 0;
  25.            p++;
  26.         }
  27.         dwIP_Part = (dwIP_Part*10)+(p[0]-'0');
  28.         p++;
  29.     }
  30.     return dwIP;
  31. }
  32.  
  33. //__m128i shuffleTable[65536];/* DEEP MAGIC BEGINS HERE. */
  34.     return (unsigned)_mm_crc32_u32(0,v*0x000020de)>>24;
  35. }
  36.  
  37. UINT32 MyGetIP(const char *str) {
  38.     __m128i input = _mm_lddqu_si128((const __m128i*)str);   //"192.167.1.3"
  39.     //  for (int i = 0; i < 16; i++) printf("%c ", input.m128i_u8[i]); printf("\n");
  40.     __m128i z     = _mm_cmpeq_epi8(input, _mm_setzero_si128());
  41.     int zfill = 31-__builtin_ctz(_mm_movemask_epi8(z));
  42.     input = _mm_sub_epi8(input, _mm_set1_epi8('0'));        //1 9 2 254 1 6 7 254 1 254 3 208 245 0 8 40
  43. //  for (int i = 0; i < 16; i++) printf("%d ", int(input.m128i_u8[i])); printf("\n");
  44.     __m128i cmp = input;                                    //...X...X.X.XX...  (signs)
  45. //  for (int i = 0; i < 16; i++) printf("%c", cmp.m128i_i8[i] < 0 ? 'X' : '.'); printf("\n");
  46.     //uint64_t mask;
  47.     //asm("rex.w pmovmskb %1, %0\n\t" : "=r"(mask) : "x"(cmp));
  48.     uint64_t mask = _mm_movemask_epi8(cmp);            //6792 - magic index
  49.     mask &= 0xFFFFFFFFU >> zfill;
  50.     uint64_t hashmask  = perfecthash(mask);
  51. //  printf("%d\n", mask);
  52.     __m128i shuf = shuffleTable[hashmask];                  //10 -1 -1 -1 8 -1 -1 -1 6 5 4 -1 2 1 0 -1
  53. //  for (int i = 0; i < 16; i++) printf("%d ", int(shuf.m128i_i8[i])); printf("\n");
  54.     __m128i arr = _mm_shuffle_epi8(input, shuf);            //3 0 0 0 | 1 0 0 0 | 7 6 1 0 | 2 9 1 0
  55. //  for (int i = 0; i < 16; i++) printf("%d ", int(arr.m128i_u8[i])); printf("\n");
  56.     __m128i coeffs = _mm_set_epi8(0, 100, 10, 1, 0, 100, 10, 1, 0, 100, 10, 1, 0, 100, 10, 1);
  57.     __m128i prod = _mm_maddubs_epi16(coeffs, arr);          //3 0 | 1 0 | 67 100 | 92 100
  58. //  for (int i = 0; i < 8; i++) printf("%d ", int(prod.m128i_u16[i])); printf("\n");
  59.     prod = _mm_hadd_epi16(prod, prod);                      //3 | 1 | 167 | 192 | ? | ? | ? | ?
  60. //  for (int i = 0; i < 4; i++) printf("%d ", int(prod.m128i_u16[i])); printf("\n");
  61.     __m128i imm = _mm_set_epi8(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6, 4, 2, 0);
  62.     prod = _mm_shuffle_epi8(prod, imm);                     //3 1 167 192 0 0 0 0 0 0 0 0 0 0 0 0
  63. //  for (int i = 0; i < 4; i++) printf("%d ", int(prod.m128i_u8[i])); printf("\n");
  64.     return _mm_extract_epi32(prod, 0);
  65. //  return (UINT32(_mm_extract_epi16(prod, 1)) << 16) + UINT32(_mm_extract_epi16(prod, 0)); //no SSE 4.1
  66. }
  67.  
  68. static const int CNT = 16<<10;
  69.  
  70. int main() {
  71.   printf("%08X\n", MyGetIP("192.167.1.3"));
  72. //  return 0;
  73.  
  74.   std::vector<std::string> samples;
  75.   for (int i = 0; i < CNT; i++) {
  76.     std::string str;
  77.     for (int j = 0; j < 4; j++) {
  78.       if (j) str += '.';
  79.       int x = rand() % 256;
  80.       char qq[16];
  81.       sprintf(qq, "%d", x);
  82.       str += qq;
  83.     }
  84.     samples.push_back(str);
  85.  
  86. //    printf("%s\n", samples[i].c_str());
  87.     auto a = GetIP(samples.back().c_str());
  88.     auto b = MyGetIP(samples.back().c_str());
  89.     if (a != b)
  90.       printf("%s: %08X vs %08X\n", samples[i].c_str(), a, b);
  91.        
  92.   }
  93.  
  94.  
  95. {
  96.   int start = clock();
  97.   int sum = 0;
  98.   for (int i = 0; i < 1<<27; i++) {
  99.       const char *input = samples[i & (CNT-1)].c_str();
  100.       sum += MyGetIP(input);
  101.   }
  102.   int elapsed = clock() - start;
  103.   printf("Time = %0.3lf   (%d)\n", double(elapsed) / CLOCKS_PER_SEC, sum);
  104. }
  105. {
  106.   int start = clock();
  107.   int sum = 0;
  108.   for (int i = 0; i < 1<<27; i++) {
  109.       const char *input = samples[i & (CNT-1)].c_str();
  110.       sum += GetIP(input);
  111.   }
  112.   int elapsed = clock() - start;
  113.   printf("Time = %0.3lf   (%d)\n", double(elapsed) / CLOCKS_PER_SEC, sum);
  114. }
  115.  
  116.   return 0;
  117. }
RAW Paste Data