LXR linux/fs/f2fs/hash.c

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