3 * $Id: gfx.c,v 1.1 2000/10/08 15:49:37 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 /*----- Revision history --------------------------------------------------*
33 * Revision 1.1 2000/10/08 15:49:37 mdw
34 * First glimmerings of binary polynomial arithmetic.
38 /*----- Header files ------------------------------------------------------*/
45 /*----- Main code ---------------------------------------------------------*/
47 /* --- @gfx_add@ --- *
49 * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
50 * @const mpw *av, *avl@ = first addend vector base and limit
51 * @const mpw *bv, *bvl@ = second addend vector base and limit
55 * Use: Adds two %$\gf{2}$% polynomials. This is the same as
59 void gfx_add(mpw
*dv
, mpw
*dvl
,
60 const mpw
*av
, const mpw
*avl
,
61 const mpw
*bv
, const mpw
*bvl
)
66 while (av
< avl
|| bv
< bvl
) {
70 a
= (av
< avl
) ?
*av
++ : 0;
71 b
= (bv
< bvl
) ?
*bv
++ : 0;
78 /* --- @gfx_acc@ --- *
80 * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
81 * @const mpw *av, *avl@ = addend vector base and limit
85 * Use: Adds the addend into the destination. This is considerably
86 * faster than the three-address add call.
89 void gfx_acc(mpw
*dv
, mpw
*dvl
, const mpw
*av
, const mpw
*avl
)
102 /* --- @gfx_accshift@ --- *
104 * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
105 * @const mpw *av, *avl@ = addend vector base and limit
106 * @size_t n@ = number of bits to shift
110 * Use: Shifts the argument left by %$n$% places and adds it to the
111 * destination. This is a primitive used by multiplication and
115 void gfx_accshift(mpw
*dv
, mpw
*dvl
, const mpw
*av
, const mpw
*avl
, size_t n
)
117 size_t c
= n
/ MPW_BITS
;
121 /* --- Sort out the shift amounts --- */
128 gfx_acc(dv
, dvl
, av
, avl
);
133 /* --- Sort out vector lengths --- */
141 /* --- Now do the hard work --- */
145 *dv
++ ^= MPW((y
<< n
) | (x
>> c
));
152 /* --- @gfx_mul@ --- *
154 * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
155 * @const mpw *av, *avl@ = first argument vector base and limit
156 * @const mpw *bv, *bvl@ = second argument vector base and limit
160 * Use: Does multiplication of polynomials over %$\gf{2}$%.
163 void gfx_mul(mpw
*dv
, mpw
*dvl
, const mpw
*av
, const mpw
*avl
,
164 const mpw
*bv
, const mpw
*bvl
)
174 MPSCAN_INITX(&sc
, av
, avl
);
177 while (bv
< bvl
&& dv
< dvl
) {
179 for (v
= av
, vv
= dv
++; v
< avl
&& vv
< dvl
; v
++) {
194 /* --- @gfx_div@ --- *
196 * Arguments: @mpw *qv, *qvl@ = quotient vector base and limit
197 * @mpw *rv, *rvl@ = dividend/remainder vector base and limit
198 * @const mpw *dv, *dvl@ = divisor vector base and limit
202 * Use: Performs division on polynomials over %$\gf{2}$%.
205 void gfx_div(mpw
*qv
, mpw
*qvl
, mpw
*rv
, mpw
*rvl
,
206 const mpw
*dv
, const mpw
*dvl
)
208 size_t dlen
, rlen
, qlen
;
216 assert(((void)"division by zero in gfx_div", dv
< dvl
));
217 MPX_BITS(dbits
, dv
, dvl
);
227 rvm
= 1 << (MPW_BITS
- 1);
228 n
= MPW_BITS
- (dbits
% MPW_BITS
);
238 gfx_accshift(rvd
, rvl
, dv
, dvl
, n
);
242 rvm
= 1 << (MPW_BITS
- 1);
260 /*----- Test rig ----------------------------------------------------------*/
264 #include <mLib/alloc.h>
265 #include <mLib/dstr.h>
266 #include <mLib/quis.h>
267 #include <mLib/testrig.h>
269 #define ALLOC(v, vl, sz) do { \
271 mpw *_vv = xmalloc(MPWS(_sz)); \
272 mpw *_vvl = _vv + _sz; \
277 #define LOAD(v, vl, d) do { \
278 const dstr *_d = (d); \
280 ALLOC(_v, _vl, MPW_RQ(_d->len)); \
281 mpx_loadb(_v, _vl, _d->buf, _d->len); \
286 #define MAX(x, y) ((x) > (y) ? (x) : (y))
288 static void dumpmp(const char *msg
, const mpw
*v
, const mpw
*vl
)
293 fprintf(stderr
, " %08lx", (unsigned long)*--vl
);
297 static int vadd(dstr
*v
)
308 ALLOC(d
, dl
, MAX(al
- a
, bl
- b
) + 1);
310 gfx_add(d
, dl
, a
, al
, b
, bl
);
311 if (!mpx_ueq(d
, dl
, c
, cl
)) {
312 fprintf(stderr
, "\n*** vadd failed\n");
315 dumpmp("expected", c
, cl
);
316 dumpmp(" result", d
, dl
);
320 free(a
); free(b
); free(c
); free(d
);
324 static int vmul(dstr
*v
)
335 ALLOC(d
, dl
, (al
- a
) + (bl
- b
));
337 gfx_mul(d
, dl
, a
, al
, b
, bl
);
338 if (!mpx_ueq(d
, dl
, c
, cl
)) {
339 fprintf(stderr
, "\n*** vmul failed\n");
342 dumpmp("expected", c
, cl
);
343 dumpmp(" result", d
, dl
);
347 free(a
); free(b
); free(c
); free(d
);
351 static int vdiv(dstr
*v
)
360 ALLOC(a
, al
, MPW_RQ(v
[0].len
) + 2); mpx_loadb(a
, al
, v
[0].buf
, v
[0].len
);
364 ALLOC(qq
, qql
, al
- a
);
366 gfx_div(qq
, qql
, a
, al
, b
, bl
);
367 if (!mpx_ueq(qq
, qql
, q
, ql
) ||
368 !mpx_ueq(a
, al
, r
, rl
)) {
369 fprintf(stderr
, "\n*** vdiv failed\n");
370 dumpmp(" divisor", b
, bl
);
371 dumpmp("expect r", r
, rl
);
372 dumpmp("result r", a
, al
);
373 dumpmp("expect q", q
, ql
);
374 dumpmp("result q", qq
, qql
);
378 free(a
); free(b
); free(r
); free(q
); free(qq
);
382 static test_chunk defs
[] = {
383 { "add", vadd
, { &type_hex
, &type_hex
, &type_hex
, 0 } },
384 { "mul", vmul
, { &type_hex
, &type_hex
, &type_hex
, 0 } },
385 { "div", vdiv
, { &type_hex
, &type_hex
, &type_hex
, &type_hex
, 0 } },
389 int main(int argc
, char *argv
[])
391 test_run(argc
, argv
, defs
, SRCDIR
"/tests/gfx");
397 /*----- That's all, folks -------------------------------------------------*/