🥮 mooncakes.io

MoonHashKit

Content-defined chunking, rolling fingerprints, and deduplication for MoonBit.

hash
rolling
content-defined-chunking
dedupe
sync
moon add cn-ybm/MoonHashKit@0.3.0
Download zip
Author
Version
0.3.0
License
Apache-2.0
Repository
Last updated
last month
Downloads
13
README

#MoonHashKit

MoonHashKit 是面向 MoonBit 的内容定义分块、滚动指纹与轻量去重基础库。它不与社区 底层 hash 函数库竞争，而是解决增量同步、备份、缓存和重复内容发现中的工程问题。

本项目只提供非密码学指纹，不用于签名、口令存储或安全认证。

#核心价值

  • 真正 O(n) 滚动哈希：窗口移动时移出旧字节、移入新字节，不再重复复制窗口。
  • 内容定义分块（CDC）：边界由有限窗口内容决定，局部编辑后可重新同步。
  • 溢出安全：使用 Int64 中间算术，避免 32 位乘法先溢出再取模。
  • 分块去重：固定分块、重复组、候选位置和内容摘要。
  • 流式 CDC：CdcStream 支持把网络包或文件块分批喂入，边界结果与一次性 处理保持一致，不必保留完整输入。
  • 双指纹与验证匹配：双多项式指纹用于低成本候选筛选；同步计划会再逐字节 验证，避免把非密码学哈希碰撞误判为可复用内容。
  • 清单与同步计划：固定分块和 CDC 都能生成确定性清单，并计算目标端缺失的 固定分块，便于上层备份、缓存或传输系统接入。
  • 后端中立：核心算法不依赖文件系统、浏览器、网络或平台 FFI。

#内容定义分块

///|
test {
  let bytes = ascii_bytes("alpha-beta-gamma-alpha-beta-gamma-alpha-beta-gamma")
  let config = CdcConfig::new(
    8, // 最小分块
     16, // 目标平均分块
     32, // 最大分块
     4, // 滚动窗口
  )
  let chunks = content_defined_chunks(bytes, config)
  let summary = summarize_cdc(chunks)

  assert_eq(summary.bytes, bytes.length())
  assert_true(summary.chunks > 0)
}

与固定大小分块相比，CDC 在文件前部插入或删除少量内容后，后续边界能够重新对齐， 从而复用更多未变化分块。

#滚动窗口指纹

///|
test {
  let hashes = window_hashes([1, 2, 3, 4, 5], 3, base=31, modulo=1009)
  assert_eq(hashes.length(), 3)
}

每个滚动结果均与对应窗口独立计算的多项式哈希一致。

#流式分块与缺失块计划

///|
let config = CdcConfig::new(8, 16, 32, 4)

///|
let stream = CdcStream::new(config)

///|
let completed = stream.push(ascii_bytes("first network packet"))

///|
let final_chunks = stream.finish()

///|
let missing = missing_fixed_chunks(
  ascii_bytes("alpha-beta-gamma"),
  ascii_bytes("alpha-beta"),
  4,
)

CdcStream 的 push 只返回已经确定边界的块；finish 返回最后的残留块。 missing_fixed_chunks 先用索引筛选候选，再做逐字节验证；它返回传输计划， 不会复制或持久化数据。

#运行与验收

moon check --target all
moon test --target wasm
moon run cmd/main
moon run cmd/bench

CI 采用当前 MoonBit 工具链可执行的等价验收门禁：moon fmt --check、 moon check --deny-warn --target all、moon info 后 .mbti 无差异，以及 moon test --deny-warn --target all。当前 moon fmt 与 moon info 不接受 --deny-warn 参数，因此不会在 CI 中加入必然失败的伪检查。

详见 验收证据、 相关工作 和 路线图。

#仓库

#
CdcConfig

source
pub(all) struct CdcConfig {
  min_size : Int
  average_size : Int
  max_size : Int
  window_size : Int
} derive(Eq, 
Debug)

Parameters for finite-window content-defined chunking.

#
CdcConfig::new

source
fn CdcConfig::new(min_size : Int, average_size : Int, max_size : Int, window_size : Int) -> CdcConfig

#
CdcStream

source
pub(all) struct CdcStream {
  config : CdcConfig
  pending : Array[Int]
  ring : Array[Int]
  ring_start : Int
  rolling_value : Int
  next_start : Int
  highest_power : Int
} derive(
Debug)

Stateful finite-window CDC processor for streaming or batched input.

The rolling window remains continuous across emitted chunks, matching the boundary semantics of content_defined_chunks while avoiding the need to retain the complete input in memory.

#
CdcStream::finish

source
fn CdcStream::finish(self : CdcStream) -> Array[ChunkFingerprint]

Finishes a stream and returns its final partial chunk, if present.

#
CdcStream::new

source
fn CdcStream::new(config : CdcConfig) -> CdcStream

#
CdcStream::pending_bytes

