/*
Cellular Automaton Addition Hashing Function
Author: Jacob I. Torrey
Date: Oct. 9, 2008
Language: C++
*/

#include<string>
#include<iostream>
#include<cstring>
#include<stdio.h>

using namespace std;

#define DEBUG 0

#define HASHLEN 22 // How many 8-bit cells long the hash should be
#define ITR 22 * 1.4 // How many iterations to perform on the system

int main(int argc, char ** argv) {
  if(argc != 2) {
    cout << "\tUsage " << argv[0] << " string - Computes a cellular automata derived hash of the passed string" << endl;
    exit(0);
  }
  int len = strlen(argv[1]);
  string in = string(argv[1]);
  int numlines = len / HASHLEN + 1;

  string * lines = new string[numlines + 1]; // The current step
  string * olines = new string[numlines + 1]; // The previous step
  for(int i = 0; i < numlines; i++) {
    if(i == numlines - 1) { // In case padding is needed
      lines[i] = in.substr(HASHLEN * i, HASHLEN);
      olines[i] = in.substr(HASHLEN * i, HASHLEN);
      while(lines[i].length() < HASHLEN) { // Pad with 0s
	lines[i].push_back('0');
	olines[i].push_back('0');
      }
    } else {
      lines[i] = in.substr(HASHLEN * i, HASHLEN);
      olines[i] = in.substr(HASHLEN * i, HASHLEN);
    }
  }

  for(int i = 0; i < HASHLEN; i++) { // Init the botton ring
    lines[numlines][i] = i;
    olines[numlines][i] = i;
  }

  numlines++; // Increase so it will see the botton ring

  for(int i = 0; i < ITR; i++) {
    for(int j = 0; j < numlines; j++) {
      for(int m = 0; m < HASHLEN; m++) {
	lines[j][m] += olines[j % numlines][(m + 1) % HASHLEN];
	lines[j][m] += olines[j % numlines][(m - 1) % HASHLEN];
	lines[j][m] += olines[(j + 1) % numlines][m % HASHLEN];
	lines[j][m] += olines[(j - 1 + numlines) % numlines][m % HASHLEN];

	lines[j][m] -= olines[j % numlines][(m + 2) % HASHLEN];
	lines[j][m] -= olines[j % numlines][(m - 2) % HASHLEN];
	lines[j][m] -= olines[(j + 2) % numlines][m % HASHLEN];
	lines[j][m] -= olines[(j - 2 + numlines) % numlines][m % HASHLEN];
      }
    }
    for(int j = 0; j < numlines; j++) { // Here we'll copy the current step to the old step
      olines[j] = lines[j];
      if(DEBUG) {
	cout << "Line " << j << endl;
	for(int k = 0; k < HASHLEN; k++) {
	  printf("%d ", lines[j][k]);
	}
	cout << endl << endl;
      }
    }
  }

  for(int i = 1; i < numlines; i++) {
    for(int j = 0; j < HASHLEN; j++) {
      lines[0][j] += lines[i][j]; // Squish all the lines together to make one total hash
    }
  }

  for(int i = 0; i < HASHLEN; i++) {
    printf("%x", (lines[0][i] & 0xff)); // Print out the hash in hexadecimal
  }
  cout << endl;

  delete [] lines; // Free our memory!
  delete [] olines;

  return 0; // All done!
}