src/mktemplate.cc

   1 /* $Id: mktemplate.cc,v 1.16 2005/07/06 15:29:59 atterer Exp $ -*- C++ -*-
   2   __   _
   3   |_) /|  Copyright (C) 2001-2002  |  richard@
   4   | \/¯|  Richard Atterer          |  atterer.org
   5   ¯ '` ¯
   6   This program is free software; you can redistribute it and/or modify it
   7   under the terms of the GNU General Public License, version 2. See the file
   8   COPYING for details.
   9
  10   Create location list (.jigdo) and image template (.template)
  11
  12   WARNING: This is very complicated code - be sure to run the "torture"
  13   regression test after making changes. Read this file from bottom to top.
  14   The .jigdo generating code is in mkjigdo.cc. The code for the queue of
  15   partial matches is in partialmatch.*.
  16
  17   In the log messages that are output with --debug, uppercase means that it
  18   is finally decided what this area of the image is: UNMATCHED or a MATCH of
  19   a file.
  20
  21 */
  22
  23 #include <config.h>
  24
  25 #include <errno.h>
  26 #include <math.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <zlib.h>
  30
  31 #include <algorithm>
  32 #include <iostream>
  33 #include <fstream>
  34 #include <map>
  35 #include <memory>
  36
  37 #include <autoptr.hh>
  38 #include <compat.hh>
  39 #include <debug.hh>
  40 #include <log.hh>
  41 #include <mimestream.hh>
  42 #include <mkimage.hh>
  43 #include <mktemplate.hh>
  44 #include <scan.hh>
  45 #include <string.hh>
  46 #include <zstream-gz.hh>
  47 #include <zstream-bz.hh>
  48 //______________________________________________________________________
  49
  50 void MkTemplate::ProgressReporter::error(const string& message) {
  51   cerr << message << endl;
  52 }
  53 void MkTemplate::ProgressReporter::scanningImage(uint64) { }
  54 void MkTemplate::ProgressReporter::matchFound(const FilePart*, uint64) { }
  55 void MkTemplate::ProgressReporter::finished(uint64) { }
  56
  57 MkTemplate::ProgressReporter MkTemplate::noReport;
  58 //______________________________________________________________________
  59
  60 MkTemplate::MkTemplate(JigdoCache* jcache, bistream* imageStream,
  61     JigdoConfig* jigdoInfo, bostream* templateStream, ProgressReporter& pr,
  62     int zipQuality, size_t readAmnt, bool addImage, bool addServers,
  63     bool useBzip2)
  64   : fileSizeTotal(0U), fileCount(0U), block(), readAmount(readAmnt),
  65     off(), unmatchedStart(), greedyMatching(true),
  66     cache(jcache),
  67     image(imageStream), templ(templateStream), zip(0),
  68     zipQual(zipQuality), reporter(pr), matches(new PartialMatchQueue()),
  69     sectorLength(),
  70     jigdo(jigdoInfo), addImageSection(addImage),
  71     addServersSection(addServers), useBzLib(useBzip2),
  72     matchExec() { }
  73 //______________________________________________________________________
  74
  75 /* Because make-template should be debuggable even in non-debug builds,
  76    always compile in debug messages. */
  77 #undef debug
  78 Logger MkTemplate::debug("make-template");
  79 //______________________________________________________________________
  80
  81 namespace {
  82
  83   // Find the position of the highest set bit (e.g. for 0x20, result is 5)
  84   inline int bitWidth(uint32 x) {
  85     int r = 0;
  86     Assert(x <= 0xffffffff); // Can't cope with >32 bits
  87     if (x & 0xffff0000) { r += 16; x >>= 16; }
  88     if (x & 0xff00) { r += 8; x >>= 8; }
  89     if (x & 0xf0) { r += 4; x >>= 4; }
  90     if (x & 0xc) { r += 2; x >>= 2; }
  91     if (x & 2) { r += 1; x >>=1; }
  92     if (x & 1) r += 1;
  93     return r;
  94   }
  95   //________________________________________
  96
  97   /* Avoid integer divisions: Modulo addition/subtraction, with
  98      certain assertions */
  99   // Returns (a + b) % m, if (a < m && b <= m)
 100   inline size_t modAdd(size_t a, size_t b, size_t m) {
 101     size_t r = a + b;
 102     if (r >= m) r -= m;
 103     Paranoid(r == (a + b) % m);
 104     return r;
 105   }
 106   // Returns (a - b) mod m, if (a < m && b <= m)
 107   inline size_t modSub(size_t a, size_t b, size_t m) {
 108     size_t r = a + m - b;
 109     if (r >= m) r -= m;
 110     Paranoid(r == (m + a - b) % m);
 111     return r;
 112   }
 113   // Returns (a + b) % m, if (a < m && -m <= b && b <= m)
 114   inline size_t modAdd(size_t a, int b, size_t m) {
 115     size_t r = a;
 116     if (b < 0) r += m;
 117     r += b;
 118     if (r >= m) r -= m;
 119     Paranoid(r == (a + static_cast<size_t>(b + m)) % m);
 120     return r;
 121   }
 122   //____________________
 123
 124   /* Write part of a circular buffer to a Zobstream object, starting
 125      with offset "start" (incl) and ending with offset "end" (excl).
 126      Offsets can be equal to bufferLength. If both offsets are equal,
 127      the whole buffer content is written. */
 128   inline void writeBuf(const byte* const buf, size_t begin, size_t end,
 129                        const size_t bufferLength, Zobstream* zip) {
 130     Paranoid(begin <= bufferLength && end <= bufferLength);
 131     if (begin < end) {
 132       zip->write(buf + begin, (unsigned int)(end - begin));
 133     } else {
 134       zip->write(buf + begin, (unsigned int)(bufferLength - begin));
 135       zip->write(buf, (unsigned int)end);
 136     }
 137   }
 138   //____________________
 139
 140   // Write lower 48 bits of x to s in little-endian order
 141   void write48(bostream& s, uint64 x) {
 142 #   if 0
 143     s << static_cast<byte>(x & 0xff)
 144       << static_cast<byte>((x >> 8) & 0xff)
 145       << static_cast<byte>((x >> 16) & 0xff)
 146       << static_cast<byte>((x >> 24) & 0xff)
 147       << static_cast<byte>((x >> 32) & 0xff)
 148       << static_cast<byte>((x >> 40) & 0xff);
 149 #   else
 150     s.put(static_cast<byte>( x        & 0xff));
 151     s.put(static_cast<byte>((x >> 8)  & 0xff));
 152     s.put(static_cast<byte>((x >> 16) & 0xff));
 153     s.put(static_cast<byte>((x >> 24) & 0xff));
 154     s.put(static_cast<byte>((x >> 32) & 0xff));
 155     s.put(static_cast<byte>((x >> 40) & 0xff));
 156 #   endif
 157   }
 158
 159 } // namespace
 160 //______________________________________________________________________
 161
 162 /** Build up a template DESC section by appending items to a
 163     JigdoDescVec. Calls to descUnmatchedData() are allowed to accumulate, so
 164     that >1 consecutive unmatched data areas are merged into one in the DESC
 165     section. */
 166 class MkTemplate::Desc {
 167 public:
 168   Desc() : files(), offset(0) { }
 169
 170   // Insert in DESC section: information about whole image
 171   inline void imageInfo(uint64 len, const MD5Sum& md5, size_t blockLength) {
 172     files.reserve((files.size() + 16) % 16);
 173     files.push_back(new JigdoDesc::ImageInfo(len, md5, blockLength));
 174   }
 175   // Insert in DESC section: info about some data that was not matched
 176   inline void unmatchedData(uint64 len) {
 177     JigdoDesc::UnmatchedData* u;
 178     if (files.size() > 0
 179         && (u = dynamic_cast<JigdoDesc::UnmatchedData*>(files.back())) !=0) {
 180       // Add more unmatched data to already existing UnmatchedData object
 181       u->resize(u->size() + len);
 182     } else {
 183       // Create new UnmatchedData object.
 184       files.reserve((files.size() + 16) % 16);
 185       files.push_back(new JigdoDesc::UnmatchedData(offset, len));
 186     }
 187     offset += len;
 188   }
 189   // Insert in DESC section: information about a file that matched
 190   inline void matchedFile(uint64 len, const RsyncSum64& r,
 191                           const MD5Sum& md5) {
 192     files.reserve((files.size() + 16) % 16);
 193     files.push_back(new JigdoDesc::MatchedFile(offset, len, r, md5));
 194     offset += len;
 195   }
 196   inline bostream& put(bostream& s, MD5Sum* md) {
 197     files.put(s, md);
 198     return s;
 199   }
 200 private:
 201   JigdoDescVec files;
 202   uint64 offset;
 203 };
 204 //______________________________________________________________________
 205
 206 /* The following are helpers used by run(). It is usually not adequate
 207    to make such large functions inline, but there is only one call to
 208    them, anyway. */
 209
 210 inline bool MkTemplate::scanFiles(size_t blockLength, uint32 blockMask,
 211                                   size_t md5BlockLength) {
 212   bool result = SUCCESS;
 213
 214   cache->setParams(blockLength, md5BlockLength);
 215   FileVec::iterator hashPos;
 216
 217   for (JigdoCache::iterator file = cache->begin();
 218        file != cache->end(); ++file) {
 219     const RsyncSum64* sum = file->getRsyncSum(cache);
 220     if (sum == 0) continue; // Error - skip
 221     // Add file to hash list
 222     hashPos = block.begin() + (sum->getHi() & blockMask);
 223     hashPos->push_back(&*file);
 224   }
 225   return result;
 226 }
 227 //________________________________________
 228
 229 void MkTemplate::checkRsyncSumMatch2(const size_t blockLen,
 230     const size_t back, const size_t md5BlockLength, uint64& nextEvent,
 231     FilePart* file) {
 232
 233   /* Don't schedule match if its startOff (== off - blockLen) is impossible.
 234      This is e.g. the case when file A is 1024 bytes long (i.e. is
 235      immediately matched once seen), and the first 1024 bytes of file B are
 236      equal to file A, and file B is in the image.
 237      [I think A gets matched, then the following line prevents that a partial
 238      match for B is also recorded.]
 239      Also prevents matches whose startOffset is <0, which could otherwise
 240      happen because rsum covers a blockLen-sized area of 0x7f bytes at the
 241      beginning. */
 242   if (off < unmatchedStart + blockLen) return;
 243
 244   PartialMatch* x; // Ptr to new entry in "matches"
 245   if (matches->full()) {
 246     x = matches->findDropCandidate(&sectorLength, off - blockLen);
 247     if (x == 0 || x->file() == file) {
 248       /* If no more space left in queue and none of the entries in it is
 249          appropriate for discarding, just discard this possible file match!
 250          It's the only option if there are many, many overlapping matches,
 251          otherwise the program would get extremely slow. */
 252       debug(" %1: DROPPED possible %2 match at offset %3 (queue full)",
 253             off, file->leafName(), off - blockLen);
 254       return;
 255     }
 256     // Overwrite existing entry in the queue
 257     debug(" %1: DROPPED possible %2 match at offset %3 (queue full, match "
 258           "below replaces it)",
 259           off, x->file()->leafName(), x->startOffset());
 260   } else { // !matches->full()
 261     // Add new entry to the queue
 262     x = matches->addFront();
 263   }
 264
 265   /* Rolling rsum matched - schedule an MD5Sum match. NB: In extreme cases,
 266      nextEvent may be equal to off */
 267   x->setStartOffset(off - blockLen);
 268   size_t eventLen = (file->size() < md5BlockLength ?
 269                      file->size() : md5BlockLength);
 270   x->setNextEvent(matches, x->startOffset() + eventLen);
 271   debug(" %1: Head of %2 match at offset %3, my next event %4",
 272         off, file->leafName(), x->startOffset(), x->nextEvent());
 273   if (x->nextEvent() < nextEvent) nextEvent = x->nextEvent();
 274   x->setBlockOffset(back);
 275   x->setBlockNumber(0);
 276   x->setFile(file);
 277 }
 278
 279 /* Look for matches of sum (i.e. scanImage()'s rsum). If found, insert
 280    appropriate entry in "matches". */
 281 void MkTemplate::checkRsyncSumMatch(const RsyncSum64& sum,
 282     const uint32& bitMask, const size_t blockLen, const size_t back,
 283     const size_t md5BlockLength, uint64& nextEvent) {
 284
 285   typedef const vector<FilePart*> FVec;
 286   FVec& hashEntry = block[sum.getHi() & bitMask];
 287   if (hashEntry.empty()) return;
 288
 289   FVec::const_iterator i = hashEntry.begin(), e = hashEntry.end();
 290   do {
 291     FilePart* file = *i;
 292     const RsyncSum64* fileSum = file->getRsyncSum(cache);
 293     if (fileSum != 0 && *fileSum == sum)
 294       // Insert new partial file match in "matches" queue
 295       checkRsyncSumMatch2(blockLen, back, md5BlockLength, nextEvent, file);
 296     ++i;
 297   } while (i != e);
 298   return;
 299 }
 300 //________________________________________
 301
 302 // Read the 'count' first bytes from file x and write them to zip
 303 bool MkTemplate::rereadUnmatched(FilePart* file, uint64 count) {
 304   // Lower peak memory usage: Deallocate cache's buffer
 305   cache->deallocBuffer();
 306
 307   ArrayAutoPtr<byte> tmpBuf(new byte[readAmount]);
 308   string inputName = file->getPath();
 309   inputName += file->leafName();
 310   auto_ptr<bistream> inputFile(new bifstream(inputName.c_str(),ios::binary));
 311   while (inputFile->good() && count > 0) {
 312     // read data
 313     readBytes(*inputFile, tmpBuf.get(),
 314               (readAmount < count ? readAmount : count));
 315     size_t n = inputFile->gcount();
 316     zip->write(tmpBuf.get(), (unsigned int)n); // will catch Zerror "upstream"
 317     Paranoid(n <= count);
 318     count -= n;
 319   }
 320   if (count == 0) return SUCCESS;
 321
 322   // error
 323   string err = subst(_("Error reading from `%1' (%2)"),
 324                      inputName, strerror(errno));
 325   reporter.error(err);
 326   return FAILURE;
 327 }
 328 //________________________________________
 329
 330 // Print info about a part of the input image
 331 void MkTemplate::printRangeInfo(uint64 start, uint64 end, const char* msg,
 332                                 const PartialMatch* x) {
 333   static const string empty;
 334   debug("[%1,%2) %3 %4", start, end, msg,
 335         (x != 0 ? x->file()->leafName() : empty) );
 336 }
 337
 338 // oldAreaEnd != start, something's seriously wrong
 339 void MkTemplate::debugRangeFailed() {
 340   static bool printed = false;
 341   cerr << "Assertion failed: oldAreaEnd == start" << endl;
 342   if (!printed) {
 343     cerr <<
 344       "You have found a bug in jigdo-file. The generated .template file is\n"
 345       "very likely broken! To help me find the bug, please rerun the\n"
 346       "command as follows:\n"
 347       "  [previous-command] --report=noprogress --debug=make-template >log 2>&1\n"
 348       "and send the _compressed_ `log' file to <jigdo" << "@atterer.org>."
 349          << endl;
 350     printed = true;
 351   }
 352 }
 353 //________________________________________
 354
 355 /* The block didn't match, so the whole file x doesn't match - re-read from
 356    file any data that is no longer buffered (and not covered by another
 357    match), and write it to the Zobstream. */
 358 bool MkTemplate::checkMD5Match_mismatch(const size_t stillBuffered,
 359                                         PartialMatch* x, Desc& desc) {
 360   const PartialMatch* oldestMatch = matches->findLowestStartOffset();
 361   uint64 rereadEnd = off - stillBuffered;
 362   uint64 xStartOffset = x->startOffset();
 363   if (x != oldestMatch || xStartOffset >= rereadEnd) {
 364     // Everything still buffered, or there is another pending match
 365     matches->eraseFront(); // return x to free pool
 366     return SUCCESS;
 367   }
 368
 369   /* Reread the right amount of data from the file for x, covering the image
 370      area from x->startOffset() to the first byte which is "claimed" by
 371      something else - either another match or the start of the still buffered
 372      data. */
 373   FilePart* xfile = x->file();
 374   Assert(matches->front() == x);
 375   matches->eraseFront(); // return x to free pool
 376   if (!matches->empty()) {
 377     // set rereadEnd to new lowest startOffset in matches
 378     const PartialMatch* newOldestMatch = matches->findLowestStartOffset();
 379     if (rereadEnd > newOldestMatch->startOffset())
 380       rereadEnd = newOldestMatch->startOffset();
 381   }
 382   debugRangeInfo(xStartOffset, rereadEnd,
 383                  "UNMATCHED after some blocks, re-reading from", x);
 384
 385   desc.unmatchedData(rereadEnd - xStartOffset);
 386   unmatchedStart = rereadEnd;
 387
 388   uint64 bytesToWrite = rereadEnd - xStartOffset;
 389   return rereadUnmatched(xfile, bytesToWrite);
 390 }
 391 //________________________________________
 392
 393 /* The file x was found in the image, and --match-exec is set. Set up env
 394    vars, run command.
 395
 396    Why does this use system() instead of the "more secure" exec()? Because
 397    then things are actually easier to get right IMHO! My scenario is that
 398    someone has set up an env var with the destination path for the fallback,
 399    say $DEST, which might contain spaces. In that case, using exec() with
 400    some kind of "%label" substitution is awkward and error-prone - let's just
 401    have one single substitution scheme, that used by the shell! */
 402 bool MkTemplate::matchExecCommands(PartialMatch* x) {
 403   Paranoid(!matchExec.empty());
 404
 405   string matchPath, leaf;
 406   const string& leafName = x->file()->leafName();
 407   string::size_type lastSlash = leafName.rfind(DIRSEP);
 408   if (lastSlash == string::npos) {
 409     leaf = leafName;
 410   } else {
 411     matchPath.assign(leafName, 0, lastSlash + 1);
 412     leaf.assign(leafName, lastSlash + 1, string::npos);
 413   }
 414   Base64String md5Sum;
 415   md5Sum.write(x->file()->getMD5Sum(cache)->digest(), 16).flush();
 416   string file = x->file()->getLocation()->getPath();
 417   file += leafName;
 418
 419   // Set environment vars
 420   if (compat_setenv("LABEL", x->file()->getLocation()->getLabel().c_str())
 421       || compat_setenv("LABELPATH", x->file()->getLocation()->getPath()
 422                        .c_str())
 423       || compat_setenv("MATCHPATH", matchPath.c_str())
 424       || compat_setenv("LEAF", leaf.c_str())
 425       || compat_setenv("MD5SUM", md5Sum.result().c_str())
 426       || compat_setenv("FILE", file.c_str())) {
 427     reporter.error(_("Could not set up environment for --match-exec "
 428                      "command"));
 429     return FAILURE;
 430   }
 431
 432   // Execute command
 433   int status = system(matchExec.c_str());
 434   if (status == 0) return SUCCESS;
 435   reporter.error(_("Command supplied with --match-exec failed"));
 436   return FAILURE;
 437 }
 438 //________________________________________
 439
 440 /* Calculate MD5 for the previous md5ChunkLength (or less if at end of match)
 441    bytes. If the calculated checksum matches and it is the last MD5 block in
 442    the file, record a file match. If the i-th MD5Sum does not match, write
 443    the i*md5ChunkLength bytes directly to templ.
 444    @param stillBuffered bytes of image data "before current position" that
 445    are still in the buffer; they are at buf[data] to
 446    buf[(data+stillBuffered-1)%bufferLength] */
 447 bool MkTemplate::checkMD5Match(byte* const buf,
 448     const size_t bufferLength, const size_t data,
 449     const size_t md5BlockLength, uint64& nextEvent,
 450     const size_t stillBuffered, Desc& desc) {
 451   PartialMatch* x = matches->front();
 452   Paranoid(x != 0 && matches->nextEvent() == off);
 453
 454   /* Calculate MD5Sum from buf[x->blockOff] to buf[data-1], deal with
 455      wraparound. NB 0 <= x->blockOff < bufferLength, but 1 <= data <
 456      bufferLength+1 */
 457   static MD5Sum md;
 458   md.reset();
 459   if (x->blockOffset() < data) {
 460     md.update(buf + x->blockOffset(), data - x->blockOffset());
 461   } else {
 462     md.update(buf + x->blockOffset(), bufferLength - x->blockOffset());
 463     md.update(buf, data);
 464   }
 465   md.finishForReuse();
 466   //____________________
 467
 468   const MD5* xfileSum = x->file()->getSums(cache, x->blockNumber());
 469   if (debug)
 470     debug("checkMD5Match?: image %1, file %2 block #%3 %4",
 471           md.toString(), x->file()->leafName(), x->blockNumber(),
 472           (xfileSum ? xfileSum->toString() : "[error]") );
 473
 474   if (xfileSum == 0 || md != *xfileSum) {
 475     /* The block didn't match, so the whole file doesn't match - re-read from
 476        file any data that is no longer buffered (and not covered by another
 477        match), and write it to the Zobstream. */
 478     return checkMD5Match_mismatch(stillBuffered, x, desc);
 479   }
 480   //____________________
 481
 482   // Another block of file matched - was it the last one?
 483   if (off < x->startOffset() + x->file()->size()) {
 484     // Still some more to go - update x and its position in queue
 485     x->setBlockOffset(data);
 486     x->setBlockNumber(x->blockNumber() + 1);
 487     x->setNextEvent(matches, min(x->nextEvent() + md5BlockLength,
 488                                  x->startOffset() + x->file()->size()));
 489     nextEvent = min(nextEvent, x->nextEvent());
 490     debug("checkMD5Match: match and more to go, next at off %1",
 491           x->nextEvent());
 492     return SUCCESS;
 493   }
 494   //____________________
 495
 496   Assert(off == x->startOffset() + x->file()->size());
 497   // Heureka! *MATCH*
 498   // x = address of PartialMatch obj of file that matched
 499
 500   const PartialMatch* oldestMatch = matches->findLowestStartOffset();
 501
 502   if (!greedyMatching && x != oldestMatch) {
 503     // A larger match is possible, so skip this match
 504     debug("IGNORING match due to --no-greedy-matching: [%1,%2) %3",
 505           x->startOffset(), off, x->file()->leafName());
 506     matches->eraseFront(); // return x to free pool
 507     return SUCCESS;
 508   }
 509
 510   reporter.matchFound(x->file(), x->startOffset());
 511   matchedParts.push_back(x->file());
 512
 513   /* Re-read and write out data before the start of the match, i.e. of any
 514      half-finished bigger match (which we abandon now that we've found a
 515      smaller match inside it). */
 516   if (x != oldestMatch && oldestMatch->startOffset() < off - stillBuffered) {
 517     unmatchedStart = min(off - stillBuffered, x->startOffset());
 518     debugRangeInfo(oldestMatch->startOffset(), unmatchedStart,
 519                    "UNMATCHED, re-reading partial match from", oldestMatch);
 520     size_t toReread = unmatchedStart - oldestMatch->startOffset();
 521     desc.unmatchedData(toReread);
 522     if (rereadUnmatched(oldestMatch->file(), toReread))
 523       return FAILURE;
 524   }
 525
 526   /* Write out data that is still buffered, and is before the start of the
 527      match. */
 528   if (unmatchedStart < x->startOffset()) {
 529     debugRangeInfo(unmatchedStart, x->startOffset(),
 530                    "UNMATCHED, buffer flush before match");
 531     size_t toWrite = x->startOffset() - unmatchedStart;
 532     Paranoid(off - unmatchedStart <= bufferLength);
 533     size_t writeStart = modSub(data, off - unmatchedStart, bufferLength);
 534     writeBuf(buf, writeStart, modAdd(writeStart, toWrite, bufferLength),
 535              bufferLength, zip);
 536     desc.unmatchedData(toWrite);
 537   }
 538
 539   // Assert(x->file->mdValid);
 540   desc.matchedFile(x->file()->size(), *(x->file()->getRsyncSum(cache)),
 541                    *(x->file()->getMD5Sum(cache)));
 542   unmatchedStart = off;
 543   debugRangeInfo(x->startOffset(), off, "MATCH:", x);
 544
 545   // With --match-exec, execute user-supplied command(s)
 546   if (!matchExec.empty()
 547       && matchExecCommands(x) == FAILURE)
 548     return FAILURE;
 549
 550   /* Remove all matches with startOff < off (this includes x). This is the
 551      greedy approach and is not ideal: If a small file A happens to match one
 552      small fraction of a large file B and B is contained in the image, then
 553      only a match of A will be found. */
 554   Paranoid(x->startOffset() < off);
 555   matches->eraseStartOffsetLess(off);
 556
 557   return SUCCESS;
 558 }
 559 //________________________________________
 560
 561 /* This is called in case the end of the image has been reached, but
 562    unmatchedStart < off, i.e. there was a partial match at the end of the
 563    image. Just discards that match and writes the data to the template,
 564    either by re-reading from the partially matched file, or from the buffer.
 565    Compare to similar code in checkMD5Match.
 566
 567    Since we are at the end of the image, the full last bufferLength bytes of
 568    the image are in the buffer. */
 569 bool MkTemplate::unmatchedAtEnd(byte* const buf,
 570     const size_t bufferLength, const size_t data, Desc& desc) {
 571   Paranoid(unmatchedStart < off); // cf. where this is called
 572
 573   // Re-read and write out data that is no longer buffered.
 574   const PartialMatch* y = matches->findStartOffset(unmatchedStart);
 575   if (y != 0 && y->startOffset() < off - bufferLength) {
 576     unmatchedStart = off - bufferLength;
 577     debugRangeInfo(y->startOffset(), unmatchedStart,
 578                    "UNMATCHED at end, re-reading partial match from", y);
 579     size_t toReread = unmatchedStart - y->startOffset();
 580     desc.unmatchedData(toReread);
 581     if (rereadUnmatched(y->file(), toReread))
 582       return FAILURE;
 583   }
 584   // Write out data that is still buffered
 585   if (unmatchedStart < off) {
 586     debugRangeInfo(unmatchedStart, off, "UNMATCHED at end");
 587     size_t toWrite = off - unmatchedStart;
 588     Assert(toWrite <= bufferLength);
 589     size_t writeStart = modSub(data, toWrite, bufferLength);
 590     writeBuf(buf, writeStart, data, bufferLength, zip);
 591     desc.unmatchedData(toWrite);
 592     unmatchedStart = off;
 593   }
 594   return SUCCESS;
 595 }
 596 //________________________________________
 597
 598 /* The "matches" queue is full. Typically, when this happens there is a big
 599    zero-filled area in the image and one or more input files start with
 600    zeroes. At this point, we must start dropping some prospective file
 601    matches. This is done based on the heuristics that actual file matches
 602    occur at a "sector boundary" in the image. See INITIAL_SECTOR_LENGTH in
 603    mktemplate.hh for more.
 604
 605    This method is a variant of the main loop which is used when
 606    matches.full(), and which advances the rsum window by one sector at a
 607    time. */
 608 void MkTemplate::scanImage_mainLoop_fastForward(uint64 nextEvent,
 609     RsyncSum64* rsum, byte* buf, size_t* data, size_t* n, size_t* rsumBack,
 610     size_t bufferLength, size_t blockLength, uint32 blockMask,
 611     size_t md5BlockLength) {
 612
 613 # if 0
 614   // Simple version
 615   debug("DROPPING, fast forward (queue full)");
 616   Assert(off >= blockLength);
 617   unsigned sectorMask = sectorLength - 1;
 618   while (off < nextEvent) {
 619     rsum->removeFront(buf[*rsumBack], blockLength);
 620     rsum->addBack(buf[*data]);
 621     ++*data; ++off; --*n;
 622     *rsumBack = modAdd(*rsumBack, 1, bufferLength);
 623     if (((off - blockLength) & sectorMask) == 0) {
 624       checkRsyncSumMatch(*rsum, blockMask, blockLength, *rsumBack,
 625                          md5BlockLength, nextEvent);
 626       sectorMask = sectorLength - 1;
 627       Paranoid(matches->empty()
 628                || matches->front()->startOffset() >= unmatchedStart);
 629     }
 630   }
 631
 632 # else
 633
 634   debug("DROPPING, fast forward (queue full)");
 635   Assert(off >= blockLength);
 636
 637   unsigned sectorMask = sectorLength - 1;
 638   uint64 notSectorMask = ~implicit_cast<uint64>(sectorMask);
 639   while (off < nextEvent) {
 640     /* Calculate next value of off where a match would end up having an even
 641        (i.e. sectorSize-aligned) start offset.
 642
 643                              |----sectorLength----|----sectorLength----|
 644                     |========+========+===========+===+===========+====+=====>EOF
 645        File offset: 0                             |  off          |
 646                                       |--blockLength--|           |
 647                                                   |--blockLength--|
 648                                                                   |
 649                                                             nextAlignedOff */
 650     uint64 nextAlignedOff = off - blockLength;
 651     nextAlignedOff = (nextAlignedOff + sectorLength) & notSectorMask;
 652     nextAlignedOff += blockLength;
 653     Assert(nextAlignedOff > off);
 654
 655     unsigned long len = nextAlignedOff - off;
 656     if (len > nextEvent - off) len = nextEvent - off;
 657     // Advance rsum by len bytes in one go
 658 #   if DEBUG
 659     RsyncSum64 rsum2 = *rsum; size_t rsumBack2 = *rsumBack;
 660     uint64 off2 = off; size_t data2 = *data;
 661 #   endif
 662     if (*rsumBack + len <= bufferLength) {
 663       rsum->removeFront(buf + *rsumBack, len, blockLength);
 664     } else {
 665       rsum->removeFront(buf + *rsumBack, bufferLength - *rsumBack,
 666                         blockLength);
 667       rsum->removeFront(buf, len + *rsumBack - bufferLength,
 668                         blockLength + *rsumBack - bufferLength);
 669     }
 670     Paranoid(*data + len <= bufferLength);
 671     rsum->addBack(buf + *data, len);
 672     *data += len; off += len; *n -= len;
 673     *rsumBack = modAdd(*rsumBack, implicit_cast<size_t>(len), bufferLength);
 674     Paranoid(off == nextEvent || off == nextAlignedOff);
 675 #   if DEBUG
 676     for (unsigned i = 0; i < len; ++i) {
 677       rsum2.removeFront(buf[rsumBack2], blockLength);
 678       rsum2.addBack(buf[data2]);
 679       ++data2; ++off2;
 680       rsumBack2 = modAdd(rsumBack2, 1, bufferLength);
 681     }
 682     Assert(rsumBack2 == *rsumBack);
 683     Assert(off2 == off);
 684     Assert(data2 == *data);
 685     Assert(rsum2 == *rsum);
 686 #   endif
 687
 688     //debug("DROPPING, fast forward (queue full) to %1", off);
 689
 690     if (off == nextAlignedOff) {
 691       Paranoid(((off - blockLength) & sectorMask) == 0);
 692       checkRsyncSumMatch(*rsum, blockMask, blockLength, *rsumBack,
 693                          md5BlockLength, nextEvent);
 694       Paranoid(matches->empty()
 695                || matches->front()->startOffset() >= unmatchedStart);
 696       sectorMask = sectorLength - 1;
 697       notSectorMask = ~implicit_cast<uint64>(sectorMask);
 698     }
 699   } // endwhile (off < nextEvent)
 700 # endif
 701 }
 702 //________________________________________
 703
 704 /* Scan image. Central function for template generation.
 705
 706    Treat buf as a circular buffer. Read new data into at most half the
 707    buffer. Calculate a rolling checksum covering blockLength bytes. When it
 708    matches an entry in block, start calculating MD5Sums of blocks of length
 709    md5BlockLength.
 710
 711    Since both image and templ can be non-seekable, we run into a problem in
 712    the following case: After the initial RsyncSum match, a few of the
 713    md5BlockLength-sized chunks of one input file were matched, but not all,
 714    so in the end, there is no match. Consequently, we would now need to
 715    re-read that part of the image and pump it through zlib to templ - but we
 716    can't if the image is stdin! Solution: Since we know that the MD5Sum of a
 717    block matched part of an input file, we can re-read from there. */
 718 inline bool MkTemplate::scanImage(byte* buf, size_t bufferLength,
 719     size_t blockLength, uint32 blockMask, size_t md5BlockLength,
 720     MD5Sum& templMd5Sum) {
 721   bool result = SUCCESS;
 722
 723   /* Cause input files to be analysed */
 724   if (scanFiles(blockLength, blockMask, md5BlockLength))
 725     result = FAILURE;
 726
 727   /* Initialise rolling sums with blockSize bytes 0x7f, and do the same with
 728      part of buffer, to avoid special-case code in main loop. (Any value
 729      would do - except that 0x00 or 0xff might lead to a larger number of
 730      false positives.) */
 731   RsyncSum64 rsum;
 732   byte* bufEnd = buf + bufferLength;
 733   //for (byte* z = bufEnd - blockLength; z < bufEnd; ++z) *z = 0x7f;
 734   // Init entire buf, keep valgrind happy
 735   for (byte* z = buf; z < bufEnd; ++z) *z = 0x7f;
 736   rsum.addBackNtimes(0x7f, blockLength);
 737
 738   // Compression pipe for templ data
 739   auto_ptr<Zobstream> zipDel;
 740   if (useBzLib)
 741     zipDel.reset(implicit_cast<Zobstream*>(
 742       new ZobstreamBz(*templ, zipQual, 256U, &templMd5Sum) ));
 743   else
 744     zipDel.reset(implicit_cast<Zobstream*>(
 745       new ZobstreamGz(*templ, ZIPCHUNK_SIZE, zipQual, 15, 8, 256U,
 746                       &templMd5Sum) ));
 747   zip = zipDel.get();
 748   Desc desc; // Buffer for DESC data, will be appended to templ at end
 749   size_t data = 0; // Offset into buf of byte currently being processed
 750   off = 0; // Current absolute offset in image, corresponds to "data"
 751   uint64 nextReport = 0; // call reporter once off reaches this value
 752
 753   /* The area delimited by unmatchedStart (incl) and off (excl) has "not been
 754      dealt with", either by writing it to zip, or by a match with the first
 755      MD5 block of an input file. Once a partial match of a file has been
 756      detected, unmatchedStart "gets stuck" at the start offset of this file
 757      within the image. */
 758   unmatchedStart = 0;
 759
 760   MD5Sum imageMd5Sum; // MD5 of whole image
 761   MD5Sum md; // Re-used for each 2nd-level check of any rsum match
 762   matches->erase();
 763   sectorLength = INITIAL_SECTOR_LENGTH;
 764
 765   // Read image
 766   size_t rsumBack = bufferLength - blockLength;
 767
 768   try {
 769     /* Catch Zerrors, which can occur in zip->write(), writeBuf(),
 770        checkMD5Match(), zip->close() */
 771     while (image->good()) {
 772
 773       debug("---------- main loop. off=%1 data=%2 unmatchedStart=%3",
 774             off, data, unmatchedStart);
 775
 776       if (off >= nextReport) { // Keep user entertained
 777         reporter.scanningImage(off);
 778         nextReport += REPORT_INTERVAL;
 779       }
 780
 781       // zip->write() out any old data that we'll destroy with read()
 782       size_t thisReadAmount = (readAmount < bufferLength - data ?
 783                                readAmount : bufferLength - data);
 784       uint64 newUnmatchedStart = 0;
 785       if (off > blockLength)
 786         newUnmatchedStart = off - blockLength;
 787       if (!matches->empty()) {
 788         newUnmatchedStart = min(newUnmatchedStart,
 789                                 matches->lowestStartOffset()->startOffset());
 790       }
 791       if (unmatchedStart < newUnmatchedStart) {
 792         size_t toWrite = newUnmatchedStart - unmatchedStart;
 793         Paranoid(off - unmatchedStart <= bufferLength);
 794         //debug("off=%1 unmatchedStart=%2 buflen=%3",
 795         //      off, unmatchedStart, bufferLength);
 796         size_t writeStart = modSub(data, off - unmatchedStart,
 797                                    bufferLength);
 798         debugRangeInfo(unmatchedStart, unmatchedStart + toWrite,
 799                        "UNMATCHED");
 800         writeBuf(buf, writeStart,
 801                  modAdd(writeStart, toWrite, bufferLength),
 802                  bufferLength, zip);
 803         unmatchedStart = newUnmatchedStart;
 804         desc.unmatchedData(toWrite);
 805       }
 806
 807       // Read new data from image
 808 #     if DEBUG // just for testing, make it sometimes read less
 809       static size_t chaosOff, acc;
 810       if (unmatchedStart == 0) { chaosOff = 0; acc = 0; }
 811       acc += buf[chaosOff] ^ buf[off % bufferLength] + ~off;
 812       if (chaosOff == 0) chaosOff = bufferLength - 1; else --chaosOff;
 813       if ((acc & 0x7) == 0) {
 814         thisReadAmount = acc % thisReadAmount + 1;
 815         debug("thisReadAmount=%1", thisReadAmount);
 816       }
 817 #     endif
 818       readBytes(*image, buf + data, thisReadAmount);
 819       size_t n = image->gcount();
 820       imageMd5Sum.update(buf + data, n);
 821
 822       while (n > 0) { // Still unprocessed bytes left
 823         uint64 nextEvent = off + n; // Special event: end of buffer
 824         if (!matches->empty())
 825           nextEvent = min(nextEvent, matches->front()->nextEvent());
 826
 827         if (!matches->full()) {
 828           sectorLength = INITIAL_SECTOR_LENGTH;
 829
 830           /* Unrolled innermost loop - see below for single-iteration
 831              version. Also see checkRsyncSumMatch above. */
 832           while (off + 32 < nextEvent && rsumBack < bufferLength - 32) {
 833             size_t dataOld = data;
 834             do {
 835               const vector<FilePart*>* hashEntry;
 836 #             define x ; \
 837               rsum.removeFront(buf[rsumBack], blockLength); \
 838               rsum.addBack(buf[data]); \
 839               ++data; ++rsumBack; \
 840               hashEntry = &block[rsum.getHi() & blockMask]; \
 841               if (hashEntry->size() > 1) break; \
 842               if (hashEntry->size() == 1) { \
 843                 FilePart* file = (*hashEntry)[0]; \
 844                 const RsyncSum64* fileSum = file->getRsyncSum(cache); \
 845                 if (fileSum != 0 && *fileSum == rsum) break; \
 846               }
 847               x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
 848 #             undef x
 849               dataOld = data; // Special case: "Did not break out of loop"
 850             } while (false);
 851             if (dataOld == data) {
 852               off += 32; n -= 32;
 853             } else {
 854               dataOld = data - dataOld; off += dataOld; n -= dataOld;
 855               checkRsyncSumMatch(rsum, blockMask, blockLength, rsumBack,
 856                                  md5BlockLength, nextEvent);
 857             }
 858             if (matches->full()) break;
 859           }
 860         } // endif (!matches->full())
 861
 862         if (!matches->full()) {
 863           // Innermost loop - single-byte version, matches not full
 864           while (off < nextEvent) {
 865             // Roll checksum by one byte
 866             rsum.removeFront(buf[rsumBack], blockLength);
 867             rsum.addBack(buf[data]);
 868             ++data; ++off; --n;
 869             rsumBack = modAdd(rsumBack, 1, bufferLength);
 870
 871             /* Look for matches of rsum. If found, insert appropriate
 872                entry in matches list and maybe modify nextEvent. */
 873             checkRsyncSumMatch(rsum, blockMask, blockLength, rsumBack,
 874                                md5BlockLength, nextEvent);
 875
 876             /* We mustn't by accident schedule an event for a part of
 877                the image that has already been flushed out of the
 878                buffer/matched */
 879             Paranoid(matches->empty()
 880                      || matches->front()->startOffset() >= unmatchedStart);
 881           }
 882         } else {
 883           // Innermost loop - MATCHES IS FULL
 884           scanImage_mainLoop_fastForward(nextEvent, &rsum, buf, &data, &n,
 885               &rsumBack, bufferLength, blockLength, blockMask,
 886               md5BlockLength);
 887         } // endif (matches->full())
 888         if (matches->empty())
 889           debug(" %1: Event, matches empty", off);
 890         else
 891           debug(" %1: Event, matchesOff=%2", off, matches->nextEvent());
 892
 893         /* Calculate MD5 for the previous md5ChunkLength (or less if
 894            at end of match) bytes, if necessary. If the calculated
 895            checksum matches and it is the last MD5 block in the file,
 896            record a file match. If the i-th MD5Sum does not match,
 897            write the i*md5ChunkLength bytes directly to templ. */
 898         while (!matches->empty() && matches->nextEvent() == off) {
 899           size_t stillBuffered = bufferLength - n;
 900           if (stillBuffered > off) stillBuffered = off;
 901           if (checkMD5Match(buf, bufferLength, data, md5BlockLength,
 902                             nextEvent, stillBuffered, desc))
 903             return FAILURE; // no recovery possible, exit immediately
 904         }
 905
 906         Assert(matches->empty() || matches->nextEvent() > off);
 907       } // endwhile (n > 0), i.e. more unprocessed bytes left in buffer
 908
 909       if (data == bufferLength) data = 0;
 910       Assert(data < bufferLength);
 911
 912     } // endwhile (image->good()), i.e. more data left in input image
 913
 914     // End of image data - any remaining partial match is UNMATCHED
 915     if (unmatchedStart < off
 916         && unmatchedAtEnd(buf, bufferLength, data, desc)) {
 917       return FAILURE;
 918     }
 919     Assert(unmatchedStart == off);
 920
 921     zip->close();
 922   }
 923   catch (Zerror ze) {
 924     string err = subst(_("Error during compression: %1"), ze.message);
 925     reporter.error(err);
 926     try { zip->close(); } catch (Zerror zze) { }
 927     return FAILURE;
 928   }
 929
 930   imageMd5Sum.finish();
 931   desc.imageInfo(off, imageMd5Sum, cache->getBlockLen());
 932   desc.put(*templ, &templMd5Sum);
 933   if (!*templ) {
 934     string err = _("Could not write template data");
 935     reporter.error(err);
 936     return FAILURE;
 937   }
 938
 939   reporter.finished(off);
 940   return result;
 941 }
 942 //______________________________________________________________________
 943
 944 // Central function which processes the data and finds matches
 945 bool MkTemplate::run(const string& imageLeafName,
 946                      const string& templLeafName) {
 947   bool result = SUCCESS;
 948   oldAreaEnd = 0;
 949
 950   // Kick out files that are too small
 951   for (JigdoCache::iterator f = cache->begin(), e = cache->end();
 952        f != e; ++f) {
 953     if (f->size() < cache->getBlockLen()) {
 954       f->markAsDeleted(cache);
 955       continue;
 956     }
 957     fileSizeTotal += f->size();
 958     ++fileCount;
 959   }
 960
 961   // Hash table performance drops when linked lists become long => "+1"
 962   int    blockBits = bitWidth((uint32)fileCount) + 1;
 963   uint32 blockMask = (1 << blockBits) - 1;
 964   block.resize(blockMask + 1);
 965
 966   size_t max_MD5Len_blockLen =
 967       cache->getBlockLen() + 64; // +64 for Assert below
 968   if (max_MD5Len_blockLen < cache->getMD5BlockLen())
 969     max_MD5Len_blockLen = cache->getMD5BlockLen();
 970   /* Pass 1 imposes no minimum buffer length, only pass 2: Must always
 971      be able to read readAmount bytes into one buffer half in one go;
 972      must be able to start calculating an MD5Sum at a position that is
 973      blockLength bytes back in input; must be able to write out at
 974      least previous md5BlockLength bytes in case there is no match. */
 975   size_t bufferLength = 2 *
 976     (max_MD5Len_blockLen > readAmount ? max_MD5Len_blockLen : readAmount);
 977   // Avoid reading less bytes than readAmount at any time
 978   bufferLength = (bufferLength + readAmount - 1) / readAmount * readAmount;
 979
 980   Paranoid(bufferLength % readAmount == 0); // for efficiency only
 981   // Asserting this makes things easier in pass 2. Yes it is ">" not ">="
 982   Assert(cache->getMD5BlockLen() > cache->getBlockLen());
 983
 984   if (debug) {
 985     debug("Nr of files: %1 (%2 bits)", fileCount, blockBits);
 986     debug("Total bytes: %1", fileSizeTotal);
 987     debug("blockLength: %1", cache->getBlockLen());
 988     debug("md5BlockLen: %1", cache->getMD5BlockLen());
 989     debug("bufLen (kB): %1", bufferLength/1024);
 990     debug("zipQual:     %1", zipQual);
 991   }
 992
 993   MD5Sum templMd5Sum;
 994   ArrayAutoPtr<byte> bufDel(new byte[bufferLength]);
 995   byte* buf = bufDel.get();
 996
 997   prepareJigdo(); // Add [Jigdo]
 998
 999   { // Write header to template file
1000     string s = TEMPLATE_HDR; append(s, FILEFORMAT_MAJOR); s += '.';
1001     append(s, FILEFORMAT_MINOR); s += " jigdo-file/" JIGDO_VERSION;
1002     s += "\r\nSee "; s += URL; s += " for details about jigdo.\r\n\r\n";
1003     const byte* t = reinterpret_cast<const byte*>(s.data());
1004     writeBytes(*templ, t, s.size());
1005     templMd5Sum.update(t, s.size());
1006     if (!*templ) result = FAILURE;
1007   }
1008
1009   // Read input image and output parts that do not match
1010   if (scanImage(buf, bufferLength, cache->getBlockLen(), blockMask,
1011                 cache->getMD5BlockLen(), templMd5Sum)) {
1012     result = FAILURE;
1013   }
1014   cache->deallocBuffer();
1015   templMd5Sum.finish();
1016
1017   // Add [Image], (re-)add [Parts]
1018   finalizeJigdo(imageLeafName, templLeafName, templMd5Sum);
1019
1020   debug("MkTemplate::run() finished");
1021   return result;
1022 }