@* Polynomial program.
\medskip
 Copyright 1991 Robert Solovay -- University of California, Berkeley
\medskip
Permission to use, copy, modify, and distribute this software and its
documentation for any purpose and without fee is hereby granted, provided
that the above copyright notice appear in all copies and that both that
copyright notice and this permission notice appear in supporting
documentation.  This software is provided ``as is'' without express or
implied warranty.
\medskip

@* The skeleton.
 Here is the main module of the program.

@c
@<Global typedefs@>@/
@<Global constants@>@/
@<Global variables@>@/
@<Global |include|s@>@/
@<All functions@>@/
@<Main@>
@
We will have a constant |SIZE| which gives the number of bits in the
polynomials we are working with.
@d SIZE 16
@<Global typedefs@>=
typedef  int Field ;
typedef Field Poly[SIZE];
typedef Poly *polyPtr;
typedef Field LongPoly[SIZE+SIZE];
@
@<Global constants@>=
unsigned int	CRC_INT = 0x8005;
@
@<Global variables@>=
Poly  *CRC_Ptr;
@
We have to include the standard I/O definitions, as well as some
other standard header files.  Until all C implementations reach
the level of the 1989 ANSI C standard, we have to be careful about
which files we try to include.  The GNU C compiler defines the
symbol |__STDC__|, but is commonly run with native pre-ANSI header
files.
@<Global |in...@>=
#include <stdio.h>

#if defined(__STDC__) && !defined(__GNUC__)
#include<stddef.h>
#include<stdlib.h>
#endif

#ifdef THINK_C
#include <console.h>
#endif

#if defined(__STDC__)||defined(__GNUC__)||defined(__TURBOC__)||defined(MSDOS)
#define ARGS(plist) plist
#else
#define ARGS(plist) ()
#endif

void ConvertIntToPoly ARGS((unsigned int Int,polyPtr Ptr));
Field FPlus ARGS((Field s,Field t));
int main ARGS((void));
void ReduceLongPoly ARGS((LongPoly *s, Poly *t, Poly *u));
unsigned int ReductionOfByte ARGS((unsigned int x));
@
First we need the standard field function |FPlus|. In
the current implementation the field is always $Z_2$.
@<All functions...@>=
Field FPlus(s,t)
	Field s,t;
{return(s != t);}


@
The next function takes a bit more explanation. It takes as inputs
three pointers |s|, |t|, |u|. Here |s| is a pointer to a |LongPoly|
and |t| and |u| are pointers to |Poly|'s. Let $f$ and $g$ be the
polynomials pointed to by |s| and |t|. We form the new polynomial
$$h = x^N + g$$
(where $N = \hbox{|SIZE|}$.)

We divide the polynomial $f$ by the polynomial $h$ and store the
result in the place indicated by the pointer |u|.
@<All functions@>=
void ReduceLongPoly(s,t,u)
	LongPoly *s;
	Poly *t, *u;
	{
	LongPoly f;
	int i,j;
	for(i=0;i < (SIZE + SIZE); i++)
	f[i] = (*s)[i];
	for(i = ((SIZE + SIZE) - 1); i >= SIZE; i--)
	if (f[i] != 0)
	{
	f[i] = 0;
	for(j=0;j < SIZE; j++)
	f[i-(1+j)] = FPlus(f[i-(1+j)],(*t)[SIZE-(1+j)]);
	}
	for(i=0;i<SIZE;i++)
	(*u)[i] = f[i];
	}
@
The following function converts an unsigned integer to a |Poly|.
@<All functions@>=
void ConvertIntToPoly(Int,Ptr)
	unsigned int Int;
	polyPtr Ptr;
{int i;
for(i=0;i< SIZE;i++)
{(*Ptr)[i] =  Int%2;
	Int = Int/2;}
}


@
The next function we will write will take an input which is an
unsigned integer (typically in the range $0 \leq x < 255$, and output
an unsigned integer, y. The semantics of the function is as follows.
it interprets $x$ as a polynomial of degree $< 8$ with coefficients in
the field $Z_2$. It multiplies this polynomial by $x^{16}$ and then
reduces it modulo the CRC polynomial, which in the current
implementation is $x^{16} + x^{15} + x^2 + 1$. The result it
reinterprets as an unsigned integer $y$ which is the output.
@<All functions@>=
unsigned int ReductionOfByte(x)
	unsigned int x;
{
Poly  *pt;
LongPoly  *pls;
int i;
unsigned int u;
	@<Assign space for the structures that our pointers point to@>@/
	x = x%256;

	for(i=0;i< (SIZE+SIZE) ;i++)
	(*pls)[i]=0;
	for(i=0; i < SIZE; i++)
	{(*pls)[SIZE+i] = x%2; x = x/2;}
	ReduceLongPoly(pls,CRC_Ptr,pt);
	u = 0;
	for(i=0;i<SIZE;i++)
	 u = (u*2) + (*pt)[SIZE - (1+i)];
	return(u);}
@
@<Assign space...@>=
pt = (Poly *) malloc(sizeof(Poly));
pls = (LongPoly *) malloc(sizeof(LongPoly));
if ( (pt == NULL) || (pls == NULL))@/
@<Complain about malloc@>@/
@
@<Complain about malloc@>=
fprintf(stderr, "Trouble assigning space to pointers.\n");
@ @<Main@>=
int
main ()

{
	@<Variables local to |main|@>@/
	@<Initialize Data Structures@>@/
	output_file = fopen("crc.tab","w");
	for(i=0;i < 32;i++)
	{for(j=0;j < 8; j++)
	fprintf(output_file,"0x%04x, ", ReductionOfByte(8*i + j));
	fprintf(output_file,"\n");}
	fclose(output_file);
	exit(0);
	return(0);
}
@
@<Variables local to...@>=
FILE *output_file;
unsigned int i, j;
@
@<Initialize Data Structures@>=
CRC_Ptr = (Poly *) malloc(sizeof(Poly));
if(CRC_Ptr == NULL)@<Complain about malloc@>@/
ConvertIntToPoly(CRC_INT,CRC_Ptr);