gitview: Fix the graph display .
[git] / diff-delta.c
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 "delta.h"
23 #include "zlib.h"
24
25
26 /* block size: min = 16, max = 64k, power of 2 */
27 #define BLK_SIZE 16
28
29 #define MIN(a, b) ((a) < (b) ? (a) : (b))
30
31 #define GR_PRIME 0x9e370001
32 #define HASH(v, b) (((unsigned int)(v) * GR_PRIME) >> (32 - (b)))
33         
34 static unsigned int hashbits(unsigned int size)
35 {
36         unsigned int val = 1, bits = 0;
37         while (val < size && bits < 32) {
38                 val <<= 1;
39                 bits++;
40         }
41         return bits ? bits: 1;
42 }
43
44 typedef struct s_chanode {
45         struct s_chanode *next;
46         int icurr;
47 } chanode_t;
48
49 typedef struct s_chastore {
50         int isize, nsize;
51         chanode_t *ancur;
52 } chastore_t;
53
54 static void cha_init(chastore_t *cha, int isize, int icount)
55 {
56         cha->isize = isize;
57         cha->nsize = icount * isize;
58         cha->ancur = NULL;
59 }
60
61 static void *cha_alloc(chastore_t *cha)
62 {
63         chanode_t *ancur;
64         void *data;
65
66         ancur = cha->ancur;
67         if (!ancur || ancur->icurr == cha->nsize) {
68                 ancur = malloc(sizeof(chanode_t) + cha->nsize);
69                 if (!ancur)
70                         return NULL;
71                 ancur->icurr = 0;
72                 ancur->next = cha->ancur;
73                 cha->ancur = ancur;
74         }
75
76         data = (void *)ancur + sizeof(chanode_t) + ancur->icurr;
77         ancur->icurr += cha->isize;
78         return data;
79 }
80
81 static void cha_free(chastore_t *cha)
82 {
83         chanode_t *cur = cha->ancur;
84         while (cur) {
85                 chanode_t *tmp = cur;
86                 cur = cur->next;
87                 free(tmp);
88         }
89 }
90
91 typedef struct s_bdrecord {
92         struct s_bdrecord *next;
93         unsigned int fp;
94         const unsigned char *ptr;
95 } bdrecord_t;
96
97 typedef struct s_bdfile {
98         chastore_t cha;
99         unsigned int fphbits;
100         bdrecord_t **fphash;
101 } bdfile_t;
102
103 static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf)
104 {
105         unsigned int fphbits;
106         int i, hsize;
107         const unsigned char *data, *top;
108         bdrecord_t *brec;
109         bdrecord_t **fphash;
110
111         fphbits = hashbits(bufsize / BLK_SIZE + 1);
112         hsize = 1 << fphbits;
113         fphash = malloc(hsize * sizeof(bdrecord_t *));
114         if (!fphash)
115                 return -1;
116         for (i = 0; i < hsize; i++)
117                 fphash[i] = NULL;
118         cha_init(&bdf->cha, sizeof(bdrecord_t), hsize / 4 + 1);
119
120         top = buf + bufsize;
121         data = buf + (bufsize / BLK_SIZE) * BLK_SIZE;
122         if (data == top)
123                 data -= BLK_SIZE;
124
125         for ( ; data >= buf; data -= BLK_SIZE) {
126                 brec = cha_alloc(&bdf->cha);
127                 if (!brec) {
128                         cha_free(&bdf->cha);
129                         free(fphash);
130                         return -1;
131                 }
132                 brec->fp = adler32(0, data, MIN(BLK_SIZE, top - data));
133                 brec->ptr = data;
134                 i = HASH(brec->fp, fphbits);
135                 brec->next = fphash[i];
136                 fphash[i] = brec;
137         }
138
139         bdf->fphbits = fphbits;
140         bdf->fphash = fphash;
141
142         return 0;
143 }
144
145 static void delta_cleanup(bdfile_t *bdf)
146 {
147         free(bdf->fphash);
148         cha_free(&bdf->cha);
149 }
150
151 #define COPYOP_SIZE(o, s) \
152     (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \
153      !!(s & 0xff) + !!(s & 0xff00) + 1)
154
155 void *diff_delta(void *from_buf, unsigned long from_size,
156                  void *to_buf, unsigned long to_size,
157                  unsigned long *delta_size,
158                  unsigned long max_size)
159 {
160         int i, outpos, outsize, inscnt, csize, msize, moff;
161         unsigned int fp;
162         const unsigned char *ref_data, *ref_top, *data, *top, *ptr1, *ptr2;
163         unsigned char *out, *orig;
164         bdrecord_t *brec;
165         bdfile_t bdf;
166
167         if (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))
168                 return NULL;
169         
170         outpos = 0;
171         outsize = 8192;
172         out = malloc(outsize);
173         if (!out) {
174                 delta_cleanup(&bdf);
175                 return NULL;
176         }
177
178         ref_data = from_buf;
179         ref_top = from_buf + from_size;
180         data = to_buf;
181         top = to_buf + to_size;
182
183         /* store reference buffer size */
184         out[outpos++] = from_size;
185         from_size >>= 7;
186         while (from_size) {
187                 out[outpos - 1] |= 0x80;
188                 out[outpos++] = from_size;
189                 from_size >>= 7;
190         }
191
192         /* store target buffer size */
193         out[outpos++] = to_size;
194         to_size >>= 7;
195         while (to_size) {
196                 out[outpos - 1] |= 0x80;
197                 out[outpos++] = to_size;
198                 to_size >>= 7;
199         }
200
201         inscnt = 0;
202         moff = 0;
203         while (data < top) {
204                 msize = 0;
205                 fp = adler32(0, data, MIN(top - data, BLK_SIZE));
206                 i = HASH(fp, bdf.fphbits);
207                 for (brec = bdf.fphash[i]; brec; brec = brec->next) {
208                         if (brec->fp == fp) {
209                                 csize = ref_top - brec->ptr;
210                                 if (csize > top - data)
211                                         csize = top - data;
212                                 for (ptr1 = brec->ptr, ptr2 = data; 
213                                      csize && *ptr1 == *ptr2;
214                                      csize--, ptr1++, ptr2++);
215
216                                 csize = ptr1 - brec->ptr;
217                                 if (csize > msize) {
218                                         moff = brec->ptr - ref_data;
219                                         msize = csize;
220                                         if (msize >= 0x10000) {
221                                                 msize = 0x10000;
222                                                 break;
223                                         }
224                                 }
225                         }
226                 }
227
228                 if (!msize || msize < COPYOP_SIZE(moff, msize)) {
229                         if (!inscnt)
230                                 outpos++;
231                         out[outpos++] = *data++;
232                         inscnt++;
233                         if (inscnt == 0x7f) {
234                                 out[outpos - inscnt - 1] = inscnt;
235                                 inscnt = 0;
236                         }
237                 } else {
238                         if (inscnt) {
239                                 out[outpos - inscnt - 1] = inscnt;
240                                 inscnt = 0;
241                         }
242
243                         data += msize;
244                         orig = out + outpos++;
245                         i = 0x80;
246
247                         if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }
248                         moff >>= 8;
249                         if (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }
250                         moff >>= 8;
251                         if (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }
252                         moff >>= 8;
253                         if (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }
254
255                         if (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }
256                         msize >>= 8;
257                         if (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }
258
259                         *orig = i;
260                 }
261
262                 if (max_size && outpos > max_size) {
263                         free(out);
264                         delta_cleanup(&bdf);
265                         return NULL;
266                 }
267
268                 /* next time around the largest possible output is 1 + 4 + 3 */
269                 if (outpos > outsize - 8) {
270                         void *tmp = out;
271                         outsize = outsize * 3 / 2;
272                         out = realloc(out, outsize);
273                         if (!out) {
274                                 free(tmp);
275                                 delta_cleanup(&bdf);
276                                 return NULL;
277                         }
278                 }
279         }
280
281         if (inscnt)
282                 out[outpos - inscnt - 1] = inscnt;
283
284         delta_cleanup(&bdf);
285         *delta_size = outpos;
286         return out;
287 }