My Project  debian-1:4.1.1-p2+ds-4build2
ffops.h
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  * @file ffops.h
5  *
6  * operations in a finite prime field F_p.
7  * The largest supported p is 536870909, i.e. the largest prime less than 2^29.
8  *
9 **/
10 
11 #ifndef INCL_FFOPS_H
12 #define INCL_FFOPS_H
13 
14 // #include "config.h"
15 
16 #include "cf_globals.h"
17 #ifdef HAVE_NTL
18 #include <NTL/config.h>
19 #endif
20 
21 /* define type of your compilers 64 bit integer type */
22 #ifndef FACTORY_INT64
23 #if SIZEOF_LONG == 8
24 #define FACTORY_INT64 long int
25 #else
26 #define FACTORY_INT64 long long int
27 #endif
28 #endif
29 
30 extern int ff_prime;
31 extern int ff_halfprime;
32 extern short * ff_invtab;
33 extern bool ff_big;
34 
35 int ff_newinv ( const int );
36 int ff_biginv ( const int );
37 void ff_setprime ( const int );
38 
39 inline int ff_norm ( const int a )
40 {
41  int n = a % ff_prime;
42 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
43  n += (n >> 31) & ff_prime;
44  return n;
45 #else
46  if (n < 0) n += ff_prime;
47  return n;
48 #endif
49 }
50 
51 inline long ff_norm ( const long a )
52 {
53  long n = a % ff_prime;
54 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
55  #if SIZEOF_LONG==8
56  n += (n >> 63) & ff_prime;
57  #else
58  n += (n >> 31) & ff_prime;
59  #endif
60  return n;
61 #else
62  if (n < 0) n += ff_prime;
63  return n;
64 #endif
65 }
66 
67 inline int ff_symmetric( const int a )
68 {
70  return ( a > ff_halfprime ) ? a - ff_prime : a;
71  else
72  return a;
73 }
74 
75 inline long ff_symmetric( const long a )
76 {
78  return ( a > ff_halfprime ) ? a - ff_prime : a;
79  else
80  return a;
81 }
82 
83 inline int ff_longnorm ( const long a )
84 {
85  int n = (int)(a % (long)ff_prime);
86 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
87  n += (n >> 31) & ff_prime;
88  return n;
89 #else
90  if (n < 0) n += ff_prime;
91  return n;
92 #endif
93 }
94 
95 inline int ff_bignorm ( const FACTORY_INT64 a )
96 {
97  int n = (int)(a % (FACTORY_INT64)ff_prime);
98 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
99  n += (n >> 31) & ff_prime;
100  return n;
101 #else
102  if (n < 0) n += ff_prime;
103  return n;
104 #endif
105 }
106 
107 inline int ff_add ( const int a, const int b )
108 {
109  //return ff_norm( a + b );
110 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
111  int r=( a + b );
112  r -= ff_prime;
113  r += (r >> 31) & ff_prime;
114  return r;
115 #else
116  int r=( a + b );
117  if (r >= ff_prime) r -= ff_prime;
118  return r;
119 #endif
120 }
121 
122 inline int ff_sub ( const int a, const int b )
123 {
124  //return ff_norm( a - b );
125 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
126  int r=( a - b );
127  r += (r >> 31) & ff_prime;
128  return r;
129 #else
130  int r=( a - b );
131  if (r < 0) r += ff_prime;
132  return r;
133 #endif
134 }
135 
136 inline int ff_neg ( const int a )
137 {
138  //return ff_norm( -a );
139 // EXPERIMENT
140 #if defined(i386) || defined(__x86_64__) || defined(NTL_AVOID_BRANCHING)
141  int r= -a;
142  r += (r >> 31) & ff_prime;
143  return r;
144 #else
145  return ( a == 0 ? 0 : ff_prime-a );
146 #endif
147 }
148 
149 inline int ff_mul ( const int a, const int b )
150 {
151  if ( ff_big )
152  return ff_bignorm( (FACTORY_INT64)a * (FACTORY_INT64)b );
153  else
154  return ff_longnorm ( (long)a * (long)b );
155 }
156 
157 inline int ff_inv ( const int a )
158 {
159  if ( ff_big )
160  return ff_biginv( a );
161  else {
162  register int b;
163  if ( (b = (int)(ff_invtab[a])) )
164  return b;
165  else
166  return ff_newinv( a );
167  }
168 
169 }
170 
171 inline int ff_div ( const int a, const int b )
172 {
173  return ff_mul( a, ff_inv( b ) );
174 }
175 
176 #endif /* ! INCL_FFOPS_H */
ff_add
int ff_add(const int a, const int b)
Definition: ffops.h:107
ff_big
bool ff_big
Definition: ffops.cc:16
ff_inv
int ff_inv(const int a)
Definition: ffops.h:157
ff_biginv
int ff_biginv(const int)
Definition: ffops.cc:71
b
CanonicalForm b
Definition: cfModGcd.cc:4044
ff_longnorm
int ff_longnorm(const long a)
Definition: ffops.h:83
ff_symmetric
int ff_symmetric(const int a)
Definition: ffops.h:67
cf_globals.h
ff_invtab
short * ff_invtab
Definition: ffops.cc:17
ff_newinv
int ff_newinv(const int)
Definition: ffops.cc:29
ff_prime
int ff_prime
Definition: ffops.cc:14
ff_mul
int ff_mul(const int a, const int b)
Definition: ffops.h:149
ff_setprime
void ff_setprime(const int)
Definition: ffops.cc:19
FACTORY_INT64
#define FACTORY_INT64
Definition: ffops.h:24
ff_bignorm
int ff_bignorm(const FACTORY_INT64 a)
Definition: ffops.h:95
cf_glob_switches
CFSwitches cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.cc:41
ff_norm
int ff_norm(const int a)
Definition: ffops.h:39
SW_SYMMETRIC_FF
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: cf_defs.h:30
ff_halfprime
int ff_halfprime
Definition: ffops.cc:15
ff_sub
int ff_sub(const int a, const int b)
Definition: ffops.h:122
ff_neg
int ff_neg(const int a)
Definition: ffops.h:136
ff_div
int ff_div(const int a, const int b)
Definition: ffops.h:171
CFSwitches::isOn
bool isOn(int s) const
check if 's' is on
Definition: cf_switches.h:55