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, sizeof(array), 0);
  23         for (i = 0; i < sizeof(uint32_t); i++) {
  24                 memcpy(array2 + i, array, sizeof(array));
  25                 ok(hash(array2 + i, sizeof(array), 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, sizeof(array), 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), 0) >> i*8)&0xFF]++;
  65                 }
  66
  67                 for (j = 0; j < 256; j++) {
  68                         if (results[j] < lowest)
  69                                 lowest = results[j];
  70                         if (results[j] > highest)
  71                                 highest = results[j];
  72                 }
  73                 /* Expect within 20% */
  74                 ok(lowest > 800, "Byte %i lowest %i", i, lowest);
  75                 ok(highest < 1200, "Byte %i highest %i", i, highest);
  76                 diag("Byte %i, range %u-%u", i, lowest, highest);
  77         }
  78
  79         /* Hash of pointer values should also have random distribution. */
  80         for (i = 0; i < sizeof(uint32_t); i++) {
  81                 unsigned int lowest = -1U, highest = 0;
  82                 char *p = malloc(256000);
  83
  84                 memset(results, 0, sizeof(results));
  85
  86                 for (j = 0; j < 256000; j++)
  87                         results[(hash_pointer(p + j, 0) >> i*8)&0xFF]++;
  88                 free(p);
  89
  90                 for (j = 0; j < 256; j++) {
  91                         if (results[j] < lowest)
  92                                 lowest = results[j];
  93                         if (results[j] > highest)
  94                                 highest = results[j];
  95                 }
  96                 /* Expect within 20% */
  97                 ok(lowest > 800, "hash_pointer byte %i lowest %i", i, lowest);
  98                 ok(highest < 1200, "hash_pointer byte %i highest %i",
  99                    i, highest);
 100                 diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
 101         }
 102
 103         if (sizeof(long) == sizeof(uint32_t))
 104                 ok1(hashl(array, sizeof(array), 0)
 105                     == hash(array, sizeof(array), 0));
 106         else
 107                 ok1(hashl(array, sizeof(array), 0)
 108                     == hash64(array, sizeof(array), 0));
 109
 110         /* String hash: weak, so only test bottom byte */
 111         for (i = 0; i < 1; i++) {
 112                 unsigned int num = 0, cursor, lowest = -1U, highest = 0;
 113                 char p[5];
 114
 115                 memset(results, 0, sizeof(results));
 116
 117                 memset(p, 'A', sizeof(p));
 118                 p[sizeof(p)-1] = '\0';
 119
 120                 for (;;) {
 121                         for (cursor = 0; cursor < sizeof(p)-1; cursor++) {
 122                                 p[cursor]++;
 123                                 if (p[cursor] <= 'z')
 124                                         break;
 125                                 p[cursor] = 'A';
 126                         }
 127                         if (cursor == sizeof(p)-1)
 128                                 break;
 129
 130                         results[(hash_string(p) >> i*8)&0xFF]++;
 131                         num++;
 132                 }
 133
 134                 for (j = 0; j < 256; j++) {
 135                         if (results[j] < lowest)
 136                                 lowest = results[j];
 137                         if (results[j] > highest)
 138                                 highest = results[j];
 139                 }
 140                 /* Expect within 20% */
 141                 ok(lowest > 35000, "hash_pointer byte %i lowest %i", i, lowest);
 142                 ok(highest < 53000, "hash_pointer byte %i highest %i",
 143                    i, highest);
 144                 diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
 145         }
 146
 147         return exit_status();
 148 }