source: git/factory/gfops.cc @ ee668e

spielwiese
Last change on this file since ee668e was e4fe2b, checked in by Oleksandr Motsak <motsak@…>, 13 years ago
FIX: Fixed huge BUG in cf_gmp.h CHG: starting to cleanup factory
  • Property mode set to 100644
File size: 4.8 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id$ */
3
4#include "config.h"
5
6#ifdef HAVE_CSTDIO
7#include <cstdio>
8#include <cstdlib>
9#else
10#include <stdio.h>
11#include <stdlib.h>
12#endif
13#include <string.h>
14
15#include "cf_assert.h"
16
17#include "cf_defs.h"
18#include "gf_tabutil.h"
19#include "cf_util.h"
20#include "canonicalform.h"
21#include "variable.h"
22#include "gfops.h"
23
24
25const int gf_maxtable = 63001;
26const int gf_maxbuffer = 200;
27
28const int gf_primes_len = 42;
29//static unsigned short gf_primes [] =
30//{
31//      2,   3,   5,   7,  11,  13,  17,  19,
32//     23,  29,  31,  37,  41,  43,  47,  53,
33//     59,  61,  67,  71,  73,  79,  83,  89,
34//     97, 101, 103, 107, 109, 113, 127, 131,
35//    137, 139, 149, 151, 157, 163, 167, 173,
36//    179, 181, 191, 193, 197, 199, 223, 211,
37//    227, 229, 233, 239, 241, 251
38//};
39
40int gf_q = 0;
41int gf_p = 0;
42int gf_n = 0;
43int gf_q1 = 0;
44int gf_m1 = 0;
45char gf_name = 'Z';
46
47unsigned short * gf_table = 0;
48
49CanonicalForm gf_mipo(0);
50
51static CanonicalForm intVec2CF ( int degree, int * coeffs, int level )
52{
53    int i;
54    CanonicalForm result;
55    for ( i = 0; i <= degree; i++ )
56    {
57        result += CanonicalForm( coeffs[ i ] ) * power( Variable( level ), degree - i );
58    }
59    return result;
60}
61
62static void gf_get_table ( int p, int n )
63{
64    char buffer[gf_maxbuffer];
65    int q = ipower( p, n );
66
67    // do not read the table a second time
68    if ( gf_q == q )
69    {
70        return;
71    }
72
73    if ( gf_table == 0 )
74        gf_table = new unsigned short[gf_maxtable];
75
76    // try to open file
77    sprintf( buffer, GFTABLEDIR "/%d", q );
78    FILE * inputfile = fopen( buffer, "r" );
79    STICKYASSERT( inputfile, "can not open GF(q) table" );
80
81    // read ID
82    char * bufptr;
83    char * success;
84    success = fgets( buffer, gf_maxbuffer, inputfile );
85    STICKYASSERT( success, "illegal table (reading ID)" );
86    STICKYASSERT( strcmp( buffer, "@@ factory GF(q) table @@\n" ) == 0, "illegal table" );
87    // read p and n from file
88    int pFile, nFile;
89    success = fgets( buffer, gf_maxbuffer, inputfile );
90    STICKYASSERT( success, "illegal table (reading p and n)" );
91    sscanf( buffer, "%d %d", &pFile, &nFile );
92    STICKYASSERT( p == pFile && n == nFile, "illegal table" );
93    // skip (sic!) factory-representation of mipo
94    // and terminating "; "
95    bufptr = (char *)strchr( buffer, ';' ) + 2;
96    // read simple representation of mipo
97    int i, degree;
98    sscanf( bufptr, "%d", &degree );
99    bufptr = (char *)strchr( bufptr, ' ' ) + 1;
100    int * mipo = new int[degree + 1];
101    for ( i = 0; i <= degree; i++ )
102    {
103        sscanf( bufptr, "%d", mipo + i );
104        bufptr = (char *)strchr( bufptr, ' ' ) + 1;
105    }
106
107    gf_p = p; gf_n = n;
108    gf_q = q; gf_q1 = q-1;
109    gf_mipo = intVec2CF( degree, mipo, 1 );
110    delete [] mipo;
111
112    // now for the table
113    int k, digs = gf_tab_numdigits62( gf_q );
114    i = 1;
115    while ( i < gf_q )
116    {
117        success = fgets( buffer, gf_maxbuffer, inputfile );
118        STICKYASSERT( strlen( buffer ) - 1 == (size_t)digs * 30, "illegal table" );
119        bufptr = buffer;
120        k = 0;
121        while ( i < gf_q && k < 30 )
122        {
123            gf_table[i] = convertback62( bufptr, digs );
124            bufptr += digs;
125            if ( gf_table[i] == gf_q )
126            {
127                if ( i == gf_q1 )
128                    gf_m1 = 0;
129                else
130                    gf_m1 = i;
131            }
132            i++; k++;
133        }
134    }
135    gf_table[0] = gf_table[gf_q1];
136    gf_table[gf_q] = 0;
137
138    (void)fclose( inputfile );
139}
140
141//static bool gf_valid_combination ( int p, int n )
142//{
143//    int i = 0;
144//    while ( i < gf_primes_len && gf_primes[i] != p ) i++;
145//    if ( i == gf_primes_len )
146//        return false;
147//    else
148//    {
149//        i = n;
150//        int a = 1;
151//        while ( a < gf_maxtable && i > 0 )
152//        {
153//            a *= p;
154//            i--;
155//        }
156//        if ( i > 0 || a > gf_maxtable )
157//            return false;
158//        else
159//            return true;
160//    }
161//}
162
163void gf_setcharacteristic ( int p, int n, char name )
164{
165    ASSERT( gf_valid_combination( p, n ), "illegal immediate GF(q)" );
166    gf_name = name;
167    gf_get_table( p, n );
168}
169
170int gf_gf2ff ( int a )
171{
172    if ( gf_iszero( a ) )
173        return 0;
174    else
175    {
176        // starting from z^0=1, step through the table
177        // counting the steps until we hit z^a or z^0
178        // again.  since we are working in char(p), the
179        // latter is guaranteed to be fulfilled.
180        int i = 0, ff = 1;
181        do
182        {
183            if ( i == a )
184                return ff;
185            ff++;
186            i = gf_table[i];
187        } while ( i != 0 );
188        return -1;
189    }
190}
191
192bool gf_isff ( int a )
193{
194    if ( gf_iszero( a ) )
195        return true;
196    else
197    {
198        // z^a in GF(p) iff (z^a)^p-1=1
199        return gf_isone( gf_power( a, gf_p - 1 ) );
200    }
201}
Note: See TracBrowser for help on using the repository browser.