[u/mdw/catacomb] / pgen.c

/* -*-c-*-
 *
 * $Id$
 *
 * Prime generation glue
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Header files ------------------------------------------------------*/

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "fibrand.h"
#include "grand.h"
#include "mp.h"
#include "mprand.h"
#include "pgen.h"
#include "pfilt.h"
#include "rabin.h"

/*----- Standard prime filter ---------------------------------------------*/

/* --- @pgen_filter@ --- */

int pgen_filter(int rq, pgen_event *ev, void *p)
{
  pgen_filterctx *f = p;
  int rc = PGEN_ABORT;

  switch (rq) {
    case PGEN_BEGIN:
      rc = pfilt_create(&f->f, ev->m);
      mp_drop(ev->m);
      break;
    case PGEN_TRY:
      mp_drop(ev->m);
      if (!((f->step | f->f.m->v[0]) & 1))
	rc = pfilt_step(&f->f, 1);
      else
	rc = pfilt_step(&f->f, f->step);
      break;
    case PGEN_DONE:
      pfilt_destroy(&f->f);
      return (PGEN_DONE);
  }
	
  while (rc == PGEN_FAIL)
    rc = pfilt_step(&f->f, f->step);
  ev->m = MP_COPY(f->f.m);
  return (rc);
}

/* --- @pgen_jump@ --- *
 *
 * Similar to the standard @pgen_filter@, but jumps in large steps rather
 * than small ones.
 */

int pgen_jump(int rq, pgen_event *ev, void *p)
{
  pgen_jumpctx *f = p;
  int rc = PGEN_ABORT;

  switch (rq) {
    case PGEN_BEGIN: {
      mp *g = MP_NEW;
      mp_gcd(&g, 0, 0, ev->m, f->j->m);
      if (MP_CMP(g, >, MP_ONE)) {
	mp_drop(g);
	return (PGEN_ABORT);
      }
      mp_drop(g);
      rc = pfilt_create(&f->f, ev->m);
      mp_drop(ev->m);
    } break;
    case PGEN_TRY:
      mp_drop(ev->m);
      rc = pfilt_jump(&f->f, f->j);
      break;
    case PGEN_DONE:
      pfilt_destroy(&f->f);
      return (PGEN_DONE);
  }
	
  while (rc == PGEN_FAIL)
    rc = pfilt_jump(&f->f, f->j);
  ev->m = MP_COPY(f->f.m);
  return (rc);
}

/*----- Standard prime test -----------------------------------------------*/

/* --- @pgen_test@ --- */

int pgen_test(int rq, pgen_event *ev, void *p)
{
  rabin *r = p;
  int rc = PGEN_ABORT;

  switch (rq) {
    case PGEN_BEGIN:
      rabin_create(r, ev->m);
      rc = PGEN_TRY;
      break;
    case PGEN_TRY:
      if (!ev->tests)
	rc = rabin_rtest(r, MP_TWO);
      else {
	mp *a = mprand_range(MP_NEW, ev->m, ev->r, 0);
	rc = rabin_rtest(r, a);
	mp_drop(a);
      }
      break;
    case PGEN_DONE:
      rabin_destroy(r);
      rc = PGEN_DONE;
      break;
  }

  return (rc);
}

/*----- The main driver ---------------------------------------------------*/

/* --- @pgen@ --- *
 *
 * Arguments:	@const char *name@ = name of the value being searched for
 *		@mp *d@ = destination for the result integer
 *		@mp *m@ = start value to pass to stepper
 *		@pgen_proc *event@ = event handler function
 *		@void *ectx@ = context argument for event andler
 *		@unsigned steps@ = number of steps to take in search
 *		@pgen_proc *step@ = stepper function to use
 *		@void *sctx@ = context argument for stepper
 *		@unsigned tests@ = number of tests to make
 *		@pgen_proc *test@ = tester function to use
 *		@void *tctx@ = context argument for tester
 *
 * Returns:	Pointer to final result, or null.
 *
 * Use:		A generalized prime-number search skeleton.  Yes, that's a
 *		scary number of arguments.
 */

