Move Courgette

   from src\third_party\courgette
   to   src\courgette and src\courgette\third_party

Fixed #includes

Added properties to ignore generated files:

C:\c5\src>svn pg svn:ignore courgette
courgette.xcodeproj
courgette.sln
courgette_fuzz.vcproj
courgette_lib.vcproj
courgette_minimal_tool.vcproj
courgette_tool.vcproj
courgette.vcproj
courgette_unittests.vcproj
SConstruct
courgette_fuzz.scons
courgette_lib.scons
courgette_main.scons
courgette_minimal_tool.scons
courgette.scons
courgette_tool.scons
courgette_unittests.scons


Review URL: http://codereview.chromium.org/115062

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@15692 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 828 insertions, 0 deletions

diff --git a/courgette/third_party/LICENCE b/courgette/third_party/LICENCE
new file mode 100644
index 0000000..c146b5b
--- /dev/null
+++ b/courgette/third_party/LICENCE
@@ -0,0 +1,121 @@
+BSD Protection License
+February 2002
+
+Preamble
+--------
+
+The Berkeley Software Distribution ("BSD") license has proven very effective
+over the years at allowing for a wide spread of work throughout both
+commercial and non-commercial products.  For programmers whose primary
+intention is to improve the general quality of available software, it is
+arguable that there is no better license than the BSD license, as it
+permits improvements to be used wherever they will help, without idealogical
+or metallic constraint.
+
+This is of particular value to those who produce reference implementations
+of proposed standards: The case of TCP/IP clearly illustrates that freely
+and universally available implementations leads the rapid acceptance of
+standards -- often even being used instead of a de jure standard (eg, OSI
+network models).
+
+With the rapid proliferation of software licensed under the GNU General
+Public License, however, the continued success of this role is called into
+question.  Given that the inclusion of a few lines of "GPL-tainted" work
+into a larger body of work will result in restricted distribution -- and
+given that further work will likely build upon the "tainted" portions,
+making them difficult to remove at a future date -- there are inevitable
+circumstances where authors would, in order to protect their goal of
+providing for the widespread usage of their work, wish to guard against
+such "GPL-taint".
+
+In addition, one can imagine that companies which operate by producing and
+selling (possibly closed-source) code would wish to protect themselves
+against the rise of a GPL-licensed competitor.  While under existing
+licenses this would mean not releasing their code under any form of open
+license, if a license existed under which they could incorporate any
+improvements back into their own (commercial) products then they might be
+far more willing to provide for non-closed distribution.
+
+For the above reasons, we put forth this "BSD Protection License": A
+license designed to retain the freedom granted by the BSD license to use
+licensed works in a wide variety of settings, both non-commercial and
+commercial, while protecting the work from having future contributors
+restrict that freedom.
+
+The precise terms and conditions for copying, distribution, and
+modification follow.
+
+BSD PROTECTION LICENSE
+TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION, AND MODIFICATION
+----------------------------------------------------------------
+
+0. Definitions.
+   a) "Program", below, refers to any program or work distributed under
+      the terms of this license.
+   b) A "work based on the Program", below, refers to either the Program
+      or any derivative work under copyright law.
+   c) "Modification", below, refers to the act of creating derivative works.
+   d) "You", below, refers to each licensee.
+
+1. Scope.
+   This license governs the copying, distribution, and modification of the
+   Program.  Other activities are outside the scope of this license; The
+   act of running the Program is not restricted, and the output from the
+   Program is covered only if its contents constitute a work based on the
+   Program.
+
+2. Verbatim copies.
+   You may copy and distribute verbatim copies of the Program as you
+   receive it, in any medium, provided that you conspicuously and
+   appropriately publish on each copy an appropriate copyright notice; keep
+   intact all the notices that refer to this License and to the absence of
+   any warranty; and give any other recipients of the Program a copy of this
+   License along with the Program.
+
+3. Modification and redistribution under closed license.
+   You may modify your copy or copies of the Program, and distribute
+   the resulting derivative works, provided that you meet the
+   following conditions:
+   a) The copyright notice and disclaimer on the Program must be reproduced
+      and included in the source code, documentation, and/or other materials
+      provided in a manner in which such notices are normally distributed.
+   b) The derivative work must be clearly identified as such, in order that
+      it may not be confused with the original work.
+   c) The license under which the derivative work is distributed must
+      expressly prohibit the distribution of further derivative works.
+
+4. Modification and redistribution under open license.
+   You may modify your copy or copies of the Program, and distribute
+   the resulting derivative works, provided that you meet the
+   following conditions:
+   a) The copyright notice and disclaimer on the Program must be reproduced
+      and included in the source code, documentation, and/or other materials
+      provided in a manner in which such notices are normally distributed.
+   b) You must clearly indicate the nature and date of any changes made
+      to the Program.  The full details need not necessarily be included in
+      the individual modified files, provided that each modified file is
+      clearly marked as such and instructions are included on where the
+      full details of the modifications may be found.
+   c) You must cause any work that you distribute or publish, that in whole
+      or in part contains or is derived from the Program or any part
+      thereof, to be licensed as a whole at no charge to all third
+      parties under the terms of this License.
+
+5. Implied acceptance.
+   You may not copy or distribute the Program or any derivative works except
+   as expressly provided under this license.  Consequently, any such action
+   will be taken as implied acceptance of the terms of this license.
+
+6. NO WARRANTY.
+   THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+   INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+   AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
+   THE COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
+   REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE FOR ANY DIRECT,
+   INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+   ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING, BUT
+   NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+   USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+   ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
+   TORT, EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
+   POSSIBILITY OF SUCH DAMAGES.
diff --git a/courgette/third_party/README.chromium b/courgette/third_party/README.chromium
new file mode 100644
index 0000000..d3037a1
--- /dev/null
+++ b/courgette/third_party/README.chromium
@@ -0,0 +1,23 @@
+This directory contains an extensively modified version of Colin Percival's

