/*----------( GARSP Program Documentation )-----------------------
   GARSP.C is a program to find golomb and optimal golomb rulers

   This program is designed to solve the "Golomb Ruler" problem
   described in the December 1985 Scientific American.  Golomb
   Rulers contain marks placed at locations such that no same
   distance can be measured by two different sets of marks.  These
   (and Sparse Rulers ... where all distances from 1-n must be
   measurable) have applications in sensor placements, such as
   interstellar radio antenna and radar receivers.

   Credit for this program goes to a number of individuals.  It's
   basic approach is a composite of work by myself (Mark Garry) and
   numerous others, as follows:

   The bitmap approach was first developed/published by David
   McCracken (working at Duke at the time).  He suggested using
   two bitmaps, the first --called DIST-- being coded left to right
   with the differences taken (coded as a 1) or available (coded as
   a zero).  Thus, to search for the optimal 20 mark ruler took >= 283
   bits, or 9 (32 bit) bitmaps.  When completed, the DIST array would
   contain 19*20/2 = 190 "1" bits and 9*32-190 empty "0" bits.  (The
   first because a golomb ruler measures n*(n-1)/2 distances, where
   n = number of marks, and the second is by difference.

   The second bitmap was called called LIST and was coded right to
   left with the distance from one mark to the next.  Thus, LIST is
   a bitmap of the actual marks used in the ruler (versus the DIST
   array which tracks the measured differences between the marks) and
   when completed would contain 20 "1" bits for a 20 mark ruler.

   By anding DIST and LIST and appropriately shifting the LIST vector
   to the right after each new mark is placed, we can easily keep
   both of these lists updated.  The approach was termed the SHIFT
   algorithm.  (Further details are available in the IEEE Paper and
   Thesis notes by Apostolos Dollas, William T Rankin and David
   McCracken (see the link from the web page:
   "http://members.aol.com/golomb20").

   With the DIST and LIST bitmaps, to place a mark we need only
   see if the bit locations in DIST are available.  If not, we
   need to shift the LIST vector once more and try ANDing again.

   Following the work at Duke, Mark Garry and David Vanderschel
   created a program called GVANT, which took a radicallly different
   approach and used integer based calculations.  Although it was much
   faster than the earlier SHIFT routine, we continued to examine
   bitmap approaches, and generated several programs in the interim.
   A lot of the basis of this program, such as the use of look-up
   tables, and the careful approach to making sure we do not use
   shift operations such as x>>32, which is undefined) comes from
   earlier programs (e.g., MYLGRUP) written by David.

   After publishing GVANT to the WEB, conversations with Apostolos
   Dollas led us back into considering ways to improve SHIFT.
   Roland Adorni (Rado), also a major contributer to GVANT, made the
   BIG breakthrough.  He suggested a third bitmap array (which I
   call COMP) which could be used to predetermine all possible
   candidates for positioning a mark.  I.e., we no longer needed
   to AND the LIST and DIST just to see if any bits collide.  We
   already know.  (And thus was born the name GARSP, an acronym
   for Garry's Adaptation of Rado's Search Priciples).

   The COMP bitmap is created by ANDing the previous level's COMP
   (shifted by the last 1-diff placed) with the current DIST.  This
   simple yet profound discovery is based on Principle 3, listed below.

   Combined on top of all the bitmap work is a general structure
   gleaned from other programs.  For instance, we use of predefined
   arrays to "look up" results of often used calculations (for
   instance, the first bit available in a bitmap).  We also implement
   the mirror reduction routine developed for GVANT.  And we use several
   principles (outlined below) to limit the focus of the calculations
   to just 1/2 of the ruler at any time.

   Special thanks go to the following individuals (and others)
   who helped to write, correct, and/or beta test the code (listed
   in alphabetical order): Roland Adorni, John Bafford, Nate Begeman,
   Uwe Falck, Mark Garry, Mike Kessler, Lloyd Miller, Paul Nord, and
   David Vanderschel.  See update notes below for additional credits!

                              * - * - *

   The following three principles are used to reduce computations.
   The first and second describe why we need only worry about
   bitmaps that are at most half of the total ruler length, and ofttimes
   can be much less.  It also explains why --in the case of rulers longer
   than half the length of the bitmaps-- the differences only need be
   checked from "bitmap length + 1" through "ruler length/2" to
   ensure we have a good ruler.  The third describes why the COMP
   array works.


   Principle-1

      If two 'spans' [a,b] and [c,d] have the same length and
      overlap, then the two non-overlapping segments [a,c] and
      [b,d] must also be equal:

          a---------------b
                c---------------d
          a-----c         b-----d

      If we have have tested the non-overlapping segments [a,c]
      and [b,d] and found them not equal, there is no need to
      test the larger segments.

      Implication: Since we work sequentially from the left side of
      the ruler we can see that if d is a new candidate mark position,
      then we need never consider (as a possible repeated difference)
      any difference d-c, where c is a placed mark position and c < d/2.

   Principle-2

      Let nf represent the largest possible span from the most recently
      placed mark to the right edge of the ruler.  Based on Principle-1,
      we know that the largest possible (non-overlapping) distance that
      we will need to check going forward from here is nf.

      Implication: when placing a mark, there is no need to account for
      any newly introduced differences in excess of nf, as we need never
      (subsequently) test against such differences.

   Principle-3

      Assume we cannot append a X 1-diff at a given point on the ruler
      without violating a constraint (i.e., the mark's location is invalid).
      If we instead append a smaller 1-diff equal to Y, then we cannot
      immediately afterwards append a 1-diff equal to X-Y.  Now let all
      further mark placements abide by this same rule, and inherit the
      same limitations.

   ----------------------------------------------------------------

   Usage:

   First create or download the CHOOSE.DAT file
       use "choose3.c" or download via links supplied at:
           http://members.aol.com/golomb20/download.htm
       note: choose[N][0]= OGR length of N segments, where 0<=N<=10

   Next create a file called SAVE.TXT with the following contents:
      X Y   Z1 Z2 ... Zn     -Y1 -Y2 ... -Yn

      X = The OGR number of marks         (e.g., 21)
      Y = The maximum length to consider  (e.g., 332 or can use -1)
      Z1 Z2 ... Zn = The starting stub    (e.g., 1 3 or can skip)
      Z1 Z2 ... Zn = The ending stub      (e.g., 1 7 or can skip)

   Finally, run GARSP:
      garsp  [optional paramaters available in non-MAC versions]
             To see the run time options, enter "garsp z z"

   Output is sent into 2 files:
      send.txt            please forward these to us for OGR-21 search
      newruler.txt        a backup file that saves found rulers in case
                             you accidentally delete send.txt  :)

   ----------------------------------------------------------------

   Post-Release Notes:

    - Added VC5 "__cdecl" declarations for main() and MyHandler()

    Version 5.13
    March 28, 1998 ... M.Garry

    - Based on suggestions from David Vanderschel and Markus Baumeister,
      added a signal handler routine.

    - Added CRC check for choose.dat file (code supplied by Alexey Guzeev)

    - Unified the way "idle" priorities were being set between OS/2 & Win

    - Reinstated the code that verifies "golombness" prior to printing.


    March 22, 1998 ... M.Garry

    - Based on heavy input from Markus Baumeister, unrolled the
      recursion loops based on the the number of bitmaps required.
      Later added the multiple leaps (e.g., from 5 to 3).  Result
      is 20-25% performance boost.  Retained a lot of unnecessary
      stuff (e.g., checks if d>64 when it cannot be) because the run-
      time cost is insignificant, and it helps users "SEE" the code.

    - Also added the DD parameter for leaping "before we should" to
      get *another* 25% performance boost.  This requires we verify
      more rulers generated to make sure they are Golomb.

    - Based on heavy input from Daniel Lovinger and Matt Thomlinson,
      added the WinNT code for memory mapped IO, and Win specific
      code enhancement.

    Version 5.12
    February 20, 1998, Program released ... M. Garry

      This invocation of the program uses FIVE 32 bit bitmaps, and
      can account for differences of up to 160, and therefore rulers
      of about 340 in length.  For shorter rulers (e.g., OGR-19),
      fewer bitmaps are more optimal.  For longer rulers, more bitmaps
      are needed.  A 64 bit version is available, which needs half
      as many bitmaps.


   ----------------------------------------------------------------*/

