Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdint.h>
- #include <stdio.h>
- #include <string.h>
- #undef get16bits
- #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
- || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
- #define get16bits(d) (*((const uint16_t *) (d)))
- #endif
- #if !defined (get16bits)
- #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
- +(uint32_t)(((const uint8_t *)(d))[0]) )
- #endif
- uint32_t SuperFastHash (const char * data, int len) {
- uint32_t hash = len, tmp;
- int rem;
- if (len <= 0 || data == NULL) return 0;
- rem = len & 3;
- len >>= 2;
- /* Main loop */
- for (;len > 0; len--) {
- hash += get16bits (data);
- tmp = (get16bits (data+2) << 11) ^ hash;
- hash = (hash << 16) ^ tmp;
- data += 2*sizeof (uint16_t);
- hash += hash >> 11;
- }
- /* Handle end cases */
- switch (rem) {
- case 3: hash += get16bits (data);
- hash ^= hash << 16;
- hash ^= ((signed char)data[sizeof (uint16_t)]) << 18;
- hash += hash >> 11;
- break;
- case 2: hash += get16bits (data);
- hash ^= hash << 11;
- hash += hash >> 17;
- break;
- case 1: hash += (signed char)*data;
- hash ^= hash << 10;
- hash += hash >> 1;
- }
- /* Force "avalanching" of final 127 bits */
- hash ^= hash << 3;
- hash += hash >> 5;
- hash ^= hash << 4;
- hash += hash >> 17;
- hash ^= hash << 25;
- hash += hash >> 6;
- return hash;
- }
- int CheckCollision(const char* s1, const char* s2) {
- //printf("\nChecking %s vs. %s\n ", s1, s2);
- return (SuperFastHash(s1, strlen(s1)) == SuperFastHash(s2, strlen(s2))) ? 1 : 0;
- }
- int main() {
- int i;
- int j;
- for (j = 1; j < 64; ++j) {
- int count = 0;
- char orig[128];
- memset(orig, 'a', j);
- sprintf(orig + j, "0000");
- for (i = 1; i < 10000; ++i) {
- char x[128];
- memset(x, 'a', j);
- sprintf(x + j, "%04d", i);
- count += CheckCollision(orig, x);
- }
- if (count)
- printf("Collisions for length: %d = %d\n", j, count);
- }
- return 0;
- }
- OUTPUT:
- $ gcc -o test test.c && ./test ù
- Collisions for length: 2 = 1
- Collisions for length: 3 = 3
- Collisions for length: 6 = 1
- Collisions for length: 7 = 1
- Collisions for length: 14 = 1
- Collisions for length: 15 = 4
- Collisions for length: 19 = 4
- Collisions for length: 22 = 1
- Collisions for length: 23 = 4
- Collisions for length: 26 = 1
- Collisions for length: 30 = 1
- Collisions for length: 31 = 3
- Collisions for length: 35 = 2
- Collisions for length: 42 = 1
- Collisions for length: 43 = 1
- Collisions for length: 46 = 1
- Collisions for length: 47 = 2
- Collisions for length: 50 = 1
- Collisions for length: 51 = 4
- Collisions for length: 54 = 1
- Collisions for length: 58 = 1
- Collisions for length: 59 = 2
- Collisions for length: 63 = 1
Advertisement
Add Comment
Please, Sign In to add comment