path: root/courgette/third_party/bsdiff_create.cc

/*
  bsdiff.c -- Binary patch generator.

  Copyright 2003 Colin Percival

  For the terms under which this work may be distributed, please see
  the adjoining file "LICENSE".

  ChangeLog:
  2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit
               values throughout.
                 --Benjamin Smedberg <benjamin@smedbergs.us>
  2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table
               provided by libbz2.
                 --Darin Fisher <darin@meer.net>
  2007-11-14 - Changed to use Crc from Lzma library instead of Bzip library
                 --Rahul Kuchhal
  2009-03-31 - Change to use Streams.  Added lots of comments.
                 --Stephen Adams <sra@chromium.org>
  2010-05-26 - Use a paged array for V and I. The address space may be too
               fragmented for these big arrays to be contiguous.
                 --Stephen Adams <sra@chromium.org>
  2015-08-03 - Extract qsufsort portion to a separate file.
                 --Samuel Huang <huangs@chromium.org>
  2015-08-12 - Interface change to qsufsort search().
                 --Samuel Huang <huangs@chromium.org>
*/

#include "courgette/third_party/bsdiff.h"

#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <algorithm>

#include "base/logging.h"
#include "base/memory/scoped_ptr.h"
#include "base/strings/string_util.h"
#include "base/time/time.h"

#include "courgette/crc.h"
#include "courgette/streams.h"
#include "courgette/third_party/paged_array.h"
#include "courgette/third_party/qsufsort.h"