source
fn CdcStream::pending_bytes(self : CdcStream) -> Int

#
CdcStream::push

source
fn CdcStream::push(self : CdcStream, bytes : Array[Int]) -> Array[ChunkFingerprint]

Feeds any number of bytes and returns only fully decided chunks.

#
CdcSummary

source
pub(all) struct CdcSummary {
  bytes : Int
  chunks : Int
  min_chunk : Int
  max_chunk : Int
  average_chunk : Double
} derive(
Debug)

#
CdcSummary::to_json

source
fn CdcSummary::to_json(self : CdcSummary) -> String

#
Checksum

source
pub(all) struct Checksum {
  algorithm : String
  value : Int
  bytes : Int
} derive(Eq, 
Debug)

#
Checksum::to_json

source
fn Checksum::to_json(self : Checksum) -> String

#
ChunkFingerprint

source
pub(all) struct ChunkFingerprint {
  start : Int
  length : Int
  hash : Int
} derive(Eq, 
Debug)

#
ChunkFingerprint::to_json

source
fn ChunkFingerprint::to_json(self : ChunkFingerprint) -> String

#
ChunkManifest

source
pub(all) struct ChunkManifest {
  bytes : Int
  entries : Array[ManifestEntry]
} derive(
Debug)

A deterministic chunk manifest suitable for backup or synchronization metadata. It stores offsets and fingerprints, not source bytes.

#
ChunkManifest::entry_count

source
fn ChunkManifest::entry_count(self : ChunkManifest) -> Int

#
ChunkManifest::to_json

source
fn ChunkManifest::to_json(self : ChunkManifest) -> String

#
CompareResult

source
pub(all) struct CompareResult {
  same_length : Bool
  same_checksum : Bool
  same_hash : Bool
} derive(Eq, 
Debug)

#
CompareResult::is_probable_match

source
fn CompareResult::is_probable_match(self : CompareResult) -> Bool

#
ContentSummary

source
pub(all) struct ContentSummary {
  bytes : Int
  checksum8 : Int
  hash32 : Int
  chunks : Int
  duplicate_pairs : Int
} derive(Eq, 
Debug)

#
ContentSummary::to_json

source
fn ContentSummary::to_json(self : ContentSummary) -> String

#
DualFingerprint

source
pub(all) struct DualFingerprint {
  primary : Int
  secondary : Int
  bytes : Int
} derive(Eq, 
Debug)

Two independent polynomial fingerprints for a byte sequence.

This reduces accidental candidate collisions during transport planning, but is still not a cryptographic digest. Use byte_ranges_equal before treating untrusted content as identical.

#
DualFingerprint::to_json

source
fn DualFingerprint::to_json(self : DualFingerprint) -> String

#
DuplicateGroup

source
pub(all) struct DuplicateGroup {
  hash : Int
  length : Int
  occurrences : Int
  first_start : Int
} derive(Eq, 
Debug)

#
DuplicateGroup::to_json

source
fn DuplicateGroup::to_json(self : DuplicateGroup) -> String

#
FingerprintBucket

source
pub(all) struct FingerprintBucket {
  hash : Int
  length : Int
  starts : Array[Int]
} derive(
Debug)

#
FingerprintBucket::add_start

source
fn FingerprintBucket::add_start(self : FingerprintBucket, start : Int) -> Unit

#
FingerprintBucket::new

source

#
FingerprintBucket::occurrences

source
fn FingerprintBucket::occurrences(self : FingerprintBucket) -> Int

#
FingerprintBucket::to_json

source
fn FingerprintBucket::to_json(self : FingerprintBucket) -> String

#
Hash32

source
pub(all) struct Hash32 {
  algorithm : String
  value : Int
  bytes : Int
} derive(Eq, 
Debug)

#
Hash32::to_json

source
fn Hash32::to_json(self : Hash32) -> String

#
HashIndex

source
pub(all) struct HashIndex {
  chunk_size : Int
  buckets : Array[FingerprintBucket]
} derive(
Debug)

#
HashIndex::add_chunk

source
fn HashIndex::add_chunk(self : HashIndex, chunk : ChunkFingerprint) -> Unit

#
HashIndex::bucket_count

source
fn HashIndex::bucket_count(self : HashIndex) -> Int

#
HashIndex::candidate_starts

source
fn HashIndex::candidate_starts(self : HashIndex, hash : Int, length : Int) -> Array[Int]

#
HashIndex::duplicate_group_count

source
fn HashIndex::duplicate_group_count(self : HashIndex) -> Int

#
HashIndex::duplicate_groups

source
fn HashIndex::duplicate_groups(self : HashIndex) -> Array[DuplicateGroup]

#
HashIndex::new

source
fn HashIndex::new(chunk_size : Int) -> HashIndex

#
HashIndex::to_json

source
fn HashIndex::to_json(self : HashIndex) -> String

#
HashIndex::total_chunks

source
fn HashIndex::total_chunks(self : HashIndex) -> Int

