3 * Textual representation of multiprecision numbers
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
38 /*----- Magical numbers ---------------------------------------------------*/
40 /* --- Maximum recursion depth --- *
42 * This is the number of bits in a @size_t@ object. Why?
44 * To see this, let %$b = \textit{MPW\_MAX} + 1$% and let %$Z$% be the
45 * largest @size_t@ value. Then the largest possible @mp@ is %$M - 1$% where
46 * %$M = b^Z$%. Let %$r$% be a radix to read or write. Since the recursion
47 * squares the radix at each step, the highest number reached by the
48 * recursion is %$d$%, where:
52 * Solving gives that %$d = \lg \log_r b^Z$%. If %$r = 2$%, this is maximum,
53 * so choosing %$d = \lg \lg b^Z = \lg (Z \lg b) = \lg Z + \lg \lg b$%.
55 * Expressing %$\lg Z$% as @CHAR_BIT * sizeof(size_t)@ yields an
56 * overestimate, since a @size_t@ representation may contain `holes'.
57 * Choosing to represent %$\lg \lg b$% by 10 is almost certainly sufficient
58 * for `some time to come'.
61 #define DEPTH (CHAR_BIT * sizeof(size_t) + 10)
63 /*----- Input -------------------------------------------------------------*/
65 /* --- @mp_read@ --- *
67 * Arguments: @mp *m@ = destination multiprecision number
68 * @int radix@ = base to assume for data (or zero to guess)
69 * @const mptext_ops *ops@ = pointer to operations block
70 * @void *p@ = data for the operations block
72 * Returns: The integer read, or zero if it didn't work.
74 * Use: Reads an integer from some source. If the @radix@ is
75 * specified, the number is assumed to be given in that radix,
76 * with the letters `a' (either upper- or lower-case) upwards
77 * standing for digits greater than 9. Otherwise, base 10 is
78 * assumed unless the number starts with `0' (octal), `0x' (hex)
79 * or `nnn_' (base `nnn'). An arbitrary amount of whitespace
80 * before the number is ignored.
83 /* --- About the algorithm --- *
85 * The algorithm here is rather aggressive. I maintain an array of
86 * successive squarings of the radix, and a stack of partial results, each
87 * with a counter attached indicating which radix square to multiply by.
88 * Once the item at the top of the stack reaches the same counter level as
89 * the next item down, they are combined together and the result is given a
90 * counter level one higher than either of the results.
92 * Gluing the results together at the end is slightly tricky. Pay attention
95 * This is more complicated because of the need to handle the slightly
99 mp
*mp_read(mp
*m
, int radix
, const mptext_ops
*ops
, void *p
)
101 int ch
; /* Current char being considered */
102 unsigned f
= 0; /* Flags about the current number */
103 int r
; /* Radix to switch over to */
104 mpw rd
; /* Radix as an @mp@ digit */
105 mp rr
; /* The @mp@ for the radix */
106 unsigned nf
= m ? m
->f
& MP_BURN
: 0; /* New @mp@ flags */
110 mp
*pow
[DEPTH
]; /* List of powers */
111 unsigned pows
; /* Next index to fill */
112 struct { unsigned i
; mp
*m
; } s
[DEPTH
]; /* Main stack */
113 unsigned sp
; /* Current stack pointer */
121 /* --- Initialize the stacks --- */
123 mp_build(&rr
, &rd
, &rd
+ 1);
129 /* --- Initialize the destination number --- */
134 /* --- Read an initial character --- */
142 /* --- Handle an initial sign --- */
144 if (radix
>= 0 && (ch
== '-' || ch
== '+')) {
147 do ch
= ops
->get(p
); while isspace(ch
);
150 /* --- If the radix is zero, look for leading zeros --- */
153 assert(((void)"ascii radix must be <= 62", radix
<= 62));
156 } else if (radix
< 0) {
158 assert(((void)"binary radix must fit in a byte", rd
<= UCHAR_MAX
));
160 } else if (ch
!= '0') {
185 /* --- Use fast algorithm for binary radix --- *
187 * This is the restart point after having parsed a radix number from the
188 * input. We check whether the radix is binary, and if so use a fast
189 * algorithm which just stacks the bits up in the right order.
196 case 2: bit
= 1; goto bin
;
197 case 4: bit
= 2; goto bin
;
198 case 8: bit
= 3; goto bin
;
199 case 16: bit
= 4; goto bin
;
200 case 32: bit
= 5; goto bin
;
201 case 64: bit
= 6; goto bin
;
202 case 128: bit
= 7; goto bin
;
206 /* --- The fast binary algorithm --- *
208 * We stack bits up starting at the top end of a word. When one word is
209 * full, we write it to the integer, and start another with the left-over
210 * bits. When the array in the integer is full, we resize using low-level
211 * calls and copy the current data to the top end. Finally, we do a single
212 * bit-shift when we know where the end of the number is.
217 unsigned b
= MPW_BITS
;
221 m
= mp_dest(MP_NEW
, 1, nf
);
225 for (;; ch
= ops
->get(p
)) {
231 /* --- Check that the character is a digit and in range --- */
238 if (ch
>= '0' && ch
<= '9')
243 if (ch
>= 'a' && ch
<= 'z') /* ASCII dependent! */
245 else if (ch
>= 'A' && ch
<= 'Z')
254 /* --- Feed the digit into the accumulator --- */
257 if (!x
&& !(f
& f_start
))
264 a
|= MPW(x
) >> (bit
- b
);
271 v
= mpalloc(m
->a
, len
);
272 memcpy(v
+ n
, m
->v
, MPWS(n
));
277 a
= (b
< MPW_BITS
) ?
MPW(x
) << b
: 0;
281 /* --- Finish up --- */
292 m
= mp_lsr(m
, m
, (unsigned long)n
* MPW_BITS
+ b
);
298 /* --- Time to start --- */
300 for (;; ch
= ops
->get(p
)) {
306 /* --- An underscore indicates a numbered base --- */
308 if (ch
== '_' && r
> 0 && r
<= 62) {
311 /* --- Clear out the stacks --- */
313 for (i
= 1; i
< pows
; i
++)
316 for (i
= 0; i
< sp
; i
++)
320 /* --- Restart the search --- */
329 /* --- Check that the character is a digit and in range --- */
336 if (ch
>= '0' && ch
<= '9')
341 if (ch
>= 'a' && ch
<= 'z') /* ASCII dependent! */
343 else if (ch
>= 'A' && ch
<= 'Z')
350 /* --- Sort out what to do with the character --- */
352 if (x
>= 10 && r
>= 0)
360 /* --- Stick the character on the end of my integer --- */
362 assert(((void)"Number is too unimaginably huge", sp
< DEPTH
));
363 s
[sp
].m
= m
= mp_new(1, nf
);
367 /* --- Now grind through the stack --- */
369 while (sp
> 0 && s
[sp
- 1].i
== s
[sp
].i
) {
371 /* --- Combine the top two items --- */
375 m
= mp_mul(m
, m
, pow
[s
[sp
].i
]);
376 m
= mp_add(m
, m
, s
[sp
+ 1].m
);
378 MP_DROP(s
[sp
+ 1].m
);
381 /* --- Make a new radix power if necessary --- */
383 if (s
[sp
].i
>= pows
) {
384 assert(((void)"Number is too unimaginably huge", pows
< DEPTH
));
385 pow
[pows
] = mp_sqr(MP_NEW
, pow
[pows
- 1]);
395 /* --- If we're done, compute the rest of the number --- */
406 /* --- Combine the top two items --- */
410 z
= mp_mul(z
, z
, pow
[s
[sp
+ 1].i
]);
412 m
= mp_add(m
, m
, s
[sp
+ 1].m
);
414 MP_DROP(s
[sp
+ 1].m
);
416 /* --- Make a new radix power if necessary --- */
418 if (s
[sp
].i
>= pows
) {
419 assert(((void)"Number is too unimaginably huge", pows
< DEPTH
));
420 pow
[pows
] = mp_sqr(MP_NEW
, pow
[pows
- 1]);
429 for (i
= 0; i
< sp
; i
++)
433 /* --- Clear the radix power list --- */
437 for (i
= 1; i
< pows
; i
++)
441 /* --- Bail out if the number was bad --- */
447 /* --- Set the sign and return --- */
459 /*----- Output ------------------------------------------------------------*/
461 /* --- @mp_write@ --- *
463 * Arguments: @mp *m@ = pointer to a multi-precision integer
464 * @int radix@ = radix to use when writing the number out
465 * @const mptext_ops *ops@ = pointer to an operations block
466 * @void *p@ = data for the operations block
468 * Returns: Zero if it worked, nonzero otherwise.
470 * Use: Writes a large integer in textual form.
473 static int digit_char(int d
, int radix
)
475 if (radix
< 0) return (d
);
476 else if (d
< 10) return (d
+ '0');
477 else if (d
< 26) return (d
- 10 + 'a');
478 else return (d
- 36 + 'A');
481 /* --- Simple case --- *
483 * Use a fixed-sized buffer and single-precision arithmetic to pick off
484 * low-order digits. Put each digit in a buffer, working backwards from the
485 * end. If the buffer becomes full, recurse to get another one. Ensure that
486 * there are at least @z@ digits by writing leading zeroes if there aren't
487 * enough real digits.
490 static int write_simple(mpw n
, int radix
, unsigned z
,
491 const mptext_ops
*ops
, void *p
)
495 unsigned i
= sizeof(buf
);
496 int rd
= radix
> 0 ? radix
: -radix
;
501 buf
[--i
] = digit_char(x
, radix
);
506 rc
= write_simple(n
, radix
, z
, ops
, p
);
509 memset(zbuf
, (radix
< 0) ?
0 : '0', sizeof(zbuf
));
510 while (!rc
&& z
>= sizeof(zbuf
)) {
511 rc
= ops
->put(zbuf
, sizeof(zbuf
), p
);
514 if (!rc
&& z
) rc
= ops
->put(zbuf
, z
, p
);
516 if (!rc
) rc
= ops
->put(buf
+ i
, sizeof(buf
) - i
, p
);
521 /* --- Complicated case --- *
523 * If the number is small, fall back to the simple case above. Otherwise
524 * divide and take remainder by current large power of the radix, and emit
525 * each separately. Don't emit a zero quotient. Be very careful about
526 * leading zeroes on the remainder part, because they're deeply significant.
529 static int write_complicated(mp
*m
, int radix
, mp
**pr
,
530 unsigned i
, unsigned z
,
531 const mptext_ops
*ops
, void *p
)
538 return (write_simple(MP_LEN(m
) ? m
->v
[0] : 0, radix
, z
, ops
, p
));
541 mp_div(&q
, &m
, m
, pr
[i
]);
542 if (MP_ZEROP(q
)) d
= z
;
546 rc
= write_complicated(q
, radix
, pr
, i
- 1, z
, ops
, p
);
548 if (!rc
) rc
= write_complicated(m
, radix
, pr
, i
- 1, d
, ops
, p
);
553 /* --- Binary case --- *
555 * Special case for binary output. Goes much faster.
558 static int write_binary(mp
*m
, int bit
, int radix
,
559 const mptext_ops
*ops
, void *p
)
573 /* --- Work out where to start --- */
576 if (n
% bit
) n
+= bit
- (n
% bit
);
580 if (n
>= MP_LEN(m
)) {
587 mask
= (1 << bit
) - 1;
590 /* --- Main code --- */
599 if (v
== m
->v
) break;
601 if (b
< MPW_BITS
) x
|= a
>> b
;
604 if (!x
&& !(f
& f_out
)) continue;
606 *q
++ = digit_char(x
, radix
);
607 if (q
>= buf
+ sizeof(buf
)) {
608 if ((rc
= ops
->put(buf
, sizeof(buf
), p
)) != 0) goto done
;
615 *q
++ = digit_char(x
, radix
);
616 rc
= ops
->put(buf
, q
- buf
, p
);
625 /* --- Main driver code --- */
627 int mp_write(mp
*m
, int radix
, const mptext_ops
*ops
, void *p
)
635 if (MP_EQ(m
, MP_ZERO
))
636 return (ops
->put(radix
> 0 ?
"0" : "\0", 1, p
));
638 /* --- Set various things up --- */
643 /* --- Check the radix for sensibleness --- */
646 assert(((void)"ascii radix must be <= 62", radix
<= 62));
648 assert(((void)"binary radix must fit in a byte", -radix
<= UCHAR_MAX
));
650 assert(((void)"radix can't be zero in mp_write", 0));
652 /* --- If the number is negative, sort that out --- */
656 if (ops
->put("-", 1, p
)) return (EOF
);
660 /* --- Handle binary radix --- */
663 case 2: case -2: return (write_binary(m
, 1, radix
, ops
, p
));
664 case 4: case -4: return (write_binary(m
, 2, radix
, ops
, p
));
665 case 8: case -8: return (write_binary(m
, 3, radix
, ops
, p
));
666 case 16: case -16: return (write_binary(m
, 4, radix
, ops
, p
));
667 case 32: case -32: return (write_binary(m
, 5, radix
, ops
, p
));
668 case -64: return (write_binary(m
, 6, radix
, ops
, p
));
669 case -128: return (write_binary(m
, 7, radix
, ops
, p
));
672 /* --- If the number is small, do it the easy way --- */
675 rc
= write_simple(MP_LEN(m
) ? m
->v
[0] : 0, radix
, 0, ops
, p
);
677 /* --- Use a clever algorithm --- *
679 * Square the radix repeatedly, remembering old results, until I get
680 * something more than half the size of the number @m@. Use this to divide
681 * the number: the quotient and remainder will be approximately the same
682 * size, and I'll have split them on a digit boundary, so I can just emit
683 * the quotient and remainder recursively, in order.
687 target
= (MP_LEN(m
) + 1) / 2;
690 /* --- Set up the exponent table --- */
692 z
->v
[0] = (radix
> 0 ? radix
: -radix
);
695 assert(((void)"Number is too unimaginably huge", i
< DEPTH
));
697 if (MP_LEN(z
) > target
) break;
698 z
= mp_sqr(MP_NEW
, z
);
701 /* --- Write out the answer --- */
703 rc
= write_complicated(m
, radix
, pr
, i
- 1, 0, ops
, p
);
705 /* --- Tidy away the array --- */
707 while (i
> 0) mp_drop(pr
[--i
]);
710 /* --- Tidying up code --- */
716 /*----- Test rig ----------------------------------------------------------*/
720 #include <mLib/testrig.h>
722 static int verify(dstr
*v
)
725 int ib
= *(int *)v
[0].buf
, ob
= *(int *)v
[2].buf
;
728 mp
*m
= mp_readdstr(MP_NEW
, &v
[1], &off
, ib
);
731 fprintf(stderr
, "*** unexpected successful parse\n"
732 "*** input [%2i] = ", ib
);
734 type_hex
.dump(&v
[1], stderr
);
736 fputs(v
[1].buf
, stderr
);
737 mp_writedstr(m
, &d
, 10);
738 fprintf(stderr
, "\n*** (value = %s)\n", d
.buf
);
741 mp_writedstr(m
, &d
, ob
);
742 if (d
.len
!= v
[3].len
|| memcmp(d
.buf
, v
[3].buf
, d
.len
) != 0) {
743 fprintf(stderr
, "*** failed read or write\n"
744 "*** input [%2i] = ", ib
);
746 type_hex
.dump(&v
[1], stderr
);
748 fputs(v
[1].buf
, stderr
);
749 fprintf(stderr
, "\n*** output [%2i] = ", ob
);
751 type_hex
.dump(&d
, stderr
);
753 fputs(d
.buf
, stderr
);
754 fprintf(stderr
, "\n*** expected [%2i] = ", ob
);
756 type_hex
.dump(&v
[3], stderr
);
758 fputs(v
[3].buf
, stderr
);
766 fprintf(stderr
, "*** unexpected parse failure\n"
767 "*** input [%2i] = ", ib
);
769 type_hex
.dump(&v
[1], stderr
);
771 fputs(v
[1].buf
, stderr
);
772 fprintf(stderr
, "\n*** expected [%2i] = ", ob
);
774 type_hex
.dump(&v
[3], stderr
);
776 fputs(v
[3].buf
, stderr
);
782 if (v
[1].len
- off
!= v
[4].len
||
783 memcmp(v
[1].buf
+ off
, v
[4].buf
, v
[4].len
) != 0) {
784 fprintf(stderr
, "*** leftovers incorrect\n"
785 "*** input [%2i] = ", ib
);
787 type_hex
.dump(&v
[1], stderr
);
789 fputs(v
[1].buf
, stderr
);
790 fprintf(stderr
, "\n*** expected `%s'\n"
792 v
[4].buf
, v
[1].buf
+ off
);
797 assert(mparena_count(MPARENA_GLOBAL
) == 0);
801 static test_chunk tests
[] = {
802 { "mptext-ascii", verify
,
803 { &type_int
, &type_string
, &type_int
, &type_string
, &type_string
, 0 } },
804 { "mptext-bin-in", verify
,
805 { &type_int
, &type_hex
, &type_int
, &type_string
, &type_string
, 0 } },
806 { "mptext-bin-out", verify
,
807 { &type_int
, &type_string
, &type_int
, &type_hex
, &type_string
, 0 } },
811 int main(int argc
, char *argv
[])
814 test_run(argc
, argv
, tests
, SRCDIR
"/t/mptext");
820 /*----- That's all, folks -------------------------------------------------*/