1 /* 2 * fs/f2fs/hash.c 3 * 4 * Copyright (c) 2012 Samsung Electronics Co., Ltd. 5 * http://www.samsung.com/ 6 * 7 * Portions of this code from linux/fs/ext3/hash.c 8 * 9 * Copyright (C) 2002 by Theodore Ts'o 10 * 11 * This program is free software; you can redistribute it and/or modify 12 * it under the terms of the GNU General Public License version 2 as 13 * published by the Free Software Foundation. 14 */ 15 #include <linux/types.h> 16 #include <linux/fs.h> 17 #include <linux/f2fs_fs.h> 18 #include <linux/cryptohash.h> 19 #include <linux/pagemap.h> 20 21 #include "f2fs.h" 22 23 /* 24 * Hashing code copied from ext3 25 */ 26 #define DELTA 0x9E3779B9 27 28 static void TEA_transform(unsigned int buf[4], unsigned int const in[]) 29 { 30 __u32 sum = 0; 31 __u32 b0 = buf[0], b1 = buf[1]; 32 __u32 a = in[0], b = in[1], c = in[2], d = in[3]; 33 int n = 16; 34 35 do { 36 sum += DELTA; 37 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); 38 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); 39 } while (--n); 40 41 buf[0] += b0; 42 buf[1] += b1; 43 } 44 45 static void str2hashbuf(const unsigned char *msg, size_t len, 46 unsigned int *buf, int num) 47 { 48 unsigned pad, val; 49 int i; 50 51 pad = (__u32)len | ((__u32)len << 8); 52 pad |= pad << 16; 53 54 val = pad; 55 if (len > num * 4) 56 len = num * 4; 57 for (i = 0; i < len; i++) { 58 if ((i % 4) == 0) 59 val = pad; 60 val = msg[i] + (val << 8); 61 if ((i % 4) == 3) { 62 *buf++ = val; 63 val = pad; 64 num--; 65 } 66 } 67 if (--num >= 0) 68 *buf++ = val; 69 while (--num >= 0) 70 *buf++ = pad; 71 } 72 73 f2fs_hash_t f2fs_dentry_hash(const struct qstr *name_info) 74 { 75 __u32 hash; 76 f2fs_hash_t f2fs_hash; 77 const unsigned char *p; 78 __u32 in[8], buf[4]; 79 const unsigned char *name = name_info->name; 80 size_t len = name_info->len; 81 82 if (is_dot_dotdot(name_info)) 83 return 0; 84 85 /* Initialize the default seed for the hash checksum functions */ 86 buf[0] = 0x67452301; 87 buf[1] = 0xefcdab89; 88 buf[2] = 0x98badcfe; 89 buf[3] = 0x10325476; 90 91 p = name; 92 while (1) { 93 str2hashbuf(p, len, in, 4); 94 TEA_transform(buf, in); 95 p += 16; 96 if (len <= 16) 97 break; 98 len -= 16; 99 } 100 hash = buf[0]; 101 f2fs_hash = cpu_to_le32(hash & ~F2FS_HASH_COL_BIT); 102 return f2fs_hash; 103 } 104