Delta Updates: Applying a Patch to an Image Already in Flash

Two consecutive firmware builds of the same product are mostly identical. The linker places functions at the same addresses, the C library is unchanged, constant tables are unchanged, and the compiler emits the same instruction sequences for the parts of the code nobody edited. A full image transfer moves all of that again to deliver a change of a few kilobytes. A delta update sends only the difference, and the receiver reconstructs the new image from the old one plus that difference.

The savings can be an order of magnitude, which matters when the link is a metered cellular connection or a low-power radio. The cost is that the receiver must now hold, or have access to, a complete correct copy of the old image while it writes the new one, and flash does not offer a place to put it for free.

Two operations are enough

A binary delta does not need to understand machine code. Any two byte strings can be expressed as a sequence of two operations: copy a range from the source, or insert literal bytes. The whole art is choosing which ranges to copy, and the encoding that names them.

The simplest useful scheme scans the source for matching blocks and emits, for each target position, either a copy instruction naming an offset and a length in the source, or a run of literal bytes. A delta produced this way is compact when the target is mostly a rearrangement of the source and bloats to roughly the target size when it is not, which is the correct degenerate behaviour: a patch that is not smaller than the image should not be used.

Better schemes find matches that are not aligned to any block boundary, which matters because a single inserted byte in the middle of a function shifts everything after it. A block-matching scheme with a fixed block size will fail to match any block that straddles the insertion, and every subsequent block is offset by one byte and therefore also unmatched. The result is a delta that is large in exactly the case that is most common: a small edit near the start of a translation unit.

The classical answer is a suffix-based algorithm of the kind described in the binary-diff literature, which indexes the source by every suffix and finds the longest match at each target position regardless of alignment. The index costs memory proportional to the source size, which is affordable on the host that builds the delta and not on the device that applies it. That asymmetry is deliberate: delta generation runs on a build machine with orders of magnitude more memory than the target, and delta application runs on the target with kilobytes.

/* A delta is a sequence of instructions. Copy reads from the source
   image; insert reads from the delta stream itself. Both are bounded
   so that a malformed delta cannot read outside either buffer. */
#define DELTA_COPY   0u
#define DELTA_INSERT 1u

struct delta_op {
    uint32_t type;      /* DELTA_COPY or DELTA_INSERT */
    uint32_t offset;    /* source offset, for COPY */
    uint32_t length;    /* bytes produced by this operation */
};

static int apply_op(const struct delta_op *op,
                    const uint8_t *src, uint32_t src_len,
                    const uint8_t *delta, uint32_t delta_len,
                    uint32_t *delta_pos,
                    uint8_t *out, uint32_t out_cap, uint32_t *out_pos)
{
    if (op->length > out_cap - *out_pos)
        return -1;                          /* would overflow the target */

    if (op->type == DELTA_COPY) {
        if (op->offset > src_len || op->length > src_len - op->offset)
            return -1;                      /* source range out of bounds */
        memcpy(out + *out_pos, src + op->offset, op->length);
    } else if (op->type == DELTA_INSERT) {
        if (op->length > delta_len - *delta_pos)
            return -1;
        memcpy(out + *out_pos, delta + *delta_pos, op->length);
        *delta_pos += op->length;
    } else {
        return -1;                          /* unknown instruction */
    }
    *out_pos += op->length;
    return 0;
}

The bounds checks are not defensive decoration. A delta is a program that reads memory, and a corrupt delta with an unchecked offset reads whatever is at that address and writes it into the image. Every field must be validated against the actual buffer sizes before use, and the validation must use subtraction rather than addition, because offset + length can wrap and pass a naive comparison.

Block alignment versus the medium

The copy instruction is the reason delta updates interact badly with flash, and the interaction is at the granularity of the erase sector rather than the byte.

A delta says: take bytes 0x2000 through 0x21FF from the source and place them at 0x2000 in the target. On a device with a scratch buffer, that is a memcpy. On a device applying the delta into a flash slot, it is not: the target location must have been erased, and it must be programmed in page-sized units, and the bytes to be programmed may come from several copy instructions whose sources are scattered.

There are two strategies, and they differ in where the reconstruction happens.

The first reconstructs in RAM. The delta is applied into a buffer, and the buffer is written to flash in page-sized chunks as it fills. This requires a buffer of at least one flash page, and it works with any delta format, because the application order is linear in the output. A 2 KiB page buffer is a reasonable price on a part with 64 KiB of RAM; on a part with 8 KiB it is a significant fraction, and on a part with 2 KiB it is impossible.

The second reconstructs in place, streaming through the target slot with a small window. This requires the delta’s copy instructions to be expressed in an order that lets the application read the source ahead of where it writes the target, because source and target are different slots and never overlap. The window then only needs to hold the bytes for the current page. The constraint is that the delta’s instruction order must be monotonic in the target offset, which the encoder can guarantee.