/*-----INCLUDES----*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
/* #include <assert.h> */
#include <signal.h>

#ifdef OS2
#define INCL_DOSPROCESS
#include <os2.h>
#endif

#ifdef WIN32
#include <windows.h>
#endif

#ifdef TIMINGTEST
#include <sys/timeb.h>
struct timeb start2,finish2;
#endif



/*-----TYPEDEFs-----*/
typedef unsigned long U;


/*-----DEFINES-----*/
/* #define NDEBUG */      /* disable assert()s and some debugging outputs */
#define OGR21             /* This sets the code to run fastest for OGR-21 */
#define MAXDEPTH  23      /* Leave this as is for OGR-21 */
#define choose(x,y) (choosedat[11*(x)+(y)])

#ifdef WIN32
#define MEMORY_MAPPED_IO 1 /* used for winNT version of Memory Mapped IO */
#endif
#ifdef SOME_OTHER_OS
#define MEMORY_MAPPED_IO 2 /* used for SOME_OTHER_SYSTEM */
#endif

#define OR |              /* Use as test: "+" better give same answer! */
#define DD 32             /* used to cut # of bitmaps early */
/*-----------------------------------------------------------------
 Using standard test of "21 332 2 22 32 21 -2 -22 -32 -21"
 #define DD 36 -> 199 seconds
 #define DD 32 -> 197 seconds   (this appeared about optimal)
 #define DD 28 -> 199 seconds
 #define DD 20 -> 205 seconds
 #define DD 16 -> 209 seconds
 #define DD 10 -> 216 seconds
 #define DD  0 -> 229 seconds   (This was base case)

 theory: DD quickens the pace of reducing # of bitmaps in use.
         This can cause extra work at end of ruler (DD units from
         right edge) but is often cancelled anyway by other
         marks (e.g., both COMP and DIST can cancel a possible
         spot, and DIST is still accurate for small diffs!)

         For consistency, do not change this from 32 for OGR-21
-----------------------------------------------------------------*/

/*-----GLOBALS-----*/
int MAXBITS=20;               /* bits in choose bitmap, RAM used = 11<<MAXBITS+2 */
char max_golomb;              /* actual depth in choose.dat file */
char max_bits;                /* actual bits in choose.dat file */
int ttmMAXBITS;               /* 32-MAXBITS, precomputed in golombInit() */
volatile int DUMPTIME=60;     /* minimum time between saves, in seconds */
char *save_file_name = "save.txt";
char *send_file_name = "send.txt";
char *choose_file_name = "choose.dat";
int max;                        /* maximum length of ruler */
int maxdepth;                   /* maximum number of marks in ruler */
int maxdepthm1;                 /* maxdepth-1, precomputed in golombInit() */
unsigned char choose_version;   /* identifies choose.dat file used */
unsigned char *choosedat;       /* array of ruler lengths */
/* unsigned char choose[1<<MAXBITS][11];  ==  array of ruler lengths */
int OGR[]={0,1,3,6,11,17,25,34,44,55,72,85,106,127,151,177,199,216,246,283,333};

FILE *length_file;              /* file to read ruler lengths from */
int half_length;                /* half of max */
int half_length2;               /* half of max using 2nd center mark */
int half_depth;                 /* half of maxdepth */
int half_depth2;                /* half of maxdepth, adjusted for 2nd mark */
int count[MAXDEPTH+1];          /* current length */
char first[65537];              /* first blank in 16 bit COMP bitmap, range: 1..16 */

volatile int DUMPDEPTH;         /* save.txt updated at this level */
int FORCEDUMP;                  /* send.txt updated at this level */

U bit[200];                     /* which bit of LIST to update */
U nodes = 0l;                   /* counts "tree branches" > 10^6 */
U nodesm = 0l;                  /* counts "tree branches" < 10^6 */
int restart=999,n_start,n_end,etime,re_depth;
int start_stub[23],end_stub[23],re_stub[23];
time_t  start0, start, middle, finish;       /* used to time search */
short dsave=0,dsend=0;          /* alter the save/send update depths */
int IDLE_state = 1;             /* turns off the 'idle' priority */
int OGR_TEST=0;                 /* Allows quick testing of small rulers */
int memory_mapped = 0l;         /* 1 = use mem-mapped IO if possible */
int pri_class = 1;                  /* # = Priority class (1=Idle, 2=Regular) */
int pri_delta = 1;                  /* # = delta within class can be 0 thru 31 */
volatile int KILL_signal = 0;   /* Used to save output ASAP, then kill */


/*-----------------------------------------*/
/*  Get command line arguments             */
/*-----------------------------------------*/
void parse_arguments (int argc, char **argv)
{
  int i = 1;
  while (i < argc) {
    char *arg = argv[i];
    /* printf("arg = %s",argv[i]); */
    if (stricmp(arg,"-save") == 0) {
      save_file_name = argv[i+1];
      i += 2;
    } else if (stricmp (arg, "-send") == 0) {
      send_file_name = argv[i+1];
      i += 2;
    } else if (stricmp (arg, "-choose") == 0) {
      choose_file_name = argv[i+1];
      i += 2;
    } else if (stricmp (arg, "-MAXBITS") == 0) {
      MAXBITS = atoi(argv[i+1]);
      i += 2;
    } else if (stricmp (arg, "-class") == 0) {
      pri_class = atoi(argv[i+1]);
      i += 2;
    } else if (stricmp (arg, "-delta") == 0) {
      pri_delta = atoi(argv[i+1]);
      i += 2;
    } else if (stricmp (arg, "-dsave") == 0) {
      dsave = atoi(argv[i+1]);
      i += 2;
    } else if (stricmp (arg, "-dsend") == 0) {  /* do not advertise this */
      dsend = atoi(argv[i+1]);
      i += 2;
    } else if (stricmp (arg, "-OGR") == 0) {    /* do not advertise this */
      maxdepth = atoi(argv[i+1]);
      max = OGR[maxdepth-1];
      OGR_TEST=1;
      i += 2;
    } else if (stricmp (arg, "-DUMPTIME") == 0) {
      DUMPTIME = atoi(argv[i+1]);
      i += 2;
    } else if (stricmp (arg, "-mm") == 0) {
      memory_mapped = 1;
      i += 1;
    } else {
      fprintf(stderr,"Illegal command line option:  %s\n", arg);
      fprintf(stderr," options:  -save xxxx     xxxx =   save.txt filename\n");
      fprintf(stderr,"           -send xxxx     xxxx =   send.txt filename\n");
      fprintf(stderr,"           -choose xxxx   xxxx = choose.dat filename\n");
      fprintf(stderr,"           -MAXBITS #     # = bits/map (e.g., 20)\n");
      fprintf(stderr,"           -DUMPTIME #    # = minimum seconds between saves\n");
      fprintf(stderr,"           -dsave #       # = extra save depth (use 1 for really hard stubs)\n");
      fprintf(stderr,"           -class #       # = Priority class (1=Idle, 2=Regular)\n");
      fprintf(stderr,"           -delta #       # = delta within class ( can be 0 upto 31)\n");
#ifdef MEMORY_MAPPED_IO
      fprintf(stderr,"           -mm            Uses memory mapped choose.dat file\n");
#endif
      exit(1);
    }
  }
}


