galois.c

通信类程序

/*
**    FILE    : galois.c   
**    PURPOSE : The functions in this file perform Galois Field arithmetic
**              ( i.e. arithmetic operations in a field with a finite number
**                of elements).
**              These operations are necessary to generate binary and
**              non-binary error-correcting codes.
**    AUTHOR  : Bart De Canne, Belgium ([e-mail])
**    COMPILER: BC++ 3.1 compiler
**    DEPENDENCIES:  Needs "galois.h" as an include file 
**    DATE    : 01-09-1994
**    VERSION : 1.0
*/

#define _GALOIS
#include "galois.h"

static void wr_el_and_optable(FILE *,pGALOIS,pOPTABLE);
static void wr_min_pol(FILE *,pGALOIS);
static void re_el_and_optable(FILE *,pGALOIS,pOPTABLE);
static void re_min_pol(FILE *,pGALOIS);

static int tmp;
static pPOLYNOM pp_tmp;

/* #######################   DYNAMIC ALLOCATION  ######################### */


pPOLYNOM FreePolynom(pPOLYNOM pp) {

   if(pp!=NULL){
      if(pp->c != NULL) {
         free(pp->c);
         pp->c=NULL;
         }
      free(pp);
      pp=NULL;
      }
   return pp;
   }

pPOLYARR FreePolyArr(pPOLYARR pa) {

   int i;

   if(pa!=NULL) {
      for(i=0;i<pa->MaxNo;i++) {
         pa->ppp[i]=FreePolynom(pa->ppp[i]);
         }
      free(pa->ppp);
      free(pa);
      pa=NULL;
      }
   return pa;
   }


pGALOIS FreeGalois(pGALOIS pg) {

   int i;

   if(pg!=NULL) {
      for(i=0;i<pg->MaxNo;i++) {
         pg->pe[i].pp=FreePolynom(pg->pe[i].pp);
         }
      free(pg->pe);
      free(pg);
      pg=NULL;
      }
   return pg;
   }


pOPTABLE FreeOpTable(pOPTABLE po) {

   int i;

   if(po!=NULL) {
      if(po->Add != NULL) {
         for(i=0;i<po->MaxNo;i++) {
            free(po->Add[i]);
            free(po->Mult[i]);
            }
         free(po->Add);
         free(po->Mult);
         free(po->InvAdd);
         free(po->InvMult);
         }
      free(po);
      po=NULL;
      }
   return po;
   }

/* 
** dyn. allocation of a table defining operations in GF(p^q).
** The table is NOT actually constructed.
*/

pOPTABLE AllocOpTable(pOPTABLE po,int p, int q) {

   int i,j;

   BEGIN("AllocOpTable");
   if(po!=NULL)
      po=FreeOpTable(po);

   po=(pOPTABLE) malloc(sizeof(OPTABLE));
   if(po==NULL) ERROR;
   po->Base=p;
   po->Exp=q;
   po->MaxNo=(int)pow((double)p,(double)q);

   po->Add=(byte**)malloc(sizeof(byte*)*po->MaxNo);
   po->Mult=(byte**)malloc(sizeof(byte*)*po->MaxNo);
   po->InvAdd=(byte*)malloc(po->MaxNo);
   po->InvMult=(byte*)malloc(po->MaxNo);

   if(po->Add==NULL || po->Mult==NULL ||
      po->InvAdd==NULL || po->InvMult==NULL)
      ERROR;

   for(i=0;i<po->MaxNo;i++) {
      po->Add[i]=(byte*)malloc(po->MaxNo-i);
      po->Mult[i]=(byte*)malloc(po->MaxNo-i);
      if(po->Add[i]==NULL || po->Mult[i]==NULL) ERROR;
      }
   return po;
   }

/*
** construction of the table <po> given the GF-elements in <pg> and the
** symbol field operations in <op>.
** Note : since operands of + & . operations commute, only half of the
** p^q x p^q table is constructed.
** Hence, when referencing the table of operations,
** the proper entry is found using the I(x,y) and J(x,y) preprocessor
** directives (see galois.h)
** For the GF-indexing convention, see infra.
*/

pOPTABLE ConstructOpTable(pOPTABLE po,pGALOIS pg,pOPTABLE op) {

   int i,j;

   BEGIN("ConstructOpTable");
   if(po==NULL) ERROR;

   START_PACIFIER;
   for(i=0;i<po->MaxNo;i++) {
      PACIFIER(100*i/po->MaxNo);
      po->InvAdd[i]  =  (byte) i_add_inv(i,pg,op);
      po->InvMult[i] =  (byte) i_mult_inv(i,pg,op);
      for(j=i;j<po->MaxNo;j++) {
         po->Add[i][j-i] = (byte) i_add(i,j,pg,op);
         po->Mult[i][j-i]= (byte) i_mult(i,j,pg,op);
         }
      }
   STOP_PACIFIER;
   return po;
   }

/*
**    !!The polynomials in <pg> are NOT allocated
*/

pGALOIS AllocGalois(pGALOIS pg,int p,int q) {

   int i;

   BEGIN("AllocGalois");
   if(pg!=NULL)
      pg=FreeGalois(pg);

   pg=(pGALOIS)malloc(sizeof(GALOIS));
   if(pg==NULL) ERROR;
   pg->Base=p;
   pg->Exp=q;
   pg->MaxNo=(int)pow((double)p,(double)q);
   pg->pe=(pELEMENT)malloc(sizeof(ELEMENT)*pg->MaxNo);
   if(pg->pe==NULL) ERROR;
   for(i=0;i<pg->MaxNo;i++)
      pg->pe[i].pp=NULL;
   return pg;
   }


pPOLYNOM AllocPolynom(pPOLYNOM pp,int p,int max_deg) {

   BEGIN("AllocPolynom");
   if(pp!=NULL)
      pp=FreePolynom(pp);

   pp=(pPOLYNOM) malloc(sizeof(POLYNOM));
   if(pp==NULL) ERROR;
   pp->MaxDeg=max_deg;
   pp->Deg=0;
   pp->Base=p;
   pp->c=(int *)malloc(sizeof(int)*(max_deg+1));
   if(pp->c==NULL) ERROR;
   memset(pp->c,0,sizeof(int)*(max_deg+1));
   return pp;
   }


pPOLYARR AllocPolyArr(pPOLYARR pa,int max_no) {

   BEGIN("AllocPolyArr");
   if(pa!=NULL)
      pa=FreePolyArr(pa);

   pa=(pPOLYARR) malloc(sizeof(POLYARR));
   if(pa==NULL) ERROR;
   pa->MaxNo = max_no;
   pa->FirstFree=0;
   pa->ppp=(ppPOLYNOM) malloc(pa->MaxNo * sizeof(pPOLYNOM));
   if(pa->ppp==NULL) ERROR;
   memset(pa->ppp,0,sizeof(pPOLYNOM)*pa->MaxNo);
   return pa;
   }


/* ######################## CALCULATIONS IN GF ########################### */
/*
**  Note: In the following functions all references to GF-elements denote
**        indexes to the <pg>-structure containing these elements.
**        The convention is:
**           index = 0        ->    GF-element = 0
**                   1        ->                 1
**                   2        ->