/* * reducedTweakedGARSP.c * * An optimized implementation of the GARSP algorithm. * - LOOKUP_FIRSTBLANK() macro replaces the first[] array * - BITOFLIST() macro replaces the bit[] lookup table * - Merged search for s and the shift of LIST and COMP * - Use temporary variables to shift LIST and COMP * * Additionally a number of search space reduction techniques were applied (as limit) * - midpoint reduction (eliminate mirror images) * - centerpoint reduction (eliminate center symmetry) * - OGR limit (the remaining space must be enough to hold the OGR for the remaing marks) * - CHOOSE limit (the remainig space must be enough to hold the smallest remaining distances) * * Created by Michael Feiri on Sat Jan 26 2002. * Copyright (c) 2002 Michael Feiri. All rights reserved. * */ #include #include "first0.h" /* LOOKUP_FIRSTBLANK */ #include "chooseV3_12_12.h" /* CHOOSE */ #define BITOFLIST(x) (0x80000000>>((x-1)&0x1f)) /*0x80000000 >> ((x-1) % 32)*/ #define MINIMUM(x,y) ((x we can create rulers up to a length of 255 */ /* but thanks to "principle #1" we can safely get rulers up to (256*2)-1=511 */ #define MAXMARKS 19 /* depth of stacks -> we can place up to 18 marks (plus the "0" mark means OGR-19) */ unsigned int reducedTweakedGARSP(int maxmarks, int maxlength); /* prototype */ unsigned int reducedTweakedGARSP(int maxmarks, int maxlength) { int hack = 0; int depth; /* current mark we are placing corresponds to the D in the PDF */ int count[MAXMARKS]; /* current ruler length (e.g. LENGTH[])*/ unsigned int list[MAXMARKS][NUMWORDS]; /* list bitmap */ unsigned int dist[MAXMARKS][NUMWORDS]; /* dist bitmap */ unsigned int comp[MAXMARKS][NUMWORDS]; /* dist bitmap */ unsigned int nodes=0; int limit; const int halfdepth=(maxmarks/2); const int halflength=(!(maxmarks%2) && (maxlength%2)) ? (maxlength/2) : (maxlength/2)-1; //const int halflength=(maxlength/2); const int OGR[] = { /* 1 */ 0, 1, 3, 6, 11, 17, 25, 34, 44, 55, 72, /* 12 */ 85, 106, 127, 151, 177, 199, 216, 246, 283, 333, 356, /* 23 */ 372, 425, 480, 492, 553, 585, 623, 680, 747, 784 }; /* Start at the very beginning (one mark set at position zero) */ depth = 1; count[0] = 0; count[1] = 0; list[depth][0]=0; list[depth][1]=0; list[depth][2]=0; list[depth][3]=0; list[depth][4]=0; list[depth][5]=0; list[depth][6]=0; list[depth][7]=0; dist[depth][0]=0; dist[depth][1]=0; dist[depth][2]=0; dist[depth][3]=0; dist[depth][4]=0; dist[depth][5]=0; dist[depth][6]=0; dist[depth][7]=0; comp[depth][0]=0; comp[depth][1]=0; comp[depth][2]=0; comp[depth][3]=0; comp[depth][4]=0; comp[depth][5]=0; comp[depth][6]=0; comp[depth][7]=0; /* search through the search space **** */ while (1) { /* CHOOSE */ if (CHOOSEMARKS>maxmarks-depth) { limit = maxlength-chooseV3[((dist[depth][0])>>(32-CHOOSEBITS))][(maxmarks-depth)]; } else { limit = maxlength-OGR[maxmarks-depth]; // midpoint reduction may supercede this } /* MIDPOINT */ if (depth<=halfdepth) { int tempLimit; // if (CHOOSEMARKS>halfdepth-depth) { // tempLimit = halflength-chooseV3[((dist[depth][0])>>(32-CHOOSEBITS))][(halfdepth-depth)]; // } else { tempLimit = halflength-OGR[halfdepth-depth]; // } limit=MINIMUM(limit,tempLimit); // if (depth==halfdepth) { // limit=MINIMUM(limit,halflength); } else if ((depth==(halfdepth+1)) && (maxmarks%2)) { int tempLimit; tempLimit = maxlength-1-count[halfdepth]; limit=MINIMUM(limit,tempLimit); //printf("l%d r%d\n",count[halfdepth],maxlength-1-count[halfdepth]); } nodes++; /* Find s = the next available mark location for this level */ /* shift LIST s steps to the right and shift COMP s steps to the left */ stay: if (comp[depth][0] < 0xfffffffe) { int s = LOOKUP_FIRSTBLANK( comp[depth][0] ); if ((count[depth] += s) > limit) goto up; /* no spaces left */ /*EXTEND_MARK(lev, s); *//* shift by s (LIST to the right, COMP to the left) */ { unsigned int temp0, temp1; register int ss=32-s; temp0 = (list[depth][0]) << ss; list[depth][0] = (list[depth][0] >> s); temp1 = (list[depth][1]) << ss; list[depth][1] = (list[depth][1] >> s) | temp0; temp0 = (list[depth][2]) << ss; list[depth][2] = (list[depth][2] >> s) | temp1; temp1 = (list[depth][3]) << ss; list[depth][3] = (list[depth][3] >> s) | temp0; temp0 = (list[depth][4]) << ss; list[depth][4] = (list[depth][4] >> s) | temp1; temp1 = (list[depth][5]) << ss; list[depth][5] = (list[depth][5] >> s) | temp0; temp0 = (list[depth][6]) << ss; list[depth][6] = (list[depth][6] >> s) | temp1; list[depth][7] = (list[depth][7] >> s) | temp0; temp1 = (comp[depth][7]) >> ss; comp[depth][7] = (comp[depth][7] << s); temp0 = (comp[depth][6]) >> ss; comp[depth][6] = (comp[depth][6] << s) | temp1; temp1 = (comp[depth][5]) >> ss; comp[depth][5] = (comp[depth][5] << s) | temp0; temp0 = (comp[depth][4]) >> ss; comp[depth][4] = (comp[depth][4] << s) | temp1; temp1 = (comp[depth][3]) >> ss; comp[depth][3] = (comp[depth][3] << s) | temp0; temp0 = (comp[depth][2]) >> ss; comp[depth][2] = (comp[depth][2] << s) | temp1; temp1 = (comp[depth][1]) >> ss; comp[depth][1] = (comp[depth][1] << s) | temp0; comp[depth][0] = (comp[depth][0] << s) | temp1; } } else { /* s>=32 */ if ((count[depth] += 32) > limit) goto up; /* no spaces left */ /*EXTEND_MARK_BY_WORD(lev); *//* shift by s (LIST to the right, COMP to the left) */ { unsigned int temp = comp[depth][0]; { comp[depth][0] = comp[depth][1]; comp[depth][1] = comp[depth][2]; comp[depth][2] = comp[depth][3]; comp[depth][3] = comp[depth][4]; comp[depth][4] = comp[depth][5]; comp[depth][5] = comp[depth][6]; comp[depth][6] = comp[depth][7]; comp[depth][7] = 0; list[depth][7] = list[depth][6]; list[depth][6] = list[depth][5]; list[depth][5] = list[depth][4]; list[depth][4] = list[depth][3]; list[depth][3] = list[depth][2]; list[depth][2] = list[depth][1]; list[depth][1] = list[depth][0]; list[depth][0] = 0; } if (temp == 0xffffffff) goto stay; } } /* did we find a ruler with the desired number of marks? */ if (depth == (maxmarks)) { int i; hack++; printf("FOUND A RULER!!!(%d)\n",hack); for(i=0; i<=maxmarks; i++ ) printf("%4d",count[i]); printf("\n"); continue; //goto stay; /* continue the search on the same level*/ } else { /* if we didnt distribute all marks we need to go deeper...*/ /* prepare LIST[D+1]=LIST+(new_mark)*/ list[depth+1][0] = list[depth][0]; list[depth+1][1] = list[depth][1]; list[depth+1][2] = list[depth][2]; list[depth+1][3] = list[depth][3]; list[depth+1][4] = list[depth][4]; list[depth+1][5] = list[depth][5]; list[depth+1][6] = list[depth][6]; list[depth+1][7] = list[depth][7]; { int d = count[depth]-count[depth-1]; if( d <= 32 ) { list[depth+1][0] = list[depth][0] + BITOFLIST(d); } else if( d <= 64 ) { list[depth+1][1] = list[depth][1] + BITOFLIST(d); } else if( d <= 96 ) { list[depth+1][2] = list[depth][2] + BITOFLIST(d); } else if( d <= 128 ) { list[depth+1][3] = list[depth][3] + BITOFLIST(d); } else if( d <= 160 ) { list[depth+1][4] = list[depth][4] + BITOFLIST(d); } else if( d <= 192 ) { list[depth+1][5] = list[depth][5] + BITOFLIST(d); } else if( d <= 224 ) { list[depth+1][6] = list[depth][6] + BITOFLIST(d); } else /*if( d <= 256 )*/ { list[depth+1][7] = list[depth][7] + BITOFLIST(d); } } /* prepare the new DIST[D+1]=DIST|LIST[D+1]*/ dist[depth+1][0] = list[depth+1][0] | dist[depth][0]; dist[depth+1][1] = list[depth+1][1] | dist[depth][1]; dist[depth+1][2] = list[depth+1][2] | dist[depth][2]; dist[depth+1][3] = list[depth+1][3] | dist[depth][3]; dist[depth+1][4] = list[depth+1][4] | dist[depth][4]; dist[depth+1][5] = list[depth+1][5] | dist[depth][5]; dist[depth+1][6] = list[depth+1][6] | dist[depth][6]; dist[depth+1][7] = list[depth+1][7] | dist[depth][7]; /* prepare COMP[D+1]=COMP|DIST[D+1]*/ comp[depth+1][0] = dist[depth+1][0] | comp[depth][0]; comp[depth+1][1] = dist[depth+1][1] | comp[depth][1]; comp[depth+1][2] = dist[depth+1][2] | comp[depth][2]; comp[depth+1][3] = dist[depth+1][3] | comp[depth][3]; comp[depth+1][4] = dist[depth+1][4] | comp[depth][4]; comp[depth+1][5] = dist[depth+1][5] | comp[depth][5]; comp[depth+1][6] = dist[depth+1][6] | comp[depth][6]; comp[depth+1][7] = dist[depth+1][7] | comp[depth][7]; count[depth+1] = count[depth]; /* pass on our current length*/ depth++; /* one level deeper*/ continue; /* go back to the start of our while(1) loop*/ } up: if (--depth == 0) return nodes;/* EXIT if we reached end of search space */ } return nodes; } #undef AS_MODULE #ifndef AS_MODULE #include #include double dtime() { struct rusage rusage; double q; getrusage(RUSAGE_SELF,&rusage); q = (double)(rusage.ru_utime.tv_sec); q = q + (double)(rusage.ru_utime.tv_usec) * 1.0e-06; return q; } int main (int argc, const char * argv[]) { double starttime, benchtime; unsigned int nodes; printf("\nreducedTweakedGARSP started...\n"); starttime = dtime(); nodes = reducedTweakedGARSP(13,127); benchtime = dtime() - starttime; printf("Nodes per second = %.3f ( %u nodes/ %.3f seconds)\n",nodes/benchtime,nodes,benchtime); return 0; } #endif