4 /* A simple progrem to compute AccurateRip checksums for a sliding window
5 * over a stream. The algorithm is based on an observation by Jon Lund
6 * Steffensen (http://jonls.dk/2009/10/calculating-accuraterip-checksums/).
8 * The basic checksum is c = SUM_i (i + i) S_i, where 0 <= i < n ranges over
9 * the sample numbers, and S_i is the data for the sample point, expressed as
10 * a single element of Z/2^{32}Z (a cheesy notational device which avoids me
11 * having to write `(mod 2^{32})' everywhere).
13 * Steffensen's observation is this: if T_i = S_{i+1} for 0 <= i < n - 1 then
14 * we can compute the checksum c' over the T_i given only a small quantity of
17 * c' - c = SUM_{0<=i<n} (i + 1) T_i - SUM_{0<=i<n} (i + 1) S_i
18 * = SUM_{0<=i<n-1} (i + 1) S_{i+1} + n T_{n-1} -
19 * SUM_{0<i<n} (i + 1) S_i - S_0
20 * = SUM_{0<i<n} i S_i + n T_{n-1} -
21 * SUM_{0<i<n} (i + 1) S_i - S_0
22 * = n T_{n-1} - SUM_{0<=i<n} S_i
24 * The term SUM_{0<=i<n} S_i can be computed while we're summing up the
25 * initial window. Obviously, maintaining it is trivial.
27 * The final track is dealt with specially by clobbering the last five frames
28 * with silence. Since silent samples contribute nothing to the checksum, we
29 * can instead consider the final track to be truncated at this point.
31 * Life gets a little bit more complicated when we deal with the special
32 * rules for the first track: rather than simply starting (almost) five
33 * frames in, we silence the initial segment. So when we advance our window,
34 * we must take off m S_0 rather than simply S_0.
44 int main(int argc, char *argv[])
46 unsigned long ns, ck, tot, i0, o = 0, x, y;
50 const char *quis = argv[0];
56 int o = getopt(argc, argv, "di:");
59 case 'd': f |= F_DEBUG; break;
60 case 'i': i0 = strtoul(optarg, 0, 0); break;
64 argv += optind; argc -= optind;
67 fprintf(stderr, "Usage: %s flaccrip-slide NSAMPLES CHECKSUM SUM "
68 "PREFIX SUFFIX TARGET ...\n", quis);
71 ns = strtoul(argv[0], 0, 0);
72 ck = strtoul(argv[1], 0, 16);
73 tot = strtoul(argv[2], 0, 0);
74 if ((fp = fopen(argv[3], "rb")) == 0) {
75 fprintf(stderr, "%s: open %s: %s\n", quis, argv[3], strerror(errno));
78 if ((fs = fopen(argv[4], "rb")) == 0) {
79 fprintf(stderr, "%s: open %s: %s\n", quis, argv[4], strerror(errno));
84 if ((tv = malloc(argc * sizeof(*tv))) == 0) {
85 fprintf(stderr, "%s: malloc: %s\n", quis, strerror(errno));
88 for (i = 0; i < argc; i++)
89 tv[i] = strtoul(argv[i], 0, 16);
94 fprintf(stderr, "%s: DEBUG: offset = %lu, ck = %08lx, tot = %lu\n",
99 for (i = 0; i < argc; i++) {
101 printf("%lu %08lx\n", o, ck);
106 if (!fread(b, 4, 1, fp)) {
108 fprintf(stderr, "%s: read prefix: %s\n", quis, strerror(errno));
113 x = (b[0] << 0) | (b[1] << 8) | (b[2] << 16) | (b[3] << 24);
115 if (!fread(b, 4, 1, fs)) {
117 fprintf(stderr, "%s: read suffix: %s\n", quis, strerror(errno));
122 y = (b[0] << 0) | (b[1] << 8) | (b[2] << 16) | (b[3] << 24);
125 fprintf(stderr, "%s: DEBUG: prefix = %08lx, suffix = %08lx\n",
128 ck += ns*y - tot - i0*x;