namespace courgette {

static CheckBool WriteHeader(SinkStream* stream, MBSPatchHeader* header) {
  bool ok = stream->Write(header->tag, sizeof(header->tag));
  ok &= stream->WriteVarint32(header->slen);
  ok &= stream->WriteVarint32(header->scrc32);
  ok &= stream->WriteVarint32(header->dlen);
  return ok;
}

BSDiffStatus CreateBinaryPatch(SourceStream* old_stream,
                               SourceStream* new_stream,
                               SinkStream* patch_stream)
{
  base::Time start_bsdiff_time = base::Time::Now();
  VLOG(1) << "Start bsdiff";
  size_t initial_patch_stream_length = patch_stream->Length();

  SinkStreamSet patch_streams;
  SinkStream* control_stream_copy_counts = patch_streams.stream(0);
  SinkStream* control_stream_extra_counts = patch_streams.stream(1);
  SinkStream* control_stream_seeks = patch_streams.stream(2);
  SinkStream* diff_skips = patch_streams.stream(3);
  SinkStream* diff_bytes = patch_streams.stream(4);
  SinkStream* extra_bytes = patch_streams.stream(5);

  const uint8_t* old = old_stream->Buffer();
  const int oldsize = static_cast<int>(old_stream->Remaining());

  uint32_t pending_diff_zeros = 0;

  PagedArray<int> I;
  PagedArray<int> V;

  if (!I.Allocate(oldsize + 1)) {
    LOG(ERROR) << "Could not allocate I[], " << ((oldsize + 1) * sizeof(int))
               << " bytes";
    return MEM_ERROR;
  }

  if (!V.Allocate(oldsize + 1)) {
    LOG(ERROR) << "Could not allocate V[], " << ((oldsize + 1) * sizeof(int))
               << " bytes";
    return MEM_ERROR;
  }

  base::Time q_start_time = base::Time::Now();
  qsuf::qsufsort<PagedArray<int>&>(I, V, old, oldsize);
  VLOG(1) << " done qsufsort "
          << (base::Time::Now() - q_start_time).InSecondsF();
  V.clear();

  const uint8_t* newbuf = new_stream->Buffer();
  const int newsize = static_cast<int>(new_stream->Remaining());

  int control_length = 0;
  int diff_bytes_length = 0;
  int diff_bytes_nonzero = 0;
  int extra_bytes_length = 0;

  // The patch format is a sequence of triples <copy,extra,seek> where 'copy' is
  // the number of bytes to copy from the old file (possibly with mistakes),
  // 'extra' is the number of bytes to copy from a stream of fresh bytes, and
  // 'seek' is an offset to move to the position to copy for the next triple.
  //
  // The invariant at the top of this loop is that we are committed to emitting
  // a triple for the part of |newbuf| surrounding a 'seed' match near
  // |lastscan|.  We are searching for a second match that will be the 'seed' of
  // the next triple.  As we scan through |newbuf|, one of four things can
  // happen at the current position |scan|:
  //
  //  1. We find a nice match that appears to be consistent with the current
  //     seed.  Continue scanning.  It is likely that this match will become
  //     part of the 'copy'.
  //
  //  2. We find match which does much better than extending the current seed
  //     old match.  Emit a triple for the current seed and take this match as
  //     the new seed for a new triple.  By 'much better' we remove 8 mismatched
  //     bytes by taking the new seed.
  //
  //  3. There is not a good match.  Continue scanning.  These bytes will likely
  //     become part of the 'extra'.
  //
  //  4. There is no match because we reached the end of the input, |newbuf|.

  // This is how the loop advances through the bytes of |newbuf|:
  //
  // ...012345678901234567890123456789...
  //    ssssssssss                      Seed at |lastscan|
  //              xxyyyxxyyxy           |scan| forward, cases (3)(x) & (1)(y)
  //                         mmmmmmmm   New match will start new seed case (2).
  //    fffffffffffffff                 |lenf| = scan forward from |lastscan|
  //                     bbbb           |lenb| = scan back from new seed |scan|.
  //    ddddddddddddddd                 Emit diff bytes for the 'copy'.
  //                   xx               Emit extra bytes.
  //                     ssssssssssss   |lastscan = scan - lenb| is new seed.
  //                                 x  Cases (1) and (3) ....


  int lastscan = 0, lastpos = 0, lastoffset = 0;

  int scan = 0;
  int match_length = 0;

  while (scan < newsize) {
    int pos = 0;
    int oldscore = 0;  // Count of how many bytes of the current match at |scan|
                       // extend the match at |lastscan|.

    scan += match_length;
    for (int scsc = scan;  scan < newsize;  ++scan) {
      match_length = qsuf::search<PagedArray<int>&>(
          I, old, oldsize, newbuf + scan, newsize - scan, &pos);

      for ( ; scsc < scan + match_length ; scsc++)
        if ((scsc + lastoffset < oldsize) &&
            (old[scsc + lastoffset] == newbuf[scsc]))
          oldscore++;

      if ((match_length == oldscore) && (match_length != 0))
        break;  // Good continuing match, case (1)
      if (match_length > oldscore + 8)
        break;  // New seed match, case (2)

      if ((scan + lastoffset < oldsize) &&
          (old[scan + lastoffset] == newbuf[scan]))
        oldscore--;
      // Case (3) continues in this loop until we fall out of the loop (4).
    }

    if ((match_length != oldscore) || (scan == newsize)) {  // Cases (2) and (4)
      // This next chunk of code finds the boundary between the bytes to be
      // copied as part of the current triple, and the bytes to be copied as
      // part of the next triple.  The |lastscan| match is extended forwards as
      // far as possible provided doing to does not add too many mistakes.  The
      // |scan| match is extended backwards in a similar way.

      // Extend the current match (if any) backwards.  |lenb| is the maximal
      // extension for which less than half the byte positions in the extension
      // are wrong.
      int lenb = 0;
      if (scan < newsize) {  // i.e. not case (4); there is a match to extend.
        int score = 0, Sb = 0;
        for (int i = 1;  (scan >= lastscan + i) && (pos >= i);  i++) {
          if (old[pos - i] == newbuf[scan - i]) score++;
          if (score*2 - i > Sb*2 - lenb) { Sb = score; lenb = i; }
        }
      }

      // Extend the lastscan match forward; |lenf| is the maximal extension for
      // which less than half of the byte positions in entire lastscan match are
      // wrong.  There is a subtle point here: |lastscan| points to before the
      // seed match by |lenb| bytes from the previous iteration.  This is why
      // the loop measures the total number of mistakes in the the match, not
      // just the from the match.
      int lenf = 0;
      {
        int score = 0, Sf = 0;
        for (int i = 0;  (lastscan + i < scan) && (lastpos + i < oldsize);  ) {
          if (old[lastpos + i] == newbuf[lastscan + i]) score++;
          i++;
          if (score*2 - i > Sf*2 - lenf) { Sf = score; lenf = i; }
        }
      }

      // If the extended scans overlap, pick a position in the overlap region
      // that maximizes the exact matching bytes.
      if (lastscan + lenf > scan - lenb) {
        int overlap = (lastscan + lenf) - (scan - lenb);
        int score = 0;
        int Ss = 0, lens = 0;
        for (int i = 0;  i < overlap;  i++) {
          if (newbuf[lastscan + lenf - overlap + i] ==
              old[lastpos + lenf - overlap + i]) score++;
          if (newbuf[scan - lenb + i] ==  old[pos - lenb + i]) score--;
          if (score > Ss) { Ss = score; lens = i + 1; }
        }

        lenf += lens - overlap;
        lenb -= lens;
      };

      for (int i = 0;  i < lenf;  i++) {
        uint8_t diff_byte = newbuf[lastscan + i] - old[lastpos + i];
        if (diff_byte) {
          ++diff_bytes_nonzero;
          if (!diff_skips->WriteVarint32(pending_diff_zeros))
            return MEM_ERROR;
          pending_diff_zeros = 0;
          if (!diff_bytes->Write(&diff_byte, 1))
            return MEM_ERROR;
        } else {
          ++pending_diff_zeros;
        }
      }
      int gap = (scan - lenb) - (lastscan + lenf);
      for (int i = 0;  i < gap;  i++) {
        if (!extra_bytes->Write(&newbuf[lastscan + lenf + i], 1))
          return MEM_ERROR;
      }

      diff_bytes_length += lenf;
      extra_bytes_length += gap;

      uint32_t copy_count = lenf;
      uint32_t extra_count = gap;
      int32_t seek_adjustment = ((pos - lenb) - (lastpos + lenf));

      if (!control_stream_copy_counts->WriteVarint32(copy_count) ||
          !control_stream_extra_counts->WriteVarint32(extra_count) ||
          !control_stream_seeks->WriteVarint32Signed(seek_adjustment)) {
        return MEM_ERROR;
      }

      ++control_length;
#ifdef DEBUG_bsmedberg
      VLOG(1) << StringPrintf("Writing a block:  copy: %-8u extra: %-8u seek: "
                              "%+-9d", copy_count, extra_count,
                              seek_adjustment);
#endif

      lastscan = scan - lenb;   // Include the backward extension in seed.
      lastpos = pos - lenb;     //  ditto.
      lastoffset = lastpos - lastscan;
    }
  }

  if (!diff_skips->WriteVarint32(pending_diff_zeros))
    return MEM_ERROR;

  I.clear();

  MBSPatchHeader header;
  // The string will have a null terminator that we don't use, hence '-1'.
  static_assert(sizeof(MBS_PATCH_HEADER_TAG) - 1 == sizeof(header.tag),
                "MBS_PATCH_HEADER_TAG must match header field size");
  memcpy(header.tag, MBS_PATCH_HEADER_TAG, sizeof(header.tag));
  header.slen     = oldsize;
  header.scrc32   = CalculateCrc(old, oldsize);
  header.dlen     = newsize;

  if (!WriteHeader(patch_stream, &header))
    return MEM_ERROR;

  size_t diff_skips_length = diff_skips->Length();
  if (!patch_streams.CopyTo(patch_stream))
    return MEM_ERROR;

  VLOG(1) << "Control tuples: " << control_length
          << "  copy bytes: " << diff_bytes_length
          << "  mistakes: " << diff_bytes_nonzero
          << "  (skips: " << diff_skips_length << ")"
          << "  extra bytes: " << extra_bytes_length
          << "\nUncompressed bsdiff patch size "
          << patch_stream->Length() - initial_patch_stream_length
          << "\nEnd bsdiff "
          << (base::Time::Now() - start_bsdiff_time).InSecondsF();

  return OK;
}

}  // namespace courgette