1 /*- 2 * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org> 3 * Copyright (c) 2012, Vyacheslav Matyushin 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 * 27 * $FreeBSD$ 28 */ 29 30 #include <sys/param.h> 31 #include <sys/systm.h> 32 #include <sys/conf.h> 33 #include <sys/vnode.h> 34 #include <sys/stat.h> 35 #include <sys/mount.h> 36 37 #include <fs/ext2fs/htree.h> 38 #include <fs/ext2fs/inode.h> 39 #include <fs/ext2fs/ext2_mount.h> 40 #include <fs/ext2fs/ext2_extern.h> 41 42 /* F, G, and H are MD4 functions */ 43 #define F(x, y, z) (((x) & (y)) | ((~x) & (z))) 44 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) 45 #define H(x, y, z) ((x) ^ (y) ^ (z)) 46 47 /* ROTATE_LEFT rotates x left n bits */ 48 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n)))) 49 50 /* 51 * FF, GG, and HH are transformations for rounds 1, 2, and 3. 52 * Rotation is separated from addition to prevent recompuatation 53 */ 54 #define FF(a, b, c, d, x, s) { \ 55 (a) += F ((b), (c), (d)) + (x); \ 56 (a) = ROTATE_LEFT ((a), (s)); \ 57 } 58 59 #define GG(a, b, c, d, x, s) { \ 60 (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \ 61 (a) = ROTATE_LEFT ((a), (s)); \ 62 } 63 64 #define HH(a, b, c, d, x, s) { \ 65 (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \ 66 (a) = ROTATE_LEFT ((a), (s)); \ 67 } 68 69 /* 70 * MD4 basic transformation. It transforms state based on block. 71 * 72 * This is a half md4 algorithm because in Linux it uses this algorithm in dir 73 * index. This function is copied from kern/md4c.c file and is modified as 74 * necessary. 75 * 76 * The return value of this function is uint32_t in Linux, but actually we don't 77 * need to check this value. So in our version this function don't return any 78 * values. 79 */ 80 static void 81 ext2_half_md4(uint32_t hash[4], uint32_t data[8]) 82 { 83 uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3]; 84 85 /* Round 1 */ 86 FF(a, b, c, d, data[0], 3); 87 FF(d, a, b, c, data[1], 7); 88 FF(c, d, a, b, data[2], 11); 89 FF(b, c, d, a, data[3], 19); 90 FF(a, b, c, d, data[4], 3); 91 FF(d, a, b, c, data[5], 7); 92 FF(c, d, a, b, data[6], 11); 93 FF(b, c, d, a, data[7], 19); 94 95 /* Round 2 */ 96 GG(a, b, c, d, data[1], 3); 97 GG(d, a, b, c, data[3], 5); 98 GG(c, d, a, b, data[5], 9); 99 GG(b, c, d, a, data[7], 13); 100 GG(a, b, c, d, data[0], 3); 101 GG(d, a, b, c, data[2], 5); 102 GG(c, d, a, b, data[4], 9); 103 GG(b, c, d, a, data[6], 13); 104 105 /* Round 3 */ 106 HH(a, b, c, d, data[3], 3); 107 HH(d, a, b, c, data[7], 9); 108 HH(c, d, a, b, data[2], 11); 109 HH(b, c, d, a, data[6], 15); 110 HH(a, b, c, d, data[1], 3); 111 HH(d, a, b, c, data[5], 9); 112 HH(c, d, a, b, data[0], 11); 113 HH(b, c, d, a, data[4], 15); 114 115 hash[0] += a; 116 hash[1] += b; 117 hash[2] += c; 118 hash[3] += d; 119 } 120 121 /* 122 * Tiny Encryption Algorithm. 123 */ 124 static void 125 ext2_tea(uint32_t hash[4], uint32_t data[8]) 126 { 127 uint32_t tea_delta = 0x9E3779B9; 128 uint32_t sum; 129 uint32_t x = hash[0], y = hash[1]; 130 int n = 16; 131 int i = 1; 132 133 while (n-- > 0) { 134 sum = i * tea_delta; 135 x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]); 136 y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]); 137 i++; 138 } 139 140 hash[0] += x; 141 hash[1] += y; 142 } 143 144 static uint32_t 145 ext2_legacy_hash(const char *name, int len, int unsigned_char) 146 { 147 uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9; 148 uint32_t multi = 0x6D22F5; 149 const unsigned char *uname = (const unsigned char *)name; 150 const signed char *sname = (const signed char *)name; 151 int val, i; 152 153 for (i = 0; i < len; i++) { 154 if (unsigned_char) 155 val = (u_int)*uname++; 156 else 157 val = (int)*sname++; 158 159 h0 = h2 + (h1 ^ (val * multi)); 160 if (h0 & 0x80000000) 161 h0 -= 0x7FFFFFFF; 162 h2 = h1; 163 h1 = h0; 164 } 165 166 return (h1 << 1); 167 } 168 169 static void 170 ext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen, 171 int unsigned_char) 172 { 173 uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24); 174 uint32_t buf_val; 175 int len, i; 176 int buf_byte; 177 const unsigned char *ubuf = (const unsigned char *)src; 178 const signed char *sbuf = (const signed char *)src; 179 180 if (slen > dlen) 181 len = dlen; 182 else 183 len = slen; 184 185 buf_val = padding; 186 187 for (i = 0; i < len; i++) { 188 if (unsigned_char) 189 buf_byte = (u_int)ubuf[i]; 190 else 191 buf_byte = (int)sbuf[i]; 192 193 if ((i % 4) == 0) 194 buf_val = padding; 195 196 buf_val <<= 8; 197 buf_val += buf_byte; 198 199 if ((i % 4) == 3) { 200 *dst++ = buf_val; 201 dlen -= sizeof(uint32_t); 202 buf_val = padding; 203 } 204 } 205 206 dlen -= sizeof(uint32_t); 207 if (dlen >= 0) 208 *dst++ = buf_val; 209 210 dlen -= sizeof(uint32_t); 211 while (dlen >= 0) { 212 *dst++ = padding; 213 dlen -= sizeof(uint32_t); 214 } 215 } 216 217 int 218 ext2_htree_hash(const char *name, int len, 219 uint32_t *hash_seed, int hash_version, 220 uint32_t *hash_major, uint32_t *hash_minor) 221 { 222 uint32_t hash[4]; 223 uint32_t data[8]; 224 uint32_t major = 0, minor = 0; 225 int unsigned_char = 0; 226 227 if (!name || !hash_major) 228 return (-1); 229 230 if (len < 1 || len > 255) 231 goto error; 232 233 hash[0] = 0x67452301; 234 hash[1] = 0xEFCDAB89; 235 hash[2] = 0x98BADCFE; 236 hash[3] = 0x10325476; 237 238 if (hash_seed) 239 memcpy(hash, hash_seed, sizeof(hash)); 240 241 switch (hash_version) { 242 case EXT2_HTREE_TEA_UNSIGNED: 243 unsigned_char = 1; 244 case EXT2_HTREE_TEA: 245 while (len > 0) { 246 ext2_prep_hashbuf(name, len, data, 16, unsigned_char); 247 ext2_tea(hash, data); 248 len -= 16; 249 name += 16; 250 } 251 major = hash[0]; 252 minor = hash[1]; 253 break; 254 case EXT2_HTREE_LEGACY_UNSIGNED: 255 unsigned_char = 1; 256 case EXT2_HTREE_LEGACY: 257 major = ext2_legacy_hash(name, len, unsigned_char); 258 break; 259 case EXT2_HTREE_HALF_MD4_UNSIGNED: 260 unsigned_char = 1; 261 case EXT2_HTREE_HALF_MD4: 262 while (len > 0) { 263 ext2_prep_hashbuf(name, len, data, 32, unsigned_char); 264 ext2_half_md4(hash, data); 265 len -= 32; 266 name += 32; 267 } 268 major = hash[0]; 269 minor = hash[1]; 270 break; 271 default: 272 goto error; 273 } 274 275 major &= ~1; 276 if (major == (EXT2_HTREE_EOF << 1)) 277 major = (EXT2_HTREE_EOF - 1) << 1; 278 *hash_major = major; 279 if (hash_minor) 280 *hash_minor = minor; 281 282 return (0); 283 284 error: 285 *hash_major = 0; 286 if (hash_minor) 287 *hash_minor = 0; 288 return (-1); 289 } 290