src/genhashnames.c

   1 /*
   2  * Creates a bunch of files in the specified directory with the same
   3  * hashvalue on-disk.
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <stdint.h>
   9 #include <string.h>
  10 #include <limits.h>
  11 #include <fcntl.h>
  12 #include <errno.h>
  13 #include <sys/types.h>
  14 #include <sys/time.h>
  15
  16 #define rol32(x,y) (((x) << (y)) | ((x) >> (32 - (y))))
  17
  18 /*
  19  * Implement a simple hash on a character string.
  20  * Rotate the hash value by 7 bits, then XOR each character in.
  21  * This is implemented with some source-level loop unrolling.
  22  */
  23 static uint32_t xfs_da_hashname(const char *name, int namelen)
  24 {
  25         uint32_t        hash;
  26
  27         /*
  28          * Do four characters at a time as long as we can.
  29          */
  30         for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
  31                 hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
  32                        (name[3] << 0) ^ rol32(hash, 7 * 4);
  33
  34         /*
  35          * Now do the rest of the characters.
  36          */
  37         switch (namelen) {
  38         case 3:
  39                 return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
  40                        rol32(hash, 7 * 3);
  41         case 2:
  42                 return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
  43         case 1:
  44                 return (name[0] << 0) ^ rol32(hash, 7 * 1);
  45         default: /* case 0: */
  46                 return hash;
  47         }
  48 }
  49
  50 static int is_invalid_char(char c)
  51 {
  52         return (c <= ' ' || c > '~' || c == '/' || (c >= 'A' && c <= 'Z'));
  53 }
  54
  55 static char random_char(void)
  56 {
  57         char    c;
  58
  59         /* get a character of "0"-"9" or "a"-"z" */
  60
  61         c = lrand48() % 36;
  62
  63         return (c >= 10) ? c + 87 : c + 48;
  64 }
  65
  66 static int generate_names(const char *path, long amount, uint32_t desired_hash)
  67 {
  68         char            **names;
  69         char            fullpath[PATH_MAX];
  70         char            *filename;
  71         long            count;
  72         long            i;
  73         uint32_t        base_hash;
  74         uint32_t        hash;
  75
  76         names = malloc(amount * sizeof(char *));
  77         if (!names) {
  78                 fprintf(stderr, "genhashnames: malloc(%lu) failed!\n",
  79                                         amount * sizeof(char *));
  80                 return 1;
  81         }
  82
  83         strcpy(fullpath, path);
  84         filename = fullpath + strlen(fullpath);
  85         if (filename[-1] != '/')
  86                 *filename++ = '/';
  87
  88         for (count = 0; count < amount; count++) {
  89                 for (;;) {
  90                         base_hash = 0;
  91                         for (i = 0; i < 6; i++) {
  92                                 filename[i] = random_char();
  93                                 base_hash = filename[i] ^ rol32(base_hash, 7);
  94                         }
  95                         while (i < 200) {
  96                                 filename[i] = random_char();
  97                                 base_hash = filename[i] ^ rol32(base_hash, 7);
  98                                 i++;
  99                                 hash = rol32(base_hash, 3) ^ desired_hash;
 100
 101                                 filename[i] = (hash >> 28) |
 102                                                         (random_char() & 0xf0);
 103                                 if (is_invalid_char(filename[i]))
 104                                         continue;
 105
 106                                 filename[i + 1] = (hash >> 21) & 0x7f;
 107                                 if (is_invalid_char(filename[i + 1]))
 108                                         continue;
 109                                 filename[i + 2] = (hash >> 14) & 0x7f;
 110                                 if (is_invalid_char(filename[i + 2]))
 111                                         continue;
 112                                 filename[i + 3] = (hash >> 7) & 0x7f;
 113                                 if (is_invalid_char(filename[i + 3]))
 114                                         continue;
 115                                 filename[i + 4] = (hash ^ (filename[i] >> 4))
 116                                                                         & 0x7f;
 117                                 if (is_invalid_char(filename[i + 4]))
 118                                         continue;
 119                                 break;
 120                         }
 121                         if (i < NAME_MAX)
 122                                 break;
 123                 }
 124                 filename[i + 5] = '\0';
 125                 if (xfs_da_hashname(filename, i + 5) != desired_hash) {
 126                         fprintf(stderr, "genhashnames: Hash mismatch!\n");
 127                         return 1;
 128                 }
 129
 130                 for (i = 0; i < count; i++) {
 131                         if (strcmp(fullpath, names[i]) == 0)
 132                                 break;
 133                 }
 134                 if (i == count) {
 135                         names[count] = strdup(fullpath);
 136                         puts(fullpath);
 137                 } else
 138                         count--;
 139         }
 140         return 0;
 141 }
 142
 143 static void usage(void)
 144 {
 145         fprintf(stderr, "Usage: genhashnames <directory> <amount> "
 146                         "[seed] [hashvalue]\n");
 147         exit(1);
 148 }
 149
 150 int main(int argc, char **argv)
 151 {
 152         long            seed;
 153         uint32_t        desired_hash;
 154
 155         if (argc < 3 || argc > 5)
 156                 usage();
 157
 158         if (argc >= 4)
 159                 seed = strtol(argv[3], NULL, 0);
 160         else {
 161                 struct timeval  tv;
 162                 gettimeofday(&tv, NULL);
 163                 seed = tv.tv_usec / 1000 + (tv.tv_sec % 1000) * 1000;
 164         }
 165         srand48(seed);
 166
 167         /*
 168          * always generate hash from random so if hash is specified, random
 169          * sequence is the same as a randomly generated hash of the same value.
 170          */
 171         desired_hash = (uint32_t)mrand48();
 172         if (argc >= 5)
 173                 desired_hash = (uint32_t)strtoul(argv[4], NULL, 0);
 174
 175         fprintf(stderr, "seed = %ld, hash = 0x%08x\n", seed, desired_hash);
 176
 177         return generate_names(argv[1], strtol(argv[2], NULL, 0), desired_hash);
 178 }