haxpatch

A single header reader and writer for the haxdiff/1.0 binary diff format.

haxdiff is the format, and the name of the reference command line tool that defined it. haxpatch is this library: it implements that format and nothing else, so that a program can create and apply patches without shelling out to a tool.

There is now a reference GUI implementation using this library here: https://github.com/rofl0r/haxgui

The format was defined by rofl0r and is placed in the public domain; the reference implementation at https://github.com/rofl0r/haxdiff. The code here is written independently against the format rather than derived from that implementation.

The format description is restated below so that it stays available in this tree regardless of what happens to the upstream repository.

Format

A patch is a text file. Lines end with \n or \r\n, and any line not beginning with @, - or + is a comment.

A patch is a sequence of hunks in ascending order of offset. Each hunk begins with a header. The trailing @@ is optional but on by default:

@@ <offset>,-<removed>,+<inserted> @@

All three numbers are hexadecimal, without a 0x prefix, in lower case. The header is followed by:

• Zero or more - lines, each carrying a hexadecimal byte sequence. Together they must total removed bytes. These are the bytes the patch expects to find, and exist so a patch can be checked against its input and read by a human. They may be omitted entirely.
• One or more + lines under the same rules, totalling inserted bytes. These are the replacement bytes.

Lines may carry up to 1000 bytes of data but are conventionally kept near 80 characters wide. A hunk with removed and inserted unequal means the file changes size: -0,+n at an offset equal to the original size appends, and -n,+0 at an offset equal to the new size truncates.

Example:

@@ 17b0,-4,+4 @@
- 04020004
+ 00000000
@@ b666c,-8,+8 @@
- 0e48396801600e48
+ 0048004701bb3e08

Offsets are text, so the format has no size ceiling. That is the reason it was chosen here: a 64DD disk image is 0x435B0C0 bytes, and IPS cannot address past 0xFFFFFF.

The patch a writer produces is still identified as haxdiff/1.0 on its first line, whatever the writing program is called. That is the format's name, not the library's.

Where the reference implementation and its specification differ

Noted from reading the implementation rather than trusting the specification. None of these are faults in the format itself.

• The implementation writes a haxdiff/1.0 banner as the first line, but the format description never mentions it and its own worked example omits it. Its parser ignores the line as a comment. This writer emits it for recognisability; this reader ignores it.
• The description says hexadecimal shall be lower case. The reference decoder accepts either case. Both are followed here: lower case is written, either is read.
• The reference decoder does not validate its input. A character that is not a hexadecimal digit yields -1 from its lookup and is shifted into the output byte, so corrupt data decodes silently to wrong bytes rather than being rejected. This reader rejects it.
• Runs of difference separated by fewer than 16 unchanged bytes are emitted as a single hunk. That is a choice of the implementation and appears nowhere in the description. It is matched here, because it is what makes the two produce identical output.
• The reference diffs in 16 KiB chunks, so a run of difference crossing a chunk boundary becomes two hunks. This writer works on whole images and emits one. Both are valid; the patches are otherwise identical.
• The reference checks a hunk header with if(pbuf[1] != '@' && pbuf[2] != ' '), where || was surely meant, so some malformed headers are accepted. This reader requires both.
• The reference's diff loop tests buf[0][i] != buf[1][i] && i < min, evaluating the comparison before the bound. At i == min it reads one byte past the valid data, and when a full 16 KiB chunk was read that is past the end of the buffer. The outcome of the comparison cannot change the result, so patches come out correct, but the read is still out of bounds. Reproduced under AddressSanitizer with two 16384 byte files differing in their last 40 bytes: stack-buffer-overflow, READ of size 1. Reaching it needs a run of difference that extends to a chunk boundary, which is why ordinary sparse diffs do not show it.
• A patch with no hunks is written as a completely empty file, not even the banner. That is valid and means "no changes".

What this implementation supports

haxpatch_write produces hunks that replace bytes in place, which is all a fixed-size image needs. haxpatch_apply works on an image already in memory and returns HAXPATCH_UNSUPPORTED for a hunk that would resize it.

The - lines are optional in the format and optional here, through haxpatch_write's verify_lines argument. They are half of a patch by volume, so a patch written without them is about half the size, but it can no longer be checked against its input or read as a before and after. A patch written either way applies either way.

The library depends on nothing beyond <stdio.h>, <stdint.h>, <stddef.h> and <string.h>, and is plain ISO C11, so it can be dropped into another project by copying haxpatch.h, with or without haxpatch.c.

Usage

Include the header wherever the declarations are wanted. In exactly one translation unit, define HAXPATCH_IMPLEMENTATION before the include to compile the implementation along with them:

#define HAXPATCH_IMPLEMENTATION
#include "haxpatch.h"

The implementation sits outside the header's include guard, so a translation unit that has already included the header plainly may include it a second time with the define set.

haxpatch.c in this repository is nothing but those two lines, for a build that would rather add a source file than carry the define in one of its own. Only one of the two approaches is needed.

The declarations are wrapped in extern "C" under a C++ compiler, so the header may be included from C++ regardless of whether the implementation was compiled as C or as C++.

Verification through the - lines covers only the bytes a hunk replaces. A patch will not detect that it has been applied to an unrelated image if the regions it touches happen to match. Anything that needs to know it has the right image should identify it separately.