src/delta-apply.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   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, alloc_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         GITERR_CHECK_ALLOC_ADD(&alloc_sz, res_sz, 1);
  78         res_dp = git__malloc(alloc_sz);
  79         GITERR_CHECK_ALLOC(res_dp);
  80
  81         res_dp[res_sz] = '\0';
  82         out->data = res_dp;
  83         out->len = res_sz;
  84
  85         while (delta < delta_end) {
  86                 unsigned char cmd = *delta++;
  87                 if (cmd & 0x80) {
  88                         /* cmd is a copy instruction; copy from the base.
  89                          */
  90                         size_t off = 0, len = 0;
  91
  92                         if (cmd & 0x01) off = *delta++;
  93                         if (cmd & 0x02) off |= *delta++ << 8;
  94                         if (cmd & 0x04) off |= *delta++ << 16;
  95                         if (cmd & 0x08) off |= *delta++ << 24;
  96
  97                         if (cmd & 0x10) len = *delta++;
  98                         if (cmd & 0x20) len |= *delta++ << 8;
  99                         if (cmd & 0x40) len |= *delta++ << 16;
 100                         if (!len)               len = 0x10000;
 101
 102                         if (base_len < off + len || res_sz < len)
 103                                 goto fail;
 104                         memcpy(res_dp, base + off, len);
 105                         res_dp += len;
 106                         res_sz -= len;
 107
 108                 } else if (cmd) {
 109                         /* cmd is a literal insert instruction; copy from
 110                          * the delta stream itself.
 111                          */
 112                         if (delta_end - delta < cmd || res_sz < cmd)
 113                                 goto fail;
 114                         memcpy(res_dp, delta, cmd);
 115                         delta += cmd;
 116                         res_dp += cmd;
 117                         res_sz -= cmd;
 118
 119                 } else {
 120                         /* cmd == 0 is reserved for future encodings.
 121                          */
 122                         goto fail;
 123                 }
 124         }
 125
 126         if (delta != delta_end || res_sz)
 127                 goto fail;
 128         return 0;
 129
 130 fail:
 131         git__free(out->data);
 132         out->data = NULL;
 133         giterr_set(GITERR_INVALID, "Failed to apply delta");
 134         return -1;
 135 }