source: trunk/gsdl/src/hashfile/hashfile.cpp@ 4

#include <stdio.h>

#define MAXNUMLEN  100   // bytes


// The number class is used to store very long unsigned integers.
// The least significant of each number is stored first. Numbers can 
// be no longer than MAXNUMLEN bytes long. A number with length=0
// is considered to be equal to 0. There should be no extra zeros
// at the front of the number.

struct number {
  unsigned int len;
  unsigned char num[MAXNUMLEN];

  number () {len = 0;}
};


// evaluates a = a + b
// a and b can be the same number
void my_inc (number &a, number &b) {
  unsigned int carry = 0;
  unsigned int num = 0;
  unsigned int i = 0;

  while ((carry || (i < a.len) || (i < b.len)) && (i < MAXNUMLEN)) {
    num = carry;
    if (i < a.len) num += a.num[i];
    if (i < b.len) num += b.num[i];

    if (num >= 256) {
      num -= 256; // assumes that each number in the list < 256
      carry = 1;
    } else {
      carry = 0;
    }
    a.num[i] = (unsigned char)num;

    i++;
  }

  a.len = i;
}


// evaluates a = a - b if a >= b
// returns true if the subtraction was possible
int my_ifpos_dec (number &a, number &b) {
  int carry = 0;
  int num = 0;
  unsigned int i = 0;
  unsigned int len = 0; // the last non-zero digit

  // make sure a >= b
  if (b.len > a.len) return 0;
  if (b.len == a.len) {
    i = a.len - 1;
    while (i >= 0) {
      if (a.num[i] > b.num[i]) break;
      if (a.num[i] < b.num[i]) return 0;
      i--;
    }
  }

  i = 0;
  len = 0;
  while ((i < a.len) || (i < b.len)) {
    num = -carry;
    if (i < a.len) num += a.num[i];
    if (i < b.len) num -= b.num[i];

    if (num < 0) {
      num += 256; // assumes each number in the list < 256
      carry = 1;
    } else {
      carry = 0;
    }

    a.num[i] = (unsigned char) num;
    
    i++;
    if (num != 0) len = i;
  }

  a.len = len;

  if (carry) {
    // panic, this should NOT happen
    fprintf (stderr, "panic: error in my_ifpos_dec\n");
  }

  return 1;
}


char *my_convert_num (number &a) {
  char *result = new char[a.len+2];
  int i,len;
  char convert[16] = {'0','1','2','3','4','5','6','7',
              '8','9','a','b','c','d','e','f'};

  // zero might be a special case
  if (a.len == 0) {
    result[0] = '0';
    result[1] = '\0';
    return result;
  }

  for (i=a.len-1, len=0; i >= 0; i--) {
    result[len++] = convert[a.num[i]/16];
    result[len++] = convert[a.num[i]%16];
  }
  result[len] = '\0';

  return result;
}


char *hashfile (char *filename) {
  FILE *infile = NULL;
  int i;

  // calculate the 8 multiples of the prime number to use
  // in the long division
  number primepow[8];
  number pow;
  number remainder;
  unsigned char c;

  // our prime number (618970019642690137449562111)
  pow.num[0] = 255;  pow.num[1] = 255;
  pow.num[2] = 255;  pow.num[3] = 255;
  pow.num[4] = 255;  pow.num[5] = 255;
  pow.num[6] = 255;  pow.num[7] = 255;
  pow.num[8] = 255;  pow.num[9] = 255;
  pow.num[10] = 255; pow.num[11] = 1;
  pow.len = 12;

  for (i=0; i<8; i++) {
    primepow[i] = pow;
    my_inc (pow, pow);
  }

  infile = fopen (filename, "rb");
  if (infile == NULL) {
    return NULL;
  }
  
  remainder.len = 0;
  c = (unsigned char)fgetc(infile);
  while (!feof (infile)) {
    // remainder = remainder * 256 + c
    if (remainder.len == MAXNUMLEN-1) {
      fprintf (stderr, "ERROR - number overflow\n");
      return NULL;
    }
    for (i=remainder.len; i>0; i--) {
      remainder.num[i] = remainder.num[i-1];
    }
    remainder.num[0] = c;
    remainder.len = remainder.len+1;
    
    for (i=7; i>=0; i--) {
      my_ifpos_dec (remainder, primepow[i]);
    }

    c = (unsigned char)fgetc(infile);
  }

  fclose (infile);

  return my_convert_num (remainder);
}


int main (int argc, char *argv[]) {
  int i;
  char *result;

  for (i = 1; i < argc; i++) {
    result = hashfile (argv[i]);
    if (result == NULL) {
      printf ("ERROR - could not process %s\n", argv[i]);
    } else {
      printf ("%s: %s\n", argv[i], result);
      delete [] result;
    }
  }

  return 0;
}