DOCSEARCHbyAlgolia
Submit Docs

HDiffPatch

repository·master·Indexed 24 days ago

https://github.com/sisong/hdiffpatch

A high-performance C/C++ library and CLI toolset for binary and directory-based differential (diff/patch) operations. It features low memory footprints and cross-platform compatibility, including specialized support for Android and embedded systems. The toolset includes hdiffz for creating delta files and hpatchz for applying them, supporting various compression algorithms like zstd, lzma2, and zlib, as well as compatibility with bsdiff4 and xdelta3.

Tokens
6.1K
Snippets
3
Records
29
Agent score
74%

What's inside HDiffPatch

  1. Overview of HDiffPatch

    master

    HDiffPatch is a C/C++ library and command-line tool designed for performing diff (creating patches) and patch (applying patches) operations on binary files or directories. It is cross-platform, high-performance, and produces small patch files. It supports very large files and allows users to control memory usage during both diff and patch operations.

    Key features include:

    • Format Compatibility: Uses its own patch format but is fully compatible with bsdiff4, endsley/bsdiff, open-vcdiff, and xdelta3 (VCDIFF RFC 3284).
    • Embedded Support: For MCU or NB-IoT devices, use [HPatchLite] with [tinyuz] to run on devices with as little as 1KB of memory.
    • Android Optimization:
      • [ApkDiffPatch] creates smaller patches for APKs but requires re-signing the APK before diffing.
      • [sfpatcher] is optimized for Android app stores, requiring $O(1)$ memory and no re-signing.
    • Sync Algorithms: [hsynz] (similar to zsync) allows incremental updates without needing the original old version data on hand, supporting zstd compression.

  2. Compare HDiffPatch with bsdiff4 and xdelta3

    master
    HDiffPatch provides various compression and diffing modes (zlib, lzma2, zstd) that can be compared against other tools like bsdiff4 and xdelta3. The performance varies significantly based on the chosen compression algorithm and the specific flags used (e.g., -BSD, -SD, -WD). For example, using hdiffz with zstd compression often results in smaller patch sizes and higher patching speeds compared to xdelta3 or bsdiff in many test scenarios.

  3. Compare HDiffPatch performance with bsdiff4 and xdelta3

    master

    HDiffPatch provides various compression and speed profiles compared to other tools like bsdiff4 and xdelta3. The performance varies significantly based on the chosen algorithm (zlib, lzma2, zstd) and optimization flags (e.g., -s for small diffs, -w for windowed diffs, -WD for windowed diff with optimized patch speed).

    Key performance characteristics observed in testing:

    • Compression Ratio: Generally ranges from ~6% to ~20% depending on the algorithm and file type.
    • Speed: hdiffz with zstd often achieves very high patch speeds (e.g., >2500 MB/s in some configurations).
    • Memory Usage: Varies widely; hsynz with zstd can use several GBs of memory, while hdiffz profiles typically stay within hundreds of MBs to a few GBs.

  4. Configure hdiffz matching modes (-m and -s)

    master

    HDiffPatch offers two primary matching strategies that balance memory usage, speed, and patch size:

    1. Memory Mode (-m) - Default

    Loads all files into memory. This generally produces the smallest patch files.

    • Memory usage: (new_version_size + old_version_size * 5 [or *9 if old >= 2GB]) + O(1).
    • matchScore: Use -m[-matchScore]. Default is 4.
      • For binary data: recommend 0 to 4.
      • For text/file data: recommend 4 to 9 (higher values work better for highly compressible data).
    • Companion options:
      • -cache: Enables a large buffer to speed up matching (increases memory usage to O(old_version_size)).
      • -block-fastMatchBlockSize: Used with -m to perform a fast block-based match before byte-by-byte matching. Default is -block-1k. Set to -block-0 to disable.
      • -w[-oldWinSize-segSize]: Window mode. When used with -m, patch files may grow slightly but optimize reading access.

    2. Stream Mode (-s)

    Loads files as streams. This is generally faster and uses less memory.

    • Memory usage: O(old_version_size * 16 / matchBlockSize + matchBlockSize * 5 * parallelThreadNumber).
    • matchBlockSize: Use -s[-matchBlockSize]. Default is 64. Recommended values: 16, 32, 48, 1k, 64k, 1m.
    • Companion options:
      • -w[-oldWinSize-segSize]: In -s mode, this can significantly reduce patch file size.

  5. Create optimized window-based diffs (-WD and -SD)

    master

    For high-performance patching (supporting multi-threading and step-by-step downloading), use these specialized formats:

    • Window Diff (-WD): The recommended primary format. It optimizes reading old data during patching and supports step-by-step patching.

      • Requires window mode (automatically enables -w-2m).
      • Default compression: zstd. Default checksum: xxh128.
      • Use -WD[-stepSize] to set granularity (default -WD-256k).

    • Single Compressed Diff (-SD): Creates an HDIFFSF20 format diff. It requires only one decompression buffer and supports multi-threaded, step-by-step patching.

      • Use -SD[-stepSize] to set granularity (default -SD-256k).

    • Window Mode Configuration (-w): Used to optimize read performance.

      • -w[-oldWinSize-segSize]
      • oldWinSize: Max window bytes on old data (default -w-2m).
      • segSize: Initial data granularity (default oldWinSize/64).

  6. Use advanced diff formats: WD, SD, BSD, and VCDIFF

    master

    HDiffPatch supports several specialized patch formats for different use cases:

    1. Window Diff (-WD) - Recommended

    Creates the HDIFFW26 format. Optimized for reading old data during patching.

    • Key Features: Supports streaming patch (patching while downloading) and multi-threaded patching.
    • Defaults: Uses zstd compression and xxh128 checksum.
    • Usage: Requires window mode (-w). Use -WD[-stepSize] where stepSize defaults to 256k.

    2. Single Compression Stream (-SD)

    Creates the HDIFFSF20 format.

    • Key Features: Requires only one decompression buffer during patching. Supports streaming patch and multi-threaded patching.
    • Usage: Use -SD[-stepSize] where stepSize defaults to 256k.

    3. BSD Compatible (-BSD)

    Creates a patch compatible with bsdiff4.

    • Limitations: Does not support folder-to-folder diffing.
    • Note: Can be combined with -SD to create a single-stream patch compatible with endsley/bsdiff.

    4. VCDIFF Standard (-VCDIFF)

    Creates a standard VCDIFF format patch.

    • Limitations: Does not support folder-to-folder diffing.
    • Compression: By default, it is uncompressed (compatible with open-vcdiff or xdelta3 -S -e -n). If a compressLevel is provided, it uses 7zXZ (xz/lzma) and is compatible with xdelta3 -S lzma -e -n.
    • Usage: -VCD[-compressLevel[-dictSize]]. Default dictSize is 8m.

  7. Build libhpatchz.so for Android

    master

    To generate .so libraries for Android use, follow these steps:

    1. Install the [Android NDK].
    2. Navigate to the Android NDK JNI directory:
      cd HDiffPatch/builds/android_ndk_jni_mk
    3. Run the build script:
      • On Linux/MacOS: ./build_libs.sh
      • On Windows: build_libs.bat
    4. Integration:
      • Add the .so files to your Android project.
      • Add com/github/sisong/HPatch.java (located in HDiffPatch/builds/android_ndk_jni_mk/java/) to your project. This Java class allows you to call the patch functions within libhpatchz.so.
    $ cd HDiffPatch/builds/android_ndk_jni_mk
