librsync  2.3.2
rollsum.h
1/*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*-
2 *
3 * rollsum -- the librsync rolling checksum
4 *
5 * Copyright (C) 2003 by Donovan Baarda <abo@minkirri.apana.org.au>
6 * based on work, Copyright (C) 2000, 2001 by Martin Pool <mbp@sourcefrog.net>
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License as published by
10 * the Free Software Foundation; either version 2.1 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 */
22#ifndef _ROLLSUM_H_
23# define _ROLLSUM_H_
24
25# include <stddef.h>
26# include <stdint.h>
27
28/* We should make this something other than zero to improve the checksum
29 algorithm: tridge suggests a prime number. */
30# define ROLLSUM_CHAR_OFFSET 31
31
32/** The Rollsum struct type \private. */
33typedef struct _Rollsum {
34 size_t count; /* count of bytes included in sum */
35 uint_fast16_t s1; /* s1 part of sum */
36 uint_fast16_t s2; /* s2 part of sum */
37} Rollsum;
38
39void RollsumUpdate(Rollsum *sum, const unsigned char *buf, size_t len);
40
41/* static inline implementations of simple routines */
42
43static inline void RollsumInit(Rollsum *sum)
44{
45 sum->count = sum->s1 = sum->s2 = 0;
46}
47
48static inline void RollsumRotate(Rollsum *sum, unsigned char out,
49 unsigned char in)
50{
51 sum->s1 += in - out;
52 sum->s2 += sum->s1 - sum->count * (out + ROLLSUM_CHAR_OFFSET);
53}
54
55static inline void RollsumRollin(Rollsum *sum, unsigned char in)
56{
57 sum->s1 += in + ROLLSUM_CHAR_OFFSET;
58 sum->s2 += sum->s1;
59 sum->count++;
60}
61
62static inline void RollsumRollout(Rollsum *sum, unsigned char out)
63{
64 sum->s1 -= out + ROLLSUM_CHAR_OFFSET;
65 sum->s2 -= sum->count * (out + ROLLSUM_CHAR_OFFSET);
66 sum->count--;
67}
68
69static inline uint32_t RollsumDigest(Rollsum *sum)
70{
71 return ((uint32_t)sum->s2 << 16) | ((uint32_t)sum->s1 & 0xffff);
72}
73
74#endif /* _ROLLSUM_H_ */