src/add-ons/kernel/file_systems/reiserfs/hashes.cpp

   1
   2 /*
   3  * Keyed 32-bit hash function using TEA in a Davis-Meyer function
   4  *   H0 = Key
   5  *   Hi = E Mi(Hi-1) + Hi-1
   6  *
   7  * (see Applied Cryptography, 2nd edition, p448).
   8  *
   9  * Jeremy Fitzhardinge <jeremy@zip.com.au> 1998
  10  *
  11  * Jeremy has agreed to the contents of reiserfs/README. -Hans
  12  * Yura's function is added (04/07/2000)
  13  */
  14
  15 // Modified by Ingo Weinhold (bonefish), Jan. 2003:
  16 // Fixed r5_hash() and added key_offset_for_name().
  17
  18 //
  19 // keyed_hash
  20 // yura_hash
  21 // r5_hash
  22 //
  23
  24 #include "hashes.h"
  25 #include "reiserfs.h"
  26
  27 #define DELTA 0x9E3779B9
  28 #define FULLROUNDS 10           /* 32 is overkill, 16 is strong crypto */
  29 #define PARTROUNDS 6            /* 6 gets complete mixing */
  30
  31 /* a, b, c, d - data; h0, h1 - accumulated hash */
  32 #define TEACORE(rounds)                                                 \
  33         do {                                                            \
  34                 uint32 sum = 0;                                         \
  35                 int n = rounds;                                         \
  36                 uint32 b0, b1;                                          \
  37                                                                         \
  38                 b0 = h0;                                                \
  39                 b1 = h1;                                                \
  40                                                                         \
  41                 do                                                      \
  42                 {                                                       \
  43                         sum += DELTA;                                   \
  44                         b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); \
  45                         b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); \
  46                 } while(--n);                                           \
  47                                                                         \
  48                 h0 += b0;                                               \
  49                 h1 += b1;                                               \
  50         } while(0)
  51
  52
  53 uint32 keyed_hash(const signed char *msg, int len)
  54 {
  55         uint32 k[] = { 0x9464a485, 0x542e1a94, 0x3e846bff, 0xb75bcfc3};
  56
  57         uint32 h0 = k[0], h1 = k[1];
  58         uint32 a, b, c, d;
  59         uint32 pad;
  60         int i;
  61
  62
  63         //      assert(len >= 0 && len < 256);
  64
  65         pad = (uint32)len | ((uint32)len << 8);
  66         pad |= pad << 16;
  67
  68         while(len >= 16)
  69         {
  70                 a = (uint32)msg[ 0]      |
  71                     (uint32)msg[ 1] << 8 |
  72                     (uint32)msg[ 2] << 16|
  73                     (uint32)msg[ 3] << 24;
  74                 b = (uint32)msg[ 4]      |
  75                     (uint32)msg[ 5] << 8 |
  76                     (uint32)msg[ 6] << 16|
  77                     (uint32)msg[ 7] << 24;
  78                 c = (uint32)msg[ 8]      |
  79                     (uint32)msg[ 9] << 8 |
  80                     (uint32)msg[10] << 16|
  81                     (uint32)msg[11] << 24;
  82                 d = (uint32)msg[12]      |
  83                     (uint32)msg[13] << 8 |
  84                     (uint32)msg[14] << 16|
  85                     (uint32)msg[15] << 24;
  86
  87                 TEACORE(PARTROUNDS);
  88
  89                 len -= 16;
  90                 msg += 16;
  91         }
  92
  93         if (len >= 12)
  94         {
  95                 //assert(len < 16);
  96                 if (len >= 16)
  97                     *(int *)0 = 0;
  98
  99                 a = (uint32)msg[ 0]      |
 100                     (uint32)msg[ 1] << 8 |
 101                     (uint32)msg[ 2] << 16|
 102                     (uint32)msg[ 3] << 24;
 103                 b = (uint32)msg[ 4]      |
 104                     (uint32)msg[ 5] << 8 |
 105                     (uint32)msg[ 6] << 16|
 106                     (uint32)msg[ 7] << 24;
 107                 c = (uint32)msg[ 8]      |
 108                     (uint32)msg[ 9] << 8 |
 109                     (uint32)msg[10] << 16|
 110                     (uint32)msg[11] << 24;
 111
 112                 d = pad;
 113                 for(i = 12; i < len; i++)
 114                 {
 115                         d <<= 8;
 116                         d |= msg[i];
 117                 }
 118         }
 119         else if (len >= 8)
 120         {
 121                 //assert(len < 12);
 122                 if (len >= 12)
 123                     *(int *)0 = 0;
 124                 a = (uint32)msg[ 0]      |
 125                     (uint32)msg[ 1] << 8 |
 126                     (uint32)msg[ 2] << 16|
 127                     (uint32)msg[ 3] << 24;
 128                 b = (uint32)msg[ 4]      |
 129                     (uint32)msg[ 5] << 8 |
 130                     (uint32)msg[ 6] << 16|
 131                     (uint32)msg[ 7] << 24;
 132
 133                 c = d = pad;
 134                 for(i = 8; i < len; i++)
 135                 {
 136                         c <<= 8;
 137                         c |= msg[i];
 138                 }
 139         }
 140         else if (len >= 4)
 141         {
 142                 //assert(len < 8);
 143                 if (len >= 8)
 144                     *(int *)0 = 0;
 145                 a = (uint32)msg[ 0]      |
 146                     (uint32)msg[ 1] << 8 |
 147                     (uint32)msg[ 2] << 16|
 148                     (uint32)msg[ 3] << 24;
 149
 150                 b = c = d = pad;
 151                 for(i = 4; i < len; i++)
 152                 {
 153                         b <<= 8;
 154                         b |= msg[i];
 155                 }
 156         }
 157         else
 158         {
 159                 //assert(len < 4);
 160                 if (len >= 4)
 161                     *(int *)0 = 0;
 162                 a = b = c = d = pad;
 163                 for(i = 0; i < len; i++)
 164                 {
 165                         a <<= 8;
 166                         a |= msg[i];
 167                 }
 168         }
 169
 170         TEACORE(FULLROUNDS);
 171
 172 /*      return 0;*/
 173         return h0^h1;
 174 }
 175
 176 /* What follows in this file is copyright 2000 by Hans Reiser, and the
 177  * licensing of what follows is governed by reiserfs/README */
 178
 179 uint32 yura_hash (const signed char *msg, int len)
 180 {
 181     int j, pow;
 182     uint32 a, c;
 183     int i;
 184
 185     for (pow=1,i=1; i < len; i++) pow = pow * 10;
 186
 187     if (len == 1)
 188         a = msg[0]-48;
 189     else
 190         a = (msg[0] - 48) * pow;
 191
 192     for (i=1; i < len; i++) {
 193         c = msg[i] - 48;
 194         for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
 195         a = a + c * pow;
 196     }
 197
 198     for (; i < 40; i++) {
 199         c = '0' - 48;
 200         for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
 201         a = a + c * pow;
 202     }
 203
 204     for (; i < 256; i++) {
 205         c = i;
 206         for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
 207         a = a + c * pow;
 208     }
 209
 210     a = a << 7;
 211     return a;
 212 }
 213
 214 uint32 r5_hash (const signed char *msg, int len)
 215 {
 216   uint32 a=0;
 217 // bonefish: len was ignored
 218 //  while(*msg) {
 219   while(len--) {
 220     a += *msg << 4;
 221     a += *msg >> 4;
 222     a *= 11;
 223     msg++;
 224    }
 225   return a;
 226 }
 227
 228
 229 // bonefish:
 230 // from reiserfs_fs.h:
 231 /* hash value occupies bits from 7 up to 30 */
 232 #define GET_HASH_VALUE(offset) ((offset) & 0x7fffff80LL)
 233 #define MAX_GENERATION_NUMBER  127
 234
 235 // bonefish:
 236 // derived from name.c: get_third_component()
 237 uint32
 238 key_offset_for_name(hash_function_t hash, const char *name, int len)
 239 {
 240     uint32 res;
 241
 242         if (!len || (len == 1 && name[0] == '.'))
 243                 return DOT_OFFSET;
 244         if (len == 2 && name[0] == '.' && name[1] == '.')
 245                 return DOT_DOT_OFFSET;
 246
 247         res = (*hash)((const signed char*)name, len);
 248
 249         // take bits from 7-th to 30-th including both bounds
 250         res = GET_HASH_VALUE(res);
 251         if (res == 0)
 252                 // needed to have no names before "." and ".." those have hash
 253                 // value == 0 and generation conters 1 and 2 accordingly
 254                 res = 128;
 255         return res + MAX_GENERATION_NUMBER;
 256 }
 257