mp *pgen(const char *name, mp *d, mp *m, pgen_proc *event, void *ectx,
	 unsigned steps, pgen_proc *step, void *sctx,
	 unsigned tests, pgen_proc *test, void *tctx)
{
  pgen_event ev;
  int rq, rc;
  pgen_proc *proc;
  void *ctx;
  int p;

  enum { P_STEP, P_TEST };

  /* --- Set up the initial event block --- */

  ev.name = name;
  if (m)
    ev.m = MP_COPY(m);
  else
    ev.m = 0;
  ev.steps = 0;
  ev.tests = 0;
  ev.r = fibrand_create(0);

  /* --- Tell the event handler we're under way --- */

  if (event && event(PGEN_BEGIN, &ev, ectx) == PGEN_ABORT) {
    ev.r->ops->destroy(ev.r);
    return (0);
  }

  /* --- Set up for the initial call --- */

  proc = step; ctx = sctx; p = P_STEP; rq = PGEN_BEGIN;

  /* --- Enter the great maelstrom of state transitions --- */

  for (;;) {
    unsigned act = 0;

#define A_STEP 1u
#define A_TEST 2u
#define A_EVENT 4u
#define A_ENDTEST 8u
#define A_ENDSTEP 16u
#define A_DONE 32u

    /* --- Call the procedure and decide what to do next --- */

    rc = proc(rq, &ev, ctx);
    switch (rc) {
      case PGEN_TRY:
	if (p == P_TEST)
	  rq = PGEN_TRY;
	else {
	  act |= A_EVENT;
	  proc = test; ctx = tctx; p = P_TEST;
	  rq = PGEN_BEGIN;
	}
	break;
      case PGEN_PASS:
	act |= A_TEST | A_EVENT;
	if (p == P_TEST)
	  rq = PGEN_TRY;
	else {
	  proc = test; ctx = tctx; p = P_TEST;
	  rq = PGEN_BEGIN;
	}
	break;
      case PGEN_FAIL:
	act |= A_STEP;
	if (p == P_TEST) {
	  act |= A_ENDTEST | A_EVENT;
	  proc = step; ctx = sctx; p = P_STEP;
	}
	rq = PGEN_TRY;
	break;
      case PGEN_DONE:
	act |= A_EVENT | A_DONE | A_ENDSTEP;
	if (p == P_TEST)
	  act |= A_ENDTEST;
	break;
      case PGEN_ABORT:
	act |= A_EVENT | A_DONE;
	if (p == P_TEST || rq == PGEN_TRY)
	  act |= A_ENDSTEP;
	if (p == P_TEST && rq != PGEN_BEGIN)
	  act |= A_ENDTEST;
	break;
      default:
	assert(((void)"Invalid response from function", 0));
	break;
    }

    /* --- If decrementing counters is requested, do that --- */

    if ((act & A_STEP) && steps) {
      ev.steps++;
      if (ev.steps == steps) {
	act |= A_EVENT | A_ENDSTEP | A_DONE;
	rc = PGEN_ABORT;
      }
      ev.tests = 0;
    }

    if ((act & A_TEST) && tests) {
      ev.tests++;
      if (ev.tests == tests) {
	act |= A_ENDTEST | A_ENDSTEP | A_DONE;
	rc = PGEN_DONE;
      }
    }

    /* --- Report an event if so directed --- */

    if ((act & A_EVENT) && event && event(rc, &ev, ectx) == PGEN_ABORT) {
      rc = PGEN_ABORT;
      if (!(act & A_DONE)) {
	act |= A_ENDSTEP | A_DONE;
	if (p == P_TEST)
	  act |= A_ENDTEST;
      }
    }	

    /* --- Close down tester and stepper functions --- */

    if (act & A_ENDTEST)
      test(PGEN_DONE, &ev, tctx);
    if (act & A_ENDSTEP)
      step(PGEN_DONE, &ev, sctx);

    /* --- Stop the entire test if necessary --- */

    if (act & A_DONE)
      break;
  }

  /* --- Tidy up and return --- */

  if (rc == PGEN_ABORT) {
    mp_drop(ev.m);
    ev.m = 0;
  }
  ev.r->ops->destroy(ev.r);
  mp_drop(d);

  return (ev.m);
}

/* --- @pgen_primep@ --- *
 *
 * Arguments:	@mp *p@ = a number to check
 *		@grand *gr@ = a random number source
 *
 * Returns:	Nonzero if @p@ is really prime.
 */

