git.ozlabs.org Git - ccan/blob - hash/test/run.c

   1 #include "hash/hash.h"
   2 #include "tap/tap.h"
   3 #include "hash/hash.c"
   4 #include <stdbool.h>
   5 #include <string.h>
   6
   7 #define ARRAY_WORDS 5
   8
   9 int main(int argc, char *argv[])
  10 {
  11         unsigned int i, j, k;
  12         uint32_t array[ARRAY_WORDS], val;
  13         char array2[sizeof(array) + sizeof(uint32_t)];
  14         uint32_t results[256];
  15
  16         /* Initialize array. */
  17         for (i = 0; i < ARRAY_WORDS; i++)
  18                 array[i] = i;
  19
  20         plan_tests(53);
  21
  22         /* hash_stable is guaranteed. */
  23         ok1(hash_stable(array, ARRAY_WORDS, 0) == 0x13305f8c);
  24         ok1(hash_stable(array, ARRAY_WORDS, 1) == 0x171abf74);
  25         ok1(hash_stable(array, ARRAY_WORDS, 2) == 0x7646fcc7);
  26         ok1(hash_stable(array, ARRAY_WORDS, 4) == 0xa758ed5);
  27         ok1(hash_stable(array, ARRAY_WORDS, 8) == 0x2dedc2e4);
  28         ok1(hash_stable(array, ARRAY_WORDS, 16) == 0x28e2076b);
  29         ok1(hash_stable(array, ARRAY_WORDS, 32) == 0xb73091c5);
  30         ok1(hash_stable(array, ARRAY_WORDS, 64) == 0x87daf5db);
  31         ok1(hash_stable(array, ARRAY_WORDS, 128) == 0xa16dfe20);
  32         ok1(hash_stable(array, ARRAY_WORDS, 256) == 0x300c63c3);
  33         ok1(hash_stable(array, ARRAY_WORDS, 512) == 0x255c91fc);
  34         ok1(hash_stable(array, ARRAY_WORDS, 1024) == 0x6357b26);
  35         ok1(hash_stable(array, ARRAY_WORDS, 2048) == 0x4bc5f339);
  36         ok1(hash_stable(array, ARRAY_WORDS, 4096) == 0x1301617c);
  37         ok1(hash_stable(array, ARRAY_WORDS, 8192) == 0x506792c9);
  38         ok1(hash_stable(array, ARRAY_WORDS, 16384) == 0xcd596705);
  39         ok1(hash_stable(array, ARRAY_WORDS, 32768) == 0xa8713cac);
  40         ok1(hash_stable(array, ARRAY_WORDS, 65536) == 0x94d9794);
  41         ok1(hash_stable(array, ARRAY_WORDS, 131072) == 0xac753e8);
  42         ok1(hash_stable(array, ARRAY_WORDS, 262144) == 0xcd8bdd20);
  43         ok1(hash_stable(array, ARRAY_WORDS, 524288) == 0xd44faf80);
  44         ok1(hash_stable(array, ARRAY_WORDS, 1048576) == 0x2547ccbe);
  45         ok1(hash_stable(array, ARRAY_WORDS, 2097152) == 0xbab06dbc);
  46         ok1(hash_stable(array, ARRAY_WORDS, 4194304) == 0xaac0e882);
  47         ok1(hash_stable(array, ARRAY_WORDS, 8388608) == 0x443f48d0);
  48         ok1(hash_stable(array, ARRAY_WORDS, 16777216) == 0xdff49fcc);
  49         ok1(hash_stable(array, ARRAY_WORDS, 33554432) == 0x9ce0fd65);
  50         ok1(hash_stable(array, ARRAY_WORDS, 67108864) == 0x9ddb1def);
  51         ok1(hash_stable(array, ARRAY_WORDS, 134217728) == 0x86096f25);
  52         ok1(hash_stable(array, ARRAY_WORDS, 268435456) == 0xe713b7b5);
  53         ok1(hash_stable(array, ARRAY_WORDS, 536870912) == 0x5baeffc5);
  54         ok1(hash_stable(array, ARRAY_WORDS, 1073741824) == 0xde874f52);
  55         ok1(hash_stable(array, ARRAY_WORDS, 2147483648U) == 0xeca13b4e);
  56
  57         /* Hash should be the same, indep of memory alignment. */
  58         val = hash(array, sizeof(array), 0);
  59         for (i = 0; i < sizeof(uint32_t); i++) {
  60                 memcpy(array2 + i, array, sizeof(array));
  61                 ok(hash(array2 + i, sizeof(array), 0) != val,
  62                    "hash matched at offset %i", i);
  63         }
  64
  65         /* Hash of random values should have random distribution:
  66          * check one byte at a time. */
  67         for (i = 0; i < sizeof(uint32_t); i++) {
  68                 unsigned int lowest = -1U, highest = 0;
  69
  70                 memset(results, 0, sizeof(results));
  71
  72                 for (j = 0; j < 256000; j++) {
  73                         for (k = 0; k < ARRAY_WORDS; k++)
  74                                 array[k] = random();
  75                         results[(hash(array, sizeof(array), 0) >> i*8)&0xFF]++;
  76                 }
  77
  78                 for (j = 0; j < 256; j++) {
  79                         if (results[j] < lowest)
  80                                 lowest = results[j];
  81                         if (results[j] > highest)
  82                                 highest = results[j];
  83                 }
  84                 /* Expect within 20% */
  85                 ok(lowest > 800, "Byte %i lowest %i", i, lowest);
  86                 ok(highest < 1200, "Byte %i highest %i", i, highest);
  87                 diag("Byte %i, range %u-%u", i, lowest, highest);
  88         }
  89
  90         /* Hash of pointer values should also have random distribution. */
  91         for (i = 0; i < sizeof(uint32_t); i++) {
  92                 unsigned int lowest = -1U, highest = 0;
  93                 char *p = malloc(256000);
  94
  95                 memset(results, 0, sizeof(results));
  96
  97                 for (j = 0; j < 256000; j++)
  98                         results[(hash_pointer(p + j, 0) >> i*8)&0xFF]++;
  99                 free(p);
 100
 101                 for (j = 0; j < 256; j++) {
 102                         if (results[j] < lowest)
 103                                 lowest = results[j];
 104                         if (results[j] > highest)
 105                                 highest = results[j];
 106                 }
 107                 /* Expect within 20% */
 108                 ok(lowest > 800, "hash_pointer byte %i lowest %i", i, lowest);
 109                 ok(highest < 1200, "hash_pointer byte %i highest %i",
 110                    i, highest);
 111                 diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
 112         }
 113
 114         return exit_status();
 115 }