1 /*
2 * The authors of this software are Rob Pike and Ken Thompson,
3 * with contributions from Mike Burrows and Sean Dorward.
4 *
5 * Copyright (c) 2002-2006 by Lucent Technologies.
6 * Portions Copyright (c) 2004 Google Inc.
7 *
8 * Permission to use, copy, modify, and distribute this software for any
9 * purpose without fee is hereby granted, provided that this entire notice
10 * is included in all copies of any software which is or includes a copy
11 * or modification of this software and in all copies of the supporting
12 * documentation for such software.
13 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
14 * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES
15 * NOR GOOGLE INC MAKE ANY REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING
16 * THE MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
17 */
18
19 /* Copyright (c) 2002-2006 Lucent Technologies; see LICENSE */
20 #include <u.h>
21 #include <errno.h>
22 #include <libc.h>
23 #include "fmtdef.h"
24
25 enum
26 {
27 FDIGIT = 30,
28 FDEFLT = 6,
29 NSIGNIF = 17
30 };
31
32 /*
33 * first few powers of 10, enough for about 1/2 of the
34 * total space for doubles.
35 */
36 static double pows10[] =
37 {
38 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
39 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
40 1e20, 1e21, 1e22, 1e23, 1e24, 1e25, 1e26, 1e27, 1e28, 1e29,
41 1e30, 1e31, 1e32, 1e33, 1e34, 1e35, 1e36, 1e37, 1e38, 1e39,
42 1e40, 1e41, 1e42, 1e43, 1e44, 1e45, 1e46, 1e47, 1e48, 1e49,
43 1e50, 1e51, 1e52, 1e53, 1e54, 1e55, 1e56, 1e57, 1e58, 1e59,
44 1e60, 1e61, 1e62, 1e63, 1e64, 1e65, 1e66, 1e67, 1e68, 1e69,
45 1e70, 1e71, 1e72, 1e73, 1e74, 1e75, 1e76, 1e77, 1e78, 1e79,
46 1e80, 1e81, 1e82, 1e83, 1e84, 1e85, 1e86, 1e87, 1e88, 1e89,
47 1e90, 1e91, 1e92, 1e93, 1e94, 1e95, 1e96, 1e97, 1e98, 1e99,
48 1e100, 1e101, 1e102, 1e103, 1e104, 1e105, 1e106, 1e107, 1e108, 1e109,
49 1e110, 1e111, 1e112, 1e113, 1e114, 1e115, 1e116, 1e117, 1e118, 1e119,
50 1e120, 1e121, 1e122, 1e123, 1e124, 1e125, 1e126, 1e127, 1e128, 1e129,
51 1e130, 1e131, 1e132, 1e133, 1e134, 1e135, 1e136, 1e137, 1e138, 1e139,
52 1e140, 1e141, 1e142, 1e143, 1e144, 1e145, 1e146, 1e147, 1e148, 1e149,
53 1e150, 1e151, 1e152, 1e153, 1e154, 1e155, 1e156, 1e157, 1e158, 1e159,
54 };
55
56 #undef pow10
57 #define npows10 ((int)(sizeof(pows10)/sizeof(pows10[0])))
58 #define pow10(x) fmtpow10(x)
59
60 static double
61 pow10(int n)
62 {
63 double d;
64 int neg;
65
66 neg = 0;
67 if(n < 0){
68 neg = 1;
69 n = -n;
70 }
71
72 if(n < npows10)
73 d = pows10[n];
74 else{
75 d = pows10[npows10-1];
76 for(;;){
77 n -= npows10 - 1;
78 if(n < npows10){
79 d *= pows10[n];
80 break;
81 }
82 d *= pows10[npows10 - 1];
83 }
84 }
85 if(neg)
86 return 1./d;
87 return d;
88 }
89
90 /*
91 * add 1 to the decimal integer string a of length n.
92 * if 99999 overflows into 10000, return 1 to tell caller
93 * to move the virtual decimal point.
94 */
95 static int
96 xadd1(char *a, int n)
97 {
98 char *b;
99 int c;
100
101 if(n < 0 || n > NSIGNIF)
102 return 0;
103 for(b = a+n-1; b >= a; b--) {
104 c = *b + 1;
105 if(c <= '9') {
106 *b = c;
107 return 0;
108 }
109 *b = '0';
110 }
111 /*
112 * need to overflow adding digit.
113 * shift number down and insert 1 at beginning.
114 * decimal is known to be 0s or we wouldn't
115 * have gotten this far. (e.g., 99999+1 => 00000)
116 */
117 a[0] = '1';
118 return 1;
119 }
120
121 /*
122 * subtract 1 from the decimal integer string a.
123 * if 10000 underflows into 09999, make it 99999
124 * and return 1 to tell caller to move the virtual
125 * decimal point. this way, xsub1 is inverse of xadd1.
126 */
127 static int
128 xsub1(char *a, int n)
129 {
130 char *b;
131 int c;
132
133 if(n < 0 || n > NSIGNIF)
134 return 0;
135 for(b = a+n-1; b >= a; b--) {
136 c = *b - 1;
137 if(c >= '0') {
138 if(c == '0' && b == a) {
139 /*
140 * just zeroed the top digit; shift everyone up.
141 * decimal is known to be 9s or we wouldn't
142 * have gotten this far. (e.g., 10000-1 => 09999)
143 */
144 *b = '9';
145 return 1;
146 }
147 *b = c;
148 return 0;
149 }
150 *b = '9';
151 }
152 /*
153 * can't get here. the number a is always normalized
154 * so that it has a nonzero first digit.
155 */
156 abort();
157 }
158
159 /*
160 * format exponent like sprintf(p, "e%+02d", e)
161 */
162 static void
163 xfmtexp(char *p, int e, int ucase)
164 {
165 char se[9];
166 int i;
167
168 *p++ = ucase ? 'E' : 'e';
169 if(e < 0) {
170 *p++ = '-';
171 e = -e;
172 } else
173 *p++ = '+';
174 i = 0;
175 while(e) {
176 se[i++] = e % 10 + '0';
177 e /= 10;
178 }
179 while(i < 2)
180 se[i++] = '0';
181 while(i > 0)
182 *p++ = se[--i];
183 *p++ = '\0';
184 }
185
186 /*
187 * compute decimal integer m, exp such that:
188 * f = m*10^exp
189 * m is as short as possible with losing exactness
190 * assumes special cases (NaN, +Inf, -Inf) have been handled.
191 */
192 static void
193 xdtoa(double f, char *s, int *exp, int *neg, int *ns)
194 {
195 int c, d, e2, e, ee, i, ndigit, oerrno;
196 char tmp[NSIGNIF+10];
197 double g;
198
199 oerrno = errno; /* in case strtod smashes errno */
200
201 /*
202 * make f non-negative.
203 */
204 *neg = 0;
205 if(f < 0) {
206 f = -f;
207 *neg = 1;
208 }
209
210 /*
211 * must handle zero specially.
212 */
213 if(f == 0){
214 *exp = 0;
215 s[0] = '0';
216 s[1] = '\0';
217 *ns = 1;
218 return;
219 }
220
221 /*
222 * find g,e such that f = g*10^e.
223 * guess 10-exponent using 2-exponent, then fine tune.
224 */
225 frexp(f, &e2);
226 e = (int)(e2 * .301029995664);
227 g = f * pow10(-e);
228 while(g < 1) {
229 e--;
230 g = f * pow10(-e);
231 }
232 while(g >= 10) {
233 e++;
234 g = f * pow10(-e);
235 }
236
237 /*
238 * convert NSIGNIF digits as a first approximation.
239 */
240 for(i=0; i<NSIGNIF; i++) {
241 d = (int)g;
242 s[i] = d+'0';
243 g = (g-d) * 10;
244 }
245 s[i] = 0;
246
247 /*
248 * adjust e because s is 314159... not 3.14159...
249 */
250 e -= NSIGNIF-1;
251 xfmtexp(s+NSIGNIF, e, 0);
252
253 /*
254 * adjust conversion until strtod(s) == f exactly.
255 */
256 for(i=0; i<10; i++) {
257 g = strtod(s, nil);
258 if(f > g) {
259 if(xadd1(s, NSIGNIF)) {
260 /* gained a digit */
261 e--;
262 xfmtexp(s+NSIGNIF, e, 0);
263 }
264 continue;
265 }
266 if(f < g) {
267 if(xsub1(s, NSIGNIF)) {
268 /* lost a digit */
269 e++;
270 xfmtexp(s+NSIGNIF, e, 0);
271 }
272 continue;
273 }
274 break;
275 }
276
277 /*
278 * play with the decimal to try to simplify.
279 */
280
281 /*
282 * bump last few digits up to 9 if we can
283 */
284 for(i=NSIGNIF-1; i>=NSIGNIF-3; i--) {
285 c = s[i];
286 if(c != '9') {
287 s[i] = '9';
288 g = strtod(s, nil);
289 if(g != f) {
290 s[i] = c;
291 break;
292 }
293 }
294 }
295
296 /*
297 * add 1 in hopes of turning 9s to 0s
298 */
299 if(s[NSIGNIF-1] == '9') {
300 strcpy(tmp, s);
301 ee = e;
302 if(xadd1(tmp, NSIGNIF)) {
303 ee--;
304 xfmtexp(tmp+NSIGNIF, ee, 0);
305 }
306 g = strtod(tmp, nil);
307 if(g == f) {
308 strcpy(s, tmp);
309 e = ee;
310 }
311 }
312
313 /*
314 * bump last few digits down to 0 as we can.
315 */
316 for(i=NSIGNIF-1; i>=NSIGNIF-3; i--) {
317 c = s[i];
318 if(c != '0') {
319 s[i] = '0';
320 g = strtod(s, nil);
321 if(g != f) {
322 s[i] = c;
323 break;
324 }
325 }
326 }
327
328 /*
329 * remove trailing zeros.
330 */
331 ndigit = NSIGNIF;
332 while(ndigit > 1 && s[ndigit-1] == '0'){
333 e++;
334 --ndigit;
335 }
336 s[ndigit] = 0;
337 *exp = e;
338 *ns = ndigit;
339 errno = oerrno;
340 }
341
342 #ifdef PLAN9PORT
343 static char *special[] = { "NaN", "NaN", "+Inf", "+Inf", "-Inf", "-Inf" };
344 #else
345 static char *special[] = { "nan", "NAN", "inf", "INF", "-inf", "-INF" };
346 #endif
347
348 int
349 __efgfmt(Fmt *fmt)
350 {
351 char buf[NSIGNIF+10], *dot, *digits, *p, *s, suf[10], *t;
352 double f;
353 int c, chr, dotwid, e, exp, fl, ndigits, neg, newndigits;
354 int pad, point, prec, realchr, sign, sufwid, ucase, wid, z1, z2;
355 Rune r, *rs, *rt;
356
357 if(fmt->flags&FmtLong)
358 f = va_arg(fmt->args, long double);
359 else
360 f = va_arg(fmt->args, double);
361
362 /*
363 * extract formatting flags
364 */
365 fl = fmt->flags;
366 fmt->flags = 0;
367 prec = FDEFLT;
368 if(fl & FmtPrec)
369 prec = fmt->prec;
370 chr = fmt->r;
371 ucase = 0;
372 switch(chr) {
373 case 'A':
374 case 'E':
375 case 'F':
376 case 'G':
377 chr += 'a'-'A';
378 ucase = 1;
379 break;
380 }
381
382 /*
383 * pick off special numbers.
384 */
385 if(__isNaN(f)) {
386 s = special[0+ucase];
387 special:
388 fmt->flags = fl & (FmtWidth|FmtLeft);
389 return __fmtcpy(fmt, s, strlen(s), strlen(s));
390 }
391 if(__isInf(f, 1)) {
392 s = special[2+ucase];
393 goto special;
394 }
395 if(__isInf(f, -1)) {
396 s = special[4+ucase];
397 goto special;
398 }
399
400 /*
401 * get exact representation.
402 */
403 digits = buf;
404 xdtoa(f, digits, &exp, &neg, &ndigits);
405
406 /*
407 * get locale's decimal point.
408 */
409 dot = fmt->decimal;
410 if(dot == nil)
411 dot = ".";
412 dotwid = utflen(dot);
413
414 /*
415 * now the formatting fun begins.
416 * compute parameters for actual fmt:
417 *
418 * pad: number of spaces to insert before/after field.
419 * z1: number of zeros to insert before digits
420 * z2: number of zeros to insert after digits
421 * point: number of digits to print before decimal point
422 * ndigits: number of digits to use from digits[]
423 * suf: trailing suffix, like "e-5"
424 */
425 realchr = chr;
426 switch(chr){
427 case 'g':
428 /*
429 * convert to at most prec significant digits. (prec=0 means 1)
430 */
431 if(prec == 0)
432 prec = 1;
433 if(ndigits > prec) {
434 if(digits[prec] >= '5' && xadd1(digits, prec))
435 exp++;
436 exp += ndigits-prec;
437 ndigits = prec;
438 }
439
440 /*
441 * extra rules for %g (implemented below):
442 * trailing zeros removed after decimal unless FmtSharp.
443 * decimal point only if digit follows.
444 */
445
446 /* fall through to %e */
447 default:
448 case 'e':
449 /*
450 * one significant digit before decimal, no leading zeros.
451 */
452 point = 1;
453 z1 = 0;
454
455 /*
456 * decimal point is after ndigits digits right now.
457 * slide to be after first.
458 */
459 e = exp + (ndigits-1);
460
461 /*
462 * if this is %g, check exponent and convert prec
463 */
464 if(realchr == 'g') {
465 if(-4 <= e && e < prec)
466 goto casef;
467 prec--; /* one digit before decimal; rest after */
468 }
469
470 /*
471 * compute trailing zero padding or truncate digits.
472 */
473 if(1+prec >= ndigits)
474 z2 = 1+prec - ndigits;
475 else {
476 /*
477 * truncate digits
478 */
479 assert(realchr != 'g');
480 newndigits = 1+prec;
481 if(digits[newndigits] >= '5' && xadd1(digits, newndigits)) {
482 /*
483 * had 999e4, now have 100e5
484 */
485 e++;
486 }
487 ndigits = newndigits;
488 z2 = 0;
489 }
490 xfmtexp(suf, e, ucase);
491 sufwid = strlen(suf);
492 break;
493
494 casef:
495 case 'f':
496 /*
497 * determine where digits go with respect to decimal point
498 */
499 if(ndigits+exp > 0) {
500 point = ndigits+exp;
501 z1 = 0;
502 } else {
503 point = 1;
504 z1 = 1 + -(ndigits+exp);
505 }
506
507 /*
508 * %g specifies prec = number of significant digits
509 * convert to number of digits after decimal point
510 */
511 if(realchr == 'g')
512 prec += z1 - point;
513
514 /*
515 * compute trailing zero padding or truncate digits.
516 */
517 if(point+prec >= z1+ndigits)
518 z2 = point+prec - (z1+ndigits);
519 else {
520 /*
521 * truncate digits
522 */
523 assert(realchr != 'g');
524 newndigits = point+prec - z1;
525 if(newndigits < 0) {
526 z1 += newndigits;
527 newndigits = 0;
528 } else if(newndigits == 0) {
529 /* perhaps round up */
530 if(digits[0] >= '5'){
531 digits[0] = '1';
532 newndigits = 1;
533 goto newdigit;
534 }
535 } else if(digits[newndigits] >= '5' && xadd1(digits, newndigits)) {
536 /*
537 * digits was 999, is now 100; make it 1000
538 */
539 digits[newndigits++] = '0';
540 newdigit:
541 /*
542 * account for new digit
543 */
544 if(z1) /* 0.099 => 0.100 or 0.99 => 1.00*/
545 z1--;
546 else /* 9.99 => 10.00 */
547 point++;
548 }
549 z2 = 0;
550 ndigits = newndigits;
551 }
552 sufwid = 0;
553 break;
554 }
555
556 /*
557 * if %g is given without FmtSharp, remove trailing zeros.
558 * must do after truncation, so that e.g. print %.3g 1.001
559 * produces 1, not 1.00. sorry, but them's the rules.
560 */
561 if(realchr == 'g' && !(fl & FmtSharp)) {
562 if(z1+ndigits+z2 >= point) {
563 if(z1+ndigits < point)
564 z2 = point - (z1+ndigits);
565 else{
566 z2 = 0;
567 while(z1+ndigits > point && digits[ndigits-1] == '0')
568 ndigits--;
569 }
570 }
571 }
572
573 /*
574 * compute width of all digits and decimal point and suffix if any
575 */
576 wid = z1+ndigits+z2;
577 if(wid > point)
578 wid += dotwid;
579 else if(wid == point){
580 if(fl & FmtSharp)
581 wid += dotwid;
582 else
583 point++; /* do not print any decimal point */
584 }
585 wid += sufwid;
586
587 /*
588 * determine sign
589 */
590 sign = 0;
591 if(neg)
592 sign = '-';
593 else if(fl & FmtSign)
594 sign = '+';
595 else if(fl & FmtSpace)
596 sign = ' ';
597 if(sign)
598 wid++;
599
600 /*
601 * compute padding
602 */
603 pad = 0;
604 if((fl & FmtWidth) && fmt->width > wid)
605 pad = fmt->width - wid;
606 if(pad && !(fl & FmtLeft) && (fl & FmtZero)){
607 z1 += pad;
608 point += pad;
609 pad = 0;
610 }
611
612 /*
613 * format the actual field. too bad about doing this twice.
614 */
615 if(fmt->runes){
616 if(pad && !(fl & FmtLeft) && __rfmtpad(fmt, pad) < 0)
617 return -1;
618 rt = (Rune*)fmt->to;
619 rs = (Rune*)fmt->stop;
620 if(sign)
621 FMTRCHAR(fmt, rt, rs, sign);
622 while(z1>0 || ndigits>0 || z2>0) {
623 if(z1 > 0){
624 z1--;
625 c = '0';
626 }else if(ndigits > 0){
627 ndigits--;
628 c = *digits++;
629 }else{
630 z2--;
631 c = '0';
632 }
633 FMTRCHAR(fmt, rt, rs, c);
634 if(--point == 0) {
635 for(p = dot; *p; ){
636 p += chartorune(&r, p);
637 FMTRCHAR(fmt, rt, rs, r);
638 }
639 }
640 }
641 fmt->nfmt += rt - (Rune*)fmt->to;
642 fmt->to = rt;
643 if(sufwid && __fmtcpy(fmt, suf, sufwid, sufwid) < 0)
644 return -1;
645 if(pad && (fl & FmtLeft) && __rfmtpad(fmt, pad) < 0)
646 return -1;
647 }else{
648 if(pad && !(fl & FmtLeft) && __fmtpad(fmt, pad) < 0)
649 return -1;
650 t = (char*)fmt->to;
651 s = (char*)fmt->stop;
652 if(sign)
653 FMTCHAR(fmt, t, s, sign);
654 while(z1>0 || ndigits>0 || z2>0) {
655 if(z1 > 0){
656 z1--;
657 c = '0';
658 }else if(ndigits > 0){
659 ndigits--;
660 c = *digits++;
661 }else{
662 z2--;
663 c = '0';
664 }
665 FMTCHAR(fmt, t, s, c);
666 if(--point == 0)
667 for(p=dot; *p; p++)
668 FMTCHAR(fmt, t, s, *p);
669 }
670 fmt->nfmt += t - (char*)fmt->to;
671 fmt->to = t;
672 if(sufwid && __fmtcpy(fmt, suf, sufwid, sufwid) < 0)
673 return -1;
674 if(pad && (fl & FmtLeft) && __fmtpad(fmt, pad) < 0)
675 return -1;
676 }
677 return 0;
678 }
679