dulwich/_pack.c

   1 /*
   2  * Copyright (C) 2009 Jelmer Vernooij <jelmer@samba.org>
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; version 2
   7  * of the License or (at your option) a later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  17  * MA  02110-1301, USA.
  18  */
  19
  20 #include <Python.h>
  21 #include <stdint.h>
  22
  23 static int py_is_sha(PyObject *sha)
  24 {
  25     if (!PyString_CheckExact(sha))
  26         return 0;
  27
  28     if (PyString_Size(sha) != 20)
  29         return 0;
  30
  31     return 1;
  32 }
  33
  34
  35 static size_t get_delta_header_size(uint8_t *delta, int *index, int length)
  36 {
  37         size_t size = 0;
  38         int i = 0;
  39         while ((*index) < length) {
  40                 uint8_t cmd = delta[*index];
  41                 (*index)++;
  42                 size |= (cmd & ~0x80) << i;
  43                 i += 7;
  44                 if (!(cmd & 0x80))
  45                         break;
  46         }
  47         return size;
  48 }
  49
  50 static PyObject *py_chunked_as_string(PyObject *py_buf)
  51 {
  52         if (PyList_Check(py_buf)) {
  53                 PyObject *sep = PyString_FromString("");
  54                 if (sep == NULL) {
  55                         PyErr_NoMemory();
  56                         return NULL;
  57                 }
  58                 py_buf = _PyString_Join(sep, py_buf);
  59                 Py_DECREF(sep);
  60                 if (py_buf == NULL) {
  61                         PyErr_NoMemory();
  62                         return NULL;
  63                 }
  64         } else if (PyString_Check(py_buf)) {
  65                 Py_INCREF(py_buf);
  66         } else {
  67                 PyErr_SetString(PyExc_TypeError,
  68                         "src_buf is not a string or a list of chunks");
  69                 return NULL;
  70         }
  71     return py_buf;
  72 }
  73
  74 static PyObject *py_apply_delta(PyObject *self, PyObject *args)
  75 {
  76         uint8_t *src_buf, *delta;
  77         int src_buf_len, delta_len;
  78         size_t src_size, dest_size;
  79         size_t outindex = 0;
  80         int index;
  81         uint8_t *out;
  82         PyObject *ret, *py_src_buf, *py_delta;
  83
  84         if (!PyArg_ParseTuple(args, "OO", &py_src_buf, &py_delta))
  85                 return NULL;
  86
  87     py_src_buf = py_chunked_as_string(py_src_buf);
  88     if (py_src_buf == NULL)
  89         return NULL;
  90
  91     py_delta = py_chunked_as_string(py_delta);
  92     if (py_delta == NULL) {
  93         Py_DECREF(py_src_buf);
  94         return NULL;
  95     }
  96
  97         src_buf = (uint8_t *)PyString_AS_STRING(py_src_buf);
  98         src_buf_len = PyString_GET_SIZE(py_src_buf);
  99
 100     delta = (uint8_t *)PyString_AS_STRING(py_delta);
 101     delta_len = PyString_GET_SIZE(py_delta);
 102
 103     index = 0;
 104     src_size = get_delta_header_size(delta, &index, delta_len);
 105     if (src_size != src_buf_len) {
 106                 PyErr_Format(PyExc_ValueError,
 107                         "Unexpected source buffer size: %lu vs %d", src_size, src_buf_len);
 108                 Py_DECREF(py_src_buf);
 109                 Py_DECREF(py_delta);
 110                 return NULL;
 111         }
 112     dest_size = get_delta_header_size(delta, &index, delta_len);
 113         ret = PyString_FromStringAndSize(NULL, dest_size);
 114         if (ret == NULL) {
 115                 PyErr_NoMemory();
 116                 Py_DECREF(py_src_buf);
 117                 Py_DECREF(py_delta);
 118                 return NULL;
 119         }
 120         out = (uint8_t *)PyString_AsString(ret);
 121     while (index < delta_len) {
 122         char cmd = delta[index];
 123         index++;
 124         if (cmd & 0x80) {
 125             size_t cp_off = 0, cp_size = 0;
 126                         int i;
 127             for (i = 0; i < 4; i++) {
 128                 if (cmd & (1 << i)) {
 129                     uint8_t x = delta[index];
 130                     index++;
 131                     cp_off |= x << (i * 8);
 132                                 }
 133                         }
 134             for (i = 0; i < 3; i++) {
 135                 if (cmd & (1 << (4+i))) {
 136                     uint8_t x = delta[index];
 137                     index++;
 138                     cp_size |= x << (i * 8);
 139                                 }
 140                         }
 141             if (cp_size == 0)
 142                 cp_size = 0x10000;
 143             if (cp_off + cp_size < cp_size ||
 144                 cp_off + cp_size > src_size ||
 145                 cp_size > dest_size)
 146                 break;
 147                         memcpy(out+outindex, src_buf+cp_off, cp_size);
 148                         outindex += cp_size;
 149                 } else if (cmd != 0) {
 150                         memcpy(out+outindex, delta+index, cmd);
 151                         outindex += cmd;
 152             index += cmd;
 153                 } else {
 154                         PyErr_SetString(PyExc_ValueError, "Invalid opcode 0");
 155                         Py_DECREF(ret);
 156             Py_DECREF(py_delta);
 157                         Py_DECREF(py_src_buf);
 158                         return NULL;
 159                 }
 160         }
 161         Py_DECREF(py_src_buf);
 162     Py_DECREF(py_delta);
 163
 164     if (index != delta_len) {
 165                 PyErr_SetString(PyExc_ValueError, "delta not empty");
 166                 Py_DECREF(ret);
 167                 return NULL;
 168         }
 169
 170         if (dest_size != outindex) {
 171         PyErr_SetString(PyExc_ValueError, "dest size incorrect");
 172                 Py_DECREF(ret);
 173                 return NULL;
 174         }
 175
 176     return Py_BuildValue("[N]", ret);
 177 }
 178
 179 static PyObject *py_bisect_find_sha(PyObject *self, PyObject *args)
 180 {
 181     PyObject *unpack_name;
 182     char *sha;
 183     int sha_len;
 184         int start, end;
 185     if (!PyArg_ParseTuple(args, "iis#O", &start, &end,
 186                                                   &sha, &sha_len, &unpack_name))
 187         return NULL;
 188
 189     if (sha_len != 20) {
 190         PyErr_SetString(PyExc_ValueError, "Sha is not 20 bytes long");
 191         return NULL;
 192     }
 193     if (start > end) {
 194         PyErr_SetString(PyExc_AssertionError, "start > end");
 195         return NULL;
 196     }
 197
 198     while (start <= end) {
 199         PyObject *file_sha;
 200         int i = (start + end)/2;
 201         int cmp;
 202         file_sha = PyObject_CallFunction(unpack_name, "i", i);
 203         if (file_sha == NULL) {
 204             return NULL;
 205         }
 206         if (!py_is_sha(file_sha)) {
 207             PyErr_SetString(PyExc_TypeError, "unpack_name returned non-sha object");
 208                         Py_DECREF(file_sha);
 209             return NULL;
 210         }
 211         cmp = memcmp(PyString_AsString(file_sha), sha, 20);
 212                 Py_DECREF(file_sha);
 213         if (cmp < 0)
 214             start = i + 1;
 215         else if (cmp > 0)
 216             end = i - 1;
 217         else {
 218                         return PyInt_FromLong(i);
 219         }
 220     }
 221     Py_RETURN_NONE;
 222 }
 223
 224
 225 static PyMethodDef py_pack_methods[] = {
 226         { "apply_delta", (PyCFunction)py_apply_delta, METH_VARARGS, NULL },
 227         { "bisect_find_sha", (PyCFunction)py_bisect_find_sha, METH_VARARGS, NULL },
 228         { NULL, NULL, 0, NULL }
 229 };
 230
 231 void init_pack(void)
 232 {
 233         PyObject *m;
 234
 235         m = Py_InitModule3("_pack", py_pack_methods, NULL);
 236         if (m == NULL)
 237                 return;
 238 }