+/* -*-c-*-
+ *
+ * $Id$
+ *
+ * Multiprecision arithmetic
+ *
+ * (c) 2004 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of the Python interface to Catacomb.
+ *
+ * Catacomb/Python is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * Catacomb/Python 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Catacomb/Python; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "catacomb-python.h"
+
+/*----- General utilities -------------------------------------------------*/
+
+PyTypeObject *mp_pytype = 0;
+PyTypeObject *gf_pytype = 0;
+
+mp *mp_frompylong(PyLongObject *l)
+{
+ unsigned long bits;
+ int sz;
+ size_t w;
+ mpd r = 0;
+ int b = 0;
+ int i;
+ mp *x;
+ mpw *p;
+
+ sz = l->ob_size;
+ if (sz < 0) sz = -sz;
+ assert(MPW_BITS >= SHIFT);
+ bits = (unsigned long)sz * SHIFT;
+ w = (bits + MPW_BITS - 1)/MPW_BITS;
+ x = mp_new(w, l->ob_size < 0 ? MP_NEG : 0);
+ p = x->v;
+ for (i = 0; i < sz; i++) {
+ r |= (mpd)l->ob_digit[i] << b;
+ b += SHIFT;
+ while (b >= MPW_BITS) {
+ *p++ = MPW(r);
+ r >>= MPW_BITS;
+ b -= MPW_BITS;
+ }
+ }
+ while (r) {
+ *p++ = MPW(r);
+ r >>= MPW_BITS;
+ }
+ x->vl = p;
+ MP_SHRINK(x);
+ return (x);
+}
+
+PyLongObject *mp_topylong(mp *x)
+{
+ unsigned long bits = mp_bits(x);
+ int sz = (bits + SHIFT - 1)/SHIFT;
+ PyLongObject *l = _PyLong_New(sz);
+ mpd r = 0;
+ int b = 0;
+ mpw *p = x->v;
+ int i = 0;
+
+ assert(MPW_BITS >= SHIFT);
+ while (i < sz && p < x->vl) {
+ r |= *p << b;
+ b += MPW_BITS;
+ while (i < sz && b >= SHIFT) {
+ l->ob_digit[i++] = r & MASK;
+ r >>= SHIFT;
+ b -= SHIFT;
+ }
+ }
+ while (i < sz && r) {
+ l->ob_digit[i++] = r & MASK;
+ r >>= SHIFT;
+ }
+ l->ob_size = (x->f & MP_NEG) ? -sz : sz;
+ return (l);
+}
+
+mp *mp_frompyobject(PyObject *o, int radix)
+{
+ mp *x;
+
+ if ((x = tomp(o)) != 0)
+ return (x);
+ if (PyString_Check(o)) {
+ mptext_stringctx sc;
+ mp *x;
+ sc.buf = PyString_AS_STRING(o);
+ sc.lim = sc.buf + PyString_GET_SIZE(o);
+ x = mp_read(MP_NEW, radix, &mptext_stringops, &sc);
+ if (!x) return (0);
+ if (sc.buf < sc.lim) { MP_DROP(x); return (0); }
+ return (x);
+ }
+ return (0);
+}
+
+PyObject *mp_topystring(mp *x, int radix, const char *xpre,
+ const char *pre, const char *post)
+{
+ int len = mptext_len(x, radix) + 1;
+ mptext_stringctx sc;
+ PyObject *o;
+ size_t xprelen = xpre ? strlen(xpre) : 0;
+ size_t prelen = pre ? strlen(pre) : 0;
+ size_t postlen = post ? strlen(post) : 0;
+ char *p;
+ MP_COPY(x);
+ o = PyString_FromStringAndSize(0, len + 1 + xprelen + prelen + postlen);
+ p = PyString_AS_STRING(o);
+ sc.buf = p;
+ if (xpre) { memcpy(sc.buf, xpre, xprelen); sc.buf += xprelen; }
+ if (MP_NEGP(x)) { *sc.buf++ = '-'; x = mp_neg(x, x); }
+ if (pre) { memcpy(sc.buf, pre, prelen); sc.buf += prelen; }
+ sc.lim = sc.buf + len;
+ mp_write(x, radix, &mptext_stringops, &sc);
+ if (post) { memcpy(sc.buf, post, postlen); sc.buf += postlen; }
+ MP_DROP(x);
+ _PyString_Resize(&o, sc.buf - p);
+ return (o);
+}
+
+PyObject *mp_pywrap(mp *x)
+{
+ mp_pyobj *z = PyObject_New(mp_pyobj, mp_pytype);
+ z->x = x;
+ return ((PyObject *)z);
+}
+
+PyObject *gf_pywrap(mp *x)
+{
+ mp_pyobj *z = PyObject_New(mp_pyobj, gf_pytype);
+ z->x = x;
+ return ((PyObject *)z);
+}
+
+int mp_tolong_checked(mp *x, long *l)
+{
+ static mp *longmin = 0, *longmax = 0;
+ int rc = -1;
+
+ if (!longmax) {
+ longmin = mp_fromlong(MP_NEW, LONG_MIN);
+ longmax = mp_fromlong(MP_NEW, LONG_MAX);
+ }
+ if (MP_CMP(x, <, longmin) || MP_CMP(x, >, longmax))
+ VALERR("mp out of range for int");
+ *l = mp_tolong(x);
+ rc = 0;
+end:
+ return (rc);
+}
+
+/*----- Python interface --------------------------------------------------*/
+
+static void mp_pydealloc(PyObject *o)
+{
+ MP_DROP(MP_X(o));
+ PyObject_DEL(o);
+}
+
+static PyObject *mp_pyrepr(PyObject *o)
+ { return mp_topystring(MP_X(o), 10, "MP(", 0, "L)"); }
+
+static PyObject *mp_pystr(PyObject *o)
+ { return mp_topystring(MP_X(o), 10, 0, 0, 0); }
+
+mp *tomp(PyObject *o)
+{
+ PyObject *l;
+ mp *x;
+
+ if (!o)
+ return (0);
+ else if (MP_PYCHECK(o) || GF_PYCHECK(o))
+ return (MP_COPY(MP_X(o)));
+ else if (FE_PYCHECK(o))
+ return (F_OUT(FE_F(o), MP_NEW, FE_X(o)));
+ else if (PFILT_PYCHECK(o))
+ return (MP_COPY(PFILT_F(o)->m));
+ else if (ECPT_PYCHECK(o)) {
+ ec p = EC_INIT;
+ getecptout(&p, o);
+ x = MP_COPY(p.x);
+ EC_DESTROY(&p);
+ return (x);
+ } else if (GE_PYCHECK(o)) {
+ if ((x = G_TOINT(GE_G(o), MP_NEW, GE_X(o))) == 0)
+ return (0);
+ return (x);
+ } else if (PyInt_Check(o))
+ return (mp_fromlong(MP_NEW, PyInt_AS_LONG(o)));
+ else if ((l = PyNumber_Long(o)) != 0) {
+ x = mp_frompylong((PyLongObject *)l);
+ Py_DECREF(l);
+ return (x);
+ } else {
+ PyErr_Clear();
+ return (0);
+ }
+}
+
+mp *getmp(PyObject *o)
+{
+ mp *x = 0;
+ if (!o) return (0);
+ if ((x = tomp(o)) == 0) {
+ PyErr_Format(PyExc_TypeError, "can't convert %.100s to mp",
+ o->ob_type->tp_name);
+ }
+ return (x);
+}
+
+int convmp(PyObject *o, void *p)
+{
+ mp *x;
+ if ((x = getmp(o)) == 0) return (0);
+ *(mp **)p = x;
+ return (1);
+}
+
+mp *getgf(PyObject *o)
+{
+ mp *x = 0;
+ if (!o) return (0);
+ if ((x = tomp(o)) == 0) {
+ PyErr_Format(PyExc_TypeError, "can't convert %.100s to gf",
+ o->ob_type->tp_name);
+ }
+ return (x);
+}
+
+int convgf(PyObject *o, void *p)
+{
+ mp *x;
+ if ((x = getgf(o)) == 0) return (0);
+ *(mp **)p = x;
+ return (1);
+}
+
+static int mpbinop(PyObject *x, PyObject *y, mp **xx, mp **yy)
+{
+ if ((*xx = tomp(x)) == 0)
+ return (-1);
+ if ((*yy = tomp(y)) == 0) {
+ MP_DROP(*xx);
+ return (-1);
+ }
+ return (0);
+}
+
+#define gf_and mp_and
+#define gf_or mp_or
+#define gf_xor mp_xor
+#define BINOP(pre, name) \
+ static PyObject *pre##_py##name(PyObject *x, PyObject *y) { \
+ mp *xx, *yy, *zz; \
+ if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL; \
+ zz = pre##_##name(MP_NEW, xx, yy); \
+ MP_DROP(xx); MP_DROP(yy); \
+ return (pre##_pywrap(zz)); \
+ }
+BINOP(mp, add)
+BINOP(mp, sub)
+BINOP(mp, mul)
+BINOP(mp, and2c)
+BINOP(mp, or2c)
+BINOP(mp, xor2c)
+BINOP(gf, add)
+BINOP(gf, sub)
+BINOP(gf, mul)
+BINOP(gf, and)
+BINOP(gf, or)
+BINOP(gf, xor)
+#undef BINOP
+
+static mp *mp_abs(mp *d, mp *x)
+{
+ if (MP_NEGP(x))
+ return (mp_neg(d, x));
+ MP_COPY(x);
+ if (d) MP_DROP(d);
+ return (x);
+}
+
+#define UNOP(pre, name) \
+ static PyObject *pre##_py##name(PyObject *x) \
+ { return mp_pywrap(pre##_##name(MP_NEW, MP_X(x))); }
+UNOP(mp, neg)
+UNOP(mp, abs)
+UNOP(mp, not2c)
+#undef UNOP
+
+static PyObject *mp_pyid(PyObject *x) { RETURN_OBJ(x); }
+
+#define gf_lsr mp_lsr
+#define SHIFTOP(pre, name, rname) \
+ static PyObject *pre##_py##name(PyObject *x, PyObject *y) { \
+ mp *xx, *yy; \
+ PyObject *z = 0; \
+ long n; \
+ if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL; \
+ if (mp_tolong_checked(yy, &n)) goto end; \
+ if (n < 0) \
+ z = pre##_pywrap(mp_##rname(MP_NEW, xx, -n)); \
+ else \
+ z = pre##_pywrap(mp_##name(MP_NEW, xx, n)); \
+ end: \
+ MP_DROP(xx); MP_DROP(yy); \
+ return (z); \
+ }
+SHIFTOP(mp, lsl2c, lsr2c)
+SHIFTOP(mp, lsr2c, lsl2c)
+SHIFTOP(gf, lsl, lsr)
+SHIFTOP(gf, lsr, lsl)
+#undef SHIFTOP
+
+#define DIVOP(pre, name, qq, rr, gather) \
+ static PyObject *pre##_py##name(PyObject *x, PyObject *y) { \
+ mp *xx, *yy; \
+ PyObject *z = 0; \
+ INIT_##qq(q) INIT_##rr(r) \
+ if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL; \
+ if (MP_ZEROP(yy)) \
+ ZDIVERR("division by zero"); \
+ pre##_div(ARG_##qq(q), ARG_##rr(r), xx, yy); \
+ z = gather; \
+ end: \
+ MP_DROP(xx); MP_DROP(yy); \
+ return (z); \
+ }
+#define INIT_YES(p) mp *p = MP_NEW;
+#define INIT_NO(p)
+#define ARG_YES(p) &p
+#define ARG_NO(p) 0
+DIVOP(mp, divmod, YES, YES,
+ Py_BuildValue("(NN)", mp_pywrap(q), mp_pywrap(r)))
+DIVOP(mp, div, YES, NO, mp_pywrap(q))
+DIVOP(mp, mod, NO, YES, mp_pywrap(r))
+DIVOP(gf, divmod, YES, YES,
+ Py_BuildValue("(NN)", gf_pywrap(q), gf_pywrap(r)))
+DIVOP(gf, div, YES, NO, gf_pywrap(q))
+DIVOP(gf, mod, NO, YES, gf_pywrap(r))
+#undef INIT_YES
+#undef INIT_NO
+#undef ARG_YES
+#undef ARG_NO
+#undef DIVOP
+
+static mp *mp_modinv_checked(mp *d, mp *x, mp *p)
+{
+ mp *g = MP_NEW;
+ mp_gcd(&g, 0, &d, p, x);
+ if (!MP_EQ(g, MP_ONE)) {
+ MP_DROP(g); MP_DROP(d);
+ PyErr_SetString(PyExc_ZeroDivisionError, "no modular inverse");
+ return (0);
+ }
+ MP_DROP(g); return (d);
+}
+
+static PyObject *mp_pyexp(PyObject *x, PyObject *y, PyObject *z)
+{
+ mp *xx = 0, *yy = 0, *zz = 0;
+ mp *r = 0;
+ PyObject *rc = 0;
+
+ if ((xx = tomp(x)) == 0 || (yy = tomp(y)) == 0 ||
+ (z && z != Py_None && (zz = tomp(z)) == 0)) {
+ mp_drop(xx); mp_drop(yy); mp_drop(zz);
+ RETURN_NOTIMPL;
+ }
+ if (!z || z == Py_None) {
+ if (MP_NEGP(yy)) VALERR("negative exponent");
+ r = mp_exp(MP_NEW, xx, yy);
+ } else {
+ if (!MP_POSP(zz)) VALERR("modulus must be positive");
+ if (MP_NEGP(yy)) {
+ if ((xx = mp_modinv_checked(xx, xx, zz)) == 0) goto end;
+ yy = mp_neg(yy, yy);
+ }
+ if (MP_ODDP(zz)) {
+ mpmont mm;
+ mpmont_create(&mm, zz);
+ r = mpmont_exp(&mm, MP_NEW, xx, yy);
+ mpmont_destroy(&mm);
+ } else {
+ mpbarrett mb;
+ mpbarrett_create(&mb, zz);
+ r = mpbarrett_exp(&mb, MP_NEW, xx, yy);
+ mpbarrett_destroy(&mb);
+ }
+ }
+ rc = mp_pywrap(r);
+end:
+ mp_drop(xx); mp_drop(yy); mp_drop(zz);
+ return (rc);
+}
+
+static mp *gf_modinv_checked(mp *d, mp *x, mp *p)
+{
+ mp *g = MP_NEW;
+ gf_gcd(&g, 0, &d, p, x);
+ if (!MP_EQ(g, MP_ONE)) {
+ MP_DROP(g); MP_DROP(d);
+ PyErr_SetString(PyExc_ZeroDivisionError, "no modular inverse");
+ return (0);
+ }
+ MP_DROP(g); return (d);
+}
+
+#define BASEOP(name, radix, pre) \
+ static PyObject *mp_py##name(PyObject *x) \
+ { return mp_topystring(MP_X(x), radix, 0, pre, 0); }
+BASEOP(oct, 8, "0");
+BASEOP(hex, 16, "0x");
+#undef BASEOP
+
+static int mp_pynonzerop(PyObject *x) { return !MP_ZEROP(MP_X(x)); }
+
+static PyObject *mp_pyint(PyObject *x)
+{
+ long l;
+ if (mp_tolong_checked(MP_X(x), &l)) return (0);
+ return (PyInt_FromLong(l));
+}
+static PyObject *mp_pylong(PyObject *x)
+ { return (PyObject *)mp_topylong(MP_X(x)); }
+static PyObject *mp_pyfloat(PyObject *x)
+{
+ PyObject *l = (PyObject *)mp_topylong(MP_X(x));
+ double f = PyLong_AsDouble(l);
+ Py_DECREF(l);
+ return (PyFloat_FromDouble(f));
+}
+
+#define COERCE(pre, PRE) \
+ static int pre##_pycoerce(PyObject **x, PyObject **y) \
+ { \
+ mp *z; \
+ \
+ if (PRE##_PYCHECK(*y)) { \
+ Py_INCREF(*x); Py_INCREF(*y); \
+ return (0); \
+ } \
+ if ((z = tomp(*y)) != 0) { \
+ Py_INCREF(*x); \
+ *y = pre##_pywrap(z); \
+ return (0); \
+ } \
+ return (1); \
+ }
+COERCE(mp, MP)
+COERCE(gf, GF)
+#undef COERCE
+
+static int mp_pycompare(PyObject *x, PyObject *y)
+ { return mp_cmp(MP_X(x), MP_X(y)); }
+
+static PyObject *mp_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
+{
+ PyObject *x;
+ mp *z;
+ mp_pyobj *zz = 0;
+ int radix = 0;
+ char *kwlist[] = { "x", "radix", 0 };
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:mp", kwlist, &x, &radix))
+ goto end;
+ if (MP_PYCHECK(x)) RETURN_OBJ(x);
+ if (radix < -255 || radix > 62) VALERR("radix out of range");
+ if ((z = mp_frompyobject(x, radix)) == 0) {
+ PyErr_Format(PyExc_TypeError, "can't convert %.100s to mp",
+ x->ob_type->tp_name);
+ goto end;
+ }
+ zz = (mp_pyobj *)ty->tp_alloc(ty, 0);
+ zz->x = z;
+end:
+ return ((PyObject *)zz);
+}
+
+static long mp_pyhash(PyObject *me)
+{
+ long i = mp_tolong(MP_X(me));
+ if (i == -1)
+ i = -2;
+ return (i);
+}
+
+static PyObject *mpmeth_jacobi(PyObject *me, PyObject *arg)
+{
+ mp *y = 0;
+ PyObject *z = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&:jacobi", convmp, &y)) goto end;
+ z = PyInt_FromLong(mp_jacobi(y, MP_X(me)));
+end:
+ if (y) MP_DROP(y);
+ return (z);
+}
+
+#define BITOP(pre, name, c) \
+ static PyObject *pre##meth_##name(PyObject *me, PyObject *arg) \
+ { \
+ int i; \
+ if (!PyArg_ParseTuple(arg, "i:" #name, &i)) return (0); \
+ return (pre##_pywrap(mp_##name##c(MP_NEW, MP_X(me), i))); \
+ }
+BITOP(mp, setbit, 2c);
+BITOP(mp, clearbit, 2c);
+BITOP(gf, setbit, );
+BITOP(gf, clearbit, );
+#undef BITOP
+
+static PyObject *mpmeth_testbit(PyObject *me, PyObject *arg)
+{
+ int i;
+ if (!PyArg_ParseTuple(arg, "i:testbit", &i)) return (0);
+ return (getbool(mp_testbit2c(MP_X(me), i)));
+}
+
+static PyObject *gfmeth_testbit(PyObject *me, PyObject *arg)
+{
+ int i;
+ if (!PyArg_ParseTuple(arg, "i:testbit", &i)) return (0);
+ return (getbool(mp_testbit(MP_X(me), i)));
+}
+
+static PyObject *mpmeth_odd(PyObject *me, PyObject *arg)
+{
+ mp *t;
+ size_t s;
+
+ if (!PyArg_ParseTuple(arg, ":odd")) return (0);
+ t = mp_odd(MP_NEW, MP_X(me), &s);
+ return (Py_BuildValue("(lN)", (long)s, mp_pywrap(t)));
+}
+
+static PyObject *mpmeth_sqr(PyObject *me, PyObject *arg)
+{
+ if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
+ return (mp_pywrap(mp_sqr(MP_NEW, MP_X(me))));
+}
+
+static PyObject *mpmeth_sqrt(PyObject *me, PyObject *arg)
+{
+ if (!PyArg_ParseTuple(arg, ":sqrt")) return (0);
+ if (MP_NEGP(MP_X(me))) VALERR("negative root");
+ return (mp_pywrap(mp_sqrt(MP_NEW, MP_X(me))));
+end:
+ return (0);
+}
+
+static PyObject *mpmeth_gcd(PyObject *me, PyObject *arg)
+{
+ mp *y = 0, *zz = MP_NEW;
+ PyObject *z = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&:gcd", convmp, &y)) goto end;
+ mp_gcd(&zz, 0, 0, MP_X(me), y);
+ z = mp_pywrap(zz);
+end:
+ if (y) MP_DROP(y);
+ return (z);
+}
+
+static PyObject *mpmeth_gcdx(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
+
+ if (!PyArg_ParseTuple(arg, "O&:gcdx", convmp, &yy)) goto end;
+ mp_gcd(&zz, &uu, &vv, MP_X(me), yy);
+ z = Py_BuildValue("(NNN)",
+ mp_pywrap(zz), mp_pywrap(uu), mp_pywrap(vv));
+end:
+ if (yy) MP_DROP(yy);
+ return (z);
+}
+
+static PyObject *mpmeth_modinv(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0, *zz = MP_NEW;
+
+ if (!PyArg_ParseTuple(arg, "O&:modinv", convmp, &yy) ||
+ (zz = mp_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
+ goto end;
+ z = mp_pywrap(zz);
+end:
+ if (yy) MP_DROP(yy);
+ return (z);
+}
+
+static PyObject *mpmeth_tostring(PyObject *me, PyObject *arg, PyObject *kw)
+{
+ int radix = 10;
+ char *kwlist[] = { "radix", 0 };
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "|i:tostring", kwlist, &radix))
+ goto end;
+ if (radix < -255 || radix > 62 || radix == -1 || radix == 0 || radix == 1)
+ VALERR("bad radix");
+ return (mp_topystring(MP_X(me), radix, 0, 0, 0));
+end:
+ return (0);
+}
+
+static PyObject *mpmeth_modsqrt(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0, *zz = MP_NEW;
+
+ if (!PyArg_ParseTuple(arg, "O&:modsqrt", convmp, &yy)) goto end;
+ if ((zz = mp_modsqrt(MP_NEW, yy, MP_X(me))) == 0)
+ VALERR("no modular square root");
+ z = mp_pywrap(zz);
+end:
+ if (yy) MP_DROP(yy);
+ return (z);
+}
+
+#define STOREOP(name, c) \
+ static PyObject *mpmeth_##name(PyObject *me, \
+ PyObject *arg, PyObject *kw) \
+ { \
+ long len = -1; \
+ char *kwlist[] = { "len", 0 }; \
+ PyObject *rc = 0; \
+ \
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "|l:" #name, \
+ kwlist, &len)) \
+ goto end; \
+ if (len < 0) { \
+ len = mp_octets##c(MP_X(me)); \
+ if (!len) len = 1; \
+ } \
+ rc = bytestring_pywrap(0, len); \
+ mp_##name(MP_X(me), PyString_AS_STRING(rc), len); \
+ end: \
+ return (rc); \
+ }
+STOREOP(storel, )
+STOREOP(storeb, )
+STOREOP(storel2c, 2c)
+STOREOP(storeb2c, 2c)
+#undef STOREOP
+
+#define BUFOP(ty, pyty) \
+ static PyObject *meth__##pyty##_frombuf(PyObject *me, PyObject *arg) \
+ { \
+ buf b; \
+ char *p; \
+ int sz; \
+ PyObject *rc = 0; \
+ mp *x; \
+ \
+ if (!PyArg_ParseTuple(arg, "Os#:frombuf", &me, &p, &sz)) goto end; \
+ buf_init(&b, p, sz); \
+ if ((x = buf_getmp(&b)) == 0) VALERR("malformed data"); \
+ rc = Py_BuildValue("(NN)", ty##_pywrap(x), \
+ bytestring_pywrapbuf(&b)); \
+ end: \
+ return (rc); \
+ }
+BUFOP(mp, MP)
+BUFOP(gf, GF)
+#undef BUFOP
+
+static PyObject *mpmeth_tobuf(PyObject *me, PyObject *arg)
+{
+ buf b;
+ PyObject *rc;
+ mp *x;
+ size_t n;
+
+ if (!PyArg_ParseTuple(arg, ":tobuf")) return (0);
+ x = MP_X(me);
+ n = mp_octets(x) + 3;
+ rc = bytestring_pywrap(0, n);
+ buf_init(&b, PyString_AS_STRING(rc), n);
+ buf_putmp(&b, x);
+ assert(BOK(&b));
+ _PyString_Resize(&rc, BLEN(&b));
+ return (rc);
+}
+
+static PyObject *mpmeth_primep(PyObject *me, PyObject *arg, PyObject *kw)
+{
+ grand *r = &rand_global;
+ char *kwlist[] = { "rng", 0 };
+ PyObject *rc = 0;
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "|O&", kwlist, convgrand, &r))
+ goto end;
+ rc = getbool(pgen_primep(MP_X(me), r));
+end:
+ return (rc);
+}
+
+static PyObject *mpget_nbits(PyObject *me, void *hunoz)
+ { return (PyInt_FromLong(mp_bits(MP_X(me)))); }
+
+static PyObject *mpget_noctets(PyObject *me, void *hunoz)
+ { return (PyInt_FromLong(mp_octets(MP_X(me)))); }
+
+static PyObject *mpget_noctets2c(PyObject *me, void *hunoz)
+ { return (PyInt_FromLong(mp_octets2c(MP_X(me)))); }
+
+static PyGetSetDef mp_pygetset[] = {
+#define GETSETNAME(op, func) mp##op##_##func
+ GET (nbits, "X.nbits -> bit length of X")
+ GET (noctets, "X.noctets -> octet length of X")
+ GET (noctets2c, "X.noctets2c -> two's complement octet length of X")
+#undef GETSETNAME
+ { 0 }
+};
+
+static PyMethodDef mp_pymethods[] = {
+#define METHNAME(func) mpmeth_##func
+ METH (jacobi, "X.jacobi(Y) -> Jacobi symbol (Y/X) (NB inversion!)")
+ METH (setbit, "X.setbit(N) -> X with bit N set")
+ METH (clearbit, "X.clearbit(N) -> X with bit N clear")
+ METH (testbit, "X.testbit(N) -> true/false if bit N set/clear in X")
+ METH (odd, "X.odd() -> S, T where X = 2^S T with T odd")
+ METH (sqr, "X.sqr() -> X^2")
+ METH (sqrt, "X.sqrt() -> largest integer <= sqrt(X)")
+ METH (gcd, "X.gcd(Y) -> gcd(X, Y)")
+ METH (gcdx,
+ "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
+ METH (modinv, "X.modinv(Y) -> multiplicative inverse of Y mod X")
+ METH (modsqrt, "X.modsqrt(Y) -> square root of Y mod X, if X prime")
+ KWMETH(primep, "X.primep(rng = rand) -> true/false if X is prime")
+ KWMETH(tostring, "X.tostring(radix = 10) -> STR")
+ KWMETH(storel, "X.storel(len = -1) -> little-endian bytes")
+ KWMETH(storeb, "X.storeb(len = -1) -> big-endian bytes")
+ KWMETH(storel2c,
+ "X.storel2c(len = -1) -> little-endian bytes, two's complement")
+ KWMETH(storeb2c,
+ "X.storeb2c(len = -1) -> big-endian bytes, two's complement")
+ METH (tobuf, "X.tobuf() -> buffer format")
+#undef METHNAME
+ { 0 }
+};
+
+static PyNumberMethods mp_pynumber = {
+ mp_pyadd, /* @nb_add@ */
+ mp_pysub, /* @nb_subtract@ */
+ mp_pymul, /* @nb_multiply@ */
+ 0, /* @nb_divide@ */
+ mp_pymod, /* @nb_remainder@ */
+ mp_pydivmod, /* @nb_divmod@ */
+ mp_pyexp, /* @nb_power@ */
+ mp_pyneg, /* @nb_negative@ */
+ mp_pyid, /* @nb_positive@ */
+ mp_pyabs, /* @nb_absolute@ */
+ mp_pynonzerop, /* @nb_nonzero@ */
+ mp_pynot2c, /* @nb_invert@ */
+ mp_pylsl2c, /* @nb_lshift@ */
+ mp_pylsr2c, /* @nb_rshift@ */
+ mp_pyand2c, /* @nb_and@ */
+ mp_pyxor2c, /* @nb_xor@ */
+ mp_pyor2c, /* @nb_or@ */
+ mp_pycoerce, /* @nb_coerce@ */
+ mp_pyint, /* @nb_int@ */
+ mp_pylong, /* @nb_long@ */
+ mp_pyfloat, /* @nb_float@ */
+ mp_pyoct, /* @nb_oct@ */
+ mp_pyhex, /* @nb_hex@ */
+
+ 0, /* @nb_inplace_add@ */
+ 0, /* @nb_inplace_subtract@ */
+ 0, /* @nb_inplace_multiply@ */
+ 0, /* @nb_inplace_divide@ */
+ 0, /* @nb_inplace_remainder@ */
+ 0, /* @nb_inplace_power@ */
+ 0, /* @nb_inplace_lshift@ */
+ 0, /* @nb_inplace_rshift@ */
+ 0, /* @nb_inplace_and@ */
+ 0, /* @nb_inplace_xor@ */
+ 0, /* @nb_inplace_or@ */
+
+ mp_pydiv, /* @nb_floor_divide@ */
+ 0, /* @nb_true_divide@ */
+ 0, /* @nb_inplace_floor_divide@ */
+ 0, /* @nb_inplace_true_divide@ */
+};
+
+static PyTypeObject mp_pytype_skel = {
+ PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
+ "catacomb.MP", /* @tp_name@ */
+ sizeof(mp_pyobj), /* @tp_basicsize@ */
+ 0, /* @tp_itemsize@ */
+
+ mp_pydealloc, /* @tp_dealloc@ */
+ 0, /* @tp_print@ */
+ 0, /* @tp_getattr@ */
+ 0, /* @tp_setattr@ */
+ mp_pycompare, /* @tp_compare@ */
+ mp_pyrepr, /* @tp_repr@ */
+ &mp_pynumber, /* @tp_as_number@ */
+ 0, /* @tp_as_sequence@ */
+ 0, /* @tp_as_mapping@ */
+ mp_pyhash, /* @tp_hash@ */
+ 0, /* @tp_call@ */
+ mp_pystr, /* @tp_str@ */
+ 0, /* @tp_getattro@ */
+ 0, /* @tp_setattro@ */
+ 0, /* @tp_as_buffer@ */
+ Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
+ Py_TPFLAGS_CHECKTYPES |
+ Py_TPFLAGS_BASETYPE,
+
+ /* @tp_doc@ */
+"Multiprecision integers, similar to `long' but more efficient and\n\
+versatile. Support all the standard arithmetic operations.\n\
+\n\
+Constructor mp(X, radix = R) attempts to convert X to an `mp'. If\n\
+X is a string, it's read in radix-R form, or we look for a prefix\n\
+if R = 0. Other acceptable things are ints and longs.\n\
+\n\
+Notes:\n\
+\n\
+ * Use `//' for division. MPs don't have `/' division.",
+
+ 0, /* @tp_traverse@ */
+ 0, /* @tp_clear@ */
+ 0, /* @tp_richcompare@ */
+ 0, /* @tp_weaklistoffset@ */
+ 0, /* @tp_iter@ */
+ 0, /* @tp_iternexr@ */
+ mp_pymethods, /* @tp_methods@ */
+ 0, /* @tp_members@ */
+ mp_pygetset, /* @tp_getset@ */
+ 0, /* @tp_base@ */
+ 0, /* @tp_dict@ */
+ 0, /* @tp_descr_get@ */
+ 0, /* @tp_descr_set@ */
+ 0, /* @tp_dictoffset@ */
+ 0, /* @tp_init@ */
+ PyType_GenericAlloc, /* @tp_alloc@ */
+ mp_pynew, /* @tp_new@ */
+ _PyObject_Del, /* @tp_free@ */
+ 0 /* @tp_is_gc@ */
+};
+
+static PyObject *meth__MP_fromstring(PyObject *me,
+ PyObject *arg, PyObject *kw)
+{
+ int r = 0;
+ char *p;
+ int len;
+ PyObject *z = 0;
+ mp *zz;
+ mptext_stringctx sc;
+ char *kwlist[] = { "class", "x", "radix", 0 };
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
+ kwlist, &me, &p, &len, &r))
+ goto end;
+ if (r < -255 || r > 62) VALERR("radix out of range");
+ sc.buf = p; sc.lim = p + len;
+ if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0)
+ SYNERR("bad integer");
+ z = Py_BuildValue("(Ns#)", mp_pywrap(zz), sc.buf, (int)(sc.lim - sc.buf));
+end:
+ return (z);
+}
+
+static PyObject *meth__MP_product(PyObject *me, PyObject *arg)
+{
+ mpmul m;
+ PyObject *q, *i;
+ mp *x;
+
+ if (PyTuple_Size(arg) != 2) {
+ i = PyObject_GetIter(arg);
+ PyIter_Next(i);
+ } else {
+ if ((q = PyTuple_GetItem(arg, 1)) == 0) return (0);
+ if ((i = PyObject_GetIter(q)) == 0) {
+ PyErr_Clear(); /* that's ok */
+ i = PyObject_GetIter(arg);
+ }
+ }
+ if (!i) return (0);
+ mpmul_init(&m);
+ while ((q = PyIter_Next(i)) != 0) {
+ x = getmp(q); Py_DECREF(q); if (!x) {
+ MP_DROP(mpmul_done(&m));
+ Py_DECREF(i);
+ return (0);
+ }
+ mpmul_add(&m, x);
+ MP_DROP(x);
+ }
+ x = mpmul_done(&m);
+ Py_DECREF(i);
+ return (mp_pywrap(x));
+}
+
+#define LOADOP(pre, py, name) \
+ static PyObject *meth__##py##_##name(PyObject *me, PyObject *arg) \
+ { \
+ char *p; \
+ int len; \
+ if (!PyArg_ParseTuple(arg, "Os#:" #name, &me, &p, &len)) return (0); \
+ return (pre##_pywrap(mp_##name(MP_NEW, p, len))); \
+ }
+LOADOP(mp, MP, loadl)
+LOADOP(mp, MP, loadb)
+LOADOP(mp, MP, loadl2c)
+LOADOP(mp, MP, loadb2c)
+LOADOP(gf, GF, loadl)
+LOADOP(gf, GF, loadb)
+#undef LOADOP
+
+/*----- Montgomery reduction ----------------------------------------------*/
+
+typedef struct mpmont_pyobj {
+ PyObject_HEAD
+ mpmont mm;
+} mpmont_pyobj;
+
+#define MPMONT_PY(o) (&((mpmont_pyobj *)(o))->mm)
+
+static PyObject *mmmeth_int(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0;
+ mpmont *mm = MPMONT_PY(me);
+
+ if (!PyArg_ParseTuple(arg, "O&:in", convmp, &yy))
+ goto end;
+ mp_div(0, &yy, yy, mm->m);
+ z = mp_pywrap(mpmont_mul(mm, MP_NEW, yy, mm->r2));
+end:
+ if (yy) MP_DROP(yy);
+ return (z);
+}
+
+static PyObject *mmmeth_mul(PyObject *me, PyObject *arg)
+{
+ PyObject *rc = 0;
+ mp *yy = 0, *zz = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&O&:mul", convmp, &yy, convmp, &zz))
+ goto end;
+ rc = mp_pywrap(mpmont_mul(MPMONT_PY(me), MP_NEW, yy, zz));
+end:
+ if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
+ return (rc);
+}
+
+static PyObject *mmmeth_exp(PyObject *me, PyObject *arg)
+{
+ PyObject *rc = 0;
+ mp *yy = 0, *zz = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
+ goto end;
+ if (MP_NEGP(zz)) {
+ if ((yy = mp_modinv_checked(yy, yy, MPMONT_PY(me)->m)) == 0) goto end;
+ zz = mp_neg(zz, zz);
+ }
+ rc = mp_pywrap(mpmont_exp(MPMONT_PY(me), MP_NEW, yy, zz));
+end:
+ if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
+ return (rc);
+}
+
+static PyObject *mmmeth_expr(PyObject *me, PyObject *arg)
+{
+ PyObject *rc = 0;
+ mp *yy = 0, *zz = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&O&:expr", convmp, &yy, convmp, &zz))
+ goto end;
+ if (MP_NEGP(zz)) {
+ yy = mpmont_reduce(MPMONT_PY(me), yy, yy);
+ if ((yy = mp_modinv_checked(yy, yy, MPMONT_PY(me)->m)) == 0) goto end;
+ yy = mpmont_mul(MPMONT_PY(me), yy, yy, MPMONT_PY(me)->r2);
+ zz = mp_neg(zz, zz);
+ }
+ rc = mp_pywrap(mpmont_expr(MPMONT_PY(me), MP_NEW, yy, zz));
+end:
+ if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
+ return (rc);
+}
+
+static PyObject *mm_mexpr_id(PyObject *me)
+ { return mp_pywrap(MP_COPY(MPMONT_PY(me)->r)); }
+
+static int mm_mexpr_fill(void *p, PyObject *me, PyObject *x, PyObject *y)
+{
+ mp *xx = 0, *yy = 0;
+ mp_expfactor *f = p;
+ mpmont *mm = MPMONT_PY(me);
+
+ if ((xx = getmp(x)) == 0 || (yy = getmp(y)) == 0)
+ goto fail;
+ if (MP_NEGP(yy)) {
+ xx = mpmont_reduce(mm, xx, xx);
+ if ((xx = mp_modinv_checked(xx, xx, yy)) == 0)
+ goto fail;
+ xx = mpmont_mul(mm, xx, xx, mm->r2);
+ yy = mp_neg(yy, yy);
+ }
+ f->base = xx;
+ f->exp = yy;
+ return (0);
+
+fail:
+ mp_drop(xx); mp_drop(yy);
+ return (-1);
+}
+
+static PyObject *mm_mexpr(PyObject *me, void *v, int n)
+ { return mp_pywrap(mpmont_mexpr(MPMONT_PY(me), MP_NEW, v, n)); }
+
+static void mp_mexp_drop(void *p)
+{
+ mp_expfactor *f = p;
+ mp_drop(f->base);
+ mp_drop(f->exp);
+}
+
+static PyObject *mmmeth_mexpr(PyObject *me, PyObject *arg)
+{
+ return mexp_common(me, arg, sizeof(mp_expfactor),
+ mm_mexpr_id, mm_mexpr_fill, mm_mexpr, mp_mexp_drop);
+}
+
+static PyObject *mp_mexp_id(PyObject *me)
+ { return mp_pywrap(MP_ONE); }
+
+static int mp_mexp_fill(void *p, PyObject *me, PyObject *x, PyObject *y)
+{
+ mp *xx = 0, *yy = 0;
+ mp_expfactor *f = p;
+
+ if ((xx = getmp(x)) == 0 || (yy = getmp(y)) == 0)
+ goto fail;
+ if (MP_NEGP(yy)) {
+ if ((xx = mp_modinv_checked(xx, xx, yy)) == 0)
+ goto fail;
+ yy = mp_neg(yy, yy);
+ }
+ f->base = xx;
+ f->exp = yy;
+ return (0);
+
+fail:
+ mp_drop(xx); mp_drop(yy);
+ return (-1);
+}
+
+static PyObject *mm_mexp(PyObject *me, void *v, int n)
+ { return mp_pywrap(mpmont_mexp(MPMONT_PY(me), MP_NEW, v, n)); }
+
+static PyObject *mmmeth_mexp(PyObject *me, PyObject *arg)
+{
+ return mexp_common(me, arg, sizeof(mp_expfactor),
+ mp_mexp_id, mp_mexp_fill, mm_mexp, mp_mexp_drop);
+}
+
+#define mmmeth_ext mmmeth_reduce
+static PyObject *mmmeth_reduce(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&", convmp, &yy)) goto end;
+ z = mp_pywrap(mpmont_reduce(MPMONT_PY(me), MP_NEW, yy));
+end:
+ return (z);
+}
+
+static void mpmont_pydealloc(PyObject *me)
+{
+ mpmont_destroy(MPMONT_PY(me));
+ PyObject_DEL(me);
+}
+
+static PyObject *mpmont_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
+{
+ mpmont_pyobj *mm = 0;
+ char *kwlist[] = { "m", 0 };
+ mp *xx = 0;
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
+ goto end;
+ if (!MP_POSP(xx) || !MP_ODDP(xx)) VALERR("m must be positive and odd");
+ mm = (mpmont_pyobj *)ty->tp_alloc(ty, 0);
+ mpmont_create(&mm->mm, xx);
+end:
+ if (xx) MP_DROP(xx);
+ return ((PyObject *)mm);
+}
+
+static PyObject *mmget_m(PyObject *me, void *hunoz)
+ { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->m))); }
+
+static PyObject *mmget_r(PyObject *me, void *hunoz)
+ { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r))); }
+
+static PyObject *mmget_r2(PyObject *me, void *hunoz)
+ { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r2))); }
+
+static PyGetSetDef mpmont_pygetset[] = {
+#define GETSETNAME(op, name) mm##op##_##name
+ GET (m, "M.m -> modulus for reduction")
+ GET (r, "M.r -> multiplicative identity")
+ GET (r2, "M.r2 -> M.r^2, Montgomerization factor")
+#undef GETSETNAME
+ { 0 }
+};
+
+static PyMethodDef mpmont_pymethods[] = {
+#define METHNAME(name) mmmeth_##name
+ METH (int, "M.out(X) -> XR")
+ METH (mul, "M.mul(XR, YR) -> ZR where Z = X Y")
+ METH (expr, "M.expr(XR, N) -> ZR where Z = X^N mod M.m")
+ METH (mexpr, "\
+B.mexp([(XR0, N0), (XR1, N1), ...]) = ZR where Z = X0^N0 X1^N1 mod B.m\n\
+\t(the list may be flattened if this more convenient.)")
+ METH (reduce, "M.reduce(XR) -> X")
+ METH (ext, "M.ext(XR) -> X")
+ METH (exp, "M.exp(X, N) -> X^N mod M.m")
+ METH (mexp, "\
+B.mexp([(X0, N0), (X1, N1), ...]) = X0^N0 X1^N1 mod B.m\n\
+\t(the list may be flattened if this more convenient.)")
+#undef METHNAME
+ { 0 }
+};
+
+static PyTypeObject *mpmont_pytype, mpmont_pytype_skel = {
+ PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
+ "catacomb.MPMont", /* @tp_name@ */
+ sizeof(mpmont_pyobj), /* @tp_basicsize@ */
+ 0, /* @tp_itemsize@ */
+
+ mpmont_pydealloc, /* @tp_dealloc@ */
+ 0, /* @tp_print@ */
+ 0, /* @tp_getattr@ */
+ 0, /* @tp_setattr@ */
+ 0, /* @tp_compare@ */
+ 0, /* @tp_repr@ */
+ 0, /* @tp_as_number@ */
+ 0, /* @tp_as_sequence@ */
+ 0, /* @tp_as_mapping@ */
+ 0, /* @tp_hash@ */
+ 0, /* @tp_call@ */
+ 0, /* @tp_str@ */
+ 0, /* @tp_getattro@ */
+ 0, /* @tp_setattro@ */
+ 0, /* @tp_as_buffer@ */
+ Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
+ Py_TPFLAGS_BASETYPE,
+
+ /* @tp_doc@ */
+"A Montgomery reduction context.",
+
+ 0, /* @tp_traverse@ */
+ 0, /* @tp_clear@ */
+ 0, /* @tp_richcompare@ */
+ 0, /* @tp_weaklistoffset@ */
+ 0, /* @tp_iter@ */
+ 0, /* @tp_iternexr@ */
+ mpmont_pymethods, /* @tp_methods@ */
+ 0, /* @tp_members@ */
+ mpmont_pygetset, /* @tp_getset@ */
+ 0, /* @tp_base@ */
+ 0, /* @tp_dict@ */
+ 0, /* @tp_descr_get@ */
+ 0, /* @tp_descr_set@ */
+ 0, /* @tp_dictoffset@ */
+ 0, /* @tp_init@ */
+ PyType_GenericAlloc, /* @tp_alloc@ */
+ mpmont_pynew, /* @tp_new@ */
+ _PyObject_Del, /* @tp_free@ */
+ 0 /* @tp_is_gc@ */
+};
+
+/*----- Barrett reduction -------------------------------------------------*/
+
+typedef struct mpbarrett_pyobj {
+ PyObject_HEAD
+ mpbarrett mb;
+} mpbarrett_pyobj;
+
+#define MPBARRETT_PY(o) (&((mpbarrett_pyobj *)(o))->mb)
+
+static PyObject *mbmeth_exp(PyObject *me, PyObject *arg)
+{
+ PyObject *rc = 0;
+ mp *yy = 0, *zz = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
+ goto end;
+ if (MP_NEGP(zz)) {
+ if ((yy = mp_modinv_checked(yy, yy, MPBARRETT_PY(me)->m)) == 0) goto end;
+ zz = mp_neg(zz, zz);
+ }
+ rc = mp_pywrap(mpbarrett_exp(MPBARRETT_PY(me), MP_NEW, yy, zz));
+end:
+ if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
+ return (rc);
+}
+
+static PyObject *mb_mexp(PyObject *me, void *v, int n)
+ { return mp_pywrap(mpbarrett_mexp(MPBARRETT_PY(me), MP_NEW, v, n)); }
+
+static PyObject *mbmeth_mexp(PyObject *me, PyObject *arg)
+{
+ return mexp_common(me, arg, sizeof(mp_expfactor),
+ mp_mexp_id, mp_mexp_fill, mb_mexp, mp_mexp_drop);
+}
+
+static PyObject *mbmeth_reduce(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&:reduce", convmp, &yy))
+ goto end;
+ z = mp_pywrap(mpbarrett_reduce(MPBARRETT_PY(me), MP_NEW, yy));
+end:
+ return (z);
+}
+
+static void mpbarrett_pydealloc(PyObject *me)
+{
+ mpbarrett_destroy(MPBARRETT_PY(me));
+ PyObject_DEL(me);
+}
+
+static PyObject *mpbarrett_pynew(PyTypeObject *ty,
+ PyObject *arg, PyObject *kw)
+{
+ mpbarrett_pyobj *mb = 0;
+ char *kwlist[] = { "m", 0 };
+ mp *xx = 0;
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
+ goto end;
+ if (!MP_POSP(xx)) VALERR("m must be positive");
+ mb = (mpbarrett_pyobj *)ty->tp_alloc(ty, 0);
+ mpbarrett_create(&mb->mb, xx);
+end:
+ if (xx) MP_DROP(xx);
+ return ((PyObject *)mb);
+}
+
+static PyObject *mbget_m(PyObject *me, void *hunoz)
+ { return (mp_pywrap(MP_COPY(MPBARRETT_PY(me)->m))); }
+
+static PyGetSetDef mpbarrett_pygetset[] = {
+#define GETSETNAME(op, name) mb##op##_##name
+ GET (m, "B.m -> modulus for reduction")
+#undef GETSETNAME
+ { 0 }
+};
+
+static PyMethodDef mpbarrett_pymethods[] = {
+#define METHNAME(name) mbmeth_##name
+ METH (reduce, "B.reduce(X) -> X mod B.m")
+ METH (exp, "B.exp(X, N) -> X^N mod B.m")
+ METH (mexp, "\
+B.mexp([(X0, N0), (X1, N1), ...]) = X0^N0 X1^N1 mod B.m\n\
+\t(the list may be flattened if this more convenient.)")
+#undef METHNAME
+ { 0 }
+};
+
+static PyTypeObject *mpbarrett_pytype, mpbarrett_pytype_skel = {
+ PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
+ "catacomb.MPBarrett", /* @tp_name@ */
+ sizeof(mpbarrett_pyobj), /* @tp_basicsize@ */
+ 0, /* @tp_itemsize@ */
+
+ mpbarrett_pydealloc, /* @tp_dealloc@ */
+ 0, /* @tp_print@ */
+ 0, /* @tp_getattr@ */
+ 0, /* @tp_setattr@ */
+ 0, /* @tp_compare@ */
+ 0, /* @tp_repr@ */
+ 0, /* @tp_as_number@ */
+ 0, /* @tp_as_sequence@ */
+ 0, /* @tp_as_mapping@ */
+ 0, /* @tp_hash@ */
+ 0, /* @tp_call@ */
+ 0, /* @tp_str@ */
+ 0, /* @tp_getattro@ */
+ 0, /* @tp_setattro@ */
+ 0, /* @tp_as_buffer@ */
+ Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
+ Py_TPFLAGS_BASETYPE,
+
+ /* @tp_doc@ */
+"A Barrett reduction context.",
+
+ 0, /* @tp_traverse@ */
+ 0, /* @tp_clear@ */
+ 0, /* @tp_richcompare@ */
+ 0, /* @tp_weaklistoffset@ */
+ 0, /* @tp_iter@ */
+ 0, /* @tp_iternexr@ */
+ mpbarrett_pymethods, /* @tp_methods@ */
+ 0, /* @tp_members@ */
+ mpbarrett_pygetset, /* @tp_getset@ */
+ 0, /* @tp_base@ */
+ 0, /* @tp_dict@ */
+ 0, /* @tp_descr_get@ */
+ 0, /* @tp_descr_set@ */
+ 0, /* @tp_dictoffset@ */
+ 0, /* @tp_init@ */
+ PyType_GenericAlloc, /* @tp_alloc@ */
+ mpbarrett_pynew, /* @tp_new@ */
+ _PyObject_Del, /* @tp_free@ */
+ 0 /* @tp_is_gc@ */
+};
+
+/*----- Nice prime reduction ----------------------------------------------*/
+
+typedef struct mpreduce_pyobj {
+ PyObject_HEAD
+ mpreduce mr;
+} mpreduce_pyobj;
+
+#define MPREDUCE_PY(o) (&((mpreduce_pyobj *)(o))->mr)
+
+static PyObject *mrmeth_exp(PyObject *me, PyObject *arg)
+{
+ PyObject *rc = 0;
+ mp *yy = 0, *zz = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
+ goto end;
+ if (MP_NEGP(zz)) {
+ if ((yy = mp_modinv_checked(yy, yy, MPREDUCE_PY(me)->p)) == 0) goto end;
+ zz = mp_neg(zz, zz);
+ }
+ rc = mp_pywrap(mpreduce_exp(MPREDUCE_PY(me), MP_NEW, yy, zz));
+end:
+ if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
+ return (rc);
+}
+
+static PyObject *mrmeth_reduce(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&:reduce", convmp, &yy)) goto end;
+ z = mp_pywrap(mpreduce_do(MPREDUCE_PY(me), MP_NEW, yy));
+end:
+ return (z);
+}
+
+static void mpreduce_pydealloc(PyObject *me)
+{
+ mpreduce_destroy(MPREDUCE_PY(me));
+ PyObject_DEL(me);
+}
+
+static PyObject *mpreduce_pynew(PyTypeObject *ty,
+ PyObject *arg, PyObject *kw)
+{
+ mpreduce_pyobj *mr = 0;
+ mpreduce r;
+ char *kwlist[] = { "m", 0 };
+ mp *xx = 0;
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
+ goto end;
+ if (!MP_POSP(xx)) VALERR("m must be positive");
+ if (mpreduce_create(&r, xx)) VALERR("bad modulus (must be 2^k - ...)");
+ mr = (mpreduce_pyobj *)ty->tp_alloc(ty, 0);
+ mr->mr = r;
+end:
+ if (xx) MP_DROP(xx);
+ return ((PyObject *)mr);
+}
+
+static PyObject *mrget_m(PyObject *me, void *hunoz)
+ { return (mp_pywrap(MP_COPY(MPREDUCE_PY(me)->p))); }
+
+static PyGetSetDef mpreduce_pygetset[] = {
+#define GETSETNAME(op, name) mr##op##_##name
+ GET (m, "R.m -> modulus for reduction")
+#undef GETSETNAME
+ { 0 }
+};
+
+static PyMethodDef mpreduce_pymethods[] = {
+#define METHNAME(name) mrmeth_##name
+ METH (reduce, "R.reduce(X) -> X mod B.m")
+ METH (exp, "R.exp(X, N) -> X^N mod B.m")
+#undef METHNAME
+ { 0 }
+};
+
+static PyTypeObject *mpreduce_pytype, mpreduce_pytype_skel = {
+ PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
+ "catacomb.MPReduce", /* @tp_name@ */
+ sizeof(mpreduce_pyobj), /* @tp_basicsize@ */
+ 0, /* @tp_itemsize@ */
+
+ mpreduce_pydealloc, /* @tp_dealloc@ */
+ 0, /* @tp_print@ */
+ 0, /* @tp_getattr@ */
+ 0, /* @tp_setattr@ */
+ 0, /* @tp_compare@ */
+ 0, /* @tp_repr@ */
+ 0, /* @tp_as_number@ */
+ 0, /* @tp_as_sequence@ */
+ 0, /* @tp_as_mapping@ */
+ 0, /* @tp_hash@ */
+ 0, /* @tp_call@ */
+ 0, /* @tp_str@ */
+ 0, /* @tp_getattro@ */
+ 0, /* @tp_setattro@ */
+ 0, /* @tp_as_buffer@ */
+ Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
+ Py_TPFLAGS_BASETYPE,
+
+ /* @tp_doc@ */
+"A reduction context for reduction modulo primes of special form.",
+
+ 0, /* @tp_traverse@ */
+ 0, /* @tp_clear@ */
+ 0, /* @tp_richcompare@ */
+ 0, /* @tp_weaklistoffset@ */
+ 0, /* @tp_iter@ */
+ 0, /* @tp_iternexr@ */
+ mpreduce_pymethods, /* @tp_methods@ */
+ 0, /* @tp_members@ */
+ mpreduce_pygetset, /* @tp_getset@ */
+ 0, /* @tp_base@ */
+ 0, /* @tp_dict@ */
+ 0, /* @tp_descr_get@ */
+ 0, /* @tp_descr_set@ */
+ 0, /* @tp_dictoffset@ */
+ 0, /* @tp_init@ */
+ PyType_GenericAlloc, /* @tp_alloc@ */
+ mpreduce_pynew, /* @tp_new@ */
+ _PyObject_Del, /* @tp_free@ */
+ 0 /* @tp_is_gc@ */
+};
+
+/*----- Chinese Remainder Theorem solution --------------------------------*/
+
+typedef struct mpcrt_pyobj {
+ PyObject_HEAD
+ mpcrt c;
+} mpcrt_pyobj;
+
+#define MPCRT_PY(o) (&((mpcrt_pyobj *)(o))->c)
+
+static PyObject *mcmeth_solve(PyObject *me, PyObject *arg)
+{
+ mpcrt *c = MPCRT_PY(me);
+ PyObject *q = 0, *x, *z = 0;
+ mp *xx;
+ mp **v = 0;
+ int i = 0, n = c->k;
+
+ Py_INCREF(me);
+ if (PyTuple_Size(arg) == n)
+ q = arg;
+ else if (!PyArg_ParseTuple(arg, "O:solve", &q))
+ goto end;
+ Py_INCREF(q);
+ if (!PySequence_Check(q)) TYERR("want a sequence of residues");
+ if (PySequence_Size(q) != n) VALERR("residue count mismatch");
+ v = xmalloc(n * sizeof(*v));
+ for (i = 0; i < n; i++) {
+ if ((x = PySequence_GetItem(q, i)) == 0) goto end;
+ xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
+ v[i] = xx;
+ }
+ z = mp_pywrap(mpcrt_solve(c, MP_NEW, v));
+end:
+ if (v) {
+ n = i;
+ for (i = 0; i < n; i++)
+ MP_DROP(v[i]);
+ xfree(v);
+ }
+ Py_DECREF(me);
+ Py_XDECREF(q);
+ return (z);
+}
+
+static void mpcrt_pydealloc(PyObject *me)
+{
+ mpcrt *c = MPCRT_PY(me);
+ mpcrt_destroy(c);
+ xfree(c->v);
+}
+
+static PyObject *mpcrt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
+{
+ mpcrt_mod *v = 0;
+ int n, i = 0;
+ char *kwlist[] = { "mv", 0 };
+ PyObject *q = 0, *x;
+ mp *xx;
+ mpcrt_pyobj *c = 0;
+
+ if (PyTuple_Size(arg) > 1)
+ q = arg;
+ else if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &q))
+ goto end;
+ Py_INCREF(q);
+ if (!PySequence_Check(q)) TYERR("want a sequence of moduli");
+ n = PySequence_Size(q);
+ if (PyErr_Occurred()) goto end;
+ if (!n) VALERR("want at least one modulus");
+ v = xmalloc(n * sizeof(*v));
+ for (i = 0; i < n; i++) {
+ if ((x = PySequence_GetItem(q, i)) == 0) goto end;
+ xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
+ v[i].m = xx; v[i].n = 0; v[i].ni = 0; v[i].nni = 0;
+ }
+ c = (mpcrt_pyobj *)ty->tp_alloc(ty, 0);
+ mpcrt_create(&c->c, v, n, 0);
+ Py_DECREF(q);
+ return ((PyObject *)c);
+
+end:
+ if (v) {
+ n = i;
+ for (i = 0; i < n; i++)
+ MP_DROP(v[i].m);
+ xfree(v);
+ }
+ Py_XDECREF(q);
+ return (0);
+}
+
+static PyObject *mcget_product(PyObject *me, void *hunoz)
+ { return (mp_pywrap(MP_COPY(MPCRT_PY(me)->mb.m))); }
+
+static PyObject *mcget_moduli(PyObject *me, void *hunoz)
+{
+ int i;
+ PyObject *q;
+ mpcrt *c = MPCRT_PY(me);
+
+ if ((q = PyList_New(c->k)) == 0) return (0);
+ for (i = 0; i < c->k; i++)
+ PyList_SetItem(q, i, mp_pywrap(c->v[i].m));
+ return (q);
+}
+
+static PyGetSetDef mpcrt_pygetset[] = {
+#define GETSETNAME(op, name) mc##op##_##name
+ GET (product, "C.product -> product of moduli")
+ GET (moduli, "C.moduli -> list of individual moduli")
+#undef GETSETNAME
+ { 0 }
+};
+
+static PyMethodDef mpcrt_pymethods[] = {
+#define METHNAME(name) mcmeth_##name
+ METH (solve, "C.solve([R0, R1]) -> X mod C.product")
+#undef METHNAME
+ { 0 }
+};
+
+static PyTypeObject *mpcrt_pytype, mpcrt_pytype_skel = {
+ PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
+ "catacomb.MPCRT", /* @tp_name@ */
+ sizeof(mpcrt_pyobj), /* @tp_basicsize@ */
+ 0, /* @tp_itemsize@ */
+
+ mpcrt_pydealloc, /* @tp_dealloc@ */
+ 0, /* @tp_print@ */
+ 0, /* @tp_getattr@ */
+ 0, /* @tp_setattr@ */
+ 0, /* @tp_compare@ */
+ 0, /* @tp_repr@ */
+ 0, /* @tp_as_number@ */
+ 0, /* @tp_as_sequence@ */
+ 0, /* @tp_as_mapping@ */
+ 0, /* @tp_hash@ */
+ 0, /* @tp_call@ */
+ 0, /* @tp_str@ */
+ 0, /* @tp_getattro@ */
+ 0, /* @tp_setattro@ */
+ 0, /* @tp_as_buffer@ */
+ Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
+ Py_TPFLAGS_BASETYPE,
+
+ /* @tp_doc@ */
+"A context for the solution of Chinese Remainder Theorem problems.",
+
+ 0, /* @tp_traverse@ */
+ 0, /* @tp_clear@ */
+ 0, /* @tp_richcompare@ */
+ 0, /* @tp_weaklistoffset@ */
+ 0, /* @tp_iter@ */
+ 0, /* @tp_iternexr@ */
+ mpcrt_pymethods, /* @tp_methods@ */
+ 0, /* @tp_members@ */
+ mpcrt_pygetset, /* @tp_getset@ */
+ 0, /* @tp_base@ */
+ 0, /* @tp_dict@ */
+ 0, /* @tp_descr_get@ */
+ 0, /* @tp_descr_set@ */
+ 0, /* @tp_dictoffset@ */
+ 0, /* @tp_init@ */
+ PyType_GenericAlloc, /* @tp_alloc@ */
+ mpcrt_pynew, /* @tp_new@ */
+ _PyObject_Del, /* @tp_free@ */
+ 0 /* @tp_is_gc@ */
+};
+
+/*----- Binary polynomials ------------------------------------------------*/
+
+static PyObject *gf_pyrepr(PyObject *o)
+ { return mp_topystring(MP_X(o), 16, "GF(", "0x", "L)"); }
+
+static PyObject *gf_pyrichcompare(PyObject *x, PyObject *y, int op)
+{
+ mp *xx, *yy;
+ int xl, yl;
+ int b;
+
+ if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL;
+ switch (op) {
+ case Py_EQ: b = MP_EQ(xx, yy); break;
+ case Py_NE: b = !MP_EQ(xx, yy); break;
+ default:
+ xl = mp_bits(xx);
+ yl = mp_bits(yy);
+ switch (op) {
+ case Py_LT: b = xl < yl; break;
+ case Py_LE: b = xl <= yl; break;
+ case Py_GT: b = xl > yl; break;
+ case Py_GE: b = xl >= yl; break;
+ default: abort();
+ }
+ break;
+ }
+ MP_DROP(xx); MP_DROP(yy);
+ return (getbool(b));
+}
+
+static PyObject *gf_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
+{
+ PyObject *x;
+ mp *z;
+ mp_pyobj *zz = 0;
+ int radix = 0;
+ char *kwlist[] = { "x", "radix", 0 };
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:gf", kwlist, &x, &radix))
+ goto end;
+ if (GF_PYCHECK(x)) RETURN_OBJ(x);
+ if (radix < -255 || radix > 62) VALERR("radix out of range");
+ if ((z = mp_frompyobject(x, radix)) == 0) {
+ PyErr_Format(PyExc_TypeError, "can't convert %.100s to gf",
+ x->ob_type->tp_name);
+ goto end;
+ }
+ if (MP_NEGP(z)) {
+ MP_DROP(z);
+ VALERR("gf cannot be negative");
+ }
+ zz = (mp_pyobj *)ty->tp_alloc(ty, 0);
+ zz->x = z;
+end:
+ return ((PyObject *)zz);
+}
+
+static long gf_pyhash(PyObject *me)
+{
+ long i = mp_tolong(MP_X(me));
+ i ^= 0xc7ecd67c; /* random perturbance */
+ if (i == -1)
+ i = -2;
+ return (i);
+}
+
+static PyObject *gf_pyexp(PyObject *x, PyObject *y, PyObject *z)
+{
+ mp *xx = 0, *yy = 0, *zz = 0;
+ mp *r = 0;
+ PyObject *rc = 0;
+
+ if ((xx = tomp(x)) == 0 || (yy = tomp(y)) == 0 ||
+ (z && z != Py_None && (zz = tomp(z)) == 0)) {
+ mp_drop(xx); mp_drop(yy); mp_drop(zz);
+ RETURN_NOTIMPL;
+ }
+ if (!z || z == Py_None) {
+ if (MP_NEGP(yy)) VALERR("negative exponent");
+ r = gf_exp(MP_NEW, xx, yy);
+ } else {
+ gfreduce gr;
+ if (MP_ZEROP(zz)) ZDIVERR("zero modulus");
+ if (MP_NEGP(yy)) {
+ if ((xx = gf_modinv_checked(xx, xx, zz)) == 0) goto end;
+ yy = mp_neg(yy, yy);
+ }
+ gfreduce_create(&gr, zz);
+ r = gfreduce_exp(&gr, MP_NEW, xx, yy);
+ gfreduce_destroy(&gr);
+ }
+ rc = gf_pywrap(r);
+end:
+ mp_drop(xx); mp_drop(yy); mp_drop(zz);
+ return (rc);
+}
+
+static PyObject *gfmeth_sqr(PyObject *me, PyObject *arg)
+{
+ if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
+ return (gf_pywrap(gf_sqr(MP_NEW, MP_X(me))));
+}
+
+static PyObject *gfmeth_gcd(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0, *zz = MP_NEW;
+
+ if (!PyArg_ParseTuple(arg, "O&:gcd", convgf, &yy)) goto end;
+ gf_gcd(&zz, 0, 0, MP_X(me), yy);
+ z = gf_pywrap(zz);
+end:
+ if (yy) MP_DROP(yy);
+ return (z);
+}
+
+static PyObject *gfmeth_gcdx(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
+
+ if (!PyArg_ParseTuple(arg, "O&:gcdx", convgf, &yy))
+ goto end;
+ gf_gcd(&zz, &uu, &vv, MP_X(me), yy);
+ z = Py_BuildValue("(NNN)",
+ gf_pywrap(zz), gf_pywrap(uu), gf_pywrap(vv));
+end:
+ if (yy) MP_DROP(yy);
+ return (z);
+}
+
+static PyObject *gfmeth_modinv(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0, *zz = MP_NEW;
+
+ if (!PyArg_ParseTuple(arg, "O&:modinv", convgf, &yy) ||
+ (zz = gf_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
+ goto end;
+ z = gf_pywrap(zz);
+end:
+ if (yy) MP_DROP(yy);
+ return (z);
+}
+
+static PyObject *gfmeth_irreduciblep(PyObject *me, PyObject *arg)
+{
+ if (!PyArg_ParseTuple(arg, ":irreduciblep")) return (0);
+ return getbool(gf_irreduciblep(MP_X(me)));
+}
+
+static PyObject *gfget_degree(PyObject *me, void *hunoz)
+ { return (PyInt_FromLong(mp_bits(MP_X(me)) - 1)); }
+
+static PyGetSetDef gf_pygetset[] = {
+#define GETSETNAME(op, name) gf##op##_##name
+ GET (degree, "X.degree -> polynomial degree of X")
+#undef GETSETNAME
+#define GETSETNAME(op, name) mp##op##_##name
+ GET (nbits, "X.nbits -> bit length of X")
+ GET (noctets, "X.noctets -> octet length of X")
+#undef GETSETNAME
+ { 0 }
+};
+
+static PyMethodDef gf_pymethods[] = {
+#define METHNAME(func) gfmeth_##func
+ METH (setbit, "X.setbit(N) -> X with bit N set")
+ METH (clearbit, "X.clearbit(N) -> X with bit N clear")
+ METH (testbit, "X.testbit(N) -> true/false if bit N set/clear in X")
+ METH (sqr, "X.sqr() -> X^2")
+ METH (gcd, "X.gcd(Y) -> gcd(X, Y)")
+ METH (gcdx,
+ "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
+ METH (modinv, "X.modinv(Y) -> multiplicative inverse of Y mod X")
+ METH (irreduciblep, "X.irreduciblep() -> true/false")
+#undef METHNAME
+#define METHNAME(func) mpmeth_##func
+ KWMETH(tostring, "X.tostring(radix = 10) -> STR")
+ KWMETH(storel, "X.storel(len = -1) -> little-endian bytes")
+ KWMETH(storeb, "X.storeb(len = -1) -> big-endian bytes")
+ KWMETH(storel2c,
+ "X.storel2c(len = -1) -> little-endian bytes, two's complement")
+ KWMETH(storeb2c,
+ "X.storeb2c(len = -1) -> big-endian bytes, two's complement")
+ METH (tobuf, "X.tobuf() -> buffer format")
+#undef METHNAME
+ { 0 }
+};
+
+static PyNumberMethods gf_pynumber = {
+ gf_pyadd, /* @nb_add@ */
+ gf_pysub, /* @nb_subtract@ */
+ gf_pymul, /* @nb_multiply@ */
+ 0, /* @nb_divide@ */
+ gf_pymod, /* @nb_remainder@ */
+ gf_pydivmod, /* @nb_divmod@ */
+ gf_pyexp, /* @nb_power@ */
+ mp_pyid, /* @nb_negative@ */
+ mp_pyid, /* @nb_positive@ */
+ mp_pyid, /* @nb_absolute@ */
+ mp_pynonzerop, /* @nb_nonzero@ */
+ 0 /* doesn't make any sense */, /* @nb_invert@ */
+ gf_pylsl, /* @nb_lshift@ */
+ gf_pylsr, /* @nb_rshift@ */
+ gf_pyand, /* @nb_and@ */
+ gf_pyxor, /* @nb_xor@ */
+ gf_pyor, /* @nb_or@ */
+ gf_pycoerce, /* @nb_coerce@ */
+ mp_pyint, /* @nb_int@ */
+ mp_pylong, /* @nb_long@ */
+ 0 /* doesn't make any sense */, /* @nb_float@ */
+ mp_pyoct, /* @nb_oct@ */
+ mp_pyhex, /* @nb_hex@ */
+
+ 0, /* @nb_inplace_add@ */
+ 0, /* @nb_inplace_subtract@ */
+ 0, /* @nb_inplace_multiply@ */
+ 0, /* @nb_inplace_divide@ */
+ 0, /* @nb_inplace_remainder@ */
+ 0, /* @nb_inplace_power@ */
+ 0, /* @nb_inplace_lshift@ */
+ 0, /* @nb_inplace_rshift@ */
+ 0, /* @nb_inplace_and@ */
+ 0, /* @nb_inplace_xor@ */
+ 0, /* @nb_inplace_or@ */
+
+ gf_pydiv, /* @nb_floor_divide@ */
+ 0, /* @nb_true_divide@ */
+ 0, /* @nb_inplace_floor_divide@ */
+ 0, /* @nb_inplace_true_divide@ */
+};
+
+static PyTypeObject gf_pytype_skel = {
+ PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
+ "catacomb.GF", /* @tp_name@ */
+ sizeof(mp_pyobj), /* @tp_basicsize@ */
+ 0, /* @tp_itemsize@ */
+
+ mp_pydealloc, /* @tp_dealloc@ */
+ 0, /* @tp_print@ */
+ 0, /* @tp_getattr@ */
+ 0, /* @tp_setattr@ */
+ 0, /* @tp_compare@ */
+ gf_pyrepr, /* @tp_repr@ */
+ &gf_pynumber, /* @tp_as_number@ */
+ 0, /* @tp_as_sequence@ */
+ 0, /* @tp_as_mapping@ */
+ gf_pyhash, /* @tp_hash@ */
+ 0, /* @tp_call@ */
+ mp_pyhex, /* @tp_str@ */
+ 0, /* @tp_getattro@ */
+ 0, /* @tp_setattro@ */
+ 0, /* @tp_as_buffer@ */
+ Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
+ Py_TPFLAGS_CHECKTYPES |
+ Py_TPFLAGS_BASETYPE,
+
+ /* @tp_doc@ */
+"Binary polynomials. Support almost all the standard arithmetic\n\
+operations.\n\
+\n\
+Constructor gf(X, radix = R) attempts to convert X to a `gf'. If\n\
+X is a string, it's read in radix-R form, or we look for a prefix\n\
+if R = 0. Other acceptable things are ints and longs.\n\
+\n\
+The name is hopelessly wrong from a technical point of view, but\n\
+but it's much easier to type than `p2' or `c2' or whatever.\n\
+\n\
+Notes:\n\
+\n\
+ * Use `//' for division. GFs don't have `/' division.",
+
+ 0, /* @tp_traverse@ */
+ 0, /* @tp_clear@ */
+ gf_pyrichcompare, /* @tp_richcompare@ */
+ 0, /* @tp_weaklistoffset@ */
+ 0, /* @tp_iter@ */
+ 0, /* @tp_iternexr@ */
+ gf_pymethods, /* @tp_methods@ */
+ 0, /* @tp_members@ */
+ gf_pygetset, /* @tp_getset@ */
+ 0, /* @tp_base@ */
+ 0, /* @tp_dict@ */
+ 0, /* @tp_descr_get@ */
+ 0, /* @tp_descr_set@ */
+ 0, /* @tp_dictoffset@ */
+ 0, /* @tp_init@ */
+ PyType_GenericAlloc, /* @tp_alloc@ */
+ gf_pynew, /* @tp_new@ */
+ _PyObject_Del, /* @tp_free@ */
+ 0 /* @tp_is_gc@ */
+};
+
+static PyObject *meth__GF_fromstring(PyObject *me,
+ PyObject *arg, PyObject *kw)
+{
+ int r = 0;
+ char *p;
+ int len;
+ PyObject *z = 0;
+ mp *zz;
+ mptext_stringctx sc;
+ char *kwlist[] = { "class", "x", "radix", 0 };
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
+ kwlist, &me, &p, &len, &r))
+ goto end;
+ if (r < -255 || r > 62) VALERR("radix out of range");
+ sc.buf = p; sc.lim = p + len;
+ if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0 || MP_NEGP(zz))
+ z = Py_BuildValue("(Os#)", Py_None, p, len);
+ else
+ z = Py_BuildValue("(Ns#)", gf_pywrap(zz),
+ sc.buf, (int)(sc.lim - sc.buf));
+end:
+ return (z);
+}
+
+/*----- Sparse poly reduction ---------------------------------------------*/
+
+typedef struct gfreduce_pyobj {
+ PyObject_HEAD
+ gfreduce mr;
+} gfreduce_pyobj;
+
+#define GFREDUCE_PY(o) (&((gfreduce_pyobj *)(o))->mr)
+
+static PyObject *grmeth_exp(PyObject *me, PyObject *arg)
+{
+ PyObject *rc = 0;
+ mp *yy = 0, *zz = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&O&:exp", convgf, &yy, convgf, &zz))
+ goto end;
+ if (MP_NEGP(zz)) {
+ if ((yy = gf_modinv_checked(yy, yy, GFREDUCE_PY(me)->p)) == 0) goto end;
+ zz = mp_neg(zz, zz);
+ }
+ rc = gf_pywrap(gfreduce_exp(GFREDUCE_PY(me), MP_NEW, yy, zz));
+end:
+ if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
+ return (rc);
+}
+
+static PyObject *grmeth_reduce(PyObject *me, PyObject *arg)
+{
+ PyObject *z = 0;
+ mp *yy = 0;
+
+ if (!PyArg_ParseTuple(arg, "O&:reduce", convgf, &yy)) goto end;
+ z = gf_pywrap(gfreduce_do(GFREDUCE_PY(me), MP_NEW, yy));
+end:
+ return (z);
+}
+
+static void gfreduce_pydealloc(PyObject *me)
+{
+ gfreduce_destroy(GFREDUCE_PY(me));
+ PyObject_DEL(me);
+}
+
+static PyObject *gfreduce_pynew(PyTypeObject *ty,
+ PyObject *arg, PyObject *kw)
+{
+ gfreduce_pyobj *mr = 0;
+ gfreduce r;
+ char *kwlist[] = { "m", 0 };
+ mp *xx = 0;
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convgf, &xx))
+ goto end;
+ if (MP_ZEROP(xx)) ZDIVERR("modulus is zero!");
+ gfreduce_create(&r, xx);
+ mr = (gfreduce_pyobj *)ty->tp_alloc(ty, 0);
+ mr->mr = r;
+end:
+ if (xx) MP_DROP(xx);
+ return ((PyObject *)mr);
+}
+
+static PyObject *grget_m(PyObject *me, void *hunoz)
+ { return (gf_pywrap(MP_COPY(GFREDUCE_PY(me)->p))); }
+
+static PyGetSetDef gfreduce_pygetset[] = {
+#define GETSETNAME(op, name) gr##op##_##name
+ GET (m, "R.m -> reduction polynomial")
+#undef GETSETNAME
+ { 0 }
+};
+
+static PyMethodDef gfreduce_pymethods[] = {
+#define METHNAME(name) grmeth_##name
+ METH (reduce, "R.reduce(X) -> X mod B.m")
+ METH (exp, "R.exp(X, N) -> X^N mod B.m")
+#undef METHNAME
+ { 0 }
+};
+
+static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = {
+ PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
+ "catacomb.GFReduce", /* @tp_name@ */
+ sizeof(gfreduce_pyobj), /* @tp_basicsize@ */
+ 0, /* @tp_itemsize@ */
+
+ gfreduce_pydealloc, /* @tp_dealloc@ */
+ 0, /* @tp_print@ */
+ 0, /* @tp_getattr@ */
+ 0, /* @tp_setattr@ */
+ 0, /* @tp_compare@ */
+ 0, /* @tp_repr@ */
+ 0, /* @tp_as_number@ */
+ 0, /* @tp_as_sequence@ */
+ 0, /* @tp_as_mapping@ */
+ 0, /* @tp_hash@ */
+ 0, /* @tp_call@ */
+ 0, /* @tp_str@ */
+ 0, /* @tp_getattro@ */
+ 0, /* @tp_setattro@ */
+ 0, /* @tp_as_buffer@ */
+ Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
+ Py_TPFLAGS_BASETYPE,
+
+ /* @tp_doc@ */
+"A reduction context for reduction modulo sparse irreducible polynomials.",
+
+ 0, /* @tp_traverse@ */
+ 0, /* @tp_clear@ */
+ 0, /* @tp_richcompare@ */
+ 0, /* @tp_weaklistoffset@ */
+ 0, /* @tp_iter@ */
+ 0, /* @tp_iternexr@ */
+ gfreduce_pymethods, /* @tp_methods@ */
+ 0, /* @tp_members@ */
+ gfreduce_pygetset, /* @tp_getset@ */
+ 0, /* @tp_base@ */
+ 0, /* @tp_dict@ */
+ 0, /* @tp_descr_get@ */
+ 0, /* @tp_descr_set@ */
+ 0, /* @tp_dictoffset@ */
+ 0, /* @tp_init@ */
+ PyType_GenericAlloc, /* @tp_alloc@ */
+ gfreduce_pynew, /* @tp_new@ */
+ _PyObject_Del, /* @tp_free@ */
+ 0 /* @tp_is_gc@ */
+};
+
+/*----- Normal/poly transformation ----------------------------------------*/
+
+typedef struct gfn_pyobj {
+ PyObject_HEAD
+ mp *p;
+ gfn ntop, pton;
+} gfn_pyobj;
+
+static PyTypeObject *gfn_pytype, gfn_pytype_skel;
+
+#define GFN_P(o) (((gfn_pyobj *)(o))->p)
+#define GFN_PTON(o) (&((gfn_pyobj *)(o))->pton)
+#define GFN_NTOP(o) (&((gfn_pyobj *)(o))->ntop)
+
+static PyObject *gfn_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
+{
+ mp *p = 0, *beta = 0;
+ gfn_pyobj *gg = 0;
+ char *kwlist[] = { "p", "beta", 0 };
+
+ if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&:new", kwlist,
+ convgf, &p, convgf, &beta))
+ goto end;
+ gg = PyObject_New(gfn_pyobj, ty);
+ if (gfn_create(p, beta, &gg->ntop, &gg->pton)) {
+ PyObject_DEL(gg);
+ gg = 0;
+ VALERR("can't invert transformation matrix");
+ }
+ gg->p = MP_COPY(p);
+end:
+ mp_drop(p);
+ mp_drop(beta);
+ return ((PyObject *)gg);
+}
+
+static PyObject *gfnget_p(PyObject *me, void *hunoz)
+ { return (gf_pywrap(MP_COPY(GFN_P(me)))); }
+
+static PyObject *gfnget_beta(PyObject *me, void *hunoz)
+{
+ gfn *n = GFN_NTOP(me);
+ mp *x = n->r[n->n - 1];
+ return (gf_pywrap(MP_COPY(x)));
+}
+
+#define XFORMOP(name, NAME) \
+ static PyObject *gfnmeth_##name(PyObject *me, PyObject *arg) \
+ { \
+ mp *xx = 0; \
+ mp *z = 0; \
+ \
+ if (!PyArg_ParseTuple(arg, "O&:" #name, convgf, &xx)) goto end; \
+ z = gfn_transform(GFN_##NAME(me), MP_NEW, xx); \
+ end: \
+ mp_drop(xx); \
+ if (!z) return (0); \
+ return (mp_pywrap(z)); \
+ }
+XFORMOP(pton, PTON)
+XFORMOP(ntop, NTOP)
+#undef XFORMOP
+
+static void gfn_pydealloc(PyObject *me)
+{
+ gfn_destroy(GFN_PTON(me));
+ gfn_destroy(GFN_NTOP(me));
+ PyObject_DEL(me);
+}
+
+static PyGetSetDef gfn_pygetset[] = {
+#define GETSETNAME(op, name) gfn##op##_##name
+ GET (p, "X.p -> polynomial basis, as polynomial")
+ GET (beta, "X.beta -> normal basis element, in poly form")
+#undef GETSETNAME
+ { 0 }
+};
+
+static PyMethodDef gfn_pymethods[] = {
+#define METHNAME(name) gfnmeth_##name
+ METH (pton, "X.pton(A) -> normal-basis representation of A")
+ METH (ntop, "X.ntop(A) -> polynomial-basis representation of A")
+#undef METHNAME
+ { 0 }
+};
+
+static PyTypeObject gfn_pytype_skel = {
+ PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
+ "catacomb.GFN", /* @tp_name@ */
+ sizeof(gfn_pyobj), /* @tp_basicsize@ */
+ 0, /* @tp_itemsize@ */
+
+ gfn_pydealloc, /* @tp_dealloc@ */
+ 0, /* @tp_print@ */
+ 0, /* @tp_getattr@ */
+ 0, /* @tp_setattr@ */
+ 0, /* @tp_compare@ */
+ 0, /* @tp_repr@ */
+ 0, /* @tp_as_number@ */
+ 0, /* @tp_as_sequence@ */
+ 0, /* @tp_as_mapping@ */
+ 0, /* @tp_hash@ */
+ 0, /* @tp_call@ */
+ 0, /* @tp_str@ */
+ 0, /* @tp_getattro@ */
+ 0, /* @tp_setattro@ */
+ 0, /* @tp_as_buffer@ */
+ Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
+ Py_TPFLAGS_BASETYPE,
+
+ /* @tp_doc@ */
+"An object for transforming elements of binary fields between polynomial\n\
+and normal basis representations.",
+
+ 0, /* @tp_traverse@ */
+ 0, /* @tp_clear@ */
+ 0, /* @tp_richcompare@ */
+ 0, /* @tp_weaklistoffset@ */
+ 0, /* @tp_iter@ */
+ 0, /* @tp_iternexr@ */
+ gfn_pymethods, /* @tp_methods@ */
+ 0, /* @tp_members@ */
+ gfn_pygetset, /* @tp_getset@ */
+ 0, /* @tp_base@ */
+ 0, /* @tp_dict@ */
+ 0, /* @tp_descr_get@ */
+ 0, /* @tp_descr_set@ */
+ 0, /* @tp_dictoffset@ */
+ 0, /* @tp_init@ */
+ PyType_GenericAlloc, /* @tp_alloc@ */
+ gfn_pynew, /* @tp_new@ */
+ _PyObject_Del, /* @tp_free@ */
+ 0 /* @tp_is_gc@ */
+};
+
+/*----- Glue --------------------------------------------------------------*/
+
+static PyMethodDef methods[] = {
+#define METHNAME(func) meth_##func
+ KWMETH(_MP_fromstring, "\
+fromstring(STR, radix = 0) -> (X, REST)\n\
+\n\
+Parse STR as a large integer, according to radix. If radix is zero,\n\
+read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
+or `R_' for other radix R.")
+ KWMETH(_GF_fromstring, "\
+fromstring(STR, radix = 0) -> (X, REST)\n\
+\n\
+Parse STR as a binary polynomial, according to radix. If radix is zero,\n\
+read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
+or `R_' for other radix R.")
+ METH (_MP_loadl, "\
+loadl(STR) -> X: read little-endian bytes")
+ METH (_MP_loadb, "\
+loadb(STR) -> X: read big-endian bytes")
+ METH (_MP_loadl2c, "\
+loadl2c(STR) -> X: read little-endian bytes, two's complement")
+ METH (_MP_loadb2c, "\
+loadb2c(STR) -> X: read big-endian bytes, two's complement")
+ METH (_MP_frombuf, "\
+frombuf(STR) -> (X, REST): read buffer format")
+ METH (_MP_product, "\
+product(ITER) -> X: product of things iterated over")
+ METH (_GF_loadl, "\
+loadl(STR) -> X: read little-endian bytes")
+ METH (_GF_loadb, "\
+loadb(STR) -> X: read big-endian bytes")
+ METH (_GF_frombuf, "\
+frombuf(STR) -> (X, REST): read buffer format")
+#undef METHNAME
+ { 0 }
+};
+
+void mp_pyinit(void)
+{
+ INITTYPE(mp, root);
+ INITTYPE(gf, root);
+ INITTYPE(mpmont, root);
+ INITTYPE(mpbarrett, root);
+ INITTYPE(mpreduce, root);
+ INITTYPE(mpcrt, root);
+ INITTYPE(gfreduce, root);
+ INITTYPE(gfn, root);
+ addmethods(methods);
+}
+
+void mp_pyinsert(PyObject *mod)
+{
+ INSERT("MP", mp_pytype);
+ INSERT("MPMont", mpmont_pytype);
+ INSERT("MPBarrett", mpbarrett_pytype);
+ INSERT("MPReduce", mpreduce_pytype);
+ INSERT("MPCRT", mpcrt_pytype);
+ INSERT("GF", gf_pytype);
+ INSERT("GFReduce", gfreduce_pytype);
+ INSERT("GFN", gfn_pytype);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
~mdw / catacomb-python / commitdiff