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 size_t hdr_sz(
  13         const unsigned char **delta,
  14         const unsigned char *end)
  15 {
  16         const unsigned char *d = *delta;
  17         size_t r = 0;
  18         unsigned int c, shift = 0;
  19
  20         do {
  21                 if (d == end)
  22                         return -1;
  23                 c = *d++;
  24                 r |= (c & 0x7f) << shift;
  25                 shift += 7;
  26         } while (c & 0x80);
  27         *delta = d;
  28         return r;
  29 }
  30
  31 int git__delta_apply(
  32         git_obj *out,
  33         const unsigned char *base,
  34         size_t base_len,
  35         const unsigned char *delta,
  36         size_t delta_len)
  37 {
  38         const unsigned char *delta_end = delta + delta_len;
  39         size_t res_sz;
  40         unsigned char *res_dp;
  41
  42         /* Check that the base size matches the data we were given;
  43          * if not we would underflow while accessing data from the
  44          * base object, resulting in data corruption or segfault.
  45          */
  46         if (base_len != hdr_sz(&delta, delta_end))
  47                 return GIT_ERROR;
  48
  49         res_sz = hdr_sz(&delta, delta_end);
  50         if ((res_dp = git__malloc(res_sz + 1)) == NULL)
  51                 return GIT_ERROR;
  52         res_dp[res_sz] = '\0';
  53         out->data = res_dp;
  54         out->len = res_sz;
  55
  56         while (delta < delta_end) {
  57                 unsigned char cmd = *delta++;
  58                 if (cmd & 0x80) {
  59                         /* cmd is a copy instruction; copy from the base.
  60                          */
  61                         size_t off = 0, len = 0;
  62
  63                         if (cmd & 0x01) off  = *delta++;
  64                         if (cmd & 0x02) off |= *delta++ <<  8;
  65                         if (cmd & 0x04) off |= *delta++ << 16;
  66                         if (cmd & 0x08) off |= *delta++ << 24;
  67
  68                         if (cmd & 0x10) len  = *delta++;
  69                         if (cmd & 0x20) len |= *delta++ <<  8;
  70                         if (cmd & 0x40) len |= *delta++ << 16;
  71                         if (!len)       len  = 0x10000;
  72
  73                         if (base_len < off + len || res_sz < len)
  74                                 goto fail;
  75                         memcpy(res_dp, base + off, len);
  76                         res_dp += len;
  77                         res_sz -= len;
  78
  79                 } else if (cmd) {
  80                         /* cmd is a literal insert instruction; copy from
  81                          * the delta stream itself.
  82                          */
  83                         if (delta_end - delta < cmd || res_sz < cmd)
  84                                 goto fail;
  85                         memcpy(res_dp, delta, cmd);
  86                         delta  += cmd;
  87                         res_dp += cmd;
  88                         res_sz -= cmd;
  89
  90                 } else {
  91                         /* cmd == 0 is reserved for future encodings.
  92                          */
  93                         goto fail;
  94                 }
  95         }
  96
  97         if (delta != delta_end || res_sz)
  98                 goto fail;
  99         return GIT_SUCCESS;
 100
 101 fail:
 102         free(out->data);
 103         out->data = NULL;
 104         return GIT_ERROR;
 105 }