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 char *msg, size_t len, unsigned int *buf, int num) 46 { 47 unsigned pad, val; 48 int i; 49 50 pad = (__u32)len | ((__u32)len << 8); 51 pad |= pad << 16; 52 53 val = pad; 54 if (len > num * 4) 55 len = num * 4; 56 for (i = 0; i < len; i++) { 57 if ((i % 4) == 0) 58 val = pad; 59 val = msg[i] + (val << 8); 60 if ((i % 4) == 3) { 61 *buf++ = val; 62 val = pad; 63 num--; 64 } 65 } 66 if (--num >= 0) 67 *buf++ = val; 68 while (--num >= 0) 69 *buf++ = pad; 70 } 71 72 f2fs_hash_t f2fs_dentry_hash(const char *name, size_t len) 73 { 74 __u32 hash; 75 f2fs_hash_t f2fs_hash; 76 const char *p; 77 __u32 in[8], buf[4]; 78 79 if ((len <= 2) && (name[0] == '.') && 80 (name[1] == '.' || name[1] == '\0')) 81 return 0; 82 83 /* Initialize the default seed for the hash checksum functions */ 84 buf[0] = 0x67452301; 85 buf[1] = 0xefcdab89; 86 buf[2] = 0x98badcfe; 87 buf[3] = 0x10325476; 88 89 p = name; 90 while (1) { 91 str2hashbuf(p, len, in, 4); 92 TEA_transform(buf, in); 93 p += 16; 94 if (len <= 16) 95 break; 96 len -= 16; 97 } 98 hash = buf[0]; 99 f2fs_hash = cpu_to_le32(hash & ~F2FS_HASH_COL_BIT); 100 return f2fs_hash; 101 } 102