librsync  2.3.1
rabinkarp.h
1 /*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*-
2  *
3  * rabinkarp -- The RabinKarp rolling checksum.
4  *
5  * Copyright (C) 2019 by Donovan Baarda <abo@minkirri.apana.org.au>
6  *
7  * This program is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU Lesser General Public License as published by
9  * the Free Software Foundation; either version 2.1 of the License, or
10  * (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public License
18  * along with this program; if not, write to the Free Software
19  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20  */
21 #ifndef _RABINKARP_H_
22 # define _RABINKARP_H_
23 
24 # include <stddef.h>
25 # include <stdint.h>
26 
27 /** The RabinKarp seed value.
28  *
29  * The seed ensures different length zero blocks have different hashes. It
30  * effectively encodes the length into the hash. */
31 # define RABINKARP_SEED 1
32 
33 /** The RabinKarp multiplier.
34  *
35  * This multiplier has a bit pattern of 1's getting sparser with significance,
36  * is the product of 2 large primes, and matches the characterstics for a good
37  * LCG multiplier. */
38 # define RABINKARP_MULT 0x08104225U
39 
40 /** The RabinKarp inverse multiplier.
41  *
42  * This is the inverse of RABINKARP_MULT modular 2^32. Multiplying by this is
43  * equivalent to dividing by RABINKARP_MULT. */
44 # define RABINKARP_INVM 0x98f009adU
45 
46 /** The RabinKarp seed adjustment.
47  *
48  * This is a factor used to adjust for the seed when rolling out values. It's
49  * equal to; (RABINKARP_MULT - 1) * RABINKARP_SEED */
50 # define RABINKARP_ADJ 0x08104224U
51 
52 /** The rabinkarp_t state type. */
53 typedef struct _rabinkarp {
54  size_t count; /**< Count of bytes included in sum. */
55  uint32_t hash; /**< The accumulated hash value. */
56  uint32_t mult; /**< The value of RABINKARP_MULT^count. */
57 } rabinkarp_t;
58 
59 static inline void rabinkarp_init(rabinkarp_t *sum)
60 {
61  sum->count = 0;
62  sum->hash = RABINKARP_SEED;
63  sum->mult = 1;
64 }
65 
66 void rabinkarp_update(rabinkarp_t *sum, const unsigned char *buf, size_t len);
67 
68 static inline void rabinkarp_rotate(rabinkarp_t *sum, unsigned char out,
69  unsigned char in)
70 {
71  sum->hash =
72  sum->hash * RABINKARP_MULT + in - sum->mult * (out + RABINKARP_ADJ);
73 }
74 
75 static inline void rabinkarp_rollin(rabinkarp_t *sum, unsigned char in)
76 {
77  sum->hash = sum->hash * RABINKARP_MULT + in;
78  sum->count++;
79  sum->mult *= RABINKARP_MULT;
80 }
81 
82 static inline void rabinkarp_rollout(rabinkarp_t *sum, unsigned char out)
83 {
84  sum->count--;
85  sum->mult *= RABINKARP_INVM;
86  sum->hash -= sum->mult * (out + RABINKARP_ADJ);
87 }
88 
89 static inline uint32_t rabinkarp_digest(rabinkarp_t *sum)
90 {
91  return sum->hash;
92 }
93 
94 #endif /* _RABINKARP_H_ */