Implementation notes

Details of the librsync 2.x formats that are easy to get wrong, and the places where Rexd deliberately differs from librsync's behaviour while staying wire-compatible. The reference is librsync 2.3.4.

Strong hash: BLAKE2b-256, not truncated BLAKE2b-512

librsync computes the strong sum with blake2b_init(&ctx, 32) and truncates the 32-byte digest to strong_sum_len when writing the signature (checksum.c, mksum.c). BLAKE2b's digest length is part of the parameter block that initialises the state, so BLAKE2b-256 is a different function from BLAKE2b-512 cut to 32 bytes:

OTP's :crypto exposes BLAKE2b only with a 64-byte digest and no length parameter, so Rexd.Blake2b implements BLAKE2b-256 in Elixir.

BLAKE2b works on 64-bit words. BEAM small integers hold 60 bits, so direct 64-bit arithmetic allocates a bignum on nearly every addition and rotation. Rexd.Blake2b carries each word as two 32-bit halves, with carries propagated by hand, and unrolls all twelve rounds at compile time. On an Apple Silicon laptop (OTP 28, JIT) this runs at about 63 MB/s over 2 KiB blocks, against about 5 MB/s for the direct 64-bit version.

RabinKarp weak checksum

From rabinkarp.h: SEED = 1, MULT = 0x08104225, arithmetic mod 2^32.

• Bytes are hashed as-is. There is no per-byte offset.
• Sliding the window is h·MULT + in − MULT^n·(out + ADJ) with ADJ = MULT − 1. The ADJ term removes the seed's contribution, which moves up one power of MULT with every appended byte. A rolling update without it is internally consistent (rolling and from-scratch results agree with each other if both omit the seed) but does not match librsync.
• MULT^n mod 2^32 and MULT^n·ADJ mod 2^32 depend only on the window length and are computed once. Inside the loop the only products are h·MULT (below 2^59.01, which exceeds the small-integer limit only when h is within about 1% of 2^32) and MULT^n·out (below 2^40).

Older signature types

librsync defines four signature magics, combining two rolling checksums with two strong hashes; librsync selects them by nibble (sumset.h): magic & 0xf0 == 0x30 means rollsum, magic & 0x0f == 0x06 means MD4. All four are read and written.

• Rollsum (rollsum.h) keeps two 16-bit sums with every byte counted as byte + 31, and the digest is s2 · 2^16 + s1. librsync declares the sums as uint_fast16_t, which is 16 bits on some platforms and 64 bits on others; the digest only keeps the low 16 bits of each, so the result is the same everywhere, and Rexd computes modulo 2^16 throughout. librsync also applies a MurmurHash3 finaliser (mix32) to rollsums, but only inside its in-memory hash table; it never reaches the wire.
• MD4 keeps at most 16 bytes per block. OTP's :crypto provides MD4 only when OpenSSL's legacy provider is loaded, which many OpenSSL 3 builds omit, so Rexd implements RFC 1320 in Elixir (lib/rexd/md4.ex). Its 32-bit words fit the small-integer range, so unlike BLAKE2b it needs no split words; its rounds are nevertheless generated at compile time, for the reason given under "Code shaped by performance".

Block length

