line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
/* |
2
|
|
|
|
|
|
|
* Copyright (C) the libgit2 contributors. All rights reserved. |
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
|
|
|
|
|
|
|
|
8
|
|
|
|
|
|
|
#include "delta.h" |
9
|
|
|
|
|
|
|
|
10
|
|
|
|
|
|
|
/* maximum hash entry list for the same hash bucket */ |
11
|
|
|
|
|
|
|
#define HASH_LIMIT 64 |
12
|
|
|
|
|
|
|
|
13
|
|
|
|
|
|
|
#define RABIN_SHIFT 23 |
14
|
|
|
|
|
|
|
#define RABIN_WINDOW 16 |
15
|
|
|
|
|
|
|
|
16
|
|
|
|
|
|
|
static const unsigned int T[256] = { |
17
|
|
|
|
|
|
|
0x00000000, 0xab59b4d1, 0x56b369a2, 0xfdeadd73, 0x063f6795, 0xad66d344, |
18
|
|
|
|
|
|
|
0x508c0e37, 0xfbd5bae6, 0x0c7ecf2a, 0xa7277bfb, 0x5acda688, 0xf1941259, |
19
|
|
|
|
|
|
|
0x0a41a8bf, 0xa1181c6e, 0x5cf2c11d, 0xf7ab75cc, 0x18fd9e54, 0xb3a42a85, |
20
|
|
|
|
|
|
|
0x4e4ef7f6, 0xe5174327, 0x1ec2f9c1, 0xb59b4d10, 0x48719063, 0xe32824b2, |
21
|
|
|
|
|
|
|
0x1483517e, 0xbfdae5af, 0x423038dc, 0xe9698c0d, 0x12bc36eb, 0xb9e5823a, |
22
|
|
|
|
|
|
|
0x440f5f49, 0xef56eb98, 0x31fb3ca8, 0x9aa28879, 0x6748550a, 0xcc11e1db, |
23
|
|
|
|
|
|
|
0x37c45b3d, 0x9c9defec, 0x6177329f, 0xca2e864e, 0x3d85f382, 0x96dc4753, |
24
|
|
|
|
|
|
|
0x6b369a20, 0xc06f2ef1, 0x3bba9417, 0x90e320c6, 0x6d09fdb5, 0xc6504964, |
25
|
|
|
|
|
|
|
0x2906a2fc, 0x825f162d, 0x7fb5cb5e, 0xd4ec7f8f, 0x2f39c569, 0x846071b8, |
26
|
|
|
|
|
|
|
0x798aaccb, 0xd2d3181a, 0x25786dd6, 0x8e21d907, 0x73cb0474, 0xd892b0a5, |
27
|
|
|
|
|
|
|
0x23470a43, 0x881ebe92, 0x75f463e1, 0xdeadd730, 0x63f67950, 0xc8afcd81, |
28
|
|
|
|
|
|
|
0x354510f2, 0x9e1ca423, 0x65c91ec5, 0xce90aa14, 0x337a7767, 0x9823c3b6, |
29
|
|
|
|
|
|
|
0x6f88b67a, 0xc4d102ab, 0x393bdfd8, 0x92626b09, 0x69b7d1ef, 0xc2ee653e, |
30
|
|
|
|
|
|
|
0x3f04b84d, 0x945d0c9c, 0x7b0be704, 0xd05253d5, 0x2db88ea6, 0x86e13a77, |
31
|
|
|
|
|
|
|
0x7d348091, 0xd66d3440, 0x2b87e933, 0x80de5de2, 0x7775282e, 0xdc2c9cff, |
32
|
|
|
|
|
|
|
0x21c6418c, 0x8a9ff55d, 0x714a4fbb, 0xda13fb6a, 0x27f92619, 0x8ca092c8, |
33
|
|
|
|
|
|
|
0x520d45f8, 0xf954f129, 0x04be2c5a, 0xafe7988b, 0x5432226d, 0xff6b96bc, |
34
|
|
|
|
|
|
|
0x02814bcf, 0xa9d8ff1e, 0x5e738ad2, 0xf52a3e03, 0x08c0e370, 0xa39957a1, |
35
|
|
|
|
|
|
|
0x584ced47, 0xf3155996, 0x0eff84e5, 0xa5a63034, 0x4af0dbac, 0xe1a96f7d, |
36
|
|
|
|
|
|
|
0x1c43b20e, 0xb71a06df, 0x4ccfbc39, 0xe79608e8, 0x1a7cd59b, 0xb125614a, |
37
|
|
|
|
|
|
|
0x468e1486, 0xedd7a057, 0x103d7d24, 0xbb64c9f5, 0x40b17313, 0xebe8c7c2, |
38
|
|
|
|
|
|
|
0x16021ab1, 0xbd5bae60, 0x6cb54671, 0xc7ecf2a0, 0x3a062fd3, 0x915f9b02, |
39
|
|
|
|
|
|
|
0x6a8a21e4, 0xc1d39535, 0x3c394846, 0x9760fc97, 0x60cb895b, 0xcb923d8a, |
40
|
|
|
|
|
|
|
0x3678e0f9, 0x9d215428, 0x66f4eece, 0xcdad5a1f, 0x3047876c, 0x9b1e33bd, |
41
|
|
|
|
|
|
|
0x7448d825, 0xdf116cf4, 0x22fbb187, 0x89a20556, 0x7277bfb0, 0xd92e0b61, |
42
|
|
|
|
|
|
|
0x24c4d612, 0x8f9d62c3, 0x7836170f, 0xd36fa3de, 0x2e857ead, 0x85dcca7c, |
43
|
|
|
|
|
|
|
0x7e09709a, 0xd550c44b, 0x28ba1938, 0x83e3ade9, 0x5d4e7ad9, 0xf617ce08, |
44
|
|
|
|
|
|
|
0x0bfd137b, 0xa0a4a7aa, 0x5b711d4c, 0xf028a99d, 0x0dc274ee, 0xa69bc03f, |
45
|
|
|
|
|
|
|
0x5130b5f3, 0xfa690122, 0x0783dc51, 0xacda6880, 0x570fd266, 0xfc5666b7, |
46
|
|
|
|
|
|
|
0x01bcbbc4, 0xaae50f15, 0x45b3e48d, 0xeeea505c, 0x13008d2f, 0xb85939fe, |
47
|
|
|
|
|
|
|
0x438c8318, 0xe8d537c9, 0x153feaba, 0xbe665e6b, 0x49cd2ba7, 0xe2949f76, |
48
|
|
|
|
|
|
|
0x1f7e4205, 0xb427f6d4, 0x4ff24c32, 0xe4abf8e3, 0x19412590, 0xb2189141, |
49
|
|
|
|
|
|
|
0x0f433f21, 0xa41a8bf0, 0x59f05683, 0xf2a9e252, 0x097c58b4, 0xa225ec65, |
50
|
|
|
|
|
|
|
0x5fcf3116, 0xf49685c7, 0x033df00b, 0xa86444da, 0x558e99a9, 0xfed72d78, |
51
|
|
|
|
|
|
|
0x0502979e, 0xae5b234f, 0x53b1fe3c, 0xf8e84aed, 0x17bea175, 0xbce715a4, |
52
|
|
|
|
|
|
|
0x410dc8d7, 0xea547c06, 0x1181c6e0, 0xbad87231, 0x4732af42, 0xec6b1b93, |
53
|
|
|
|
|
|
|
0x1bc06e5f, 0xb099da8e, 0x4d7307fd, 0xe62ab32c, 0x1dff09ca, 0xb6a6bd1b, |
54
|
|
|
|
|
|
|
0x4b4c6068, 0xe015d4b9, 0x3eb80389, 0x95e1b758, 0x680b6a2b, 0xc352defa, |
55
|
|
|
|
|
|
|
0x3887641c, 0x93ded0cd, 0x6e340dbe, 0xc56db96f, 0x32c6cca3, 0x999f7872, |
56
|
|
|
|
|
|
|
0x6475a501, 0xcf2c11d0, 0x34f9ab36, 0x9fa01fe7, 0x624ac294, 0xc9137645, |
57
|
|
|
|
|
|
|
0x26459ddd, 0x8d1c290c, 0x70f6f47f, 0xdbaf40ae, 0x207afa48, 0x8b234e99, |
58
|
|
|
|
|
|
|
0x76c993ea, 0xdd90273b, 0x2a3b52f7, 0x8162e626, 0x7c883b55, 0xd7d18f84, |
59
|
|
|
|
|
|
|
0x2c043562, 0x875d81b3, 0x7ab75cc0, 0xd1eee811 |
60
|
|
|
|
|
|
|
}; |
61
|
|
|
|
|
|
|
|
62
|
|
|
|
|
|
|
static const unsigned int U[256] = { |
63
|
|
|
|
|
|
|
0x00000000, 0x7eb5200d, 0x5633f4cb, 0x2886d4c6, 0x073e5d47, 0x798b7d4a, |
64
|
|
|
|
|
|
|
0x510da98c, 0x2fb88981, 0x0e7cba8e, 0x70c99a83, 0x584f4e45, 0x26fa6e48, |
65
|
|
|
|
|
|
|
0x0942e7c9, 0x77f7c7c4, 0x5f711302, 0x21c4330f, 0x1cf9751c, 0x624c5511, |
66
|
|
|
|
|
|
|
0x4aca81d7, 0x347fa1da, 0x1bc7285b, 0x65720856, 0x4df4dc90, 0x3341fc9d, |
67
|
|
|
|
|
|
|
0x1285cf92, 0x6c30ef9f, 0x44b63b59, 0x3a031b54, 0x15bb92d5, 0x6b0eb2d8, |
68
|
|
|
|
|
|
|
0x4388661e, 0x3d3d4613, 0x39f2ea38, 0x4747ca35, 0x6fc11ef3, 0x11743efe, |
69
|
|
|
|
|
|
|
0x3eccb77f, 0x40799772, 0x68ff43b4, 0x164a63b9, 0x378e50b6, 0x493b70bb, |
70
|
|
|
|
|
|
|
0x61bda47d, 0x1f088470, 0x30b00df1, 0x4e052dfc, 0x6683f93a, 0x1836d937, |
71
|
|
|
|
|
|
|
0x250b9f24, 0x5bbebf29, 0x73386bef, 0x0d8d4be2, 0x2235c263, 0x5c80e26e, |
72
|
|
|
|
|
|
|
0x740636a8, 0x0ab316a5, 0x2b7725aa, 0x55c205a7, 0x7d44d161, 0x03f1f16c, |
73
|
|
|
|
|
|
|
0x2c4978ed, 0x52fc58e0, 0x7a7a8c26, 0x04cfac2b, 0x73e5d470, 0x0d50f47d, |
74
|
|
|
|
|
|
|
0x25d620bb, 0x5b6300b6, 0x74db8937, 0x0a6ea93a, 0x22e87dfc, 0x5c5d5df1, |
75
|
|
|
|
|
|
|
0x7d996efe, 0x032c4ef3, 0x2baa9a35, 0x551fba38, 0x7aa733b9, 0x041213b4, |
76
|
|
|
|
|
|
|
0x2c94c772, 0x5221e77f, 0x6f1ca16c, 0x11a98161, 0x392f55a7, 0x479a75aa, |
77
|
|
|
|
|
|
|
0x6822fc2b, 0x1697dc26, 0x3e1108e0, 0x40a428ed, 0x61601be2, 0x1fd53bef, |
78
|
|
|
|
|
|
|
0x3753ef29, 0x49e6cf24, 0x665e46a5, 0x18eb66a8, 0x306db26e, 0x4ed89263, |
79
|
|
|
|
|
|
|
0x4a173e48, 0x34a21e45, 0x1c24ca83, 0x6291ea8e, 0x4d29630f, 0x339c4302, |
80
|
|
|
|
|
|
|
0x1b1a97c4, 0x65afb7c9, 0x446b84c6, 0x3adea4cb, 0x1258700d, 0x6ced5000, |
81
|
|
|
|
|
|
|
0x4355d981, 0x3de0f98c, 0x15662d4a, 0x6bd30d47, 0x56ee4b54, 0x285b6b59, |
82
|
|
|
|
|
|
|
0x00ddbf9f, 0x7e689f92, 0x51d01613, 0x2f65361e, 0x07e3e2d8, 0x7956c2d5, |
83
|
|
|
|
|
|
|
0x5892f1da, 0x2627d1d7, 0x0ea10511, 0x7014251c, 0x5facac9d, 0x21198c90, |
84
|
|
|
|
|
|
|
0x099f5856, 0x772a785b, 0x4c921c31, 0x32273c3c, 0x1aa1e8fa, 0x6414c8f7, |
85
|
|
|
|
|
|
|
0x4bac4176, 0x3519617b, 0x1d9fb5bd, 0x632a95b0, 0x42eea6bf, 0x3c5b86b2, |
86
|
|
|
|
|
|
|
0x14dd5274, 0x6a687279, 0x45d0fbf8, 0x3b65dbf5, 0x13e30f33, 0x6d562f3e, |
87
|
|
|
|
|
|
|
0x506b692d, 0x2ede4920, 0x06589de6, 0x78edbdeb, 0x5755346a, 0x29e01467, |
88
|
|
|
|
|
|
|
0x0166c0a1, 0x7fd3e0ac, 0x5e17d3a3, 0x20a2f3ae, 0x08242768, 0x76910765, |
89
|
|
|
|
|
|
|
0x59298ee4, 0x279caee9, 0x0f1a7a2f, 0x71af5a22, 0x7560f609, 0x0bd5d604, |
90
|
|
|
|
|
|
|
0x235302c2, 0x5de622cf, 0x725eab4e, 0x0ceb8b43, 0x246d5f85, 0x5ad87f88, |
91
|
|
|
|
|
|
|
0x7b1c4c87, 0x05a96c8a, 0x2d2fb84c, 0x539a9841, 0x7c2211c0, 0x029731cd, |
92
|
|
|
|
|
|
|
0x2a11e50b, 0x54a4c506, 0x69998315, 0x172ca318, 0x3faa77de, 0x411f57d3, |
93
|
|
|
|
|
|
|
0x6ea7de52, 0x1012fe5f, 0x38942a99, 0x46210a94, 0x67e5399b, 0x19501996, |
94
|
|
|
|
|
|
|
0x31d6cd50, 0x4f63ed5d, 0x60db64dc, 0x1e6e44d1, 0x36e89017, 0x485db01a, |
95
|
|
|
|
|
|
|
0x3f77c841, 0x41c2e84c, 0x69443c8a, 0x17f11c87, 0x38499506, 0x46fcb50b, |
96
|
|
|
|
|
|
|
0x6e7a61cd, 0x10cf41c0, 0x310b72cf, 0x4fbe52c2, 0x67388604, 0x198da609, |
97
|
|
|
|
|
|
|
0x36352f88, 0x48800f85, 0x6006db43, 0x1eb3fb4e, 0x238ebd5d, 0x5d3b9d50, |
98
|
|
|
|
|
|
|
0x75bd4996, 0x0b08699b, 0x24b0e01a, 0x5a05c017, 0x728314d1, 0x0c3634dc, |
99
|
|
|
|
|
|
|
0x2df207d3, 0x534727de, 0x7bc1f318, 0x0574d315, 0x2acc5a94, 0x54797a99, |
100
|
|
|
|
|
|
|
0x7cffae5f, 0x024a8e52, 0x06852279, 0x78300274, 0x50b6d6b2, 0x2e03f6bf, |
101
|
|
|
|
|
|
|
0x01bb7f3e, 0x7f0e5f33, 0x57888bf5, 0x293dabf8, 0x08f998f7, 0x764cb8fa, |
102
|
|
|
|
|
|
|
0x5eca6c3c, 0x207f4c31, 0x0fc7c5b0, 0x7172e5bd, 0x59f4317b, 0x27411176, |
103
|
|
|
|
|
|
|
0x1a7c5765, 0x64c97768, 0x4c4fa3ae, 0x32fa83a3, 0x1d420a22, 0x63f72a2f, |
104
|
|
|
|
|
|
|
0x4b71fee9, 0x35c4dee4, 0x1400edeb, 0x6ab5cde6, 0x42331920, 0x3c86392d, |
105
|
|
|
|
|
|
|
0x133eb0ac, 0x6d8b90a1, 0x450d4467, 0x3bb8646a |
106
|
|
|
|
|
|
|
}; |
107
|
|
|
|
|
|
|
|
108
|
|
|
|
|
|
|
struct index_entry { |
109
|
|
|
|
|
|
|
const unsigned char *ptr; |
110
|
|
|
|
|
|
|
unsigned int val; |
111
|
|
|
|
|
|
|
struct index_entry *next; |
112
|
|
|
|
|
|
|
}; |
113
|
|
|
|
|
|
|
|
114
|
|
|
|
|
|
|
struct git_delta_index { |
115
|
|
|
|
|
|
|
unsigned long memsize; |
116
|
|
|
|
|
|
|
const void *src_buf; |
117
|
|
|
|
|
|
|
size_t src_size; |
118
|
|
|
|
|
|
|
unsigned int hash_mask; |
119
|
|
|
|
|
|
|
struct index_entry *hash[GIT_FLEX_ARRAY]; |
120
|
|
|
|
|
|
|
}; |
121
|
|
|
|
|
|
|
|
122
|
12
|
|
|
|
|
|
static int lookup_index_alloc( |
123
|
|
|
|
|
|
|
void **out, unsigned long *out_len, size_t entries, size_t hash_count) |
124
|
|
|
|
|
|
|
{ |
125
|
|
|
|
|
|
|
size_t entries_len, hash_len, index_len; |
126
|
|
|
|
|
|
|
|
127
|
12
|
50
|
|
|
|
|
GIT_ERROR_CHECK_ALLOC_MULTIPLY(&entries_len, entries, sizeof(struct index_entry)); |
|
|
50
|
|
|
|
|
|
128
|
12
|
50
|
|
|
|
|
GIT_ERROR_CHECK_ALLOC_MULTIPLY(&hash_len, hash_count, sizeof(struct index_entry *)); |
|
|
50
|
|
|
|
|
|
129
|
|
|
|
|
|
|
|
130
|
12
|
50
|
|
|
|
|
GIT_ERROR_CHECK_ALLOC_ADD(&index_len, sizeof(struct git_delta_index), entries_len); |
|
|
50
|
|
|
|
|
|
131
|
12
|
50
|
|
|
|
|
GIT_ERROR_CHECK_ALLOC_ADD(&index_len, index_len, hash_len); |
|
|
50
|
|
|
|
|
|
132
|
|
|
|
|
|
|
|
133
|
12
|
50
|
|
|
|
|
if (!git__is_ulong(index_len)) { |
134
|
0
|
|
|
|
|
|
git_error_set(GIT_ERROR_NOMEMORY, "overly large delta"); |
135
|
0
|
|
|
|
|
|
return -1; |
136
|
|
|
|
|
|
|
} |
137
|
|
|
|
|
|
|
|
138
|
12
|
|
|
|
|
|
*out = git__malloc(index_len); |
139
|
12
|
50
|
|
|
|
|
GIT_ERROR_CHECK_ALLOC(*out); |
140
|
|
|
|
|
|
|
|
141
|
12
|
|
|
|
|
|
*out_len = (unsigned long)index_len; |
142
|
12
|
|
|
|
|
|
return 0; |
143
|
|
|
|
|
|
|
} |
144
|
|
|
|
|
|
|
|
145
|
12
|
|
|
|
|
|
int git_delta_index_init( |
146
|
|
|
|
|
|
|
git_delta_index **out, const void *buf, size_t bufsize) |
147
|
|
|
|
|
|
|
{ |
148
|
|
|
|
|
|
|
unsigned int i, hsize, hmask, entries, prev_val, *hash_count; |
149
|
12
|
|
|
|
|
|
const unsigned char *data, *buffer = buf; |
150
|
|
|
|
|
|
|
struct git_delta_index *index; |
151
|
|
|
|
|
|
|
struct index_entry *entry, **hash; |
152
|
|
|
|
|
|
|
void *mem; |
153
|
|
|
|
|
|
|
unsigned long memsize; |
154
|
|
|
|
|
|
|
|
155
|
12
|
|
|
|
|
|
*out = NULL; |
156
|
|
|
|
|
|
|
|
157
|
12
|
50
|
|
|
|
|
if (!buf || !bufsize) |
|
|
50
|
|
|
|
|
|
158
|
0
|
|
|
|
|
|
return 0; |
159
|
|
|
|
|
|
|
|
160
|
|
|
|
|
|
|
/* Determine index hash size. Note that indexing skips the |
161
|
|
|
|
|
|
|
first byte to allow for optimizing the rabin polynomial |
162
|
|
|
|
|
|
|
initialization in create_delta(). */ |
163
|
12
|
|
|
|
|
|
entries = (unsigned int)(bufsize - 1) / RABIN_WINDOW; |
164
|
12
|
50
|
|
|
|
|
if (bufsize >= 0xffffffffUL) { |
165
|
|
|
|
|
|
|
/* |
166
|
|
|
|
|
|
|
* Current delta format can't encode offsets into |
167
|
|
|
|
|
|
|
* reference buffer with more than 32 bits. |
168
|
|
|
|
|
|
|
*/ |
169
|
0
|
|
|
|
|
|
entries = 0xfffffffeU / RABIN_WINDOW; |
170
|
|
|
|
|
|
|
} |
171
|
12
|
|
|
|
|
|
hsize = entries / 4; |
172
|
12
|
50
|
|
|
|
|
for (i = 4; i < 31 && (1u << i) < hsize; i++); |
|
|
50
|
|
|
|
|
|
173
|
12
|
|
|
|
|
|
hsize = 1 << i; |
174
|
12
|
|
|
|
|
|
hmask = hsize - 1; |
175
|
|
|
|
|
|
|
|
176
|
12
|
50
|
|
|
|
|
if (lookup_index_alloc(&mem, &memsize, entries, hsize) < 0) |
177
|
0
|
|
|
|
|
|
return -1; |
178
|
|
|
|
|
|
|
|
179
|
12
|
|
|
|
|
|
index = mem; |
180
|
12
|
|
|
|
|
|
mem = index->hash; |
181
|
12
|
|
|
|
|
|
hash = mem; |
182
|
12
|
|
|
|
|
|
mem = hash + hsize; |
183
|
12
|
|
|
|
|
|
entry = mem; |
184
|
|
|
|
|
|
|
|
185
|
12
|
|
|
|
|
|
index->memsize = memsize; |
186
|
12
|
|
|
|
|
|
index->src_buf = buf; |
187
|
12
|
|
|
|
|
|
index->src_size = bufsize; |
188
|
12
|
|
|
|
|
|
index->hash_mask = hmask; |
189
|
12
|
|
|
|
|
|
memset(hash, 0, hsize * sizeof(*hash)); |
190
|
|
|
|
|
|
|
|
191
|
|
|
|
|
|
|
/* allocate an array to count hash entries */ |
192
|
12
|
|
|
|
|
|
hash_count = git__calloc(hsize, sizeof(*hash_count)); |
193
|
12
|
50
|
|
|
|
|
if (!hash_count) { |
194
|
0
|
|
|
|
|
|
git__free(index); |
195
|
0
|
|
|
|
|
|
return -1; |
196
|
|
|
|
|
|
|
} |
197
|
|
|
|
|
|
|
|
198
|
|
|
|
|
|
|
/* then populate the index */ |
199
|
12
|
|
|
|
|
|
prev_val = ~0; |
200
|
132
|
100
|
|
|
|
|
for (data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW; |
201
|
|
|
|
|
|
|
data >= buffer; |
202
|
120
|
|
|
|
|
|
data -= RABIN_WINDOW) { |
203
|
120
|
|
|
|
|
|
unsigned int val = 0; |
204
|
2040
|
100
|
|
|
|
|
for (i = 1; i <= RABIN_WINDOW; i++) |
205
|
1920
|
|
|
|
|
|
val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT]; |
206
|
120
|
50
|
|
|
|
|
if (val == prev_val) { |
207
|
|
|
|
|
|
|
/* keep the lowest of consecutive identical blocks */ |
208
|
0
|
|
|
|
|
|
entry[-1].ptr = data + RABIN_WINDOW; |
209
|
|
|
|
|
|
|
} else { |
210
|
120
|
|
|
|
|
|
prev_val = val; |
211
|
120
|
|
|
|
|
|
i = val & hmask; |
212
|
120
|
|
|
|
|
|
entry->ptr = data + RABIN_WINDOW; |
213
|
120
|
|
|
|
|
|
entry->val = val; |
214
|
120
|
|
|
|
|
|
entry->next = hash[i]; |
215
|
120
|
|
|
|
|
|
hash[i] = entry++; |
216
|
120
|
|
|
|
|
|
hash_count[i]++; |
217
|
|
|
|
|
|
|
} |
218
|
|
|
|
|
|
|
} |
219
|
|
|
|
|
|
|
|
220
|
|
|
|
|
|
|
/* |
221
|
|
|
|
|
|
|
* Determine a limit on the number of entries in the same hash |
222
|
|
|
|
|
|
|
* bucket. This guard us against patological data sets causing |
223
|
|
|
|
|
|
|
* really bad hash distribution with most entries in the same hash |
224
|
|
|
|
|
|
|
* bucket that would bring us to O(m*n) computing costs (m and n |
225
|
|
|
|
|
|
|
* corresponding to reference and target buffer sizes). |
226
|
|
|
|
|
|
|
* |
227
|
|
|
|
|
|
|
* Make sure none of the hash buckets has more entries than |
228
|
|
|
|
|
|
|
* we're willing to test. Otherwise we cull the entry list |
229
|
|
|
|
|
|
|
* uniformly to still preserve a good repartition across |
230
|
|
|
|
|
|
|
* the reference buffer. |
231
|
|
|
|
|
|
|
*/ |
232
|
204
|
100
|
|
|
|
|
for (i = 0; i < hsize; i++) { |
233
|
192
|
50
|
|
|
|
|
if (hash_count[i] < HASH_LIMIT) |
234
|
192
|
|
|
|
|
|
continue; |
235
|
|
|
|
|
|
|
|
236
|
0
|
|
|
|
|
|
entry = hash[i]; |
237
|
|
|
|
|
|
|
do { |
238
|
0
|
|
|
|
|
|
struct index_entry *keep = entry; |
239
|
0
|
|
|
|
|
|
int skip = hash_count[i] / HASH_LIMIT / 2; |
240
|
|
|
|
|
|
|
do { |
241
|
0
|
|
|
|
|
|
entry = entry->next; |
242
|
0
|
0
|
|
|
|
|
} while(--skip && entry); |
|
|
0
|
|
|
|
|
|
243
|
0
|
|
|
|
|
|
keep->next = entry; |
244
|
0
|
0
|
|
|
|
|
} while (entry); |
245
|
|
|
|
|
|
|
} |
246
|
12
|
|
|
|
|
|
git__free(hash_count); |
247
|
|
|
|
|
|
|
|
248
|
12
|
|
|
|
|
|
*out = index; |
249
|
12
|
|
|
|
|
|
return 0; |
250
|
|
|
|
|
|
|
} |
251
|
|
|
|
|
|
|
|
252
|
0
|
|
|
|
|
|
void git_delta_index_free(git_delta_index *index) |
253
|
|
|
|
|
|
|
{ |
254
|
0
|
|
|
|
|
|
git__free(index); |
255
|
0
|
|
|
|
|
|
} |
256
|
|
|
|
|
|
|
|
257
|
12
|
|
|
|
|
|
size_t git_delta_index_size(git_delta_index *index) |
258
|
|
|
|
|
|
|
{ |
259
|
12
|
50
|
|
|
|
|
assert(index); |
260
|
|
|
|
|
|
|
|
261
|
12
|
|
|
|
|
|
return index->memsize; |
262
|
|
|
|
|
|
|
} |
263
|
|
|
|
|
|
|
|
264
|
|
|
|
|
|
|
/* |
265
|
|
|
|
|
|
|
* The maximum size for any opcode sequence, including the initial header |
266
|
|
|
|
|
|
|
* plus rabin window plus biggest copy. |
267
|
|
|
|
|
|
|
*/ |
268
|
|
|
|
|
|
|
#define MAX_OP_SIZE (5 + 5 + 1 + RABIN_WINDOW + 7) |
269
|
|
|
|
|
|
|
|
270
|
20
|
|
|
|
|
|
int git_delta_create_from_index( |
271
|
|
|
|
|
|
|
void **out, |
272
|
|
|
|
|
|
|
size_t *out_len, |
273
|
|
|
|
|
|
|
const struct git_delta_index *index, |
274
|
|
|
|
|
|
|
const void *trg_buf, |
275
|
|
|
|
|
|
|
size_t trg_size, |
276
|
|
|
|
|
|
|
size_t max_size) |
277
|
|
|
|
|
|
|
{ |
278
|
|
|
|
|
|
|
unsigned int i, bufpos, bufsize, moff, msize, val; |
279
|
|
|
|
|
|
|
int inscnt; |
280
|
|
|
|
|
|
|
const unsigned char *ref_data, *ref_top, *data, *top; |
281
|
|
|
|
|
|
|
unsigned char *buf; |
282
|
|
|
|
|
|
|
|
283
|
20
|
|
|
|
|
|
*out = NULL; |
284
|
20
|
|
|
|
|
|
*out_len = 0; |
285
|
|
|
|
|
|
|
|
286
|
20
|
50
|
|
|
|
|
if (!trg_buf || !trg_size) |
|
|
50
|
|
|
|
|
|
287
|
0
|
|
|
|
|
|
return 0; |
288
|
|
|
|
|
|
|
|
289
|
20
|
50
|
|
|
|
|
if (index->src_size > UINT_MAX || |
|
|
50
|
|
|
|
|
|
290
|
20
|
50
|
|
|
|
|
trg_size > UINT_MAX || |
291
|
|
|
|
|
|
|
max_size > (UINT_MAX - MAX_OP_SIZE - 1)) { |
292
|
0
|
|
|
|
|
|
git_error_set(GIT_ERROR_INVALID, "buffer sizes too large for delta processing"); |
293
|
0
|
|
|
|
|
|
return -1; |
294
|
|
|
|
|
|
|
} |
295
|
|
|
|
|
|
|
|
296
|
20
|
|
|
|
|
|
bufpos = 0; |
297
|
20
|
|
|
|
|
|
bufsize = 8192; |
298
|
20
|
50
|
|
|
|
|
if (max_size && bufsize >= max_size) |
|
|
50
|
|
|
|
|
|
299
|
20
|
|
|
|
|
|
bufsize = (unsigned int)(max_size + MAX_OP_SIZE + 1); |
300
|
20
|
|
|
|
|
|
buf = git__malloc(bufsize); |
301
|
20
|
50
|
|
|
|
|
GIT_ERROR_CHECK_ALLOC(buf); |
302
|
|
|
|
|
|
|
|
303
|
|
|
|
|
|
|
/* store reference buffer size */ |
304
|
20
|
|
|
|
|
|
i = (unsigned int)index->src_size; |
305
|
33
|
100
|
|
|
|
|
while (i >= 0x80) { |
306
|
13
|
|
|
|
|
|
buf[bufpos++] = i | 0x80; |
307
|
13
|
|
|
|
|
|
i >>= 7; |
308
|
|
|
|
|
|
|
} |
309
|
20
|
|
|
|
|
|
buf[bufpos++] = i; |
310
|
|
|
|
|
|
|
|
311
|
|
|
|
|
|
|
/* store target buffer size */ |
312
|
20
|
|
|
|
|
|
i = (unsigned int)trg_size; |
313
|
33
|
100
|
|
|
|
|
while (i >= 0x80) { |
314
|
13
|
|
|
|
|
|
buf[bufpos++] = i | 0x80; |
315
|
13
|
|
|
|
|
|
i >>= 7; |
316
|
|
|
|
|
|
|
} |
317
|
20
|
|
|
|
|
|
buf[bufpos++] = i; |
318
|
|
|
|
|
|
|
|
319
|
20
|
|
|
|
|
|
ref_data = index->src_buf; |
320
|
20
|
|
|
|
|
|
ref_top = ref_data + index->src_size; |
321
|
20
|
|
|
|
|
|
data = trg_buf; |
322
|
20
|
|
|
|
|
|
top = (const unsigned char *) trg_buf + trg_size; |
323
|
|
|
|
|
|
|
|
324
|
20
|
|
|
|
|
|
bufpos++; |
325
|
20
|
|
|
|
|
|
val = 0; |
326
|
340
|
100
|
|
|
|
|
for (i = 0; i < RABIN_WINDOW && data < top; i++, data++) { |
|
|
50
|
|
|
|
|
|
327
|
320
|
|
|
|
|
|
buf[bufpos++] = *data; |
328
|
320
|
|
|
|
|
|
val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT]; |
329
|
|
|
|
|
|
|
} |
330
|
20
|
|
|
|
|
|
inscnt = i; |
331
|
|
|
|
|
|
|
|
332
|
20
|
|
|
|
|
|
moff = 0; |
333
|
20
|
|
|
|
|
|
msize = 0; |
334
|
939
|
100
|
|
|
|
|
while (data < top) { |
335
|
936
|
50
|
|
|
|
|
if (msize < 4096) { |
336
|
|
|
|
|
|
|
struct index_entry *entry; |
337
|
936
|
|
|
|
|
|
val ^= U[data[-RABIN_WINDOW]]; |
338
|
936
|
|
|
|
|
|
val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT]; |
339
|
936
|
|
|
|
|
|
i = val & index->hash_mask; |
340
|
1834
|
100
|
|
|
|
|
for (entry = index->hash[i]; entry; entry = entry->next) { |
341
|
898
|
|
|
|
|
|
const unsigned char *ref = entry->ptr; |
342
|
898
|
|
|
|
|
|
const unsigned char *src = data; |
343
|
898
|
|
|
|
|
|
unsigned int ref_size = (unsigned int)(ref_top - ref); |
344
|
898
|
100
|
|
|
|
|
if (entry->val != val) |
345
|
889
|
|
|
|
|
|
continue; |
346
|
9
|
100
|
|
|
|
|
if (ref_size > (unsigned int)(top - src)) |
347
|
6
|
|
|
|
|
|
ref_size = (unsigned int)(top - src); |
348
|
9
|
50
|
|
|
|
|
if (ref_size <= msize) |
349
|
0
|
|
|
|
|
|
break; |
350
|
384
|
100
|
|
|
|
|
while (ref_size-- && *src++ == *ref) |
|
|
100
|
|
|
|
|
|
351
|
375
|
|
|
|
|
|
ref++; |
352
|
9
|
50
|
|
|
|
|
if (msize < (unsigned int)(ref - entry->ptr)) { |
353
|
|
|
|
|
|
|
/* this is our best match so far */ |
354
|
9
|
|
|
|
|
|
msize = (unsigned int)(ref - entry->ptr); |
355
|
9
|
|
|
|
|
|
moff = (unsigned int)(entry->ptr - ref_data); |
356
|
9
|
50
|
|
|
|
|
if (msize >= 4096) /* good enough */ |
357
|
0
|
|
|
|
|
|
break; |
358
|
|
|
|
|
|
|
} |
359
|
|
|
|
|
|
|
} |
360
|
|
|
|
|
|
|
} |
361
|
|
|
|
|
|
|
|
362
|
936
|
100
|
|
|
|
|
if (msize < 4) { |
363
|
927
|
100
|
|
|
|
|
if (!inscnt) |
364
|
7
|
|
|
|
|
|
bufpos++; |
365
|
927
|
|
|
|
|
|
buf[bufpos++] = *data++; |
366
|
927
|
|
|
|
|
|
inscnt++; |
367
|
927
|
50
|
|
|
|
|
if (inscnt == 0x7f) { |
368
|
0
|
|
|
|
|
|
buf[bufpos - inscnt - 1] = inscnt; |
369
|
0
|
|
|
|
|
|
inscnt = 0; |
370
|
|
|
|
|
|
|
} |
371
|
927
|
|
|
|
|
|
msize = 0; |
372
|
|
|
|
|
|
|
} else { |
373
|
|
|
|
|
|
|
unsigned int left; |
374
|
|
|
|
|
|
|
unsigned char *op; |
375
|
|
|
|
|
|
|
|
376
|
9
|
50
|
|
|
|
|
if (inscnt) { |
377
|
168
|
50
|
|
|
|
|
while (moff && ref_data[moff-1] == data[-1]) { |
|
|
100
|
|
|
|
|
|
378
|
|
|
|
|
|
|
/* we can match one byte back */ |
379
|
162
|
|
|
|
|
|
msize++; |
380
|
162
|
|
|
|
|
|
moff--; |
381
|
162
|
|
|
|
|
|
data--; |
382
|
162
|
|
|
|
|
|
bufpos--; |
383
|
162
|
100
|
|
|
|
|
if (--inscnt) |
384
|
159
|
|
|
|
|
|
continue; |
385
|
3
|
|
|
|
|
|
bufpos--; /* remove count slot */ |
386
|
3
|
|
|
|
|
|
inscnt--; /* make it -1 */ |
387
|
3
|
|
|
|
|
|
break; |
388
|
|
|
|
|
|
|
} |
389
|
9
|
|
|
|
|
|
buf[bufpos - inscnt - 1] = inscnt; |
390
|
9
|
|
|
|
|
|
inscnt = 0; |
391
|
|
|
|
|
|
|
} |
392
|
|
|
|
|
|
|
|
393
|
|
|
|
|
|
|
/* A copy op is currently limited to 64KB (pack v2) */ |
394
|
9
|
50
|
|
|
|
|
left = (msize < 0x10000) ? 0 : (msize - 0x10000); |
395
|
9
|
|
|
|
|
|
msize -= left; |
396
|
|
|
|
|
|
|
|
397
|
9
|
|
|
|
|
|
op = buf + bufpos++; |
398
|
9
|
|
|
|
|
|
i = 0x80; |
399
|
|
|
|
|
|
|
|
400
|
9
|
100
|
|
|
|
|
if (moff & 0x000000ff) |
401
|
6
|
|
|
|
|
|
buf[bufpos++] = moff >> 0, i |= 0x01; |
402
|
9
|
50
|
|
|
|
|
if (moff & 0x0000ff00) |
403
|
0
|
|
|
|
|
|
buf[bufpos++] = moff >> 8, i |= 0x02; |
404
|
9
|
50
|
|
|
|
|
if (moff & 0x00ff0000) |
405
|
0
|
|
|
|
|
|
buf[bufpos++] = moff >> 16, i |= 0x04; |
406
|
9
|
50
|
|
|
|
|
if (moff & 0xff000000) |
407
|
0
|
|
|
|
|
|
buf[bufpos++] = moff >> 24, i |= 0x08; |
408
|
|
|
|
|
|
|
|
409
|
9
|
50
|
|
|
|
|
if (msize & 0x00ff) |
410
|
9
|
|
|
|
|
|
buf[bufpos++] = msize >> 0, i |= 0x10; |
411
|
9
|
50
|
|
|
|
|
if (msize & 0xff00) |
412
|
0
|
|
|
|
|
|
buf[bufpos++] = msize >> 8, i |= 0x20; |
413
|
|
|
|
|
|
|
|
414
|
9
|
|
|
|
|
|
*op = i; |
415
|
|
|
|
|
|
|
|
416
|
9
|
|
|
|
|
|
data += msize; |
417
|
9
|
|
|
|
|
|
moff += msize; |
418
|
9
|
|
|
|
|
|
msize = left; |
419
|
|
|
|
|
|
|
|
420
|
9
|
50
|
|
|
|
|
if (msize < 4096) { |
421
|
|
|
|
|
|
|
int j; |
422
|
9
|
|
|
|
|
|
val = 0; |
423
|
153
|
100
|
|
|
|
|
for (j = -RABIN_WINDOW; j < 0; j++) |
424
|
288
|
|
|
|
|
|
val = ((val << 8) | data[j]) |
425
|
144
|
|
|
|
|
|
^ T[val >> RABIN_SHIFT]; |
426
|
|
|
|
|
|
|
} |
427
|
|
|
|
|
|
|
} |
428
|
|
|
|
|
|
|
|
429
|
936
|
100
|
|
|
|
|
if (bufpos >= bufsize - MAX_OP_SIZE) { |
430
|
17
|
|
|
|
|
|
void *tmp = buf; |
431
|
17
|
|
|
|
|
|
bufsize = bufsize * 3 / 2; |
432
|
17
|
50
|
|
|
|
|
if (max_size && bufsize >= max_size) |
|
|
50
|
|
|
|
|
|
433
|
17
|
|
|
|
|
|
bufsize = (unsigned int)(max_size + MAX_OP_SIZE + 1); |
434
|
17
|
50
|
|
|
|
|
if (max_size && bufpos > max_size) |
|
|
50
|
|
|
|
|
|
435
|
17
|
|
|
|
|
|
break; |
436
|
0
|
|
|
|
|
|
buf = git__realloc(buf, bufsize); |
437
|
0
|
0
|
|
|
|
|
if (!buf) { |
438
|
0
|
|
|
|
|
|
git__free(tmp); |
439
|
0
|
|
|
|
|
|
return -1; |
440
|
|
|
|
|
|
|
} |
441
|
|
|
|
|
|
|
} |
442
|
|
|
|
|
|
|
} |
443
|
|
|
|
|
|
|
|
444
|
20
|
100
|
|
|
|
|
if (inscnt) |
445
|
18
|
|
|
|
|
|
buf[bufpos - inscnt - 1] = inscnt; |
446
|
|
|
|
|
|
|
|
447
|
20
|
50
|
|
|
|
|
if (max_size && bufpos > max_size) { |
|
|
100
|
|
|
|
|
|
448
|
17
|
|
|
|
|
|
git_error_set(GIT_ERROR_NOMEMORY, "delta would be larger than maximum size"); |
449
|
17
|
|
|
|
|
|
git__free(buf); |
450
|
17
|
|
|
|
|
|
return GIT_EBUFS; |
451
|
|
|
|
|
|
|
} |
452
|
|
|
|
|
|
|
|
453
|
3
|
|
|
|
|
|
*out_len = bufpos; |
454
|
3
|
|
|
|
|
|
*out = buf; |
455
|
3
|
|
|
|
|
|
return 0; |
456
|
|
|
|
|
|
|
} |
457
|
|
|
|
|
|
|
|
458
|
|
|
|
|
|
|
/* |
459
|
|
|
|
|
|
|
* Delta application was heavily cribbed from BinaryDelta.java in JGit, which |
460
|
|
|
|
|
|
|
* itself was heavily cribbed from patch-delta.c in the |
461
|
|
|
|
|
|
|
* GIT project. The original delta patching code was written by |
462
|
|
|
|
|
|
|
* Nicolas Pitre . |
463
|
|
|
|
|
|
|
*/ |
464
|
|
|
|
|
|
|
|
465
|
4
|
|
|
|
|
|
static int hdr_sz( |
466
|
|
|
|
|
|
|
size_t *size, |
467
|
|
|
|
|
|
|
const unsigned char **delta, |
468
|
|
|
|
|
|
|
const unsigned char *end) |
469
|
|
|
|
|
|
|
{ |
470
|
4
|
|
|
|
|
|
const unsigned char *d = *delta; |
471
|
4
|
|
|
|
|
|
size_t r = 0; |
472
|
4
|
|
|
|
|
|
unsigned int c, shift = 0; |
473
|
|
|
|
|
|
|
|
474
|
|
|
|
|
|
|
do { |
475
|
4
|
50
|
|
|
|
|
if (d == end) { |
476
|
0
|
|
|
|
|
|
git_error_set(GIT_ERROR_INVALID, "truncated delta"); |
477
|
0
|
|
|
|
|
|
return -1; |
478
|
|
|
|
|
|
|
} |
479
|
|
|
|
|
|
|
|
480
|
4
|
|
|
|
|
|
c = *d++; |
481
|
4
|
|
|
|
|
|
r |= (c & 0x7f) << shift; |
482
|
4
|
|
|
|
|
|
shift += 7; |
483
|
4
|
50
|
|
|
|
|
} while (c & 0x80); |
484
|
4
|
|
|
|
|
|
*delta = d; |
485
|
4
|
|
|
|
|
|
*size = r; |
486
|
4
|
|
|
|
|
|
return 0; |
487
|
|
|
|
|
|
|
} |
488
|
|
|
|
|
|
|
|
489
|
0
|
|
|
|
|
|
int git_delta_read_header( |
490
|
|
|
|
|
|
|
size_t *base_out, |
491
|
|
|
|
|
|
|
size_t *result_out, |
492
|
|
|
|
|
|
|
const unsigned char *delta, |
493
|
|
|
|
|
|
|
size_t delta_len) |
494
|
|
|
|
|
|
|
{ |
495
|
0
|
|
|
|
|
|
const unsigned char *delta_end = delta + delta_len; |
496
|
0
|
|
|
|
|
|
if ((hdr_sz(base_out, &delta, delta_end) < 0) || |
497
|
0
|
|
|
|
|
|
(hdr_sz(result_out, &delta, delta_end) < 0)) |
498
|
0
|
|
|
|
|
|
return -1; |
499
|
0
|
|
|
|
|
|
return 0; |
500
|
|
|
|
|
|
|
} |
501
|
|
|
|
|
|
|
|
502
|
|
|
|
|
|
|
#define DELTA_HEADER_BUFFER_LEN 16 |
503
|
0
|
|
|
|
|
|
int git_delta_read_header_fromstream( |
504
|
|
|
|
|
|
|
size_t *base_sz, size_t *res_sz, git_packfile_stream *stream) |
505
|
|
|
|
|
|
|
{ |
506
|
|
|
|
|
|
|
static const size_t buffer_len = DELTA_HEADER_BUFFER_LEN; |
507
|
|
|
|
|
|
|
unsigned char buffer[DELTA_HEADER_BUFFER_LEN]; |
508
|
|
|
|
|
|
|
const unsigned char *delta, *delta_end; |
509
|
|
|
|
|
|
|
size_t len; |
510
|
|
|
|
|
|
|
ssize_t read; |
511
|
|
|
|
|
|
|
|
512
|
0
|
|
|
|
|
|
len = read = 0; |
513
|
0
|
0
|
|
|
|
|
while (len < buffer_len) { |
514
|
0
|
|
|
|
|
|
read = git_packfile_stream_read(stream, &buffer[len], buffer_len - len); |
515
|
|
|
|
|
|
|
|
516
|
0
|
0
|
|
|
|
|
if (read == 0) |
517
|
0
|
|
|
|
|
|
break; |
518
|
|
|
|
|
|
|
|
519
|
0
|
0
|
|
|
|
|
if (read == GIT_EBUFS) |
520
|
0
|
|
|
|
|
|
continue; |
521
|
|
|
|
|
|
|
|
522
|
0
|
|
|
|
|
|
len += read; |
523
|
|
|
|
|
|
|
} |
524
|
|
|
|
|
|
|
|
525
|
0
|
|
|
|
|
|
delta = buffer; |
526
|
0
|
|
|
|
|
|
delta_end = delta + len; |
527
|
0
|
|
|
|
|
|
if ((hdr_sz(base_sz, &delta, delta_end) < 0) || |
528
|
0
|
|
|
|
|
|
(hdr_sz(res_sz, &delta, delta_end) < 0)) |
529
|
0
|
|
|
|
|
|
return -1; |
530
|
|
|
|
|
|
|
|
531
|
0
|
|
|
|
|
|
return 0; |
532
|
|
|
|
|
|
|
} |
533
|
|
|
|
|
|
|
|
534
|
2
|
|
|
|
|
|
int git_delta_apply( |
535
|
|
|
|
|
|
|
void **out, |
536
|
|
|
|
|
|
|
size_t *out_len, |
537
|
|
|
|
|
|
|
const unsigned char *base, |
538
|
|
|
|
|
|
|
size_t base_len, |
539
|
|
|
|
|
|
|
const unsigned char *delta, |
540
|
|
|
|
|
|
|
size_t delta_len) |
541
|
|
|
|
|
|
|
{ |
542
|
2
|
|
|
|
|
|
const unsigned char *delta_end = delta + delta_len; |
543
|
|
|
|
|
|
|
size_t base_sz, res_sz, alloc_sz; |
544
|
|
|
|
|
|
|
unsigned char *res_dp; |
545
|
|
|
|
|
|
|
|
546
|
2
|
|
|
|
|
|
*out = NULL; |
547
|
2
|
|
|
|
|
|
*out_len = 0; |
548
|
|
|
|
|
|
|
|
549
|
|
|
|
|
|
|
/* |
550
|
|
|
|
|
|
|
* Check that the base size matches the data we were given; |
551
|
|
|
|
|
|
|
* if not we would underflow while accessing data from the |
552
|
|
|
|
|
|
|
* base object, resulting in data corruption or segfault. |
553
|
|
|
|
|
|
|
*/ |
554
|
2
|
50
|
|
|
|
|
if ((hdr_sz(&base_sz, &delta, delta_end) < 0) || (base_sz != base_len)) { |
|
|
50
|
|
|
|
|
|
555
|
0
|
|
|
|
|
|
git_error_set(GIT_ERROR_INVALID, "failed to apply delta: base size does not match given data"); |
556
|
0
|
|
|
|
|
|
return -1; |
557
|
|
|
|
|
|
|
} |
558
|
|
|
|
|
|
|
|
559
|
2
|
50
|
|
|
|
|
if (hdr_sz(&res_sz, &delta, delta_end) < 0) { |
560
|
0
|
|
|
|
|
|
git_error_set(GIT_ERROR_INVALID, "failed to apply delta: base size does not match given data"); |
561
|
0
|
|
|
|
|
|
return -1; |
562
|
|
|
|
|
|
|
} |
563
|
|
|
|
|
|
|
|
564
|
2
|
50
|
|
|
|
|
GIT_ERROR_CHECK_ALLOC_ADD(&alloc_sz, res_sz, 1); |
|
|
50
|
|
|
|
|
|
565
|
2
|
|
|
|
|
|
res_dp = git__malloc(alloc_sz); |
566
|
2
|
50
|
|
|
|
|
GIT_ERROR_CHECK_ALLOC(res_dp); |
567
|
|
|
|
|
|
|
|
568
|
2
|
|
|
|
|
|
res_dp[res_sz] = '\0'; |
569
|
2
|
|
|
|
|
|
*out = res_dp; |
570
|
2
|
|
|
|
|
|
*out_len = res_sz; |
571
|
|
|
|
|
|
|
|
572
|
4
|
100
|
|
|
|
|
while (delta < delta_end) { |
573
|
2
|
|
|
|
|
|
unsigned char cmd = *delta++; |
574
|
2
|
50
|
|
|
|
|
if (cmd & 0x80) { |
575
|
|
|
|
|
|
|
/* cmd is a copy instruction; copy from the base. */ |
576
|
2
|
|
|
|
|
|
size_t off = 0, len = 0, end; |
577
|
|
|
|
|
|
|
|
578
|
|
|
|
|
|
|
#define ADD_DELTA(o, shift) { if (delta < delta_end) (o) |= ((unsigned) *delta++ << shift); else goto fail; } |
579
|
2
|
50
|
|
|
|
|
if (cmd & 0x01) ADD_DELTA(off, 0UL); |
|
|
0
|
|
|
|
|
|
580
|
2
|
50
|
|
|
|
|
if (cmd & 0x02) ADD_DELTA(off, 8UL); |
|
|
0
|
|
|
|
|
|
581
|
2
|
50
|
|
|
|
|
if (cmd & 0x04) ADD_DELTA(off, 16UL); |
|
|
0
|
|
|
|
|
|
582
|
2
|
50
|
|
|
|
|
if (cmd & 0x08) ADD_DELTA(off, 24UL); |
|
|
0
|
|
|
|
|
|
583
|
|
|
|
|
|
|
|
584
|
2
|
50
|
|
|
|
|
if (cmd & 0x10) ADD_DELTA(len, 0UL); |
|
|
50
|
|
|
|
|
|
585
|
2
|
50
|
|
|
|
|
if (cmd & 0x20) ADD_DELTA(len, 8UL); |
|
|
0
|
|
|
|
|
|
586
|
2
|
50
|
|
|
|
|
if (cmd & 0x40) ADD_DELTA(len, 16UL); |
|
|
0
|
|
|
|
|
|
587
|
2
|
50
|
|
|
|
|
if (!len) len = 0x10000; |
588
|
|
|
|
|
|
|
#undef ADD_DELTA |
589
|
|
|
|
|
|
|
|
590
|
2
|
50
|
|
|
|
|
if (GIT_ADD_SIZET_OVERFLOW(&end, off, len) || |
|
|
50
|
|
|
|
|
|
591
|
2
|
50
|
|
|
|
|
base_len < end || res_sz < len) |
592
|
|
|
|
|
|
|
goto fail; |
593
|
|
|
|
|
|
|
|
594
|
2
|
|
|
|
|
|
memcpy(res_dp, base + off, len); |
595
|
2
|
|
|
|
|
|
res_dp += len; |
596
|
2
|
|
|
|
|
|
res_sz -= len; |
597
|
|
|
|
|
|
|
|
598
|
0
|
0
|
|
|
|
|
} else if (cmd) { |
599
|
|
|
|
|
|
|
/* |
600
|
|
|
|
|
|
|
* cmd is a literal insert instruction; copy from |
601
|
|
|
|
|
|
|
* the delta stream itself. |
602
|
|
|
|
|
|
|
*/ |
603
|
0
|
0
|
|
|
|
|
if (delta_end - delta < cmd || res_sz < cmd) |
|
|
0
|
|
|
|
|
|
604
|
|
|
|
|
|
|
goto fail; |
605
|
0
|
|
|
|
|
|
memcpy(res_dp, delta, cmd); |
606
|
0
|
|
|
|
|
|
delta += cmd; |
607
|
0
|
|
|
|
|
|
res_dp += cmd; |
608
|
0
|
|
|
|
|
|
res_sz -= cmd; |
609
|
|
|
|
|
|
|
|
610
|
|
|
|
|
|
|
} else { |
611
|
|
|
|
|
|
|
/* cmd == 0 is reserved for future encodings. */ |
612
|
0
|
|
|
|
|
|
goto fail; |
613
|
|
|
|
|
|
|
} |
614
|
|
|
|
|
|
|
} |
615
|
|
|
|
|
|
|
|
616
|
2
|
50
|
|
|
|
|
if (delta != delta_end || res_sz) |
|
|
50
|
|
|
|
|
|
617
|
|
|
|
|
|
|
goto fail; |
618
|
2
|
|
|
|
|
|
return 0; |
619
|
|
|
|
|
|
|
|
620
|
|
|
|
|
|
|
fail: |
621
|
0
|
|
|
|
|
|
git__free(*out); |
622
|
|
|
|
|
|
|
|
623
|
0
|
|
|
|
|
|
*out = NULL; |
624
|
0
|
|
|
|
|
|
*out_len = 0; |
625
|
|
|
|
|
|
|
|
626
|
0
|
|
|
|
|
|
git_error_set(GIT_ERROR_INVALID, "failed to apply delta"); |
627
|
2
|
|
|
|
|
|
return -1; |
628
|
|
|
|
|
|
|
} |