\input cwebmac

\N1.  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

\fi

\N2.  The skeleton.
Here is the main module of the program.

\Y\B\X3:Global typedefs\X\6
\X4:Global constants\X\6
\X5:Global variables\X\6
\X6:Global \&{include}s\X\6
\X7:All functions\X\6
\X13:Main\X\par
\fi

\M3.
We will have a constant \.{SIZE} which gives the number of bits in the
polynomials we are working with.
\Y\B\4\D$\.{SIZE}$ \5
\T{16}\par
\Y\B\4\X3:Global typedefs\X${}\E{}$\6
\&{typedef} \&{int} \&{Field};\6
\&{typedef} \&{Field} \&{Poly}[\.{SIZE}];\6
\&{typedef} \&{Poly} ${}{*}\&{polyPtr};{}$\6
\&{typedef} \&{Field} ${}\&{LongPoly}[\.{SIZE}+\.{SIZE}]{}$;\par
\U2.\fi

\M4.
\Y\B\4\X4:Global constants\X${}\E{}$\6
\&{unsigned} \&{int} \.{CRC\_INT}${}\K\T{\^8005}{}$;\par
\U2.\fi

\M5.
\Y\B\4\X5:Global variables\X${}\E{}$\6
\&{Poly} ${}{*}\\{CRC\_Ptr}{}$;\par
\U2.\fi

\M6.
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.
\Y\B\4\X6:Global \&{include}s\X${}\E{}$\6
\8\#\&{include} \.{<stdio.h>}\6
\8\#\&{if} ${}\\{defined}(\.{\_\_STDC\_\_})\W\R\\{defined} \5(\.{\_\_GNUC\_%
\_}){}$\6
\8\#\&{include} \.{<stddef.h>}\6
\8\#\&{include} \.{<stdlib.h>}\6
\8\#\&{endif}\6
\8\#\&{ifdef} \.{THINK\_C}\6
\8\#\&{include} \.{<console.h>}\6
\8\#\&{endif}\6
\8\#\&{if} ${}\\{defined}(\.{\_\_STDC\_\_})\V\\{defined}(\.{\_\_GNUC\_\_})\V%
\\{defined}(\.{\_\_TURBOC\_\_})\V\\{defined} \5(\.{MSDOS}){}$\6
\8\#\&{define} \.{ARGS}(\\{plist}) \5\\{plist}\6
\8\#\&{else}\6
\8\#\&{define} \.{ARGS}(\\{plist}) \5(\,)\6
\8\#\&{endif}\6
\&{void}  \\{ConvertIntToPoly}\.{ARGS} ( ( \&{unsigned} \&{int} \\{Int}${},{}$ %
\1\1 \&{polyPtr} \\{Ptr} ) )  ; \&{Field}  \\{FPlus}\.{ARGS} ( ( \&{Field} %
\|s${},{}$ \1\1 \&{Field} \|t ) )  ; \&{int}  \\{main}\.{ARGS} ( (\&{void}) )
; \&{void}  \\{ReduceLongPoly}\.{ARGS} ( ( \&{LongPoly} ${}{*}\|s,{}$ \1\1 %
\&{Poly} ${}{*}\|t,{}$ \1\1 \&{Poly} ${}{*}\|u$ ) )  ; \&{unsigned} \&{int}  %
\\{ReductionOfByte}\.{ARGS} ( (\&{unsigned} \&{int} \|x) )  ;\par
\U2.\fi

\M7.
First we need the standard field function \\{FPlus}. In
the current implementation the field is always $Z_2$.
\Y\B\4\X7:All functions\X${}\E{}$\6
\&{Field} ${}\\{FPlus}(\|s,\39\|t){}$\1\1\6
\&{Field} \|s${},{}$ \|t;\2\2\6
${}\{{}$\1\6
\&{return} ${}(\|s\I\|t);{}$\6
\4${}\}{}$\2\par
\As8, 9\ETs10.
\U2.\fi

