Memory optimized block-based differential update algorithm

A method for updating a firmware image of an embedded device, the method comprising:

• dividing a new firmware image into blocks 1* . . . n* . . . N* of size S, wherein n* and N* are natural numbers, and wherein the size S of the blocks is determined empirically before updating the firmware image,
• considering an old firmware image of the embedded device by dividing the old firmware image into blocks 1 . . . m . . . M of size S, wherein m and M are natural numbers,
• a) matching a first block 1* of the new firmware image against the full old firmware image using a binary differential and patching algorithm by
• b) creating a first block patch 1 of the new and old firmware image according to said first block 1* of the new firmware image and the blocks 1 to M of the old firmware image and storing the first block patch in a patch file, wherein
• repeating steps a) and b) for matching against all blocks of the old firmware image that are not being processed yet and creating block patches 1 . . . n . . . N until all the blocks N* and M are processed, respectively, and wherein
• the old binary firmware image of the embedded device is updated on a block-by-block basis, by application of the corresponding block patch 1 . . . n . . . N, wherein n and N are natural numbers, and wherein a currently processed block patch n is tracked for ensuring said block patch n is not applied twice to an updated part of the old firmware image.