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

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