haxpatch.h

/*
Copyright (c) 2026 Rupert Carmichael
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this
   list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice,
   this list of conditions and the following disclaimer in the documentation
   and/or other materials provided with the distribution.

3. Neither the name of the copyright holder nor the names of its
   contributors may be used to endorse or promote products derived from
   this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

//
// haxpatch.h: reader and writer for the haxdiff/1.0 binary diff format.
//
// haxdiff is the format, and the name of its reference command line
// tool; haxpatch is this library, which implements the format and
// nothing else. The format is public domain and is described in
// README.md alongside this file. This implementation is independent of
// the reference one and works on images already held in memory rather
// than on files.
//
// This is a single header library. Include it wherever the declarations
// are wanted, and in exactly one translation unit define
// HAXPATCH_IMPLEMENTATION before the include to compile the
// implementation along with them:
//
//     #define HAXPATCH_IMPLEMENTATION
//     #include "haxpatch.h"
//
// A translation unit that has already included the header plainly may
// include it again with the define set. The haxpatch.c beside this file
// 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.
//
// The declarations carry C linkage under a C++ compiler, so the header
// may be included from C++ whether the implementation was compiled as C
// or as C++.
//

#ifndef HAXPATCH_H
#define HAXPATCH_H

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

#ifdef __cplusplus
extern "C" {
#endif

enum haxpatch_result {
  HAXPATCH_OK = 0,
  HAXPATCH_IO,           // the stream could not be read or written
  HAXPATCH_MALFORMED,    // the patch does not parse
  HAXPATCH_MISMATCH,     // a '-' line disagrees with the image it is applied to
  HAXPATCH_RANGE,        // a hunk falls outside the image
  HAXPATCH_UNSUPPORTED   // a hunk resizes the image, which is fixed here
};

/* Writes a patch to out describing how to turn base into mod, both of
   which are size bytes long. An unchanged image produces an empty patch,
   which is valid and applies as a no-op.

   With verify_lines set the patch also records the bytes it expects to
   replace, so that it can be checked against its input and read as a
   before and after. They are what haxpatch_apply checks, and they double
   the size of the patch; a patch written without them still applies. */
int haxpatch_write(FILE *out, const uint8_t *base, const uint8_t *mod,
  size_t size, int verify_lines);

/* Applies a patch read from in to image, in place. When verify is
   non-zero the '-' lines must match what the image already holds, and
   HAXPATCH_MISMATCH is returned if any does not; the image may have been
   partly modified by that point. */
int haxpatch_apply(FILE *in, uint8_t *image, size_t size, int verify);

// A short description of a result code, for reporting to the user.
const char *haxpatch_strerror(int result);

#ifdef __cplusplus
}
#endif

#endif // HAXPATCH_H

/* The implementation. It sits outside the guard above, so that having
   included this file for its declarations does not stop a later include
   with HAXPATCH_IMPLEMENTATION set from compiling it. */
#ifdef HAXPATCH_IMPLEMENTATION

#include <string.h>

/* Bytes of image data per output line. The format allows up to 1000
   bytes to a line but advises keeping them near 80 characters wide; at
   this width a line is 2 + 76 + 1 characters, which also keeps every
   line well inside the reference implementation's 1024 byte reader. */
#define HAXPATCH_LINE_BYTES 38

/* Runs of difference closer together than this are emitted as one hunk.
   A hunk header costs more than a handful of unchanged bytes, so joining
   them produces a smaller patch. */
#define HAXPATCH_JOIN_GAP 16

// Long enough for the widest line the format permits, plus its newline.
#define HAXPATCH_LINE_MAX 1024

static const char haxpatch_hex[] = "0123456789abcdef";

static const char *const haxpatch_message[] = {
  "no error",
  "patch input or output failed",
  "malformed patch",
  "patch does not match the data it is applied to",
  "patch refers to data outside the image",
  "patch resizes the image"
};

const char *haxpatch_strerror(int result) {
  if (result < 0 || (size_t) result >= sizeof(haxpatch_message) /
      sizeof(haxpatch_message[0]))
    return "unknown error";

  return haxpatch_message[result];
}

static int haxpatch_nibble(int c) {
  if (c >= '0' && c <= '9')
    return c - '0';

  // The format calls for lower case, but upper case costs nothing to accept.
  if (c >= 'a' && c <= 'f')
    return c - 'a' + 10;
  if (c >= 'A' && c <= 'F')
    return c - 'A' + 10;

  return -1;
}

