1 /* SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0 */
2 /*
3 * Copyright (C) 2022 Alibaba Cloud
4 */
5 #ifndef __ROLLING_HASH_H__
6 #define __ROLLING_HASH_H__
7
8 #include <erofs/defs.h>
9
10 #define PRIME_NUMBER 4294967295LL
11 #define RADIX 256
12
erofs_rolling_hash_init(u8 * input,int len,bool backwards)13 static inline long long erofs_rolling_hash_init(u8 *input,
14 int len, bool backwards)
15 {
16 long long hash = 0;
17
18 if (!backwards) {
19 int i;
20
21 for (i = 0; i < len; ++i)
22 hash = (RADIX * hash + input[i]) % PRIME_NUMBER;
23 } else {
24 while (len)
25 hash = (RADIX * hash + input[--len]) % PRIME_NUMBER;
26 }
27 return hash;
28 }
29
30 /* RM = R ^ (M-1) % Q */
31 /*
32 * NOTE: value of "hash" could be negative so we cannot use unsiged types for "hash"
33 * "long long" is used here and PRIME_NUMBER can be ULONG_MAX
34 */
erofs_rolling_hash_advance(long long old_hash,unsigned long long RM,u8 to_remove,u8 to_add)35 static inline long long erofs_rolling_hash_advance(long long old_hash,
36 unsigned long long RM,
37 u8 to_remove, u8 to_add)
38 {
39 long long hash = old_hash;
40 long long to_remove_val = (to_remove * RM) % PRIME_NUMBER;
41
42 hash = RADIX * (old_hash - to_remove_val) % PRIME_NUMBER;
43 hash = (hash + to_add) % PRIME_NUMBER;
44
45 /* We might get negative value of hash, converting it to positive */
46 if (hash < 0)
47 hash += PRIME_NUMBER;
48 return hash;
49 }
50
erofs_rollinghash_calc_rm(int window_size)51 static inline long long erofs_rollinghash_calc_rm(int window_size)
52 {
53 int i;
54 long long RM = 1;
55
56 for (i = 0; i < window_size - 1; ++i)
57 RM = (RM * RADIX) % PRIME_NUMBER;
58 return RM;
59 }
60 #endif
61