/* CSC 310, SPRING 2004, ASSIGNMENT 4. */

#include <stdio.h>
#include <stdlib.h>


#define N 35		/* Number of bits in a codeword */
#define M 20		/* Number of parity checks */


main (int argc, char **argv)
{
  FILE *Hfile;		/* File to read parity check matrix from */
  int H[M][N];		/* Parity check matrix */
  int change;		/* Has scan of parity checks changed anything? */
  int r[N];		/* Received vector */
  int ne;		/* Number of erasures remaining */

  int i, j, s, b;

  /* Check the program arguments.  Exit with amessage if they're not valid. */

  if (argc!=2)
  { fprintf(stderr,"Usage: a4-sol parity-check-file\n");
    exit(1);
  }

  /* Read the parity check matrix.  Exit if there's an error reading it. */

  Hfile = fopen(argv[1],"r");

  for (i = 0; i<M; i++)
  { for (j = 0; j<N; j++)
    { if (fscanf(Hfile,"%d",&H[i][j])!=1) 
      { fprintf(stderr,"Error reading %s\n",argv[2]);
        exit(1);
      }
    }
  }
  
  fclose(Hfile);

  /* Read received vectors from standard input and try to decode them. */
     
  for (;;)
  { 
    /* Read the next received vector, exiting if EOF is encountered. */

    for (j = 0; j<N; j++)
    { if (scanf("%d",&r[j])!=1) 
      { exit(0);
      }
    }

    /* Try to remove erases by considering all parity checks, until 
       nothing changes as a result. */

    change = 1; 

    while (change)
    { 
      change = 0;  

      /* Look at all parity checks, correcting an erasure when all but
         one of the bits involved in a parity check are known. */

      for (i = 0; i<M; i++)
      { 
        s = 0;   /* Sum of bits in parity check, other than erasure. */
        b = -1;  /* Location of erasure, -1 if erasure not yet encountered */

        for (j = 0; j<N; j++)
        { 
          if (H[i][j]==1) /* If this bit is involved in the parity check.. */
          { 
            if (r[j]==2)  /* If this bit is still an erasure... */
            { if (b != -1) 
              { goto nexti;  /* Go to the next check if more than one erasure */
              }	
              b = j;         /* Record location of erasure involved in check */
            }
            else          /* If this bit is not an erasure... */
            { 
              s ^= r[j];     /* Add this bit to the sum (mod 2) */
            }
          }
        }

        /* If exactly one erasure was involved in the check, correct it, and
           record the fact that a change was made. */

        if (b != -1)
        { r[b] = s;
          change = 1;
        }

      nexti: ;
      }
    }

    /* Print the decoded vector. */

    for (j = 0; j<N; j++)
    { printf(" %d",r[j]);
    }

    /* Count how many erasures remain. */

    ne = 0;
    for (j = 0; j<N; j++)
    { ne += r[j]==2;
    }

    /* Print message if erasures remain. */

    if (ne>0) 
    { printf("  Not fully decoded");
    }

    /* Check that it's a codeword if all erasures were removed. */

    if (ne==0)
    { 
      /* Verify that the decoded vector is a codeword, by verifying that all
         parity checks are satisfied. */

      for (i = 0; i<M; i++)
      { 
        /* Compute the sum (mod 2) of the bits involved in this parity check. */

        s = 0;
        for (j = 0; j<N; j++)
        { if (H[i][j]==1)
          { s ^= r[j];
          }
        }

        /* Write out a message if the parity check isn't satisfied. */

        if (s!=0)
        { printf("  Not a codeword (fails check %d)",i);
          break;
        }
      }
    }

    printf("\n");
  }

}