Reed-Solomon erasure codec over GF(2^8). More...

#include <stdlib.h>
#include <string.h>
#include "reed_solomon.h"
#include "gf256.h"

Data Structures
struct	rs_context

Functions
static uint8_t *	build_vandermonde (uint16_t K, uint16_t M)
	Build a Vandermonde matrix (K+M) x K in GF(2^8).
static int	invert_matrix (const uint8_t mat, uint8_t inv, uint16_t K)
	Invert a K x K matrix in-place using Gaussian elimination over GF(2^8).
rs_context *	rs_create (uint16_t K, uint16_t M)
	Create a Reed-Solomon codec for RS(K, M) over GF(2^8).
void	rs_free (rs_context *ctx)
	Free a Reed-Solomon codec context.
uint8_t	rs_get_coefficient (const rs_context *ctx, uint16_t m, uint16_t k)
	Get the generator matrix coefficient for parity shard m, data shard k.
void	rs_encode_incremental (uint8_t coeff, const uint8_t data, uint8_t parity, size_t shard_size)
	Incrementally accumulate one data shard's contribution to one parity shard.
int	rs_decode (const rs_context ctx, uint8_t shards, const uint8_t present, size_t shard_size)
	Decode (reconstruct) erased shards.

Detailed Description

Reed-Solomon erasure codec over GF(2^8).

Implements RS(K, M) encoding and decoding using a Vandermonde-derived generator matrix. Encoding is incremental (one data shard at a time). Decoding uses Gaussian elimination to reconstruct erased shards.

The coding matrix is (K+M) x K where:

Top K rows form an identity matrix (data shards pass through unchanged)
Bottom M rows are the generator matrix (parity = G * data)

Generator matrix construction: Start with a (K+M) x K Vandermonde matrix V where V[i][j] = i^j in GF(2^8). Invert the top K x K submatrix and multiply the entire matrix by the inverse so that the top K rows become identity. The bottom M rows are the generator.

Definition in file reed_solomon.c.

Function Documentation

◆ build_vandermonde()

uint8_t * build_vandermonde	(	uint16_t	K,
		uint16_t	M )

static

Build a Vandermonde matrix (K+M) x K in GF(2^8).

V[i][j] = i^j in GF(2^8), where i is the row index and j is the column index. Row 0 is all zeros except column 0 (since 0^0 = 1 by convention, 0^j = 0 for j>0). We use row indices 0..K+M-1.

Definition at line 58 of file reed_solomon.c.

References build_vandermonde(), and gf256_mul().

Referenced by build_vandermonde(), and rs_create().

◆ invert_matrix()

int invert_matrix	(	const uint8_t *	mat,
		uint8_t *	inv,
		uint16_t	K )

static

Invert a K x K matrix in-place using Gaussian elimination over GF(2^8).

Parameters

mat	The matrix to invert, stored row-major in K*K bytes.
inv	Output inverse matrix (must be pre-initialized to identity).
K	Matrix dimension.

Returns: 0 on success, -1 if singular.

Definition at line 84 of file reed_solomon.c.

References gf256_inv(), gf256_mul(), and invert_matrix().

Referenced by invert_matrix(), rs_create(), and rs_decode().

◆ rs_create()

rs_context * rs_create	(	uint16_t	K,
		uint16_t	M )

Create a Reed-Solomon codec for RS(K, M) over GF(2^8).

K = number of data shards, M = number of parity shards. K + M must be <= 255 (GF(2^8) field size minus 1).

The codec precomputes the Vandermonde-derived generator matrix (M rows x K columns) used for encoding.

Parameters

K	Number of data shards (>= 1).
M	Number of parity shards (>= 1).

Returns: Codec context, or NULL on error.

Definition at line 150 of file reed_solomon.c.

References build_vandermonde(), rs_context::coding, rs_context::gen, gf256_mul(), invert_matrix(), rs_context::K, rs_context::M, and rs_create().

Referenced by aaruf_set_erasure_coding(), ec_load_ecmb(), ec_recover_raw_block(), ec_write_batch_parity(), and rs_create().

◆ rs_decode()

int rs_decode	(	const rs_context *	ctx,
		uint8_t **	shards,
		const uint8_t *	present,
		size_t	shard_size )

Decode (reconstruct) erased shards.

Given K+M shards where some are erased, reconstruct the erased ones using Gaussian elimination over GF(2^8).

Parameters

ctx	Codec context.
shards	Array of K+M shard pointers (each shard_size bytes). Erased shards must point to allocated buffers of shard_size bytes (content will be overwritten).
present	Boolean array of K+M entries: 1 = shard is valid, 0 = shard is erased.
shard_size	Number of bytes per shard.

Returns: 0 on success, -1 if too many erasures (> M), -2 on allocation failure.

Definition at line 218 of file reed_solomon.c.

References rs_context::coding, gf256_mul(), gf256_mul_region(), invert_matrix(), rs_context::K, rs_context::M, and rs_decode().

Referenced by ec_recover_data_block(), ec_recover_raw_block(), and rs_decode().

◆ rs_encode_incremental()

void rs_encode_incremental	(	uint8_t	coeff,
		const uint8_t *	data,
		uint8_t *	parity,
		size_t	shard_size )

Incrementally accumulate one data shard's contribution to one parity shard.

Computes: parity[i] ^= GF_mul(data[i], coeff) for all i in [0, shard_size).

This is the core primitive for streaming write: for each data block written, call this M times (once per parity shard) with the appropriate coefficient.

For M=1 (XOR-only), coeff is always 1, and this reduces to XOR.

Parameters

coeff	GF(2^8) coefficient from rs_get_coefficient().
data	Data shard bytes (read-only, shard_size bytes).
parity	Parity shard accumulator (read-write, shard_size bytes, must be zeroed before first call).
shard_size	Number of bytes per shard.

Definition at line 213 of file reed_solomon.c.

References gf256_mul_region(), and rs_encode_incremental().

Referenced by ec_accumulate_data_block(), ec_write_batch_parity(), and rs_encode_incremental().