QRScanner/mobile/jni/fitz/ftoa.c

   1 /* The authors of this software are Rob Pike and Ken Thompson.
   2  * Copyright (c) 2002 by Lucent Technologies.
   3  * Permission to use, copy, modify, and distribute this software for any
   4  * purpose without fee is hereby granted, provided that this entire notice
   5  * is included in all copies of any software which is or includes a copy
   6  * or modification of this software and in all copies of the supporting
   7  * documentation for such software.
   8  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
   9  * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES MAKE ANY
  10  * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
  11  * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
  12  */
  13
  14 #include "mupdf/fitz.h"
  15
  16 #include <stdio.h>
  17 #include <math.h>
  18 #include <float.h>
  19 #include <string.h>
  20 #include <stdlib.h>
  21 #include <errno.h>
  22
  23 #ifndef INFINITY
  24 #define INFINITY (DBL_MAX+DBL_MAX)
  25 #endif
  26 #ifndef NAN
  27 #define NAN (INFINITY-INFINITY)
  28 #endif
  29
  30 #ifndef DEFINED_ULONG
  31 #define DEFINED_ULONG
  32 typedef unsigned long ulong;
  33 #endif
  34
  35 enum { NSIGNIF  = 9 };
  36
  37 /*
  38  * first few powers of 10
  39  */
  40 static float pows10[] =
  41 {
  42         1e0f,   1e1f,   1e2f,   1e3f,   1e4f,   1e5f,   1e6f,   1e7f,   1e8f,   1e9f,
  43         1e10f,  1e11f,  1e12f,  1e13f,  1e14f,  1e15f,  1e16f,  1e17f,  1e18f,  1e19f,
  44         1e20f,  1e21f,  1e22f,  1e23f,  1e24f,  1e25f,  1e26f,  1e27f,  1e28f,  1e29f,
  45         1e30f,  1e31f,  1e32f,  1e33f,  1e34f,  1e35f,  1e36f,  1e37f,  1e38f
  46 };
  47 #define npows10 ((int)(sizeof(pows10)/sizeof(pows10[0])))
  48 #define pow10(x) fmtpow10(x)
  49
  50 static float
  51 pow10(int n)
  52 {
  53         float d;
  54         int neg;
  55
  56         neg = 0;
  57         if(n < 0){
  58                 neg = 1;
  59                 n = -n;
  60         }
  61
  62         if(n < npows10)
  63                 d = pows10[n];
  64         else{
  65                 d = pows10[npows10-1];
  66                 for(;;){
  67                         n -= npows10 - 1;
  68                         if(n < npows10){
  69                                 d *= pows10[n];
  70                                 break;
  71                         }
  72                         d *= pows10[npows10 - 1];
  73                 }
  74         }
  75         if(neg)
  76                 return 1./d;
  77         return d;
  78 }
  79
  80 /*
  81  * add 1 to the decimal integer string a of length n.
  82  * if 99999 overflows into 10000, return 1 to tell caller
  83  * to move the virtual decimal point.
  84  */
  85 static int
  86 xadd1(char *a, int n)
  87 {
  88         char *b;
  89         int c;
  90
  91         if(n < 0 || n > NSIGNIF)
  92                 return 0;
  93         for(b = a+n-1; b >= a; b--) {
  94                 c = *b + 1;
  95                 if(c <= '9') {
  96                         *b = c;
  97                         return 0;
  98                 }
  99                 *b = '0';
 100         }
 101         /*
 102          * need to overflow adding digit.
 103          * shift number down and insert 1 at beginning.
 104          * decimal is known to be 0s or we wouldn't
 105          * have gotten this far. (e.g., 99999+1 => 00000)
 106          */
 107         a[0] = '1';
 108         return 1;
 109 }
 110
 111 /*
 112  * subtract 1 from the decimal integer string a.
 113  * if 10000 underflows into 09999, make it 99999
 114  * and return 1 to tell caller to move the virtual
 115  * decimal point. this way, xsub1 is inverse of xadd1.
 116  */
 117 static int
 118 xsub1(char *a, int n)
 119 {
 120         char *b;
 121         int c;
 122
 123         if(n < 0 || n > NSIGNIF)
 124                 return 0;
 125         for(b = a+n-1; b >= a; b--) {
 126                 c = *b - 1;
 127                 if(c >= '0') {
 128                         if(c == '0' && b == a) {
 129                                 /*
 130                                  * just zeroed the top digit; shift everyone up.
 131                                  * decimal is known to be 9s or we wouldn't
 132                                  * have gotten this far. (e.g., 10000-1 => 09999)
 133                                  */
 134                                 *b = '9';
 135                                 return 1;
 136                         }
 137                         *b = c;
 138                         return 0;
 139                 }
 140                 *b = '9';
 141         }
 142         /*
 143          * can't get here. the number a is always normalized
 144          * so that it has a nonzero first digit.
 145          */
 146         return 0;
 147 }
 148
 149 /*
 150  * format exponent like sprintf(p, "e%+d", e)
 151  */
 152 static void
 153 fmtexp(char *p, int e)
 154 {
 155         char se[9];
 156         int i;
 157
 158         *p++ = 'e';
 159         if(e < 0) {
 160                 *p++ = '-';
 161                 e = -e;
 162         } else
 163                 *p++ = '+';
 164         i = 0;
 165         while(e) {
 166                 se[i++] = e % 10 + '0';
 167                 e /= 10;
 168         }
 169         while(i < 1)
 170                 se[i++] = '0';
 171         while(i > 0)
 172                 *p++ = se[--i];
 173         *p++ = '\0';
 174 }
 175
 176 /*
 177  * compute decimal integer m, exp such that:
 178  *      f = m*10^exp
 179  *      m is as short as possible with losing exactness
 180  * assumes special cases (NaN, +Inf, -Inf) have been handled.
 181  */
 182 void
 183 fz_ftoa(float f, char *s, int *exp, int *neg, int *ns)
 184 {
 185         int c, d, e2, e, ee, i, ndigit, oerrno;
 186         char tmp[NSIGNIF+10];
 187         float g;
 188
 189         oerrno = errno; /* in case strtod smashes errno */
 190
 191         /*
 192          * make f non-negative.
 193          */
 194         *neg = 0;
 195         if(f < 0) {
 196                 f = -f;
 197                 *neg = 1;
 198         }
 199
 200         /*
 201          * must handle zero specially.
 202          */
 203         if(f == 0){
 204                 *exp = 0;
 205                 s[0] = '0';
 206                 s[1] = '\0';
 207                 *ns = 1;
 208                 return;
 209         }
 210
 211         /*
 212          * find g,e such that f = g*10^e.
 213          * guess 10-exponent using 2-exponent, then fine tune.
 214          */
 215         frexpf(f, &e2);
 216         e = (int)(e2 * .301029995664f);
 217         g = f * pow10(-e);
 218         while(g < 1) {
 219                 e--;
 220                 g = f * pow10(-e);
 221         }
 222         while(g >= 10) {
 223                 e++;
 224                 g = f * pow10(-e);
 225         }
 226
 227         /*
 228          * convert NSIGNIF digits as a first approximation.
 229          */
 230         for(i=0; i<NSIGNIF; i++) {
 231                 d = (int)g;
 232                 s[i] = d+'0';
 233                 g = (g-d) * 10;
 234         }
 235         s[i] = 0;
 236
 237         /*
 238          * adjust e because s is 314159... not 3.14159...
 239          */
 240         e -= NSIGNIF-1;
 241         fmtexp(s+NSIGNIF, e);
 242
 243         /*
 244          * adjust conversion until strtod(s) == f exactly.
 245          */
 246         for(i=0; i<10; i++) {
 247                 g = fz_strtod(s, NULL);
 248                 if(f > g) {
 249                         if(xadd1(s, NSIGNIF)) {
 250                                 /* gained a digit */
 251                                 e--;
 252                                 fmtexp(s+NSIGNIF, e);
 253                         }
 254                         continue;
 255                 }
 256                 if(f < g) {
 257                         if(xsub1(s, NSIGNIF)) {
 258                                 /* lost a digit */
 259                                 e++;
 260                                 fmtexp(s+NSIGNIF, e);
 261                         }
 262                         continue;
 263                 }
 264                 break;
 265         }
 266
 267         /*
 268          * play with the decimal to try to simplify.
 269          */
 270
 271         /*
 272          * bump last few digits up to 9 if we can
 273          */
 274         for(i=NSIGNIF-1; i>=NSIGNIF-3; i--) {
 275                 c = s[i];
 276                 if(c != '9') {
 277                         s[i] = '9';
 278                         g = fz_strtod(s, NULL);
 279                         if(g != f) {
 280                                 s[i] = c;
 281                                 break;
 282                         }
 283                 }
 284         }
 285
 286         /*
 287          * add 1 in hopes of turning 9s to 0s
 288          */
 289         if(s[NSIGNIF-1] == '9') {
 290                 strcpy(tmp, s);
 291                 ee = e;
 292                 if(xadd1(tmp, NSIGNIF)) {
 293                         ee--;
 294                         fmtexp(tmp+NSIGNIF, ee);
 295                 }
 296                 g = fz_strtod(tmp, NULL);
 297                 if(g == f) {
 298                         strcpy(s, tmp);
 299                         e = ee;
 300                 }
 301         }
 302
 303         /*
 304          * bump last few digits down to 0 as we can.
 305          */
 306         for(i=NSIGNIF-1; i>=NSIGNIF-3; i--) {
 307                 c = s[i];
 308                 if(c != '0') {
 309                         s[i] = '0';
 310                         g = fz_strtod(s, NULL);
 311                         if(g != f) {
 312                                 s[i] = c;
 313                                 break;
 314                         }
 315                 }
 316         }
 317
 318         /*
 319          * remove trailing zeros.
 320          */
 321         ndigit = NSIGNIF;
 322         while(ndigit > 1 && s[ndigit-1] == '0'){
 323                 e++;
 324                 --ndigit;
 325         }
 326         s[ndigit] = 0;
 327         *exp = e;
 328         *ns = ndigit;
 329         errno = oerrno;
 330 }