raw
vtools_genesis          1 
vtools_genesis          2 #include "diff.h"
vtools_genesis          3 #include <cmpbuf.h>
vtools_genesis          4 #include <xalloc.h>
vtools_genesis          5 #include <string.h>
vtools_genesis          6 #include <limits.h>
vtools_genesis          7 #include <stdlib.h>
vtools_genesis          8 
vtools_genesis          9 /* Rotate an unsigned value to the left.  */
vtools_genesis         10 #define ROL(v, n) ((v) << (n) | (v) >> (sizeof (v) * CHAR_BIT - (n)))
vtools_genesis         11 
vtools_genesis         12 /* Given a hash value and a new character, return a new hash
vtools_genesis         13    value.  */
vtools_genesis         14 #define HASH(h, c) ((c) + ROL (h, 7))
vtools_genesis         15 
vtools_genesis         16 /* The type of a hash value.  */
vtools_genesis         17 typedef size_t hash_value;
vtools_genesis         18 
vtools_genesis         19 /* Lines are put into equivalence classes of lines that match in
vtools_genesis         20    |lines_differ|.  Each equivalence class is represented by one of
vtools_genesis         21    these structures, but only while the classes are being computed.
vtools_genesis         22    Afterward, each class is represented by a number.  */
vtools_genesis         23 struct equivclass {
vtools_genesis         24     lin next;        /* Next item in this bucket.  */
vtools_genesis         25     hash_value hash;    /* Hash of lines in this class.  */
vtools_genesis         26     char const *line;    /* A line that fits this class.  */
vtools_genesis         27     size_t length;    /* That line's length, not counting its newline.  */
vtools_genesis         28 };
vtools_genesis         29 
vtools_genesis         30 /* Hash-table: array of buckets, each being a chain of equivalence
vtools_genesis         31    classes.  |buckets[-1]| is reserved for incomplete lines.  */
vtools_genesis         32 static lin *buckets;
vtools_genesis         33 
vtools_genesis         34 /* Number of buckets in the hash table array, not counting
vtools_genesis         35    |buckets[-1]|.  */
vtools_genesis         36 static size_t nbuckets;
vtools_genesis         37 
vtools_genesis         38 /* Array in which the equivalence classes are allocated.  The
vtools_genesis         39    bucket-chains go through the elements in this array.  The number of
vtools_genesis         40    an equivalence class is its index in this array.  */
vtools_genesis         41 static struct equivclass *equivs;
vtools_genesis         42 
vtools_genesis         43 /* Index of first free element in the array |equivs|.  */
vtools_genesis         44 static lin equivs_index;
vtools_genesis         45 
vtools_genesis         46 /* Number of elements allocated in the array |equivs|.  */
vtools_genesis         47 static lin equivs_alloc;
vtools_genesis         48 
vtools_genesis         49 /* Read a block of data into a file buffer, checking for EOF and
vtools_genesis         50    error.  */
vtools_genesis         51 
vtools_genesis         52 void
vtools_genesis         53 file_block_read(struct file_data *current, size_t size) {
vtools_genesis         54     if (size && !current->eof) {
vtools_genesis         55         size_t s = block_read(current->desc,
vtools_genesis         56                               FILE_BUFFER (current) + current->buffered, size);
vtools_genesis         57         if (s == SIZE_MAX)
vtools_genesis         58             pfatal_with_name(current->name);
vtools_genesis         59 
vtools_genesis         60         current->buffered += s;
vtools_genesis         61         current->eof = s < size;
vtools_genesis         62     }
vtools_genesis         63 }
vtools_genesis         64 
vtools_genesis         65 /* Check for binary files and compare them for exact identity.  */
vtools_genesis         66 
vtools_genesis         67 /* Return 1 if |buf| contains a non text character.  |size| is the
vtools_genesis         68    number of characters in |buf|.  */
vtools_genesis         69 
vtools_genesis         70 #define binary_file_p(buf, size) (memchr (buf, 0, size) != 0)
vtools_genesis         71 
vtools_genesis         72 /* Get ready to read the current file.  Return nonzero if |skip_test|
vtools_genesis         73    is zero, and if it appears to be a binary file.  */
vtools_genesis         74 
vtools_genesis         75 static bool
vtools_genesis         76 sip(struct file_data *current, bool skip_test) {
vtools_genesis         77     /* If we have a nonexistent file at this stage, treat it as
vtools_genesis         78        empty.  */
vtools_genesis         79     if (current->desc < 0) {
vtools_genesis         80         /* Leave room for a sentinel.  */
vtools_genesis         81         current->bufsize = sizeof(word);
vtools_genesis         82         current->buffer = xmalloc(current->bufsize);
vtools_genesis         83     } else {
vtools_genesis         84         current->bufsize = buffer_lcm(sizeof(word),
vtools_genesis         85                                       STAT_BLOCKSIZE (current->stat),
vtools_genesis         86                                       PTRDIFF_MAX - 2 * sizeof(word));
vtools_genesis         87         current->buffer = xmalloc(current->bufsize);
vtools_genesis         88 
vtools_genesis         89         if (!skip_test) {
vtools_genesis         90             /* Check first part of file to see if it's a binary file.  */
vtools_genesis         91 
vtools_genesis         92             off_t buffered;
vtools_genesis         93             file_block_read(current, current->bufsize);
vtools_genesis         94             buffered = current->buffered;
vtools_genesis         95             return binary_file_p (current->buffer, buffered);
vtools_genesis         96         }
vtools_genesis         97     }
vtools_genesis         98 
vtools_genesis         99     current->buffered = 0;
vtools_genesis        100     current->eof = false;
vtools_genesis        101     return false;
vtools_genesis        102 }
vtools_genesis        103 
vtools_genesis        104 /* Slurp the rest of the current file completely into memory.  */
vtools_genesis        105 
vtools_genesis        106 static void
vtools_genesis        107 slurp(struct file_data *current) {
vtools_genesis        108     size_t cc;
vtools_genesis        109 
vtools_genesis        110     if (current->desc < 0) {
vtools_genesis        111         /* The file is nonexistent.  */
vtools_genesis        112         return;
vtools_genesis        113     }
vtools_genesis        114 
vtools_genesis        115     if (S_ISREG (current->stat.st_mode)) {
vtools_genesis        116         /* It's a regular file; slurp in the rest all at once.  */
vtools_genesis        117 
vtools_genesis        118         /* Get the size out of the stat block.  Allocate just enough
vtools_genesis        119        room for appended newline plus word sentinel, plus
vtools_genesis        120        word-alignment since we want the buffer word-aligned.  */
vtools_genesis        121         size_t file_size = current->stat.st_size;
vtools_genesis        122         cc = file_size + 2 * sizeof(word) - file_size % sizeof(word);
vtools_genesis        123         if (file_size != current->stat.st_size || cc < file_size
vtools_genesis        124             || PTRDIFF_MAX <= cc)
vtools_genesis        125             xalloc_die();
vtools_genesis        126 
vtools_genesis        127         if (current->bufsize < cc) {
vtools_genesis        128             current->bufsize = cc;
vtools_genesis        129             current->buffer = xrealloc(current->buffer, cc);
vtools_genesis        130         }
vtools_genesis        131 
vtools_genesis        132         /* Try to read at least 1 more byte than the size indicates,
vtools_genesis        133        to detect whether the file is growing.  This is a nicety for
vtools_genesis        134        users who run 'diff' on files while they are changing.  */
vtools_genesis        135 
vtools_genesis        136         if (current->buffered <= file_size) {
vtools_genesis        137             file_block_read(current, file_size + 1 - current->buffered);
vtools_genesis        138             if (current->buffered <= file_size)
vtools_genesis        139                 return;
vtools_genesis        140         }
vtools_genesis        141     }
vtools_genesis        142 
vtools_genesis        143     /* It's not a regular file, or it's a growing regular file; read
vtools_genesis        144        it, growing the buffer as needed.  */
vtools_genesis        145 
vtools_genesis        146     file_block_read(current, current->bufsize - current->buffered);
vtools_genesis        147 
vtools_genesis        148     if (current->buffered) {
vtools_genesis        149         while (current->buffered == current->bufsize) {
vtools_genesis        150             if (PTRDIFF_MAX / 2 - sizeof(word) < current->bufsize)
vtools_genesis        151                 xalloc_die();
vtools_genesis        152             current->bufsize *= 2;
vtools_genesis        153             current->buffer = xrealloc(current->buffer, current->bufsize);
vtools_genesis        154             file_block_read(current, current->bufsize - current->buffered);
vtools_genesis        155         }
vtools_genesis        156 
vtools_genesis        157         /* Allocate just enough room for appended newline plus word
vtools_genesis        158        sentinel, plus word-alignment.  */
vtools_genesis        159         cc = current->buffered + 2 * sizeof(word);
vtools_genesis        160         current->bufsize = cc - cc % sizeof(word);
vtools_genesis        161         current->buffer = xrealloc(current->buffer, current->bufsize);
vtools_genesis        162     }
vtools_genesis        163 }
vtools_genesis        164 
vtools_genesis        165 /* Split the file into lines, simultaneously computing the equivalence
vtools_genesis        166    class for each line.  */
vtools_genesis        167 
vtools_genesis        168 static void
vtools_genesis        169 find_and_hash_each_line(struct file_data *current) {
vtools_genesis        170     char const *p = current->prefix_end;
vtools_genesis        171     lin i, *bucket;
vtools_genesis        172     size_t length;
vtools_genesis        173 
vtools_genesis        174     /* Cache often-used quantities in local variables to help the compiler.  */
vtools_genesis        175     char const **linbuf = current->linbuf;
vtools_genesis        176     lin alloc_lines = current->alloc_lines;
vtools_genesis        177     lin line = 0;
vtools_genesis        178     lin linbuf_base = current->linbuf_base;
vtools_genesis        179     lin *cureqs = xmalloc(alloc_lines * sizeof *cureqs);
vtools_genesis        180     struct equivclass *eqs = equivs;
vtools_genesis        181     lin eqs_index = equivs_index;
vtools_genesis        182     lin eqs_alloc = equivs_alloc;
vtools_genesis        183     char const *suffix_begin = current->suffix_begin;
vtools_genesis        184     char const *bufend = FILE_BUFFER (current) + current->buffered;
vtools_genesis        185 
vtools_genesis        186 
vtools_genesis        187     while (p < suffix_begin) {
vtools_genesis        188         char const *ip = p;
vtools_genesis        189         hash_value h = 0;
vtools_genesis        190         unsigned char c;
vtools_genesis        191 
vtools_genesis        192         /* Hash this line until we find a newline.  */
vtools_genesis        193         while ((c = *p++) != '\n')
vtools_genesis        194             h = HASH (h, c);
vtools_genesis        195 
vtools_genesis        196         bucket = &buckets[h % nbuckets];
vtools_genesis        197         length = p - ip - 1;
vtools_genesis        198 
vdiff_fixes_newli...  199         if (p == bufend
vdiff_fixes_newli...  200             && current->missing_newline) {
vdiff_fixes_newli...  201             /* The last line is incomplete.  If the line cannot
vdiff_fixes_newli...  202                compare equal to any complete line, put it into
vdiff_fixes_newli...  203                buckets[-1] so that it can compare equal only to the
vdiff_fixes_newli...  204                other file's incomplete line (if one exists).  */
vdiff_fixes_newli...  205                 bucket = &buckets[-1];
vdiff_fixes_newli...  206         }
vdiff_fixes_newli...  207 
vtools_genesis        208         for (i = *bucket;; i = eqs[i].next)
vtools_genesis        209             if (!i) {
vtools_genesis        210                 /* Create a new equivalence class in this bucket.  */
vtools_genesis        211                 i = eqs_index++;
vtools_genesis        212                 if (i == eqs_alloc) {
vtools_genesis        213                     if (PTRDIFF_MAX / (2 * sizeof *eqs) <= eqs_alloc)
vtools_genesis        214                         xalloc_die();
vtools_genesis        215                     eqs_alloc *= 2;
vtools_genesis        216                     eqs = xrealloc(eqs, eqs_alloc * sizeof *eqs);
vtools_genesis        217                 }
vtools_genesis        218                 eqs[i].next = *bucket;
vtools_genesis        219                 eqs[i].hash = h;
vtools_genesis        220                 eqs[i].line = ip;
vtools_genesis        221                 eqs[i].length = length;
vtools_genesis        222                 *bucket = i;
vtools_genesis        223                 break;
vtools_genesis        224             } else if (eqs[i].hash == h) {
vtools_genesis        225                 char const *eqline = eqs[i].line;
vtools_genesis        226 
vtools_genesis        227                 /* Reuse existing class if |lines_differ| reports the
vtools_genesis        228                    lines equal.  */
vtools_genesis        229                 if (eqs[i].length == length) {
vtools_genesis        230                     /* Reuse existing equivalence class if the lines
vtools_genesis        231                        are identical.  This detects the common case of
vtools_genesis        232                        exact identity faster than |lines_differ|
vtools_genesis        233                        would.  */
vtools_genesis        234                     if (memcmp(eqline, ip, length) == 0)
vtools_genesis        235                         break;
vtools_genesis        236                     continue;
vtools_genesis        237                 } else
vtools_genesis        238                     continue;
vtools_genesis        239             }
vtools_genesis        240 
vtools_genesis        241         /* Maybe increase the size of the line table.  */
vtools_genesis        242         if (line == alloc_lines) {
vtools_genesis        243             /* Double |(alloc_lines - linbuf_base)| by adding to
vtools_genesis        244                |alloc_lines|.  */
vtools_genesis        245             if (PTRDIFF_MAX / 3 <= alloc_lines
vtools_genesis        246                 || PTRDIFF_MAX / sizeof *cureqs <= 2 * alloc_lines - linbuf_base
vtools_genesis        247                 || PTRDIFF_MAX / sizeof *linbuf <= alloc_lines - linbuf_base)
vtools_genesis        248                 xalloc_die();
vtools_genesis        249             alloc_lines = 2 * alloc_lines - linbuf_base;
vtools_genesis        250             cureqs = xrealloc(cureqs, alloc_lines * sizeof *cureqs);
vtools_genesis        251             linbuf += linbuf_base;
vtools_genesis        252             linbuf = xrealloc(linbuf,
vtools_genesis        253                               (alloc_lines - linbuf_base) * sizeof *linbuf);
vtools_genesis        254             linbuf -= linbuf_base;
vtools_genesis        255         }
vtools_genesis        256         linbuf[line] = ip;
vtools_genesis        257         cureqs[line] = i;
vtools_genesis        258         ++line;
vtools_genesis        259     }
vtools_genesis        260 
vtools_genesis        261     current->buffered_lines = line;
vtools_genesis        262 
vtools_genesis        263     for (i = 0;; i++) {
vtools_genesis        264         /* Record the line start for lines in the suffix that we care
vtools_genesis        265        about.  Record one more line start than lines, so that we can
vtools_genesis        266        compute the length of any buffered line.  */
vtools_genesis        267         if (line == alloc_lines) {
vtools_genesis        268             /* Double |(alloc_lines - linbuf_base)| by adding to
vtools_genesis        269                |alloc_lines|.  */
vtools_genesis        270             if (PTRDIFF_MAX / 3 <= alloc_lines
vtools_genesis        271                 || PTRDIFF_MAX / sizeof *cureqs <= 2 * alloc_lines - linbuf_base
vtools_genesis        272                 || PTRDIFF_MAX / sizeof *linbuf <= alloc_lines - linbuf_base)
vtools_genesis        273                 xalloc_die();
vtools_genesis        274             alloc_lines = 2 * alloc_lines - linbuf_base;
vtools_genesis        275             linbuf += linbuf_base;
vtools_genesis        276             linbuf = xrealloc(linbuf,
vtools_genesis        277                               (alloc_lines - linbuf_base) * sizeof *linbuf);
vtools_genesis        278             linbuf -= linbuf_base;
vtools_genesis        279         }
vtools_genesis        280         linbuf[line] = p;
vtools_genesis        281 
vtools_genesis        282         if (p == bufend) {
vdiff_fixes_newli...  283             /* If the last line is incomplete, don't count its
vdiff_fixes_newli...  284                appended newline.  */
vdiff_fixes_newli...  285             if (current->missing_newline)
vtools_genesis        286                 linbuf[line]--;
vtools_genesis        287             break;
vtools_genesis        288         }
vtools_genesis        289 
vtools_genesis        290         line++;
vtools_genesis        291 
vtools_genesis        292         while (*p++ != '\n')
vtools_genesis        293             continue;
vtools_genesis        294     }
vtools_genesis        295 
vtools_genesis        296     /* Done with cache in local variables.  */
vtools_genesis        297     current->linbuf = linbuf;
vtools_genesis        298     current->valid_lines = line;
vtools_genesis        299     current->alloc_lines = alloc_lines;
vtools_genesis        300     current->equivs = cureqs;
vtools_genesis        301     equivs = eqs;
vtools_genesis        302     equivs_alloc = eqs_alloc;
vtools_genesis        303     equivs_index = eqs_index;
vtools_genesis        304 }
vtools_genesis        305 
vtools_genesis        306 /* Prepare the text.  Make sure the text end is initialized.  Make
vtools_genesis        307    sure text ends in a newline, but remember that we had to add one.
vtools_genesis        308    Strip trailing CRs, if that was requested.  */
vtools_genesis        309 
vtools_genesis        310 static void
vtools_genesis        311 prepare_text(struct file_data *current) {
vtools_genesis        312     size_t buffered = current->buffered;
vtools_genesis        313     char *p = FILE_BUFFER (current);
vtools_genesis        314 
vtools_genesis        315     if (buffered == 0 || p[buffered - 1] == '\n')
vtools_genesis        316         current->missing_newline = false;
vtools_genesis        317     else {
vtools_genesis        318         p[buffered++] = '\n';
vtools_genesis        319         current->missing_newline = true;
vtools_genesis        320     }
vtools_genesis        321 
vtools_genesis        322     if (!p)
vtools_genesis        323         return;
vtools_genesis        324 
vtools_genesis        325     /* Don't use uninitialized storage when planting or using sentinels.  */
vtools_genesis        326     memset (p + buffered, 0, sizeof(word));
vtools_genesis        327 
vtools_genesis        328     current->buffered = buffered;
vtools_genesis        329 }
vtools_genesis        330 
vtools_genesis        331 /* We have found |n| lines in a buffer of size |s|; guess the
vtools_genesis        332    proportionate number of lines that will be found in a buffer of
vtools_genesis        333    size |t|.  However, do not guess a number of lines so large that
vtools_genesis        334    the resulting line table might cause overflow in size
vtools_genesis        335    calculations.  */
vtools_genesis        336 static lin
vtools_genesis        337 guess_lines(lin n, size_t s, size_t t) {
vtools_genesis        338     size_t guessed_bytes_per_line = n < 10 ? 32 : s / (n - 1);
vtools_genesis        339     lin guessed_lines = MAX (1, t / guessed_bytes_per_line);
vtools_genesis        340     return MIN (guessed_lines, PTRDIFF_MAX / (2 * sizeof(char *) + 1) - 5) + 5;
vtools_genesis        341 }
vtools_genesis        342 
vtools_genesis        343 /* Given a vector of two |file_data| objects, find the identical
vtools_genesis        344    prefixes and suffixes of each object.  */
vtools_genesis        345 
vtools_genesis        346 static void
vtools_genesis        347 find_identical_ends(struct file_data filevec[]) {
vtools_genesis        348     word *w0, *w1;
vtools_genesis        349     char *p0, *p1, *buffer0, *buffer1;
vtools_genesis        350     char const *end0, *beg0;
vtools_genesis        351     char const **linbuf0, **linbuf1;
vtools_genesis        352     lin i, lines;
vtools_genesis        353     size_t n0, n1;
vtools_genesis        354     lin alloc_lines0, alloc_lines1;
vtools_genesis        355     lin buffered_prefix, prefix_count, prefix_mask;
vtools_genesis        356     lin middle_guess, suffix_guess;
vtools_genesis        357 
vtools_genesis        358     slurp(&filevec[0]);
vtools_genesis        359     prepare_text(&filevec[0]);
vtools_genesis        360     if (filevec[0].desc != filevec[1].desc) {
vtools_genesis        361         slurp(&filevec[1]);
vtools_genesis        362         prepare_text(&filevec[1]);
vtools_genesis        363     } else {
vtools_genesis        364         filevec[1].buffer = filevec[0].buffer;
vtools_genesis        365         filevec[1].bufsize = filevec[0].bufsize;
vtools_genesis        366         filevec[1].buffered = filevec[0].buffered;
vtools_genesis        367         filevec[1].missing_newline = filevec[0].missing_newline;
vtools_genesis        368     }
vtools_genesis        369 
vtools_genesis        370     /* Find identical prefix.  */
vtools_genesis        371 
vtools_genesis        372     w0 = filevec[0].buffer;
vtools_genesis        373     w1 = filevec[1].buffer;
vtools_genesis        374     p0 = buffer0 = (char *) w0;
vtools_genesis        375     p1 = buffer1 = (char *) w1;
vtools_genesis        376     n0 = filevec[0].buffered;
vtools_genesis        377     n1 = filevec[1].buffered;
vtools_genesis        378 
vtools_genesis        379     if (p0 == p1)
vtools_genesis        380         /* The buffers are the same; sentinels won't work.  */
vtools_genesis        381         p0 = p1 += n1;
vtools_genesis        382     else {
vtools_genesis        383         /* Insert end sentinels, in this case characters that are
vtools_genesis        384        guaranteed to make the equality test false, and thus terminate
vtools_genesis        385        the loop.  */
vtools_genesis        386 
vtools_genesis        387         if (n0 < n1)
vtools_genesis        388             p0[n0] = ~p1[n0];
vtools_genesis        389         else
vtools_genesis        390             p1[n1] = ~p0[n1];
vtools_genesis        391 
vtools_genesis        392         /* Loop until first mismatch, or to the sentinel
vtools_genesis        393            characters.  */
vtools_genesis        394 
vtools_genesis        395         /* Compare a word at a time for speed.  */
vtools_genesis        396         while (*w0 == *w1)
vtools_genesis        397             w0++, w1++;
vtools_genesis        398 
vtools_genesis        399         /* Do the last few bytes of comparison a byte at a time.  */
vtools_genesis        400         p0 = (char *) w0;
vtools_genesis        401         p1 = (char *) w1;
vtools_genesis        402         while (*p0 == *p1)
vtools_genesis        403             p0++, p1++;
vtools_genesis        404 
vtools_genesis        405         /* Don't mistakenly count missing newline as part of
vtools_genesis        406            prefix.  */
vdiff_fixes_newli...  407         if ((buffer0 + n0 - filevec[0].missing_newline < p0)
vdiff_fixes_newli...  408             !=
vdiff_fixes_newli...  409             (buffer1 + n1 - filevec[1].missing_newline < p1))
vtools_genesis        410             p0--, p1--;
vtools_genesis        411     }
vtools_genesis        412 
vtools_genesis        413     /* Now |p0| and |p1| point at the first nonmatching
vtools_genesis        414        characters.  */
vtools_genesis        415 
vtools_genesis        416     /* Skip back to last line-beginning in the prefix, and then
vtools_genesis        417        discard up to |horizon_lines| lines from the prefix.  */
vtools_genesis        418     i = horizon_lines;
vtools_genesis        419     while (p0 != buffer0 && (p0[-1] != '\n' || i--))
vtools_genesis        420         p0--, p1--;
vtools_genesis        421 
vtools_genesis        422     /* Record the prefix.  */
vtools_genesis        423     filevec[0].prefix_end = p0;
vtools_genesis        424     filevec[1].prefix_end = p1;
vtools_genesis        425 
vtools_genesis        426     /* Find identical suffix.  */
vtools_genesis        427 
vtools_genesis        428     /* |p0| and |p1| point beyond the last chars not yet compared.  */
vtools_genesis        429     p0 = buffer0 + n0;
vtools_genesis        430     p1 = buffer1 + n1;
vtools_genesis        431 
vtools_genesis        432     if (filevec[0].missing_newline == filevec[1].missing_newline) {
vtools_genesis        433         end0 = p0;    /* Addr of last char in file 0.  */
vtools_genesis        434 
vtools_genesis        435         /* Get value of |p0| at which we should stop scanning
vtools_genesis        436        backward: this is when either |p0| or |p1| points just past the
vtools_genesis        437        last char of the identical prefix.  */
vtools_genesis        438         beg0 = filevec[0].prefix_end + (n0 < n1 ? 0 : n0 - n1);
vtools_genesis        439 
vtools_genesis        440         /* Scan back until chars don't match or we reach that point.  */
vtools_genesis        441         while (p0 != beg0)
vtools_genesis        442             if (*--p0 != *--p1) {
vtools_genesis        443                 /* Point at the first char of the matching suffix.  */
vtools_genesis        444                 ++p0, ++p1;
vtools_genesis        445                 beg0 = p0;
vtools_genesis        446                 break;
vtools_genesis        447             }
vtools_genesis        448 
vtools_genesis        449         /* Are we at a line-beginning in both files?  If not, add the
vtools_genesis        450        rest of this line to the main body.  Discard up to
vtools_genesis        451        |horizon_lines| lines from the identical suffix.  Also, discard
vtools_genesis        452        one extra line, because |shift_boundaries| may need it.  */
vtools_genesis        453         i = horizon_lines + !((buffer0 == p0 || p0[-1] == '\n')
vtools_genesis        454                               &&
vtools_genesis        455                               (buffer1 == p1 || p1[-1] == '\n'));
vtools_genesis        456         while (i-- && p0 != end0)
vtools_genesis        457             while (*p0++ != '\n')
vtools_genesis        458                 continue;
vtools_genesis        459 
vtools_genesis        460         p1 += p0 - beg0;
vtools_genesis        461     }
vtools_genesis        462 
vtools_genesis        463     /* Record the suffix.  */
vtools_genesis        464     filevec[0].suffix_begin = p0;
vtools_genesis        465     filevec[1].suffix_begin = p1;
vtools_genesis        466 
vtools_genesis        467     /* Calculate number of lines of prefix to save.
vtools_genesis        468 
vtools_genesis        469        |prefix_count == 0| means save the whole prefix; we need this
vtools_genesis        470        for options like |-D| that output the whole file, or for
vtools_genesis        471        enormous contexts (to avoid worrying about arithmetic
vtools_genesis        472        overflow).  We also need it for options like |-F| that output
vtools_genesis        473        some preceding line; at least we will need to find the last few
vtools_genesis        474        lines, but since we don't know how many, it's easiest to find
vtools_genesis        475        them all.
vtools_genesis        476 
vtools_genesis        477        Otherwise, |prefix_count != 0|.  Save just |prefix_count| lines
vtools_genesis        478        at start of the line buffer; they'll be moved to the proper
vtools_genesis        479        location later.  Handle 1 more line than the context says
vtools_genesis        480        (because we count 1 too many), rounded up to the next power of
vtools_genesis        481        2 to speed index computation.  */
vtools_genesis        482 
vtools_genesis        483     prefix_count = 0;
vtools_genesis        484     alloc_lines0 = guess_lines(0, 0, n0);
vtools_genesis        485     prefix_mask = prefix_count - 1;
vtools_genesis        486     lines = 0;
vtools_genesis        487     linbuf0 = xmalloc(alloc_lines0 * sizeof *linbuf0);
vtools_genesis        488     p0 = buffer0;
vtools_genesis        489 
vtools_genesis        490     /* If the prefix is needed, find the prefix lines.  */
vtools_genesis        491     end0 = filevec[0].prefix_end;
vtools_genesis        492     while (p0 != end0) {
vtools_genesis        493         lin l = lines++ & prefix_mask;
vtools_genesis        494         if (l == alloc_lines0) {
vtools_genesis        495             if (PTRDIFF_MAX / (2 * sizeof *linbuf0) <= alloc_lines0)
vtools_genesis        496                 xalloc_die();
vtools_genesis        497             alloc_lines0 *= 2;
vtools_genesis        498             linbuf0 = xrealloc(linbuf0, alloc_lines0 * sizeof *linbuf0);
vtools_genesis        499         }
vtools_genesis        500         linbuf0[l] = p0;
vtools_genesis        501         while (*p0++ != '\n')
vtools_genesis        502             continue;
vtools_genesis        503     }
vtools_genesis        504     buffered_prefix = prefix_count && context < lines ? context : lines;
vtools_genesis        505 
vtools_genesis        506     /* Allocate line buffer 1.  */
vtools_genesis        507 
vtools_genesis        508     middle_guess = guess_lines(lines, p0 - buffer0, p1 - filevec[1].prefix_end);
vtools_genesis        509     suffix_guess = guess_lines(lines, p0 - buffer0, buffer1 + n1 - p1);
vtools_genesis        510     alloc_lines1 = buffered_prefix + middle_guess + MIN (context, suffix_guess);
vtools_genesis        511     if (alloc_lines1 < buffered_prefix
vtools_genesis        512         || PTRDIFF_MAX / sizeof *linbuf1 <= alloc_lines1)
vtools_genesis        513         xalloc_die();
vtools_genesis        514     linbuf1 = xmalloc(alloc_lines1 * sizeof *linbuf1);
vtools_genesis        515 
vtools_genesis        516     if (buffered_prefix != lines) {
vtools_genesis        517         /* Rotate prefix lines to proper location.  */
vtools_genesis        518         for (i = 0; i < buffered_prefix; i++)
vtools_genesis        519             linbuf1[i] = linbuf0[(lines - context + i) & prefix_mask];
vtools_genesis        520         for (i = 0; i < buffered_prefix; i++)
vtools_genesis        521             linbuf0[i] = linbuf1[i];
vtools_genesis        522     }
vtools_genesis        523 
vtools_genesis        524     /* Initialize line buffer 1 from line buffer 0.  */
vtools_genesis        525     for (i = 0; i < buffered_prefix; i++)
vtools_genesis        526         linbuf1[i] = linbuf0[i] - buffer0 + buffer1;
vtools_genesis        527 
vtools_genesis        528     /* Record the line buffer, adjusted so that
vtools_genesis        529        |linbuf[0]| points at the first differing line.  */
vtools_genesis        530     filevec[0].linbuf = linbuf0 + buffered_prefix;
vtools_genesis        531     filevec[1].linbuf = linbuf1 + buffered_prefix;
vtools_genesis        532     filevec[0].linbuf_base = filevec[1].linbuf_base = -buffered_prefix;
vtools_genesis        533     filevec[0].alloc_lines = alloc_lines0 - buffered_prefix;
vtools_genesis        534     filevec[1].alloc_lines = alloc_lines1 - buffered_prefix;
vtools_genesis        535     filevec[0].prefix_lines = filevec[1].prefix_lines = lines;
vtools_genesis        536 }
vtools_genesis        537 
vtools_genesis        538 /* If $1 < k$, then $(2^k - {\rm prime\_offset}_k)$ is the largest
vtools_genesis        539    prime less than $2^k$.  This table is derived from
vtools_genesis        540    Chris~K.~Caldwell's list
vtools_genesis        541    \url{http://www.utm.edu/research/primes/lists/2small/}.  */
vtools_genesis        542 
vtools_genesis        543 static unsigned char const prime_offset[] =
vtools_genesis        544         {
vtools_genesis        545                 0, 0, 1, 1, 3, 1, 3, 1, 5, 3, 3, 9, 3, 1, 3, 19, 15, 1, 5, 1, 3, 9, 3,
vtools_genesis        546                 15, 3, 39, 5, 39, 57, 3, 35, 1, 5, 9, 41, 31, 5, 25, 45, 7, 87, 21,
vtools_genesis        547                 11, 57, 17, 55, 21, 115, 59, 81, 27, 129, 47, 111, 33, 55, 5, 13, 27,
vtools_genesis        548                 55, 93, 1, 57, 25
vtools_genesis        549         };
vtools_genesis        550 
vtools_genesis        551 /* Given a vector of two |file_data| objects, read the file associated
vtools_genesis        552    with each one, and build the table of equivalence classes.  Return
vtools_genesis        553    nonzero if either file appears to be a binary file.  If
vtools_genesis        554    |pretend_binary| is nonzero, pretend they are binary
vtools_genesis        555    regardless.  */
vtools_genesis        556 
vtools_genesis        557 bool
vtools_genesis        558 read_files(struct file_data filevec[], bool pretend_binary) {
vtools_genesis        559     int i;
vtools_genesis        560     bool skip_test = text | pretend_binary;
vtools_genesis        561     bool appears_binary = pretend_binary | sip(&filevec[0], skip_test);
vtools_genesis        562 
vtools_genesis        563     if (filevec[0].desc != filevec[1].desc)
vtools_genesis        564         appears_binary |= sip(&filevec[1], skip_test | appears_binary);
vtools_genesis        565     else {
vtools_genesis        566         filevec[1].buffer = filevec[0].buffer;
vtools_genesis        567         filevec[1].bufsize = filevec[0].bufsize;
vtools_genesis        568         filevec[1].buffered = filevec[0].buffered;
vtools_genesis        569     }
vtools_genesis        570     if (appears_binary) {
vtools_genesis        571         return true;
vtools_genesis        572     }
vtools_genesis        573 
vtools_genesis        574     find_identical_ends(filevec);
vtools_genesis        575 
vtools_genesis        576     equivs_alloc = filevec[0].alloc_lines + filevec[1].alloc_lines + 1;
vtools_genesis        577     if (PTRDIFF_MAX / sizeof *equivs <= equivs_alloc)
vtools_genesis        578         xalloc_die();
vtools_genesis        579     equivs = xmalloc(equivs_alloc * sizeof *equivs);
vtools_genesis        580     /* Equivalence class 0 is permanently safe for lines that were not
vtools_genesis        581        hashed.  Real equivalence classes start at 1.  */
vtools_genesis        582     equivs_index = 1;
vtools_genesis        583 
vtools_genesis        584     /* Allocate (one plus) a prime number of hash buckets.  Use a
vtools_genesis        585        prime number between $1/3$ and $2/3$ of the value of
vtools_genesis        586        |equiv_allocs|, approximately.  */
vtools_genesis        587     for (i = 9; (size_t) 1 << i < equivs_alloc / 3; i++)
vtools_genesis        588         continue;
vtools_genesis        589     nbuckets = ((size_t) 1 << i) - prime_offset[i];
vtools_genesis        590     if (PTRDIFF_MAX / sizeof *buckets <= nbuckets)
vtools_genesis        591         xalloc_die();
vtools_genesis        592     buckets = zalloc((nbuckets + 1) * sizeof *buckets);
vtools_genesis        593     buckets++;
vtools_genesis        594 
vtools_genesis        595     for (i = 0; i < 2; i++)
vtools_genesis        596         find_and_hash_each_line(&filevec[i]);
vtools_genesis        597 
vtools_genesis        598     filevec[0].equiv_max = filevec[1].equiv_max = equivs_index;
vtools_genesis        599 
vtools_genesis        600     free(equivs);
vtools_genesis        601     free(buckets - 1);
vtools_genesis        602 
vtools_genesis        603     return false;
vtools_genesis        604 }