fs/ext3/hash.c

   1 /*
   2  *  linux/fs/ext3/hash.c
   3  *
   4  * Copyright (C) 2002 by Theodore Ts'o
   5  *
   6  * This file is released under the GPL v2.
   7  *
   8  * This file may be redistributed under the terms of the GNU Public
   9  * License.
  10  */
  11
  12 #include <linux/fs.h>
  13 #include <linux/jbd.h>
  14 #include <linux/ext3_fs.h>
  15 #include <linux/cryptohash.h>
  16
  17 #define DELTA 0x9E3779B9
  18
  19 static void TEA_transform(__u32 buf[4], __u32 const in[])
  20 {
  21         __u32   sum = 0;
  22         __u32   b0 = buf[0], b1 = buf[1];
  23         __u32   a = in[0], b = in[1], c = in[2], d = in[3];
  24         int     n = 16;
  25
  26         do {
  27                 sum += DELTA;
  28                 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
  29                 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
  30         } while(--n);
  31
  32         buf[0] += b0;
  33         buf[1] += b1;
  34 }
  35
  36
  37 /* The old legacy hash */
  38 static __u32 dx_hack_hash_unsigned(const char *name, int len)
  39 {
  40         __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
  41         const unsigned char *ucp = (const unsigned char *) name;
  42
  43         while (len--) {
  44                 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373));
  45
  46                 if (hash & 0x80000000)
  47                         hash -= 0x7fffffff;
  48                 hash1 = hash0;
  49                 hash0 = hash;
  50         }
  51         return hash0 << 1;
  52 }
  53
  54 static __u32 dx_hack_hash_signed(const char *name, int len)
  55 {
  56         __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
  57         const signed char *scp = (const signed char *) name;
  58
  59         while (len--) {
  60                 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373));
  61
  62                 if (hash & 0x80000000)
  63                         hash -= 0x7fffffff;
  64                 hash1 = hash0;
  65                 hash0 = hash;
  66         }
  67         return hash0 << 1;
  68 }
  69
  70 static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num)
  71 {
  72         __u32   pad, val;
  73         int     i;
  74         const signed char *scp = (const signed char *) msg;
  75
  76         pad = (__u32)len | ((__u32)len << 8);
  77         pad |= pad << 16;
  78
  79         val = pad;
  80         if (len > num*4)
  81                 len = num * 4;
  82         for (i = 0; i < len; i++) {
  83                 if ((i % 4) == 0)
  84                         val = pad;
  85                 val = ((int) scp[i]) + (val << 8);
  86                 if ((i % 4) == 3) {
  87                         *buf++ = val;
  88                         val = pad;
  89                         num--;
  90                 }
  91         }
  92         if (--num >= 0)
  93                 *buf++ = val;
  94         while (--num >= 0)
  95                 *buf++ = pad;
  96 }
  97
  98 static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num)
  99 {
 100         __u32   pad, val;
 101         int     i;
 102         const unsigned char *ucp = (const unsigned char *) msg;
 103
 104         pad = (__u32)len | ((__u32)len << 8);
 105         pad |= pad << 16;
 106
 107         val = pad;
 108         if (len > num*4)
 109                 len = num * 4;
 110         for (i=0; i < len; i++) {
 111                 if ((i % 4) == 0)
 112                         val = pad;
 113                 val = ((int) ucp[i]) + (val << 8);
 114                 if ((i % 4) == 3) {
 115                         *buf++ = val;
 116                         val = pad;
 117                         num--;
 118                 }
 119         }
 120         if (--num >= 0)
 121                 *buf++ = val;
 122         while (--num >= 0)
 123                 *buf++ = pad;
 124 }
 125
 126 /*
 127  * Returns the hash of a filename.  If len is 0 and name is NULL, then
 128  * this function can be used to test whether or not a hash version is
 129  * supported.
 130  *
 131  * The seed is an 4 longword (32 bits) "secret" which can be used to
 132  * uniquify a hash.  If the seed is all zero's, then some default seed
 133  * may be used.
 134  *
 135  * A particular hash version specifies whether or not the seed is
 136  * represented, and whether or not the returned hash is 32 bits or 64
 137  * bits.  32 bit hashes will return 0 for the minor hash.
 138  */
 139 int ext3fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
 140 {
 141         __u32   hash;
 142         __u32   minor_hash = 0;
 143         const char      *p;
 144         int             i;
 145         __u32           in[8], buf[4];
 146         void            (*str2hashbuf)(const char *, int, __u32 *, int) =
 147                                 str2hashbuf_signed;
 148
 149         /* Initialize the default seed for the hash checksum functions */
 150         buf[0] = 0x67452301;
 151         buf[1] = 0xefcdab89;
 152         buf[2] = 0x98badcfe;
 153         buf[3] = 0x10325476;
 154
 155         /* Check to see if the seed is all zero's */
 156         if (hinfo->seed) {
 157                 for (i=0; i < 4; i++) {
 158                         if (hinfo->seed[i])
 159                                 break;
 160                 }
 161                 if (i < 4)
 162                         memcpy(buf, hinfo->seed, sizeof(buf));
 163         }
 164
 165         switch (hinfo->hash_version) {
 166         case DX_HASH_LEGACY_UNSIGNED:
 167                 hash = dx_hack_hash_unsigned(name, len);
 168                 break;
 169         case DX_HASH_LEGACY:
 170                 hash = dx_hack_hash_signed(name, len);
 171                 break;
 172         case DX_HASH_HALF_MD4_UNSIGNED:
 173                 str2hashbuf = str2hashbuf_unsigned;
 174         case DX_HASH_HALF_MD4:
 175                 p = name;
 176                 while (len > 0) {
 177                         (*str2hashbuf)(p, len, in, 8);
 178                         half_md4_transform(buf, in);
 179                         len -= 32;
 180                         p += 32;
 181                 }
 182                 minor_hash = buf[2];
 183                 hash = buf[1];
 184                 break;
 185         case DX_HASH_TEA_UNSIGNED:
 186                 str2hashbuf = str2hashbuf_unsigned;
 187         case DX_HASH_TEA:
 188                 p = name;
 189                 while (len > 0) {
 190                         (*str2hashbuf)(p, len, in, 4);
 191                         TEA_transform(buf, in);
 192                         len -= 16;
 193                         p += 16;
 194                 }
 195                 hash = buf[0];
 196                 minor_hash = buf[1];
 197                 break;
 198         default:
 199                 hinfo->hash = 0;
 200                 return -1;
 201         }
 202         hash = hash & ~1;
 203         if (hash == (EXT3_HTREE_EOF << 1))
 204                 hash = (EXT3_HTREE_EOF-1) << 1;
 205         hinfo->hash = hash;
 206         hinfo->minor_hash = minor_hash;
 207         return 0;
 208 }