Looking at bsdiff's comment, original author want to generate a diff
patch only if diff is no smaller than 8 bytes. Actual code only only
permits the diff to be generated if diff > 8 bytes.
Partners reported a pair of problematic files where BSDIFF takes more
than 10 hours(input file is only ~80MB). After applying this patch,
bsdiff takes ~1 minute.
To make sure this patch does not harm patch size for non-pathological
cases, I tested multiple pixel OTAs. Total OTA size increased by just
0.002% . Basically negligible.
Test: Multiple pixle OTAs
Bug: 285271992
Change-Id: I2a9b52939f8d17ea48dc2908942b2cc21cbe4e09
|lastoffset| and |oldsize| doesn't change in this loop, no point keep
incrementing |scsc| and comparing.
bsdiff is about 2% faster with no change on the patch content.
Bug: 77817425
Test: bsdiff_unittest
Change-Id: Ie6a5ddc4b8805ed76c9c626fa75010617b7975ef
The minimum required match length plays an important role in the
current algorithm. This algorithm requires that the current match
has at least 8 mismatches over a region where we find a new match,
therefore imposing a minimum match length of at least 8 bytes.
This patch allows to increase this minium value to avoid using small
matches that only match a very small region. A larger value can
improve the patch size, depending on the data, but a too large value
will cause the algorithm to miss matches that were otherwise benefical.
Bug: 73107113
Test: Added unittests. Ran it with different minlen values.
Change-Id: Iac594fc1cd7ecd5cfdc676bdb6ebe7c626de6dcd
Add a parser of format, type and quality in the bsdiff main function.
This allow the bsdiff binary to choose between the BSDFF40|BSDF2 patch
format and compress the patch with desired algorithms.
Bug: 34220646
Test: unittest pass; generate brotli compressed patches with bsdiff
binary
Change-Id: Ia4f7941e4eca7e6047e2749315127d1cf4a988ee
Add a new BSDF2 format that allows compression of ctrl/diff/extra streams
with different algorithms. The compression algorithm supported for now is
bz2 and brotli. This new format is similar to the legacy "BSDIFF40" format
except for the magic headers.
File format:
0 8 magic header
8 8 X
16 8 Y
24 8 new_file_size
32 X compressed control block
32+X Y compressed diff block
32+X+Y ??? compressed extra block
The magic header for BSDF2 format:
0 5 BSDF2
5 1 compressed type for control stream
6 1 compressed type for diff stream
7 1 compressed type for extra stream
Bug: 34220646
Test: unittest pass
Change-Id: I6eb0867e88476dbc4a4b7be609783f8c8a0a41cd
Add a new compressor interface; and the brotli compressor which is
similar to the existing bz2 one.
Also add a new CompressorType argument to PatchWriter's init function;
this allows us to choose the right compressor based on the input option
in the future.
Bug: 34220646
Test: Run bsdiff/bspatch with brotli compressor/decompressor over a
list of files from angler's system image. Make succeeds.
Change-Id: Id9a3db2d7d051dcb751a1fc362f4c3b9226e878b
Most patch formats include the size of the new file in the header.
To help streaming the patch to disk while generating it, this CL
passes the size of the new file to the patch writer on initialization.
To do this, we also move the Init() call to the patch writer to the
DiffEncoder, which makes more sense since the Close() call is also made
from the DiffEnconder.
Bug: None
Test: Updated tests to check for this value.
Change-Id: Idfaedbd492d68ab6e6cb2c1cb3883947f068c3aa
The original function used to generate a patch from two files is no
longer used elsewhere so this patch removes it in favour of the newer
version that takes the streams from memory buffers and uses a patch
writer to generate the patch.
Bug: None.
Test: Ran `bsdiff` manually, verified bspatch applied correctly.
Change-Id: I17aac1d3dd405d733ff6dc35abe8e683adea0d4f
The suffix array is used to search for strings from the new file in the
old file. The size of each element of the suffix array must be big
enough to hold the length of the old file. In most of the cases we use,
if not all of them, the old file is smaller than 2 GiB, which allows to
use 32-bit integers for the suffix array.
The previous code decided whether to use 64-bit or 32-bit integers
based on the large-file surpport, even in 32-bit computers architectures
which would not work in those cases; and would also use twice as much
memory when constructing the suffix array of inputs smaller than 2 GiB.
This patch selects the suffix array size based on the input size,
effectively using half the memory in the most common case. This also
improves the runtime performance due to lower cache pressure.
As a side effect, this patch hides the suffix array implementation
details from the public interface. This removes the limitation where
the caller of libbsdiff and libbsdiff needed to be compiled with the
same large-file support flags; and also hides the dependency on
libdivsufsort from the public interface.
While doing so, instead of re-implementing the suffix array search
algorithm (which had a history of bugs and corner cases) we re-use the
one from libdivsufsort, adapted to the bsdiff algorithm use-case.
The result is about 40% faster when diffing 10MiB files, and the patch
size is within 0.1%, due to differences in the position selected
whenever more than one match is available.
Bug: 34220646
Test: Added unittests for the suffix array.
Change-Id: Ib9dc85a83bbf10157a3937c5687e5663ab0d20d5
The recently introduced PatchWriterInterface had both the patch file
format logic and the diff/extra streams selection from the control
entries. While this simplifies the bsdiff main algorithm and makes
invalid usages of the BsdiffPatchWriter evident, writing alternative
PatchWriterInterface classes required to replicate the diff/extra
stream selection logic.
This patch splits out the diff/extra stream generation and all the
checks around those to a new helper class DiffEncoder. The public
interface PatchWriterInterface now has two methods to accept the diff
and extra stream data, and does not compute them.
Bug: 34220646
Test: Added unittests. Ran bsdiff on some pairs of files obtaining the same result as before.
Change-Id: I5f303c06f1e10910eb00dcfda38c6811977a91cf
Split the unittest logic between bsdiff() function and the PatchWriter.
This patch now tests individually the PatchWriter logic that writes to
disk and the bsdiff() logic to create patches in the same very simple
cases.
We also update the Android.bp file to only pass -DBSDIFF_TARGET_UNITTEST
when building for the target.
Bug: 34220646
Test: ran unittests.
Change-Id: I9350157ee4a0b5a617f44bb187bd7652f6d6f017
Currently, all bsdiff() functions take a filename for the patch, which
is called with a temporary file in all cases. To help expose an
interface that allows to write bsdiff patches in different formats (for
example, changing the compressor and header format) we expose the
PatchWriterInterface class in the public interface so callers can use
a different one or define their own to help experimenting with bsdiff
enconding improvements.
Bug: 34220646
Test: make bsdiff and update_engine; ran bsdiff_unittest
Change-Id: Ie450b2790137665bc033cb36d037171090b18a4b
This prevents accidentally including a header file from another project
that happens to have the same name.
Test: `make checkbuild`; emerge-${BOARD} bsdiff
Bug: None
Change-Id: I8af132ed388738c30a8e3d7434de70b1e9d2f924
bsdiff.cc had code to handle both the sub-streams compression and the
patch format. This CL moves the patch file format logic to a new class
in a separated file, and the bzip2 compression to another class. This
allows to replace the core bsdiff logic separatedly from the patch
format.
There are no changes to the functionality of bsdiff and the generated
patches. The code does a bit more of memcpy() since it doesn't write
the control stream to disk as it goes.
Bug: 34220646
Test: Ran bsdiff and compared results with previous version.
Change-Id: Ibdc1482e98cbd370cbed677c326008e19a217ef8
The Makefile didn't build libbspatch and libbsdiff. This patch includes
those libraries in the Makefile and moves the header files exposed by
those to an include/bsdiff subdirectory following the Android
convention so calling program can include "bsdiff/bspatch.h" avoiding
any collision with other libraries.
The Android.mk is updated to export the new include path while keeping
the old style until calling programs are updated.
The new Makefile allows Chromium OS to build the new libraries.
Bug: None
Test: FEATURES=test emerge-link bsdiff; sudo emerge bsdiff
Test: mmma external/bsdiff
Change-Id: I2ea9251eb224e9418fe236e4c4c9c5621853f590
If the same old data is passed to bsdiff repeatedly, allow caller to
cache the suffix array, this is used by imgdiff in zip mode.
Bug: 34281147
Test: =time -v imgdiff -z Chrome-ORF74B.apk Chrome-ORF76B.apk Chrome.imgdiff
Change-Id: I0a69fc2d0b1a0d5791f78d0380df957981318daa
The bug was introduced when we replaced qsufsort with divsufsort, the
implementation of qsufsort in bsdiff will set I[oldsize] for some reason,
and later on search() might access I[oldsize] in a corner case. But
divsufsort will only set I[0...oldsize-1] which is WAI, and now I[oldsize]
will be random.
The search() function is basically a binary search, and the end should
be oldsize-1 so that it will never access I[oldsize].
Interestingly, it will only segfault when used in imgdiff, even if I
extract the same old data and new data passed to bsdiff() and call bsdiff
binary with the files, segfault disappears, probably because imgdiff did
many malloc and free before calling bsdiff and the memory already contains
random data, whereas in bsdiff binary that is always 0. That's probably
why we did not encounter this bug in Chrome OS.
Bug: 28631841
Test: `imgdiff boot.img recovery.img recovery_from_boot.p` from shamu build
Change-Id: If10ec64b125131b348444364626307d379c2b8ba
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
Kelvin Zhang