Commit | Line | Data |
---|---|---|
583b7e4a MW |
1 | #! /usr/bin/tcc -run |
2 | /* -*-c-*- */ | |
3 | ||
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/). | |
7 | * | |
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). | |
12 | * | |
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 | |
15 | * data. Indeed, | |
16 | * | |
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 | |
23 | * | |
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. | |
26 | * | |
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. | |
30 | * | |
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. | |
35 | */ | |
36 | ||
37 | #include <errno.h> | |
38 | #include <stdio.h> | |
39 | #include <stdlib.h> | |
40 | #include <string.h> | |
41 | ||
42 | #include <getopt.h> | |
43 | ||
44 | int main(int argc, char *argv[]) | |
45 | { | |
46 | unsigned long ns, ck, tot, i0, o = 0, x, y; | |
47 | FILE *fp, *fs; | |
48 | unsigned long *tv; | |
49 | int i; | |
50 | const char *quis = argv[0]; | |
51 | unsigned char b[4]; | |
52 | unsigned f = 0; | |
53 | #define F_DEBUG 1u | |
54 | ||
55 | for (;;) { | |
56 | int o = getopt(argc, argv, "di:"); | |
57 | if (o == EOF) break; | |
58 | switch (o) { | |
59 | case 'd': f |= F_DEBUG; break; | |
60 | case 'i': i0 = strtoul(optarg, 0, 0); break; | |
61 | default: exit(1); | |
62 | } | |
63 | } | |
64 | argv += optind; argc -= optind; | |
65 | ||
66 | if (argc < 6) { | |
67 | fprintf(stderr, "Usage: %s flaccrip-slide NSAMPLES CHECKSUM SUM " | |
68 | "PREFIX SUFFIX TARGET ...\n", quis); | |
69 | exit(1); | |
70 | } | |
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)); | |
76 | exit(1); | |
77 | } | |
78 | if ((fs = fopen(argv[4], "rb")) == 0) { | |
79 | fprintf(stderr, "%s: open %s: %s\n", quis, argv[4], strerror(errno)); | |
80 | exit(1); | |
81 | } | |
82 | argv += 5; argc -= 5; | |
83 | ||
84 | if ((tv = malloc(argc * sizeof(*tv))) == 0) { | |
85 | fprintf(stderr, "%s: malloc: %s\n", quis, strerror(errno)); | |
86 | exit(1); | |
87 | } | |
88 | for (i = 0; i < argc; i++) | |
89 | tv[i] = strtoul(argv[i], 0, 16); | |
90 | ||
91 | for (;;) { | |
92 | ||
93 | if (f & F_DEBUG) { | |
94 | fprintf(stderr, "%s: DEBUG: offset = %lu, ck = %08lx, tot = %lu\n", | |
95 | quis, o, ck, tot); | |
96 | } | |
97 | ||
98 | ck &= 0xffffffff; | |
99 | for (i = 0; i < argc; i++) { | |
100 | if (ck == tv[i]) { | |
101 | printf("%lu %08lx\n", o, ck); | |
102 | break; | |
103 | } | |
104 | } | |
105 | ||
106 | if (!fread(b, 4, 1, fp)) { | |
107 | if (ferror(fp)) { | |
108 | fprintf(stderr, "%s: read prefix: %s\n", quis, strerror(errno)); | |
109 | exit(1); | |
110 | } | |
111 | break; | |
112 | } | |
113 | x = (b[0] << 0) | (b[1] << 8) | (b[2] << 16) | (b[3] << 24); | |
114 | ||
115 | if (!fread(b, 4, 1, fs)) { | |
116 | if (ferror(fs)) { | |
117 | fprintf(stderr, "%s: read suffix: %s\n", quis, strerror(errno)); | |
118 | exit(1); | |
119 | } | |
120 | break; | |
121 | } | |
122 | y = (b[0] << 0) | (b[1] << 8) | (b[2] << 16) | (b[3] << 24); | |
123 | ||
124 | if (f & F_DEBUG) | |
125 | fprintf(stderr, "%s: DEBUG: prefix = %08lx, suffix = %08lx\n", | |
126 | quis, x, y); | |
127 | ||
128 | ck += ns*y - tot - i0*x; | |
129 | tot += y - x; | |
130 | o++; | |
131 | } | |
132 | ||
133 | return (0); | |
134 | } |