Andrew's git - gitweb.git/blob

   1/*
   2 * diff-delta.c: generate a delta between two buffers
   3 *
   4 *  Many parts of this file have been lifted from LibXDiff version 0.10.
   5 *  http://www.xmailserver.org/xdiff-lib.html
   6 *
   7 *  LibXDiff was written by Davide Libenzi <davidel@xmailserver.org>
   8 *  Copyright (C) 2003  Davide Libenzi
   9 *
  10 *  Many mods for GIT usage by Nicolas Pitre <nico@cam.org>, (C) 2005.
  11 *
  12 *  This file is free software; you can redistribute it and/or
  13 *  modify it under the terms of the GNU Lesser General Public
  14 *  License as published by the Free Software Foundation; either
  15 *  version 2.1 of the License, or (at your option) any later version.
  16 *
  17 *  Use of this within git automatically means that the LGPL
  18 *  licensing gets turned into GPLv2 within this project.
  19 */
  20
  21#include <stdlib.h>
  22#include <string.h>
  23#include <zlib.h>
  24#include "delta.h"
  25
  26
  27/* block size: min = 16, max = 64k, power of 2 */
  28#define BLK_SIZE 16
  29
  30#define MIN(a, b) ((a) < (b) ? (a) : (b))
  31
  32#define GR_PRIME 0x9e370001
  33#define HASH(v, shift) (((unsigned int)(v) * GR_PRIME) >> (shift))
  34
  35struct index {
  36        const unsigned char *ptr;
  37        unsigned int val;
  38        struct index *next;
  39};
  40
  41static struct index ** delta_index(const unsigned char *buf,
  42                                   unsigned long bufsize,
  43                                   unsigned long trg_bufsize,
  44                                   unsigned int *hash_shift)
  45{
  46        unsigned int i, hsize, hshift, hlimit, entries, *hash_count;
  47        const unsigned char *data;
  48        struct index *entry, **hash;
  49        void *mem;
  50
  51        /* determine index hash size */
  52        entries = bufsize  / BLK_SIZE;
  53        hsize = entries / 4;
  54        for (i = 4; (1 << i) < hsize && i < 31; i++);
  55        hsize = 1 << i;
  56        hshift = 32 - i;
  57        *hash_shift = hshift;
  58
  59        /* allocate lookup index */
  60        mem = malloc(hsize * sizeof(*hash) + entries * sizeof(*entry));
  61        if (!mem)
  62                return NULL;
  63        hash = mem;
  64        entry = mem + hsize * sizeof(*hash);
  65        memset(hash, 0, hsize * sizeof(*hash));
  66
  67        /* allocate an array to count hash entries */
  68        hash_count = calloc(hsize, sizeof(*hash_count));
  69        if (!hash_count) {
  70                free(hash);
  71                return NULL;
  72        }
  73
  74        /* then populate the index */
  75        data = buf + entries * BLK_SIZE - BLK_SIZE;
  76        while (data >= buf) {
  77                unsigned int val = adler32(0, data, BLK_SIZE);
  78                i = HASH(val, hshift);
  79                entry->ptr = data;
  80                entry->val = val;
  81                entry->next = hash[i];
  82                hash[i] = entry++;
  83                hash_count[i]++;
  84                data -= BLK_SIZE;
  85        }
  86
  87        /*
  88         * Determine a limit on the number of entries in the same hash
  89         * bucket.  This guard us against patological data sets causing
  90         * really bad hash distribution with most entries in the same hash
  91         * bucket that would bring us to O(m*n) computing costs (m and n
  92         * corresponding to reference and target buffer sizes).
  93         *
  94         * The more the target buffer is large, the more it is important to
  95         * have small entry lists for each hash buckets.  With such a limit
  96         * the cost is bounded to something more like O(m+n).
  97         */
  98        hlimit = (1 << 26) / trg_bufsize;
  99        if (hlimit < 4*BLK_SIZE)
 100                hlimit = 4*BLK_SIZE;
 101
 102        /*
 103         * Now make sure none of the hash buckets has more entries than
 104         * we're willing to test.  Otherwise we cull the entry list
 105         * uniformly to still preserve a good repartition across
 106         * the reference buffer.
 107         */
 108        for (i = 0; i < hsize; i++) {
 109                if (hash_count[i] < hlimit)
 110                        continue;
 111                entry = hash[i];
 112                do {
 113                        struct index *keep = entry;
 114                        int skip = hash_count[i] / hlimit / 2;
 115                        do {
 116                                entry = entry->next;
 117                        } while(--skip && entry);
 118                        keep->next = entry;
 119                } while(entry);
 120        }
 121        free(hash_count);
 122
 123        return hash;
 124}
 125
 126/* provide the size of the copy opcode given the block offset and size */
 127#define COPYOP_SIZE(o, s) \
 128    (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \
 129     !!(s & 0xff) + !!(s & 0xff00) + 1)
 130
 131/* the maximum size for any opcode */
 132#define MAX_OP_SIZE COPYOP_SIZE(0xffffffff, 0xffffffff)
 133
 134void *diff_delta(void *from_buf, unsigned long from_size,
 135                 void *to_buf, unsigned long to_size,
 136                 unsigned long *delta_size,
 137                 unsigned long max_size)
 138{
 139        unsigned int i, outpos, outsize, hash_shift;
 140        int inscnt;
 141        const unsigned char *ref_data, *ref_top, *data, *top;
 142        unsigned char *out;
 143        struct index *entry, **hash;
 144
 145        if (!from_size || !to_size)
 146                return NULL;
 147        hash = delta_index(from_buf, from_size, to_size, &hash_shift);
 148        if (!hash)
 149                return NULL;
 150
 151        outpos = 0;
 152        outsize = 8192;
 153        if (max_size && outsize >= max_size)
 154                outsize = max_size + MAX_OP_SIZE + 1;
 155        out = malloc(outsize);
 156        if (!out) {
 157                free(hash);
 158                return NULL;
 159        }
 160
 161        ref_data = from_buf;
 162        ref_top = from_buf + from_size;
 163        data = to_buf;
 164        top = to_buf + to_size;
 165
 166        /* store reference buffer size */
 167        out[outpos++] = from_size;
 168        from_size >>= 7;
 169        while (from_size) {
 170                out[outpos - 1] |= 0x80;
 171                out[outpos++] = from_size;
 172                from_size >>= 7;
 173        }
 174
 175        /* store target buffer size */
 176        out[outpos++] = to_size;
 177        to_size >>= 7;
 178        while (to_size) {
 179                out[outpos - 1] |= 0x80;
 180                out[outpos++] = to_size;
 181                to_size >>= 7;
 182        }
 183
 184        inscnt = 0;
 185
 186        while (data < top) {
 187                unsigned int moff = 0, msize = 0;
 188                if (data + BLK_SIZE <= top) {
 189                        unsigned int val = adler32(0, data, BLK_SIZE);
 190                        i = HASH(val, hash_shift);
 191                        for (entry = hash[i]; entry; entry = entry->next) {
 192                                const unsigned char *ref = entry->ptr;
 193                                const unsigned char *src = data;
 194                                unsigned int ref_size = ref_top - ref;
 195                                if (entry->val != val)
 196                                        continue;
 197                                if (ref_size > top - src)
 198                                        ref_size = top - src;
 199                                if (ref_size > 0x10000)
 200                                        ref_size = 0x10000;
 201                                if (ref_size <= msize)
 202                                        break;
 203                                while (ref_size-- && *src++ == *ref)
 204                                        ref++;
 205                                if (msize < ref - entry->ptr) {
 206                                        /* this is our best match so far */
 207                                        msize = ref - entry->ptr;
 208                                        moff = entry->ptr - ref_data;
 209                                }
 210                        }
 211                }
 212
 213                if (!msize || msize < COPYOP_SIZE(moff, msize)) {
 214                        if (!inscnt)
 215                                outpos++;
 216                        out[outpos++] = *data++;
 217                        inscnt++;
 218                        if (inscnt == 0x7f) {
 219                                out[outpos - inscnt - 1] = inscnt;
 220                                inscnt = 0;
 221                        }
 222                } else {
 223                        unsigned char *op;
 224
 225                        if (inscnt) {
 226                                while (moff && ref_data[moff-1] == data[-1]) {
 227                                        if (msize == 0x10000)
 228                                                break;
 229                                        /* we can match one byte back */
 230                                        msize++;
 231                                        moff--;
 232                                        data--;
 233                                        outpos--;
 234                                        if (--inscnt)
 235                                                continue;
 236                                        outpos--;  /* remove count slot */
 237                                        inscnt--;  /* make it -1 */
 238                                        break;
 239                                }
 240                                out[outpos - inscnt - 1] = inscnt;
 241                                inscnt = 0;
 242                        }
 243
 244                        data += msize;
 245                        op = out + outpos++;
 246                        i = 0x80;
 247
 248                        if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }
 249                        moff >>= 8;
 250                        if (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }
 251                        moff >>= 8;
 252                        if (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }
 253                        moff >>= 8;
 254                        if (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }
 255
 256                        if (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }
 257                        msize >>= 8;
 258                        if (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }
 259
 260                        *op = i;
 261                }
 262
 263                if (outpos >= outsize - MAX_OP_SIZE) {
 264                        void *tmp = out;
 265                        outsize = outsize * 3 / 2;
 266                        if (max_size && outsize >= max_size)
 267                                outsize = max_size + MAX_OP_SIZE + 1;
 268                        if (max_size && outpos > max_size)
 269                                out = NULL;
 270                        else
 271                                out = realloc(out, outsize);
 272                        if (!out) {
 273                                free(tmp);
 274                                free(hash);
 275                                return NULL;
 276                        }
 277                }
 278        }
 279
 280        if (inscnt)
 281                out[outpos - inscnt - 1] = inscnt;
 282
 283        free(hash);
 284        *delta_size = outpos;
 285        return out;
 286}