chiark / gitweb /
~mdw / catacomb-python / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
catacomb-python.h: Don't inhibit 64-bit type detection any more.
[catacomb-python] / pgen.c
CommitLineData
d7ab1bab 1/* -*-c-*-
d7ab1bab 2 *
3 * Prime number generation
4 *
5 * (c) 2005 Straylight/Edgeware
6 */
7
b2687a0a 8/*----- Licensing notice --------------------------------------------------*
d7ab1bab 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.
b2687a0a 16 *
d7ab1bab 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.
b2687a0a 21 *
d7ab1bab 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
33PyTypeObject *pfilt_pytype;
34
35static 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);
b2687a0a 41 return ((PyObject *)o);
d7ab1bab 42}
43
44static 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);
53end:
54 mp_drop(x);
55 return ((PyObject *)o);
56}
57
58static 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
68static void pfilt_pydealloc(PyObject *me)
3aa33042 69 { pfilt_destroy(PFILT_F(me)); FREEOBJ(me); }
d7ab1bab 70
71static 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
80static 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
92static CONVFUNC(pfilt, pfilt *, PFILT_F)
93
94static 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
103static 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));
110end:
111 mp_drop(x);
112 return (rc);
113}
114
115static int pfilt_pynonzerop(PyObject *me)
116 { return (PFILT_ST(me) != PGEN_FAIL); }
117
118static PyObject *pfilt_pyint(PyObject *me)
119{
120 long l;
121 PyObject *rc = 0;
122
123 if (mp_tolong_checked(PFILT_F(me)->m, &l)) goto end;
124 rc = PyInt_FromLong(l);
125end:
126 return (rc);
127}
128
129static PyObject *pfilt_pylong(PyObject *me)
f368b46e 130 { return (mp_topylong(PFILT_F(me)->m)); }
d7ab1bab 131
132static PyObject *pfget_x(PyObject *me, void *hunoz)
133 { return (mp_pywrap(MP_COPY(PFILT_F(me)->m))); }
134
135static PyObject *pfget_status(PyObject *me, void *hunoz)
136 { return (PyInt_FromLong(PFILT_ST(me))); }
137
138static PyGetSetDef pfilt_pygetset[] = {
139#define GETSETNAME(op, name) pf##op##_##name
140 GET (x, "F.x -> current position of filter")
141 GET (status, "F.status -> primality status of filter")
142#undef GETSETNAME
143 { 0 }
144};
145
146static PyMethodDef pfilt_pymethods[] = {
147#define METHNAME(name) pfmeth_##name
148 METH (step, "F.step(N)")
149 METH (muladd, "F.muladd(M, A)")
150 METH (jump, "F.jump(FF)")
151#undef METHNAME
152 { 0 }
153};
154
155static PyNumberMethods pfilt_pynumber = {
156 0, /* @nb_add@ */
157 0, /* @nb_subtract@ */
158 0, /* @nb_multiply@ */
159 0, /* @nb_divide@ */
160 0, /* @nb_remainder@ */
161 0, /* @nb_divmod@ */
162 0, /* @nb_power@ */
163 0, /* @nb_negative@ */
164 0, /* @nb_positive@ */
165 0, /* @nb_absolute@ */
166 pfilt_pynonzerop, /* @nb_nonzero@ */
167 0, /* @nb_invert@ */
168 0, /* @nb_lshift@ */
169 0, /* @nb_rshift@ */
170 0, /* @nb_and@ */
171 0, /* @nb_xor@ */
172 0, /* @nb_or@ */
173 0, /* @nb_coerce@ */
174 pfilt_pyint, /* @nb_int@ */
175 pfilt_pylong, /* @nb_long@ */
176 0, /* @nb_float@ */
177 0, /* @nb_oct@ */
178 0, /* @nb_hex@ */
179
180 0, /* @nb_inplace_add@ */
181 0, /* @nb_inplace_subtract@ */
182 0, /* @nb_inplace_multiply@ */
183 0, /* @nb_inplace_divide@ */
184 0, /* @nb_inplace_remainder@ */
185 0, /* @nb_inplace_power@ */
186 0, /* @nb_inplace_lshift@ */
187 0, /* @nb_inplace_rshift@ */
188 0, /* @nb_inplace_and@ */
189 0, /* @nb_inplace_xor@ */
190 0, /* @nb_inplace_or@ */
191
192 0, /* @nb_floor_divide@ */
193 0, /* @nb_true_divide@ */
194 0, /* @nb_inplace_floor_divide@ */
195 0, /* @nb_inplace_true_divide@ */
196};
197
198static PyTypeObject pfilt_pytype_skel = {
6d4db0bf 199 PyObject_HEAD_INIT(0) 0, /* Header */
c461c9b3 200 "PrimeFilter", /* @tp_name@ */
d7ab1bab 201 sizeof(pfilt_pyobj), /* @tp_basicsize@ */
202 0, /* @tp_itemsize@ */
203
204 pfilt_pydealloc, /* @tp_dealloc@ */
205 0, /* @tp_print@ */
206 0, /* @tp_getattr@ */
207 0, /* @tp_setattr@ */
208 0, /* @tp_compare@ */
209 0, /* @tp_repr@ */
210 &pfilt_pynumber, /* @tp_as_number@ */
211 0, /* @tp_as_sequence@ */
212 0, /* @tp_as_mapping@ */
213 0, /* @tp_hash@ */
214 0, /* @tp_call@ */
215 0, /* @tp_str@ */
216 0, /* @tp_getattro@ */
217 0, /* @tp_setattro@ */
218 0, /* @tp_as_buffer@ */
219 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
220 Py_TPFLAGS_BASETYPE,
221
222 /* @tp_doc@ */
223"Small-primes filter.",
224
225 0, /* @tp_traverse@ */
226 0, /* @tp_clear@ */
227 0, /* @tp_richcompare@ */
228 0, /* @tp_weaklistoffset@ */
229 0, /* @tp_iter@ */
963a6148 230 0, /* @tp_iternext@ */
d7ab1bab 231 pfilt_pymethods, /* @tp_methods@ */
232 0, /* @tp_members@ */
233 pfilt_pygetset, /* @tp_getset@ */
234 0, /* @tp_base@ */
235 0, /* @tp_dict@ */
236 0, /* @tp_descr_get@ */
237 0, /* @tp_descr_set@ */
238 0, /* @tp_dictoffset@ */
239 0, /* @tp_init@ */
240 PyType_GenericAlloc, /* @tp_alloc@ */
241 pfilt_pynew, /* @tp_new@ */
3aa33042 242 0, /* @tp_free@ */
d7ab1bab 243 0 /* @tp_is_gc@ */
244};
245
246/*----- Rabin-Miller testing ----------------------------------------------*/
247
248typedef struct rabin_pyobj {
249 PyObject_HEAD
250 rabin r;
251} rabin_pyobj;
252
253static PyTypeObject *rabin_pytype;
254#define RABIN_R(o) (&((rabin_pyobj *)(o))->r)
255
256static PyObject *rabin_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
257{
258 mp *x = 0;
259 rabin_pyobj *o = 0;
260 char *kwlist[] = { "x", 0 };
261
262 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &x))
263 goto end;
264 if (!MP_POSP(x) || MP_EVENP(x)) VALERR("must be positive and odd");
265 o = (rabin_pyobj *)ty->tp_alloc(ty, 0);
266 rabin_create(&o->r, x);
267end:
268 return ((PyObject *)o);
269}
270
271static void rabin_pydealloc(PyObject *me)
272{
273 rabin_destroy(RABIN_R(me));
3aa33042 274 FREEOBJ(me);
d7ab1bab 275}
276
277static PyObject *rmeth_test(PyObject *me, PyObject *arg)
278{
279 mp *w = 0;
280 PyObject *rc = 0;
281
282 if (!PyArg_ParseTuple(arg, "O&:test", convmp, &w)) goto end;
283 rc = PyInt_FromLong(rabin_test(RABIN_R(me), w));
284end:
285 mp_drop(w);
286 return (rc);
287}
288
289static PyObject *rmeth_rtest(PyObject *me, PyObject *arg)
290{
291 mp *w = 0;
292 PyObject *rc = 0;
293
294 if (!PyArg_ParseTuple(arg, "O&:rtest", convmp, &w)) goto end;
295 rc = PyInt_FromLong(rabin_rtest(RABIN_R(me), w));
296end:
297 mp_drop(w);
298 return (rc);
299}
300
301static PyObject *rget_niters(PyObject *me, void *hunoz)
302 { return (PyInt_FromLong(rabin_iters(mp_bits(RABIN_R(me)->mm.m)))); }
303
304static PyObject *rget_x(PyObject *me, void *hunoz)
305 { return (mp_pywrap(MP_COPY(RABIN_R(me)->mm.m))); }
306
307static PyObject *meth__RabinMiller_iters(PyObject *me, PyObject *arg)
308{
309 unsigned n;
310
311 if (!PyArg_ParseTuple(arg, "OO&:iters", &me, convuint, &n)) return (0);
312 return (PyInt_FromLong(rabin_iters(n)));
313}
314
315static PyGetSetDef rabin_pygetset[] = {
316#define GETSETNAME(op, name) r##op##_##name
317 GET (x, "R.x -> number under test")
318 GET (niters, "R.niters -> suggested number of tests")
319#undef GETSETNAME
320 { 0 }
321};
322
323static PyMethodDef rabin_pymethods[] = {
324#define METHNAME(name) rmeth_##name
325 METH (test, "R.test(W) -> PGST")
326 METH (rtest, "R.rtest(W) -> PGST")
327#undef METHNAME
328 { 0 }
329};
330
331static PyTypeObject rabin_pytype_skel = {
6d4db0bf 332 PyObject_HEAD_INIT(0) 0, /* Header */
c461c9b3 333 "RabinMiller", /* @tp_name@ */
d7ab1bab 334 sizeof(rabin_pyobj), /* @tp_basicsize@ */
335 0, /* @tp_itemsize@ */
336
337 rabin_pydealloc, /* @tp_dealloc@ */
338 0, /* @tp_print@ */
339 0, /* @tp_getattr@ */
340 0, /* @tp_setattr@ */
341 0, /* @tp_compare@ */
342 0, /* @tp_repr@ */
343 0, /* @tp_as_number@ */
344 0, /* @tp_as_sequence@ */
345 0, /* @tp_as_mapping@ */
346 0, /* @tp_hash@ */
347 0, /* @tp_call@ */
348 0, /* @tp_str@ */
349 0, /* @tp_getattro@ */
350 0, /* @tp_setattro@ */
351 0, /* @tp_as_buffer@ */
352 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
353 Py_TPFLAGS_BASETYPE,
354
355 /* @tp_doc@ */
356"Rabin-Miller strong primality test.",
357
358 0, /* @tp_traverse@ */
359 0, /* @tp_clear@ */
360 0, /* @tp_richcompare@ */
361 0, /* @tp_weaklistoffset@ */
362 0, /* @tp_iter@ */
963a6148 363 0, /* @tp_iternext@ */
d7ab1bab 364 rabin_pymethods, /* @tp_methods@ */
365 0, /* @tp_members@ */
366 rabin_pygetset, /* @tp_getset@ */
367 0, /* @tp_base@ */
368 0, /* @tp_dict@ */
369 0, /* @tp_descr_get@ */
370 0, /* @tp_descr_set@ */
371 0, /* @tp_dictoffset@ */
372 0, /* @tp_init@ */
373 PyType_GenericAlloc, /* @tp_alloc@ */
374 rabin_pynew, /* @tp_new@ */
3aa33042 375 0, /* @tp_free@ */
d7ab1bab 376 0 /* @tp_is_gc@ */
377};
378
379/*----- Events ------------------------------------------------------------*/
380
381typedef struct pgevent_pyobj {
382 PyObject_HEAD
383 pgen_event *ev;
384} pgevent_pyobj;
385
386static PyTypeObject *pgevent_pytype;
387#define PGEVENT_EV(o) (((pgevent_pyobj *)(o))->ev)
388
389static PyObject *pgevent_pywrap(pgen_event *ev)
390{
391 pgevent_pyobj *o = PyObject_New(pgevent_pyobj, pgevent_pytype);
392 o->ev = ev;
393 return ((PyObject *)o);
394}
395
396static CONVFUNC(pgevent, pgen_event *, PGEVENT_EV)
397
398static void pgevent_kill(PyObject *me) { PGEVENT_EV(me) = 0; }
3aa33042 399static void pgevent_pydealloc(PyObject *me) { FREEOBJ(me); }
d7ab1bab 400
401#define PGEVENT_CHECK(me) do { \
402 if (!PGEVENT_EV(me)) { \
403 PyErr_SetString(PyExc_ValueError, "event object is dead"); \
404 return (0); \
405 } \
406} while (0)
407
408static PyObject *peget_name(PyObject *me, void *hunoz)
409 { PGEVENT_CHECK(me); return (PyString_FromString(PGEVENT_EV(me)->name)); }
410
411static PyObject *peget_x(PyObject *me, void *hunoz)
412 { PGEVENT_CHECK(me); return (mp_pywrap(MP_COPY(PGEVENT_EV(me)->m))); }
413
414static PyObject *peget_steps(PyObject *me, void *hunoz)
415 { PGEVENT_CHECK(me); return (PyInt_FromLong(PGEVENT_EV(me)->steps)); }
416
417static PyObject *peget_tests(PyObject *me, void *hunoz)
418 { PGEVENT_CHECK(me); return (PyInt_FromLong(PGEVENT_EV(me)->tests)); }
419
420static PyObject *peget_rng(PyObject *me, void *hunoz)
421 { PGEVENT_CHECK(me); return (grand_pywrap(PGEVENT_EV(me)->r, 0)); }
422
423static int peset_x(PyObject *me, PyObject *xobj, void *hunoz)
424{
425 mp *x = 0;
426 pgen_event *ev = PGEVENT_EV(me);
427 int rc = -1;
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;
433end:
434 mp_drop(x);
435 return (rc);
436}
437
438static 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
449static PyTypeObject pgevent_pytype_skel = {
6d4db0bf 450 PyObject_HEAD_INIT(0) 0, /* Header */
c461c9b3 451 "PrimeGenEvent", /* @tp_name@ */
d7ab1bab 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@ */
963a6148 481 0, /* @tp_iternext@ */
d7ab1bab 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@ */
3aa33042 493 0, /* @tp_free@ */
d7ab1bab 494 0 /* @tp_is_gc@ */
495};
496
497/*----- Event handlers ----------------------------------------------------*/
498
499PyTypeObject *pgev_pytype;
500
501typedef struct pgstep_pyobj {
502 PGEV_HEAD
503 pgen_filterctx f;
504} pgstep_pyobj;
505
506static PyTypeObject *pgstep_pytype;
507#define PGSTEP_STEP(o) (((pgstep_pyobj *)(o))->f.step)
508
509typedef struct pgjump_pyobj {
510 PGEV_HEAD
511 PyObject *fobj;
512 pgen_jumpctx j;
513} pgjump_pyobj;
514
515static PyTypeObject *pgjump_pytype;
516#define PGJUMP_FOBJ(o) (((pgjump_pyobj *)(o))->fobj)
517#define PGJUMP_J(o) (&((pgjump_pyobj *)(o))->j)
518
519typedef struct pgtest_pyobj {
520 PGEV_HEAD
521 rabin r;
522} pgtest_pyobj;
523
524static PyTypeObject *pgtest_pytype;
525
526static 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");
b2687a0a 549 else
d7ab1bab 550 st = l;
551end:
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
561static 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
570int 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
584void droppgev(pgev *p)
585{
586 if (p->proc == pgev_python) {
587 PyObject *py = p->ctx;
588 Py_DECREF(py);
589 }
590}
591
592static 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));
600end:
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); }
607PGMETH(abort, ABORT)
608PGMETH(done, DONE)
609PGMETH(begin, BEGIN)
610PGMETH(try, TRY)
611PGMETH(pass, PASS)
612PGMETH(fail, FAIL)
613#undef PGMETH
614
615static PyObject *pgev_stdev(pgen_proc *proc)
616 { pgev pg; pg.proc = proc; pg.ctx = 0; return (pgev_pywrap(&pg)); }
617
618static PyMethodDef pgev_pymethods[] = {
619#define METHNAME(name) pgmeth_##name
620 METH (pg_abort, "E.pg_abort() -> PGRC -- prime generation aborted")
621 METH (pg_done, "E.pg_done() -> PGRC -- prime generation finished")
622 METH (pg_begin, "E.pg_begin() -> PGRC -- commence stepping/testing")
623 METH (pg_try, "E.pg_try() -> PGRC -- found new candidate")
624 METH (pg_pass, "E.pg_pass() -> PGRC -- passed primality test")
625 METH (pg_fail, "E.pg_fail() -> PGRC -- failed primality test")
626#undef METHNAME
627 { 0 }
628};
629
630static PyTypeObject pgev_pytype_skel = {
6d4db0bf 631 PyObject_HEAD_INIT(0) 0, /* Header */
c461c9b3 632 "PrimeGenBuiltinHandler", /* @tp_name@ */
d7ab1bab 633 sizeof(pgev_pyobj), /* @tp_basicsize@ */
634 0, /* @tp_itemsize@ */
635
3aa33042 636 0, /* @tp_dealloc@ */
d7ab1bab 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@ */
963a6148 662 0, /* @tp_iternext@ */
d7ab1bab 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@ */
3aa33042 674 0, /* @tp_free@ */
d7ab1bab 675 0 /* @tp_is_gc@ */
676};
677
678static 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;
690end:
691 return ((PyObject *)rc);
692}
693
694static PyObject *psget_step(PyObject *me, void *hunoz)
695 { return (PyInt_FromLong(PGSTEP_STEP(me))); }
696
697static PyGetSetDef pgstep_pygetset[] = {
698#define GETSETNAME(op, name) ps##op##_##name
b2687a0a 699 GET (step, "S.step -> step size for the stepper")
d7ab1bab 700#undef GETSETNAME
701 { 0 }
702};
703
704static PyTypeObject pgstep_pytype_skel = {
6d4db0bf 705 PyObject_HEAD_INIT(0) 0, /* Header */
c461c9b3 706 "PrimeGenStepper", /* @tp_name@ */
d7ab1bab 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@ */
963a6148 736 0, /* @tp_iternext@ */
d7ab1bab 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@ */
3aa33042 748 0, /* @tp_free@ */
d7ab1bab 749 0 /* @tp_is_gc@ */
750};
751
752static 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;
766end:
767 return ((PyObject *)rc);
768}
769
770static void pgjump_pydealloc(PyObject *me)
771{
772 Py_DECREF(PGJUMP_FOBJ(me));
3aa33042 773 FREEOBJ(me);
d7ab1bab 774}
775
776static PyObject *pjget_jump(PyObject *me, void *hunoz)
777 { RETURN_OBJ(PGJUMP_FOBJ(me)); }
778
779static PyGetSetDef pgjump_pygetset[] = {
780#define GETSETNAME(op, name) pj##op##_##name
b2687a0a 781 GET (jump, "S.jump -> jump size for the stepper")
d7ab1bab 782#undef GETSETNAME
783 { 0 }
784};
785
786static PyTypeObject pgjump_pytype_skel = {
6d4db0bf 787 PyObject_HEAD_INIT(0) 0, /* Header */
c461c9b3 788 "PrimeGenJumper", /* @tp_name@ */
d7ab1bab 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@ */
963a6148 818 0, /* @tp_iternext@ */
d7ab1bab 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@ */
3aa33042 830 0, /* @tp_free@ */
d7ab1bab 831 0 /* @tp_is_gc@ */
832};
833
834static 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;
843end:
844 return ((PyObject *)rc);
845}
846
847static PyTypeObject pgtest_pytype_skel = {
6d4db0bf 848 PyObject_HEAD_INIT(0) 0, /* Header */
c461c9b3 849 "PrimeGenTester", /* @tp_name@ */
d7ab1bab 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@ */
963a6148 879 0, /* @tp_iternext@ */
d7ab1bab 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@ */
3aa33042 891 0, /* @tp_free@ */
d7ab1bab 892 0 /* @tp_is_gc@ */
893};
894
895/*----- Prime generation functions ----------------------------------------*/
896
897void pgenerr(void)
898{
899 if (!PyErr_Occurred())
900 PyErr_SetString(PyExc_ValueError, "prime generation failed");
901}
902
903static 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;
931end:
932 mp_drop(r); mp_drop(x);
933 droppgev(&step); droppgev(&test); droppgev(&evt);
b2687a0a 934 return (rc);
d7ab1bab 935}
936
937static 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;
960end:
961 mp_drop(x);
962 droppgev(&evt);
963 return (rc);
964}
965
966static 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;
987end:
988 mp_drop(x);
989 droppgev(&evt);
990 return (rc);
991}
992
993static 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);
1019end:
1020 droppgev(&oe); droppgev(&ie);
1021 return (rc);
1022}
1023
1024/*----- Global stuff ------------------------------------------------------*/
1025
1026static 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, "\
1031pgen(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, "\
1035strongprime_setup(NBITS, [name = 'p', event = pgen_nullev,\n\
b2687a0a 1036 rng = rand, nsteps = 0]) -> (START, JUMP)")
d7ab1bab 1037 KWMETH(strongprime, "\
986bcc44
MW		 1038strongprime(NBITS, [name = 'p', event = pgen_nullev,\n\
1039 rng = rand, nsteps = 0]) -> P")
d7ab1bab 1040 KWMETH(limlee, "\
1041limlee(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
1047void 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
1059static PyObject *obj;
1060
1061void 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 -------------------------------------------------*/
Catacomb cryptographic library -- Python bindings