X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/b817bfc642225b8c3c0b6a7e42d1fb949b61a606..fe6657c961b01ec72e9f35f4c3d96b11b31cf09c:/mpreduce.c

diff --git a/mpreduce.c b/mpreduce.c
index 7d31334..bc41f60 100644
--- a/mpreduce.c
+++ b/mpreduce.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: mpreduce.c,v 1.2 2004/04/08 01:36:15 mdw Exp $
+ * $Id$
  *
  * Efficient reduction modulo nice primes
  *
@@ -47,12 +47,12 @@ DA_DECL(instr_v, mpreduce_instr);
  * Arguments:	@gfreduce *r@ = structure to fill in
  *		@mp *x@ = an integer
  *
- * Returns:	---
+ * Returns:	Zero if successful; nonzero on failure.
  *
  * Use:		Initializes a context structure for reduction.
  */
 
-void mpreduce_create(mpreduce *r, mp *p)
+int mpreduce_create(mpreduce *r, mp *p)
 {
   mpscan sc;
   enum { Z = 0, Z1 = 2, X = 4, X0 = 6 };
@@ -60,11 +60,12 @@ void mpreduce_create(mpreduce *r, mp *p)
   instr_v iv = DA_INIT;
   unsigned long d, i;
   unsigned op;
-  size_t w, b;
+  size_t w, b, bb;
 
   /* --- Fill in the easy stuff --- */
 
-  assert(MP_ISPOS(p));
+  if (!MP_POSP(p))
+    return (-1);
   d = mp_bits(p);
   r->lim = d/MPW_BITS;
   r->s = d%MPW_BITS;
@@ -100,10 +101,12 @@ void mpreduce_create(mpreduce *r, mp *p)
       case X0 | 0: st =  Z; printf("+ %lu\n", i - 1); break;
     }
   }
-  if (st >= X) printf("+ %lu\n", i);
+  if (st >= X) printf("+ %lu\n", i - 1);
+  st = Z;
 #endif
 
-  for (i = 0, mp_scan(&sc, p); i < d  - 1 && mp_step(&sc); i++) {
+  bb = MPW_BITS - (d + 1)%MPW_BITS;
+  for (i = 0, mp_scan(&sc, p); i < d && mp_step(&sc); i++) {
     switch (st | mp_bit(&sc)) {
       case  Z | 1: st = Z1; break;
       case Z1 | 0: st =  Z; op = MPRI_SUB; goto instr;
@@ -113,14 +116,14 @@ void mpreduce_create(mpreduce *r, mp *p)
       case X0 | 0: st =  Z; op = MPRI_SUB; goto instr;
       instr:
 	w = (d - i)/MPW_BITS + 1;
-	b = (MPW_BITS + i - d - 1)%MPW_BITS;
+	b = (bb + i)%MPW_BITS;
 	INSTR(op | !!b, w, b);
     }
   }
-  if ((DA(&iv)[DA_LEN(&iv) - 1].op & ~1u) == MPRI_SUB) {
-    fprintf(stderr,
-	    "mpreduce can't handle moduli of the form 2^m + x\n");
-    abort();
+  if (DA_LEN(&iv) && (DA(&iv)[DA_LEN(&iv) - 1].op & ~1u) == MPRI_SUB) {
+    mp_drop(r->p);
+    DA_DESTROY(&iv);
+    return (-1);
   }
 
 #undef INSTR
@@ -128,7 +131,9 @@ void mpreduce_create(mpreduce *r, mp *p)
   /* --- Wrap up --- */
 
   r->in = DA_LEN(&iv);
-  if (!r->s) {
+  if (!r->in)
+    r->iv = 0;
+  else if (!r->s) {
     r->iv = xmalloc(r->in * sizeof(mpreduce_instr));
     memcpy(r->iv, DA(&iv), r->in * sizeof(mpreduce_instr));
   } else {
@@ -149,7 +154,12 @@ void mpreduce_create(mpreduce *r, mp *p)
       r->iv[i + r->in].argy = b;
     }
   }
-  DA_DESTROY(&iv);  
+  DA_DESTROY(&iv);
+
+#ifdef DEBUG
+  mpreduce_dump(r, stdout);
+#endif
+  return (0);
 }
 
 /* --- @mpreduce_destroy@ --- *
@@ -164,7 +174,7 @@ void mpreduce_create(mpreduce *r, mp *p)
 void mpreduce_destroy(mpreduce *r)
 {
   mp_drop(r->p);
-  xfree(r->iv);
+  if (r->iv) xfree(r->iv);
 }
 
 /* --- @mpreduce_dump@ --- *
@@ -253,7 +263,7 @@ mp *mpreduce_do(mpreduce *r, mp *d, mp *x)
 
   /* --- If source is negative, divide --- */
 
-  if (MP_ISNEG(x)) {
+  if (MP_NEGP(x)) {
     mp_div(0, &d, x, r->p);
     return (d);
   }
@@ -283,9 +293,9 @@ mp *mpreduce_do(mpreduce *r, mp *d, mp *x)
 	*vl = 0;
 	run(r->iv, il, vl, z);
 #ifdef DEBUG
-  MP_PRINTX("x", x);
-  mp_div(0, &_rr, x, r->p);
-  assert(MP_EQ(_r, _rr));
+	MP_PRINTX("x", x);
+	mp_div(0, &_rr, x, r->p);
+	assert(MP_EQ(_r, _rr));
 #endif
       }
     }
@@ -295,9 +305,9 @@ mp *mpreduce_do(mpreduce *r, mp *d, mp *x)
 	*vl &= ((1 << r->s) - 1);
 	run(r->iv + r->in, il + r->in, vl, z);
 #ifdef DEBUG
-  MP_PRINTX("x", x);
-  mp_div(0, &_rr, x, r->p);
-  assert(MP_EQ(_r, _rr));
+	MP_PRINTX("x", x);
+	mp_div(0, &_rr, x, r->p);
+	assert(MP_EQ(_r, _rr));
 #endif
       }
     }
@@ -335,12 +345,18 @@ mp *mpreduce_exp(mpreduce *mr, mp *d, mp *a, mp *e)
   mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW;
 
   MP_SHRINK(e);
-  if (!MP_LEN(e))
+  MP_COPY(a);
+  if (MP_ZEROP(e))
     ;
-  else if (MP_LEN(e) < EXP_THRESH)
-    EXP_SIMPLE(x, a, e);
-  else
-    EXP_WINDOW(x, a, e);
+  else {
+    if (MP_NEGP(e))
+      a = mp_modinv(a, a, mr->p);
+    if (MP_LEN(e) < EXP_THRESH)
+      EXP_SIMPLE(x, a, e);
+    else
+      EXP_WINDOW(x, a, e);
+  }
+  mp_drop(a);
   mp_drop(d);
   mp_drop(spare);
   return (x);