// Writes one '-' or '+' line holding len bytes of data.
static int haxpatch_put_line(FILE *out, int prefix, const uint8_t *data,
  size_t len) {
  char line[2 + HAXPATCH_LINE_BYTES * 2 + 2];
  size_t i;

  line[0] = (char) prefix;
  line[1] = ' ';

  for (i = 0; i < len; i++) {
    line[2 + i * 2] = haxpatch_hex[data[i] >> 4];
    line[3 + i * 2] = haxpatch_hex[data[i] & 0xF];
  }

  line[2 + len * 2] = '\n';

  if (fwrite(line, 1, len * 2 + 3, out) != len * 2 + 3)
    return HAXPATCH_IO;

  return HAXPATCH_OK;
}

static int haxpatch_put_run(FILE *out, int prefix, const uint8_t *data,
  size_t len) {
  size_t done = 0;

  while (done < len) {
    size_t n = len - done;
    int rc;

    if (n > HAXPATCH_LINE_BYTES)
      n = HAXPATCH_LINE_BYTES;

    if ((rc = haxpatch_put_line(out, prefix, data + done, n)) != HAXPATCH_OK)
      return rc;

    done += n;
  }

  return HAXPATCH_OK;
}

int haxpatch_write(FILE *out, const uint8_t *base, const uint8_t *mod,
  size_t size, int verify_lines) {
  size_t pos = 0;
  int started = 0;

  if (out == NULL || base == NULL || mod == NULL)
    return HAXPATCH_MALFORMED;

  while (pos < size) {
    size_t start, end, gap;
    int rc;

    if (base[pos] == mod[pos]) {
      pos++;
      continue;
    }

    /* Extend across every differing byte, and on across any run of equal
       bytes shorter than the gap threshold so that near neighbours share
       one hunk. */
    start = pos;
    end = pos;

    while (end < size) {
      if (base[end] != mod[end]) {
        end++;
        continue;
      }

      gap = end;

      while (gap < size && gap < end + HAXPATCH_JOIN_GAP &&
             base[gap] == mod[gap])
        gap++;

      if (gap >= size || gap - end >= HAXPATCH_JOIN_GAP)
        break;

      end = gap;
    }

    if (!started) {
      if (fputs("haxdiff/1.0\n", out) == EOF)
        return HAXPATCH_IO;

      started = 1;
    }

    if (fprintf(out, "@@ %llx,-%llx,+%llx @@\n",
        (unsigned long long) start,
        (unsigned long long) (end - start),
        (unsigned long long) (end - start)) < 0)
      return HAXPATCH_IO;

    if (verify_lines) {
      if ((rc = haxpatch_put_run(out, '-', base + start, end - start)))
        return rc;
    }

    if ((rc = haxpatch_put_run(out, '+', mod + start, end - start)))
      return rc;

    pos = end;
  }

  if (fflush(out) == EOF)
    return HAXPATCH_IO;

  return HAXPATCH_OK;
}

/* Parses a hunk header of the form "offset,-removed,+inserted", all
   hexadecimal and without any 0x prefix. The fields may be followed by
   an optional " @@" tail, which exists so that the line matches what
   unified diff syntax highlighting expects; it carries no information
   and a header without it parses just the same. */
static int haxpatch_parse_header(const char *p, unsigned long long *offset,
  unsigned long long *removed, unsigned long long *inserted) {
  unsigned long long *field[3];
  unsigned i;

  field[0] = offset;
  field[1] = removed;
  field[2] = inserted;

  for (i = 0; i < 3; i++) {
    int digits = 0;

    if (i == 1 && *p++ != '-')
      return HAXPATCH_MALFORMED;
    if (i == 2 && *p++ != '+')
      return HAXPATCH_MALFORMED;

    *field[i] = 0;

    while (haxpatch_nibble((unsigned char) *p) >= 0) {
      *field[i] = (*field[i] << 4) |
        (unsigned long long) haxpatch_nibble((unsigned char) *p);
      digits++;
      p++;
    }

    if (digits == 0)
      return HAXPATCH_MALFORMED;

    if (i < 2 && *p++ != ',')
      return HAXPATCH_MALFORMED;
  }

  if (*p == ' ') {
    if (p[1] != '@' || p[2] != '@')
      return HAXPATCH_MALFORMED;

    p += 3;
  }

  /* Nothing but the end of the line may follow. The reference reader
     stops at the last field and ignores the rest, so it would accept
     trailing text here that this one refuses. */
  if (*p == '\r')
    p++;

  if (*p != '\n' && *p != '\0')
    return HAXPATCH_MALFORMED;

  return HAXPATCH_OK;
}

