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. */
35typedef enum {
36 RS_ROLLSUM,
37 RS_RABINKARP,
39
40/** Strongsum implementations. */
41typedef 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. */
56typedef struct weaksum {
57 weaksum_kind_t kind;
58 union {
59 Rollsum rs;
60 rabinkarp_t rk;
61 } sum;
63
64static 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
72static 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
79static 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
85static 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
94static 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
103static 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
111static 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
119static 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. */
134rs_weak_sum_t rs_calc_weak_sum(weaksum_kind_t kind, void const *buf,
135 size_t len);
136
137/** Calculate a strongsum. */
138void 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 */
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
strongsum_kind_t
Strongsum implementations.
Definition: checksum.h:41
weaksum_kind_t
Weaksum implementations.
Definition: checksum.h:35
struct weaksum weaksum_t
Abstract wrapper around weaksum implementations.
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
A generic open addressing hashtable.
static unsigned mix32(unsigned h)
MurmurHash3 finalization mix function.
Definition: hashtable.h:170
Public header for librsync.
The rabinkarp class implementation of the RabinKarp rollsum.
The Rollsum class implementation of the original rsync rollsum.
The Rollsum state type.
Definition: rollsum.h:36
size_t count
count of bytes included in sum
Definition: rollsum.h:37
The rabinkarp_t state type.
Definition: rabinkarp.h:56
Abstract wrapper around weaksum implementations.
Definition: checksum.h:56