[u/mdw/catacomb] / pgen.c

/* -*-c-*-
 *
 * $Id: pgen.c,v 1.4 1999/12/22 16:01:11 mdw Exp $
 *
 * 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.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: pgen.c,v $
 * Revision 1.4  1999/12/22 16:01:11  mdw
 * Same file, completely different code.  Main interface for new prime-
 * search system.
 *
 */

/*----- 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:
      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: {
      mp *a = mprand_range(MP_NEW, ev->m, ev->r, 0);
      rc = rabin_test(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;

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

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

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

  if (event && event(PGEN_BEGIN, &ev, ectx) == PGEN_ABORT)
    return (0);

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

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

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

  for (;;) {
    unsigned act = 0;

    enum {
      A_STEP = 1u,
      A_TEST = 2u,
      A_EVENT = 4u,
      A_ENDTEST = 8u,
      A_ENDSTEP = 16u,
      A_DONE = 32u
    };

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

    rc = proc(rq, &ev, ctx);
    switch (rc) {
      case PGEN_TRY:
	if (proc == test)
	  rq = PGEN_TRY;
	else {
	  act |= A_EVENT;
	  proc = test; ctx = tctx;
	  rq = PGEN_BEGIN;
	}
	break;
      case PGEN_PASS:
	act |= A_TEST | A_EVENT;
	if (proc == test)
	  rq = PGEN_TRY;
	else {
	  proc = test; ctx = tctx;
	  rq = PGEN_BEGIN;
	}
	break;
      case PGEN_FAIL:
	act |= A_STEP;
	if (proc == test) {
	  act |= A_ENDTEST | A_EVENT;
	  proc = step; ctx = sctx;
	}
	rq = PGEN_TRY;
	break;
      case PGEN_DONE:
	act |= A_EVENT | A_DONE | A_ENDSTEP;
	if (proc == test)
	  act |= A_ENDTEST;
	break;
      case PGEN_ABORT:
	act |= A_EVENT | A_DONE;
	if (proc == test || rq == PGEN_TRY)
	  act |= A_ENDSTEP;
	if (proc == 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) {
	act |= A_EVENT | A_ENDSTEP | A_DONE;
	rc = PGEN_ABORT;
      }
      ev.tests = tests;
    }

    if ((act & A_TEST) && tests) {
      ev.tests--;
      if (!ev.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 (proc == 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);
  if (d != MP_NEW)
    mp_drop(d);

  return (ev.m);
}

/*----- 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_CMP(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);
  if (p)
    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	*
581c854e	3	* $Id: pgen.c,v 1.4 1999/12/22 16:01:11 mdw Exp $
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
	30	/----- Revision history --------------------------------------------------
	31	*
	32	* $Log: pgen.c,v $
581c854e	33	* Revision 1.4 1999/12/22 16:01:11 mdw
	34	* Same file, completely different code. Main interface for new prime-
	35	* search system.
0f5ec153	36	*
	37	*/
	38
	39	/----- Header files ------------------------------------------------------/
	40
581c854e	41	#include <assert.h>
	42	#include <stdio.h>
	43	#include <stdlib.h>
	44	#include <string.h>
	45
	46	#include "fibrand.h"
	47	#include "grand.h"
0f5ec153	48	#include "mp.h"
581c854e	49	#include "mprand.h"
0f5ec153	50	#include "pgen.h"
581c854e	51	#include "pfilt.h"
0f5ec153	52	#include "rabin.h"
0f5ec153	53
581c854e	54	/----- Standard prime filter ---------------------------------------------/
0f5ec153	55
581c854e	56	/* --- @pgen_filter@ --- */
0f5ec153	57
581c854e	58	int pgen_filter(int rq, pgen_event ev, void p)
0f5ec153	59	{
581c854e	60	pgen_filterctx *f = p;
	61	int rc = PGEN_ABORT;
	62
	63	switch (rq) {
	64	case PGEN_BEGIN:
	65	rc = pfilt_create(&f->f, ev->m);
	66	mp_drop(ev->m);
	67	break;
	68	case PGEN_TRY:
	69	mp_drop(ev->m);
	70	if (!((f->step \| f->f.m->v[0]) & 1))
	71	rc = pfilt_step(&f->f, 1);
0f5ec153	72	else
581c854e	73	rc = pfilt_step(&f->f, f->step);
	74	break;
	75	case PGEN_DONE:
	76	pfilt_destroy(&f->f);
	77	return (PGEN_DONE);
0f5ec153	78	}
581c854e	79
	80	while (rc == PGEN_FAIL)
	81	rc = pfilt_step(&f->f, f->step);
	82	ev->m = MP_COPY(f->f.m);
0f5ec153	83	return (rc);
	84	}
	85
