CPatch v3: Instruction Set Aware Patches

TLDR - Median Patch Size of 1.4%

Infuse-IoT's binary diff firmware update tool has just received some major improvements:

Details

One of Infuse-IoT's great features is the ability to perform device firmware updates (DFU) without needing to send the entire new firmware image to the device. Instead, we enable constructing a smaller patch file which contains a set of instructions that the running application can use to construct the new firmware image, using the current firmware as a base.

This approach was already resulting in huge data-volume and energy-consumption wins with the original patch scheme, but recent improvements really surprised us. While the median patch size was already only 9.8% (49 kB for a 500 kB image), our new instruction-set-aware encoding has brought that down to just 1.4% (7 kB for a 500 kB image). And because that value is a median, half of all patches are even smaller than that!

With firmware updates that small, suddenly performing a fleet upgrade over NB-IoT NTN or LoRaWAN is becoming practical for real-world deployments.

For more details about the design goals and original implementation of CPatch, see my presentation at the 2025 Zephyr Developer Summit (Slides (opens in a new tab), Recording (opens in a new tab)).

The graphs presented below broadly cover three different application types; Bluetooth-only applications (320-400 kB), nRF91 LTE applications (500-600 kB), and nRF7002 Wi-Fi applications (~900 kB).

CPatch v1.1

The size gains for already deployed firmware came from one prompt and 20 minutes of spinning:

Using the same patching instructions, create a more efficient diff encoder for cpatch.py

The original encoder used a greedy approach with post-processing heuristics, while Claude Opus 5.5 created a more optimal graph-based shortest-path encoder.

This was purely an encoding-side change, so the smaller patches can be immediately used with already compiled and deployed firmware.

CPatch v2.0

Future generic firmware images can take advantage of the v2.0 encoding (shortest-path-delta), which re-uses the v1 instructions and adds in a more efficient mode for encoding address shifts over 1 byte. While the original PATCH instruction is a sequence of counts to copy followed by single-byte values to replace, PATCH_DELTA encodes 16-bit shifts which can be cached with a 1-byte index. This results in both less instruction overhead and less 'new' data being required, assuming that the address shifts are not completely random.

Note that achieving these gains requires an application compiled with v2.0 format support, so the first upgrade after updating Infuse-IoT SDK still needs to use the v1.1 format.

CPatch v3.0

Finally, a completely new patch encoding scheme was derived by Claude Opus 5.5, using the corpus of 300 releases as the ground truth of how real applications differ over time:

Create an alternate implementation of cpatch that maintains the same design goals (linear output write, no dynamic memory, no patch compression, minimal state) but isn't restricted to the current instruction format. The header format should remain the same.

After additional massaging, we ended up with an encoder that was almost magic in its efficiency. No longer are we fighting in the middle of the pack for encoding efficiency versus other schemes like JoJoDiff and bsdiff4; we are resoundingly beating them without compromising on our design goals:

1.10.0+d43d6563 -> 1.11.0+ca2a3746
Original File: 519500 bytes
     New File: 522228 bytes

Tool Comparison:
          CPatch:  67558 12.94% (greedy, v1.0)
          CPatch:  64369 12.33% (shortest-path, v1.1)
          CPatch:  36107  6.91% (shortest-path-delta, v2.0)
          CPatch:   9142  1.75% (stream-thumb2, v3.0)
        JojoDiff:  86820 16.62%
         bsdiff4:  35834  6.86%
          xdelta: 119791 22.94%

This new encoder, which we call stream-thumb2, derives its efficiency by being instruction set aware. This is a patch algorithm optimised specifically for the ARM Thumb-2 instruction set, not for generic binary data. The key insight is that most changes in a firmware image are due to memory addresses shifting, for example in branch instructions. But the instruction set itself constrains where these shifts can be, so a lot more information can be implicit, if the patch applier does the work of scanning for these branches as it is applying the patch.

The end result is an encoding scheme that is much more computationally intensive to create, and requires marginally more resources⁴ in the applier, but results in patch files so small that the tradeoff is easily worth it.

Note that achieving these gains requires an application compiled with v3.0 format support, so the first upgrade after updating Infuse-IoT SDK still needs to use either the v1.1 or v2.0 format.

Hardware Test

To see how CPatch v3 does on a realistic update, we built two versions of a small test application for the nRF54L15 DK. Both are about 300 kB and talk to the host over a 115200 bps serial link. The "original" version runs a periodic logging task and blinks an LED once a second. The "updated" version is the kind of change a real product release brings. It logs twice as often and adds a SoC temperature task, which pulls in the sensor and zbus subsystems. It also adds a new source file that handles a button press, and changes the LED to a double blink. None of these changes are large, but together they shift code and data across the whole image. Every branch and pointer that crosses a moved region changes too, which is what makes binary patches between releases bigger than the source changes suggest.

That moved code is what v3 is built for. When v3 copies a block from the old image, it updates the Thumb-2 branches and pointers inside the block for their new locations, instead of sending them again as new data. The patch sizes show the difference:

The v3 upgrade patch is under 1% of the new image size, five times smaller than v2. The downgrade patch is almost ten times smaller. This discrepancy can be explained by noticing that the upgrade contains new code, which requires relocations and new data, while removing code is primarily about relocations.

Updating the relocated branches and pointers takes extra work on the device, so v3 patches take longer to apply. On the nRF54L15, the upgrade took 1.94 s to apply instead of 1.31 s, and the downgrade 1.50 s instead of 1.31 s. That extra time is more than made up for by sending less data. At the roughly 7 kB/s our serial link reached, here is the whole update, from the start of the transfer to rebooting into the new image:

Conclusion

The new CPatch v3.0 encoding scheme opens up new possibilities for remote firmware management, enabling non-trivial firmware changes over extremely constrained links without draining your battery or your wallet. With the EU Cyber Resilience Act (CRA) requiring that products can receive security updates, device firmware updates are becoming mandatory, not optional. Infuse-IoT can be your superpower for enabling full updates over communications technologies where you pay for every byte.