Mercurial > ~dholland > hg > ag > index.cgi

annotate checksum/dosum.c @ 24:a4899cdfc2d6 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Obfuscate the regexps to strip off the IBM compiler's copyright banners. I don't want bots scanning github to think they're real copyright notices because that could cause real problems.
author David A. Holland
date Mon, 13 Jun 2022 00:40:23 -0400
parents 3aa0f5a02342
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
1 /*
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
2 * AnaGram, A System for Syntax Directed Programming
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
3 * Copyright 1993 Parsifal Software. All Rights Reserved.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
4 * Copyright 2006 David A. Holland. All Rights Reserved.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
5 * See the file COPYING for license and usage terms.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
6 *
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
7 * dosum.c - checksums.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
8 */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
9
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
10 /*
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
11 * Fletcher's check-sum routines for AnaGram
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
12 *
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
13 * Freely adapted from routines published in Dr. Dobbs Journal
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
14 * May 1992, p. 64
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
15 *
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
16 * Revised as portable C in June 2006.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
17 */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
18
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
19 #include <stdint.h>
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
20 #include <string.h>
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
21 #include <assert.h>
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
22
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
23 #include "bits.h"
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
24
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
25 struct sumstate {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
26 uint16_t k1, k2;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
27 };
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
28
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
29 static void sumstate_init(struct sumstate *s, size_t length) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
30 s->k1 = (uint16_t) (length >> 16);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
31 s->k2 = (uint16_t) length;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
32
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
33 if (s->k1 == 0) s->k1++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
34 if (s->k2 == 0) s->k2++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
35 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
36
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
37 static void sumstate_sum(struct sumstate *s, const void *buf, size_t len) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
38 const uint8_t *cb;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
39 unsigned i, n;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
40 uint16_t x;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
41
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
42 cb = buf;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
43 n = len/sizeof(uint16_t);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
44 for (i=0; i<n; i++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
45
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
46 // read one octet at a time so the byte order is deterministic
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
47 x = *cb++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
48 x += ((uint16_t)*cb++) << 8;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
49
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
50 s->k1 += x;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
51 if (s->k1 < x) s->k1++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
52 s->k2 += s->k1;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
53 if (s->k2 < s->k1) s->k2++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
54 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
55 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
56
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
57 static uint32_t sumstate_finish(struct sumstate *s) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
58 uint32_t sum;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
59
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
60 s->k1 ^= 0xffff;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
61 s->k2 ^= 0xffff;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
62 sum = 65535UL*s->k2 + s->k1;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
63
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
64 return sum;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
65 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
66
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
67 uint32_t dosum(const char *buf, size_t len, size_t skipstart, size_t skiplen) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
68 struct sumstate s;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
69 size_t numwords;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
70
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
71 assert(skiplen%2==0);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
72 assert(skipstart==0 || skipstart+skiplen <= len);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
73 sumstate_init(&s, len);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
74
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
75 /*
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
76 * It would be nice if we could count on skipstart being aligned.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
77 * But we can't. Nor is the filesize necessarily even.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
78 *
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
79 * The followed mangled logic that rounds some things up matches
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
80 * what used to be done in an even uglier way.
11
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
81 *
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
82 * To wit: if there's a skip area, we start after it and read pairs
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
83 * of octets, including a zero past the end of the file if the
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
84 * remaining data length after the skip area has odd size, so as to
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
85 * get the last byte. (The caller is responsible for making sure
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
86 * there's a zero there.) Then we read the beginning of the file up
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
87 * to the skip area, but round down so as to not read the first byte
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
88 * of the skip area if skipstart is odd. If skipstart is odd then we
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
89 * wedge in that last byte along with a zero.
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
90 *
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
91 * If there isn't a skip area, we read the whole thing in order,
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
92 * including the zero past the end if the size is odd.
0
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
93 */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
94
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
95 assert(sizeof(uint16_t)==2);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
96 numwords = (len+1)/2;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
97
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
98 if (skipstart > 0) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
99 size_t p0 = skipstart+skiplen;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
100 size_t l0 = (numwords - p0/2) * 2;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
101 size_t p1 = 0;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
102 size_t l1 = (skipstart/2) * 2;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
103
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
104 sumstate_sum(&s, buf+p0, l0);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
105 sumstate_sum(&s, buf+p1, l1);
11
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
106 if (skipstart % 2 == 1) {
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
107 char tmp[2];
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
108
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
109 tmp[0] = buf[skipstart - 1];
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
110 tmp[1] = 0;
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
111 sumstate_sum(&s, tmp, 2);
3aa0f5a02342 Remove unused variable; fix what it was supposed to be doing.
David A. Holland
parents: 0
diff changeset
112 }
0
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
113 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
114 else {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
115 sumstate_sum(&s, buf, numwords * 2);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
116 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
117
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
118 return sumstate_finish(&s);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial.
David A. Holland
parents:
diff changeset
119 }