int pgen_primep(mp *p, grand *gr)
{
  int i;
  rabin r;
  mp *x = MP_NEW;

  if (MP_NEGP(p)) return (0);
  switch (pfilt_smallfactor(p)) {
    case PGEN_DONE: return (1);
    case PGEN_FAIL: return (0);
  }
  rabin_create(&r, p);
  for (i = 32; i; i--) {
    x = mprand_range(x, p, gr, 0);
    if (rabin_rtest(&r, x) == PGEN_FAIL)
      break;
  }
  MP_DROP(x);
  rabin_destroy(&r);
  return (!i);
}

/*----- Test rig ----------------------------------------------------------*/

#ifdef TEST_RIG

#include <mLib/testrig.h>

static int verify(dstr *v)
{
  mp *m = *(mp **)v[0].buf;
  mp *q = *(mp **)v[1].buf;
  mp *p;
  int ok = 1;

  pgen_filterctx pf;
  rabin r;

  pf.step = 2;
  p = pgen("p", MP_NEW, m, pgen_evspin, 0, 0, pgen_filter, &pf,
	   rabin_iters(mp_bits(m)), pgen_test, &r);
  if (!p || !MP_EQ(p, q)) {
    fputs("\n*** pgen failed", stderr);
    fputs("\nm = ", stderr); mp_writefile(m, stderr, 10);
    fputs("\np = ", stderr); mp_writefile(p, stderr, 10);
    fputs("\nq = ", stderr); mp_writefile(q, stderr, 10);
    fputc('\n', stderr);
    ok = 0;
  }

  mp_drop(m);
  mp_drop(q);
  mp_drop(p);
  assert(mparena_count(MPARENA_GLOBAL) == 0);
  return (ok);
}

static test_chunk tests[] = {
  { "pgen", verify, { &type_mp, &type_mp, 0 } },
  { 0, 0, { 0 } }
};

int main(int argc, char *argv[])
{
  sub_init();
  test_run(argc, argv, tests, SRCDIR "/tests/pgen");
  return (0);
}
#endif

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
0f5ec153	1	/* --c--
0f5ec153	2	*
a69a3efd	3	* $Id$
0f5ec153	4	*
581c854e	5	* Prime generation glue
0f5ec153	6	*
	7	* (c) 1999 Straylight/Edgeware
	8	*/
	9
	10	/----- Licensing notice --------------------------------------------------
	11	*
	12	* This file is part of Catacomb.
	13	*
	14	* Catacomb is free software; you can redistribute it and/or modify
	15	* it under the terms of the GNU Library General Public License as
	16	* published by the Free Software Foundation; either version 2 of the
	17	* License, or (at your option) any later version.
	18	*
	19	* Catacomb 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 Library General Public License for more details.
	23	*
	24	* You should have received a copy of the GNU Library General Public
	25	* License along with Catacomb; if not, write to the Free
	26	* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
	27	* MA 02111-1307, USA.
	28	*/
	29
0f5ec153	30	/----- Header files ------------------------------------------------------/
0f5ec153	31
581c854e	32	#include <assert.h>
	33	#include <stdio.h>
	34	#include <stdlib.h>
	35	#include <string.h>
	36
	37	#include "fibrand.h"
	38	#include "grand.h"
0f5ec153	39	#include "mp.h"
581c854e	40	#include "mprand.h"
0f5ec153	41	#include "pgen.h"
581c854e	42	#include "pfilt.h"
0f5ec153	43	#include "rabin.h"
0f5ec153	44
581c854e	45	/----- Standard prime filter ---------------------------------------------/
0f5ec153	46
581c854e	47	/* --- @pgen_filter@ --- */
0f5ec153	48
581c854e	49	int pgen_filter(int rq, pgen_event ev, void p)
0f5ec153	50	{
581c854e	51	pgen_filterctx *f = p;
	52	int rc = PGEN_ABORT;
	53
	54	switch (rq) {
	55	case PGEN_BEGIN:
	56	rc = pfilt_create(&f->f, ev->m);
	57	mp_drop(ev->m);
	58	break;
	59	case PGEN_TRY:
	60	mp_drop(ev->m);
	61	if (!((f->step \| f->f.m->v[0]) & 1))
	62	rc = pfilt_step(&f->f, 1);
0f5ec153	63	else
581c854e	64	rc = pfilt_step(&f->f, f->step);
	65	break;
	66	case PGEN_DONE:
	67	pfilt_destroy(&f->f);
	68	return (PGEN_DONE);
0f5ec153	69	}
581c854e	70
	71	while (rc == PGEN_FAIL)
	72	rc = pfilt_step(&f->f, f->step);
	73	ev->m = MP_COPY(f->f.m);
0f5ec153	74	return (rc);
	75	}
	76
