🥮 mooncakes.io

    MoonHashKit

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

    hash
    rolling
    content-defined-chunking
    dedupe
    sync
    Download zip
    Author
    Version
    0.3.0
    License
    Apache-2.0
    Repository
    Last updated
    3 months ago
    Downloads
    53

    No dependencies

    #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 issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io