\M8.
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.
\Y\B\4\X7:All functions\X${}\mathrel+\E{}$\6
\&{void} ${}\\{ReduceLongPoly}(\|s,\39\|t,\39\|u){}$\1\1\6
\&{LongPoly} ${}{*}\|s;{}$\6
\&{Poly} ${}{*}\|t,{}$ ${}{*}\|u;\2\2{}$\6
${}\{{}$\1\6
\&{LongPoly} \|f;\6
\&{int} \|i${},{}$ \|j;\7
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<(\.{SIZE}+\.{SIZE});{}$ ${}\|i\PP){}$\1\5
${}\|f[\|i]\K({*}\|s)[\|i];{}$\2\6
\&{for} ${}(\|i\K((\.{SIZE}+\.{SIZE})-\T{1});{}$ ${}\|i\G\.{SIZE};{}$ ${}\|i%
\MM){}$\1\6
\&{if} ${}(\|f[\|i]\I\T{0}){}$\5
${}\{{}$\1\6
${}\|f[\|i]\K\T{0};{}$\6
\&{for} ${}(\|j\K\T{0};{}$ ${}\|j<\.{SIZE};{}$ ${}\|j\PP){}$\1\5
${}\|f[\|i-(\T{1}+\|j)]\K\\{FPlus}(\|f[\|i-(\T{1}+\|j)],\39({*}\|t)[\.{SIZE}-(%
\T{1}+\|j)]);{}$\2\6
\4${}\}{}$\2\2\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\.{SIZE};{}$ ${}\|i\PP){}$\1\5
${}({*}\|u)[\|i]\K\|f[\|i];{}$\2\6
\4${}\}{}$\2\par
\fi

\M9.
The following function converts an unsigned integer to a \&{Poly}.
\Y\B\4\X7:All functions\X${}\mathrel+\E{}$\6
\&{void} ${}\\{ConvertIntToPoly}(\\{Int},\39\\{Ptr}){}$\1\1\6
\&{unsigned} \&{int} \\{Int};\6
\&{polyPtr} \\{Ptr};\2\2\6
${}\{{}$\1\6
\&{int} \|i;\7
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\.{SIZE};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
${}({*}\\{Ptr})[\|i]\K\\{Int}\MOD\T{2};{}$\6
${}\\{Int}\K\\{Int}/\T{2};{}$\6
\4${}\}{}$\2\6
\4${}\}{}$\2\par
\fi

\M10.
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.
\Y\B\4\X7:All functions\X${}\mathrel+\E{}$\6
\&{unsigned} \&{int} \\{ReductionOfByte}(\|x)\1\1\6
\&{unsigned} \&{int} \|x;\2\2\6
${}\{{}$\1\6
\&{Poly} ${}{*}\\{pt};{}$\6
\&{LongPoly} ${}{*}\\{pls};{}$\6
\&{int} \|i;\6
\&{unsigned} \&{int} \|u;\7
\X11:Assign space for the structures that our pointers point to\X\6
\|x${}\K\|x\MOD\T{256};{}$\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<(\.{SIZE}+\.{SIZE});{}$ ${}\|i\PP){}$\1\5
${}({*}\\{pls})[\|i]\K\T{0};{}$\2\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\.{SIZE};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
${}({*}\\{pls})[\.{SIZE}+\|i]\K\|x\MOD\T{2};{}$\6
${}\|x\K\|x/\T{2};{}$\6
\4${}\}{}$\2\6
${}\\{ReduceLongPoly}(\\{pls},\39\\{CRC\_Ptr},\39\\{pt});{}$\6
${}\|u\K\T{0};{}$\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\.{SIZE};{}$ ${}\|i\PP){}$\1\5
${}\|u\K(\|u*\T{2})+({*}\\{pt})[\.{SIZE}-(\T{1}+\|i)];{}$\2\6
\&{return} (\|u);\6
\4${}\}{}$\2\par
\fi

\M11.
\Y\B\4\X11:Assign space for the structures that our pointers point to\X${}\E{}$%
\6
${}\\{pt}\K{}$(\&{Poly} ${}{*}){}$ \\{malloc}(\&{sizeof}(\&{Poly}));\6
${}\\{pls}\K{}$(\&{LongPoly} ${}{*}){}$ \\{malloc}(\&{sizeof}(\&{LongPoly})); %
\&{if} ${}((\\{pt}\E\NULL)\V(\\{pls}\E\NULL){}$)\6
\X12:Complain about malloc\X\par
\U10.\fi

