ext2_hash.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    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         const unsigned char *ubuf = (const unsigned char *)src;
  200         const signed char *sbuf = (const signed char *)src;
  201         int len, i;
  202         int buf_byte;
  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                 /* FALLTHROUGH */
  269         case EXT2_HTREE_TEA:
  270                 while (len > 0) {
  271                         ext2_prep_hashbuf(name, len, data, 16, unsigned_char);
  272                         ext2_tea(hash, data);
  273                         len -= 16;
  274                         name += 16;
  275                 }
  276                 major = hash[0];
  277                 minor = hash[1];
  278                 break;
  279         case EXT2_HTREE_LEGACY_UNSIGNED:
  280                 unsigned_char = 1;
  281                 /* FALLTHROUGH */
  282         case EXT2_HTREE_LEGACY:
  283                 major = ext2_legacy_hash(name, len, unsigned_char);
  284                 break;
  285         case EXT2_HTREE_HALF_MD4_UNSIGNED:
  286                 unsigned_char = 1;
  287                 /* FALLTHROUGH */
  288         case EXT2_HTREE_HALF_MD4:
  289                 while (len > 0) {
  290                         ext2_prep_hashbuf(name, len, data, 32, unsigned_char);
  291                         ext2_half_md4(hash, data);
  292                         len -= 32;
  293                         name += 32;
  294                 }
  295                 major = hash[1];
  296                 minor = hash[2];
  297                 break;
  298         default:
  299                 goto error;
  300         }
  301 
  302         major &= ~1;
  303         if (major == (EXT2_HTREE_EOF << 1))
  304                 major = (EXT2_HTREE_EOF - 1) << 1;
  305         *hash_major = major;
  306         if (hash_minor)
  307                 *hash_minor = minor;
  308 
  309         return (0);
  310 
  311 error:
  312         *hash_major = 0;
  313         if (hash_minor)
  314                 *hash_minor = 0;
  315         return (-1);
  316 }
Cache object: 3597ca184bb8f3bc0222bdf2e60d63db
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/fs/ext2fs/ext2_hash.c

FreeBSD/Linux Kernel Cross Reference
sys/fs/ext2fs/ext2_hash.c
