--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: gfx.c,v 1.1 2000/10/08 15:49:37 mdw Exp $
+ *
+ * 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.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: gfx.c,v $
+ * Revision 1.1 2000/10/08 15:49:37 mdw
+ * First glimmerings of binary polynomial arithmetic.
+ *
+ */
+
+/*----- 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;
+ }
+
+ free(a); free(b); free(c); free(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;
+ }
+
+ free(a); free(b); free(c); free(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;
+ }
+
+ free(a); free(b); free(r); free(q); free(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