.gdbinit: Delete this obsolete file.

[catacomb-python] / pgen.c

/* -*-c-*-
 *
 * Prime number generation
 *
 * (c) 2005 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"

/*----- Filters -----------------------------------------------------------*/

PyTypeObject *pfilt_pytype;

static PyObject *pfilt_pywrap(pfilt *f)
{
  pfilt_pyobj *o = 0;
  o = PyObject_New(pfilt_pyobj, pfilt_pytype);
  o->f = *f;
  o->st = pfilt_step(f, 0);
  return ((PyObject *)o);
}

static PyObject *pfilt_pymake(PyTypeObject *ty, PyObject *xobj)
{
  mp *x = 0;
  pfilt_pyobj *o = 0;

  if (PFILT_PYCHECK(xobj)) RETURN_OBJ(xobj);
  if ((x = getmp(xobj)) == 0) goto end;
  o = (pfilt_pyobj *)ty->tp_alloc(ty, 0);
  o->st = pfilt_create(&o->f, x);
end:
  mp_drop(x);
  return ((PyObject *)o);
}

static PyObject *pfilt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
{
  static const char *const kwlist[] = { "x", 0 };
  PyObject *xobj;

  if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", KWLIST, &xobj))
    return (0);
  return (pfilt_pymake(ty, xobj));
}

static void pfilt_pydealloc(PyObject *me)
  { pfilt_destroy(PFILT_F(me)); FREEOBJ(me); }

static PyObject *pfmeth_step(PyObject *me, PyObject *arg)
{
  mpw x;

  if (!PyArg_ParseTuple(arg, "O&:step", convmpw, &x)) return (0);
  PFILT_ST(me) = pfilt_step(PFILT_F(me), x);
  RETURN_ME;
}

static PyObject *pfmeth_muladd(PyObject *me, PyObject *arg)
{
  mpw m, a;
  pfilt_pyobj *o = 0;

  if (!PyArg_ParseTuple(arg, "O&O&:muladd", convmpw, &m, convmpw, &a))
    return (0);
  o = PyObject_New(pfilt_pyobj, pfilt_pytype);
  o->st = pfilt_muladd(&o->f, PFILT_F(me), m, a);
  return ((PyObject *)o);
}

static CONVFUNC(pfilt, pfilt *, PFILT_F)

static PyObject *pfmeth_jump(PyObject *me, PyObject *arg)
{
  pfilt *f;

  if (!PyArg_ParseTuple(arg, "O&:jump", convpfilt, &f)) return (0);
  PFILT_ST(me) = pfilt_jump(PFILT_F(me), f);
  RETURN_ME;
}

static PyObject *meth__PrimeFilter_smallfactor(PyObject *me, PyObject *arg)
{
  mp *x = 0;
  PyObject *rc = 0;

  if (!PyArg_ParseTuple(arg, "OO&:smallfactor", &me, convmp, &x)) goto end;
  rc = PyInt_FromLong(pfilt_smallfactor(x));
end:
  mp_drop(x);
  return (rc);
}

static int pfilt_pynonzerop(PyObject *me)
  { return (PFILT_ST(me) != PGEN_FAIL); }

static PyObject *pfilt_pyint(PyObject *me)
{
  long l;
  PyObject *rc = 0;

  if (!mp_tolong_checked(PFILT_F(me)->m, &l, 0)) rc = PyInt_FromLong(l);
  else rc = mp_topylong(PFILT_F(me)->m);
  return (rc);
}

static PyObject *pfilt_pylong(PyObject *me)
  { return (mp_topylong(PFILT_F(me)->m)); }

static PyObject *pfget_x(PyObject *me, void *hunoz)
  { return (mp_pywrap(MP_COPY(PFILT_F(me)->m))); }

static PyObject *pfget_status(PyObject *me, void *hunoz)
  { return (PyInt_FromLong(PFILT_ST(me))); }

static PyGetSetDef pfilt_pygetset[] = {
#define GETSETNAME(op, name) pf##op##_##name
  GET	(x,		"F.x -> current position of filter")
  GET	(status,	"F.status -> primality status of filter")
#undef GETSETNAME
  { 0 }
};

