My Project
Loading...
Searching...
No Matches
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
30const int gf_maxtable = 63001;
31const int gf_maxbuffer = 200;
32
33const int gf_primes_len = 42;
34#ifndef NOASSERT
35STATIC_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
47VAR int gf_q = 0;
48VAR int gf_p = 0;
49VAR int gf_n = 0;
50VAR int gf_q1 = 0;
51VAR int gf_m1 = 0;
52VAR char gf_name = 'Z';
53
54VAR unsigned short * gf_table = 0;
55
57
58static CanonicalForm intVec2CF ( int degree, int * coeffs, int level )
59{
60 int i;
62 for ( i = 0; i <= degree; i++ )
63 {
65 }
66 return result;
67}
68
70extern "C" {
71 void set_gftable_dir(char *d){
72 gftable_dir = d;
73 }
74}
75
76static 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
179static 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
202void 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
209long 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
231int 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
253bool 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
264bool 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: variable.h:33
return result
Definition: facAbsBiFact.cc:75
CanonicalForm mipo
Definition: facAlgExt.cc:57
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.
#define malloc
Definition: omAllocFunc.c:12
helper functions for conversion to and from Singular
int name
New type name for int.
Definition: templateForC.h:21
operations on variables