home *** CD-ROM | disk | FTP | other *** search
/ ftp.wwiv.com / ftp.wwiv.com.zip / ftp.wwiv.com / pub / MISC / MN321SRC.ZIP / mkdiff.c < prev    next >
C/C++ Source or Header  |  2004-07-21  |  18KB  |  582 lines
  1. /* $Id: mkdiff.c,v 1.10 2004/07/20 04:29:47 fido Exp $ */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6.  
  7. #include "makenl.h"
  8. #include "fileutil.h"
  9. #include "lsttool.h"
  10.  
  11. #ifdef MALLOC_DEBUG
  12. #include "rmalloc.h"
  13. #endif
  14.  
  15. #ifdef DMALLOC
  16. #include "dmalloc.h"
  17. #endif
  18.  
  19. #ifdef __FLAT__
  20. #define COLLTBLSIZE         ((65536 * 2) / 8)
  21. #define COLLTBLBYTEPOS(idx) (idx >> 2)
  22. #define COLLTBLBITPOS(idx)  ((idx & 3) << 1)
  23. #define MAXHASHLISTENTRIES  16200
  24. #define MINHASHLISTENTRIES  40
  25. #else
  26. #define COLLTBLSIZE         ((int)((32768L * 2) / 8))
  27. #define COLLTBLBYTEPOS(idx) (idx >> 3)
  28. #define COLLTBLBITPOS(idx)  (idx & 6)
  29. #define MAXHASHLISTENTRIES  2050
  30. #define MINHASHLISTENTRIES  20
  31. #endif
  32.  
  33.  
  34. #define ISHASH(entry)      (entry.hash < 0)
  35. #define ISLINENO(entry)    (entry.hash >= 0)
  36. #define ISCONNECTED(entry) ISLINENO(entry)
  37.  
  38. union _hashentry
  39. {
  40.     unsigned short hashlow;
  41.     long hash;
  42.     int lineno;
  43. };
  44.  
  45.  
  46. struct DiffingInfo
  47. {
  48.     FILE *theFILE;
  49.     int lineno;                 /* # of last read line from file */
  50.     char *CollTbl;              /* hash collision table */
  51.     union _hashentry *HashList; /* hash list */
  52.     int hashentries;            /* current # entries in HashList */
  53. };
  54.  
  55. static int maxhashes;           /* maximum entries in hash tables */
  56.  
  57. int CopyrightLines;
  58.  
  59. static int StillData;
  60. static FILE *DiffFILE;
  61. static struct DiffingInfo OldFile, NowFile;
  62.  
  63. static int primebuffer(struct DiffingInfo *f, char *linebuf);
  64. static long hashstr(const char *linebuf);
  65. static int Get2Bit(char *bitptr, unsigned short bitno);
  66. static void Set2Bit(char *bitptr, unsigned short bitno, int val);
  67. static void WriteDiffPart(char *linebuf);
  68. static int lineread(char *linebuf, int currentline, struct DiffingInfo *f);
  69.  
  70. int makediff(char *filename)
  71. {
  72.     char *run1, *run2;
  73.     int foundConns;
  74.     int synced;
  75.     int i;
  76.     char newext[MYMAXEXT];
  77.     int cause;
  78.     char oldname[MYMAXDIR];
  79.     char diffname[MYMAXDIR];
  80.     char linebuf[linelength];
  81.  
  82.     swapext(oldname, filename, OldExtensions[1]);
  83.     if (filesize(filename) > DIFFThreshold  && DIFFThreshold != -1)
  84.     {
  85.         cause = CAUSE_THRESHOLD;
  86.         strcpy(newext, OldExtensions[0]);
  87.         newext[0] = 'd';        /* foo.206 --> foo.d06 */
  88.         myfnmerge(diffname, NULL, OutDir, OutFile, newext);
  89.     }
  90.     else
  91.     {
  92.         if (OutDiff[0] == 0)
  93.             return 0;
  94.         cause = CAUSE_OUTDIFF;
  95.         myfnmerge(diffname, NULL, OutDir, OutDiff, OldExtensions[0]);
  96.     }
  97.  
  98.     OldFile.theFILE = fopen(oldname, "r");
  99.     if (!OldFile.theFILE)
  100.     {
  101.         fprintf(stderr,
  102.                 "\nOld file \"%s\" does not exist, no difference file made\n",
  103.                 oldname);
  104.         return 0;
  105.     }
  106.  
  107.     NowFile.theFILE = fopen(filename, "r");
  108.     if (!NowFile.theFILE)
  109.         die(254, 1, "Unable to open new node list -- \"%s\"\n", filename);
  110.  
  111.     DiffFILE = fopen(diffname, "w");
  112.     if (!DiffFILE)
  113.         die(254, 1, "Unable to create difference file -- \"%s\"\n",
  114.             diffname);
  115.  
  116.     /* skip first line of new file */
  117.     if (!fgets(linebuf, linelength, NowFile.theFILE))
  118.     {
  119.         fclose(OldFile.theFILE);
  120.         fclose(NowFile.theFILE);
  121.         fclose(DiffFILE);
  122.         unlink(diffname);
  123.         return 0;
  124.     }
  125.  
  126.     /* get first line of old file */
  127.     if (!fgets(linebuf, linelength, OldFile.theFILE))
  128.     {
  129.         fclose(OldFile.theFILE);
  130.         fclose(NowFile.theFILE);
  131.         fclose(DiffFILE);
  132.         unlink(diffname);
  133.         return 0;
  134.     }
  135.     fputs(linebuf, DiffFILE);
  136.  
  137.     fprintf(stdout,
  138.             "\nCreating difference file \"%s\" from \"%s\" and \"%s\"\n",
  139.             diffname, oldname, filename);
  140.  
  141.     /* allocate buffer memory for diff-hashing */
  142.     OldFile.CollTbl = NULL;
  143.     maxhashes = MAXHASHLISTENTRIES;
  144.  
  145.     while (maxhashes >= MINHASHLISTENTRIES)
  146.     {
  147.         OldFile.CollTbl =
  148.             malloc(2 * COLLTBLSIZE + 2 * maxhashes * sizeof(long));
  149.  
  150.         if (OldFile.CollTbl)
  151.             break;
  152.         else                    /* no memory: */
  153.             maxhashes -= 100;   /* shorten hash table by 100 entries */
  154.     }
  155.     if (!OldFile.CollTbl)
  156.     {
  157.         fprintf(stderr,
  158.                 "Unable to allocate memory -- no difference file generated\n");
  159.         fclose(OldFile.theFILE);
  160.         fclose(NowFile.theFILE);
  161.         fclose(DiffFILE);
  162.         unlink(diffname);
  163.         return 0;
  164.     }
  165.  
  166.     /* order of buffers in allocated memory: */
  167.     /* OldFile.CollTbl, NowFile.CollTbl, OldFile.HashList,
  168.        NowFile.HashList */
  169.     NowFile.CollTbl = OldFile.CollTbl + COLLTBLSIZE;
  170.     OldFile.HashList =
  171.         (union _hashentry *)((char *)NowFile.CollTbl + COLLTBLSIZE);
  172.     NowFile.HashList = OldFile.HashList + maxhashes;
  173.  
  174.  
  175.     /* begin diff process */
  176.     fseek(OldFile.theFILE, 0L, SEEK_SET);
  177.     fseek(NowFile.theFILE, 0L, SEEK_SET);
  178.     do
  179.     {
  180.         int idxold;
  181.         int idxnow;
  182.  
  183.         StillData = 0;
  184.         primebuffer(&NowFile, linebuf);
  185.         primebuffer(&OldFile, linebuf);
  186.         run1 = OldFile.CollTbl;
  187.         run2 = NowFile.CollTbl;
  188.         for (i = 0; i < COLLTBLSIZE; i++)
  189.             *(run1++) &= *(run2++);
  190.  
  191.         /* Step 1: connect all lines with unique hash value */
  192.         idxnow = idxold = 0;
  193.         while (idxold < OldFile.hashentries) /* Walk old file line-by-line 
  194.                                               */
  195.         {
  196.             if (idxnow < NowFile.hashentries) /* try walking in new file
  197.                                                  also */
  198.                 idxnow++;
  199.  
  200.             if (Get2Bit(OldFile.CollTbl, OldFile.HashList[idxold].hashlow)
  201.                 == 1)
  202.             {
  203.                 int searchforw = idxnow;
  204.                 int searchback = idxnow;
  205.  
  206.                 /* If the hash value is unique in both files... */
  207.                 /* ...search the line in the new file */
  208.                 while (searchforw < NowFile.hashentries || searchback > 0)
  209.                 {
  210.                     if (searchforw < NowFile.hashentries &&
  211.                         NowFile.HashList[searchforw++].hash ==
  212.                         OldFile.HashList[idxold].hash)
  213.                     {
  214.                         idxnow = searchforw - 1;
  215.                         NowFile.HashList[idxnow].hash = 0;
  216.                         OldFile.HashList[idxold].hash = 0;
  217.                         NowFile.HashList[idxnow].lineno = idxold;
  218.                         OldFile.HashList[idxold].lineno = idxnow;
  219.                         break;
  220.                     }
  221.                     if (searchback > 0 &&
  222.                         NowFile.HashList[--searchback].hash ==
  223.                         OldFile.HashList[idxold].hash)
  224.                     {
  225.                         idxnow = searchback;
  226.                         NowFile.HashList[idxnow].hash = 0;
  227.                         OldFile.HashList[idxold].hash = 0;
  228.                         NowFile.HashList[idxnow].lineno = idxold;
  229.                         OldFile.HashList[idxold].lineno = idxnow;
  230.                         break;
  231.                     }
  232.                 }
  233.             }
  234.             idxold++;
  235.         }
  236.  
  237.         /* Step 2: Walk through the lines of the old file. If you hit an
  238.            unconnected line after connected lines, test whether in both
  239.            files the lines have the same hash value (it need not to be
  240.            unique, we just guess that lines with a non-unique hash value
  241.            after connected lines are also equal. In a second iteration,
  242.            connect lines before already connected lines. */
  243.  
  244.         /* Step 2a: go forward */
  245.         synced = 1;
  246.         idxold = idxnow = -1;
  247.         while (++idxold < OldFile.hashentries) /* Again, walk old file
  248.                                                   step by step */
  249.         {
  250.             /* This line connected to a line in the new file? */
  251.             if (ISCONNECTED(OldFile.HashList[idxold]))
  252.             {
  253.                 synced = 1;     /* if yes, resynchronize... */
  254.                 idxnow = OldFile.HashList[idxold].lineno;
  255.             }
  256.             else if (synced)
  257.             {
  258.                 /* Do the hashes match? */
  259.                 if (++idxnow < NowFile.hashentries &&
  260.                     NowFile.HashList[idxnow].hash ==
  261.                     OldFile.HashList[idxold].hash)
  262.                 {
  263.                     /* Yes, connect the lines! */
  264.                     OldFile.HashList[idxold].hash = 0;
  265.                     NowFile.HashList[idxnow].hash = 0;
  266.                     OldFile.HashList[idxold].lineno = idxnow;
  267.                     NowFile.HashList[idxnow].lineno = idxold;
  268.                 }
  269.                 else
  270.                     /* No, fell out of sync */
  271.                     synced = 0;
  272.             }
  273.         }
  274.  
  275.         /* Step 2b: Now do the same thing again backwards, and test,
  276.            whether there are any connections - we need this information
  277.            later */
  278.  
  279.         synced = 1;
  280.         foundConns = 0;
  281.         idxold = OldFile.hashentries;
  282.         idxnow = NowFile.hashentries;
  283.         while (--idxold >= 0)
  284.         {
  285.             if (ISCONNECTED(OldFile.HashList[idxold]))
  286.             {
  287.                 foundConns = 1;
  288.                 synced = 1;
  289.                 idxnow = OldFile.HashList[idxold].lineno;
  290.             }
  291.             else if (synced)
  292.             {
  293.                 if (--idxnow >= 0 &&
  294.                     NowFile.HashList[idxnow].hash ==
  295.                     OldFile.HashList[idxold].hash)
  296.                 {
  297.                     OldFile.HashList[idxold].hash = 0;
  298.                     NowFile.HashList[idxnow].hash = 0;
  299.                     OldFile.HashList[idxold].lineno = idxnow;
  300.                     NowFile.HashList[idxnow].lineno = idxold;
  301.                 }
  302.                 else
  303.                     synced = 0;
  304.             }
  305.         }
  306.  
  307.         /* If you found connections, try in the next iteration with
  308.            datablocks directly after the last connection. */
  309.  
  310.         if (StillData && foundConns)
  311.         {
  312.             while (!ISCONNECTED(OldFile.HashList[--OldFile.hashentries]))
  313.                 ;
  314.             OldFile.hashentries++;
  315.             while (!ISCONNECTED(NowFile.HashList[--NowFile.hashentries]))
  316.                 ;
  317.             NowFile.hashentries++;
  318.         }
  319.  
  320.         WriteDiffPart(linebuf);
  321.     }
  322.     while (StillData);
  323.     free(OldFile.CollTbl);      /* The start of the memory area */
  324.     fclose(OldFile.theFILE);
  325.     fclose(NowFile.theFILE);
  326.     fclose(DiffFILE);
  327.     if (cause == CAUSE_THRESHOLD)
  328.     {
  329.         strcpy(filename, diffname);
  330.         if (OutDiff[0] != 0)
  331.         {
  332.             cause = CAUSE_THRESHOLD | CAUSE_OUTDIFF;
  333.             CopyOrMove(1, diffname, OutDir, OutDiff);
  334.         }
  335.     }
  336.     return cause;
  337. }
  338.  
  339.  
  340. int primebuffer(struct DiffingInfo *f, char *linebuf)
  341. {
  342.     unsigned short hashlow;
  343.     long pos;
  344.  
  345.     memset(f->CollTbl, 0, COLLTBLSIZE);
  346.     f->lineno = 0;
  347.     f->hashentries = 0;
  348.  
  349.     pos = ftell(f->theFILE);
  350.     while (lineread(linebuf, f->lineno, f))
  351.     {
  352.         if (f->hashentries >= maxhashes)
  353.         {
  354.             StillData = 1;
  355.             break;
  356.         }
  357.  
  358.         f->HashList[f->hashentries].hash = hashstr(linebuf);
  359.         hashlow = f->HashList[f->hashentries].hashlow;
  360.         f->hashentries++;
  361.         switch (Get2Bit(f->CollTbl, hashlow))
  362.         {
  363.         case 0:
  364.             Set2Bit(f->CollTbl, hashlow, 1);
  365.             break;
  366.         case 1:
  367.             Set2Bit(f->CollTbl, hashlow, 2);
  368.             break;
  369.         }
  370.     }
  371.     fseek(f->theFILE, pos, SEEK_SET);
  372.     f->lineno = 0;
  373.     return f->hashentries;
  374. }
  375.  
  376.  
  377. long hashstr(const char *linebuf)
  378. {
  379.     long hashval = 0;
  380.  
  381.     while (*linebuf)
  382.     {
  383.         hashval <<= 1;
  384.         if (hashval < 0)
  385.             hashval |= 1;
  386.         hashval ^= *linebuf;
  387.         linebuf++;
  388.     }
  389.     return hashval | 0x80000000UL;
  390. }
  391.  
  392.  
  393. /* Collision table handling                                                 */
  394. /* The collision table has 32768 2-bit entries. Index into the table is     */
  395. /* a 16-bit hash (in fact: only higher 15 bit of an unsigned short).        */
  396. /* On 32-bit systems the collision table is 65536 entries with full 16-bit  */
  397. /* index.                                                                   */
  398. /* entry: 0=hash not used, 1=hash uniquely used, 2=hash collision           */
  399.  
  400. /* Get2Bit/Set2Bit: */
  401. /* bitno:  the lower 16 bit of the hash value; index into the table         */
  402. /* bitptr: pointer to the collision table                                   */
  403.  
  404. int Get2Bit(char *bitptr, unsigned short bitno)
  405. {
  406.     return (bitptr[COLLTBLBYTEPOS(bitno)] >> COLLTBLBITPOS(bitno)) & 3;
  407. }
  408.  
  409.  
  410. void Set2Bit(char *bitptr, unsigned short bitno, int val)
  411. {
  412.     bitptr[COLLTBLBYTEPOS(bitno)] &= ~(3 << COLLTBLBITPOS(bitno));
  413.     bitptr[COLLTBLBYTEPOS(bitno)] |= val << COLLTBLBITPOS(bitno);
  414. }
  415.  
  416.  
  417. void WriteDiffPart(char *linebuf)
  418. {
  419.     int i;
  420.     int idxnow, idxold;
  421.     int aktline, linecount;
  422.     char mybuf[linelength];
  423.  
  424.     /* Make the Copyright appear in the diff */
  425.     /* if the copyright has more lines than the hashbuffer, then let only */
  426.     /* as much lines appear as fit in the hash buffer.  */
  427.     /* FIXED BUG from makenl 2.51: it crashes if the copyright has more */
  428.     /* lines than the hashbuffer.  */
  429.     if (CopyrightLines >= maxhashes)
  430.         CopyrightLines = maxhashes - 1;
  431.  
  432.     for (i = 1; i <= CopyrightLines; i++)
  433.     {
  434.         if (ISCONNECTED(NowFile.HashList[i]))
  435.             NowFile.HashList[i].hash = -1; /* remove connection */
  436.     }
  437.     CopyrightLines = 0;
  438.  
  439.     idxnow = idxold = 0;
  440.     while (idxold < OldFile.hashentries && idxnow < NowFile.hashentries)
  441.     {
  442.         /* count matching lines, and do a real line compare on them */
  443.         for (linecount = 0;
  444.              idxold < OldFile.hashentries &&
  445.              idxnow < NowFile.hashentries &&
  446.              OldFile.HashList[idxold].lineno == idxnow;
  447.              idxnow++, linecount++, idxold++)
  448.         {
  449.             lineread(mybuf, idxold, &OldFile);
  450.             lineread(linebuf, idxnow, &NowFile);
  451.             if (strcmp(mybuf, linebuf) != 0)
  452.             {
  453.                 /* Remove false connections - after comparing input lines, 
  454.                    you can be sure, whether the lines are equal */
  455.                 NowFile.HashList[idxnow].hash = -1;
  456.                 OldFile.HashList[idxold].hash = -1;
  457.                 break;
  458.             }
  459.         }
  460.         if (linecount)
  461.         {
  462.             /* There is at least one copyable line */
  463.             fprintf(DiffFILE, "C%d\n", linecount);
  464.             continue;
  465.         }
  466.  
  467.         /* Count unmatched lines in the old file, or lines matched against 
  468.            some lines in the new file already written */
  469.         linecount = 0;
  470.         while (idxold < OldFile.hashentries &&
  471.                (ISHASH(OldFile.HashList[idxold]) ||
  472.                 OldFile.HashList[idxold].lineno < idxnow))
  473.         {
  474.             linecount++;
  475.             idxold++;
  476.         }
  477.         if (linecount)
  478.         {
  479.             /* Throw them away! */
  480.             fprintf(DiffFILE, "D%d\n", linecount);
  481.             continue;
  482.         }
  483.  
  484.         /* Count lines in the new file that were not matched or matched
  485.            against lines already read and copied/deleted */
  486.  
  487.         linecount = 0;
  488.         while (idxnow < NowFile.hashentries &&
  489.                (ISHASH(NowFile.HashList[idxnow]) ||
  490.                 NowFile.HashList[idxnow].lineno < idxold))
  491.         {
  492.             linecount++;
  493.             idxnow++;
  494.         }
  495.         if (linecount)
  496.         {
  497.             /* There are such lines - put them into the diff */
  498.  
  499.             fprintf(DiffFILE, "A%d\n", linecount);
  500.             aktline = idxnow - linecount;
  501.             while (linecount--)
  502.             {
  503.                 lineread(linebuf, aktline++, &NowFile);
  504.                 fputs(linebuf, DiffFILE);
  505.             }
  506.         }
  507.         /* There seems to be a change in the order of the lines... Look
  508.            which number is larger a) the numbers of line in the input till 
  509.            the expected line comes OR b) the numbers of lines in the
  510.            output, till the next input line appears */
  511.  
  512.         else if (NowFile.HashList[idxnow].lineno - idxold >=
  513.                  OldFile.HashList[idxold].lineno - idxnow)
  514.         {
  515.             /* a) is larger - so emit the lines till the input line
  516.                appears in output */
  517.             linecount = OldFile.HashList[idxold].lineno - idxnow;
  518.             fprintf(DiffFILE, "A%d\n", linecount);
  519.             aktline = idxnow;
  520.             for (; linecount != 0; linecount--)
  521.             {
  522.                 lineread(linebuf, aktline++, &NowFile);
  523.                 fputs(linebuf, DiffFILE);
  524.             }
  525.             idxnow = OldFile.HashList[idxold].lineno;
  526.         }
  527.         else
  528.         {
  529.             /* b) is larger, so tell the reader to ignore input lines up
  530.                to the matching line */
  531.  
  532.             fprintf(DiffFILE, "D%d\n",
  533.                     NowFile.HashList[idxnow].lineno - idxold);
  534.             idxold = NowFile.HashList[idxnow].lineno;
  535.         }
  536.     }
  537.  
  538.     /* this was not the last data block... Put the filepointers into
  539.        correct position for next block */
  540.     if (StillData)
  541.     {
  542.         NowFile.hashentries = idxnow;
  543.         lineread(linebuf, OldFile.hashentries - 1, &OldFile);
  544.         lineread(linebuf, NowFile.hashentries - 1, &NowFile);
  545.         return;
  546.     }
  547.  
  548.     /* we have to clean up... if there are lines left in the old file -
  549.        DELETE them! */
  550.     if (idxold < OldFile.hashentries)
  551.         fprintf(DiffFILE, "D%d\n", OldFile.hashentries - idxold);
  552.  
  553.     /* if there are additional lines in the new file, they have to appear
  554.        in the diff! */
  555.     if (idxnow < NowFile.hashentries)
  556.     {
  557.         fprintf(DiffFILE, "A%d\n", NowFile.hashentries - idxnow);
  558.         aktline = idxnow;
  559.         for (; idxnow < NowFile.hashentries; idxnow++)
  560.         {
  561.             lineread(linebuf, aktline++, &NowFile);
  562.             fputs(linebuf, DiffFILE);
  563.         }
  564.     }
  565. }
  566.  
  567.  
  568. /* read line from source file until a new line is read. return this new line */
  569. int lineread(char *linebuf, int currentline, struct DiffingInfo *f)
  570. {
  571.     if (f->lineno > currentline)
  572.         return 1;
  573.     do
  574.     {
  575.         if (fgets(linebuf, linelength, f->theFILE) == NULL)
  576.             return 0;
  577.         f->lineno++;
  578.     }
  579.     while (f->lineno <= currentline);
  580.     return 1;
  581. }
  582.