math/gfreduce.[ch]: Fix out-of-bounds memory access.

The final pass of the reduction adds a multiple of the extra top bits
from the most significant word; but at this point, the generated
instruction sequence will access a word one beyond the bottom of the
supplied memory vector.  While it (probably) won't modify this word, it
will still attempt to read and write it.

This is relatively harmless, since typically the vector will have been
allocated from our custom arena, and therefore there'll be a header word
in this position, but hand-built polynomials may cause trouble.

Fix this bug by keeping track of the first instruction which accesses a
word other than the least significant, and using this alternative entry
point in the final pass.  Fortunately, there's an unused slot in the
context structure which we can use for this purpose!

(Yes, the previous refactoring was largely for the purpose of fixing
this bug.)

diff --git a/math/gfreduce.c b/math/gfreduce.c
index 96e0ced..45591dd 100644 (file)
--- a/math/gfreduce.c
+++ b/math/gfreduce.c
@@ -79,9 +79,12 @@ struct gen {
   unsigned f;                          /* Flags */
 #define f_lsr 1u                       /*   Overflow from previous word */
 #define f_load 2u                      /*   Outstanding @LOAD@ */
   unsigned f;                          /* Flags */
 #define f_lsr 1u                       /*   Overflow from previous word */
 #define f_load 2u                      /*   Outstanding @LOAD@ */

+#define f_fip 4u                       /*   Final-pass offset is set */

   instr_v iv;                          /* Instruction vector */
   instr_v iv;                          /* Instruction vector */

+  size_t fip;                          /* Offset for final-pass reduction */

   size_t w;                            /* Currently loaded target word */
   size_t wi;                           /* Left-shifts for current word */
   size_t w;                            /* Currently loaded target word */
   size_t wi;                           /* Left-shifts for current word */

+  gfreduce *r;                         /* Reduction context pointer */

 };
 
 #define INSTR(g_, op_, arg_) do {                                      \
 };
 
 #define INSTR(g_, op_, arg_) do {                                      \


@@ -97,6 +100,24 @@ struct gen {
 
 static void emit_load(struct gen *g, size_t w)
 {
 
 static void emit_load(struct gen *g, size_t w)
 {

+  /* --- If this is not the low-order word then note final-pass start --- *
+   *
+   * Once we've eliminated the whole high-degree words, there will possibly
+   * remain a few high-degree bits.  We can further reduce the subject
+   * polynomial by subtracting an appropriate multiple of %$p'$%, but if we
+   * do this naively we'll end up addressing `low-order' words beyond the
+   * bottom of our input.  We solve this problem by storing an alternative
+   * start position for this final pass (which works because we scan bits
+   * right-to-left).
+   */
+
+  if (!(g->f & f_fip) && w < g->r->lim) {
+    g->fip = DA_LEN(&g->iv);
+    g->f |= f_fip;
+  }
+
+  /* --- Actually emit the instruction --- */
+

   INSTR(g, GFRI_LOAD, w);
   g->f |= f_load;
   g->w = w;
   INSTR(g, GFRI_LOAD, w);
   g->f |= f_load;
   g->w = w;


@@ -160,6 +181,7 @@ void gfreduce_create(gfreduce *r, mp *p)
 
   /* --- Sort out the easy stuff --- */
 
 
   /* --- Sort out the easy stuff --- */
 

+  g.r = r;

   d = mp_bits(p); assert(d); d--;
   r->lim = d/MPW_BITS;
   dw = d%MPW_BITS;
   d = mp_bits(p); assert(d); d--;
   r->lim = d/MPW_BITS;
   dw = d%MPW_BITS;


@@ -234,9 +256,20 @@ void gfreduce_create(gfreduce *r, mp *p)
     INSTR(&g, GFRI_STORE, g.w);
   }
 
     INSTR(&g, GFRI_STORE, g.w);
   }
 

+  /* --- Copy the instruction vector.
+   *
+   * If we've not set a final-pass offset yet then now would be an excellent
+   * time.  Obviously it should be right at the end, because there's nothing
+   * for a final pass to do.
+   */
+

   r->in = DA_LEN(&g.iv);
   r->iv = xmalloc(r->in * sizeof(gfreduce_instr));
   memcpy(r->iv, DA(&g.iv), r->in * sizeof(gfreduce_instr));
   r->in = DA_LEN(&g.iv);
   r->iv = xmalloc(r->in * sizeof(gfreduce_instr));
   memcpy(r->iv, DA(&g.iv), r->in * sizeof(gfreduce_instr));

+
+  if (!(g.f & f_fip)) g.fip = DA_LEN(&g.iv);
+  r->fiv = r->iv + g.fip;
+

   DA_DESTROY(&g.iv);
 }
 
   DA_DESTROY(&g.iv);
 }
 