static PyMethodDef pfilt_pymethods[] = {
#define METHNAME(name) pfmeth_##name
  METH	(step,		"F.step(N)")
  METH	(muladd,	"F.muladd(M, A)")
  METH	(jump,		"F.jump(FF)")
#undef METHNAME
  { 0 }
};

static PyNumberMethods pfilt_pynumber = {
  0,					/* @nb_add@ */
  0,					/* @nb_subtract@ */
  0,					/* @nb_multiply@ */
  0,					/* @nb_divide@ */
  0,					/* @nb_remainder@ */
  0,					/* @nb_divmod@ */
  0,					/* @nb_power@ */
  0,					/* @nb_negative@ */
  0,					/* @nb_positive@ */
  0,					/* @nb_absolute@ */
  pfilt_pynonzerop,			/* @nb_nonzero@ */
  0,					/* @nb_invert@ */
  0,					/* @nb_lshift@ */
  0,					/* @nb_rshift@ */
  0,					/* @nb_and@ */
  0,					/* @nb_xor@ */
  0,					/* @nb_or@ */
  0,					/* @nb_coerce@ */
  pfilt_pyint,				/* @nb_int@ */
  pfilt_pylong,				/* @nb_long@ */
  0,					/* @nb_float@ */
  0,					/* @nb_oct@ */
  0,					/* @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@ */

  0,					/* @nb_floor_divide@ */
  0,					/* @nb_true_divide@ */
  0,					/* @nb_inplace_floor_divide@ */
  0,					/* @nb_inplace_true_divide@ */
};

static PyTypeObject pfilt_pytype_skel = {
  PyObject_HEAD_INIT(0) 0,		/* Header */
  "PrimeFilter",			/* @tp_name@ */
  sizeof(pfilt_pyobj),			/* @tp_basicsize@ */
  0,					/* @tp_itemsize@ */

  pfilt_pydealloc,			/* @tp_dealloc@ */
  0,					/* @tp_print@ */
  0,					/* @tp_getattr@ */
  0,					/* @tp_setattr@ */
  0,					/* @tp_compare@ */
  0,					/* @tp_repr@ */
  &pfilt_pynumber,			/* @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@ */
"PrimeFilter(X): small-primes filter.",

  0,					/* @tp_traverse@ */
  0,					/* @tp_clear@ */
  0,					/* @tp_richcompare@ */
  0,					/* @tp_weaklistoffset@ */
  0,					/* @tp_iter@ */
  0,					/* @tp_iternext@ */
  pfilt_pymethods,			/* @tp_methods@ */
  0,					/* @tp_members@ */
  pfilt_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@ */
  pfilt_pynew,				/* @tp_new@ */
  0,					/* @tp_free@ */
  0					/* @tp_is_gc@ */
};

/*----- Rabin-Miller testing ----------------------------------------------*/

typedef struct rabin_pyobj {
  PyObject_HEAD
  rabin r;
} rabin_pyobj;

static PyTypeObject *rabin_pytype;
#define RABIN_R(o) (&((rabin_pyobj *)(o))->r)

static PyObject *rabin_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
{
  mp *x = 0;
  rabin_pyobj *o = 0;
  static const char *const kwlist[] = { "x", 0 };

  if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", KWLIST, convmp, &x))
    goto end;
  if (!MP_POSP(x) || MP_EVENP(x)) VALERR("must be positive and odd");
  o = (rabin_pyobj *)ty->tp_alloc(ty, 0);
  rabin_create(&o->r, x);
end:
  return ((PyObject *)o);
}

static void rabin_pydealloc(PyObject *me)
{
  rabin_destroy(RABIN_R(me));
  FREEOBJ(me);
}

static PyObject *rmeth_test(PyObject *me, PyObject *arg)
{
  mp *w = 0;
  PyObject *rc = 0;

  if (!PyArg_ParseTuple(arg, "O&:test", convmp, &w)) goto end;
  rc = PyInt_FromLong(rabin_test(RABIN_R(me), w));
end:
  mp_drop(w);
  return (rc);
}

static PyObject *rmeth_rtest(PyObject *me, PyObject *arg)
{
  mp *w = 0;
  PyObject *rc = 0;

  if (!PyArg_ParseTuple(arg, "O&:rtest", convmp, &w)) goto end;
  rc = PyInt_FromLong(rabin_rtest(RABIN_R(me), w));
end:
  mp_drop(w);
  return (rc);
}

