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 
vtools_genesis        199         for (i = *bucket;; i = eqs[i].next)
vtools_genesis        200             if (!i) {
vtools_genesis        201                 /* Create a new equivalence class in this bucket.  */
vtools_genesis        202                 i = eqs_index++;
vtools_genesis        203                 if (i == eqs_alloc) {
vtools_genesis        204                     if (PTRDIFF_MAX / (2 * sizeof *eqs) <= eqs_alloc)
vtools_genesis        205                         xalloc_die();
vtools_genesis        206                     eqs_alloc *= 2;
vtools_genesis        207                     eqs = xrealloc(eqs, eqs_alloc * sizeof *eqs);
vtools_genesis        208                 }
vtools_genesis        209                 eqs[i].next = *bucket;
vtools_genesis        210                 eqs[i].hash = h;
vtools_genesis        211                 eqs[i].line = ip;
vtools_genesis        212                 eqs[i].length = length;
vtools_genesis        213                 *bucket = i;
vtools_genesis        214                 break;
vtools_genesis        215             } else if (eqs[i].hash == h) {
vtools_genesis        216                 char const *eqline = eqs[i].line;
vtools_genesis        217 
vtools_genesis        218                 /* Reuse existing class if |lines_differ| reports the
vtools_genesis        219                    lines equal.  */
vtools_genesis        220                 if (eqs[i].length == length) {
vtools_genesis        221                     /* Reuse existing equivalence class if the lines
vtools_genesis        222                        are identical.  This detects the common case of
vtools_genesis        223                        exact identity faster than |lines_differ|
vtools_genesis        224                        would.  */
vtools_genesis        225                     if (memcmp(eqline, ip, length) == 0)
vtools_genesis        226                         break;
vtools_genesis        227                     continue;
vtools_genesis        228                 } else
vtools_genesis        229                     continue;
vtools_genesis        230             }
vtools_genesis        231 
vtools_genesis        232         /* Maybe increase the size of the line table.  */
vtools_genesis        233         if (line == alloc_lines) {
vtools_genesis        234             /* Double |(alloc_lines - linbuf_base)| by adding to
vtools_genesis        235                |alloc_lines|.  */
vtools_genesis        236             if (PTRDIFF_MAX / 3 <= alloc_lines
vtools_genesis        237                 || PTRDIFF_MAX / sizeof *cureqs <= 2 * alloc_lines - linbuf_base
vtools_genesis        238                 || PTRDIFF_MAX / sizeof *linbuf <= alloc_lines - linbuf_base)
vtools_genesis        239                 xalloc_die();
vtools_genesis        240             alloc_lines = 2 * alloc_lines - linbuf_base;
vtools_genesis        241             cureqs = xrealloc(cureqs, alloc_lines * sizeof *cureqs);
vtools_genesis        242             linbuf += linbuf_base;
vtools_genesis        243             linbuf = xrealloc(linbuf,
vtools_genesis        244                               (alloc_lines - linbuf_base) * sizeof *linbuf);
vtools_genesis        245             linbuf -= linbuf_base;
vtools_genesis        246         }
vtools_genesis        247         linbuf[line] = ip;
vtools_genesis        248         cureqs[line] = i;
vtools_genesis        249         ++line;
vtools_genesis        250     }
vtools_genesis        251 
vtools_genesis        252     current->buffered_lines = line;
vtools_genesis        253 
vtools_genesis        254     for (i = 0;; i++) {
vtools_genesis        255         /* Record the line start for lines in the suffix that we care
vtools_genesis        256        about.  Record one more line start than lines, so that we can
vtools_genesis        257        compute the length of any buffered line.  */
vtools_genesis        258         if (line == alloc_lines) {
vtools_genesis        259             /* Double |(alloc_lines - linbuf_base)| by adding to
vtools_genesis        260                |alloc_lines|.  */
vtools_genesis        261             if (PTRDIFF_MAX / 3 <= alloc_lines
vtools_genesis        262                 || PTRDIFF_MAX / sizeof *cureqs <= 2 * alloc_lines - linbuf_base
vtools_genesis        263                 || PTRDIFF_MAX / sizeof *linbuf <= alloc_lines - linbuf_base)
vtools_genesis        264                 xalloc_die();
vtools_genesis        265             alloc_lines = 2 * alloc_lines - linbuf_base;
vtools_genesis        266             linbuf += linbuf_base;
vtools_genesis        267             linbuf = xrealloc(linbuf,
vtools_genesis        268                               (alloc_lines - linbuf_base) * sizeof *linbuf);
vtools_genesis        269             linbuf -= linbuf_base;
vtools_genesis        270         }
vtools_genesis        271         linbuf[line] = p;
vtools_genesis        272 
vtools_genesis        273         if (p == bufend) {
vtools_genesis        274             /* If the last line is incomplete and we do not silently
vtools_genesis        275                complete lines, don't count its appended newline.  */
vtools_genesis        276             if (current->missing_newline && false) /* our output style not robust */
vtools_genesis        277                 linbuf[line]--;
vtools_genesis        278             break;
vtools_genesis        279         }
vtools_genesis        280 
vtools_genesis        281         line++;
vtools_genesis        282 
vtools_genesis        283         while (*p++ != '\n')
vtools_genesis        284             continue;
vtools_genesis        285     }
vtools_genesis        286 
vtools_genesis        287     /* Done with cache in local variables.  */
vtools_genesis        288     current->linbuf = linbuf;
vtools_genesis        289     current->valid_lines = line;
vtools_genesis        290     current->alloc_lines = alloc_lines;
vtools_genesis        291     current->equivs = cureqs;
vtools_genesis        292     equivs = eqs;
vtools_genesis        293     equivs_alloc = eqs_alloc;
vtools_genesis        294     equivs_index = eqs_index;
vtools_genesis        295 }
vtools_genesis        296 
vtools_genesis        297 /* Prepare the text.  Make sure the text end is initialized.  Make
vtools_genesis        298    sure text ends in a newline, but remember that we had to add one.
vtools_genesis        299    Strip trailing CRs, if that was requested.  */
vtools_genesis        300 
vtools_genesis        301 static void
vtools_genesis        302 prepare_text(struct file_data *current) {
vtools_genesis        303     size_t buffered = current->buffered;
vtools_genesis        304     char *p = FILE_BUFFER (current);
vtools_genesis        305 
vtools_genesis        306     if (buffered == 0 || p[buffered - 1] == '\n')
vtools_genesis        307         current->missing_newline = false;
vtools_genesis        308     else {
vtools_genesis        309         p[buffered++] = '\n';
vtools_genesis        310         current->missing_newline = true;
vtools_genesis        311     }
vtools_genesis        312 
vtools_genesis        313     if (!p)
vtools_genesis        314         return;
vtools_genesis        315 
vtools_genesis        316     /* Don't use uninitialized storage when planting or using sentinels.  */
vtools_genesis        317     memset (p + buffered, 0, sizeof(word));
vtools_genesis        318 
vtools_genesis        319     current->buffered = buffered;
vtools_genesis        320 }
vtools_genesis        321 
vtools_genesis        322 /* We have found |n| lines in a buffer of size |s|; guess the
vtools_genesis        323    proportionate number of lines that will be found in a buffer of
vtools_genesis        324    size |t|.  However, do not guess a number of lines so large that
vtools_genesis        325    the resulting line table might cause overflow in size
vtools_genesis        326    calculations.  */
vtools_genesis        327 static lin
vtools_genesis        328 guess_lines(lin n, size_t s, size_t t) {
vtools_genesis        329     size_t guessed_bytes_per_line = n < 10 ? 32 : s / (n - 1);
vtools_genesis        330     lin guessed_lines = MAX (1, t / guessed_bytes_per_line);
vtools_genesis        331     return MIN (guessed_lines, PTRDIFF_MAX / (2 * sizeof(char *) + 1) - 5) + 5;
vtools_genesis        332 }
vtools_genesis        333 
vtools_genesis        334 /* Given a vector of two |file_data| objects, find the identical
vtools_genesis        335    prefixes and suffixes of each object.  */
vtools_genesis        336 
vtools_genesis        337 static void
vtools_genesis        338 find_identical_ends(struct file_data filevec[]) {
vtools_genesis        339     word *w0, *w1;
vtools_genesis        340     char *p0, *p1, *buffer0, *buffer1;
vtools_genesis        341     char const *end0, *beg0;
vtools_genesis        342     char const **linbuf0, **linbuf1;
vtools_genesis        343     lin i, lines;
vtools_genesis        344     size_t n0, n1;
vtools_genesis        345     lin alloc_lines0, alloc_lines1;
vtools_genesis        346     lin buffered_prefix, prefix_count, prefix_mask;
vtools_genesis        347     lin middle_guess, suffix_guess;
vtools_genesis        348 
vtools_genesis        349     slurp(&filevec[0]);
vtools_genesis        350     prepare_text(&filevec[0]);
vtools_genesis        351     if (filevec[0].desc != filevec[1].desc) {
vtools_genesis        352         slurp(&filevec[1]);
vtools_genesis        353         prepare_text(&filevec[1]);
vtools_genesis        354     } else {
vtools_genesis        355         filevec[1].buffer = filevec[0].buffer;
vtools_genesis        356         filevec[1].bufsize = filevec[0].bufsize;
vtools_genesis        357         filevec[1].buffered = filevec[0].buffered;
vtools_genesis        358         filevec[1].missing_newline = filevec[0].missing_newline;
vtools_genesis        359     }
vtools_genesis        360 
vtools_genesis        361     /* Find identical prefix.  */
vtools_genesis        362 
vtools_genesis        363     w0 = filevec[0].buffer;
vtools_genesis        364     w1 = filevec[1].buffer;
vtools_genesis        365     p0 = buffer0 = (char *) w0;
vtools_genesis        366     p1 = buffer1 = (char *) w1;
vtools_genesis        367     n0 = filevec[0].buffered;
vtools_genesis        368     n1 = filevec[1].buffered;
vtools_genesis        369 
vtools_genesis        370     if (p0 == p1)
vtools_genesis        371         /* The buffers are the same; sentinels won't work.  */
vtools_genesis        372         p0 = p1 += n1;
vtools_genesis        373     else {
vtools_genesis        374         /* Insert end sentinels, in this case characters that are
vtools_genesis        375        guaranteed to make the equality test false, and thus terminate
vtools_genesis        376        the loop.  */
vtools_genesis        377 
vtools_genesis        378         if (n0 < n1)
vtools_genesis        379             p0[n0] = ~p1[n0];
vtools_genesis        380         else
vtools_genesis        381             p1[n1] = ~p0[n1];
vtools_genesis        382 
vtools_genesis        383         /* Loop until first mismatch, or to the sentinel
vtools_genesis        384            characters.  */
vtools_genesis        385 
vtools_genesis        386         /* Compare a word at a time for speed.  */
vtools_genesis        387         while (*w0 == *w1)
vtools_genesis        388             w0++, w1++;
vtools_genesis        389 
vtools_genesis        390         /* Do the last few bytes of comparison a byte at a time.  */
vtools_genesis        391         p0 = (char *) w0;
vtools_genesis        392         p1 = (char *) w1;
vtools_genesis        393         while (*p0 == *p1)
vtools_genesis        394             p0++, p1++;
vtools_genesis        395 
vtools_genesis        396         /* Don't mistakenly count missing newline as part of
vtools_genesis        397            prefix.  */
vtools_genesis        398         if (false
vtools_genesis        399             && ((buffer0 + n0 - filevec[0].missing_newline < p0)
vtools_genesis        400                 !=
vtools_genesis        401                 (buffer1 + n1 - filevec[1].missing_newline < p1)))
vtools_genesis        402             p0--, p1--;
vtools_genesis        403     }
vtools_genesis        404 
vtools_genesis        405     /* Now |p0| and |p1| point at the first nonmatching
vtools_genesis        406        characters.  */
vtools_genesis        407 
vtools_genesis        408     /* Skip back to last line-beginning in the prefix, and then
vtools_genesis        409        discard up to |horizon_lines| lines from the prefix.  */
vtools_genesis        410     i = horizon_lines;
vtools_genesis        411     while (p0 != buffer0 && (p0[-1] != '\n' || i--))
vtools_genesis        412         p0--, p1--;
vtools_genesis        413 
vtools_genesis        414     /* Record the prefix.  */
vtools_genesis        415     filevec[0].prefix_end = p0;
vtools_genesis        416     filevec[1].prefix_end = p1;
vtools_genesis        417 
vtools_genesis        418     /* Find identical suffix.  */
vtools_genesis        419 
vtools_genesis        420     /* |p0| and |p1| point beyond the last chars not yet compared.  */
vtools_genesis        421     p0 = buffer0 + n0;
vtools_genesis        422     p1 = buffer1 + n1;
vtools_genesis        423 
vtools_genesis        424     if (filevec[0].missing_newline == filevec[1].missing_newline) {
vtools_genesis        425         end0 = p0;    /* Addr of last char in file 0.  */
vtools_genesis        426 
vtools_genesis        427         /* Get value of |p0| at which we should stop scanning
vtools_genesis        428        backward: this is when either |p0| or |p1| points just past the
vtools_genesis        429        last char of the identical prefix.  */
vtools_genesis        430         beg0 = filevec[0].prefix_end + (n0 < n1 ? 0 : n0 - n1);
vtools_genesis        431 
vtools_genesis        432         /* Scan back until chars don't match or we reach that point.  */
vtools_genesis        433         while (p0 != beg0)
vtools_genesis        434             if (*--p0 != *--p1) {
vtools_genesis        435                 /* Point at the first char of the matching suffix.  */
vtools_genesis        436                 ++p0, ++p1;
vtools_genesis        437                 beg0 = p0;
vtools_genesis        438                 break;
vtools_genesis        439             }
vtools_genesis        440 
vtools_genesis        441         /* Are we at a line-beginning in both files?  If not, add the
vtools_genesis        442        rest of this line to the main body.  Discard up to
vtools_genesis        443        |horizon_lines| lines from the identical suffix.  Also, discard
vtools_genesis        444        one extra line, because |shift_boundaries| may need it.  */
vtools_genesis        445         i = horizon_lines + !((buffer0 == p0 || p0[-1] == '\n')
vtools_genesis        446                               &&
vtools_genesis        447                               (buffer1 == p1 || p1[-1] == '\n'));
vtools_genesis        448         while (i-- && p0 != end0)
vtools_genesis        449             while (*p0++ != '\n')
vtools_genesis        450                 continue;
vtools_genesis        451 
vtools_genesis        452         p1 += p0 - beg0;
vtools_genesis        453     }
vtools_genesis        454 
vtools_genesis        455     /* Record the suffix.  */
vtools_genesis        456     filevec[0].suffix_begin = p0;
vtools_genesis        457     filevec[1].suffix_begin = p1;
vtools_genesis        458 
vtools_genesis        459     /* Calculate number of lines of prefix to save.
vtools_genesis        460 
vtools_genesis        461        |prefix_count == 0| means save the whole prefix; we need this
vtools_genesis        462        for options like |-D| that output the whole file, or for
vtools_genesis        463        enormous contexts (to avoid worrying about arithmetic
vtools_genesis        464        overflow).  We also need it for options like |-F| that output
vtools_genesis        465        some preceding line; at least we will need to find the last few
vtools_genesis        466        lines, but since we don't know how many, it's easiest to find
vtools_genesis        467        them all.
vtools_genesis        468 
vtools_genesis        469        Otherwise, |prefix_count != 0|.  Save just |prefix_count| lines
vtools_genesis        470        at start of the line buffer; they'll be moved to the proper
vtools_genesis        471        location later.  Handle 1 more line than the context says
vtools_genesis        472        (because we count 1 too many), rounded up to the next power of
vtools_genesis        473        2 to speed index computation.  */
vtools_genesis        474 
vtools_genesis        475     prefix_count = 0;
vtools_genesis        476     alloc_lines0 = guess_lines(0, 0, n0);
vtools_genesis        477     prefix_mask = prefix_count - 1;
vtools_genesis        478     lines = 0;
vtools_genesis        479     linbuf0 = xmalloc(alloc_lines0 * sizeof *linbuf0);
vtools_genesis        480     p0 = buffer0;
vtools_genesis        481 
vtools_genesis        482     /* If the prefix is needed, find the prefix lines.  */
vtools_genesis        483     end0 = filevec[0].prefix_end;
vtools_genesis        484     while (p0 != end0) {
vtools_genesis        485         lin l = lines++ & prefix_mask;
vtools_genesis        486         if (l == alloc_lines0) {
vtools_genesis        487             if (PTRDIFF_MAX / (2 * sizeof *linbuf0) <= alloc_lines0)
vtools_genesis        488                 xalloc_die();
vtools_genesis        489             alloc_lines0 *= 2;
vtools_genesis        490             linbuf0 = xrealloc(linbuf0, alloc_lines0 * sizeof *linbuf0);
vtools_genesis        491         }
vtools_genesis        492         linbuf0[l] = p0;
vtools_genesis        493         while (*p0++ != '\n')
vtools_genesis        494             continue;
vtools_genesis        495     }
vtools_genesis        496     buffered_prefix = prefix_count && context < lines ? context : lines;
vtools_genesis        497 
vtools_genesis        498     /* Allocate line buffer 1.  */
vtools_genesis        499 
vtools_genesis        500     middle_guess = guess_lines(lines, p0 - buffer0, p1 - filevec[1].prefix_end);
vtools_genesis        501     suffix_guess = guess_lines(lines, p0 - buffer0, buffer1 + n1 - p1);
vtools_genesis        502     alloc_lines1 = buffered_prefix + middle_guess + MIN (context, suffix_guess);
vtools_genesis        503     if (alloc_lines1 < buffered_prefix
vtools_genesis        504         || PTRDIFF_MAX / sizeof *linbuf1 <= alloc_lines1)
vtools_genesis        505         xalloc_die();
vtools_genesis        506     linbuf1 = xmalloc(alloc_lines1 * sizeof *linbuf1);
vtools_genesis        507 
vtools_genesis        508     if (buffered_prefix != lines) {
vtools_genesis        509         /* Rotate prefix lines to proper location.  */
vtools_genesis        510         for (i = 0; i < buffered_prefix; i++)
vtools_genesis        511             linbuf1[i] = linbuf0[(lines - context + i) & prefix_mask];
vtools_genesis        512         for (i = 0; i < buffered_prefix; i++)
vtools_genesis        513             linbuf0[i] = linbuf1[i];
vtools_genesis        514     }
vtools_genesis        515 
vtools_genesis        516     /* Initialize line buffer 1 from line buffer 0.  */
vtools_genesis        517     for (i = 0; i < buffered_prefix; i++)
vtools_genesis        518         linbuf1[i] = linbuf0[i] - buffer0 + buffer1;
vtools_genesis        519 
vtools_genesis        520     /* Record the line buffer, adjusted so that
vtools_genesis        521        |linbuf[0]| points at the first differing line.  */
vtools_genesis        522     filevec[0].linbuf = linbuf0 + buffered_prefix;
vtools_genesis        523     filevec[1].linbuf = linbuf1 + buffered_prefix;
vtools_genesis        524     filevec[0].linbuf_base = filevec[1].linbuf_base = -buffered_prefix;
vtools_genesis        525     filevec[0].alloc_lines = alloc_lines0 - buffered_prefix;
vtools_genesis        526     filevec[1].alloc_lines = alloc_lines1 - buffered_prefix;
vtools_genesis        527     filevec[0].prefix_lines = filevec[1].prefix_lines = lines;
vtools_genesis        528 }
vtools_genesis        529 
vtools_genesis        530 /* If $1 < k$, then $(2^k - {\rm prime\_offset}_k)$ is the largest
vtools_genesis        531    prime less than $2^k$.  This table is derived from
vtools_genesis        532    Chris~K.~Caldwell's list
vtools_genesis        533    \url{http://www.utm.edu/research/primes/lists/2small/}.  */
vtools_genesis        534 
vtools_genesis        535 static unsigned char const prime_offset[] =
vtools_genesis        536         {
vtools_genesis        537                 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        538                 15, 3, 39, 5, 39, 57, 3, 35, 1, 5, 9, 41, 31, 5, 25, 45, 7, 87, 21,
vtools_genesis        539                 11, 57, 17, 55, 21, 115, 59, 81, 27, 129, 47, 111, 33, 55, 5, 13, 27,
vtools_genesis        540                 55, 93, 1, 57, 25
vtools_genesis        541         };
vtools_genesis        542 
vtools_genesis        543 /* Given a vector of two |file_data| objects, read the file associated
vtools_genesis        544    with each one, and build the table of equivalence classes.  Return
vtools_genesis        545    nonzero if either file appears to be a binary file.  If
vtools_genesis        546    |pretend_binary| is nonzero, pretend they are binary
vtools_genesis        547    regardless.  */
vtools_genesis        548 
vtools_genesis        549 bool
vtools_genesis        550 read_files(struct file_data filevec[], bool pretend_binary) {
vtools_genesis        551     int i;
vtools_genesis        552     bool skip_test = text | pretend_binary;
vtools_genesis        553     bool appears_binary = pretend_binary | sip(&filevec[0], skip_test);
vtools_genesis        554 
vtools_genesis        555     if (filevec[0].desc != filevec[1].desc)
vtools_genesis        556         appears_binary |= sip(&filevec[1], skip_test | appears_binary);
vtools_genesis        557     else {
vtools_genesis        558         filevec[1].buffer = filevec[0].buffer;
vtools_genesis        559         filevec[1].bufsize = filevec[0].bufsize;
vtools_genesis        560         filevec[1].buffered = filevec[0].buffered;
vtools_genesis        561     }
vtools_genesis        562     if (appears_binary) {
vtools_genesis        563         return true;
vtools_genesis        564     }
vtools_genesis        565 
vtools_genesis        566     find_identical_ends(filevec);
vtools_genesis        567 
vtools_genesis        568     equivs_alloc = filevec[0].alloc_lines + filevec[1].alloc_lines + 1;
vtools_genesis        569     if (PTRDIFF_MAX / sizeof *equivs <= equivs_alloc)
vtools_genesis        570         xalloc_die();
vtools_genesis        571     equivs = xmalloc(equivs_alloc * sizeof *equivs);
vtools_genesis        572     /* Equivalence class 0 is permanently safe for lines that were not
vtools_genesis        573        hashed.  Real equivalence classes start at 1.  */
vtools_genesis        574     equivs_index = 1;
vtools_genesis        575 
vtools_genesis        576     /* Allocate (one plus) a prime number of hash buckets.  Use a
vtools_genesis        577        prime number between $1/3$ and $2/3$ of the value of
vtools_genesis        578        |equiv_allocs|, approximately.  */
vtools_genesis        579     for (i = 9; (size_t) 1 << i < equivs_alloc / 3; i++)
vtools_genesis        580         continue;
vtools_genesis        581     nbuckets = ((size_t) 1 << i) - prime_offset[i];
vtools_genesis        582     if (PTRDIFF_MAX / sizeof *buckets <= nbuckets)
vtools_genesis        583         xalloc_die();
vtools_genesis        584     buckets = zalloc((nbuckets + 1) * sizeof *buckets);
vtools_genesis        585     buckets++;
vtools_genesis        586 
vtools_genesis        587     for (i = 0; i < 2; i++)
vtools_genesis        588         find_and_hash_each_line(&filevec[i]);
vtools_genesis        589 
vtools_genesis        590     filevec[0].equiv_max = filevec[1].equiv_max = equivs_index;
vtools_genesis        591 
vtools_genesis        592     free(equivs);
vtools_genesis        593     free(buckets - 1);
vtools_genesis        594 
vtools_genesis        595     return false;
vtools_genesis        596 }