The in-place strategy fails when the source and target are the same slot, which happens in a design without a second slot. Applying a delta over the image being read destroys the source for every copy instruction that has not yet executed. A design that does this must first copy the source to a scratch region, which consumes the same flash the second slot would have, or must order the delta so that every copy reads from a region already consumed, which is a much stronger constraint and is not achievable in general.

The practical conclusion is that delta updates do not remove the need for a second slot. They reduce the bytes transferred, not the bytes stored. A design with two slots and a delta still needs both slots; the delta is delivered into the inactive slot, applied against the active one, and the result is a complete image there.

Where the delta is stored while it is applied

The delta itself needs a home. It is smaller than the image, but it is not small enough to hold in RAM on a constrained part, and it arrives over the same link as a full image would.

Three placements are possible. The delta can be written into the inactive slot and applied from there, producing the new image into a second region, which requires three regions and is rarely available. The delta can be streamed and applied as it arrives, which requires the application to be resumable at instruction granularity and therefore requires the stream to be ordered by output position. Or the delta can be written into the inactive slot, and the reconstruction can overwrite the delta region as it proceeds, which works only if the delta is consumed strictly in order and the write position never falls behind the read position.

The streaming form is the most attractive and the most demanding. It requires that the delta’s instructions be in output order, which is natural for an encoder that walks the target sequentially, and it requires the receiver to know the output size before it begins so it can refuse a delta that would overflow the slot. The output size is a header field, and it must be validated against the slot size exactly as the image length is in image header and integrity validation.

Streaming also removes the ability to verify the delta before applying it. A delta received in full can be hashed and checked against a signature before any write occurs; a delta applied as it streams can only be checked incrementally. The compromise is to sign the delta and verify the signature over the header before applying anything, then rely on the final image hash to catch a corrupt body. That leaves the intermediate writes unverified, which is acceptable because they go to a slot that is not bootable until the final check passes.

Binding the patch to its base

A delta is only valid against one specific source image. Applying it to a different base produces a target that is the right length and wrong in every byte that differed between the bases. If the source was version 1.2 and the delta expects 1.3, the copied regions are 1.2 content placed at 1.3 offsets, and the result is a chimera.

Nothing in the delta’s structure detects this. The copy instructions are offsets and lengths; they do not name the content they expect. So the binding has to be explicit, and there are two ways to provide it.

The first is a hash of the source image in the delta header. The receiver computes the hash of the base slot and compares. This costs a full hash over the base image, which is the same cost as the boot-time integrity check and can be avoided if that check’s result is cached. The comparison is exact and catches any difference in the base.

The second is a version identifier, which is cheaper and weaker. It catches a base that is the wrong version but not a base that is the right version and corrupted. Since corruption is precisely what the base’s own integrity check is for, the two together are sound: the base must pass its own check, and the delta must name the version it expects.

The failure mode to guard against is the base that passes its check and is the wrong version, because the device has no way to obtain the right one. It must fall back to a full image transfer, and the fallback must be automatic rather than requiring a human decision, because the device may be unreachable. That means the update service must be prepared to send a full image when the device reports that the delta does not apply, which is a protocol capability rather than a device capability.

When the delta is the wrong choice

The savings are real but they are not free, and four conditions make a delta worse than a full image.

When the base image is not present. A device that has never been updated, or whose active slot was erased, has no base. The delta is useless and the transfer must be full. A fleet that has devices at many versions needs a delta for each version pair, or a chain of deltas that is applied in sequence, which multiplies the failure surface.

When the change is large. A rebuild that changes compiler flags, or switches optimisation level, or updates the C library, produces an image that differs almost everywhere. The delta approaches the size of the image and adds the application cost on top. Encoders usually report the ratio and the distribution system chooses per release; a threshold near half the image size is a workable cut-off, because below it the saving does not repay the extra failure mode.

When RAM is the binding constraint. A part with a small page buffer can stream a full image in page-sized writes with almost no memory, because a full image arrives in order. A delta needs a buffer for the copy source and the literal stream at the same time, plus the bounds state, and on the smallest parts that is the difference between an update path that fits and one that does not.

When verification matters more than bandwidth. A full image is verified end to end before anything is written. A delta is verified after the writes have happened, and the intermediate state is a slot full of unverified bytes. On a device where a partially written slot can affect anything else, that is a real risk. It is the same risk a full image carries, because a full image is also written before it is verified, which is the argument for the inactive slot being genuinely inactive: no code runs from it, and nothing reads it, until the verification passes.

The last condition is worth stating as a principle. Delta updates change the size of the transfer, not the structure of the update. The slots, the metadata, the trial boot, and the rollback all remain, and the delta is a compression of the delivery step. A design that tries to simplify the slot layout because the delta is small has traded a solved problem for an unsolved one, and the arrangement in dual-bank slots and boot selection is what the reconstruction depends on.