/*-----------------------------------------*/
/*  found_one() - print out golomb rulers  */
/*-----------------------------------------*/
void found_one(int cnt2, int cnt1, U list0, U list1, U list2, U list3, U list4)
{
   FILE *fout;
   int i,j;

   count[maxdepth-1] = cnt2;       /* not placed yet into list arrays! */

   /* confirm ruler is golomb */
   {
      int diff;
      char diffs[334];
      for( i=1; i <= max/2; i++ ) diffs[i]=0;
      for( i=1; i < maxdepth; i++ ) {
         for( j=0; j<i; j++ ) {
            diff = count[i]-count[j];
            if( diff+diff <= max ) {        /* Principle 1 */
               if( diff <= 64 ) break;      /* 2 bitmaps always tracked */
               if( diffs[diff] ) return;
               diffs[diff] = 1;
            }
         }
      }
   }

   fout = fopen("newruler.txt","a");
   fprintf(fout,"found: length = %d\n", count[maxdepth-1]);
   for( i=0; i<maxdepth; i++ ) fprintf(fout,"%4d",count[i]);
   fprintf(fout,"\n  ");
   for( i=1; i<maxdepth; i++ ) fprintf(fout,"%4d",count[i]-count[i-1]);
   fprintf(fout,"\n");
   fclose(fout);

   fout = fopen(send_file_name,"a");
   fprintf(fout,"0 found: length = %d\n", count[maxdepth-1]);
   for( i=0; i<maxdepth; i++ ) fprintf(fout,"%4d",count[i]);
   fprintf(fout,"\n  ");
   for( i=1; i<maxdepth; i++ ) fprintf(fout,"%4d",count[i]-count[i-1]);
   fprintf(fout,"\n");
   fclose(fout);

   printf("\n");
   for( i=0; i<maxdepth; i++ ) printf("%4d",count[i]);
   printf("\n  ");
   for( i=1; i<maxdepth; i++ ) printf("%4d",count[i]-count[i-1]);
   printf("\n");
}


/*-----------------------------------------*/
/*  get_input() get the input to use       */
/*-----------------------------------------*/
void get_input(void)
{
   FILE *fout;
   int i,j;

   restart = 1;

   /* File Read */
   fout = fopen(save_file_name,"r");
   if( !fout ) {printf("Cannot open %s",save_file_name);exit(1);}

   fscanf(fout,"%d %d",&maxdepth,&max);
   if( max <= 0 ) max = OGR[maxdepth-1];

   /* The remainder of the input file is optional */

   re_stub[1] = start_stub[1] = 1;
   /* Starting Stub */
   for(i=1; ;i++) {
      j = fscanf(fout,"%d",&start_stub[i]);
      if( j == EOF || j == 0 ) {
         n_start = re_depth = i-1;
         fclose(fout);
         fout = fopen(save_file_name,"a");
         if( n_start == 0 ) fprintf(fout," 1");
         fprintf(fout," -999\n\n");
         fclose(fout);
         re_stub[re_depth]--;
         return;
      }
      if( (re_stub[i]=start_stub[i]) < 0 ) {
         re_depth = n_start = i-1;
         re_stub[re_depth]--;  /* needed because we will start AFTER this */
         break;
      }
   }

   /* Ending Stub */
   end_stub[1] = -start_stub[i];
   for(i=2; ;i++) {
      j = fscanf(fout,"%d",&end_stub[i]);
      if( j == EOF || j == 0 ) {
         n_end=i-1;
         fclose(fout);
         fout = fopen(save_file_name,"a");
         if( n_end == 0 ) fprintf(fout," -999");
         fprintf(fout,"\n\n");
         fclose(fout);
         return;
      }
      if( end_stub[i] > 0 ) {n_end=i-1;break;}
      end_stub[i] = -end_stub[i];
   }

   /* Restart Stub -- overwrite the restart stub if work already completed */
   re_depth = end_stub[i];
   while(1) {
      for( i=1; i<=re_depth; i++ ) {fscanf(fout,"%d",&re_stub[i]);}
      fscanf(fout,"%d %ld %ld",&etime,&nodesm,&nodes);
      if( fscanf(fout,"%d",&i ) != 1 ) break;
      re_depth = i;
   }
   fclose(fout);

   /* Screen Dump if we are restarting */
   printf("\n\n-----------------------------------------");
   printf("\n          GARSP is resuming after...\n");
   printf(" Searched through");
   for( i=1; i<=re_depth; i++ ) printf(" %d",re_stub[i]);
   printf(" ...in %d seconds (%lum + %lu nodes)\n",etime,nodesm,nodes);
   printf("-----------------------------------------\n\n");

}



/*-----------------------------------------*/
/*  store_temp() store state for future use*/
/*-----------------------------------------*/
void store_temp(int depth)
{
   FILE *fout;
   int i;

   /* Screen Dump */
   printf("Searched thru");
   for( i=1; i<=depth; i++ ) printf(" %d",count[i]-count[i-1]);
   printf(" ... %d secs, %ldm + %06ld nodes\n",etime+(int)difftime(finish,start),nodesm,nodes);
   fflush(stdout);
   middle = finish;

   /* File Storage */
   fout = fopen(save_file_name,"a");

   fprintf(fout,"%d   ",depth);
   for( i=1; i<=depth; i++ ) fprintf(fout," %d",count[i]-count[i-1]);
   fprintf(fout,"   %d %ld %ld\n",etime+(int)difftime(finish,start),nodesm,nodes);
   fclose(fout);

   if( KILL_signal ) exit(1);  /* exit with error, so batch files work OK */
}


/*-----------------------------------------*/
/*  store() - store state for future use   */
/*-----------------------------------------*/
void store(void)
{
   FILE *fout;
   int i;

   /* Screen Dump */
   printf("Searched thru");
   for( i=1; i<=FORCEDUMP; i++ ) printf(" %d",count[i]-count[i-1]);
   printf(" ... %d secs, %ldm + %06ld nodes",etime+(int)difftime(finish,start),nodesm,nodes);
   printf("  *** saved in %s\n",send_file_name);
   fflush(stdout);
   middle = finish;

   /* Permanent File Storage */
   fout = fopen(send_file_name,"a");
   fprintf(fout,"%d %d",maxdepth,max);
   for( i=1; i<=FORCEDUMP; i++ ) fprintf(fout," %d",count[i]-count[i-1]);
   fprintf(fout,"  %d %ld %ld\n",etime+(int)difftime(finish,start),nodesm,nodes);
   fclose(fout);

   /* Reset Temp File Storage */
   fout = fopen(save_file_name,"w");
   fprintf(fout,"%d %d  ",maxdepth,max);
   for( i=1;i<=n_start;i++) fprintf(fout,"%d ",start_stub[i]);
   if( ! n_start ) fprintf(fout," 1");
   for( i=1;i<=n_end;i++) fprintf(fout," %d",-end_stub[i]);
   if( ! n_end ) fprintf(fout," -999");

   fprintf(fout,"\n\n%d   ",FORCEDUMP);
   for( i=1; i<=FORCEDUMP; i++ ) fprintf(fout," %d",count[i]-count[i-1]);
   fprintf(fout,"   0 0 0\n");   /* time and node counts reset to zero */
   fclose(fout);

   { nodesm=0; nodes=0; etime=0; start=finish; }
}



