/* * tweakedGARSP.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) * * A safety net was installed to allow searching for large rulers without enlarging the bitmap size * - verify the golombness of found rulers * - introduced sanity checks to guarantee the safe operation * * Created by Michael Feiri on Thu Jan 03 2002. * Copyright (c) 2002 Michael Feiri. All rights reserved. * */ #define NUMWORDS 3 /* 2 words (2*32=64) -> we can create rulers up to a length of 64-1=63 */ /* but thanks to principle 1 we can create rulers up to ((64*2)-1)=127 */ #define MAXMARKS 19 /* depth of stacks -> we can place up to 18 marks (plus the "0" mark means OGR-19) */ #define NUMDIFFS 32 /* size of the array where I can verify the golombness of rulers */ /* e.g. with NUMDIFFS 8 we can safely search for rulers up to 16 units longer */ #include #include /* */ #include "bitmaps32.h" /* BITMAP */ #include "limits_steps.h" /* LIMITS */ /* 1, 65 -> no tests necessary (maintaned in bitmaps) 66, 129 -> no tests necessary (principle 1) 130, 131 -> 65 may occur twice (need diffs[1]) 132, 133 -> 65,66 may occur twice (need diffs[2]) 134, 135 -> 65,66,67 may occur twice (need diffs[3]) ((NUMWORDS*32*2)+1)+(NUMDIFFS*2) The left part represents the real size of our bitmaps (times 2, thanks to principle 1) The right part represents the size of our overfolw test (times 2, thanks to principle 1) */ static uint32_t halfTweakedGARSP(const int maxmarks, const int maxlength); /* prototype */ void binary (unsigned int value) { int index; for(index=0;index<32;index++) { if(value & 0x80000000) { printf("1"); } else { printf("0"); } value = value << 1; } } static uint32_t halfTweakedGARSP(const int maxmarks, const int maxlength) { int depth=1; /* current mark we are placing corresponds to the D in the PDF */ signed int count[MAXMARKS]={0}; /* current ruler length (e.g. LENGTH[])*/ uint32_t nodes=0; SETUP_BITMAPS; /* THIS SEMICOLON MUST GO IF YOU WANT TO COMPILE USING GCC2 */ SETUP_LIMITS; if ((maxlength/2)-(NUMWORDS*32) > NUMDIFFS) { /* sanity check -> size of bitmaps */ printf("Your NUMWORDS(%d) including the overflow space in NUMDIFFS(%d) are too short\n",NUMWORDS,NUMDIFFS); printf("Your current limit is ((NUMWORDS*32*2)+1)+(NUMDIFFS*2)=%d\n",(((NUMWORDS*32*2)+1)+(NUMDIFFS*2))); printf("You can either use more bitmaps (NUMWORDS) or enlarge the overflow test (NUMDIFFS)\n"); return 0; } else if (maxmarks>=MAXMARKS) { /* sanity check -> depth of stack */ // Most compilers would allow maxmarks==MAXMARKS because the 0-level of our arrays if never used. Therefor // it wouldnt matter if for example the list[] array spills one level into (the 0-level of) the dist[] array. // But for safety reasons we enforce the logical limit. // The reason why we keep the 0-level is to maintain readability of the code and because count[0] is actually used. printf("With MAXMARKS=%d you can only search up to OGR-%d but you requested OGR-%d\n",MAXMARKS,MAXMARKS,maxmarks+1); printf("Just raise the MAXMARKS setting and you are fine"); return 0; } else if (maxmarks>32) { /* sanity check -> OGR[] limit (the CHOOSE[] limit is selfregulating) */ // Example: OGR-13 (at position OGR[13-1=12]) is the highest value used in a search for OGR-14 // As of this writing lists of currently known optimal ruler sizes are publically available from // http://www.cuug.ab.ca/~millerl/g3-records.html and http://www.research.ibm.com/people/s/shearer/grtab.html // Alternatively one could always use the naively constructed ruler 0,1,3,7,15,31,63,127,255,511,1023,.... printf("In a search for OGR-(N) you must provide the limits for all rulers up to OGR-(N-1)"); printf("Note that these limits (in the OGR[] array) dont need to be prooven optimal"); printf("But the better your limits are the more can you reduce the searchspace"); return 0; } INTITIALIZE_BITMAPS; CALCULATE_LIMITS; /* search through the search space **** */ do { while (1) { nodes++; //{ // int i; for(i=0; i<=depth; i++ ) printf("%4d",count[i]); printf(" before(depth=%d)\n",depth); // printf("DIST: ");binary(dist[depth][0]);/*binary(dist[depth][1])*/;printf("\n"); // printf("LIST: ");binary(list[depth][0]);/*binary(list[depth][1]);*/printf("\n"); // printf("COMP: ");binary(comp[depth][0]);/*binary(comp[depth][1]);*/printf("\n"); //} stay: SET_NEXT_MARK; //comp0 // if (comp[depth][0] < 0xfffffffe) { // int s = LOOKUP_FIRSTBLANK( comp[depth][0] ); // if ((count[depth] += s) > limit[depth]) {break;} /* no spaces left */ // CLLR_XX_BITMAPS; // } else { /* s>=32 */ // if ((count[depth] += 32) > limit[depth]) {break;} /* no spaces left */ // CLLR_32_BITMAPS; // } //{ // int i; for(i=0; i<=depth; i++ ) printf("%4d",count[i]); printf(" after\n"); // printf("DIST: ");binary(dist[depth][0]);/*binary(dist[depth][1])*/;printf("\n"); // printf("LIST: ");binary(list[depth][0]);/*binary(list[depth][1]);*/printf("\n"); // printf("COMP: ");binary(comp[depth][0]);/*binary(comp[depth][1]);*/printf("\n\n"); //} if (depth == (maxmarks)) { int i,j; char diffs[NUMDIFFS]={0}; // can store diffs up to and including 32 for (i=1; i <= maxmarks; i++) { for (j=0; j(NUMWORDS*32))) { diff -= (NUMWORDS*32)+1; /* we want to start saving at position 0 rather than 1 */ if (diffs[diff]!=0) { goto stay; } diffs[diff] = 1; } } } #if defined(STORE_DIST) STORE_DIST; #else printf("FOUND A RULER!!!\n"); for(i=0; i<=maxmarks; i++ ) printf("%4d",count[i]); printf("\n"); #endif } else { /* #define depthm1 depth-1 depth++; //int depthm1=depth++; // one level deeper count[depth] = count[depthm1]; // pass on our current length DEEPER_BITMAPS_FIRST_WORD; CALCULATE_LIMITS; //if(limit[depth]<=count[depth]) {break;} DEEPER_BITMAPS_REST; //if (limit[depth]<=count[depth]) {UP_BITMAPS;depth--;} else {DEEPER_BITMAPS_REST;} */ DEEPER_BITMAPS; count[depth+1] = count[depth]; // pass on our current length depth++; // one level deeper CALCULATE_LIMITS; //if((limit[depth]-count[depth])<=0) {newbit=0;depth--;continue;} //{nodes++;break;} //if(limit[depth]<=count[depth]) {break;} //{nodes++;break;} /* // mit diesem setup kommt stay nie in die verlegenhnheit garkeinen treffer zu landen // daher kann der zwang newbit auf null zu setzen falls // if((count[depth]+=s)>limit[depth]){newbit=0; break;} entfallen. */ } //if((limit[depth]-count[depth])<=0) {printf("JH\n");} } UP_BITMAPS; } while (--depth>0); return nodes; } #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; uint32_t nodes; printf("\nhalfTweakedGARSP started...\n"); starttime = dtime(); //nodes = halfTweakedGARSP(1,1); //nodes = halfTweakedGARSP(2,3); //nodes = halfTweakedGARSP(3,6); //nodes = halfTweakedGARSP(4,11); //nodes = halfTweakedGARSP(5,17); //nodes = halfTweakedGARSP(6,25); //nodes = halfTweakedGARSP(7,34); //nodes = halfTweakedGARSP(8,44); //nodes = halfTweakedGARSP(9,55); //nodes = halfTweakedGARSP(10,72); //nodes = halfTweakedGARSP(11,85); //nodes = halfTweakedGARSP(12,106); //nodes = halfTweakedGARSP(13,127); nodes = halfTweakedGARSP(14,151); //nodes = halfTweakedGARSP(15,177); benchtime = dtime() - starttime; printf("Nodes per second = %.3f ( %u nodes/ %.3f seconds)\n",nodes/benchtime,nodes,benchtime); return 0; } #endif