static PyObject *rget_niters(PyObject *me, void *hunoz)
  { return (PyInt_FromLong(rabin_iters(mp_bits(RABIN_R(me)->mm.m)))); }

static PyObject *rget_x(PyObject *me, void *hunoz)
  { return (mp_pywrap(MP_COPY(RABIN_R(me)->mm.m))); }

static PyObject *meth__RabinMiller_iters(PyObject *me, PyObject *arg)
{
  unsigned n;

  if (!PyArg_ParseTuple(arg, "OO&:iters", &me, convuint, &n)) return (0);
  return (PyInt_FromLong(rabin_iters(n)));
}

static PyGetSetDef rabin_pygetset[] = {
#define GETSETNAME(op, name) r##op##_##name
  GET	(x,		"R.x -> number under test")
  GET	(niters,	"R.niters -> suggested number of tests")
#undef GETSETNAME
  { 0 }
};

static PyMethodDef rabin_pymethods[] = {
#define METHNAME(name) rmeth_##name
  METH	(test,		"R.test(W) -> PGST")
  METH	(rtest,		"R.rtest(W) -> PGST")
#undef METHNAME
  { 0 }
};

static PyTypeObject rabin_pytype_skel = {
  PyObject_HEAD_INIT(0) 0,		/* Header */
  "RabinMiller",			/* @tp_name@ */
  sizeof(rabin_pyobj),			/* @tp_basicsize@ */
  0,					/* @tp_itemsize@ */

  rabin_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@ */
"RabinMiller(X): Rabin-Miller strong primality test.",

  0,					/* @tp_traverse@ */
  0,					/* @tp_clear@ */
  0,					/* @tp_richcompare@ */
  0,					/* @tp_weaklistoffset@ */
  0,					/* @tp_iter@ */
  0,					/* @tp_iternext@ */
  rabin_pymethods,			/* @tp_methods@ */
  0,					/* @tp_members@ */
  rabin_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@ */
  rabin_pynew,				/* @tp_new@ */
  0,					/* @tp_free@ */
  0					/* @tp_is_gc@ */
};

/*----- Events ------------------------------------------------------------*/

typedef struct pgevent_pyobj {
  PyObject_HEAD
  PyObject *r;
  pgen_event *ev;
} pgevent_pyobj;

static PyTypeObject *pgevent_pytype;
#define PGEVENT_EV(o) (((pgevent_pyobj *)(o))->ev)

static PyObject *pgevent_pywrap(pgen_event *ev)
{
  pgevent_pyobj *o = PyObject_New(pgevent_pyobj, pgevent_pytype);
  o->ev = ev; o->r = 0;
  return ((PyObject *)o);
}

static CONVFUNC(pgevent, pgen_event *, PGEVENT_EV)

static void pgevent_kill(PyObject *me)
{
  pgevent_pyobj *ev = (pgevent_pyobj *)me;

  ev->ev = 0;
  if (ev->r) GRAND_R(ev->r) = 0;
}

static void pgevent_pydealloc(PyObject *me)
{
  pgevent_pyobj *ev = (pgevent_pyobj *)me;
  if (ev->r) Py_DECREF(ev->r);
  FREEOBJ(me);
}

#define PGEVENT_CHECK(me) do {						\
  if (!PGEVENT_EV(me)) {						\
    PyErr_SetString(PyExc_ValueError, "event object is no longer valid"); \
    return (0);								\
  }									\
} while (0)

static PyObject *peget_name(PyObject *me, void *hunoz)
  { PGEVENT_CHECK(me); return (PyString_FromString(PGEVENT_EV(me)->name)); }

static PyObject *peget_x(PyObject *me, void *hunoz)
  { PGEVENT_CHECK(me); return (mp_pywrap(MP_COPY(PGEVENT_EV(me)->m))); }

static PyObject *peget_steps(PyObject *me, void *hunoz)
  { PGEVENT_CHECK(me); return (PyInt_FromLong(PGEVENT_EV(me)->steps)); }

