I was hacking on a simple problem and got to this program:
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int memo[6][6][6][6][6][26];
int offset;
int num;
char input[31];
char prefix[31];
int prefix_sz;
int getchar(int row, int col)
{
if (row < 0 || col < 0 || prefix[row*5 + col] == 0)
return -1;
return prefix[row*5 + col] - 'A';
}
int cnt(int A, int B, int C, int D, int E, int CH)
{
if (CH == 25)
return 1;
if (count(prefix, prefix+prefix_sz, CH+'A'))
return cnt(A, B, C, D, E, CH+1);
int &res = memo[A][B][C][D][E][CH];
if (res != -1)
return res;
int as = 0, bs = 0, cs = 0, ds = 0, es = 0;
if (A < 5 && getchar(0,A-1) < CH) as = cnt(A+1, B, C, D, E, CH+1);
if (B < A && getchar(0, B) < CH && getchar(1,B-1) < CH) bs = cnt(A,
B+1, C, D, E, CH+1);
if (C < B && getchar(1, C) < CH && getchar(2,C-1) < CH) cs = cnt(A, B,
C+1, D, E, CH+1);
if (D < C && getchar(2, D) < CH && getchar(3,D-1) < CH) ds = cnt(A, B,
C, D+1, E, CH+1);
if (E < D && getchar(3, E) < CH && getchar(4,E-1) < CH) es = cnt(A, B,
C, D, E+1, CH+1);
res = as+bs+cs+ds+es;
return res;
}
int getcnt()
{
memset(memo, -1, sizeof memo);
int arr[5] = {0};
int i;
prefix_sz += 1;
for (i = 0; i < prefix_sz / 5; ++i)
arr[i] = 5;
arr[i] = prefix_sz % 5;
int res = cnt(arr[0], arr[1], arr[2], arr[3], arr[4], 0);
prefix_sz -= 1;
return res;
}
int main()
{
memset(memo, -1, sizeof memo);
num = 1;
int offset = 0;
int &s = prefix_sz;
int last = 0;
int lastc = 0;
prefix[0] = 'A';
for (s = 1; s < 25; ++s) {
for (int c = 'B'; c <= 'Y'; ++c) { // here seems to be the
problem when s=24, the c should go from 'B' to 'Y'
// because I don't modify c
anywhere else and not even s
prefix[s] = c;
if (s == 24)
printf("prefix[%d] = %c (%d), lastc = %c\n", s,
prefix[s], c, (char)lastc);
if (getchar(s/5-1,s%5) >= c-'A' || getchar(s/5,s%5-1)
>= c-'A' || count(prefix, prefix+s, c))
continue;
if (offset >= num) {
offset -= last;
prefix[s] = lastc;
break;
}
last = getcnt();
offset += last;
lastc = c;
}
}
printf("%s\n", prefix);
return 0;
}
The outputs:
g++ file.cpp ; ./a.out
prefix[24] = B (66), lastc = X
prefix[24] = C (67), lastc = X
prefix[24] = D (68), lastc = X
prefix[24] = E (69), lastc = X
prefix[24] = F (70), lastc = X
prefix[24] = G (71), lastc = X
prefix[24] = H (72), lastc = X
prefix[24] = I (73), lastc = X
prefix[24] = J (74), lastc = X
prefix[24] = K (75), lastc = X
prefix[24] = L (76), lastc = X
prefix[24] = M (77), lastc = X
prefix[24] = N (78), lastc = X
prefix[24] = O (79), lastc = X
prefix[24] = P (80), lastc = X
prefix[24] = Q (81), lastc = X
prefix[24] = R (82), lastc = X
prefix[24] = S (83), lastc = X
prefix[24] = T (84), lastc = X
prefix[24] = U (85), lastc = X
prefix[24] = V (86), lastc = X
prefix[24] = W (87), lastc = X
prefix[24] = X (88), lastc = X
prefix[24] = Y (89), lastc = X
ABCDEFGHIJKLMNOPQRSTUVWXY
g++ -O2 file.cpp ; ./a.out
prefix[24] = B (66), lastc = X
prefix[24] = C (67), lastc = X
prefix[24] = D (68), lastc = X
prefix[24] = E (69), lastc = X
prefix[24] = F (70), lastc = X
prefix[24] = G (71), lastc = X
prefix[24] = H (72), lastc = X
prefix[24] = I (73), lastc = X
prefix[24] = J (74), lastc = X
prefix[24] = K (75), lastc = X
prefix[24] = L (76), lastc = X
prefix[24] = M (77), lastc = X
prefix[24] = N (78), lastc = X
prefix[24] = O (79), lastc = X
prefix[24] = P (80), lastc = X
prefix[24] = Q (81), lastc = X
prefix[24] = R (82), lastc = X
prefix[24] = S (83), lastc = X
prefix[24] = T (84), lastc = X
prefix[24] = U (85), lastc = X
prefix[24] = V (86), lastc = X
prefix[24] = W (87), lastc = X
prefix[24] = X (88), lastc = X
prefix[24] = Y (89), lastc = X
prefix[24] = (1), lastc =
prefix[24] = (2), lastc =
prefix[24] = (3), lastc =
prefix[24] = (4), lastc =
prefix[24] = (5), lastc =
prefix[24] = (6), lastc =
prefix[24] = (7), lastc =
prefix[24] = (8), lastc =
prefix[24] = (9), lastc =
prefix[24] =
(10), lastc =
prefix[24] =
(11), lastc =
prefix[24] =
(12), lastc =
(13), lastc =
prefix[24] = (14), ┌▒⎽├␌ =
⎻⎼␊°␋│[24] = (15), lastc =
prefix[24] = (16), lastc =
prefix[24] = (17), lastc =
prefix[24] = (18), lastc =
prefix[24] = (19), lastc =
prefix[24] = (20), lastc =
prefix[24] = (21), lastc =
prefix[24] = (22), lastc =
prefix[24] = (23), lastc =
prefix[24] = (24), lastc =
prefix[24] = (25), lastc =
prefix[24] = (26), lastc =
prefix[24] = (27), lastc =
prefix[24] = (28), lastc =
prefix[24] = (29), lastc =
prefix[24] = (30), lastc =
prefix[24] = (31), lastc =
prefix[24] = (32), lastc =
prefix[24] = ! (33), lastc =
prefix[24] = " (34), lastc =
prefix[24] = # (35), lastc =
prefix[24] = $ (36), lastc =
prefix[24] = % (37), lastc =
prefix[24] = & (38), lastc =
prefix[24] = ' (39), lastc =
prefix[24] = ( (40), lastc =
prefix[24] = ) (41), lastc =
prefix[24] = * (42), lastc =
prefix[24] = + (43), lastc =
prefix[24] = , (44), lastc =
prefix[24] = - (45), lastc =
prefix[24] = . (46), lastc =
prefix[24] = / (47), lastc =
prefix[24] = 0 (48), lastc =
prefix[24] = 1 (49), lastc =
prefix[24] = 2 (50), lastc =
prefix[24] = 3 (51), lastc =
prefix[24] = 4 (52), lastc =
prefix[24] = 5 (53), lastc =
prefix[24] = 6 (54), lastc =
prefix[24] = 7 (55), lastc =
prefix[24] = 8 (56), lastc =
prefix[24] = 9 (57), lastc =
prefix[24] = : (58), lastc =
prefix[24] = ; (59), lastc =
prefix[24] = < (60), lastc =
prefix[24] = = (61), lastc =
prefix[24] = > (62), lastc =
prefix[24] = ? (63), lastc =
prefix[24] = @ (64), lastc =
prefix[24] = A (65), lastc =
prefix[24] = B (66), lastc =
prefix[24] = C (67), lastc =
prefix[24] = D (68), lastc =
prefix[24] = E (69), lastc =
prefix[24] = F (70), lastc =
prefix[24] = G (71), lastc =
prefix[24] = H (72), lastc =
prefix[24] = I (73), lastc =
prefix[24] = J (74), lastc =
prefix[24] = K (75), lastc =
prefix[24] = L (76), lastc =
prefix[24] = M (77), lastc =
prefix[24] = N (78), lastc =
prefix[24] = O (79), lastc =
prefix[24] = P (80), lastc =
prefix[24] = Q (81), lastc =
prefix[24] = R (82), lastc =
prefix[24] = S (83), lastc =
prefix[24] = T (84), lastc =
prefix[24] = U (85), lastc =
prefix[24] = V (86), lastc =
prefix[24] = W (87), lastc =
prefix[24] = X (88), lastc =
prefix[24] = Y (89), lastc =
ABCDEFGHIJKLMNOPQRSTUVWX
I was testing this with my distro's g++, g++ -v:
Using built-in specs.
Target: i686-pc-linux-gnu
Configured with: ../configure --prefix=/usr --enable-shared
--enable-languages=c,c++,fortran,objc,obj-c++,treelang --enable-threads=posix
--mandir=/usr/share/man --enable-__cxa_atexit --disable-multilib
--libdir=/usr/lib --libexecdir=/usr/lib --enable-clocale=gnu
--disable-libstdcxx-pch --with-tune=generic
Thread model: posix
gcc version 4.3.1 (GCC)
Then I downloaded it from SVN, where it segfaults for -O3 after displaying the
correct output, g++ -v:
Using built-in specs.
Target: i686-pc-linux-gnu
Configured with: ./configure
Thread model: posix
gcc version 4.4.0 20080618 (experimental) (GCC)
For the segfaulting -O3 version the output of valgrind:
valgrind ./a.out
==23963== Memcheck, a memory error detector.
==23963== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
==23963== Using LibVEX rev 1854, a library for dynamic binary translation.
==23963== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==23963== Using valgrind-3.3.1, a dynamic binary instrumentation framework.
==23963== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==23963== For more details, rerun with: -v
==23963==
==23963== Conditional jump or move depends on uninitialised value(s)
==23963== at 0x400AC2B: _dl_relocate_object (in /lib/ld-2.8.so)
==23963== by 0x4003788: dl_main (in /lib/ld-2.8.so)
==23963== by 0x4014460: _dl_sysdep_start (in /lib/ld-2.8.so)
==23963== by 0x4001187: _dl_start (in /lib/ld-2.8.so)
==23963== by 0x40007F6: (within /lib/ld-2.8.so)
==23963==
==23963== Conditional jump or move depends on uninitialised value(s)
==23963== at 0x400AC33: _dl_relocate_object (in /lib/ld-2.8.so)
==23963== by 0x4003788: dl_main (in /lib/ld-2.8.so)
==23963== by 0x4014460: _dl_sysdep_start (in /lib/ld-2.8.so)
==23963== by 0x4001187: _dl_start (in /lib/ld-2.8.so)
==23963== by 0x40007F6: (within /lib/ld-2.8.so)
==23963==
==23963== Conditional jump or move depends on uninitialised value(s)
==23963== at 0x400BB61: _dl_relocate_object (in /lib/ld-2.8.so)
==23963== by 0x4003788: dl_main (in /lib/ld-2.8.so)
==23963== by 0x4014460: _dl_sysdep_start (in /lib/ld-2.8.so)
==23963== by 0x4001187: _dl_start (in /lib/ld-2.8.so)
==23963== by 0x40007F6: (within /lib/ld-2.8.so)
==23963==
==23963== Conditional jump or move depends on uninitialised value(s)
==23963== at 0x400ADE0: _dl_relocate_object (in /lib/ld-2.8.so)
==23963== by 0x4003788: dl_main (in /lib/ld-2.8.so)
==23963== by 0x4014460: _dl_sysdep_start (in /lib/ld-2.8.so)
==23963== by 0x4001187: _dl_start (in /lib/ld-2.8.so)
==23963== by 0x40007F6: (within /lib/ld-2.8.so)
==23963==
==23963== Conditional jump or move depends on uninitialised value(s)
==23963== at 0x400BC74: _dl_relocate_object (in /lib/ld-2.8.so)
==23963== by 0x4003788: dl_main (in /lib/ld-2.8.so)
==23963== by 0x4014460: _dl_sysdep_start (in /lib/ld-2.8.so)
==23963== by 0x4001187: _dl_start (in /lib/ld-2.8.so)
==23963== by 0x40007F6: (within /lib/ld-2.8.so)
==23963==
==23963== Conditional jump or move depends on uninitialised value(s)
==23963== at 0x400AC2B: _dl_relocate_object (in /lib/ld-2.8.so)
==23963== by 0x40038B3: dl_main (in /lib/ld-2.8.so)
==23963== by 0x4014460: _dl_sysdep_start (in /lib/ld-2.8.so)
==23963== by 0x4001187: _dl_start (in /lib/ld-2.8.so)
==23963== by 0x40007F6: (within /lib/ld-2.8.so)
==23963==
==23963== Conditional jump or move depends on uninitialised value(s)
==23963== at 0x400AC33: _dl_relocate_object (in /lib/ld-2.8.so)
==23963== by 0x40038B3: dl_main (in /lib/ld-2.8.so)
==23963== by 0x4014460: _dl_sysdep_start (in /lib/ld-2.8.so)
==23963== by 0x4001187: _dl_start (in /lib/ld-2.8.so)
==23963== by 0x40007F6: (within /lib/ld-2.8.so)
==23963==
==23963== Conditional jump or move depends on uninitialised value(s)
==23963== at 0x400ADE0: _dl_relocate_object (in /lib/ld-2.8.so)
==23963== by 0x40038B3: dl_main (in /lib/ld-2.8.so)
==23963== by 0x4014460: _dl_sysdep_start (in /lib/ld-2.8.so)
==23963== by 0x4001187: _dl_start (in /lib/ld-2.8.so)
==23963== by 0x40007F6: (within /lib/ld-2.8.so)
prefix[24] = B (66), lastc = X
prefix[24] = C (67), lastc = X
prefix[24] = D (68), lastc = X
prefix[24] = E (69), lastc = X
prefix[24] = F (70), lastc = X
prefix[24] = G (71), lastc = X
prefix[24] = H (72), lastc = X
prefix[24] = I (73), lastc = X
prefix[24] = J (74), lastc = X
prefix[24] = K (75), lastc = X
prefix[24] = L (76), lastc = X
prefix[24] = M (77), lastc = X
prefix[24] = N (78), lastc = X
prefix[24] = O (79), lastc = X
prefix[24] = P (80), lastc = X
prefix[24] = Q (81), lastc = X
prefix[24] = R (82), lastc = X
prefix[24] = S (83), lastc = X
prefix[24] = T (84), lastc = X
prefix[24] = U (85), lastc = X
prefix[24] = V (86), lastc = X
prefix[24] = W (87), lastc = X
prefix[24] = X (88), lastc = X
prefix[24] = Y (89), lastc = X
ABCDEFGHIJKLMNOPQRSTUVWXY
==23963== Warning: client switching stacks? SP change: 0xBEC1F798 -->
0xFFFFFFFC
==23963== to suppress, use: --max-stackframe=1094584420 or greater
==23963==
==23963== Invalid read of size 4
==23963== at 0x8048C72: main (twofive.cpp:88)
==23963== Address 0xfffffffc is not stack'd, malloc'd or (recently) free'd
==23963==
==23963== Process terminating with default action of signal 11 (SIGSEGV)
==23963== Access not within mapped region at address 0xFFFFFFFC
==23963== at 0x8048C72: main (twofive.cpp:88)
==23963==
==23963== Process terminating with default action of signal 11 (SIGSEGV)
==23963== Access not within mapped region at address 0xFFFFFFF8
==23963== at 0x401E200: _vgnU_freeres (in
/usr/lib/valgrind/x86-linux/vgpreload_core.so)
==23963==
==23963== ERROR SUMMARY: 20 errors from 9 contexts (suppressed: 0 from 0)
==23963== malloc/free: in use at exit: 0 bytes in 0 blocks.
==23963== malloc/free: 0 allocs, 0 frees, 0 bytes allocated.
==23963== For counts of detected errors, rerun with: -v
==23963== All heap blocks were freed -- no leaks are possible.
Segmentation fault
I've tested on several < 4.3 compilers, it worked everywhere as it should.
A slight statement order reorganization and the problem is gone.
I have a simple 32 bit laptop, uname -a:
Linux shiro 2.6.25-ARCH #1 SMP PREEMPT Sat Jun 14 18:07:19 CEST 2008 i686
Genuine Intel(R) CPU T2130 @ 1.86GHz GenuineIntel GNU/Linux
--
Summary: Wrong code generation with -O2 and segfault with -O3
Product: gcc
Version: 4.4.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: rlblaster at gmail dot com
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36565