@@ -244,6 +277,7 @@ void gfreduce_create(gfreduce *r, mp *p)
 
 #undef f_lsr
 #undef f_load
 
 #undef f_lsr
 #undef f_load

+#undef f_fip

 
 /* --- @gfreduce_destroy@ --- *
  *
 
 /* --- @gfreduce_destroy@ --- *
  *


@@ -279,11 +313,15 @@ void gfreduce_dump(gfreduce *r, FILE *fp)
          (unsigned long)r->lim, (unsigned long)r->mask);
   for (i = 0; i < r->in; i++) {
     static const char *opname[] = { "load", "lsl", "lsr", "store" };
          (unsigned long)r->lim, (unsigned long)r->mask);
   for (i = 0; i < r->in; i++) {
     static const char *opname[] = { "load", "lsl", "lsr", "store" };

+    if (&r->iv[i] == r->fiv)
+      fputs("final:\n", fp);

     assert(r->iv[i].op < N(opname));
     fprintf(fp, "  %s %lu\n",
            opname[r->iv[i].op],
            (unsigned long)r->iv[i].arg);
   }
     assert(r->iv[i].op < N(opname));
     fprintf(fp, "  %s %lu\n",
            opname[r->iv[i].op],
            (unsigned long)r->iv[i].arg);
   }

+  if (&r->iv[i] == r->fiv)
+    fputs("final:\n", fp);

 }
 
 /* --- @gfreduce_do@ --- *
 }
 
 /* --- @gfreduce_do@ --- *


@@ -340,7 +378,7 @@ mp *gfreduce_do(gfreduce *r, mp *d, mp *x)
       while (*vl & r->mask) {
        z = *vl & r->mask;
        *vl &= ~r->mask;
       while (*vl & r->mask) {
        z = *vl & r->mask;
        *vl &= ~r->mask;

-       run(r->iv, il, vl, z);
+       run(r->fiv, il, vl, z);

       }
     }
   }
       }
     }
   }

diff --git a/math/gfreduce.h b/math/gfreduce.h
index b60c8fa..9f69585 100644 (file)
--- a/math/gfreduce.h
+++ b/math/gfreduce.h
@@ -60,7 +60,8 @@ typedef struct gfreduce {
   mpw mask;                            /* Mask for degree word */
   mp *p;                               /* Copy of the polynomial */
   size_t in;                           /* Number of instruction words */
   mpw mask;                            /* Mask for degree word */
   mp *p;                               /* Copy of the polynomial */
   size_t in;                           /* Number of instruction words */

-  gfreduce_instr *iv, *liv;            /* Vector of instructions */
+  gfreduce_instr *iv;                  /* Vector of instructions */
+  gfreduce_instr *fiv;                 /* Final-pass instruction suffix */

 } gfreduce;
 
 /*----- Functions provided ------------------------------------------------*/
 } gfreduce;
 
 /*----- Functions provided ------------------------------------------------*/

