Bug 89979 - subtract_with_carry_engine incorrect carry flag
Summary: subtract_with_carry_engine incorrect carry flag
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 8.2.0
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2019-04-04 21:46 UTC by Christoph Conrads
Modified: 2021-08-31 09:39 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail: 7.3.0, 8.2.0
Last reconfirmed: 2019-04-05 00:00:00

Attachments
The initial state in combination with the incorrect carry computation makes the PRNG enter the unescapable all zero state. (278 bytes, text/x-csrc)
2019-04-04 21:46 UTC, Christoph Conrads 		Details
View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Christoph Conrads 2019-04-04 21:46:47 UTC 
Created attachment 46090 [details]
The initial state in combination with the incorrect carry computation makes the PRNG enter the unescapable all zero state.

The carry inside `std::subtract_with_carry_engine` is computed incorrectly if word_size == std::numeric_limits<result_type>::digits. 

The bug can be triggered neither by std::ranlux24 nor by std::ranlux48.

The bug occurs with GCC 7.3.0, GCC 8.2.0, and Clang when using the GNU Standard C++ Library shipping with GCC 7.3.0.

$ gcc --version
gcc (Gentoo 7.3.0-r3 p1.4) 7.3.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ g++-7.3.0 -Wextra -Wall -std=c++11 -pedantic -v -save-temps ~/libstdcxx-swc-bug.cpp
Using built-in specs.
COLLECT_GCC=g++-7.3.0
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-pc-linux-gnu/7.3.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /var/tmp/portage/sys-devel/gcc-7.3.0-r3/work/gcc-7.3.0/configure --host=x86_64-pc-linux-gnu --build=x86_64-pc-linux-gnu --prefix=/usr --bindir=/usr/x86_64-pc-linux-gnu/gcc-bin/7.3.0 --includedir=/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/include --datadir=/usr/share/gcc-data/x86_64-pc-linux-gnu/7.3.0 --mandir=/usr/share/gcc-data/x86_64-pc-linux-gnu/7.3.0/man --infodir=/usr/share/gcc-data/x86_64-pc-linux-gnu/7.3.0/info --with-gxx-include-dir=/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/include/g++-v7 --with-python-dir=/share/gcc-data/x86_64-pc-linux-gnu/7.3.0/python --enable-languages=c,c++,fortran --enable-obsolete --enable-secureplt --disable-werror --with-system-zlib --enable-nls --without-included-gettext --enable-checking=release --with-bugurl=https://bugs.gentoo.org/ --with-pkgversion='Gentoo 7.3.0-r3 p1.4' --disable-esp --enable-libstdcxx-time --enable-shared --enable-threads=posix --enable-__cxa_atexit --enable-clocale=gnu --disable-multilib --with-multilib-list=m64 --disable-altivec --disable-fixed-point --enable-targets=all --enable-libgomp --disable-libmudflap --disable-libssp --disable-libcilkrts --disable-libmpx --enable-vtable-verify --enable-libvtv --enable-lto --without-isl --enable-libsanitizer --enable-default-pie --enable-default-ssp
Thread model: posix
gcc version 7.3.0 (Gentoo 7.3.0-r3 p1.4) 
COLLECT_GCC_OPTIONS='-Wextra' '-Wall' '-std=c++11' '-Wpedantic' '-v' '-save-temps' '-shared-libgcc' '-mtune=generic' '-march=x86-64'
 /usr/libexec/gcc/x86_64-pc-linux-gnu/7.3.0/cc1plus -E -quiet -v -D_GNU_SOURCE /home/starfish/libstdcxx-swc-bug.cpp -mtune=generic -march=x86-64 -std=c++11 -Wextra -Wall -Wpedantic -fpch-preprocess -o libstdcxx-swc-bug.ii
ignoring nonexistent directory "/usr/local/include"
ignoring nonexistent directory "/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../../x86_64-pc-linux-gnu/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/include/g++-v7
 /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/include/g++-v7/x86_64-pc-linux-gnu
 /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/include/g++-v7/backward
 /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/include
 /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/include-fixed
 /usr/include
End of search list.
COLLECT_GCC_OPTIONS='-Wextra' '-Wall' '-std=c++11' '-Wpedantic' '-v' '-save-temps' '-shared-libgcc' '-mtune=generic' '-march=x86-64'
 /usr/libexec/gcc/x86_64-pc-linux-gnu/7.3.0/cc1plus -fpreprocessed libstdcxx-swc-bug.ii -quiet -dumpbase libstdcxx-swc-bug.cpp -mtune=generic -march=x86-64 -auxbase libstdcxx-swc-bug -Wextra -Wall -Wpedantic -std=c++11 -version -o libstdcxx-swc-bug.s
GNU C++11 (Gentoo 7.3.0-r3 p1.4) version 7.3.0 (x86_64-pc-linux-gnu)
	compiled by GNU C version 7.3.0, GMP version 6.1.2, MPFR version 3.1.6, MPC version 1.0.3, isl version none
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
GNU C++11 (Gentoo 7.3.0-r3 p1.4) version 7.3.0 (x86_64-pc-linux-gnu)
	compiled by GNU C version 7.3.0, GMP version 6.1.2, MPFR version 3.1.6, MPC version 1.0.3, isl version none
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
Compiler executable checksum: 09ac773f85349e020b5b36ead38f9924
COLLECT_GCC_OPTIONS='-Wextra' '-Wall' '-std=c++11' '-Wpedantic' '-v' '-save-temps' '-shared-libgcc' '-mtune=generic' '-march=x86-64'
 /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../../x86_64-pc-linux-gnu/bin/as -v --64 -o libstdcxx-swc-bug.o libstdcxx-swc-bug.s
