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

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