view checksum/dosum.c @ 0:13d2b8934445

Import AnaGram (near-)release tree into Mercurial.
author David A. Holland
date Sat, 22 Dec 2007 17:52:45 -0500
parents
children 3aa0f5a02342
line wrap: on
line source

/*
 * AnaGram, A System for Syntax Directed Programming
 * Copyright 1993 Parsifal Software. All Rights Reserved.
 * Copyright 2006 David A. Holland. All Rights Reserved.
 * See the file COPYING for license and usage terms.
 *
 * dosum.c - checksums.
 */

/*
 * Fletcher's check-sum routines for AnaGram
 * 
 * Freely adapted from routines published in Dr. Dobbs Journal
 * May 1992, p. 64
 *
 * Revised as portable C in June 2006.
 */

#include <stdint.h>
#include <string.h>
#include <assert.h>

#include "bits.h"

struct sumstate {
  uint16_t k1, k2;
};

static void sumstate_init(struct sumstate *s, size_t length) {
  s->k1 = (uint16_t) (length >> 16);
  s->k2 = (uint16_t) length;

  if (s->k1 == 0) s->k1++;
  if (s->k2 == 0) s->k2++;
}

static void sumstate_sum(struct sumstate *s, const void *buf, size_t len) {
  const uint8_t *cb;
  unsigned i, n;
  uint16_t x;

  cb = buf;
  n = len/sizeof(uint16_t);
  for (i=0; i<n; i++) {

    // read one octet at a time so the byte order is deterministic
    x = *cb++;
    x += ((uint16_t)*cb++) << 8;

    s->k1 += x;
    if (s->k1 < x) s->k1++;
    s->k2 += s->k1;
    if (s->k2 < s->k1) s->k2++;
  }
}

static uint32_t sumstate_finish(struct sumstate *s) {
  uint32_t sum;

  s->k1 ^= 0xffff;
  s->k2 ^= 0xffff;
  sum = 65535UL*s->k2 + s->k1;

  return sum;
}

uint32_t dosum(const char *buf, size_t len, size_t skipstart, size_t skiplen) {
  struct sumstate s;
  unsigned fudge;
  size_t numwords;

  assert(skiplen%2==0);
  assert(skipstart==0 || skipstart+skiplen <= len);
  sumstate_init(&s, len);

  /*
   * It would be nice if we could count on skipstart being aligned.
   * But we can't. Nor is the filesize necessarily even.
   *
   * The followed mangled logic that rounds some things up matches
   * what used to be done in an even uglier way.
   */

  assert(sizeof(uint16_t)==2);
  numwords = (len+1)/2;

  if (skipstart > 0) {
    size_t p0 = skipstart+skiplen;
    size_t l0 = (numwords - p0/2) * 2;
    size_t p1 = 0;
    size_t l1 = (skipstart/2) * 2;

    fudge = skipstart%2;
    sumstate_sum(&s, buf+p0, l0);
    sumstate_sum(&s, buf+p1, l1);
  }
  else {
    sumstate_sum(&s, buf, numwords * 2);
  }

  return sumstate_finish(&s);
}