Sunday, March 8, 2009

Don't use old dtoa.c

A lot of projects use the dtoa.c file that bears the following copyright notice:

 * The author of this software is David M. Gay.
*
* Copyright (c) 1991, 2000, 2001 by Lucent Technologies.


If your software uses it, please take steps to update this file or stop using it. The reason is very simple: your program will compile just fine, but will work incorrectly when compiled with gcc-4.4.0 (not released yet). Here is a short testcase (save as test.c):

#include <stdio.h>

double strtod(const char *s00, char **se);

int main(int argc, char* argv[])
{
double result = strtod(argv[1], 0);
printf("%f\n", result);
return 0;
}


Compile as follows: gcc-4.4 -O2 -Dstrtod=my_strtod -DIEEE_8087=1 -DHonor_FLT_ROUNDS=1 -DTrust_FLT_ROUNDS -DOmit_Private_Memory=1 -DNO_INFNAN_CHECK=1 -DNO_HEX_FP=1 dtoa.c test.c

The -Dstrtod=my_strtod flag is needed in order to make sure that the version of strtod() from dtoa.c, not from your system C library, is used. -O2 is the default optimization level used by many software projects. The rest of the flags are explained in the dtoa.c file.

The testcase converts its argument to a double-precision floating-point number, and then prints the result. So, when given a number, this testcase should print it back. let's try:

$ ./a.out 1.1
11.000000


The result is clearly incorrect. The reason (as one can see by appending -Wall to the compiler command line) is that strict aliasing rules are violated in dtoa.c. Indeed, if one adds the -fno-strict-aliasing flag to the compiler command line, the resulting program will behave correctly:

$ ./a.out 1.1
1.100000


Here is the formulation of the aliasing rules from ISO/IEC 9899:TC2, section 6.5:


An object shall have its stored value accessed only by an lvalue expression that has one of the following types:


  • a type compatible with the effective type of the object,

  • a qualified version of a type compatible with the effective type of the object,

  • a type that is the signed or unsigned type corresponding to the effective type of the object,

  • a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,

  • an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or

  • a character type.



dtoa.c does this:

typedef union { double d; ULong L[2]; } U;

#define word0(x) ((U*)&x)->L[1]
#define word1(x) ((U*)&x)->L[0]
#define dval(x) ((U*)&x)->d


So, it stores doubles, but reads this memory using lvalue expressions of the "ULong" type (and the other way round), contrary to the standard.

GCC allows such access only if the memory is accessed through a union type. The TC3 revision of the C99 standard also allows type punning through the union in the footnote in the section 6.5.2.3:

If the member used to access the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning".


In dtoa.c, the union is "invented" each time the code wants to reinterpret a double value as two ULongs. So, it doesn't make sense to speak about the member last used to store a value in the union, and the note above doesn't apply. I.e., instead of this code,

double a;
word0(a) = L;
word1(a) = 0;
return dval(a);


this should be used:

U a;
a.L[0] = L;
a.L[1] = 0;
return a.d;


Note that there are no pointer casts in the corrected code.

The topic of strict aliasing rules, with working and non-working examples, is explained in the GCC manual. An updated version of dtoa.c and the needed header are available in the sources of GCC itself.

8 comments:

Xan said...

Hi. The compiler flags you suggest does not seem to actually work, at least on my box:

niraikanai:~/dtoa%gcc -O2 -Dstrtod=my_strtod -DIEEE_8087=1 -DHonor_FLT_ROUNDS=1 -DTrust_FLT_ROUNDS -DOmit_Private_Memory=1 -DNO_INFNAN_CHECK=1 -DNO_HEX_FP=1 dtoa.c test.c
dtoa.c: In function ‘dshift’:
dtoa.c:2099: error: ‘kmask’ undeclared (first use in this function)
dtoa.c:2099: error: (Each undeclared identifier is reported only once
dtoa.c:2099: error: for each function it appears in.)
dtoa.c: In function ‘bigcomp’:
dtoa.c:2291: warning: assignment makes pointer from integer without a cast
niraikanai:~/dtoa%

I guess this is system-dependent, but just in case you missed something obvious (for you) :)

Alexander Patrakov said...

On that server, dtoa.c was modified on March 16th, 2009 and no longer contains the strict aliasing problem. As for the compilation error, it looks like they broke -DNO_HEX_FP=1.

Alexander Patrakov said...

The old and buggy version of dtoa.c, for those interested, is still available at http://web.archive.org/web/20070831185511/http://www.netlib.org/fp/dtoa.c

Flameeyes said...

Hah! Thanks for your head up, I just hit a miscompilation bug with the FreeBSD C library.. when I have seen a reference to dtoa it rang an immediate bell!

Alexander Patrakov said...

Due to spam, anonymous comments for this blog post are disabled.

Rick Regan said...

Alexander,

What project are you using dtoa.c in? I see you compile with "-DHonor_FLT_ROUNDS=1". I've been looking for projects that use this flag, and your blog post is the only reference to that flag I've found so far.

The reason I am curious: the current copy of dtoa.c does not correctly round in the other three IEEE rounding modes (see my article http://www.exploringbinary.com/incorrect-directed-conversions-in-david-gays-strtod/ .)

Alexander Patrakov said...

This was an internal project, under NDA. So no details here. The blog post appeared because the test suite of that project failed.

Aj said...

Hi! Thanks for the details! Now I know the reason behind why my dtoac does not work properly, will update and have some modifications,

Thanks for sharing!