3 * $Id: mptext.c,v 1.4 1999/12/22 15:56:56 mdw Exp $
5 * Textual representation of multiprecision numbers
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.4 1999/12/22 15:56:56 mdw
34 * Use clever recursive algorithm for writing numbers out.
36 * Revision 1.3 1999/12/10 23:23:26 mdw
37 * Allocate slightly less memory.
39 * Revision 1.2 1999/11/20 22:24:15 mdw
40 * Use function versions of MPX_UMULN and MPX_UADDN.
42 * Revision 1.1 1999/11/17 18:02:16 mdw
43 * New multiprecision integer arithmetic suite.
47 /*----- Header files ------------------------------------------------------*/
56 /*----- Main code ---------------------------------------------------------*/
58 /* --- @mp_read@ --- *
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
65 * Returns: The integer read, or zero if it didn't work.
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.
76 mp
*mp_read(mp
*m
, int radix
, const mptext_ops
*ops
, void *p
)
87 /* --- Initialize the destination number --- */
93 /* --- Read an initial character --- */
99 /* --- Handle an initial sign --- */
108 /* --- If the radix is zero, look for leading zeros --- */
112 else if (ch
!= '0') {
127 /* --- Time to start --- */
129 for (;; ch
= ops
->get(p
)) {
132 /* --- An underscore indicates a numbered base --- */
134 if (ch
== '_' && r
> 0 && r
<= 36) {
142 /* --- Check that the character is a digit and in range --- */
146 if (ch
>= '0' && ch
<= '9')
150 if (ch
>= 'a' && ch
<= 'z') /* ASCII dependent! */
156 /* --- Sort out what to do with the character --- */
158 if (x
>= 10 && r
>= 0)
166 /* --- Stick the character on the end of my integer --- */
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
);
177 /* --- Bail out if the number was bad --- */
184 /* --- Set the sign and return --- */
192 /* --- @mp_write@ --- *
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
199 * Returns: Zero if it worked, nonzero otherwise.
201 * Use: Writes a large integer in textual form.
204 /* --- Simple case --- *
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.
213 static int simple(mp
*m
, int radix
, unsigned z
,
214 const mptext_ops
*ops
, void *p
)
218 unsigned i
= sizeof(buf
);
224 x
= mpx_udivn(m
->v
, m
->vl
, m
->v
, m
->vl
, radix
);
233 } while (i
&& MP_LEN(m
));
236 rc
= simple(m
, radix
, z
, ops
, p
);
238 static const char zero
[32] = "00000000000000000000000000000000";
239 while (!rc
&& z
>= sizeof(zero
)) {
240 rc
= ops
->put(zero
, sizeof(zero
), p
);
244 rc
= ops
->put(zero
, z
, p
);
247 ops
->put(buf
+ i
, sizeof(buf
) - i
, p
);
253 /* --- Complicated case --- *
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.
261 static int complicated(mp
*m
, int radix
, mp
**pr
, unsigned i
, unsigned z
,
262 const mptext_ops
*ops
, void *p
)
269 return (simple(m
, radix
, z
, ops
, p
));
271 mp_div(&q
, &m
, m
, pr
[i
]);
279 rc
= complicated(q
, radix
, pr
, i
- 1, z
, ops
, p
);
282 rc
= complicated(m
, radix
, pr
, i
- 1, d
, ops
, p
);
287 /* --- Main driver code --- */
289 int mp_write(mp
*m
, int radix
, const mptext_ops
*ops
, void *p
)
293 /* --- Set various things up --- */
298 /* --- If the number is negative, sort that out --- */
301 if (ops
->put("-", 1, p
))
305 /* --- If the number is small, do it the easy way --- */
308 rc
= simple(m
, radix
, 0, ops
, p
);
310 /* --- Use a clever algorithm --- *
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.
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.
323 mp
*pr
[CHAR_BIT
* sizeof(size_t)];
324 size_t target
= MP_LEN(m
) / 2;
326 mp
*z
= mp_create(1);
328 /* --- Set up the exponent table --- */
333 assert(((void)"Number is too unimaginably huge",
334 i
< sizeof(pr
) / sizeof(pr
[0])));
336 if (MP_LEN(z
) > target
)
338 z
= mp_sqr(MP_NEW
, z
);
341 /* --- Write out the answer --- */
343 rc
= complicated(m
, radix
, pr
, i
- 1, 0, ops
, p
);
345 /* --- Tidy away the array --- */
351 /* --- Tidying up code --- */
357 /*----- Test rig ----------------------------------------------------------*/
361 #include <mLib/testrig.h>
363 static int verify(dstr
*v
)
366 int ib
= *(int *)v
[0].buf
, ob
= *(int *)v
[2].buf
;
368 mp
*m
= mp_readdstr(MP_NEW
, &v
[1], 0, ib
);
371 fprintf(stderr
, "*** unexpected successful parse\n"
372 "*** input [%i] = %s\n",
374 mp_writedstr(m
, &d
, 10);
375 fprintf(stderr
, "*** (value = %s)\n", d
.buf
);
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
);
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
);
400 assert(mparena_count(MPARENA_GLOBAL
) == 0);
404 static test_chunk tests
[] = {
406 { &type_int
, &type_string
, &type_int
, &type_string
, 0 } },
410 int main(int argc
, char *argv
[])
413 test_run(argc
, argv
, tests
, SRCDIR
"/tests/mptext");
419 /*----- That's all, folks -------------------------------------------------*/