]>
Commit | Line | Data |
---|---|---|
c15648cb | 1 | /* |
359fc2d2 | 2 | * Copyright (C) the libgit2 contributors. All rights reserved. |
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 | ||
eae0bfdc PP |
8 | #include "oid.h" |
9 | ||
44908fe7 | 10 | #include "git2/oid.h" |
58519018 | 11 | #include "repository.h" |
4ca0b566 | 12 | #include "global.h" |
c15648cb | 13 | #include <string.h> |
26022f07 | 14 | #include <limits.h> |
c15648cb | 15 | |
af795e49 | 16 | static char to_hex[] = "0123456789abcdef"; |
c15648cb | 17 | |
7c7ff7d1 RB |
18 | static int oid_error_invalid(const char *msg) |
19 | { | |
ac3d33df | 20 | git_error_set(GIT_ERROR_INVALID, "unable to parse OID - %s", msg); |
7c7ff7d1 RB |
21 | return -1; |
22 | } | |
23 | ||
d5afc039 | 24 | int git_oid_fromstrn(git_oid *out, const char *str, size_t length) |
c15648cb | 25 | { |
0ef9d2aa | 26 | size_t p; |
e724b058 | 27 | int v; |
d5afc039 | 28 | |
00258cc0 | 29 | assert(out && str); |
d5afc039 | 30 | |
00258cc0 JP |
31 | if (!length) |
32 | return oid_error_invalid("too short"); | |
d5afc039 | 33 | |
00258cc0 JP |
34 | if (length > GIT_OID_HEXSZ) |
35 | return oid_error_invalid("too long"); | |
d5afc039 | 36 | |
00258cc0 | 37 | memset(out->id, 0, GIT_OID_RAWSZ); |
d5afc039 | 38 | |
00258cc0 JP |
39 | for (p = 0; p < length; p++) { |
40 | v = git__fromhex(str[p]); | |
0e058e78 | 41 | if (v < 0) |
7c7ff7d1 | 42 | return oid_error_invalid("contains invalid characters"); |
0e058e78 | 43 | |
00258cc0 | 44 | out->id[p / 2] |= (unsigned char)(v << (p % 2 ? 0 : 4)); |
e724b058 DI |
45 | } |
46 | ||
7c7ff7d1 | 47 | return 0; |
c15648cb | 48 | } |
af795e49 | 49 | |
0c8efb38 X |
50 | int git_oid_fromstrp(git_oid *out, const char *str) |
51 | { | |
1e7b7523 | 52 | return git_oid_fromstrn(out, str, strlen(str)); |
0c8efb38 X |
53 | } |
54 | ||
d5afc039 VM |
55 | int git_oid_fromstr(git_oid *out, const char *str) |
56 | { | |
57 | return git_oid_fromstrn(out, str, GIT_OID_HEXSZ); | |
58 | } | |
59 | ||
213e720c | 60 | GIT_INLINE(char) *fmt_one(char *str, unsigned int val) |
af795e49 SP |
61 | { |
62 | *str++ = to_hex[val >> 4]; | |
63 | *str++ = to_hex[val & 0xf]; | |
64 | return str; | |
65 | } | |
66 | ||
22a2d3d5 | 67 | int git_oid_nfmt(char *str, size_t n, const git_oid *oid) |
af795e49 | 68 | { |
660d59ca RB |
69 | size_t i, max_i; |
70 | ||
71 | if (!oid) { | |
72 | memset(str, 0, n); | |
22a2d3d5 | 73 | return 0; |
660d59ca RB |
74 | } |
75 | if (n > GIT_OID_HEXSZ) { | |
76 | memset(&str[GIT_OID_HEXSZ], 0, n - GIT_OID_HEXSZ); | |
77 | n = GIT_OID_HEXSZ; | |
78 | } | |
79 | ||
80 | max_i = n / 2; | |
af795e49 | 81 | |
660d59ca | 82 | for (i = 0; i < max_i; i++) |
af795e49 | 83 | str = fmt_one(str, oid->id[i]); |
660d59ca RB |
84 | |
85 | if (n & 1) | |
86 | *str++ = to_hex[oid->id[i] >> 4]; | |
22a2d3d5 UG |
87 | |
88 | return 0; | |
660d59ca RB |
89 | } |
90 | ||
22a2d3d5 | 91 | int git_oid_fmt(char *str, const git_oid *oid) |
660d59ca | 92 | { |
22a2d3d5 | 93 | return git_oid_nfmt(str, GIT_OID_HEXSZ, oid); |
af795e49 SP |
94 | } |
95 | ||
22a2d3d5 | 96 | int git_oid_pathfmt(char *str, const git_oid *oid) |
af795e49 | 97 | { |
0ef9d2aa | 98 | size_t i; |
af795e49 SP |
99 | |
100 | str = fmt_one(str, oid->id[0]); | |
101 | *str++ = '/'; | |
102 | for (i = 1; i < sizeof(oid->id); i++) | |
103 | str = fmt_one(str, oid->id[i]); | |
22a2d3d5 UG |
104 | |
105 | return 0; | |
af795e49 SP |
106 | } |
107 | ||
4ca0b566 VM |
108 | char *git_oid_tostr_s(const git_oid *oid) |
109 | { | |
110 | char *str = GIT_GLOBAL->oid_fmt; | |
111 | git_oid_nfmt(str, GIT_OID_HEXSZ + 1, oid); | |
112 | return str; | |
113 | } | |
114 | ||
af795e49 SP |
115 | char *git_oid_allocfmt(const git_oid *oid) |
116 | { | |
64a47c01 | 117 | char *str = git__malloc(GIT_OID_HEXSZ + 1); |
af795e49 SP |
118 | if (!str) |
119 | return NULL; | |
660d59ca | 120 | git_oid_nfmt(str, GIT_OID_HEXSZ + 1, oid); |
af795e49 SP |
121 | return str; |
122 | } | |
960ca1d7 | 123 | |
5621d809 | 124 | char *git_oid_tostr(char *out, size_t n, const git_oid *oid) |
960ca1d7 | 125 | { |
8fe713cc | 126 | if (!out || n == 0) |
960ca1d7 RJ |
127 | return ""; |
128 | ||
660d59ca RB |
129 | if (n > GIT_OID_HEXSZ + 1) |
130 | n = GIT_OID_HEXSZ + 1; | |
960ca1d7 | 131 | |
660d59ca RB |
132 | git_oid_nfmt(out, n - 1, oid); /* allow room for terminating NUL */ |
133 | out[n - 1] = '\0'; | |
960ca1d7 RJ |
134 | |
135 | return out; | |
136 | } | |
137 | ||
7c7ff7d1 RB |
138 | int git_oid__parse( |
139 | git_oid *oid, const char **buffer_out, | |
140 | const char *buffer_end, const char *header) | |
58519018 VM |
141 | { |
142 | const size_t sha_len = GIT_OID_HEXSZ; | |
143 | const size_t header_len = strlen(header); | |
144 | ||
720d5472 | 145 | const char *buffer = *buffer_out; |
58519018 VM |
146 | |
147 | if (buffer + (header_len + sha_len + 1) > buffer_end) | |
73fe6a8e | 148 | return -1; |
58519018 VM |
149 | |
150 | if (memcmp(buffer, header, header_len) != 0) | |
73fe6a8e | 151 | return -1; |
58519018 VM |
152 | |
153 | if (buffer[header_len + sha_len] != '\n') | |
73fe6a8e | 154 | return -1; |
58519018 | 155 | |
7c7ff7d1 RB |
156 | if (git_oid_fromstr(oid, buffer + header_len) < 0) |
157 | return -1; | |
58519018 VM |
158 | |
159 | *buffer_out = buffer + (header_len + sha_len + 1); | |
160 | ||
7c7ff7d1 | 161 | return 0; |
58519018 VM |
162 | } |
163 | ||
afeecf4f VM |
164 | void git_oid__writebuf(git_buf *buf, const char *header, const git_oid *oid) |
165 | { | |
166 | char hex_oid[GIT_OID_HEXSZ]; | |
167 | ||
168 | git_oid_fmt(hex_oid, oid); | |
169 | git_buf_puts(buf, header); | |
170 | git_buf_put(buf, hex_oid, GIT_OID_HEXSZ); | |
171 | git_buf_putc(buf, '\n'); | |
172 | } | |
173 | ||
22a2d3d5 | 174 | int git_oid_fromraw(git_oid *out, const unsigned char *raw) |
d12299fe VM |
175 | { |
176 | memcpy(out->id, raw, sizeof(out->id)); | |
22a2d3d5 | 177 | return 0; |
d12299fe VM |
178 | } |
179 | ||
22a2d3d5 | 180 | int git_oid_cpy(git_oid *out, const git_oid *src) |
d12299fe VM |
181 | { |
182 | memcpy(out->id, src->id, sizeof(out->id)); | |
22a2d3d5 | 183 | return 0; |
d12299fe VM |
184 | } |
185 | ||
b7f167da | 186 | int git_oid_cmp(const git_oid *a, const git_oid *b) |
0c72248b | 187 | { |
b7f167da | 188 | return git_oid__cmp(a, b); |
0c72248b RB |
189 | } |
190 | ||
978a4ed5 RB |
191 | int git_oid_equal(const git_oid *a, const git_oid *b) |
192 | { | |
193 | return (git_oid__cmp(a, b) == 0); | |
194 | } | |
195 | ||
b8457baa | 196 | int git_oid_ncmp(const git_oid *oid_a, const git_oid *oid_b, size_t len) |
53c0bd81 | 197 | { |
f1d01851 VM |
198 | const unsigned char *a = oid_a->id; |
199 | const unsigned char *b = oid_b->id; | |
200 | ||
8564a022 RB |
201 | if (len > GIT_OID_HEXSZ) |
202 | len = GIT_OID_HEXSZ; | |
203 | ||
204 | while (len > 1) { | |
f1d01851 VM |
205 | if (*a != *b) |
206 | return 1; | |
207 | a++; | |
208 | b++; | |
209 | len -= 2; | |
8564a022 | 210 | }; |
f1d01851 VM |
211 | |
212 | if (len) | |
213 | if ((*a ^ *b) & 0xf0) | |
214 | return 1; | |
215 | ||
216 | return 0; | |
53c0bd81 MP |
217 | } |
218 | ||
aa8f0101 | 219 | int git_oid_strcmp(const git_oid *oid_a, const char *str) |
34aff010 | 220 | { |
ea66215d | 221 | const unsigned char *a; |
aa8f0101 RB |
222 | unsigned char strval; |
223 | int hexval; | |
224 | ||
225 | for (a = oid_a->id; *str && (a - oid_a->id) < GIT_OID_RAWSZ; ++a) { | |
226 | if ((hexval = git__fromhex(*str++)) < 0) | |
227 | return -1; | |
66566516 | 228 | strval = (unsigned char)(hexval << 4); |
aa8f0101 RB |
229 | if (*str) { |
230 | if ((hexval = git__fromhex(*str++)) < 0) | |
231 | return -1; | |
232 | strval |= hexval; | |
233 | } | |
234 | if (*a != strval) | |
235 | return (*a - strval); | |
236 | } | |
34aff010 | 237 | |
aa8f0101 RB |
238 | return 0; |
239 | } | |
34aff010 | 240 | |
aa8f0101 RB |
241 | int git_oid_streq(const git_oid *oid_a, const char *str) |
242 | { | |
243 | return git_oid_strcmp(oid_a, str) == 0 ? 0 : -1; | |
34aff010 | 244 | } |
245 | ||
22a2d3d5 | 246 | int git_oid_is_zero(const git_oid *oid_a) |
74fa4bfa RB |
247 | { |
248 | const unsigned char *a = oid_a->id; | |
249 | unsigned int i; | |
250 | for (i = 0; i < GIT_OID_RAWSZ; ++i, ++a) | |
251 | if (*a != 0) | |
252 | return 0; | |
253 | return 1; | |
254 | } | |
255 | ||
22a2d3d5 UG |
256 | #ifndef GIT_DEPRECATE_HARD |
257 | int git_oid_iszero(const git_oid *oid_a) | |
258 | { | |
259 | return git_oid_is_zero(oid_a); | |
260 | } | |
261 | #endif | |
262 | ||
26022f07 VM |
263 | typedef short node_index; |
264 | ||
265 | typedef union { | |
266 | const char *tail; | |
267 | node_index children[16]; | |
268 | } trie_node; | |
269 | ||
270 | struct git_oid_shorten { | |
271 | trie_node *nodes; | |
272 | size_t node_count, size; | |
273 | int min_length, full; | |
274 | }; | |
275 | ||
276 | static int resize_trie(git_oid_shorten *self, size_t new_size) | |
277 | { | |
3603cb09 | 278 | self->nodes = git__reallocarray(self->nodes, new_size, sizeof(trie_node)); |
ac3d33df | 279 | GIT_ERROR_CHECK_ALLOC(self->nodes); |
26022f07 VM |
280 | |
281 | if (new_size > self->size) { | |
282 | memset(&self->nodes[self->size], 0x0, (new_size - self->size) * sizeof(trie_node)); | |
283 | } | |
284 | ||
285 | self->size = new_size; | |
7c7ff7d1 | 286 | return 0; |
26022f07 VM |
287 | } |
288 | ||
289 | static trie_node *push_leaf(git_oid_shorten *os, node_index idx, int push_at, const char *oid) | |
290 | { | |
291 | trie_node *node, *leaf; | |
292 | node_index idx_leaf; | |
293 | ||
294 | if (os->node_count >= os->size) { | |
7c7ff7d1 | 295 | if (resize_trie(os, os->size * 2) < 0) |
26022f07 VM |
296 | return NULL; |
297 | } | |
298 | ||
299 | idx_leaf = (node_index)os->node_count++; | |
300 | ||
52f537e9 | 301 | if (os->node_count == SHRT_MAX) { |
26022f07 | 302 | os->full = 1; |
52f537e9 AW |
303 | return NULL; |
304 | } | |
26022f07 VM |
305 | |
306 | node = &os->nodes[idx]; | |
307 | node->children[push_at] = -idx_leaf; | |
308 | ||
309 | leaf = &os->nodes[idx_leaf]; | |
310 | leaf->tail = oid; | |
311 | ||
312 | return node; | |
313 | } | |
314 | ||
315 | git_oid_shorten *git_oid_shorten_new(size_t min_length) | |
316 | { | |
317 | git_oid_shorten *os; | |
318 | ||
44ef8b1b RB |
319 | assert((size_t)((int)min_length) == min_length); |
320 | ||
7c7ff7d1 | 321 | os = git__calloc(1, sizeof(git_oid_shorten)); |
26022f07 VM |
322 | if (os == NULL) |
323 | return NULL; | |
324 | ||
7c7ff7d1 | 325 | if (resize_trie(os, 16) < 0) { |
3286c408 | 326 | git__free(os); |
26022f07 VM |
327 | return NULL; |
328 | } | |
329 | ||
330 | os->node_count = 1; | |
44ef8b1b | 331 | os->min_length = (int)min_length; |
26022f07 VM |
332 | |
333 | return os; | |
334 | } | |
335 | ||
336 | void git_oid_shorten_free(git_oid_shorten *os) | |
337 | { | |
32b7e84e BR |
338 | if (os == NULL) |
339 | return; | |
340 | ||
3286c408 VM |
341 | git__free(os->nodes); |
342 | git__free(os); | |
26022f07 VM |
343 | } |
344 | ||
345 | ||
346 | /* | |
347 | * What wizardry is this? | |
348 | * | |
349 | * This is just a memory-optimized trie: basically a very fancy | |
350 | * 16-ary tree, which is used to store the prefixes of the OID | |
351 | * strings. | |
352 | * | |
353 | * Read more: http://en.wikipedia.org/wiki/Trie | |
354 | * | |
355 | * Magic that happens in this method: | |
356 | * | |
357 | * - Each node in the trie is an union, so it can work both as | |
358 | * a normal node, or as a leaf. | |
359 | * | |
360 | * - Each normal node points to 16 children (one for each possible | |
361 | * character in the oid). This is *not* stored in an array of | |
932d1baf | 362 | * pointers, because in a 64-bit arch this would be sucking |
826bc4a8 | 363 | * 16*sizeof(void*) = 128 bytes of memory per node, which is |
26022f07 VM |
364 | * insane. What we do is store Node Indexes, and use these indexes |
365 | * to look up each node in the om->index array. These indexes are | |
366 | * signed shorts, so this limits the amount of unique OIDs that | |
367 | * fit in the structure to about 20000 (assuming a more or less uniform | |
368 | * distribution). | |
369 | * | |
370 | * - All the nodes in om->index array are stored contiguously in | |
371 | * memory, and each of them is 32 bytes, so we fit 2x nodes per | |
372 | * cache line. Convenient for speed. | |
373 | * | |
374 | * - To differentiate the leafs from the normal nodes, we store all | |
375 | * the indexes towards a leaf as a negative index (indexes to normal | |
376 | * nodes are positives). When we find that one of the children for | |
377 | * a node has a negative value, that means it's going to be a leaf. | |
378 | * This reduces the amount of indexes we have by two, but also reduces | |
379 | * the size of each node by 1-4 bytes (the amount we would need to | |
380 | * add a `is_leaf` field): this is good because it allows the nodes | |
381 | * to fit cleanly in cache lines. | |
382 | * | |
383 | * - Once we reach an empty children, instead of continuing to insert | |
384 | * new nodes for each remaining character of the OID, we store a pointer | |
385 | * to the tail in the leaf; if the leaf is reached again, we turn it | |
386 | * into a normal node and use the tail to create a new leaf. | |
387 | * | |
388 | * This is a pretty good balance between performance and memory usage. | |
389 | */ | |
390 | int git_oid_shorten_add(git_oid_shorten *os, const char *text_oid) | |
391 | { | |
44ef8b1b RB |
392 | int i; |
393 | bool is_leaf; | |
26022f07 VM |
394 | node_index idx; |
395 | ||
d45e9480 | 396 | if (os->full) { |
ac3d33df | 397 | git_error_set(GIT_ERROR_INVALID, "unable to shorten OID - OID set full"); |
7c7ff7d1 | 398 | return -1; |
d45e9480 | 399 | } |
26022f07 | 400 | |
f0ab9fda VM |
401 | if (text_oid == NULL) |
402 | return os->min_length; | |
403 | ||
26022f07 | 404 | idx = 0; |
44ef8b1b | 405 | is_leaf = false; |
26022f07 VM |
406 | |
407 | for (i = 0; i < GIT_OID_HEXSZ; ++i) { | |
eb8de747 | 408 | int c = git__fromhex(text_oid[i]); |
26022f07 VM |
409 | trie_node *node; |
410 | ||
7c7ff7d1 | 411 | if (c == -1) { |
ac3d33df | 412 | git_error_set(GIT_ERROR_INVALID, "unable to shorten OID - invalid hex value"); |
7c7ff7d1 RB |
413 | return -1; |
414 | } | |
26022f07 VM |
415 | |
416 | node = &os->nodes[idx]; | |
417 | ||
418 | if (is_leaf) { | |
419 | const char *tail; | |
420 | ||
421 | tail = node->tail; | |
422 | node->tail = NULL; | |
423 | ||
eb8de747 | 424 | node = push_leaf(os, idx, git__fromhex(tail[0]), &tail[1]); |
d45e9480 L |
425 | if (node == NULL) { |
426 | if (os->full) | |
ac3d33df | 427 | git_error_set(GIT_ERROR_INVALID, "unable to shorten OID - OID set full"); |
d45e9480 L |
428 | return -1; |
429 | } | |
26022f07 VM |
430 | } |
431 | ||
432 | if (node->children[c] == 0) { | |
d45e9480 L |
433 | if (push_leaf(os, idx, c, &text_oid[i + 1]) == NULL) { |
434 | if (os->full) | |
ac3d33df | 435 | git_error_set(GIT_ERROR_INVALID, "unable to shorten OID - OID set full"); |
7c7ff7d1 | 436 | return -1; |
d45e9480 | 437 | } |
26022f07 VM |
438 | break; |
439 | } | |
440 | ||
441 | idx = node->children[c]; | |
44ef8b1b | 442 | is_leaf = false; |
26022f07 VM |
443 | |
444 | if (idx < 0) { | |
445 | node->children[c] = idx = -idx; | |
44ef8b1b | 446 | is_leaf = true; |
26022f07 VM |
447 | } |
448 | } | |
449 | ||
450 | if (++i > os->min_length) | |
451 | os->min_length = i; | |
452 | ||
453 | return os->min_length; | |
454 | } | |
455 |