chiark - git - mdw - catacomb-python/blob - pgen.c

   1 /* -*-c-*-
   2  *
   3  * Prime number generation
   4  *
   5  * (c) 2005 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of the Python interface to Catacomb.
  11  *
  12  * Catacomb/Python is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU General Public License as published by
  14  * the Free Software Foundation; either version 2 of the License, or
  15  * (at your option) any later version.
  16  *
  17  * Catacomb/Python is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with Catacomb/Python; if not, write to the Free Software Foundation,
  24  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  25  */
  26
  27 /*----- Header files ------------------------------------------------------*/
  28
  29 #include "catacomb-python.h"
  30
  31 /*----- Filters -----------------------------------------------------------*/
  32
  33 PyTypeObject *pfilt_pytype;
  34
  35 static PyObject *pfilt_pywrap(pfilt *f)
  36 {
  37   pfilt_pyobj *o = 0;
  38   o = PyObject_New(pfilt_pyobj, pfilt_pytype);
  39   o->f = *f;
  40   o->st = pfilt_step(f, 0);
  41   return ((PyObject *)o);
  42 }
  43
  44 static PyObject *pfilt_pymake(PyTypeObject *ty, PyObject *xobj)
  45 {
  46   mp *x = 0;
  47   pfilt_pyobj *o = 0;
  48
  49   if (PFILT_PYCHECK(xobj)) RETURN_OBJ(xobj);
  50   if ((x = getmp(xobj)) == 0) goto end;
  51   o = (pfilt_pyobj *)ty->tp_alloc(ty, 0);
  52   o->st = pfilt_create(&o->f, x);
  53 end:
  54   mp_drop(x);
  55   return ((PyObject *)o);
  56 }
  57
  58 static PyObject *pfilt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
  59 {
  60   char *kwlist[] = { "x", 0 };
  61   PyObject *xobj;
  62
  63   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &xobj))
  64     return (0);
  65   return (pfilt_pymake(ty, xobj));
  66 }
  67
  68 static void pfilt_pydealloc(PyObject *me)
  69   { pfilt_destroy(PFILT_F(me)); FREEOBJ(me); }
  70
  71 static PyObject *pfmeth_step(PyObject *me, PyObject *arg)
  72 {
  73   mpw x;
  74
  75   if (!PyArg_ParseTuple(arg, "O&:step", convmpw, &x)) return (0);
  76   PFILT_ST(me) = pfilt_step(PFILT_F(me), x);
  77   RETURN_ME;
  78 }
  79
  80 static PyObject *pfmeth_muladd(PyObject *me, PyObject *arg)
  81 {
  82   mpw m, a;
  83   pfilt_pyobj *o = 0;
  84
  85   if (!PyArg_ParseTuple(arg, "O&O&:muladd", convmpw, &m, convmpw, &a))
  86     return (0);
  87   o = PyObject_New(pfilt_pyobj, pfilt_pytype);
  88   o->st = pfilt_muladd(&o->f, PFILT_F(me), m, a);
  89   return ((PyObject *)o);
  90 }
  91
  92 static CONVFUNC(pfilt, pfilt *, PFILT_F)
  93
  94 static PyObject *pfmeth_jump(PyObject *me, PyObject *arg)
  95 {
  96   pfilt *f;
  97
  98   if (!PyArg_ParseTuple(arg, "O&:jump", convpfilt, &f)) return (0);
  99   PFILT_ST(me) = pfilt_jump(PFILT_F(me), f);
 100   RETURN_ME;
 101 }
 102
 103 static PyObject *meth__PrimeFilter_smallfactor(PyObject *me, PyObject *arg)
 104 {
 105   mp *x = 0;
 106   PyObject *rc = 0;
 107
 108   if (!PyArg_ParseTuple(arg, "OO&:smallfactor", &me, convmp, &x)) goto end;
 109   rc = PyInt_FromLong(pfilt_smallfactor(x));
 110 end:
 111   mp_drop(x);
 112   return (rc);
 113 }
 114
 115 static int pfilt_pynonzerop(PyObject *me)
 116   { return (PFILT_ST(me) != PGEN_FAIL); }
 117
 118 static PyObject *pfilt_pyint(PyObject *me)
 119 {
 120   long l;
 121   PyObject *rc = 0;
 122
 123   if (!mp_tolong_checked(PFILT_F(me)->m, &l, 0)) rc = PyInt_FromLong(l);
 124   else rc = mp_topylong(PFILT_F(me)->m);
 125   return (rc);
 126 }
 127
 128 static PyObject *pfilt_pylong(PyObject *me)
 129   { return (mp_topylong(PFILT_F(me)->m)); }
 130
 131 static PyObject *pfget_x(PyObject *me, void *hunoz)
 132   { return (mp_pywrap(MP_COPY(PFILT_F(me)->m))); }
 133
 134 static PyObject *pfget_status(PyObject *me, void *hunoz)
 135   { return (PyInt_FromLong(PFILT_ST(me))); }
 136
 137 static PyGetSetDef pfilt_pygetset[] = {
 138 #define GETSETNAME(op, name) pf##op##_##name
 139   GET   (x,             "F.x -> current position of filter")
 140   GET   (status,        "F.status -> primality status of filter")
 141 #undef GETSETNAME
 142   { 0 }
 143 };
 144
 145 static PyMethodDef pfilt_pymethods[] = {
 146 #define METHNAME(name) pfmeth_##name
 147   METH  (step,          "F.step(N)")
 148   METH  (muladd,        "F.muladd(M, A)")
 149   METH  (jump,          "F.jump(FF)")
 150 #undef METHNAME
 151   { 0 }
 152 };
 153
 154 static PyNumberMethods pfilt_pynumber = {
 155   0,                                    /* @nb_add@ */
 156   0,                                    /* @nb_subtract@ */
 157   0,                                    /* @nb_multiply@ */
 158   0,                                    /* @nb_divide@ */
 159   0,                                    /* @nb_remainder@ */
 160   0,                                    /* @nb_divmod@ */
 161   0,                                    /* @nb_power@ */
 162   0,                                    /* @nb_negative@ */
 163   0,                                    /* @nb_positive@ */
 164   0,                                    /* @nb_absolute@ */
 165   pfilt_pynonzerop,                     /* @nb_nonzero@ */
 166   0,                                    /* @nb_invert@ */
 167   0,                                    /* @nb_lshift@ */
 168   0,                                    /* @nb_rshift@ */
 169   0,                                    /* @nb_and@ */
 170   0,                                    /* @nb_xor@ */
 171   0,                                    /* @nb_or@ */
 172   0,                                    /* @nb_coerce@ */
 173   pfilt_pyint,                          /* @nb_int@ */
 174   pfilt_pylong,                         /* @nb_long@ */
 175   0,                                    /* @nb_float@ */
 176   0,                                    /* @nb_oct@ */
 177   0,                                    /* @nb_hex@ */
 178
 179   0,                                    /* @nb_inplace_add@ */
 180   0,                                    /* @nb_inplace_subtract@ */
 181   0,                                    /* @nb_inplace_multiply@ */
 182   0,                                    /* @nb_inplace_divide@ */
 183   0,                                    /* @nb_inplace_remainder@ */
 184   0,                                    /* @nb_inplace_power@ */
 185   0,                                    /* @nb_inplace_lshift@ */
 186   0,                                    /* @nb_inplace_rshift@ */
 187   0,                                    /* @nb_inplace_and@ */
 188   0,                                    /* @nb_inplace_xor@ */
 189   0,                                    /* @nb_inplace_or@ */
 190
 191   0,                                    /* @nb_floor_divide@ */
 192   0,                                    /* @nb_true_divide@ */
 193   0,                                    /* @nb_inplace_floor_divide@ */
 194   0,                                    /* @nb_inplace_true_divide@ */
 195 };
 196
 197 static PyTypeObject pfilt_pytype_skel = {
 198   PyObject_HEAD_INIT(0) 0,              /* Header */
 199   "PrimeFilter",                        /* @tp_name@ */
 200   sizeof(pfilt_pyobj),                  /* @tp_basicsize@ */
 201   0,                                    /* @tp_itemsize@ */
 202
 203   pfilt_pydealloc,                      /* @tp_dealloc@ */
 204   0,                                    /* @tp_print@ */
 205   0,                                    /* @tp_getattr@ */
 206   0,                                    /* @tp_setattr@ */
 207   0,                                    /* @tp_compare@ */
 208   0,                                    /* @tp_repr@ */
 209   &pfilt_pynumber,                      /* @tp_as_number@ */
 210   0,                                    /* @tp_as_sequence@ */
 211   0,                                    /* @tp_as_mapping@ */
 212   0,                                    /* @tp_hash@ */
 213   0,                                    /* @tp_call@ */
 214   0,                                    /* @tp_str@ */
 215   0,                                    /* @tp_getattro@ */
 216   0,                                    /* @tp_setattro@ */
 217   0,                                    /* @tp_as_buffer@ */
 218   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 219     Py_TPFLAGS_BASETYPE,
 220
 221   /* @tp_doc@ */
 222 "Small-primes filter.",
 223
 224   0,                                    /* @tp_traverse@ */
 225   0,                                    /* @tp_clear@ */
 226   0,                                    /* @tp_richcompare@ */
 227   0,                                    /* @tp_weaklistoffset@ */
 228   0,                                    /* @tp_iter@ */
 229   0,                                    /* @tp_iternext@ */
 230   pfilt_pymethods,                      /* @tp_methods@ */
 231   0,                                    /* @tp_members@ */
 232   pfilt_pygetset,                       /* @tp_getset@ */
 233   0,                                    /* @tp_base@ */
 234   0,                                    /* @tp_dict@ */
 235   0,                                    /* @tp_descr_get@ */
 236   0,                                    /* @tp_descr_set@ */
 237   0,                                    /* @tp_dictoffset@ */
 238   0,                                    /* @tp_init@ */
 239   PyType_GenericAlloc,                  /* @tp_alloc@ */
 240   pfilt_pynew,                          /* @tp_new@ */
 241   0,                                    /* @tp_free@ */
 242   0                                     /* @tp_is_gc@ */
 243 };
 244
 245 /*----- Rabin-Miller testing ----------------------------------------------*/
 246
 247 typedef struct rabin_pyobj {
 248   PyObject_HEAD
 249   rabin r;
 250 } rabin_pyobj;
 251
 252 static PyTypeObject *rabin_pytype;
 253 #define RABIN_R(o) (&((rabin_pyobj *)(o))->r)
 254
 255 static PyObject *rabin_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
 256 {
 257   mp *x = 0;
 258   rabin_pyobj *o = 0;
 259   char *kwlist[] = { "x", 0 };
 260
 261   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &x))
 262     goto end;
 263   if (!MP_POSP(x) || MP_EVENP(x)) VALERR("must be positive and odd");
 264   o = (rabin_pyobj *)ty->tp_alloc(ty, 0);
 265   rabin_create(&o->r, x);
 266 end:
 267   return ((PyObject *)o);
 268 }
 269
 270 static void rabin_pydealloc(PyObject *me)
 271 {
 272   rabin_destroy(RABIN_R(me));
 273   FREEOBJ(me);
 274 }
 275
 276 static PyObject *rmeth_test(PyObject *me, PyObject *arg)
 277 {
 278   mp *w = 0;
 279   PyObject *rc = 0;
 280
 281   if (!PyArg_ParseTuple(arg, "O&:test", convmp, &w)) goto end;
 282   rc = PyInt_FromLong(rabin_test(RABIN_R(me), w));
 283 end:
 284   mp_drop(w);
 285   return (rc);
 286 }
 287
 288 static PyObject *rmeth_rtest(PyObject *me, PyObject *arg)
 289 {
 290   mp *w = 0;
 291   PyObject *rc = 0;
 292
 293   if (!PyArg_ParseTuple(arg, "O&:rtest", convmp, &w)) goto end;
 294   rc = PyInt_FromLong(rabin_rtest(RABIN_R(me), w));
 295 end:
 296   mp_drop(w);
 297   return (rc);
 298 }
 299
 300 static PyObject *rget_niters(PyObject *me, void *hunoz)
 301   { return (PyInt_FromLong(rabin_iters(mp_bits(RABIN_R(me)->mm.m)))); }
 302
 303 static PyObject *rget_x(PyObject *me, void *hunoz)
 304   { return (mp_pywrap(MP_COPY(RABIN_R(me)->mm.m))); }
 305
 306 static PyObject *meth__RabinMiller_iters(PyObject *me, PyObject *arg)
 307 {
 308   unsigned n;
 309
 310   if (!PyArg_ParseTuple(arg, "OO&:iters", &me, convuint, &n)) return (0);
 311   return (PyInt_FromLong(rabin_iters(n)));
 312 }
 313
 314 static PyGetSetDef rabin_pygetset[] = {
 315 #define GETSETNAME(op, name) r##op##_##name
 316   GET   (x,             "R.x -> number under test")
 317   GET   (niters,        "R.niters -> suggested number of tests")
 318 #undef GETSETNAME
 319   { 0 }
 320 };
 321
 322 static PyMethodDef rabin_pymethods[] = {
 323 #define METHNAME(name) rmeth_##name
 324   METH  (test,          "R.test(W) -> PGST")
 325   METH  (rtest,         "R.rtest(W) -> PGST")
 326 #undef METHNAME
 327   { 0 }
 328 };
 329
 330 static PyTypeObject rabin_pytype_skel = {
 331   PyObject_HEAD_INIT(0) 0,              /* Header */
 332   "RabinMiller",                        /* @tp_name@ */
 333   sizeof(rabin_pyobj),                  /* @tp_basicsize@ */
 334   0,                                    /* @tp_itemsize@ */
 335
 336   rabin_pydealloc,                      /* @tp_dealloc@ */
 337   0,                                    /* @tp_print@ */
 338   0,                                    /* @tp_getattr@ */
 339   0,                                    /* @tp_setattr@ */
 340   0,                                    /* @tp_compare@ */
 341   0,                                    /* @tp_repr@ */
 342   0,                                    /* @tp_as_number@ */
 343   0,                                    /* @tp_as_sequence@ */
 344   0,                                    /* @tp_as_mapping@ */
 345   0,                                    /* @tp_hash@ */
 346   0,                                    /* @tp_call@ */
 347   0,                                    /* @tp_str@ */
 348   0,                                    /* @tp_getattro@ */
 349   0,                                    /* @tp_setattro@ */
 350   0,                                    /* @tp_as_buffer@ */
 351   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 352     Py_TPFLAGS_BASETYPE,
 353
 354   /* @tp_doc@ */
 355 "Rabin-Miller strong primality test.",
 356
 357   0,                                    /* @tp_traverse@ */
 358   0,                                    /* @tp_clear@ */
 359   0,                                    /* @tp_richcompare@ */
 360   0,                                    /* @tp_weaklistoffset@ */
 361   0,                                    /* @tp_iter@ */
 362   0,                                    /* @tp_iternext@ */
 363   rabin_pymethods,                      /* @tp_methods@ */
 364   0,                                    /* @tp_members@ */
 365   rabin_pygetset,                       /* @tp_getset@ */
 366   0,                                    /* @tp_base@ */
 367   0,                                    /* @tp_dict@ */
 368   0,                                    /* @tp_descr_get@ */
 369   0,                                    /* @tp_descr_set@ */
 370   0,                                    /* @tp_dictoffset@ */
 371   0,                                    /* @tp_init@ */
 372   PyType_GenericAlloc,                  /* @tp_alloc@ */
 373   rabin_pynew,                          /* @tp_new@ */
 374   0,                                    /* @tp_free@ */
 375   0                                     /* @tp_is_gc@ */
 376 };
 377
 378 /*----- Events ------------------------------------------------------------*/
 379
 380 typedef struct pgevent_pyobj {
 381   PyObject_HEAD
 382   pgen_event *ev;
 383 } pgevent_pyobj;
 384
 385 static PyTypeObject *pgevent_pytype;
 386 #define PGEVENT_EV(o) (((pgevent_pyobj *)(o))->ev)
 387
 388 static PyObject *pgevent_pywrap(pgen_event *ev)
 389 {
 390   pgevent_pyobj *o = PyObject_New(pgevent_pyobj, pgevent_pytype);
 391   o->ev = ev;
 392   return ((PyObject *)o);
 393 }
 394
 395 static CONVFUNC(pgevent, pgen_event *, PGEVENT_EV)
 396
 397 static void pgevent_kill(PyObject *me) { PGEVENT_EV(me) = 0; }
 398 static void pgevent_pydealloc(PyObject *me) { FREEOBJ(me); }
 399
 400 #define PGEVENT_CHECK(me) do {                                          \
 401   if (!PGEVENT_EV(me)) {                                                \
 402     PyErr_SetString(PyExc_ValueError, "event object is dead");          \
 403     return (0);                                                         \
 404   }                                                                     \
 405 } while (0)
 406
 407 static PyObject *peget_name(PyObject *me, void *hunoz)
 408   { PGEVENT_CHECK(me); return (PyString_FromString(PGEVENT_EV(me)->name)); }
 409
 410 static PyObject *peget_x(PyObject *me, void *hunoz)
 411   { PGEVENT_CHECK(me); return (mp_pywrap(MP_COPY(PGEVENT_EV(me)->m))); }
 412
 413 static PyObject *peget_steps(PyObject *me, void *hunoz)
 414   { PGEVENT_CHECK(me); return (PyInt_FromLong(PGEVENT_EV(me)->steps)); }
 415
 416 static PyObject *peget_tests(PyObject *me, void *hunoz)
 417   { PGEVENT_CHECK(me); return (PyInt_FromLong(PGEVENT_EV(me)->tests)); }
 418
 419 static PyObject *peget_rng(PyObject *me, void *hunoz)
 420   { PGEVENT_CHECK(me); return (grand_pywrap(PGEVENT_EV(me)->r, 0)); }
 421
 422 static int peset_x(PyObject *me, PyObject *xobj, void *hunoz)
 423 {
 424   mp *x = 0;
 425   pgen_event *ev = PGEVENT_EV(me);
 426   int rc = -1;
 427   if (!x) NIERR("__del__");
 428   PGEVENT_CHECK(me);
 429   if ((x = getmp(xobj)) == 0) goto end;
 430   mp_drop(ev->m);
 431   ev->m = MP_COPY(x);
 432   rc = 0;
 433 end:
 434   mp_drop(x);
 435   return (rc);
 436 }
 437
 438 static PyGetSetDef pgevent_pygetset[] = {
 439 #define GETSETNAME(op, name) pe##op##_##name
 440   GET   (name,          "EV.name -> value being generated")
 441   GETSET(x,             "EV.x -> value under test")
 442   GET   (steps,         "EV.steps -> number of steps left")
 443   GET   (tests,         "EV.tests -> tests before passing")
 444   GET   (rng,           "EV.rng -> (noncrypto) random number generator")
 445 #undef GETSETNAME
 446   { 0 }
 447 };
 448
 449 static PyTypeObject pgevent_pytype_skel = {
 450   PyObject_HEAD_INIT(0) 0,              /* Header */
 451   "PrimeGenEvent",                      /* @tp_name@ */
 452   sizeof(pgevent_pyobj),                /* @tp_basicsize@ */
 453   0,                                    /* @tp_itemsize@ */
 454
 455   pgevent_pydealloc,                    /* @tp_dealloc@ */
 456   0,                                    /* @tp_print@ */
 457   0,                                    /* @tp_getattr@ */
 458   0,                                    /* @tp_setattr@ */
 459   0,                                    /* @tp_compare@ */
 460   0,                                    /* @tp_repr@ */
 461   0,                                    /* @tp_as_number@ */
 462   0,                                    /* @tp_as_sequence@ */
 463   0,                                    /* @tp_as_mapping@ */
 464   0,                                    /* @tp_hash@ */
 465   0,                                    /* @tp_call@ */
 466   0,                                    /* @tp_str@ */
 467   0,                                    /* @tp_getattro@ */
 468   0,                                    /* @tp_setattro@ */
 469   0,                                    /* @tp_as_buffer@ */
 470   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 471     Py_TPFLAGS_BASETYPE,
 472
 473   /* @tp_doc@ */
 474 "Prime-generation event.",
 475
 476   0,                                    /* @tp_traverse@ */
 477   0,                                    /* @tp_clear@ */
 478   0,                                    /* @tp_richcompare@ */
 479   0,                                    /* @tp_weaklistoffset@ */
 480   0,                                    /* @tp_iter@ */
 481   0,                                    /* @tp_iternext@ */
 482   0,                                    /* @tp_methods@ */
 483   0,                                    /* @tp_members@ */
 484   pgevent_pygetset,                     /* @tp_getset@ */
 485   0,                                    /* @tp_base@ */
 486   0,                                    /* @tp_dict@ */
 487   0,                                    /* @tp_descr_get@ */
 488   0,                                    /* @tp_descr_set@ */
 489   0,                                    /* @tp_dictoffset@ */
 490   0,                                    /* @tp_init@ */
 491   PyType_GenericAlloc,                  /* @tp_alloc@ */
 492   abstract_pynew,                       /* @tp_new@ */
 493   0,                                    /* @tp_free@ */
 494   0                                     /* @tp_is_gc@ */
 495 };
 496
 497 /*----- Event handlers ----------------------------------------------------*/
 498
 499 PyTypeObject *pgev_pytype;
 500
 501 typedef struct pgstep_pyobj {
 502   PGEV_HEAD
 503   pgen_filterctx f;
 504 } pgstep_pyobj;
 505
 506 static PyTypeObject *pgstep_pytype;
 507 #define PGSTEP_STEP(o) (((pgstep_pyobj *)(o))->f.step)
 508
 509 typedef struct pgjump_pyobj {
 510   PGEV_HEAD
 511   PyObject *fobj;
 512   pgen_jumpctx j;
 513 } pgjump_pyobj;
 514
 515 static PyTypeObject *pgjump_pytype;
 516 #define PGJUMP_FOBJ(o) (((pgjump_pyobj *)(o))->fobj)
 517 #define PGJUMP_J(o) (&((pgjump_pyobj *)(o))->j)
 518
 519 typedef struct pgtest_pyobj {
 520   PGEV_HEAD
 521   rabin r;
 522 } pgtest_pyobj;
 523
 524 static PyTypeObject *pgtest_pytype;
 525
 526 static int pgev_python(int rq, pgen_event *ev, void *p)
 527 {
 528   PyObject *py = p;
 529   PyObject *pyev = 0;
 530   PyObject *rc = 0;
 531   int st = PGEN_ABORT;
 532   long l;
 533   char *meth[] = {
 534     "pg_abort", "pg_done", "pg_begin", "pg_try", "pg_fail", "pg_pass"
 535   };
 536
 537   Py_INCREF(py);
 538   rq++;
 539   if (rq > N(meth)) SYSERR("event code out of range");
 540   pyev = pgevent_pywrap(ev);
 541   if ((rc = PyObject_CallMethod(py, meth[rq], "(O)", pyev)) == 0)
 542     goto end;
 543   if (rc == Py_None)
 544     st = PGEN_TRY;
 545   else if ((l = PyInt_AsLong(rc)) == -1 && PyErr_Occurred())
 546     goto end;
 547   else if (l < PGEN_ABORT || l > PGEN_PASS)
 548     VALERR("return code out of range");
 549   else
 550     st = l;
 551 end:
 552   if (pyev) {
 553     pgevent_kill(pyev);
 554     Py_DECREF(pyev);
 555   }
 556   Py_XDECREF(rc);
 557   Py_DECREF(py);
 558   return (st);
 559 }
 560
 561 static PyObject *pgev_pywrap(const pgev *pg)
 562 {
 563   pgev_pyobj *o;
 564
 565   o = PyObject_New(pgev_pyobj, pgev_pytype);
 566   o->pg = *pg;
 567   return ((PyObject *)o);
 568 }
 569
 570 int convpgev(PyObject *o, void *p)
 571 {
 572   pgev *pg = p;
 573
 574   if (PGEV_PYCHECK(o))
 575     *pg = *PGEV_PG(o);
 576   else {
 577     pg->proc = pgev_python;
 578     pg->ctx = o;
 579     Py_INCREF(o);
 580   }
 581   return (1);
 582 }
 583
 584 void droppgev(pgev *p)
 585 {
 586   if (p->proc == pgev_python) {
 587     PyObject *py = p->ctx;
 588     Py_DECREF(py);
 589   }
 590 }
 591
 592 static PyObject *pgmeth_common(PyObject *me, PyObject *arg, int rq)
 593 {
 594   pgen_event *ev;
 595   pgev *pg = PGEV_PG(me);
 596   PyObject *rc = 0;
 597
 598   if (!PyArg_ParseTuple(arg, "O&", convpgevent, &ev)) goto end;
 599   rc = PyInt_FromLong(!pg->proc ? rq : pg->proc(rq, ev, pg->ctx));
 600 end:
 601   return (rc);
 602 }
 603
 604 #define PGMETH(lc, uc)                                                  \
 605   static PyObject *pgmeth_pg_##lc(PyObject *me, PyObject *arg)          \
 606     { return pgmeth_common(me, arg, PGEN_##uc); }
 607 PGMETH(abort,   ABORT)
 608 PGMETH(done,    DONE)
 609 PGMETH(begin,   BEGIN)
 610 PGMETH(try,     TRY)
 611 PGMETH(pass,    PASS)
 612 PGMETH(fail,    FAIL)
 613 #undef PGMETH
 614
 615 static PyObject *pgev_stdev(pgen_proc *proc)
 616   { pgev pg; pg.proc = proc; pg.ctx = 0; return (pgev_pywrap(&pg)); }
 617
 618 static PyMethodDef pgev_pymethods[] = {
 619 #define METHNAME(name) pgmeth_##name
 620   METH  (pg_abort,      "E.pg_abort(EV) -> PGRC -- prime generation aborted")
 621   METH  (pg_done,       "E.pg_done(EV) -> PGRC -- prime generation finished")
 622   METH  (pg_begin,     "E.pg_begin(EV) -> PGRC -- commence stepping/testing")
 623   METH  (pg_try,        "E.pg_try(EV) -> PGRC -- found new candidate")
 624   METH  (pg_pass,       "E.pg_pass(EV) -> PGRC -- passed primality test")
 625   METH  (pg_fail,       "E.pg_fail(EV) -> PGRC -- failed primality test")
 626 #undef METHNAME
 627   { 0 }
 628 };
 629
 630 static PyTypeObject pgev_pytype_skel = {
 631   PyObject_HEAD_INIT(0) 0,              /* Header */
 632   "PrimeGenBuiltinHandler",             /* @tp_name@ */
 633   sizeof(pgev_pyobj),                   /* @tp_basicsize@ */
 634   0,                                    /* @tp_itemsize@ */
 635
 636   0,                                    /* @tp_dealloc@ */
 637   0,                                    /* @tp_print@ */
 638   0,                                    /* @tp_getattr@ */
 639   0,                                    /* @tp_setattr@ */
 640   0,                                    /* @tp_compare@ */
 641   0,                                    /* @tp_repr@ */
 642   0,                                    /* @tp_as_number@ */
 643   0,                                    /* @tp_as_sequence@ */
 644   0,                                    /* @tp_as_mapping@ */
 645   0,                                    /* @tp_hash@ */
 646   0,                                    /* @tp_call@ */
 647   0,                                    /* @tp_str@ */
 648   0,                                    /* @tp_getattro@ */
 649   0,                                    /* @tp_setattro@ */
 650   0,                                    /* @tp_as_buffer@ */
 651   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 652     Py_TPFLAGS_BASETYPE,
 653
 654   /* @tp_doc@ */
 655 "Built-in prime-generation event handler, base class.",
 656
 657   0,                                    /* @tp_traverse@ */
 658   0,                                    /* @tp_clear@ */
 659   0,                                    /* @tp_richcompare@ */
 660   0,                                    /* @tp_weaklistoffset@ */
 661   0,                                    /* @tp_iter@ */
 662   0,                                    /* @tp_iternext@ */
 663   pgev_pymethods,                       /* @tp_methods@ */
 664   0,                                    /* @tp_members@ */
 665   0,                                    /* @tp_getset@ */
 666   0,                                    /* @tp_base@ */
 667   0,                                    /* @tp_dict@ */
 668   0,                                    /* @tp_descr_get@ */
 669   0,                                    /* @tp_descr_set@ */
 670   0,                                    /* @tp_dictoffset@ */
 671   0,                                    /* @tp_init@ */
 672   PyType_GenericAlloc,                  /* @tp_alloc@ */
 673   abstract_pynew,                       /* @tp_new@ */
 674   0,                                    /* @tp_free@ */
 675   0                                     /* @tp_is_gc@ */
 676 };
 677
 678 static PyObject *pgstep_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
 679 {
 680   mpw s;
 681   pgstep_pyobj *rc = 0;
 682   char *kwlist[] = { "step", 0 };
 683
 684   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmpw, &s))
 685     goto end;
 686   rc = (pgstep_pyobj *)ty->tp_alloc(ty, 0);
 687   rc->f.step = s;
 688   rc->pg.proc = pgen_filter;
 689   rc->pg.ctx = &rc->f;
 690 end:
 691   return ((PyObject *)rc);
 692 }
 693
 694 static PyObject *psget_step(PyObject *me, void *hunoz)
 695   { return (PyInt_FromLong(PGSTEP_STEP(me))); }
 696
 697 static PyGetSetDef pgstep_pygetset[] = {
 698 #define GETSETNAME(op, name) ps##op##_##name
 699   GET   (step,          "S.step -> step size for the stepper")
 700 #undef GETSETNAME
 701   { 0 }
 702 };
 703
 704 static PyTypeObject pgstep_pytype_skel = {
 705   PyObject_HEAD_INIT(0) 0,              /* Header */
 706   "PrimeGenStepper",                    /* @tp_name@ */
 707   sizeof(pgstep_pyobj),                 /* @tp_basicsize@ */
 708   0,                                    /* @tp_itemsize@ */
 709
 710   0,                                    /* @tp_dealloc@ */
 711   0,                                    /* @tp_print@ */
 712   0,                                    /* @tp_getattr@ */
 713   0,                                    /* @tp_setattr@ */
 714   0,                                    /* @tp_compare@ */
 715   0,                                    /* @tp_repr@ */
 716   0,                                    /* @tp_as_number@ */
 717   0,                                    /* @tp_as_sequence@ */
 718   0,                                    /* @tp_as_mapping@ */
 719   0,                                    /* @tp_hash@ */
 720   0,                                    /* @tp_call@ */
 721   0,                                    /* @tp_str@ */
 722   0,                                    /* @tp_getattro@ */
 723   0,                                    /* @tp_setattro@ */
 724   0,                                    /* @tp_as_buffer@ */
 725   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 726     Py_TPFLAGS_BASETYPE,
 727
 728   /* @tp_doc@ */
 729   "Simple prime-number stepper with small-factors filter.",
 730
 731   0,                                    /* @tp_traverse@ */
 732   0,                                    /* @tp_clear@ */
 733   0,                                    /* @tp_richcompare@ */
 734   0,                                    /* @tp_weaklistoffset@ */
 735   0,                                    /* @tp_iter@ */
 736   0,                                    /* @tp_iternext@ */
 737   0,                                    /* @tp_methods@ */
 738   0,                                    /* @tp_members@ */
 739   pgstep_pygetset,                      /* @tp_getset@ */
 740   0,                                    /* @tp_base@ */
 741   0,                                    /* @tp_dict@ */
 742   0,                                    /* @tp_descr_get@ */
 743   0,                                    /* @tp_descr_set@ */
 744   0,                                    /* @tp_dictoffset@ */
 745   0,                                    /* @tp_init@ */
 746   PyType_GenericAlloc,                  /* @tp_alloc@ */
 747   pgstep_pynew,                         /* @tp_new@ */
 748   0,                                    /* @tp_free@ */
 749   0                                     /* @tp_is_gc@ */
 750 };
 751
 752 static PyObject *pgjump_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
 753 {
 754   PyObject *o, *fobj;
 755   pgjump_pyobj *rc = 0;
 756   char *kwlist[] = { "jump", 0 };
 757
 758   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &o) ||
 759       (fobj = pfilt_pymake(pfilt_pytype, o)) == 0)
 760     goto end;
 761   rc = (pgjump_pyobj *)ty->tp_alloc(ty, 0);
 762   rc->fobj = fobj;
 763   rc->j.j = PFILT_F(fobj);
 764   rc->pg.proc = pgen_jump;
 765   rc->pg.ctx = &rc->j;
 766 end:
 767   return ((PyObject *)rc);
 768 }
 769
 770 static void pgjump_pydealloc(PyObject *me)
 771 {
 772   Py_DECREF(PGJUMP_FOBJ(me));
 773   FREEOBJ(me);
 774 }
 775
 776 static PyObject *pjget_jump(PyObject *me, void *hunoz)
 777   { RETURN_OBJ(PGJUMP_FOBJ(me)); }
 778
 779 static PyGetSetDef pgjump_pygetset[] = {
 780 #define GETSETNAME(op, name) pj##op##_##name
 781   GET   (jump,          "S.jump -> jump size for the stepper")
 782 #undef GETSETNAME
 783   { 0 }
 784 };
 785
 786 static PyTypeObject pgjump_pytype_skel = {
 787   PyObject_HEAD_INIT(0) 0,              /* Header */
 788   "PrimeGenJumper",                     /* @tp_name@ */
 789   sizeof(pgjump_pyobj),                 /* @tp_basicsize@ */
 790   0,                                    /* @tp_itemsize@ */
 791
 792   pgjump_pydealloc,                     /* @tp_dealloc@ */
 793   0,                                    /* @tp_print@ */
 794   0,                                    /* @tp_getattr@ */
 795   0,                                    /* @tp_setattr@ */
 796   0,                                    /* @tp_compare@ */
 797   0,                                    /* @tp_repr@ */
 798   0,                                    /* @tp_as_number@ */
 799   0,                                    /* @tp_as_sequence@ */
 800   0,                                    /* @tp_as_mapping@ */
 801   0,                                    /* @tp_hash@ */
 802   0,                                    /* @tp_call@ */
 803   0,                                    /* @tp_str@ */
 804   0,                                    /* @tp_getattro@ */
 805   0,                                    /* @tp_setattro@ */
 806   0,                                    /* @tp_as_buffer@ */
 807   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 808     Py_TPFLAGS_BASETYPE,
 809
 810   /* @tp_doc@ */
 811 "Stepper for larger steps, with small-factors filter.",
 812
 813   0,                                    /* @tp_traverse@ */
 814   0,                                    /* @tp_clear@ */
 815   0,                                    /* @tp_richcompare@ */
 816   0,                                    /* @tp_weaklistoffset@ */
 817   0,                                    /* @tp_iter@ */
 818   0,                                    /* @tp_iternext@ */
 819   0,                                    /* @tp_methods@ */
 820   0,                                    /* @tp_members@ */
 821   pgjump_pygetset,                      /* @tp_getset@ */
 822   0,                                    /* @tp_base@ */
 823   0,                                    /* @tp_dict@ */
 824   0,                                    /* @tp_descr_get@ */
 825   0,                                    /* @tp_descr_set@ */
 826   0,                                    /* @tp_dictoffset@ */
 827   0,                                    /* @tp_init@ */
 828   PyType_GenericAlloc,                  /* @tp_alloc@ */
 829   pgjump_pynew,                         /* @tp_new@ */
 830   0,                                    /* @tp_free@ */
 831   0                                     /* @tp_is_gc@ */
 832 };
 833
 834 static PyObject *pgtest_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
 835 {
 836   pgtest_pyobj *rc = 0;
 837   char *kwlist[] = { 0 };
 838
 839   if (!PyArg_ParseTupleAndKeywords(arg, kw, ":new", kwlist)) goto end;
 840   rc = (pgtest_pyobj *)ty->tp_alloc(ty, 0);
 841   rc->pg.proc = pgen_test;
 842   rc->pg.ctx = &rc->r;
 843 end:
 844   return ((PyObject *)rc);
 845 }
 846
 847 static PyTypeObject pgtest_pytype_skel = {
 848   PyObject_HEAD_INIT(0) 0,              /* Header */
 849   "PrimeGenTester",                     /* @tp_name@ */
 850   sizeof(pgtest_pyobj),                 /* @tp_basicsize@ */
 851   0,                                    /* @tp_itemsize@ */
 852
 853   0,                                    /* @tp_dealloc@ */
 854   0,                                    /* @tp_print@ */
 855   0,                                    /* @tp_getattr@ */
 856   0,                                    /* @tp_setattr@ */
 857   0,                                    /* @tp_compare@ */
 858   0,                                    /* @tp_repr@ */
 859   0,                                    /* @tp_as_number@ */
 860   0,                                    /* @tp_as_sequence@ */
 861   0,                                    /* @tp_as_mapping@ */
 862   0,                                    /* @tp_hash@ */
 863   0,                                    /* @tp_call@ */
 864   0,                                    /* @tp_str@ */
 865   0,                                    /* @tp_getattro@ */
 866   0,                                    /* @tp_setattro@ */
 867   0,                                    /* @tp_as_buffer@ */
 868   Py_TPFLAGS_DEFAULT |                  /* @tp_flags@ */
 869     Py_TPFLAGS_BASETYPE,
 870
 871   /* @tp_doc@ */
 872 "Rabin-Miller tester.",
 873
 874   0,                                    /* @tp_traverse@ */
 875   0,                                    /* @tp_clear@ */
 876   0,                                    /* @tp_richcompare@ */
 877   0,                                    /* @tp_weaklistoffset@ */
 878   0,                                    /* @tp_iter@ */
 879   0,                                    /* @tp_iternext@ */
 880   0,                                    /* @tp_methods@ */
 881   0,                                    /* @tp_members@ */
 882   0,                                    /* @tp_getset@ */
 883   0,                                    /* @tp_base@ */
 884   0,                                    /* @tp_dict@ */
 885   0,                                    /* @tp_descr_get@ */
 886   0,                                    /* @tp_descr_set@ */
 887   0,                                    /* @tp_dictoffset@ */
 888   0,                                    /* @tp_init@ */
 889   PyType_GenericAlloc,                  /* @tp_alloc@ */
 890   pgtest_pynew,                         /* @tp_new@ */
 891   0,                                    /* @tp_free@ */
 892   0                                     /* @tp_is_gc@ */
 893 };
 894
 895 /*----- Prime generation functions ----------------------------------------*/
 896
 897 void pgenerr(void)
 898 {
 899   if (!PyErr_Occurred())
 900     PyErr_SetString(PyExc_ValueError, "prime generation failed");
 901 }
 902
 903 static PyObject *meth_pgen(PyObject *me, PyObject *arg, PyObject *kw)
 904 {
 905   mp *x = 0;
 906   mp *r = 0;
 907   PyObject *rc = 0;
 908   char *p = "p";
 909   pgen_filterctx fc = { 2 };
 910   rabin tc;
 911   pgev step = { 0 }, test = { 0 }, evt = { 0 };
 912   unsigned nsteps = 0, ntests = 0;
 913   char *kwlist[] = { "start", "name", "stepper", "tester", "event",
 914                      "nsteps", "ntests", 0 };
 915
 916   step.proc = pgen_filter; step.ctx = &fc;
 917   test.proc = pgen_test; test.ctx = &tc;
 918   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&O&O&:pgen", kwlist,
 919                                    convmp, &x, &p, convpgev, &step,
 920                                    convpgev, &test, convpgev, &evt,
 921                                    convuint, &nsteps, convuint, &ntests))
 922     goto end;
 923   if (!ntests) ntests = rabin_iters(mp_bits(x));
 924   if ((r = pgen(p, MP_NEW, x, evt.proc, evt.ctx,
 925                 nsteps, step.proc, step.ctx,
 926                 ntests, test.proc, test.ctx)) == 0)
 927     PGENERR;
 928   if (PyErr_Occurred()) goto end;
 929   rc = mp_pywrap(r);
 930   r = 0;
 931 end:
 932   mp_drop(r); mp_drop(x);
 933   droppgev(&step); droppgev(&test); droppgev(&evt);
 934   return (rc);
 935 }
 936
 937 static PyObject *meth_strongprime_setup(PyObject *me,
 938                                         PyObject *arg, PyObject *kw)
 939 {
 940   mp *x = 0;
 941   pfilt f;
 942   grand *r = &rand_global;
 943   unsigned nbits;
 944   char *name = "p";
 945   unsigned n = 0;
 946   pgev evt = { 0 };
 947   PyObject *rc = 0;
 948   char *kwlist[] = { "nbits", "name", "event", "rng", "nsteps", 0 };
 949
 950   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&", kwlist,
 951                                    convuint, &nbits, &name,
 952                                    convpgev, &evt, convgrand, &r,
 953                                    convuint, &n))
 954     goto end;
 955   if ((x = strongprime_setup(name, MP_NEW, &f, nbits,
 956                              r, n, evt.proc, evt.ctx)) == 0)
 957     PGENERR;
 958   rc = Py_BuildValue("(NN)", mp_pywrap(x), pfilt_pywrap(&f));
 959   x = 0;
 960 end:
 961   mp_drop(x);
 962   droppgev(&evt);
 963   return (rc);
 964 }
 965
 966 static PyObject *meth_strongprime(PyObject *me, PyObject *arg, PyObject *kw)
 967 {
 968   mp *x = 0;
 969   grand *r = &rand_global;
 970   unsigned nbits;
 971   char *name = "p";
 972   unsigned n = 0;
 973   pgev evt = { 0 };
 974   PyObject *rc = 0;
 975   char *kwlist[] = { "nbits", "name", "event", "rng", "nsteps", 0 };
 976
 977   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&", kwlist,
 978                                    convuint, &nbits, &name,
 979                                    convpgev, &evt, convgrand, &r,
 980                                    convuint, &n))
 981     goto end;
 982   if ((x = strongprime(name, MP_NEW, nbits,
 983                        r, n, evt.proc, evt.ctx)) == 0)
 984     PGENERR;
 985   rc = mp_pywrap(x);
 986   x = 0;
 987 end:
 988   mp_drop(x);
 989   droppgev(&evt);
 990   return (rc);
 991 }
 992
 993 static PyObject *meth_limlee(PyObject *me, PyObject *arg, PyObject *kw)
 994 {
 995   char *p = "p";
 996   pgev ie = { 0 }, oe = { 0 };
 997   unsigned ql, pl;
 998   grand *r = &rand_global;
 999   unsigned on = 0;
1000   size_t i, nf = 0;
1001   PyObject *rc = 0, *vec;
1002   char *kwlist[] = { "pbits", "qbits", "name", "event", "ievent",
1003                      "rng", "nsteps", 0 };
1004   mp *x = 0, **v = 0;
1005
1006   if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&|sO&O&O&O&:limlee", kwlist,
1007                                    convuint, &pl, convuint, &ql,
1008                                    &p, convpgev, &oe, convpgev, &ie,
1009                                    convgrand, &r, convuint, &on))
1010     goto end;
1011   if ((x = limlee(p, MP_NEW, MP_NEW, ql, pl, r, on,
1012                   oe.proc, oe.ctx, ie.proc, ie.ctx, &nf, &v)) == 0)
1013     PGENERR;
1014   vec = PyList_New(nf);
1015   for (i = 0; i < nf; i++)
1016     PyList_SetItem(vec, i, mp_pywrap(v[i]));
1017   xfree(v);
1018   rc = Py_BuildValue("(NN)", mp_pywrap(x), vec);
1019 end:
1020   droppgev(&oe); droppgev(&ie);
1021   return (rc);
1022 }
1023
1024 /*----- Global stuff ------------------------------------------------------*/
1025
1026 static PyMethodDef methods[] = {
1027 #define METHNAME(name) meth_##name
1028   METH  (_PrimeFilter_smallfactor,      "smallfactor(X) -> PGRC")
1029   METH  (_RabinMiller_iters,            "iters(NBITS) -> NITERS")
1030   KWMETH(pgen,                          "\
1031 pgen(START, [name = 'p'[, [stepper = PrimeGenStepper(2)],\n\
1032      [tester = PrimeGenTester()], [event = pgen_nullev],\n\
1033      [nsteps = 0], [ntests = RabinMiller.iters(START.nbits)]) -> P")
1034   KWMETH(strongprime_setup,             "\
1035 strongprime_setup(NBITS, [name = 'p'], [event = pgen_nullev],\n\
1036                   [rng = rand], [nsteps = 0]) -> (START, JUMP)")
1037   KWMETH(strongprime,                   "\
1038 strongprime(NBITS, [name = 'p'], [event = pgen_nullev],\n\
1039             [rng = rand], [nsteps = 0]) -> P")
1040   KWMETH(limlee,                        "\
1041 limlee(PBITS, QBITS, [name = 'p'], [event = pgen_nullev],\n\
1042        [ievent = pgen_nullev], [rng = rand], [nsteps = 0]) -> (P, [Q, ...])")
1043 #undef METHNAME
1044   { 0 }
1045 };
1046
1047 void pgen_pyinit(void)
1048 {
1049   INITTYPE(pfilt, root);
1050   INITTYPE(rabin, root);
1051   INITTYPE(pgevent, root);
1052   INITTYPE(pgev, root);
1053   INITTYPE(pgstep, pgev);
1054   INITTYPE(pgjump, pgev);
1055   INITTYPE(pgtest, pgev);
1056   addmethods(methods);
1057 }
1058
1059 static PyObject *obj;
1060
1061 void pgen_pyinsert(PyObject *mod)
1062 {
1063   INSERT("PrimeFilter", pfilt_pytype);
1064   INSERT("RabinMiller", rabin_pytype);
1065   INSERT("PrimeGenEvent", pgevent_pytype);
1066   INSERT("PrimeGenBuiltinHandler", pgev_pytype);
1067   INSERT("PrimeGenStepper", pgstep_pytype);
1068   INSERT("PrimeGenJumper", pgjump_pytype);
1069   INSERT("PrimeGenTester", pgtest_pytype);
1070   INSERT("pgen_nullev", obj = pgev_stdev(0));
1071   INSERT("pgen_stdev", pgev_stdev(pgen_ev));
1072   INSERT("pgen_spinev", pgev_stdev(pgen_evspin));
1073   INSERT("pgen_subev", pgev_stdev(pgen_subev));
1074 }
1075
1076 /*----- That's all, folks -------------------------------------------------*/