What would be a good algorithm for patching binary files on Linux?

I am trying to reduce data transfer to my embedded Linux device by creating patches for almost similar binaries.

I have memory constraints on my device and hence heavy algorithms like bsdiff and bspatch are unaffordable on my target for binary sizes of around 36-60 MB. I would like to know the commands that have the best algorithms for diffing and patching files that can work with minimalistic amount of memory. I am attaching output of df and free as well here.

Answer

It turns out that rdiff uses a slightly better algorithm in terms of memory, but it creates a bigger patch (delta) file than either of bsdiff or xdelta3.

xdelta3 creates the smallest patchfile, but it uses more memory to create the patch than rdiff does. So in terms of the created patch size, we have—xdelta3 < bsdiff < rdiff.

And in terms of memory consumption while applying patch we have—rdiff < xdelta3 < bsdiff