fs/reiser4/plugin/hash.c

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by
   2  * reiser4/README */
   3
   4 /* Hash functions */
   5
   6 #include "../debug.h"
   7 #include "plugin_header.h"
   8 #include "plugin.h"
   9 #include "../super.h"
  10 #include "../inode.h"
  11
  12 #include <linux/types.h>
  13
  14 /* old rupasov (yura) hash */
  15 static __u64 hash_rupasov(const unsigned char *name /* name to hash */ ,
  16                           int len/* @name's length */)
  17 {
  18         int i;
  19         int j;
  20         int pow;
  21         __u64 a;
  22         __u64 c;
  23
  24         assert("nikita-672", name != NULL);
  25         assert("nikita-673", len >= 0);
  26
  27         for (pow = 1, i = 1; i < len; ++i)
  28                 pow = pow * 10;
  29
  30         if (len == 1)
  31                 a = name[0] - 48;
  32         else
  33                 a = (name[0] - 48) * pow;
  34
  35         for (i = 1; i < len; ++i) {
  36                 c = name[i] - 48;
  37                 for (pow = 1, j = i; j < len - 1; ++j)
  38                         pow = pow * 10;
  39                 a = a + c * pow;
  40         }
  41         for (; i < 40; ++i) {
  42                 c = '0' - 48;
  43                 for (pow = 1, j = i; j < len - 1; ++j)
  44                         pow = pow * 10;
  45                 a = a + c * pow;
  46         }
  47
  48         for (; i < 256; ++i) {
  49                 c = i;
  50                 for (pow = 1, j = i; j < len - 1; ++j)
  51                         pow = pow * 10;
  52                 a = a + c * pow;
  53         }
  54
  55         a = a << 7;
  56         return a;
  57 }
  58
  59 /* r5 hash */
  60 static __u64 hash_r5(const unsigned char *name /* name to hash */ ,
  61                      int len UNUSED_ARG/* @name's length */)
  62 {
  63         __u64 a = 0;
  64
  65         assert("nikita-674", name != NULL);
  66         assert("nikita-675", len >= 0);
  67
  68         while (*name) {
  69                 a += *name << 4;
  70                 a += *name >> 4;
  71                 a *= 11;
  72                 name++;
  73         }
  74         return a;
  75 }
  76
  77 /* Keyed 32-bit hash function using TEA in a Davis-Meyer function
  78      H0 = Key
  79      Hi = E Mi(Hi-1) + Hi-1
  80
  81    (see Applied Cryptography, 2nd edition, p448).
  82
  83    Jeremy Fitzhardinge <jeremy@zip.com.au> 1998
  84
  85    Jeremy has agreed to the contents of reiserfs/README. -Hans
  86
  87    This code was blindly upgraded to __u64 by s/__u32/__u64/g.
  88 */
  89 static __u64 hash_tea(const unsigned char *name /* name to hash */ ,
  90                       int len/* @name's length */)
  91 {
  92         __u64 k[] = { 0x9464a485u, 0x542e1a94u, 0x3e846bffu, 0xb75bcfc3u };
  93
  94         __u64 h0 = k[0], h1 = k[1];
  95         __u64 a, b, c, d;
  96         __u64 pad;
  97         int i;
  98
  99         assert("nikita-676", name != NULL);
 100         assert("nikita-677", len >= 0);
 101
 102 #define DELTA 0x9E3779B9u
 103 #define FULLROUNDS 10           /* 32 is overkill, 16 is strong crypto */
 104 #define PARTROUNDS 6            /* 6 gets complete mixing */
 105
 106 /* a, b, c, d - data; h0, h1 - accumulated hash */
 107 #define TEACORE(rounds)                                                 \
 108         do {                                                            \
 109                 __u64 sum = 0;                                          \
 110                 int n = rounds;                                         \
 111                 __u64 b0, b1;                                           \
 112                                                                         \
 113                 b0 = h0;                                                \
 114                 b1 = h1;                                                \
 115                                                                         \
 116                 do {                                                    \
 117                         sum += DELTA;                                   \
 118                         b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); \
 119                         b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); \
 120                 } while (--n);                                          \
 121                                                                         \
 122                 h0 += b0;                                               \
 123                 h1 += b1;                                               \
 124         } while (0)
 125
 126         pad = (__u64) len | ((__u64) len << 8);
 127         pad |= pad << 16;
 128
 129         while (len >= 16) {
 130                 a = (__u64) name[0] | (__u64) name[1] << 8 | (__u64) name[2] <<
 131                     16 | (__u64) name[3] << 24;
 132                 b = (__u64) name[4] | (__u64) name[5] << 8 | (__u64) name[6] <<
 133                     16 | (__u64) name[7] << 24;
 134                 c = (__u64) name[8] | (__u64) name[9] << 8 | (__u64) name[10] <<
 135                     16 | (__u64) name[11] << 24;
 136                 d = (__u64) name[12] | (__u64) name[13] << 8 | (__u64) name[14]
 137                     << 16 | (__u64) name[15] << 24;
 138
 139                 TEACORE(PARTROUNDS);
 140
 141                 len -= 16;
 142                 name += 16;
 143         }
 144
 145         if (len >= 12) {
 146                 /* assert(len < 16); */
 147                 if (len >= 16)
 148                         *(int *)0 = 0;
 149
 150                 a = (__u64) name[0] | (__u64) name[1] << 8 | (__u64) name[2] <<
 151                     16 | (__u64) name[3] << 24;
 152                 b = (__u64) name[4] | (__u64) name[5] << 8 | (__u64) name[6] <<
 153                     16 | (__u64) name[7] << 24;
 154                 c = (__u64) name[8] | (__u64) name[9] << 8 | (__u64) name[10] <<
 155                     16 | (__u64) name[11] << 24;
 156
 157                 d = pad;
 158                 for (i = 12; i < len; i++) {
 159                         d <<= 8;
 160                         d |= name[i];
 161                 }
 162         } else if (len >= 8) {
 163                 /* assert(len < 12); */
 164                 if (len >= 12)
 165                         *(int *)0 = 0;
 166                 a = (__u64) name[0] | (__u64) name[1] << 8 | (__u64) name[2] <<
 167                     16 | (__u64) name[3] << 24;
 168                 b = (__u64) name[4] | (__u64) name[5] << 8 | (__u64) name[6] <<
 169                     16 | (__u64) name[7] << 24;
 170
 171                 c = d = pad;
 172                 for (i = 8; i < len; i++) {
 173                         c <<= 8;
 174                         c |= name[i];
 175                 }
 176         } else if (len >= 4) {
 177                 /* assert(len < 8); */
 178                 if (len >= 8)
 179                         *(int *)0 = 0;
 180                 a = (__u64) name[0] | (__u64) name[1] << 8 | (__u64) name[2] <<
 181                     16 | (__u64) name[3] << 24;
 182
 183                 b = c = d = pad;
 184                 for (i = 4; i < len; i++) {
 185                         b <<= 8;
 186                         b |= name[i];
 187                 }
 188         } else {
 189                 /* assert(len < 4); */
 190                 if (len >= 4)
 191                         *(int *)0 = 0;
 192                 a = b = c = d = pad;
 193                 for (i = 0; i < len; i++) {
 194                         a <<= 8;
 195                         a |= name[i];
 196                 }
 197         }
 198
 199         TEACORE(FULLROUNDS);
 200
 201 /*      return 0;*/
 202         return h0 ^ h1;
 203
 204 }
 205
 206 /* classical 64 bit Fowler/Noll/Vo-1 (FNV-1) hash.
 207
 208    See http://www.isthe.com/chongo/tech/comp/fnv/ for details.
 209
 210    Excerpts:
 211
 212      FNV hashes are designed to be fast while maintaining a low collision
 213      rate.
 214
 215      [This version also seems to preserve lexicographical order locally.]
 216
 217      FNV hash algorithms and source code have been released into the public
 218      domain.
 219
 220 */
 221 static __u64 hash_fnv1(const unsigned char *name /* name to hash */ ,
 222                        int len UNUSED_ARG/* @name's length */)
 223 {
 224         unsigned long long a = 0xcbf29ce484222325ull;
 225         const unsigned long long fnv_64_prime = 0x100000001b3ull;
 226
 227         assert("nikita-678", name != NULL);
 228         assert("nikita-679", len >= 0);
 229
 230         /* FNV-1 hash each octet in the buffer */
 231         for (; *name; ++name) {
 232                 /* multiply by the 32 bit FNV magic prime mod 2^64 */
 233                 a *= fnv_64_prime;
 234                 /* xor the bottom with the current octet */
 235                 a ^= (unsigned long long)(*name);
 236         }
 237         /* return our new hash value */
 238         return a;
 239 }
 240
 241 /* degenerate hash function used to simplify testing of non-unique key
 242    handling */
 243 static __u64 hash_deg(const unsigned char *name UNUSED_ARG /* name to hash */ ,
 244                       int len UNUSED_ARG/* @name's length */)
 245 {
 246         return 0xc0c0c0c010101010ull;
 247 }
 248
 249 static int change_hash(struct inode *inode,
 250                        reiser4_plugin * plugin,
 251                        pset_member memb)
 252 {
 253         int result;
 254
 255         assert("nikita-3503", inode != NULL);
 256         assert("nikita-3504", plugin != NULL);
 257
 258         assert("nikita-3505", is_reiser4_inode(inode));
 259         assert("nikita-3507", plugin->h.type_id == REISER4_HASH_PLUGIN_TYPE);
 260
 261         if (!plugin_of_group(inode_file_plugin(inode), REISER4_DIRECTORY_FILE))
 262                 return RETERR(-EINVAL);
 263
 264         result = 0;
 265         if (inode_hash_plugin(inode) == NULL ||
 266             inode_hash_plugin(inode)->h.id != plugin->h.id) {
 267                 if (is_dir_empty(inode) == 0)
 268                         result = aset_set_unsafe(&reiser4_inode_data(inode)->pset,
 269                                                  PSET_HASH, plugin);
 270                 else
 271                         result = RETERR(-ENOTEMPTY);
 272
 273         }
 274         return result;
 275 }
 276
 277 static reiser4_plugin_ops hash_plugin_ops = {
 278         .init = NULL,
 279         .load = NULL,
 280         .save_len = NULL,
 281         .save = NULL,
 282         .change = change_hash
 283 };
 284
 285 /* hash plugins */
 286 hash_plugin hash_plugins[LAST_HASH_ID] = {
 287         [RUPASOV_HASH_ID] = {
 288                 .h = {
 289                         .type_id = REISER4_HASH_PLUGIN_TYPE,
 290                         .id = RUPASOV_HASH_ID,
 291                         .pops = &hash_plugin_ops,
 292                         .label = "rupasov",
 293                         .desc = "Original Yura's hash",
 294                         .linkage = {NULL, NULL}
 295                 },
 296                 .hash = hash_rupasov
 297         },
 298         [R5_HASH_ID] = {
 299                 .h = {
 300                         .type_id = REISER4_HASH_PLUGIN_TYPE,
 301                         .id = R5_HASH_ID,
 302                         .pops = &hash_plugin_ops,
 303                         .label = "r5",
 304                         .desc = "r5 hash",
 305                         .linkage = {NULL, NULL}
 306                 },
 307                 .hash = hash_r5
 308         },
 309         [TEA_HASH_ID] = {
 310                 .h = {
 311                         .type_id = REISER4_HASH_PLUGIN_TYPE,
 312                         .id = TEA_HASH_ID,
 313                         .pops = &hash_plugin_ops,
 314                         .label = "tea",
 315                         .desc = "tea hash",
 316                         .linkage = {NULL, NULL}
 317                 },
 318                 .hash = hash_tea
 319         },
 320         [FNV1_HASH_ID] = {
 321                 .h = {
 322                         .type_id = REISER4_HASH_PLUGIN_TYPE,
 323                         .id = FNV1_HASH_ID,
 324                         .pops = &hash_plugin_ops,
 325                         .label = "fnv1",
 326                         .desc = "fnv1 hash",
 327                         .linkage = {NULL, NULL}
 328                 },
 329                 .hash = hash_fnv1
 330         },
 331         [DEGENERATE_HASH_ID] = {
 332                 .h = {
 333                         .type_id = REISER4_HASH_PLUGIN_TYPE,
 334                         .id = DEGENERATE_HASH_ID,
 335                         .pops = &hash_plugin_ops,
 336                         .label = "degenerate hash",
 337                         .desc = "Degenerate hash: only for testing",
 338                         .linkage = {NULL, NULL}
 339                 },
 340                 .hash = hash_deg
 341         }
 342 };
 343
 344 /* Make Linus happy.
 345    Local variables:
 346    c-indentation-style: "K&R"
 347    mode-name: "LC"
 348    c-basic-offset: 8
 349    tab-width: 8
 350    fill-column: 120
 351    End:
 352 */