diff --git a/math/t/gfreduce b/math/t/gfreduce
index ecece92..ab6291a 100644 (file)
--- a/math/t/gfreduce
+++ b/math/t/gfreduce
@@ -19,6 +19,59 @@ reduce {
   0x20000000000000000000000000000000000000004000000000000000001
     0x110414154054140445011511541540514401111414505115044104145451505001151441450000541004550554154040500000411050400055041
     0x1bf878a39fbee9cf20a2f6f41eadda756518f1669b2c7d8f9234965b6b3;
   0x20000000000000000000000000000000000000004000000000000000001
     0x110414154054140445011511541540514401111414505115044104145451505001151441450000541004550554154040500000411050400055041
     0x1bf878a39fbee9cf20a2f6f41eadda756518f1669b2c7d8f9234965b6b3;

+
+  # --- Some randomized tests ---
+
+  0x8000000000000000 0x1053e80c002df41fe6b0362 0x4002df41fe6b0362;
+  0x8000000000000000 0x8988a38f375ecdf7dc69fb79 0x375ecdf7dc69fb79;
+  0x8000000000000000 0x9c2c4431aa69d5b2fc67a432 0x2a69d5b2fc67a432;
+  0x8000000000000000 0x5cd61819c2ce11ff5edf5010 0x42ce11ff5edf5010;
+  0x8000000000000000 0xc3b542762081f9ad85ef454c 0x2081f9ad85ef454c;
+  0x8000000000000000 0x4b7afa54a524a75e619c7d75 0x2524a75e619c7d75;
+  0x8000000000000000 0x2aa3ec8bbd8d3c54d9d8743c 0x3d8d3c54d9d8743c;
+  0x8000000000000000 0xc43d78723951e2e3bb2320f8 0x3951e2e3bb2320f8;
+
+  0x8000000000000001 0xf2b637dd4b236c3c82c307cd 0x4b236c3d67af6877;
+  0x8000000000000001 0xb6b4472822f7938380ef4ae7 0x22f79382ed87c4b7;
+  0x8000000000000001 0x8325aacc0aa94e489805a261 0xaa94e499e4ef7f9;
+  0x8000000000000001 0xa9a1e52b51d3bdfe17121e97 0x51d3bdff4451d4c1;
+  0x8000000000000001 0x23f79afedb882fe867fe217a 0x5b882fe820111487;
+  0x8000000000000001 0xb14c1917425430945b851a07 0x42543095391d2829;
+  0x8000000000000001 0xcd66f07ce64acb56b8a5e6d9 0x664acb5722680620;
+  0x8000000000000001 0x3aff3bbc3a68db8eb78ccd2c 0x3a68db8ec272ba54;
+
+  0x788bb9913c202db 0xdae682a9d44ccaf8961e6d70 0xb4f429af6b42d9;
+  0xdb31e7bcb59249e 0xc721aacf0c8c0924d0c71c1f 0x4c098e94efcdff3;
+  0x64849830bf2edc64 0x4e53a42e9a5db6f4589222c3 0x21746a64956f27d3;
+  0x3d0c6311af50234 0x28060553212fb75c63bd1b37 0x1c180e845f9eeb;
+  0x3fa21cc125ba9dc3 0x4a1f7351962c7ea1e13913bd 0x1d0b916b8653e959;
+  0xb8ed0bc2a356bb2a 0x82f8a7aa2d5d627808ccd318 0x4f860208c89b6810;
+  0x874421067d7e18ce 0x12a96980346a4ec9d63a6ed6 0xbd6ab5dedb4f198;
+  0x112351ba108debb4 0xb16dd89e0be5854390bca556 0xeb7f9a731006a12;
+  0xdc377451028c0b36 0xbc10689c07a0a58889311e64 0x9c9a4f6d04d469a;
+  0xc5a35ba806bbd020 0x55d4006788dcea573bd68917 0x41833c4fda163bb7;
+  0x155496cfddfc17a 0x5192caf13d7bc577a2a99a85 0x1907b684ea1887;
+  0x1f219e5fc63e4b3 0xb2cd7b1451e88b1cd00178fa 0x80aff284f49f01;
+  0x379065bfb08efca5 0x27b6c5bbfc67dcf9ad7a11b7 0xe93af61c7b85801;
+  0x819e1387819a26b 0x70f45f72bdbaa8e1506f18e3 0x67f64ac9afeae07;
+  0xfa1cd3ca5f9c522b 0x8ff38bb5a723bcfb47cd95b7 0x465b9a116273658;
+  0x355eaf2dc02cad7c 0xa1b872689bf1a4be64943fb0 0xa2b4230ace983b8;
+  0x1cab10c75272d1cb 0x4d136f699bfd2a522aea313f 0xe55a379963cad23;
+  0xafa255df350035f3 0x5be0694600777ed13e451fb2 0x5d88a4df4e905304;
+  0xe19e06e81ebdd297 0x6cc418e1ff14727eeee081c6 0x5210e67e1ad0991;
+  0xb7425b2c5d818f53 0x3c8961ad01d592f12c2ce614 0x4fa4779ada95654a;
+  0xe62d043eaef81ee7 0x18a4dca5f6400fb1449fd9ff 0x1aca3d5de57cde99;
+  0xd2c2d1e2c0c7a792 0x31004ca4536e34b6ebf6f57c 0x59bb10d3427ce3e;
+  0x8aba5ba8e2a698ae 0x956450deee45f8d1d98671fc 0x1b2a841625705e1e;
+  0x66148a4fedc06808 0x21891c1e1b8c5a7c7d28ba4d 0x33ccd0ee20a4e525;
+  0xcef2153f6e0c6024 0xd88db076e6eaf444dee7832a 0x7d8ef4fedae03a2a;
+  0xd8c542c228374b1b 0x6b6ee7f636f6854e2b9cd961 0xaeeff6053c02317;
+  0x4e64f6a86b57044f 0x7250da4089e2fec345bc6d5f 0x6a194ad03c08c31;
+  0xc0e088778e03e46 0xb870e803a983c4b89e878cb2 0x3b089eeb4d989f8;
+  0xc64c07833520a47b 0x8e2ad857329dab69faa94aa0 0x5e1dbf6d86801a8b;
+  0x89c585e342019d99 0x1ea855935fd5e6ead876af4e 0x720b1de7af48d59e;
+  0x6e76875b22338dd5 0xfe211090944db98481ee5cfc 0x3a19861807cefb5b;
+  0x44478351598d8ff8 0x878f198f78e130a6807a3af1 0x3850ab7a8e9c67b1;

 }
 
 modexp {
 }
 
 modexp {