The original bsdiff and bspatch source files are governed by the
BSD-style license with Colin Percival's copyright. The new files added
by the Chromium OS project are licensed under the BSD-style Chromium OS
license.

This patch reflects this situation adding the "LICENSE" file referenced
from the Chromium OS license header with both licenses while keeping
the "NOTICE" file pointing to it.

Bug: None
Change-Id: Ib12712dd68664879358280618f4cc56164cbe514

The unitests were compiled in the Makefile but not on Android. This
patch builds the unittests for the host on Android.

Bug: 24478450
Test: mmma external/bsdiff && out/host/linux-x86/bin/bsdiff_unittest

Change-Id: Ib9f70e57273e585f31b46068d29b277aaae611eb

With the implementation of the ExtentsFile, we can now use the
FileInterface from bspatch to read and write files. This patch
re-enables the extent argument support and adds unittests for the
argument parsing.

Bug: 24478450
Test: make all test && ./unittest

Change-Id: If6837f250df10c24d3ff96f7ad8f0e0d98126788

This patch attempts to uniform the format on bspatch before we land
further changes there.

Bug: 24478450
Test: make all test && ./unittest

Change-Id: I45ec3d45ab4b081bddef1ac7f5df35ac7e6e554c

Implemented a method to get the size of the FileInterface object
directly.

Bug: 24478450
Change-Id: I9aab80b33cc554551ce79bfee52e94e8e04775db
Test: make all test && ./unittest

This patch moves the exfile.cc implementation to a C++ class with an
abstract interface of a file. The implementation of exfile.cc, renamed
to extents_file.cc, now uses C++ STL classes and has unittests to test
its core functionality.

Bug: 24478450
Test: Unittests added. make all test -j5 && ./unittests

Change-Id: I8d8f07150ad2ea465c55b5178ca9fbab49185eea

To help refactoring the FILE* access behind an interface and better
integrate with unittest code, this patch moves the C sources to C++.
Minor changes to make this conform to C++ were included.

Bug: 24478450
Test: `make all test && ./unittests`; mm

Change-Id: I27d7fb0660efc18ea0cb84ff544c9dd9c4803050

The source code has mixed style guides. The new introduced extents and
exfile modules had 4-spaces indents but one tab instead of two indents
probably due to bad editor cofiguration. These modules were first
introduced as local patches to the .ebuild file but later merged in the
git repository.

This patch fixes the style guide on all the files added by Chromium OS
(all the source files execpt bsdiff.c and bspatch.c). The remaining
file should be converted over to the Chromium style guide when parts
of it are modified. A .clang-format file is included in this patch to
help with that process.

Bug: None
Test: `make all test && ./unittests`; mm

Change-Id: Ief3c557cb35aae67871a5ccde8486af651b84a35

Bspatch uses fopencookie(3) and some other GNU extensions not
implemented on mac and some targets. This patch fixes the build by
disabling the code using those features, that will be re-enabled on a
follow up CL.

Change-Id: Ibc7975b3ab6b4afa7c7ac1ee445173973a2a570a
Test: `mmma external/bsdiff` on the target and on mac.

The merged CLs from Chromium OS include a new dependency in
libdivsufsort and split some source files. This patch includes changes
to the Android.mk to build with the new CLs.

Bug: 24332905
Change-Id: Id7cc128bc7527e2c1eadc2319dd249e5746a903f
Test: mmm external/bsdiff; make otatools

In last CL we introduced a bug where the old_filename was mixed with
the new_filename. This obvious bug didn't trigger any failure because
update_engine uses always the same name (/dev/fd/N) for both old and
new files since the files are applied in place, and also because bsdiff
doesn't have any unittest... yet.

BUG=None
TEST=sudo emerge bsdiff; tested bspatch manually.
TEST=cros flash an image with payload minor_version=2, which uses different old and new files.

Change-Id: I8b5715cd422612b9bbf7eaf3d4d3813c659fd10c