\M12.
\Y\B\4\X12:Complain about malloc\X${}\E{}$\6
${}\\{fprintf}(\\{stderr},\39\.{"Trouble\ assigning\ s}\)\.{pace\ to\ pointers.%
\\n"}){}$;\par
\Us11\ET15.\fi

\M13. \B\X13:Main\X${}\E{}$\6
\&{int} \\{main}(\,)\1\1\2\2\6
${}\{{}$\1\6
\X14:Variables local to \\{main}\X\6
\X15:Initialize Data Structures\X\6
\\{output\_file}${}\K\\{fopen}(\.{"crc.tab"},\39\.{"w"});{}$\6
\&{for} ${}(\|i\K\T{0};{}$ ${}\|i<\T{32};{}$ ${}\|i\PP){}$\5
${}\{{}$\1\6
\&{for} ${}(\|j\K\T{0};{}$ ${}\|j<\T{8};{}$ ${}\|j\PP){}$\1\5
${}\\{fprintf}(\\{output\_file},\39\.{"0x\%04x,\ "},\39\\{ReductionOfByte}(%
\T{8}*\|i+\|j));{}$\2\6
${}\\{fprintf}(\\{output\_file},\39\.{"\\n"});{}$\6
\4${}\}{}$\2\6
\\{fclose}(\\{output\_file});\6
\\{exit}(\T{0});\6
\&{return} (\T{0});\6
\4${}\}{}$\2\par
\U2.\fi

\M14.
\Y\B\4\X14:Variables local to \\{main}\X${}\E{}$\6
\&{FILE} ${}{*}\\{output\_file};{}$\6
\&{unsigned} \&{int} \|i${},{}$ \|j;\par
\U13.\fi

\M15.
\Y\B\4\X15:Initialize Data Structures\X${}\E{}$\6
${}\\{CRC\_Ptr}\K{}$(\&{Poly} ${}{*}){}$ \\{malloc}(\&{sizeof}(\&{Poly}));\6
\&{if} ${}(\\{CRC\_Ptr}\E\NULL){}$\1\5
\X12:Complain about malloc\X\6
\\{ConvertIntToPoly}${}(\.{CRC\_INT},\39\\{CRC\_Ptr}){}$;\2\par

\U13.\fi


\inx
\I\.{\_\_GNUC\_\_}, 6.
\I\.{\_\_STDC\_\_}, 6.
\I\.{\_\_TURBOC\_\_}, 6.
\I\.{ARGS}, \[6].
\I\\{ConvertIntToPoly}, 6, \[9], 15.
\I\.{CRC\_INT}, \[4], 15.
\I\\{CRC\_Ptr}, \[5], 10, 15.
\I\\{defined}, 6.
\I\\{exit}, 13.
\I\|{f}, \[8].
\I\\{fclose}, 13.
\I\&{Field}, \[3], 6, 7.
\I\\{fopen}, 13.
\I\\{FPlus}, 6, \[7], 8.
\I\\{fprintf}, 12, 13.
\I\|{i}, \[8], \[9], \[10], \[14].
\I\\{Int}, \[6], \[9].
\I\|{j}, \[8], \[14].
\I\&{LongPoly}, \[3], 6, 8, 10, 11.
\I\\{main}, 6, \[13].
\I\\{malloc}, 11, 15.
\I\.{MSDOS}, 6.
\I\\{output\_file}, 13, \[14].
\I\\{plist}, 6.
\I\\{pls}, \[10], 11.
\I\&{Poly}, \[3], 5, 6, 8, 9, 10, 11, 15.
\I\&{polyPtr}, \[3], 6, 9.
\I\\{pt}, \[10], 11.
\I\\{Ptr}, \[6], \[9].
\I\\{ReduceLongPoly}, 6, \[8], 10.
\I\\{ReductionOfByte}, 6, \[10], 13.
\I\|{s}, \[6], \[7], \[8].
\I\.{SIZE}, \[3], 8, 9, 10.
\I\\{stderr}, 12.
\I\|{t}, \[6], \[7], \[8].
\I\.{THINK\_C}, 6.
\I\|{u}, \[6], \[8], \[10].
\I\|{x}, \[6], \[10].
\fin
\I\X7, 8, 9, 10:All functions\X
\U2.
\I\X11:Assign space for the structures that our pointers point to\X
\U10.
\I\X12:Complain about malloc\X
\Us11\ET15.
\I\X4:Global constants\X
\U2.
\I\X3:Global typedefs\X
\U2.
\I\X5:Global variables\X
\U2.
\I\X6:Global \&{include}s\X
\U2.
\I\X15:Initialize Data Structures\X
\U13.
\I\X13:Main\X
\U2.
\I\X14:Variables local to \\{main}\X
\U13.
\con
