source: mainline/uspace/lib/posix/stdlib/strtold.c@ 5ee9692

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 5ee9692 was 5ee9692, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 14 years ago

strtold(): fix problem with leading zeros and exponent overflow
  • Property mode set to 100644
File size: 12.0 KB
Line 
1/*
2 * Copyright (c) 2011 Jiri Zarevucky
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup libposix
30 * @{
31 */
32/** @file
33 */
34
35#define LIBPOSIX_INTERNAL
36
37#include "../internal/common.h"
38
39#include "../libc/assert.h"
40#include "../ctype.h"
41#include <errno.h> // TODO: use POSIX errno
42#include "../libc/bool.h"
43#include "../libc/stdint.h"
44#include "../stdlib.h"
45#include "../strings.h"
46
47#ifndef HUGE_VALL
48 #define HUGE_VALL (+1.0l / +0.0l)
49#endif
50
51#ifndef abs
52 #define abs(x) ((x < 0) ? -x : x)
53#endif
54
55// TODO: clean up, documentation
56
57// FIXME: ensure it builds and works on all platforms
58
59const int max_small_pow5 = 15;
60
61/* The value at index i is approximately 5**i. */
62long double small_pow5[] = {
63 0x1P0,
64 0x5P0,
65 0x19P0,
66 0x7dP0,
67 0x271P0,
68 0xc35P0,
69 0x3d09P0,
70 0x1312dP0,
71 0x5f5e1P0,
72 0x1dcd65P0,
73 0x9502f9P0,
74 0x2e90eddP0,
75 0xe8d4a51P0,
76 0x48c27395P0,
77 0x16bcc41e9P0,
78 0x71afd498dP0
79};
80
81/* The value at index i is approximately 5**(2**i). */
82long double large_pow5[] = {
83 0x5P0l,
84 0x19P0l,
85 0x271P0l,
86 0x5f5e1P0l,
87 0x2386f26fc1P0l,
88 0x4ee2d6d415b85acef81P0l,
89 0x184f03e93ff9f4daa797ed6e38ed64bf6a1f01P0l,
90 0x24ee91f2603a6337f19bccdb0dac404dc08d3cff5ecP128l,
91 0x553f75fdcefcef46eeddcP512l,
92 0x1c633415d4c1d238d98cab8a978a0b1f138cb07303P1024l,
93 0x325d9d61a05d4305d9434f4a3c62d433949ae6209d492P2200l,
94 0x9e8b3b5dc53d5de4a74d28ce329ace526a3197bbebe3034f77154ce2bcba1964P4500l,
95 0x6230290145104bcd64a60a9fc025254932bb0fd922271133eeae7P9300l
96};
97
98/* Powers of two. */
99long double pow2[] = {
100 0x1P1l,
101 0x1P2l,
102 0x1P4l,
103 0x1P8l,
104 0x1P16l,
105 0x1P32l,
106 0x1P64l,
107 0x1P128l,
108 0x1P256l,
109 0x1P512l,
110 0x1P1024l,
111 0x1P2048l,
112 0x1P4096l,
113 0x1P8192l
114};
115
116static inline bool out_of_range(long double num)
117{
118 return num == 0.0l || num == HUGE_VALL;
119}
120
121/**
122 * Multiplies a number by a power of five.
123 * The result is not exact and may not be the best possible approximation.
124 *
125 * @param base Number to be multiplied.
126 * @param exponent Base 5 exponent.
127 * @return base multiplied by 5**exponent
128 */
129static long double mul_pow5(long double base, int exponent)
130{
131 if (out_of_range(base)) {
132 return base;
133 }
134
135 if (abs(exponent) >> 13 != 0) {
136 errno = ERANGE;
137 return exponent < 0 ? 0.0l : HUGE_VALL;
138 }
139
140 if (exponent < 0) {
141 exponent = -exponent;
142 base /= small_pow5[exponent & 0xF];
143 for (int i = 4; i < 13; ++i) {
144 if (((exponent >> i) & 1) != 0) {
145 base /= large_pow5[i];
146 if (out_of_range(base)) {
147 errno = ERANGE;
148 break;
149 }
150 }
151 }
152 } else {
153 base *= small_pow5[exponent & 0xF];
154 for (int i = 4; i < 13; ++i) {
155 if (((exponent >> i) & 1) != 0) {
156 base *= large_pow5[i];
157 if (out_of_range(base)) {
158 errno = ERANGE;
159 break;
160 }
161 }
162 }
163 }
164
165 return base;
166}
167
168/**
169 * Multiplies a number by a power of two.
170 *
171 * @param base Number to be multiplied.
172 * @param exponent Base 2 exponent.
173 * @return base multiplied by 2**exponent
174 */
175static long double mul_pow2(long double base, int exponent)
176{
177 if (out_of_range(base)) {
178 return base;
179 }
180
181 if (abs(exponent) >> 14 != 0) {
182 errno = ERANGE;
183 return exponent < 0 ? 0.0l : HUGE_VALL;
184 }
185
186 if (exponent < 0) {
187 exponent = -exponent;
188 for (int i = 0; i < 14; ++i) {
189 if (((exponent >> i) & 1) != 0) {
190 base /= pow2[i];
191 if (out_of_range(base)) {
192 errno = ERANGE;
193 break;
194 }
195 }
196 }
197 } else {
198 for (int i = 0; i < 14; ++i) {
199 if (((exponent >> i) & 1) != 0) {
200 base *= pow2[i];
201 if (out_of_range(base)) {
202 errno = ERANGE;
203 break;
204 }
205 }
206 }
207 }
208
209 return base;
210}
211
212
213static long double parse_decimal(const char **sptr)
214{
215 // TODO: Use strtol(), at least for exponent.
216
217 const int DEC_BASE = 10;
218 const char DECIMAL_POINT = '.';
219 const char EXPONENT_MARK = 'e';
220 /* The highest amount of digits that can be safely parsed
221 * before an overflow occurs.
222 */
223 const int PARSE_DECIMAL_DIGS = 19;
224
225 /* significand */
226 uint64_t significand = 0;
227
228 /* position in the input string */
229 int i = 0;
230
231 /* number of digits parsed so far */
232 int parsed_digits = 0;
233
234 int exponent = 0;
235
236 const char *str = *sptr;
237
238 /* digits before decimal point */
239 while (isdigit(str[i])) {
240 if (parsed_digits == 0 && str[i] == '0') {
241 /* Nothing, just skip leading zeros. */
242 } else if (parsed_digits < PARSE_DECIMAL_DIGS) {
243 significand *= DEC_BASE;
244 significand += str[i] - '0';
245 parsed_digits++;
246 } else {
247 exponent++;
248 }
249
250 i++;
251 }
252
253 if (str[i] == DECIMAL_POINT) {
254 i++;
255
256 /* digits after decimal point */
257 while (isdigit(str[i])) {
258 if (parsed_digits == 0 && str[i] == '0') {
259 /* Skip leading zeros and decrement exponent. */
260 exponent--;
261 } else if (parsed_digits < PARSE_DECIMAL_DIGS) {
262 significand *= DEC_BASE;
263 significand += str[i] - '0';
264 exponent--;
265 parsed_digits++;
266 } else {
267 /* ignore */
268 }
269
270 i++;
271 }
272 }
273
274 /* exponent */
275 if (tolower(str[i]) == EXPONENT_MARK) {
276 i++;
277
278 bool negative = false;
279 int exp = 0;
280
281 switch (str[i]) {
282 case '-':
283 negative = true;
284 /* fallthrough */
285 case '+':
286 i++;
287 }
288
289 while (isdigit(str[i]) && exp < 65536) {
290 exp *= DEC_BASE;
291 exp += str[i] - '0';
292
293 i++;
294 }
295
296 if (negative) {
297 exp = -exp;
298 }
299
300 exponent += exp;
301 }
302
303 long double result = (long double) significand;
304 result = mul_pow5(result, exponent);
305 if (result != HUGE_VALL) {
306 result = mul_pow2(result, exponent);
307 }
308
309 *sptr = &str[i];
310 return result;
311}
312
313static inline int hex_value(char ch)
314{
315 if (ch <= '9') {
316 return ch - '0';
317 } else {
318 return 10 + tolower(ch) - 'a';
319 }
320}
321
322/**
323 * @param val Integer value.
324 * @return How many leading zero bits there are. (Maximum is 3)
325 */
326static inline int leading_zeros(uint64_t val)
327{
328 for (int i = 3; i > 0; --i) {
329 if ((val >> (64 - i)) == 0) {
330 return i;
331 }
332 }
333
334 return 0;
335}
336
337static long double parse_hexadecimal(const char **sptr)
338{
339 // TODO: Use strtol(), at least for exponent.
340
341 /* this function currently always rounds to zero */
342 // TODO: honor rounding mode
343
344 const int DEC_BASE = 10;
345 const int HEX_BASE = 16;
346 const char DECIMAL_POINT = '.';
347 const char EXPONENT_MARK = 'p';
348 /* The highest amount of digits that can be safely parsed
349 * before an overflow occurs.
350 */
351 const int PARSE_HEX_DIGS = 16;
352
353 /* significand */
354 uint64_t significand = 0;
355
356 /* position in the input string */
357 int i = 0;
358
359 /* number of digits parsed so far */
360 int parsed_digits = 0;
361
362 int exponent = 0;
363
364 const char *str = *sptr;
365
366 /* digits before decimal point */
367 while (posix_isxdigit(str[i])) {
368 if (parsed_digits == 0 && str[i] == '0') {
369 /* Nothing, just skip leading zeros. */
370 } else if (parsed_digits < PARSE_HEX_DIGS) {
371 significand *= HEX_BASE;
372 significand += hex_value(str[i]);
373 parsed_digits++;
374 } else if (parsed_digits == PARSE_HEX_DIGS) {
375 /* The first digit may have had leading zeros,
376 * so we need to parse one more digit and shift
377 * the value accordingly.
378 */
379
380 int zeros = leading_zeros(significand);
381 significand = (significand << zeros) |
382 (hex_value(str[i]) >> (4 - zeros));
383
384 exponent += (4 - zeros);
385 parsed_digits++;
386 } else {
387 exponent += 4;
388 }
389
390 i++;
391 }
392
393 if (str[i] == DECIMAL_POINT) {
394 i++;
395
396 /* digits after decimal point */
397 while (posix_isxdigit(str[i])) {
398 if (parsed_digits == 0 && str[i] == '0') {
399 /* Skip leading zeros and decrement exponent. */
400 exponent -= 4;
401 } else if (parsed_digits < PARSE_HEX_DIGS) {
402 significand *= HEX_BASE;
403 significand += hex_value(str[i]);
404 exponent -= 4;
405 parsed_digits++;
406 } else if (parsed_digits == PARSE_HEX_DIGS) {
407 /* The first digit may have had leading zeros,
408 * so we need to parse one more digit and shift
409 * the value accordingly.
410 */
411
412 int zeros = leading_zeros(significand);
413 significand = (significand << zeros) |
414 (hex_value(str[i]) >> (4 - zeros));
415
416 exponent -= zeros;
417 parsed_digits++;
418 } else {
419 /* ignore */
420 }
421
422 i++;
423 }
424 }
425
426 /* exponent */
427 if (tolower(str[i]) == EXPONENT_MARK) {
428 i++;
429
430 bool negative = false;
431 int exp = 0;
432
433 switch (str[i]) {
434 case '-':
435 negative = true;
436 /* fallthrough */
437 case '+':
438 i++;
439 }
440
441 while (isdigit(str[i]) && exp < 65536) {
442 exp *= DEC_BASE;
443 exp += str[i] - '0';
444
445 i++;
446 }
447
448 if (negative) {
449 exp = -exp;
450 }
451
452 exponent += exp;
453 }
454
455 long double result = (long double) significand;
456 result = mul_pow2(result, exponent);
457
458 *sptr = &str[i];
459 return result;
460}
461
462/**
463 * Converts a string representation of a floating-point number to
464 * its native representation. Largely POSIX compliant, except for
465 * locale differences (always uses '.' at the moment) and rounding.
466 * Decimal strings are NOT guaranteed to be correctly rounded. This function
467 * should return a good enough approximation for most purposes but if you
468 * depend on a precise conversion, use hexadecimal representation.
469 * Hexadecimal strings are currently always rounded towards zero, regardless
470 * of the current rounding mode.
471 *
472 * @param nptr Input string.
473 * @param endptr If non-NULL, *endptr is set to the position of the first
474 * unrecognized character.
475 * @return An approximate representation of the input floating-point number.
476 */
477long double posix_strtold(const char *restrict nptr, char **restrict endptr)
478{
479 assert(nptr != NULL);
480
481 const int RADIX = '.';
482
483 /* minus sign */
484 bool negative = false;
485 /* current position in the string */
486 int i = 0;
487
488 /* skip whitespace */
489 while (isspace(nptr[i])) {
490 i++;
491 }
492
493 /* parse sign */
494 switch (nptr[i]) {
495 case '-':
496 negative = true;
497 /* fallthrough */
498 case '+':
499 i++;
500 }
501
502 /* check for NaN */
503 if (posix_strncasecmp(&nptr[i], "nan", 3) == 0) {
504 // FIXME: return NaN
505 // TODO: handle the parenthesised case
506
507 if (endptr != NULL) {
508 *endptr = (char *) &nptr[i + 3];
509 }
510 errno = ERANGE;
511 return negative ? -0.0l : +0.0l;
512 }
513
514 /* check for Infinity */
515 if (posix_strncasecmp(&nptr[i], "inf", 3) == 0) {
516 i += 3;
517 if (posix_strncasecmp(&nptr[i], "inity", 5) == 0) {
518 i += 5;
519 }
520
521 if (endptr != NULL) {
522 *endptr = (char *) &nptr[i];
523 }
524 return negative ? -HUGE_VALL : +HUGE_VALL;
525 }
526
527 /* check for a hex number */
528 if (nptr[i] == '0' && tolower(nptr[i + 1]) == 'x' &&
529 (posix_isxdigit(nptr[i + 2]) ||
530 (nptr[i + 2] == RADIX && posix_isxdigit(nptr[i + 3])))) {
531 i += 2;
532
533 const char *ptr = &nptr[i];
534 /* this call sets errno if appropriate. */
535 long double result = parse_hexadecimal(&ptr);
536 if (endptr != NULL) {
537 *endptr = (char *) ptr;
538 }
539 return negative ? -result : result;
540 }
541
542 /* check for a decimal number */
543 if (isdigit(nptr[i]) || (nptr[i] == RADIX && isdigit(nptr[i + 1]))) {
544 const char *ptr = &nptr[i];
545 /* this call sets errno if appropriate. */
546 long double result = parse_decimal(&ptr);
547 if (endptr != NULL) {
548 *endptr = (char *) ptr;
549 }
550 return negative ? -result : result;
551 }
552
553 /* nothing to parse */
554 if (endptr != NULL) {
555 *endptr = (char *) nptr;
556 }
557 errno = EINVAL;
558 return 0;
559}
560
561/** @}
562 */
563
Note: See TracBrowser for help on using the repository browser.