bsdiff and bspatch are in C and had no unittest. This patch keeps
those programs as C code, but adds the C++ gtest unittest framework
to allow testing them. Two simple unittests added to validate that the
unittests work.

BUG=None
TEST=make test; ./unittests

Change-Id: I8bca6b0c6bc5d5880464183d50a602c9886d20d0

The local README.chromium includes a description of the project and
release version it is based on.

BUG=chromium:474769
TEST=None

Change-Id: I5f8123984c820c64e7cbe5a9cc1642061aa2ed1c

BUG=None
TEST=git ls-files -i --exclude-standard

Change-Id: Ic64b5cec6cb35aa8893db0aeb8e7c73bef93bcfc

Update Engine's delta_generator requires the bsdiff binary to be
present on the host when the au-generator.zip is created with the
generate_au_zip.py script. This .zip file will later run on the
builders. Nevertheless, the bsdiff binary is not required on the
ChromeOS devices, only bspatch is.

This patch removes the bsdiff and its dependencies from the device
saving a few KB.

BUG=chromium:372644
TEST=Manual test:
TEST=emerge-link --unmerge libdivsufsort && emerge-link bsdiff # Both work, bsdiff not present on link
TEST=sudo emerge bsdiff # Works, bsdiff present on the host.

Change-Id: Ie2823c796185d616523fe8bf79a7c4c91fa3a0c0
Reviewed-on: https://chromium-review.googlesource.com/199466


Reviewed-by: Mike Frysinger <vapier@chromium.org>
Reviewed-by: Don Garrett <dgarrett@chromium.org>
Commit-Queue: Alex Deymo <deymo@chromium.org>
Tested-by: Alex Deymo <deymo@chromium.org>

Previously, bspatch used to read the whole content of a file to be
patched into a memory buffer, only to copy this data while generating
the new file content, which is written to a second buffer.  The said
read buffer entails an unnecessary memory allocation requirement,
especially since it's being indexed almost linearly.  This behavior was
further extended to support extents (i.e. a list of <offset, length>
pairs), which are used extensively during Chrome OS updates.

This change introduces extent files, which let users open files through
a layer of extents as ordinary glibc file handles. This in turn allows
us to easily convert reads from a memory buffer into direct reads from
an extent file. Extent files are buffered on the outer level (done for
us by glibc), but otherwise use a system file descriptor for the
underlying I/O; this proved to be the most efficient combination when
applying actual update payloads. Since we are reading a single byte at
a time using fread(2), and since the program is decidedly
single-threaded, we shift to using _unlocked variants, which appear to
reduce the total update time significantly without otherwise affecting
memory/CPU footprint.

We expect this to cut bspatch's memory usage by nearly one half.  Note
that in general it is possible to use the same abstraction for
implementing direct writing to the target file; however, due to the way
we implement delta updates, there is risk that such writes might clobber
the read data, and so further support is needed to mark safe operations
(i.e. no read/write dependencies) as such.

This CL obsoletes the previous ebuild patch for handling extent
arguments, which is therefore removed. It also (i) gets rid of logic for
special handling of /dev/fd filenames, which is deemed redundant; (ii)
fixes the Makefile (via a separate patch) and changes the ebuild to use
it, for uniformity; (iii) updates the ebuild to EAPI version 4; (iv)
sets -Wall -Werror and fixes eliminates a warning due to bsdiff.c; (v)
enhances man pages for both bsdiff/bspatch.

BUG=chromium:229705
TEST=Passes update engine unittests with new bspatch
TEST=delta payload with BSDIFF operations updates correctly on x86-alex

Change-Id: I4bb4afa42e43279048093e7a7f0ef96406b0c9e0
Reviewed-on: https://gerrit.chromium.org/gerrit/49595


Reviewed-by: Gilad Arnold <garnold@chromium.org>
Tested-by: Gilad Arnold <garnold@chromium.org>
Commit-Queue: Gilad Arnold <garnold@chromium.org>