581c854e	77	/* --- @pgen_jump@ --- *
0f5ec153	78	*
581c854e	79	* Similar to the standard @pgen_filter@, but jumps in large steps rather
581c854e	80	* than small ones.
0f5ec153	81	*/
0f5ec153	82
581c854e	83	int pgen_jump(int rq, pgen_event ev, void p)
0f5ec153	84	{
581c854e	85	pgen_jumpctx *f = p;
581c854e	86	int rc = PGEN_ABORT;
0f5ec153	87
581c854e	88	switch (rq) {
8b021c3f	89	case PGEN_BEGIN: {
	90	mp *g = MP_NEW;
	91	mp_gcd(&g, 0, 0, ev->m, f->j->m);
	92	if (MP_CMP(g, >, MP_ONE)) {
	93	mp_drop(g);
	94	return (PGEN_ABORT);
	95	}
	96	mp_drop(g);
581c854e	97	rc = pfilt_create(&f->f, ev->m);
581c854e	98	mp_drop(ev->m);
8b021c3f	99	} break;
581c854e	100	case PGEN_TRY:
	101	mp_drop(ev->m);
	102	rc = pfilt_jump(&f->f, f->j);
	103	break;
	104	case PGEN_DONE:
	105	pfilt_destroy(&f->f);
	106	return (PGEN_DONE);
	107	}
	108
	109	while (rc == PGEN_FAIL)
	110	rc = pfilt_jump(&f->f, f->j);
	111	ev->m = MP_COPY(f->f.m);
	112	return (rc);
	113	}
0f5ec153	114
581c854e	115	/----- Standard prime test -----------------------------------------------/
0f5ec153	116
581c854e	117	/* --- @pgen_test@ --- */
0f5ec153	118
581c854e	119	int pgen_test(int rq, pgen_event ev, void p)
	120	{
	121	rabin *r = p;
	122	int rc = PGEN_ABORT;
0f5ec153	123
581c854e	124	switch (rq) {
	125	case PGEN_BEGIN:
	126	rabin_create(r, ev->m);
	127	rc = PGEN_TRY;
	128	break;
283b9af0	129	case PGEN_TRY:
	130	if (!ev->tests)
	131	rc = rabin_rtest(r, MP_TWO);
	132	else {
	133	mp *a = mprand_range(MP_NEW, ev->m, ev->r, 0);
	134	rc = rabin_rtest(r, a);
	135	mp_drop(a);
	136	}
	137	break;
581c854e	138	case PGEN_DONE:
	139	rabin_destroy(r);
	140	rc = PGEN_DONE;
	141	break;
0f5ec153	142	}
0f5ec153	143
0f5ec153	144	return (rc);
	145	}
	146
581c854e	147	/----- The main driver ---------------------------------------------------/
	148
	149	/* --- @pgen@ --- *
bd98b2df	150	*
581c854e	151	* Arguments: @const char *name@ = name of the value being searched for
	152	* @mp *d@ = destination for the result integer
	153	* @mp *m@ = start value to pass to stepper
	154	* @pgen_proc *event@ = event handler function
	155	* @void *ectx@ = context argument for event andler
	156	* @unsigned steps@ = number of steps to take in search
	157	* @pgen_proc *step@ = stepper function to use
	158	* @void *sctx@ = context argument for stepper
	159	* @unsigned tests@ = number of tests to make
	160	* @pgen_proc *test@ = tester function to use
	161	* @void *tctx@ = context argument for tester
bd98b2df	162	*
581c854e	163	* Returns: Pointer to final result, or null.
bd98b2df	164	*
581c854e	165	* Use: A generalized prime-number search skeleton. Yes, that's a
581c854e	166	* scary number of arguments.
bd98b2df	167	*/
bd98b2df	168
581c854e	169	mp pgen(const char name, mp d, mp m, pgen_proc event, void ectx,
	170	unsigned steps, pgen_proc step, void sctx,
	171	unsigned tests, pgen_proc test, void tctx)
