1 //==============================================================================================
2 //
3 // This file is part of LiDIA --- a library for computational number theory
4 //
5 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved.
6 //
7 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/
8 //
9 //----------------------------------------------------------------------------------------------
10 //
11 // $Id$
12 //
13 // Author : Franz-Dieter Berger (FDB), Patric Kirsch (PK),
14 // Volker Mueller(VM)
15 // Changes : See CVS log
16 //
17 //==============================================================================================
18
19
20 #ifdef HAVE_CONFIG_H
21 # include "config.h"
22 #endif
23 #include "LiDIA/finite_fields/info_gf2n.h"
24
25
26
27 #ifdef LIDIA_NAMESPACE
28 namespace LiDIA {
29 #endif
30
31
32
33 // ==============================================================
34 // Function: partial_reduce1
35 // ==============================================================
36 //
37 // reduce all array elements with indices >= anzBI to zero
38 // Note: for complete reduction, the coefficients for x^k with
39 // k > extension degree have to be reduced, too.
40 // --> partial_reduce2
41 //
42 // special versions for trinomials, pentinomials
43 // ==============================================================
44
tri_partial_reduce1(udigit * f) const45 void info_gf2n::tri_partial_reduce1(udigit *f) const
46 {
47 register unsigned int i, k, l, w;
48 register udigit h;
49
50 i = 2*anzBI - 1;
51
52 while (i >= anzBI) {
53 h = f[i];
54 if (!h) {
55 i--;
56 continue;
57 }
58
59 k = BITS_PER_LONG*i - degree;
60 f[i--] = static_cast<udigit>(0); // x^degree
61
62 w = k / (BITS_PER_LONG); // x^0
63 l = k % (BITS_PER_LONG);
64
65 if (l != 0) {
66 f[w] ^= (h << l);
67 f[w+1] ^= (h >> (BITS_PER_LONG-l));
68 }
69 else
70 f[w] ^= h;
71
72 w = (k + exp1) / (BITS_PER_LONG);
73 l = (k + exp1) % (BITS_PER_LONG);
74
75 if (l != 0) {
76 f[w] ^= (h << l);
77 f[w+1] ^= (h >> (BITS_PER_LONG-l));
78 }
79 else
80 f[w] ^= h;
81 }
82 }
83
84
85
pent_partial_reduce1(udigit * f) const86 void info_gf2n::pent_partial_reduce1(udigit *f) const
87 {
88 register unsigned int i, k, l, w;
89 register udigit h;
90
91 i = 2*anzBI - 1;
92
93 while (i >= anzBI) {
94 h = f[i];
95 if (!h) {
96 i--;
97 continue;
98 }
99
100 k = BITS_PER_LONG*i - degree;
101 f[i--] = static_cast<udigit>(0); // x^degree
102
103 w = k / (BITS_PER_LONG); // x^0
104 l = k % (BITS_PER_LONG);
105
106 if (l != 0) {
107 f[w] ^= (h << l);
108 f[w+1] ^= (h >> (BITS_PER_LONG-l));
109 }
110 else
111 f[w] ^= h;
112
113 w = (k + exp1) / (BITS_PER_LONG);
114 l = (k + exp1) % (BITS_PER_LONG);
115
116 if (l != 0) {
117 f[w] ^= (h << l);
118 f[w+1] ^= (h >> (BITS_PER_LONG-l));
119 }
120 else
121 f[w] ^= h;
122
123 w = (k + exp2) / (BITS_PER_LONG);
124 l = (k + exp2) % (BITS_PER_LONG);
125
126 if (l != 0) {
127 f[w] ^= (h << l);
128 f[w+1] ^= (h >> (BITS_PER_LONG-l));
129 }
130 else
131 f[w] ^= h;
132
133 w = (k + exp3) / (BITS_PER_LONG);
134 l = (k + exp3) % (BITS_PER_LONG);
135
136 if (l != 0) {
137 f[w] ^= (h << l);
138 f[w+1] ^= (h >> (BITS_PER_LONG-l));
139 }
140 else
141 f[w] ^= h;
142 }
143 }
144
145
146
general_partial_reduce1(udigit * f) const147 void info_gf2n::general_partial_reduce1(udigit *f) const
148 {
149 register unsigned int i, j, k, l, w, s;
150 register udigit h;
151
152 i = 2*anzBI - 1;
153
154 while (i >= anzBI) {
155 h = f[i];
156 if (!h) {
157 i--;
158 continue;
159 }
160
161 k = BITS_PER_LONG*i - degree;
162 f[i] = static_cast<udigit>(0);
163
164 w = k / (BITS_PER_LONG);
165 l = k % (BITS_PER_LONG);
166
167 if (l != 0) {
168 f[w] ^= (h << l);
169 f[w+1] ^= (h >> (BITS_PER_LONG-l));
170 }
171 else
172 f[w] ^= h;
173
174 for (j = 0; j < anz_exponents; j++) {
175 s = k + exponents[j];
176 w = s / (BITS_PER_LONG);
177 l = s % (BITS_PER_LONG);
178
179 if (l != 0) {
180 f[w] ^= (h << l);
181 f[w+1] ^= (h >> (BITS_PER_LONG-l));
182 }
183 else
184 f[w] ^= h;
185 }
186 }
187 }
188
189
190
191 // ==============================================================
192 // Function: partial_reduce2
193 // ==============================================================
194 // we assume that partial_reduce1 has been used and only the
195 // word with index (anzBI-1) may be unreduced
196 //
197 // special versions for trinomials, pentinomials
198 // ==============================================================
199
200
tri_partial_reduce2(udigit * f) const201 void info_gf2n::tri_partial_reduce2(udigit *f) const
202 {
203 register unsigned int l, w, deg, anz;
204 register udigit h;
205
206 anz = anzBI-1;
207 deg = degree % (BITS_PER_LONG);
208 if (deg != 0)
209 h = f[anz] >> deg;
210 else
211 h = f[anz];
212
213 if (h == static_cast<udigit>(0)) // deg(f) < deg(modulus)
214 return;
215
216 f[0] ^= h;
217 f[anz] ^= (h << deg);
218
219 w = exp1 / (BITS_PER_LONG);
220 l = exp1 % (BITS_PER_LONG);
221
222 if (l != 0) {
223 f[w] ^= (h << l);
224 f[w+1] ^= (h >> (BITS_PER_LONG-l));
225 }
226 else
227 f[w] ^= h;
228 }
229
230
231
pent_partial_reduce2(udigit * f) const232 void info_gf2n::pent_partial_reduce2(udigit *f) const
233 {
234 register unsigned int l, w, anz, deg;
235 register udigit h;
236
237 anz = anzBI-1;
238 deg = degree % (BITS_PER_LONG);
239 if (deg != 0)
240 h = f[anz] >> deg;
241 else
242 h = f[anz];
243
244 if (h == static_cast<udigit>(0)) // deg(f) < deg(modulus)
245 return;
246
247 f[0] ^= h;
248 f[anz] ^= (h << deg);
249
250 w = exp1 / (BITS_PER_LONG);
251 l = exp1 % (BITS_PER_LONG);
252
253 if (l != 0) {
254 f[w] ^= (h << l);
255 f[w+1] ^= (h >> (BITS_PER_LONG-l));
256 }
257 else
258 f[w] ^= h;
259
260 w = exp2 / (BITS_PER_LONG);
261 l = exp2 % (BITS_PER_LONG);
262
263 if (l != 0) {
264 f[w] ^= (h << l);
265 f[w+1] ^= (h >> (BITS_PER_LONG-l));
266 }
267 else
268 f[w] ^= h;
269
270 w = exp3 / (BITS_PER_LONG);
271 l = exp3 % (BITS_PER_LONG);
272
273 if (l != 0) {
274 f[w] ^= (h << l);
275 f[w+1] ^= (h >> (BITS_PER_LONG-l));
276 }
277 else
278 f[w] ^= h;
279 }
280
281
282
general_partial_reduce2(udigit * f) const283 void info_gf2n::general_partial_reduce2(udigit *f) const
284 {
285 register unsigned int j, s, l, w, anz, deg;
286 register udigit h;
287
288 anz = anzBI-1;
289 deg = degree % (BITS_PER_LONG);
290 if (deg != 0)
291 h = f[anz] >> deg;
292 else
293 h = f[anz];
294
295
296 if (h == static_cast<udigit>(0)) // deg(f) < deg(modulus)
297 return;
298
299 while (h != 0) {
300 f[0] ^= h;
301 f[anz] ^= (h << deg);
302
303 for (j = 0; j < anz_exponents; j++) {
304 s = exponents[j];
305 w = s / (BITS_PER_LONG);
306 l = s % (BITS_PER_LONG);
307
308 if (l != 0) {
309 f[w] ^= (h << l);
310
311 if (w < anz)
312 f[w+1] ^= (h >> (BITS_PER_LONG-l));
313 }
314 else
315 f[w] ^= h;
316 }
317 h = f[anz] >> deg;
318 }
319 }
320
321
322
323 #ifdef LIDIA_NAMESPACE
324 } // end of namespace LiDIA
325 #endif
326