rdiff does not use a fixed default. With -b 0, its default, it applies rs_sig_args: 256 bytes for inputs up to 65 536 bytes, otherwise the integer square root of the input size rounded down to a multiple of 128. Rexd.recommended_block_len/1 reproduces that choice. Rexd.signature/2 defaults to 2048 (RS_DEFAULT_BLOCK_LEN, librsync's value when the input size is unknown), because a signature may be computed before the size is known.

The signature format does not record the basis length, so a decoded signature cannot tell whether its last block is short.

Delta command encoding

The opcode table is generated from prototab.c (scripts/gen_prototab.exs). Encoding follows emit.c:

• literals of 1 to 64 bytes put the length in the opcode (0x01–0x40);
• longer literals use LITERAL_N1/N2/N4, whichever is smallest;
• copy commands choose the offset width and the length width independently.

librsync bounds the size of a literal command and so never emits LITERAL_N8. Rexd emits a single literal per unmatched run, which uses LITERAL_N8 only above 4 GiB. Both decoders accept it.

Rexd.Delta.decode/1 rejects bytes after the END command, and rejects what librsync's patcher (patch.c) reports as a corrupt stream: zero-length literal or copy commands, and 8-byte arguments of 2^63 or more, which librsync reads as negative signed integers.

Rexd.patch/3 checks every copy against the basis length and computes the output size before building any output. A delta of a few kilobytes can describe gigabytes of output through repeated copies, so :max_size bounds it for deltas from untrusted sources.

Delta search

The search follows delta.c: a full-block window rolls one byte at a time until its weak checksum is found in the signature and its strong hash confirms a block; a match emits a copy and restarts the window after it; contiguous copies are merged; at the end of the input the window shrinks from the front so that a short last block can still match.

Differences, none of which affect the wire format:

• Continuation preference. When a window matches several identical basis blocks, Rexd picks the block that directly follows the previous copy, if it matches. librsync picks the first block its hash table returns. On repetitive input such as runs of zero bytes, Rexd therefore emits one long copy where librsync emits one copy per block. On the committed test vectors the encoded deltas are otherwise byte-identical to rdiff's.
• Short windows only against the last block. Only the last basis block can be shorter than block_len, so shrinking end-of-input windows are compared against that block alone. librsync compares them against every block with a matching weak checksum, which can only succeed through a hash collision.
• Literals reference the input. Literal commands are sub-binaries of the new data, not copies.

Untrusted input

Signatures and deltas usually arrive from another machine, so every decoder and applier treats them as hostile.

• Decoding returns an error tuple for any byte sequence: truncation, unknown or reserved opcodes, zero lengths, and arguments librsync would read as negative. Mutation-based property tests (bit flips, insertions, deletions, truncation of valid encodings) check that no other exception escapes, and that the streaming and whole-binary patchers reject exactly the same corrupted deltas.
• Patching validates every copy against the basis and computes the output size before building output; :max_size bounds it. Implausible lengths (a literal or copy claiming 2^62 bytes) fail without allocating.
• Signature index. A signature can be crafted so that many blocks share one weak checksum. The index maps each weak checksum to a map keyed by strong hash, so building it and looking a window up stay constant-time per block; with a list of candidates instead, 200 000 such blocks take minutes to index and every matching window scans all of them.
• Crafted weak collisions. RabinKarp is not keyed. Anyone who knows the signature can construct new data in which every window matches some weak checksum, forcing a BLAKE2b computation per input byte and slowing the delta to roughly 30 KB/s with block_len 2048. The output remains correct. librsync has the same property; it is inherent to an unkeyed rolling checksum, and callers that compute deltas over data supplied by an untrusted party should bound the time spent.

In-place patching

Rexd.InPlace follows Rasch and Burns, In-Place Rsync: File Synchronization for Mobile and Wireless Devices (USENIX ATC 2003), without changing the delta format.

• No destination offsets needed on the wire. librsync commands carry no output position, but each one follows from the lengths of the commands before it, so both sides can compute where every copy writes. An in-place delta is an ordinary delta: rdiff patch applies it front to back as usual.
• Dependency graph. Copy i must run before copy j when i reads a byte j writes. A copy overlapping its own destination is not a dependency; it is applied in the direction that never reads an overwritten byte. Literals read nothing and are written last.
• Cycles. When a depth-first search closes a cycle, the sender converts the shortest copy on it into a literal (the "locally minimum" policy of the paper), unwinds only the part of the search below that copy, and continues. The receiver runs the same search and rejects a delta that still contains a cycle, before writing anything.
• Linear-time traversal. Output ranges are disjoint and in order, so the copies a given copy depends on form one contiguous index range, found by binary search. Finished copies are skipped through a next-pointer structure with path compression, so no range is scanned twice past finished copies. A delta constructed with 20 000 copies reading the output of 20 000 others, 400 million dependencies, is ordered in about a second; with a linear skip in place of path compression it exceeds the test's five-second bound.
• Common edits need no conversion. An insertion moves later data forward and a deletion moves it backward; both produce overlapping copies but no cycles. Cycles arise when regions trade places, and cost the bytes of the shorter region.

Streaming

Rexd.Stream shares its algorithms with the whole-binary functions rather than reimplementing them.

• Signature. Input is grouped into whole blocks and signed with Rexd.Signature; the output is byte-identical to Rexd.Signature.encode/1.
• Delta. The search (lib/rexd/delta/search.ex) is resumable: it consumes input in chunks and suspends when the rolling window reaches the end of the buffered data, recording the window position and its weak checksum. Rexd.delta/2 is the same search fed once. Matches are therefore identical; the only difference is that a stream emits pending unmatched bytes as a literal command once they reach 64 KiB at the end of an input chunk, as librsync bounds literals to MAX_DELTA_CMD. Bytes already covered by emitted commands are dropped from the buffer once they make up at least half of it, which keeps both memory and copying linear.
• Patch. A single-command decoder in lib/rexd/delta.ex decodes one command at a time and serves both Rexd.Delta.decode/1 and the streaming patcher. Literal data is passed through as it arrives; copies are read from the basis lazily, in pieces of at most 64 KiB, so a single large copy never materialises in memory.
• Errors. A stream cannot return an error tuple, so invalid input raises Rexd.StreamError when the stream is consumed. Its reason uses the same terms as the tuple-returning functions.

Code shaped by performance

A few places favour speed over the most direct form of the code. Each is listed here with the direct form it replaces and the measured difference, and carries a short comment at the code site.

Measurements: Apple Silicon laptop, Elixir 1.19 / OTP 28 with the JIT, random data, block_len 2048, strong_sum_len 32.

The reverse trade was also made once. The delta search was first written as a single loop with nine positional arguments, which ran at 43.7 MB/s on unmatched data. It was restructured around the Context and Output structs for clarity at a cost of about 18%, since the result stays well above the 20 MB/s design target.

MD4 was first written directly: the 48 steps folded over a tuple of state words with Enum.reduce/3. That form allocates on every step, and its speed depended on the calling process's heap: rollsum + MD4 signatures of 20 MiB ran at 51 MiB/s in a fresh process and 117 MiB/s in one with a grown heap. Generating the steps at compile time as plain variable rebindings removes the allocation; the same signatures run at 141 MiB/s in both.

One apparent optimisation was rejected: splitting h·MULT in RabinKarp into 16-bit halves to avoid occasional bignums measured 305 MB/s against 473 MB/s for the plain product.