Chris Mason | 62e2749 | 2007-03-15 12:56:47 -0400 | [diff] [blame] | 1 | /* |
Chris Mason | 6cbd557 | 2007-06-12 09:07:21 -0400 | [diff] [blame] | 2 | * Copyright (C) 2007 Oracle. All rights reserved. |
| 3 | * |
| 4 | * This program is free software; you can redistribute it and/or |
| 5 | * modify it under the terms of the GNU General Public |
| 6 | * License v2 as published by the Free Software Foundation. |
| 7 | * |
| 8 | * This program is distributed in the hope that it will be useful, |
| 9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 11 | * General Public License for more details. |
| 12 | * |
| 13 | * You should have received a copy of the GNU General Public |
| 14 | * License along with this program; if not, write to the |
| 15 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, |
| 16 | * Boston, MA 021110-1307, USA. |
| 17 | */ |
| 18 | |
| 19 | /* |
Chris Mason | 62e2749 | 2007-03-15 12:56:47 -0400 | [diff] [blame] | 20 | * Original copy from: |
| 21 | * linux/fs/ext3/hash.c |
| 22 | * |
| 23 | * Copyright (C) 2002 by Theodore Ts'o |
| 24 | * |
| 25 | * This file is released under the GPL v2. |
| 26 | * |
| 27 | * This file may be redistributed under the terms of the GNU Public |
| 28 | * License. |
| 29 | */ |
| 30 | |
Chris Mason | e20d96d | 2007-03-22 12:13:20 -0400 | [diff] [blame] | 31 | #include <linux/types.h> |
Chris Mason | 35b7e47 | 2007-05-02 15:53:43 -0400 | [diff] [blame] | 32 | #include "hash.h" |
Chris Mason | 62e2749 | 2007-03-15 12:56:47 -0400 | [diff] [blame] | 33 | #define DELTA 0x9E3779B9 |
| 34 | |
| 35 | static void TEA_transform(__u32 buf[2], __u32 const in[]) |
| 36 | { |
| 37 | __u32 sum = 0; |
| 38 | __u32 b0 = buf[0], b1 = buf[1]; |
| 39 | __u32 a = in[0], b = in[1], c = in[2], d = in[3]; |
| 40 | int n = 16; |
| 41 | |
| 42 | do { |
| 43 | sum += DELTA; |
| 44 | b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); |
| 45 | b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); |
| 46 | } while(--n); |
| 47 | |
| 48 | buf[0] += b0; |
| 49 | buf[1] += b1; |
| 50 | } |
| 51 | |
| 52 | static void str2hashbuf(const char *msg, int len, __u32 *buf, int num) |
| 53 | { |
| 54 | __u32 pad, val; |
| 55 | int i; |
| 56 | |
| 57 | pad = (__u32)len | ((__u32)len << 8); |
| 58 | pad |= pad << 16; |
| 59 | |
| 60 | val = pad; |
| 61 | if (len > num*4) |
| 62 | len = num * 4; |
| 63 | for (i=0; i < len; i++) { |
| 64 | if ((i % 4) == 0) |
| 65 | val = pad; |
| 66 | val = msg[i] + (val << 8); |
| 67 | if ((i % 4) == 3) { |
| 68 | *buf++ = val; |
| 69 | val = pad; |
| 70 | num--; |
| 71 | } |
| 72 | } |
| 73 | if (--num >= 0) |
| 74 | *buf++ = val; |
| 75 | while (--num >= 0) |
| 76 | *buf++ = pad; |
| 77 | } |
| 78 | |
David Miller | df68b8a | 2008-02-15 10:40:52 -0500 | [diff] [blame] | 79 | u64 btrfs_name_hash(const char *name, int len) |
Chris Mason | 62e2749 | 2007-03-15 12:56:47 -0400 | [diff] [blame] | 80 | { |
| 81 | __u32 hash; |
| 82 | __u32 minor_hash = 0; |
| 83 | const char *p; |
Alex Chiang | 140dfd0 | 2008-04-01 11:21:40 -0400 | [diff] [blame] | 84 | __u32 in[8], buf[4]; |
David Miller | df68b8a | 2008-02-15 10:40:52 -0500 | [diff] [blame] | 85 | u64 hash_result; |
Chris Mason | 62e2749 | 2007-03-15 12:56:47 -0400 | [diff] [blame] | 86 | |
Chris Mason | e20d96d | 2007-03-22 12:13:20 -0400 | [diff] [blame] | 87 | if (len == 1 && *name == '.') { |
David Miller | df68b8a | 2008-02-15 10:40:52 -0500 | [diff] [blame] | 88 | return 1; |
Chris Mason | e20d96d | 2007-03-22 12:13:20 -0400 | [diff] [blame] | 89 | } else if (len == 2 && name[0] == '.' && name[1] == '.') { |
David Miller | df68b8a | 2008-02-15 10:40:52 -0500 | [diff] [blame] | 90 | return 2; |
Chris Mason | e20d96d | 2007-03-22 12:13:20 -0400 | [diff] [blame] | 91 | } |
| 92 | |
Chris Mason | 62e2749 | 2007-03-15 12:56:47 -0400 | [diff] [blame] | 93 | /* Initialize the default seed for the hash checksum functions */ |
| 94 | buf[0] = 0x67452301; |
| 95 | buf[1] = 0xefcdab89; |
| 96 | buf[2] = 0x98badcfe; |
| 97 | buf[3] = 0x10325476; |
| 98 | |
| 99 | p = name; |
| 100 | while (len > 0) { |
| 101 | str2hashbuf(p, len, in, 4); |
| 102 | TEA_transform(buf, in); |
| 103 | len -= 16; |
| 104 | p += 16; |
| 105 | } |
| 106 | hash = buf[0]; |
| 107 | minor_hash = buf[1]; |
David Miller | df68b8a | 2008-02-15 10:40:52 -0500 | [diff] [blame] | 108 | hash_result = buf[0]; |
| 109 | hash_result <<= 32; |
| 110 | hash_result |= buf[1]; |
| 111 | return hash_result; |
Chris Mason | 62e2749 | 2007-03-15 12:56:47 -0400 | [diff] [blame] | 112 | } |