| Start/ | End/ | |||
| True | False | - | Line | Source |
| 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/sched.h> | |||
| 15 | #include <linux/ext3_fs.h> | |||
| 16 | #include <linux/cryptohash.h> | |||
| 17 | ||||
| 18 | #define DELTA 0x9E3779B9 | |||
| 19 | ||||
| 0 | 0 | - | 20 | static void TEA_transform(__u32 buf[4], __u32 const in[]) |
| 21 | { | |||
| 22 | __u32 sum = 0; | |||
| 23 | __u32 b0 = buf[0], b1 = buf[1]; | |||
| 24 | __u32 a = in[0], b = in[1], c = in[2], d = in[3]; | |||
| 25 | int n = 16; | |||
| 26 | ||||
| 27 | do { | |||
| 28 | sum += DELTA; | |||
| 29 | b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); | |||
| 30 | b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); | |||
| 0 | 0 | - | 31 | } while(--n); |
| 32 | ||||
| 33 | buf[0] += b0; | |||
| 34 | buf[1] += b1; | |||
| 35 | } | |||
| 36 | ||||
| 37 | ||||
| 38 | /* The old legacy hash */ | |||
| 0 | 0 | - | 39 | static __u32 dx_hack_hash (const char *name, int len) |
| 40 | { | |||
| 41 | __u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; | |||
| 0 | 0 | - | 42 | while (len--) { |
| 43 | __u32 hash = hash1 + (hash0 ^ (*name++ * 7152373)); | |||
| 44 | ||||
| 0 | 0 | - | 45 | if (hash & 0x80000000) hash -= 0x7fffffff; |
| 46 | hash1 = hash0; | |||
| 47 | hash0 = hash; | |||
| 48 | } | |||
| 0 | - | 49 | return (hash0 << 1); | |
| 50 | } | |||
| 51 | ||||
| 0 | 0 | - | 52 | static void str2hashbuf(const char *msg, int len, __u32 *buf, int num) |
| 53 | { | |||
| 54 | __u32 pad, val; | |||
| 55 | int i; | |||
| 56 | ||||
| 57 | pad = (__u32)len | ((__u32)len << 8); | |||
| 58 | pad |= pad << 16; | |||
| 59 | ||||
| 60 | val = pad; | |||
| 0 | 0 | - | 61 | if (len > num*4) |
| 62 | len = num * 4; | |||
| 0 | 0 | - | 63 | for (i=0; i < len; i++) { |
| 0 | 0 | - | 64 | if ((i % 4) == 0) |
| 65 | val = pad; | |||
| 66 | val = msg[i] + (val << 8); | |||
| 0 | 0 | - | 67 | if ((i % 4) == 3) { |
| 68 | *buf++ = val; | |||
| 69 | val = pad; | |||
| 70 | num--; | |||
| 71 | } | |||
| 72 | } | |||
| 0 | 0 | - | 73 | if (--num >= 0) |
| 74 | *buf++ = val; | |||
| 0 | 0 | - | 75 | while (--num >= 0) |
| 76 | *buf++ = pad; | |||
| 77 | } | |||
| 78 | ||||
| 79 | /* | |||
| 80 | * Returns the hash of a filename. If len is 0 and name is NULL, then | |||
| 81 | * this function can be used to test whether or not a hash version is | |||
| 82 | * supported. | |||
| 83 | * | |||
| 84 | * The seed is an 4 longword (32 bits) "secret" which can be used to | |||
| 85 | * uniquify a hash. If the seed is all zero's, then some default seed | |||
| 86 | * may be used. | |||
| 87 | * | |||
| 88 | * A particular hash version specifies whether or not the seed is | |||
| 89 | * represented, and whether or not the returned hash is 32 bits or 64 | |||
| 90 | * bits. 32 bit hashes will return 0 for the minor hash. | |||
| 91 | */ | |||
| 0 | 0 | - | 92 | int ext3fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo) |
| 93 | { | |||
| 94 | __u32 hash; | |||
| 95 | __u32 minor_hash = 0; | |||
| 96 | const char *p; | |||
| 97 | int i; | |||
| 98 | __u32 in[8], buf[4]; | |||
| 99 | ||||
| 100 | /* Initialize the default seed for the hash checksum functions */ | |||
| 101 | buf[0] = 0x67452301; | |||
| 102 | buf[1] = 0xefcdab89; | |||
| 103 | buf[2] = 0x98badcfe; | |||
| 104 | buf[3] = 0x10325476; | |||
| 105 | ||||
| 106 | /* Check to see if the seed is all zero's */ | |||
| 0 | 0 | - | 107 | if (hinfo->seed) { |
| 0 | 0 | - | 108 | for (i=0; i < 4; i++) { |
| 0 | 0 | - | 109 | if (hinfo->seed[i]) |
| 0 | - | 110 | break; | |
| 111 | } | |||
| 0 | 0 | - | 112 | if (i < 4) |
| 113 | memcpy(buf, hinfo->seed, sizeof(buf)); | |||
| 114 | } | |||
| 115 | ||||
| 116 | switch (hinfo->hash_version) { | |||
| 0 | - | 117 | case DX_HASH_LEGACY: | |
| 118 | hash = dx_hack_hash(name, len); | |||
| 0 | - | 119 | break; | |
| 0 | - | 120 | case DX_HASH_HALF_MD4: | |
| 121 | p = name; | |||
| 0 | 0 | - | 122 | while (len > 0) { |
| 123 | str2hashbuf(p, len, in, 8); | |||
| 124 | half_md4_transform(buf, in); | |||
| 125 | len -= 32; | |||
| 126 | p += 32; | |||
| 127 | } | |||
| 128 | minor_hash = buf[2]; | |||
| 129 | hash = buf[1]; | |||
| 0 | - | 130 | break; | |
| 0 | - | 131 | case DX_HASH_TEA: | |
| 132 | p = name; | |||
| 0 | 0 | - | 133 | while (len > 0) { |
| 134 | str2hashbuf(p, len, in, 4); | |||
| 135 | TEA_transform(buf, in); | |||
| 136 | len -= 16; | |||
| 137 | p += 16; | |||
| 138 | } | |||
| 139 | hash = buf[0]; | |||
| 140 | minor_hash = buf[1]; | |||
| 0 | - | 141 | break; | |
| 0 | - | 142 | default: | |
| 143 | hinfo->hash = 0; | |||
| 0 | - | 144 | return -1; | |
| 145 | } | |||
| 146 | hash = hash & ~1; | |||
| 0 | 0 | - | 147 | if (hash == (EXT3_HTREE_EOF << 1)) |
| 148 | hash = (EXT3_HTREE_EOF-1) << 1; | |||
| 149 | hinfo->hash = hash; | |||
| 150 | hinfo->minor_hash = minor_hash; | |||
| 0 | - | 151 | return 0; | |
| 152 | } | |||
| ***TER 0% (0/47) of SOURCE FILE hash.c | ||||