X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb-python/blobdiff_plain/32507e35eeef67236e12adf7d00458e303f8c9aa..a157093f4bbc3066fea2f77078b99489c76e62f8:/mp.c diff --git a/mp.c b/mp.c index 4b73223..29e8881 100644 --- a/mp.c +++ b/mp.c @@ -1,13 +1,11 @@ /* -*-c-*- * - * $Id$ - * * Multiprecision arithmetic * * (c) 2004 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of the Python interface to Catacomb. * @@ -15,12 +13,12 @@ * 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. @@ -165,7 +163,7 @@ PyObject *gf_pywrap(mp *x) return ((PyObject *)z); } -int mp_tolong_checked(mp *x, long *l) +int mp_tolong_checked(mp *x, long *l, int must) { static mp *longmin = 0, *longmax = 0; int rc = -1; @@ -174,8 +172,10 @@ int mp_tolong_checked(mp *x, long *l) 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"); + if (MP_CMP(x, <, longmin) || MP_CMP(x, >, longmax)) { + if (must) VALERR("mp out of range for int"); + else goto end; + } *l = mp_tolong(x); rc = 0; end: @@ -211,6 +211,7 @@ mp *tomp(PyObject *o) return (MP_COPY(PFILT_F(o)->m)); else if (ECPT_PYCHECK(o)) { ec p = EC_INIT; + if (EC_ATINF(ECPT_P(o))) return (0); getecptout(&p, o); x = MP_COPY(p.x); EC_DESTROY(&p); @@ -269,11 +270,44 @@ int convgf(PyObject *o, void *p) return (1); } +static mp *implicitmp(PyObject *o) +{ + if (!o || + GF_PYCHECK(o) || + ECPT_PYCHECK(o) || + FE_PYCHECK(o) || + GE_PYCHECK(o)) + return (0); + return (tomp(o)); +} + +static mp *implicitgf(PyObject *o) +{ + if (!o || + MP_PYCHECK(o) || + ECPT_PYCHECK(o) || + FE_PYCHECK(o) || + GE_PYCHECK(o)) + return (0); + return (tomp(o)); +} + static int mpbinop(PyObject *x, PyObject *y, mp **xx, mp **yy) { - if ((*xx = tomp(x)) == 0) + if ((*xx = implicitmp(x)) == 0) + return (-1); + if ((*yy = implicitmp(y)) == 0) { + MP_DROP(*xx); + return (-1); + } + return (0); +} + +static int gfbinop(PyObject *x, PyObject *y, mp **xx, mp **yy) +{ + if ((*xx = implicitgf(x)) == 0) return (-1); - if ((*yy = tomp(y)) == 0) { + if ((*yy = implicitgf(y)) == 0) { MP_DROP(*xx); return (-1); } @@ -286,7 +320,7 @@ static int mpbinop(PyObject *x, PyObject *y, mp **xx, mp **yy) #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; \ + if (pre##binop(x, y, &xx, &yy)) RETURN_NOTIMPL; \ zz = pre##_##name(MP_NEW, xx, yy); \ MP_DROP(xx); MP_DROP(yy); \ return (pre##_pywrap(zz)); \ @@ -330,8 +364,8 @@ static PyObject *mp_pyid(PyObject *x) { RETURN_OBJ(x); } 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 (pre##binop(x, y, &xx, &yy)) RETURN_NOTIMPL; \ + if (mp_tolong_checked(yy, &n, 1)) goto end; \ if (n < 0) \ z = pre##_pywrap(mp_##rname(MP_NEW, xx, -n)); \ else \ @@ -351,7 +385,7 @@ SHIFTOP(gf, lsr, lsl) mp *xx, *yy; \ PyObject *z = 0; \ INIT_##qq(q) INIT_##rr(r) \ - if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL; \ + if (pre##binop(x, y, &xx, &yy)) RETURN_NOTIMPL; \ if (MP_ZEROP(yy)) \ ZDIVERR("division by zero"); \ pre##_div(ARG_##qq(q), ARG_##rr(r), xx, yy); \ @@ -396,7 +430,7 @@ static PyObject *mp_pyexp(PyObject *x, PyObject *y, PyObject *z) mp *r = 0; PyObject *rc = 0; - if ((xx = tomp(x)) == 0 || (yy = tomp(y)) == 0 || + if ((xx = implicitmp(x)) == 0 || (yy = implicitmp(y)) == 0 || (z && z != Py_None && (zz = tomp(z)) == 0)) { mp_drop(xx); mp_drop(yy); mp_drop(zz); RETURN_NOTIMPL; @@ -452,8 +486,8 @@ 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)); + if (!mp_tolong_checked(MP_X(x), &l, 0)) return (PyInt_FromLong(l)); + else return mp_topylong(MP_X(x)); } static PyObject *mp_pylong(PyObject *x) { return (mp_topylong(MP_X(x))); } @@ -465,7 +499,7 @@ static PyObject *mp_pyfloat(PyObject *x) return (PyFloat_FromDouble(f)); } -#define COERCE(pre, PRE) \ +#define COERCE(pre, PRE) \ static int pre##_pycoerce(PyObject **x, PyObject **y) \ { \ mp *z; \ @@ -494,9 +528,9 @@ static PyObject *mp_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw) mp *z; mp_pyobj *zz = 0; int radix = 0; - char *kwlist[] = { "x", "radix", 0 }; + static const char *const kwlist[] = { "x", "radix", 0 }; - if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:new", kwlist, &x, &radix)) + if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:new", KWLIST, &x, &radix)) goto end; if (MP_PYCHECK(x)) RETURN_OBJ(x); if (!good_radix_p(radix, 1)) VALERR("bad radix"); @@ -511,21 +545,21 @@ end: return ((PyObject *)zz); } -static long mp_pyhash(PyObject *me) +long mphash(mp *x) { - long h; - PyObject *l = mp_topylong(MP_X(me)); h = PyObject_Hash(l); + PyObject *l = mp_topylong(x); + long h = PyObject_Hash(l); Py_DECREF(l); return (h); } +static long mp_pyhash(PyObject *me) { return (mphash(MP_X(me))); } + static PyObject *mpmeth_jacobi(PyObject *me, PyObject *arg) { mp *y = 0; PyObject *z = 0; if (!PyArg_ParseTuple(arg, "O&:jacobi", convmp, &y)) goto end; - if (MP_NEGP(MP_X(me)) || MP_EVENP(MP_X(me))) - VALERR("must be positive and odd"); z = PyInt_FromLong(mp_jacobi(y, MP_X(me))); end: if (y) MP_DROP(y); @@ -535,27 +569,27 @@ end: #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); \ + unsigned long i; \ + if (!PyArg_ParseTuple(arg, "O&:" #name, convulong, &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, 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); + unsigned long i; + if (!PyArg_ParseTuple(arg, "O&:testbit", convulong, &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); + unsigned long i; + if (!PyArg_ParseTuple(arg, "O&:testbit", convulong, &i)) return (0); return (getbool(mp_testbit(MP_X(me), i))); } @@ -628,8 +662,8 @@ end: 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)) + static const char *const kwlist[] = { "radix", 0 }; + if (!PyArg_ParseTupleAndKeywords(arg, kw, "|i:tostring", KWLIST, &radix)) goto end; if (!good_radix_p(radix, 0)) VALERR("bad radix"); return (mp_topystring(MP_X(me), radix, 0, 0, 0)); @@ -651,16 +685,29 @@ end: return (z); } +static PyObject *mpmeth_leastcongruent(PyObject *me, PyObject *arg) +{ + mp *z, *b, *m; + PyObject *rc = 0; + + if (!PyArg_ParseTuple(arg, "O&O&:leastcongruent", convmp, &b, convmp, &m)) + goto end; + z = mp_leastcongruent(MP_NEW, b, MP_X(me), m); + rc = mp_pywrap(z); +end: + return (rc); +} + #define STOREOP(name, c) \ static PyObject *mpmeth_##name(PyObject *me, \ PyObject *arg, PyObject *kw) \ { \ long len = -1; \ - char *kwlist[] = { "len", 0 }; \ + static const char *const kwlist[] = { "len", 0 }; \ PyObject *rc = 0; \ \ if (!PyArg_ParseTupleAndKeywords(arg, kw, "|l:" #name, \ - kwlist, &len)) \ + KWLIST, &len)) \ goto end; \ if (len < 0) { \ len = mp_octets##c(MP_X(me)); \ @@ -677,16 +724,16 @@ STOREOP(storel2c, 2c) STOREOP(storeb2c, 2c) #undef STOREOP -#define BUFOP(ty, pyty) \ - static PyObject *meth__##pyty##_frombuf(PyObject *me, PyObject *arg) \ +#define BUFOP(ty) \ + static PyObject *ty##meth_frombuf(PyObject *me, PyObject *arg) \ { \ buf b; \ char *p; \ - int sz; \ + Py_ssize_t sz; \ PyObject *rc = 0; \ mp *x; \ \ - if (!PyArg_ParseTuple(arg, "Os#:frombuf", &me, &p, &sz)) goto end; \ + if (!PyArg_ParseTuple(arg, "s#:frombuf", &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), \ @@ -694,8 +741,8 @@ STOREOP(storeb2c, 2c) end: \ return (rc); \ } -BUFOP(mp, MP) -BUFOP(gf, GF) +BUFOP(mp) +BUFOP(gf) #undef BUFOP static PyObject *mpmeth_tobuf(PyObject *me, PyObject *arg) @@ -719,16 +766,74 @@ static PyObject *mpmeth_tobuf(PyObject *me, PyObject *arg) static PyObject *mpmeth_primep(PyObject *me, PyObject *arg, PyObject *kw) { grand *r = &rand_global; - char *kwlist[] = { "rng", 0 }; + static const char *const kwlist[] = { "rng", 0 }; PyObject *rc = 0; - if (!PyArg_ParseTupleAndKeywords(arg, kw, "|O&", kwlist, convgrand, &r)) + if (!PyArg_ParseTupleAndKeywords(arg, kw, "|O&", KWLIST, convgrand, &r)) goto end; rc = getbool(pgen_primep(MP_X(me), r)); end: return (rc); } +static PyObject *mpmeth_fromstring(PyObject *me, + PyObject *arg, PyObject *kw) +{ + int r = 0; + char *p; + Py_ssize_t len; + PyObject *z = 0; + mp *zz; + mptext_stringctx sc; + static const char *const kwlist[] = { "x", "radix", 0 }; + + if (!PyArg_ParseTupleAndKeywords(arg, kw, "s#|i:fromstring", KWLIST, + &p, &len, &r)) + goto end; + if (!good_radix_p(r, 1)) VALERR("bad radix"); + sc.buf = p; sc.lim = p + len; + if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0) + VALERR("bad integer"); + z = Py_BuildValue("(Ns#)", mp_pywrap(zz), + sc.buf, (Py_ssize_t)(sc.lim - sc.buf)); +end: + return (z); +} + +static PyObject *mpmeth_factorial(PyObject *me, PyObject *arg) +{ + unsigned long i; + mp *x; + if (!PyArg_ParseTuple(arg, "O&:factorial", convulong, &i)) return (0); + x = mp_factorial(i); + return mp_pywrap(x); +} + +static PyObject *mpmeth_fibonacci(PyObject *me, PyObject *arg) +{ + long i; + mp *x; + if (!PyArg_ParseTuple(arg, "l:fibonacci", &i)) return (0); + x = mp_fibonacci(i); + return mp_pywrap(x); +} + +#define LOADOP(pre, name) \ + static PyObject *pre##meth_##name(PyObject *me, PyObject *arg) \ + { \ + char *p; \ + Py_ssize_t len; \ + if (!PyArg_ParseTuple(arg, "s#:" #name, &p, &len)) return (0); \ + return (pre##_pywrap(mp_##name(MP_NEW, p, len))); \ + } +LOADOP(mp, loadl) +LOADOP(mp, loadb) +LOADOP(mp, loadl2c) +LOADOP(mp, loadb2c) +LOADOP(gf, loadl) +LOADOP(gf, loadb) +#undef LOADOP + static PyObject *mpget_nbits(PyObject *me, void *hunoz) { return (PyInt_FromLong(mp_bits(MP_X(me)))); } @@ -738,7 +843,7 @@ static PyObject *mpget_noctets(PyObject *me, void *hunoz) static PyObject *mpget_noctets2c(PyObject *me, void *hunoz) { return (PyInt_FromLong(mp_octets2c(MP_X(me)))); } -static PyGetSetDef mp_pygetset[] = { +static const 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") @@ -747,9 +852,9 @@ static PyGetSetDef mp_pygetset[] = { { 0 } }; -static PyMethodDef mp_pymethods[] = { +static const PyMethodDef mp_pymethods[] = { #define METHNAME(func) mpmeth_##func - METH (jacobi, "X.jacobi(Y) -> Jacobi symbol (Y/X) (NB inversion!)") + 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") @@ -757,24 +862,39 @@ static PyMethodDef mp_pymethods[] = { 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 (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 (leastcongruent, "X.leastcongruent(B, M) -> " + "smallest Z >= B with Z == X (mod M)") + KWMETH(primep, "X.primep([rng = rand]) -> 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") + KWSMTH(fromstring, "fromstring(STR, [radix = 0]) -> (X, REST)\n" + " Parse STR as a large integer, according to RADIX. If RADIX is\n" + " zero, read a prefix from STR to decide radix: allow `0b' for binary,\n" + " `0' or `0o' for octal, `0x' for hex, or `R_' for other radix R.") + SMTH (factorial, "factorial(I) -> I!: compute factorial") + SMTH (fibonacci, "fibonacci(I) -> F(I): compute Fibonacci number") + SMTH (loadl, "loadl(STR) -> X: read little-endian bytes") + SMTH (loadb, "loadb(STR) -> X: read big-endian bytes") + SMTH (loadl2c, "loadl2c(STR) -> X: " + "read little-endian bytes, two's complement") + SMTH (loadb2c, "loadb2c(STR) -> X: " + "read big-endian bytes, two's complement") + SMTH (frombuf, "frombuf(STR) -> (X, REST): read buffer format") #undef METHNAME { 0 } }; -static PyNumberMethods mp_pynumber = { +static const PyNumberMethods mp_pynumber = { mp_pyadd, /* @nb_add@ */ mp_pysub, /* @nb_subtract@ */ mp_pymul, /* @nb_multiply@ */ @@ -819,7 +939,7 @@ static PyNumberMethods mp_pynumber = { static PyTypeObject mp_pytype_skel = { PyObject_HEAD_INIT(0) 0, /* Header */ - "catacomb.MP", /* @tp_name@ */ + "MP", /* @tp_name@ */ sizeof(mp_pyobj), /* @tp_basicsize@ */ 0, /* @tp_itemsize@ */ @@ -829,7 +949,7 @@ static PyTypeObject mp_pytype_skel = { 0, /* @tp_setattr@ */ mp_pycompare, /* @tp_compare@ */ mp_pyrepr, /* @tp_repr@ */ - &mp_pynumber, /* @tp_as_number@ */ + PYNUMBER(mp), /* @tp_as_number@ */ 0, /* @tp_as_sequence@ */ 0, /* @tp_as_mapping@ */ mp_pyhash, /* @tp_hash@ */ @@ -843,16 +963,20 @@ static PyTypeObject mp_pytype_skel = { 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.", + "Multiprecision integers, similar to `long' but more efficient and\n" + "versatile. Support all the standard arithmetic operations, with\n" + "implicit conversions from `PrimeFilter', and other objects which\n" + "convert to `long'.\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 field elements, elliptic curve\n" + "points, group elements, Python `int' and `long' objects, and anything\n" + "with an integer conversion.\n" + "\n" + "Notes:\n" + "\n" + " * Use `//' for integer division: `/' gives exact rational division.", 0, /* @tp_traverse@ */ 0, /* @tp_clear@ */ @@ -860,9 +984,9 @@ Notes:\n\ 0, /* @tp_weaklistoffset@ */ 0, /* @tp_iter@ */ 0, /* @tp_iternext@ */ - mp_pymethods, /* @tp_methods@ */ + PYMETHODS(mp), /* @tp_methods@ */ 0, /* @tp_members@ */ - mp_pygetset, /* @tp_getset@ */ + PYGETSET(mp), /* @tp_getset@ */ 0, /* @tp_base@ */ 0, /* @tp_dict@ */ 0, /* @tp_descr_get@ */ @@ -875,45 +999,6 @@ Notes:\n\ 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 (!good_radix_p(r, 1)) VALERR("bad radix"); - 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); -} - -#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 - /*----- Products of small integers ----------------------------------------*/ typedef struct mpmul_pyobj { @@ -938,10 +1023,10 @@ static PyObject *mmmeth_factor(PyObject *me, PyObject *arg) mp *x; if (!MPMUL_LIVEP(me)) VALERR("MPMul object invalid"); - if (PyTuple_Size(arg) != 1) + if (PyTuple_GET_SIZE(arg) != 1) i = PyObject_GetIter(arg); else { - if ((q = PyTuple_GetItem(arg, 0)) == 0) goto end; + if ((q = PyTuple_GET_ITEM(arg, 0)) == 0) goto end; if ((i = PyObject_GetIter(q)) == 0) { PyErr_Clear(); /* that's ok */ i = PyObject_GetIter(arg); @@ -995,24 +1080,24 @@ end: static PyObject *mmget_livep(PyObject *me, void *hunoz) { return (getbool(MPMUL_LIVEP(me))); } -static PyGetSetDef mpmul_pygetset[] = { +static const PyGetSetDef mpmul_pygetset[] = { #define GETSETNAME(op, name) mm##op##_##name - GET (livep, "MM.livep -> flag: object still valid?") + GET (livep, "MM.livep -> flag: object still valid?") #undef GETSETNAME { 0 } }; -static PyMethodDef mpmul_pymethods[] = { +static const PyMethodDef mpmul_pymethods[] = { #define METHNAME(name) mmmeth_##name - METH (factor, "MM.factor(ITERABLE) or MM.factor(I, ...)") - METH (done, "MM.done() -> PRODUCT") + METH (factor, "MM.factor(ITERABLE) or MM.factor(I, ...)") + METH (done, "MM.done() -> PRODUCT") #undef METHNAME { 0 } }; static PyTypeObject *mpmul_pytype, mpmul_pytype_skel = { PyObject_HEAD_INIT(0) 0, /* Header */ - "catacomb.MPMul", /* @tp_name@ */ + "MPMul", /* @tp_name@ */ sizeof(mpmul_pyobj), /* @tp_basicsize@ */ 0, /* @tp_itemsize@ */ @@ -1035,7 +1120,7 @@ static PyTypeObject *mpmul_pytype, mpmul_pytype_skel = { Py_TPFLAGS_BASETYPE, /* @tp_doc@ */ -"An object for multiplying many small integers.", + "MPMul(N_0, N_1, ....): an object for multiplying many small integers.", 0, /* @tp_traverse@ */ 0, /* @tp_clear@ */ @@ -1043,9 +1128,9 @@ static PyTypeObject *mpmul_pytype, mpmul_pytype_skel = { 0, /* @tp_weaklistoffset@ */ 0, /* @tp_iter@ */ 0, /* @tp_iternext@ */ - mpmul_pymethods, /* @tp_methods@ */ + PYMETHODS(mpmul), /* @tp_methods@ */ 0, /* @tp_members@ */ - mpmul_pygetset, /* @tp_getset@ */ + PYGETSET(mpmul), /* @tp_getset@ */ 0, /* @tp_base@ */ 0, /* @tp_dict@ */ 0, /* @tp_descr_get@ */ @@ -1160,7 +1245,7 @@ fail: 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; @@ -1200,7 +1285,7 @@ fail: 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), @@ -1228,10 +1313,10 @@ static void mpmont_pydealloc(PyObject *me) static PyObject *mpmont_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw) { mpmont_pyobj *mm = 0; - char *kwlist[] = { "m", 0 }; + static const char *const kwlist[] = { "m", 0 }; mp *xx = 0; - if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx)) + 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); @@ -1250,7 +1335,7 @@ static PyObject *mmget_r(PyObject *me, void *hunoz) static PyObject *mmget_r2(PyObject *me, void *hunoz) { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r2))); } -static PyGetSetDef mpmont_pygetset[] = { +static const PyGetSetDef mpmont_pygetset[] = { #define GETSETNAME(op, name) mm##op##_##name GET (m, "M.m -> modulus for reduction") GET (r, "M.r -> multiplicative identity") @@ -1259,27 +1344,27 @@ static PyGetSetDef mpmont_pygetset[] = { { 0 } }; -static PyMethodDef mpmont_pymethods[] = { +static const PyMethodDef mpmont_pymethods[] = { #define METHNAME(name) mmmeth_##name - METH (int, "M.out(X) -> XR") + METH (int, "M.int(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 (mexpr, "M.mexpr([(XR0, N0), (XR1, N1), ...]) = ZR " + "where Z = X0^N0 X1^N1 ... mod M.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.)") + METH (mexp, "M.mexp([(X0, N0), (X1, N1), ...]) = " + "X0^N0 X1^N1 ... mod M.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(0) 0, /* Header */ - "catacomb.MPMont", /* @tp_name@ */ + "MPMont", /* @tp_name@ */ sizeof(mpmont_pyobj), /* @tp_basicsize@ */ 0, /* @tp_itemsize@ */ @@ -1302,7 +1387,7 @@ static PyTypeObject *mpmont_pytype, mpmont_pytype_skel = { Py_TPFLAGS_BASETYPE, /* @tp_doc@ */ -"A Montgomery reduction context.", + "MPMont(N): a Montgomery reduction context.", 0, /* @tp_traverse@ */ 0, /* @tp_clear@ */ @@ -1310,9 +1395,9 @@ static PyTypeObject *mpmont_pytype, mpmont_pytype_skel = { 0, /* @tp_weaklistoffset@ */ 0, /* @tp_iter@ */ 0, /* @tp_iternext@ */ - mpmont_pymethods, /* @tp_methods@ */ + PYMETHODS(mpmont), /* @tp_methods@ */ 0, /* @tp_members@ */ - mpmont_pygetset, /* @tp_getset@ */ + PYGETSET(mpmont), /* @tp_getset@ */ 0, /* @tp_base@ */ 0, /* @tp_dict@ */ 0, /* @tp_descr_get@ */ @@ -1353,7 +1438,7 @@ end: 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), @@ -1382,10 +1467,10 @@ static PyObject *mpbarrett_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw) { mpbarrett_pyobj *mb = 0; - char *kwlist[] = { "m", 0 }; + static const char *const kwlist[] = { "m", 0 }; mp *xx = 0; - if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx)) + 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); @@ -1398,27 +1483,27 @@ end: static PyObject *mbget_m(PyObject *me, void *hunoz) { return (mp_pywrap(MP_COPY(MPBARRETT_PY(me)->m))); } -static PyGetSetDef mpbarrett_pygetset[] = { +static const PyGetSetDef mpbarrett_pygetset[] = { #define GETSETNAME(op, name) mb##op##_##name GET (m, "B.m -> modulus for reduction") #undef GETSETNAME { 0 } }; -static PyMethodDef mpbarrett_pymethods[] = { +static const 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.)") + 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(0) 0, /* Header */ - "catacomb.MPBarrett", /* @tp_name@ */ + "MPBarrett", /* @tp_name@ */ sizeof(mpbarrett_pyobj), /* @tp_basicsize@ */ 0, /* @tp_itemsize@ */ @@ -1441,7 +1526,7 @@ static PyTypeObject *mpbarrett_pytype, mpbarrett_pytype_skel = { Py_TPFLAGS_BASETYPE, /* @tp_doc@ */ -"A Barrett reduction context.", + "MPBarrett(N): a Barrett reduction context.", 0, /* @tp_traverse@ */ 0, /* @tp_clear@ */ @@ -1449,9 +1534,9 @@ static PyTypeObject *mpbarrett_pytype, mpbarrett_pytype_skel = { 0, /* @tp_weaklistoffset@ */ 0, /* @tp_iter@ */ 0, /* @tp_iternext@ */ - mpbarrett_pymethods, /* @tp_methods@ */ + PYMETHODS(mpbarrett), /* @tp_methods@ */ 0, /* @tp_members@ */ - mpbarrett_pygetset, /* @tp_getset@ */ + PYGETSET(mpbarrett), /* @tp_getset@ */ 0, /* @tp_base@ */ 0, /* @tp_dict@ */ 0, /* @tp_descr_get@ */ @@ -1512,10 +1597,10 @@ static PyObject *mpreduce_pynew(PyTypeObject *ty, { mpreduce_pyobj *mr = 0; mpreduce r; - char *kwlist[] = { "m", 0 }; + static const char *const kwlist[] = { "m", 0 }; mp *xx = 0; - if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx)) + 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 - ...)"); @@ -1529,14 +1614,14 @@ end: static PyObject *mrget_m(PyObject *me, void *hunoz) { return (mp_pywrap(MP_COPY(MPREDUCE_PY(me)->p))); } -static PyGetSetDef mpreduce_pygetset[] = { +static const PyGetSetDef mpreduce_pygetset[] = { #define GETSETNAME(op, name) mr##op##_##name GET (m, "R.m -> modulus for reduction") #undef GETSETNAME { 0 } }; -static PyMethodDef mpreduce_pymethods[] = { +static const const 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") @@ -1546,7 +1631,7 @@ static PyMethodDef mpreduce_pymethods[] = { static PyTypeObject *mpreduce_pytype, mpreduce_pytype_skel = { PyObject_HEAD_INIT(0) 0, /* Header */ - "catacomb.MPReduce", /* @tp_name@ */ + "MPReduce", /* @tp_name@ */ sizeof(mpreduce_pyobj), /* @tp_basicsize@ */ 0, /* @tp_itemsize@ */ @@ -1569,7 +1654,7 @@ static PyTypeObject *mpreduce_pytype, mpreduce_pytype_skel = { Py_TPFLAGS_BASETYPE, /* @tp_doc@ */ -"A reduction context for reduction modulo primes of special form.", + "MPReduce(N): a reduction context for reduction modulo Solinas primes.", 0, /* @tp_traverse@ */ 0, /* @tp_clear@ */ @@ -1577,9 +1662,9 @@ static PyTypeObject *mpreduce_pytype, mpreduce_pytype_skel = { 0, /* @tp_weaklistoffset@ */ 0, /* @tp_iter@ */ 0, /* @tp_iternext@ */ - mpreduce_pymethods, /* @tp_methods@ */ + PYMETHODS(mpreduce), /* @tp_methods@ */ 0, /* @tp_members@ */ - mpreduce_pygetset, /* @tp_getset@ */ + PYGETSET(mpreduce), /* @tp_getset@ */ 0, /* @tp_base@ */ 0, /* @tp_dict@ */ 0, /* @tp_descr_get@ */ @@ -1607,16 +1692,17 @@ static PyObject *mcmeth_solve(PyObject *me, PyObject *arg) PyObject *q = 0, *x, *z = 0; mp *xx; mp **v = 0; - int i = 0, n = c->k; + Py_ssize_t i = 0, n = c->k; Py_INCREF(me); - if (PyTuple_Size(arg) == n) + if (PyTuple_GET_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"); + i = PySequence_Size(q); if (i < 0) goto end; + if (i != 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; @@ -1646,30 +1732,41 @@ static void mpcrt_pydealloc(PyObject *me) static PyObject *mpcrt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw) { mpcrt_mod *v = 0; - int n, i = 0; - char *kwlist[] = { "mv", 0 }; + Py_ssize_t n, i = 0, j; + static const char *const kwlist[] = { "mv", 0 }; PyObject *q = 0, *x; - mp *xx; + mp *xx = MP_NEW, *y = MP_NEW, *g = MP_NEW; + mpmul mm; mpcrt_pyobj *c = 0; - if (PyTuple_Size(arg) > 1) + if (PyTuple_GET_SIZE(arg) > 1) q = arg; - else if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &q)) + 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; + n = PySequence_Size(q); if (n < 0) 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; + if (MP_CMP(xx, <=, MP_ZERO)) VALERR("moduli must be positive"); + v[i].m = xx; v[i].n = 0; v[i].ni = 0; v[i].nni = 0; xx = MP_NEW; + } + mpmul_init(&mm); + for (j = 0; j < i; j++) mpmul_add(&mm, v[j].m); + xx = mpmul_done(&mm); + for (j = 0; j < i; j++) { + mp_div(&y, 0, xx, v[j].m); + mp_gcd(&g, 0, 0, y, v[j].m); + if (!MP_EQ(g, MP_ONE)) VALERR("moduli must be pairwise coprime"); } + c = (mpcrt_pyobj *)ty->tp_alloc(ty, 0); mpcrt_create(&c->c, v, n, 0); Py_DECREF(q); + mp_drop(xx); mp_drop(y); mp_drop(g); return ((PyObject *)c); end: @@ -1680,6 +1777,7 @@ end: xfree(v); } Py_XDECREF(q); + mp_drop(xx); mp_drop(y); mp_drop(g); return (0); } @@ -1694,11 +1792,11 @@ static PyObject *mcget_moduli(PyObject *me, void *hunoz) 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)); + PyList_SET_ITEM(q, i, mp_pywrap(c->v[i].m)); return (q); } -static PyGetSetDef mpcrt_pygetset[] = { +static const 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") @@ -1706,7 +1804,7 @@ static PyGetSetDef mpcrt_pygetset[] = { { 0 } }; -static PyMethodDef mpcrt_pymethods[] = { +static const PyMethodDef mpcrt_pymethods[] = { #define METHNAME(name) mcmeth_##name METH (solve, "C.solve([R0, R1]) -> X mod C.product") #undef METHNAME @@ -1715,7 +1813,7 @@ static PyMethodDef mpcrt_pymethods[] = { static PyTypeObject *mpcrt_pytype, mpcrt_pytype_skel = { PyObject_HEAD_INIT(0) 0, /* Header */ - "catacomb.MPCRT", /* @tp_name@ */ + "MPCRT", /* @tp_name@ */ sizeof(mpcrt_pyobj), /* @tp_basicsize@ */ 0, /* @tp_itemsize@ */ @@ -1738,7 +1836,7 @@ static PyTypeObject *mpcrt_pytype, mpcrt_pytype_skel = { Py_TPFLAGS_BASETYPE, /* @tp_doc@ */ -"A context for the solution of Chinese Remainder Theorem problems.", + "MPCRT(SEQ): a context for solving Chinese Remainder Theorem problems.", 0, /* @tp_traverse@ */ 0, /* @tp_clear@ */ @@ -1746,9 +1844,9 @@ static PyTypeObject *mpcrt_pytype, mpcrt_pytype_skel = { 0, /* @tp_weaklistoffset@ */ 0, /* @tp_iter@ */ 0, /* @tp_iternext@ */ - mpcrt_pymethods, /* @tp_methods@ */ + PYMETHODS(mpcrt), /* @tp_methods@ */ 0, /* @tp_members@ */ - mpcrt_pygetset, /* @tp_getset@ */ + PYGETSET(mpcrt), /* @tp_getset@ */ 0, /* @tp_base@ */ 0, /* @tp_dict@ */ 0, /* @tp_descr_get@ */ @@ -1772,7 +1870,7 @@ static PyObject *gf_pyrichcompare(PyObject *x, PyObject *y, int op) int xl, yl; int b; - if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL; + if (gfbinop(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; @@ -1798,9 +1896,9 @@ static PyObject *gf_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw) mp *z; mp_pyobj *zz = 0; int radix = 0; - char *kwlist[] = { "x", "radix", 0 }; + static const char *const kwlist[] = { "x", "radix", 0 }; - if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:gf", kwlist, &x, &radix)) + if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:gf", KWLIST, &x, &radix)) goto end; if (GF_PYCHECK(x)) RETURN_OBJ(x); if (!good_radix_p(radix, 1)) VALERR("radix out of range"); @@ -1819,15 +1917,6 @@ 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; @@ -1907,6 +1996,33 @@ end: return (z); } +static PyObject *gfmeth_fromstring(PyObject *me, + PyObject *arg, PyObject *kw) +{ + int r = 0; + char *p; + Py_ssize_t len; + PyObject *z = 0; + mp *zz; + mptext_stringctx sc; + static const char *const kwlist[] = { "x", "radix", 0 }; + + if (!PyArg_ParseTupleAndKeywords(arg, kw, "s#|i:fromstring", KWLIST, + &p, &len, &r)) + goto end; + if (!good_radix_p(r, 1)) VALERR("bad radix"); + sc.buf = p; sc.lim = p + len; + if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0 || + MP_NEGP(zz)) { + if (zz) MP_DROP(zz); + VALERR("bad binary polynomial"); + } + z = Py_BuildValue("(Ns#)", gf_pywrap(zz), + sc.buf, (Py_ssize_t)(sc.lim - sc.buf)); +end: + return (z); +} + static PyObject *gfmeth_irreduciblep(PyObject *me, PyObject *arg) { if (!PyArg_ParseTuple(arg, ":irreduciblep")) return (0); @@ -1916,7 +2032,7 @@ static PyObject *gfmeth_irreduciblep(PyObject *me, PyObject *arg) static PyObject *gfget_degree(PyObject *me, void *hunoz) { return (PyInt_FromLong(mp_bits(MP_X(me)) - 1)); } -static PyGetSetDef gf_pygetset[] = { +static const PyGetSetDef gf_pygetset[] = { #define GETSETNAME(op, name) gf##op##_##name GET (degree, "X.degree -> polynomial degree of X") #undef GETSETNAME @@ -1927,32 +2043,38 @@ static PyGetSetDef gf_pygetset[] = { { 0 } }; -static PyMethodDef gf_pymethods[] = { +static const 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 (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") + METH (irreduciblep, "X.irreduciblep() -> true/false") + KWSMTH(fromstring, "fromstring(STR, [radix = 0]) -> (X, REST)\n" + " Parse STR as a binary polynomial, according to RADIX. If RADIX is\n" + " zero, read a prefix from STR to decide radix: allow `0b' for binary,\n" + " `0' or `0o' for octal, `0x' for hex, or `R_' for other radix R.") + SMTH (loadl, "loadl(STR) -> X: read little-endian bytes") + SMTH (loadb, "loadb(STR) -> X: read big-endian bytes") + SMTH (frombuf, "frombuf(STR) -> (X, REST): read buffer format") #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") + 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 = { +static const PyNumberMethods gf_pynumber = { gf_pyadd, /* @nb_add@ */ gf_pysub, /* @nb_subtract@ */ gf_pymul, /* @nb_multiply@ */ @@ -1997,7 +2119,7 @@ static PyNumberMethods gf_pynumber = { static PyTypeObject gf_pytype_skel = { PyObject_HEAD_INIT(0) 0, /* Header */ - "catacomb.GF", /* @tp_name@ */ + "GF", /* @tp_name@ */ sizeof(mp_pyobj), /* @tp_basicsize@ */ 0, /* @tp_itemsize@ */ @@ -2007,10 +2129,10 @@ static PyTypeObject gf_pytype_skel = { 0, /* @tp_setattr@ */ 0, /* @tp_compare@ */ gf_pyrepr, /* @tp_repr@ */ - &gf_pynumber, /* @tp_as_number@ */ + PYNUMBER(gf), /* @tp_as_number@ */ 0, /* @tp_as_sequence@ */ 0, /* @tp_as_mapping@ */ - gf_pyhash, /* @tp_hash@ */ + mp_pyhash, /* @tp_hash@ */ 0, /* @tp_call@ */ mp_pyhex, /* @tp_str@ */ 0, /* @tp_getattro@ */ @@ -2021,19 +2143,21 @@ static PyTypeObject gf_pytype_skel = { 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.", + "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 field elements, elliptic curve\n" + "points, group elements, Python `int' and `long' objects, and anything\n" + "with an integer conversion.\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 Euclidean division: `/' gives exact rational division.", 0, /* @tp_traverse@ */ 0, /* @tp_clear@ */ @@ -2041,9 +2165,9 @@ Notes:\n\ 0, /* @tp_weaklistoffset@ */ 0, /* @tp_iter@ */ 0, /* @tp_iternext@ */ - gf_pymethods, /* @tp_methods@ */ + PYMETHODS(gf), /* @tp_methods@ */ 0, /* @tp_members@ */ - gf_pygetset, /* @tp_getset@ */ + PYGETSET(gf), /* @tp_getset@ */ 0, /* @tp_base@ */ 0, /* @tp_dict@ */ 0, /* @tp_descr_get@ */ @@ -2056,31 +2180,6 @@ Notes:\n\ 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 (!good_radix_p(r, 1)) 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 { @@ -2107,6 +2206,58 @@ end: return (rc); } +static PyObject *grmeth_trace(PyObject *me, PyObject *arg) +{ + PyObject *rc = 0; + mp *xx = 0; + + if (!PyArg_ParseTuple(arg, "O&:trace", convgf, &xx)) goto end; + rc = PyInt_FromLong(gfreduce_trace(GFREDUCE_PY(me), xx)); +end: + if (xx) MP_DROP(xx); + return (rc); +} + +static PyObject *grmeth_halftrace(PyObject *me, PyObject *arg) +{ + PyObject *rc = 0; + mp *xx = 0; + + if (!PyArg_ParseTuple(arg, "O&:halftrace", convgf, &xx)) goto end; + rc = gf_pywrap(gfreduce_halftrace(GFREDUCE_PY(me), MP_NEW, xx)); +end: + if (xx) MP_DROP(xx); + return (rc); +} + +static PyObject *grmeth_sqrt(PyObject *me, PyObject *arg) +{ + PyObject *rc = 0; + mp *xx = 0, *yy; + + if (!PyArg_ParseTuple(arg, "O&:sqrt", convgf, &xx)) goto end; + if ((yy = gfreduce_sqrt(GFREDUCE_PY(me), MP_NEW, xx)) == 0) + VALERR("no modular square root"); + rc = gf_pywrap(yy); +end: + if (xx) MP_DROP(xx); + return (rc); +} + +static PyObject *grmeth_quadsolve(PyObject *me, PyObject *arg) +{ + PyObject *rc = 0; + mp *xx = 0, *yy; + + if (!PyArg_ParseTuple(arg, "O&:quadsolve", convgf, &xx)) goto end; + if ((yy = gfreduce_quadsolve(GFREDUCE_PY(me), MP_NEW, xx)) == 0) + VALERR("no solution found"); + rc = gf_pywrap(yy); +end: + if (xx) MP_DROP(xx); + return (rc); +} + static PyObject *grmeth_reduce(PyObject *me, PyObject *arg) { PyObject *z = 0; @@ -2129,10 +2280,10 @@ static PyObject *gfreduce_pynew(PyTypeObject *ty, { gfreduce_pyobj *mr = 0; gfreduce r; - char *kwlist[] = { "m", 0 }; + static const char *const kwlist[] = { "m", 0 }; mp *xx = 0; - if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convgf, &xx)) + if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", KWLIST, convgf, &xx)) goto end; if (MP_ZEROP(xx)) ZDIVERR("modulus is zero!"); gfreduce_create(&r, xx); @@ -2146,16 +2297,20 @@ end: static PyObject *grget_m(PyObject *me, void *hunoz) { return (gf_pywrap(MP_COPY(GFREDUCE_PY(me)->p))); } -static PyGetSetDef gfreduce_pygetset[] = { +static const PyGetSetDef gfreduce_pygetset[] = { #define GETSETNAME(op, name) gr##op##_##name GET (m, "R.m -> reduction polynomial") #undef GETSETNAME { 0 } }; -static PyMethodDef gfreduce_pymethods[] = { +static const PyMethodDef gfreduce_pymethods[] = { #define METHNAME(name) grmeth_##name METH (reduce, "R.reduce(X) -> X mod B.m") + METH (trace, "R.trace(X) -> Tr(X) = x + x^2 + ... + x^{2^{m - 1}}") + METH (halftrace, "R.halftrace(X) -> x + x^{2^2} + ... + x^{2^{m - 1}}") + METH (sqrt, "R.sqrt(X) -> Y where Y^2 = X mod R") + METH (quadsolve, "R.quadsolve(X) -> Y where Y^2 + Y = X mod R") METH (exp, "R.exp(X, N) -> X^N mod B.m") #undef METHNAME { 0 } @@ -2163,7 +2318,7 @@ static PyMethodDef gfreduce_pymethods[] = { static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = { PyObject_HEAD_INIT(0) 0, /* Header */ - "catacomb.GFReduce", /* @tp_name@ */ + "GFReduce", /* @tp_name@ */ sizeof(gfreduce_pyobj), /* @tp_basicsize@ */ 0, /* @tp_itemsize@ */ @@ -2186,7 +2341,7 @@ static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = { Py_TPFLAGS_BASETYPE, /* @tp_doc@ */ -"A reduction context for reduction modulo sparse irreducible polynomials.", + "GFReduce(N): a context for reduction modulo sparse polynomials.", 0, /* @tp_traverse@ */ 0, /* @tp_clear@ */ @@ -2194,9 +2349,9 @@ static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = { 0, /* @tp_weaklistoffset@ */ 0, /* @tp_iter@ */ 0, /* @tp_iternext@ */ - gfreduce_pymethods, /* @tp_methods@ */ + PYMETHODS(gfreduce), /* @tp_methods@ */ 0, /* @tp_members@ */ - gfreduce_pygetset, /* @tp_getset@ */ + PYGETSET(gfreduce), /* @tp_getset@ */ 0, /* @tp_base@ */ 0, /* @tp_dict@ */ 0, /* @tp_descr_get@ */ @@ -2227,14 +2382,15 @@ static PyObject *gfn_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw) { mp *p = 0, *beta = 0; gfn_pyobj *gg = 0; - char *kwlist[] = { "p", "beta", 0 }; + static const char *const kwlist[] = { "p", "beta", 0 }; - if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&:new", kwlist, + if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&:new", KWLIST, convgf, &p, convgf, &beta)) goto end; gg = PyObject_New(gfn_pyobj, ty); + gg->p = 0; if (gfn_create(p, beta, &gg->ntop, &gg->pton)) { - FREEOBJ(gg); + Py_DECREF(gg); gg = 0; VALERR("can't invert transformation matrix"); } @@ -2266,7 +2422,7 @@ static PyObject *gfnget_beta(PyObject *me, void *hunoz) end: \ mp_drop(xx); \ if (!z) return (0); \ - return (mp_pywrap(z)); \ + return (gf_pywrap(z)); \ } XFORMOP(pton, PTON) XFORMOP(ntop, NTOP) @@ -2274,12 +2430,15 @@ XFORMOP(ntop, NTOP) static void gfn_pydealloc(PyObject *me) { - gfn_destroy(GFN_PTON(me)); - gfn_destroy(GFN_NTOP(me)); + if (GFN_P(me)) { + MP_DROP(GFN_P(me)); + gfn_destroy(GFN_PTON(me)); + gfn_destroy(GFN_NTOP(me)); + } FREEOBJ(me); } -static PyGetSetDef gfn_pygetset[] = { +static const 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") @@ -2287,7 +2446,7 @@ static PyGetSetDef gfn_pygetset[] = { { 0 } }; -static PyMethodDef gfn_pymethods[] = { +static const 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") @@ -2297,7 +2456,7 @@ static PyMethodDef gfn_pymethods[] = { static PyTypeObject gfn_pytype_skel = { PyObject_HEAD_INIT(0) 0, /* Header */ - "catacomb.GFN", /* @tp_name@ */ + "GFN", /* @tp_name@ */ sizeof(gfn_pyobj), /* @tp_basicsize@ */ 0, /* @tp_itemsize@ */ @@ -2320,8 +2479,8 @@ static PyTypeObject gfn_pytype_skel = { Py_TPFLAGS_BASETYPE, /* @tp_doc@ */ -"An object for transforming elements of binary fields between polynomial\n\ -and normal basis representations.", + "GFN(P, BETA): an object for transforming elements of binary fields\n" + " between polynomial and normal basis representations.", 0, /* @tp_traverse@ */ 0, /* @tp_clear@ */ @@ -2329,9 +2488,9 @@ and normal basis representations.", 0, /* @tp_weaklistoffset@ */ 0, /* @tp_iter@ */ 0, /* @tp_iternext@ */ - gfn_pymethods, /* @tp_methods@ */ + PYMETHODS(gfn), /* @tp_methods@ */ 0, /* @tp_members@ */ - gfn_pygetset, /* @tp_getset@ */ + PYGETSET(gfn), /* @tp_getset@ */ 0, /* @tp_base@ */ 0, /* @tp_dict@ */ 0, /* @tp_descr_get@ */ @@ -2346,40 +2505,6 @@ and normal basis representations.", /*----- 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 (_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); @@ -2391,7 +2516,6 @@ void mp_pyinit(void) INITTYPE(mpcrt, root); INITTYPE(gfreduce, root); INITTYPE(gfn, root); - addmethods(methods); } void mp_pyinsert(PyObject *mod)