My Project  debian-1:4.1.2-p1+ds-2
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 /*#ifdef SINGULAR
91  // just copy the table if Singular already read it
92  //printf("init_gf(gf_get_table) q=%d, nfCharQ=%d\n",q,nfCharQ);
93  if ( q == nfCharQ )
94  {
95  gf_p = p; gf_n = n;
96  gf_q = q; gf_q1 = q - 1;
97  gf_m1 = nfM1;
98  gf_mipo = intVec2CF( nfMinPoly[0], nfMinPoly + 1, 1 );
99  (void)memcpy( gf_table, nfPlus1Table, gf_q * sizeof( unsigned short ) );
100  gf_table[gf_q] = 0;
101  return;
102  }
103 #endif*/
104 
105  // try to open file
106  char *gffilename;
107  FILE * inputfile;
108  if (gftable_dir)
109  {
110  sprintf( buffer, "gftables/%d", q);
111  gffilename = (char *)malloc(strlen(gftable_dir) + strlen(buffer) + 1);
112  STICKYASSERT(gffilename,"out of memory");
113  strcpy(gffilename,gftable_dir);
114  strcat(gffilename,buffer);
115  inputfile = fopen( gffilename, "r" );
116  }
117  else
118  {
119 #ifndef SINGULAR
120  sprintf( buffer, "gftables/%d", q );
121  gffilename = buffer;
122  inputfile = fopen( buffer, "r" );
123 #else
124  sprintf( buffer, "gftables/%d", q );
125  gffilename = buffer;
126  inputfile = feFopen( buffer, "r" );
127 #endif
128  }
129  if (!inputfile)
130  {
131  fprintf(stderr,"can not open GF(q) addition table: %s\n",gffilename);
132  STICKYASSERT(inputfile, "can not open GF(q) table");
133  }
134 
135  // read ID
136  char * bufptr;
137  char * success;
138  success = fgets( buffer, gf_maxbuffer, inputfile );
139  STICKYASSERT( success, "illegal table (reading ID)" );
140  STICKYASSERT( strcmp( buffer, "@@ factory GF(q) table @@\n" ) == 0, "illegal table" );
141  // read p and n from file
142  int pFile, nFile;
143  success = fgets( buffer, gf_maxbuffer, inputfile );
144  STICKYASSERT( success, "illegal table (reading p and n)" );
145  sscanf( buffer, "%d %d", &pFile, &nFile );
146  STICKYASSERT( p == pFile && n == nFile, "illegal table" );
147  // skip (sic!) factory-representation of mipo
148  // and terminating "; "
149  bufptr = (char *)strchr( buffer, ';' ) + 2;
150  // read simple representation of mipo
151  int i, degree;
152  sscanf( bufptr, "%d", &degree );
153  bufptr = (char *)strchr( bufptr, ' ' ) + 1;
154  int * mipo = NEW_ARRAY(int,degree+1);
155  for ( i = 0; i <= degree; i++ )
156  {
157  sscanf( bufptr, "%d", mipo + i );
158  bufptr = (char *)strchr( bufptr, ' ' ) + 1;
159  }
160 
161  gf_p = p; gf_n = n;
162  gf_q = q; gf_q1 = q-1;
163  gf_mipo = intVec2CF( degree, mipo, 1 );
165 
166  // now for the table
167  int k, digs = gf_tab_numdigits62( gf_q );
168  i = 1;
169  while ( i < gf_q )
170  {
171  success = fgets( buffer, gf_maxbuffer, inputfile );
172  STICKYASSERT( strlen( buffer ) - 1 == (size_t)digs * 30, "illegal table" );
173  bufptr = buffer;
174  k = 0;
175  while ( i < gf_q && k < 30 )
176  {
177  gf_table[i] = convertback62( bufptr, digs );
178  bufptr += digs;
179  if ( gf_table[i] == gf_q )
180  {
181  if ( i == gf_q1 )
182  gf_m1 = 0;
183  else
184  gf_m1 = i;
185  }
186  i++; k++;
187  }
188  }
189  gf_table[0] = gf_table[gf_q1];
190  gf_table[gf_q] = 0;
191 
192  (void)fclose( inputfile );
193 }
194 
195 #ifndef NOASSERT
196 static bool gf_valid_combination ( int p, int n )
197 {
198  int i = 0;
199  while ( i < gf_primes_len && gf_primes[i] != p ) i++;
200  if ( i == gf_primes_len )
201  return false;
202  else
203  {
204  i = n;
205  int a = 1;
206  while ( a < gf_maxtable && i > 0 )
207  {
208  a *= p;
209  i--;
210  }
211  if ( i > 0 || a > gf_maxtable )
212  return false;
213  else
214  return true;
215  }
216 }
217 #endif
218 
219 void gf_setcharacteristic ( int p, int n, char name )
220 {
221  ASSERT( gf_valid_combination( p, n ), "illegal immediate GF(q)" );
222  gf_name = name;
223  gf_get_table( p, n );
224 }
225 
226 long gf_gf2ff ( long a )
227 {
228  if ( gf_iszero( a ) )
229  return 0;
230  else
231  {
232  // starting from z^0=1, step through the table
233  // counting the steps until we hit z^a or z^0
234  // again. since we are working in char(p), the
235  // latter is guaranteed to be fulfilled.
236  long i = 0, ff = 1;
237  do
238  {
239  if ( i == a )
240  return ff;
241  ff++;
242  i = gf_table[i];
243  } while ( i != 0 );
244  return -1;
245  }
246 }
247 
248 int gf_gf2ff ( int a )
249 {
250  if ( gf_iszero( a ) )
251  return 0;
252  else
253  {
254  // starting from z^0=1, step through the table
255  // counting the steps until we hit z^a or z^0
256  // again. since we are working in char(p), the
257  // latter is guaranteed to be fulfilled.
258  int i = 0, ff = 1;
259  do
260  {
261  if ( i == a )
262  return ff;
263  ff++;
264  i = gf_table[i];
265  } while ( i != 0 );
266  return -1;
267  }
268 }
269 
270 bool gf_isff ( long a )
271 {
272  if ( gf_iszero( a ) )
273  return true;
274  else
275  {
276  // z^a in GF(p) iff (z^a)^p-1=1
277  return gf_isone( gf_power( a, gf_p - 1 ) );
278  }
279 }
280 
281 bool gf_isff ( int a )
282 {
283  if ( gf_iszero( a ) )
284  return true;
285  else
286  {
287  // z^a in GF(p) iff (z^a)^p-1=1
288  return gf_isone( gf_power( a, gf_p - 1 ) );
289  }
290 }
gf_q1
VAR int gf_q1
Definition: gfops.cc:50
gf_table
VAR unsigned short * gf_table
Definition: gfops.cc:54
gf_isone
bool gf_isone(int a)
Definition: gfops.h:53
gf_q
VAR int gf_q
Definition: gfops.cc:47
feFopen
FILE * feFopen(const char *path, const char *mode, char *where, short useWerror, short path_only)
Definition: feFopen.cc:46
set_gftable_dir
void set_gftable_dir(char *d)
Definition: gfops.cc:71
k
int k
Definition: cfEzgcd.cc:92
canonicalform.h
gf_primes
STATIC_VAR unsigned short gf_primes[]
Definition: gfops.cc:35
gf_power
int gf_power(int a, int n)
Definition: gfops.h:222
result
return result
Definition: facAbsBiFact.cc:76
gf_tabutil.h
gf_maxbuffer
const int gf_maxbuffer
Definition: gfops.cc:31
singext.h
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition: cf_defs.h:50
STATIC_VAR
#define STATIC_VAR
Definition: globaldefs.h:7
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
intVec2CF
static CanonicalForm intVec2CF(int degree, int *coeffs, int level)
Definition: gfops.cc:58
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
gf_valid_combination
static bool gf_valid_combination(int p, int n)
Definition: gfops.cc:196
gf_tab_numdigits62
int gf_tab_numdigits62(int q)
Definition: gf_tabutil.cc:12
convertback62
int convertback62(char *p, int n)
Definition: gf_tabutil.cc:50
CanonicalForm
factory's main class
Definition: canonicalform.h:77
gf_name
VAR char gf_name
Definition: gfops.cc:52
gf_isff
bool gf_isff(long a)
Definition: gfops.cc:270
i
int i
Definition: cfEzgcd.cc:125
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
gf_get_table
static void gf_get_table(int p, int n)
Definition: gfops.cc:76
malloc
void * malloc(size_t size)
Definition: omalloc.c:91
cf_defs.h
cf_util.h
VAR
#define VAR
Definition: globaldefs.h:5
coeffs
gfops.h
gf_maxtable
const int gf_maxtable
Definition: gfops.cc:30
gf_setcharacteristic
void gf_setcharacteristic(int p, int n, char name)
Definition: gfops.cc:219
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:26
variable.h
gf_iszero
bool gf_iszero(int a)
Definition: gfops.h:43
gf_p
VAR int gf_p
Definition: gfops.cc:48
STICKYASSERT
#define STICKYASSERT(expression, message)
Definition: cf_assert.h:64
gf_gf2ff
long gf_gf2ff(long a)
Definition: gfops.cc:226
Variable
factory's class for variables
Definition: factory.h:117
INST_VAR
#define INST_VAR
Definition: globaldefs.h:8
gf_n
VAR int gf_n
Definition: gfops.cc:49
name
char name(const Variable &v)
Definition: factory.h:180
gftable_dir
STATIC_VAR char * gftable_dir
Definition: gfops.cc:69
gf_m1
VAR int gf_m1
Definition: gfops.cc:51
cf_assert.h
gf_primes_len
const int gf_primes_len
Definition: gfops.cc:33
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
gf_mipo
INST_VAR CanonicalForm gf_mipo
Definition: gfops.cc:56
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:49