static PyObject *peget_tests(PyObject *me, void *hunoz)
  { PGEVENT_CHECK(me); return (PyInt_FromLong(PGEVENT_EV(me)->tests)); }

static PyObject *peget_rng(PyObject *me, void *hunoz)
{
  pgevent_pyobj *ev = (pgevent_pyobj *)me;

  PGEVENT_CHECK(me);
  if (!ev->r) ev->r = grand_pywrap(ev->ev->r, 0);
  Py_INCREF(ev->r); return ((PyObject *)ev->r);
}

static int peset_x(PyObject *me, PyObject *xobj, void *hunoz)
{
  mp *x = 0;
  pgen_event *ev = PGEVENT_EV(me);
  int rc = -1;
  if (!xobj) NIERR("__del__");
  PGEVENT_CHECK(me);
  if ((x = getmp(xobj)) == 0) goto end;
  mp_drop(ev->m);
  ev->m = MP_COPY(x);
  rc = 0;
end:
  mp_drop(x);
  return (rc);
}

static PyGetSetDef pgevent_pygetset[] = {
#define GETSETNAME(op, name) pe##op##_##name
  GET	(name,		"EV.name -> value being generated")
  GETSET(x,		"EV.x -> value under test")
  GET	(steps,		"EV.steps -> number of steps left")
  GET	(tests,		"EV.tests -> tests before passing")
  GET	(rng,		"EV.rng -> (noncrypto) random number generator")
#undef GETSETNAME
  { 0 }
};

static PyTypeObject pgevent_pytype_skel = {
  PyObject_HEAD_INIT(0) 0,		/* Header */
  "PrimeGenEvent",			/* @tp_name@ */
  sizeof(pgevent_pyobj),		/* @tp_basicsize@ */
  0,					/* @tp_itemsize@ */

  pgevent_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@ */
"Prime-generation event.",

  0,					/* @tp_traverse@ */
  0,					/* @tp_clear@ */
  0,					/* @tp_richcompare@ */
  0,					/* @tp_weaklistoffset@ */
  0,					/* @tp_iter@ */
  0,					/* @tp_iternext@ */
  0,					/* @tp_methods@ */
  0,					/* @tp_members@ */
  pgevent_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@ */
  abstract_pynew,			/* @tp_new@ */
  0,					/* @tp_free@ */
  0					/* @tp_is_gc@ */
};

/*----- Event handlers ----------------------------------------------------*/

PyTypeObject *pgev_pytype;

typedef struct pgstep_pyobj {
  PGEV_HEAD
  pgen_filterctx f;
} pgstep_pyobj;

static PyTypeObject *pgstep_pytype;
#define PGSTEP_STEP(o) (((pgstep_pyobj *)(o))->f.step)

typedef struct pgjump_pyobj {
  PGEV_HEAD
  PyObject *fobj;
  pgen_jumpctx j;
} pgjump_pyobj;

static PyTypeObject *pgjump_pytype;
#define PGJUMP_FOBJ(o) (((pgjump_pyobj *)(o))->fobj)
#define PGJUMP_J(o) (&((pgjump_pyobj *)(o))->j)

typedef struct pgtest_pyobj {
  PGEV_HEAD
  rabin r;
} pgtest_pyobj;

static PyTypeObject *pgtest_pytype;

static int pgev_python(int rq, pgen_event *ev, void *p)
{
  pypgev *pg = p;
  PyObject *pyev = 0;
  PyObject *rc = 0;
  int st = PGEN_ABORT;
  long l;
  static const char *const meth[] =
    { "pg_abort", "pg_done", "pg_begin", "pg_try", "pg_fail", "pg_pass" };

  rq++;
  if (rq > N(meth)) SYSERR("event code out of range");
  pyev = pgevent_pywrap(ev);
  if ((rc = PyObject_CallMethod(pg->obj, (/*unconst*/ char *)meth[rq],
				"(O)", pyev)) == 0)
    goto end;
  if (rc == Py_None)
    st = PGEN_TRY;
  else if ((l = PyInt_AsLong(rc)) == -1 && PyErr_Occurred())
    goto end;
  else if (l < PGEN_ABORT || l > PGEN_PASS)
    VALERR("return code out of range");
  else
    st = l;
end:
  if (PyErr_Occurred())
    stash_exception(pg->exc, "exception from `pgen' handler");
  if (pyev) {
    pgevent_kill(pyev);
    Py_DECREF(pyev);
  }
  Py_XDECREF(rc);
  return (st);
}