Modify bsdiff to better handle the case where files differ by <8 bytes
in some regions, not limitting this case to linear traversal.

BUG=chromium-os:28552
TEST=Manual bsdiff of problematic files, update engine unit tests

Change-Id: I5b796977fc0e81d08b2e22abae48ae9e7dd2dba6
Reviewed-on: https://gerrit.chromium.org/gerrit/19270


Reviewed-by: Don Garrett <dgarrett@chromium.org>
Commit-Ready: Thieu Le <thieule@chromium.org>
Tested-by: Thieu Le <thieule@chromium.org>

BUG=chrome-os-partner:6056
TEST=Manually create diff of obfuscated lib, apply diff and verify same
as target file, run cros_generate_update_payload to make sure it still
works

Change-Id: Ib0a68789fdf725d126467cbd86ca7ae28817b06c
Reviewed-on: http://gerrit.chromium.org/gerrit/8179


Reviewed-by: Andrew de los Reyes <adlr@chromium.org>
Commit-Ready: Thieu Le <thieule@chromium.org>
Tested-by: Thieu Le <thieule@chromium.org>

bsdiff does not properly handle the case where there is a large block of
data in the new file that only differs from the old file by less than 8
bytes.  This causes bsdiff to continue searching through the files one
byte at a time and at each byte, re-compare the same large block of data
which leads to excessively long run times.  This fix checks for this
edge condition and breaks out of the search loop early.  This retains
the size efficiency of the patch file for most binaries while preserving
the runtime efficiency for files that fall into this category.

BUG=chromium-os:16377
TEST=unit tests, manually applied update, bsdiff known problematic files

Change-Id: If84ad928603c71297f4d0977405893345f39d5c3
Reviewed-on: http://gerrit.chromium.org/gerrit/2640


Reviewed-by: Andrew de los Reyes <adlr@chromium.org>
Tested-by: Thieu Le <thieule@chromium.org>

Divsufsort is more efficient and addresses the problem of bsdiff hanging
on certain files.

Here are some measurements of the delta diff generator comparing the two
suffix sort alogrithms.

qsufsort:
real	4m40.670s
user	4m19.170s
sys	0m6.400s

divsufsort:
real	3m29.426s
user	3m7.890s
sys	0m6.630s

BUG=chrome-os-partner:3785
TEST=Unit tests, created + applied delta and ensured the system updated
properly, manually ran bsdiff against problematic files to ensure it
completed in a timely manner

Change-Id: Ic5d4215a2de5a1845d88fad5c466f1adf0eaccee
Reviewed-on: http://gerrit.chromium.org/gerrit/1080


Reviewed-by: Darin Petkov <petkov@chromium.org>
Tested-by: Thieu Le <thieule@chromium.org>

The updater, in an attempt to keep bspatch from open/closing the raw
block device frequently, passes a file descriptor and a path of
/dev/fd/(some number) as the path. This patch causes bspatch to
recognize that magic file path and not call open/close.

This dramatically reduces resource usage on client machines performing
delta updates.

BUG=7636
TEST=Installed delta on device

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

BUG=chromium-os:5364
TEST=tested doing a delta update on a device

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

Portage automatically uses an overlay ebuild of the same name, so it suffices to copy and modify the original ebuild.

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

Change-Id: I27caa31a00a1dc92bd117fe24d9cb7c8cfbda033

Patches with control data tuples with negative numbers in the first
and/or second can cause bspatch to write to arbitrary locations in the
heap.

Change-Id: Ibfccf222dbc24328ce7593476da36212d9052e12

Change-Id: I9bceb790b67e3197a2f1470041e3c268caa1ef58

Bug: 5010576

Change-Id: Iff124dd7b79a5b338ddadbcfc0a67d09b151bcae

Change-Id: I3944d75f64a31479d843116c69a4b1a6ad96b73b