+++ /dev/null
-/* -*-c-*-
- *
- * $Id$
- *
- * Low-level arithmetic on binary polynomials
- *
- * (c) 2000 Straylight/Edgeware
- */
-
-/*----- Licensing notice --------------------------------------------------*
- *
- * This file is part of Catacomb.
- *
- * Catacomb is free software; you can redistribute it and/or modify
- * it under the terms of the GNU Library General Public License as
- * published by the Free Software Foundation; either version 2 of the
- * License, or (at your option) any later version.
- *
- * Catacomb is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU Library General Public License for more details.
- *
- * You should have received a copy of the GNU Library General Public
- * License along with Catacomb; if not, write to the Free
- * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- * MA 02111-1307, USA.
- */
-
-/*----- Header files ------------------------------------------------------*/
-
-#include <assert.h>
-
-#include "mpx.h"
-#include "mpscan.h"
-
-/*----- Main code ---------------------------------------------------------*/
-
-/* --- @gfx_add@ --- *
- *
- * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
- * @const mpw *av, *avl@ = first addend vector base and limit
- * @const mpw *bv, *bvl@ = second addend vector base and limit
- *
- * Returns: ---
- *
- * Use: Adds two %$\gf{2}$% polynomials. This is the same as
- * subtraction.
- */
-
-void gfx_add(mpw *dv, mpw *dvl,
- const mpw *av, const mpw *avl,
- const mpw *bv, const mpw *bvl)
-{
- MPX_SHRINK(av, avl);
- MPX_SHRINK(bv, bvl);
-
- while (av < avl || bv < bvl) {
- mpw a, b;
- if (dv >= dvl)
- return;
- a = (av < avl) ? *av++ : 0;
- b = (bv < bvl) ? *bv++ : 0;
- *dv++ = a ^ b;
- }
- if (dv < dvl)
- MPX_ZERO(dv, dvl);
-}
-
-/* --- @gfx_acc@ --- *
- *
- * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
- * @const mpw *av, *avl@ = addend vector base and limit
- *
- * Returns: ---
- *
- * Use: Adds the addend into the destination. This is considerably
- * faster than the three-address add call.
- */
-
-void gfx_acc(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl)
-{
- size_t dlen, alen;
-
- MPX_SHRINK(av, avl);
- dlen = dvl - dv;
- alen = avl - av;
- if (dlen < alen)
- avl = av + dlen;
- while (av < avl)
- *dv++ ^= *av++;
-}
-
-/* --- @gfx_accshift@ --- *
- *
- * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
- * @const mpw *av, *avl@ = addend vector base and limit
- * @size_t n@ = number of bits to shift
- *
- * Returns: ---
- *
- * Use: Shifts the argument left by %$n$% places and adds it to the
- * destination. This is a primitive used by multiplication and
- * division.
- */
-
-void gfx_accshift(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, size_t n)
-{
- size_t c = n / MPW_BITS;
- mpw x = 0, y;
- size_t dlen, alen;
-
- /* --- Sort out the shift amounts --- */
-
- if (dvl - dv < c)
- return;
- dv += c;
- n %= MPW_BITS;
- if (!n) {
- gfx_acc(dv, dvl, av, avl);
- return;
- }
- c = MPW_BITS - n;
-
- /* --- Sort out vector lengths --- */
-
- MPX_SHRINK(av, avl);
- dlen = dvl - dv;
- alen = avl - av;
- if (dlen < alen)
- avl = av + dlen;
-
- /* --- Now do the hard work --- */
-
- while (av < avl) {
- y = *av++;
- *dv++ ^= MPW((y << n) | (x >> c));
- x = y;
- }
- if (dv < dvl)
- *dv++ ^= x >> c;
-}
-
-/* --- @gfx_mul@ --- *
- *
- * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
- * @const mpw *av, *avl@ = first argument vector base and limit
- * @const mpw *bv, *bvl@ = second argument vector base and limit
- *
- * Returns: ---
- *
- * Use: Does multiplication of polynomials over %$\gf{2}$%.
- */
-
-void gfx_mul(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl,
- const mpw *bv, const mpw *bvl)
-{
- mpscan sc;
- const mpw *v;
- mpw *vv;
- mpw z;
- mpd x, y;
-
- MPX_SHRINK(av, avl);
- MPX_SHRINK(bv, bvl);
- MPSCAN_INITX(&sc, av, avl);
- MPX_ZERO(dv, dvl);
-
- while (bv < bvl && dv < dvl) {
- x = 0;
- for (v = av, vv = dv++; v < avl && vv < dvl; v++) {
- z = *bv; y = *v;
- while (z) {
- if (z & 1u) x ^= y;
- z >>= 1; y <<= 1;
- }
- *vv++ ^= MPW(x);
- x >>= MPW_BITS;
- }
- if (vv < dvl)
- *vv++ = MPW(x);
- bv++;
- }
-}
-
-/* --- @gfx_div@ --- *
- *
- * Arguments: @mpw *qv, *qvl@ = quotient vector base and limit
- * @mpw *rv, *rvl@ = dividend/remainder vector base and limit
- * @const mpw *dv, *dvl@ = divisor vector base and limit
- *
- * Returns: ---
- *
- * Use: Performs division on polynomials over %$\gf{2}$%.
- */
-
-void gfx_div(mpw *qv, mpw *qvl, mpw *rv, mpw *rvl,
- const mpw *dv, const mpw *dvl)
-{
- size_t dlen, rlen, qlen;
- size_t dbits;
- mpw *rvv, *rvd;
- unsigned rvm, n, qi;
- mpw q;
-
- MPX_SHRINK(rv, rvl);
- MPX_SHRINK(dv, dvl);
- assert(((void)"division by zero in gfx_div", dv < dvl));
- MPX_BITS(dbits, dv, dvl);
- dlen = dvl - dv;
- rlen = rvl - rv;
- qlen = qvl - qv;
-
- MPX_ZERO(qv, qvl);
- if (dlen > rlen)
- return;
- rvd = rvl - dlen;
- rvv = rvl - 1;
- rvm = 1 << (MPW_BITS - 1);
- n = MPW_BITS - (dbits % MPW_BITS);
- if (n == MPW_BITS)
- n = 0;
- q = 0;
- qi = rvd - rv;
-
- for (;;) {
- q <<= 1;
- if (*rvv & rvm) {
- q |= 1;
- gfx_accshift(rvd, rvl, dv, dvl, n);
- }
- rvm >>= 1;
- if (!rvm) {
- rvm = 1 << (MPW_BITS - 1);
- rvv--;
- }
- if (n)
- n--;
- else {
- if (qi < qlen)
- qv[qi] = q;
- q = 0;
- qi--;
- if (rvd == rv)
- break;
- n = MPW_BITS - 1;
- rvd--;
- }
- }
-}
-
-/*----- Test rig ----------------------------------------------------------*/
-
-#ifdef TEST_RIG
-
-#include <mLib/alloc.h>
-#include <mLib/dstr.h>
-#include <mLib/quis.h>
-#include <mLib/testrig.h>
-
-#define ALLOC(v, vl, sz) do { \
- size_t _sz = (sz); \
- mpw *_vv = xmalloc(MPWS(_sz)); \
- mpw *_vvl = _vv + _sz; \
- (v) = _vv; \
- (vl) = _vvl; \
-} while (0)
-
-#define LOAD(v, vl, d) do { \
- const dstr *_d = (d); \
- mpw *_v, *_vl; \
- ALLOC(_v, _vl, MPW_RQ(_d->len)); \
- mpx_loadb(_v, _vl, _d->buf, _d->len); \
- (v) = _v; \
- (vl) = _vl; \
-} while (0)
-
-#define MAX(x, y) ((x) > (y) ? (x) : (y))
-
-static void dumpmp(const char *msg, const mpw *v, const mpw *vl)
-{
- fputs(msg, stderr);
- MPX_SHRINK(v, vl);
- while (v < vl)
- fprintf(stderr, " %08lx", (unsigned long)*--vl);
- fputc('\n', stderr);
-}
-
-static int vadd(dstr *v)
-{
- mpw *a, *al;
- mpw *b, *bl;
- mpw *c, *cl;
- mpw *d, *dl;
- int ok = 1;
-
- LOAD(a, al, &v[0]);
- LOAD(b, bl, &v[1]);
- LOAD(c, cl, &v[2]);
- ALLOC(d, dl, MAX(al - a, bl - b) + 1);
-
- gfx_add(d, dl, a, al, b, bl);
- if (!mpx_ueq(d, dl, c, cl)) {
- fprintf(stderr, "\n*** vadd failed\n");
- dumpmp(" a", a, al);
- dumpmp(" b", b, bl);
- dumpmp("expected", c, cl);
- dumpmp(" result", d, dl);
- ok = 0;
- }
-
- xfree(a); xfree(b); xfree(c); xfree(d);
- return (ok);
-}
-
-static int vmul(dstr *v)
-{
- mpw *a, *al;
- mpw *b, *bl;
- mpw *c, *cl;
- mpw *d, *dl;
- int ok = 1;
-
- LOAD(a, al, &v[0]);
- LOAD(b, bl, &v[1]);
- LOAD(c, cl, &v[2]);
- ALLOC(d, dl, (al - a) + (bl - b));
-
- gfx_mul(d, dl, a, al, b, bl);
- if (!mpx_ueq(d, dl, c, cl)) {
- fprintf(stderr, "\n*** vmul failed\n");
- dumpmp(" a", a, al);
- dumpmp(" b", b, bl);
- dumpmp("expected", c, cl);
- dumpmp(" result", d, dl);
- ok = 0;
- }
-
- xfree(a); xfree(b); xfree(c); xfree(d);
- return (ok);
-}
-
-static int vdiv(dstr *v)
-{
- mpw *a, *al;
- mpw *b, *bl;
- mpw *q, *ql;
- mpw *r, *rl;
- mpw *qq, *qql;
- int ok = 1;
-
- ALLOC(a, al, MPW_RQ(v[0].len) + 2); mpx_loadb(a, al, v[0].buf, v[0].len);
- LOAD(b, bl, &v[1]);
- LOAD(q, ql, &v[2]);
- LOAD(r, rl, &v[3]);
- ALLOC(qq, qql, al - a);
-
- gfx_div(qq, qql, a, al, b, bl);
- if (!mpx_ueq(qq, qql, q, ql) ||
- !mpx_ueq(a, al, r, rl)) {
- fprintf(stderr, "\n*** vdiv failed\n");
- dumpmp(" divisor", b, bl);
- dumpmp("expect r", r, rl);
- dumpmp("result r", a, al);
- dumpmp("expect q", q, ql);
- dumpmp("result q", qq, qql);
- ok = 0;
- }
-
- xfree(a); xfree(b); xfree(r); xfree(q); xfree(qq);
- return (ok);
-}
-
-static test_chunk defs[] = {
- { "add", vadd, { &type_hex, &type_hex, &type_hex, 0 } },
- { "mul", vmul, { &type_hex, &type_hex, &type_hex, 0 } },
- { "div", vdiv, { &type_hex, &type_hex, &type_hex, &type_hex, 0 } },
- { 0, 0, { 0 } }
-};
-
-int main(int argc, char *argv[])
-{
- test_run(argc, argv, defs, SRCDIR"/tests/gfx");
- return (0);
-}
-
-#endif
-
-/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff