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