《移动游戏产品的架构·网络、资源与热更新》11.1 差量算法与补丁格式

// file: src/hotfix/delta.ts
// tier: L1
// verify: node --test test/hotfix/delta.test.ts

export interface FileEntry {
  readonly path: string;
  readonly bytes: number;
  readonly hash: string;
  readonly content?: string;
}

export interface Manifest {
  readonly version: string;
  readonly files: readonly FileEntry[];
}

export type ChangeKind = "keep" | "add" | "replace" | "remove";

export interface FileChange {
  readonly kind: ChangeKind;
  readonly path: string;
  readonly bytes: number;
  readonly fromHash?: string;
  readonly toHash?: string;
}

export interface ManifestDiff {
  readonly changes: readonly FileChange[];
  readonly keepBytes: number;
  readonly addBytes: number;
  readonly removeBytes: number;
  readonly replaceBytes: number;
}

export interface ContentDiff {
  readonly copyBlocks: number;
  readonly literalBytes: number;
  readonly copyBytes: number;
}

export interface DeltaOptions {
  readonly blockSize?: number;
}

export interface DeltaPlan extends ManifestDiff {
  readonly baseVersion: string;
  readonly targetVersion: string;
  readonly patchBytes: number;
  readonly fullBytes: number;
  readonly savingRatio: number;
  readonly warnings: readonly string[];
}

export const DEFAULT_BLOCK_SIZE = 4096;
const RECORD_OVERHEAD = 48;
const COPY_OP_OVERHEAD = 12;

function indexManifest(manifest: Manifest): Map<string, FileEntry> {
  if (manifest.version.trim() === "") {
    throw new Error("manifest version is empty");
  }
  const index = new Map<string, FileEntry>();
  for (const file of manifest.files) {
    if (file.path.trim() === "") {
      throw new Error("file path is empty");
    }
    if (!Number.isInteger(file.bytes) || file.bytes < 0) {
      throw new Error(`invalid bytes for ${file.path}: ${file.bytes}`);
    }
    if (file.hash.trim() === "") {
      throw new Error(`missing hash for ${file.path}`);
    }
    if (index.has(file.path)) {
      throw new Error(`duplicate path: ${file.path}`);
    }
    if (file.content !== undefined && Buffer.byteLength(file.content, "utf8") !== file.bytes) {
      throw new Error(`content size mismatch for ${file.path}`);
    }
    index.set(file.path, file);
  }
  return index;
}

export function diffContent(
  oldContent: string,
  newContent: string,
  blockSize: number = DEFAULT_BLOCK_SIZE,
): ContentDiff {
  if (!Number.isInteger(blockSize) || blockSize <= 0) {
    throw new Error(`invalid block size: ${blockSize}`);
  }
  const oldBuffer = Buffer.from(oldContent, "utf8");
  const newBuffer = Buffer.from(newContent, "utf8");
  const known = new Map<string, number>();
  for (let offset = 0; offset < oldBuffer.length; offset += blockSize) {
    const key = oldBuffer.subarray(offset, offset + blockSize).toString("base64");
    if (!known.has(key)) known.set(key, offset);
  }

  let copyBlocks = 0;
  let literalBytes = 0;
  let copyBytes = 0;
  for (let offset = 0; offset < newBuffer.length; offset += blockSize) {
    const block = newBuffer.subarray(offset, offset + blockSize);
    if (known.has(block.toString("base64"))) {
      copyBlocks += 1;
      copyBytes += block.length;
    } else {
      literalBytes += block.length;
    }
  }
  return { copyBlocks, literalBytes, copyBytes };
}

