/* * 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 * * Created by Michael Feiri on Thu Jan 03 2002. * Copyright (c) 2002 Michael Feiri. All rights reserved. * */ #include #include "first0.h" /* LOOKUP_FIRSTBLANK */ #define BITOFLIST(x) (0x80000000>>((x-1)&0x1f)) /*0x80000000 >> ((x-1) % 32)*/ #define NUMWORDS 8 /* 8 words (8*32=256) -> 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 tweakedGARSP(int maxmarks, int maxlength); /* prototype */ unsigned int tweakedGARSP(int maxmarks, int maxlength) { int depth; /* current mark we are placing corresponds to the D in the PDF */ unsigned 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; /* 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) { 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) > maxlength) 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) > maxlength) 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; printf("FOUND A RULER!!!\n"); for(i=0; i<=maxmarks; i++ ) printf("%4d",count[i]); printf("\n"); continue; /* go back to the start of our while(1) loop*/ } 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; } #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("\ntweakedGARSP started...\n"); starttime = dtime(); nodes = tweakedGARSP(10,72); benchtime = dtime() - starttime; printf("Nodes per second = %.3f ( %u nodes/ %.3f seconds)\n",nodes/benchtime,nodes,benchtime); return 0; } #endif