581c854e	86	/* --- @pgen_jump@ --- *
0f5ec153	87	*
581c854e	88	* Similar to the standard @pgen_filter@, but jumps in large steps rather
581c854e	89	* than small ones.
0f5ec153	90	*/
0f5ec153	91
581c854e	92	int pgen_jump(int rq, pgen_event ev, void p)
0f5ec153	93	{
581c854e	94	pgen_jumpctx *f = p;
581c854e	95	int rc = PGEN_ABORT;
0f5ec153	96
581c854e	97	switch (rq) {
	98	case PGEN_BEGIN:
	99	rc = pfilt_create(&f->f, ev->m);
	100	mp_drop(ev->m);
	101	break;
	102	case PGEN_TRY:
	103	mp_drop(ev->m);
	104	rc = pfilt_jump(&f->f, f->j);
	105	break;
	106	case PGEN_DONE:
	107	pfilt_destroy(&f->f);
	108	return (PGEN_DONE);
	109	}
	110
	111	while (rc == PGEN_FAIL)
	112	rc = pfilt_jump(&f->f, f->j);
	113	ev->m = MP_COPY(f->f.m);
	114	return (rc);
	115	}
0f5ec153	116
581c854e	117	/----- Standard prime test -----------------------------------------------/
0f5ec153	118
581c854e	119	/* --- @pgen_test@ --- */
0f5ec153	120
581c854e	121	int pgen_test(int rq, pgen_event ev, void p)
	122	{
	123	rabin *r = p;
	124	int rc = PGEN_ABORT;
0f5ec153	125
581c854e	126	switch (rq) {
	127	case PGEN_BEGIN:
	128	rabin_create(r, ev->m);
	129	rc = PGEN_TRY;
	130	break;
	131	case PGEN_TRY: {
	132	mp *a = mprand_range(MP_NEW, ev->m, ev->r, 0);
	133	rc = rabin_test(r, a);
	134	mp_drop(a);
	135	} break;
	136	case PGEN_DONE:
	137	rabin_destroy(r);
	138	rc = PGEN_DONE;
	139	break;
0f5ec153	140	}
0f5ec153	141
0f5ec153	142	return (rc);
	143	}
	144
581c854e	145	/----- The main driver ---------------------------------------------------/
	146
	147	/* --- @pgen@ --- *
bd98b2df	148	*
581c854e	149	* Arguments: @const char *name@ = name of the value being searched for
	150	* @mp *d@ = destination for the result integer
	151	* @mp *m@ = start value to pass to stepper
	152	* @pgen_proc *event@ = event handler function
	153	* @void *ectx@ = context argument for event andler
	154	* @unsigned steps@ = number of steps to take in search
	155	* @pgen_proc *step@ = stepper function to use
	156	* @void *sctx@ = context argument for stepper
	157	* @unsigned tests@ = number of tests to make
	158	* @pgen_proc *test@ = tester function to use
	159	* @void *tctx@ = context argument for tester
bd98b2df	160	*
581c854e	161	* Returns: Pointer to final result, or null.
bd98b2df	162	*
581c854e	163	* Use: A generalized prime-number search skeleton. Yes, that's a
581c854e	164	* scary number of arguments.
bd98b2df	165	*/
bd98b2df	166
581c854e	167	mp pgen(const char name, mp d, mp m, pgen_proc event, void ectx,
	168	unsigned steps, pgen_proc step, void sctx,
	169	unsigned tests, pgen_proc test, void tctx)