static PyObject *pgev_pywrap(const pgev *pg)
{
  pgev_pyobj *o;

  o = PyObject_New(pgev_pyobj, pgev_pytype);
  o->pg = *pg;
  return ((PyObject *)o);
}

int convpgev(PyObject *o, void *p)
{
  pypgev *pg = p;

  if (PGEV_PYCHECK(o))
    pg->ev = *PGEV_PG(o);
  else {
    pg->ev.proc = pgev_python;
    pg->ev.ctx = pg;
    pg->obj = o; Py_INCREF(o);
  }
  return (1);
}

void droppgev(pypgev *pg)
{
  if (pg->ev.proc == pgev_python)
    { assert(pg->ev.ctx == pg); Py_DECREF(pg->obj); }
}

static PyObject *pgmeth_common(PyObject *me, PyObject *arg, int rq)
{
  pgen_event *ev;
  pgev *pg = PGEV_PG(me);
  PyObject *rc = 0;

  if (!PyArg_ParseTuple(arg, "O&", convpgevent, &ev)) goto end;
  rc = PyInt_FromLong(!pg->proc ? rq : pg->proc(rq, ev, pg->ctx));
end:
  return (rc);
}

#define PGMETH(lc, uc)							\
  static PyObject *pgmeth_pg_##lc(PyObject *me, PyObject *arg)		\
    { return pgmeth_common(me, arg, PGEN_##uc); }
PGMETH(abort,	ABORT)
PGMETH(done,	DONE)
PGMETH(begin,	BEGIN)
PGMETH(try,	TRY)
PGMETH(pass,	PASS)
PGMETH(fail,	FAIL)
#undef PGMETH

static PyObject *pgev_stdev(pgen_proc *proc)
  { pgev pg; pg.proc = proc; pg.ctx = 0; return (pgev_pywrap(&pg)); }

static PyMethodDef pgev_pymethods[] = {
#define METHNAME(name) pgmeth_##name
  METH	(pg_abort,	"E.pg_abort(EV) -> PGRC -- prime generation aborted")
  METH	(pg_done,	"E.pg_done(EV) -> PGRC -- prime generation finished")
  METH	(pg_begin,     "E.pg_begin(EV) -> PGRC -- commence stepping/testing")
  METH	(pg_try,	"E.pg_try(EV) -> PGRC -- found new candidate")
  METH	(pg_pass,	"E.pg_pass(EV) -> PGRC -- passed primality test")
  METH	(pg_fail,	"E.pg_fail(EV) -> PGRC -- failed primality test")
#undef METHNAME
  { 0 }
};

static PyTypeObject pgev_pytype_skel = {
  PyObject_HEAD_INIT(0) 0,		/* Header */
  "PrimeGenBuiltinHandler",		/* @tp_name@ */
  sizeof(pgev_pyobj),			/* @tp_basicsize@ */
  0,					/* @tp_itemsize@ */

  0,					/* @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@ */
"Built-in prime-generation event handler, base class.",

  0,					/* @tp_traverse@ */
  0,					/* @tp_clear@ */
  0,					/* @tp_richcompare@ */
  0,					/* @tp_weaklistoffset@ */
  0,					/* @tp_iter@ */
  0,					/* @tp_iternext@ */
  pgev_pymethods,			/* @tp_methods@ */
  0,					/* @tp_members@ */
  0,					/* @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@ */
  abstract_pynew,			/* @tp_new@ */
  0,					/* @tp_free@ */
  0					/* @tp_is_gc@ */
};

static PyObject *pgstep_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
{
  mpw s;
  pgstep_pyobj *rc = 0;
  static const char *const kwlist[] = { "step", 0 };

  if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", KWLIST, convmpw, &s))
    goto end;
  rc = (pgstep_pyobj *)ty->tp_alloc(ty, 0);
  rc->f.step = s;
  rc->pg.proc = pgen_filter;
  rc->pg.ctx = &rc->f;
end:
  return ((PyObject *)rc);
}

static PyObject *psget_step(PyObject *me, void *hunoz)
  { return (PyInt_FromLong(PGSTEP_STEP(me))); }

static PyGetSetDef pgstep_pygetset[] = {
#define GETSETNAME(op, name) ps##op##_##name
  GET	(step,		"S.step -> step size for the stepper")
#undef GETSETNAME
  { 0 }
};

static PyTypeObject pgstep_pytype_skel = {
  PyObject_HEAD_INIT(0) 0,		/* Header */
  "PrimeGenStepper",			/* @tp_name@ */
  sizeof(pgstep_pyobj),			/* @tp_basicsize@ */
  0,					/* @tp_itemsize@ */

  0,					/* @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@ */
"PrimeGenStepper(STEP): simple stepper with small-factors filter.",

  0,					/* @tp_traverse@ */
  0,					/* @tp_clear@ */
  0,					/* @tp_richcompare@ */
  0,					/* @tp_weaklistoffset@ */
  0,					/* @tp_iter@ */
  0,					/* @tp_iternext@ */
  0,					/* @tp_methods@ */
  0,					/* @tp_members@ */
  pgstep_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@ */
  pgstep_pynew,				/* @tp_new@ */
  0,					/* @tp_free@ */
  0					/* @tp_is_gc@ */
};

static PyObject *pgjump_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
{
  PyObject *o, *fobj;
  pgjump_pyobj *rc = 0;
  static const char *const kwlist[] = { "jump", 0 };

  if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", KWLIST, &o) ||
      (fobj = pfilt_pymake(pfilt_pytype, o)) == 0)
    goto end;
  rc = (pgjump_pyobj *)ty->tp_alloc(ty, 0);
  rc->fobj = fobj;
  rc->j.j = PFILT_F(fobj);
  rc->pg.proc = pgen_jump;
  rc->pg.ctx = &rc->j;
end:
  return ((PyObject *)rc);
}

static void pgjump_pydealloc(PyObject *me)
{
  Py_DECREF(PGJUMP_FOBJ(me));
  FREEOBJ(me);
}

static PyObject *pjget_jump(PyObject *me, void *hunoz)
  { RETURN_OBJ(PGJUMP_FOBJ(me)); }

static PyGetSetDef pgjump_pygetset[] = {
#define GETSETNAME(op, name) pj##op##_##name
  GET	(jump,		"S.jump -> jump size for the stepper")
#undef GETSETNAME
  { 0 }
};

static PyTypeObject pgjump_pytype_skel = {
  PyObject_HEAD_INIT(0) 0,		/* Header */
  "PrimeGenJumper",			/* @tp_name@ */
  sizeof(pgjump_pyobj),			/* @tp_basicsize@ */
  0,					/* @tp_itemsize@ */

  pgjump_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@ */
"PrimeGenJumper(JUMP): stepper for larger steps with small-factors filter.",

  0,					/* @tp_traverse@ */
  0,					/* @tp_clear@ */
  0,					/* @tp_richcompare@ */
  0,					/* @tp_weaklistoffset@ */
  0,					/* @tp_iter@ */
  0,					/* @tp_iternext@ */
  0,					/* @tp_methods@ */
  0,					/* @tp_members@ */
  pgjump_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@ */
  pgjump_pynew,				/* @tp_new@ */
  0,					/* @tp_free@ */
  0					/* @tp_is_gc@ */
};

static PyObject *pgtest_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
{
  pgtest_pyobj *rc = 0;
  static const char *const kwlist[] = { 0 };

  if (!PyArg_ParseTupleAndKeywords(arg, kw, ":new", KWLIST)) goto end;
  rc = (pgtest_pyobj *)ty->tp_alloc(ty, 0);
  rc->pg.proc = pgen_test;
  rc->pg.ctx = &rc->r;
end:
  return ((PyObject *)rc);
}

static PyTypeObject pgtest_pytype_skel = {
  PyObject_HEAD_INIT(0) 0,		/* Header */
  "PrimeGenTester",			/* @tp_name@ */
  sizeof(pgtest_pyobj),			/* @tp_basicsize@ */
  0,					/* @tp_itemsize@ */

  0,					/* @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@ */
"PrimeGenTester(): Rabin-Miller tester.",

  0,					/* @tp_traverse@ */
  0,					/* @tp_clear@ */
  0,					/* @tp_richcompare@ */
  0,					/* @tp_weaklistoffset@ */
  0,					/* @tp_iter@ */
  0,					/* @tp_iternext@ */
  0,					/* @tp_methods@ */
  0,					/* @tp_members@ */
  0,					/* @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@ */
  pgtest_pynew,				/* @tp_new@ */
  0,					/* @tp_free@ */
  0					/* @tp_is_gc@ */
};

/*----- Prime generation functions ----------------------------------------*/

void pgenerr(struct excinfo *exc)
{
  if (exc->ty) RESTORE_EXCINFO(exc);
  else PyErr_SetString(PyExc_ValueError, "prime generation failed");
}

static PyObject *meth_pgen(PyObject *me, PyObject *arg, PyObject *kw)
{
  mp *x = 0;
  mp *r = 0;
  PyObject *rc = 0;
  char *p = "p";
  pgen_filterctx fc = { 2 };
  rabin tc;
  struct excinfo exc = EXCINFO_INIT;
  pypgev step = { { 0 } }, test = { { 0 } }, evt = { { 0 } };
  unsigned nsteps = 0, ntests = 0;
  static const char *const kwlist[] =
    { "start", "name", "stepper", "tester", "event", "nsteps", "ntests", 0 };

  step.exc = &exc; step.ev.proc = pgen_filter; step.ev.ctx = &fc;
  test.exc = &exc; test.ev.proc = pgen_test; test.ev.ctx = &tc;
  evt.exc = &exc;
  if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&O&O&:pgen", KWLIST,
				   convmp, &x, &p, convpgev, &step,
				   convpgev, &test, convpgev, &evt,
				   convuint, &nsteps, convuint, &ntests))
    goto end;
  if (!ntests) ntests = rabin_iters(mp_bits(x));
  if ((r = pgen(p, MP_NEW, x, evt.ev.proc, evt.ev.ctx,
		nsteps, step.ev.proc, step.ev.ctx,
		ntests, test.ev.proc, test.ev.ctx)) == 0)
    PGENERR(&exc);
  rc = mp_pywrap(r); r = 0;
