librsync  2.3.4
rabinkarp.h
Go to the documentation of this file.
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 
22 /** \file rabinkarp.h
23  * The rabinkarp class implementation of the RabinKarp rollsum. */
24 #ifndef RABINKARP_H
25 # define RABINKARP_H
26 
27 # include <stddef.h>
28 # include <stdint.h>
29 
30 /** The RabinKarp seed value.
31  *
32  * The seed ensures different length zero blocks have different hashes. It
33  * effectively encodes the length into the hash. */
34 # define RABINKARP_SEED 1
35 
36 /** The RabinKarp multiplier.
37  *
38  * This multiplier has a bit pattern of 1's getting sparser with significance,
39  * is the product of 2 large primes, and matches the characterstics for a good
40  * LCG multiplier. */
41 # define RABINKARP_MULT 0x08104225U
42 
43 /** The RabinKarp inverse multiplier.
44  *
45  * This is the inverse of RABINKARP_MULT modular 2^32. Multiplying by this is
46  * equivalent to dividing by RABINKARP_MULT. */
47 # define RABINKARP_INVM 0x98f009adU
48 
49 /** The RabinKarp seed adjustment.
50  *
51  * This is a factor used to adjust for the seed when rolling out values. It's
52  * equal to; (RABINKARP_MULT - 1) * RABINKARP_SEED */
53 # define RABINKARP_ADJ 0x08104224U
54 
55 /** The rabinkarp_t state type. */
56 typedef struct rabinkarp {
57  size_t count; /**< Count of bytes included in sum. */
58  uint32_t hash; /**< The accumulated hash value. */
59  uint32_t mult; /**< The value of RABINKARP_MULT^count. */
60 } rabinkarp_t;
61 
62 static inline void rabinkarp_init(rabinkarp_t *sum)
63 {
64  sum->count = 0;
65  sum->hash = RABINKARP_SEED;
66  sum->mult = 1;
67 }
68 
69 void rabinkarp_update(rabinkarp_t *sum, const unsigned char *buf, size_t len);
70 
71 static inline void rabinkarp_rotate(rabinkarp_t *sum, unsigned char out,
72  unsigned char in)
73 {
74  sum->hash =
75  sum->hash * RABINKARP_MULT + in - sum->mult * (out + RABINKARP_ADJ);
76 }
77 
78 static inline void rabinkarp_rollin(rabinkarp_t *sum, unsigned char in)
79 {
80  sum->hash = sum->hash * RABINKARP_MULT + in;
81  sum->count++;
82  sum->mult *= RABINKARP_MULT;
83 }
84 
85 static inline void rabinkarp_rollout(rabinkarp_t *sum, unsigned char out)
86 {
87  sum->count--;
88  sum->mult *= RABINKARP_INVM;
89  sum->hash -= sum->mult * (out + RABINKARP_ADJ);
90 }
91 
92 static inline uint32_t rabinkarp_digest(rabinkarp_t *sum)
93 {
94  return sum->hash;
95 }
96 
97 #endif /* !RABINKARP_H */
uint32_t hash
The accumulated hash value.
Definition: rabinkarp.h:58
#define RABINKARP_ADJ
The RabinKarp seed adjustment.
Definition: rabinkarp.h:53
#define RABINKARP_INVM
The RabinKarp inverse multiplier.
Definition: rabinkarp.h:47
#define RABINKARP_SEED
The RabinKarp seed value.
Definition: rabinkarp.h:34
size_t count
Count of bytes included in sum.
Definition: rabinkarp.h:57
#define RABINKARP_MULT
The RabinKarp multiplier.
Definition: rabinkarp.h:41
uint32_t mult
The value of RABINKARP_MULT^count.
Definition: rabinkarp.h:59
The rabinkarp_t state type.
Definition: rabinkarp.h:56
struct rabinkarp rabinkarp_t
The rabinkarp_t state type.