/*-----------------------------------------*/
/*  The golomb workhorse engine!           */
/*-----------------------------------------*/

/* Bitmaps used: comp=comparison, list=ruler, dist=distances */
#ifdef _WIN32_
void __fastcall Recursion2(
#else
void Recursion2(
#endif
   U list1, U dist1, U comp1,
   U list0, U dist0, U comp0,
   int depth, int cnt1, int cnt2)
{
   int limit;             /* limit for this mark */

   count[depth-1]=cnt2;
#ifndef OGR21
   if (depth <= half_depth2) {
      if (depth <= half_depth) {
          if( nodes > 1000000 ) {  /* prevent overflows */
             nodesm += nodes/1000000;
             nodes -= (nodes/1000000)*1000000;
          }

         /*
          * Restart code placed here to keep speed up
          * depth = 1 for first mark after the left edge
          * restart = 999 means this is a new run, =1+ means otherwise
          * We evaluate the second+ time we enter this routine
          */

         if( depth-1 == restart ) {
            if( count[restart]-count[restart-1] < re_stub[restart] ) return;
            if( count[restart]-count[restart-1] > re_stub[restart] ) {
               nodes-=restart;  /* correct the node count for restarts */
               restart=999;  /* started or restarted */
            } else {
               if( restart == re_depth ) {
                    return;
               }
               restart++;
            }
         }
         limit = max-OGR[maxdepthm1-depth];
         limit = limit < half_length ? limit : half_length;
      } else {
         limit = max-choose(dist0>>(ttmMAXBITS),maxdepthm1-depth);
         limit = limit < max-count[half_depth]-1 ? limit : max-count[half_depth]-1;
      }
   } else
#endif

   {
      limit = max-choose(dist0>>(ttmMAXBITS),maxdepthm1-depth);
   }

   nodes++;

   /* Find the next available mark location for this level */
   {
      int s; /* count bits of next free distance */
stay:
      if( comp0 < 0xffff0000 ) {
         s = first[comp0>>16];
      } else {
         if( comp0 < 0xfffffffe ) {
            /* s = 16 + first[comp0 & 0x0000ffff]; slow code */
            s = 16 + first[comp0 - 0xffff0000];
         } else {
            /* s>=32 */
            U comptemp=comp0;
            if( (cnt2 += 32) > limit ) return; /* no spaces left */
            comp0 = comp1;
            comp1 = 0;
            list1 = list0;
            list0 = 0;
            if(comptemp==0xffffffff) goto stay;  /* no free bit was found => s>32 */
            goto skip_out; /* s==32 */
         }
      }
      if( (cnt2 += s) > limit ) return; /* no spaces left */

      {
          int ss=32-s;
          comp0 = (comp0 << s) OR (comp1 >> ss);
          comp1 <<= s;
          list1 = (list1 >> s) OR (list0 << ss);
          list0 >>= s;
      }
   }
skip_out:

   /* New ruler? */
   if (depth == maxdepthm1) {
      found_one(cnt2,cnt1,list0,list1,0,0,0);
      goto stay;
   }

   /* Go Deeper */
   {
      U list0a,list1a;
      int d = cnt2-cnt1;
      if( d <= 32 ) {
         list0a = list0 OR bit[ d ];
         list1a = list1;
      } else if( d <= 64 ) {
         list0a = list0;
         list1a = list1 OR bit[ d ];
      } else {
         list0a = list0;
         list1a = list1;
      }
      Recursion2(
         list1a, dist1 OR list1a, comp1 | (dist1 OR list1a),
         list0a, dist0 OR list0a, comp0 | (dist0 OR list0a),
         depth+1 , cnt2, cnt2);
   }

#ifndef OGR21
   /* Save results? */
   if ( depth <= DUMPDEPTH ) {
      if( depth  == FORCEDUMP ) {
         if( restart == 999 ) store();
      } else {
         time(&finish);
         if( difftime(finish,middle) >= DUMPTIME ) store_temp(depth);
      }
      if( depth <= n_end ) {
         int i;
         for( i=1; i <= n_end; i++) {
            if(count[i]-count[i-1] > end_stub[i]) break;
            if(count[i]-count[i-1] < end_stub[i]) goto stay;
         }
         printf("\n The assigned Stub Range is finished! "); return;
      }
   }
#endif

   goto stay; /* repeat this level till done */
}

#ifdef _WIN32_
void __fastcall Recursion3(
#else
void Recursion3(
#endif
   U list2, U dist2, U comp2,
   U list1, U dist1, U comp1,
   U list0, U dist0, U comp0,
   int depth, int cnt1, int cnt2)
{
   int limit;             /* limit for this mark */

   count[depth-1]=cnt2;
   if (depth <= half_depth2) {
#ifndef OGR21
      if (depth <= half_depth) {
          if( nodes > 1000000 ) {  /* prevent overflows */
             nodesm += nodes/1000000;
             nodes -= (nodes/1000000)*1000000;
          }

         /*
          * Restart code placed here to keep speed up
          * depth = 1 for first mark after the left edge
          * restart = 999 means this is a new run, =1+ means otherwise
          * We evaluate the second+ time we enter this routine
          */

         if( depth-1 == restart ) {
            if( count[restart]-count[restart-1] < re_stub[restart] ) return;
            if( count[restart]-count[restart-1] > re_stub[restart] ) {
               nodes-=restart;  /* correct the node count for restarts */
               restart=999;  /* started or restarted */
            } else {
               if( restart == re_depth ) {
                   return;
               }
               restart++;
            }
         }
         limit = max-OGR[maxdepthm1-depth];
         limit = limit < half_length ? limit : half_length;
      } else
#endif
      {
         limit = max-choose(dist0>>(ttmMAXBITS),maxdepthm1-depth);
         limit = limit < max-count[half_depth]-1 ? limit : max-count[half_depth]-1;
      }
   } else {
      limit = max-choose(dist0>>(ttmMAXBITS),maxdepthm1-depth);
   }

   nodes++;

   /* Find the next available mark location for this level */
   {
      int s; /* count bits of next free distance */
stay:
      if( comp0 < 0xffff0000 ) {
         s = first[comp0>>16];
      } else {
         if( comp0 < 0xfffffffe ) {
            /* s = 16 + first[comp0 & 0x0000ffff]; slow code */
            s = 16 + first[comp0 - 0xffff0000];
         } else {
            /* s>32 */
            U comptemp=comp0;
            if( (cnt2 += 32) > limit ) return; /* no spaces left */
            comp0 = comp1;
            comp1 = comp2;
            comp2 = 0;
            list2 = list1;
            list1 = list0;
            list0 = 0;
            if(comptemp==0xffffffff) goto stay;
            goto skip_out;
         }
      }
      if( (cnt2 += s) > limit ) return; /* no spaces left */

      {
          int ss=32-s;
          comp0 = (comp0 << s) OR (comp1 >> ss);
          comp1 = (comp1 << s) OR (comp2 >> ss);
          comp2 <<= s;
          list2 = (list2 >> s) OR (list1 << ss);
          list1 = (list1 >> s) OR (list0 << ss);
          list0 >>= s;
      }
   }
skip_out:

#ifndef OGR21
   /* New ruler? */
   if (depth == maxdepthm1) {
      found_one(cnt2,cnt1,list0,list1,list2,0,0);
      goto stay;
   }
#endif

   /* Go Deeper */
   {
      U list0a,list1a,list2a;
      int d = cnt2-cnt1;
      if( d <= 32 ) {
         list0a = list0 | bit[ d ];
         list1a = list1;
         list2a = list2;
      } else if( d <= 64 ) {
         list0a = list0;
         list1a = list1 | bit[ d ];
         list2a = list2;
      } else if( d <= 96 ) {
         list0a = list0;
         list1a = list1;
         list2a = list2 | bit[ d ];
      } else {
         list0a = list0;
         list1a = list1;
         list2a = list2;
      }
      if(max-cnt2>64+DD) {
          Recursion3(
             list2a, dist2 | list2a, comp2 | (dist2 | list2a),
             list1a, dist1 | list1a, comp1 | (dist1 | list1a),
             list0a, dist0 | list0a, comp0 | (dist0 | list0a),
             depth+1 , cnt2, cnt2);
      } else {
          Recursion2(
             list1a, dist1 | list1a, comp1 | (dist1 | list1a),
             list0a, dist0 | list0a, comp0 | (dist0 | list0a),
             depth+1 , cnt2, cnt2);
      }
   }

#ifndef OGR21
   /* Save results? */
   if ( depth <= DUMPDEPTH ) {
      if( depth  == FORCEDUMP ) {
         if( restart == 999 ) store();
      } else {
         time(&finish);
         if( difftime(finish,middle) >= DUMPTIME ) store_temp(depth);
      }
      if( depth <= n_end ) {
         int i;
         for( i=1; i <= n_end; i++) {
            if(count[i]-count[i-1] > end_stub[i]) break;
            if(count[i]-count[i-1] < end_stub[i]) goto stay;
         }
         printf("\n The assigned Stub Range is finished! "); return;
      }
   }
#endif

   goto stay; /* repeat this level till done */
}

#ifdef _WIN32_
void __fastcall Recursion4(
#else
void Recursion4(
#endif
   U list3, U dist3, U comp3,
   U list2, U dist2, U comp2,
   U list1, U dist1, U comp1,
   U list0, U dist0, U comp0,
   int depth, int cnt1, int cnt2)
{
   int limit;             /* limit for this mark */

   count[depth-1]=cnt2;
   if (depth <= half_depth2) {
#ifndef OGR21
      if (depth <= half_depth) {
          if( nodes > 1000000 ) {  /* prevent overflows */
             nodesm += nodes/1000000;
             nodes -= (nodes/1000000)*1000000;
          }

         /*
          * Restart code placed here to keep speed up
          * depth = 1 for first mark after the left edge
          * restart = 999 means this is a new run, =1+ means otherwise
          * We evaluate the second+ time we enter this routine
          */

         if( depth-1 == restart ) {
            if( count[restart]-count[restart-1] < re_stub[restart] ) return;
            if( count[restart]-count[restart-1] > re_stub[restart] ) {
               nodes-=restart;  /* correct the node count for restarts */
               restart=999;  /* started or restarted */
            } else {
               if( restart == re_depth ) {
                   return;
               }
               restart++;
            }
         }
         limit = max-OGR[maxdepthm1-depth];
         limit = limit < half_length ? limit : half_length;
      } else
#endif
      {
         limit = max-choose(dist0>>(ttmMAXBITS),maxdepthm1-depth);
         limit = limit < max-count[half_depth]-1 ? limit : max-count[half_depth]-1;
      }
   } else {
      limit = max-choose(dist0>>(ttmMAXBITS),maxdepthm1-depth);
   }

   nodes++;

   /* Find the next available mark location for this level */
   {
      int s; /* count bits of next free distance */
stay:
      if( comp0 < 0xffff0000 ) {
         s = first[comp0>>16];
      } else {
         if( comp0 < 0xfffffffe ) {
            /* s = 16 + first[comp0 & 0x0000ffff]; slow code */
            s = 16 + first[comp0 - 0xffff0000];
         } else {
            /* s>32 */
            U comptemp=comp0;
            if( (cnt2 += 32) > limit ) return; /* no spaces left */
            comp0 = comp1;
            comp1 = comp2;
            comp2 = comp3;
            comp3 = 0;
            list3 = list2;
            list2 = list1;
            list1 = list0;
            list0 = 0;
            if(comptemp==0xffffffff) goto stay;
            goto skip_out;
         }
      }
      if( (cnt2 += s) > limit ) return; /* no spaces left */

      {
          int ss=32-s;
          comp0 = (comp0 << s) | (comp1 >> ss);
          comp1 = (comp1 << s) | (comp2 >> ss);
          comp2 = (comp2 << s) | (comp3 >> ss);
          comp3 <<= s;
          list3 = (list3 >> s) | (list2 << ss);
          list2 = (list2 >> s) | (list1 << ss);
          list1 = (list1 >> s) | (list0 << ss);
          list0 >>= s;
      }
   }
skip_out:

#ifndef OGR21
   /* New ruler? */
   if (depth == maxdepthm1) {
      found_one(cnt2,cnt1,list0,list1,list2,list3,0);
      goto stay;
   }
#endif

   /* Go Deeper */
   {
      U list0a,list1a,list2a,list3a;
      int d = cnt2-cnt1;
      if( d <= 32 ) {
         list0a = list0 | bit[ d ];
         list1a = list1;
         list2a = list2;
         list3a = list3;
      } else if( d <= 64 ) {
         list0a = list0;
         list1a = list1 | bit[ d ];
         list2a = list2;
         list3a = list3;
      } else if( d <= 96 ) {
         list0a = list0;
         list1a = list1;
         list2a = list2 | bit[ d ];
         list3a = list3;
      } else if( d <= 128 ) {
         list0a = list0;
         list1a = list1;
         list2a = list2;
         list3a = list3 | bit[ d ];
      } else {
         list0a = list0;
         list1a = list1;
         list2a = list2;
         list3a = list3;
      }
      if(max-cnt2>96+DD) {
          Recursion4(
             list3a, dist3 | list3a, comp3 | (dist3 | list3a),
             list2a, dist2 | list2a, comp2 | (dist2 | list2a),
             list1a, dist1 | list1a, comp1 | (dist1 | list1a),
             list0a, dist0 | list0a, comp0 | (dist0 | list0a),
             depth+1 , cnt2, cnt2);
      } else if(max-cnt2>64+DD) {
          Recursion3(
             list2a, dist2 | list2a, comp2 | (dist2 | list2a),
             list1a, dist1 | list1a, comp1 | (dist1 | list1a),
             list0a, dist0 | list0a, comp0 | (dist0 | list0a),
             depth+1 , cnt2, cnt2);
      } else {
          Recursion2(
             list1a, dist1 | list1a, comp1 | (dist1 | list1a),
             list0a, dist0 | list0a, comp0 | (dist0 | list0a),
             depth+1 , cnt2, cnt2);
      }
   }

#ifndef OGR21
   /* Save results? */
   if ( depth <= DUMPDEPTH ) {
      if( depth  == FORCEDUMP ) {
         if( restart == 999 ) store();
      } else {
         time(&finish);
         if( difftime(finish,middle) >= DUMPTIME ) store_temp(depth);
      }
      if( depth <= n_end ) {
         int i;
         for( i=1; i <= n_end; i++) {
            if(count[i]-count[i-1] > end_stub[i]) break;
            if(count[i]-count[i-1] < end_stub[i]) goto stay;
         }
         printf("\n The assigned Stub Range is finished! "); return;
      }
   }
#endif

   goto stay; /* repeat this level till done */
}

#ifdef _WIN32_
void __fastcall Recursion5(
#else
void Recursion5(
#endif
   U list4, U dist4, U comp4,
   U list3, U dist3, U comp3,
   U list2, U dist2, U comp2,
   U list1, U dist1, U comp1,
   U list0, U dist0, U comp0,
   int depth, int cnt1, int cnt2)
{
   int limit;             /* limit for this mark */

   count[depth-1]=cnt2;
   if (depth <= half_depth2) {
      if (depth <= half_depth) {
          if( nodes > 1000000 ) {  /* prevent overflows */
             nodesm += nodes/1000000;
             nodes -= (nodes/1000000)*1000000;
          }

         /*
          * Restart code placed here to keep speed up
          * depth = 1 for first mark after the left edge
          * restart = 999 means this is a new run, =1+ means otherwise
          * We evaluate the second+ time we enter this routine
          */

         if( depth-1 == restart ) {
            if( count[restart]-count[restart-1] < re_stub[restart] ) return;
            if( count[restart]-count[restart-1] > re_stub[restart] ) {
               nodes-=restart;  /* correct the node count for restarts */
               restart=999;  /* started or restarted */
            } else {
               if( restart == re_depth ) {
                   return;
               }
               restart++;
            }
         }
         limit = max-OGR[maxdepthm1-depth];
         limit = limit < half_length ? limit : half_length;
      } else {
         limit = max-choose(dist0>>(ttmMAXBITS),maxdepthm1-depth);
         limit = limit < max-count[half_depth]-1 ? limit : max-count[half_depth]-1;
      }
   } else {
      limit = max-choose(dist0>>(ttmMAXBITS),maxdepthm1-depth);
   }

   nodes++;

   /* Find the next available mark location for this level */
   {
      int s; /* count bits of next free distance */
stay:
      if( comp0 < 0xffff0000 ) {
         s = first[comp0>>16];
      } else {
         if( comp0 < 0xfffffffe ) {
            /* s = 16 + first[comp0 & 0x0000ffff]; slow code */
            s = 16 + first[comp0 - 0xffff0000];
         } else {
            /* s>32 */
            U comptemp=comp0;
            if( (cnt2 += 32) > limit ) return; /* no spaces left */
            comp0 = comp1;
            comp1 = comp2;
            comp2 = comp3;
            comp3 = comp4;
            comp4 = 0;
            list4 = list3;
            list3 = list2;
            list2 = list1;
            list1 = list0;
            list0 = 0;
            if(comptemp==0xffffffff) goto stay;
            goto skip_out;
         }
      }
      if( (cnt2 += s) > limit ) return; /* no spaces left */

      {
       int ss=32-s;
       comp0 = (comp0 << s) | (comp1 >> ss);
       comp1 = (comp1 << s) | (comp2 >> ss);
       comp2 = (comp2 << s) | (comp3 >> ss);
       comp3 = (comp3 << s) | (comp4 >> ss);
       comp4 <<= s;
       list4 = (list4 >> s) | (list3 << ss);
       list3 = (list3 >> s) | (list2 << ss);
       list2 = (list2 >> s) | (list1 << ss);
       list1 = (list1 >> s) | (list0 << ss);
       list0 >>= s;
      }
   }
skip_out:

#ifndef OGR21
   /* New ruler? */
   if (depth == maxdepthm1) {
      found_one(cnt2,cnt1,list0,list1,list2,list3,list4);
      goto stay;
   }
#endif

   /* Go Deeper */
   {
      U list0a,list1a,list2a,list3a,list4a;
      int d = cnt2-cnt1;
      if( d <= 32 ) {
         list0a = list0 | bit[ d ];
         list1a = list1;
         list2a = list2;
         list3a = list3;
         list4a = list4;
      } else if( d <= 64 ) {
         list0a = list0;
         list1a = list1 | bit[ d ];
         list2a = list2;
         list3a = list3;
         list4a = list4;
      } else if( d <= 96 ) {
         list0a = list0;
         list1a = list1;
         list2a = list2 | bit[ d ];
         list3a = list3;
         list4a = list4;
      } else if( d <= 128 ) {
         list0a = list0;
         list1a = list1;
         list2a = list2;
         list3a = list3 | bit[ d ];
         list4a = list4;
      } else if( d <= 160 ) {
         list0a = list0;
         list1a = list1;
         list2a = list2;
         list3a = list3;
         list4a = list4 | bit[ d ];
      } else {
         list0a = list0;
         list1a = list1;
         list2a = list2;
         list3a = list3;
         list4a = list4;
      }
      if(max-cnt2>128+DD) {
         Recursion5(
            list4a, dist4 | list4a, comp4 | (dist4 | list4a),
            list3a, dist3 | list3a, comp3 | (dist3 | list3a),
            list2a, dist2 | list2a, comp2 | (dist2 | list2a),
            list1a, dist1 | list1a, comp1 | (dist1 | list1a),
            list0a, dist0 | list0a, comp0 | (dist0 | list0a),
            depth+1 , cnt2, cnt2);
      } else if(max-cnt2>96+DD) {
         Recursion4(
            list3a, dist3 | list3a, comp3 | (dist3 | list3a),
            list2a, dist2 | list2a, comp2 | (dist2 | list2a),
            list1a, dist1 | list1a, comp1 | (dist1 | list1a),
            list0a, dist0 | list0a, comp0 | (dist0 | list0a),
            depth+1 , cnt2, cnt2);
      } else if(max-cnt2>64+DD) {
         Recursion3(
            list2a, dist2 | list2a, comp2 | (dist2 | list2a),
            list1a, dist1 | list1a, comp1 | (dist1 | list1a),
            list0a, dist0 | list0a, comp0 | (dist0 | list0a),
            depth+1 , cnt2, cnt2);
      } else {
         Recursion2(
            list1a, dist1 | list1a, comp1 | (dist1 | list1a),
            list0a, dist0 | list0a, comp0 | (dist0 | list0a),
            depth+1 , cnt2, cnt2);
      }
   }

   /* Save results? */
   if ( depth <= DUMPDEPTH ) {
      if( depth  == FORCEDUMP ) {
         if( restart == 999 ) store();
      } else {
         time(&finish);
         if( difftime(finish,middle) >= DUMPTIME ) store_temp(depth);
      }
      if( depth <= n_end ) {
         int i;
         for( i=1; i <= n_end; i++) {
            if(count[i]-count[i-1] > end_stub[i]) break;
            if(count[i]-count[i-1] < end_stub[i]) goto stay;
         }
         printf("\n The assigned Stub Range is finished! "); return;
      }
   }

   goto stay; /* repeat this level till done */
}




/*--------------------------------------------*/
/*      The Garsp Init Routine                */
/*--------------------------------------------*/
void golombInit()
{
   U comp0,comp1,comp2,comp3;  /* comparison bitmap */
   U list0,list1,list2,list3;  /* ruler bitmap */
   U dist0,dist1,dist2,dist3;  /* distance bitmap */
   int i;          /* counters */
   int depth;      /* the depth of recursion */

   for( i=1; i<200; i++) {
      bit[i] = 0x80000000 >> ((i-1)%32);
   }
   depth    = 1;
   list0  = list1 = list2 = list3 = 0;
   dist0  = dist1 = dist2 = dist3 = 0;
   comp0  = comp1 = comp2 = comp3 = 0;
   count[1] = count[0] = 0;

   /* precomputed here, used in Recursion() */
   maxdepthm1=maxdepth-1;
   ttmMAXBITS=32-MAXBITS;

   Recursion5(
      list3,dist3,comp3,
      list3,dist3,comp3,
      list2,dist2,comp2,
      list1,dist1,comp1,
      list0,dist0,comp0,
      depth,0,0);
}



/*--------------------------------------------*/
/*     READ the choose.dat file !!!           */
/*--------------------------------------------*/
void SetupChooseMalloc()
{
   FILE *length_file;            /* file to read ruler lengths from */
   int i,j;                      /* counters */

   printf("Allocating %d bytes\n", 11<<MAXBITS);

#ifdef OS2
# ifdef __EMX__
   if (DosAllocMem((void**)(&choosedat), 11<<MAXBITS, PAG_COMMIT|PAG_READ|PAG_WRITE)) {
     choosedat=NULL;
   }
# else
   choosedat = (unsigned char *)malloc( 11 << MAXBITS );
# endif
#else
   choosedat = (unsigned char *)malloc( 11 << MAXBITS );
#endif

   if( choosedat == NULL ) {
      printf(" GARSP could not get enough RAM to use %d bits/map (MAXBITS)",MAXBITS);
      exit(1);
   }

   if ((length_file = fopen(choose_file_name,"rb")) == NULL) {
      printf("\n\nError: Cannot open %s\n\n",choose_file_name);
      exit(1);
   }
   fread(&choose_version,sizeof(char),1,length_file); /* read file version */
   fread(&max_golomb,sizeof(char),1,length_file);     /* read choose data */
   fread(&max_bits  ,sizeof(char),1,length_file);
   if( max_golomb > 11 ) {
      printf("\nmax_golomb(%d) exceeds bounds, reset to 11\n",max_golomb);
      max_golomb=11;
   }
   if( MAXBITS > max_bits ) {
      printf("\nMAXBITS(%d) > choose file's MAXBITS(%d)\n",MAXBITS,max_bits);
      exit(1);
   }
   if( max_bits == MAXBITS ) {
      fread(&(choose(0,0)),sizeof(char),max_golomb*(1<<MAXBITS),length_file);
   } else {
      printf("Reading %d bits/map from the choose.dat (%d bits/map)\n\n",MAXBITS,max_bits);
      {
         char dummy[22];
         for( j=0; j<1<<MAXBITS; j++ ) {
            fread(&(choose(j,0)),sizeof(char),max_golomb,length_file);
            for( i=1; i<1<<(max_bits-MAXBITS); i++ ) {
               fread(dummy,sizeof(char),max_golomb,length_file);
            }
         }
      }
   }
   fclose(length_file);
}

/*----------------------START---memory mapped IO section----------*/
#if MEMORY_MAPPED_IO == 1   /* 1==NT version */
void SetupChooseMapped()
{
    HANDLE File, Mapping;

    printf("Running with memory-mapped choose file.\n");

    /*----------/
        Use mapped IO to access the choose file.  All that is really
        neccesary is to yank in the version of the file and bias the
        choose array start up to match.
      
        N.B.: we are reliant on choosedat being a char array.  This
        means that we don't have to worry about CPU alignment.
    /----------*/

    File = CreateFileA( choose_file_name,
                       GENERIC_READ,
                       FILE_SHARE_READ,
                       NULL,
                       OPEN_EXISTING,
                       FILE_ATTRIBUTE_NORMAL,
                       NULL );

    if (File == INVALID_HANDLE_VALUE || File == NULL) {
        printf("\n\nError: Cannot open %s\n\n",choose_file_name);
        exit(1);
    }

    Mapping = CreateFileMapping( File,
                                 NULL,
                                 PAGE_READONLY,
                                 0,
                                 0,
                                 NULL );

    if (Mapping == INVALID_HANDLE_VALUE || Mapping == NULL) {
        printf("\n\nError: Cannot create mapping object for %s\n\n",choose_file_name);
        exit(1);
    }

    choosedat = (char *)MapViewOfFile( Mapping,
                                       FILE_MAP_READ,
                                       0,
                                       0,
                                       0 );

    
    if (choosedat == NULL) {
        printf("\n\nError: Cannot create mapping of %s\n\n",choose_file_name);
        exit(1);
    }
    
    /*----------/
        Now pull the version in and set up the bitsize to use.  Note that
        we override the default and just use the whole file.
      
        We must align choosedat onto the start of the actual data bits
        before returning.
    /----------*/

    choose_version = *(choosedat++);   /* increment ptr after reading */
    max_golomb     = *(choosedat++);
    max_bits       = *(choosedat++);
    if(MAXBITS!=max_bits) {
       printf(" Default value of MAXBITS=%d",MAXBITS);
       printf(" is being overridden by the MAXBITS=%d",max_bits);
       printf(" setting in the memory mapped choose.dat\n");
       fflush(stdout);
       MAXBITS=max_bits;
    }
}
#endif

#if MEMORY_MAPPED_IO == 2   /* 2==SOME_OTHER_SYSTEM version */
#endif
/*----------------------END---memory mapped IO section----------*/



/*---------------------------*/
/*      CRC32 Routines       */
/*---------------------------*/

static const unsigned crc32tab[256] = {  /* CRC polynomial 0xedb88320 */
  0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419,
  0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4,
  0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07,
  0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
  0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856,
  0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
  0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4,
  0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
  0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3,
  0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a,
  0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599,
  0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
  0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190,
  0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f,
  0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e,
  0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
  0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed,
  0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
  0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3,
  0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
  0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a,
  0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5,
  0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010,
  0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
  0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17,
  0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6,
  0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615,
  0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
  0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344,
  0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
  0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a,
  0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
  0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1,
  0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c,
  0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef,
  0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
  0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe,
  0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31,
  0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c,
  0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
  0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b,
  0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
  0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1,
  0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
  0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278,
  0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7,
  0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66,
  0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
  0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
  0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
  0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b,
  0x2d02ef8d
};


#define CRC32(crc,c) (crc32tab[((unsigned char)(crc) ^ (c)) & 0xff] ^ (((crc) >> 8) & 0x00FFFFFFl))


unsigned crc32_a1 (unsigned init_crc, void *pdata, int count) {
  unsigned char *p=(unsigned char*)pdata;
  while (count-- > 0) init_crc=CRC32(init_crc, *p++);
  return init_crc;
}

static const unsigned chooseCRC32[24] = {
  0xCF4CB8FE,   /* 0 */
  0x1CCBEB38,
  0xB19475A8,
  0x90A92DEB,
  0xEA1A2993,
  0xCF235C49,   /* 5 */
  0x448AC8D4,
  0x9265C50C,
  0x86CA4E98,
  0x6DA62613,
  0xD51F87A4,   /* 10 */
  0x57F02A8D,
  0x46897545,
  0xBCAADCB3,
  0xBBC59E93,
  0xB312FA7B,   /* 15 */
  0x05260663,
  0x860A1266,
  0x5E2FBFD5,
  0x1087F74E,
  0x1FA27ED1,   /* 20 */
  0x1D3BEC69,
  0xD9EFCD1A,
  0x063D42A0
};




/*---------------------------------------*/
/*      The Signal Catch Routine         */
/*---------------------------------------*/
#ifdef WIN32       /* fix needed for VC5 */
void __cdecl MyHandler( int sig_number )
#else
void MyHandler( int sig_number )
#endif
{
   DUMPDEPTH = half_depth-1;
   DUMPTIME  = 0;
   KILL_signal = 1;
}



/*---------------------------------------*/
/*      The Main Routine                 */
/*---------------------------------------*/
#ifdef WIN32       /* fix needed for VC5 */
int __cdecl main(argc,argv)
#else
int main(argc,argv)
#endif
   int argc;
   char *argv[];
{
   int i,j;                      /* counters */
   int mask[17];
   FILE *fout;

   if( sizeof(U) != 4 ) {
      printf("GARSP only works with 32 bit ints\n\n");
      printf("sizeof(char)=%d sizeof(short)=%d sizeof(int)=%d sizeof(long)=%d\n\n",
         (int)sizeof(char),(int)sizeof(short),(int)sizeof(int),(int)sizeof(long));
      exit(1);
   }

   /*--- init data ---*/
   n_end = n_start = etime = 0;

   parse_arguments (argc, argv);


   /* bump priority into idle class -- let others get CPU first */

   if (pri_class < 1 || pri_class > 2) {
     fprintf(stderr,"class must be either 1 or 2\n");
     fprintf(stderr,"A value of 1 (Idle) is used\n");
     pri_class = 1; 
   }
   if (pri_delta < 0 || pri_delta > 31) {
     fprintf(stderr,"delta must be a value between 0 & 31\n");
     fprintf(stderr,"A value of 0 (lowest) is used\n");
     pri_delta = 0;
   }

#ifdef WIN32
   SetPriorityClass(GetCurrentProcess(), (pri_class == 1)  ? IDLE_PRIORITY_CLASS : NORMAL_PRIORITY_CLASS);
   SetThreadPriority(GetCurrentThread(), pri_delta /*THREAD_PRIORITY_IDLE*/);
#endif
#ifdef OS2
    DosSetPriority(PRTYS_THREAD, pri_class /*PRTYC_IDLETIME*/,pri_delta/*PRTYD_MINIMUM*/, 0);
#endif


   // printf About...
   printf("\nProgram GARSP, Version 5.13 using %d bits/map\n", MAXBITS);

   /*---  Read in CHOOSE.DAT file ---*/
   if (memory_mapped) {
#ifdef MEMORY_MAPPED_IO
       SetupChooseMapped();
#else
       printf("Error: This version was not compiled for memory mapping\n");
       exit(1);
#endif
   } else {
       SetupChooseMalloc();
   }

   /* always do CRC32 check */
   {
     unsigned crc32=CRC32(0xffffffff, 1);   /* Version reset to 1 for this */
     crc32=CRC32(crc32, max_golomb);        /* Currently set at 11 */
     crc32=CRC32(crc32, MAXBITS);           /* This varies a lot */
     for (j=0; j<1<<MAXBITS; j++) {
       for (i=0; i<max_golomb; ++i) crc32=CRC32(crc32, choose(j,i));
     }
     crc32=~crc32;
     if( MAXBITS<24 ) {
        if (chooseCRC32[MAXBITS]!=crc32) {
           printf("Your choose.dat (CRC=%08x) is corrupted!\n",crc32);
           exit(1);
        }
     } else {
        printf("(Your choose.dat has a CRC of %08x)\n",crc32);
     }
     printf("Choose file succesfully accessed.\n\n");
   }


   if (!OGR_TEST) get_input();

   
#ifdef OGR21
   if(maxdepth!=21)
   {
      fprintf(stderr,"This compilation is specifically optimized for OGR-21.\n You may not use it for length %d!\n",maxdepth);
      exit(10);
   }
#endif


   FORCEDUMP = (maxdepth >> 2)-2 +dsend; /* SEND.TXT file contents norm=-2 */
   DUMPDEPTH = (maxdepth >> 2)   +dsave; /* SAVE.TXT file contents norm=+0 */

   if( FORCEDUMP < 0 ) FORCEDUMP = 0;
   printf("\n saving at depth = %2d (%s)\n",FORCEDUMP,send_file_name);
   printf("  and at depths <= %2d (%s)",DUMPDEPTH,save_file_name);
   printf(" if elapsed time >= %d seconds\n\n",DUMPTIME);
   fflush(stdout);


   /* Note, marks are labled 0, 1...  so mark @ depth=1 is 2nd mark */
   half_depth2 = half_depth = ((maxdepth+1)>>1)-1;
   if ( !(maxdepth%2) ) half_depth2++;        /* if even, use 2 marks */

   /* Simulate GVANT's "KTEST=1" */
   half_depth--;
   half_depth2++;
   /*------------------
   Since:  half_depth2 = half_depth+2 (or 3 if maxdepth even) ...
   We get: half_length2 >= half_length + 3 (or 6 if maxdepth even)
   But:    half_length2 + half_length <= max-1    (our midpoint reduction)
   So:     half_length + 3 (6 if maxdepth even) + half_length <= max-1
   ------------------*/
                        half_length = (max-4) >> 1;
   if ( !(maxdepth%2) ) half_length = (max-7) >> 1;




   /* Permanent File Storage */
   fout = fopen(send_file_name,"a");
   fprintf(fout,"-99 Version 5.13 "); /* DO NOT change this line! */
   fprintf(fout,"(32)");              /* you may enter a 2 char code here */
   fprintf(fout," continuing after 0");
   for( i=1; i<=re_depth; i++ ) fprintf(fout,"-%d",re_stub[i]);
   fprintf(fout,"  (OGR-%d<=%d; %d bits v%d)\n",maxdepth,max,MAXBITS,choose_version);
   fclose(fout);
   mask[1] = 1<<15;
   for( i=2; i<=16; i++ ) mask[i] = mask[i-1] >> 1;
   for( i=0; i < 65536; i++ ) {
      for( j=1; j <=16; j++) {
         if( !(mask[j] & i) ) {
            first[i] = j;           /* location of 1st bit */
            break;
         }
      }
   }

   n_end   = n_end   < FORCEDUMP ? n_end   : FORCEDUMP;
   printf(" OGR(%d) limited to %d length",maxdepth,max);
   if( n_start ) {
      printf(" is being searched from");
      for(i=1;i<=n_start;i++) printf(" %d",start_stub[i]);
   }
   if( n_end ) {
      printf(" through");
      for(i=1;i<=n_end;i++) printf(" %d",end_stub[i]);
   }
   printf("\n\n");
   fflush(stdout);


   /* Prepare ctrl-break functions prior to starting loops */
   /* Note: UNIX & DJGPP (GCC's DOS port) have no SIGBREAK defined */
#ifndef SIGBREAK
#define SIGBREAK SIGINT
#endif
   signal( SIGBREAK, MyHandler );       /* Ctrl-Break */
   signal( SIGINT  , MyHandler );       /* Ctrl-C     */


   middle = start0 = time (&start);
#ifdef TIMINGTEST
   ftime(&start2);
   golombInit();
   ftime(&finish2);
   printf ("\n Session lasted %.2f seconds\n",((double)(finish2.time-start2.time))+
           (double)((signed)finish2.millitm-(signed)start2.millitm)/(double)1000.0);
#else
   golombInit();
   time (&finish);
   printf ("\n Session lasted %.0f seconds\n", difftime(finish,start0));
#endif
   return 0;
}


