Guest User

Untitled

a guest
Jun 23rd, 2015
43
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.97 KB | None | 0 0
  1. #include <stdint.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. #undef get16bits
  6. #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
  7.   || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
  8. #define get16bits(d) (*((const uint16_t *) (d)))
  9. #endif
  10.  
  11. #if !defined (get16bits)
  12. #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
  13.                        +(uint32_t)(((const uint8_t *)(d))[0]) )
  14. #endif
  15.  
  16. uint32_t SuperFastHash (const char * data, int len) {
  17. uint32_t hash = len, tmp;
  18. int rem;
  19.  
  20.     if (len <= 0 || data == NULL) return 0;
  21.  
  22.     rem = len & 3;
  23.     len >>= 2;
  24.  
  25.     /* Main loop */
  26.     for (;len > 0; len--) {
  27.         hash  += get16bits (data);
  28.         tmp    = (get16bits (data+2) << 11) ^ hash;
  29.         hash   = (hash << 16) ^ tmp;
  30.         data  += 2*sizeof (uint16_t);
  31.         hash  += hash >> 11;
  32.     }
  33.  
  34.     /* Handle end cases */
  35.     switch (rem) {
  36.         case 3: hash += get16bits (data);
  37.                 hash ^= hash << 16;
  38.                 hash ^= ((signed char)data[sizeof (uint16_t)]) << 18;
  39.                 hash += hash >> 11;
  40.                 break;
  41.         case 2: hash += get16bits (data);
  42.                 hash ^= hash << 11;
  43.                 hash += hash >> 17;
  44.                 break;
  45.         case 1: hash += (signed char)*data;
  46.                 hash ^= hash << 10;
  47.                 hash += hash >> 1;
  48.     }
  49.  
  50.     /* Force "avalanching" of final 127 bits */
  51.     hash ^= hash << 3;
  52.     hash += hash >> 5;
  53.     hash ^= hash << 4;
  54.     hash += hash >> 17;
  55.     hash ^= hash << 25;
  56.     hash += hash >> 6;
  57.  
  58.     return hash;
  59. }
  60.  
  61. int CheckCollision(const char* s1, const char* s2) {
  62.   //printf("\nChecking %s vs. %s\n  ", s1, s2);
  63.   return (SuperFastHash(s1, strlen(s1)) ==  SuperFastHash(s2, strlen(s2))) ? 1 : 0;
  64. }
  65.  
  66. int main() {
  67.   int i;
  68.   int j;
  69.  
  70.   for (j = 1; j < 64; ++j) {
  71.     int count = 0;
  72.     char orig[128];
  73.     memset(orig, 'a', j);
  74.     sprintf(orig + j, "0000");
  75.     for (i = 1; i < 10000; ++i) {
  76.       char x[128];
  77.       memset(x, 'a', j);
  78.       sprintf(x + j, "%04d", i);
  79.       count += CheckCollision(orig, x);
  80.     }
  81.     if (count)
  82.       printf("Collisions for length: %d =  %d\n", j, count);
  83.   }
  84.   return 0;
  85. }
  86.  
  87.  
  88. OUTPUT:
  89. $ gcc -o test test.c && ./test ù
  90. Collisions for length: 2 =  1
  91. Collisions for length: 3 =  3
  92. Collisions for length: 6 =  1
  93. Collisions for length: 7 =  1
  94. Collisions for length: 14 =  1
  95. Collisions for length: 15 =  4
  96. Collisions for length: 19 =  4
  97. Collisions for length: 22 =  1
  98. Collisions for length: 23 =  4
  99. Collisions for length: 26 =  1
  100. Collisions for length: 30 =  1
  101. Collisions for length: 31 =  3
  102. Collisions for length: 35 =  2
  103. Collisions for length: 42 =  1
  104. Collisions for length: 43 =  1
  105. Collisions for length: 46 =  1
  106. Collisions for length: 47 =  2
  107. Collisions for length: 50 =  1
  108. Collisions for length: 51 =  4
  109. Collisions for length: 54 =  1
  110. Collisions for length: 58 =  1
  111. Collisions for length: 59 =  2
  112. Collisions for length: 63 =  1
Advertisement
Add Comment
Please, Sign In to add comment