src/ext4_hash.c

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