-/*\r
- * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)\r
- *\r
- * FreeBSD:\r
- * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org>\r
- * Copyright (c) 2012, Vyacheslav Matyushin\r
- * All rights reserved.\r
- *\r
- * Redistribution and use in source and binary forms, with or without\r
- * modification, are permitted provided that the following conditions\r
- * are met:\r
- * 1. Redistributions of source code must retain the above copyright\r
- * notice, this list of conditions and the following disclaimer.\r
- * 2. Redistributions in binary form must reproduce the above copyright\r
- * notice, this list of conditions and the following disclaimer in the\r
- * documentation and/or other materials provided with the distribution.\r
- *\r
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND\r
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE\r
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\r
- * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE\r
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL\r
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS\r
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)\r
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT\r
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY\r
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF\r
- * SUCH DAMAGE.\r
- *\r
- */\r
-\r
-/*\r
- * The following notice applies to the code in ext2_half_md4():\r
- *\r
- * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved.\r
- *\r
- * License to copy and use this software is granted provided that it\r
- * is identified as the "RSA Data Security, Inc. MD4 Message-Digest\r
- * Algorithm" in all material mentioning or referencing this software\r
- * or this function.\r
- *\r
- * License is also granted to make and use derivative works provided\r
- * that such works are identified as "derived from the RSA Data\r
- * Security, Inc. MD4 Message-Digest Algorithm" in all material\r
- * mentioning or referencing the derived work.\r
- *\r
- * RSA Data Security, Inc. makes no representations concerning either\r
- * the merchantability of this software or the suitability of this\r
- * software for any particular purpose. It is provided "as is"\r
- * without express or implied warranty of any kind.\r
- *\r
- * These notices must be retained in any copies of any part of this\r
- * documentation and/or software.\r
- */\r
-\r
-/** @addtogroup lwext4\r
- * @{\r
- */\r
-/**\r
- * @file ext4_hash.c\r
- * @brief Directory indexing hash functions.\r
- */\r
-\r
-#include <ext4_config.h>\r
-#include <ext4_types.h>\r
-#include <string.h>\r
-#include <ext4_errno.h>\r
-\r
-/* F, G, and H are MD4 functions */\r
-#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))\r
-#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))\r
-#define H(x, y, z) ((x) ^ (y) ^ (z))\r
-\r
-/* ROTATE_LEFT rotates x left n bits */\r
-#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))\r
-\r
-/*\r
- * FF, GG, and HH are transformations for rounds 1, 2, and 3.\r
- * Rotation is separated from addition to prevent recomputation.\r
- */\r
-#define FF(a, b, c, d, x, s) \\r
- { \\r
- (a) += F((b), (c), (d)) + (x); \\r
- (a) = ROTATE_LEFT((a), (s)); \\r
- \\r
-}\r
-\r
-#define GG(a, b, c, d, x, s) \\r
- { \\r
- (a) += G((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \\r
- (a) = ROTATE_LEFT((a), (s)); \\r
- \\r
-}\r
-\r
-#define HH(a, b, c, d, x, s) \\r
- { \\r
- (a) += H((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \\r
- (a) = ROTATE_LEFT((a), (s)); \\r
- \\r
-}\r
-\r
-/*\r
- * MD4 basic transformation. It transforms state based on block.\r
- *\r
- * This is a half md4 algorithm since Linux uses this algorithm for dir\r
- * index. This function is derived from the RSA Data Security, Inc. MD4\r
- * Message-Digest Algorithm and was modified as necessary.\r
- *\r
- * The return value of this function is uint32_t in Linux, but actually we don't\r
- * need to check this value, so in our version this function doesn't return any\r
- * value.\r
- */\r
-static void ext2_half_md4(uint32_t hash[4], uint32_t data[8])\r
-{\r
- uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3];\r
-\r
- /* Round 1 */\r
- FF(a, b, c, d, data[0], 3);\r
- FF(d, a, b, c, data[1], 7);\r
- FF(c, d, a, b, data[2], 11);\r
- FF(b, c, d, a, data[3], 19);\r
- FF(a, b, c, d, data[4], 3);\r
- FF(d, a, b, c, data[5], 7);\r
- FF(c, d, a, b, data[6], 11);\r
- FF(b, c, d, a, data[7], 19);\r
-\r
- /* Round 2 */\r
- GG(a, b, c, d, data[1], 3);\r
- GG(d, a, b, c, data[3], 5);\r
- GG(c, d, a, b, data[5], 9);\r
- GG(b, c, d, a, data[7], 13);\r
- GG(a, b, c, d, data[0], 3);\r
- GG(d, a, b, c, data[2], 5);\r
- GG(c, d, a, b, data[4], 9);\r
- GG(b, c, d, a, data[6], 13);\r
-\r
- /* Round 3 */\r
- HH(a, b, c, d, data[3], 3);\r
- HH(d, a, b, c, data[7], 9);\r
- HH(c, d, a, b, data[2], 11);\r
- HH(b, c, d, a, data[6], 15);\r
- HH(a, b, c, d, data[1], 3);\r
- HH(d, a, b, c, data[5], 9);\r
- HH(c, d, a, b, data[0], 11);\r
- HH(b, c, d, a, data[4], 15);\r
-\r
- hash[0] += a;\r
- hash[1] += b;\r
- hash[2] += c;\r
- hash[3] += d;\r
-}\r
-\r
-/*\r
- * Tiny Encryption Algorithm.\r
- */\r
-static void ext2_tea(uint32_t hash[4], uint32_t data[8])\r
-{\r
- uint32_t tea_delta = 0x9E3779B9;\r
- uint32_t sum;\r
- uint32_t x = hash[0], y = hash[1];\r
- int n = 16;\r
- int i = 1;\r
-\r
- while (n-- > 0) {\r
- sum = i * tea_delta;\r
- x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]);\r
- y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]);\r
- i++;\r
- }\r
-\r
- hash[0] += x;\r
- hash[1] += y;\r
-}\r
-\r
-static uint32_t ext2_legacy_hash(const char *name, int len, int unsigned_char)\r
-{\r
- uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9;\r
- uint32_t multi = 0x6D22F5;\r
- const unsigned char *uname = (const unsigned char *)name;\r
- const signed char *sname = (const signed char *)name;\r
- int val, i;\r
-\r
- for (i = 0; i < len; i++) {\r
- if (unsigned_char)\r
- val = (unsigned int)*uname++;\r
- else\r
- val = (int)*sname++;\r
-\r
- h0 = h2 + (h1 ^ (val * multi));\r
- if (h0 & 0x80000000)\r
- h0 -= 0x7FFFFFFF;\r
- h2 = h1;\r
- h1 = h0;\r
- }\r
-\r
- return (h1 << 1);\r
-}\r
-\r
-static void ext2_prep_hashbuf(const char *src, uint32_t slen, uint32_t *dst,\r
- int dlen, int unsigned_char)\r
-{\r
- uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24);\r
- uint32_t buf_val;\r
- int len, i;\r
- int buf_byte;\r
- const unsigned char *ubuf = (const unsigned char *)src;\r
- const signed char *sbuf = (const signed char *)src;\r
-\r
- if (slen > (uint32_t)dlen)\r
- len = dlen;\r
- else\r
- len = slen;\r
-\r
- buf_val = padding;\r
-\r
- for (i = 0; i < len; i++) {\r
- if (unsigned_char)\r
- buf_byte = (unsigned int)ubuf[i];\r
- else\r
- buf_byte = (int)sbuf[i];\r
-\r
- if ((i % 4) == 0)\r
- buf_val = padding;\r
-\r
- buf_val <<= 8;\r
- buf_val += buf_byte;\r
-\r
- if ((i % 4) == 3) {\r
- *dst++ = buf_val;\r
- dlen -= sizeof(uint32_t);\r
- buf_val = padding;\r
- }\r
- }\r
-\r
- dlen -= sizeof(uint32_t);\r
- if (dlen >= 0)\r
- *dst++ = buf_val;\r
-\r
- dlen -= sizeof(uint32_t);\r
- while (dlen >= 0) {\r
- *dst++ = padding;\r
- dlen -= sizeof(uint32_t);\r
- }\r
-}\r
-\r
-int ext2_htree_hash(const char *name, int len, const uint32_t *hash_seed,\r
- int hash_version, uint32_t *hash_major,\r
- uint32_t *hash_minor)\r
-{\r
- uint32_t hash[4];\r
- uint32_t data[8];\r
- uint32_t major = 0, minor = 0;\r
- int unsigned_char = 0;\r
-\r
- if (!name || !hash_major)\r
- return (-1);\r
-\r
- if (len < 1 || len > 255)\r
- goto error;\r
-\r
- hash[0] = 0x67452301;\r
- hash[1] = 0xEFCDAB89;\r
- hash[2] = 0x98BADCFE;\r
- hash[3] = 0x10325476;\r
-\r
- if (hash_seed)\r
- memcpy(hash, hash_seed, sizeof(hash));\r
-\r
- switch (hash_version) {\r
- case EXT2_HTREE_TEA_UNSIGNED:\r
- unsigned_char = 1;\r
- case EXT2_HTREE_TEA:\r
- while (len > 0) {\r
- ext2_prep_hashbuf(name, len, data, 16, unsigned_char);\r
- ext2_tea(hash, data);\r
- len -= 16;\r
- name += 16;\r
- }\r
- major = hash[0];\r
- minor = hash[1];\r
- break;\r
- case EXT2_HTREE_LEGACY_UNSIGNED:\r
- unsigned_char = 1;\r
- case EXT2_HTREE_LEGACY:\r
- major = ext2_legacy_hash(name, len, unsigned_char);\r
- break;\r
- case EXT2_HTREE_HALF_MD4_UNSIGNED:\r
- unsigned_char = 1;\r
- case EXT2_HTREE_HALF_MD4:\r
- while (len > 0) {\r
- ext2_prep_hashbuf(name, len, data, 32, unsigned_char);\r
- ext2_half_md4(hash, data);\r
- len -= 32;\r
- name += 32;\r
- }\r
- major = hash[1];\r
- minor = hash[2];\r
- break;\r
- default:\r
- goto error;\r
- }\r
-\r
- major &= ~1;\r
- if (major == (EXT2_HTREE_EOF << 1))\r
- major = (EXT2_HTREE_EOF - 1) << 1;\r
- *hash_major = major;\r
- if (hash_minor)\r
- *hash_minor = minor;\r
-\r
- return EOK;\r
-\r
-error:\r
- *hash_major = 0;\r
- if (hash_minor)\r
- *hash_minor = 0;\r
- return ENOTSUP;\r
-}\r
-\r
-/**\r
- * @}\r
- */\r
+/*
+ * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
+ *
+ * FreeBSD:
+ * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org>
+ * Copyright (c) 2012, Vyacheslav Matyushin
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ */
+
+/*
+ * The following notice applies to the code in ext2_half_md4():
+ *
+ * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved.
+ *
+ * License to copy and use this software is granted provided that it
+ * is identified as the "RSA Data Security, Inc. MD4 Message-Digest
+ * Algorithm" in all material mentioning or referencing this software
+ * or this function.
+ *
+ * License is also granted to make and use derivative works provided
+ * that such works are identified as "derived from the RSA Data
+ * Security, Inc. MD4 Message-Digest Algorithm" in all material
+ * mentioning or referencing the derived work.
+ *
+ * RSA Data Security, Inc. makes no representations concerning either
+ * the merchantability of this software or the suitability of this
+ * software for any particular purpose. It is provided "as is"
+ * without express or implied warranty of any kind.
+ *
+ * These notices must be retained in any copies of any part of this
+ * documentation and/or software.
+ */
+
+/** @addtogroup lwext4
+ * @{
+ */
+/**
+ * @file ext4_hash.c
+ * @brief Directory indexing hash functions.
+ */
+
+#include "ext4_config.h"
+#include "ext4_types.h"
+#include "ext4_errno.h"
+
+#include <string.h>
+
+/* F, G, and H are MD4 functions */
+#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
+#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
+#define H(x, y, z) ((x) ^ (y) ^ (z))
+
+/* ROTATE_LEFT rotates x left n bits */
+#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
+
+/*
+ * FF, GG, and HH are transformations for rounds 1, 2, and 3.
+ * Rotation is separated from addition to prevent recomputation.
+ */
+#define FF(a, b, c, d, x, s) \
+ { \
+ (a) += F((b), (c), (d)) + (x); \
+ (a) = ROTATE_LEFT((a), (s)); \
+ \
+}
+
+#define GG(a, b, c, d, x, s) \
+ { \
+ (a) += G((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \
+ (a) = ROTATE_LEFT((a), (s)); \
+ \
+}
+
+#define HH(a, b, c, d, x, s) \
+ { \
+ (a) += H((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \
+ (a) = ROTATE_LEFT((a), (s)); \
+ \
+}
+
+/*
+ * MD4 basic transformation. It transforms state based on block.
+ *
+ * This is a half md4 algorithm since Linux uses this algorithm for dir
+ * index. This function is derived from the RSA Data Security, Inc. MD4
+ * Message-Digest Algorithm and was modified as necessary.
+ *
+ * The return value of this function is uint32_t in Linux, but actually we don't
+ * need to check this value, so in our version this function doesn't return any
+ * value.
+ */
+static void ext2_half_md4(uint32_t hash[4], uint32_t data[8])
+{
+ uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3];
+
+ /* Round 1 */
+ FF(a, b, c, d, data[0], 3);
+ FF(d, a, b, c, data[1], 7);
+ FF(c, d, a, b, data[2], 11);
+ FF(b, c, d, a, data[3], 19);
+ FF(a, b, c, d, data[4], 3);
+ FF(d, a, b, c, data[5], 7);
+ FF(c, d, a, b, data[6], 11);
+ FF(b, c, d, a, data[7], 19);
+
+ /* Round 2 */
+ GG(a, b, c, d, data[1], 3);
+ GG(d, a, b, c, data[3], 5);
+ GG(c, d, a, b, data[5], 9);
+ GG(b, c, d, a, data[7], 13);
+ GG(a, b, c, d, data[0], 3);
+ GG(d, a, b, c, data[2], 5);
+ GG(c, d, a, b, data[4], 9);
+ GG(b, c, d, a, data[6], 13);
+
+ /* Round 3 */
+ HH(a, b, c, d, data[3], 3);
+ HH(d, a, b, c, data[7], 9);
+ HH(c, d, a, b, data[2], 11);
+ HH(b, c, d, a, data[6], 15);
+ HH(a, b, c, d, data[1], 3);
+ HH(d, a, b, c, data[5], 9);
+ HH(c, d, a, b, data[0], 11);
+ HH(b, c, d, a, data[4], 15);
+
+ hash[0] += a;
+ hash[1] += b;
+ hash[2] += c;
+ hash[3] += d;
+}
+
+/*
+ * Tiny Encryption Algorithm.
+ */
+static void ext2_tea(uint32_t hash[4], uint32_t data[8])
+{
+ uint32_t tea_delta = 0x9E3779B9;
+ uint32_t sum;
+ uint32_t x = hash[0], y = hash[1];
+ int n = 16;
+ int i = 1;
+
+ while (n-- > 0) {
+ sum = i * tea_delta;
+ x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]);
+ y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]);
+ i++;
+ }
+
+ hash[0] += x;
+ hash[1] += y;
+}
+
+static uint32_t ext2_legacy_hash(const char *name, int len, int unsigned_char)
+{
+ uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9;
+ uint32_t multi = 0x6D22F5;
+ const unsigned char *uname = (const unsigned char *)name;
+ const signed char *sname = (const signed char *)name;
+ int val, i;
+
+ for (i = 0; i < len; i++) {
+ if (unsigned_char)
+ val = (unsigned int)*uname++;
+ else
+ val = (int)*sname++;
+
+ h0 = h2 + (h1 ^ (val * multi));
+ if (h0 & 0x80000000)
+ h0 -= 0x7FFFFFFF;
+ h2 = h1;
+ h1 = h0;
+ }
+
+ return (h1 << 1);
+}
+
+static void ext2_prep_hashbuf(const char *src, uint32_t slen, uint32_t *dst,
+ int dlen, int unsigned_char)
+{
+ uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24);
+ uint32_t buf_val;
+ int len, i;
+ int buf_byte;
+ const unsigned char *ubuf = (const unsigned char *)src;
+ const signed char *sbuf = (const signed char *)src;
+
+ if (slen > (uint32_t)dlen)
+ len = dlen;
+ else
+ len = slen;
+
+ buf_val = padding;
+
+ for (i = 0; i < len; i++) {
+ if (unsigned_char)
+ buf_byte = (unsigned int)ubuf[i];
+ else
+ buf_byte = (int)sbuf[i];
+
+ if ((i % 4) == 0)
+ buf_val = padding;
+
+ buf_val <<= 8;
+ buf_val += buf_byte;
+
+ if ((i % 4) == 3) {
+ *dst++ = buf_val;
+ dlen -= sizeof(uint32_t);
+ buf_val = padding;
+ }
+ }
+
+ dlen -= sizeof(uint32_t);
+ if (dlen >= 0)
+ *dst++ = buf_val;
+
+ dlen -= sizeof(uint32_t);
+ while (dlen >= 0) {
+ *dst++ = padding;
+ dlen -= sizeof(uint32_t);
+ }
+}
+
+int ext2_htree_hash(const char *name, int len, const uint32_t *hash_seed,
+ int hash_version, uint32_t *hash_major,
+ uint32_t *hash_minor)
+{
+ uint32_t hash[4];
+ uint32_t data[8];
+ uint32_t major = 0, minor = 0;
+ int unsigned_char = 0;
+
+ if (!name || !hash_major)
+ return (-1);
+
+ if (len < 1 || len > 255)
+ goto error;
+
+ hash[0] = 0x67452301;
+ hash[1] = 0xEFCDAB89;
+ hash[2] = 0x98BADCFE;
+ hash[3] = 0x10325476;
+
+ if (hash_seed)
+ memcpy(hash, hash_seed, sizeof(hash));
+
+ switch (hash_version) {
+ case EXT2_HTREE_TEA_UNSIGNED:
+ unsigned_char = 1;
+ case EXT2_HTREE_TEA:
+ while (len > 0) {
+ ext2_prep_hashbuf(name, len, data, 16, unsigned_char);
+ ext2_tea(hash, data);
+ len -= 16;
+ name += 16;
+ }
+ major = hash[0];
+ minor = hash[1];
+ break;
+ case EXT2_HTREE_LEGACY_UNSIGNED:
+ unsigned_char = 1;
+ case EXT2_HTREE_LEGACY:
+ major = ext2_legacy_hash(name, len, unsigned_char);
+ break;
+ case EXT2_HTREE_HALF_MD4_UNSIGNED:
+ unsigned_char = 1;
+ case EXT2_HTREE_HALF_MD4:
+ while (len > 0) {
+ ext2_prep_hashbuf(name, len, data, 32, unsigned_char);
+ ext2_half_md4(hash, data);
+ len -= 32;
+ name += 32;
+ }
+ major = hash[1];
+ minor = hash[2];
+ break;
+ default:
+ goto error;
+ }
+
+ major &= ~1;
+ if (major == (EXT2_HTREE_EOF << 1))
+ major = (EXT2_HTREE_EOF - 1) << 1;
+ *hash_major = major;
+ if (hash_minor)
+ *hash_minor = minor;
+
+ return EOK;
+
+error:
+ *hash_major = 0;
+ if (hash_minor)
+ *hash_minor = 0;
+ return ENOTSUP;
+}
+
+/**
+ * @}
+ */
projects / lwext4.git / blobdiff