#! /usr/bin/tcc -run
/* -*-c-*- */

/* A simple progrem to compute AccurateRip checksums for a sliding window
 * over a stream.  The algorithm is based on an observation by Jon Lund
 * Steffensen (http://jonls.dk/2009/10/calculating-accuraterip-checksums/).
 *
 * The basic checksum is c = SUM_i (i + i) S_i, where 0 <= i < n ranges over
 * the sample numbers, and S_i is the data for the sample point, expressed as
 * a single element of Z/2^{32}Z (a cheesy notational device which avoids me
 * having to write `(mod 2^{32})' everywhere).
 *
 * Steffensen's observation is this: if T_i = S_{i+1} for 0 <= i < n - 1 then
 * we can compute the checksum c' over the T_i given only a small quantity of
 * data.  Indeed,
 *
 *   c' - c = SUM_{0<=i<n} (i + 1) T_i - SUM_{0<=i<n} (i + 1) S_i
 *	    = SUM_{0<=i<n-1} (i + 1) S_{i+1} + n T_{n-1} -
 *		SUM_{0<i<n} (i + 1) S_i - S_0
 *	    = SUM_{0<i<n} i S_i + n T_{n-1} -
 *		SUM_{0<i<n} (i + 1) S_i - S_0
 *	    = n T_{n-1} - SUM_{0<=i<n} S_i
 *
 * The term SUM_{0<=i<n} S_i can be computed while we're summing up the
 * initial window.  Obviously, maintaining it is trivial.
 *
 * The final track is dealt with specially by clobbering the last five frames
 * with silence.  Since silent samples contribute nothing to the checksum, we
 * can instead consider the final track to be truncated at this point.
 *
 * Life gets a little bit more complicated when we deal with the special
 * rules for the first track: rather than simply starting (almost) five
 * frames in, we silence the initial segment.  So when we advance our window,
 * we must take off m S_0 rather than simply S_0.
 */

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <getopt.h>

int main(int argc, char *argv[])
{
  unsigned long ns, ck, tot, i0, o = 0, x, y;
  FILE *fp, *fs;
  unsigned long *tv;
  int i;
  const char *quis = argv[0];
  unsigned char b[4];
  unsigned f = 0;
#define F_DEBUG 1u

  for (;;) {
    int o = getopt(argc, argv, "di:");
    if (o == EOF) break;
    switch (o) {
      case 'd': f |= F_DEBUG; break;
      case 'i': i0 = strtoul(optarg, 0, 0); break;
      default: exit(1);
    }
  }
  argv += optind; argc -= optind;

  if (argc < 6) {
    fprintf(stderr, "Usage: %s flaccrip-slide NSAMPLES CHECKSUM SUM "
	    "PREFIX SUFFIX TARGET ...\n", quis);
    exit(1);
  }
  ns = strtoul(argv[0], 0, 0);
  ck = strtoul(argv[1], 0, 16);
  tot = strtoul(argv[2], 0, 0);
  if ((fp = fopen(argv[3], "rb")) == 0) {
    fprintf(stderr, "%s: open %s: %s\n", quis, argv[3], strerror(errno));
    exit(1);
  }
  if ((fs = fopen(argv[4], "rb")) == 0) {
    fprintf(stderr, "%s: open %s: %s\n", quis, argv[4], strerror(errno));
    exit(1);
  }
  argv += 5; argc -= 5;

  if ((tv = malloc(argc * sizeof(*tv))) == 0) {
    fprintf(stderr, "%s: malloc: %s\n", quis, strerror(errno));
    exit(1);
  }
  for (i = 0; i < argc; i++)
    tv[i] = strtoul(argv[i], 0, 16);

  for (;;) {

    if (f & F_DEBUG) {
      fprintf(stderr, "%s: DEBUG: offset = %lu, ck = %08lx, tot = %lu\n",
	      quis, o, ck, tot);
    }

    ck &= 0xffffffff;
    for (i = 0; i < argc; i++) {
      if (ck == tv[i]) {
	printf("%lu %08lx\n", o, ck);
	break;
      }
    }

    if (!fread(b, 4, 1, fp)) {
      if (ferror(fp)) {
	fprintf(stderr, "%s: read prefix: %s\n", quis, strerror(errno));
	exit(1);
      }
      break;
    }
    x = (b[0] <<  0) | (b[1] <<  8) | (b[2] << 16) | (b[3] << 24);

    if (!fread(b, 4, 1, fs)) {
      if (ferror(fs)) {
	fprintf(stderr, "%s: read suffix: %s\n", quis, strerror(errno));
	exit(1);
      }
      break;
    }
    y = (b[0] <<  0) | (b[1] <<  8) | (b[2] << 16) | (b[3] << 24);

    if (f & F_DEBUG)
      fprintf(stderr, "%s: DEBUG: prefix = %08lx, suffix = %08lx\n",
	      quis, x, y);

    ck += ns*y - tot - i0*x;
    tot += y - x;
    o++;
  }

  return (0);
}