+bsdiff, available in its original form from:

+

+   http://www.daemonology.net/bsdiff/

+

+The basic principles of operation are best understood by reading Colin's

+unpublised paper:

+

+Colin Percival, Naive differences of executable code, http://www.daemonology.net/bsdiff/, 200

+

+The copy on this directory so extensively modified that the binary format is

+incompatible with the original and it cannot be compiled outside the Chromium

+source tree or the Courgette project.

+

+List of changes made to original code:

+  - wrapped functions in 'courgette' namespace

+  - renamed .c files to .cc

+  - added bsdiff.h header file

+  - changed the code to use streams.h from courgette

+  - changed the encoding of numbers to use the 'varint' encoding

+  - reformatted code to be closer to Google coding standards

+  - renamed variables

+  - added comments

diff --git a/courgette/third_party/bsdiff.h b/courgette/third_party/bsdiff.h
new file mode 100644
index 0000000..bf7fdec
--- /dev/null
+++ b/courgette/third_party/bsdiff.h
@@ -0,0 +1,87 @@
+/*-
+ * Copyright 2003,2004 Colin Percival
+ * All rights reserved
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted providing that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+ * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Changelog:
+ * 2005-04-26 - Define the header as a C structure, add a CRC32 checksum to
+ *              the header, and make all the types 32-bit.
+ *                --Benjamin Smedberg <benjamin@smedbergs.us>
+ * 2009-03-31 - Change to use Streams.  Move CRC code to crc.{h,cc}
+ *              Changed status to an enum, removed unused status codes.
+ *                --Stephen Adams <sra@chromium.org>
+ */
+
+#ifndef COURGETTE_BSDIFF_H_
+#define COURGETTE_BSDIFF_H_
+
+#include "base/basictypes.h"
+
+namespace courgette {
+
+enum BSDiffStatus {
+  OK = 0,
+  MEM_ERROR = 1,
+  CRC_ERROR = 2,
+  READ_ERROR = 3,
+  UNEXPECTED_ERROR = 4
+};
+
+class SourceStream;
+class SinkStream;
+
+// Creates a binary patch.
+//
+BSDiffStatus CreateBinaryPatch(SourceStream* old_stream,
+                               SourceStream* new_stream,
+                               SinkStream* patch_stream);
+
+// Applies the given patch file to a given source file. This method validates
+// the CRC of the original file stored in the patch file, before applying the
+// patch to it.
+//
+BSDiffStatus ApplyBinaryPatch(SourceStream* old_stream,
+                              SourceStream* patch_stream,
+                              SinkStream* new_stream);
+
+
+// The following declarations are common to the patch-creation and
+// patch-application code.
+
+// The patch stream starts with a MBSPatchHeader.
+typedef struct MBSPatchHeader_ {
+  char tag[8];       // Contains MBS_PATCH_HEADER_TAG
+  uint32 slen;       // Length of the file to be patched.
+  uint32 scrc32;     // CRC32 of the file to be patched.
+  uint32 dlen;       // Length of the result file.
+  uint32 cblen;      // Length of the control block in bytes.
+  uint32 difflen;    // Length of the diff block in bytes.
+  uint32 extralen;   // Length of the extra block in bytes.
+} MBSPatchHeader;
+
+// This is the value for the tag field.  Must match length exactly, not counting
+// null at end of string.
+#define MBS_PATCH_HEADER_TAG "GBSDIF42"
+
+}  // namespace
+#endif  // COURGETTE_BSDIFF_H_
diff --git a/courgette/third_party/bsdiff_apply.cc b/courgette/third_party/bsdiff_apply.cc
new file mode 100644
index 0000000..4b6a011
--- /dev/null
+++ b/courgette/third_party/bsdiff_apply.cc
@@ -0,0 +1,165 @@
+/*-
+ * Copyright 2003,2004 Colin Percival
+ * All rights reserved
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted providing that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+ * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Changelog:
+ * 2009-03-31 - Change to use Streams.  Move CRC code to crc.{h,cc}
+ *                --Stephen Adams <sra@chromium.org>
+ */
+
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "courgette/third_party/bsdiff.h"
+
+#include "courgette/crc.h"
+#include "courgette/streams.h"
+
+namespace courgette {
+
+BSDiffStatus MBS_ReadHeader(SourceStream* stream, MBSPatchHeader* header) {
+  if (!stream->Read(header->tag, sizeof(header->tag))) return READ_ERROR;
+  if (!stream->ReadVarint32(&header->slen)) return READ_ERROR;
+  if (!stream->ReadVarint32(&header->scrc32)) return READ_ERROR;
+  if (!stream->ReadVarint32(&header->dlen)) return READ_ERROR;
+  if (!stream->ReadVarint32(&header->cblen)) return READ_ERROR;
+  if (!stream->ReadVarint32(&header->difflen)) return READ_ERROR;
+  if (!stream->ReadVarint32(&header->extralen)) return READ_ERROR;
+
+  // The string will have a NUL terminator that we don't use, hence '-1'.
+  COMPILE_ASSERT(sizeof(MBS_PATCH_HEADER_TAG) - 1 == sizeof(header->tag),
+                 MBS_PATCH_HEADER_TAG_must_match_header_field_size);
+  if (memcmp(header->tag, MBS_PATCH_HEADER_TAG, 8) != 0)
+    return UNEXPECTED_ERROR;
+
+  size_t bytes_remaining = stream->Remaining();
+  if (header->cblen +
+      header->difflen +
+      header->extralen != bytes_remaining)
+    return UNEXPECTED_ERROR;
+
+  return OK;
+}
+
+BSDiffStatus MBS_ApplyPatch(const MBSPatchHeader *header,
+                            SourceStream* patch_stream,
+                            const uint8* old_start, size_t old_size,
+                            SinkStream* new_stream) {
+  const uint8* old_end = old_start + old_size;
+
+  SourceStream control_stream;
+
+  const uint8* control_start = patch_stream->Buffer();
+  if (!patch_stream->ReadSubstream(header->cblen, &control_stream))
+    return READ_ERROR;
+  if (!patch_stream->Skip(header->difflen + header->extralen))
+    return READ_ERROR;
+  if (!patch_stream->Empty())
+    return READ_ERROR;
+
+  const uint8* diff_start = control_start + header->cblen;
+  const uint8* diff_end = diff_start + header->difflen;
+  const uint8* extra_start = diff_end;
+  const uint8* extra_end = extra_start + header->extralen;
+
+  const uint8* old_position = old_start;
+  const uint8* diff_position = diff_start;
+  const uint8* extra_position = extra_start;
+
+  new_stream->Reserve(header->dlen);
+
+  while (!control_stream.Empty()) {
+    uint32 copy_count, extra_count;
+    int32 seek_adjustment;
+    if (!control_stream.ReadVarint32(&copy_count))
+      return UNEXPECTED_ERROR;
+    if (!control_stream.ReadVarint32(&extra_count))
+      return UNEXPECTED_ERROR;
+    if (!control_stream.ReadVarint32Signed(&seek_adjustment))
+      return UNEXPECTED_ERROR;
+
+#ifdef DEBUG_bsmedberg
+    printf("Applying block:  copy: %-8u extra: %-8u seek: %+i\n",
+           copy_count, extra_count, seek_adjustment);
+#endif
+    // Byte-wise arithmetically add bytes from old file to bytes from the diff
+    // block.
+    if (copy_count > static_cast<size_t>(old_end - old_position))
+      return UNEXPECTED_ERROR;
+    if (copy_count > static_cast<size_t>(diff_end - diff_position))
+      return UNEXPECTED_ERROR;
+
+    // Add together bytes from the 'old' file and the 'diff' stream.
+    for (size_t i = 0;  i < copy_count;  ++i) {
+      uint8 byte = old_position[i] + diff_position[i];
+      new_stream->Write(&byte, 1);
+    }
+    old_position += copy_count;
+    diff_position += copy_count;
+
+    // Copy bytes from the extra block.
+    if (extra_count > static_cast<size_t>(extra_end - extra_position))
+      return UNEXPECTED_ERROR;
+
+    new_stream->Write(extra_position, extra_count);
+    extra_position += extra_count;
+
+    // "seek" forwards (or backwards) in oldfile.
+    if (old_position + seek_adjustment < old_start ||
+        old_position + seek_adjustment > old_end)
+      return UNEXPECTED_ERROR;
+
+    old_position += seek_adjustment;
+  }
+
+  if (diff_position != diff_end)
+    return UNEXPECTED_ERROR;
+  if (extra_position != extra_end)
+    return UNEXPECTED_ERROR;
+
+  return OK;
+}
+
+BSDiffStatus ApplyBinaryPatch(SourceStream* old_stream,
+                              SourceStream* patch_stream,
+                              SinkStream* new_stream) {
+  MBSPatchHeader header;
+  BSDiffStatus ret = MBS_ReadHeader(patch_stream, &header);
+  if (ret != OK) return ret;
+
+  const uint8* old_start = old_stream->Buffer();
+  size_t old_size = old_stream->Remaining();
+
+  if (old_size != header.slen) return UNEXPECTED_ERROR;
+
+  if (CalculateCrc(old_start, old_size) != header.scrc32)
+    return CRC_ERROR;
+
+  MBS_ApplyPatch(&header, patch_stream, old_start, old_size, new_stream);
+
+  return OK;
+}
+
+}  // namespace
diff --git a/courgette/third_party/bsdiff_create.cc b/courgette/third_party/bsdiff_create.cc
new file mode 100644
index 0000000..d59dc21
--- /dev/null
+++ b/courgette/third_party/bsdiff_create.cc
@@ -0,0 +1,432 @@
+/*
+  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>
+*/
+
+#include "courgette/third_party/bsdiff.h"
+
+#include <stdlib.h>
+#include <algorithm>
+
+#include "base/logging.h"
+#include "base/scoped_ptr.h"
+#include "base/string_util.h"
+#include "base/time.h"
+
+#include "courgette/crc.h"
+#include "courgette/streams.h"
+
+namespace courgette {
+
+// ------------------------------------------------------------------------
+//
+// The following code is taken verbatim from 'bsdiff.c'. Please keep all the
+// code formatting and variable names.  The only changes from the original are
+// replacing tabs with spaces, indentation, and using 'const'.
+//
+// The code appears to be a rewritten version of the suffix array algorithm
+// presented in "Faster Suffix Sorting" by N. Jesper Larsson and Kunihiko
+// Sadakane, special-cased for bytes.
+
+static void
+split(int *I,int *V,int start,int len,int h)
+{
+  int i,j,k,x,tmp,jj,kk;
+
+  if(len<16) {
+    for(k=start;k<start+len;k+=j) {
+      j=1;x=V[I[k]+h];
+      for(i=1;k+i<start+len;i++) {
+        if(V[I[k+i]+h]<x) {
+          x=V[I[k+i]+h];
+          j=0;
+        };
+        if(V[I[k+i]+h]==x) {
+          tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;
+          j++;
+        };
+      };
+      for(i=0;i<j;i++) V[I[k+i]]=k+j-1;
+      if(j==1) I[k]=-1;
+    };
+    return;
+  };
+
+  x=V[I[start+len/2]+h];
+  jj=0;kk=0;
+  for(i=start;i<start+len;i++) {
+    if(V[I[i]+h]<x) jj++;
+    if(V[I[i]+h]==x) kk++;
+  };
+  jj+=start;kk+=jj;
+
+  i=start;j=0;k=0;
+  while(i<jj) {
+    if(V[I[i]+h]<x) {
+      i++;
+    } else if(V[I[i]+h]==x) {
+      tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;
+      j++;
+    } else {
+      tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;
+      k++;
+    };
+  };
+
+  while(jj+j<kk) {
+    if(V[I[jj+j]+h]==x) {
+      j++;
+    } else {
+      tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;
+      k++;
+    };
+  };
+
+  if(jj>start) split(I,V,start,jj-start,h);
+
+  for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;
+  if(jj==kk-1) I[jj]=-1;
+
+  if(start+len>kk) split(I,V,kk,start+len-kk,h);
+}
+
+static void
+qsufsort(int *I,int *V,const unsigned char *old,int oldsize)
+{
+  int buckets[256];
+  int i,h,len;
+
+  for(i=0;i<256;i++) buckets[i]=0;
+  for(i=0;i<oldsize;i++) buckets[old[i]]++;
+  for(i=1;i<256;i++) buckets[i]+=buckets[i-1];
+  for(i=255;i>0;i--) buckets[i]=buckets[i-1];
+  buckets[0]=0;
+
+  for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i;
+  I[0]=oldsize;
+  for(i=0;i<oldsize;i++) V[i]=buckets[old[i]];
+  V[oldsize]=0;
+  for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1;
+  I[0]=-1;
+
+  for(h=1;I[0]!=-(oldsize+1);h+=h) {
+    len=0;
+    for(i=0;i<oldsize+1;) {
+      if(I[i]<0) {
+        len-=I[i];
+        i-=I[i];
+      } else {
+        if(len) I[i-len]=-len;
+        len=V[I[i]]+1-i;
+        split(I,V,i,len,h);
+        i+=len;
+        len=0;
+      };
+    };
+    if(len) I[i-len]=-len;
+  };
+
+  for(i=0;i<oldsize+1;i++) I[V[i]]=i;
+}
+
+static int
+matchlen(const unsigned char *old,int oldsize,const unsigned char *newbuf,int newsize)
+{
+  int i;
+
+  for(i=0;(i<oldsize)&&(i<newsize);i++)
+    if(old[i]!=newbuf[i]) break;
+
+  return i;
+}
+
+static int
+search(int *I,const unsigned char *old,int oldsize,
+       const unsigned char *newbuf,int newsize,int st,int en,int *pos)
+{
+  int x,y;
+
+  if(en-st<2) {
+    x=matchlen(old+I[st],oldsize-I[st],newbuf,newsize);
+    y=matchlen(old+I[en],oldsize-I[en],newbuf,newsize);
+
+    if(x>y) {
+      *pos=I[st];
+      return x;
+    } else {
+      *pos=I[en];
+      return y;
+    }
+  }
+
+  x=st+(en-st)/2;
+  if(memcmp(old+I[x],newbuf,std::min(oldsize-I[x],newsize))<0) {
+    return search(I,old,oldsize,newbuf,newsize,x,en,pos);
+  } else {
+    return search(I,old,oldsize,newbuf,newsize,st,x,pos);
+  }
+}
+
+//  End of 'verbatim' code.
+// ------------------------------------------------------------------------
+
+static void WriteHeader(SinkStream* stream, MBSPatchHeader* header) {
+  stream->Write(header->tag, sizeof(header->tag));
+  stream->WriteVarint32(header->slen);
+  stream->WriteVarint32(header->scrc32);
+  stream->WriteVarint32(header->dlen);
+  stream->WriteVarint32(header->cblen);
+  stream->WriteVarint32(header->difflen);
+  stream->WriteVarint32(header->extralen);
+}
+
+BSDiffStatus CreateBinaryPatch(SourceStream* old_stream,
+                               SourceStream* new_stream,
+                               SinkStream* patch_stream)
+{
+  base::Time start_bsdiff_time = base::Time::Now();
+  LOG(INFO) << "Start bsdiff";
+  size_t initial_patch_stream_length = patch_stream->Length();
+
+  const uint8* old = old_stream->Buffer();
+  const int oldsize = old_stream->Remaining();
+
+  scoped_array<int> I(new(std::nothrow) int[oldsize + 1]);
+  scoped_array<int> V(new(std::nothrow) int[oldsize + 1]);
+  if (I == NULL || V == NULL)
+    return MEM_ERROR;
+
+  base::Time q_start_time = base::Time::Now();
+  qsufsort(I.get(), V.get(), old, oldsize);
+  LOG(INFO) << " done qsufsort "
+            << (base::Time::Now() - q_start_time).InSecondsF();
+  V.reset();
+
+  const uint8* newbuf = new_stream->Buffer();
+  const int newsize = new_stream->Remaining();
+
+  // Allocate newsize+1 bytes instead of newsize bytes to ensure that we never
+  // try to malloc(0) and get a NULL pointer.
+
+  scoped_array<uint8> diff_bytes_array(new(std::nothrow) uint8[newsize + 1]);
+  scoped_array<uint8> extra_bytes_array(new(std::nothrow) uint8[newsize + 1]);
+  if (diff_bytes_array == NULL || extra_bytes_array == NULL)
+    return MEM_ERROR;
+
+  uint8* diff_bytes = diff_bytes_array.get();
+  uint8* extra_bytes = extra_bytes_array.get();
+  int control_length = 0;
+  int diff_bytes_length = 0;
+  int diff_bytes_nonzero = 0;
+  int extra_bytes_length = 0;
+  int eblen = 0;
+
+  SinkStream control_stream;
+
+  // 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 = search(I.get(), old, oldsize,
+                            newbuf + scan, newsize - scan,
+                            0, oldsize, &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 diff_byte = newbuf[lastscan + i] - old[lastpos + i];
+        diff_bytes[diff_bytes_length + i] = diff_byte;
+        if (diff_byte)
+          ++diff_bytes_nonzero;
+      }
+      int gap = (scan - lenb) - (lastscan + lenf);
+      for (int i = 0;  i < gap;  i++)
+        extra_bytes[extra_bytes_length + i] = newbuf[lastscan + lenf + i];
+
+      diff_bytes_length += lenf;
+      extra_bytes_length += gap;
+
+      uint32 copy_count = lenf;
+      uint32 extra_count = gap;
+      int32 seek_adjustment = ((pos - lenb) - (lastpos + lenf));
+
+      control_stream.WriteVarint32(copy_count);
+      control_stream.WriteVarint32(extra_count);
+      control_stream.WriteVarint32Signed(seek_adjustment);
+      ++control_length;
+#ifdef DEBUG_bsmedberg
+      LOG(INFO) << 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;
+    }
+  }
+
+  I.reset();
+
+  MBSPatchHeader header;
+  // The string will have a null terminator that we don't use, hence '-1'.
+  COMPILE_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;
+  header.cblen    = control_stream.Length();
+  header.difflen  = diff_bytes_length;
+  header.extralen = extra_bytes_length;
+
+  WriteHeader(patch_stream, &header);
+
+  patch_stream->Append(&control_stream);
+  patch_stream->Write(diff_bytes, diff_bytes_length);
+  patch_stream->Write(extra_bytes, extra_bytes_length);
+
+  LOG(INFO) << "Control tuples: " << control_length
+            << "  copy bytes: " << diff_bytes_length
+            << "  mistakes: " << diff_bytes_nonzero
+            << "  extra bytes: " << extra_bytes_length;
+
+  LOG(INFO) << "Uncompressed bsdiff patch size "
+            << patch_stream->Length() - initial_patch_stream_length;
+
+  LOG(INFO) << "End bsdiff "
+            << (base::Time::Now() - start_bsdiff_time).InSecondsF();
+
+  return OK;
+}
+
+}  // namespace