end:
  mp_drop(r); mp_drop(x);
  droppgev(&step); droppgev(&test); droppgev(&evt);
  return (rc);
}

static PyObject *meth_strongprime_setup(PyObject *me,
					PyObject *arg, PyObject *kw)
{
  mp *x = 0;
  pfilt f;
  grand *r = &rand_global;
  unsigned nbits;
  char *name = "p";
  unsigned n = 0;
  struct excinfo exc = EXCINFO_INIT;
  pypgev evt = { { 0 } };
  PyObject *rc = 0;
  static const char *const kwlist[] =
    { "nbits", "name", "event", "rng", "nsteps", 0 };

  evt.exc = &exc;
  if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&", KWLIST,
				   convuint, &nbits, &name,
				   convpgev, &evt, convgrand, &r,
				   convuint, &n))
    goto end;
  if ((x = strongprime_setup(name, MP_NEW, &f, nbits,
			     r, n, evt.ev.proc, evt.ev.ctx)) == 0)
    PGENERR(&exc);
  rc = Py_BuildValue("(NN)", mp_pywrap(x), pfilt_pywrap(&f));
  x = 0;
end:
  mp_drop(x);
  droppgev(&evt);
  return (rc);
}

static PyObject *meth_strongprime(PyObject *me, PyObject *arg, PyObject *kw)
{
  mp *x = 0;
  grand *r = &rand_global;
  unsigned nbits;
  char *name = "p";
  unsigned n = 0;
  struct excinfo exc = EXCINFO_INIT;
  pypgev evt = { { 0 } };
  PyObject *rc = 0;
  static const char *const kwlist[] =
    { "nbits", "name", "event", "rng", "nsteps", 0 };

  evt.exc = &exc;
  if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&", KWLIST,
				   convuint, &nbits, &name,
				   convpgev, &evt, convgrand, &r,
				   convuint, &n))
    goto end;
  if ((x = strongprime(name, MP_NEW, nbits,
		       r, n, evt.ev.proc, evt.ev.ctx)) == 0)
    PGENERR(&exc);
  rc = mp_pywrap(x);
  x = 0;