$ build_libs.sh

  8. Use the HDiffPatch CLI to create and apply deltas

    master

    You can use the hdiffz command to create a delta file and hpatchz to apply it.

    Create a delta: Use hdiffz with the syntax: hdiffz oldPath newPath outDiffFile [options].

    • Use -WD to enable the format that supports multi-threaded patching.
    • Use -s-64 for a balance of speed and size. For more precise matching (at the cost of higher memory usage), try -m-4.

    Apply a delta: Use hpatchz with the syntax: hpatchz oldPath diffFile outNewPath.

    • To speed up patching using multiple threads, add the -p-<threads> parameter (e.g., -p-5). Note: Multi-threading is not recommended on HDDs.

    Example Workflow:

  9. Build HDiffPatch from source

    master

    To build HDiffPatch, you must first clone the repository and its submodules.

    Step 1: Clone the repository

    git clone --recurse-submodules https://github.com/sisong/HDiffPatch5.git <code_dir>
cd <code_dir>

    Step 2: Compile based on your platform

    Linux or MacOS

    cd HDiffPatch
make -j

    On MacOS, you can also open HDiffPatch/builds/xcode/HDiffPatch.xcworkspace using Xcode.

    Windows

    Open HDiffPatch/builds/vc/HDiffPatch.sln using Visual Studio.

    Android (libhpatchz.so)

    1. Install the Android NDK.
    2. Navigate to the JNI directory: cd HDiffPatch/builds/android_ndk_jni_mk.
    3. Run the build script: ./build_libs.sh (or build_libs.bat on Windows).
    4. This generates .so files. To use them in an Android app, import the generated .so files and the Java class com/github/sisong/HPatch.java located in HDiffPatch/builds/android_ndk_jni_mk/java/.
    git clone --recurse-submodules https://github.com/sisong/HDiffPatch5.git <code_dir>