bd98b2df	172	{
581c854e	173	pgen_event ev;
	174	int rq, rc;
	175	pgen_proc *proc;
	176	void *ctx;
4108c8d2	177	int p;
	178
	179	enum { P_STEP, P_TEST };
bd98b2df	180
581c854e	181	/* --- Set up the initial event block --- */
bd98b2df	182
581c854e	183	ev.name = name;
	184	if (m)
	185	ev.m = MP_COPY(m);
	186	else
	187	ev.m = 0;
283b9af0	188	ev.steps = 0;
283b9af0	189	ev.tests = 0;
581c854e	190	ev.r = fibrand_create(0);
bd98b2df	191
581c854e	192	/* --- Tell the event handler we're under way --- */
bd98b2df	193
4108c8d2	194	if (event && event(PGEN_BEGIN, &ev, ectx) == PGEN_ABORT) {
4108c8d2	195	ev.r->ops->destroy(ev.r);
581c854e	196	return (0);
4108c8d2	197	}
bd98b2df	198
581c854e	199	/* --- Set up for the initial call --- */
bd98b2df	200
4108c8d2	201	proc = step; ctx = sctx; p = P_STEP; rq = PGEN_BEGIN;
0f5ec153	202
581c854e	203	/* --- Enter the great maelstrom of state transitions --- */
0f5ec153	204
581c854e	205	for (;;) {
	206	unsigned act = 0;
	207
4108c8d2	208	#define A_STEP 1u
	209	#define A_TEST 2u
	210	#define A_EVENT 4u
	211	#define A_ENDTEST 8u
	212	#define A_ENDSTEP 16u
	213	#define A_DONE 32u
581c854e	214
	215	/* --- Call the procedure and decide what to do next --- */
	216
	217	rc = proc(rq, &ev, ctx);
	218	switch (rc) {
	219	case PGEN_TRY:
4108c8d2	220	if (p == P_TEST)
581c854e	221	rq = PGEN_TRY;
	222	else {
	223	act \|= A_EVENT;
4108c8d2	224	proc = test; ctx = tctx; p = P_TEST;
581c854e	225	rq = PGEN_BEGIN;
	226	}
	227	break;
	228	case PGEN_PASS:
	229	act \|= A_TEST \| A_EVENT;
4108c8d2	230	if (p == P_TEST)
581c854e	231	rq = PGEN_TRY;
581c854e	232	else {
4108c8d2	233	proc = test; ctx = tctx; p = P_TEST;
581c854e	234	rq = PGEN_BEGIN;
	235	}
	236	break;
	237	case PGEN_FAIL:
	238	act \|= A_STEP;
4108c8d2	239	if (p == P_TEST) {
581c854e	240	act \|= A_ENDTEST \| A_EVENT;
4108c8d2	241	proc = step; ctx = sctx; p = P_STEP;
581c854e	242	}
	243	rq = PGEN_TRY;
	244	break;
	245	case PGEN_DONE:
	246	act \|= A_EVENT \| A_DONE \| A_ENDSTEP;
4108c8d2	247	if (p == P_TEST)
581c854e	248	act \|= A_ENDTEST;
	249	break;
	250	case PGEN_ABORT:
	251	act \|= A_EVENT \| A_DONE;
4108c8d2	252	if (p == P_TEST \|\| rq == PGEN_TRY)
581c854e	253	act \|= A_ENDSTEP;
4108c8d2	254	if (p == P_TEST && rq != PGEN_BEGIN)
581c854e	255	act \|= A_ENDTEST;
	256	break;
	257	default:
	258	assert(((void)"Invalid response from function", 0));
	259	break;
	260	}
0f5ec153	261
581c854e	262	/* --- If decrementing counters is requested, do that --- */
0f5ec153	263
581c854e	264	if ((act & A_STEP) && steps) {
283b9af0	265	ev.steps++;
283b9af0	266	if (ev.steps == steps) {
581c854e	267	act \|= A_EVENT \| A_ENDSTEP \| A_DONE;
	268	rc = PGEN_ABORT;
	269	}
283b9af0	270	ev.tests = 0;
581c854e	271	}
0f5ec153	272
581c854e	273	if ((act & A_TEST) && tests) {
283b9af0	274	ev.tests++;
283b9af0	275	if (ev.tests == tests) {
581c854e	276	act \|= A_ENDTEST \| A_ENDSTEP \| A_DONE;
	277	rc = PGEN_DONE;
	278	}
0f5ec153	279	}
0f5ec153	280
581c854e	281	/* --- Report an event if so directed --- */
bd98b2df	282
581c854e	283	if ((act & A_EVENT) && event && event(rc, &ev, ectx) == PGEN_ABORT) {
	284	rc = PGEN_ABORT;
	285	if (!(act & A_DONE)) {
	286	act \|= A_ENDSTEP \| A_DONE;
4108c8d2	287	if (p == P_TEST)
581c854e	288	act \|= A_ENDTEST;
	289	}
	290	}
bd98b2df	291
581c854e	292	/* --- Close down tester and stepper functions --- */
0f5ec153	293
581c854e	294	if (act & A_ENDTEST)
	295	test(PGEN_DONE, &ev, tctx);
	296	if (act & A_ENDSTEP)
	297	step(PGEN_DONE, &ev, sctx);
	298
	299	/* --- Stop the entire test if necessary --- */
	300
	301	if (act & A_DONE)
	302	break;
	303	}
	304
	305	/* --- Tidy up and return --- */
	306
	307	if (rc == PGEN_ABORT) {
	308	mp_drop(ev.m);
	309	ev.m = 0;
	310	}
	311	ev.r->ops->destroy(ev.r);
eab06f16	312	mp_drop(d);
581c854e	313
581c854e	314	return (ev.m);
0f5ec153	315	}
0f5ec153	316
34e4f738	317	/* --- @pgen_primep@ --- *
	318	*
	319	* Arguments: @mp *p@ = a number to check
	320	* @grand *gr@ = a random number source
	321	*
	322	* Returns: Nonzero if @p@ is really prime.
	323	*/
	324
	325	int pgen_primep(mp p, grand gr)
	326	{
4108c8d2	327	int i;
34e4f738	328	rabin r;
	329	mp *x = MP_NEW;
	330
a69a3efd	331	if (MP_NEGP(p)) return (0);
34e4f738	332	switch (pfilt_smallfactor(p)) {
	333	case PGEN_DONE: return (1);
	334	case PGEN_FAIL: return (0);
	335	}
	336	rabin_create(&r, p);
4108c8d2	337	for (i = 32; i; i--) {
34e4f738	338	x = mprand_range(x, p, gr, 0);
	339	if (rabin_rtest(&r, x) == PGEN_FAIL)
	340	break;
34e4f738	341	}
	342	MP_DROP(x);
	343	rabin_destroy(&r);
	344	return (!i);
	345	}
	346
