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