First, Merry Christmas and thank you for the autographed book. The problem below happened simply because people in Canada ( possibly USA also ) have formed the silly habit of gifting people at Christmas time with nice cards that have a lottery ticket in them. Personally I hate lotteries because they are just a tax on people with little or no math skills. Regardless the habit continues, much like smoking, you just can help some people with facts.
So I saw this happen in front of me and I had to say "next time just give the money to a nice charity, a guy on the street or keep it" along with "only idiots buy those things." Yeah, I have a lot of social graces to be sure. You try teaching teenagers ! After many years of being the "go to person" for math homework I am generally trusted in these things but can suck the air out of a room with "facts" and such. So off I went to write a quick code thingy that would output all possible tickets for a lottery that uses six numbers out of 49 total. The usual lotto649 garbage that people buy into up here in Canada. Furthermore I wanted to be able to output all possible tickets of six numbers from any group of ten numbers chosen, or twelve or whatever. I first looked around the net for code that others have probably written, this sort of thing over and over, and its old hat. Found a code chunk, cleaned it up and made it C99 ready with a few little enhancements. See the bottom of : http://stackoverflow.com/questions/8316479/combination-without-repetition-of-n-elements-without-use-for-to-do [ I'll put the source here also .. at the bottom ] Well the source there is exactly what I used to crack out all 13.9 million possible tickets in a lotto649 style. Works like a charm. What I did not see coming was a SEGV core dump on my T5240 when I started to push a few larger numbers at it thus : dev $ uname -a SunOS dev 5.10 Generic_147440-23 sun4v sparc SUNW,T5240 dev $ zonename z_004 dev $ mdigest -a sha1 combinations.c b5ca76095a364ab67bd86863b6f94e006909aae7 combinations.c dev $ echo $CFLAGS -errfmt=error -erroff=%none -errshort=full -errwarn=%all -xstrconst -xildoff -m64 -xmemalign=8s -xnolibmil -Xc -xcode=pic32 -xregs=no%appl -xlibmieee -mc -g -xs -ftrap=%none -Qy -xbuiltin=%none -xdebugformat=dwarf -xunroll=1 -xtarget=ultraT2 -xcache=8/16/4:4096/64/16 -D_TS_ERRNO -D_POSIX_PTHREAD_SEMANTICS -D_LARGEFILE64_SOURCE dev $ ls /opt/solarisstudio12.3/bin/c99 /opt/solarisstudio12.3/bin/c99 dev $ /opt/solarisstudio12.3/bin/fpversion A SPARC-based CPU is available. Kernel says CPU's clock rate is 1581.6 MHz. The clock rate is probably 14.3 MHz. Sun-4 floating-point controller version 0 found. An UltraSPARC chip is available. Use "-xtarget=generic -xcache=generic" code-generation option. Hostid = 0xbadcaffe <-- not really ;-) dev $ /opt/solarisstudio12.3/bin/c99 $CFLAGS -o combinations combinations.c dev $ elfdump -ed combinations ELF Header ei_magic: { 0x7f, E, L, F } ei_class: ELFCLASS64 ei_data: ELFDATA2MSB ei_osabi: ELFOSABI_SOLARIS ei_abiversion: EAV_SUNW_CURRENT e_machine: EM_SPARCV9 e_version: EV_CURRENT e_type: ET_EXEC e_flags: [ EF_SPARCV9_TSO EF_SPARC_SUN_US1 EF_SPARC_SUN_US3 ] e_entry: 0x100000980 e_ehsize: 64 e_shstrndx: 28 e_shoff: 0x33e0 e_shentsize: 64 e_shnum: 29 e_phoff: 0x40 e_phentsize: 56 e_phnum: 5 Dynamic Section: .dynamic index tag value [0] NEEDED 0xf7 libc.so.1 [1] INIT 0x100000fc0 [2] FINI 0x100000fd0 [3] RUNPATH 0x10a /usr/xpg6/lib/64:/usr/xpg4/lib/64 [4] RPATH 0x10a /usr/xpg6/lib/64:/usr/xpg4/lib/64 [5] HASH 0x100000178 [6] STRTAB 0x100000540 [7] STRSZ 0x32c [8] SYMTAB 0x100000270 [9] SYMENT 0x18 [10] CHECKSUM 0xe821 [11] VERNEED 0x100000870 [12] VERNEEDNUM 0x1 [13] PLTRELSZ 0xa8 [14] PLTREL 0x7 [15] JMPREL 0x1000008d0 [16] RELA 0x1000008d0 [17] RELASZ 0xa8 [18] RELAENT 0x18 [19] DEBUG 0 [20] FLAGS 0 0 [21] FLAGS_1 0 0 [22] SUNW_STRPAD 0x200 [23] SUNW_LDMACH 0x2b EM_SPARCV9 [24] PLTGOT 0x100101100 [25-35] NULL 0 dev $ dev $ /usr/bin/time -p ./combinations 49 6 > /tmp/lotto_649.dat real 77.38 user 75.63 sys 1.74 dev $ wc -l /tmp/lotto_649.dat 13983816 /tmp/lotto_649.dat That result is correct and WolframAlpha agrees : http://www.wolframalpha.com/input/?i=%28+49+!+%29+%2F+%28+%28+49+-+6+%29!++*++%28+6!+%29+%29 So then I pushed it a bit and eventually saw this : dev $ /usr/bin/time -p ./combinations 30 22 > /dev/null time: command terminated abnormally. real 0.49 user 0.00 sys 0.03 dev $ dbx combinations core Reading combinations core file header read successfully Reading ld.so.1 Reading libc.so.1 Reading libc_psr.so.1 program terminated by signal SEGV (no mapping at the fault address) 0xffffffff7ef63624: _malloc_unlocked+0x023c: ldx [%g5 + 16], %o1 Current function is printc 28 printf("{ "); (dbx) where [1] _malloc_unlocked(0x2010, 0x100101560, 0x100101560, 0x0, 0x0, 0x100101560), at 0xffffffff7ef63624 [2] malloc(0x2008, 0x23e0, 0x1dac88, 0x0, 0xffffffff7f13e000, 0x2000), at 0xffffffff7ef633c8 [3] _findbuf(0xffffffff7f1496b8, 0x0, 0x102, 0x2000, 0x1, 0x0), at 0xffffffff7efb7fd8 [4] _ndoprnt(0x100000fe8, 0xffffffff7ffff678, 0xffffffff7f1496b8, 0x0, 0x192fac, 0x2), at 0xffffffff7efab09c [5] printf(0x100000fe8, 0x0, 0x0, 0xffffffff7f1496dc, 0xffffffff7f13e000, 0x2), at 0xffffffff7efaef20 =>[6] printc(comb = 0x100101500, k = 22), line 28 in "combinations.c" [7] main(argc = 3, argv = 0xffffffff7ffff868), line 101 in "combinations.c" (dbx) (dbx) regs current frame: [6] g0-g1 0x0000000000000000 0x0000000600003f70 g2-g3 0x0000000000000000 0x0000000000000000 g4-g5 0x0000000600003f70 0x00000007001054d0 g6-g7 0x0000000000000000 0xffffffff7f100200 o0-o1 0x0000000100000fe8 0x0000000000000000 o2-o3 0x0000000000000000 0xffffffff7f1496dc o4-o5 0xffffffff7f13e000 0x0000000000000002 o6-o7 0xffffffff7fffedf1 0x0000000100000b0c l0-l1 0x0000000100000fe8 0x000000007f608000 l2-l3 0xffffffffffffffff 0xffffffff7f300768 l4-l5 0x0000000000001cc1 0x0000000000000000 l6-l7 0xffffffff7f14bfc4 0x00000001001010a8 i0-i1 0x0000000100101500 0x0000000000000016 i2-i3 0x0000000000000000 0xfffffffffffffff8 i4-i5 0x0000000000000000 0x0000000100101558 i6-i7 0xffffffff7fffeec1 0x0000000100000f28 y 0x0000000000000000 ccr 0x0000000000000099 pc 0x0000000100000b0c:printc+0x2c call printf [PLT] ! 0x1001011e0 npc 0xffffffff7ef63628:_malloc_unlocked+0x240 and %o1, -3, %o0 (dbx) quit dev $ Really ? There is plenty of memory here and no reason to dump core that I can see. In fact ... I went over to a Red Hat Enterprise Linux machine and tried the exact same test with the same code and .. no problem at all. So I am at a loss why the Solaris 10 based T5240 would dump core over this. For the sake of beeing really verbose and detailed I have run a pile of tests on both the RHEL box and the T5240 with identical results everywhere until I push the numbers a bit and whammo .. the T5240 dumps core. On the global zone of the server I see this : # uname -a SunOS t5240 5.10 Generic_147440-23 sun4v sparc SUNW,T5240 # psrinfo -pv The physical processor has 64 virtual processors (0-63) UltraSPARC-T2+ (chipid 0, clock 1582 MHz) The physical processor has 64 virtual processors (64-127) UltraSPARC-T2+ (chipid 1, clock 1582 MHz) # zonename global # coreadm global core file pattern: /var/crash/t5240/coredump/node_%n-host_%m-zone_%z-time_%t-pid_%p-uid_%u-gid_%g-fid_%f.core global core file content: all init core file pattern: /var/crash/t5240/coredump/node_%n-host_%m-zone_%z-time_%t-pid_%p-uid_%u-gid_%g-fid_%f.per-process-core init core file content: all global core dumps: enabled per-process core dumps: enabled global setid core dumps: enabled per-process setid core dumps: enabled global core dump logging: enabled # Message seen on the console when running the test with "30 22" parameters : # Dec 29 04:25:15 t5240 genunix: NOTICE: core_log: combinations[2267] core dumped: /var/crash/t5240/coredump/node_trend-dev-host_sun4v-zone_z_004-time_1356755115-pid_2267-uid_16411-gid_20002-fid_combinations.core That, should not happen. Any clues ? Dennis ------------------- combinations.c ----------------------------- /********************************************************************* * The Open Group Base Specifications Issue 6 * IEEE Std 1003.1, 2004 Edition * * An XSI-conforming application should ensure that the feature * test macro _XOPEN_SOURCE is defined with the value 600 before * inclusion of any header. This is needed to enable the * functionality described in The _POSIX_C_SOURCE Feature Test * Macro and in addition to enable the XSI extension. * * Compile with c99 or with gcc and CFLAGS to include options * -std=iso9899:199409 -pedantic-errors in order to ensure compliance * with ISO IEC 9899:1999 C spec. * * Code cleanup and transition to comb as a pointer to type ( int * ) * array by Dennis Clarke dcla...@blastwave.org 28 Dec 2012 * *********************************************************************/ #define _XOPEN_SOURCE 600 #include <stdio.h> #include <stdlib.h> /* Prints out a combination like {1, 2} */ void printc( int *comb, int k) { int j; printf("{ "); for ( j = 0; j < k; ++j ) printf("%d , ", *( comb + j * sizeof(int) ) + 1 ); printf( "\b\b}\n" ); } /* printc */ /********************************************************************** next_comb(int comb[], int k, int n) Generates the next combination of n elements as k after comb comb => the previous combination ( use (0, 1, 2, ..., k) for first) k => the size of the subsets to generate n => the size of the original set Returns: 1 if a valid combination was found 0, otherwise **********************************************************************/ int next_comb( int *comb, int k, int n) { int i = k - 1; ++*( comb + sizeof(int) * i ); while ( ( i >= 0 ) && ( *( comb + i * sizeof(int) ) >= n - k + 1 + i ) ) { --i; ++*( comb + i * sizeof(int) ); } if ( *comb > n - k) /* Combination (n-k, n-k+1, ..., n) reached */ return 0; /* No more combinations can be generated */ /* comb now looks like (..., x, n, n, n, ..., n). * Turn it into (..., x, x + 1, x + 2, ...) */ for (i = i + 1; i < k; ++i) *( comb + i * sizeof(int) ) = *( comb + ( i - 1 ) * sizeof(int) ) + 1; return 1; } /* next_comb */ int main(int argc, char *argv[]) { int *comb, i, n, k; n = 9; /* The size of the set; for {1, 2, 3, 4} it's 4 */ k = 6; /* The size of the subsets; for {1, 2}, {1, 3}, .. it's 2 */ if ( argc < 3 ) { printf ( "\nUSAGE : %s n k\n", argv[0] ); printf ( " : Where n is the set size and k the sub set size.\n" ); printf ( " : Note that k <= n\n" ); return ( EXIT_FAILURE ); } n = atoi ( argv[1] ); k = atoi ( argv[2] ); if ( k > n ) { printf ( "\nWARN : k > n is not allowed.\n" ); printf ( "USAGE : %s n k\n", argv[0] ); printf ( " : Where n is the set size and k the sub set size.\n" ); printf ( " : Note that k <= n\n" ); return ( EXIT_FAILURE ); } comb = ( int * ) calloc( (size_t) k, sizeof(int) ); for ( i = 0; i < k; ++i) *( comb + i * sizeof(int) ) = i; /* Print the first combination */ printc( comb, k ); /* Generate and print all the other combinations */ while ( next_comb( comb, k, n ) ) printc( comb, k ); free ( comb ); return ( EXIT_SUCCESS ); } -------- SHA1 hash = b5ca76095a364ab67bd86863b6f94e006909aae7 --------- _______________________________________________ opensolaris-code mailing list opensolaris-code@opensolaris.org http://mail.opensolaris.org/mailman/listinfo/opensolaris-code
