Chris added a missing "not" to a comment.
[rsync.git] / checksum.c
1 /* 
2    Copyright (C) Andrew Tridgell 1996
3    Copyright (C) Paul Mackerras 1996
4    
5    This program is free software; you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published by
7    the Free Software Foundation; either version 2 of the License, or
8    (at your option) any later version.
9    
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13    GNU General Public License for more details.
14    
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software
17    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 */
19
20 #include "rsync.h"
21
22 int csum_length=2; /* initial value */
23
24 #define CSUM_CHUNK 64
25
26 extern int checksum_seed;
27 extern int protocol_version;
28
29 /*
30   a simple 32 bit checksum that can be upadted from either end
31   (inspired by Mark Adler's Adler-32 checksum)
32   */
33 uint32 get_checksum1(char *buf1,int len)
34 {
35     int i;
36     uint32 s1, s2;
37     schar *buf = (schar *)buf1;
38
39     s1 = s2 = 0;
40     for (i = 0; i < (len-4); i+=4) {
41         s2 += 4*(s1 + buf[i]) + 3*buf[i+1] + 2*buf[i+2] + buf[i+3] + 
42           10*CHAR_OFFSET;
43         s1 += (buf[i+0] + buf[i+1] + buf[i+2] + buf[i+3] + 4*CHAR_OFFSET); 
44     }
45     for (; i < len; i++) {
46         s1 += (buf[i]+CHAR_OFFSET); s2 += s1;
47     }
48     return (s1 & 0xffff) + (s2 << 16);
49 }
50
51
52 void get_checksum2(char *buf,int len,char *sum)
53 {
54         int i;
55         static char *buf1;
56         static int len1;
57         struct mdfour m;
58
59         if (len > len1) {
60                 if (buf1) free(buf1);
61                 buf1 = new_array(char, len+4);
62                 len1 = len;
63                 if (!buf1) out_of_memory("get_checksum2");
64         }
65         
66         mdfour_begin(&m);
67         
68         memcpy(buf1,buf,len);
69         if (checksum_seed) {
70                 SIVAL(buf1,len,checksum_seed);
71                 len += 4;
72         }
73         
74         for(i = 0; i + CSUM_CHUNK <= len; i += CSUM_CHUNK) {
75                 mdfour_update(&m, (uchar *)(buf1+i), CSUM_CHUNK);
76         }
77         /*
78          * Prior to version 27 an incorrect MD4 checksum was computed
79          * by failing to call mdfour_tail() for block sizes that
80          * are multiples of 64.  This is fixed by calling mdfour_update()
81          * even when there are no more bytes.
82          */
83         if (len - i > 0 || protocol_version >= 27) {
84                 mdfour_update(&m, (uchar *)(buf1+i), (len-i));
85         }
86         
87         mdfour_result(&m, (uchar *)sum);
88 }
89
90
91 void file_checksum(char *fname,char *sum,OFF_T size)
92 {
93         OFF_T i;
94         struct map_struct *buf;
95         int fd;
96         OFF_T len = size;
97         struct mdfour m;
98         
99         memset(sum,0,MD4_SUM_LENGTH);
100         
101         fd = do_open(fname, O_RDONLY, 0);
102         if (fd == -1)
103                 return;
104         
105         buf = map_file(fd, size, CSUM_CHUNK);
106         
107         mdfour_begin(&m);
108
109         for(i = 0; i + CSUM_CHUNK <= len; i += CSUM_CHUNK) {
110                 mdfour_update(&m, (uchar *)map_ptr(buf, i, CSUM_CHUNK),
111                               CSUM_CHUNK);
112         }
113
114         /* Prior to version 27 an incorrect MD4 checksum was computed
115          * by failing to call mdfour_tail() for block sizes that
116          * are multiples of 64.  This is fixed by calling mdfour_update()
117          * even when there are no more bytes. */
118         if (len - i > 0 || protocol_version >= 27)
119                 mdfour_update(&m, (uchar *)map_ptr(buf, i, len-i), len-i);
120
121         mdfour_result(&m, (uchar *)sum);
122
123         close(fd);
124         unmap_file(buf);
125 }
126
127
128 static int sumresidue;
129 static char sumrbuf[CSUM_CHUNK];
130 static struct mdfour md;
131
132 void sum_init(int seed)
133 {
134         char s[4];
135         mdfour_begin(&md);
136         sumresidue = 0;
137         SIVAL(s, 0, seed);
138         sum_update(s, 4);
139 }
140
141 /**
142  * Feed data into an MD4 accumulator, md.  The results may be
143  * retrieved using sum_end().  md is used for different purposes at
144  * different points during execution.
145  *
146  * @todo Perhaps get rid of md and just pass in the address each time.
147  * Very slightly clearer and slower.
148  **/
149 void sum_update(char *p, int len)
150 {
151         int i;
152         if (len + sumresidue < CSUM_CHUNK) {
153                 memcpy(sumrbuf+sumresidue, p, len);
154                 sumresidue += len;
155                 return;
156         }
157
158         if (sumresidue) {
159                 i = MIN(CSUM_CHUNK-sumresidue,len);
160                 memcpy(sumrbuf+sumresidue,p,i);
161                 mdfour_update(&md, (uchar *)sumrbuf, (i+sumresidue));
162                 len -= i;
163                 p += i;
164         }
165
166         for(i = 0; i + CSUM_CHUNK <= len; i += CSUM_CHUNK) {
167                 memcpy(sumrbuf,p+i,CSUM_CHUNK);
168                 mdfour_update(&md, (uchar *)sumrbuf, CSUM_CHUNK);
169         }
170
171         if (len - i > 0) {
172                 sumresidue = len-i;
173                 memcpy(sumrbuf,p+i,sumresidue);
174         } else {
175                 sumresidue = 0;    
176         }
177 }
178
179 void sum_end(char *sum)
180 {
181         if (sumresidue || protocol_version >= 27) {
182                 mdfour_update(&md, (uchar *)sumrbuf, sumresidue);
183         }
184
185         mdfour_result(&md, (uchar *)sum);
186 }