bd98b2df	170	{
581c854e	171	pgen_event ev;
	172	int rq, rc;
	173	pgen_proc *proc;
	174	void *ctx;
bd98b2df	175
581c854e	176	/* --- Set up the initial event block --- */
bd98b2df	177
581c854e	178	ev.name = name;
	179	if (m)
	180	ev.m = MP_COPY(m);
	181	else
	182	ev.m = 0;
	183	ev.steps = steps;
	184	ev.tests = tests;
	185	ev.r = fibrand_create(0);
bd98b2df	186
581c854e	187	/* --- Tell the event handler we're under way --- */
bd98b2df	188
581c854e	189	if (event && event(PGEN_BEGIN, &ev, ectx) == PGEN_ABORT)
581c854e	190	return (0);
bd98b2df	191
581c854e	192	/* --- Set up for the initial call --- */
bd98b2df	193
581c854e	194	proc = step; ctx = sctx; rq = PGEN_BEGIN;
0f5ec153	195
581c854e	196	/* --- Enter the great maelstrom of state transitions --- */
0f5ec153	197
581c854e	198	for (;;) {
	199	unsigned act = 0;
	200
	201	enum {
	202	A_STEP = 1u,
	203	A_TEST = 2u,
	204	A_EVENT = 4u,
	205	A_ENDTEST = 8u,
	206	A_ENDSTEP = 16u,
	207	A_DONE = 32u
	208	};
	209
	210	/* --- Call the procedure and decide what to do next --- */
	211
	212	rc = proc(rq, &ev, ctx);
	213	switch (rc) {
	214	case PGEN_TRY:
	215	if (proc == test)
	216	rq = PGEN_TRY;
	217	else {
	218	act \|= A_EVENT;
	219	proc = test; ctx = tctx;
	220	rq = PGEN_BEGIN;
	221	}
	222	break;
	223	case PGEN_PASS:
	224	act \|= A_TEST \| A_EVENT;
	225	if (proc == test)
	226	rq = PGEN_TRY;
	227	else {
	228	proc = test; ctx = tctx;
	229	rq = PGEN_BEGIN;
	230	}
	231	break;
	232	case PGEN_FAIL:
	233	act \|= A_STEP;
	234	if (proc == test) {
	235	act \|= A_ENDTEST \| A_EVENT;
	236	proc = step; ctx = sctx;
	237	}
	238	rq = PGEN_TRY;
	239	break;
	240	case PGEN_DONE:
	241	act \|= A_EVENT \| A_DONE \| A_ENDSTEP;
	242	if (proc == test)
	243	act \|= A_ENDTEST;
	244	break;
	245	case PGEN_ABORT:
	246	act \|= A_EVENT \| A_DONE;
	247	if (proc == test \|\| rq == PGEN_TRY)
	248	act \|= A_ENDSTEP;
	249	if (proc == test && rq == PGEN_BEGIN)
	250	act \|= A_ENDTEST;
	251	break;
	252	default:
	253	assert(((void)"Invalid response from function", 0));
	254	break;
	255	}
0f5ec153	256
581c854e	257	/* --- If decrementing counters is requested, do that --- */
0f5ec153	258
581c854e	259	if ((act & A_STEP) && steps) {
	260	ev.steps--;
	261	if (!ev.steps) {
	262	act \|= A_EVENT \| A_ENDSTEP \| A_DONE;
	263	rc = PGEN_ABORT;
	264	}
	265	ev.tests = tests;
	266	}
0f5ec153	267
581c854e	268	if ((act & A_TEST) && tests) {
	269	ev.tests--;
	270	if (!ev.tests) {
	271	act \|= A_ENDTEST \| A_ENDSTEP \| A_DONE;
	272	rc = PGEN_DONE;
	273	}
0f5ec153	274	}
0f5ec153	275
581c854e	276	/* --- Report an event if so directed --- */
bd98b2df	277
581c854e	278	if ((act & A_EVENT) && event && event(rc, &ev, ectx) == PGEN_ABORT) {
	279	rc = PGEN_ABORT;
	280	if (!(act & A_DONE)) {
	281	act \|= A_ENDSTEP \| A_DONE;
	282	if (proc == test)
	283	act \|= A_ENDTEST;
	284	}
	285	}
bd98b2df	286
581c854e	287	/* --- Close down tester and stepper functions --- */
0f5ec153	288
581c854e	289	if (act & A_ENDTEST)
	290	test(PGEN_DONE, &ev, tctx);
	291	if (act & A_ENDSTEP)
	292	step(PGEN_DONE, &ev, sctx);
	293
	294	/* --- Stop the entire test if necessary --- */
	295
	296	if (act & A_DONE)
	297	break;
	298	}
	299
	300	/* --- Tidy up and return --- */
	301
	302	if (rc == PGEN_ABORT) {
	303	mp_drop(ev.m);
	304	ev.m = 0;
	305	}
	306	ev.r->ops->destroy(ev.r);
	307	if (d != MP_NEW)
	308	mp_drop(d);
	309
	310	return (ev.m);
0f5ec153	311	}
0f5ec153	312
581c854e	313	/----- Test rig ----------------------------------------------------------/
0f5ec153	314
	315	#ifdef TEST_RIG
	316
	317	#include <mLib/testrig.h>
	318
	319	static int verify(dstr *v)
	320	{
	321	mp m = (mp **)v[0].buf;
581c854e	322	mp q = (mp **)v[1].buf;
581c854e	323	mp *p;
0f5ec153	324	int ok = 1;
0f5ec153	325
581c854e	326	pgen_filterctx pf;
581c854e	327	rabin r;
0f5ec153	328
581c854e	329	pf.step = 2;
	330	p = pgen("p", MP_NEW, m, pgen_evspin, 0, 0, pgen_filter, &pf,
	331	rabin_iters(mp_bits(m)), pgen_test, &r);
	332	if (!p \|\| MP_CMP(p, !=, q)) {
	333	fputs("\n*** pgen failed", stderr);
0f5ec153	334	fputs("\nm = ", stderr); mp_writefile(m, stderr, 10);
581c854e	335	fputs("\np = ", stderr); mp_writefile(p, stderr, 10);
581c854e	336	fputs("\nq = ", stderr); mp_writefile(q, stderr, 10);
0f5ec153	337	fputc('\n', stderr);
	338	ok = 0;
	339	}
	340
	341	mp_drop(m);
581c854e	342	mp_drop(q);
	343	if (p)
	344	mp_drop(p);
d94f85ac	345	assert(mparena_count(MPARENA_GLOBAL) == 0);
0f5ec153	346	return (ok);
	347	}
	348
	349	static test_chunk tests[] = {
	350	{ "pgen", verify, { &type_mp, &type_mp, 0 } },
	351	{ 0, 0, { 0 } }
	352	};
	353
	354	int main(int argc, char *argv[])
	355	{
	356	sub_init();
	357	test_run(argc, argv, tests, SRCDIR "/tests/pgen");
	358	return (0);
	359	}
0f5ec153	360	#endif
	361
	362	/----- That's all, folks -------------------------------------------------/