From a951033da37da66f31d13d4825c562bf7762e213 Mon Sep 17 00:00:00 2001
From: mdw <mdw>
Date: Sat, 16 Jun 2001 13:22:40 +0000
Subject: [PATCH] Added fast-track code for binary output bases, and tests.

---
 mptext.c     | 241 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 tests/mptext |  14 +++-
 2 files changed, 242 insertions(+), 13 deletions(-)

diff --git a/mptext.c b/mptext.c
index 55ef579..57521da 100644
--- a/mptext.c
+++ b/mptext.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: mptext.c,v 1.9 2001/02/03 16:05:17 mdw Exp $
+ * $Id: mptext.c,v 1.10 2001/06/16 13:22:39 mdw Exp $
  *
  * Textual representation of multiprecision numbers
  *
@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------* 
  *
  * $Log: mptext.c,v $
+ * Revision 1.10  2001/06/16 13:22:39  mdw
+ * Added fast-track code for binary output bases, and tests.
+ *
  * Revision 1.9  2001/02/03 16:05:17  mdw
  * Make flags be unsigned.  Improve the write algorithm: recurse until the
  * parts are one word long and use single-precision arithmetic from there.
@@ -154,6 +157,7 @@ mp *mp_read(mp *m, int radix, const mptext_ops *ops, void *p)
 
 #define f_neg 1u
 #define f_ok 2u
+#define f_start 4u
 
   /* --- Initialize the stacks --- */
 
@@ -207,10 +211,119 @@ mp *mp_read(mp *m, int radix, const mptext_ops *ops, void *p)
     r = -1;
   }
 
+  /* --- Use fast algorithm for binary radix --- *
+   *
+   * This is the restart point after having parsed a radix number from the
+   * input.  We check whether the radix is binary, and if so use a fast
+   * algorithm which just stacks the bits up in the right order.
+   */
+
+restart:
+  switch (rd) {
+    unsigned bit;
+
+    case   2: bit = 1; goto bin;
+    case   4: bit = 2; goto bin;
+    case   8: bit = 3; goto bin;
+    case  16: bit = 4; goto bin;
+    case  32: bit = 5; goto bin;
+    case  64: bit = 6; goto bin;
+    case 128: bit = 7; goto bin;
+    default:
+      break;
+
+  /* --- The fast binary algorithm --- *
+   *
+   * We stack bits up starting at the top end of a word.  When one word is
+   * full, we write it to the integer, and start another with the left-over
+   * bits.  When the array in the integer is full, we resize using low-level
+   * calls and copy the current data to the top end.  Finally, we do a single
+   * bit-shift when we know where the end of the number is.
+   */
+
+  bin: {
+    mpw a = 0;
+    unsigned b = MPW_BITS;
+    size_t len, n;
+    mpw *v;
+
+    m = mp_dest(MP_NEW, 1, nf);
+    len = n = m->sz;
+    n = len;
+    v = m->v + n;
+    for (;; ch = ops->get(p)) {
+      unsigned x;
+
+      if (ch < 0)
+	break;
+
+      /* --- Check that the character is a digit and in range --- */
+
+      if (radix < 0)
+	x = ch % rd;
+      else {
+	if (!isalnum(ch))
+	  break;
+	if (ch >= '0' && ch <= '9')
+	  x = ch - '0';
+	else {
+	  ch = tolower(ch);
+	  if (ch >= 'a' && ch <= 'z')	/* ASCII dependent! */
+	    x = ch - 'a' + 10;
+	  else
+	    break;
+	}
+      }
+      if (x >= rd)
+	break;
+
+      /* --- Feed the digit into the accumulator --- */
+
+      f |= f_ok;
+      if (!x && !(f & f_start))
+	continue;
+      f |= f_start;
+      if (b > bit) {
+	b -= bit;
+	a |= MPW(x) << b;
+      } else {
+	a |= MPW(x) >> (bit - b);
+    	b += MPW_BITS - bit;
+	*--v = MPW(a);
+	n--;
+	if (!n) {
+	  n = len;
+	  len <<= 1;
+	  v = mpalloc(m->a, len);
+	  memcpy(v + n, m->v, MPWS(n));
+	  mpfree(m->a, m->v);
+	  m->v = v;
+	  v = m->v + n;
+	}
+	a = (b < MPW_BITS) ? MPW(x) << b : 0;
+      }
+    }
+
+    /* --- Finish up --- */
+
+    if (!(f & f_ok)) {
+      mp_drop(m);
+      m = 0;
+    } else {
+      *--v = MPW(a);
+      n--;
+      m->sz = len;
+      m->vl = m->v + len;
+      m->f &= ~MP_UNDEF;
+      m = mp_lsr(m, m, (unsigned long)n * MPW_BITS + b);
+    }
+    goto done;
+  }}
+
   /* --- Time to start --- */
 
   for (;; ch = ops->get(p)) {
-    int x;
+    unsigned x;
 
     if (ch < 0)
       break;
@@ -234,7 +347,8 @@ mp *mp_read(mp *m, int radix, const mptext_ops *ops, void *p)
       rd = r;
       r = -1;
       f &= ~f_ok;
-      continue;
+      ch = ops->get(p);
+      goto restart;
     }
 
     /* --- Check that the character is a digit and in range --- */
