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