mojette

README

mojette

Pure-Go implementation of the Mojette transform erasure code: the discrete Radon-projection code used by RozoFS, operating XOR-only (GF(2) addition) over fixed-size byte blocks.

• CGO_ENABLED=0; the only dependency is golang.org/x/sys (CPU feature detection).
• Go 1.26.4 floor; builds for linux/{amd64,arm64,riscv64,ppc64le,s390x,loong64}, darwin/{amd64,arm64}, and windows/amd64.
• 100% test coverage, verified natively on amd64/arm64 and under QEMU for the other four SIMD targets.

SIMD XOR fast path

The hot kernel of both Encode and Reconstruct is a region XOR (dst[i] ^= src[i] over a block). It dispatches to a vectorised kernel generated by go-asmgen on all six 64-bit SIMD targets, falling back to the scalar loop elsewhere:

Arch	Instruction	Kernel width	Notes
amd64	VPXOR / PXOR	32 B / 16 B	AVX2 when present, else SSE2 (baseline)
arm64	VEOR (NEON)	16 B	NEON baseline
riscv64	VXORVV (RVV)	length-agnostic	dispatched when the V extension is present
ppc64le	VXOR (VSX)	16 B	POWER8 baseline (LXVD2X/STXVD2X)
s390x	VX (vector)	16 B	z13 vector facility
loong64	VXORV (LSX)	16 B	LSX baseline

The scalar loop remains the correctness oracle: a differential fuzzer and a size-sweep table test check every kernel's output byte-for-byte against it (empty, 1 byte, sub-block, exact and non-multiple block lengths, and large buffers). On an Apple M4 Max the arm64 NEON kernel runs the 1 MiB XOR at ~47 GB/s vs ~3.8 GB/s scalar (about 12×).

