diffcore-delta.con commit conditional markdown preprocessing (c8b1cd9)
   1#include "cache.h"
   2#include "diff.h"
   3#include "diffcore.h"
   4
   5/*
   6 * Idea here is very simple.
   7 *
   8 * Almost all data we are interested in are text, but sometimes we have
   9 * to deal with binary data.  So we cut them into chunks delimited by
  10 * LF byte, or 64-byte sequence, whichever comes first, and hash them.
  11 *
  12 * For those chunks, if the source buffer has more instances of it
  13 * than the destination buffer, that means the difference are the
  14 * number of bytes not copied from source to destination.  If the
  15 * counts are the same, everything was copied from source to
  16 * destination.  If the destination has more, everything was copied,
  17 * and destination added more.
  18 *
  19 * We are doing an approximation so we do not really have to waste
  20 * memory by actually storing the sequence.  We just hash them into
  21 * somewhere around 2^16 hashbuckets and count the occurrences.
  22 */
  23
  24/* Wild guess at the initial hash size */
  25#define INITIAL_HASH_SIZE 9
  26
  27/* We leave more room in smaller hash but do not let it
  28 * grow to have unused hole too much.
  29 */
  30#define INITIAL_FREE(sz_log2) ((1<<(sz_log2))*(sz_log2-3)/(sz_log2))
  31
  32/* A prime rather carefully chosen between 2^16..2^17, so that
  33 * HASHBASE < INITIAL_FREE(17).  We want to keep the maximum hashtable
  34 * size under the current 2<<17 maximum, which can hold this many
  35 * different values before overflowing to hashtable of size 2<<18.
  36 */
  37#define HASHBASE 107927
  38
  39struct spanhash {
  40        unsigned int hashval;
  41        unsigned int cnt;
  42};
  43struct spanhash_top {
  44        int alloc_log2;
  45        int free;
  46        struct spanhash data[FLEX_ARRAY];
  47};
  48
  49static struct spanhash_top *spanhash_rehash(struct spanhash_top *orig)
  50{
  51        struct spanhash_top *new_spanhash;
  52        int i;
  53        int osz = 1 << orig->alloc_log2;
  54        int sz = osz << 1;
  55
  56        new_spanhash = xmalloc(st_add(sizeof(*orig),
  57                             st_mult(sizeof(struct spanhash), sz)));
  58        new_spanhash->alloc_log2 = orig->alloc_log2 + 1;
  59        new_spanhash->free = INITIAL_FREE(new_spanhash->alloc_log2);
  60        memset(new_spanhash->data, 0, sizeof(struct spanhash) * sz);
  61        for (i = 0; i < osz; i++) {
  62                struct spanhash *o = &(orig->data[i]);
  63                int bucket;
  64                if (!o->cnt)
  65                        continue;
  66                bucket = o->hashval & (sz - 1);
  67                while (1) {
  68                        struct spanhash *h = &(new_spanhash->data[bucket++]);
  69                        if (!h->cnt) {
  70                                h->hashval = o->hashval;
  71                                h->cnt = o->cnt;
  72                                new_spanhash->free--;
  73                                break;
  74                        }
  75                        if (sz <= bucket)
  76                                bucket = 0;
  77                }
  78        }
  79        free(orig);
  80        return new_spanhash;
  81}
  82
  83static struct spanhash_top *add_spanhash(struct spanhash_top *top,
  84                                         unsigned int hashval, int cnt)
  85{
  86        int bucket, lim;
  87        struct spanhash *h;
  88
  89        lim = (1 << top->alloc_log2);
  90        bucket = hashval & (lim - 1);
  91        while (1) {
  92                h = &(top->data[bucket++]);
  93                if (!h->cnt) {
  94                        h->hashval = hashval;
  95                        h->cnt = cnt;
  96                        top->free--;
  97                        if (top->free < 0)
  98                                return spanhash_rehash(top);
  99                        return top;
 100                }
 101                if (h->hashval == hashval) {
 102                        h->cnt += cnt;
 103                        return top;
 104                }
 105                if (lim <= bucket)
 106                        bucket = 0;
 107        }
 108}
 109
 110static int spanhash_cmp(const void *a_, const void *b_)
 111{
 112        const struct spanhash *a = a_;
 113        const struct spanhash *b = b_;
 114
 115        /* A count of zero compares at the end.. */
 116        if (!a->cnt)
 117                return !b->cnt ? 0 : 1;
 118        if (!b->cnt)
 119                return -1;
 120        return a->hashval < b->hashval ? -1 :
 121                a->hashval > b->hashval ? 1 : 0;
 122}
 123
 124static struct spanhash_top *hash_chars(struct repository *r,
 125                                       struct diff_filespec *one)
 126{
 127        int i, n;
 128        unsigned int accum1, accum2, hashval;
 129        struct spanhash_top *hash;
 130        unsigned char *buf = one->data;
 131        unsigned int sz = one->size;
 132        int is_text = !diff_filespec_is_binary(r, one);
 133
 134        i = INITIAL_HASH_SIZE;
 135        hash = xmalloc(st_add(sizeof(*hash),
 136                              st_mult(sizeof(struct spanhash), 1<<i)));
 137        hash->alloc_log2 = i;
 138        hash->free = INITIAL_FREE(i);
 139        memset(hash->data, 0, sizeof(struct spanhash) * (1<<i));
 140
 141        n = 0;
 142        accum1 = accum2 = 0;
 143        while (sz) {
 144                unsigned int c = *buf++;
 145                unsigned int old_1 = accum1;
 146                sz--;
 147
 148                /* Ignore CR in CRLF sequence if text */
 149                if (is_text && c == '\r' && sz && *buf == '\n')
 150                        continue;
 151
 152                accum1 = (accum1 << 7) ^ (accum2 >> 25);
 153                accum2 = (accum2 << 7) ^ (old_1 >> 25);
 154                accum1 += c;
 155                if (++n < 64 && c != '\n')
 156                        continue;
 157                hashval = (accum1 + accum2 * 0x61) % HASHBASE;
 158                hash = add_spanhash(hash, hashval, n);
 159                n = 0;
 160                accum1 = accum2 = 0;
 161        }
 162        QSORT(hash->data, 1ul << hash->alloc_log2, spanhash_cmp);
 163        return hash;
 164}
 165
 166int diffcore_count_changes(struct repository *r,
 167                           struct diff_filespec *src,
 168                           struct diff_filespec *dst,
 169                           void **src_count_p,
 170                           void **dst_count_p,
 171                           unsigned long *src_copied,
 172                           unsigned long *literal_added)
 173{
 174        struct spanhash *s, *d;
 175        struct spanhash_top *src_count, *dst_count;
 176        unsigned long sc, la;
 177
 178        src_count = dst_count = NULL;
 179        if (src_count_p)
 180                src_count = *src_count_p;
 181        if (!src_count) {
 182                src_count = hash_chars(r, src);
 183                if (src_count_p)
 184                        *src_count_p = src_count;
 185        }
 186        if (dst_count_p)
 187                dst_count = *dst_count_p;
 188        if (!dst_count) {
 189                dst_count = hash_chars(r, dst);
 190                if (dst_count_p)
 191                        *dst_count_p = dst_count;
 192        }
 193        sc = la = 0;
 194
 195        s = src_count->data;
 196        d = dst_count->data;
 197        for (;;) {
 198                unsigned dst_cnt, src_cnt;
 199                if (!s->cnt)
 200                        break; /* we checked all in src */
 201                while (d->cnt) {
 202                        if (d->hashval >= s->hashval)
 203                                break;
 204                        la += d->cnt;
 205                        d++;
 206                }
 207                src_cnt = s->cnt;
 208                dst_cnt = 0;
 209                if (d->cnt && d->hashval == s->hashval) {
 210                        dst_cnt = d->cnt;
 211                        d++;
 212                }
 213                if (src_cnt < dst_cnt) {
 214                        la += dst_cnt - src_cnt;
 215                        sc += src_cnt;
 216                }
 217                else
 218                        sc += dst_cnt;
 219                s++;
 220        }
 221        while (d->cnt) {
 222                la += d->cnt;
 223                d++;
 224        }
 225
 226        if (!src_count_p)
 227                free(src_count);
 228        if (!dst_count_p)
 229                free(dst_count);
 230        *src_copied = sc;
 231        *literal_added = la;
 232        return 0;
 233}