sys/fs/ext2fs/ext2_hash.c

   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 /*
  31  * The following notice applies to the code in ext2_half_md4():
  32  *
  33  * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved.
  34  *
  35  * License to copy and use this software is granted provided that it
  36  * is identified as the "RSA Data Security, Inc. MD4 Message-Digest
  37  * Algorithm" in all material mentioning or referencing this software
  38  * or this function.
  39  *
  40  * License is also granted to make and use derivative works provided
  41  * that such works are identified as "derived from the RSA Data
  42  * Security, Inc. MD4 Message-Digest Algorithm" in all material
  43  * mentioning or referencing the derived work.
  44  *
  45  * RSA Data Security, Inc. makes no representations concerning either
  46  * the merchantability of this software or the suitability of this
  47  * software for any particular purpose. It is provided "as is"
  48  * without express or implied warranty of any kind.
  49  *
  50  * These notices must be retained in any copies of any part of this
  51  * documentation and/or software.
  52  */
  53
  54 #include <sys/param.h>
  55 #include <sys/systm.h>
  56 #include <sys/conf.h>
  57 #include <sys/vnode.h>
  58 #include <sys/stat.h>
  59 #include <sys/mount.h>
  60
  61 #include <fs/ext2fs/htree.h>
  62 #include <fs/ext2fs/inode.h>
  63 #include <fs/ext2fs/ext2_mount.h>
  64 #include <fs/ext2fs/ext2_extern.h>
  65
  66 /* F, G, and H are MD4 functions */
  67 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
  68 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
  69 #define H(x, y, z) ((x) ^ (y) ^ (z))
  70
  71 /* ROTATE_LEFT rotates x left n bits */
  72 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
  73
  74 /*
  75  * FF, GG, and HH are transformations for rounds 1, 2, and 3.
  76  * Rotation is separated from addition to prevent recomputation.
  77  */
  78 #define FF(a, b, c, d, x, s) { \
  79         (a) += F ((b), (c), (d)) + (x); \
  80         (a) = ROTATE_LEFT ((a), (s)); \
  81 }
  82
  83 #define GG(a, b, c, d, x, s) { \
  84         (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \
  85         (a) = ROTATE_LEFT ((a), (s)); \
  86 }
  87
  88 #define HH(a, b, c, d, x, s) { \
  89         (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \
  90         (a) = ROTATE_LEFT ((a), (s)); \
  91 }
  92
  93 /*
  94  * MD4 basic transformation.  It transforms state based on block.
  95  *
  96  * This is a half md4 algorithm since Linux uses this algorithm for dir
  97  * index.  This function is derived from the RSA Data Security, Inc. MD4
  98  * Message-Digest Algorithm and was modified as necessary.
  99  *
 100  * The return value of this function is uint32_t in Linux, but actually we don't
 101  * need to check this value, so in our version this function doesn't return any
 102  * value.
 103  */
 104 static void
 105 ext2_half_md4(uint32_t hash[4], uint32_t data[8])
 106 {
 107         uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3];
 108
 109         /* Round 1 */
 110         FF(a, b, c, d, data[0],  3);
 111         FF(d, a, b, c, data[1],  7);
 112         FF(c, d, a, b, data[2], 11);
 113         FF(b, c, d, a, data[3], 19);
 114         FF(a, b, c, d, data[4],  3);
 115         FF(d, a, b, c, data[5],  7);
 116         FF(c, d, a, b, data[6], 11);
 117         FF(b, c, d, a, data[7], 19);
 118
 119         /* Round 2 */
 120         GG(a, b, c, d, data[1],  3);
 121         GG(d, a, b, c, data[3],  5);
 122         GG(c, d, a, b, data[5],  9);
 123         GG(b, c, d, a, data[7], 13);
 124         GG(a, b, c, d, data[0],  3);
 125         GG(d, a, b, c, data[2],  5);
 126         GG(c, d, a, b, data[4],  9);
 127         GG(b, c, d, a, data[6], 13);
 128
 129         /* Round 3 */
 130         HH(a, b, c, d, data[3],  3);
 131         HH(d, a, b, c, data[7],  9);
 132         HH(c, d, a, b, data[2], 11);
 133         HH(b, c, d, a, data[6], 15);
 134         HH(a, b, c, d, data[1],  3);
 135         HH(d, a, b, c, data[5],  9);
 136         HH(c, d, a, b, data[0], 11);
 137         HH(b, c, d, a, data[4], 15);
 138
 139         hash[0] += a;
 140         hash[1] += b;
 141         hash[2] += c;
 142         hash[3] += d;
 143 }
 144
 145 /*
 146  * Tiny Encryption Algorithm.
 147  */
 148 static void
 149 ext2_tea(uint32_t hash[4], uint32_t data[8])
 150 {
 151         uint32_t tea_delta = 0x9E3779B9;
 152         uint32_t sum;
 153         uint32_t x = hash[0], y = hash[1];
 154         int n = 16;
 155         int i = 1;
 156
 157         while (n-- > 0) {
 158                 sum = i * tea_delta;
 159                 x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]);
 160                 y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]);
 161                 i++;
 162         }
 163
 164         hash[0] += x;
 165         hash[1] += y;
 166 }
 167
 168 static uint32_t
 169 ext2_legacy_hash(const char *name, int len, int unsigned_char)
 170 {
 171         uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9;
 172         uint32_t multi = 0x6D22F5;
 173         const unsigned char *uname = (const unsigned char *)name;
 174         const signed char *sname = (const signed char *)name;
 175         int val, i;
 176
 177         for (i = 0; i < len; i++) {
 178                 if (unsigned_char)
 179                         val = (u_int)*uname++;
 180                 else
 181                         val = (int)*sname++;
 182
 183                 h0 = h2 + (h1 ^ (val * multi));
 184                 if (h0 & 0x80000000)
 185                         h0 -= 0x7FFFFFFF;
 186                 h2 = h1;
 187                 h1 = h0;
 188         }
 189
 190         return (h1 << 1);
 191 }
 192
 193 static void
 194 ext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen,
 195              int unsigned_char)
 196 {
 197         uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24);
 198         uint32_t buf_val;
 199         int len, i;
 200         int buf_byte;
 201         const unsigned char *ubuf = (const unsigned char *)src;
 202         const signed char *sbuf = (const signed char *)src;
 203
 204         if (slen > dlen)
 205                 len = dlen;
 206         else
 207                 len = slen;
 208
 209         buf_val = padding;
 210
 211         for (i = 0; i < len; i++) {
 212                 if (unsigned_char)
 213                         buf_byte = (u_int)ubuf[i];
 214                 else
 215                         buf_byte = (int)sbuf[i];
 216
 217                 if ((i % 4) == 0)
 218                         buf_val = padding;
 219
 220                 buf_val <<= 8;
 221                 buf_val += buf_byte;
 222
 223                 if ((i % 4) == 3) {
 224                         *dst++ = buf_val;
 225                         dlen -= sizeof(uint32_t);
 226                         buf_val = padding;
 227                 }
 228         }
 229
 230         dlen -= sizeof(uint32_t);
 231         if (dlen >= 0)
 232                 *dst++ = buf_val;
 233
 234         dlen -= sizeof(uint32_t);
 235         while (dlen >= 0) {
 236                 *dst++ = padding;
 237                 dlen -= sizeof(uint32_t);
 238         }
 239 }
 240
 241 int
 242 ext2_htree_hash(const char *name, int len,
 243                 uint32_t *hash_seed, int hash_version,
 244                 uint32_t *hash_major, uint32_t *hash_minor)
 245 {
 246         uint32_t hash[4];
 247         uint32_t data[8];
 248         uint32_t major = 0, minor = 0;
 249         int unsigned_char = 0;
 250
 251         if (!name || !hash_major)
 252                 return (-1);
 253
 254         if (len < 1 || len > 255)
 255                 goto error;
 256
 257         hash[0] = 0x67452301;
 258         hash[1] = 0xEFCDAB89;
 259         hash[2] = 0x98BADCFE;
 260         hash[3] = 0x10325476;
 261
 262         if (hash_seed)
 263                 memcpy(hash, hash_seed, sizeof(hash));
 264
 265         switch (hash_version) {
 266         case EXT2_HTREE_TEA_UNSIGNED:
 267                 unsigned_char = 1;
 268         case EXT2_HTREE_TEA:
 269                 while (len > 0) {
 270                         ext2_prep_hashbuf(name, len, data, 16, unsigned_char);
 271                         ext2_tea(hash, data);
 272                         len -= 16;
 273                         name += 16;
 274                 }
 275                 major = hash[0];
 276                 minor = hash[1];
 277                 break;
 278         case EXT2_HTREE_LEGACY_UNSIGNED:
 279                 unsigned_char = 1;
 280         case EXT2_HTREE_LEGACY:
 281                 major = ext2_legacy_hash(name, len, unsigned_char);
 282                 break;
 283         case EXT2_HTREE_HALF_MD4_UNSIGNED:
 284                 unsigned_char = 1;
 285         case EXT2_HTREE_HALF_MD4:
 286                 while (len > 0) {
 287                         ext2_prep_hashbuf(name, len, data, 32, unsigned_char);
 288                         ext2_half_md4(hash, data);
 289                         len -= 32;
 290                         name += 32;
 291                 }
 292                 major = hash[0];
 293                 minor = hash[1];
 294                 break;
 295         default:
 296                 goto error;
 297         }
 298
 299         major &= ~1;
 300         if (major == (EXT2_HTREE_EOF << 1))
 301                 major = (EXT2_HTREE_EOF - 1) << 1;
 302         *hash_major = major;
 303         if (hash_minor)
 304                 *hash_minor = minor;
 305
 306         return (0);
 307
 308 error:
 309         *hash_major = 0;
 310         if (hash_minor)
 311                 *hash_minor = 0;
 312         return (-1);
 313 }