X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/a951033da37da66f31d13d4825c562bf7762e213..025c5f4aa5ffbf8948482a4233318db81c2df5d2:/mptext.c diff --git a/mptext.c b/mptext.c index 57521da..9cca8a8 100644 --- a/mptext.c +++ b/mptext.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mptext.c,v 1.10 2001/06/16 13:22:39 mdw Exp $ + * $Id$ * * Textual representation of multiprecision numbers * @@ -27,45 +27,6 @@ * MA 02111-1307, USA. */ -/*----- 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. - * Fix off-by-one bug when breaking the number apart. - * - * Revision 1.8 2000/12/06 20:32:42 mdw - * Reduce binary bytes (to allow marker bits to be ignored). Fix error - * message string a bit. Allow leading `+' signs. - * - * Revision 1.7 2000/07/15 10:01:08 mdw - * Bug fix in binary input. - * - * Revision 1.6 2000/06/25 12:58:23 mdw - * Fix the derivation of `depth' commentary. - * - * Revision 1.5 2000/06/17 11:46:19 mdw - * New and much faster stack-based algorithm for reading integers. Support - * reading and writing binary integers in bases between 2 and 256. - * - * Revision 1.4 1999/12/22 15:56:56 mdw - * Use clever recursive algorithm for writing numbers out. - * - * Revision 1.3 1999/12/10 23:23:26 mdw - * Allocate slightly less memory. - * - * Revision 1.2 1999/11/20 22:24:15 mdw - * Use function versions of MPX_UMULN and MPX_UADDN. - * - * Revision 1.1 1999/11/17 18:02:16 mdw - * New multiprecision integer arithmetic suite. - * - */ - /*----- Header files ------------------------------------------------------*/ #include @@ -82,7 +43,7 @@ * * This is the number of bits in a @size_t@ object. Why? * - * To see this, let %$b = \mathit{MPW\_MAX} + 1$% and let %$Z$% be the + * To see this, let %$b = \textit{MPW\_MAX} + 1$% and let %$Z$% be the * largest @size_t@ value. Then the largest possible @mp@ is %$M - 1$% where * %$M = b^Z$%. Let %$r$% be a radix to read or write. Since the recursion * squares the radix at each step, the highest number reached by the @@ -189,24 +150,34 @@ mp *mp_read(mp *m, int radix, const mptext_ops *ops, void *p) /* --- If the radix is zero, look for leading zeros --- */ if (radix > 0) { - assert(((void)"ascii radix must be <= 36", radix <= 36)); + assert(((void)"ascii radix must be <= 62", radix <= 62)); rd = radix; r = -1; } else if (radix < 0) { rd = -radix; - assert(((void)"binary radix must fit in a byte", rd < UCHAR_MAX)); + assert(((void)"binary radix must fit in a byte", rd <= UCHAR_MAX)); r = -1; } else if (ch != '0') { rd = 10; r = 0; } else { ch = ops->get(p); - if (ch == 'x') { - ch = ops->get(p); - rd = 16; - } else { - rd = 8; - f |= f_ok; + switch (ch) { + case 'x': + rd = 16; + goto prefix; + case 'o': + rd = 8; + goto prefix; + case 'b': + rd = 2; + goto prefix; + prefix: + ch = ops->get(p); + break; + default: + rd = 8; + f |= f_ok; } r = -1; } @@ -267,9 +238,12 @@ restart: if (ch >= '0' && ch <= '9') x = ch - '0'; else { - ch = tolower(ch); + if (rd <= 36) + ch = tolower(ch); if (ch >= 'a' && ch <= 'z') /* ASCII dependent! */ x = ch - 'a' + 10; + else if (ch >= 'A' && ch <= 'Z') + x = ch - 'A' + 36; else break; } @@ -317,6 +291,7 @@ restart: m->f &= ~MP_UNDEF; m = mp_lsr(m, m, (unsigned long)n * MPW_BITS + b); } + ops->unget(ch, p); goto done; }} @@ -330,7 +305,7 @@ restart: /* --- An underscore indicates a numbered base --- */ - if (ch == '_' && r > 0 && r <= 36) { + if (ch == '_' && r > 0 && r <= 62) { unsigned i; /* --- Clear out the stacks --- */ @@ -361,9 +336,12 @@ restart: if (ch >= '0' && ch <= '9') x = ch - '0'; else { - ch = tolower(ch); + if (rd <= 36) + ch = tolower(ch); if (ch >= 'a' && ch <= 'z') /* ASCII dependent! */ x = ch - 'a' + 10; + else if (ch >= 'A' && ch <= 'Z') + x = ch - 'A' + 36; else break; } @@ -470,6 +448,7 @@ done: if (f & f_neg) m->f |= MP_NEG; + MP_SHRINK(m); return (m); #undef f_start @@ -516,8 +495,10 @@ static int simple(mpw n, int radix, unsigned z, ch = x; else if (x < 10) ch = '0' + x; - else + else if (x < 36) /* Ascii specific */ ch = 'a' + x - 10; + else + ch = 'A' + x - 36; buf[--i] = ch; if (z) z--; @@ -561,7 +542,7 @@ static int complicated(mp *m, int radix, mp **pr, unsigned i, unsigned z, assert(i); mp_div(&q, &m, m, pr[i]); - if (!MP_LEN(q)) + if (MP_ZEROP(q)) d = z; else { if (z > d) @@ -599,11 +580,12 @@ static int binary(mp *m, int bit, int radix, const mptext_ops *ops, void *p) /* --- Work out where to start --- */ n = mp_bits(m); - n += bit - (n % bit); + if (n % bit) + n += bit - (n % bit); b = n % MPW_BITS; n /= MPW_BITS; - - if (n > MP_LEN(m)) { + + if (n >= MP_LEN(m)) { n--; b += MPW_BITS; } @@ -636,8 +618,10 @@ static int binary(mp *m, int bit, int radix, const mptext_ops *ops, void *p) ch = x; else if (x < 10) ch = '0' + x; + else if (x < 36) + ch = 'a' + x - 10; /* Ascii specific */ else - ch = 'a' + x - 10; + ch = 'A' + x - 36; *q++ = ch; if (q >= buf + sizeof(buf)) { if ((rc = ops->put(buf, sizeof(buf), p)) != 0) @@ -652,8 +636,10 @@ static int binary(mp *m, int bit, int radix, const mptext_ops *ops, void *p) ch = x; else if (x < 10) ch = '0' + x; + else if (x < 36) + ch = 'a' + x - 10; /* Ascii specific */ else - ch = 'a' + x - 10; + ch = 'A' + x - 36; *q++ = ch; rc = ops->put(buf, q - buf, p); @@ -670,6 +656,9 @@ int mp_write(mp *m, int radix, const mptext_ops *ops, void *p) { int rc; + if (MP_EQ(m, MP_ZERO)) + return (ops->put("0", 1, p)); + /* --- Set various things up --- */ m = MP_COPY(m); @@ -678,15 +667,15 @@ int mp_write(mp *m, int radix, const mptext_ops *ops, void *p) /* --- Check the radix for sensibleness --- */ if (radix > 0) - assert(((void)"ascii radix must be <= 36", radix <= 36)); + assert(((void)"ascii radix must be <= 62", radix <= 62)); else if (radix < 0) - assert(((void)"binary radix must fit in a byte", -radix < UCHAR_MAX)); + assert(((void)"binary radix must fit in a byte", -radix <= UCHAR_MAX)); else assert(((void)"radix can't be zero in mp_write", 0)); /* --- If the number is negative, sort that out --- */ - if (m->f & MP_NEG) { + if (MP_NEGP(m)) { if (ops->put("-", 1, p)) return (EOF); m->f &= ~MP_NEG; @@ -763,7 +752,8 @@ static int verify(dstr *v) int ok = 1; int ib = *(int *)v[0].buf, ob = *(int *)v[2].buf; dstr d = DSTR_INIT; - mp *m = mp_readdstr(MP_NEW, &v[1], 0, ib); + size_t off = 0; + mp *m = mp_readdstr(MP_NEW, &v[1], &off, ib); if (m) { if (!ob) { fprintf(stderr, "*** unexpected successful parse\n" @@ -802,12 +792,12 @@ static int verify(dstr *v) } else { if (ob) { fprintf(stderr, "*** unexpected parse failure\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*** expected [%i] = ", ob); + fprintf(stderr, "\n*** expected [%2i] = ", ob); if (ob < 0) type_hex.dump(&v[3], stderr); else @@ -817,6 +807,20 @@ static int verify(dstr *v) } } + if (v[1].len - off != v[4].len || + memcmp(v[1].buf + off, v[4].buf, v[4].len) != 0) { + fprintf(stderr, "*** leftovers incorrect\n" + "*** input [%2i] = ", ib); + if (ib < 0) + type_hex.dump(&v[1], stderr); + else + fputs(v[1].buf, stderr); + fprintf(stderr, "\n*** expected `%s'\n" + "*** found `%s'\n", + v[4].buf, v[1].buf + off); + ok = 0; + } + dstr_destroy(&d); assert(mparena_count(MPARENA_GLOBAL) == 0); return (ok); @@ -824,11 +828,11 @@ static int verify(dstr *v) static test_chunk tests[] = { { "mptext-ascii", verify, - { &type_int, &type_string, &type_int, &type_string, 0 } }, + { &type_int, &type_string, &type_int, &type_string, &type_string, 0 } }, { "mptext-bin-in", verify, - { &type_int, &type_hex, &type_int, &type_string, 0 } }, + { &type_int, &type_hex, &type_int, &type_string, &type_string, 0 } }, { "mptext-bin-out", verify, - { &type_int, &type_string, &type_int, &type_hex, 0 } }, + { &type_int, &type_string, &type_int, &type_hex, &type_string, 0 } }, { 0, 0, { 0 } } };