end:
  mp_drop(x);
  droppgev(&evt);
  return (rc);
}

static PyObject *meth_limlee(PyObject *me, PyObject *arg, PyObject *kw)
{
  char *p = "p";
  struct excinfo exc = EXCINFO_INIT;
  pypgev ie = { { 0 } }, oe = { { 0 } };
  unsigned ql, pl;
  grand *r = &rand_global;
  unsigned on = 0;
  size_t i, nf = 0;
  PyObject *rc = 0, *vec;
  static const char *const kwlist[] =
    { "pbits", "qbits", "name", "event", "ievent", "rng", "nsteps", 0 };
  mp *x = 0, **v = 0;

  ie.exc = oe.exc = &exc;
  if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&|sO&O&O&O&:limlee", KWLIST,
				   convuint, &pl, convuint, &ql,
				   &p, convpgev, &oe, convpgev, &ie,
				   convgrand, &r, convuint, &on))
    goto end;
  if ((x = limlee(p, MP_NEW, MP_NEW, ql, pl, r, on,
		  oe.ev.proc, oe.ev.ctx, ie.ev.proc, ie.ev.ctx,
		  &nf, &v)) == 0)
    PGENERR(&exc);;
  vec = PyList_New(nf);
  for (i = 0; i < nf; i++)
    PyList_SetItem(vec, i, mp_pywrap(v[i]));
  xfree(v);
  rc = Py_BuildValue("(NN)", mp_pywrap(x), vec);
