[Epic 4G Android Development] LiberatorUSA:
Courgette

Turns out that Red Bend uses a delta compression technique for which they filed a patent. They already filed a lawsuit about this see links below:

http://www.whda.com/blog/wp-content/uploads/2011/04/2011.3.31-MO-Red-Bend-v.-Googlepdf1.pdf

http://lists.freebsd.org/pipermail/freebsd-hubs/2010-March/002178.html

The complaint is against Chromium's Courgette update tooling which they claim infringes on their patent. This in my mind means that at minimum their algorithm does something similar which means it is a good place to look for hints on how one goes about constructing such a delta file.

Going through the legal documents it seems clear that bsdiff itself does not infringe on their patent but now that an additional stage was added to the compression/decompression process as described suddenly there is mention of patent infringement by Courgette. This to me suggests this extra stage comes close to what redbend does.

http://www.chromium.org/developers/design-documents/software-updates-courgette

Note that their patent is no doubt based on their algorithm (I haven't checked) and not the file format. So it should in theory be possible to produce a compatible file without having to use their compression algorithm. typically the compression algorithm is a lot more complex then the decompression algorithm since it has to look for maximum compression. We don't care about that since we just need a delta the software will accept even if its inefficient.

Long story short this could be a good hint and need not be a deterrent.

Having read the Courgette article I see that what is described also resembles to some extend the proposal in a document I posted earlier. Reading this you would think it is a daunting task to write tooling which performs all the steps described. But keeping in mind our objective that is not necessary.

If you look at this section of the algorithm:

For optimal compression you would need to perform the process outlined which handles different data differently by trying out what the most optimal compression method is (assembly mapping technique described vs standard bin diff) and then simply use that answer as part of your delta meta data with the optimal delta data itself.

Now suppose we ignore the optimization possibilities and we just claim (in the delta file) that the simplest compression method was the best possible compression method then you could imagine being able to generate a (albeit rather large) delta file which the firmware will happily swallow.

View Courgette source:

http://src.chromium.org/viewvc/chrome/trunk/src/courgette/

Download source using SVN:

http://src.chromium.org/svn/trunk/src/courgette

From Courgette code:

As for the 'Kind' mentioned,.. here is the enum:

enum Kind { WIN32_X86_WITH_CODE, WIN32_NOCODE };

I was going over their x86 specific code which is interesting and all but it is irrelevant for what we want to do I think. What we want is to figure out how they signal the difference between ARM assembly code and non-code. If we can figure out what in the delta file format determines this we can claim that all changes we wish to apply are of the non-code type which would be the simpler or at least more standardized compression method.

I highly doubt they tried to come up with a way to better compress a jpeg or png. Those formats already do a good job at compression themselves. It is in the assembly sections where the real gains are to be made.

The modem is no doubt almost entirely assembly code but I'm guessing the compression/decompression code is the same regardless of what partition is written to. Thus we can fool said code into thinking our update is all non-code for which we can more easily reverse-engineer a delta compression algorithm

In order to use an algorithm like this you cannot just take source_modem.bin and destination_modem.bin and treat it as a single file. You have to understand the filesystem employed and thus know which files are actually inside that bin file. You also have to know the type of those files at least to the extent of the different transformation types you support with your algorithm.