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(22);
  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 pointer values should also have random distribution. */
  55         for (i = 0; i < sizeof(uint32_t); i++) {
  56                 unsigned int lowest = -1U, highest = 0;
  57                 char *p = malloc(256000);
  58
  59                 memset(results, 0, sizeof(results));
  60
  61                 for (j = 0; j < 256000; j++)
  62                         results[(hash_pointer(p + j, 0) >> i*8)&0xFF]++;
  63                 free(p);
  64
  65                 for (j = 0; j < 256; j++) {
  66                         if (results[j] < lowest)
  67                                 lowest = results[j];
  68                         if (results[j] > highest)
  69                                 highest = results[j];
  70                 }
  71                 /* Expect within 20% */
  72                 ok(lowest > 800, "hash_pointer byte %i lowest %i", i, lowest);
  73                 ok(highest < 1200, "hash_pointer byte %i highest %i",
  74                    i, highest);
  75                 diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
  76         }
  77
  78         /* String hash: weak, so only test bottom byte */
  79         for (i = 0; i < 1; i++) {
  80                 unsigned int num = 0, cursor, lowest = -1U, highest = 0;
  81                 char p[5];
  82
  83                 memset(results, 0, sizeof(results));
  84
  85                 memset(p, 'A', sizeof(p));
  86                 p[sizeof(p)-1] = '\0';
  87
  88                 for (;;) {
  89                         for (cursor = 0; cursor < sizeof(p)-1; cursor++) {
  90                                 p[cursor]++;
  91                                 if (p[cursor] <= 'z')
  92                                         break;
  93                                 p[cursor] = 'A';
  94                         }
  95                         if (cursor == sizeof(p)-1)
  96                                 break;
  97
  98                         results[(hash_string(p) >> i*8)&0xFF]++;
  99                         num++;
 100                 }
 101
 102                 for (j = 0; j < 256; j++) {
 103                         if (results[j] < lowest)
 104                                 lowest = results[j];
 105                         if (results[j] > highest)
 106                                 highest = results[j];
 107                 }
 108                 /* Expect within 20% */
 109                 ok(lowest > 35000, "hash_pointer byte %i lowest %i", i, lowest);
 110                 ok(highest < 53000, "hash_pointer byte %i highest %i",
 111                    i, highest);
 112                 diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
 113         }
 114
 115         return exit_status();
 116 }