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                 {                                                       \
 118                         sum += DELTA;                                   \
 119                         b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); \
 120                         b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); \
 121                 } while(--n);                                           \
 122                                                                         \
 123                 h0 += b0;                                               \
 124                 h1 += b1;                                               \
 125         } while(0)
 126
 127         pad = (__u64) len | ((__u64) len << 8);
 128         pad |= pad << 16;
 129
 130         while (len >= 16) {
 131                 a = (__u64) name[0] | (__u64) name[1] << 8 | (__u64) name[2] <<
 132                     16 | (__u64) name[3] << 24;
 133                 b = (__u64) name[4] | (__u64) name[5] << 8 | (__u64) name[6] <<
 134                     16 | (__u64) name[7] << 24;
 135                 c = (__u64) name[8] | (__u64) name[9] << 8 | (__u64) name[10] <<
 136                     16 | (__u64) name[11] << 24;
 137                 d = (__u64) name[12] | (__u64) name[13] << 8 | (__u64) name[14]
 138                     << 16 | (__u64) name[15] << 24;
 139
 140                 TEACORE(PARTROUNDS);
 141
 142                 len -= 16;
 143                 name += 16;
 144         }
 145
 146         if (len >= 12) {
 147                 //assert(len < 16);
 148                 if (len >= 16)
 149                         *(int *)0 = 0;
 150
 151                 a = (__u64) name[0] | (__u64) name[1] << 8 | (__u64) name[2] <<
 152                     16 | (__u64) name[3] << 24;
 153                 b = (__u64) name[4] | (__u64) name[5] << 8 | (__u64) name[6] <<
 154                     16 | (__u64) name[7] << 24;
 155                 c = (__u64) name[8] | (__u64) name[9] << 8 | (__u64) name[10] <<
 156                     16 | (__u64) name[11] << 24;
 157
 158                 d = pad;
 159                 for (i = 12; i < len; i++) {
 160                         d <<= 8;
 161                         d |= name[i];
 162                 }
 163         } else if (len >= 8) {
 164                 //assert(len < 12);
 165                 if (len >= 12)
 166                         *(int *)0 = 0;
 167                 a = (__u64) name[0] | (__u64) name[1] << 8 | (__u64) name[2] <<
 168                     16 | (__u64) name[3] << 24;
 169                 b = (__u64) name[4] | (__u64) name[5] << 8 | (__u64) name[6] <<
 170                     16 | (__u64) name[7] << 24;
 171
 172                 c = d = pad;
 173                 for (i = 8; i < len; i++) {
 174                         c <<= 8;
 175                         c |= name[i];
 176                 }
 177         } else if (len >= 4) {
 178                 //assert(len < 8);
 179                 if (len >= 8)
 180                         *(int *)0 = 0;
 181                 a = (__u64) name[0] | (__u64) name[1] << 8 | (__u64) name[2] <<
 182                     16 | (__u64) name[3] << 24;
 183
 184                 b = c = d = pad;
 185                 for (i = 4; i < len; i++) {
 186                         b <<= 8;
 187                         b |= name[i];
 188                 }
 189         } else {
 190                 //assert(len < 4);
 191                 if (len >= 4)
 192                         *(int *)0 = 0;
 193                 a = b = c = d = pad;
 194                 for (i = 0; i < len; i++) {
 195                         a <<= 8;
 196                         a |= name[i];
 197                 }
 198         }
 199
 200         TEACORE(FULLROUNDS);
 201
 202 /*      return 0;*/
 203         return h0 ^ h1;
 204
 205 }
 206
 207 /* classical 64 bit Fowler/Noll/Vo-1 (FNV-1) hash.
 208
 209    See http://www.isthe.com/chongo/tech/comp/fnv/ for details.
 210
 211    Excerpts:
 212
 213      FNV hashes are designed to be fast while maintaining a low collision
 214      rate.
 215
 216      [This version also seems to preserve lexicographical order locally.]
 217
 218      FNV hash algorithms and source code have been released into the public
 219      domain.
 220
 221 */
 222 static __u64 hash_fnv1(const unsigned char *name /* name to hash */ ,
 223                        int len UNUSED_ARG /* @name's length */ )
 224 {
 225         unsigned long long a = 0xcbf29ce484222325ull;
 226         const unsigned long long fnv_64_prime = 0x100000001b3ull;
 227
 228         assert("nikita-678", name != NULL);
 229         assert("nikita-679", len >= 0);
 230
 231         /* FNV-1 hash each octet in the buffer */
 232         for (; *name; ++name) {
 233                 /* multiply by the 32 bit FNV magic prime mod 2^64 */
 234                 a *= fnv_64_prime;
 235                 /* xor the bottom with the current octet */
 236                 a ^= (unsigned long long)(*name);
 237         }
 238         /* return our new hash value */
 239         return a;
 240 }
 241
 242 /* degenerate hash function used to simplify testing of non-unique key
 243    handling */
 244 static __u64 hash_deg(const unsigned char *name UNUSED_ARG /* name to hash */ ,
 245                       int len UNUSED_ARG /* @name's length */ )
 246 {
 247         return 0xc0c0c0c010101010ull;
 248 }
 249
 250 static int change_hash(struct inode *inode,
 251                        reiser4_plugin * plugin,
 252                        pset_member memb)
 253 {
 254         int result;
 255
 256         assert("nikita-3503", inode != NULL);
 257         assert("nikita-3504", plugin != NULL);
 258
 259         assert("nikita-3505", is_reiser4_inode(inode));
 260         assert("nikita-3507", plugin->h.type_id == REISER4_HASH_PLUGIN_TYPE);
 261
 262         if (!plugin_of_group(inode_file_plugin(inode), REISER4_DIRECTORY_FILE))
 263                 return RETERR(-EINVAL);
 264
 265         result = 0;
 266         if (inode_hash_plugin(inode) == NULL ||
 267             inode_hash_plugin(inode)->h.id != plugin->h.id) {
 268                 if (is_dir_empty(inode) == 0)
 269                         result = aset_set_unsafe(&reiser4_inode_data(inode)->pset,
 270                                                  PSET_HASH, plugin);
 271                 else
 272                         result = RETERR(-ENOTEMPTY);
 273
 274         }
 275         return result;
 276 }
 277
 278 static reiser4_plugin_ops hash_plugin_ops = {
 279         .init = NULL,
 280         .load = NULL,
 281         .save_len = NULL,
 282         .save = NULL,
 283         .change = change_hash
 284 };
 285
 286 /* hash plugins */
 287 hash_plugin hash_plugins[LAST_HASH_ID] = {
 288         [RUPASOV_HASH_ID] = {
 289                 .h = {
 290                         .type_id = REISER4_HASH_PLUGIN_TYPE,
 291                         .id = RUPASOV_HASH_ID,
 292                         .pops = &hash_plugin_ops,
 293                         .label = "rupasov",
 294                         .desc = "Original Yura's hash",
 295                         .linkage = {NULL, NULL}
 296                 },
 297                 .hash = hash_rupasov
 298         },
 299         [R5_HASH_ID] = {
 300                 .h = {
 301                         .type_id = REISER4_HASH_PLUGIN_TYPE,
 302                         .id = R5_HASH_ID,
 303                         .pops = &hash_plugin_ops,
 304                         .label = "r5",
 305                         .desc = "r5 hash",
 306                         .linkage = {NULL, NULL}
 307                 },
 308                 .hash = hash_r5
 309         },
 310         [TEA_HASH_ID] = {
 311                 .h = {
 312                         .type_id = REISER4_HASH_PLUGIN_TYPE,
 313                         .id = TEA_HASH_ID,
 314                         .pops = &hash_plugin_ops,
 315                         .label = "tea",
 316                         .desc = "tea hash",
 317                         .linkage = {NULL, NULL}
 318                 },
 319                 .hash = hash_tea
 320         },
 321         [FNV1_HASH_ID] = {
 322                 .h = {
 323                         .type_id = REISER4_HASH_PLUGIN_TYPE,
 324                         .id = FNV1_HASH_ID,
 325                         .pops = &hash_plugin_ops,
 326                         .label = "fnv1",
 327                         .desc = "fnv1 hash",
 328                         .linkage = {NULL, NULL}
 329                 },
 330                 .hash = hash_fnv1
 331         },
 332         [DEGENERATE_HASH_ID] = {
 333                 .h = {
 334                         .type_id = REISER4_HASH_PLUGIN_TYPE,
 335                         .id = DEGENERATE_HASH_ID,
 336                         .pops = &hash_plugin_ops,
 337                         .label = "degenerate hash",
 338                         .desc = "Degenerate hash: only for testing",
 339                         .linkage = {NULL, NULL}
 340                 },
 341                 .hash = hash_deg
 342         }
 343 };
 344
 345 /* Make Linus happy.
 346    Local variables:
 347    c-indentation-style: "K&R"
 348    mode-name: "LC"
 349    c-basic-offset: 8
 350    tab-width: 8
 351    fill-column: 120
 352    End:
 353 */