hash.c 3.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * fs/f2fs/hash.c
  4. *
  5. * Copyright (c) 2012 Samsung Electronics Co., Ltd.
  6. * http://www.samsung.com/
  7. *
  8. * Portions of this code from linux/fs/ext3/hash.c
  9. *
  10. * Copyright (C) 2002 by Theodore Ts'o
  11. */
  12. #include <linux/types.h>
  13. #include <linux/fs.h>
  14. #include <linux/f2fs_fs.h>
  15. #include <linux/pagemap.h>
  16. #include <linux/unicode.h>
  17. #include "f2fs.h"
  18. /*
  19. * Hashing code copied from ext3
  20. */
  21. #define DELTA 0x9E3779B9
  22. static void TEA_transform(unsigned int buf[4], unsigned int const in[])
  23. {
  24. __u32 sum = 0;
  25. __u32 b0 = buf[0], b1 = buf[1];
  26. __u32 a = in[0], b = in[1], c = in[2], d = in[3];
  27. int n = 16;
  28. do {
  29. sum += DELTA;
  30. b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
  31. b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
  32. } while (--n);
  33. buf[0] += b0;
  34. buf[1] += b1;
  35. }
  36. static void str2hashbuf(const unsigned char *msg, size_t len,
  37. unsigned int *buf, int num)
  38. {
  39. unsigned pad, val;
  40. int i;
  41. pad = (__u32)len | ((__u32)len << 8);
  42. pad |= pad << 16;
  43. val = pad;
  44. if (len > num * 4)
  45. len = num * 4;
  46. for (i = 0; i < len; i++) {
  47. if ((i % 4) == 0)
  48. val = pad;
  49. val = msg[i] + (val << 8);
  50. if ((i % 4) == 3) {
  51. *buf++ = val;
  52. val = pad;
  53. num--;
  54. }
  55. }
  56. if (--num >= 0)
  57. *buf++ = val;
  58. while (--num >= 0)
  59. *buf++ = pad;
  60. }
  61. static u32 TEA_hash_name(const u8 *p, size_t len)
  62. {
  63. __u32 in[8], buf[4];
  64. /* Initialize the default seed for the hash checksum functions */
  65. buf[0] = 0x67452301;
  66. buf[1] = 0xefcdab89;
  67. buf[2] = 0x98badcfe;
  68. buf[3] = 0x10325476;
  69. while (1) {
  70. str2hashbuf(p, len, in, 4);
  71. TEA_transform(buf, in);
  72. p += 16;
  73. if (len <= 16)
  74. break;
  75. len -= 16;
  76. }
  77. return buf[0] & ~F2FS_HASH_COL_BIT;
  78. }
  79. /*
  80. * Compute @fname->hash. For all directories, @fname->disk_name must be set.
  81. * For casefolded directories, @fname->usr_fname must be set, and also
  82. * @fname->cf_name if the filename is valid Unicode.
  83. */
  84. void f2fs_hash_filename(const struct inode *dir, struct f2fs_filename *fname)
  85. {
  86. const u8 *name = fname->disk_name.name;
  87. size_t len = fname->disk_name.len;
  88. WARN_ON_ONCE(!name);
  89. if (is_dot_dotdot(name, len)) {
  90. fname->hash = 0;
  91. return;
  92. }
  93. #ifdef CONFIG_UNICODE
  94. if (IS_CASEFOLDED(dir)) {
  95. /*
  96. * If the casefolded name is provided, hash it instead of the
  97. * on-disk name. If the casefolded name is *not* provided, that
  98. * should only be because the name wasn't valid Unicode, so fall
  99. * back to treating the name as an opaque byte sequence. Note
  100. * that to handle encrypted directories, the fallback must use
  101. * usr_fname (plaintext) rather than disk_name (ciphertext).
  102. */
  103. WARN_ON_ONCE(!fname->usr_fname->name);
  104. if (fname->cf_name.name) {
  105. name = fname->cf_name.name;
  106. len = fname->cf_name.len;
  107. } else {
  108. name = fname->usr_fname->name;
  109. len = fname->usr_fname->len;
  110. }
  111. if (IS_ENCRYPTED(dir)) {
  112. struct qstr tmp = QSTR_INIT(name, len);
  113. fname->hash =
  114. cpu_to_le32(fscrypt_fname_siphash(dir, &tmp));
  115. return;
  116. }
  117. }
  118. #endif
  119. fname->hash = cpu_to_le32(TEA_hash_name(name, len));
  120. }