src/delta-apply.c

   1 /*
   2  * Copyright (C) 2009-2012 the libgit2 contributors
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7 #include "common.h"
   8 #include "git2/odb.h"
   9 #include "delta-apply.h"
  10
  11 /*
  12  * This file was heavily cribbed from BinaryDelta.java in JGit, which
  13  * itself was heavily cribbed from <code>patch-delta.c</code> in the
  14  * GIT project. The original delta patching code was written by
  15  * Nicolas Pitre <nico@cam.org>.
  16  */
  17
  18 static int hdr_sz(
  19         size_t *size,
  20         const unsigned char **delta,
  21         const unsigned char *end)
  22 {
  23         const unsigned char *d = *delta;
  24         size_t r = 0;
  25         unsigned int c, shift = 0;
  26
  27         do {
  28                 if (d == end)
  29                         return -1;
  30                 c = *d++;
  31                 r |= (c & 0x7f) << shift;
  32                 shift += 7;
  33         } while (c & 0x80);
  34         *delta = d;
  35         *size = r;
  36         return 0;
  37 }
  38
  39 int git__delta_read_header(
  40         const unsigned char *delta,
  41         size_t delta_len,
  42         size_t *base_sz,
  43         size_t *res_sz)
  44 {
  45         const unsigned char *delta_end = delta + delta_len;
  46         if ((hdr_sz(base_sz, &delta, delta_end) < 0) ||
  47             (hdr_sz(res_sz, &delta, delta_end) < 0))
  48                 return -1;
  49         return 0;
  50 }
  51
  52 int git__delta_apply(
  53         git_rawobj *out,
  54         const unsigned char *base,
  55         size_t base_len,
  56         const unsigned char *delta,
  57         size_t delta_len)
  58 {
  59         const unsigned char *delta_end = delta + delta_len;
  60         size_t base_sz, res_sz;
  61         unsigned char *res_dp;
  62
  63         /* Check that the base size matches the data we were given;
  64          * if not we would underflow while accessing data from the
  65          * base object, resulting in data corruption or segfault.
  66          */
  67         if ((hdr_sz(&base_sz, &delta, delta_end) < 0) || (base_sz != base_len)) {
  68                 giterr_set(GITERR_INVALID, "Failed to apply delta. Base size does not match given data");
  69                 return -1;
  70         }
  71
  72         if (hdr_sz(&res_sz, &delta, delta_end) < 0) {
  73                 giterr_set(GITERR_INVALID, "Failed to apply delta. Base size does not match given data");
  74                 return -1;
  75         }
  76
  77         res_dp = git__malloc(res_sz + 1);
  78         GITERR_CHECK_ALLOC(res_dp);
  79
  80         res_dp[res_sz] = '\0';
  81         out->data = res_dp;
  82         out->len = res_sz;
  83
  84         while (delta < delta_end) {
  85                 unsigned char cmd = *delta++;
  86                 if (cmd & 0x80) {
  87                         /* cmd is a copy instruction; copy from the base.
  88                          */
  89                         size_t off = 0, len = 0;
  90
  91                         if (cmd & 0x01) off = *delta++;
  92                         if (cmd & 0x02) off |= *delta++ << 8;
  93                         if (cmd & 0x04) off |= *delta++ << 16;
  94                         if (cmd & 0x08) off |= *delta++ << 24;
  95
  96                         if (cmd & 0x10) len = *delta++;
  97                         if (cmd & 0x20) len |= *delta++ << 8;
  98                         if (cmd & 0x40) len |= *delta++ << 16;
  99                         if (!len)               len = 0x10000;
 100
 101                         if (base_len < off + len || res_sz < len)
 102                                 goto fail;
 103                         memcpy(res_dp, base + off, len);
 104                         res_dp += len;
 105                         res_sz -= len;
 106
 107                 } else if (cmd) {
 108                         /* cmd is a literal insert instruction; copy from
 109                          * the delta stream itself.
 110                          */
 111                         if (delta_end - delta < cmd || res_sz < cmd)
 112                                 goto fail;
 113                         memcpy(res_dp, delta, cmd);
 114                         delta += cmd;
 115                         res_dp += cmd;
 116                         res_sz -= cmd;
 117
 118                 } else {
 119                         /* cmd == 0 is reserved for future encodings.
 120                          */
 121                         goto fail;
 122                 }
 123         }
 124
 125         if (delta != delta_end || res_sz)
 126                 goto fail;
 127         return 0;
 128
 129 fail:
 130         git__free(out->data);
 131         out->data = NULL;
 132         giterr_set(GITERR_INVALID, "Failed to apply delta");
 133         return -1;
 134 }