Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #126461
| From | jacobnavia <jacob@jacob.remcomp.fr> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | The bug |
| Date | 2018-02-08 22:50 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <p5ignt$45g$1@dont-email.me> (permalink) |
Consider this program:
1 #include <string.h>
2 #include <stdio.h>
3 #define MANTISSA_LENGTH 7
4 typedef struct tagQfloatAccum {
5 int sign;
6 unsigned int exponent;
7 unsigned long long mantissa[MANTISSA_LENGTH+8];
8 } QfloatAccum;
9 typedef QfloatAccum * QfloatAccump;
10 typedef unsigned long long QELT;
11 static void square(QfloatAccump a,QfloatAccump b,int prec )
12 {
13 QELT *p, *q, *r;
14 unsigned __int128 u, lp;
15 int k;
16
17 memset(b->mantissa,0,sizeof(b->mantissa));
18 r = &b->mantissa[prec+2];
19 for( k=prec+2; k>=2; k-- ) {
20 q = &a->mantissa[1];
21 p = &a->mantissa[k-1];
22 while( p >= q ) {
23 lp = ((__int128)(*p)) * (*q);
24 if( p != q ) {
25 if( ((lp >> 127) & 1 ) )
26 *(r-2) += 1;
27 lp <<= 1;
28 }
29 u = lp&0xffffffffffffffffULL;;
30 u += *r;
31 (*r) = (u&0xffffffffffffffffULL);
32 u = u >> 64;
33 u += (lp >> 64);
34 u += *(r-1);
35 *(r-1) = u;
36 *(r-2) += (u >> 64);
37 p--;
38 q++;
39 }
40 --r;
41 }
42 }
43
44 QfloatAccum a =
45 {0x0, 0x0, {0x0, 0x5c551d94ae0bf85d, 0xdf43ff68348e9f44,
0x75abbd546eb4ad2c , 0x45928b3668d09923, 0xef0e21fbaa8bb66b,
46 0xd834f79a27f3d70b, 0xe29f8b325d2f09bc, 0x22342f2796cceefe,
0x15136c1f 974cb8e4, 0x0, 0x0, 0x0, 0x0, 0x0}};
47 QfloatAccum b = {0};
48 QfloatAccum result =
49 {0x0, 0x0, {0x0, 0x214d498f853f343e, 0xd13fda08f3fdf79d,
0x6066a345e0141842 ,
50 0x8db2e50b963ec962, 0x703ffb7a840af142, 0xfebe1ffca06b368,
0xe705569e6ab 50956, 0x8c5227bc21e99054, 0x641cbb8833747c1a,
51 0xd32c84d233a9e32a, 0x12d004571d8dad0a, 0x0, 0x0, 0x0}};
52 int main(void)
53 {
54 square(&a,&b,9);
55 if (memcmp(&result,&b,sizeof(QfloatAccum))) {
56 printf("bug!\n");
57 }
58 }
---------------------------------------------------------------------------
Compiled without any optimizations, this program outputs nothing. Gcc
with -O2 will print "bug".
Why is this happening?
I have tried it with gcc in the ARM, where I discovered this problem.
Clang in the Macintosh has the same problem. gcc under linux x86 has the
same problem.
Context:
This program is squaring a number represented by a series of numbers
sotred modulo pow(2,64). ALl the data (variables) in this program are
unsigned.
It was a lot of effort to isolate this piece of code and build this
repro but I do not know where the bug is.
Following the lead that David Brown told me, I noticed that if you
compile this with
-fwrapv
the bug disappears.
The problem is in line 23. I forgot to put an "unsigned" in the cast to
force a 128 bit multiplication. If you add that, that code compiles with
-O2.
What is happening in line 23?
23 lp = ((__int128)(*p)) * (*q);
This specifies that:
1) The 64 bit unsigned value stored at the location pointed to by "p"
should be converted into a signed 128 bit value.
2) That value should be multiplied in 128 bit with the unsigned 64 bit
value pointed to by "q".
3) The result of the 128 bit multiplication should be stored in the
unsigned 128 bit number "lp".
4) Since the rank of a 128 bit integer is higher than the rank of the 64
bit value, the multiplication is a signed multiplication.
Where is here an undefined behavior?
The generated code in assembler is completely scrambled since gcc
reorganizes the operations of the machine so that the pipeline is always
doing several things. It makes the code impossible to follow. I noticed
also that gcc tries to fuse the two accesses to the same memory location
*(r-2), what could be a source of bugs but maybe has nothing to do with
the problem. (Lines 26 and 36)
The code generated both in the ARM 64 and the x86 does NOT store
anything as specified in line 25 and looks plainly wrong. This provokes
that squaring gives wrong results after the 58th decimal digit and the
whole software is unusable.
Is this a bug in the optimizer?
Or I am doing some "UB"?
Why should be forbidden to store a 128 bit signed value into a 128 bit
unsigned value?
What is the behavior of the other compilers? My copy of msvc is not
working anymore, I think that the updates screwed that up, it worked
last time I used it. Intel compiler anyone? Or MSVC?
Thanks in advance
Back to comp.lang.c | Previous | Next — Next in thread | Find similar | Unroll thread
The bug jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-08 22:50 +0100
Re: The bug Keith Thompson <kst-u@mib.org> - 2018-02-08 14:15 -0800
Re: The bug jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-13 10:25 +0100
Re: The bug David Brown <david.brown@hesbynett.no> - 2018-02-13 10:51 +0100
Re: The bug jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-13 11:19 +0100
Re: The bug David Brown <david.brown@hesbynett.no> - 2018-02-13 12:23 +0100
Re: The bug Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2018-02-13 08:19 -0800
Re: The bug David Brown <david.brown@hesbynett.no> - 2018-02-15 10:52 +0100
Re: The bug Noob <root@127.0.0.1> - 2018-02-13 16:19 +0100
Re: The bug Tim Rentsch <txr@alumni.caltech.edu> - 2018-02-19 12:11 -0800
Re: The bug supercat@casperkitty.com - 2018-02-19 16:31 -0800
Re: The bug Tim Rentsch <txr@alumni.caltech.edu> - 2018-02-21 23:03 -0800
Re: The bug supercat@casperkitty.com - 2018-02-23 16:40 -0800
Re: The bug Richard Damon <Richard@Damon-Family.org> - 2018-02-24 05:57 -0500
Re: The bug Tim Rentsch <txr@alumni.caltech.edu> - 2018-02-24 13:11 -0800
Re: The bug Anton Shepelev <anton.txt@gmail.com> - 2018-02-25 00:15 +0300
Re: The bug Keith Thompson <kst-u@mib.org> - 2018-02-13 11:44 -0800
Re: The bug asetofsymbols@gmail.com - 2018-02-13 12:13 -0800
Re: The bug Noob <root@127.0.0.1> - 2018-02-15 09:45 +0100
csiph-web