fs/reiserfs/hashes.c

   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 //
  16 // keyed_hash
  17 // yura_hash
  18 // r5_hash
  19 //
  20
  21 #include <linux/kernel.h>       /* for printk() as called by BUG() */
  22 #include <asm/types.h>
  23 #include <asm/page.h>
  24
  25
  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                 u32 sum = 0;                                            \
  35                 int n = rounds;                                         \
  36                 u32 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 u32 keyed_hash(const signed char *msg, int len)
  54 {
  55         u32 k[] = { 0x9464a485, 0x542e1a94, 0x3e846bff, 0xb75bcfc3};
  56
  57         u32 h0 = k[0], h1 = k[1];
  58         u32 a, b, c, d;
  59         u32 pad;
  60         int i;
  61
  62         //      assert(len >= 0 && len < 256);
  63
  64         pad = (u32)len | ((u32)len << 8);
  65         pad |= pad << 16;
  66
  67         while(len >= 16)
  68         {
  69                 a = (u32)msg[ 0]      |
  70                     (u32)msg[ 1] << 8 |
  71                     (u32)msg[ 2] << 16|
  72                     (u32)msg[ 3] << 24;
  73                 b = (u32)msg[ 4]      |
  74                     (u32)msg[ 5] << 8 |
  75                     (u32)msg[ 6] << 16|
  76                     (u32)msg[ 7] << 24;
  77                 c = (u32)msg[ 8]      |
  78                     (u32)msg[ 9] << 8 |
  79                     (u32)msg[10] << 16|
  80                     (u32)msg[11] << 24;
  81                 d = (u32)msg[12]      |
  82                     (u32)msg[13] << 8 |
  83                     (u32)msg[14] << 16|
  84                     (u32)msg[15] << 24;
  85
  86                 TEACORE(PARTROUNDS);
  87
  88                 len -= 16;
  89                 msg += 16;
  90         }
  91
  92         if (len >= 12)
  93         {
  94                 //assert(len < 16);
  95                 if (len >= 16)
  96                     BUG();
  97
  98                 a = (u32)msg[ 0]      |
  99                     (u32)msg[ 1] << 8 |
 100                     (u32)msg[ 2] << 16|
 101                     (u32)msg[ 3] << 24;
 102                 b = (u32)msg[ 4]      |
 103                     (u32)msg[ 5] << 8 |
 104                     (u32)msg[ 6] << 16|
 105                     (u32)msg[ 7] << 24;
 106                 c = (u32)msg[ 8]      |
 107                     (u32)msg[ 9] << 8 |
 108                     (u32)msg[10] << 16|
 109                     (u32)msg[11] << 24;
 110
 111                 d = pad;
 112                 for(i = 12; i < len; i++)
 113                 {
 114                         d <<= 8;
 115                         d |= msg[i];
 116                 }
 117         }
 118         else if (len >= 8)
 119         {
 120                 //assert(len < 12);
 121                 if (len >= 12)
 122                     BUG();
 123                 a = (u32)msg[ 0]      |
 124                     (u32)msg[ 1] << 8 |
 125                     (u32)msg[ 2] << 16|
 126                     (u32)msg[ 3] << 24;
 127                 b = (u32)msg[ 4]      |
 128                     (u32)msg[ 5] << 8 |
 129                     (u32)msg[ 6] << 16|
 130                     (u32)msg[ 7] << 24;
 131
 132                 c = d = pad;
 133                 for(i = 8; i < len; i++)
 134                 {
 135                         c <<= 8;
 136                         c |= msg[i];
 137                 }
 138         }
 139         else if (len >= 4)
 140         {
 141                 //assert(len < 8);
 142                 if (len >= 8)
 143                     BUG();
 144                 a = (u32)msg[ 0]      |
 145                     (u32)msg[ 1] << 8 |
 146                     (u32)msg[ 2] << 16|
 147                     (u32)msg[ 3] << 24;
 148
 149                 b = c = d = pad;
 150                 for(i = 4; i < len; i++)
 151                 {
 152                         b <<= 8;
 153                         b |= msg[i];
 154                 }
 155         }
 156         else
 157         {
 158                 //assert(len < 4);
 159                 if (len >= 4)
 160                     BUG();
 161                 a = b = c = d = pad;
 162                 for(i = 0; i < len; i++)
 163                 {
 164                         a <<= 8;
 165                         a |= msg[i];
 166                 }
 167         }
 168
 169         TEACORE(FULLROUNDS);
 170
 171 /*      return 0;*/
 172         return h0^h1;
 173 }
 174
 175 /* What follows in this file is copyright 2000-2002 by Hans Reiser, and the
 176  * licensing of what follows is governed by reiserfs/README */
 177
 178 u32 yura_hash (const signed char *msg, int len)
 179 {
 180     int j, pow;
 181     u32 a, c;
 182     int i;
 183
 184     for (pow=1,i=1; i < len; i++) pow = pow * 10;
 185
 186     if (len == 1)
 187         a = msg[0]-48;
 188     else
 189         a = (msg[0] - 48) * pow;
 190
 191     for (i=1; i < len; i++) {
 192         c = msg[i] - 48;
 193         for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
 194         a = a + c * pow;
 195     }
 196
 197     for (; i < 40; i++) {
 198         c = '0' - 48;
 199         for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
 200         a = a + c * pow;
 201     }
 202
 203     for (; i < 256; i++) {
 204         c = i;
 205         for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
 206         a = a + c * pow;
 207     }
 208
 209     a = a << 7;
 210     return a;
 211 }
 212
 213 u32 r5_hash (const signed char *msg, int len)
 214 {
 215   u32 a=0;
 216   while(*msg) {
 217     a += *msg << 4;
 218     a += *msg >> 4;
 219     a *= 11;
 220     msg++;
 221    }
 222   return a;
 223 }