/* * plainSHIFT.c * * A clean implementation of the SHIFT algorithm * * Created by Michael Feiri on Sat Dec 29 2001. * Copyright (c) 2001 Michael Feiri. All rights reserved. * */ #include #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 plainSHIFT(int maxmarks, int maxlength); /* prototype */ unsigned int plainSHIFT(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 temp0,temp1; /* temporary variables for shifting */ 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]=0x80000000; /* 10000000000000000000000000000000 */ 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; /* search through the search space **** */ while (1) { nodes++; /*if the length of our ruler does not exceeds the maximum length we can proceed */ if (++count[depth] <= maxlength/* SearchSpaceReduction(3.3) maxlimit[depth]*/) { /* Check if LIST[D]&DIST[D]=0 ( we can set a new mark ) */ if ( ((list[depth][0] & dist[depth][0]) == 0) && ((list[depth][1] & dist[depth][1]) == 0) && ((list[depth][2] & dist[depth][2]) == 0) && ((list[depth][3] & dist[depth][3]) == 0) && ((list[depth][4] & dist[depth][4]) == 0) && ((list[depth][5] & dist[depth][5]) == 0) && ((list[depth][6] & dist[depth][6]) == 0) && ((list[depth][7] & dist[depth][7]) == 0) ) { /* set the new DIST[D+1] */ dist[depth+1][0] = list[depth][0] | dist[depth][0]; dist[depth+1][1] = list[depth][1] | dist[depth][1]; dist[depth+1][2] = list[depth][2] | dist[depth][2]; dist[depth+1][3] = list[depth][3] | dist[depth][3]; dist[depth+1][4] = list[depth][4] | dist[depth][4]; dist[depth+1][5] = list[depth][5] | dist[depth][5]; dist[depth+1][6] = list[depth][6] | dist[depth][6]; dist[depth+1][7] = list[depth][7] | dist[depth][7]; /* set the new LIST[D] and LIST[D+1] */ temp0 = (list[depth][0] & 1) << 31; list[depth][0] = (list[depth][0] >> 1); list[depth+1][0] = list[depth][0] | 0x80000000; temp1 = (list[depth][1] & 1) << 31; list[depth][1] = (list[depth][1] >> 1) | temp0; list[depth+1][1] = list[depth][1]; temp0 = (list[depth][2] & 1) << 31; list[depth][2] = (list[depth][2] >> 1) | temp1; list[depth+1][2] = list[depth][2]; temp1 = (list[depth][3] & 1) << 31; list[depth][3] = (list[depth][3] >> 1) | temp0; list[depth+1][3] = list[depth][3]; temp0 = (list[depth][4] & 1) << 31; list[depth][4] = (list[depth][4] >> 1) | temp1; list[depth+1][4] = list[depth][4]; temp1 = (list[depth][5] & 1) << 31; list[depth][5] = (list[depth][5] >> 1) | temp0; list[depth+1][5] = list[depth][5]; temp0 = (list[depth][6] & 1) << 31; list[depth][6] = (list[depth][6] >> 1) | temp1; list[depth+1][6] = list[depth][6]; list[depth][7] = (list[depth][7] >> 1) | temp0; list[depth+1][7] = list[depth][7]; /* did we find a ruler with the desired number of marks golomb? */ if (depth == (maxmarks)){ int i; printf("FOUND A RULER!!!\n"); for(i=0; i<=maxmarks; i++ ) printf("%4d",count[i]); printf("\n"); } /* if we didnt distribute all marks we need to go deeper... */ else { count[depth+1] = count[depth]; /* pass on our current length */ depth++; /* one level deeper */ /* SearchSpaceReduction (3.4) while(count[depth] < minlimit[depth] -1) { temp0 = (list[depth][0] & 1) << 31; list[depth][0] = (list[depth][0] >> 1); temp1 = (list[depth][1] & 1) << 31; list[depth][1] = (list[depth][1] >> 1) | temp0; temp0 = (list[depth][2] & 1) << 31; list[depth][2] = (list[depth][2] >> 1) | temp1; temp1 = (list[depth][3] & 1) << 31; list[depth][3] = (list[depth][3] >> 1) | temp0; temp0 = (list[depth][4] & 1) << 31; list[depth][4] = (list[depth][4] >> 1) | temp1; temp1 = (list[depth][5] & 1) << 31; list[depth][5] = (list[depth][5] >> 1) | temp0; temp0 = (list[depth][6] & 1) << 31; list[depth][6] = (list[depth][6] >> 1) | temp1; list[depth][7] = (list[depth][7] >> 1) | temp0; count[depth]++; } */ continue; /* go to the start of our while(1) loop the choose[depth] will be incremented by one (e.g. the length of our ruler) */ } } /* LIST[D]&DIST[D]!=0 ergo we need to shift the entire LIST[] array one to the right */ else { nodes--; /* we only want to have the number of checked valid rulers */ temp0 = (list[depth][0]) << 31; list[depth][0] = (list[depth][0] >> 1); temp1 = (list[depth][1]) << 31; list[depth][1] = (list[depth][1] >> 1) | temp0; temp0 = (list[depth][2]) << 31; list[depth][2] = (list[depth][2] >> 1) | temp1; temp1 = (list[depth][3]) << 31; list[depth][3] = (list[depth][3] >> 1) | temp0; temp0 = (list[depth][4]) << 31; list[depth][4] = (list[depth][4] >> 1) | temp1; temp1 = (list[depth][5]) << 31; list[depth][5] = (list[depth][5] >> 1) | temp0; temp0 = (list[depth][6]) << 31; list[depth][6] = (list[depth][6] >> 1) | temp1; list[depth][7] = (list[depth][7] >> 1) | temp0; } /* Go back to the start of our while(1) loop the count[depth] will be incremented by one (e.g. the length of our ruler) */ } /*if the length of our ruler exceeds the maximum length we need to go up one depth */ else { if (--depth == 0) return nodes;/* break; // EXIT if we reached end of search space */ } } return nodes; /* never reached */ } #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("plainSHIFT started...\n"); starttime = dtime(); nodes = plainSHIFT(10,72); benchtime = dtime() - starttime; printf("Nodes per second = %.3f ( %u nodes / %.3f seconds )\n",nodes/benchtime,nodes,benchtime); return 0; } #endif