chiark - git - mdw - autoys/blob - flaccrip/flaccrip-slide

   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 }