/* Program to generate addition and multiplication tables for polynomials wih
   coefficients in the integers modulo 2.  Each such polynomial is equivalent
   to a nonnegative integer whose binary expansion has kth bit equal to the
   coefficient of the kth power, for k=0,1,2,... */

#include <assert.h>
#include <stdio.h>



int
deg2 ( int p )			/* return degree of p */
{
  int d= -1;			/* -1 signifies degree = -infinity */
  assert(p>=0);			/* require nonnegative input */
  while(p>0) { ++d; p>>=1; }
  return d;
}

void
divide2 ( int numer, int denom, int *quot, int *rem )
{
  int shift, result=0;
  assert(numer>=0);  assert(denom>0);
  assert(quot);  assert(rem);
  
  while( (shift=deg2(numer)-deg2(denom)) >= 0 ) {
    numer ^= denom<<shift;
    result |= 1<<shift;
  }
  *quot = result;
  *rem = numer;
  return;
}

int
p2 ( int x, int y )		/* return x times y in GF2 */
{
  int shift=0, result=0;
  assert(x>=0);  assert(y>=0);	/* require nonnegative inputs */
  while(x>0) {
    if( x&1 )
      result ^=(y<<shift);
    ++shift;			/* to consider next digit of x */
    x>>=1;			/* put the next bit of x at position 0 */
  }
  return result;
}

int
main ( void )
{
  int x,y, n;

  n = 8;			/* create an n by n table */

  /* Addition is equivalent to bitwise exclusive OR: */
  printf(" +  ");		/* table label */
  for(y=0; y<n; y++)
    printf(" %d ", y);		/* column labels */
  printf("\n   -------------------------\n"); /* for 8x8 table only */
  for(x=0;x<n;x++) {
    printf(" %d |", x);		/* row label  */
    for(y=0; y<n; y++)
      printf(" %d ", x^y);	/* table value */
    putchar('\n');
  }

  printf("\n\n");		/* Separate the tables */

  /* Multiplication is equivalent to shifts and bitwise exclusive ORs: */
  printf(" x  ");		/* table label */
  for(y=0; y<n; y++)
    printf(" %2d ", y);		/* column labels */
  printf("\n   ---------------------------------\n"); /* for 8x8 table only */
  for(x=0;x<n;x++) {
    printf(" %d |", x);		/* row label  */
    for(y=0; y<n; y++)
      printf(" %2d ",p2(x,y));	/* table value */
    putchar('\n');
  }
  printf("\n\n");		/* Separate the tables */

  /* Multiplication with reduction modulo t^3, or 8: */
  printf(" x_8");		/* table label */
  for(y=0; y<n; y++)
    printf(" %2d ", y);		/* column labels */
  printf("\n   ---------------------------------\n"); /* for 8x8 table only */
  for(x=0;x<n;x++) {
    printf(" %d |", x);		/* row label  */
    for(y=0; y<n; y++)
      printf(" %2d ",p2(x,y)%8);	/* table value */
    putchar('\n');
  }
  printf("\n\n");		/* Separate the tables */

  /* Multiplication with reduction modulo t^3+t+1, or 11: */
  printf(" x_11");		/* table label */
  for(y=0; y<11; y++)
    printf(" %2d ", y);		/* column labels */
  printf("\n    ---------------------------------------------\n"); /* 11x11 only */
  for(x=0;x<11;x++) {
    printf(" %2d |", x);		/* row label  */
    for(y=0; y<11; y++) {
      int quot,rem;
      divide2 ( p2(x,y), 11, &quot, &rem );
      printf(" %2d ",rem);	/* table value */
    }
    putchar('\n');
  }
  printf("\n\n");		/* Separate the tables */

  /* Quotient and remainder of x/y : */
  printf(" /%% ");		/* table label */
  for(y=1; y<=n; y++)
    printf("  %d  ", y);		/* column labels */
  printf("\n   -----------------------------------------\n"); /* 8x8 only */
  for(x=1;x<=n;x++) {
    printf(" %d |", x);		/* row label  */
    for(y=1; y<=n; y++) {
      int quot, rem;
      divide2(x,y, &quot, &rem);
      printf(" %d,%d ",quot,rem);	/* table value */
    }
    putchar('\n');
  }
  printf("\n\n");		/* Separate the tables */

  /* Checksums modulo t^3+t+1, or 11: */
  printf("  x | c_S(x) for S(t)=t^3+t+1 ~ 11\n");	/* table label */
  for(x=0;x<32;x++) {
    int quot,rem;
    divide2 ( x, 11, &quot, &rem );
    printf(" %2d | %d\n", x, rem);	/* table value */
  }


  return 0;
}