3 * $Id: gfx.c,v 1.2 2004/04/08 01:36:15 mdw Exp $
5 * Low-level arithmetic on binary polynomials
7 * (c) 2000 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Header files ------------------------------------------------------*/
37 /*----- Main code ---------------------------------------------------------*/
39 /* --- @gfx_add@ --- *
41 * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
42 * @const mpw *av, *avl@ = first addend vector base and limit
43 * @const mpw *bv, *bvl@ = second addend vector base and limit
47 * Use: Adds two %$\gf{2}$% polynomials. This is the same as
51 void gfx_add(mpw
*dv
, mpw
*dvl
,
52 const mpw
*av
, const mpw
*avl
,
53 const mpw
*bv
, const mpw
*bvl
)
58 while (av
< avl
|| bv
< bvl
) {
62 a
= (av
< avl
) ?
*av
++ : 0;
63 b
= (bv
< bvl
) ?
*bv
++ : 0;
70 /* --- @gfx_acc@ --- *
72 * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
73 * @const mpw *av, *avl@ = addend vector base and limit
77 * Use: Adds the addend into the destination. This is considerably
78 * faster than the three-address add call.
81 void gfx_acc(mpw
*dv
, mpw
*dvl
, const mpw
*av
, const mpw
*avl
)
94 /* --- @gfx_accshift@ --- *
96 * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
97 * @const mpw *av, *avl@ = addend vector base and limit
98 * @size_t n@ = number of bits to shift
102 * Use: Shifts the argument left by %$n$% places and adds it to the
103 * destination. This is a primitive used by multiplication and
107 void gfx_accshift(mpw
*dv
, mpw
*dvl
, const mpw
*av
, const mpw
*avl
, size_t n
)
109 size_t c
= n
/ MPW_BITS
;
113 /* --- Sort out the shift amounts --- */
120 gfx_acc(dv
, dvl
, av
, avl
);
125 /* --- Sort out vector lengths --- */
133 /* --- Now do the hard work --- */
137 *dv
++ ^= MPW((y
<< n
) | (x
>> c
));
144 /* --- @gfx_mul@ --- *
146 * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
147 * @const mpw *av, *avl@ = first argument vector base and limit
148 * @const mpw *bv, *bvl@ = second argument vector base and limit
152 * Use: Does multiplication of polynomials over %$\gf{2}$%.
155 void gfx_mul(mpw
*dv
, mpw
*dvl
, const mpw
*av
, const mpw
*avl
,
156 const mpw
*bv
, const mpw
*bvl
)
166 MPSCAN_INITX(&sc
, av
, avl
);
169 while (bv
< bvl
&& dv
< dvl
) {
171 for (v
= av
, vv
= dv
++; v
< avl
&& vv
< dvl
; v
++) {
186 /* --- @gfx_div@ --- *
188 * Arguments: @mpw *qv, *qvl@ = quotient vector base and limit
189 * @mpw *rv, *rvl@ = dividend/remainder vector base and limit
190 * @const mpw *dv, *dvl@ = divisor vector base and limit
194 * Use: Performs division on polynomials over %$\gf{2}$%.
197 void gfx_div(mpw
*qv
, mpw
*qvl
, mpw
*rv
, mpw
*rvl
,
198 const mpw
*dv
, const mpw
*dvl
)
200 size_t dlen
, rlen
, qlen
;
208 assert(((void)"division by zero in gfx_div", dv
< dvl
));
209 MPX_BITS(dbits
, dv
, dvl
);
219 rvm
= 1 << (MPW_BITS
- 1);
220 n
= MPW_BITS
- (dbits
% MPW_BITS
);
230 gfx_accshift(rvd
, rvl
, dv
, dvl
, n
);
234 rvm
= 1 << (MPW_BITS
- 1);
252 /*----- Test rig ----------------------------------------------------------*/
256 #include <mLib/alloc.h>
257 #include <mLib/dstr.h>
258 #include <mLib/quis.h>
259 #include <mLib/testrig.h>
261 #define ALLOC(v, vl, sz) do { \
263 mpw *_vv = xmalloc(MPWS(_sz)); \
264 mpw *_vvl = _vv + _sz; \
269 #define LOAD(v, vl, d) do { \
270 const dstr *_d = (d); \
272 ALLOC(_v, _vl, MPW_RQ(_d->len)); \
273 mpx_loadb(_v, _vl, _d->buf, _d->len); \
278 #define MAX(x, y) ((x) > (y) ? (x) : (y))
280 static void dumpmp(const char *msg
, const mpw
*v
, const mpw
*vl
)
285 fprintf(stderr
, " %08lx", (unsigned long)*--vl
);
289 static int vadd(dstr
*v
)
300 ALLOC(d
, dl
, MAX(al
- a
, bl
- b
) + 1);
302 gfx_add(d
, dl
, a
, al
, b
, bl
);
303 if (!mpx_ueq(d
, dl
, c
, cl
)) {
304 fprintf(stderr
, "\n*** vadd failed\n");
307 dumpmp("expected", c
, cl
);
308 dumpmp(" result", d
, dl
);
312 free(a
); free(b
); free(c
); free(d
);
316 static int vmul(dstr
*v
)
327 ALLOC(d
, dl
, (al
- a
) + (bl
- b
));
329 gfx_mul(d
, dl
, a
, al
, b
, bl
);
330 if (!mpx_ueq(d
, dl
, c
, cl
)) {
331 fprintf(stderr
, "\n*** vmul failed\n");
334 dumpmp("expected", c
, cl
);
335 dumpmp(" result", d
, dl
);
339 free(a
); free(b
); free(c
); free(d
);
343 static int vdiv(dstr
*v
)
352 ALLOC(a
, al
, MPW_RQ(v
[0].len
) + 2); mpx_loadb(a
, al
, v
[0].buf
, v
[0].len
);
356 ALLOC(qq
, qql
, al
- a
);
358 gfx_div(qq
, qql
, a
, al
, b
, bl
);
359 if (!mpx_ueq(qq
, qql
, q
, ql
) ||
360 !mpx_ueq(a
, al
, r
, rl
)) {
361 fprintf(stderr
, "\n*** vdiv failed\n");
362 dumpmp(" divisor", b
, bl
);
363 dumpmp("expect r", r
, rl
);
364 dumpmp("result r", a
, al
);
365 dumpmp("expect q", q
, ql
);
366 dumpmp("result q", qq
, qql
);
370 free(a
); free(b
); free(r
); free(q
); free(qq
);
374 static test_chunk defs
[] = {
375 { "add", vadd
, { &type_hex
, &type_hex
, &type_hex
, 0 } },
376 { "mul", vmul
, { &type_hex
, &type_hex
, &type_hex
, 0 } },
377 { "div", vdiv
, { &type_hex
, &type_hex
, &type_hex
, &type_hex
, 0 } },
381 int main(int argc
, char *argv
[])
383 test_run(argc
, argv
, defs
, SRCDIR
"/tests/gfx");
389 /*----- That's all, folks -------------------------------------------------*/