Kernels are regenerated with go run mojette_xor_<arch>_gen.go (the //go:build ignore generators); the committed mojette_xor_<arch>.s files are the output.

Model

Data is a Grid of Rows×Cols blocks in row-major order, each block BlockSize bytes. A Direction (P, Q) (with Q >= 1 and gcd(|P|, Q) == 1) defines a family of discrete lines. Its Projection has one bin block per line; each grid block is XOR-accumulated into the bin its cell falls on.

For cell (i, j) (row i ∈ [0, Rows), col j ∈ [0, Cols)) and direction (P, Q):

raw    = Q*i - P*j
minRaw = (P > 0) ? -P*(Cols-1) : 0
bin    = raw - minRaw                       // >= 0
nbins  = Q*(Rows-1) + |P|*(Cols-1) + 1

Encode does bins[bin(i,j)] ^= data[i*Cols+j] for every cell.

Reconstruction is the iterative inverse Mojette (corner / back-projection): repeatedly find a bin whose contributing cells are all known but one, assign that cell the bin's current value, XOR it back out of every projection, and repeat.

Because it is XOR-only, this is an erasure code for whole blocks (recover missing projections), not a general error-correcting code.

Katz criterion

Reconstructible(rows, cols, dirs) implements the Katz sufficiency criterion:

sum(Q_k) >= rows   OR   sum(|P_k|) >= cols

Katz is a sufficient geometric bound in the ideal Mojette setting; a particular subset of projections is guaranteed reconstructible when it holds. Reconstruct returns ErrNotReconstructible when the supplied projections do not actually suffice.

Example

package main

import (
	"fmt"

	"github.com/go-erasure/mojette"
)

func main() {
	// 4x3 grid of 2-byte blocks.
	g := &mojette.Grid{Rows: 4, Cols: 3, BlockSize: 2}
	for c := 0; c < g.Rows*g.Cols; c++ {
		g.Data = append(g.Data, []byte{byte(c), byte(c * 3)})
	}

	dirs := []mojette.Direction{{P: -1, Q: 1}, {P: 0, Q: 1}, {P: 1, Q: 1}, {P: 2, Q: 1}}
	projs, err := mojette.Encode(g, dirs)
	if err != nil {
		panic(err)
	}

	// Lose one projection; the remaining three still satisfy Katz (sum|P| >= Cols).
	subset := []mojette.Projection{projs[0], projs[2], projs[3]}

	out, err := mojette.Reconstruct(g.Rows, g.Cols, g.BlockSize, subset)
	if err != nil {
		panic(err)
	}
	fmt.Println(len(out.Data)) // 12 blocks recovered exactly
}

API

func Encode(g *Grid, dirs []Direction) ([]Projection, error)
func Reconstruct(rows, cols, blockSize int, projs []Projection) (*Grid, error)
func Reconstructible(rows, cols int, dirs []Direction) bool

License

BSD-3-Clause. See LICENSE.

Documentation

Overview

Package mojette implements the Mojette transform erasure code: the discrete Radon-projection code used by RozoFS, operating XOR-wise (GF(2) addition) over fixed-size byte blocks.

Data is arranged as a Grid of Rows*Cols blocks in row-major order, each block being BlockSize bytes. Each Direction (P, Q) yields one Projection built by summing (XOR-ing) grid blocks that fall onto the same discrete line. Given a Katz-sufficient subset of projections, the grid can be rebuilt with the iterative inverse Mojette (back-projection) algorithm.

Index

• Variables
• func Reconstructible(rows, cols int, dirs []Direction) bool
• type Direction
• type Grid
  • func Reconstruct(rows, cols, blockSize int, projs []Projection) (*Grid, error)
• type Projection
  • func Encode(g *Grid, dirs []Direction) ([]Projection, error)

Variables

var (
	// ErrInvalidGrid reports a grid (or reconstruction target) whose
	// dimensions or block sizes are inconsistent.
	ErrInvalidGrid = errors.New("mojette: invalid grid dimensions or block sizes")
	// ErrInvalidDirection reports a direction violating Q>=1 and gcd(|P|,Q)=1.
	ErrInvalidDirection = errors.New("mojette: direction requires Q>=1 and gcd(|P|,Q)=1")
	// ErrNotReconstructible reports that the supplied projections are not
	// sufficient to rebuild the grid.
	ErrNotReconstructible = errors.New("mojette: projections insufficient to reconstruct")
)

Functions

func Reconstructible

func Reconstructible(rows, cols int, dirs []Direction) bool

Reconstructible reports whether dirs satisfy the Katz criterion for a rows*cols grid:

sum(Q_k) >= rows  OR  sum(|P_k|) >= cols

Types

type Direction

type Direction struct{ P, Q int }

Direction is a Mojette projection direction (P, Q). It requires Q >= 1 and gcd(|P|, Q) == 1.

type Grid

type Grid struct {
	Rows, Cols int
	BlockSize  int
	Data       [][]byte // len == Rows*Cols, each block == BlockSize bytes
}

Grid holds Rows*Cols data blocks in row-major order, each block BlockSize bytes long.

func Reconstruct

func Reconstruct(rows, cols, blockSize int, projs []Projection) (*Grid, error)

Reconstruct rebuilds the rows*cols grid (blocks of blockSize) from a subset of projections using the iterative inverse Mojette (back-projection) over XOR. It returns ErrInvalidGrid for bad dimensions or mismatched projection bins, ErrInvalidDirection for a bad projection direction, and ErrNotReconstructible when the projections do not suffice.

type Projection

type Projection struct {
	Dir  Direction
	Bins [][]byte // len == nbins for Dir on the grid; each block BlockSize bytes
}

Projection is the Mojette projection of a grid along Dir. Bins has one block per discrete line; its length is the number of bins of Dir on the grid.

func Encode

func Encode(g *Grid, dirs []Direction) ([]Projection, error)

Encode computes one projection per direction. It returns ErrInvalidGrid for a malformed grid and ErrInvalidDirection for a direction that violates Q>=1 or gcd(|P|,Q)==1.