This utility allows a directory of binary files to be selectively bsdiff-encoded, and reconstructed on the fly.
The first consumer of this tool is ChromeOS cellular team, where modem firmware is stored in binary formats.
Patch storage can provide benefits in several scenarios:
bsdiff allows efficient patches to be generated between two similar binary files. To try and identify files that are similar and address the above use-cases, the following greedy algorithm will process all files present to determine which must be shipped in a full copy, and which can use existing full copies to produce a diff.
As it is unintuitive and arbitrary to take diffs of files with very different sizes, a preprocessing step gathers the files into clusters, where files whose sizes are within 20% of each other will be clustered together. Each cluster can then be processed independently with the next steps.
All modem firmware is put into a compressed squashfs before being installed on the ChromeOS device. For each file we process, we first compress it to get a baseline size. If the following patch generation attempts don‘t result in sizes smaller than compression, we won’t use a patch.
First priority, we attempt patch generation between files with matching filename and depth. Clearly, the following file pairs are for the same purpose:
`fm101/19500.0000.00.01.01.52/NON-HLOS.ubi` `fm101/19500.0000.00.01.02.73/NON-HLOS.ubi` `fm101/19500.0000.00.01.01.52/NON-HLOS.ubi` `rw101/19512.0000.00.11.02.01/NON-HLOS.ubi`
`fm350/OP_OTA_000.042.img` `fm350/OP_OTA_000.043.img`