Editing Delta encoding (section)

===bsdiff===
Bsdiff is a binary diff program using [[Suffix array|suffix sorting]]. For executables that contain many changes in pointer addresses, it performs better than VCDIFF-type "copy and literal" encodings. The intent is to find a way to generate a small diff without needing to parse assembly code (as in Google's Courgette). Bsdiff achieves this by allowing "copy" matches with errors, which are then corrected using an extra "add" array of bytewise differences. Since this array is mostly either zero or repeated values for offset changes, it takes up little space after compression.<ref>{{Cite web|url=http://www.daemonology.net/bsdiff/|title=Binary diff|website=www.daemonology.net|accessdate=November 9, 2024}}</ref>

Bsdiff is useful for delta updates. Google uses bsdiff in Chromium and Android. The ''deltarpm'' feature of the [[RPM Package Manager]] is based on a heavily modified bsdiff that can use a hash table for matching.<ref>{{cite web |title=rpmdelta/delta.c |url=https://github.com/rpm-software-management/deltarpm/blob/c5e0ca7482e2cfea5e4d902ffe488e0a71ed3e67/delta.c |publisher=rpm-software-management |access-date=13 January 2020 |date=3 July 2019}}</ref> [[FreeBSD]] also uses bsdiff for updates.<ref>{{cite web|author=Anonymous|website=GitHub Gist|url=https://gist.github.com/anonymous/e48209b03f1dd9625a992717e7b89c4f|title=NON-CRYPTANALYTIC ATTACKS AGAINST FREEBSD UPDATE COMPONENTS|date=May 2016}}</ref>

Since the 4.3 release of bsdiff in 2005, various improvements or fixes have been produced for it. Google maintains multiple versions of the code for each of its products.<ref>{{cite web |title=xtraeme/bsdiff-chromium: README.chromium |url=https://github.com/xtraeme/bsdiff-chromium/blob/master/README.chromium |website=GitHub |language=en |date=2012}}; {{cite web |title=courgette/third_party/bsdiff/README.chromium - chromium/src |url=https://chromium.googlesource.com/chromium/src/+/master/courgette/third_party/bsdiff/README.chromium |website=Git at Google}}; {{cite web |title= android/platform/external/bsdiff/|url=https://android.googlesource.com/platform/external/bsdiff/+/refs/heads/master|website=Git at Google}}</ref> FreeBSD takes many of Google's compatible changes, mainly a vulnerability fix and a switch to the faster {{code|divsufsort}} suffix-sorting routine.<ref>{{cite web|url=https://github.com/freebsd/freebsd/commits/master/usr.bin/bsdiff|website=GitHub|title=History for freebsd/usr.bin/bsdiff}}</ref> [[Debian]] has a series of performance tweaks to the program.<ref>{{cite web|url=https://sources.debian.org/patches/bsdiff/ |website=Debian Patch Tracker |title=Package: bsdiff}}</ref>

''ddelta'' is a rewrite of bsdiff proposed for use in Debian's delta updates. Among other efficiency improvements, it uses a sliding window to reduce memory and CPU cost.<ref>{{cite web |last1=Klode |first1=Julian |title=julian-klode/ddelta |url=https://github.com/julian-klode/ddelta |website=GitHub |access-date=13 January 2020}}</ref>