Zucchini equivalence map consists of items. Denote these as {src[i], dst[i], len[i]}, where:
src[i] = "old" offset,
dst[i] = "new" offset,
len[i] = length of range.
Currently patches store src and dst using delta-encoding, i.e.:
[src[0], src[1] - src[0], src[2] - src[1], ...],
[dst[0], dst[1] - dst[0], dst[2] - dst[1], ...].
However, the following constraints are imposed on the equivalence map:
- Equivalence are sorted by "new" offsets.
- "New" ranges never overlap.
Together these mean src[i + 1] >= src[i] + len[i], and this gives rise to potential patch optimization: We can store
[dst[0], dst[1] - (dst[0] - len[0]), dst[2] - (dst[1] - len[1]), ...].
The results are always non-negative, but this results in values that are smaller than delta-encoding raw dst[].
The experiment can be conducted by operating directly on patch (using zucchini.js).
Comment 1 by hua...@chromium.org
, Apr 26 2018