README
¶
reedsolomon
Pure-Go, dependency-free Reed-Solomon erasure code over GF(2¹⁶). It works both as a general erasure codec for storage redundancy and as the arithmetic core for PAR2.
- CGO_ENABLED=0, standard library only, no third-party dependencies.
- MDS systematic code: a Cauchy generator matrix guarantees any
dataShardsof thedataShards + parityShardsshards reconstruct the original data. - PAR2-compatible field: GF(2¹⁶) with primitive polynomial
0x1100Band generator2. The exportedGF16type can be reused by a PAR2 layer built on top of this package. - SIMD region multiply: the field-region hot loops (
galMul/galMulAdd, which is allEncode/Verify/Reconstructspend their time in) have a go-asmgen split-table fast path on all six 64-bit targets — amd64, arm64, s390x, ppc64le, riscv64 and loong64 — each proven bit-identical to the scalar loop by a differential oracle (under QEMU for the emulated arches). See Performance. - 100% test coverage, verified across nine
GOOS/GOARCHtargets.
Performance
The region multiply uses the GF-Complete SPLIT(16,4) technique: for a fixed coefficient, four low-byte and four high-byte 16-entry nibble tables turn a GF(2¹⁶) product into eight byte-shuffle lookups XORed together, so 16 words are multiplied per iteration instead of one at a time. Each arch expresses the same math with its native byte-permute: deinterleave the big-endian words into HI/LO byte planes, extract the four nibbles, do the eight table lookups, XOR, and re-interleave. The Go dispatch builds the per-coefficient tables (256 field multiplies, cheap next to folding a whole shard) and hands them to the assembly kernel; the sub-block tail falls back to the scalar loop.
| Arch | Kernel | Verification |
|---|---|---|
| amd64 | SSSE3 PSHUFB, 128-bit, 32 B/iter |
native CI + Rosetta |
| arm64 | NEON VLD2/TBL/VST2, 32 B/iter |
native CI + dev host |
| s390x | z13 vector VPERM + VMRHB/VMRLB |
QEMU (differential + 100% cov) |
| ppc64le | POWER8 VSX LXVD2X/VPERM/STXVD2X |
QEMU power9 + power8 ISA guard |
| riscv64 | RVV vlseg2e8/vrgather.vv, VLEN-agnostic |
QEMU v=true,vlen=256 (+ 128) |
| loong64 | LSX vshuf.b + vilvl.b/vilvh.b |
QEMU la464 |
The ppc64le kernel is strictly POWER8-baseline (no ISA-3.0 LXVB16X); a dedicated
CI lane runs it under QEMU_CPU=power8 to prove it never SIGILLs. The riscv64
kernel dispatches only when the V extension is present (cpu.RISCV64.HasV) and is
byte-granular (segment loads), so it is VLEN-agnostic and free of the misaligned
wider-load trap.
galMulAdd over a 1 MiB region, dev host (Apple arm64):
BenchmarkGalMulAddScalar 1447 MB/s
BenchmarkGalMulAddSIMD 19453 MB/s (~13.4x, NEON)
Every kernel is proven byte-for-byte identical to the scalar oracle by the
galois_simd_test.go differential size-sweep and fuzz — natively on amd64/arm64
and under QEMU user emulation on the other four — and each emulated lane also
gates at 100% statement coverage. Absolute throughput of the four emulated kernels
is a real-hardware measurement (cfarm POWER/RISC-V/loong, direct LinuxONE s390x)
tracked separately; correctness does not wait on it.
Install
go get github.com/go-erasure/reedsolomon
Requires Go 1.26.4 or newer.
Example
package main
import (
"bytes"
"fmt"
"github.com/go-erasure/reedsolomon"
)
func main() {
// 4 data shards + 2 parity shards: any 4 of the 6 shards recover everything.
enc, err := reedsolomon.New(4, 2)
if err != nil {
panic(err)
}
// Shards are byte slices read as big-endian uint16 words; all shards must
// share the same even length. The parity shards are written by Encode.
shards := make([][]byte, 6)
for i := range shards {
shards[i] = make([]byte, 8)
}
copy(shards[0], []byte("data0..."))
copy(shards[1], []byte("data1..."))
copy(shards[2], []byte("data2..."))
copy(shards[3], []byte("data3..."))
if err := enc.Encode(shards); err != nil {
panic(err)
}
// Simulate the loss of two shards (one data, one parity).
original := append([]byte(nil), shards[1]...)
present := []bool{true, false, true, true, false, true}
for i, ok := range present {
if !ok {
for k := range shards[i] {
shards[i][k] = 0 // erased slice must stay allocated to shard length
}
}
}
if err := enc.Reconstruct(shards, present); err != nil {
panic(err)
}
fmt.Println("recovered:", bytes.Equal(shards[1], original)) // true
}
API
func New(dataShards, parityShards int) (*Encoder, error)
func (e *Encoder) Encode(shards [][]byte) error
func (e *Encoder) Verify(shards [][]byte) (bool, error)
func (e *Encoder) Reconstruct(shards [][]byte, present []bool) error
Shards are interpreted as big-endian uint16 words, so every shard must have
the same even length. Reconstruct succeeds whenever at least dataShards
shards are present; each erased shard's slice must remain allocated to the
common shard length.
The finite field
GF16 implements GF(2¹⁶) with primitive polynomial 0x1100B and generator 2,
the exact field used by PAR2:
f := reedsolomon.NewGF16()
f.Add(a, b) // XOR
f.Mul(a, b)
f.Div(a, b) // panics if b == 0
f.Exp(power)
f.Pow(a, n)
License
BSD-3-Clause. See LICENSE. Copyright the go-erasure/reedsolomon authors.
Documentation
¶
Overview ¶
Package reedsolomon implements a pure-Go, dependency-free Reed-Solomon erasure code over GF(2^16).
The finite field uses the primitive polynomial 0x1100B and generator 2, making it byte-for-byte compatible with the field used by the PAR2 recovery format. The GF16 type is exported so that a PAR2 layer built on top of this package can reuse the exact same arithmetic core.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrShardCount is returned when the number of shards (or present flags) // does not equal dataShards+parityShards. ErrShardCount = errors.New("reedsolomon: wrong number of shards") // ErrShardSize is returned when shards are not all equal length or their // length is odd (shards are big-endian uint16 words). ErrShardSize = errors.New("reedsolomon: shards must be equal, even-length") // ErrTooFewShards is returned when fewer than dataShards shards are present // during reconstruction. ErrTooFewShards = errors.New("reedsolomon: not enough shards present to reconstruct") // ErrInvalidParams is returned by New for non-positive shard counts or when // dataShards+parityShards exceeds 65535. ErrInvalidParams = errors.New("reedsolomon: invalid data/parity shard counts") )
Errors returned by the package.
Functions ¶
This section is empty.
Types ¶
type Encoder ¶
type Encoder struct {
// contains filtered or unexported fields
}
Encoder is an (n = dataShards + parityShards) Reed-Solomon erasure coder over GF(2^16). Shards are byte slices interpreted as big-endian uint16 words; all shards must share the same even length.
func New ¶
New returns an encoder for dataShards data shards plus parityShards parity shards. It returns ErrInvalidParams if either count is non-positive or if dataShards+parityShards exceeds 65535.
func (*Encoder) DataShards ¶
DataShards returns the number of data shards.
func (*Encoder) Encode ¶
Encode fills the parity shards from the data shards. shards must have length dataShards+parityShards; the first dataShards are read and the remaining parityShards are written.
func (*Encoder) ParityShards ¶
ParityShards returns the number of parity shards.
func (*Encoder) Reconstruct ¶
Reconstruct recovers missing shards in place. present[i] == false marks shard i (data or parity) as erased; each erased shard's slice must already be allocated to the common shard length. It succeeds when at least dataShards shards are present.
type GF16 ¶
type GF16 struct {
// contains filtered or unexported fields
}
GF16 provides arithmetic over GF(2^16) with primitive polynomial 0x1100B and generator 2. It holds precomputed exponent and logarithm tables over the 65535-element multiplicative group.
func NewGF16 ¶
func NewGF16() *GF16
NewGF16 returns a GF16 with its exp/log tables built for generator 2 and primitive polynomial 0x1100B.
func (*GF16) Div ¶
Div returns a / b in GF(2^16). Dividing by zero panics; callers must ensure b is non-zero.
func (*GF16) Exp ¶
Exp returns generator^power. Negative and large powers are reduced modulo the order of the multiplicative group.
Source Files