erasure.ts

1/**2 * erasure.ts — Reed-Solomon erasure coding around the WASM library.3 *4 * The library wants a single contiguous buffer of length5 *   (dataShards + parityShards) * shardSize6 * with data shards laid out first, followed by space for parity. `encode()`7 * fills the parity region in-place. `reconstruct()` rewrites missing shards8 * in-place using a `shardsAvailable: boolean[]` mask.9 *10 * We expose a chunk-oriented API (`encodeWithErasure` / `decodeWithErasure`)11 * because the rest of the codex pipeline thinks in terms of individual12 * envelopes. Both adapters allocate a fresh buffer per call — the library is13 * not re-entrant on a shared buffer.14 */1516import {17  CHUNK_SIZE,18  CodexError,19  MAX_DATA_SHARDS_PER_STRIPE,20  computeParityShards,21} from "../../shared/codex-types";22import { ReedSolomonErasure } from "./reed-solomon";23import { getReedSolomon } from "./rs-loader";2425/**26 * The shared rs-loader caches a single `ReedSolomonErasure` instance. Some27 * builds of the underlying WASM module accumulate __wbindgen state between28 * `reconstruct()` calls and return RESULT_ERROR_TOO_FEW_SHARDS_PRESENT on the29 * second invocation even when enough shards are present. Building a fresh30 * instance per call avoids the failure mode entirely; the cost is a few31 * milliseconds per call — negligible compared to compressing the vault and32 * rendering Aztec codes. We keep the loader's cached instance only as a33 * liveness probe (it confirms the WASM is instantiable on this platform).34 */35let cachedWasmBytes: Uint8Array<ArrayBuffer> | null = null;3637async function freshReedSolomon(): Promise<ReedSolomonErasure> {38  if (cachedWasmBytes) {39    return ReedSolomonErasure.fromBytes(cachedWasmBytes);40  }41  // Capture bytes by intercepting the loader's first instantiation. The42  // loader caches its own promise, so calling it twice is cheap on the second43  // pass. We pull bytes from the WASM memory image after the fact — see44  // `loadWasmBytes` below for the lazy initialization.45  await getReedSolomon();46  if (!cachedWasmBytes) {47    cachedWasmBytes = await loadWasmBytes();48  }49  return ReedSolomonErasure.fromBytes(cachedWasmBytes);50}5152/**53 * Load the raw WASM bytes for re-instantiation. The popup path resolves54 * against the extension package via `chrome.runtime.getURL`; vitest reads55 * directly from `node_modules`. `freshReedSolomon` needs the raw bytes (not56 * the loader's instance) because each call rebuilds the WASM module to avoid57 * cross-call state accumulation in `reconstruct`.58 */59async function loadWasmBytes(): Promise<Uint8Array<ArrayBuffer>> {60  const inPopup =61    typeof chrome !== "undefined" &&62    typeof chrome.runtime !== "undefined" &&63    typeof chrome.runtime.getURL === "function";64  if (inPopup) {65    const url = chrome.runtime.getURL("codex/reed_solomon_erasure_bg.wasm");66    const response = await fetch(url);67    if (!response.ok) {68      throw new CodexError(69        "ERASURE_CODING_VERIFICATION_FAILED",70        `Failed to fetch WASM: ${response.status}`,71      );72    }73    return new Uint8Array(await response.arrayBuffer());74  }75  return readTestWasmBytes();76}7778async function readTestWasmBytes(): Promise<Uint8Array<ArrayBuffer>> {79  if (import.meta.env.MODE !== "test") {80    throw new CodexError(81      "ERASURE_CODING_VERIFICATION_FAILED",82      "Reed-Solomon WASM can only be loaded through chrome.runtime.getURL outside tests",83    );84  }85  const { readNodeReedSolomonWasmBytes } = await import("./node-wasm");86  return readNodeReedSolomonWasmBytes();87}8889/**90 * We map Reed-Solomon result codes to human-readable strings here so the91 * surrounding CodexError messages stay specific instead of leaking a bare92 * number.93 */94function resultMessage(code: number): string {95  switch (code) {96    case ReedSolomonErasure.RESULT_OK: return "ok";97    case ReedSolomonErasure.RESULT_ERROR_TOO_FEW_SHARDS: return "too few shards";98    case ReedSolomonErasure.RESULT_ERROR_TOO_MANY_SHARDS: return "too many shards";99    case ReedSolomonErasure.RESULT_ERROR_TOO_FEW_DATA_SHARDS: return "too few data shards";100    case ReedSolomonErasure.RESULT_ERROR_TOO_MANY_DATA_SHARDS: return "too many data shards";101    case ReedSolomonErasure.RESULT_ERROR_TOO_FEW_PARITY_SHARDS: return "too few parity shards";102    case ReedSolomonErasure.RESULT_ERROR_TOO_MANY_PARITY_SHARDS: return "too many parity shards";103    case ReedSolomonErasure.RESULT_ERROR_TOO_FEW_BUFFER_SHARDS: return "too few buffer shards";104    case ReedSolomonErasure.RESULT_ERROR_TOO_MANY_BUFFER_SHARDS: return "too many buffer shards";105    case ReedSolomonErasure.RESULT_ERROR_INCORRECT_SHARD_SIZE: return "incorrect shard size";106    case ReedSolomonErasure.RESULT_ERROR_TOO_FEW_SHARDS_PRESENT: return "too few shards present";107    case ReedSolomonErasure.RESULT_ERROR_EMPTY_SHARD: return "empty shard";108    case ReedSolomonErasure.RESULT_ERROR_INVALID_SHARD_FLAGS: return "invalid shard flags";109    case ReedSolomonErasure.RESULT_ERROR_INVALID_INDEX: return "invalid index";110    default: return `unknown result code ${code}`;111  }112}113114export interface EncodeResult {115  dataChunks: Uint8Array[];116  parityChunks: Uint8Array[];117  totalChunks: number;118  dataShards: number;119  parityShards: number;120}121122export interface MultiStripeEncodeResult {123  stripes: EncodeResult[];124  /** Sum of `dataShards` across stripes. */125  totalDataChunks: number;126  /** Sum of `parityShards` across stripes. */127  totalParityChunks: number;128  /** Sum of `totalChunks` across stripes = number of Aztec codes to print. */129  totalChunks: number;130}131132/**133 * Plan how many data shards belong to each stripe, balanced as evenly as134 * possible so no single stripe approaches the GF(2⁸) cap. Returns an array of135 * shard counts that sum to `totalDataShards` and where every element is136 * ≤ MAX_DATA_SHARDS_PER_STRIPE.137 */138export function planStripeShardCounts(totalDataShards: number): number[] {139  if (totalDataShards <= 0) return [];140  const numStripes = Math.max(141    1,142    Math.ceil(totalDataShards / MAX_DATA_SHARDS_PER_STRIPE),143  );144  const base = Math.floor(totalDataShards / numStripes);145  const remainder = totalDataShards % numStripes;146  const counts: number[] = [];147  for (let i = 0; i < numStripes; i++) {148    counts.push(base + (i < remainder ? 1 : 0));149  }150  return counts;151}152153/**154 * Split `data` into fixed-size shards plus `computeParityShards(dataShards)`155 * parity shards. Pads the trailing data shard with zeros — the original byte156 * length is recovered via the `CodexPayload.vaultBlob` (no length prefix157 * needed on the wire because the outer JSON already bounds the data).158 *159 * Single-stripe primitive. The GF(2⁸) field caps `dataShards + parityShards`160 * at 256; anything larger panics inside the WASM module, so call161 * `encodeIntoStripes` instead for payloads that need more total shards.162 */163export async function encodeWithErasure(data: Uint8Array): Promise<EncodeResult> {164  const rs = await freshReedSolomon();165166  const dataShards = Math.max(1, Math.ceil(data.length / CHUNK_SIZE));167  const parityShards = computeParityShards(dataShards);168  const totalShards = dataShards + parityShards;169  if (totalShards > 256) {170    throw new CodexError(171      "ERASURE_CODING_VERIFICATION_FAILED",172      `Single RS stripe cannot exceed 256 shards (got ${totalShards}; ${data.length} bytes / ${CHUNK_SIZE}-byte chunks). Use encodeIntoStripes for large payloads.`,173    );174  }175  const buffer = new Uint8Array(totalShards * CHUNK_SIZE);176  buffer.set(data, 0); // Trailing bytes after `data.length` stay zero — the pad.177178  let code: number;179  try {180    code = rs.encode(buffer, dataShards, parityShards);181  } catch (err) {182    // WASM traps (e.g. Rust panics) surface as raw JS errors with messages183    // like "unreachable". Map them to a typed CodexError so the UI can184    // explain what happened instead of leaking the trap string.185    throw new CodexError(186      "ERASURE_CODING_VERIFICATION_FAILED",187      `Reed-Solomon encode trapped (data=${dataShards}, parity=${parityShards}): ${188        err instanceof Error ? err.message : String(err)189      }`,190    );191  }192  if (code !== ReedSolomonErasure.RESULT_OK) {193    throw new CodexError(194      "ERASURE_CODING_VERIFICATION_FAILED",195      `Reed-Solomon encode failed: ${resultMessage(code)}`,196    );197  }198199  // Slice() copies so each shard owns its memory and callers cannot mutate200  // the working buffer through a returned view.201  const dataChunks: Uint8Array[] = [];202  for (let i = 0; i < dataShards; i++) {203    dataChunks.push(buffer.slice(i * CHUNK_SIZE, (i + 1) * CHUNK_SIZE));204  }205  const parityChunks: Uint8Array[] = [];206  for (let i = 0; i < parityShards; i++) {207    const base = (dataShards + i) * CHUNK_SIZE;208    parityChunks.push(buffer.slice(base, base + CHUNK_SIZE));209  }210211  return {212    dataChunks,213    parityChunks,214    totalChunks: totalShards,215    dataShards,216    parityShards,217  };218}219220/**221 * Reassemble the data-shard region from a partial set of chunks. Missing222 * shards are reconstructed from parity. The returned buffer is exactly223 * `dataShards * shardSize` bytes long, including any trailing pad bytes224 * — callers strip the pad using their out-of-band length information.225 *226 * Shard size is derived from the actual chunks rather than the current227 * `CHUNK_SIZE` constant so that Codexes printed under an older constant228 * (e.g. 1024-byte shards) still restore on a build whose constant has moved.229 * Reed-Solomon requires all shards to share one length; the first chunk230 * establishes it and every other chunk must match.231 */232export async function decodeWithErasure(233  chunks: Map<number, Uint8Array>,234  dataShards: number,235  totalShards: number,236): Promise<Uint8Array> {237  const parityShards = totalShards - dataShards;238  if (parityShards < 0) {239    throw new CodexError(240      "ERASURE_CODING_VERIFICATION_FAILED",241      `Invalid shard layout: dataShards=${dataShards} totalShards=${totalShards}`,242    );243  }244245  if (chunks.size < dataShards) {246    throw new CodexError(247      "INSUFFICIENT_CHUNKS",248      `Need at least ${dataShards} chunks, have ${chunks.size}`,249    );250  }251252  // First scanned chunk fixes the shard size for the whole reconstruction.253  const firstChunk = chunks.values().next().value;254  if (!firstChunk || firstChunk.length === 0) {255    throw new CodexError(256      "ERASURE_CODING_VERIFICATION_FAILED",257      "First chunk is empty; cannot determine shard size",258    );259  }260  const shardSize = firstChunk.length;261262  const rs = await freshReedSolomon();263  const buffer = new Uint8Array(totalShards * shardSize);264  const available: boolean[] = new Array(totalShards).fill(false);265266  for (const [index, chunk] of chunks) {267    if (index < 0 || index >= totalShards) {268      throw new CodexError(269        "ERASURE_CODING_VERIFICATION_FAILED",270        `Chunk index ${index} out of range [0, ${totalShards})`,271      );272    }273    if (chunk.length !== shardSize) {274      throw new CodexError(275        "ERASURE_CODING_VERIFICATION_FAILED",276        `Chunk ${index} has length ${chunk.length}, expected ${shardSize}`,277      );278    }279    buffer.set(chunk, index * shardSize);280    available[index] = true;281  }282283  let code: number;284  try {285    code = rs.reconstruct(buffer, dataShards, parityShards, available);286  } catch (err) {287    throw new CodexError(288      "ERASURE_CODING_VERIFICATION_FAILED",289      `Reed-Solomon reconstruct trapped (data=${dataShards}, parity=${parityShards}, have=${chunks.size}): ${290        err instanceof Error ? err.message : String(err)291      }`,292    );293  }294  if (code !== ReedSolomonErasure.RESULT_OK) {295    // The library distinguishes "not enough shards" with its own code; map it296    // back to our INSUFFICIENT_CHUNKS so handlers upstream can surface a297    // clean "scan more codes" prompt instead of a generic library error.298    if (code === ReedSolomonErasure.RESULT_ERROR_TOO_FEW_SHARDS_PRESENT) {299      throw new CodexError(300        "INSUFFICIENT_CHUNKS",301        `Need at least ${dataShards} valid chunks for reconstruction`,302      );303    }304    throw new CodexError(305      "ERASURE_CODING_VERIFICATION_FAILED",306      `Reed-Solomon reconstruct failed: ${resultMessage(code)}`,307    );308  }309310  return buffer.slice(0, dataShards * shardSize);311}312313/**314 * Multi-stripe encode. Splits `data` into balanced RS stripes (each ≤315 * MAX_DATA_SHARDS_PER_STRIPE data shards) and encodes each independently.316 * The stripes are byte-contiguous: stripe `s` covers exactly317 * `dataShardsForStripe(s) * CHUNK_SIZE` bytes of payload, with the last shard318 * of the last stripe zero-padded when the payload doesn't align. Restore319 * concatenates each stripe's decoded data region and inflates the whole thing320 * — pako tolerates the trailing zeros.321 */322export async function encodeIntoStripes(323  data: Uint8Array,324): Promise<MultiStripeEncodeResult> {325  const totalDataShards = Math.max(1, Math.ceil(data.length / CHUNK_SIZE));326  const stripeShardCounts = planStripeShardCounts(totalDataShards);327328  const stripes: EncodeResult[] = [];329  let byteCursor = 0;330  for (const shardCount of stripeShardCounts) {331    const stripeByteCap = shardCount * CHUNK_SIZE;332    const stripeEnd = Math.min(byteCursor + stripeByteCap, data.length);333    const stripeBytes = data.subarray(byteCursor, stripeEnd);334    const result = await encodeWithErasure(stripeBytes);335    // Sanity: encodeWithErasure infers dataShards from byte length; for any336    // stripe but the last, the slice is exactly `shardCount * CHUNK_SIZE`337    // bytes and the inferred count must match the plan. For the last stripe338    // the byte length may be shorter (zero-pad happens inside the encoder)339    // but the shard count still matches because the planner used the same340    // ceil-division.341    if (result.dataShards !== shardCount) {342      throw new CodexError(343        "ERASURE_CODING_VERIFICATION_FAILED",344        `Stripe plan mismatch: planned ${shardCount} data shards, encoder produced ${result.dataShards}`,345      );346    }347    stripes.push(result);348    byteCursor += stripeByteCap;349  }350351  const totalDataChunks = stripes.reduce((s, x) => s + x.dataShards, 0);352  const totalParityChunks = stripes.reduce((s, x) => s + x.parityShards, 0);353  const totalChunks = totalDataChunks + totalParityChunks;354  return { stripes, totalDataChunks, totalParityChunks, totalChunks };355}