/* Decodes a line of hexadecimal into out. Unlike the reference decoder
   this rejects anything that is not a hexadecimal digit rather than
   folding it into the output. */
static int haxpatch_decode(const char *p, uint8_t *out, size_t max,
  size_t *len) {
  size_t n = 0;

  while (*p != '\0' && *p != '\n' && *p != '\r') {
    int hi = haxpatch_nibble((unsigned char) p[0]);
    int lo;

    if (hi < 0)
      return HAXPATCH_MALFORMED;

    lo = haxpatch_nibble((unsigned char) p[1]);

    if (lo < 0)
      return HAXPATCH_MALFORMED;

    if (n >= max)
      return HAXPATCH_MALFORMED;

    out[n++] = (uint8_t) ((hi << 4) | lo);
    p += 2;
  }

  if (n == 0)
    return HAXPATCH_MALFORMED;

  *len = n;
  return HAXPATCH_OK;
}

int haxpatch_apply(FILE *in, uint8_t *image, size_t size, int verify) {
  char line[HAXPATCH_LINE_MAX];
  uint8_t data[HAXPATCH_LINE_MAX / 2];
  unsigned long long minus_at = 0, plus_at = 0;
  unsigned long long minus_left = 0, plus_left = 0;
  int in_hunk = 0, minus_seen = 0;

  if (in == NULL || image == NULL)
    return HAXPATCH_MALFORMED;

  while (fgets(line, sizeof(line), in) != NULL) {
    size_t len = strlen(line);
    unsigned long long offset, removed, inserted;
    size_t got;
    int rc;

    /* A line the buffer could not hold would otherwise be split, and the
       remainder silently read as a comment. Refuse it instead. */
    if (len + 1 == sizeof(line) && line[len - 1] != '\n')
      return HAXPATCH_MALFORMED;

    if (line[0] == '@') {
      if (line[1] != '@' || line[2] != ' ')
        return HAXPATCH_MALFORMED;

      // The hunk before this one has to have delivered what it promised.
      if (in_hunk && (plus_left != 0 || (minus_seen && minus_left != 0)))
        return HAXPATCH_MALFORMED;

      if ((rc = haxpatch_parse_header(line + 3, &offset, &removed, &inserted)))
        return rc;

      // Every hunk here replaces bytes in place; the image cannot resize.
      if (removed != inserted)
        return HAXPATCH_UNSUPPORTED;

      if (offset > size || inserted > size - offset)
        return HAXPATCH_RANGE;

      minus_at = plus_at = offset;
      minus_left = plus_left = inserted;
      in_hunk = 1;
      minus_seen = 0;
      continue;
    }

    if (line[0] == '-' || line[0] == '+') {
      if (!in_hunk || line[1] != ' ')
        return HAXPATCH_MALFORMED;

      if ((rc = haxpatch_decode(line + 2, data, sizeof(data), &got)))
        return rc;

      if (line[0] == '-') {
        // The '-' lines are optional, but may not exceed the hunk.
        if (got > minus_left)
          return HAXPATCH_MALFORMED;

        if (verify && memcmp(image + minus_at, data, got) != 0)
          return HAXPATCH_MISMATCH;

        minus_at += got;
        minus_left -= got;
        minus_seen = 1;
      }

      else {
        if (got > plus_left)
          return HAXPATCH_MALFORMED;

        memcpy(image + plus_at, data, got);
        plus_at += got;
        plus_left -= got;
      }

      continue;
    }

    // Anything else, the version banner included, is a comment.
  }

  if (ferror(in))
    return HAXPATCH_IO;

  /* The last hunk must also be complete. Omitting the '-' lines entirely
     is allowed by the format; supplying only some of them is not. */
  if (in_hunk && (plus_left != 0 || (minus_seen && minus_left != 0)))
    return HAXPATCH_MALFORMED;

  return HAXPATCH_OK;
}

#endif // HAXPATCH_IMPLEMENTATION