My Project
gfops.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 
4 #include "config.h"
5 
6 
7 #ifdef HAVE_CSTDIO
8 #include <cstdio>
9 #include <cstdlib>
10 #else
11 #include <stdio.h>
12 #include <stdlib.h>
13 #endif
14 #include <string.h>
15 
16 #include "cf_assert.h"
17 
18 #include "cf_defs.h"
19 #include "gf_tabutil.h"
20 #include "cf_util.h"
21 #include "canonicalform.h"
22 #include "variable.h"
23 #include "gfops.h"
24 
25 #ifdef SINGULAR
26 #include "singext.h"
27 #endif
28 
29 
30 const int gf_maxtable = 63001;
31 const int gf_maxbuffer = 200;
32 
33 const int gf_primes_len = 42;
34 #ifndef NOASSERT
35 STATIC_VAR unsigned short gf_primes [] =
36 {
37  2, 3, 5, 7, 11, 13, 17, 19,
38  23, 29, 31, 37, 41, 43, 47, 53,
39  59, 61, 67, 71, 73, 79, 83, 89,
40  97, 101, 103, 107, 109, 113, 127, 131,
41  137, 139, 149, 151, 157, 163, 167, 173,
42  179, 181, 191, 193, 197, 199, 223, 211,
43  227, 229, 233, 239, 241, 251
44 };
45 #endif
46 
47 VAR int gf_q = 0;
48 VAR int gf_p = 0;
49 VAR int gf_n = 0;
50 VAR int gf_q1 = 0;
51 VAR int gf_m1 = 0;
52 VAR char gf_name = 'Z';
53 
54 VAR unsigned short * gf_table = 0;
55 
57 
58 static CanonicalForm intVec2CF ( int degree, int * coeffs, int level )
59 {
60  int i;
62  for ( i = 0; i <= degree; i++ )
63  {
64  result += CanonicalForm( coeffs[ i ] ) * power( Variable( level ), degree - i );
65  }
66  return result;
67 }
68 
70 extern "C" {
71  void set_gftable_dir(char *d){
72  gftable_dir = d;
73  }
74 }
75 
76 static void gf_get_table ( int p, int n )
77 {
78  char buffer[gf_maxbuffer];
79  int q = ipower( p, n );
80 
81  // do not read the table a second time
82  if ( gf_q == q )
83  {
84  return;
85  }
86 
87  if ( gf_table == 0 )
88  gf_table = new unsigned short[gf_maxtable];
89 
90  // try to open file
91  char *gffilename;
92  FILE * inputfile;
93  if (gftable_dir)
94  {
95  sprintf( buffer, "gftables/%d", q);
96  gffilename = (char *)malloc(strlen(gftable_dir) + strlen(buffer) + 1);
97  STICKYASSERT(gffilename,"out of memory");
98  strcpy(gffilename,gftable_dir);
99  strcat(gffilename,buffer);
100  inputfile = fopen( gffilename, "r" );
101  }
102  else
103  {
104  sprintf( buffer, "gftables/%d", q );
105  gffilename = buffer;
106 #ifndef SINGULAR
107  inputfile = fopen( buffer, "r" );
108 #else
109  inputfile = feFopen( buffer, "r" );
110 #endif
111  }
112  if (!inputfile)
113  {
114  fprintf(stderr,"can not open GF(q) addition table: %s\n",gffilename);
115  STICKYASSERT(inputfile, "can not open GF(q) table");
116  }
117 
118  // read ID
119  char * bufptr;
120  char * success;
121  success = fgets( buffer, gf_maxbuffer, inputfile );
122  STICKYASSERT( success, "illegal table (reading ID)" );
123  STICKYASSERT( strcmp( buffer, "@@ factory GF(q) table @@\n" ) == 0, "illegal table" );
124  // read p and n from file
125  int pFile, nFile;
126  success = fgets( buffer, gf_maxbuffer, inputfile );
127  STICKYASSERT( success, "illegal table (reading p and n)" );
128  sscanf( buffer, "%d %d", &pFile, &nFile );
129  STICKYASSERT( p == pFile && n == nFile, "illegal table" );
130  // skip (sic!) factory-representation of mipo
131  // and terminating "; "
132  bufptr = (char *)strchr( buffer, ';' ) + 2;
133  // read simple representation of mipo
134  int i, degree;
135  sscanf( bufptr, "%d", &degree );
136  bufptr = (char *)strchr( bufptr, ' ' ) + 1;
137  int * mipo = NEW_ARRAY(int,degree+1);
138  for ( i = 0; i <= degree; i++ )
139  {
140  sscanf( bufptr, "%d", mipo + i );
141  bufptr = (char *)strchr( bufptr, ' ' ) + 1;
142  }
143 
144  gf_p = p; gf_n = n;
145  gf_q = q; gf_q1 = q-1;
146  gf_mipo = intVec2CF( degree, mipo, 1 );
148 
149  // now for the table
150  int k, digs = gf_tab_numdigits62( gf_q );
151  i = 1;
152  while ( i < gf_q )
153  {
154  success = fgets( buffer, gf_maxbuffer, inputfile );
155  STICKYASSERT( strlen( buffer ) - 1 == (size_t)digs * 30, "illegal table" );
156  bufptr = buffer;
157  k = 0;
158  while ( i < gf_q && k < 30 )
159  {
160  gf_table[i] = convertback62( bufptr, digs );
161  bufptr += digs;
162  if ( gf_table[i] == gf_q )
163  {
164  if ( i == gf_q1 )
165  gf_m1 = 0;
166  else
167  gf_m1 = i;
168  }
169  i++; k++;
170  }
171  }
172  gf_table[0] = gf_table[gf_q1];
173  gf_table[gf_q] = 0;
174 
175  (void)fclose( inputfile );
176 }
177 
178 #ifndef NOASSERT
179 static bool gf_valid_combination ( int p, int n )
180 {
181  int i = 0;
182  while ( i < gf_primes_len && gf_primes[i] != p ) i++;
183  if ( i == gf_primes_len )
184  return false;
185  else
186  {
187  i = n;
188  int a = 1;
189  while ( a < gf_maxtable && i > 0 )
190  {
191  a *= p;
192  i--;
193  }
194  if ( i > 0 || a > gf_maxtable )
195  return false;
196  else
197  return true;
198  }
199 }
200 #endif
201 
202 void gf_setcharacteristic ( int p, int n, char name )
203 {
204  ASSERT( gf_valid_combination( p, n ), "illegal immediate GF(q)" );
205  gf_name = name;
206  gf_get_table( p, n );
207 }
208 
209 long gf_gf2ff ( long a )
210 {
211  if ( gf_iszero( a ) )
212  return 0;
213  else
214  {
215  // starting from z^0=1, step through the table
216  // counting the steps until we hit z^a or z^0
217  // again. since we are working in char(p), the
218  // latter is guaranteed to be fulfilled.
219  long i = 0, ff = 1;
220  do
221  {
222  if ( i == a )
223  return ff;
224  ff++;
225  i = gf_table[i];
226  } while ( i != 0 );
227  return -1;
228  }
229 }
230 
231 int gf_gf2ff ( int a )
232 {
233  if ( gf_iszero( a ) )
234  return 0;
235  else
236  {
237  // starting from z^0=1, step through the table
238  // counting the steps until we hit z^a or z^0
239  // again. since we are working in char(p), the
240  // latter is guaranteed to be fulfilled.
241  int i = 0, ff = 1;
242  do
243  {
244  if ( i == a )
245  return ff;
246  ff++;
247  i = gf_table[i];
248  } while ( i != 0 );
249  return -1;
250  }
251 }
252 
253 bool gf_isff ( long a )
254 {
255  if ( gf_iszero( a ) )
256  return true;
257  else
258  {
259  // z^a in GF(p) iff (z^a)^p-1=1
260  return gf_isone( gf_power( a, gf_p - 1 ) );
261  }
262 }
263 
264 bool gf_isff ( int a )
265 {
266  if ( gf_iszero( a ) )
267  return true;
268  else
269  {
270  // z^a in GF(p) iff (z^a)^p-1=1
271  return gf_isone( gf_power( a, gf_p - 1 ) );
272  }
273 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
int degree(const CanonicalForm &f)
int level(const CanonicalForm &f)
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4078
assertions for Factory
#define STICKYASSERT(expression, message)
Definition: cf_assert.h:64
#define ASSERT(expression, message)
Definition: cf_assert.h:99
factory switches.
#define DELETE_ARRAY(P)
Definition: cf_defs.h:65
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:64
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
factory's main class
Definition: canonicalform.h:86
factory's class for variables
Definition: factory.h:127
return result
Definition: facAbsBiFact.cc:75
CanonicalForm mipo
Definition: facAlgExt.cc:57
char name(const Variable &v)
Definition: factory.h:189
FILE * feFopen(const char *path, const char *mode, char *where, short useWerror, short path_only)
Definition: feFopen.cc:47
int convertback62(char *p, int n)
Definition: gf_tabutil.cc:50
int gf_tab_numdigits62(int q)
Definition: gf_tabutil.cc:12
utility functions to access GF Tables
const int gf_maxtable
Definition: gfops.cc:30
void gf_setcharacteristic(int p, int n, char name)
Definition: gfops.cc:202
VAR int gf_m1
Definition: gfops.cc:51
VAR int gf_q
Definition: gfops.cc:47
VAR int gf_n
Definition: gfops.cc:49
STATIC_VAR char * gftable_dir
Definition: gfops.cc:69
VAR unsigned short * gf_table
Definition: gfops.cc:54
static CanonicalForm intVec2CF(int degree, int *coeffs, int level)
Definition: gfops.cc:58
VAR char gf_name
Definition: gfops.cc:52
const int gf_primes_len
Definition: gfops.cc:33
const int gf_maxbuffer
Definition: gfops.cc:31
void set_gftable_dir(char *d)
Definition: gfops.cc:71
VAR int gf_p
Definition: gfops.cc:48
static void gf_get_table(int p, int n)
Definition: gfops.cc:76
long gf_gf2ff(long a)
Definition: gfops.cc:209
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56
bool gf_isff(long a)
Definition: gfops.cc:253
VAR int gf_q1
Definition: gfops.cc:50
Operations in GF, where GF is a finite field of size less than 2^16 represented by a root of Conway p...
bool gf_isone(int a)
Definition: gfops.h:53
int gf_power(int a, int n)
Definition: gfops.h:222
bool gf_iszero(int a)
Definition: gfops.h:43
#define STATIC_VAR
Definition: globaldefs.h:7
#define INST_VAR
Definition: globaldefs.h:8
#define VAR
Definition: globaldefs.h:5
The main handler for Singular numbers which are suitable for Singular polynomials.
void * malloc(size_t size)
Definition: omalloc.c:85
helper functions for conversion to and from Singular
operations on variables