My Project
Loading...
Searching...
No Matches
ffops.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#include <string.h>
8
9#include "cf_assert.h"
10
11#include "cf_defs.h"
12#include "ffops.h"
13
14/// For optimizing if-branches
15#ifdef __GNUC__
16#define LIKELY(expression) (__builtin_expect(!!(expression), 1))
17#define UNLIKELY(expression) (__builtin_expect(!!(expression), 0))
18#else
19#define LIKELY(expression) (expression)
20#define UNLIKELY(expression) (expression)
21#endif
22
23VAR int ff_prime = 0;
25VAR bool ff_big = false;
26VAR short * ff_invtab = new short [32767];
27
28void ff_setprime ( const int p )
29{
30 if ( p != ff_prime )
31 {
32 ff_prime = p;
34 if ( ! ff_big )
35 memset( ff_invtab, 0, ff_prime*sizeof(short) );
36 }
37}
38
39int ff_newinv ( const int a )
40{
41 if (a < 2)
42 return (ff_invtab[a] = a);
43 int p, q, r1, r2, y1, y2;
44 r1 = p = ff_prime;
45 q = r1 / a;
46 y1 = -q;
47 r1 -= a * q;
48 if (r1 == 1)
49 {
50 y1 += p;
51 ff_invtab[y1] = a;
52 return (ff_invtab[a] = y1);
53 }
54 r2 = a;
55 y2 = 1;
56 for (;;)
57 {
58 q = r2 / r1;
59 y2 -= y1 * q;
60 r2 -= r1 * q;
61 if (r2 == 1)
62 {
63 if (y2 < 0)
64 y2 += p;
65 ff_invtab[y2] = a;
66 return (ff_invtab[a] = y2);
67 }
68 q = r1 / r2;
69 y1 -= y2 * q;
70 r1 -= r2 * q;
71 if (r1 == 1)
72 {
73 if (y1 < 0)
74 y1 += p;
75 ff_invtab[y1] = a;
76 return (ff_invtab[a] = y1);
77 }
78 }
79}
80
81int ff_biginv ( const int a )
82{
83 if (UNLIKELY(a < 2))
84 return a;
85 int p, q, r1, r2, y1, y2;
86 r1 = p = ff_prime;
87 q = r1 / a;
88 y1 = -q;
89 r1 -= a * q;
90 if (r1 == 1)
91 return p + y1;
92 r2 = a;
93 y2 = 1;
94 for (;;)
95 {
96 q = r2 / r1;
97 y2 -= y1 * q;
98 r2 -= r1 * q;
99 if (r2 == 1)
100 {
101 if (y2 > 0)
102 return y2;
103 else
104 return p + y2;
105 }
106 q = r1 / r2;
107 y1 -= y2 * q;
108 r1 -= r2 * q;
109 if (r1 == 1)
110 {
111 if (y1 > 0)
112 return y1;
113 else
114 return p + y1;
115 }
116 }
117}
int p
Definition cfModGcd.cc:4086
assertions for Factory
factory switches.
#define UNLIKELY(expression)
Definition ffops.cc:20
int ff_biginv(const int a)
Definition ffops.cc:81
VAR int ff_prime
Definition ffops.cc:23
VAR short * ff_invtab
Definition ffops.cc:26
VAR int ff_halfprime
Definition ffops.cc:24
VAR bool ff_big
Definition ffops.cc:25
void ff_setprime(const int p)
Definition ffops.cc:28
int ff_newinv(const int a)
Definition ffops.cc:39
operations in a finite prime field F_p.
#define VAR
Definition globaldefs.h:5