git.distorted.org.uk Git - u/mdw/catacomb/blob - pgen.c

   1 /* -*-c-*-
   2  *
   3  * $Id: pgen.c,v 1.4 1999/12/22 16:01:11 mdw Exp $
   4  *
   5  * Prime generation glue
   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 $
  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.
  36  *
  37  */
  38
  39 /*----- Header files ------------------------------------------------------*/
  40
  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"
  48 #include "mp.h"
  49 #include "mprand.h"
  50 #include "pgen.h"
  51 #include "pfilt.h"
  52 #include "rabin.h"
  53
  54 /*----- Standard prime filter ---------------------------------------------*/
  55
  56 /* --- @pgen_filter@ --- */
  57
  58 int pgen_filter(int rq, pgen_event *ev, void *p)
  59 {
  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);
  72       else
  73         rc = pfilt_step(&f->f, f->step);
  74       break;
  75     case PGEN_DONE:
  76       pfilt_destroy(&f->f);
  77       return (PGEN_DONE);
  78   }
  79
  80   while (rc == PGEN_FAIL)
  81     rc = pfilt_step(&f->f, f->step);
  82   ev->m = MP_COPY(f->f.m);
  83   return (rc);
  84 }
  85
  86 /* --- @pgen_jump@ --- *
  87  *
  88  * Similar to the standard @pgen_filter@, but jumps in large steps rather
  89  * than small ones.
  90  */
  91
  92 int pgen_jump(int rq, pgen_event *ev, void *p)
  93 {
  94   pgen_jumpctx *f = p;
  95   int rc = PGEN_ABORT;
  96
  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 }
 116
 117 /*----- Standard prime test -----------------------------------------------*/
 118
 119 /* --- @pgen_test@ --- */
 120
 121 int pgen_test(int rq, pgen_event *ev, void *p)
 122 {
 123   rabin *r = p;
 124   int rc = PGEN_ABORT;
 125
 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;
 140   }
 141
 142   return (rc);
 143 }
 144
 145 /*----- The main driver ---------------------------------------------------*/
 146
 147 /* --- @pgen@ --- *
 148  *
 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
 160  *
 161  * Returns:     Pointer to final result, or null.
 162  *
 163  * Use:         A generalized prime-number search skeleton.  Yes, that's a
 164  *              scary number of arguments.
 165  */
 166
 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)
 170 {
 171   pgen_event ev;
 172   int rq, rc;
 173   pgen_proc *proc;
 174   void *ctx;
 175
 176   /* --- Set up the initial event block --- */
 177
 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);
 186
 187   /* --- Tell the event handler we're under way --- */
 188
 189   if (event && event(PGEN_BEGIN, &ev, ectx) == PGEN_ABORT)
 190     return (0);
 191
 192   /* --- Set up for the initial call --- */
 193
 194   proc = step; ctx = sctx; rq = PGEN_BEGIN;
 195
 196   /* --- Enter the great maelstrom of state transitions --- */
 197
 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     }
 256
 257     /* --- If decrementing counters is requested, do that --- */
 258
 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     }
 267
 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       }
 274     }
 275
 276     /* --- Report an event if so directed --- */
 277
 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     }
 286
 287     /* --- Close down tester and stepper functions --- */
 288
 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);
 311 }
 312
 313 /*----- Test rig ----------------------------------------------------------*/
 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;
 322   mp *q = *(mp **)v[1].buf;
 323   mp *p;
 324   int ok = 1;
 325
 326   pgen_filterctx pf;
 327   rabin r;
 328
 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);
 334     fputs("\nm = ", stderr); mp_writefile(m, stderr, 10);
 335     fputs("\np = ", stderr); mp_writefile(p, stderr, 10);
 336     fputs("\nq = ", stderr); mp_writefile(q, stderr, 10);
 337     fputc('\n', stderr);
 338     ok = 0;
 339   }
 340
 341   mp_drop(m);
 342   mp_drop(q);
 343   if (p)
 344     mp_drop(p);
 345   assert(mparena_count(MPARENA_GLOBAL) == 0);
 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 }
 360 #endif
 361
 362 /*----- That's all, folks -------------------------------------------------*/