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

   1 #include <ccan/hash/hash.h>
   2 #include <ccan/tap/tap.h>
   3 #include <ccan/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(39);
  21         /* Hash should be the same, indep of memory alignment. */
  22         val = hash(array, ARRAY_WORDS, 0);
  23         for (i = 0; i < sizeof(uint32_t); i++) {
  24                 memcpy(array2 + i, array, sizeof(array));
  25                 ok(hash(array2 + i, ARRAY_WORDS, 0) != val,
  26                    "hash matched at offset %i", i);
  27         }
  28
  29         /* Hash of random values should have random distribution:
  30          * check one byte at a time. */
  31         for (i = 0; i < sizeof(uint32_t); i++) {
  32                 unsigned int lowest = -1U, highest = 0;
  33
  34                 memset(results, 0, sizeof(results));
  35
  36                 for (j = 0; j < 256000; j++) {
  37                         for (k = 0; k < ARRAY_WORDS; k++)
  38                                 array[k] = random();
  39                         results[(hash(array, ARRAY_WORDS, 0) >> i*8)&0xFF]++;
  40                 }
  41
  42                 for (j = 0; j < 256; j++) {
  43                         if (results[j] < lowest)
  44                                 lowest = results[j];
  45                         if (results[j] > highest)
  46                                 highest = results[j];
  47                 }
  48                 /* Expect within 20% */
  49                 ok(lowest > 800, "Byte %i lowest %i", i, lowest);
  50                 ok(highest < 1200, "Byte %i highest %i", i, highest);
  51                 diag("Byte %i, range %u-%u", i, lowest, highest);
  52         }
  53
  54         /* Hash of random values should have random distribution:
  55          * check one byte at a time. */
  56         for (i = 0; i < sizeof(uint64_t); i++) {
  57                 unsigned int lowest = -1U, highest = 0;
  58
  59                 memset(results, 0, sizeof(results));
  60
  61                 for (j = 0; j < 256000; j++) {
  62                         for (k = 0; k < ARRAY_WORDS; k++)
  63                                 array[k] = random();
  64                         results[(hash64(array, sizeof(array)/sizeof(uint64_t),
  65                                         0) >> i*8)&0xFF]++;
  66                 }
  67
  68                 for (j = 0; j < 256; j++) {
  69                         if (results[j] < lowest)
  70                                 lowest = results[j];
  71                         if (results[j] > highest)
  72                                 highest = results[j];
  73                 }
  74                 /* Expect within 20% */
  75                 ok(lowest > 800, "Byte %i lowest %i", i, lowest);
  76                 ok(highest < 1200, "Byte %i highest %i", i, highest);
  77                 diag("Byte %i, range %u-%u", i, lowest, highest);
  78         }
  79
  80         /* Hash of pointer values should also have random distribution. */
  81         for (i = 0; i < sizeof(uint32_t); i++) {
  82                 unsigned int lowest = -1U, highest = 0;
  83                 char *p = malloc(256000);
  84
  85                 memset(results, 0, sizeof(results));
  86
  87                 for (j = 0; j < 256000; j++)
  88                         results[(hash_pointer(p + j, 0) >> i*8)&0xFF]++;
  89                 free(p);
  90
  91                 for (j = 0; j < 256; j++) {
  92                         if (results[j] < lowest)
  93                                 lowest = results[j];
  94                         if (results[j] > highest)
  95                                 highest = results[j];
  96                 }
  97                 /* Expect within 20% */
  98                 ok(lowest > 800, "hash_pointer byte %i lowest %i", i, lowest);
  99                 ok(highest < 1200, "hash_pointer byte %i highest %i",
 100                    i, highest);
 101                 diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
 102         }
 103
 104         if (sizeof(long) == sizeof(uint32_t))
 105                 ok1(hashl(array, ARRAY_WORDS, 0)
 106                     == hash(array, ARRAY_WORDS, 0));
 107         else
 108                 ok1(hashl(array, ARRAY_WORDS, 0)
 109                     == hash64(array, ARRAY_WORDS, 0));
 110
 111         /* String hash: weak, so only test bottom byte */
 112         for (i = 0; i < 1; i++) {
 113                 unsigned int num = 0, cursor, lowest = -1U, highest = 0;
 114                 char p[5];
 115
 116                 memset(results, 0, sizeof(results));
 117
 118                 memset(p, 'A', sizeof(p));
 119                 p[sizeof(p)-1] = '\0';
 120
 121                 for (;;) {
 122                         for (cursor = 0; cursor < sizeof(p)-1; cursor++) {
 123                                 p[cursor]++;
 124                                 if (p[cursor] <= 'z')
 125                                         break;
 126                                 p[cursor] = 'A';
 127                         }
 128                         if (cursor == sizeof(p)-1)
 129                                 break;
 130
 131                         results[(hash_string(p) >> i*8)&0xFF]++;
 132                         num++;
 133                 }
 134
 135                 for (j = 0; j < 256; j++) {
 136                         if (results[j] < lowest)
 137                                 lowest = results[j];
 138                         if (results[j] > highest)
 139                                 highest = results[j];
 140                 }
 141                 /* Expect within 20% */
 142                 ok(lowest > 35000, "hash_pointer byte %i lowest %i", i, lowest);
 143                 ok(highest < 53000, "hash_pointer byte %i highest %i",
 144                    i, highest);
 145                 diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
 146         }
 147
 148         return exit_status();
 149 }