API tools faq
paste
Advertisement
stgatilov

Vectorized in-register deduplication

stgatilov
Aug 3rd, 2015
874
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 21.78 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #include <assert.h>
  4. #include <time.h>
  5. #include <string.h>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <tmmintrin.h>  //SSSE3 is required
  9. #ifdef __AVX__
  10.     #include <immintrin.h>
  11. #endif
  12.  
  13. #ifdef _MSC_VER
  14.     #define ALIGN(n) __declspec(align(n))
  15. #else
  16.     #define ALIGN(n) __attribute__((aligned(n)))
  17. #endif
  18.  
  19.  
  20. //============================ Solutions ==============================
  21.  
  22. #define MIN(a, b) ((a) < (b) ? (a) : (b))
  23. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  24.  
  25. static inline void deduplicate4_trivial(const uint32_t *arr, uint32_t *res) {
  26.     res[0] = arr[0];
  27.     res[1] = arr[1];
  28.     res[2] = arr[2];
  29.     res[3] = arr[3];
  30.     //sorting network for 4 numbers, taken from https://en.wikipedia.org/wiki/Sorting_network
  31.     #define CMP(i, j) {\
  32.         uint32_t a = MIN(res[i], res[j]);\
  33.         uint32_t b = MAX(res[i], res[j]);\
  34.         res[i] = a;\
  35.         res[j] = b;\
  36.     }
  37.     CMP(0, 2);
  38.     CMP(1, 3);
  39.     CMP(0, 1);
  40.     CMP(2, 3);
  41.     CMP(1, 2);
  42.     //remove consecutive duplicates
  43.     size_t pos = 1;
  44.     if (res[0] != res[1])
  45.         res[pos++] = res[1];
  46.     if (res[1] != res[2])
  47.         res[pos++] = res[2];
  48.     if (res[2] != res[3])
  49.         res[pos++] = res[3];
  50.     //fill rest with zeros
  51.     while (pos < 4)
  52.         res[pos++] = 0;
  53. }
  54.  
  55. ALIGN(16) unsigned char lookup_bmi_chars[64][16] = {    //1Kb size
  56.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F},
  57.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF},
  58.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF},
  59.     {0x00, 0x01, 0x02, 0x03, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  60.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  61.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  62.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  63.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  64.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  65.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  66.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  67.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  68.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  69.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  70.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  71.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  72.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF},
  73.     {0x00, 0x01, 0x02, 0x03, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  74.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF},
  75.     {0x00, 0x01, 0x02, 0x03, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  76.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  77.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  78.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  79.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  80.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  81.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  82.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  83.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  84.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  85.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  86.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  87.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  88.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  89.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  90.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  91.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  92.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  93.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  94.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  95.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  96.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  97.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  98.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  99.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  100.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  101.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  102.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  103.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  104.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  105.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  106.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  107.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  108.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  109.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  110.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  111.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  112.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  113.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  114.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  115.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  116.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  117.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  118.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  119.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}
  120. };
  121. static __m128i *const lookup_bmi = (__m128i*) &lookup_bmi_chars[0][0];
  122. #ifdef __AVX__
  123. static inline __m128i deduplicate4_ssse3_bmi2(__m128i abcd) {
  124.     __m128i bcda = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(0, 3, 2, 1));
  125.     __m128i cdab = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(1, 0, 3, 2));
  126.     unsigned int mask1 = _mm_movemask_epi8(_mm_cmpeq_epi32(abcd, bcda));
  127.     unsigned int mask2 = _mm_movemask_epi8(_mm_cmpeq_epi32(abcd, cdab));
  128.     unsigned int maskFull = (mask2 << 16U) + mask1;
  129.     //Note: BMI2 instruction used here!
  130.     unsigned int lutIndex = _pext_u32(maskFull, (1<<0) | (1<<4) | (1<<8) | (1<<12) | (1<<16) | (1<<20));
  131.     __m128i shuf = lookup_bmi[lutIndex];
  132.     return _mm_shuffle_epi8(abcd, shuf);
  133. }
  134. #endif
  135.  
  136. static const int HASH_BITS = 6;
  137. ALIGN(16) unsigned char lookup_hash_chars[1 << HASH_BITS][16] = {   //1Kb size
  138.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F},
  139.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF},
  140.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  141.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  142.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF},
  143.     {0x00, 0x01, 0x02, 0x03, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  144.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  145.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  146.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  147.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  148.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  149.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  150.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  151.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  152.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  153.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  154.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF},
  155.     {0x00, 0x01, 0x02, 0x03, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  156.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  157.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  158.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF},
  159.     {0x00, 0x01, 0x02, 0x03, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  160.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  161.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  162.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  163.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  164.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  165.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  166.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  167.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  168.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  169.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  170.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  171.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  172.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  173.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  174.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  175.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  176.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  177.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  178.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  179.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  180.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF},
  181.     {0x00, 0x01, 0x02, 0x03, 0x08, 0x09, 0x0A, 0x0B, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  182.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  183.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  184.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  185.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  186.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  187.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  188.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  189.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  190.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  191.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  192.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  193.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  194.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  195.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  196.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  197.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  198.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  199.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  200.     {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF},
  201.     {0x00, 0x01, 0x02, 0x03, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}
  202. };
  203. static __m128i *const lookup_hash = (__m128i*) &lookup_hash_chars[0][0];
  204.  
  205. static inline __m128i deduplicate4_ssse3(__m128i abcd) {
  206.     __m128i bcda = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(0, 3, 2, 1));
  207.     __m128i cdab = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(1, 0, 3, 2));
  208.     uint32_t mask1 = _mm_movemask_epi8(_mm_cmpeq_epi32(abcd, bcda));
  209.     uint32_t mask2 = _mm_movemask_epi8(_mm_cmpeq_epi32(abcd, cdab));
  210.     uint32_t maskFull = (mask2 << 16U) + mask1;
  211.     //Note: minimal perfect hash function here
  212.     uint32_t lutIndex = (maskFull * 0X0044CCCEU) >> 26U;
  213.     __m128i shuf = lookup_hash[lutIndex];
  214.     return _mm_shuffle_epi8(abcd, shuf);
  215. }
  216.  
  217.  
  218. static __m128i *const lookup_direct = (__m128i*) &lookup_bmi_chars[0][0];
  219. static __m128i *const lookup_direct_offset = lookup_direct - 0xC0U;
  220.  
  221. static inline __m128i deduplicate4_ssse3_direct(__m128i abcd) {
  222.     __m128i bcda = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(0, 3, 2, 1));
  223.     __m128i cdcd = _mm_shuffle_epi32(abcd, _MM_SHUFFLE(3, 2, 3, 2));
  224.     uint32_t mask1 = _mm_movemask_ps(_mm_castsi128_ps(_mm_cmpeq_epi32(abcd, bcda)));
  225.     uint32_t mask2 = _mm_movemask_ps(_mm_castsi128_ps(_mm_cmpeq_epi32(abcd, cdcd)));
  226.     uint32_t maskFull = 16U * mask2 + mask1;
  227.     //Note: use index directly
  228.     uint32_t lutIndex = maskFull;
  229.     __m128i shuf = lookup_direct_offset[lutIndex];
  230.     return _mm_shuffle_epi8(abcd, shuf);
  231. }
  232.  
  233. //======================== Perfect hash generator =========================
  234.  
  235. typedef uint32_t hash_int;
  236.  
  237. //searching for a hash function of this kind:
  238. hash_int HashFunction(hash_int param, hash_int x, int bits) {
  239.     return (param * x) >> hash_int(32 - bits);
  240. }
  241.  
  242. static const hash_int NO_PARAM = hash_int(-1);
  243. hash_int GeneratePerfectHash(std::vector<hash_int> values, int bits, hash_int tries = NO_PARAM) {
  244.     std::vector<int> table;
  245.     for (hash_int param = 0; param < tries; param++) {
  246.         table.assign(hash_int(1)<<bits, 0);
  247.         bool ok = true;
  248.         for (int i = 0; ok && i < values.size(); i++) {
  249.             hash_int x = values[i];
  250.             hash_int cell = HashFunction(param, x, bits);
  251.             if (table[cell]++)
  252.                 ok = false;
  253.         }
  254.         if (ok)
  255.             return param;
  256.     }
  257.     return NO_PARAM;
  258. }
  259.  
  260. //======================== Lookup table generator =========================
  261.  
  262. void PrintTable(const __m128i *lut, int size) {
  263.     for (int i = 0; i < size; i++) {
  264.         const unsigned char *entry = (unsigned char*) &lut[i];
  265.         printf("\t{");
  266.         for (int j = 0; j < 16; j++) {
  267.             if (j) printf(", ");
  268.             printf("0x%02X", (unsigned int)(entry[j]));
  269.         }
  270.         printf("},\n");
  271.     }
  272.     printf("\n");
  273. }
  274.  
  275. void GenerateLookupTable() {
  276.     for (int minMask = 0; minMask < 64; minMask++) {
  277.         bool matr[4][4];
  278.         matr[0][1] = (minMask >> 0) & 1;
  279.         matr[1][2] = (minMask >> 1) & 1;
  280.         matr[2][3] = (minMask >> 2) & 1;
  281.         matr[0][3] = (minMask >> 3) & 1;
  282.         matr[0][2] = (minMask >> 4) & 1;
  283.         matr[1][3] = (minMask >> 5) & 1;
  284.         int order[4] = {-1, -1, -1, -1};
  285.         int pos = 0;
  286.         for (int i = 0; i < 4; i++) {
  287.             bool isNew = true;
  288.             for (int j = 0; j < i; j++)
  289.                 if (matr[j][i])
  290.                     isNew = false;
  291.             if (isNew)
  292.                 order[pos++] = i;
  293.         }
  294.         unsigned char *bytes = lookup_bmi_chars[minMask];
  295.         for (int i = 0; i < 4; i++)
  296.             for (int j = 0; j < 4; j++)
  297.                 bytes[4 * i + j] = (order[i] < 0 ? -1 : 4 * order[i] + j);
  298.     }
  299. }
  300.  
  301. uint32_t GenerateLookupTableHash() {
  302.     GenerateLookupTable();
  303.     std::vector<uint32_t> allMasks;
  304.     for (int minMask = 0; minMask < 64; minMask++) {
  305.         uint32_t fullMask = 0;
  306.         for (int i = 0; i < 6; i++)
  307.             if ((minMask >> i) & 1) {
  308.                 fullMask |= 0xFU << (4*i);
  309.                 if (i >= 4) //comparisons 4 and 6, 5 and 7 are same
  310.                     fullMask |= 0xFU << (4*(i+2));
  311.             }
  312.         allMasks.push_back(fullMask);
  313.     }
  314.     uint32_t param = GeneratePerfectHash(allMasks, HASH_BITS);
  315.     assert(param != NO_PARAM);
  316.     memset(lookup_hash, -1, sizeof(lookup_hash));
  317.     for (int i = 0; i < allMasks.size(); i++) {
  318.         uint32_t hash = HashFunction(param, allMasks[i], HASH_BITS);
  319.         lookup_hash[hash] = lookup_bmi[i];
  320.     }
  321.     return param;
  322. }
  323.  
  324. void GenAll() {
  325.     GenerateLookupTable();
  326.     printf("lookup_bmi:\n");
  327.     PrintTable(lookup_bmi, 64);
  328.  
  329.     uint32_t param = GenerateLookupTableHash();
  330.     printf("lookup_hash (%08X):\n", param);
  331.     PrintTable(lookup_hash, 1 << HASH_BITS);
  332. }
  333.  
  334. //=============================== Testing =================================
  335.  
  336. static const int CASES = 1<<14;
  337. static const int TRIES = 1<<29;
  338.  
  339. static union {
  340.     uint32_t input_i[CASES][4];
  341.     __m128i input_r[CASES];
  342. };
  343.  
  344. int main() {
  345. /*  GenAll();
  346.     return 0;*/
  347.  
  348.     for (int i = 0; i < CASES; i++) {
  349.         for (int j = 0; j < 4; j++)
  350.             input_i[i][j] = rand() * 13457U + rand();
  351.         int eq = rand() % 5;
  352.         for (int c = 0; c < eq; c++) {
  353.             int a = rand() % 4, b = rand() % 4;
  354.             input_i[i][a] = input_i[i][b];
  355.         }
  356.     }
  357.  
  358.     for (int i = 0; i < CASES; i++) {
  359.         uint32_t res0[4], res1[4], res2[4], res3[4];
  360.         uint32_t *ptr = input_i[i];
  361.         deduplicate4_trivial(ptr, res0);
  362.         _mm_storeu_si128((__m128i*)res1, deduplicate4_ssse3(input_r[i]));
  363.         _mm_storeu_si128((__m128i*)res2, deduplicate4_ssse3_direct(input_r[i]));
  364.        
  365.         memcpy(res3, res2, 16);
  366. #ifdef __AVX__
  367.         _mm_storeu_si128((__m128i*)res3, deduplicate4_ssse3_bmi2(input_r[i]));
  368. #endif
  369.         uint32_t srt0[4], srt1[4], srt2[4], srt3[4];
  370.         memcpy(srt0, res0, 16);
  371.         memcpy(srt1, res1, 16);
  372.         memcpy(srt2, res2, 16);
  373.         memcpy(srt3, res3, 16);
  374.         std::sort(srt0, srt0 + 4);
  375.         std::sort(srt1, srt1 + 4);
  376.         std::sort(srt2, srt2 + 4);
  377.         std::sort(srt3, srt3 + 4);
  378.         if (memcmp(srt0, srt1, 16) || memcmp(srt0, srt2, 16) || memcmp(srt0, srt3, 16)) {
  379.             printf("%d %d %d %d\n", ptr[0], ptr[1], ptr[2], ptr[3]);
  380.             printf("%d %d %d %d\n", res0[0], res0[1], res0[2], res0[3]);
  381.             printf("%d %d %d %d\n", res1[0], res1[1], res1[2], res1[3]);
  382.             printf("%d %d %d %d\n", res2[0], res2[1], res2[2], res2[3]);
  383.             printf("%d %d %d %d\n", res3[0], res3[1], res3[2], res3[3]);
  384.         }
  385.     }
  386.  
  387. #ifdef __AVX__
  388.     {
  389.         __m128i sum = _mm_setzero_si128();
  390.         int start = clock();
  391.         for (int i = 0; i < TRIES; i++) {
  392.             __m128i res = deduplicate4_ssse3_bmi2(input_r[i & (CASES-1)]);
  393.             sum = _mm_add_epi32(sum, res);
  394.         }
  395.         uint32_t tmp[4];
  396.         _mm_storeu_si128((__m128i*)tmp, sum);
  397.         printf("Time = %0.3lf   (%u)\n", double(clock() - start) / CLOCKS_PER_SEC, tmp[0] + tmp[1] + tmp[2] + tmp[3]);
  398.     }
  399. #endif
  400.     {
  401.         __m128i sum = _mm_setzero_si128();
  402.         int start = clock();
  403.         for (int i = 0; i < TRIES; i++) {
  404.             __m128i res = deduplicate4_ssse3_direct(input_r[i & (CASES-1)]);
  405.             sum = _mm_add_epi32(sum, res);
  406.         }
  407.         uint32_t tmp[4];
  408.         _mm_storeu_si128((__m128i*)tmp, sum);
  409.         printf("Time = %0.3lf   (%u)\n", double(clock() - start) / CLOCKS_PER_SEC, tmp[0] + tmp[1] + tmp[2] + tmp[3]);
  410.     }
  411.     {
  412.         __m128i sum = _mm_setzero_si128();
  413.         int start = clock();
  414.         for (int i = 0; i < TRIES; i++) {
  415.             __m128i res = deduplicate4_ssse3(input_r[i & (CASES-1)]);
  416.             sum = _mm_add_epi32(sum, res);
  417.         }
  418.         uint32_t tmp[4];
  419.         _mm_storeu_si128((__m128i*)tmp, sum);
  420.         printf("Time = %0.3lf   (%u)\n", double(clock() - start) / CLOCKS_PER_SEC, tmp[0] + tmp[1] + tmp[2] + tmp[3]);
  421.     }
  422.     {
  423.         uint32_t res[4];
  424.         uint32_t sum = 0;
  425.         int start = clock();
  426.         for (int i = 0; i < TRIES; i++) {
  427.             deduplicate4_trivial(input_i[i & (CASES-1)], res);
  428.             sum += res[0] + res[1] + res[2] + res[3];
  429.         }
  430.         printf("Time = %0.3lf   (%u)\n", double(clock() - start) / CLOCKS_PER_SEC, sum);
  431.     }
  432.  
  433.     return 0;
  434. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!