end:
  droppgev(&oe); droppgev(&ie);
  return (rc);
}

/*----- Global stuff ------------------------------------------------------*/

static PyMethodDef methods[] = {
#define METHNAME(name) meth_##name
  METH	(_PrimeFilter_smallfactor,	"smallfactor(X) -> PGRC")
  METH	(_RabinMiller_iters,		"iters(NBITS) -> NITERS")
  KWMETH(pgen,				"\
pgen(START, [name = 'p'[, [stepper = PrimeGenStepper(2)],\n\
     [tester = PrimeGenTester()], [event = pgen_nullev],\n\
     [nsteps = 0], [ntests = RabinMiller.iters(START.nbits)]) -> P")
  KWMETH(strongprime_setup,		"\
strongprime_setup(NBITS, [name = 'p'], [event = pgen_nullev],\n\
		  [rng = rand], [nsteps = 0]) -> (START, JUMP)")
  KWMETH(strongprime,			"\
strongprime(NBITS, [name = 'p'], [event = pgen_nullev],\n\
	    [rng = rand], [nsteps = 0]) -> P")
  KWMETH(limlee,			"\
limlee(PBITS, QBITS, [name = 'p'], [event = pgen_nullev],\n\
       [ievent = pgen_nullev], [rng = rand], [nsteps = 0]) -> (P, [Q, ...])")
#undef METHNAME
  { 0 }
};

void pgen_pyinit(void)
{
  INITTYPE(pfilt, root);
  INITTYPE(rabin, root);
  INITTYPE(pgevent, root);
  INITTYPE(pgev, root);
  INITTYPE(pgstep, pgev);
  INITTYPE(pgjump, pgev);
  INITTYPE(pgtest, pgev);
  addmethods(methods);
}

static PyObject *obj;

void pgen_pyinsert(PyObject *mod)
{
  INSERT("PrimeFilter", pfilt_pytype);
  INSERT("RabinMiller", rabin_pytype);
  INSERT("PrimeGenEvent", pgevent_pytype);
  INSERT("PrimeGenBuiltinHandler", pgev_pytype);
  INSERT("PrimeGenStepper", pgstep_pytype);
  INSERT("PrimeGenJumper", pgjump_pytype);
  INSERT("PrimeGenTester", pgtest_pytype);
  INSERT("pgen_nullev", obj = pgev_stdev(0));
  INSERT("pgen_stdev", pgev_stdev(pgen_ev));
  INSERT("pgen_spinev", pgev_stdev(pgen_evspin));
  INSERT("pgen_subev", pgev_stdev(pgen_subev));
}

/*----- That's all, folks -------------------------------------------------*/