generate version 2 blockimgdiff files
Generate version 2 of the block_image_update transfer list format.
This improves patch size by a different strategy for dealing with
out-of-order transfers. If transfer A must be done before transfer B
due to B overwriting A's source but we want to do B before A, we
resolve the conflict by:
- before B is executed, we save ("stash") the overlapping region (ie
the blocks B will overwrite that A wants to read)
- when A is executed, it will read those parts of source data from
the stash rather than from the image.
This reverses the ordering constraint; with these additions now B
*must* go before A. The implementation of the stash is left up to the
code that executes the transfer list to apply the patch; it could hold
stashed data in RAM or on a scratch disk such as /cache, if available.
The code retains the ability to build a version 1 block image patch;
it's needed for processing older target-files.
Change-Id: Ia9aa0bd45d5dc3ef7c5835e483b1b2ead10135fe
diff --git a/tools/releasetools/rangelib.py b/tools/releasetools/rangelib.py
index 8a85d2d..b83396c 100644
--- a/tools/releasetools/rangelib.py
+++ b/tools/releasetools/rangelib.py
@@ -173,3 +173,39 @@
else:
total -= p
return total
+
+ def map_within(self, other):
+ """'other' should be a subset of 'self'. Returns a RangeSet
+ representing what 'other' would get translated to if the integers
+ of 'self' were translated down to be contiguous starting at zero.
+
+ >>> RangeSet.parse("0-9").map_within(RangeSet.parse("3-4")).to_string()
+ '3-4'
+ >>> RangeSet.parse("10-19").map_within(RangeSet.parse("13-14")).to_string()
+ '3-4'
+ >>> RangeSet.parse("10-19 30-39").map_within(
+ ... RangeSet.parse("17-19 30-32")).to_string()
+ '7-12'
+ >>> RangeSet.parse("10-19 30-39").map_within(
+ ... RangeSet.parse("12-13 17-19 30-32")).to_string()
+ '2-3 7-12'
+ """
+
+ out = []
+ offset = 0
+ start = None
+ for p, d in heapq.merge(zip(self.data, itertools.cycle((-5, +5))),
+ zip(other.data, itertools.cycle((-1, +1)))):
+ if d == -5:
+ start = p
+ elif d == +5:
+ offset += p-start
+ start = None
+ else:
+ out.append(offset + p - start)
+ return RangeSet(data=out)
+
+
+if __name__ == "__main__":
+ import doctest
+ doctest.testmod()