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

   1 /* -*-c-*-
   2  *
   3  * $Id: mptext.c,v 1.4 1999/12/22 15:56:56 mdw Exp $
   4  *
   5  * Textual representation of multiprecision numbers
   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: mptext.c,v $
  33  * Revision 1.4  1999/12/22 15:56:56  mdw
  34  * Use clever recursive algorithm for writing numbers out.
  35  *
  36  * Revision 1.3  1999/12/10 23:23:26  mdw
  37  * Allocate slightly less memory.
  38  *
  39  * Revision 1.2  1999/11/20 22:24:15  mdw
  40  * Use function versions of MPX_UMULN and MPX_UADDN.
  41  *
  42  * Revision 1.1  1999/11/17 18:02:16  mdw
  43  * New multiprecision integer arithmetic suite.
  44  *
  45  */
  46
  47 /*----- Header files ------------------------------------------------------*/
  48
  49 #include <ctype.h>
  50 #include <stdio.h>
  51
  52 #include "mp.h"
  53 #include "mptext.h"
  54 #include "paranoia.h"
  55
  56 /*----- Main code ---------------------------------------------------------*/
  57
  58 /* --- @mp_read@ --- *
  59  *
  60  * Arguments:   @mp *m@ = destination multiprecision number
  61  *              @int radix@ = base to assume for data (or zero to guess)
  62  *              @const mptext_ops *ops@ = pointer to operations block
  63  *              @void *p@ = data for the operations block
  64  *
  65  * Returns:     The integer read, or zero if it didn't work.
  66  *
  67  * Use:         Reads an integer from some source.  If the @radix@ is
  68  *              specified, the number is assumed to be given in that radix,
  69  *              with the letters `a' (either upper- or lower-case) upwards
  70  *              standing for digits greater than 9.  Otherwise, base 10 is
  71  *              assumed unless the number starts with `0' (octal), `0x' (hex)
  72  *              or `nnn_' (base `nnn').  An arbitrary amount of whitespace
  73  *              before the number is ignored.
  74  */
  75
  76 mp *mp_read(mp *m, int radix, const mptext_ops *ops, void *p)
  77 {
  78   int r;
  79   int ch;
  80   unsigned f = 0;
  81
  82   enum {
  83     f_neg = 1u,
  84     f_ok = 2u
  85   };
  86
  87   /* --- Initialize the destination number --- */
  88
  89   MP_MODIFY(m, 4);
  90   m->vl = m->v;
  91   m->f &= ~MP_UNDEF;
  92
  93   /* --- Read an initial character --- */
  94
  95   ch = ops->get(p);
  96   while (isspace(ch))
  97     ch = ops->get(p);
  98
  99   /* --- Handle an initial sign --- */
 100
 101   if (ch == '-') {
 102     f |= f_neg;
 103     ch = ops->get(p);
 104     while (isspace(ch))
 105       ch = ops->get(p);
 106   }
 107
 108   /* --- If the radix is zero, look for leading zeros --- */
 109
 110   if (radix)
 111     r = -1;
 112   else if (ch != '0') {
 113     radix = 10;
 114     r = 0;
 115   } else {
 116     ch = ops->get(p);
 117     if (ch == 'x') {
 118       ch = ops->get(p);
 119       radix = 16;
 120     } else {
 121       radix = 8;
 122       f |= f_ok;
 123     }
 124     r = -1;
 125   }
 126
 127   /* --- Time to start --- */
 128
 129   for (;; ch = ops->get(p)) {
 130     int x;
 131
 132     /* --- An underscore indicates a numbered base --- */
 133
 134     if (ch == '_' && r > 0 && r <= 36) {
 135       radix = r;
 136       m->vl = m->v;
 137       r = -1;
 138       f &= ~f_ok;
 139       continue;
 140     }
 141
 142     /* --- Check that the character is a digit and in range --- */
 143
 144     if (!isalnum(ch))
 145       break;
 146     if (ch >= '0' && ch <= '9')
 147       x = ch - '0';
 148     else {
 149       ch = tolower(ch);
 150       if (ch >= 'a' && ch <= 'z')       /* ASCII dependent! */
 151         x = ch - 'a' + 10;
 152       else
 153         break;
 154     }
 155
 156     /* --- Sort out what to do with the character --- */
 157
 158     if (x >= 10 && r >= 0)
 159       r = -1;
 160     if (x >= radix)
 161       break;
 162
 163     if (r >= 0)
 164       r = r * 10 + x;
 165
 166     /* --- Stick the character on the end of my integer --- */
 167
 168     mp_ensure(m, MP_LEN(m) + 1);
 169     mpx_umuln(m->v, m->vl, m->v, m->vl - 1, radix);
 170     mpx_uaddn(m->v, m->vl, x);
 171     mp_shrink(m);
 172     f |= f_ok;
 173   }
 174
 175   ops->unget(ch, p);
 176
 177   /* --- Bail out if the number was bad --- */
 178
 179   if (!(f & f_ok)) {
 180     MP_DROP(m);
 181     return (0);
 182   }
 183
 184   /* --- Set the sign and return --- */
 185
 186   m->f = 0;
 187   if (f & f_neg)
 188     m->f |= MP_NEG;
 189   return (m);
 190 }
 191
 192 /* --- @mp_write@ --- *
 193  *
 194  * Arguments:   @mp *m@ = pointer to a multi-precision integer
 195  *              @int radix@ = radix to use when writing the number out
 196  *              @const mptext_ops *ops@ = pointer to an operations block
 197  *              @void *p@ = data for the operations block
 198  *
 199  * Returns:     Zero if it worked, nonzero otherwise.
 200  *
 201  * Use:         Writes a large integer in textual form.
 202  */
 203
 204 /* --- Simple case --- *
 205  *
 206  * Use a fixed-sized buffer and the simple single-precision division
 207  * algorithm to pick off low-order digits.  Put each digit in a buffer,
 208  * working backwards from the end.  If the buffer becomes full, recurse to
 209  * get another one.  Ensure that there are at least @z@ digits by writing
 210  * leading zeroes if there aren't enough real digits.
 211  */
 212
 213 static int simple(mp *m, int radix, unsigned z,
 214                   const mptext_ops *ops, void *p)
 215 {
 216   int rc = 0;
 217   char buf[64];
 218   unsigned i = sizeof(buf);
 219
 220   do {
 221     int ch;
 222     mpw x;
 223
 224     x = mpx_udivn(m->v, m->vl, m->v, m->vl, radix);
 225     MP_SHRINK(m);
 226     if (x < 10)
 227       ch = '0' + x;
 228     else
 229       ch = 'a' + x - 10;
 230     buf[--i] = ch;
 231     if (z)
 232       z--;
 233   } while (i && MP_LEN(m));
 234
 235   if (MP_LEN(m))
 236     rc = simple(m, radix, z, ops, p);
 237   else {
 238     static const char zero[32] = "00000000000000000000000000000000";
 239     while (!rc && z >= sizeof(zero)) {
 240       rc = ops->put(zero, sizeof(zero), p);
 241       z -= sizeof(zero);
 242     }
 243     if (!rc && z)
 244       rc = ops->put(zero, z, p);
 245   }
 246   if (!rc)
 247     ops->put(buf + i, sizeof(buf) - i, p);
 248   if (m->f & MP_BURN)
 249     BURN(buf);
 250   return (rc);
 251 }
 252
 253 /* --- Complicated case --- *
 254  *
 255  * If the number is small, fall back to the simple case above.  Otherwise
 256  * divide and take remainder by current large power of the radix, and emit
 257  * each separately.  Don't emit a zero quotient.  Be very careful about
 258  * leading zeroes on the remainder part, because they're deeply significant.
 259  */
 260
 261 static int complicated(mp *m, int radix, mp **pr, unsigned i, unsigned z,
 262                        const mptext_ops *ops, void *p)
 263 {
 264   int rc = 0;
 265   mp *q = MP_NEW;
 266   unsigned d = 1 << i;
 267
 268   if (MP_LEN(m) < 8)
 269     return (simple(m, radix, z, ops, p));
 270
 271   mp_div(&q, &m, m, pr[i]);
 272   if (!MP_LEN(q))
 273     d = z;
 274   else {
 275     if (z > d)
 276       z -= d;
 277     else
 278       z = 0;
 279     rc = complicated(q, radix, pr, i - 1, z, ops, p);
 280   }
 281   if (!rc)
 282     rc = complicated(m, radix, pr, i - 1, d, ops, p);
 283   mp_drop(q);
 284   return (rc);
 285 }
 286
 287 /* --- Main driver code --- */
 288
 289 int mp_write(mp *m, int radix, const mptext_ops *ops, void *p)
 290 {
 291   int rc;
 292
 293   /* --- Set various things up --- */
 294
 295   m = MP_COPY(m);
 296   MP_SPLIT(m);
 297
 298   /* --- If the number is negative, sort that out --- */
 299
 300   if (m->f & MP_NEG) {
 301     if (ops->put("-", 1, p))
 302       return (EOF);
 303   }
 304
 305   /* --- If the number is small, do it the easy way --- */
 306
 307   if (MP_LEN(m) < 8)
 308     rc = simple(m, radix, 0, ops, p);
 309
 310   /* --- Use a clever algorithm --- *
 311    *
 312    * Square the radix repeatedly, remembering old results, until I get
 313    * something more than half the size of the number @m@.  Use this to divide
 314    * the number: the quotient and remainder will be approximately the same
 315    * size, and I'll have split them on a digit boundary, so I can just emit
 316    * the quotient and remainder recursively, in order.
 317    *
 318    * The array size copes with the largest number possibly representable on
 319    * the host machine.  Such a large number shouldn't ever arise in real use.
 320    */
 321
 322   else {
 323     mp *pr[CHAR_BIT * sizeof(size_t)];
 324     size_t target = MP_LEN(m) / 2;
 325     unsigned i = 0;
 326     mp *z = mp_create(1);
 327
 328     /* --- Set up the exponent table --- */
 329
 330     z->v[0] = radix;
 331     z->f = 0;
 332     for (;;) {
 333       assert(((void)"Number is too unimaginably huge",
 334               i < sizeof(pr) / sizeof(pr[0])));
 335       pr[i++] = z;
 336       if (MP_LEN(z) > target)
 337         break;
 338       z = mp_sqr(MP_NEW, z);
 339     }
 340
 341     /* --- Write out the answer --- */
 342
 343     rc = complicated(m, radix, pr, i - 1, 0, ops, p);
 344
 345     /* --- Tidy away the array --- */
 346
 347     while (i > 0)
 348       mp_drop(pr[--i]);
 349   }
 350
 351   /* --- Tidying up code --- */
 352
 353   MP_DROP(m);
 354   return (rc);
 355 }
 356
 357 /*----- Test rig ----------------------------------------------------------*/
 358
 359 #ifdef TEST_RIG
 360
 361 #include <mLib/testrig.h>
 362
 363 static int verify(dstr *v)
 364 {
 365   int ok = 1;
 366   int ib = *(int *)v[0].buf, ob = *(int *)v[2].buf;
 367   dstr d = DSTR_INIT;
 368   mp *m = mp_readdstr(MP_NEW, &v[1], 0, ib);
 369   if (m) {
 370     if (!ob) {
 371       fprintf(stderr, "*** unexpected successful parse\n"
 372                       "*** input [%i] = %s\n",
 373               ib, v[1].buf);
 374       mp_writedstr(m, &d, 10);
 375       fprintf(stderr, "*** (value = %s)\n", d.buf);
 376       ok = 0;
 377     } else {
 378       mp_writedstr(m, &d, ob);
 379       if (d.len != v[3].len || memcmp(d.buf, v[3].buf, d.len) != 0) {
 380         fprintf(stderr, "*** failed read or write\n"
 381                         "*** input [%i]    = %s\n"
 382                         "*** output [%i]   = %s\n"
 383                         "*** expected [%i] = %s\n",
 384                 ib, v[1].buf, ob, d.buf, ob, v[3].buf);
 385         ok = 0;
 386       }
 387     }
 388     mp_drop(m);
 389   } else {
 390     if (ob) {
 391       fprintf(stderr, "*** unexpected parse failure\n"
 392                       "*** input [%i] = %s\n"
 393                       "*** expected [%i] = %s\n",
 394               ib, v[1].buf, ob, v[3].buf);
 395       ok = 0;
 396     }
 397   }
 398
 399   dstr_destroy(&d);
 400   assert(mparena_count(MPARENA_GLOBAL) == 0);
 401   return (ok);
 402 }
 403
 404 static test_chunk tests[] = {
 405   { "mptext", verify,
 406     { &type_int, &type_string, &type_int, &type_string, 0 } },
 407   { 0, 0, { 0 } }
 408 };
 409
 410 int main(int argc, char *argv[])
 411 {
 412   sub_init();
 413   test_run(argc, argv, tests, SRCDIR "/tests/mptext");
 414   return (0);
 415 }
 416
 417 #endif
 418
 419 /*----- That's all, folks -------------------------------------------------*/