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