aboutsummaryrefslogtreecommitdiffstats
path: root/store
diff options
context:
space:
mode:
Diffstat (limited to 'store')
-rw-r--r--store/digest.h79
-rw-r--r--store/store-tree.c71
2 files changed, 80 insertions, 70 deletions
diff --git a/store/digest.h b/store/digest.h
new file mode 100644
index 0000000..52a1cbc
--- /dev/null
+++ b/store/digest.h
@@ -0,0 +1,79 @@
+#ifndef PURE_STORE_DIGEST_H
+#define PURE_STORE_DIGEST_H
+/* The store's digest, shared by its files (the tree, the log, list images). */
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+
+/* The xxHash64 construction without a seed: four multiply-rotate lanes over
+ * 32-byte stripes, several GB/s. An all-zero Digest is an empty one. */
+typedef struct { uint64_t lane[4], length; unsigned char held[32]; size_t count; } Digest;
+
+static inline uint64_t load64(const unsigned char *bytes) {
+ uint64_t value;
+ memcpy(&value, bytes, 8);
+#if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
+ value = __builtin_bswap64(value);
+#endif
+ return value;
+}
+
+/* Digests find torn and missing writes; they are not a defence against a
+ * hostile file. */
+static const uint64_t P1 = UINT64_C(0x9E3779B185EBCA87), P2 = UINT64_C(0xC2B2AE3D27D4EB4F),
+ P3 = UINT64_C(0x165667B19E3779F9), P4 = UINT64_C(0x85EBCA77C2B2AE63),
+ P5 = UINT64_C(0x27D4EB2F165667C5);
+
+static inline uint64_t rotate(uint64_t value, unsigned bits) { return value << bits | value >> (64 - bits); }
+static inline uint64_t mix(uint64_t lane, uint64_t word) { return rotate(lane + word * P2, 31) * P1; }
+
+static inline void stripes(Digest *digest, const unsigned char *bytes, size_t count) {
+ uint64_t a = digest->lane[0], b = digest->lane[1], c = digest->lane[2], d = digest->lane[3];
+ for (; count; --count, bytes += 32) {
+ a = mix(a, load64(bytes));
+ b = mix(b, load64(bytes + 8));
+ c = mix(c, load64(bytes + 16));
+ d = mix(d, load64(bytes + 24));
+ }
+ digest->lane[0] = a, digest->lane[1] = b, digest->lane[2] = c, digest->lane[3] = d;
+}
+
+static inline void digest_add(Digest *digest, const unsigned char *bytes, size_t length) {
+ digest->length += length;
+ if (digest->count) {
+ size_t take = 32 - digest->count < length ? 32 - digest->count : length;
+ memcpy(digest->held + digest->count, bytes, take);
+ digest->count += take;
+ bytes += take;
+ length -= take;
+ if (digest->count < 32) return;
+ stripes(digest, digest->held, 1);
+ digest->count = 0;
+ }
+ stripes(digest, bytes, length / 32);
+ digest->count = length % 32;
+ if (digest->count) memcpy(digest->held, bytes + length - digest->count, digest->count);
+}
+
+static inline uint64_t digest_end(const Digest *digest) {
+ const uint64_t *lane = digest->lane;
+ uint64_t hash = rotate(lane[0], 1) + rotate(lane[1], 7) + rotate(lane[2], 12) + rotate(lane[3], 18);
+ for (unsigned i = 0; i < 4; ++i) hash = (hash ^ mix(0, lane[i])) * P1 + P4;
+ hash += digest->length;
+ size_t i = 0;
+ for (; i + 8 <= digest->count; i += 8) hash = rotate(hash ^ mix(0, load64(digest->held + i)), 27) * P1 + P4;
+ for (; i < digest->count; ++i) hash = rotate(hash ^ digest->held[i] * P5, 11) * P1;
+ hash ^= hash >> 33;
+ hash *= P2;
+ hash ^= hash >> 29;
+ hash *= P3;
+ return hash ^ hash >> 32;
+}
+
+static inline uint64_t digest_of(const unsigned char *bytes, size_t length) {
+ Digest digest = {0};
+ digest_add(&digest, bytes, length);
+ return digest_end(&digest);
+}
+
+#endif
diff --git a/store/store-tree.c b/store/store-tree.c
index 0f83f27..b9ae847 100644
--- a/store/store-tree.c
+++ b/store/store-tree.c
@@ -15,6 +15,7 @@
#endif
#include "store.h"
#include "state.h"
+#include "digest.h"
#include <errno.h>
#include <fcntl.h>
#include <inttypes.h>
@@ -80,9 +81,6 @@ typedef struct {
/* A commit's bytes are start..end (none for a file synced whole before it was
* published); check is their digest. */
typedef struct { uint64_t seq, end, catalog, catalog_bytes, live, start, check; } Head;
-/* The xxHash64 construction without a seed: four multiply-rotate lanes over
- * 32-byte stripes, several GB/s. An all-zero Digest is an empty one. */
-typedef struct { uint64_t lane[4], length; unsigned char held[32]; size_t count; } Digest;
typedef struct {
int fd;
uint64_t at; /* file offset of the next byte */
@@ -130,73 +128,6 @@ static void encode64(unsigned char *bytes, uint64_t value) {
for (unsigned i = 0; i < 8; ++i) bytes[i] = (unsigned char)(value >> (8 * i));
}
-static uint64_t load64(const unsigned char *bytes) {
- uint64_t value;
- memcpy(&value, bytes, 8);
-#if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
- value = __builtin_bswap64(value);
-#endif
- return value;
-}
-
-/* Digests find torn and missing writes; they are not a defence against a
- * hostile file. */
-static const uint64_t P1 = UINT64_C(0x9E3779B185EBCA87), P2 = UINT64_C(0xC2B2AE3D27D4EB4F),
- P3 = UINT64_C(0x165667B19E3779F9), P4 = UINT64_C(0x85EBCA77C2B2AE63),
- P5 = UINT64_C(0x27D4EB2F165667C5);
-
-static uint64_t rotate(uint64_t value, unsigned bits) { return value << bits | value >> (64 - bits); }
-static uint64_t mix(uint64_t lane, uint64_t word) { return rotate(lane + word * P2, 31) * P1; }
-
-static void stripes(Digest *digest, const unsigned char *bytes, size_t count) {
- uint64_t a = digest->lane[0], b = digest->lane[1], c = digest->lane[2], d = digest->lane[3];
- for (; count; --count, bytes += 32) {
- a = mix(a, load64(bytes));
- b = mix(b, load64(bytes + 8));
- c = mix(c, load64(bytes + 16));
- d = mix(d, load64(bytes + 24));
- }
- digest->lane[0] = a, digest->lane[1] = b, digest->lane[2] = c, digest->lane[3] = d;
-}
-
-static void digest_add(Digest *digest, const unsigned char *bytes, size_t length) {
- digest->length += length;
- if (digest->count) {
- size_t take = 32 - digest->count < length ? 32 - digest->count : length;
- memcpy(digest->held + digest->count, bytes, take);
- digest->count += take;
- bytes += take;
- length -= take;
- if (digest->count < 32) return;
- stripes(digest, digest->held, 1);
- digest->count = 0;
- }
- stripes(digest, bytes, length / 32);
- digest->count = length % 32;
- if (digest->count) memcpy(digest->held, bytes + length - digest->count, digest->count);
-}
-
-static uint64_t digest_end(const Digest *digest) {
- const uint64_t *lane = digest->lane;
- uint64_t hash = rotate(lane[0], 1) + rotate(lane[1], 7) + rotate(lane[2], 12) + rotate(lane[3], 18);
- for (unsigned i = 0; i < 4; ++i) hash = (hash ^ mix(0, lane[i])) * P1 + P4;
- hash += digest->length;
- size_t i = 0;
- for (; i + 8 <= digest->count; i += 8) hash = rotate(hash ^ mix(0, load64(digest->held + i)), 27) * P1 + P4;
- for (; i < digest->count; ++i) hash = rotate(hash ^ digest->held[i] * P5, 11) * P1;
- hash ^= hash >> 33;
- hash *= P2;
- hash ^= hash >> 29;
- hash *= P3;
- return hash ^ hash >> 32;
-}
-
-static uint64_t digest_of(const unsigned char *bytes, size_t length) {
- Digest digest = {0};
- digest_add(&digest, bytes, length);
- return digest_end(&digest);
-}
-
#ifdef PURE_STORE_TEST
static unsigned long syncs;
unsigned long pure_tree_test_syncs(void) { return __atomic_load_n(&syncs, __ATOMIC_RELAXED); }
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-20 18:21:25 +0000