gizlang:erasure

Erasure codes over GF(2^8) (polynomial 0x11D): Reed-Solomon and locally repairable codes (LRC). DATA pieces of equal length give parity pieces; any DATA independent pieces give back each lost one. An LRC adds to each group of data pieces a local parity (their XOR), so one lost piece of a group is rebuilt from its group alone, and global parities (Cauchy rows) for more losses. The products run 32 bytes a step: each nibble one table lookup (pshufb, NEON tbl).

import * as Erasure from "gizlang:erasure";

Types

Code

type Code = { data: i64; parity: Vec<Vec<i64>>; }

DATA data pieces, then a parity piece for each row of PARITY: its coefficient for each data piece.

• data: i64
• parity: Vec<Vec<i64>>

Functions

reedSolomon

function reedSolomon(data: i64, parities: i64): Code throws string

Reed-Solomon: DATA data pieces and PARITIES parity pieces; any DATA of them give back the others.

Effects: fail.

lrc

function lrc(data: i64, groups: i64, globals: i64): Code throws string

An LRC: DATA data pieces in GROUPS groups of equal size, a local parity for each group (the XOR of its pieces), then GLOBALS global parities. LRC(12, 2, 2) stores 16 pieces for 12 (1.33x), rebuilds one lost piece from 6 others and survives any 3 losses. With no groups it is Reed-Solomon.

Effects: fail.

Methods

Code.pieces

function Code.pieces(self: Code): i64

The pieces that a stripe of the code has: its data pieces and its parity pieces.

Effects: fail.

Code.encode

function Code.encode(self: Code, data: Vec<bytes>): Vec<bytes> throws string

The parity pieces of DATA, the data pieces in order, all of one length.

Effects: fail.

Code.sources

function Code.sources(self: Code, want: i64, available: Vec<bool>): Option<Vec<i64>>

The pieces to read to rebuild piece WANT, of those AVAILABLE (by piece): the other pieces of a local group when they are all available, else DATA independent pieces, data pieces first. None when too many pieces are lost.

Effects: fail.

Code.rebuild

function Code.rebuild(self: Code, want: i64, pieces: Vec<Option<bytes>>): bytes throws string

Piece WANT, rebuilt from PIECES (by piece; none where absent): the pieces that Code.sources names for what is given.

Effects: fail.