]>
Commit | Line | Data |
---|---|---|
c15648cb | 1 | /* |
bb742ede | 2 | * Copyright (C) 2009-2011 the libgit2 contributors |
c15648cb | 3 | * |
bb742ede VM |
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. | |
c15648cb SP |
6 | */ |
7 | ||
b3be0fc7 | 8 | #include "common.h" |
44908fe7 | 9 | #include "git2/oid.h" |
58519018 | 10 | #include "repository.h" |
c15648cb | 11 | #include <string.h> |
26022f07 | 12 | #include <limits.h> |
c15648cb SP |
13 | |
14 | static signed char from_hex[] = { | |
15 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 00 */ | |
16 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 10 */ | |
17 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 20 */ | |
87d9869f | 18 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, /* 30 */ |
c15648cb SP |
19 | -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 40 */ |
20 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 50 */ | |
21 | -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 60 */ | |
22 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 70 */ | |
23 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 80 */ | |
24 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* 90 */ | |
25 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* a0 */ | |
26 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* b0 */ | |
27 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* c0 */ | |
28 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* d0 */ | |
29 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* e0 */ | |
30 | -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* f0 */ | |
31 | }; | |
af795e49 | 32 | static char to_hex[] = "0123456789abcdef"; |
c15648cb | 33 | |
d5afc039 | 34 | int git_oid_fromstrn(git_oid *out, const char *str, size_t length) |
c15648cb | 35 | { |
0ef9d2aa | 36 | size_t p; |
d5afc039 VM |
37 | |
38 | if (length > GIT_OID_HEXSZ) | |
39 | length = GIT_OID_HEXSZ; | |
40 | ||
41 | if (length % 2) | |
42 | length--; | |
43 | ||
44 | for (p = 0; p < length; p += 2) { | |
45 | int v = (from_hex[(unsigned char)str[p + 0]] << 4) | |
87d9869f | 46 | | from_hex[(unsigned char)str[p + 1]]; |
d5afc039 | 47 | |
c15648cb | 48 | if (v < 0) |
bea54842 | 49 | return git__throw(GIT_ENOTOID, "Failed to generate sha1. Given string is not a valid sha1 hash"); |
d5afc039 VM |
50 | |
51 | out->id[p / 2] = (unsigned char)v; | |
c15648cb | 52 | } |
d5afc039 VM |
53 | |
54 | for (; p < GIT_OID_HEXSZ; p += 2) | |
55 | out->id[p / 2] = 0x0; | |
56 | ||
c15648cb SP |
57 | return GIT_SUCCESS; |
58 | } | |
af795e49 | 59 | |
d5afc039 VM |
60 | int git_oid_fromstr(git_oid *out, const char *str) |
61 | { | |
62 | return git_oid_fromstrn(out, str, GIT_OID_HEXSZ); | |
63 | } | |
64 | ||
213e720c | 65 | GIT_INLINE(char) *fmt_one(char *str, unsigned int val) |
af795e49 SP |
66 | { |
67 | *str++ = to_hex[val >> 4]; | |
68 | *str++ = to_hex[val & 0xf]; | |
69 | return str; | |
70 | } | |
71 | ||
72 | void git_oid_fmt(char *str, const git_oid *oid) | |
73 | { | |
0ef9d2aa | 74 | size_t i; |
af795e49 SP |
75 | |
76 | for (i = 0; i < sizeof(oid->id); i++) | |
77 | str = fmt_one(str, oid->id[i]); | |
78 | } | |
79 | ||
80 | void git_oid_pathfmt(char *str, const git_oid *oid) | |
81 | { | |
0ef9d2aa | 82 | size_t i; |
af795e49 SP |
83 | |
84 | str = fmt_one(str, oid->id[0]); | |
85 | *str++ = '/'; | |
86 | for (i = 1; i < sizeof(oid->id); i++) | |
87 | str = fmt_one(str, oid->id[i]); | |
88 | } | |
89 | ||
90 | char *git_oid_allocfmt(const git_oid *oid) | |
91 | { | |
64a47c01 | 92 | char *str = git__malloc(GIT_OID_HEXSZ + 1); |
af795e49 SP |
93 | if (!str) |
94 | return NULL; | |
95 | git_oid_fmt(str, oid); | |
96 | str[GIT_OID_HEXSZ] = '\0'; | |
97 | return str; | |
98 | } | |
960ca1d7 RJ |
99 | |
100 | char *git_oid_to_string(char *out, size_t n, const git_oid *oid) | |
101 | { | |
102 | char str[GIT_OID_HEXSZ]; | |
103 | ||
104 | if (!out || n == 0 || !oid) | |
105 | return ""; | |
106 | ||
87d9869f | 107 | n--; /* allow room for terminating NUL */ |
960ca1d7 RJ |
108 | |
109 | if (n > 0) { | |
110 | git_oid_fmt(str, oid); | |
552e23ba RJ |
111 | if (n > GIT_OID_HEXSZ) |
112 | n = GIT_OID_HEXSZ; | |
113 | memcpy(out, str, n); | |
960ca1d7 RJ |
114 | } |
115 | ||
116 | out[n] = '\0'; | |
117 | ||
118 | return out; | |
119 | } | |
120 | ||
06c43821 | 121 | int git_oid__parse(git_oid *oid, const char **buffer_out, |
58519018 VM |
122 | const char *buffer_end, const char *header) |
123 | { | |
124 | const size_t sha_len = GIT_OID_HEXSZ; | |
125 | const size_t header_len = strlen(header); | |
126 | ||
720d5472 | 127 | const char *buffer = *buffer_out; |
58519018 VM |
128 | |
129 | if (buffer + (header_len + sha_len + 1) > buffer_end) | |
bea54842 | 130 | return git__throw(GIT_EOBJCORRUPTED, "Failed to parse OID. Buffer too small"); |
58519018 VM |
131 | |
132 | if (memcmp(buffer, header, header_len) != 0) | |
bea54842 | 133 | return git__throw(GIT_EOBJCORRUPTED, "Failed to parse OID. Buffer and header do not match"); |
58519018 VM |
134 | |
135 | if (buffer[header_len + sha_len] != '\n') | |
bea54842 | 136 | return git__throw(GIT_EOBJCORRUPTED, "Failed to parse OID. Buffer not terminated correctly"); |
58519018 | 137 | |
fa48608e | 138 | if (git_oid_fromstr(oid, buffer + header_len) < GIT_SUCCESS) |
bea54842 | 139 | return git__throw(GIT_EOBJCORRUPTED, "Failed to parse OID. Failed to generate sha1"); |
58519018 VM |
140 | |
141 | *buffer_out = buffer + (header_len + sha_len + 1); | |
142 | ||
6f02c3ba | 143 | return GIT_SUCCESS; |
58519018 VM |
144 | } |
145 | ||
afeecf4f VM |
146 | void git_oid__writebuf(git_buf *buf, const char *header, const git_oid *oid) |
147 | { | |
148 | char hex_oid[GIT_OID_HEXSZ]; | |
149 | ||
150 | git_oid_fmt(hex_oid, oid); | |
151 | git_buf_puts(buf, header); | |
152 | git_buf_put(buf, hex_oid, GIT_OID_HEXSZ); | |
153 | git_buf_putc(buf, '\n'); | |
154 | } | |
155 | ||
fa48608e | 156 | void git_oid_fromraw(git_oid *out, const unsigned char *raw) |
d12299fe VM |
157 | { |
158 | memcpy(out->id, raw, sizeof(out->id)); | |
159 | } | |
160 | ||
161 | void git_oid_cpy(git_oid *out, const git_oid *src) | |
162 | { | |
163 | memcpy(out->id, src->id, sizeof(out->id)); | |
164 | } | |
165 | ||
166 | int git_oid_cmp(const git_oid *a, const git_oid *b) | |
167 | { | |
168 | return memcmp(a->id, b->id, sizeof(a->id)); | |
169 | } | |
26022f07 | 170 | |
f1d01851 | 171 | int git_oid_ncmp(const git_oid *oid_a, const git_oid *oid_b, unsigned int len) |
53c0bd81 | 172 | { |
f1d01851 VM |
173 | const unsigned char *a = oid_a->id; |
174 | const unsigned char *b = oid_b->id; | |
175 | ||
176 | do { | |
177 | if (*a != *b) | |
178 | return 1; | |
179 | a++; | |
180 | b++; | |
181 | len -= 2; | |
182 | } while (len > 1); | |
183 | ||
184 | if (len) | |
185 | if ((*a ^ *b) & 0xf0) | |
186 | return 1; | |
187 | ||
188 | return 0; | |
53c0bd81 MP |
189 | } |
190 | ||
26022f07 VM |
191 | typedef short node_index; |
192 | ||
193 | typedef union { | |
194 | const char *tail; | |
195 | node_index children[16]; | |
196 | } trie_node; | |
197 | ||
198 | struct git_oid_shorten { | |
199 | trie_node *nodes; | |
200 | size_t node_count, size; | |
201 | int min_length, full; | |
202 | }; | |
203 | ||
204 | static int resize_trie(git_oid_shorten *self, size_t new_size) | |
205 | { | |
206 | self->nodes = realloc(self->nodes, new_size * sizeof(trie_node)); | |
207 | if (self->nodes == NULL) | |
208 | return GIT_ENOMEM; | |
209 | ||
210 | if (new_size > self->size) { | |
211 | memset(&self->nodes[self->size], 0x0, (new_size - self->size) * sizeof(trie_node)); | |
212 | } | |
213 | ||
214 | self->size = new_size; | |
215 | return GIT_SUCCESS; | |
216 | } | |
217 | ||
218 | static trie_node *push_leaf(git_oid_shorten *os, node_index idx, int push_at, const char *oid) | |
219 | { | |
220 | trie_node *node, *leaf; | |
221 | node_index idx_leaf; | |
222 | ||
223 | if (os->node_count >= os->size) { | |
224 | if (resize_trie(os, os->size * 2) < GIT_SUCCESS) | |
225 | return NULL; | |
226 | } | |
227 | ||
228 | idx_leaf = (node_index)os->node_count++; | |
229 | ||
230 | if (os->node_count == SHRT_MAX) | |
231 | os->full = 1; | |
232 | ||
233 | node = &os->nodes[idx]; | |
234 | node->children[push_at] = -idx_leaf; | |
235 | ||
236 | leaf = &os->nodes[idx_leaf]; | |
237 | leaf->tail = oid; | |
238 | ||
239 | return node; | |
240 | } | |
241 | ||
242 | git_oid_shorten *git_oid_shorten_new(size_t min_length) | |
243 | { | |
244 | git_oid_shorten *os; | |
245 | ||
246 | os = git__malloc(sizeof(git_oid_shorten)); | |
247 | if (os == NULL) | |
248 | return NULL; | |
249 | ||
250 | memset(os, 0x0, sizeof(git_oid_shorten)); | |
251 | ||
252 | if (resize_trie(os, 16) < GIT_SUCCESS) { | |
253 | free(os); | |
254 | return NULL; | |
255 | } | |
256 | ||
257 | os->node_count = 1; | |
258 | os->min_length = min_length; | |
259 | ||
260 | return os; | |
261 | } | |
262 | ||
263 | void git_oid_shorten_free(git_oid_shorten *os) | |
264 | { | |
265 | free(os->nodes); | |
266 | free(os); | |
267 | } | |
268 | ||
269 | ||
270 | /* | |
271 | * What wizardry is this? | |
272 | * | |
273 | * This is just a memory-optimized trie: basically a very fancy | |
274 | * 16-ary tree, which is used to store the prefixes of the OID | |
275 | * strings. | |
276 | * | |
277 | * Read more: http://en.wikipedia.org/wiki/Trie | |
278 | * | |
279 | * Magic that happens in this method: | |
280 | * | |
281 | * - Each node in the trie is an union, so it can work both as | |
282 | * a normal node, or as a leaf. | |
283 | * | |
284 | * - Each normal node points to 16 children (one for each possible | |
285 | * character in the oid). This is *not* stored in an array of | |
932d1baf | 286 | * pointers, because in a 64-bit arch this would be sucking |
26022f07 VM |
287 | * 16*sizeof(void*) = 128 bytes of memory per node, which is fucking |
288 | * insane. What we do is store Node Indexes, and use these indexes | |
289 | * to look up each node in the om->index array. These indexes are | |
290 | * signed shorts, so this limits the amount of unique OIDs that | |
291 | * fit in the structure to about 20000 (assuming a more or less uniform | |
292 | * distribution). | |
293 | * | |
294 | * - All the nodes in om->index array are stored contiguously in | |
295 | * memory, and each of them is 32 bytes, so we fit 2x nodes per | |
296 | * cache line. Convenient for speed. | |
297 | * | |
298 | * - To differentiate the leafs from the normal nodes, we store all | |
299 | * the indexes towards a leaf as a negative index (indexes to normal | |
300 | * nodes are positives). When we find that one of the children for | |
301 | * a node has a negative value, that means it's going to be a leaf. | |
302 | * This reduces the amount of indexes we have by two, but also reduces | |
303 | * the size of each node by 1-4 bytes (the amount we would need to | |
304 | * add a `is_leaf` field): this is good because it allows the nodes | |
305 | * to fit cleanly in cache lines. | |
306 | * | |
307 | * - Once we reach an empty children, instead of continuing to insert | |
308 | * new nodes for each remaining character of the OID, we store a pointer | |
309 | * to the tail in the leaf; if the leaf is reached again, we turn it | |
310 | * into a normal node and use the tail to create a new leaf. | |
311 | * | |
312 | * This is a pretty good balance between performance and memory usage. | |
313 | */ | |
314 | int git_oid_shorten_add(git_oid_shorten *os, const char *text_oid) | |
315 | { | |
316 | int i, is_leaf; | |
317 | node_index idx; | |
318 | ||
319 | if (os->full) | |
320 | return GIT_ENOMEM; | |
321 | ||
f0ab9fda VM |
322 | if (text_oid == NULL) |
323 | return os->min_length; | |
324 | ||
26022f07 VM |
325 | idx = 0; |
326 | is_leaf = 0; | |
327 | ||
328 | for (i = 0; i < GIT_OID_HEXSZ; ++i) { | |
329 | int c = from_hex[(int)text_oid[i]]; | |
330 | trie_node *node; | |
331 | ||
332 | if (c == -1) | |
bea54842 | 333 | return git__throw(GIT_ENOTOID, "Failed to shorten OID. Invalid hex value"); |
26022f07 VM |
334 | |
335 | node = &os->nodes[idx]; | |
336 | ||
337 | if (is_leaf) { | |
338 | const char *tail; | |
339 | ||
340 | tail = node->tail; | |
341 | node->tail = NULL; | |
342 | ||
343 | node = push_leaf(os, idx, from_hex[(int)tail[0]], &tail[1]); | |
344 | if (node == NULL) | |
345 | return GIT_ENOMEM; | |
346 | } | |
347 | ||
348 | if (node->children[c] == 0) { | |
349 | if (push_leaf(os, idx, c, &text_oid[i + 1]) == NULL) | |
350 | return GIT_ENOMEM; | |
351 | break; | |
352 | } | |
353 | ||
354 | idx = node->children[c]; | |
355 | is_leaf = 0; | |
356 | ||
357 | if (idx < 0) { | |
358 | node->children[c] = idx = -idx; | |
359 | is_leaf = 1; | |
360 | } | |
361 | } | |
362 | ||
363 | if (++i > os->min_length) | |
364 | os->min_length = i; | |
365 | ||
366 | return os->min_length; | |
367 | } | |
368 |