/* crc_fsa.c */ 
#include  <stdio.h>
#include  <stdlib.h>
#include  <time.h>
 
#define  gp   285      /* the generator polynomial */ 
#define  hpo2 256      /* highest power of 2 in the gp */ 
 
int main() 
{ 
  int r,c, t, cs, cs2, pos; 
  int i, bb, li, 
      bim,        /* bits in the message */ 
      btbc,       /* bit to be changed */ 
      bigp,       /* bits in the gp */ 
      debug = 0; 
  int msg[hpo2];  /* the actual message */
  int fsa_table[hpo2][2]; 
  int checksum[hpo2]; 
  time_t tt; 
 
  /* initialize the random number generator */ 
  srand((unsigned) time(&tt)); 
 
  /* determine the number of bits (bigp) in the gp */ 
  li = gp >> 1; 
  bigp = 1; 
  while (li) { li = li >> 1; bigp++; } 

  /* determine the maximum number of bits in the message */ 
  bim = hpo2 - bigp; 
 
  printf("generator polynomial          %2d\n",gp); 
  printf("highest power of 2 in gp      %2d\n",hpo2); 
  printf("bits in generator polynomial  %2d\n",bigp); 
  printf("bits in message               %2d\n\n",bim); 
 
  /* Both the sender and the receiver need to build the FST */ 
  for (r = 0; r < hpo2; r++) 
    for (c = 0; c < 2; c++) 
      { 
        t = r*2+c; 
        if (t >= hpo2) t ^= gp; 
        fsa_table[r][c] = t; 
      } 
 
  /* display the FST */ 
  if (debug) 
    { 
      printf("FST table for gp = %d\n\n",gp); 
      printf("index     0     1\n"); 
      printf("        -----------\n"); 
      for (r = 0; r < hpo2; r++) 
        { printf("   %2d  | ",r); 
          for (c = 0; c < 2; c++) printf("%2d  | ",fsa_table[r][c]); 
          printf("\n"); 
        } 
    } 
 
  /* Only the receiver will need to build the Error Correction 
     table for the GP */ 
  for (pos=hpo2-1; pos > 0; pos--) checksum[pos]=0; 
  t = 1; 
  for (pos=hpo2-1; pos > 0; pos--) 
    { 
      if (checksum[t]) printf("%d is not a valid gp\n",gp), exit(0); 
      else checksum[t] = pos; 
      t *= 2; 
      if (t >= hpo2) t ^= gp; 
    } 
 
  /* display the error correction table for the gp */ 
  if (debug) 
    { 
      printf("\n\nError Correction table for gp = %d\n",gp); 
      printf("index   position of\n"); 
      printf("        the bad bit\n"); 
      printf("            --- \n"); 
      for (r=1; r < hpo2; r++) 
        printf("    %2d     | %2d |\n",r,checksum[r]); 
      printf("\n"); 
    } 
 
  /* generate a random message */ 
  for (i=0; i <= bim; i++) msg[i] = rand()%2; 
 
  /* display the message */ 
  printf("The original message         "); 
  for (i=1; i <= bim; i++) printf("%d",msg[i]); 
  printf("\n"); 
 
  /* zero out then compute the checksum */ 
  for (i=bim+1; i < hpo2; i++) msg[i] = 0; 
  cs = 0; 
  for (r = 1; r < hpo2; r++) 
    cs = fsa_table[cs][msg[r]]; 
 
  /* Put the checksum on the end of the message */ 
  for (i = bim+1; i < hpo2; i++) msg[i] = (cs >> hpo2-i-1) & 1; 
 
  /* display the message and the checksum */ 
  if (debug) 
    { 
      printf("with the checksum            "); 
      for (i=1; i < hpo2; i++) 
        printf("%d",msg[i]); 
      printf("\n"); 
    } 
 
  /* The message|checksum can now be sent.  Simulate a problem by 
     changing a random bit */ 
  btbc = rand()%(hpo2-1)+1; 
  msg[btbc] ^= 1; 
 
 /* 
  * Part 2 
  * The receiver has received a message with 1 bad bit. 
  */ 
  printf("After receiving the message, msg = "); 
  for (r = 1; r < hpo2; r++) printf("%d",msg[r]); 
  printf("\n"); 
 
  /* compute the checksum */ 
  cs2 = 0; 
  for (r = 1; r < hpo2; r++) 
    cs2 = fsa_table[cs2][msg[r]]; 
 
  if (debug) printf("the checksum is %d\n",cs2); 
 
  if (cs2 > 0) 
    { 
      /* determine the bad bit */ 
      pos = checksum[cs2]; 
 
      /* correct the bad bit */ 
      msg[pos] ^= 1; 
    } 
 
  /* display the (corrected) message */ 
  printf("The corrected message        "); 
  for (i=1; i <= bim; i++) printf("%d",msg[i]); printf("\n"); 
 
  printf("Normal Termination\n"); 
}