GNU assembler version 2.30.0 (x86_64-pc-linux-gnu) using BFD version (Gentoo 2.30 p5) 2.30.0
COMPILER_PATH=/usr/libexec/gcc/x86_64-pc-linux-gnu/7.3.0/:/usr/libexec/gcc/x86_64-pc-linux-gnu/7.3.0/:/usr/libexec/gcc/x86_64-pc-linux-gnu/:/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/:/usr/lib/gcc/x86_64-pc-linux-gnu/:/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../../x86_64-pc-linux-gnu/bin/
LIBRARY_PATH=/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/:/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../../lib64/:/lib/../lib64/:/usr/lib/../lib64/:/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../../x86_64-pc-linux-gnu/lib/:/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../:/lib/:/usr/lib/
COLLECT_GCC_OPTIONS='-Wextra' '-Wall' '-std=c++11' '-Wpedantic' '-v' '-save-temps' '-shared-libgcc' '-mtune=generic' '-march=x86-64'
 /usr/libexec/gcc/x86_64-pc-linux-gnu/7.3.0/collect2 -plugin /usr/libexec/gcc/x86_64-pc-linux-gnu/7.3.0/liblto_plugin.so -plugin-opt=/usr/libexec/gcc/x86_64-pc-linux-gnu/7.3.0/lto-wrapper -plugin-opt=-fresolution=libstdcxx-swc-bug.res -plugin-opt=-pass-through=-lgcc_s -plugin-opt=-pass-through=-lgcc -plugin-opt=-pass-through=-lc -plugin-opt=-pass-through=-lgcc_s -plugin-opt=-pass-through=-lgcc --eh-frame-hdr -m elf_x86_64 -dynamic-linker /lib64/ld-linux-x86-64.so.2 -pie /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../../lib64/Scrt1.o /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../../lib64/crti.o /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/crtbeginS.o -L/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0 -L/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../../lib64 -L/lib/../lib64 -L/usr/lib/../lib64 -L/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../../x86_64-pc-linux-gnu/lib -L/usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../.. libstdcxx-swc-bug.o -lstdc++ -lm -lgcc_s -lgcc -lc -lgcc_s -lgcc /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/crtendS.o /usr/lib/gcc/x86_64-pc-linux-gnu/7.3.0/../../../../lib64/crtn.o
COLLECT_GCC_OPTIONS='-Wextra' '-Wall' '-std=c++11' '-Wpedantic' '-v' '-save-temps' '-shared-libgcc' '-mtune=generic' '-march=x86-64'
Comment 1 Christoph Conrads 2019-04-04 21:50:51 UTC 
There is no attachment with the preprocessed code demonstrating the problem because the this code is 1.2 MB large.
Comment 2 Jonathan Wakely 2019-04-05 10:22:47 UTC 
(In reply to Christoph Conrads from comment #1)
> There is no attachment with the preprocessed code demonstrating the problem
> because the this code is 1.2 MB large.

That's OK in this case as you code doesn't depend on anything except standard library headers.
Comment 3 Drea Pinski 2021-08-22 21:46:46 UTC 
LLVM's libc++ does not go into the 0 loop but still does not do a good job:
4294967295 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 4294967295 1
0 0 0 0 0 4294967295 4294967295 1
0 0 0 0 4294967295 4294967295 4294967295 1
0 0 0 4294967295 4294967295 4294967295 4294967294 0
0 0 4294967295 4294967295 4294967295 4294967294 4294967295 0
0 4294967295 4294967295 4294967295 4294967294 4294967295 4294967295 0
4294967295 4294967295 4294967295 4294967294 4294967295 4294967295 4294967294 0
4294967295 4294967295 4294967294 4294967295 4294967295 4294967294 0 0
4294967295 4294967294 4294967295 4294967295 4294967294 0 0 0
4294967294 4294967295 4294967295 4294967294 0 0 4294967295 1


While libstdc++ does seems to get into a loop:
4294967295 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 6
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 4
Comment 4 Christoph Conrads 2021-08-31 09:39:24 UTC 
> LLVM's libc++ does not go into the 0 loop but still does not do a good job:

The subtract-with-carry PRNG is a simple PRNG, it has a very long period whose length can be proved with elementary number theory but the randomness properties of an SWC on its own are bad which is why you have to discard a lot of values. For reference, std::ranlux48 uses about 11 out of 389 values and you can detect (self-advertisement: it discards much less variates if you you use my parameters: b=32, s=2, r=13, see https://github.com/boostorg/random/issues/57).

Here are the random values are drawing 100 times:

114294 141465 4294632814 252684 106646 4294497449 475286

Here are the random values after drawing 1000 times:

3844519667 4029384828 773557245 3005408692 1891078342 2314767096 2602358454

After drawing 2000 times:

671901017 3735908022 2276383719 2942324048 2197640583 3544339665 2823890385