581c854e	347	/----- Test rig ----------------------------------------------------------/
0f5ec153	348
	349	#ifdef TEST_RIG
	350
	351	#include <mLib/testrig.h>
	352
	353	static int verify(dstr *v)
	354	{
	355	mp m = (mp **)v[0].buf;
581c854e	356	mp q = (mp **)v[1].buf;
581c854e	357	mp *p;
0f5ec153	358	int ok = 1;
0f5ec153	359
581c854e	360	pgen_filterctx pf;
581c854e	361	rabin r;
0f5ec153	362
581c854e	363	pf.step = 2;
	364	p = pgen("p", MP_NEW, m, pgen_evspin, 0, 0, pgen_filter, &pf,
	365	rabin_iters(mp_bits(m)), pgen_test, &r);
22bab86c	366	if (!p \|\| !MP_EQ(p, q)) {
581c854e	367	fputs("\n*** pgen failed", stderr);
0f5ec153	368	fputs("\nm = ", stderr); mp_writefile(m, stderr, 10);
581c854e	369	fputs("\np = ", stderr); mp_writefile(p, stderr, 10);
581c854e	370	fputs("\nq = ", stderr); mp_writefile(q, stderr, 10);
0f5ec153	371	fputc('\n', stderr);
	372	ok = 0;
	373	}
	374
	375	mp_drop(m);
581c854e	376	mp_drop(q);
eab06f16	377	mp_drop(p);
d94f85ac	378	assert(mparena_count(MPARENA_GLOBAL) == 0);
0f5ec153	379	return (ok);
	380	}
	381
	382	static test_chunk tests[] = {
	383	{ "pgen", verify, { &type_mp, &type_mp, 0 } },
	384	{ 0, 0, { 0 } }
	385	};
	386
	387	int main(int argc, char *argv[])
	388	{
	389	sub_init();
	390	test_run(argc, argv, tests, SRCDIR "/tests/pgen");
	391	return (0);
	392	}
0f5ec153	393	#endif
	394
	395	/----- That's all, folks -------------------------------------------------/