@@ -348,6 +462,7 @@ mp *mp_read(mp *m, int radix, const mptext_ops *ops, void *p)
 
   /* --- Bail out if the number was bad --- */
 
+done:
   if (!(f & f_ok))    
     return (0);
 
@@ -357,6 +472,7 @@ mp *mp_read(mp *m, int radix, const mptext_ops *ops, void *p)
     m->f |= MP_NEG;
   return (m);
 
+#undef f_start
 #undef f_neg
 #undef f_ok
 }
@@ -410,13 +526,14 @@ static int simple(mpw n, int radix, unsigned z,
   if (n)
     rc = simple(n, radix, z, ops, p);
   else {
-    static const char zero[32] = "00000000000000000000000000000000";
-    while (!rc && z >= sizeof(zero)) {
-      rc = ops->put(zero, sizeof(zero), p);
-      z -= sizeof(zero);
+    char zbuf[32];
+    memset(zbuf, (radix < 0) ? 0 : '0', sizeof(zbuf));
+    while (!rc && z >= sizeof(zbuf)) {
+      rc = ops->put(zbuf, sizeof(zbuf), p);
+      z -= sizeof(zbuf);
     }
     if (!rc && z)
-      rc = ops->put(zero, z, p);
+      rc = ops->put(zbuf, z, p);
   }
   if (!rc)
     rc = ops->put(buf + i, sizeof(buf) - i, p);
@@ -459,6 +576,94 @@ static int complicated(mp *m, int radix, mp **pr, unsigned i, unsigned z,
   return (rc);
 }
 
+/* --- Binary case --- *
+ *
+ * Special case for binary output.  Goes much faster.
+ */
+
+static int binary(mp *m, int bit, int radix, const mptext_ops *ops, void *p)
+{
+  mpw *v;
+  mpw a;
+  int rc = 0;
+  unsigned b;
+  unsigned mask;
+  unsigned long n;
+  unsigned f = 0;
+  char buf[8], *q;
+  unsigned x;
+  int ch;
+
+#define f_out 1u
+
+  /* --- Work out where to start --- */
+
+  n = mp_bits(m);
+  n += bit - (n % bit);
+  b = n % MPW_BITS;
+  n /= MPW_BITS;
+  
+  if (n > MP_LEN(m)) {
+    n--;
+    b += MPW_BITS;
+  }
+
+  v = m->v + n;
+  a = *v;
+  mask = (1 << bit) - 1;
+  q = buf;
+
+  /* --- Main code --- */
+
+  for (;;) {
+    if (b > bit) {
+      b -= bit;
+      x = a >> b;
+    } else {
+      x = a << (bit - b);
+      b += MPW_BITS - bit;
+      if (v == m->v)
+	break;
+      a = *--v;
+      if (b < MPW_BITS)
+	x |= a >> b;
+    }
+    x &= mask;
+    if (!x && !(f & f_out))
+      continue;
+
+    if (radix < 0)
+      ch = x;
+    else if (x < 10)
+      ch = '0' + x;
+    else
+      ch = 'a' + x - 10;
+    *q++ = ch;
+    if (q >= buf + sizeof(buf)) {
+      if ((rc = ops->put(buf, sizeof(buf), p)) != 0)
+	goto done;
+      q = buf;
+    }
+    f |= f_out;
+  }
+
+  x &= mask;
+  if (radix < 0)
+    ch = x;
+  else if (x < 10)
+    ch = '0' + x;
+  else
+    ch = 'a' + x - 10;
+  *q++ = ch;
+  rc = ops->put(buf, q - buf, p);
+
+done:
+  mp_drop(m);
+  return (rc);
+
+#undef f_out
+}
+
 /* --- Main driver code --- */
 
 int mp_write(mp *m, int radix, const mptext_ops *ops, void *p)
@@ -487,6 +692,18 @@ int mp_write(mp *m, int radix, const mptext_ops *ops, void *p)
     m->f &= ~MP_NEG;
   }
 
+  /* --- Handle binary radix --- */
+
+  switch (radix) {
+    case   2: case   -2: return (binary(m, 1, radix, ops, p));
+    case   4: case   -4: return (binary(m, 2, radix, ops, p));
+    case   8: case   -8: return (binary(m, 3, radix, ops, p));
+    case  16: case  -16: return (binary(m, 4, radix, ops, p));
+    case  32: case  -32: return (binary(m, 5, radix, ops, p));
+              case  -64: return (binary(m, 6, radix, ops, p));
+              case -128: return (binary(m, 7, radix, ops, p));
+  }
+
   /* --- If the number is small, do it the easy way --- */
 
   if (MP_LEN(m) < 2)
@@ -550,7 +767,7 @@ static int verify(dstr *v)
   if (m) {
     if (!ob) {
       fprintf(stderr, "*** unexpected successful parse\n"
-	              "*** input [%i] = ", ib);
+	              "*** input [%2i] =     ", ib);
       if (ib < 0)
 	type_hex.dump(&v[1], stderr);
       else
@@ -562,17 +779,17 @@ static int verify(dstr *v)
       mp_writedstr(m, &d, ob);
       if (d.len != v[3].len || memcmp(d.buf, v[3].buf, d.len) != 0) {
 	fprintf(stderr, "*** failed read or write\n"
-		        "*** input [%i]    = ", ib);
+		        "*** input [%2i]      = ", ib);
 	if (ib < 0)
 	  type_hex.dump(&v[1], stderr);
 	else
 	  fputs(v[1].buf, stderr);
-	fprintf(stderr, "\n*** output [%i]   = ", ob);
+	fprintf(stderr, "\n*** output [%2i]     = ", ob);
 	if (ob < 0)
 	  type_hex.dump(&d, stderr);
 	else
 	  fputs(d.buf, stderr);
-	fprintf(stderr, "\n*** expected [%i]   = ", ob);
+	fprintf(stderr, "\n*** expected [%2i]   = ", ob);
 	if (ob < 0)
 	  type_hex.dump(&v[3], stderr);
 	else
diff --git a/tests/mptext b/tests/mptext
index 6da5aeb..1d9168a 100644
--- a/tests/mptext
+++ b/tests/mptext
@@ -1,6 +1,6 @@
 # Test vectors for MP textual I/O
 #
-# $Id: mptext,v 1.6 2001/02/03 16:10:27 mdw Exp $
+# $Id: mptext,v 1.7 2001/06/16 13:22:40 mdw Exp $
 
 mptext-ascii {
   # --- Perfectly valid things ---
@@ -10,10 +10,12 @@ mptext-ascii {
   10 52					10 52;
   10 654365464655464577673765769678	10 654365464655464577673765769678;
   10 654365464655464577673765769678	16 8425e6d06f272b9a2d73ed1ce;
+  10 596569802840985608098409867	8 366570443501403714657464766613;
   16 8425E6D06F272B9A2D73ED1CE		10 654365464655464577673765769678;
   0 654365464655464577673765769678	16 8425e6d06f272b9a2d73ed1ce;
   0 16_8425E6D06F272B9A2D73ED1CE	10 654365464655464577673765769678;
   0 -0x8425E6D06F272B9A2D73ED1CE	10 -654365464655464577673765769678;
+  0 -8_366570443501403714657464766613	10 -596569802840985608098409867;
   8 -366570443501403714657464766613	10 -596569802840985608098409867;
   0 0366570443501403714657464766613	10 596569802840985608098409867;
 
@@ -26,6 +28,16 @@ mptext-ascii {
   0 37_ 10 37;			# 37 is an invalid base, so stop at `_'
   0 36_ 0 0;			# 36 is a valid base, so restart and fail
 
+  # --- Word-boundary tests for binary-radix translation ---
+
+  8 1234567012				8 1234567012;
+  8 12345670123				8 12345670123;
+  8 123456701234			8 123456701234;
+
+  16 1234567				16 1234567;
+  16 12345678				16 12345678;
+  16 123456789				16 123456789;
+
   # --- Bugs ---
 
   16 84d192cd06ae59691897fa409da6198d5269325d
-- 
2.11.0