Line Flow Count Block(s) Source
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 "oid.h"
9 -
10 - #include "git2/oid.h"
11 - #include "repository.h"
12 - #include "global.h"
13 - #include <string.h>
14 - #include <limits.h>
15 -
16 - static char to_hex[] = "0123456789abcdef";
17 -
18 1351 2 static int oid_error_invalid(const char *msg)
19 - {
20 1351 2 git_error_set(GIT_ERROR_INVALID, "unable to parse OID - %s", msg);
21 1351 3 return -1;
22 - }
23 -
24 - 2 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files)int git_oid_fromstrn(git_oid *out, const char *str, size_t length)
25 - {
26 - size_t p;
27 - int v;
28 -
29 - 2-4 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) assert(out && str);
30 -
31 - 5 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) if (!length)
32 - 6 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) return oid_error_invalid("too short");
33 -
34 - 7 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) if (length > GIT_OID_HEXSZ)
35 - 8 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) return oid_error_invalid("too long");
36 -
37 - 9 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) memset(out->id, 0, GIT_OID_RAWSZ);
38 -
39 - 9,16,17 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) for (p = 0; p < length; p++) {
40 - 10 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) v = git__fromhex(str[p]);
41 - 11 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) if (v < 0)
42 - 12 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) return oid_error_invalid("contains invalid characters");
43 -
44 - 13-15 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) out->id[p / 2] |= (unsigned char)(v << (p % 2 ? 0 : 4));
45 - }
46 -
47 - 18 suppressed: function cannot be solved git_oid_fromstrn (automatic due to inconsistent arc counts in .gcda files) return 0;
48 - }
49 -
50 8 2 int git_oid_fromstrp(git_oid *out, const char *str)
51 - {
52 8 2 return git_oid_fromstrn(out, str, strlen(str));
53 - }
54 -
55 98948 2 int git_oid_fromstr(git_oid *out, const char *str)
56 - {
57 98948 2 return git_oid_fromstrn(out, str, GIT_OID_HEXSZ);
58 - }
59 -
60 5657089 2 GIT_INLINE(char) *fmt_one(char *str, unsigned int val)
61 - {
62 5657089 2 *str++ = to_hex[val >> 4];
63 5657089 2 *str++ = to_hex[val & 0xf];
64 5657089 2 return str;
65 - }
66 -
67 244416 2 int git_oid_nfmt(char *str, size_t n, const git_oid *oid)
68 - {
69 - size_t i, max_i;
70 -
71 244416 2 if (!oid) {
72 1 3 memset(str, 0, n);
73 1 3 return 0;
74 - }
75 244415 4 if (n > GIT_OID_HEXSZ) {
76 29880 5 memset(&str[GIT_OID_HEXSZ], 0, n - GIT_OID_HEXSZ);
77 29880 5 n = GIT_OID_HEXSZ;
78 - }
79 -
80 244415 6 max_i = n / 2;
81 -
82 4750308 6,8,9 for (i = 0; i < max_i; i++)
83 4506009 7 str = fmt_one(str, oid->id[i]);
84 -
85 244299 10 if (n & 1)
86 961 11 *str++ = to_hex[oid->id[i] >> 4];
87 -
88 244299 12 return 0;
89 - }
90 -
91 4231 2 int git_oid_fmt(char *str, const git_oid *oid)
92 - {
93 4231 2 return git_oid_nfmt(str, GIT_OID_HEXSZ, oid);
94 - }
95 -
96 66559 2 int git_oid_pathfmt(char *str, const git_oid *oid)
97 - {
98 - size_t i;
99 -
100 66559 2 str = fmt_one(str, oid->id[0]);
101 72019 3 *str++ = '/';
102 1314184 3,5,6 for (i = 1; i < sizeof(oid->id); i++)
103 1247394 4 str = fmt_one(str, oid->id[i]);
104 -
105 66790 7 return 0;
106 - }
107 -
108 321 2 char *git_oid_tostr_s(const git_oid *oid)
109 - {
110 321 2 char *str = GIT_GLOBAL->oid_fmt;
111 321 3 git_oid_nfmt(str, GIT_OID_HEXSZ + 1, oid);
112 321 4 return str;
113 - }
114 -
115 63 2 char *git_oid_allocfmt(const git_oid *oid)
116 - {
117 63 2 char *str = git__malloc(GIT_OID_HEXSZ + 1);
118 63 3 if (!str)
119 ##### 4 return NULL;
120 63 5 git_oid_nfmt(str, GIT_OID_HEXSZ + 1, oid);
121 63 6 return str;
122 - }
123 -
124 - 2 suppressed: function cannot be solved git_oid_tostr (automatic due to inconsistent arc counts in .gcda files)char *git_oid_tostr(char *out, size_t n, const git_oid *oid)
125 - {
126 - 2,3 suppressed: function cannot be solved git_oid_tostr (automatic due to inconsistent arc counts in .gcda files) if (!out || n == 0)
127 - 4 suppressed: function cannot be solved git_oid_tostr (automatic due to inconsistent arc counts in .gcda files) return "";
128 -
129 - 5 suppressed: function cannot be solved git_oid_tostr (automatic due to inconsistent arc counts in .gcda files) if (n > GIT_OID_HEXSZ + 1)
130 - 6 suppressed: function cannot be solved git_oid_tostr (automatic due to inconsistent arc counts in .gcda files) n = GIT_OID_HEXSZ + 1;
131 -
132 - 7 suppressed: function cannot be solved git_oid_tostr (automatic due to inconsistent arc counts in .gcda files) git_oid_nfmt(out, n - 1, oid); /* allow room for terminating NUL */
133 - 8 suppressed: function cannot be solved git_oid_tostr (automatic due to inconsistent arc counts in .gcda files) out[n - 1] = '\0';
134 -
135 - 8 suppressed: function cannot be solved git_oid_tostr (automatic due to inconsistent arc counts in .gcda files) return out;
136 - }
137 -
138 31233 2 int git_oid__parse(
139 - git_oid *oid, const char **buffer_out,
140 - const char *buffer_end, const char *header)
141 - {
142 31233 2 const size_t sha_len = GIT_OID_HEXSZ;
143 31233 2 const size_t header_len = strlen(header);
144 -
145 31233 2 const char *buffer = *buffer_out;
146 -
147 31233 2 if (buffer + (header_len + sha_len + 1) > buffer_end)
148 13 3 return -1;
149 -
150 31220 4 if (memcmp(buffer, header, header_len) != 0)
151 11199 5 return -1;
152 -
153 20021 6 if (buffer[header_len + sha_len] != '\n')
154 4 7 return -1;
155 -
156 20017 8,9 if (git_oid_fromstr(oid, buffer + header_len) < 0)
157 3 10 return -1;
158 -
159 20014 11 *buffer_out = buffer + (header_len + sha_len + 1);
160 -
161 20014 11 return 0;
162 - }
163 -
164 730 2 void git_oid__writebuf(git_buf *buf, const char *header, const git_oid *oid)
165 - {
166 - char hex_oid[GIT_OID_HEXSZ];
167 -
168 730 2 git_oid_fmt(hex_oid, oid);
169 730 3 git_buf_puts(buf, header);
170 730 4 git_buf_put(buf, hex_oid, GIT_OID_HEXSZ);
171 730 5 git_buf_putc(buf, '\n');
172 730 6 }
173 -
174 39177 2 int git_oid_fromraw(git_oid *out, const unsigned char *raw)
175 - {
176 39177 2 memcpy(out->id, raw, sizeof(out->id));
177 39177 2 return 0;
178 - }
179 -
180 816927 2 int git_oid_cpy(git_oid *out, const git_oid *src)
181 - {
182 816927 2 memcpy(out->id, src->id, sizeof(out->id));
183 816927 2 return 0;
184 - }
185 -
186 252091 2 int git_oid_cmp(const git_oid *a, const git_oid *b)
187 - {
188 252091 2 return git_oid__cmp(a, b);
189 - }
190 -
191 16086557 2 int git_oid_equal(const git_oid *a, const git_oid *b)
192 - {
193 16086557 2 return (git_oid__cmp(a, b) == 0);
194 - }
195 -
196 125280 2 int git_oid_ncmp(const git_oid *oid_a, const git_oid *oid_b, size_t len)
197 - {
198 125280 2 const unsigned char *a = oid_a->id;
199 125280 2 const unsigned char *b = oid_b->id;
200 -
201 125280 2 if (len > GIT_OID_HEXSZ)
202 3 3 len = GIT_OID_HEXSZ;
203 -
204 162969 4,8 while (len > 1) {
205 162677 5 if (*a != *b)
206 124988 6 return 1;
207 37689 7 a++;
208 37689 7 b++;
209 37689 7 len -= 2;
210 - };
211 -
212 292 9 if (len)
213 99 10 if ((*a ^ *b) & 0xf0)
214 12 11 return 1;
215 -
216 280 12 return 0;
217 - }
218 -
219 167 2 int git_oid_strcmp(const git_oid *oid_a, const char *str)
220 - {
221 - const unsigned char *a;
222 - unsigned char strval;
223 - int hexval;
224 -
225 3059 2,13-15 for (a = oid_a->id; *str && (a - oid_a->id) < GIT_OID_RAWSZ; ++a) {
226 2915 3,4 if ((hexval = git__fromhex(*str++)) < 0)
227 4 5 return -1;
228 2911 6 strval = (unsigned char)(hexval << 4);
229 2911 6 if (*str) {
230 2909 7,8 if ((hexval = git__fromhex(*str++)) < 0)
231 2 9 return -1;
232 2907 10 strval |= hexval;
233 - }
234 2909 11 if (*a != strval)
235 17 12 return (*a - strval);
236 - }
237 -
238 144 16 return 0;
239 - }
240 -
241 155 2 int git_oid_streq(const git_oid *oid_a, const char *str)
242 - {
243 155 2 return git_oid_strcmp(oid_a, str) == 0 ? 0 : -1;
244 - }
245 -
246 356118 2 int git_oid_is_zero(const git_oid *oid_a)
247 - {
248 356118 2 const unsigned char *a = oid_a->id;
249 - unsigned int i;
250 2881436 2,5,6 for (i = 0; i < GIT_OID_RAWSZ; ++i, ++a)
251 2755185 3 if (*a != 0)
252 229867 4 return 0;
253 126251 7 return 1;
254 - }
255 -
256 - #ifndef GIT_DEPRECATE_HARD
257 ##### 2 int git_oid_iszero(const git_oid *oid_a)
258 - {
259 ##### 2 return git_oid_is_zero(oid_a);
260 - }
261 - #endif
262 -
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 23 2 static int resize_trie(git_oid_shorten *self, size_t new_size)
277 - {
278 23 2 self->nodes = git__reallocarray(self->nodes, new_size, sizeof(trie_node));
279 23 3,4 GIT_ERROR_CHECK_ALLOC(self->nodes);
280 -
281 23 5 if (new_size > self->size) {
282 23 6 memset(&self->nodes[self->size], 0x0, (new_size - self->size) * sizeof(trie_node));
283 - }
284 -
285 23 7 self->size = new_size;
286 23 7 return 0;
287 - }
288 -
289 34177 2 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 34177 2 if (os->node_count >= os->size) {
295 20 3,4 if (resize_trie(os, os->size * 2) < 0)
296 ##### 5 return NULL;
297 - }
298 -
299 34177 6 idx_leaf = (node_index)os->node_count++;
300 -
301 34177 6 if (os->node_count == SHRT_MAX) {
302 1 7 os->full = 1;
303 1 7 return NULL;
304 - }
305 -
306 34176 8 node = &os->nodes[idx];
307 34176 8 node->children[push_at] = -idx_leaf;
308 -
309 34176 8 leaf = &os->nodes[idx_leaf];
310 34176 8 leaf->tail = oid;
311 -
312 34176 8 return node;
313 - }
314 -
315 3 2 git_oid_shorten *git_oid_shorten_new(size_t min_length)
316 - {
317 - git_oid_shorten *os;
318 -
319 3 2,3 assert((size_t)((int)min_length) == min_length);
320 -
321 3 4 os = git__calloc(1, sizeof(git_oid_shorten));
322 3 5 if (os == NULL)
323 ##### 6 return NULL;
324 -
325 3 7,8 if (resize_trie(os, 16) < 0) {
326 ##### 9 git__free(os);
327 ##### 10 return NULL;
328 - }
329 -
330 3 11 os->node_count = 1;
331 3 11 os->min_length = (int)min_length;
332 -
333 3 11 return os;
334 - }
335 -
336 3 2 void git_oid_shorten_free(git_oid_shorten *os)
337 - {
338 3 2 if (os == NULL)
339 3 3,6 return;
340 -
341 3 4 git__free(os->nodes);
342 3 5 git__free(os);
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
362 - * pointers, because in a 64-bit arch this would be sucking
363 - * 16*sizeof(void*) = 128 bytes of memory per node, which is
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 25560 2 int git_oid_shorten_add(git_oid_shorten *os, const char *text_oid)
391 - {
392 - int i;
393 - bool is_leaf;
394 - node_index idx;
395 -
396 25560 2 if (os->full) {
397 ##### 3 git_error_set(GIT_ERROR_INVALID, "unable to shorten OID - OID set full");
398 ##### 4 return -1;
399 - }
400 -
401 25560 5 if (text_oid == NULL)
402 ##### 6 return os->min_length;
403 -
404 25560 7 idx = 0;
405 25560 7 is_leaf = false;
406 -
407 101165 7,28,29 for (i = 0; i < GIT_OID_HEXSZ; ++i) {
408 101164 8 int c = git__fromhex(text_oid[i]);
409 - trie_node *node;
410 -
411 101164 9 if (c == -1) {
412 ##### 10 git_error_set(GIT_ERROR_INVALID, "unable to shorten OID - invalid hex value");
413 ##### 11 return -1;
414 - }
415 -
416 101164 12 node = &os->nodes[idx];
417 -
418 101164 12 if (is_leaf) {
419 - const char *tail;
420 -
421 8618 13 tail = node->tail;
422 8618 13 node->tail = NULL;
423 -
424 8618 13,14 node = push_leaf(os, idx, git__fromhex(tail[0]), &tail[1]);
425 8618 15 if (node == NULL) {
426 ##### 16 if (os->full)
427 ##### 17 git_error_set(GIT_ERROR_INVALID, "unable to shorten OID - OID set full");
428 ##### 18 return -1;
429 - }
430 - }
431 -
432 101164 19 if (node->children[c] == 0) {
433 25559 20,21 if (push_leaf(os, idx, c, &text_oid[i + 1]) == NULL) {
434 1 22 if (os->full)
435 1 23 git_error_set(GIT_ERROR_INVALID, "unable to shorten OID - OID set full");
436 1 24 return -1;
437 - }
438 25558 25 break;
439 - }
440 -
441 75605 26 idx = node->children[c];
442 75605 26 is_leaf = false;
443 -
444 75605 26 if (idx < 0) {
445 8619 27 node->children[c] = idx = -idx;
446 8619 27 is_leaf = true;
447 - }
448 - }
449 -
450 25559 30 if (++i > os->min_length)
451 15 31 os->min_length = i;
452 -
453 25559 32 return os->min_length;
454 - }
455 -