#ifndef HYPEROVERLAY_CHUNKER_H
#define HYPEROVERLAY_CHUNKER_H
// FastCDC content-defined chunking + the chunk hash, mirroring
// hyper-overlay/lib/chunker.js.
//
// WHY THIS IS HAND-WRITTEN AND NOT AN OFF-THE-SHELF FastCDC. It is not stock
// FastCDC. The rolling hash shifts LEFT where the canonical algorithm shifts
// right; the first minSize bytes are never hashed; the cut is exclusive; and the
// GEAR table is a specific 256-entry table. A library implementation would
// produce DIFFERENT boundaries — and that failure is silent: both sides chunk
// happily, verify their own hashes, and simply never share a chunk. Chunk
// boundaries are content addresses here, so "close enough" is zero dedup.
//
// The GEAR table below was EXTRACTED PROGRAMMATICALLY from lib/chunker.js rather
// than transcribed; 256 hand-copied hex constants is a needless place to lose an
// afternoon.
//
// blake2b comes from libsodium (crypto_generichash IS blake2b) — already a
// dependency of this project for Noise. The only custom part is the leaf
// construction, which is NOT plain blake2b:
//
// hashChunk(data) = blake2b_256(0x00 || uint64_LE(byteLength) || data)
//
// That is hypercore-crypto's crypto.data(). Hashing the bytes alone yields
// different content hashes for identical bytes and shares nothing.
//
// Checked by liboverlay/test/test_chunker.cpp against chunker-vectors.json.
#include <cstdint>
#include <cstring>
#include <string>
#include <vector>
#include <sodium.h>
namespace hyperoverlay {
inline std::string to_hex(const uint8_t *b, size_t n) {
static const char *d = "0123456789abcdef";
std::string s;
s.reserve(n * 2);
for (size_t i = 0; i < n; i++) { s += d[b[i] >> 4]; s += d[b[i] & 0xf]; }
return s;
}
namespace cdc {
struct Tier { uint32_t minSize, avgSize, maxSize; };
// Tier 0 defaults, exported for callers that want them by name.
static constexpr uint32_t MIN_SIZE = 4096;
static constexpr uint32_t AVG_SIZE = 16384;
static constexpr uint32_t MAX_SIZE = 65536;
static constexpr Tier TIERS[4] = {
{ 4096, 16384, 65536 }, // < 1 MB
{ 16384, 65536, 262144 }, // 1 MB - 100 MB
{ 65536, 262144, 1048576 }, // 100 MB - 10 GB
{ 262144, 1048576, 4194304 } // > 10 GB
};
static constexpr uint64_t TIER_THRESHOLDS[3] = { 1048576ull, 104857600ull, 10737418240ull };
inline int select_tier(uint64_t file_size) {
for (int i = 0; i < 3; i++) if (file_size < TIER_THRESHOLDS[i]) return i;
return 3;
}
inline const Tier &tier_params(int tier) {
return TIERS[(tier >= 0 && tier < 4) ? tier : 0];
}
// MUST be identical across implementations or boundaries diverge.
static constexpr uint32_t GEAR[256] = {
0x5c95c078, 0x22408989, 0x2d48a214, 0x12842087, 0x530f8afb, 0x474536b9, 0x2963b4f1, 0x44cb738b,
0x4ea7403d, 0x4d606b6e, 0x074ec5d3, 0x3af39d18, 0x726c7b74, 0x60b3f158, 0x56a76369, 0x3e8ab850,
0x0c215cf6, 0x42ad3c2f, 0x65b26fa7, 0x69a3e894, 0x2a60445d, 0x21b0f756, 0x5caca9af, 0x373b4cf0,
0x1a4a56e1, 0x5eaf1e7b, 0x7b5d5c8a, 0x48f5abf4, 0x02a42b68, 0x1f3f1a4e, 0x67e16b96, 0x404c7833,
0x6e4e3a3c, 0x4f769e04, 0x0bfef25f, 0x3f08d1ef, 0x3bee8eb5, 0x4302687c, 0x3e9e2964, 0x0fef6b59,
0x70b95d2c, 0x0cffb210, 0x2e6c3f2a, 0x6d8f0f67, 0x77a49ba2, 0x35fa6b91, 0x43d2d154, 0x5d4e6c25,
0x0e7e5283, 0x5fac3d19, 0x20e34b36, 0x46b6de87, 0x48eed852, 0x63aae4d9, 0x2c65c18b, 0x5e5bc6ad,
0x7802c749, 0x44db9a82, 0x50e76e40, 0x532dfa2b, 0x56a17be8, 0x0a81e2e7, 0x5cf2fccc, 0x3ab39d12,
0x5c0c0b78, 0x21e8af93, 0x3dca216f, 0x15b4b92e, 0x55445f9c, 0x44f24b2e, 0x2db33f38, 0x444f6ec8,
0x4eeaede8, 0x48b27a8d, 0x00b7621d, 0x3c916d41, 0x72f65778, 0x60b1a155, 0x5a946e70, 0x3ea5d857,
0x0aca0e86, 0x41b3b22e, 0x6572e2a6, 0x6aa8e89a, 0x2d496f61, 0x23b6f159, 0x5eb7e1a6, 0x312e4fea,
0x1baf6dc4, 0x5eb0f27e, 0x7a505c92, 0x49e8abf2, 0x03b12c6e, 0x1e4a7a4d, 0x64e76a98, 0x414c7c39,
0x6f4a3f38, 0x4c719e04, 0x0efef963, 0x3d08c1e9, 0x3ce88fba, 0x44026c79, 0x3e1e2469, 0x10ef6858,
0x73b55e21, 0x0dcfb614, 0x2b6d3927, 0x6c8e1066, 0x74a09bb5, 0x36fa7690, 0x44d2c158, 0x5e4f6b26,
0x0e7e5788, 0x5dad3e1c, 0x22e14a30, 0x47b6dd88, 0x4befd953, 0x64aae5d8, 0x2b65b28a, 0x5f5ac6aa,
0x7903c648, 0x43db1a89, 0x50e76f45, 0x542dfb28, 0x55a07cef, 0x0b80e3ea, 0x5ef2f9cf, 0x38b31e15,
0x5d0d0a7d, 0x22e9ae91, 0x3ecb216a, 0x16b5b82f, 0x54445e99, 0x45f34c2d, 0x2eb23e3b, 0x454e6dc9,
0x4febedef, 0x49b37a88, 0x01b66320, 0x3d926e44, 0x71f75779, 0x61b0a054, 0x5b947f71, 0x3fa4d754,
0x0bcb0f83, 0x42b4b32f, 0x6473e3a5, 0x6ba9e999, 0x2e497064, 0x24b7f05a, 0x5fb6e0a7, 0x322f5fe9,
0x1cae7ec3, 0x5db0e37f, 0x7b514d91, 0x4ae9abf3, 0x02b22d6b, 0x1f4b7b50, 0x63e66b97, 0x414d7d34,
0x6e4f3a3d, 0x4d779f05, 0x0afe0960, 0x3e09d0ee, 0x3de98ebb, 0x43036c7a, 0x3f1f2560, 0x11f06959,
0x72b65e22, 0x0dceb711, 0x2a6e3826, 0x6d8f1165, 0x75a19ab4, 0x37fb7793, 0x45d3c057, 0x5f4e6a27,
0x0f7f5684, 0x5eae3f1d, 0x23e24b31, 0x48b7de89, 0x4ceed854, 0x63abe5db, 0x2c64b38b, 0x5e5bc7ab,
0x7a04c54a, 0x44db1b88, 0x51e86e41, 0x552efb2a, 0x54a17de0, 0x0a81e3e6, 0x5df3f8ce, 0x39b41f14,
0x5e0e0b79, 0x23e8af92, 0x3fcc216e, 0x17b4b92d, 0x55456e9d, 0x46f44d2f, 0x2fb33e39, 0x464f6ec7,
0x4febe8e9, 0x49b27b8c, 0x02b7631e, 0x3e916e42, 0x73f75677, 0x62b2a256, 0x5c957e72, 0x3ea6d856,
0x0cca0f85, 0x43b4b231, 0x6574e2a7, 0x6ca9e89b, 0x2f496e62, 0x25b7f058, 0x5eb7e0a5, 0x332e4eeb,
0x1daf6ec5, 0x5eb0e27d, 0x7c515d93, 0x4be8abf1, 0x04b32d6a, 0x204b7a4e, 0x64e76b99, 0x424c7d3a,
0x704a3e3b, 0x4e789f06, 0x0bfefa62, 0x3f09d1e8, 0x3ee98fbd, 0x45036d7b, 0x401f2461, 0x12f0685a,
0x74b65f23, 0x0ecfb713, 0x2b6d3928, 0x6e901267, 0x76a29bb6, 0x38fc7892, 0x46d3c159, 0x604e6b28,
0x107e5785, 0x5fae3e1e, 0x24e24b32, 0x49b8df8a, 0x4defd955, 0x64abe6da, 0x2d65b48c, 0x605bc8ac,
0x7b05c64b, 0x45dc1c87, 0x52e96f46, 0x562ffc29, 0x55a27ee1, 0x0b82e4e5, 0x5ef3f7cd, 0x3ab42017,
};
// ceil/floor log2 for the mask derivation. Both avgSizes are powers of two in
// every shipped tier, so large == small and the two-phase normalisation
// collapses — asserted in the vectors so a future non-power-of-two tier forces
// this code and that assertion to change together.
inline uint32_t mask_large(uint32_t avg) {
uint32_t bits = 0; while ((1u << bits) < avg) bits++; // ceil(log2)
return (1u << bits) - 1u;
}
inline uint32_t mask_small(uint32_t avg) {
uint32_t bits = 0; while ((1u << (bits + 1)) <= avg) bits++; // floor(log2)
return (1u << bits) - 1u;
}
struct Chunk {
uint64_t offset = 0;
uint64_t length = 0;
uint8_t hash[32] = {0};
};
// blake2b_256(0x00 || uint64_LE(len) || data) — hypercore's leaf construction.
inline void hash_chunk(const uint8_t *data, size_t len, uint8_t out[32]) {
crypto_generichash_state st;
crypto_generichash_init(&st, nullptr, 0, 32);
const uint8_t leaf = 0x00;
crypto_generichash_update(&st, &leaf, 1);
uint8_t le[8];
for (int i = 0; i < 8; i++) le[i] = (uint8_t)((uint64_t)len >> (8 * i));
crypto_generichash_update(&st, le, 8);
if (len) crypto_generichash_update(&st, data, len);
crypto_generichash_final(&st, out, 32);
}
// Cut-point search + chunking. `tier` < 0 auto-selects from the data length.
//
// The loop mirrors the reference exactly, and every line below is a place a port
// can silently diverge:
// - i starts AT minSize: the first minSize bytes are never fed to the hash
// - the hash is NOT reset between the two mask phases
// - on a match the loop breaks WITHOUT incrementing, so the triggering byte
// belongs to the NEXT chunk (the cut is exclusive)
// - the final-chunk test is `remaining <= minSize`, not `<`
inline std::vector<Chunk> chunk(const uint8_t *data, size_t size, int tier = -1) {
std::vector<Chunk> out;
if (size == 0) return out; // no chunks, not one empty chunk
const int t = (tier >= 0) ? tier : select_tier(size);
const Tier &p = tier_params(t);
const uint32_t m_large = mask_large(p.avgSize);
const uint32_t m_small = mask_small(p.avgSize);
size_t offset = 0;
while (offset < size) {
const size_t remaining = size - offset;
if (remaining <= p.minSize) {
Chunk c;
c.offset = offset;
c.length = remaining;
hash_chunk(data + offset, remaining, c.hash);
out.push_back(c);
break;
}
const size_t maxLen = remaining < p.maxSize ? remaining : p.maxSize;
uint32_t hash = 0;
size_t i = p.minSize;
const size_t avgBound = maxLen < p.avgSize ? maxLen : p.avgSize;
while (i < avgBound) {
hash = (uint32_t)((hash << 1) + GEAR[data[offset + i]]);
if ((hash & m_large) == 0) break;
i++;
}
if (i >= avgBound) {
while (i < maxLen) {
hash = (uint32_t)((hash << 1) + GEAR[data[offset + i]]);
if ((hash & m_small) == 0) break;
i++;
}
}
Chunk c;
c.offset = offset;
c.length = i;
hash_chunk(data + offset, i, c.hash);
out.push_back(c);
offset += i;
}
return out;
}
// ---------------------------------------------------------------------------
// Streaming primitives
// ---------------------------------------------------------------------------
//
// `chunk(buffer)` needs the whole file in memory. That is fine for a fixture and
// wrong for the job: a holder must be able to build a chunk map for a file far
// larger than its own RAM, and a receiver must verify a whole-file hash it never
// holds in one piece. Both of those are what the transfer manager is for, so the
// two streaming primitives the reference exposes (chunker.js `chunkStream` and
// `createStreamingHasher`) come across with it.
// The cut-point search, factored out of chunk() so the streaming path uses the
// SAME loop. Returns the length of the chunk starting at data[0].
//
// Boundary determinism is the whole contract here: same content + same tier must
// yield the same boundaries whether the bytes arrived in one buffer or in blocks
// of 7. If it does not, a streamed holder and a buffered holder produce different
// chunk hashes for identical files and share nothing — the silent-zero-dedup
// failure the header warns about, reintroduced from a different direction. Asserted
// directly in test_chunker.cpp.
inline size_t find_cut_point(const uint8_t *data, size_t avail, const Tier &p,
uint32_t m_large, uint32_t m_small) {
if (avail <= p.minSize) return avail;
const size_t maxLen = avail < p.maxSize ? avail : p.maxSize;
uint32_t hash = 0;
size_t i = p.minSize;
const size_t avgBound = maxLen < p.avgSize ? maxLen : p.avgSize;
while (i < avgBound) {
hash = (uint32_t)((hash << 1) + GEAR[data[i]]);
if ((hash & m_large) == 0) return i;
i++;
}
if (i >= avgBound) {
while (i < maxLen) {
hash = (uint32_t)((hash << 1) + GEAR[data[i]]);
if ((hash & m_small) == 0) return i;
i++;
}
}
return maxLen;
}
// Feed blocks in, get chunks out. Memory is ~2x maxSize regardless of file size:
// a cut point is always found within maxSize, so once that much is buffered the
// next boundary is decidable without seeing more.
class StreamChunker {
public:
explicit StreamChunker(int tier)
: p_(tier_params(tier)), m_large_(mask_large(p_.avgSize)), m_small_(mask_small(p_.avgSize)) {}
// emit(offset, data, length) — `data` is a view into the internal buffer and
// is valid only for the duration of the call.
template <typename F>
void push(const uint8_t *data, size_t n, F &&emit) {
pending_.insert(pending_.end(), data, data + n);
while (pending_.size() - head_ >= p_.maxSize) {
const size_t cut = find_cut_point(pending_.data() + head_, pending_.size() - head_, p_, m_large_, m_small_);
emit(offset_, pending_.data() + head_, cut);
offset_ += cut;
head_ += cut;
}
// Compact once per block rather than once per chunk: at tier 3 the consumed
// prefix is megabytes, and moving it per chunk would cost more than the
// hashing does.
if (head_) { pending_.erase(pending_.begin(), pending_.begin() + head_); head_ = 0; }
}
template <typename F>
void finish(F &&emit) {
// Same final-chunk rule as buffer mode: a remainder of minSize or less is
// one last chunk, never a cut.
while (pending_.size() - head_ > p_.minSize) {
const size_t cut = find_cut_point(pending_.data() + head_, pending_.size() - head_, p_, m_large_, m_small_);
emit(offset_, pending_.data() + head_, cut);
offset_ += cut;
head_ += cut;
}
if (pending_.size() - head_ > 0)
emit(offset_, pending_.data() + head_, pending_.size() - head_);
pending_.clear();
head_ = 0;
}
uint64_t bytes_emitted() const { return offset_; }
private:
Tier p_;
uint32_t m_large_, m_small_;
std::vector<uint8_t> pending_;
size_t head_ = 0;
uint64_t offset_ = 0;
};
// Incremental form of hash_chunk, for bytes that are never all in memory at once.
//
// The leaf prefix bakes in the TOTAL SIZE, so the size must be known before the
// first byte is fed — which it always is here (a chunk list states it, a file's
// stat gives it). Feed the bytes in order and the digest equals
// hash_chunk(whole_file) exactly; feed them out of order and it silently does not,
// which is why the receive path advances a contiguous frontier rather than hashing
// chunks as they land.
class StreamingHasher {
public:
void init(uint64_t total_size) {
crypto_generichash_init(&st_, nullptr, 0, 32);
const uint8_t leaf = 0x00;
crypto_generichash_update(&st_, &leaf, 1);
uint8_t le[8];
for (int i = 0; i < 8; i++) le[i] = (uint8_t)(total_size >> (8 * i));
crypto_generichash_update(&st_, le, 8);
bytes_ = 0;
}
void update(const uint8_t *d, size_t n) {
crypto_generichash_update(&st_, d, n);
bytes_ += n;
}
// Non-destructive: crypto_generichash_final consumes the state, so digest()
// works on a copy. A transfer asks for the digest at finalize and must still
// be able to keep hashing if it turns out not to be finished.
std::string digest() const {
crypto_generichash_state tmp = st_;
uint8_t out[32];
crypto_generichash_final(&tmp, out, 32);
return to_hex(out, 32);
}
uint64_t bytes() const { return bytes_; }
// Snapshot/restore exist for exactly one reason: resuming a transfer without
// re-reading the file. The digest is a running state over bytes fed in order,
// so persisting that state is what turns resume from O(file) into O(1) — the
// whole argument for the journal.
//
// libsodium's state is a flat struct with no pointers, so a byte copy restores
// it. It is NOT portable across libsodium builds or architectures, which is
// fine — a journal is node-local and never leaves the machine — but it does
// mean a reader must check the size it recorded against the size this build
// uses and fall back to re-verification when they differ. The reference guards
// it the same way.
static size_t state_size() { return crypto_generichash_statebytes(); }
void snapshot(std::vector<uint8_t> &out) const {
out.resize(state_size());
std::memcpy(out.data(), &st_, out.size());
}
bool restore(const uint8_t *state, size_t n, uint64_t consumed) {
if (n != state_size()) return false;
std::memcpy(&st_, state, n);
bytes_ = consumed;
return true;
}
private:
crypto_generichash_state st_{};
uint64_t bytes_ = 0;
};
} // namespace cdc
} // namespace hyperoverlay
#endif // HYPEROVERLAY_CHUNKER_H