The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

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

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

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

Cache object: 70c53a1c6a579982f13814a33754c5f0


[ 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.