# This is a shell archive. Save it in a file, remove anything before
# this line, and then unpack it by entering "sh file". Note, it may
# create directories; files and directories will be owned by you and
# have default permissions.
#
# This archive contains:
#
# gf_div.c
# gf_mult.c
# gflib.c
# parity_test.c
# rs_decode_file.c
# rs_encode_file.c
# xor.c
# gflib.h
# makefile
# LICENSE
#
echo x - gf_div.c
sed 's/^X//' >gf_div.c << 'END-of-gf_div.c'
X/*
XProcedures and Programs for Galois-Field Arithmetic and Reed-Solomon Coding.
XCopyright (C) 2003 James S. Plank
X
XThis library is free software; you can redistribute it and/or
Xmodify it under the terms of the GNU Lesser General Public
XLicense as published by the Free Software Foundation; either
Xversion 2.1 of the License, or (at your option) any later version.
X
XThis library is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
XLesser General Public License for more details.
X
XYou should have received a copy of the GNU Lesser General Public
XLicense along with this library; if not, write to the Free Software
XFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
X
X---------------------------------------------------------------------------
XPlease see http://web.eecs.utk.edu/~jplank/plank/gflib
Xfor instruction on how to use this library.
X
XJim Plank
Xplank@cs.utk.edu
Xhttp://web.eecs.utk.edu/~jplank
X
XAssociate Professor
XDepartment of Computer Science
XUniversity of Tennessee
X203 Claxton Complex
X1122 Volunteer Blvd.
XKnoxville, TN 37996-3450
X
X 865-974-4397
XFax: 865-974-4404
X
X$Revision: 1.1 $
X*/
X
X#include
X#include "gflib.h"
X#include
X
X
Xmain(int argc, char **argv)
X{
X int i, size, iterations, check, factor, inv_f, j;
X int x, y;
X struct timeval tv1, tv2;
X struct timezone tz1, tz2;
X
X if (argc != 3) {
X fprintf(stderr, "usage: gf_div x y\n");
X exit(1);
X }
X
X x = atoi(argv[1]);
X y = atoi(argv[2]);
X
X printf("%d\n", gf_single_divide(x, y));
X}
X
END-of-gf_div.c
echo x - gf_mult.c
sed 's/^X//' >gf_mult.c << 'END-of-gf_mult.c'
X/*
XProcedures and Programs for Galois-Field Arithmetic and Reed-Solomon Coding.
XCopyright (C) 2003 James S. Plank
X
XThis library is free software; you can redistribute it and/or
Xmodify it under the terms of the GNU Lesser General Public
XLicense as published by the Free Software Foundation; either
Xversion 2.1 of the License, or (at your option) any later version.
X
XThis library is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
XLesser General Public License for more details.
X
XYou should have received a copy of the GNU Lesser General Public
XLicense along with this library; if not, write to the Free Software
XFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
X
X---------------------------------------------------------------------------
XPlease see http://web.eecs.utk.edu/~jplank/plank/gflib
Xfor instruction on how to use this library.
X
XJim Plank
Xplank@cs.utk.edu
Xhttp://web.eecs.utk.edu/~jplank
X
XAssociate Professor
XDepartment of Computer Science
XUniversity of Tennessee
X203 Claxton Complex
X1122 Volunteer Blvd.
XKnoxville, TN 37996-3450
X
X 865-974-4397
XFax: 865-974-4404
X
X$Revision: 1.1 $
X*/
X
X#include
X#include "gflib.h"
X#include
X
X
Xmain(int argc, char **argv)
X{
X int i, size, iterations, check, factor, inv_f, j;
X int x, y;
X struct timeval tv1, tv2;
X struct timezone tz1, tz2;
X
X if (argc != 3) {
X fprintf(stderr, "usage: gf_mult x y\n");
X exit(1);
X }
X
X x = atoi(argv[1]);
X y = atoi(argv[2]);
X
X printf("%d\n", gf_single_multiply(x, y));
X}
X
END-of-gf_mult.c
echo x - gflib.c
sed 's/^X//' >gflib.c << 'END-of-gflib.c'
X/*
XProcedures and Programs for Galois-Field Arithmetic and Reed-Solomon Coding.
XCopyright (C) 2003 James S. Plank
X
XThis library is free software; you can redistribute it and/or
Xmodify it under the terms of the GNU Lesser General Public
XLicense as published by the Free Software Foundation; either
Xversion 2.1 of the License, or (at your option) any later version.
X
XThis library is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
XLesser General Public License for more details.
X
XYou should have received a copy of the GNU Lesser General Public
XLicense along with this library; if not, write to the Free Software
XFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
X
X---------------------------------------------------------------------------
XPlease see http://web.eecs.utk.edu/~jplank/plank/gflib
Xfor instruction on how to use this library.
X
XJim Plank
Xplank@cs.utk.edu
Xhttp://web.eecs.utk.edu/~jplank
X
XAssociate Professor
XDepartment of Computer Science
XUniversity of Tennessee
X203 Claxton Complex
X1122 Volunteer Blvd.
XKnoxville, TN 37996-3450
X
X 865-974-4397
XFax: 865-974-4404
X
X$Revision: 1.1 $
X*/
X
X
X#include
X#include
X#include "gflib.h"
X
X#define prim_poly_32 020000007
X#define prim_poly_16 0210013
X#define prim_poly_8 0435
X#define prim_poly_4 023
X#define prim_poly_2 07
X
Xstatic int gf_already_setup = 0;
X
X#ifdef W_8
X static int Modar_w = 8;
X static int Modar_nw = 256;
X static int Modar_nwm1 = 255;
X static int Modar_poly = prim_poly_8;
X#elif W_16
X static int Modar_w = 16;
X static int Modar_nw = 65536;
X static int Modar_nwm1 = 65535;
X static int Modar_poly = prim_poly_16;
X#endif
X
Xstatic int *B_TO_J;
Xstatic int *J_TO_B;
Xstatic int Modar_M;
Xstatic int Modar_N;
Xstatic int Modar_Iam;
X
Xint gf_single_multiply(int xxx, int yyy)
X{
X unsigned int sum_j;
X unit zzz;
X
X gf_modar_setup();
X if (xxx == 0 || yyy == 0) {
X zzz = 0;
X } else {
X sum_j = (int) (B_TO_J[xxx] + (int) B_TO_J[yyy]);
X#ifdef W_16
X if (sum_j >= Modar_nwm1) sum_j -= Modar_nwm1;
X#endif
X zzz = J_TO_B[sum_j];
X }
X return zzz;
X}
X
Xint gf_single_divide(int a, int b)
X{
X int sum_j;
X
X gf_modar_setup();
X if (b == 0) return -1;
X if (a == 0) return 0;
X sum_j = B_TO_J[a] - B_TO_J[b];
X#ifdef W_16
X if (sum_j < 0) sum_j += Modar_nwm1;
X#endif
X return (int) J_TO_B[sum_j];
X}
X
X
Xvoid gf_mult_region(void *region, int size, int factor)
X{
X int sum_j;
X int flog;
X unit *r;
X int sz;
X int r_cache;
X
X gf_modar_setup();
X
X if (factor == 1) return;
X if (factor == 0) {
X (void) memset(region, 0, size);
X return;
X }
X
X flog = B_TO_J[factor];
X sz = size / sizeof(unit);
X r = ((unit *) region) + sz;
X
X while (r != region) {
X r--;
X r_cache = *r;
X if (r_cache != 0) {
X sum_j = (int) (B_TO_J[r_cache] + flog);
X#ifdef W_16
X if (sum_j >= Modar_nwm1) sum_j -= Modar_nwm1;
X#endif
X *r = J_TO_B[sum_j];
X }
X }
X}
X
Xvoid gf_modar_setup()
X{
X int j, b, t;
X if (gf_already_setup) return;
X
X B_TO_J = (int *) malloc(sizeof(int)*Modar_nw);
X if (B_TO_J == NULL) {
X perror("gf_modar_setup, malloc B_TO_J");
X exit(1);
X }
X /* When the word size is 8 bits, make three copies of the table so that
X you don't have to do the extra addition or subtraction in the
X multiplication/division routines */
X
X#ifdef W_8
X J_TO_B = (int *) malloc(sizeof(int)*Modar_nw*3);
X#elif W_16
X J_TO_B = (int *) malloc(sizeof(int)*Modar_nw);
X#endif
X if (J_TO_B == NULL) {
X perror("gf_modar_setup, malloc J_TO_B");
X exit(1);
X }
X for (j = 0; j < Modar_nw; j++) {
X B_TO_J[j] = Modar_nwm1;
X J_TO_B[j] = 0;
X }
X
X b = 1;
X for (j = 0; j < Modar_nwm1; j++) {
X if (B_TO_J[b] != Modar_nwm1) {
X fprintf(stderr, "Error: j=%d, b=%d, B->J[b]=%d, J->B[j]=%d (0%o)\n",
X j, b, B_TO_J[b], J_TO_B[j], (b << 1) ^ Modar_poly);
X exit(1);
X }
X B_TO_J[b] = j;
X J_TO_B[j] = b;
X b = b << 1;
X if (b & Modar_nw) b = (b ^ Modar_poly) & Modar_nwm1;
X }
X/* for (j = 0; j < Modar_nw; j++) { */
X/* printf("%3d b->j %3d %3d j->b %3d\n", */
X/* j, B_TO_J[j], j, J_TO_B[j]; */
X/* } */
X
X#ifdef W_8
X for (j = 0; j < Modar_nwm1; j++) {
X J_TO_B[j+Modar_nwm1] = J_TO_B[j];
X J_TO_B[j+2*Modar_nwm1] = J_TO_B[j];
X }
X J_TO_B += Modar_nwm1;
X#endif
X gf_already_setup = 1;
X
X}
X
X
Xvoid gf_fast_add_parity(void *to_add, void *to_modify, int size)
X{
X unsigned long *p, *t;
X int j;
X
X j = size/sizeof(unsigned long);
X t = (unsigned long *) to_add;
X p = (unsigned long *) to_modify;
X p += j;
X t += j;
X while(t != (unsigned long *) to_add) {
X p--;
X t--;
X *p = *p ^ *t;
X }
X}
X
Xvoid gf_add_parity(void *to_add, void *to_modify, int size)
X{
X unsigned long ta, tm;
X unsigned char *cta, *ctm;
X int sml;
X
X if (size <= 0) return;
X
X ta = (unsigned long) to_add % sizeof(unsigned long);
X tm = (unsigned long) to_modify% sizeof(unsigned long);
X if (ta != tm) {
X fprintf(stderr, "Error: gf_add_parity: to_add and to_modify are not aligned\n");
X exit(1);
X }
X
X cta = (unsigned char *) to_add;
X ctm = (unsigned char *) to_modify;
X
X /* Align to long boundary */
X if (ta != 0) {
X while (ta != sizeof(unsigned long) && size > 0) {
X *ctm = *ctm ^ *cta;
X ctm++;
X cta++;
X size--;
X ta++;
X }
X }
X
X if (size == 0) return;
X
X /* Call gf_fast_add_parity to do it fast */
X
X sml = size / sizeof(unsigned long);
X if (sml > 0) gf_fast_add_parity(cta, ctm, size);
X size -= sml * sizeof(unsigned long);
X
X if (size == 0) return;
X
X /* Do the last few bytes if they are unalighed */
X cta += sml * sizeof(unsigned long);
X ctm += sml * sizeof(unsigned long);
X while (size > 0) {
X *ctm = *ctm ^ *cta;
X ctm++;
X cta++;
X size--;
X }
X}
X
Xint gf_log(int value)
X{
X return B_TO_J[value];
X}
X
X/* This returns the rows*cols vandermonde matrix. N+M must be
X < 2^w -1. Row 0 is in elements 0 to cols-1. Row one is
X in elements cols to 2cols-1. Etc.*/
X
Xint *gf_make_vandermonde(int rows, int cols)
X{
X int *vdm, i, j, k;
X void gf_modar_setup();
X
X if (rows >= Modar_nwm1 || cols >= Modar_nwm1) {
X fprintf(stderr, "Error: gf_make_vandermonde: %d + %d >= %d\n",
X rows, cols, Modar_nwm1);
X exit(1);
X }
X
X vdm = (int *) malloc(sizeof(int) * rows * cols);
X if (vdm == NULL) {
X perror("Malloc: Vandermonde matrix");
X exit(1);
X }
X for (i = 0; i < rows; i++) {
X k = 1;
X for (j = 0; j < cols; j++) {
X vdm[i*cols+j] = k;
X k = gf_single_multiply(k, i);
X }
X }
X return vdm;
X}
X
Xstatic int find_swap_row(int *matrix, int rows, int cols, int row_num)
X{
X int j;
X
X for (j = row_num; j < rows; j++) {
X if (matrix[j*cols+row_num] != 0) return j;
X }
X return -1;
X}
X
Xvoid gf_fprint_matrix(FILE *f, int *matrix, int rows, int cols)
X{
X int i, j;
X for (i = 0; i < rows; i++) {
X for (j = 0; j < cols; j++) {
X fprintf(f, "%4d", matrix[i*cols+j]);
X }
X fprintf(f, "\n");
X }
X}
X
Xint *gf_make_dispersal_matrix(int rows, int cols)
X{
X int *vdm, i, j, k, l, inv, tmp, colindex;
X
X vdm = gf_make_vandermonde(rows, cols);
X
X for (i = 0; i < cols && i < rows; i++) {
X j = find_swap_row(vdm, rows, cols, i);
X if (j == -1) {
X fprintf(stderr, "Error: make_dispersal_matrix. Can't find swap row %d\n",
X i);
X exit(1);
X }
X
X/* printf("\nSwap row: %d\n\n", j);
X print_matrix(vdm, rows, cols); */
X
X if (j != i) {
X for (k = 0; k < cols; k++) {
X tmp = vdm[j*cols+k];
X vdm[j*cols+k] = vdm[i*cols+k];
X vdm[i*cols+k] = tmp;
X }
X }
X if (vdm[i*cols+i] == 0) {
X fprintf(stderr, "Internal error -- this shouldn't happen\n");
X exit(1);
X }
X
X/* printf("\nAfter Swap: %d\n\n", j);
X print_matrix(vdm, rows, cols); */
X
X if (vdm[i*cols+i] != 1) {
X inv = gf_single_divide(1, vdm[i*cols+i]);
X k = i;
X for (j = 0; j < rows; j++) {
X vdm[k] = gf_single_multiply(inv, vdm[k]);
X k += cols;
X }
X/* printf("\nAfter multiplying column by : %d\n\n", inv);
X print_matrix(vdm, rows, cols); */
X
X }
X if (vdm[i*cols+i] != 1) {
X fprintf(stderr, "Internal error -- this shouldn't happen #2)\n");
X exit(1);
X }
X
X for (j = 0; j < cols; j++) {
X colindex = vdm[i*cols+j];
X if (j != i && colindex != 0) {
X k = j;
X for (l = 0; l < rows; l++) {
X vdm[k] = vdm[k] ^ gf_single_multiply(colindex, vdm[l*cols+i]);
X k += cols;
X }
X }
X }
X
X/* printf("\nAfter Messing with other columns\n\n", inv);
X print_matrix(vdm, rows, cols); */
X
X }
X
X return vdm;
X}
X
Xextern Condensed_Matrix *gf_condense_dispersal_matrix(
X int *disp, int *existing_rows, int rows, int cols)
X{
X Condensed_Matrix *cm;
X int *m;
X int *id;
X int i, j, k, tmp;
X
X /* Allocate cm and initialize */
X cm = (Condensed_Matrix *) malloc(sizeof(Condensed_Matrix));
X if (cm == NULL) { perror("gf_condense_dispersal_matrix - Condensed_Matrix"); exit(1); }
X cm->condensed_matrix = (int *) malloc(sizeof(int)*cols*cols);
X if (cm->condensed_matrix == NULL) {
X perror("gf_condense_dispersal_matrix - cm->condensed_matrix");
X exit(1);
X }
X cm->row_identities = (int *) malloc(sizeof(int)*cols);
X if (cm->row_identities == NULL) {
X perror("gf_condense_dispersal_matrix - cm->row_identities");
X exit(1);
X }
X m = cm->condensed_matrix;
X id = cm->row_identities;
X for (i = 0; i < cols; i++) id[i] = -1;
X
X /* First put identity rows in their proper places */
X
X for (i = 0; i < cols; i++) {
X if (existing_rows[i] != 0) {
X id[i] = i;
X tmp = cols*i;
X for (j = 0; j < cols; j++) m[tmp+j] = disp[tmp+j];
X }
X }
X
X /* Next, put coding rows in */
X k = 0;
X for (i = cols; i < rows; i++) {
X if (existing_rows[i] != 0) {
X while(k < cols && id[k] != -1) k++;
X if (k == cols) return cm;
X id[k] = i;
X for (j = 0; j < cols; j++) m[cols*k+j] = disp[cols*i+j];
X }
X }
X
X /* If we're here, there are no more coding rows -- check to see that the
X condensed dispersal matrix is full -- otherwise, it's not -- return an
X error */
X
X while(k < cols && id[k] != -1) k++;
X if (k == cols) return cm;
X
X free(id);
X free(m);
X free(cm);
X return NULL;
X}
X
Xstatic pic(int *inv, int *copy, int rows, char *s)
X{
X printf("\n%s\n\n", s);
X gf_fprint_matrix(stdout, inv, rows, rows);
X printf("\n");
X gf_fprint_matrix(stdout, copy, rows, rows);
X}
X
Xint *gf_invert_matrix(int *mat, int rows)
X{
X int *inv;
X int *copy;
X int cols, i, j, k, x, rs2;
X int row_start, tmp, inverse;
X
X cols = rows;
X
X inv = (int *) malloc(sizeof(int)*rows*cols);
X if (inv == NULL) { perror("gf_invert_matrix - inv"); exit(1); }
X copy = (int *) malloc(sizeof(int)*rows*cols);
X if (copy == NULL) { perror("gf_invert_matrix - copy"); exit(1); }
X
X k = 0;
X for (i = 0; i < rows; i++) {
X for (j = 0; j < cols; j++) {
X inv[k] = (i == j) ? 1 : 0;
X copy[k] = mat[k];
X k++;
X }
X }
X
X /* pic(inv, copy, rows, "Start"); */
X
X /* First -- convert into upper triangular */
X for (i = 0; i < cols; i++) {
X row_start = cols*i;
X
X /* Swap rows if we ave a zero i,i element. If we can't swap, then the
X matrix was not invertible */
X
X if (copy[row_start+i] == 0) {
X for (j = i+1; j < rows && copy[cols*j+i] == 0; j++) ;
X if (j == rows) {
X fprintf(stderr, "gf_invert_matrix: Matrix not invertible!!\n");
X exit(1);
X }
X rs2 = j*cols;
X for (k = 0; k < cols; k++) {
X tmp = copy[row_start+k];
X copy[row_start+k] = copy[rs2+k];
X copy[rs2+k] = tmp;
X tmp = inv[row_start+k];
X inv[row_start+k] = inv[rs2+k];
X inv[rs2+k] = tmp;
X }
X }
X
X /* Multiply the row by 1/element i,i */
X tmp = copy[row_start+i];
X if (tmp != 1) {
X inverse = gf_single_divide(1, tmp);
X for (j = 0; j < cols; j++) {
X copy[row_start+j] = gf_single_multiply(copy[row_start+j], inverse);
X inv[row_start+j] = gf_single_multiply(inv[row_start+j], inverse);
X }
X /* pic(inv, copy, rows, "Divided through"); */
X }
X
X /* Now for each j>i, add A_ji*Ai to Aj */
X k = row_start+i;
X for (j = i+1; j != cols; j++) {
X k += cols;
X if (copy[k] != 0) {
X if (copy[k] == 1) {
X rs2 = cols*j;
X for (x = 0; x < cols; x++) {
X copy[rs2+x] ^= copy[row_start+x];
X inv[rs2+x] ^= inv[row_start+x];
X }
X } else {
X tmp = copy[k];
X rs2 = cols*j;
X for (x = 0; x < cols; x++) {
X copy[rs2+x] ^= gf_single_multiply(tmp, copy[row_start+x]);
X inv[rs2+x] ^= gf_single_multiply(tmp, inv[row_start+x]);
X }
X }
X }
X }
X /* pic(inv, copy, rows, "Eliminated rows"); */
X }
X
X /* Now the matrix is upper triangular. Start at the top and multiply down */
X
X for (i = rows-1; i >= 0; i--) {
X row_start = i*cols;
X for (j = 0; j < i; j++) {
X rs2 = j*cols;
X if (copy[rs2+i] != 0) {
X tmp = copy[rs2+i];
X copy[rs2+i] = 0;
X for (k = 0; k < cols; k++) {
X inv[rs2+k] ^= gf_single_multiply(tmp, inv[row_start+k]);
X }
X }
X }
X /* pic(inv, copy, rows, "One Column"); */
X }
X free(copy);
X return inv;
X}
X
Xint *gf_matrix_multiply(int *a, int *b, int cols)
X{
X int *prod, i, j, k;
X
X prod = (int *) malloc(sizeof(int)*cols*cols);
X if (prod == NULL) { perror("gf_matrix_multiply - prod"); exit(1); }
X
X for (i = 0; i < cols*cols; i++) prod[i] = 0;
X
X for (i = 0; i < cols; i++) {
X for (j = 0; j < cols; j++) {
X for (k = 0; k < cols; k++) {
X prod[i*cols+j] ^= gf_single_multiply(a[i*cols+k], b[k*cols+j]);
X }
X }
X }
X return prod;
X}
X
Xvoid gf_write_matrix(FILE *f, int *a, int rows, int cols)
X{
X int i;
X fprintf(f, "%d\n%d\n", rows, cols);
X for (i = 0; i < rows*cols; i++) fprintf(f, "%d\n", a[i]);
X}
X
Xint *gf_read_matrix(FILE *f, int *rows, int *cols)
X{
X int i, r, c, *a;
X
X if (fscanf(f, "%d", &r) == 0) {
X fprintf(stderr, "ERROR reading file -- rows\n");
X exit(1);
X }
X if (fscanf(f, "%d", &c) == 0) {
X fprintf(stderr, "ERROR reading file -- cols\n");
X exit(1);
X }
X a = (int *) malloc(sizeof(int)*r*c);
X if (a == NULL) { perror("gf_read_matrix: malloc"); exit(1); }
X
X for (i = 0; i < r*c; i++) {
X if (fscanf(f, "%d", a+i) == 0) {
X fprintf(stderr, "ERROR reading file -- element %d\n", i);
X exit(1);
X }
X }
X *rows = r;
X *cols = c;
X return a;
X}
END-of-gflib.c
echo x - parity_test.c
sed 's/^X//' >parity_test.c << 'END-of-parity_test.c'
X/*
XProcedures and Programs for Galois-Field Arithmetic and Reed-Solomon Coding.
XCopyright (C) 2003 James S. Plank
X
XThis library is free software; you can redistribute it and/or
Xmodify it under the terms of the GNU Lesser General Public
XLicense as published by the Free Software Foundation; either
Xversion 2.1 of the License, or (at your option) any later version.
X
XThis library is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
XLesser General Public License for more details.
X
XYou should have received a copy of the GNU Lesser General Public
XLicense along with this library; if not, write to the Free Software
XFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
X
X---------------------------------------------------------------------------
XPlease see http://web.eecs.utk.edu/~jplank/plank/gflib
Xfor instruction on how to use this library.
X
XJim Plank
Xplank@cs.utk.edu
Xhttp://web.eecs.utk.edu/~jplank
X
XAssociate Professor
XDepartment of Computer Science
XUniversity of Tennessee
X203 Claxton Complex
X1122 Volunteer Blvd.
XKnoxville, TN 37996-3450
X
X 865-974-4397
XFax: 865-974-4404
X
X$Revision: 1.1 $
X*/
X
X
X#include
X#include "gflib.h"
X#include
X
X
Xmain(int argc, char **argv)
X{
X char *y;
X char *x;
X char *z;
X int i, size, iterations, check_end;
X struct timeval tv1, tv2;
X struct timezone tz1, tz2;
X
X if (argc != 4) {
X fprintf(stderr, "usage: parity_test buffer-size iterations check-at-end(Y/N)\n");
X exit(1);
X }
X
X size = atoi(argv[1]);
X iterations = atoi(argv[2]);
X check_end = (argv[3][0] == 'Y' || argv[3][0] == 'y');
X
X srand48();
X
X y = (char *) malloc(size);
X x = (char *) malloc(size);
X z = (char *) malloc(size);
X
X for (i = 0; i < size; i++) {
X y[i] = lrand48()%256;
X x[i] = lrand48()%256;
X z[i] = y[i];
X }
X
X gettimeofday(&tv1, &tz1);
X for (i = 0; i < iterations; i++) {
X gf_add_parity(x, y, size);
X }
X gettimeofday(&tv2, &tz2);
X
X tv2.tv_sec -= tv1.tv_sec;
X tv2.tv_usec -= tv1.tv_usec;
X if (tv2.tv_usec < 0) {
X tv2.tv_sec--;
X tv2.tv_usec += 1000000;
X }
X printf("%6d.%06d\n", tv2.tv_sec, tv2.tv_usec);
X if (check_end) {
X for (i = 0; i < size; i++) {
X if (z[i] != y[i]) printf("Error in byte %d\n", i);
X }
X }
X
X}
X
END-of-parity_test.c
echo x - rs_decode_file.c
sed 's/^X//' >rs_decode_file.c << 'END-of-rs_decode_file.c'
X/*
XProcedures and Programs for Galois-Field Arithmetic and Reed-Solomon Coding.
XCopyright (C) 2003 James S. Plank
X
XThis library is free software; you can redistribute it and/or
Xmodify it under the terms of the GNU Lesser General Public
XLicense as published by the Free Software Foundation; either
Xversion 2.1 of the License, or (at your option) any later version.
X
XThis library is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
XLesser General Public License for more details.
X
XYou should have received a copy of the GNU Lesser General Public
XLicense along with this library; if not, write to the Free Software
XFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
X
X---------------------------------------------------------------------------
XPlease see http://web.eecs.utk.edu/~jplank/plank/gflib
Xfor instruction on how to use this library.
X
XJim Plank
Xplank@cs.utk.edu
Xhttp://web.eecs.utk.edu/~jplank
X
XAssociate Professor
XDepartment of Computer Science
XUniversity of Tennessee
X203 Claxton Complex
X1122 Volunteer Blvd.
XKnoxville, TN 37996-3450
X
X 865-974-4397
XFax: 865-974-4404
X
X$Revision: 1.1 $
X*/
X
X
X#include
X#include "gflib.h"
X#include
X#include
X#include
X
X/* This one is going to be in-core */
X
Xmain(int argc, char **argv)
X{
X int i, j, k, *vdm, *inv, *prod, cache_size;
X int rows, cols, blocksize, orig_size;
X int n, m, sz, *factors, tmp, factor, *exists, *map;
X char *stem, *filename;
X char **buffer, *buf_file, *block;
X struct stat buf;
X Condensed_Matrix *cm;
X int *mat, *id;
X FILE *f;
X
X if (argc != 2) {
X fprintf(stderr, "usage: rs_decode_file stem\n");
X exit(1);
X }
X
X stem = argv[1];
X buf_file = (char *) malloc(sizeof(char)*(strlen(stem)+30));
X if (buf_file == NULL) { perror("malloc - buf_file"); exit(1); }
X sprintf(buf_file, "%s-info.txt", stem, i);
X f = fopen(buf_file, "r");
X if (f == NULL) { perror(buf_file); exit(1); }
X if (fscanf(f, "%d\n", &orig_size) != 1) { fprintf(stderr, "Error reading info file 1\n"); exit(1); }
X if (fscanf(f, "%d\n", &sz) != 1) { fprintf(stderr, "Error reading info file 2\n"); exit(1); }
X if (fscanf(f, "%d\n", &blocksize) != 1) { fprintf(stderr, "Error reading info file 3\n"); exit(1); }
X if (fscanf(f, "%d\n", &n) != 1) { fprintf(stderr, "Error reading info file 4\n"); exit(1); }
X if (fscanf(f, "%d\n", &m) != 1) { fprintf(stderr, "Error reading info file 5\n"); exit(1); }
X vdm = gf_read_matrix(f, &rows, &cols);
X if (vdm == NULL) { fprintf(stderr, "Error reading info file matrix\n"); exit(1); }
X fclose(f);
X
X if (rows != n+m) {
X fprintf(stderr, "Error in %s - rows != n+m\n", buf_file);
X exit(1);
X }
X if (cols != n) {
X fprintf(stderr, "Error in %s - cols != n\n", buf_file);
X exit(1);
X }
X
X exists = (int *) malloc(sizeof(int) * rows);
X if (exists == NULL) { perror("malloc - exists"); exit(1); }
X factors = (int *) malloc(sizeof(int) * rows);
X if (factors == NULL) { perror("malloc - factors"); exit(1); }
X map = (int *) malloc(sizeof(int) * rows);
X if (map == NULL) { perror("malloc - map"); exit(1); }
X
X buffer = (char **) malloc(sizeof(char *)*n);
X for (i = 0; i < n; i++) {
X buffer[i] = (char *) malloc(blocksize);
X if (buffer[i] == NULL) {
X perror("Allocating buffer to store the whole file");
X exit(1);
X }
X }
X
X j = 0;
X for (i = 0; i < rows && j < cols; i++) {
X sprintf(buf_file, "%s-%04d.rs", stem, i);
X if (stat(buf_file, &buf) != 0) {
X map[i] = -1;
X } else {
X if (buf.st_size != blocksize) {
X map[i] = -1;
X } else {
X map[i] = j++;
X f = fopen(buf_file, "r");
X if (f == NULL) { perror(buf_file); exit(1); }
X k = fread(buffer[map[i]], 1, blocksize, f);
X if (k != blocksize) {
X fprintf(stderr, "%s -- stat says %d bytes, but only read %d\n",
X buf_file, buf.st_size, k);
X exit(1);
X }
X }
X }
X }
X
X if (j < cols) {
X fprintf(stderr, "Only %d fragments -- need %d. Sorry\n", j, cols);
X exit(1);
X }
X
X j = 0;
X for (i = 0; i < cols; i++) if (map[i] == -1) j++;
X fprintf(stderr, "Blocks to decode: %d\n", j);
X if (j == 0) {
X cache_size = orig_size;
X for (i = 0; i < cols; i++) {
X if (cache_size > 0) {
X fwrite(buffer[i], 1, (cache_size > blocksize) ? blocksize : cache_size, stdout);
X cache_size -= blocksize;
X }
X }
X exit(0);
X }
X
X block = (char *) malloc(sizeof(char)*blocksize);
X if (block == NULL) { perror("malloc - block"); exit(1); }
X
X for (i = 0; i < rows; i++) exists[i] = (map[i] != -1);
X cm = gf_condense_dispersal_matrix(vdm, exists, rows, cols);
X mat = cm->condensed_matrix;
X id = cm->row_identities;
X /* Fix it so that map[i] for i = 0 to cols-1 is defined correctly.
X map[i] is the index of buffer[] that holds the blocks for row i in
X the condensed matrix */
X
X for (i = 0; i < cols; i++) {
X if (map[i] == -1) map[i] = map[id[i]];
X }
X
X fprintf(stderr, "Inverting condensed dispersal matrix ... "); fflush(stderr);
X inv = gf_invert_matrix(mat, cols);
X if (inv == NULL) {
X fprintf(stderr, "\n\nError -- matrix unvertible\n");
X exit(1);
X }
X fprintf(stderr, "Done\n"); fflush(stderr);
X
X fprintf(stderr, "\nCondensed matrix:\n\n");
X gf_fprint_matrix(stderr, mat, cols, cols);
X
X fprintf(stderr, "\nInverted matrix:\n\n");
X gf_fprint_matrix(stderr, inv, cols, cols);
X
X for(i = 0; i < rows; i++) factors[i] = 1;
X
X cache_size = orig_size;
X for (i = 0; i < cols && cache_size > 0; i++) {
X if (id[i] < cols) {
X fprintf(stderr, "Writing block %d from memory ... ", i); fflush(stderr);
X if (factors[i] != 1) {
X tmp = gf_single_divide(1, factors[i]);
X/* fprintf(stderr, "Factor = %3d. Tmp = %3d. Before[0] = %3d. ",
X factors[i], tmp, (unsigned char) buffer[map[i]][0]); */
X factors[i] = 1;
X gf_mult_region(buffer[map[i]], blocksize, tmp);
X/* fprintf(stderr, "After[0] = %3d.\n", (unsigned char) buffer[map[i]][0]); */
X } else {
X/* fprintf(stderr, "Factor = %3d. Buffer[0] = %3d.\b", factors[i],
X (unsigned char) buffer[map[i]][0]); */
X }
X fwrite(buffer[map[i]], 1, (cache_size > blocksize) ? blocksize : cache_size, stdout);
X cache_size -= blocksize;
X fprintf(stderr, "Done\n"); fflush(stderr);
X } else {
X fprintf(stderr, "Decoding block %d ... ", i); fflush(stderr);
X memset(block, 0, blocksize);
X for (j = 0; j < cols; j++) {
X tmp = inv[i*cols+j];
X factor = gf_single_divide(tmp, factors[j]);
X/* fprintf(stderr, "Factors[%d] = %3d. Tmp = %3d. Factor = %3d\n Before[j][0] = %3d. ",
X j, factors[j], tmp, factor, (unsigned char) buffer[map[j]][0]); */
X factors[j] = tmp;
X gf_mult_region(buffer[map[j]], blocksize, factor);
X/* fprintf(stderr, "After[j][0] = %3d. ", (unsigned char) buffer[map[j]][0]);
X fprintf(stderr, "Before-block[0] = %3d. ", (unsigned char) block[0]); */
X gf_add_parity(buffer[map[j]], block, blocksize);
X/* fprintf(stderr, "After-block[0] = %3d.\n", (unsigned char) block[0]); */
X }
X fprintf(stderr, "writing ... "); fflush(stderr);
X fwrite(block, 1, (cache_size > blocksize) ? blocksize : cache_size, stdout);
X cache_size -= blocksize;
X fprintf(stderr, "Done\n"); fflush(stderr);
X }
X }
X}
END-of-rs_decode_file.c
echo x - rs_encode_file.c
sed 's/^X//' >rs_encode_file.c << 'END-of-rs_encode_file.c'
X/*
XProcedures and Programs for Galois-Field Arithmetic and Reed-Solomon Coding.
XCopyright (C) 2003 James S. Plank
X
XThis library is free software; you can redistribute it and/or
Xmodify it under the terms of the GNU Lesser General Public
XLicense as published by the Free Software Foundation; either
Xversion 2.1 of the License, or (at your option) any later version.
X
XThis library is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
XLesser General Public License for more details.
X
XYou should have received a copy of the GNU Lesser General Public
XLicense along with this library; if not, write to the Free Software
XFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
X
X---------------------------------------------------------------------------
XPlease see http://web.eecs.utk.edu/~jplank/plank/gflib
Xfor instruction on how to use this library.
X
XJim Plank
Xplank@cs.utk.edu
Xhttp://web.eecs.utk.edu/~jplank
X
XAssociate Professor
XDepartment of Computer Science
XUniversity of Tennessee
X203 Claxton Complex
X1122 Volunteer Blvd.
XKnoxville, TN 37996-3450
X
X 865-974-4397
XFax: 865-974-4404
X
X$Revision: 1.1 $
X*/
X
X#include
X#include "gflib.h"
X#include
X#include
X#include
X
X/* This one is going to be in-core */
X
Xmain(int argc, char **argv)
X{
X int i, j, *vdm, *inv, *prod, cache_size;
X int rows, cols, blocksize, orig_size;
X int n, m, sz, *factors, tmp, factor;
X char *stem, *filename;
X char **buffer, *buf_file, *block;
X struct stat buf;
X FILE *f;
X
X if (argc != 5) {
X fprintf(stderr, "usage: rs_encode_file filename n m stem\n");
X exit(1);
X }
X
X n = atoi(argv[2]);
X m = atoi(argv[3]);
X stem = argv[4];
X filename = argv[1];
X
X rows = n+m;
X cols = n;
X
X if (stat(filename, &buf) != 0) {
X perror(filename);
X exit(1);
X }
X
X sz = buf.st_size;
X orig_size = buf.st_size;
X if (sz % (n*sizeof(unit)) != 0) {
X sz += (n*sizeof(unit) - (sz % (n*sizeof(unit))));
X }
X blocksize = sz/n;
X
X buffer = (char **) malloc(sizeof(char *)*n);
X for (i = 0; i < n; i++) {
X buffer[i] = (char *) malloc(blocksize);
X if (buffer[i] == NULL) {
X perror("Allocating buffer to store the whole file");
X exit(1);
X }
X }
X
X f = fopen(filename, "r");
X if (f == NULL) { perror(filename); }
X cache_size = orig_size;
X
X for (i = 0; i < n; i++) {
X if (cache_size < blocksize) memset(buffer[i], 0, blocksize);
X if (cache_size > 0) {
X if (fread(buffer[i], 1, (cache_size > blocksize) ? blocksize : cache_size, f) <= 0) {
X fprintf(stderr, "Couldn't read the right bytes into the buffer\n");
X exit(1);
X }
X }
X cache_size -= blocksize;
X }
X fclose(f);
X
X buf_file = (char *) malloc(sizeof(char)*(strlen(stem)+30));
X if (buf_file == NULL) { perror("malloc - buf_file"); exit(1); }
X block = (char *) malloc(sizeof(char)*blocksize);
X if (block == NULL) { perror("malloc - block"); exit(1); }
X for (i = 0; i < n; i++) {
X sprintf(buf_file, "%s-%04d.rs", stem, i);
X printf("Writing %s ...", buf_file); fflush(stdout);
X f = fopen(buf_file, "w");
X if (f == NULL) { perror(buf_file); exit(1); }
X fwrite(buffer[i], 1, blocksize, f);
X fclose(f);
X printf(" Done\n");
X }
X
X factors = (int *) malloc(sizeof(int)*n);
X if (factors == NULL) { perror("malloc - factors"); exit(1); }
X
X for (i = 0; i < n; i++) factors[i] = 1;
X
X vdm = gf_make_dispersal_matrix(rows, cols);
X
X for (i = cols; i < rows; i++) {
X sprintf(buf_file, "%s-%04d.rs", stem, i);
X printf("Calculating %s ...", buf_file); fflush(stdout);
X memset(block, 0, blocksize);
X for (j = 0; j < cols; j++) {
X tmp = vdm[i*cols+j];
X if (tmp != 0) {
X factor = gf_single_divide(tmp, factors[j]);
X/* printf("M[%02d,%02d] = %3d. Factors[%02d] = %3d. Factor = %3d.\n",
X i, j, tmp, j, factors[j], factor); */
X factors[j] = tmp;
X/* printf(" Block %2d Bef: %3d. ", j, buffer[j][0]); */
X gf_mult_region(buffer[j], blocksize, factor);
X/* printf("Block %2d Aft: %3d. ", j, buffer[j][0]); */
X/* printf("Block %2d Bef: %3d. ", i, block[0]); */
X gf_add_parity(buffer[j], block, blocksize);
X /* printf("Block %2d Aft: %3d.\n", i, block[0]); */
X }
X }
X printf(" writing ...", buf_file); fflush(stdout);
X f = fopen(buf_file, "w");
X if (f == NULL) { perror(buf_file); exit(1); }
X fwrite(block, 1, blocksize, f);
X printf(" Done\n");
X fclose(f);
X }
X
X sprintf(buf_file, "%s-info.txt", stem, i);
X f = fopen(buf_file, "w");
X if (f == NULL) { perror(buf_file); exit(1); }
X fprintf(f, "%d\n", orig_size);
X fprintf(f, "%d\n", sz);
X fprintf(f, "%d\n", blocksize);
X fprintf(f, "%d\n", n);
X fprintf(f, "%d\n", m);
X gf_write_matrix(f, vdm, rows, cols);
X}
END-of-rs_encode_file.c
echo x - xor.c
sed 's/^X//' >xor.c << 'END-of-xor.c'
X/*
XProcedures and Programs for Galois-Field Arithmetic and Reed-Solomon Coding.
XCopyright (C) 2003 James S. Plank
X
XThis library is free software; you can redistribute it and/or
Xmodify it under the terms of the GNU Lesser General Public
XLicense as published by the Free Software Foundation; either
Xversion 2.1 of the License, or (at your option) any later version.
X
XThis library is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
XLesser General Public License for more details.
X
XYou should have received a copy of the GNU Lesser General Public
XLicense along with this library; if not, write to the Free Software
XFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
X
X---------------------------------------------------------------------------
XPlease see http://web.eecs.utk.edu/~jplank/plank/gflib
Xfor instruction on how to use this library.
X
XJim Plank
Xplank@cs.utk.edu
Xhttp://web.eecs.utk.edu/~jplank
X
XAssociate Professor
XDepartment of Computer Science
XUniversity of Tennessee
X203 Claxton Complex
X1122 Volunteer Blvd.
XKnoxville, TN 37996-3450
X
X 865-974-4397
XFax: 865-974-4404
X
X$Revision: 1.1 $
X*/
X
X#include
X
Xmain(argc, argv)
Xint argc;
Xchar **argv;
X{
X int n, m, i;
X
X m = 0;
X for (i = 1; i < argc; i++) {
X n = atoi(argv[i]);
X m = m ^ n;
X }
X printf("%d\n", m);
X}
END-of-xor.c
echo x - gflib.h
sed 's/^X//' >gflib.h << 'END-of-gflib.h'
X/*
XProcedures and Programs for Galois-Field Arithmetic and Reed-Solomon Coding.
XCopyright (C) 2003 James S. Plank
X
XThis library is free software; you can redistribute it and/or
Xmodify it under the terms of the GNU Lesser General Public
XLicense as published by the Free Software Foundation; either
Xversion 2.1 of the License, or (at your option) any later version.
X
XThis library is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
XLesser General Public License for more details.
X
XYou should have received a copy of the GNU Lesser General Public
XLicense along with this library; if not, write to the Free Software
XFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
X
X---------------------------------------------------------------------------
XPlease see http://web.eecs.utk.edu/~jplank/plank/gflib
Xfor instruction on how to use this library.
X
XJim Plank
Xplank@cs.utk.edu
Xhttp://web.eecs.utk.edu/~jplank
X
XAssociate Professor
XDepartment of Computer Science
XUniversity of Tennessee
X203 Claxton Complex
X1122 Volunteer Blvd.
XKnoxville, TN 37996-3450
X
X 865-974-4397
XFax: 865-974-4404
X
X$Revision: 1.1 $
X*/
X
X#include
X
X#ifdef W_8
X typedef unsigned char unit;
X#elif W_16
X typedef unsigned short unit;
X#endif
X
Xtypedef struct {
X int *condensed_matrix; /* The n*n dispersal matrix with rows deleted */
X int *row_identities; /* A nx1 vector of the original row identities of the cond_matrix */
X} Condensed_Matrix;
X
Xextern void gf_modar_setup();
Xextern int gf_single_multiply(int a, int b);
Xextern int gf_single_divide(int a, int b);
Xextern void gf_fprint_matrix(FILE *f, int *m, int rows, int cols);
Xextern void gf_fast_add_parity(void *to_add, void *to_modify, int size);
Xextern void gf_add_parity(void *to_add, void *to_modify, int size);
Xextern void gf_mult_region(void *region, int size, int factor);
Xextern int gf_log(int value);
Xextern int *gf_make_vandermonde(int rows, int cols);
Xextern int *gf_make_dispersal_matrix(int rows, int cols);
Xextern Condensed_Matrix *gf_condense_dispersal_matrix(
X int *disp, /* The rows*cols dispersal matrix */
X int *existing_rows, /* A 0/1 column vector -- 1 if the row still exists */
X int rows,
X int cols);
Xextern int *gf_invert_matrix(int *mat, int rows);
Xextern int *gf_matrix_multiply(int *a, int *b, int rows); /* Must be square */
Xextern void gf_write_matrix(FILE *f, int *a, int rows, int cols);
Xextern int *gf_read_matrix(FILE *f, int *rows, int *cols);
END-of-gflib.h
echo x - makefile
sed 's/^X//' >makefile << 'END-of-makefile'
X# Procedures and Programs for Galois-Field Arithmetic and Reed-Solomon Coding.
X# Copyright (C) 2003 James S. Plank
X#
X# This library is free software; you can redistribute it and/or
X# modify it under the terms of the GNU Lesser General Public
X# License as published by the Free Software Foundation; either
X# version 2.1 of the License, or (at your option) any later version.
X#
X# This library is distributed in the hope that it will be useful,
X# but WITHOUT ANY WARRANTY; without even the implied warranty of
X# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
X# Lesser General Public License for more details.
X#
X# You should have received a copy of the GNU Lesser General Public
X# License along with this library; if not, write to the Free Software
X# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
X#
X# ---------------------------------------------------------------------------
X# Please see http://web.eecs.utk.edu/~jplank/plank/gflib
X# for instruction on how to use this library.
X#
X# Jim Plank
X# plank@cs.utk.edu
X# http://web.eecs.utk.edu/~jplank
X#
X# Associate Professor
X# Department of Computer Science
X# University of Tennessee
X# 203 Claxton Complex
X# 1122 Volunteer Blvd.
X# Knoxville, TN 37996-3450
X#
X# 865-974-4397
X# Fax: 865-974-4404
X#
X# $Revision: 1.1 $
X
XCC = gcc
XCFLAGS = -O
X
XALL = gf_mult gf_div parity_test \
X xor rs_encode_file rs_decode_file
X
Xall:
X @ echo "use one of the following targets: w8, w16"
X
Xw8:
X make "CFLAGS=$(CFLAGS) -DW_8 -DTABLE" $(ALL)
X
Xw16:
X make "CFLAGS=$(CFLAGS) -DW_16 -DTABLE" $(ALL)
X
X# w32:
X# make "CFLAGS=$(CFLAGS) -DW_32 -DXOR_N_SHIFT" gfm gfd
X
X# +mkmake+ -- Everything after this line is automatically generated
X
X
Xclean:
X rm -f core *.o $(ALL) a.out
X
X.SUFFIXES: .c .o
X.c.o:
X $(CC) $(CFLAGS) -c $*.c
X
X
Xgflib.o: gflib.h
X
Xparity_test.o: gflib.h gflib.o
Xparity_test: parity_test.o gflib.o
X $(CC) $(CFLAGS) -o parity_test parity_test.o gflib.o
X
Xcreate_rs_matrix.o: gflib.h gflib.o
Xcreate_rs_matrix: create_rs_matrix.o gflib.o
X $(CC) $(CFLAGS) -o create_rs_matrix create_rs_matrix.o gflib.o
X
Xgf_mult_test.o: gflib.h gflib.o
Xgf_mult_test: gf_mult_test.o gflib.o
X $(CC) $(CFLAGS) -o gf_mult_test gf_mult_test.o gflib.o
X
Xgf_mult.o: gflib.h gflib.o
Xgf_mult: gf_mult.o gflib.o
X $(CC) $(CFLAGS) -o gf_mult gf_mult.o gflib.o
X
X
Xrs_encode_file.o: gflib.h gflib.o
Xrs_encode_file: rs_encode_file.o gflib.o
X $(CC) $(CFLAGS) -o rs_encode_file rs_encode_file.o gflib.o
X
Xrs_decode_file.o: gflib.h gflib.o
Xrs_decode_file: rs_decode_file.o gflib.o
X $(CC) $(CFLAGS) -o rs_decode_file rs_decode_file.o gflib.o
X
Xgf_div.o: gflib.h gflib.o
Xgf_div: gf_div.o gflib.o
X $(CC) $(CFLAGS) -o gf_div gf_div.o gflib.o
X
Xxor: xor.o gflib.o
X $(CC) $(CFLAGS) -o xor xor.o
X
END-of-makefile
echo x - LICENSE
sed 's/^X//' >LICENSE << 'END-of-LICENSE'
XCopyright (C) 1991, 1999 Free Software Foundation, Inc.
X59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
XEveryone is permitted to copy and distribute verbatim copies
Xof this license document, but changing it is not allowed.
X
X[This is the first released version of the Lesser GPL. It also counts
X as the successor of the GNU Library Public License, version 2, hence
X the version number 2.1.]
X
X[9]Preamble
X
X The licenses for most software are designed to take away your freedom
X to share and change it. By contrast, the GNU General Public Licenses
X are intended to guarantee your freedom to share and change free
X software--to make sure the software is free for all its users.
X
X This license, the Lesser General Public License, applies to some
X specially designated software packages--typically libraries--of the
X Free Software Foundation and other authors who decide to use it. You
X can use it too, but we suggest you first think carefully about whether
X this license or the ordinary General Public License is the better
X strategy to use in any particular case, based on the explanations
X below.
X
X When we speak of free software, we are referring to freedom of use,
X not price. Our General Public Licenses are designed to make sure that
X you have the freedom to distribute copies of free software (and charge
X for this service if you wish); that you receive source code or can get
X it if you want it; that you can change the software and use pieces of
X it in new free programs; and that you are informed that you can do
X these things.
X
X To protect your rights, we need to make restrictions that forbid
X distributors to deny you these rights or to ask you to surrender these
X rights. These restrictions translate to certain responsibilities for
X you if you distribute copies of the library or if you modify it.
X
X For example, if you distribute copies of the library, whether gratis
X or for a fee, you must give the recipients all the rights that we gave
X you. You must make sure that they, too, receive or can get the source
X code. If you link other code with the library, you must provide
X complete object files to the recipients, so that they can relink them
X with the library after making changes to the library and recompiling
X it. And you must show them these terms so they know their rights.
X
X We protect your rights with a two-step method: (1) we copyright the
X library, and (2) we offer you this license, which gives you legal
X permission to copy, distribute and/or modify the library.
X
X To protect each distributor, we want to make it very clear that there
X is no warranty for the free library. Also, if the library is modified
X by someone else and passed on, the recipients should know that what
X they have is not the original version, so that the original author's
X reputation will not be affected by problems that might be introduced
X by others.
X
X Finally, software patents pose a constant threat to the existence of
X any free program. We wish to make sure that a company cannot
X effectively restrict the users of a free program by obtaining a
X restrictive license from a patent holder. Therefore, we insist that
X any patent license obtained for a version of the library must be
X consistent with the full freedom of use specified in this license.
X
X Most GNU software, including some libraries, is covered by the
X ordinary GNU General Public License. This license, the GNU Lesser
X General Public License, applies to certain designated libraries, and
X is quite different from the ordinary General Public License. We use
X this license for certain libraries in order to permit linking those
X libraries into non-free programs.
X
X When a program is linked with a library, whether statically or using a
X shared library, the combination of the two is legally speaking a
X combined work, a derivative of the original library. The ordinary
X General Public License therefore permits such linking only if the
X entire combination fits its criteria of freedom. The Lesser General
X Public License permits more lax criteria for linking other code with
X the library.
X
X We call this license the "Lesser" General Public License because it
X does Less to protect the user's freedom than the ordinary General
X Public License. It also provides other free software developers Less
X of an advantage over competing non-free programs. These disadvantages
X are the reason we use the ordinary General Public License for many
X libraries. However, the Lesser license provides advantages in certain
X special circumstances.
X
X For example, on rare occasions, there may be a special need to
X encourage the widest possible use of a certain library, so that it
X becomes a de-facto standard. To achieve this, non-free programs must
X be allowed to use the library. A more frequent case is that a free
X library does the same job as widely used non-free libraries. In this
X case, there is little to gain by limiting the free library to free
X software only, so we use the Lesser General Public License.
X
X In other cases, permission to use a particular library in non-free
X programs enables a greater number of people to use a large body of
X free software. For example, permission to use the GNU C Library in
X non-free programs enables many more people to use the whole GNU
X operating system, as well as its variant, the GNU/Linux operating
X system.
X
X Although the Lesser General Public License is Less protective of the
X users' freedom, it does ensure that the user of a program that is
X linked with the Library has the freedom and the wherewithal to run
X that program using a modified version of the Library.
X
X The precise terms and conditions for copying, distribution and
X modification follow. Pay close attention to the difference between a
X "work based on the library" and a "work that uses the library". The
X former contains code derived from the library, whereas the latter must
X be combined with the library in order to run.
X
X[10]TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
X
X 0. This License Agreement applies to any software library or other
X program which contains a notice placed by the copyright holder or
X other authorized party saying it may be distributed under the terms of
X this Lesser General Public License (also called "this License"). Each
X licensee is addressed as "you".
X
X A "library" means a collection of software functions and/or data
X prepared so as to be conveniently linked with application programs
X (which use some of those functions and data) to form executables.
X
X The "Library", below, refers to any such software library or work
X which has been distributed under these terms. A "work based on the
X Library" means either the Library or any derivative work under
X copyright law: that is to say, a work containing the Library or a
X portion of it, either verbatim or with modifications and/or translated
X straightforwardly into another language. (Hereinafter, translation is
X included without limitation in the term "modification".)
X
X "Source code" for a work means the preferred form of the work for
X making modifications to it. For a library, complete source code means
X all the source code for all modules it contains, plus any associated
X interface definition files, plus the scripts used to control
X compilation and installation of the library.
X
X Activities other than copying, distribution and modification are not
X covered by this License; they are outside its scope. The act of
X running a program using the Library is not restricted, and output from
X such a program is covered only if its contents constitute a work based
X on the Library (independent of the use of the Library in a tool for
X writing it). Whether that is true depends on what the Library does and
X what the program that uses the Library does.
X
X 1. You may copy and distribute verbatim copies of the Library's
X complete source code as you receive it, in any medium, provided that
X you conspicuously and appropriately publish on each copy an
X appropriate copyright notice and disclaimer of warranty; keep intact
X all the notices that refer to this License and to the absence of any
X warranty; and distribute a copy of this License along with the
X Library.
X
X You may charge a fee for the physical act of transferring a copy, and
X you may at your option offer warranty protection in exchange for a
X fee.
X
X 2. You may modify your copy or copies of the Library or any portion of
X it, thus forming a work based on the Library, and copy and distribute
X such modifications or work under the terms of Section 1 above,
X provided that you also meet all of these conditions:
X
X * a) The modified work must itself be a software library.
X * b) You must cause the files modified to carry prominent notices
X stating that you changed the files and the date of any change.
X * c) You must cause the whole of the work to be licensed at no
X charge to all third parties under the terms of this License.
X * d) If a facility in the modified Library refers to a function or a
X table of data to be supplied by an application program that uses
X the facility, other than as an argument passed when the facility
X is invoked, then you must make a good faith effort to ensure that,
X in the event an application does not supply such function or
X table, the facility still operates, and performs whatever part of
X its purpose remains meaningful.
X (For example, a function in a library to compute square roots has
X a purpose that is entirely well-defined independent of the
X application. Therefore, Subsection 2d requires that any
X application-supplied function or table used by this function must
X be optional: if the application does not supply it, the square
X root function must still compute square roots.)
X These requirements apply to the modified work as a whole. If
X identifiable sections of that work are not derived from the
X Library, and can be reasonably considered independent and separate
X works in themselves, then this License, and its terms, do not
X apply to those sections when you distribute them as separate
X works. But when you distribute the same sections as part of a
X whole which is a work based on the Library, the distribution of
X the whole must be on the terms of this License, whose permissions
X for other licensees extend to the entire whole, and thus to each
X and every part regardless of who wrote it.
X Thus, it is not the intent of this section to claim rights or
X contest your rights to work written entirely by you; rather, the
X intent is to exercise the right to control the distribution of
X derivative or collective works based on the Library.
X In addition, mere aggregation of another work not based on the
X Library with the Library (or with a work based on the Library) on
X a volume of a storage or distribution medium does not bring the
X other work under the scope of this License.
X
X 3. You may opt to apply the terms of the ordinary GNU General Public
X License instead of this License to a given copy of the Library. To do
X this, you must alter all the notices that refer to this License, so
X that they refer to the ordinary GNU General Public License, version 2,
X instead of to this License. (If a newer version than version 2 of the
X ordinary GNU General Public License has appeared, then you can specify
X that version instead if you wish.) Do not make any other change in
X these notices.
X
X Once this change is made in a given copy, it is irreversible for that
X copy, so the ordinary GNU General Public License applies to all
X subsequent copies and derivative works made from that copy.
X
X This option is useful when you wish to copy part of the code of the
X Library into a program that is not a library.
X
X 4. You may copy and distribute the Library (or a portion or derivative
X of it, under Section 2) in object code or executable form under the
X terms of Sections 1 and 2 above provided that you accompany it with
X the complete corresponding machine-readable source code, which must be
X distributed under the terms of Sections 1 and 2 above on a medium
X customarily used for software interchange.
X
X If distribution of object code is made by offering access to copy from
X a designated place, then offering equivalent access to copy the source
X code from the same place satisfies the requirement to distribute the
X source code, even though third parties are not compelled to copy the
X source along with the object code.
X
X 5. A program that contains no derivative of any portion of the
X Library, but is designed to work with the Library by being compiled or
X linked with it, is called a "work that uses the Library". Such a work,
X in isolation, is not a derivative work of the Library, and therefore
X falls outside the scope of this License.
X
X However, linking a "work that uses the Library" with the Library
X creates an executable that is a derivative of the Library (because it
X contains portions of the Library), rather than a "work that uses the
X library". The executable is therefore covered by this License. Section
X 6 states terms for distribution of such executables.
X
X When a "work that uses the Library" uses material from a header file
X that is part of the Library, the object code for the work may be a
X derivative work of the Library even though the source code is not.
X Whether this is true is especially significant if the work can be
X linked without the Library, or if the work is itself a library. The
X threshold for this to be true is not precisely defined by law.
X
X If such an object file uses only numerical parameters, data structure
X layouts and accessors, and small macros and small inline functions
X (ten lines or less in length), then the use of the object file is
X unrestricted, regardless of whether it is legally a derivative work.
X (Executables containing this object code plus portions of the Library
X will still fall under Section 6.)
X
X Otherwise, if the work is a derivative of the Library, you may
X distribute the object code for the work under the terms of Section 6.
X Any executables containing that work also fall under Section 6,
X whether or not they are linked directly with the Library itself.
X
X 6. As an exception to the Sections above, you may also combine or link
X a "work that uses the Library" with the Library to produce a work
X containing portions of the Library, and distribute that work under
X terms of your choice, provided that the terms permit modification of
X the work for the customer's own use and reverse engineering for
X debugging such modifications.
X
X You must give prominent notice with each copy of the work that the
X Library is used in it and that the Library and its use are covered by
X this License. You must supply a copy of this License. If the work
X during execution displays copyright notices, you must include the
X copyright notice for the Library among them, as well as a reference
X directing the user to the copy of this License. Also, you must do one
X of these things:
X
X * a) Accompany the work with the complete corresponding
X machine-readable source code for the Library including whatever
X changes were used in the work (which must be distributed under
X Sections 1 and 2 above); and, if the work is an executable linked
X with the Library, with the complete machine-readable "work that
X uses the Library", as object code and/or source code, so that the
X user can modify the Library and then relink to produce a modified
X executable containing the modified Library. (It is understood that
X the user who changes the contents of definitions files in the
X Library will not necessarily be able to recompile the application
X to use the modified definitions.)
X * b) Use a suitable shared library mechanism for linking with the
X Library. A suitable mechanism is one that (1) uses at run time a
X copy of the library already present on the user's computer system,
X rather than copying library functions into the executable, and (2)
X will operate properly with a modified version of the library, if
X the user installs one, as long as the modified version is
X interface-compatible with the version that the work was made with.
X * c) Accompany the work with a written offer, valid for at least
X three years, to give the same user the materials specified in
X Subsection 6a, above, for a charge no more than the cost of
X performing this distribution.
X * d) If distribution of the work is made by offering access to copy
X from a designated place, offer equivalent access to copy the above
X specified materials from the same place.
X * e) Verify that the user has already received a copy of these
X materials or that you have already sent this user a copy.
X
X For an executable, the required form of the "work that uses the
X Library" must include any data and utility programs needed for
X reproducing the executable from it. However, as a special exception,
X the materials to be distributed need not include anything that is
X normally distributed (in either source or binary form) with the major
X components (compiler, kernel, and so on) of the operating system on
X which the executable runs, unless that component itself accompanies
X the executable.
X
X It may happen that this requirement contradicts the license
X restrictions of other proprietary libraries that do not normally
X accompany the operating system. Such a contradiction means you cannot
X use both them and the Library together in an executable that you
X distribute.
X
X 7. You may place library facilities that are a work based on the
X Library side-by-side in a single library together with other library
X facilities not covered by this License, and distribute such a combined
X library, provided that the separate distribution of the work based on
X the Library and of the other library facilities is otherwise
X permitted, and provided that you do these two things:
X
X * a) Accompany the combined library with a copy of the same work
X based on the Library, uncombined with any other library
X facilities. This must be distributed under the terms of the
X Sections above.
X * b) Give prominent notice with the combined library of the fact
X that part of it is a work based on the Library, and explaining
X where to find the accompanying uncombined form of the same work.
X
X 8. You may not copy, modify, sublicense, link with, or distribute the
X Library except as expressly provided under this License. Any attempt
X otherwise to copy, modify, sublicense, link with, or distribute the
X Library is void, and will automatically terminate your rights under
X this License. However, parties who have received copies, or rights,
X from you under this License will not have their licenses terminated so
X long as such parties remain in full compliance.
X
X 9. You are not required to accept this License, since you have not
X signed it. However, nothing else grants you permission to modify or
X distribute the Library or its derivative works. These actions are
X prohibited by law if you do not accept this License. Therefore, by
X modifying or distributing the Library (or any work based on the
X Library), you indicate your acceptance of this License to do so, and
X all its terms and conditions for copying, distributing or modifying
X the Library or works based on it.
X
X 10. Each time you redistribute the Library (or any work based on the
X Library), the recipient automatically receives a license from the
X original licensor to copy, distribute, link with or modify the Library
X subject to these terms and conditions. You may not impose any further
X restrictions on the recipients' exercise of the rights granted herein.
X You are not responsible for enforcing compliance by third parties with
X this License.
X
X 11. If, as a consequence of a court judgment or allegation of patent
X infringement or for any other reason (not limited to patent issues),
X conditions are imposed on you (whether by court order, agreement or
X otherwise) that contradict the conditions of this License, they do not
X excuse you from the conditions of this License. If you cannot
X distribute so as to satisfy simultaneously your obligations under this
X License and any other pertinent obligations, then as a consequence you
X may not distribute the Library at all. For example, if a patent
X license would not permit royalty-free redistribution of the Library by
X all those who receive copies directly or indirectly through you, then
X the only way you could satisfy both it and this License would be to
X refrain entirely from distribution of the Library.
X
X If any portion of this section is held invalid or unenforceable under
X any particular circumstance, the balance of the section is intended to
X apply, and the section as a whole is intended to apply in other
X circumstances.
X
X It is not the purpose of this section to induce you to infringe any
X patents or other property right claims or to contest validity of any
X such claims; this section has the sole purpose of protecting the
X integrity of the free software distribution system which is
X implemented by public license practices. Many people have made
X generous contributions to the wide range of software distributed
X through that system in reliance on consistent application of that
X system; it is up to the author/donor to decide if he or she is willing
X to distribute software through any other system and a licensee cannot
X impose that choice.
X
X This section is intended to make thoroughly clear what is believed to
X be a consequence of the rest of this License.
X
X 12. If the distribution and/or use of the Library is restricted in
X certain countries either by patents or by copyrighted interfaces, the
X original copyright holder who places the Library under this License
X may add an explicit geographical distribution limitation excluding
X those countries, so that distribution is permitted only in or among
X countries not thus excluded. In such case, this License incorporates
X the limitation as if written in the body of this License.
X
X 13. The Free Software Foundation may publish revised and/or new
X versions of the Lesser General Public License from time to time. Such
X new versions will be similar in spirit to the present version, but may
X differ in detail to address new problems or concerns.
X
X Each version is given a distinguishing version number. If the Library
X specifies a version number of this License which applies to it and
X "any later version", you have the option of following the terms and
X conditions either of that version or of any later version published by
X the Free Software Foundation. If the Library does not specify a
X license version number, you may choose any version ever published by
X the Free Software Foundation.
X
X 14. If you wish to incorporate parts of the Library into other free
X programs whose distribution conditions are incompatible with these,
X write to the author to ask for permission. For software which is
X copyrighted by the Free Software Foundation, write to the Free
X Software Foundation; we sometimes make exceptions for this. Our
X decision will be guided by the two goals of preserving the free status
X of all derivatives of our free software and of promoting the sharing
X and reuse of software generally.
X
X NO WARRANTY
X
X 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO
X WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW.
X EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR
X OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY
X KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE
X IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
X PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE
X LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME
X THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
X
X 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN
X WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY
X AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU
X FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR
X CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE
X LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING
X RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A
X FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF
X SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
X DAMAGES.
X
XEND OF TERMS AND CONDITIONS
X
X[11]How to Apply These Terms to Your New Libraries
X
X If you develop a new library, and you want it to be of the greatest
X possible use to the public, we recommend making it free software that
X everyone can redistribute and change. You can do so by permitting
X redistribution under these terms (or, alternatively, under the terms
X of the ordinary General Public License).
X
X To apply these terms, attach the following notices to the library. It
X is safest to attach them to the start of each source file to most
X effectively convey the exclusion of warranty; and each file should
X have at least the "copyright" line and a pointer to where the full
X notice is found.
X
Xone line to give the library's name and an idea of what it does.
XCopyright (C) year name of author
X
XThis library is free software; you can redistribute it and/or
Xmodify it under the terms of the GNU Lesser General Public
XLicense as published by the Free Software Foundation; either
Xversion 2.1 of the License, or (at your option) any later version.
X
XThis library is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY; without even the implied warranty of
XMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
XLesser General Public License for more details.
X
XYou should have received a copy of the GNU Lesser General Public
XLicense along with this library; if not, write to the Free Software
XFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
X
X Also add information on how to contact you by electronic and paper
X mail.
X
X You should also get your employer (if you work as a programmer) or
X your school, if any, to sign a "copyright disclaimer" for the library,
X if necessary. Here is a sample; alter the names:
X
XYoyodyne, Inc., hereby disclaims all copyright interest in
Xthe library `Frob' (a library for tweaking knobs) written
Xby James Random Hacker.
X
Xsignature of Ty Coon, 1 April 1990
XTy Coon, President of Vice
X
X That's all there is to it!
X _________________________________________________________________
X
X Return to [12]GNU's home page.
X
X FSF & GNU inquiries & questions to [13]gnu@gnu.org. Other [14]ways to
X contact the FSF.
X
X Comments on these web pages to [15]webmasters@www.gnu.org, send other
X questions to [16]gnu@gnu.org.
X
X Copyright notice above.
X Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
X MA 02111, USA
X
X Updated: 7 Jan 2000 rms
X _________________________________________________________________
X
XReferences
X
X 1. http://www.gnu.org/graphics/philosophicalgnu.html
X 2. http://www.gnu.org/copyleft/copyleft.html#translationsLGPL
X 3. http://www.gnu.org/philosophy/why-not-lgpl.html
X 4. http://www.gnu.org/copyleft/lesser.html#SEC1
X 5. http://www.gnu.org/copyleft/lesser.html#SEC2
X 6. http://www.gnu.org/copyleft/lesser.html#SEC3
X 7. http://www.gnu.org/copyleft/lesser.html#SEC4
X 8. http://www.gnu.org/copyleft/lesser.html#TOC1
X 9. http://www.gnu.org/copyleft/lesser.html#TOC2
X 10. http://www.gnu.org/copyleft/lesser.html#TOC3
X 11. http://www.gnu.org/copyleft/lesser.html#TOC4
X 12. http://www.gnu.org/home.html
X 13. mailto:gnu@gnu.org
X 14. http://www.gnu.org/home.html#ContactInfo
X 15. mailto:webmasters@www.gnu.org
X 16. mailto:gnu@gnu.org
END-of-LICENSE
exit