lwext4/ext4_hash.c

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