librsync  2.3.2
checksum.h
1 /*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*-
2  *
3  * librsync -- the library for network deltas
4  *
5  * Copyright (C) 2000, 2001 by Martin Pool <mbp@sourcefrog.net>
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 _CHECKSUM_H_
22 # define _CHECKSUM_H_
23 # include <assert.h>
24 # include "librsync.h"
25 # include "rollsum.h"
26 # include "rabinkarp.h"
27 # include "hashtable.h"
28 
29 /** Weaksum implementations. */
30 typedef enum {
31  RS_ROLLSUM,
32  RS_RABINKARP,
33 } weaksum_kind_t;
34 
35 /** Strongsum implementations. */
36 typedef enum {
37  RS_MD4,
38  RS_BLAKE2,
39 } strongsum_kind_t;
40 
41 /** Abstract wrapper around weaksum implementations.
42  *
43  * This is a polymorphic interface to the different rollsum implementations.
44  *
45  * Historically rollsum methods were implemented as static inline functions
46  * because they were small and needed to be fast. Now that we need to call
47  * different methods for different rollsum implementations, they are getting
48  * more complicated. Is it better to delegate calls to the right implementation
49  * using static inline switch statements, or stop inlining them and use virtual
50  * method pointers? Tests suggest inlined switch statements is faster. */
51 typedef struct weaksum {
52  weaksum_kind_t kind;
53  union {
54  Rollsum rs;
55  rabinkarp_t rk;
56  } sum;
57 } weaksum_t;
58 
59 static inline void weaksum_reset(weaksum_t *sum)
60 {
61  if (sum->kind == RS_ROLLSUM)
62  RollsumInit(&sum->sum.rs);
63  else
64  rabinkarp_init(&sum->sum.rk);
65 }
66 
67 static inline void weaksum_init(weaksum_t *sum, weaksum_kind_t kind)
68 {
69  assert(kind == RS_ROLLSUM || kind == RS_RABINKARP);
70  sum->kind = kind;
71  weaksum_reset(sum);
72 }
73 
74 static inline size_t weaksum_count(weaksum_t *sum)
75 {
76  /* We take advantage of sum->sum.rs.count overlaying sum->sum.rk.count. */
77  return sum->sum.rs.count;
78 }
79 
80 static inline void weaksum_update(weaksum_t *sum, const unsigned char *buf,
81  size_t len)
82 {
83  if (sum->kind == RS_ROLLSUM)
84  RollsumUpdate(&sum->sum.rs, buf, len);
85  else
86  rabinkarp_update(&sum->sum.rk, buf, len);
87 }
88 
89 static inline void weaksum_rotate(weaksum_t *sum, unsigned char out,
90  unsigned char in)
91 {
92  if (sum->kind == RS_ROLLSUM)
93  RollsumRotate(&sum->sum.rs, out, in);
94  else
95  rabinkarp_rotate(&sum->sum.rk, out, in);
96 }
97 
98 static inline void weaksum_rollin(weaksum_t *sum, unsigned char in)
99 {
100  if (sum->kind == RS_ROLLSUM)
101  RollsumRollin(&sum->sum.rs, in);
102  else
103  rabinkarp_rollin(&sum->sum.rk, in);
104 }
105 
106 static inline void weaksum_rollout(weaksum_t *sum, unsigned char out)
107 {
108  if (sum->kind == RS_ROLLSUM)
109  RollsumRollout(&sum->sum.rs, out);
110  else
111  rabinkarp_rollout(&sum->sum.rk, out);
112 }
113 
114 static inline rs_weak_sum_t weaksum_digest(weaksum_t *sum)
115 {
116  if (sum->kind == RS_ROLLSUM)
117  /* We apply mix32() to rollsums before using them for matching. */
118  return mix32(RollsumDigest(&sum->sum.rs));
119  else
120  return rabinkarp_digest(&sum->sum.rk);
121 }
122 
123 /** Calculate a weaksum.
124  *
125  * Note this does not apply mix32() to rollsum digests, unlike
126  * weaksum_digest(). This is because rollsums are stored raw without mix32()
127  * applied for backwards-compatibility, but we apply mix32() when adding them
128  * into a signature and when getting the digest for calculating deltas. */
129 rs_weak_sum_t rs_calc_weak_sum(weaksum_kind_t kind, void const *buf,
130  size_t len);
131 
132 /** Calculate a strongsum. */
133 void rs_calc_strong_sum(strongsum_kind_t kind, void const *buf, size_t len,
134  rs_strong_sum_t *sum);
135 
136 #endif /* _CHECKSUM_H_ */
A generic open addressing hashtable.
static unsigned mix32(unsigned h)
MurmurHash3 finalization mix function.
Definition: hashtable.h:172
Public header for librsync.
Abstract wrapper around weaksum implementations.
Definition: checksum.h:51