/* god.c - bit prediction from input string 
   KMB & AS 97 Nov 11 
   Revised KMB 97 Nov 12
   Usage: god [level] <inputfile
   where length(inputfile)>level>0 (default level=4)
   e.g. 
   echo 010101010101 | god 2
   will predict 0.
   return value is predicted bit.
   Compilation: gcc -O god.c -o god
*/

#include <stdio.h>
void *calloc(); int atoi(char*);
#define O (n=((n<<=1)+c-'0'),n%=m)

int main(int argc, char* argv[]) {
  int n,l,m,p,*x; char c;
  l=(argc>1)?((l=atoi(argv[1]))<1?1:l):4;
  for (p=0,m=1;
    c=getc(stdin),c=='0'||c=='1';
    (p++>=l)?
    (p==l+1?(x=(int*)calloc(m,sizeof(int)),x[O]++):x[O]++):
    (O,m<<=1)
  );
  printf("Predicted next bit=%d\n",(n<<=1,p=x[(n+1)%m]>x[n%m]));
  free(x); return p;
}