cd <code_dir>

# For Linux/MacOS
cd HDiffPatch
make -j

  10. Create and apply patches using CLI

    master

    You can use the pre-compiled binaries for Windows, Linux, and MacOS to manage patches via the command line.

    Create a patch with hdiffz

    Use the hdiffz command to generate a patch file between an old path and a new path.

    $ hdiffz oldPath newPath outDiffFile -WD -s-64
    • Tip: To achieve more precise matching (at the cost of higher memory usage), replace -s-64 with -m-4.

    Apply a patch with hpatchz

    Use the hpatchz command to reconstruct the new file using the old file and the patch.

    $ hpatchz oldPath diffFile outNewPath
    • Tip: The -WD format supports multi-threading to speed up the patching process. You can add a parameter like -p-5 to enable multiple threads (note: multi-threading is not recommended on HDD disks).

  11. Exclude paths from folder diffs using -g

    master

    When performing folder-to-folder diffs, you can exclude specific files or directories from the process using the -g flags.

    Syntax Rules

    • Separator: Use # to separate multiple paths. If a path contains a #, escape it as #:.
    • Wildcards: Use * for any character sequence. If a path contains a *, escape it as *:.
    • Directories: A trailing / indicates the pattern matches a directory and all its contents.

    Flags

    • -g#ignorePath[#ignorePath...]: General ignore list for both old and new versions.
    • -g-old#ignorePath[...]: Ignore paths in the old version (useful for files that might be modified by running processes).
    • -g-new#ignorePath[...]: Ignore paths in the new version.

    Example Pattern

    #.DS_Store#desktop.ini#*thumbs*.db#.git*#.svn/#cache_*/00*11/*.tmp

  12. Configure hdiffz compression algorithms and levels

    master

    Use the -c-compressType[-compressLevel] option to specify the compression algorithm and level for the patch data. Note that -WD (Window Diff) defaults to zstd compression.

    Supported Compression Types

    TypeFlagNotes
    None-c-noDisables compression
    Zlib-c-zlib[-{1..9}[-dictBits]]Default level 9, default dictBits 15. Supports multi-threading.
    Libdeflate-c-ldef[-{1..12}]Faster/smaller than zlib. dictBits is always 15. Supports multi-threading.
    Bzip2-c-bzip2[-{1..9}] (or -bz2)Default level 9.
    Parallel Bzip2-c-pbzip2[-{1..9}] (or -pbz2)Default level 8. Produces slightly different output than standard bzip2.
    LZMA-c-lzma[-{0..9}[-dictSize]]Default level 7, default dictSize 8m. Supports 2 threads.
    LZMA2-c-lzma2[-{0..9}[-dictSize[-blockSize]]]Default level 7, default dictSize 8m. For multi-threaded decompression, set blockSize equal to dictSize.
    Zstd-c-zstd[-{0..22}[-dictBits]]Default level 20, default dictBits 23. Supports multi-threading.

    Note: lzma and lzma2 use different encoding formats.