#
ManifestEntry

source
pub(all) struct ManifestEntry {
  start : Int
  length : Int
  fingerprint : DualFingerprint
} derive(
Debug)

A serializable entry in a fixed-size or CDC chunk manifest.

#
VerifiedChunkMatch

source
pub(all) struct VerifiedChunkMatch {
  left_start : Int
  right_start : Int
  length : Int
} derive(Eq, 
Debug)

A content match that has been verified byte-for-byte after fingerprint lookup. Hash equality alone is deliberately not treated as proof of equality by this type.

#
VerifiedChunkMatch::to_json

source
fn VerifiedChunkMatch::to_json(self : VerifiedChunkMatch) -> String

#
ascii_bytes

source
fn ascii_bytes(text : String) -> Array[Int]

#
ascii_code

source
fn ascii_code(ch : Char) -> Int

#
ascii_window_hashes

source
fn ascii_window_hashes(text : String, window_size : Int) -> Array[Hash32]

#
build_hash_index

source
fn build_hash_index(bytes : Array[Int], chunk_size : Int) -> HashIndex

#
byte_ranges_equal

source
fn byte_ranges_equal(left : Array[Int], left_start : Int, right : Array[Int], right_start : Int, length : Int) -> Bool

Compares two byte ranges without allocating slice arrays.

Inputs are normalized in the same way as the polynomial fingerprint APIs, so a caller cannot accidentally accept bytes that hash differently from their verification representation.

#
cdc_chunk_manifest

source
fn cdc_chunk_manifest(bytes : Array[Int], config : CdcConfig) -> ChunkManifest

Builds a manifest for content-defined chunks.

#
checksum8

source
fn checksum8(bytes : Array[Int]) -> Checksum

#
checksum8_value

source
fn checksum8_value(bytes : Array[Int]) -> Int

#
chunk_fingerprints

source
fn chunk_fingerprints(bytes : Array[Int], chunk_size : Int) -> Array[ChunkFingerprint]

#
compare_content

source
fn compare_content(left : Array[Int], right : Array[Int]) -> CompareResult

#
content_defined_chunks

source
fn content_defined_chunks(bytes : Array[Int], config : CdcConfig) -> Array[ChunkFingerprint]

Splits data at content-derived boundaries.

Boundary decisions use a finite rolling window, allowing chunk boundaries to resynchronize after local insertions or deletions.

#
dual_fingerprint

source
fn dual_fingerprint(bytes : Array[Int]) -> DualFingerprint

#
duplicate_hash_count

source
fn duplicate_hash_count(chunks : Array[ChunkFingerprint]) -> Int

#
fixed_chunk_manifest

source
fn fixed_chunk_manifest(bytes : Array[Int], chunk_size : Int) -> ChunkManifest

Builds a manifest for fixed-size chunking.

#
has_duplicate_hashes

source
fn has_duplicate_hashes(chunks : Array[ChunkFingerprint]) -> Bool

#
hash_ascii

source
fn hash_ascii(text : String) -> Hash32

#
missing_fixed_chunks

source
fn missing_fixed_chunks(source : Array[Int], destination : Array[Int], chunk_size : Int) -> Array[ChunkFingerprint]

Returns source chunks not present in a destination under byte-for-byte verification. This is a transport plan, not a copy operation.

#
normalize_byte

source
fn normalize_byte(value : Int) -> Int

#
polynomial_hash

source
fn polynomial_hash(bytes : Array[Int], base? : Int, modulo? : Int) -> Hash32

#
polynomial_hash_value

source
fn polynomial_hash_value(bytes : Array[Int], base? : Int, modulo? : Int) -> Int

#
summarize_cdc

source
fn summarize_cdc(chunks : Array[ChunkFingerprint]) -> CdcSummary

#
summarize_content

source
fn summarize_content(bytes : Array[Int], chunk_size? : Int) -> ContentSummary

#
verified_chunk_matches

source
fn verified_chunk_matches(left : Array[Int], left_chunks : Array[ChunkFingerprint], right : Array[Int], right_chunks : Array[ChunkFingerprint]) -> Array[VerifiedChunkMatch]

Verifies matches between arbitrary chunk layouts, including CDC manifests. It is intentionally straightforward so callers can apply their own index strategy when processing very large manifests.

#
verified_fixed_chunk_matches

source
fn verified_fixed_chunk_matches(left : Array[Int], right : Array[Int], chunk_size : Int) -> Array[VerifiedChunkMatch]

Finds equal fixed-size chunks in two contents.

The right-side index narrows the search by fingerprint and length; every candidate is then checked with byte_ranges_equal, avoiding false-positive deduplication when a non-cryptographic fingerprint collides.

#
window_hashes

source
fn window_hashes(bytes : Array[Int], window_size : Int, base? : Int, modulo? : Int) -> Array[Hash32]

Source Files

Powered by MoonBit

Site sourceReport issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io