src/delta-apply.c

   1 /*
   2  * Copyright (C) 2009-2011 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_apply(
  40         git_rawobj *out,
  41         const unsigned char *base,
  42         size_t base_len,
  43         const unsigned char *delta,
  44         size_t delta_len)
  45 {
  46         const unsigned char *delta_end = delta + delta_len;
  47         size_t base_sz, res_sz;
  48         unsigned char *res_dp;
  49
  50         /* Check that the base size matches the data we were given;
  51          * if not we would underflow while accessing data from the
  52          * base object, resulting in data corruption or segfault.
  53          */
  54         if ((hdr_sz(&base_sz, &delta, delta_end) < 0) || (base_sz != base_len))
  55                 return git__throw(GIT_ERROR, "Failed to apply delta. Base size does not match given data");
  56
  57         if (hdr_sz(&res_sz, &delta, delta_end) < 0)
  58                 return git__throw(GIT_ERROR, "Failed to apply delta. Base size does not match given data");
  59
  60         if ((res_dp = git__malloc(res_sz + 1)) == NULL)
  61                 return GIT_ENOMEM;
  62         res_dp[res_sz] = '\0';
  63         out->data = res_dp;
  64         out->len = res_sz;
  65
  66         while (delta < delta_end) {
  67                 unsigned char cmd = *delta++;
  68                 if (cmd & 0x80) {
  69                         /* cmd is a copy instruction; copy from the base.
  70                          */
  71                         size_t off = 0, len = 0;
  72
  73                         if (cmd & 0x01) off = *delta++;
  74                         if (cmd & 0x02) off |= *delta++ << 8;
  75                         if (cmd & 0x04) off |= *delta++ << 16;
  76                         if (cmd & 0x08) off |= *delta++ << 24;
  77
  78                         if (cmd & 0x10) len = *delta++;
  79                         if (cmd & 0x20) len |= *delta++ << 8;
  80                         if (cmd & 0x40) len |= *delta++ << 16;
  81                         if (!len)               len = 0x10000;
  82
  83                         if (base_len < off + len || res_sz < len)
  84                                 goto fail;
  85                         memcpy(res_dp, base + off, len);
  86                         res_dp += len;
  87                         res_sz -= len;
  88
  89                 } else if (cmd) {
  90                         /* cmd is a literal insert instruction; copy from
  91                          * the delta stream itself.
  92                          */
  93                         if (delta_end - delta < cmd || res_sz < cmd)
  94                                 goto fail;
  95                         memcpy(res_dp, delta, cmd);
  96                         delta += cmd;
  97                         res_dp += cmd;
  98                         res_sz -= cmd;
  99
 100                 } else {
 101                         /* cmd == 0 is reserved for future encodings.
 102                          */
 103                         goto fail;
 104                 }
 105         }
 106
 107         if (delta != delta_end || res_sz)
 108                 goto fail;
 109         return GIT_SUCCESS;
 110
 111 fail:
 112         git__free(out->data);
 113         out->data = NULL;
 114         return git__throw(GIT_ERROR, "Failed to apply delta");
 115 }