chiark / gitweb /
utils/mpreducetests.py: Tool to generate unpleasant mpreduce tests.
[catacomb] / gfreduce.c
CommitLineData
ceb3f0c0 1/* -*-c-*-
2 *
a69a3efd 3 * $Id$
ceb3f0c0 4 *
5 * Efficient reduction modulo sparse binary polynomials
6 *
7 * (c) 2004 Straylight/Edgeware
8 */
9
10/*----- Licensing notice --------------------------------------------------*
11 *
12 * This file is part of Catacomb.
13 *
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
18 *
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
23 *
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
27 * MA 02111-1307, USA.
28 */
29
ceb3f0c0 30/*----- Header files ------------------------------------------------------*/
31
32#include <mLib/alloc.h>
33#include <mLib/darray.h>
34#include <mLib/macros.h>
35
36#include "gf.h"
37#include "gfreduce.h"
38#include "gfreduce-exp.h"
39#include "fibrand.h"
40#include "mprand.h"
41
42/*----- Data structures ---------------------------------------------------*/
43
44DA_DECL(instr_v, gfreduce_instr);
45
46/*----- Main code ---------------------------------------------------------*/
47
48/* --- What's going on here? --- *
49 *
50 * Let's face it, @gfx_div@ sucks. It works (I hope), but it's not in any
51 * sense fast. Here, we do efficient reduction modulo sparse polynomials.
52 *
53 * Suppose we have a polynomial @X@ we're trying to reduce mod @P@. If we
54 * take the topmost nonzero word of @X@, call it @w@, then we can eliminate
55 * it by subtracting off @w P x^{k}@ for an appropriate value of @k@. The
56 * trick is in observing that if @P@ is sparse we can do this multiplication
57 * and subtraction efficiently, just by XORing appropriate shifts of @w@ into
58 * @X@.
59 *
60 * The first tricky bit is in working out when to stop. I'll use eight-bit
61 * words to demonstrate what I'm talking about.
62 *
63 * xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
64 * 001ppppp pppppppp pppppppp pppppppp
65 * |<rp>|
66 * |<------------ bp ------------->|
67 * |<------------ nw --------------->|
68 *
69 * The trick of taking whole words off of @X@ stops working when there are
70 * only @nw@ words left. Then we have to mask off the bottom bits of @w@
71 * before continuing.
72 */
73
74/* --- @gfreduce_create@ --- *
75 *
76 * Arguments: @gfreduce *r@ = structure to fill in
77 * @mp *x@ = a (hopefully sparse) polynomial
78 *
79 * Returns: ---
80 *
81 * Use: Initializes a context structure for reduction.
82 */
83
84void gfreduce_create(gfreduce *r, mp *p)
85{
86 instr_v iv = DA_INIT;
f46efa79 87 unsigned long d;
88 unsigned dw;
ceb3f0c0 89 mpscan sc;
90 unsigned long i;
91 gfreduce_instr *ip;
92 unsigned f = 0;
93 size_t w, ww, wi, wl, ll;
94
95 /* --- Sort out the easy stuff --- */
96
97 d = mp_bits(p); assert(d); d--;
98 r->lim = d/MPW_BITS;
99 dw = d%MPW_BITS;
100 if (!dw)
101 r->mask = 0;
102 else {
103 r->mask = MPW(((mpw)-1) << dw);
104 r->lim++;
105 }
106 r->p = mp_copy(p);
107
108 /* --- Stash a new instruction --- */
109
110#define INSTR(op_, arg_) do { \
111 DA_ENSURE(&iv, 1); \
112 DA(&iv)[DA_LEN(&iv)].op = (op_); \
113 DA(&iv)[DA_LEN(&iv)].arg = (arg_); \
114 DA_EXTEND(&iv, 1); \
115} while (0)
116
117#define f_lsr 1u
118
119 w = (d + MPW_BITS - 1)/MPW_BITS;
120 INSTR(GFRI_LOAD, w);
121 wi = DA_LEN(&iv);
122 f = 0;
123 ll = 0;
124 for (i = 0, mp_scan(&sc, p); mp_step(&sc) && i < d; i++) {
125 if (!mp_bit(&sc))
126 continue;
127 ww = (d - i + MPW_BITS - 1)/MPW_BITS;
128 if (ww != w) {
129 wl = DA_LEN(&iv);
130 INSTR(GFRI_STORE, w);
131 if (!ll)
132 ll = DA_LEN(&iv);
133 if (!(f & f_lsr))
134 INSTR(GFRI_LOAD, ww);
135 else {
136 INSTR(GFRI_LOAD, w - 1);
137 for (; wi < wl; wi++) {
138 ip = &DA(&iv)[wi];
139 assert(ip->op == GFRI_LSL);
140 if (ip->arg)
141 INSTR(GFRI_LSR, MPW_BITS - ip->arg);
142 }
143 if (w - 1 != ww) {
144 INSTR(GFRI_STORE, w - 1);
145 INSTR(GFRI_LOAD, ww);
146 }
147 f &= ~f_lsr;
148 }
149 w = ww;
150 wi = DA_LEN(&iv);
151 }
f46efa79 152 INSTR(GFRI_LSL, (MPW_BITS + i - d)%MPW_BITS);
153 if ((MPW_BITS + i - d)%MPW_BITS)
ceb3f0c0 154 f |= f_lsr;
155 }
156 wl = DA_LEN(&iv);
157 INSTR(GFRI_STORE, w);
158 if (!ll)
159 ll = DA_LEN(&iv);
160 if (f & f_lsr) {
161 INSTR(GFRI_LOAD, w - 1);
162 for (; wi < wl; wi++) {
163 ip = &DA(&iv)[wi];
164 assert(ip->op == GFRI_LSL);
165 if (ip->arg)
166 INSTR(GFRI_LSR, MPW_BITS - ip->arg);
167 }
168 INSTR(GFRI_STORE, w - 1);
169 }
170
171#undef INSTR
172
173 r->in = DA_LEN(&iv);
174 r->iv = xmalloc(r->in * sizeof(gfreduce_instr));
175 r->liv = r->iv + ll;
176 memcpy(r->iv, DA(&iv), r->in * sizeof(gfreduce_instr));
177 DA_DESTROY(&iv);
178}
179
180/* --- @gfreduce_destroy@ --- *
181 *
182 * Arguments: @gfreduce *r@ = structure to free
183 *
184 * Returns: ---
185 *
186 * Use: Reclaims the resources from a reduction context.
187 */
188
189void gfreduce_destroy(gfreduce *r)
190{
191 mp_drop(r->p);
192 xfree(r->iv);
193}
194
195/* --- @gfreduce_dump@ --- *
196 *
197 * Arguments: @gfreduce *r@ = structure to dump
198 * @FILE *fp@ = file to dump on
199 *
200 * Returns: ---
201 *
202 * Use: Dumps a reduction context.
203 */
204
205void gfreduce_dump(gfreduce *r, FILE *fp)
206{
207 size_t i;
208
209 fprintf(fp, "poly = "); mp_writefile(r->p, fp, 16);
210 fprintf(fp, "\n lim = %lu; mask = %lx\n",
211 (unsigned long)r->lim, (unsigned long)r->mask);
212 for (i = 0; i < r->in; i++) {
213 static const char *opname[] = { "load", "lsl", "lsr", "store" };
214 assert(r->iv[i].op < N(opname));
215 fprintf(fp, " %s %lu\n",
216 opname[r->iv[i].op],
217 (unsigned long)r->iv[i].arg);
218 }
219}
220
221/* --- @gfreduce_do@ --- *
222 *
223 * Arguments: @gfreduce *r@ = reduction context
224 * @mp *d@ = destination
225 * @mp *x@ = source
226 *
227 * Returns: Destination, @x@ reduced modulo the reduction poly.
228 */
229
230static void run(const gfreduce_instr *i, const gfreduce_instr *il,
231 mpw *v, mpw z)
232{
233 mpw w = 0;
234
235 for (; i < il; i++) {
236 switch (i->op) {
237 case GFRI_LOAD: w = *(v - i->arg); break;
238 case GFRI_LSL: w ^= z << i->arg; break;
239 case GFRI_LSR: w ^= z >> i->arg; break;
240 case GFRI_STORE: *(v - i->arg) = MPW(w); break;
241 default: abort();
242 }
243 }
244}
245
246mp *gfreduce_do(gfreduce *r, mp *d, mp *x)
247{
248 mpw *v, *vl;
249 const gfreduce_instr *il;
250 mpw z;
251
252 /* --- Try to reuse the source's space --- */
253
254 MP_COPY(x);
255 if (d) MP_DROP(d);
256 MP_DEST(x, MP_LEN(x), x->f);
257
258 /* --- Do the reduction --- */
259
260 il = r->iv + r->in;
261 if (MP_LEN(x) >= r->lim) {
262 v = x->v + r->lim;
263 vl = x->vl;
264 while (vl-- > v) {
265 while (*vl) {
266 z = *vl;
267 *vl = 0;
268 run(r->iv, il, vl, z);
269 }
270 }
271 if (r->mask) {
272 while (*vl & r->mask) {
273 z = *vl & r->mask;
274 *vl &= ~r->mask;
275 run(r->iv, il, vl, z);
276 }
277 }
278 }
279
280 /* --- Done --- */
281
282 MP_SHRINK(x);
283 return (x);
284}
285
286/* --- @gfreduce_sqrt@ --- *
287 *
288 * Arguments: @gfreduce *r@ = pointer to reduction context
289 * @mp *d@ = destination
290 * @mp *x@ = some polynomial
291 *
292 * Returns: The square root of @x@ modulo @r->p@, or null.
293 */
294
295mp *gfreduce_sqrt(gfreduce *r, mp *d, mp *x)
296{
297 mp *y = MP_COPY(x);
298 mp *z, *spare = MP_NEW;
299 unsigned long m = mp_bits(r->p) - 1;
300 unsigned long i;
301
302 for (i = 0; i < m - 1; i++) {
303 mp *t = gf_sqr(spare, y);
304 spare = y;
305 y = gfreduce_do(r, t, t);
306 }
307 z = gf_sqr(spare, y);
308 z = gfreduce_do(r, z, z);
309 if (!MP_EQ(x, z)) {
310 mp_drop(y);
311 y = 0;
312 }
313 mp_drop(z);
314 mp_drop(d);
315 return (y);
316}
317
318/* --- @gfreduce_trace@ --- *
319 *
320 * Arguments: @gfreduce *r@ = pointer to reduction context
321 * @mp *x@ = some polynomial
322 *
323 * Returns: The trace of @x@. (%$\Tr(x)=x + x^2 + \cdots + x^{2^{m-1}}$%
324 * if %$x \in \gf{2^m}$%).
325 */
326
327int gfreduce_trace(gfreduce *r, mp *x)
328{
329 mp *y = MP_COPY(x);
330 mp *spare = MP_NEW;
331 unsigned long m = mp_bits(r->p) - 1;
332 unsigned long i;
333 int rc;
334
335 for (i = 0; i < m - 1; i++) {
336 mp *t = gf_sqr(spare, y);
337 spare = y;
338 y = gfreduce_do(r, t, t);
339 y = gf_add(y, y, x);
340 }
a69a3efd 341 rc = !MP_ZEROP(y);
ceb3f0c0 342 mp_drop(spare);
343 mp_drop(y);
344 return (rc);
345}
346
347/* --- @gfreduce_halftrace@ --- *
348 *
349 * Arguments: @gfreduce *r@ = pointer to reduction context
350 * @mp *d@ = destination
351 * @mp *x@ = some polynomial
352 *
353 * Returns: The half-trace of @x@.
354 * (%$\HfTr(x)= x + x^{2^2} + \cdots + x^{2^{m-1}}$%
355 * if %$x \in \gf{2^m}$% with %$m$% odd).
356 */
357
358mp *gfreduce_halftrace(gfreduce *r, mp *d, mp *x)
359{
360 mp *y = MP_COPY(x);
361 mp *spare = MP_NEW;
362 unsigned long m = mp_bits(r->p) - 1;
363 unsigned long i;
364
365 mp_drop(d);
366 for (i = 0; i < m - 1; i += 2) {
367 mp *t = gf_sqr(spare, y);
368 spare = y;
369 y = gfreduce_do(r, t, t);
370 t = gf_sqr(spare, y);
371 spare = y;
372 y = gfreduce_do(r, t, t);
373 y = gf_add(y, y, x);
374 }
375 mp_drop(spare);
376 return (y);
377}
378
379/* --- @gfreduce_quadsolve@ --- *
380 *
381 * Arguments: @gfreduce *r@ = pointer to reduction context
382 * @mp *d@ = destination
383 * @mp *x@ = some polynomial
384 *
385 * Returns: A polynomial @y@ such that %$y^2 + y = x$%, or null.
386 */
387
388mp *gfreduce_quadsolve(gfreduce *r, mp *d, mp *x)
389{
390 unsigned long m = mp_bits(r->p) - 1;
391 mp *t;
392
393 MP_COPY(x);
394 if (m & 1)
395 d = gfreduce_halftrace(r, d, x);
396 else {
397 mp *z, *w, *rho = MP_NEW;
398 mp *spare = MP_NEW;
399 grand *fr = fibrand_create(0);
400 unsigned long i;
401
402 for (;;) {
403 rho = mprand(rho, m, fr, 0);
404 z = MP_ZERO;
405 w = MP_COPY(rho);
406 for (i = 0; i < m - 1; i++) {
407 t = gf_sqr(spare, z); spare = z; z = gfreduce_do(r, t, t);
408 t = gf_sqr(spare, w); spare = w; w = gfreduce_do(r, t, t);
409 t = gf_mul(spare, w, x); t = gfreduce_do(r, t, t); spare = t;
410 z = gf_add(z, z, t);
411 w = gf_add(w, w, rho);
412 }
a69a3efd 413 if (!MP_ZEROP(w))
ceb3f0c0 414 break;
415 MP_DROP(z);
416 MP_DROP(w);
417 }
418 if (d) MP_DROP(d);
419 MP_DROP(w);
420 MP_DROP(spare);
421 MP_DROP(rho);
422 fr->ops->destroy(fr);
423 d = z;
424 }
425
426 t = gf_sqr(MP_NEW, d); t = gfreduce_do(r, t, t); t = gf_add(t, t, d);
427 if (!MP_EQ(t, x)) {
428 MP_DROP(d);
429 d = 0;
430 }
431 MP_DROP(t);
432 MP_DROP(x);
bc985cef 433 if (d) d->v[0] &= ~(mpw)1;
ceb3f0c0 434 return (d);
435}
436
437/* --- @gfreduce_exp@ --- *
438 *
439 * Arguments: @gfreduce *gr@ = pointer to reduction context
440 * @mp *d@ = fake destination
441 * @mp *a@ = base
442 * @mp *e@ = exponent
443 *
444 * Returns: Result, %$a^e \bmod m$%.
445 */
446
447mp *gfreduce_exp(gfreduce *gr, mp *d, mp *a, mp *e)
448{
449 mp *x = MP_ONE;
450 mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW;
451
452 MP_SHRINK(e);
a69a3efd 453 MP_COPY(a);
454 if (MP_ZEROP(e))
ceb3f0c0 455 ;
a69a3efd 456 else {
457 if (MP_NEGP(e))
458 a = gf_modinv(a, a, gr->p);
459 if (MP_LEN(e) < EXP_THRESH)
460 EXP_SIMPLE(x, a, e);
461 else
462 EXP_WINDOW(x, a, e);
463 }
ceb3f0c0 464 mp_drop(d);
a69a3efd 465 mp_drop(a);
ceb3f0c0 466 mp_drop(spare);
467 return (x);
468}
469
470/*----- Test rig ----------------------------------------------------------*/
471
472#ifdef TEST_RIG
473
474#define MP(x) mp_readstring(MP_NEW, #x, 0, 0)
475
476static int vreduce(dstr *v)
477{
478 mp *d = *(mp **)v[0].buf;
479 mp *n = *(mp **)v[1].buf;
480 mp *r = *(mp **)v[2].buf;
481 mp *c;
482 int ok = 1;
483 gfreduce rr;
484
485 gfreduce_create(&rr, d);
486 c = gfreduce_do(&rr, MP_NEW, n);
487 if (!MP_EQ(c, r)) {
488 fprintf(stderr, "\n*** reduction failed\n*** ");
489 gfreduce_dump(&rr, stderr);
490 fprintf(stderr, "\n*** n = "); mp_writefile(n, stderr, 16);
491 fprintf(stderr, "\n*** r = "); mp_writefile(r, stderr, 16);
492 fprintf(stderr, "\n*** c = "); mp_writefile(c, stderr, 16);
493 fprintf(stderr, "\n");
494 ok = 0;
495 }
496 gfreduce_destroy(&rr);
497 mp_drop(n); mp_drop(d); mp_drop(r); mp_drop(c);
498 assert(mparena_count(MPARENA_GLOBAL) == 0);
499 return (ok);
500}
501
502static int vmodexp(dstr *v)
503{
504 mp *p = *(mp **)v[0].buf;
505 mp *g = *(mp **)v[1].buf;
506 mp *x = *(mp **)v[2].buf;
507 mp *r = *(mp **)v[3].buf;
508 mp *c;
509 int ok = 1;
510 gfreduce rr;
511
512 gfreduce_create(&rr, p);
513 c = gfreduce_exp(&rr, MP_NEW, g, x);
514 if (!MP_EQ(c, r)) {
515 fprintf(stderr, "\n*** modexp failed\n*** ");
516 fprintf(stderr, "\n*** p = "); mp_writefile(p, stderr, 16);
517 fprintf(stderr, "\n*** g = "); mp_writefile(g, stderr, 16);
518 fprintf(stderr, "\n*** x = "); mp_writefile(x, stderr, 16);
519 fprintf(stderr, "\n*** c = "); mp_writefile(c, stderr, 16);
520 fprintf(stderr, "\n*** r = "); mp_writefile(r, stderr, 16);
521 fprintf(stderr, "\n");
522 ok = 0;
523 }
524 gfreduce_destroy(&rr);
525 mp_drop(p); mp_drop(g); mp_drop(r); mp_drop(x); mp_drop(c);
526 assert(mparena_count(MPARENA_GLOBAL) == 0);
527 return (ok);
528}
529
530static int vsqrt(dstr *v)
531{
532 mp *p = *(mp **)v[0].buf;
533 mp *x = *(mp **)v[1].buf;
534 mp *r = *(mp **)v[2].buf;
535 mp *c;
536 int ok = 1;
537 gfreduce rr;
538
539 gfreduce_create(&rr, p);
540 c = gfreduce_sqrt(&rr, MP_NEW, x);
541 if (!MP_EQ(c, r)) {
542 fprintf(stderr, "\n*** sqrt failed\n*** ");
543 fprintf(stderr, "\n*** p = "); mp_writefile(p, stderr, 16);
544 fprintf(stderr, "\n*** x = "); mp_writefile(x, stderr, 16);
545 fprintf(stderr, "\n*** c = "); mp_writefile(c, stderr, 16);
546 fprintf(stderr, "\n*** r = "); mp_writefile(r, stderr, 16);
547 fprintf(stderr, "\n");
548 ok = 0;
549 }
550 gfreduce_destroy(&rr);
551 mp_drop(p); mp_drop(r); mp_drop(x); mp_drop(c);
552 assert(mparena_count(MPARENA_GLOBAL) == 0);
553 return (ok);
554}
555
556static int vtr(dstr *v)
557{
558 mp *p = *(mp **)v[0].buf;
559 mp *x = *(mp **)v[1].buf;
560 int r = *(int *)v[2].buf, c;
561 int ok = 1;
562 gfreduce rr;
563
564 gfreduce_create(&rr, p);
565 c = gfreduce_trace(&rr, x);
566 if (c != r) {
567 fprintf(stderr, "\n*** trace failed\n*** ");
568 fprintf(stderr, "\n*** p = "); mp_writefile(p, stderr, 16);
569 fprintf(stderr, "\n*** x = "); mp_writefile(x, stderr, 16);
570 fprintf(stderr, "\n*** c = %d", c);
571 fprintf(stderr, "\n*** r = %d", r);
572 fprintf(stderr, "\n");
573 ok = 0;
574 }
575 gfreduce_destroy(&rr);
576 mp_drop(p); mp_drop(x);
577 assert(mparena_count(MPARENA_GLOBAL) == 0);
578 return (ok);
579}
580
581static int vhftr(dstr *v)
582{
583 mp *p = *(mp **)v[0].buf;
584 mp *x = *(mp **)v[1].buf;
585 mp *r = *(mp **)v[2].buf;
586 mp *c;
587 int ok = 1;
588 gfreduce rr;
589
590 gfreduce_create(&rr, p);
591 c = gfreduce_halftrace(&rr, MP_NEW, x);
592 if (!MP_EQ(c, r)) {
593 fprintf(stderr, "\n*** halftrace failed\n*** ");
594 fprintf(stderr, "\n*** p = "); mp_writefile(p, stderr, 16);
595 fprintf(stderr, "\n*** x = "); mp_writefile(x, stderr, 16);
596 fprintf(stderr, "\n*** c = "); mp_writefile(c, stderr, 16);
597 fprintf(stderr, "\n*** r = "); mp_writefile(r, stderr, 16);
598 fprintf(stderr, "\n");
599 ok = 0;
600 }
601 gfreduce_destroy(&rr);
602 mp_drop(p); mp_drop(r); mp_drop(x); mp_drop(c);
603 assert(mparena_count(MPARENA_GLOBAL) == 0);
604 return (ok);
605}
606
607static int vquad(dstr *v)
608{
609 mp *p = *(mp **)v[0].buf;
610 mp *x = *(mp **)v[1].buf;
611 mp *r = *(mp **)v[2].buf;
612 mp *c;
613 int ok = 1;
614 gfreduce rr;
615
616 gfreduce_create(&rr, p);
617 c = gfreduce_quadsolve(&rr, MP_NEW, x);
618 if (!MP_EQ(c, r)) {
619 fprintf(stderr, "\n*** quadsolve failed\n*** ");
620 fprintf(stderr, "\n*** p = "); mp_writefile(p, stderr, 16);
621 fprintf(stderr, "\n*** x = "); mp_writefile(x, stderr, 16);
622 fprintf(stderr, "\n*** c = "); mp_writefile(c, stderr, 16);
623 fprintf(stderr, "\n*** r = "); mp_writefile(r, stderr, 16);
624 fprintf(stderr, "\n");
625 ok = 0;
626 }
627 gfreduce_destroy(&rr);
628 mp_drop(p); mp_drop(r); mp_drop(x); mp_drop(c);
629 assert(mparena_count(MPARENA_GLOBAL) == 0);
630 return (ok);
631}
632
633static test_chunk defs[] = {
634 { "reduce", vreduce, { &type_mp, &type_mp, &type_mp, 0 } },
635 { "modexp", vmodexp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
636 { "sqrt", vsqrt, { &type_mp, &type_mp, &type_mp, 0 } },
637 { "trace", vtr, { &type_mp, &type_mp, &type_int, 0 } },
638 { "halftrace", vhftr, { &type_mp, &type_mp, &type_mp, 0 } },
639 { "quadsolve", vquad, { &type_mp, &type_mp, &type_mp, 0 } },
640 { 0, 0, { 0 } }
641};
642
643int main(int argc, char *argv[])
644{
645 test_run(argc, argv, defs, SRCDIR"/tests/gfreduce");
646 return (0);
647}
648
649#endif
650
651/*----- That's all, folks -------------------------------------------------*/