src/delta-apply.c

   1 #include "common.h"
   2 #include "git/odb.h"
   3 #include "delta-apply.h"
   4
   5 /*
   6  * This file was heavily cribbed from BinaryDelta.java in JGit, which
   7  * itself was heavily cribbed from <code>patch-delta.c</code> in the
   8  * GIT project.   The original delta patching code was written by
   9  * Nicolas Pitre <nico@cam.org>.
  10  */
  11
  12 static int hdr_sz(
  13         size_t *size,
  14         const unsigned char **delta,
  15         const unsigned char *end)
  16 {
  17         const unsigned char *d = *delta;
  18         size_t r = 0;
  19         unsigned int c, shift = 0;
  20
  21         do {
  22                 if (d == end)
  23                         return -1;
  24                 c = *d++;
  25                 r |= (c & 0x7f) << shift;
  26                 shift += 7;
  27         } while (c & 0x80);
  28         *delta = d;
  29         *size = r;
  30         return 0;
  31 }
  32
  33 int git__delta_apply(
  34         git_obj *out,
  35         const unsigned char *base,
  36         size_t base_len,
  37         const unsigned char *delta,
  38         size_t delta_len)
  39 {
  40         const unsigned char *delta_end = delta + delta_len;
  41         size_t base_sz, res_sz;
  42         unsigned char *res_dp;
  43
  44         /* Check that the base size matches the data we were given;
  45          * if not we would underflow while accessing data from the
  46          * base object, resulting in data corruption or segfault.
  47          */
  48         if ((hdr_sz(&base_sz, &delta, delta_end) < 0) || (base_sz != base_len))
  49                 return GIT_ERROR;
  50
  51         if (hdr_sz(&res_sz, &delta, delta_end) < 0)
  52                 return GIT_ERROR;
  53
  54         if ((res_dp = git__malloc(res_sz + 1)) == NULL)
  55                 return GIT_ERROR;
  56         res_dp[res_sz] = '\0';
  57         out->data = res_dp;
  58         out->len = res_sz;
  59
  60         while (delta < delta_end) {
  61                 unsigned char cmd = *delta++;
  62                 if (cmd & 0x80) {
  63                         /* cmd is a copy instruction; copy from the base.
  64                          */
  65                         size_t off = 0, len = 0;
  66
  67                         if (cmd & 0x01) off  = *delta++;
  68                         if (cmd & 0x02) off |= *delta++ <<  8;
  69                         if (cmd & 0x04) off |= *delta++ << 16;
  70                         if (cmd & 0x08) off |= *delta++ << 24;
  71
  72                         if (cmd & 0x10) len  = *delta++;
  73                         if (cmd & 0x20) len |= *delta++ <<  8;
  74                         if (cmd & 0x40) len |= *delta++ << 16;
  75                         if (!len)       len  = 0x10000;
  76
  77                         if (base_len < off + len || res_sz < len)
  78                                 goto fail;
  79                         memcpy(res_dp, base + off, len);
  80                         res_dp += len;
  81                         res_sz -= len;
  82
  83                 } else if (cmd) {
  84                         /* cmd is a literal insert instruction; copy from
  85                          * the delta stream itself.
  86                          */
  87                         if (delta_end - delta < cmd || res_sz < cmd)
  88                                 goto fail;
  89                         memcpy(res_dp, delta, cmd);
  90                         delta  += cmd;
  91                         res_dp += cmd;
  92                         res_sz -= cmd;
  93
  94                 } else {
  95                         /* cmd == 0 is reserved for future encodings.
  96                          */
  97                         goto fail;
  98                 }
  99         }
 100
 101         if (delta != delta_end || res_sz)
 102                 goto fail;
 103         return GIT_SUCCESS;
 104
 105 fail:
 106         free(out->data);
 107         out->data = NULL;
 108         return GIT_ERROR;
 109 }