export function diffManifests(base: Manifest, target: Manifest): ManifestDiff {
  const from = indexManifest(base);
  const to = indexManifest(target);
  const paths = [...new Set([...from.keys(), ...to.keys()])].sort();

  const changes: FileChange[] = [];
  let keepBytes = 0;
  let addBytes = 0;
  let removeBytes = 0;
  let replaceBytes = 0;

  for (const path of paths) {
    const before = from.get(path);
    const after = to.get(path);
    if (before !== undefined && after !== undefined) {
      if (before.hash === after.hash) {
        changes.push({
          kind: "keep",
          path,
          bytes: after.bytes,
          fromHash: before.hash,
          toHash: after.hash,
        });
        keepBytes += after.bytes;
      } else {
        changes.push({
          kind: "replace",
          path,
          bytes: after.bytes,
          fromHash: before.hash,
          toHash: after.hash,
        });
        replaceBytes += after.bytes;
      }
    } else if (after !== undefined) {
      changes.push({ kind: "add", path, bytes: after.bytes, toHash: after.hash });
      addBytes += after.bytes;
    } else if (before !== undefined) {
      changes.push({ kind: "remove", path, bytes: before.bytes, fromHash: before.hash });
      removeBytes += before.bytes;
    }
  }

  return { changes, keepBytes, addBytes, removeBytes, replaceBytes };
}

export function planDelta(
  base: Manifest,
  target: Manifest,
  options: DeltaOptions = {},
): DeltaPlan {
  const diff = diffManifests(base, target);
  const from = indexManifest(base);
  const to = indexManifest(target);
  const blockSize = options.blockSize ?? DEFAULT_BLOCK_SIZE;
  if (!Number.isInteger(blockSize) || blockSize <= 0) {
    throw new Error(`invalid block size: ${blockSize}`);
  }

  let patchBytes = 0;
  let replacedWithoutContent = 0;
  let fullBytes = 0;
  for (const file of target.files) fullBytes += file.bytes;

  for (const change of diff.changes) {
    patchBytes += RECORD_OVERHEAD;
    if (change.kind === "add") {
      patchBytes += change.bytes;
    } else if (change.kind === "replace") {
      const before = from.get(change.path);
      const after = to.get(change.path);
      if (before?.content !== undefined && after?.content !== undefined) {
        const contentDiff = diffContent(before.content, after.content, blockSize);
        patchBytes += contentDiff.literalBytes + contentDiff.copyBlocks * COPY_OP_OVERHEAD;
      } else {
        patchBytes += change.bytes;
        replacedWithoutContent += 1;
      }
    }
  }

  const warnings: string[] = [];
  if (replacedWithoutContent > 0) {
    warnings.push(
      `${replacedWithoutContent} replaced files lack content; counted as full replacement`,
    );
  }
  if (fullBytes > 0 && patchBytes >= fullBytes) {
    warnings.push("delta patch is not smaller than the full package");
  }

  const savingRatio = fullBytes === 0 ? 0 : Number((1 - patchBytes / fullBytes).toFixed(4));

  return {
    ...diff,
    baseVersion: base.version,
    targetVersion: target.version,
    patchBytes,
    fullBytes,
    savingRatio,
    warnings,
  };
}

export function formatDeltaPlan(plan: DeltaPlan): string {
  const counts: Record<ChangeKind, number> = { keep: 0, add: 0, replace: 0, remove: 0 };
  const lines = [`delta ${plan.baseVersion} -> ${plan.targetVersion}`];
  for (const change of plan.changes) {
    counts[change.kind] += 1;
    lines.push(`${change.kind}\t${change.path}\t${change.bytes}`);
  }
  lines.push(
    `summary\tfull=${plan.fullBytes}B\tpatch=${plan.patchBytes}B\tsaving=${(plan.savingRatio * 100).toFixed(1)}%\tkeep=${counts.keep}\tadd=${counts.add}\treplace=${counts.replace}\tremove=${counts.remove}`,
  );
  return lines.join("\n");
}

delta 2026.10.28 -> 2026.11.05
replace	config/battle.json	8192
keep	ui/atlas/hud.png	40960
add	ui/atlas/new-mode.png	2048
remove	ui/atlas/retired.png	4096
summary	full=51200B	patch=4360B	saving=91.5%	keep=1	add=1	replace=1	remove=1