@leroysheep / rag-system
Code Commits Pulls CI/CD 81,348
maint
bisect jch maint master next seen test todo
h 475 lines 14.8 KB
Raw
1 #ifndef HASH_H
2 #define HASH_H
3
4 #if defined(SHA1_APPLE)
5 #define SHA1_BACKEND "SHA1_APPLE (No collision detection)"
6 #include <CommonCrypto/CommonDigest.h>
7 #elif defined(SHA1_OPENSSL)
8 # define SHA1_BACKEND "SHA1_OPENSSL (No collision detection)"
9 # include <openssl/sha.h>
10 # if defined(OPENSSL_API_LEVEL) && OPENSSL_API_LEVEL >= 3
11 # define SHA1_NEEDS_CLONE_HELPER
12 # include "sha1/openssl.h"
13 # endif
14 #elif defined(SHA1_DC)
15 #define SHA1_BACKEND "SHA1_DC"
16 #include "sha1dc_git.h"
17 #else /* SHA1_BLK */
18 #define SHA1_BACKEND "SHA1_BLK (No collision detection)"
19 #include "block-sha1/sha1.h"
20 #endif
21
22 #if defined(SHA1_APPLE_UNSAFE)
23 # define SHA1_UNSAFE_BACKEND "SHA1_APPLE_UNSAFE"
24 # include <CommonCrypto/CommonDigest.h>
25 # define platform_SHA_CTX_unsafe CC_SHA1_CTX
26 # define platform_SHA1_Init_unsafe CC_SHA1_Init
27 # define platform_SHA1_Update_unsafe CC_SHA1_Update
28 # define platform_SHA1_Final_unsafe CC_SHA1_Final
29 #elif defined(SHA1_OPENSSL_UNSAFE)
30 # define SHA1_UNSAFE_BACKEND "SHA1_OPENSSL_UNSAFE"
31 # include <openssl/sha.h>
32 # if defined(OPENSSL_API_LEVEL) && OPENSSL_API_LEVEL >= 3
33 # define SHA1_NEEDS_CLONE_HELPER_UNSAFE
34 # include "sha1/openssl.h"
35 # define platform_SHA_CTX_unsafe openssl_SHA1_CTX
36 # define platform_SHA1_Init_unsafe openssl_SHA1_Init
37 # define platform_SHA1_Clone_unsafe openssl_SHA1_Clone
38 # define platform_SHA1_Update_unsafe openssl_SHA1_Update
39 # define platform_SHA1_Final_unsafe openssl_SHA1_Final
40 # else
41 # define platform_SHA_CTX_unsafe SHA_CTX
42 # define platform_SHA1_Init_unsafe SHA1_Init
43 # define platform_SHA1_Update_unsafe SHA1_Update
44 # define platform_SHA1_Final_unsafe SHA1_Final
45 # endif
46 #elif defined(SHA1_BLK_UNSAFE)
47 # define SHA1_UNSAFE_BACKEND "SHA1_BLK_UNSAFE"
48 # include "block-sha1/sha1.h"
49 # define platform_SHA_CTX_unsafe blk_SHA_CTX
50 # define platform_SHA1_Init_unsafe blk_SHA1_Init
51 # define platform_SHA1_Update_unsafe blk_SHA1_Update
52 # define platform_SHA1_Final_unsafe blk_SHA1_Final
53 #endif
54
55 #if defined(SHA256_NETTLE)
56 #define SHA256_BACKEND "SHA256_NETTLE"
57 #include "sha256/nettle.h"
58 #elif defined(SHA256_GCRYPT)
59 #define SHA256_BACKEND "SHA256_GCRYPT"
60 #define SHA256_NEEDS_CLONE_HELPER
61 #include "sha256/gcrypt.h"
62 #elif defined(SHA256_OPENSSL)
63 # define SHA256_BACKEND "SHA256_OPENSSL"
64 # include <openssl/sha.h>
65 # if defined(OPENSSL_API_LEVEL) && OPENSSL_API_LEVEL >= 3
66 # define SHA256_NEEDS_CLONE_HELPER
67 # include "sha256/openssl.h"
68 # endif
69 #else
70 #define SHA256_BACKEND "SHA256_BLK"
71 #include "sha256/block/sha256.h"
72 #endif
73
74 #ifndef platform_SHA_CTX
75 /*
76 * platform's underlying implementation of SHA-1; could be OpenSSL,
77 * blk_SHA, Apple CommonCrypto, etc... Note that the relevant
78 * SHA-1 header may have already defined platform_SHA_CTX for our
79 * own implementations like block-sha1, so we list
80 * the default for OpenSSL compatible SHA-1 implementations here.
81 */
82 #define platform_SHA_CTX SHA_CTX
83 #define platform_SHA1_Init SHA1_Init
84 #define platform_SHA1_Update SHA1_Update
85 #define platform_SHA1_Final SHA1_Final
86 #endif
87
88 #ifndef platform_SHA_CTX_unsafe
89 # define platform_SHA_CTX_unsafe platform_SHA_CTX
90 # define platform_SHA1_Init_unsafe platform_SHA1_Init
91 # define platform_SHA1_Update_unsafe platform_SHA1_Update
92 # define platform_SHA1_Final_unsafe platform_SHA1_Final
93 # ifdef platform_SHA1_Clone
94 # define platform_SHA1_Clone_unsafe platform_SHA1_Clone
95 # endif
96 # ifdef SHA1_NEEDS_CLONE_HELPER
97 # define SHA1_NEEDS_CLONE_HELPER_UNSAFE
98 # endif
99 #endif
100
101 #define git_SHA_CTX platform_SHA_CTX
102 #define git_SHA1_Init platform_SHA1_Init
103 #define git_SHA1_Update platform_SHA1_Update
104 #define git_SHA1_Final platform_SHA1_Final
105
106 #define git_SHA_CTX_unsafe platform_SHA_CTX_unsafe
107 #define git_SHA1_Init_unsafe platform_SHA1_Init_unsafe
108 #define git_SHA1_Update_unsafe platform_SHA1_Update_unsafe
109 #define git_SHA1_Final_unsafe platform_SHA1_Final_unsafe
110
111 #ifdef platform_SHA1_Clone
112 #define git_SHA1_Clone platform_SHA1_Clone
113 #endif
114 #ifdef platform_SHA1_Clone_unsafe
115 # define git_SHA1_Clone_unsafe platform_SHA1_Clone_unsafe
116 #endif
117
118 #ifndef platform_SHA256_CTX
119 #define platform_SHA256_CTX SHA256_CTX
120 #define platform_SHA256_Init SHA256_Init
121 #define platform_SHA256_Update SHA256_Update
122 #define platform_SHA256_Final SHA256_Final
123 #endif
124
125 #define git_SHA256_CTX platform_SHA256_CTX
126 #define git_SHA256_Init platform_SHA256_Init
127 #define git_SHA256_Update platform_SHA256_Update
128 #define git_SHA256_Final platform_SHA256_Final
129
130 #ifdef platform_SHA256_Clone
131 #define git_SHA256_Clone platform_SHA256_Clone
132 #endif
133
134 #ifdef SHA1_MAX_BLOCK_SIZE
135 #include "compat/sha1-chunked.h"
136 #undef git_SHA1_Update
137 #define git_SHA1_Update git_SHA1_Update_Chunked
138 #endif
139
140 #ifndef SHA1_NEEDS_CLONE_HELPER
141 static inline void git_SHA1_Clone(git_SHA_CTX *dst, const git_SHA_CTX *src)
142 {
143 memcpy(dst, src, sizeof(*dst));
144 }
145 #endif
146 #ifndef SHA1_NEEDS_CLONE_HELPER_UNSAFE
147 static inline void git_SHA1_Clone_unsafe(git_SHA_CTX_unsafe *dst,
148 const git_SHA_CTX_unsafe *src)
149 {
150 memcpy(dst, src, sizeof(*dst));
151 }
152 #endif
153
154 #ifndef SHA256_NEEDS_CLONE_HELPER
155 static inline void git_SHA256_Clone(git_SHA256_CTX *dst, const git_SHA256_CTX *src)
156 {
157 memcpy(dst, src, sizeof(*dst));
158 }
159 #endif
160
161 /*
162 * Note that these constants are suitable for indexing the hash_algos array and
163 * comparing against each other, but are otherwise arbitrary, so they should not
164 * be exposed to the user or serialized to disk. To know whether a
165 * git_hash_algo struct points to some usable hash function, test the format_id
166 * field for being non-zero. Use the name field for user-visible situations and
167 * the format_id field for fixed-length fields on disk.
168 */
169 /* An unknown hash function. */
170 #define GIT_HASH_UNKNOWN 0
171 /* SHA-1 */
172 #define GIT_HASH_SHA1 1
173 /* SHA-256 */
174 #define GIT_HASH_SHA256 2
175 /* Number of algorithms supported (including unknown). */
176 #define GIT_HASH_NALGOS (GIT_HASH_SHA256 + 1)
177
178 /* Default hash algorithm if unspecified. */
179 #ifdef WITH_BREAKING_CHANGES
180 # define GIT_HASH_DEFAULT GIT_HASH_SHA256
181 #else
182 # define GIT_HASH_DEFAULT GIT_HASH_SHA1
183 #endif
184
185 /* Legacy hash algorithm. Implied for older data formats which don't specify. */
186 #define GIT_HASH_SHA1_LEGACY GIT_HASH_SHA1
187
188 /* "sha1", big-endian */
189 #define GIT_SHA1_FORMAT_ID 0x73686131
190
191 /* The length in bytes and in hex digits of an object name (SHA-1 value). */
192 #define GIT_SHA1_RAWSZ 20
193 #define GIT_SHA1_HEXSZ (2 * GIT_SHA1_RAWSZ)
194 /* The block size of SHA-1. */
195 #define GIT_SHA1_BLKSZ 64
196
197 /* "s256", big-endian */
198 #define GIT_SHA256_FORMAT_ID 0x73323536
199
200 /* The length in bytes and in hex digits of an object name (SHA-256 value). */
201 #define GIT_SHA256_RAWSZ 32
202 #define GIT_SHA256_HEXSZ (2 * GIT_SHA256_RAWSZ)
203 /* The block size of SHA-256. */
204 #define GIT_SHA256_BLKSZ 64
205
206 /* The length in byte and in hex digits of the largest possible hash value. */
207 #define GIT_MAX_RAWSZ GIT_SHA256_RAWSZ
208 #define GIT_MAX_HEXSZ GIT_SHA256_HEXSZ
209 /* The largest possible block size for any supported hash. */
210 #define GIT_MAX_BLKSZ GIT_SHA256_BLKSZ
211
212 struct object_id {
213 unsigned char hash[GIT_MAX_RAWSZ];
214 uint32_t algo; /* XXX requires 4-byte alignment */
215 };
216
217 #define GET_OID_QUIETLY 01
218 #define GET_OID_COMMIT 02
219 #define GET_OID_COMMITTISH 04
220 #define GET_OID_TREE 010
221 #define GET_OID_TREEISH 020
222 #define GET_OID_BLOB 040
223 #define GET_OID_FOLLOW_SYMLINKS 0100
224 #define GET_OID_RECORD_PATH 0200
225 #define GET_OID_ONLY_TO_DIE 04000
226 #define GET_OID_REQUIRE_PATH 010000
227 #define GET_OID_HASH_ANY 020000
228 #define GET_OID_SKIP_AMBIGUITY_CHECK 040000
229 #define GET_OID_GENTLY 0100000
230
231 #define GET_OID_DISAMBIGUATORS \
232 (GET_OID_COMMIT | GET_OID_COMMITTISH | \
233 GET_OID_TREE | GET_OID_TREEISH | \
234 GET_OID_BLOB)
235
236 enum get_oid_result {
237 FOUND = 0,
238 MISSING_OBJECT = -1, /* The requested object is missing */
239 SHORT_NAME_AMBIGUOUS = -2,
240 /* The following only apply when symlinks are followed */
241 DANGLING_SYMLINK = -4, /*
242 * The initial symlink is there, but
243 * (transitively) points to a missing
244 * in-tree file
245 */
246 SYMLINK_LOOP = -5,
247 NOT_DIR = -6, /*
248 * Somewhere along the symlink chain, a path is
249 * requested which contains a file as a
250 * non-final element.
251 */
252 };
253
254 #ifdef USE_THE_REPOSITORY_VARIABLE
255 # include "repository.h"
256 # define the_hash_algo the_repository->hash_algo
257 #endif
258
259 /* A suitably aligned type for stack allocations of hash contexts. */
260 struct git_hash_ctx {
261 const struct git_hash_algo *algop;
262 union {
263 git_SHA_CTX sha1;
264 git_SHA_CTX_unsafe sha1_unsafe;
265 git_SHA256_CTX sha256;
266 } state;
267 };
268
269 typedef void (*git_hash_init_fn)(struct git_hash_ctx *ctx);
270 typedef void (*git_hash_clone_fn)(struct git_hash_ctx *dst, const struct git_hash_ctx *src);
271 typedef void (*git_hash_update_fn)(struct git_hash_ctx *ctx, const void *in, size_t len);
272 typedef void (*git_hash_final_fn)(unsigned char *hash, struct git_hash_ctx *ctx);
273 typedef void (*git_hash_final_oid_fn)(struct object_id *oid, struct git_hash_ctx *ctx);
274
275 struct git_hash_algo {
276 /*
277 * The name of the algorithm, as appears in the config file and in
278 * messages.
279 */
280 const char *name;
281
282 /* A four-byte version identifier, used in pack indices. */
283 uint32_t format_id;
284
285 /* The length of the hash in binary. */
286 size_t rawsz;
287
288 /* The length of the hash in hex characters. */
289 size_t hexsz;
290
291 /* The block size of the hash. */
292 size_t blksz;
293
294 /* The hash initialization function. */
295 git_hash_init_fn init_fn;
296
297 /* The hash context cloning function. */
298 git_hash_clone_fn clone_fn;
299
300 /* The hash update function. */
301 git_hash_update_fn update_fn;
302
303 /* The hash finalization function. */
304 git_hash_final_fn final_fn;
305
306 /* The hash finalization function for object IDs. */
307 git_hash_final_oid_fn final_oid_fn;
308
309 /* The OID of the empty tree. */
310 const struct object_id *empty_tree;
311
312 /* The OID of the empty blob. */
313 const struct object_id *empty_blob;
314
315 /* The all-zeros OID. */
316 const struct object_id *null_oid;
317
318 /* The unsafe variant of this hash function, if one exists. */
319 const struct git_hash_algo *unsafe;
320 };
321 extern const struct git_hash_algo hash_algos[GIT_HASH_NALGOS];
322
323 void git_hash_init(struct git_hash_ctx *ctx, const struct git_hash_algo *algop);
324 void git_hash_clone(struct git_hash_ctx *dst, const struct git_hash_ctx *src);
325 void git_hash_update(struct git_hash_ctx *ctx, const void *in, size_t len);
326 void git_hash_final(unsigned char *hash, struct git_hash_ctx *ctx);
327 void git_hash_final_oid(struct object_id *oid, struct git_hash_ctx *ctx);
328 const struct git_hash_algo *hash_algo_ptr_by_number(uint32_t algo);
329 struct git_hash_ctx *git_hash_alloc(void);
330 void git_hash_free(struct git_hash_ctx *ctx);
331 /*
332 * Return a GIT_HASH_* constant based on the name. Returns GIT_HASH_UNKNOWN if
333 * the name doesn't match a known algorithm.
334 */
335 uint32_t hash_algo_by_name(const char *name);
336 /* Identical, except based on the format ID. */
337 uint32_t hash_algo_by_id(uint32_t format_id);
338 /* Identical, except based on the length. */
339 uint32_t hash_algo_by_length(size_t len);
340 /* Identical, except for a pointer to struct git_hash_algo. */
341 static inline uint32_t hash_algo_by_ptr(const struct git_hash_algo *p)
342 {
343 size_t i;
344 for (i = 0; i < GIT_HASH_NALGOS; i++) {
345 const struct git_hash_algo *algop = &hash_algos[i];
346 if (p == algop)
347 return i;
348 }
349 return GIT_HASH_UNKNOWN;
350 }
351
352 const struct git_hash_algo *unsafe_hash_algo(const struct git_hash_algo *algop);
353
354 const struct object_id *null_oid(const struct git_hash_algo *algop);
355
356 static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2, const struct git_hash_algo *algop)
357 {
358 /*
359 * Teach the compiler that there are only two possibilities of hash size
360 * here, so that it can optimize for this case as much as possible.
361 */
362 if (algop->rawsz == GIT_MAX_RAWSZ)
363 return memcmp(sha1, sha2, GIT_MAX_RAWSZ);
364 return memcmp(sha1, sha2, GIT_SHA1_RAWSZ);
365 }
366
367 static inline int hasheq(const unsigned char *sha1, const unsigned char *sha2, const struct git_hash_algo *algop)
368 {
369 /*
370 * We write this here instead of deferring to hashcmp so that the
371 * compiler can properly inline it and avoid calling memcmp.
372 */
373 if (algop->rawsz == GIT_MAX_RAWSZ)
374 return !memcmp(sha1, sha2, GIT_MAX_RAWSZ);
375 return !memcmp(sha1, sha2, GIT_SHA1_RAWSZ);
376 }
377
378 static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src,
379 const struct git_hash_algo *algop)
380 {
381 memcpy(sha_dst, sha_src, algop->rawsz);
382 }
383
384 static inline void hashclr(unsigned char *hash, const struct git_hash_algo *algop)
385 {
386 memset(hash, 0, algop->rawsz);
387 }
388
389 static inline int oidcmp(const struct object_id *oid1, const struct object_id *oid2)
390 {
391 return memcmp(oid1->hash, oid2->hash, GIT_MAX_RAWSZ);
392 }
393
394 static inline int oideq(const struct object_id *oid1, const struct object_id *oid2)
395 {
396 return !memcmp(oid1->hash, oid2->hash, GIT_MAX_RAWSZ);
397 }
398
399 unsigned oid_common_prefix_hexlen(const struct object_id *a,
400 const struct object_id *b);
401
402 static inline void oidcpy(struct object_id *dst, const struct object_id *src)
403 {
404 memcpy(dst->hash, src->hash, GIT_MAX_RAWSZ);
405 dst->algo = src->algo;
406 }
407
408 static inline void oidread(struct object_id *oid, const unsigned char *hash,
409 const struct git_hash_algo *algop)
410 {
411 memcpy(oid->hash, hash, algop->rawsz);
412 if (algop->rawsz < GIT_MAX_RAWSZ)
413 memset(oid->hash + algop->rawsz, 0, GIT_MAX_RAWSZ - algop->rawsz);
414 oid->algo = hash_algo_by_ptr(algop);
415 }
416
417 static inline void oidclr(struct object_id *oid,
418 const struct git_hash_algo *algop)
419 {
420 memset(oid->hash, 0, GIT_MAX_RAWSZ);
421 oid->algo = hash_algo_by_ptr(algop);
422 }
423
424 static inline struct object_id *oiddup(const struct object_id *src)
425 {
426 struct object_id *dst = xmalloc(sizeof(struct object_id));
427 oidcpy(dst, src);
428 return dst;
429 }
430
431 static inline void oid_set_algo(struct object_id *oid, const struct git_hash_algo *algop)
432 {
433 oid->algo = hash_algo_by_ptr(algop);
434 }
435
436 /*
437 * Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code
438 * for use in hash tables. Cryptographic hashes are supposed to have
439 * uniform distribution, so in contrast to `memhash()`, this just copies
440 * the first `sizeof(int)` bytes without shuffling any bits. Note that
441 * the results will be different on big-endian and little-endian
442 * platforms, so they should not be stored or transferred over the net.
443 */
444 static inline unsigned int oidhash(const struct object_id *oid)
445 {
446 /*
447 * Equivalent to 'return *(unsigned int *)oid->hash;', but safe on
448 * platforms that don't support unaligned reads.
449 */
450 unsigned int hash;
451 memcpy(&hash, oid->hash, sizeof(hash));
452 return hash;
453 }
454
455 static inline int is_null_oid(const struct object_id *oid)
456 {
457 static const unsigned char null_hash[GIT_MAX_RAWSZ];
458 return !memcmp(oid->hash, null_hash, GIT_MAX_RAWSZ);
459 }
460
461 const char *empty_tree_oid_hex(const struct git_hash_algo *algop);
462
463 static inline int is_empty_blob_oid(const struct object_id *oid,
464 const struct git_hash_algo *algop)
465 {
466 return oideq(oid, algop->empty_blob);
467 }
468
469 static inline int is_empty_tree_oid(const struct object_id *oid,
470 const struct git_hash_algo *algop)
471 {
472 return oideq(oid, algop->empty_tree);
473 }
474
475 #endif