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