/* ========================== C MeatAxe ============================= Finite field arithmetic and common functions. `Small' version for field orders q <= 256. Originally based on the `hprout.c' written by Klaus Lux. (C) Copyright 1993 Michael Ringe, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany This program is free software; see the file COPYING for details. ================================================================== */ /* $Id: zzz.c,v 2.5 1994/02/15 14:09:19 mringe Exp $ * * $Log: zzz.c,v $ * Revision 2.5 1994/02/15 14:09:19 mringe * zsetlen() erweitert fuer Permutationen. * * Revision 2.4 1994/02/15 10:28:33 mringe * MSDOS_BCC entfernt. * * Revision 2.3 1994/02/13 18:26:56 mringe * Neu: os.c, os.h. * * Revision 2.2 1993/10/21 21:57:35 mringe * Permutationen. * * Revision 2.1 1993/10/20 18:17:07 mringe * MeatAxe-2.0, Phase II. * * Revision 2.0 1993/10/14 18:54:18 mringe * MeatAxe-2.0, Phase I * * Revision 1.43 1993/10/11 19:05:28 mringe * Neue Library-Struktur. * * Revision 1.42 1993/10/06 04:41:05 mringe * utils Library eliminiert. * * Revision 1.41 1993/10/05 23:35:02 mringe * zerrno eliminiert. * * Revision 1.40 1993/08/12 16:14:23 mringe * Include . * * Revision 1.39 1993/08/10 08:47:20 mringe * Dokumentation entfernt. * * Revision 1.38 1993/08/09 14:00:43 mringe * Dok. teilweise entfernt. * * Revision 1.37 1993/08/06 14:01:59 mringe * Neuer File-header. * * Revision 1.36 1993/07/29 14:47:00 mringe * OS_xxx-Symbole. * * Revision 1.35 1993/07/28 13:34:49 mringe * *** empty log message *** * * Revision 1.34 1993/07/23 13:46:27 mringe * OS-Symbole neu (SYS_xxx) * * Revision 1.33 1993/07/18 15:28:15 mringe * Definiere zinittime fuer SYS_MSDOS * * Revision 1.32 1993/07/13 20:30:59 mringe * Neue File i/o library. * * Revision 1.31 1993/07/13 16:54:20 mringe * Benutze -Q beim Aufruf von maketab. * * Revision 1.30 1993/05/25 13:08:07 mringe * File i/o nach zfile.c verlagert. * * Revision 1.29 1993/05/24 17:17:24 mringe * Dokumentation. * * Revision 1.28 1993/05/24 08:02:34 mringe * Dokumentation. * * Revision 1.27 1993/05/21 09:54:19 mringe * Pruefe Filegroesse bei Matrizen, um alte Version zu erkennen. * * Revision 1.26 1993/05/19 09:55:48 mringe * zreadlong(): VZ-Erweiterung, falls sizeof(long)>4 * * Revision 1.25 1993/05/18 12:17:50 mringe * Neues Fileformat. * * Revision 1.24 1993/05/18 06:53:15 mringe * zRead(), zWrite(): Zeilenweise lesen/schreiben. * * Revision 1.23 1993/05/17 16:36:04 mringe * Aenderungen fuer 64-Bit-Maschinen (noch unvollstaendig!) * * Revision 1.22 1993/03/23 14:23:05 mringe * zsetlen(): Cache fuer Zeilenlaengen eingebaut. * * Revision 1.21 1993/03/22 10:31:33 mringe * Kleine Aenderungen an zsetlen() und zextract(). * * Revision 1.20 1993/02/17 11:16:12 mringe * Include-Files... * * Revision 1.19 1993/02/16 17:33:20 mringe * Symbole SYS_BSD und SYS_SYSV eingefuehrt. * * Revision 1.18 1993/02/10 19:40:54 mringe * Libraries angelegt (YYY und ZZZ). * * Revision 1.17 1993/01/11 16:08:37 hiss * *** empty log message *** * * Revision 1.16 1992/12/24 08:47:30 mringe * Bug in zsetlen() behoben. Einbettung von K"orpern sollte jetzt * jetzt maschinenunabh"angig sein. * * Revision 1.15 1992/12/08 08:32:48 mringe * Abfrage wieder raus - bringt nichts. * * Revision 1.14 1992/12/07 20:30:02 mringe * zmulrow(): Teste, ob Wert = 1 * * Revision 1.13 1992/11/04 09:10:16 mringe * Neu: zpermrow() * * Revision 1.12 1992/09/01 12:18:43 mringe * Kleine "Anderungen an zalloc() und zmaprow() * * Revision 1.11 1992/08/31 13:50:43 mringe * zmaprow() f"ur GF(2) verbessert (kein zextract() benutzen!) * * Revision 1.10 1992/07/24 09:59:46 mringe * Include unistd.h * * Revision 1.9 1992/07/23 06:38:03 mringe * Rufe MAKETAB auf, falls noetig. * * Revision 1.8 1992/07/22 14:04:09 mringe * zrestrict() * * Revision 1.7 1992/06/30 12:37:16 mringe * Lese Header am Anfang des Files. * * Revision 1.6 1992/06/28 08:58:28 mringe * CHECKRANGE zeigt jetzt Wert und Grenzen an. * CHECKFILE akzeptiert auf file #0. * * Revision 1.5 1992/06/28 08:22:32 mringe * CHECKCOL() in zextract() und zinsert() entfernt. * * Revision 1.4 1992/06/27 17:16:46 mringe * ZZZ Version 2: zembed() neu hinzugekommen. * * Revision 1.3 1992/05/29 11:21:38 mringe * Id string eingef"ugt. * */ #include #include #include "meataxe.h" /* ------------------------------------------------------------------ Gobal data ------------------------------------------------------------------ */ typedef unsigned char BYTE; BYTE tmult[256][256], tadd[256][256], tffirst[256][2], textract[8][256], taddinv[256], tmultinv[256], tnull[8][256], tinsert[8][256]; static long embedord[4]; /* Subfield orders */ static BYTE embed[4][16]; /* Embeddings of subfields */ static BYTE restrict[4][256]; /* Restrictions to subfields */ long zchar = 0; /* Characteristic */ long zfl = -1; /* Field order */ FEL zgen = -1; /* Generator */ long znoc = 0; /* No. of columns for row operations */ static long MPB = 0; /* No. of marks per byte */ long BPR = 0; /* No. of bytes actually used */ long LPR = 0; /* Long ints per row */ static long rowsize = 0;/* Row size (in bytes) = LPR*sizeof(long) */ /* ------------------------------------------------------------------ Argument checking ------------------------------------------------------------------ */ #if defined(DEBUG) #define CHECKRANGE(x,lo,hi) if ((x)<(lo)||(x)>(hi)) {\ fprintf(stderr,"%ld <= %ld <= %ld ?\n",(long)(lo),\ (long)(x),(long)(hi));\ fatal("RANGE CHECK ERROR",__LINE__);} #define CHECKINIT() {if (zfl == -1) fatal("not initialized",__LINE__); } #else #define CHECKRANGE(x,lo,hi) #define CHECKINIT() #endif #define CHECKFEL(x) CHECKRANGE(x,0,zfl-1) #define CHECKCOL(x) CHECKRANGE(x,1,znoc) /* ------------------------------------------------------------------ zadd(), zsub(), zmul(), zdiv() - Finite field arithmetic return value: a+b, a-b, a*b, a/b ------------------------------------------------------------------ */ #if 0 #if defined (__STDC__) FEL zadd(FEL a, FEL b) #else FEL zadd(a, b) FEL a, b; #endif { CHECKINIT(); CHECKFEL(a); CHECKFEL(b); return tadd[a][b]; } #if defined (__STDC__) FEL zsub(FEL a, FEL b) #else FEL zsub(a, b) FEL a, b; #endif { CHECKINIT(); CHECKFEL(a); CHECKFEL(b); return tadd[a][taddinv[b]]; } #if defined (__STDC__) FEL zmul(FEL a, FEL b) #else FEL zmul(a, b) FEL a, b; #endif { CHECKINIT(); CHECKFEL(a); CHECKFEL(b); return tmult[a][b]; } #if defined (__STDC__) FEL zdiv(FEL a, FEL b) #else FEL zdiv(a, b) FEL a, b; #endif { CHECKINIT(); CHECKFEL(a); CHECKFEL(b); if (b == 0) FATAL("DIVISION BY ZERO"); return tmult[a][tmultinv[b]]; } #endif /* ------------------------------------------------------------------ zalloc() - Allocate memory and initialize ------------------------------------------------------------------ */ PTR zalloc(nrows) long nrows; /* Number of rows */ { PTR p; CHECKINIT(); if ((p = (PTR) malloc((size_t)(rowsize * nrows))) == NULL) { fprintf(stderr,"zalloc(): Request=%ld Bytes\n",rowsize*nrows); FATAL("OUT OF MEMORY"); } memset(p,0,(size_t)(rowsize*nrows)); return p; } /* ------------------------------------------------------------------ zsize() - Size of a matrix or permutation(s) ------------------------------------------------------------------ */ size_t zsize(nrows) long nrows; { CHECKINIT(); return ((size_t)(rowsize * nrows)); } /* ------------------------------------------------------------------ zmoverow() - Move row/vector return value: none ------------------------------------------------------------------ */ void zmoverow(dest, src) PTR dest, src; { register long *s = (long *) src, *d = (long *) dest, i; CHECKINIT(); for (i = LPR; i > 0; --i) *d++ = *s++; } /* ------------------------------------------------------------------ zswaprow() - Swap two rows return value: none ------------------------------------------------------------------ */ void zswaprow(dest, src) PTR dest, src; { register long *p1 = (long *) src, *p2 = (long *) dest, i, l; CHECKINIT(); for (i = LPR; i > 0; --i) { l = *p1; *p1++ = *p2; *p2++ = l; } } /* ------------------------------------------------------------------ zcmprow() - Compare two rows ------------------------------------------------------------------ */ int zcmprow(dest, src) PTR dest, src; { register long k; register long *d = (long *) dest, *s = (long *) src; CHECKINIT(); for (k = LPR; k > 0; --k) if (*d++ != *s++) return 1; return 0; } /* ------------------------------------------------------------------ zadvance() - advance pointer return value: none ------------------------------------------------------------------ */ void zadvance(ptr, nrows) PTR *ptr; long nrows; { CHECKINIT(); *(long **)ptr += nrows * LPR; } /* ------------------------------------------------------------------ zinsert() - insert mark into row return value: none ------------------------------------------------------------------ */ #if defined (__STDC__) void zinsert(PTR row, long col, FEL mark) #else void zinsert(row, col, mark) PTR row; long col; FEL mark; #endif { register BYTE *loc = (BYTE *)row + ((col - 1) / MPB); register long idx = (col - 1) % MPB; CHECKINIT(); CHECKFEL(mark); *loc = tnull[idx][*loc] + tinsert[idx][mark]; } /* ------------------------------------------------------------------ zextract() - extract mark from row return value: mark extracted from row[col] ------------------------------------------------------------------ */ FEL zextract(row, col) PTR row; long col; { register BYTE *loc = (BYTE *)row + ((col - 1) / MPB); CHECKINIT(); return (textract[(col - 1) % MPB][*loc]); } /* ----------------------------------------------------------------- zsetlen() - Set field parameter and row length. Read table file if necessary. ------------------------------------------------------------------ */ void zsetlen(field, ncols) long field; long ncols; { static char filename[50]; FILE *fd; long info[5]; if (field != zfl && field != -1) { int count = 2; /* Open table file --------------- */ while (count-- > 0) { sprintf(filename,"p%3.3ld.zzz",(long)field); if ((fd = os_fopen(filename,FM_READ|FM_LIB)) == NULL) { if (count == 0) { perror(filename); FATAL("ERROR OPENING TABLE FILE"); } else { sprintf(filename,"maketab -Q %ld",field); system(filename); } } else break; } /* Read header, perform some checks -------------------------------- */ if (zreadlong(fd,info,5) != 5) { perror(filename); FATAL("ERROR READING FILE HEADER"); }; if (info[2] != field || info[1] < 0 || info[1] > field || info[0] <= 1 || info[2] % info[0] != 0 || info[3] < 1 || info[3] > 8) { fprintf(stderr,"%s: Invalid header\n", filename); FATAL("TABLE FILE CORRUPTED"); } zchar = info[0]; zgen = (FEL) info[1]; MPB = info[3]; if (info[4] != (long) ZZZVERSION) fprintf(stderr,"BAD VERSION NUMBER IN TABLE FILE"); /* Read tables ----------- */ if (fread(tmult,4,sizeof(tmult)/4,fd) != sizeof(tmult)/4 || fread(tadd,4,sizeof(tadd)/4,fd) != sizeof(tadd)/4 || fread(tffirst,1,sizeof(tffirst),fd) != sizeof(tffirst) || fread(textract,1,sizeof(textract),fd) != sizeof(textract) || fread(taddinv,1,sizeof(taddinv),fd) != sizeof(taddinv) || fread(tmultinv,1,sizeof(tmultinv),fd) != sizeof(tmultinv) || fread(tnull,1,sizeof(tnull),fd) != sizeof(tnull) || fread(tinsert,1,sizeof(tinsert),fd) != sizeof(tinsert) || zreadlong(fd,embedord,4) != 4 || fread(embed,16,4,fd) != 4 || fread(restrict,256,4,fd) != 4 ) { perror(filename); FATAL("ERROR READING FILE"); } fclose(fd); } /* Set row length -------------- */ zfl = field; if (field == -1) /* Permutations */ { znoc = ncols; BPR = rowsize = ncols * sizeof(long); /* Bytes per row */ LPR = ncols; /* Ints per row */ } else /* Vectors */ { znoc = ncols; BPR = (znoc-1) / MPB + 1; /* Used bytes per row */ LPR = (BPR-1) / (sizeof(long)) + 1; /* Ints per row */ rowsize = LPR * sizeof(long); /* Total bytes per row */ } } /* ------------------------------------------------------------------ zembed() - Embed a subfield element. return value: Embedded field element. ------------------------------------------------------------------ */ #if defined (__STDC__) FEL zembed(FEL a, long subfield) #else FEL zembed(a, subfield) FEL a; long subfield; #endif { int i; for (i = 0; embedord[i] != subfield && i < 4; ++i); if (i >= 4) FATAL("NO SUCH SUBFIELD"); return embed[i][a]; } /* ------------------------------------------------------------------ zrestrict() - Restrict to a subfield. return value: Embedded field element. ------------------------------------------------------------------ */ #if defined (__STDC__) FEL zrestrict(FEL a, long subfield) #else FEL zrestrict(a, subfield) FEL a; long subfield; #endif { int i; for (i = 0; embedord[i] != subfield && i < 4; ++i); if (i >= 4) FATAL("NO SUCH SUBFIELD"); return restrict[i][a]; } /* ------------------------------------------------------------------ zaddrow() - Add two rows (row1 += row2) ------------------------------------------------------------------ */ void zaddrow(row1, row2) PTR row1, row2; { register long i; CHECKINIT(); if (zchar == 2) /* characteristic 2 is simple... */ { register long *l1 = (long *) row1; register long *l2 = (long *) row2; for (i = LPR; i != 0; --i) *l1++ ^= *l2++; } else /* any other characteristic */ { register BYTE *p1 = row1; register BYTE *p2 = row2; for (i = BPR; i != 0; --i) { *p1 = tadd[*p1][*p2++]; ++p1; } } } /* ------------------------------------------------------------------ zmulrow() - Multiply row by field element ------------------------------------------------------------------ */ #if defined (__STDC__) void zmulrow(PTR row, FEL mark) #else void zmulrow(row, mark) PTR row; FEL mark; #endif { register BYTE *m; register BYTE *multab; register long i; CHECKFEL(mark); if (mark == F_ZERO) memset(row,0,(size_t)rowsize); else if (mark == F_ONE) return; else { CHECKINIT(); multab = tmult[mark]; m = row; for (i = BPR; i != 0; --i) { *m = multab[*m]; ++m; } } } /* ----------------------------------------------------------------- zmaprow() - multiply a row by a matrix ------------------------------------------------------------------ */ void zmaprow(row, matrix, nor, result) PTR row, matrix, result; long nor; /* number of rows in matrix */ { register long i; register FEL f; BYTE *m = (BYTE *) matrix; CHECKINIT(); memset(result,0,(size_t)rowsize); if (zfl == 2) /* GF(2) is a special case */ { register long *x1 = (long *) matrix; register BYTE *r = (BYTE *) row; register BYTE mask = 0x80; for (i = nor; i != 0; --i) { if ((*r & mask) != 0) { register long *x2 = (long *)result; register long k; for (k = LPR; k; --k) *x2++ ^= *x1++; } else x1 += LPR; /* Skip that row */ if ((mask >>= 1) == 0) { mask = 0x80; ++r; } } } else /* Any other field */ { register BYTE *brow = (BYTE *) row; register int pos = 0; for (i = nor; i != 0; --i) { f = textract[pos][*brow]; if (++pos == MPB) { pos = 0; ++brow; } if (f != F_ZERO) { register BYTE *v = m; register BYTE *r = result; register long k = BPR; if (f == F_ONE) { for (; k != 0; --k) { *r = tadd[*r][*v++]; ++r; } } else { register BYTE *multab = tmult[f]; for (; k != 0; --k) { *r = tadd[*r][multab[*v++]]; ++r; } } } m += rowsize; /* next row */ } } } /* ------------------------------------------------------------------ zpermrow() - multiply a row by a permutation ------------------------------------------------------------------ */ void zpermrow(row, perm, result) PTR row, result; PTR perm; { register FEL f; register long i; register long *p = (long *)perm; for (i = 1; i <= znoc; ++i) { f = zextract(row,i); zinsert(result,*p++,f); } } /* ------------------------------------------------------------------ zfindpiv() - Find first non-zero mark in row return value: column (0 if row is zero) ------------------------------------------------------------------ */ long zfindpiv(row, mark) PTR row; FEL *mark; { register long *l = (long *) row; register long idx; register BYTE *m; CHECKINIT(); for (idx = 0; *l == 0 && idx < LPR; ++idx, ++l); if (*l == 0) return 0; idx = idx * sizeof(long) * MPB + 1; m = (BYTE *)l; while (*m == 0) { ++m; idx += MPB; } idx += tffirst[*m][1]; if (idx <= znoc) { *mark = tffirst[*m][0]; return idx; } return 0; } /* ------------------------------------------------------------------ mtxinit() - Initialize ------------------------------------------------------------------ */ int mtxinit() { zchar = 0; zgen = 0; zfl = 0; /* This forces zsetlen() to read the tables! */ os_init(); return (ZZZVERSION); } /* ------------------------------------------------------------------ zaddmulrow() - row1 += f * row2 return value: none ------------------------------------------------------------------ */ #if defined (__STDC__) void zaddmulrow(PTR row1, PTR row2, FEL f) #else void zaddmulrow(row1, row2, f) PTR row1, row2; FEL f; #endif { register long i; register BYTE *p1, *p2, *multab; CHECKFEL(f); if (f == F_ZERO) return; if (f == F_ONE) { zaddrow(row1,row2); return; } multab = tmult[f]; p1 = row1; p2 = row2; for (i = BPR; i != 0; --i) { *p1 = tadd[*p1][multab[*p2++]]; ++p1; } } /* ------------------------------------------------------------------ zitof(), zftoi() - Convert between long and FEL ------------------------------------------------------------------ */ FEL zitof(l) long l; { register long f; f = l % zfl; if (f < 0) f += zfl; return (FEL) f; } #if defined (__STDC__) long zftoi(FEL f) #else long zftoi(f) FEL f; #endif { return (long) f; }