Version:  2.0.40 2.2.26 2.4.37 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18

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

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us