home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / compsrcs / misc / volume02 / pdcdifpa.tch < prev    next >
Encoding:
Internet Message Format  |  1991-08-27  |  35.7 KB
  1. From mipos3!omepd!intelisc!littlei!uunet!husc6!necntc!ncoast!allbery Sun Feb 21 18:24:08 PST 1988
  2. Article 306 of comp.sources.misc:
  3. Path: td2cad!mipos3!omepd!intelisc!littlei!uunet!husc6!necntc!ncoast!allbery
  4. From: mike2@lcuxa.UUCP
  5. Newsgroups: comp.sources.misc
  6. Subject: v02i059: Patch for pd-cdiff (MS C, probably others)
  7. Message-ID: <7242@ncoast.UUCP>
  8. Date: 18 Feb 88 02:35:18 GMT
  9. Sender: allbery@ncoast.UUCP
  10. Lines: 1610
  11. Approved: allbery@ncoast.UUCP
  12. X-Archive: comp.sources.misc/8802/17
  13. Comp.sources.misc: Volume 2, Issue 59
  14. Submitted-By: <mike2@lcuxa.UUCP>
  15. Archive-Name: pd-cdiff-patch
  16.  
  17. Comp.sources.misc: Volume 2, Issue 59
  18. Submitted-By: <mike2@lcuxa.UUCP>
  19. Archive-Name: pd-cdiff-patch
  20.  
  21. [Nested shars?  That's a new one.  ++bsa]
  22.  
  23. Neil Dixon uncovered a flaw in the logic of the cdiff program that
  24. was distributed early in January, and which was redistributed with
  25. changes to make it compilable in Turbo C.  I've tested his patch
  26. both on the Unix SysVr2 version and on the PC, and have not found
  27. any errors.  Conversely, the earlier version when compiled in MSC
  28. 4.0 (but, for some reason, not when compiled in TC 1.5) would
  29. sporadically come up with "read" errors.  Since it now works in MSC as
  30. well as TC, I've included the appropriate ifdefs for both compilers,
  31. and have incorporated Neil's patch.  (This was for clarity.  The line
  32. numbers in his patch did not correspond precisely to the line numbers
  33. in the distributed code.)  Both the patch as sent to me and the
  34. revised code are contained below.
  35.  
  36. As before, I did not write this code.  I merely ported it, and of
  37. course make no warranties whatsoever.
  38.  
  39. -------------------------CUT HERE-------------------------------
  40. #!/bin/sh
  41. echo extracting cdiff.pat ...
  42. cat >cdiff.pat <<xzyyz
  43. >From rutgers!mimsy.umd.edu!uunet!mcvax!esatst!neil  Wed Feb  3 10:48:40 1988 
  44. Message-Id: <22649.8802021606@esatst.yc.estec.nl>
  45. To: bellcore!lcuxa!mike2
  46. Subject: patch for PD context diff.
  47. Date: Tue, 02 Feb 88 17:06:29 +0100
  48. From: Neil Dixon <rutgers!mimsy.umd.edu!uunet!mcvax!esatst!neil>
  49.  
  50. When running the PD context diff program recently submitted to comp.sources.misc
  51. we get a 'Can't read ...' error, when not performing a context diff. Here's the
  52. simple patch.
  53.  
  54. Regards,
  55.     Neil Dixon.
  56.         
  57.  
  58. Neil Dixon <neil@yc.estec.nl> UUCP:  ...!mcvax!esatst!neil,
  59. Thermal Control & Life Support Division (YCV) 
  60. European Space Research and Technology Centre (ESTEC),
  61. Noordwijk, The Netherlands.
  62. Phone:    +31 1719 84013
  63.  
  64.  
  65. #! /bin/sh
  66. # This is a shell archive, meaning:
  67. # 1. Remove everything above the #! /bin/sh line.
  68. # 2. Save the resulting text in a file.
  69. # 3. Execute the file with /bin/sh (not csh) to create the files:
  70. #    cdiff.patch
  71. # This archive created: Tue Feb  2 17:05:14 1988
  72. export PATH; PATH=/bin:$PATH
  73. if test -f 'cdiff.patch'
  74. then
  75.     echo shar: will not over-write existing file "'cdiff.patch'"
  76. else
  77. cat << \SHAR_EOF > 'cdiff.patch'
  78. *** cdiff.c
  79. --- cdiff.c.orig
  80. **************
  81. *** 935,942
  82.       }
  83.     }
  84.     putchar('\n');
  85. !   if ((!eflag && c != 'a') || cflag) {
  86. !       fetch(oldseek, astart , aend, lenA, infd[0], 
  87.           cflag ? (c=='d' ? "- " : "! ") : "< ");
  88.       if (cflag) {
  89.         fputs("--- ", stdout);
  90. --- 937,944 -----
  91.       }
  92.     }
  93.     putchar('\n');
  94. !   if (!eflag) {
  95. !       fetch(oldseek, astart, aend, lenA, infd[0], 
  96.           cflag ? (c=='d' ? "- " : "! ") : "< ");
  97.       if (cflag) {
  98.         fputs("--- ", stdout);
  99. SHAR_EOF
  100. fi # end of overwriting check
  101. #    End of shell archive
  102. exit 0
  103. xzyyz
  104. echo extracting cdiff2.c ...
  105. cat >cdiff2.c <<xzyyz
  106. /* Change the following as appropriate */
  107. #undef vms
  108. #undef TURBO           /*  Note:  Use the small model in TC, and
  109.                invoke optimization for speed, registers,
  110.                and jumps.  Even so, it still runs slowly! */
  111. #undef pdp11
  112. #undef OSK
  113. #undef DEBUG
  114. #undef unix 
  115. #define MSC 1          /*  Note: The source compiles properly on
  116.             *  MSC 4.0 (small model).  I have no idea
  117.             *  whether it will work on 5.0          */
  118.  
  119. #ifdef TURBO
  120. #include <alloc.h>
  121. #include <errno.h>
  122. #include <process.h>
  123. #include <stdio.h>
  124. #include <stdlib.h>
  125. #include <string.h>
  126.  
  127. #else
  128. #include <stdio.h>
  129. #include <ctype.h>
  130. #endif
  131.  
  132. #ifdef vms
  133. #include      <ssdef.h>
  134. #include      <stsdef.h>
  135. #define  IO_SUCCESS  (SS$_NORMAL | STS$M_INHIB_MSG)
  136. #define  IO_ERROR  SS$_ABORT
  137. #endif
  138. /*
  139.  * Note: IO_SUCCESS and IO_ERROR are defined in the Decus C stdio.h file
  140.  */
  141. #ifndef  IO_SUCCESS
  142. #define  IO_SUCCESS  0
  143. #endif
  144. #ifndef  IO_ERROR
  145. #define  IO_ERROR  1
  146. #endif
  147.  
  148. #define  EOS      0
  149. #ifdef unix
  150. char temfile[L_tmpnam];
  151. char *tmpnam();
  152. #define  TEMPFILE  (temfile[0]? temfile: (tmpnam(temfile), temfile))
  153. #else
  154. #define  TEMPFILE  "diff.tmp"
  155. #endif
  156. #define  TRUE      1
  157. #define  FALSE      0
  158.  
  159. #ifdef  pdp11
  160. #define  short  int
  161. #endif
  162.  
  163. typedef struct candidate {
  164.   int  b;        /* Line in fileB      */
  165.   int  a;        /* Line in fileA      */
  166.   int  link;        /* Previous candidate      */
  167. } CANDIDATE;
  168.  
  169. typedef struct line {
  170.   unsigned short  hash;      /* Hash value etc.      */
  171.   short      serial;      /* Line number        */
  172. } LINE;
  173.  
  174. LINE  *file[2];        /* Hash/line for total file  */
  175. #define  fileA  file[0]
  176. #define  fileB  file[1]
  177.  
  178. LINE  *sfile[2];        /* Hash/line after prefix  */
  179. #define  sfileA  sfile[0]
  180. #define  sfileB  sfile[1]
  181.  
  182. int  len[2];            /* Actual lines in each file  */
  183. #define  lenA  len[0]
  184. #define  lenB  len[1]
  185.  
  186. int  slen[2];        /* Squished lengths      */
  187. #define  slenA  slen[0]
  188. #define  slenB  slen[1]
  189.  
  190. int  prefix;            /* Identical lines at start  */
  191. int  suffix;            /* Identical lenes at end  */
  192.  
  193. FILE  *infd[2] = { NULL, NULL };  /* Input file identifiers  */
  194. FILE  *tempfd;        /* Temp for input redirection  */
  195.  
  196. extern long  ftell();
  197. extern FILE *fopen();
  198.  
  199. #ifdef TURBO
  200. extern void *malloc();
  201. #else
  202. extern char *malloc();
  203. #endif
  204.  
  205. char    *fgetss();
  206. unsigned short      hash();
  207.  
  208. #ifdef    AMIGA
  209. /* Define these types for Amiga C */
  210. char    *savptr;
  211. int    savsiz;
  212. char    *wrk;
  213. char    *wrk2;
  214. int    cpysiz;
  215. #endif
  216. /*
  217.  * The following vectors overlay the area defined by fileA
  218.  */
  219.  
  220. short      *class;      /* Unsorted line numbers  */
  221. int      *klist;      /* Index of element in clist  */
  222. CANDIDATE  *clist;      /* Storage pool for candidates  */
  223. int      clength = 0;      /* Number of active candidates  */
  224. #define    CSIZE_INC 50    /* How many to allocate each time we have to */
  225. int    csize = CSIZE_INC; /* Current size of storage pool */
  226.  
  227. int      *match;        /* Longest subsequence      */
  228. long      *oldseek;      /* Seek position in file A  */
  229.  
  230. /*
  231.  * The following vectors overlay the area defined by fileB
  232.  */
  233.  
  234. short      *member;      /* Concatenated equiv. classes  */
  235. long      *newseek;      /* Seek position in file B  */
  236. char      *textb;        /* Input from file2 for check  */
  237.  
  238. /*
  239.  * Global variables
  240.  */
  241.  
  242. int      eflag  = FALSE;  /* Edit script requested  */
  243. int      bflag  = FALSE;  /* Blank supress requested  */
  244. int      cflag  = FALSE;  /* Context printout      */
  245. int      iflag  = FALSE;  /* Ignore case requested  */
  246. char      text[257];      /* Input line from file1  */
  247. extern char  *myalloc();      /* Storage allocator      */
  248.  
  249. extern char  *compact();      /* Storage compactor      */
  250.  
  251. #ifdef  DEBUG
  252. #ifndef OSK
  253. #define  TIMING
  254. #endif
  255. #endif
  256. #ifdef  TIMING
  257. extern long  time();
  258. extern char  *$$mend;
  259. long      totaltime;
  260. long      sectiontime;
  261. char      *mstart;
  262. #endif
  263.  
  264. main(argc, argv)
  265. int      argc;
  266. char      **argv;
  267. /*
  268.  * Diff main program
  269.  */
  270. {
  271.   register int  i;
  272.   register char  *ap;
  273.  
  274. #ifdef OSK
  275.   extern int _memmins;
  276.   _memmins = 16 * 1024;            /* tell OSK we will malloc a lot */
  277. #endif
  278. #ifdef  TIMING
  279.   sectiontime = time(&totaltime);
  280. #endif
  281. #ifdef vms
  282.   argc = getredirection(argc,argv);
  283. #endif
  284.   while (argc > 1 && *(ap = argv[1]) == '-' && *++ap != EOS) {
  285.       while (*ap != EOS) {
  286.         switch ((*ap++)) {
  287.         case 'b':
  288.               bflag++;
  289.               break;
  290.  
  291.         case 'c':
  292.           if (*ap > '0' && *ap <= '9') cflag = *ap++ - '0';
  293.           else cflag = 3;
  294.           break;
  295.  
  296.         case 'e':
  297.               eflag++;
  298.               break;
  299.  
  300.         case 'i':
  301.               iflag++;
  302.               break;
  303.  
  304.         default:
  305.               fprintf(stderr,
  306.                   "Warning, bad option '%c'\n",
  307.                   ap[-1]);
  308.               break;
  309.         }
  310.       }
  311.       argc--;
  312.       argv++;
  313.   }
  314.  
  315.   if (argc != 3)
  316.       error("Usage: diff [-options] file1 file2");
  317.   if (cflag && eflag) {
  318.       fprintf(stderr,
  319.         "Warning, -c and -e are incompatible, -c supressed.\n");
  320.       cflag = FALSE;
  321.   }
  322.   argv++;
  323.   for (i = 0; i <= 1; i++) {
  324.       if (argv[i][0] == '-' && argv[i][1] == EOS) {
  325.         infd[i] = stdin;
  326.         if ((tempfd = fopen(TEMPFILE, "w")) == NULL)
  327.             cant(TEMPFILE, "work", 1);
  328.       }
  329.       else {
  330.         infd[i] = fopen(argv[i], "r");
  331.       if (!infd[i]) cant(argv[i], "input", 2);    /* Fatal error */
  332.       }
  333.   }
  334.  
  335.   if (infd[0] == stdin && infd[1] == stdin)
  336.     error("Can't diff two things both on standard input.");
  337.  
  338.   if (infd[0] == NULL && infd[1] == NULL) {
  339.       cant(argv[0], "input", 0);
  340.       cant(argv[1], "input", 1);
  341.   }
  342. #ifdef vms
  343.   else if (infd[1] == NULL)
  344.       opendir(1, &argv[1], infd[0]);
  345.   else if (infd[0] == NULL)
  346.       opendir(0, &argv[0], infd[1]);
  347. #endif
  348.  
  349.  /*
  350.    * Read input, building hash tables.
  351.    */
  352.   input(0);
  353.   input(1);
  354.   squish();
  355. #ifdef  DEBUG
  356.   printf("before sort\n");
  357.   for (i = 1; i <= slenA; i++)
  358.       printf("sfileA[%d] = %6d %06o\n",
  359.         i, sfileA[i].serial, sfileA[i].hash);
  360.   for (i = 1; i <= slenB; i++)
  361.       printf("sfileB[%d] = %6d %06o\n",
  362.         i, sfileB[i].serial, sfileB[i].hash);
  363. #endif
  364.   sort(sfileA, slenA);
  365.   sort(sfileB, slenB);
  366. #ifdef  TIMING
  367.   ptime("input");
  368. #endif
  369. #ifdef  DEBUG
  370.   printf("after sort\n");
  371.   for (i = 1; i <= slenA; i++)
  372.       printf("sfileA[%d] = %6d %06o\n",
  373.         i, sfileA[i].serial, sfileB[i].hash);
  374.   for (i = 1; i <= slenB; i++)
  375.       printf("sfileB[%d] = %6d %06o\n",
  376.         i, sfileB[i].serial, sfileB[i].hash);
  377. #endif
  378.   /*
  379.    * Build equivalence classes.
  380.    */
  381.   member = (short *)fileB;
  382.   equiv();
  383.   member = (short *)compact((char *)member, (slenB + 2) * sizeof (int),
  384.         "squeezing member vector");
  385.   /*
  386.    * Reorder equivalence classes into array class[]
  387.    */
  388.   class = (short *)fileA;
  389.   unsort();
  390.   class = (short *)compact((char *)class, (slenA + 2) * sizeof (int),
  391.         "compacting class vector");
  392. #ifdef  TIMING
  393.   ptime("equiv/unsort");
  394. #endif
  395.   /*
  396.     * Find longest subsequences
  397.    */
  398.   klist = (int *)myalloc((slenA + 2) * sizeof (int), "klist");
  399.   clist = (CANDIDATE *)myalloc(csize * sizeof (CANDIDATE), "clist");
  400.   i = subseq();
  401. #ifndef OSK
  402.   free((char *)member);
  403.   free((char *)class);
  404. #else
  405.   free((char *)member - sizeof(int));
  406.   free((char *)class - sizeof(int));
  407. #endif
  408.   match = (int *)myalloc((lenA + 2) * sizeof (int), "match");
  409.   unravel(klist[i]);
  410. #ifndef OSK
  411.   free((char *)clist);
  412.   free((char *)klist);
  413. #else
  414.   free((char *)clist - sizeof(int));
  415.   free((char *)klist - sizeof(int));
  416. #endif
  417. #ifdef  TIMING
  418.   ptime("subsequence/unravel");
  419. #endif
  420.   /*
  421.    * Check for fortuitous matches and output differences
  422.    */
  423.   oldseek = (long *)myalloc((lenA + 2) * sizeof (* oldseek), "oldseek");
  424.   newseek = (long *)myalloc((lenB + 2) * sizeof (* newseek), "newseek");
  425.   textb = myalloc(sizeof text, "textbuffer");
  426.   if (check(argv[0], argv[1]))
  427.       fprintf(stderr, "Spurious match, output is not optimal\n");
  428. #ifdef  TIMING
  429.   ptime("check");
  430. #endif
  431.   output(argv[0], argv[1]);
  432. #ifdef  TIMING
  433.   ptime("output");
  434.   printf("%ld seconds required\n", sectiontime - totaltime);
  435. #endif
  436.   if (tempfd != NULL) {
  437.       fclose(tempfd);
  438. #ifdef unix
  439.       unlink(TEMPFILE);
  440. #else
  441. #ifdef OSK
  442.     unlink(TEMPFILE);
  443. #else
  444. #ifdef MSC            /*  MSC 4.0 does not understand disjunctive
  445.                     #if's.  */
  446.     unlink(TEMPFILE);
  447. #else
  448.     remove(TEMPFILE);
  449. #endif
  450. #endif
  451. #endif
  452.   }
  453. }
  454.  
  455.  
  456. input(which)
  457. int      which;        /* 0 or 1 to redefine infd[]  */
  458. /*
  459.  * Read the file, building hash table
  460.  */
  461. {
  462.   register LINE      *lentry;
  463.   register int      linect = 0;
  464.   FILE        *fd;
  465. #define    LSIZE_INC 200    /* # of line entries to alloc at once */
  466.   int    lsize = LSIZE_INC;
  467.  
  468.   lentry = (LINE *)myalloc(sizeof(LINE) * (lsize+3), "line");
  469.   fd = infd[which];
  470.   while (!getline(fd, text)) {
  471.     if (++linect >= lsize) {
  472.         lsize += 200;
  473.         lentry = (LINE *)compact((char *)lentry,
  474.           (lsize + 3) * sizeof(LINE),
  475.           "extending line vector");
  476.     }
  477.       lentry[linect].hash = hash(text);
  478.   }
  479.   /*
  480.    * If input was from stdin ("-" command), finish off the temp file.
  481.    */
  482.   if (fd == stdin) {
  483.       fclose(tempfd);
  484.       tempfd = infd[which] = fopen(TEMPFILE, "r");
  485.   }
  486.   /* If we wanted to be stingy with memory, we could realloc lentry down
  487.    * to its exact size (+3 for some odd reason) here.  No need?  */
  488.   len[which] = linect;
  489.   file[which] = lentry;
  490. }
  491.  
  492. squish()
  493. /*
  494.  * Look for initial and trailing sequences that have identical hash values.
  495.  * Don't bother building them into the candidate vector.
  496.  */
  497. {
  498.   register int  i;
  499.   register LINE  *ap;
  500.   register LINE  *bp;
  501.   int      j;
  502.   int      k;
  503.  
  504.   /*
  505.    * prefix -> first line (from start) that doesn't hash identically
  506.    */
  507.   i = 0; ap = &fileA[1]; bp = &fileB[1];
  508.   while (i < lenA && i < lenB && ap->hash == bp->hash) {
  509.       i++; ap++; bp++;
  510.   }
  511.   prefix = i;
  512.   /*
  513.     * suffix -> first line (from end) that doesn't hash identically
  514.    */
  515.   j = lenA - i;
  516.   k = lenB - i;
  517.   ap = &fileA[lenA];
  518.   bp = &fileB[lenB];
  519.   i = 0;
  520.   while (i < j && i < k && ap->hash == bp->hash) {
  521.       i++; ap--; bp--;
  522.   }
  523.   suffix = i;
  524.   /*
  525.    * Tuck the counts away
  526.    */
  527.   for (k = 0; k <= 1; k++) {
  528.       sfile[k] = file[k] + prefix;
  529.       j = slen[k] = len[k] - prefix - suffix;
  530.  
  531.       for (i = 0, ap = sfile[k]; i <= slen[k]; i++, ap++) {
  532.         ap->serial = i;
  533.       }
  534.   }
  535. }
  536.  
  537. sort(vector, vecsize)
  538. LINE      *vector;      /* What to sort        */
  539. int      vecsize;      /* How many to sort      */
  540. /*
  541.  * Sort hash entries
  542.  */
  543. {
  544.   register int  j;
  545.   register LINE  *aim;
  546.   register LINE  *ai;
  547.   int      mid;  
  548.   int      k;
  549.   LINE      work;
  550.  
  551.   for (j = 1; j <= vecsize; j *= 2);
  552.   mid = (j - 1);
  553.   while ((mid /= 2) != 0) {
  554.       k = vecsize - mid;
  555.       for (j = 1; j <= k; j++) {
  556.         for (ai = &vector[j]; ai > vector; ai -= mid) {
  557.             aim = &ai[mid];
  558.             if (aim < ai)
  559.               break;  /* ?? Why ??      */
  560.             if (aim->hash > ai->hash ||
  561.                   aim->hash == ai->hash &&
  562.                   aim->serial > ai->serial)
  563.               break;
  564.             work.hash = ai->hash;
  565.             ai->hash = aim->hash;
  566.             aim->hash = work.hash;
  567.             work.serial = ai->serial;
  568.             ai->serial = aim->serial;
  569.             aim->serial = work.serial;
  570.         }
  571.       }
  572.   }
  573. }
  574.  
  575. equiv()
  576. /*
  577.  * Build equivalence class vector
  578.  */
  579. {
  580.   register LINE  *ap;
  581. #ifdef TURBO
  582.   union {
  583. #else
  584.   register union {
  585. #endif
  586.       LINE    *bp;
  587.       short    *mp;
  588.   } r;
  589.   register int  j;
  590.   LINE    *atop;
  591.  
  592. #ifdef  DEBUG
  593.   printf("equiv entry\n");
  594.   for (j = 1; j <= slenA; j++)
  595.       printf("sfileA[%d] = %6d %06o\n",
  596.             j, sfileA[j].serial, sfileA[j].hash);
  597.   for (j = 1; j <= slenB; j++)
  598.       printf("sfileB[%d] = %6d %06o\n",
  599.             j, sfileB[j].serial, sfileB[j].hash);
  600. #endif
  601.   j = 1;
  602.   ap = &sfileA[1];
  603.   r.bp = &sfileB[1];
  604.   atop = &sfileA[slenA];
  605.   while (ap <= atop && j <= slenB) {
  606.       if (ap->hash < r.bp->hash) {
  607.         ap->hash = 0;
  608.         ap++;
  609.       }
  610.       else if (ap->hash == r.bp->hash) {
  611.         ap->hash = j;
  612.         ap++;
  613.       }
  614.       else {
  615.         r.bp++;
  616.         j++;
  617.       }
  618.   }
  619.   while (ap <= atop) {
  620.       ap->hash = 0;
  621.       ap++;
  622.   }
  623.   sfileB[slenB + 1].hash = 0;
  624. #ifdef  DEBUG
  625.   printf("equiv exit\n");
  626.   for (j = 1; j <= slenA; j++)
  627.       printf("sfileA[%d] = %6d %06o\n",
  628.             j, sfileA[j].serial, sfileA[j].hash);
  629.   for (j = 1; j <= slenB; j++)
  630.       printf("sfileB[%d] = %6d %06o\n",
  631.             j, sfileB[j].serial, sfileB[j].hash);
  632. #endif
  633.   ap = &sfileB[0];
  634.   atop = &sfileB[slenB];
  635.   r.mp = &member[0];
  636.   while (++ap <= atop) {
  637.       r.mp++;
  638.       *r.mp = -(ap->serial);
  639.       while (ap[1].hash == ap->hash) {
  640.         ap++;
  641.         r.mp++;
  642.         *r.mp = ap->serial;
  643.       }
  644.   }
  645.   r.mp[1] = -1;
  646. #ifdef  DEBUG
  647.   for (j = 0; j <= slenB; j++)
  648.       printf("member[%d] = %d\n", j, member[j]);
  649. #endif
  650. }
  651.  
  652. unsort()
  653. /*
  654.  * Build class vector
  655.  */
  656. {
  657.   register int  *temp;
  658.   register int  *tp;
  659. #if TURBO
  660.   union {
  661. #else
  662.   register union {
  663. #endif
  664.       LINE    *ap;
  665.       short    *cp;
  666.   } u;
  667.   LINE    *evec;
  668.   short    *eclass;
  669. #ifdef  DEBUG
  670.   int      i;
  671. #endif
  672.  
  673.   temp = (int *)myalloc((slenA + 1) * sizeof(int), "unsort scratch");
  674.   u.ap = &sfileA[1];
  675.   evec = &sfileA[slenA];
  676.   while (u.ap <= evec) {
  677. #ifdef  DEBUG
  678.       printf("temp[%2d] := %06o\n", u.ap->serial, u.ap->hash);
  679. #endif
  680.       temp[u.ap->serial] = u.ap->hash;
  681.       u.ap++;
  682.   }
  683.   /*
  684.    * Copy into class vector and free work space
  685.    */
  686.   u.cp = &class[1];
  687.   eclass = &class[slenA];
  688.   tp = &temp[1];
  689.   while (u.cp <= eclass)
  690.       *u.cp++ = *tp++;
  691. #ifndef OSK
  692.   free((char *) temp);
  693. #else
  694.   free((char *)temp - sizeof(int));
  695. #endif
  696. #ifdef  DEBUG
  697.   printf("unsort exit\n");
  698.   for (i = 1; i <= slenA; i++)
  699.       printf("class[%d] = %d %06o\n", i, class[i], class[i]);
  700. #endif
  701. }
  702.  
  703. subseq()
  704. /*
  705.  * Generate maximum common subsequence chain in clist[]
  706.  */
  707. {
  708.   int        a;
  709.   register unsigned      ktop;
  710.   register int      b;
  711.   register int      s;
  712.   unsigned        r;
  713.   int        i;
  714.   int        cand;
  715.  
  716.   klist[0] = newcand(0, 0, -1);
  717.   klist[1] = newcand(slenA + 1, slenB + 1, -1);
  718.   ktop = 1;            /* -> guard entry  */
  719.   for (a = 1; a <= slenA; a++) {
  720.       /*
  721.        * For each non-zero element in fileA ...
  722.        */
  723.       if ((i = class[a]) == 0)
  724.         continue;
  725.       cand = klist[0];      /* No candidate now  */
  726.       r = 0;            /* Current r-candidate  */
  727.       do {
  728. #ifdef  DEBUG
  729.         printf("a = %d, i = %d, b = %d\n", a, i, member[i]);
  730. #endif
  731.         /*
  732.          * Perform the merge algorithm
  733.          */
  734.         if ((b = member[i]) < 0)
  735.             b = -b;
  736. #ifdef  DEBUG
  737.         printf("search(%d, %d, %d) -> %d\n",
  738.               r, ktop, b, search(r, ktop, b));
  739. #endif
  740.         if ((s = search(r, ktop, b)) != 0) {
  741.             if (clist[klist[s]].b > b) {
  742.               klist[r] = cand;
  743.               r = s;
  744.               cand = newcand(a, b, klist[s-1]);
  745. #ifdef  DEBUG
  746.               dumpklist(ktop, "klist[s-1]->b > b");
  747. #endif
  748.             }
  749.             if (s >= ktop) {
  750.               klist[ktop + 1] = klist[ktop];
  751.               ktop++;
  752. #ifdef  DEBUG
  753.               klist[r] = cand;
  754.               dumpklist(ktop, "extend");
  755. #endif
  756.               break;
  757.             }
  758.         }
  759.       } while (member[++i] > 0);
  760.     klist[r] = cand;
  761.   }
  762. #ifdef  DEBUG
  763.   printf("last entry = %d\n", ktop - 1);
  764. #endif
  765.   return(ktop - 1);        /* Last entry found  */
  766. }
  767.  
  768. int
  769. newcand(a, b, pred)
  770. int      a;      /* Line in fileA        */
  771. int      b;      /* Line in fileB        */
  772. int      pred;      /* Link to predecessor, index in cand[]  */
  773. {
  774.   register CANDIDATE  *new;
  775.  
  776.   clength++;
  777.   if (++clength >= csize) {
  778.     csize += CSIZE_INC;
  779.     clist = (CANDIDATE *)compact((char *)clist,
  780.           csize * sizeof (CANDIDATE),
  781.           "extending clist");
  782.   }
  783.   new = &clist[clength - 1];
  784.   new->a = a;
  785.   new->b = b;
  786.   new->link = pred;
  787.   return(clength - 1);
  788. }
  789.  
  790. search(low, high, b)
  791. register unsigned  low;
  792. register unsigned  high;
  793. register int  b;
  794. /*
  795.  * Search klist[low..top] (inclusive) for b.  If klist[low]->b >= b,
  796.  * return zero.  Else return s such that klist[s-1]->b < b and
  797.  * klist[s]->b >= b.  Note that the algorithm presupposes the two
  798.  * preset "fence" elements, (0, 0) and (slenA, slenB).
  799.  */
  800. {
  801.   register int      temp;
  802.   register unsigned      mid;
  803.  
  804.   if (clist[klist[low]].b >= b)
  805.       return(0);
  806.   while ((mid = (low + high) / 2) > low) {
  807.       if ((temp = clist[klist[mid]].b) > b)
  808.         high = mid;
  809.       else if (temp < b)
  810.         low = mid;
  811.       else {
  812.         return(mid);
  813.       }
  814.   }
  815.   return(mid + 1);
  816. }
  817.  
  818.  
  819. unravel(k)
  820. register int  k;
  821. {
  822.   register int      i;
  823.   register CANDIDATE  *cp;
  824.   int        first_trailer;
  825.   int        difference;
  826.  
  827.   first_trailer = lenA - suffix;
  828.   difference = lenB - lenA;
  829. #ifdef  DEBUG
  830.   printf("first trailer = %d, difference = %d\n",
  831.       first_trailer, difference);
  832. #endif
  833.   for (i = 0; i <= lenA; i++) {
  834.       match[i] = (i <= prefix) ? i
  835.         : (i > first_trailer) ? i + difference
  836.         : 0;
  837.   }
  838. #ifdef  DEBUG
  839.   printf("unravel\n");
  840. #endif
  841.   while (k != -1) {
  842.       cp = &clist[k];
  843. #ifdef  DEBUG
  844.       if (k < 0 || k >= clength)
  845.         error("Illegal link -> %d", k);
  846.       printf("match[%d] := %d\n", cp->a + prefix, cp->b + prefix);
  847. #endif
  848.       match[cp->a + prefix] = cp->b + prefix;
  849.       k = cp->link;
  850.   }
  851. }
  852.  
  853.  
  854. /*
  855.  * Check for hash matches (jackpots) and collect random access indices to
  856.  * the two files.
  857.  *
  858.  * It should be possible to avoid doing most of the ftell's by noticing
  859.  * that we are not doing a context diff and noticing that if a line
  860.  * compares equal to the other file, we will not ever need to know its
  861.  * file position.  FIXME.
  862.  */
  863. check(fileAname, fileBname)
  864. char      *fileAname;
  865. char      *fileBname;
  866. {
  867.   register int  a;      /* Current line in file A  */
  868.   register int  b;      /* Current line in file B  */
  869.   int      jackpot;
  870.  
  871. /*
  872.  * The VAX C ftell() returns the address of the CURRENT record, not the
  873.  * next one (as in DECUS C or, effectively, other C's).  Hence, the values
  874.  * are "off by one" in the array.  OFFSET compensates for this.
  875.  */
  876. #ifdef vms
  877. #define OFFSET (-1)
  878. #else
  879. #define OFFSET 0
  880. #endif
  881.  
  882.   b = 1;
  883.   rewind(infd[0]);
  884.   rewind(infd[1]);
  885. /*
  886.  * See above; these would be over-written on VMS anyway.
  887.  */
  888. #ifndef vms
  889.   oldseek[0] = ftell(infd[0]);
  890.   newseek[0] = ftell(infd[1]);
  891. #endif
  892.  
  893.   jackpot = 0;
  894. #ifdef  DEBUG
  895.   printf("match vector\n");
  896.   for (a = 0; a <= lenA; a++)
  897.       printf("match[%d] = %d\n", a, match[a]);
  898. #endif
  899.   for (a = 1; a <= lenA; a++) {
  900.       if (match[a] == 0) {
  901.       /* Unique line in A */
  902.         oldseek[a+OFFSET] = ftell(infd[0]);
  903.         getline(infd[0], text);
  904.         continue;  
  905.       }
  906.       while (b < match[a]) {
  907.       /* Skip over unique lines in B */
  908.         newseek[b+OFFSET] = ftell(infd[1]);
  909.         getline(infd[1], textb);
  910.         b++;
  911.       }
  912.  
  913.     /*
  914.      * Compare the two, supposedly matching, lines.
  915.      * Unless we are going to print these lines, don't bother to
  916.      * remember where they are.  We only print matching lines
  917.      * if a context diff is happening, or if a jackpot occurs.
  918.      */
  919.     if (cflag) {
  920.         oldseek[a+OFFSET] = ftell(infd[0]);
  921.         newseek[b+OFFSET] = ftell(infd[1]);
  922.     }
  923.       getline(infd[0], text);
  924.       getline(infd[1], textb);
  925.       if (!streq(text, textb)) {
  926.         fprintf(stderr,  "Spurious match:\n");
  927.         fprintf(stderr, "line %d in %s, \"%s\"\n",
  928.             a, fileAname, text);
  929.         fprintf(stderr, "line %d in %s, \"%s\"\n",
  930.             b, fileBname, textb);
  931.         match[a] = 0;
  932.         jackpot++;
  933.       }
  934.  
  935.       b++;
  936.   }
  937.   for (; b <= lenB; b++) {
  938.       newseek[b+OFFSET] = ftell(infd[1]);
  939.       getline(infd[1], textb);
  940.   }
  941. /*
  942.  * The logical converse to the code up above, for NON-VMS systems, to
  943.  * store away an fseek() pointer at the beginning of the file.  For VMS,
  944.  * we need one at EOF...
  945.  */
  946. #ifdef vms
  947.   oldseek[lenA] = ftell(infd[0]);
  948.   getline(infd[0],text);        /* Will hit EOF...  */
  949.   newseek[lenB] = ftell(infd[1]);
  950.   getline(infd[1],textb);        /* Will hit EOF...  */
  951. #endif
  952.  
  953.   return(jackpot);
  954. }
  955.  
  956. output(fileAname, fileBname)
  957. char *fileAname, *fileBname;
  958. {
  959.   register int  astart;
  960.   register int  aend = 0;
  961.   int      bstart;
  962.   register int  bend;
  963.  
  964.   rewind(infd[0]);
  965.   rewind(infd[1]);
  966.   match[0] = 0;
  967.   match[lenA+1] = lenB + 1;
  968.   if (!eflag) {
  969.     if (cflag) {
  970.         /*
  971.          * Should include ctime style dates after the file names, but
  972.          * this would be non-trivial on OSK.  Perhaps there should be
  973.          * a special case for stdin.
  974.          */
  975.         printf("*** %s\n--- %s\n", fileAname, fileBname);
  976.     }
  977.       /*
  978.        * Normal printout
  979.        */
  980.       for (astart = 1; astart <= lenA; astart = aend + 1) {
  981.         /*
  982.          * New subsequence, skip over matching stuff
  983.          */
  984.         while (astart <= lenA
  985.               && match[astart] == (match[astart - 1] + 1))
  986.             astart++;
  987.         /*
  988.          * Found a difference, setup range and print it
  989.          */
  990.         bstart = match[astart - 1] + 1;
  991.         aend = astart - 1;
  992.         while (aend < lenA && match[aend + 1] == 0)
  993.             aend++;
  994.         bend = match[aend + 1] - 1;
  995.         match[aend] = bend;
  996.         change(astart, aend, bstart, bend);
  997.       }
  998.   }
  999.   else {
  1000.       /*
  1001.        * Edit script output -- differences are output "backwards"
  1002.        * for the benefit of a line-oriented editor.
  1003.        */
  1004.       for (aend = lenA; aend >= 1; aend = astart - 1) {
  1005.         while (aend >= 1
  1006.               && match[aend] == (match[aend + 1] - 1)
  1007.               && match[aend] != 0)
  1008.             aend--;
  1009.         bend = match[aend + 1] - 1;
  1010.         astart = aend + 1;
  1011.         while (astart > 1 && match[astart - 1] == 0)
  1012.             astart--;
  1013.         bstart = match[astart - 1] + 1;
  1014.         match[astart] = bstart;
  1015.         change(astart, aend, bstart, bend);
  1016.       }
  1017.   }
  1018.   if (lenA == 0)
  1019.       change(1, 0, 1, lenB);
  1020. }
  1021.  
  1022.  
  1023. /*
  1024.  * Output a change entry: fileA[astart..aend] changed to fileB[bstart..bend]
  1025.  */
  1026. change(astart, aend, bstart, bend)
  1027. int      astart;
  1028. int      aend;
  1029. int      bstart;
  1030. int      bend;
  1031. {
  1032.   char c;
  1033.   /*
  1034.    * This catches a "dummy" last entry
  1035.    */
  1036.   if (astart > aend && bstart > bend)
  1037.       return;
  1038.   c = (astart > aend) ? 'a' : (bstart > bend) ? 'd' : 'c';
  1039.   if (cflag) fputs("**************\n*** ", stdout);
  1040.  
  1041.   if (c == 'a' && !cflag)
  1042.     range(astart-1, astart-1, 0);    /* Addition: just print one odd # */
  1043.   else
  1044.     range(astart, aend, 0);        /* Print both, if different */
  1045.   if (!cflag) {
  1046.     putchar(c);
  1047.     if (!eflag) {
  1048.     if (c == 'd')
  1049.         range(bstart-1, bstart-1, 1); /* Deletion: just print one odd # */
  1050.     else
  1051.         range(bstart, bend, 1);    /* Print both, if different */
  1052.     }
  1053.   }
  1054.   putchar('\n');
  1055.   if ((!eflag && c != 'a') || cflag) {
  1056.       fetch(oldseek, astart, aend, lenA, infd[0], 
  1057.         cflag ? (c=='d' ? "- " : "! ") : "< ");
  1058.     if (cflag) {
  1059.       fputs("--- ", stdout);
  1060.       range(bstart, bend, 1);
  1061.       fputs(" -----\n", stdout);
  1062.     } else if (astart <= aend && bstart <= bend)
  1063.         printf("---\n");
  1064.   }
  1065.   fetch(newseek, bstart, bend, lenB, infd[1], 
  1066.       cflag ? (c=='a' ? "+ " : "! ") : (eflag ? "" : "> "));
  1067.   if (eflag && bstart <= bend)
  1068.       printf(".\n");
  1069. }
  1070.  
  1071.  
  1072. range(from, to, w)
  1073. int      from;
  1074. int      to;
  1075. int    w;
  1076. /*
  1077.  * Print a range
  1078.  */
  1079. {
  1080.   if (cflag) {
  1081.     if((from -= cflag) <= 0) from = 1;
  1082.     if((to += cflag) > len[w]) to = len[w];
  1083.   }
  1084.   if (to > from) {
  1085.     printf("%d,%d", from, to);
  1086.   } else if (to < from) {
  1087.     printf("%d,%d", to, from);
  1088.   } else {
  1089.     printf("%d", from);
  1090.   }
  1091. }
  1092.  
  1093.  
  1094. fetch(seekvec, start, end, trueend, fd, pfx)
  1095. long      *seekvec;
  1096. register int  start;
  1097. register int  end;
  1098. int      trueend;
  1099. FILE      *fd;
  1100. char      *pfx;
  1101. /*
  1102.  * Print the appropriate text
  1103.  */
  1104. {
  1105.   register int  i;
  1106.   register int    first;
  1107.   register int    last;
  1108.  
  1109.   if (cflag) {
  1110.     if((first = start - cflag) <= 0) first = 1;
  1111.     if((last = end + cflag) > trueend) last = trueend;
  1112.   } else {
  1113.     first = start;
  1114.     last = end;
  1115.   }
  1116.   if (fseek(fd, seekvec[first], 0) != 0) {
  1117.       printf("?Can't read line %d at %08lx (hex) in file%c\n",
  1118.         start, seekvec[first],
  1119.         (fd == infd[0]) ? 'A' : 'B');
  1120.   }
  1121.   else {
  1122.       for (i = first; i <= last; i++) {
  1123.         if (fgetss(text, sizeof text, fd) == NULL) {
  1124.             printf("** Unexpected end of file\n");
  1125.             break;
  1126.         }
  1127. #ifdef DEBUG
  1128.         printf("%5d: %s%s\n", i, pfx, text);
  1129. #else
  1130.         fputs((cflag && (i<start || i>end)) ? "  " : pfx, stdout);
  1131.         fputs(text, stdout);
  1132.       putchar('\n');
  1133. #endif
  1134.       }
  1135.   }  
  1136. }
  1137.  
  1138.  
  1139. /*
  1140.  * Input routine, read one line to buffer[], return TRUE on eof, else FALSE.
  1141.  * The terminating newline is always removed.  If "-b" was given, trailing
  1142.  * whitespace (blanks and tabs) are removed and strings of blanks and
  1143.  * tabs are replaced by a single blank.  Getline() does all hacking for
  1144.  * redirected input files.
  1145.  */
  1146. int
  1147. getline(fd, buffer)
  1148. FILE      *fd;
  1149. char      *buffer;
  1150. {
  1151.   register char  *top;
  1152.   register char  *fromp;
  1153.   register char  c;
  1154.  
  1155.   if (fgetss(buffer, sizeof text, fd) == NULL) {
  1156.       *buffer = EOS;
  1157.       return(TRUE);
  1158.   }
  1159.   if (fd == stdin)
  1160.       fputss(buffer, tempfd);
  1161.   if (bflag || iflag) {
  1162.       top = buffer;
  1163.       fromp = buffer;
  1164.       while ((c = *fromp++) != EOS) {
  1165.         if (bflag && (c == ' ' || c == '\t')) {
  1166.             c = ' ';
  1167.             while (*fromp == ' ' || *fromp == '\t')
  1168.               fromp++;
  1169.         }
  1170.         if (iflag)
  1171.             c = tolower(c);
  1172.         *top++ = c;
  1173.       }
  1174.       if (bflag && top[-1] == ' ')
  1175.         top--;
  1176.       *top = EOS;
  1177.   }
  1178.   return(FALSE);
  1179. }
  1180. static unsigned short crc16a[] = {
  1181.   0000000,  0140301,  0140601,  0000500,
  1182.   0141401,  0001700,  0001200,  0141101,
  1183.   0143001,  0003300,  0003600,  0143501,
  1184.   0002400,  0142701,  0142201,  0002100,  
  1185. };
  1186. static unsigned short crc16b[] = {
  1187.   0000000,  0146001,  0154001,  0012000,
  1188.   0170001,  0036000,  0024000,  0162001,
  1189.   0120001,  0066000,  0074000,  0132001,
  1190.   0050000,  0116001,  0104001,  0043000,
  1191. };
  1192.  
  1193. unsigned short
  1194. hash(buffer)
  1195. char      *buffer;
  1196. /*
  1197.  * Return the CRC16 hash code for the buffer
  1198.  * Algorithm from Stu Wecker (Digital memo 130-959-002-00).
  1199.  */
  1200. {
  1201.   register unsigned short  crc;
  1202.   register char      *tp;
  1203.   register short       temp;
  1204.  
  1205.   crc = 0;
  1206.   for (tp = buffer; *tp != EOS;) {
  1207.       temp = *tp++ ^ crc;  /* XOR crc with new char  */
  1208.       crc = (crc >> 8)
  1209.         ^ crc16a[(temp & 0017)]
  1210.         ^ crc16b[(temp & 0360) >> 4];
  1211.   }
  1212. #ifdef  DEBUG_ALL
  1213.   printf("%06o: %s\n", (crc == 0) ? 1 : crc, buffer);
  1214. #endif
  1215.   return((crc == 0) ? (unsigned short) 1 : crc);
  1216. }      
  1217.  
  1218.  
  1219. #ifdef vms
  1220. opendir(which, arg, okfd)
  1221. int      which;      /* Which file to open (0 or 1)      */
  1222. char      **arg;      /* File name argument, &argv[which]  */
  1223. FILE      *okfd;      /* File name (already open)      */
  1224. {
  1225.   register char      *tp;
  1226.   register int      c;
  1227.   register char      *newname;
  1228.  
  1229.   fgetname(okfd, text);
  1230.   /*
  1231.    * Skip over device name
  1232.    */
  1233.   for (tp = text; (c = *tp) && c != ':'; tp++);
  1234.   if (c)  tp++;
  1235.   else  tp = text;
  1236.   /*
  1237.    * Skip over [UIC] or [PPN] if present
  1238.    */
  1239.   if (*tp == '[' || *tp == '(') {
  1240.       while ((c = *tp++) && c != ']' && c != ')');
  1241.       if (c == 0) {
  1242.         fprintf(stderr, "?Bug: bad file name \"%s\"\n",
  1243.               text);
  1244.         tp--;
  1245.       }
  1246.   }
  1247.   strcpy(text, tp);
  1248.   /*
  1249.    * Don't include version
  1250.    */
  1251.   for (tp = text; (c = *tp) && c != ';'; tp++);
  1252.   *tp = 0;
  1253.   /*
  1254.    * Now, text has the file name, tp - text, its length,
  1255.    * and *arg the (possible) directory name.  Create a new
  1256.    * file name for opening.
  1257.    */
  1258. #ifndef    OSK
  1259.   if ((newname = malloc(tp - text + strlen(*arg) + 1)) == NULL)
  1260.       error("Out of space at start");
  1261. #ifdef    AMIGA
  1262.     savsiz = tp - text + strlen(*arg) + 1;
  1263.     savptr = newname;
  1264. #endif
  1265. #else
  1266.   newname = myalloc(tp - text + strlen(*arg) + 1, "Out of space at start");
  1267. #endif
  1268.   concat(newname, *arg, text, NULL);
  1269.   if ((infd[which] = fopen(newname, "r")) == NULL)
  1270.       cant(*arg, "constructed input", 1);
  1271.   else
  1272.       *arg = newname;
  1273. }
  1274. /* Amiga C doesn't have all these extensions for directory... */
  1275. #endif
  1276.  
  1277. char *
  1278. myalloc(amount, why)
  1279. int      amount;
  1280. char      *why;
  1281. /*
  1282.  * Allocate or crash.
  1283.  */
  1284. {
  1285.   register char  *pointer;
  1286.  
  1287. #ifdef OSK
  1288.   amount += sizeof(int);
  1289. #endif
  1290.   if ((pointer = malloc((unsigned) amount)) == NULL)
  1291.       noroom(why);
  1292. #ifdef OSK
  1293.   *((int *)pointer) = amount;
  1294.   pointer += sizeof(int);
  1295. #ifdef DEBUG
  1296.   fprintf(stderr, "Myalloc: %d at %06o\n", amount, pointer);
  1297. #endif
  1298. #endif
  1299. #ifdef    AMIGA
  1300.    savsiz =  amount;
  1301.    savptr = pointer;
  1302. #endif
  1303.  
  1304.   return (pointer);
  1305. }
  1306.  
  1307.  
  1308. /*
  1309.  * Reallocate pointer, compacting storage
  1310.  *
  1311.  * The "compacting storage" part is probably not relevant any more.
  1312.  * There used to be horrid code here that malloc'd one byte and freed
  1313.  * it at magic times, to cause garbage collection of the freespace
  1314.  * or something.  It's safely gone now, you didn't have to see it.
  1315.  *    -- John Gilmore, Nebula Consultants, Sept 26, 1986
  1316.  */
  1317. char *
  1318. compact(pointer, new_amount, why)
  1319. char      *pointer;
  1320. int      new_amount;
  1321. char      *why;
  1322. {
  1323.   register char *new_pointer;
  1324.  
  1325. #ifndef AMIGA
  1326. #ifndef OSK
  1327. #ifdef TURBO
  1328.   extern void *realloc();
  1329. #else
  1330.   extern char *realloc();
  1331. #endif
  1332.  
  1333.   if ((new_pointer =  realloc(pointer, (unsigned) new_amount)) == NULL){
  1334.       noroom(why);
  1335.   }
  1336. #else
  1337.   register int old_amount;
  1338.   new_amount += sizeof(int);
  1339.   if((new_pointer = malloc(new_amount)) == NULL) noroom(why);
  1340.   *(int *)new_pointer = new_amount;
  1341.   new_pointer += sizeof(int);
  1342.   old_amount = *(((int *)pointer)-1);
  1343.   /* _strass is like bcopy with the first two arguments reversted */
  1344.   _strass(new_pointer, pointer, (new_amount <= old_amount ?
  1345.       new_amount : old_amount) - sizeof(int));
  1346. #ifdef DEBUG
  1347.   fprintf(stderr, "compact %d to %d from %06o to %06o\n", 
  1348.     old_amount, new_amount, pointer, new_pointer);
  1349. #endif
  1350.   free(pointer - sizeof(int));
  1351. #endif
  1352. #else
  1353.   /*
  1354.    * This routine is heavily dependent on C storage allocator hacks
  1355.    * For Amiga, we can't rely on storage being left alone "up to"
  1356.    * the boundary of allocation as in VMS or RSX. Therefore we have
  1357.    * to be different here and allocate a new larger segment, then
  1358.    * free the old one. Messy but hopefully it will work.
  1359.    */
  1360.   extern char  *malloc();
  1361.  
  1362.   /* No realloc().  Do a malloc and copy it.  */
  1363.   if ((new_pointer = malloc((unsigned) new_amount)) == NULL){
  1364.       noroom(why);
  1365.   }
  1366. /* This MUST assume the program calls compact using the old pointer as the
  1367.   last call of malloc... Reason is that RSX version is really simpleminded */
  1368.    cpysiz=savsiz;
  1369. /* Complain if deallocate area not same as last allocate area */
  1370.  if (savptr != pointer) bogus(why);
  1371.    wrk2=new_pointer;
  1372.    for (wrk=pointer;cpysiz > 0;cpysiz--){
  1373. /* copy data to new area */
  1374.      *wrk2++ = *wrk++;
  1375.      }
  1376. /* when done, free old memory area. */
  1377.    free(pointer);
  1378. #endif
  1379.  
  1380. #ifndef OSK
  1381. #ifdef  DEBUG
  1382.   if (new_pointer != pointer) {
  1383.       fprintf(stderr, "moved from %06o to %06o\n",
  1384.         pointer, new_pointer);
  1385.   }
  1386. /*  rdump(new_pointer, why);
  1387. */
  1388. #endif
  1389. #endif
  1390.   return (new_pointer);
  1391. }
  1392.  
  1393. noroom(why)
  1394. char      *why;
  1395. {
  1396.   fprintf(stderr, "?DIFF-F-out of room when %s\n", why);
  1397.   exit(IO_ERROR);
  1398. }
  1399.  
  1400. #ifdef    AMIGA
  1401. bogus(why)
  1402. char      *why;
  1403. {
  1404.   fprintf(stderr, "?DIFF-F-invalid compaction when %s\n", why);
  1405.   exit(IO_ERROR);
  1406. }
  1407. #endif
  1408.  
  1409. #ifdef  DEBUG
  1410. rdump(pointer, why)
  1411. int      *pointer;
  1412. char      *why;
  1413. /*
  1414.  * Dump memory block
  1415.  */
  1416. {
  1417.   int  *last;
  1418.   int  count;
  1419.  
  1420.   last = ((int **)pointer)[-1];
  1421.   fprintf(stderr, "dump %s of %06o -> %06o, %d words",
  1422.         why, pointer, last, last - pointer);
  1423.   last = (int *)(((int) last) & ~1);
  1424.   for (count = 0; pointer < last; ++count) {
  1425.       if ((count & 07) == 0) {
  1426.         fprintf(stderr, "\n%06o", pointer);
  1427.       }
  1428.       fprintf(stderr, "\t%06o", *pointer);
  1429.       pointer++;
  1430.   }
  1431.   fprintf(stderr, "\n");
  1432. }
  1433. #endif
  1434. cant(filename, what, fatalflag)
  1435. char      *filename;
  1436. char      *what;
  1437. int      fatalflag;
  1438. /*
  1439.  * Can't open file message
  1440.  */
  1441. {
  1442.   fprintf(stderr, "Can't open %s file \"%s\": ", what, filename);
  1443. #ifndef    OSK
  1444.   perror((char *)NULL);
  1445. #else
  1446.   prerr(0, errno);
  1447. #endif
  1448.   if (fatalflag) {
  1449.       exit(fatalflag);
  1450.   }
  1451. }
  1452. #ifdef  DEBUG
  1453. dump(d_linep, d_len, d_which)
  1454. LINE  *d_linep;
  1455. {
  1456.   register int i;
  1457.   
  1458.   printf("Dump of file%c, %d elements\n", "AB"[d_which], d_len);
  1459.   printf("linep @ %06o\n", d_linep);
  1460.   for (i = 0; i <= d_len; i++) {
  1461.       printf("%3d  %6d  %06o\n", i,
  1462.             d_linep[i].serial, d_linep[i].hash);
  1463.   }
  1464. }
  1465.  
  1466. dumpklist(kmax, why)
  1467. int  kmax;
  1468. char  *why;
  1469. /*
  1470.  * Dump klist
  1471.  */
  1472. {
  1473.   register int      i;
  1474.   register CANDIDATE  *cp;
  1475.   register int      count;
  1476.  
  1477.   printf("\nklist[0..%d] %s, clength = %d\n", kmax, why, clength);
  1478.   for (i = 0; i <= kmax; i++) {
  1479.       cp = &clist[klist[i]];
  1480.       printf("%2d %2d", i, klist[i]);
  1481.       if (cp >= &clist[0] && cp < &clist[clength])
  1482.         printf(" (%2d %2d -> %2d)\n", cp->a, cp->b, cp->link);
  1483.       else if (klist[i] == -1)
  1484.         printf(" End of chain\n");
  1485.       else  printf(" illegal klist element\n");
  1486.   }
  1487.   for (i = 0; i <= kmax; i++) {
  1488.       count = -1;
  1489.       for (cp = (CANDIDATE *)klist[i]; cp > &clist[0];
  1490.         cp = (CANDIDATE *)&cp->link) {
  1491.         if (++count >= 6) {
  1492.             printf("\n    ");
  1493.             count = 0;
  1494.         }
  1495.         printf(" (%2d: %2d,%2d -> %d)",
  1496.             cp-clist, cp->a, cp->b, cp->link);
  1497.       }
  1498.       printf("\n");
  1499.   }
  1500.   printf("*\n");
  1501. }
  1502. #endif
  1503. #ifdef  TIMING
  1504. ptime(why)
  1505. char      *why;
  1506. /*
  1507.  * Dump time buffer
  1508.  */
  1509. {
  1510.   long  ttemp;
  1511.  
  1512.   ttemp = time(NULL);
  1513.   printf("%ld seconds for %s\n",
  1514.       ttemp - sectiontime, why);
  1515.   sectiontime = ttemp;
  1516. }
  1517. #endif
  1518.  
  1519. /*
  1520.  *        s t r e q . c
  1521.  */
  1522.  
  1523. /*)LIBRARY
  1524. */
  1525.  
  1526.  
  1527. /* #define  EOS  0
  1528. #define  FALSE  0
  1529. #define  TRUE  1
  1530. */
  1531. int
  1532. streq(s1, s2)
  1533. register char  *s1;
  1534. register char  *s2;
  1535. /*
  1536.  * TRUE if strings are identical
  1537.  */
  1538. {
  1539.   while (*s1++ == *s2) {
  1540.       if (*s2++ == EOS)
  1541.       return (TRUE);
  1542.   }
  1543.   return (FALSE);
  1544. }
  1545. /*
  1546.  *        e r r o r . c
  1547.  */
  1548.  
  1549. /*)LIBRARY
  1550. */
  1551.  
  1552.  
  1553. /* VARARGS */
  1554. error(format, args)
  1555. char      *format;
  1556. /*
  1557.  * Error message before retiring.
  1558.  */
  1559. {
  1560.   fprintf(stderr, format, &args);
  1561.   putc('\n', stderr);
  1562.   _error();
  1563. }
  1564.  
  1565. _error()
  1566. {
  1567.   exit(1);
  1568. }
  1569.  
  1570. /* #include  <stdio.h> */
  1571.   
  1572. fputss(s, iop)
  1573. register char *s;
  1574. register FILE *iop;
  1575. /*
  1576.  * Like fput() except that it puts a newline at the end of the line.
  1577.  */
  1578. {
  1579. #ifndef OSK
  1580. /*
  1581.  * Why wasn't this written like the OSK section?  What's the difference between
  1582.  * fputc and putc other than I've never heard of fputc?
  1583.  */
  1584.   register c;
  1585.  
  1586.   while (c = *s++)
  1587.     fputc(c, iop);
  1588.   fputc('\n', iop);
  1589. #else
  1590.   fputs(s, iop);
  1591.   putc('\n', iop);
  1592. #endif
  1593. }
  1594.  
  1595.  
  1596. /*
  1597.  * Fgetss() is like fgets() except that the terminating newline
  1598.  * is removed.
  1599.  */
  1600. char *fgetss(s, n, iop)
  1601. char *s;
  1602. register FILE *iop;
  1603. {
  1604.   register c;
  1605.   register char *cs;
  1606.  
  1607.   cs = s;
  1608.   /*
  1609.    * The getc in the next line used to be an "fgetc".  Change it back if
  1610.    * getc doesn't work on your system, though that would be odd.
  1611.    */
  1612.   while ((c = getc(iop))>=0 && --n>0) {
  1613.       if (c=='\n')
  1614.         break;
  1615.       *cs++ = c;
  1616.   }
  1617.   if (c<0 && cs==s)
  1618.       return((char *)NULL);
  1619.   *cs = '\0';        /* Overwrite newline as null  */
  1620.   return(s);
  1621. }
  1622. xzyyz
  1623. echo done
  1624. ---
  1625.                 Mike Slomin
  1626.                 bellcore!lcuxa!mike2
  1627.  
  1628.  
  1629.