rs

README

Reed-Solomon ECC in Go

Implements error correcting codes using Russ Cox's rsc.io/qr/gf256 library.

It doesn't implement interleaved data, the data is assumed to be external to the content.

Documentation

Overview

Package rs implements Reed-Solomon error correcting codes.

The code was inspired by ZXing's Java implementation but was reduced to only support 256 values space. Source: https://github.com/zxing/zxing

Much credit is due to Sean Owen, William Rucklidge since portions of this code are an indirect port of their Java or C++ Reed-Solomon implementations.

Parts of ZXing's implementation have been replaced by Russ Cox's gf256 library https://rsc.io/qr/gf256.

Index

• Variables
• type Decoder
  • func NewDecoder(f *Field) Decoder
• type Encoder
  • func NewEncoder(f *Field, c int) Encoder
• type Field
  • func NewField(poly int, α byte) *Field
• Bugs

Examples

• NewDecoder
• NewEncoder

Variables

var QRCodeField256 = NewField(0x11D, 2)

QRCodeField256 the Galois Field for QR codes. See http://research.swtch.com/field for more information.

x^8 + x^4 + x^3 + x^2 + 1

Types

type Decoder

type Decoder interface {
	// Decodes given set of received codewords, which include both data and
	// error-correction codewords. Really, this means it uses Reed-Solomon to
	// detect and correct errors, in-place, in the input.
	//
	// Returns the number of errors corrected or an error if decoding failed.
	Decode(data, ecc []byte) (int, error)
}

Decoder can error correct data with the corresponding ECC codes.

func NewDecoder

func NewDecoder(f *Field) Decoder

NewDecoder creates a decoder in the defined field.

Example

package main

import (
	"fmt"

	"github.com/maruel/rs"
)

func main() {
	data := []byte("hello, wXrld")
	ecc := []byte{171, 167}
	fmt.Printf("Corrupted data: %s\n", data)
	d := rs.NewDecoder(rs.QRCodeField256)
	if nb, err := d.Decode(data, ecc); err != nil || nb != 1 {
		fmt.Printf("Expected 1 fix, for %d. Error: %s\n", nb, err)
	}
	fmt.Printf("Fixed data: %s\n", data)
}

Output:

Corrupted data: hello, wXrld
Fixed data: hello, world

type Encoder

type Encoder interface {
	// Encode calculates the ECC code for data and writes it into ecc.
	Encode(data []byte, ecc []byte)
}

Encoder can encode data into ecc codes.

func NewEncoder

func NewEncoder(f *Field, c int) Encoder

NewEncoder generates a Reed-Solomon encoder that can generate ECC codes.

Example

package main

import (
	"fmt"

	"github.com/maruel/rs"
)

func main() {
	data := []byte("hello, world")
	fmt.Printf("Original data: %s\n", data)
	ecc := make([]byte, 2)
	e := rs.NewEncoder(rs.QRCodeField256, len(ecc))
	e.Encode(data, ecc)
	fmt.Printf("ECC bytes: %v\n", ecc)
}

Output:

Original data: hello, world
ECC bytes: [171 167]

type Field

type Field struct {
	// contains filtered or unexported fields
}

Field is a wrapper to gf256.Field so the type doesn't leak in.

func NewField

func NewField(poly int, α byte) *Field

NewField wraps gf256.NewField(). It is safe to use the premade QRCodeField256 all the time.

Notes

Bugs

• It's far from complete. It can't accept total buffer size of more than 255 bytes. So len(data)+len(ecc) must be under 256 bytes.