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