README
¶
crcutil
When communicating with hardware devices like integrated circuits, often CRC sums need to be calculated with polynomials of orders lower than 32, like 3, 4, 6, 8 or 16. Sometimes the so-called reflected form of algorithms has to be used on the wire, sometimes the normal form — or even both forms in the same protocol; in some cases obscure additional reflections need to be performed.
As the Go standard library offers no support for these smaller widths of CRCs — also its crc32 implementation implements solely the commonly used reflected form of the algorithm, and does not provide a generic way to specify initial values or final XORing —, this module tries to provide that functionality in a generic way.
Using the type Poly, a polynomial may be specified by its word value and bit width,
and whether the word refers to the normal, reflected, or a reciprocal representation.
A value of type Poly may be converted to other representations, e.g. from normal to reflected form, using the corresponding method.
From a Poly, a lookup table may be created that may be used directly, if the amount of data is very small, like e.g. in case of a CRC-3.
A Model specifies a CRC algorithm: the polynomial,
the initial value (resp. optional initial inversion) to be used,
and whether a final operation like inversion (XORing) shall be applied. From a static Model,
an Inst may be created that allows to calculate a checksum over an amount of data.
There exist sub-packages poly{n} and crc{n}
that provide concrete versions of the generic Poly and Model types for some common values of bit widths and word types.
One example for a predefined Model is crc8.SAEJ1850, which uses poly8.SAEJ1850 with initial and final bitwise inversion. Another example is crc16.Modbus, based on the reversed form of poly16.IBM.
Example
As a real example, the LED driver circuit Infineon TLD7002-16ES uses both a CRC-3 in reflected form and a CRC-8 (SAEJ1850) in normal form in the same serial protocol.
CRC-3
The CRC-3 polynomial x³ + x¹ + 1 (GSM, value = 0b11 = 3) can be created in the following equivalent ways:
p := poly3.GSM // using predefined polynomial
p := poly3.New(0b11) // 0b11 = 2¹ + 2°
p := &poly8.Poly{Word: 0b11, Width: 3}
p := &Poly[uint8]{Word: 0b11, Width: 3} // using the generic type
Since the 3-bit polynomial can be represented by an 8-bit value,
the poly3 internally uses poly8.Poly,
like shown in the third line above.
If we wanted to create a lookup table for five bits of data, with an initial value of 5 — as defined by the specification — encoded into the table, we could write
p := poly3.GSM.ReversedForm()
tab := p.MakeTable(crcutil.WithInitialValue(5), crcutil.WithDataWidth(5))
To get the CRC-sum of a 5-bit value of 13 it would be sufficient to
evaluate tab[13].
For more details see the example for func (*Poly[T]) MakeTable() in the documentation.
CRC-8-SAE-J1850
To calculate a checksum over some bytes using the SAE-J1850 polynomial x⁸ + x⁴ + x³ + x² + 1, follow this example (compare the result the one listed at AUTOSAR Specification of CRC Routines, p.24):
// create an instance
crc := crc8.SAEJ1850.New()
// insert some bytes
crc.Write([]byte{0xF2, 0x01, 0x83})
fmt.Printf("0x02x\n", crc.Sum())
// => 0x37
Implicit +1 notation
Functions FromImplicit1Notation and FromImplicit1NotationReciprocal
create a Poly from a polynomial word in Koopman's implicit +1 notation,
which may be helpful when using polynomials with specific Hamming Distance
properties from the tables provided by Philip Koopman.
hash.Hash interface
For an implementation aligned with Go's hash.Hash interface, see github.com/knieriem/hash, which is a thin wrapper
around crcutil.
Documentation
¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BitwiseUpdateFn ¶
BitwiseUpdateFn returns a function that returns the result of adding the bits defined by data and dataWidth into the crc. The actual function returned depends on the polynomial's representation (normal or reversed form).
func UpdateBitwise ¶
Types ¶
type Inst ¶
type Inst[T Word] struct { // contains filtered or unexported fields }
Inst is an instance of a Model; it contains the current state of the crc calculation. current state of
func (*Inst[T]) AppendSum ¶
AppendSum appends the crc checksum to the provided slice and returns the resulting slice. If AppendSumXORed is set, it will apply, if specified, the final inversion or final xor value before appending the checksum, otherwise this step will be skipped. Calling AppendSum does not change the instance's current state.
func (*Inst[T]) Reset ¶
func (inst *Inst[T]) Reset()
Reset sets the instance back to its initial state.
func (*Inst[T]) Sum ¶
func (inst *Inst[T]) Sum() T
Sum returns the crc checksum; it does not change the current state.
type InstOption ¶
type InstOption func(*instConf)
func AppendSumSkipFinalXOR ¶
func AppendSumSkipFinalXOR() InstOption
AppendSumSkipFinalXOR ensures that when calling AppendSum the final inversion or xor-ing will be skipped.
func WithSwappedInputNibbles ¶ added in v0.2.0
func WithSwappedInputNibbles() InstOption
WithSwappedInputNibbles ensures that bytes are processed with upper and lower nibbles swapped. This option is useful for 4-bit CRCs, when an LSBit-first implementation is used, and the input bytes shall be processed with high nibble first.
type Model ¶
type Model[T Word] struct { Poly *Poly[T] // Table may be assigned an alternative table to be used for // calculation. On default, MakeTable derives a table from Poly. Table []T // Initial is the start value to be used for crc calculation. // If left empty, zero will be used. Initial T // InitialInvert may be set to true, if the initial value shall // be inverted. If Initial is left empty, setting InitialInvert // has the effect of an initial value with all bits set. InitialInvert bool // FinalInvert may be set to true, if a crc value shall // be inverted before being returned as checksum. // Alternatively, FinalXOR could be set to a value with all bits set // for the same effect. FinalInvert bool // FinalXOR may contain a value to be XORed into the crc value // before returning the checksum. In most cases leaving FinalXOR // empty, and setting FinalInvert instead will suffice, as cases // where the final step isn't either a no-op or an inversion, // but an XOR-operation with a specific value seem rare. FinalXOR T }
Model defines how a concrete CRC calculation should be performed, based on a polynomial, and parameters. To calculate a crc value, an instance needs to be created using New, followed by calls to methods Write or Update, and if appropriate, Reset.
A Model may also be used to create a hash.Hash using packages github.com/knieriem/hash/crc8 or packages github.com/knieriem/hash/crc16.
Example ¶
This example calculates a Modbus crc over an example frame; see “MODBUS over serial line specification and implementation guide V1.02”, p. 41
package main
import (
"fmt"
"github.com/knieriem/crcutil"
"github.com/knieriem/crcutil/crc16"
"github.com/knieriem/crcutil/poly16"
)
var (
ibmcrc = &crcutil.Model[uint16]{
Poly: poly16.IBM.ReversedForm(),
InitialInvert: true,
}
)
// This example calculates a Modbus crc over an example frame;
// see “MODBUS over serial line specification and implementation guide V1.02”, p. 41
func main() {
inst := ibmcrc.New()
inst.Update([]byte{2, 7})
fmt.Printf("%#04x\n", inst.Sum())
// Alternatively, use a predefined model:
sum := crc16.Modbus.Checksum([]byte{2, 7})
fmt.Printf("%#04x", sum)
}
Output: 0x1241 0x1241
func (*Model[T]) Checksum ¶
Checksum returns the CRC checksum calculated over the bytes in the data slice.
func (*Model[T]) MakeTable ¶
func (m *Model[T]) MakeTable() []T
MakeTable returns the lookup table stored in the Table field. If this field is nil, a table generated by Poly.MakeTable() will be returned.
func (*Model[T]) New ¶
func (m *Model[T]) New(opts ...InstOption) *Inst[T]
NewInst returns a new instance of the Model.
type Poly ¶
Poly defines a polynomial in a specific representation.
Example ¶
This example calculates representations of the CCITT-16 polynomial as shown in https://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks#Polynomial_representations
package main
import (
"fmt"
"github.com/knieriem/crcutil"
"github.com/knieriem/crcutil/poly16"
)
var ccitt16 = poly16.CCITT
// This example calculates representations of the CCITT-16
// polynomial as shown in
// https://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks#Polynomial_representations
func main() {
reversed := ccitt16.ReversedForm()
formatPoly("reversed", reversed)
formatPoly("reciprocal", ccitt16.ReciprocalForm())
formatPoly("reversed reciprocal", reversed.ReciprocalForm())
}
func formatPoly[T crcutil.Word](variant string, poly *crcutil.Poly[T]) {
fmt.Printf("%#04x\t%s\n", poly.Word, variant)
}
Output: 0x8408 reversed 0x0811 reciprocal 0x8810 reversed reciprocal
func FromImplicit1Notation ¶
FromImplicit1Notation returns a Poly with the word k converted from Koopman's implicit +1 notation to the explicit +1 notation used within this module. An advantage of the implicit +1 notation is that the bit width of the polynomial can be derived from the word value.
Notation examples:
implicit +1: 1*x^3 + 0*x^2 + 1*x^1 + (1*x^0) = 0b 1 01(1) => 0x5 explicit +1: (1*x^3) + 0*x^2 + 1*x^1 + 1*x^0 = 0b(1)01 1 => 0x3
See https://users.ece.cmu.edu/~koopman/crc/notes.html for details.
Note that the implicit +1 notation is only a different way to write the polynomial word, but there is no algorithmic difference calculating the CRC. A word in implicit +1 notation looks identical to the word value of a Poly refering to the same polynomial, but converted to reverse reciprocal form.
Example ¶
package main
import (
"fmt"
"github.com/knieriem/crcutil"
)
func main() {
p := crcutil.FromImplicit1Notation(uint32(0x19d17))
fmt.Printf("%#05x %d", p.Word, p.Width)
}
Output: 0x13a2f 17
func FromImplicit1NotationReciprocal ¶
FromImplicit1NotationReciprocal is like FromImplicit1Notation but returns a Poly with the Reciprocal flag set.
Note: A word in implicit +1 notation looks identical to the word value of a Poly refering to the same polynomial, but converted to reverse form.
Example ¶
package main
import (
"fmt"
"github.com/knieriem/crcutil"
)
func main() {
p := crcutil.FromImplicit1NotationReciprocal(uint32(0x1e8b9)).NormalForm()
fmt.Printf("%#05x %d", p.Word, p.Width)
}
Output: 0x13a2f 17
func (*Poly[T]) LSBitFirst ¶
LSBitFirst reports whether the polynomial's representation is lsbit-first.
func (*Poly[T]) MakeTable ¶
func (poly *Poly[T]) MakeTable(opts ...TableOption) []T
MakeTable creates a lookup table for the specified polynomial. The size of the table returned equals the length of the value range determined by the number of data bits.
Example ¶
package main
import (
"fmt"
"github.com/knieriem/crcutil"
"github.com/knieriem/crcutil/poly3"
)
// This example shows how to calculate a 3-bit CRC over
// 13 bits of data from two bytes of a frame of a serial
// communication protocol:
//
// byte 0: crc (3 bits) | device address (5 bits)
// byte 1: function code + length (8 bits)
//
// A specific algorithm will be used: 3-bit polynomial 0x3 (GSM),
// in reversed form. With an initial value of 5, the crc is calculated first
// over the five bits of the first byte, then the 8 bits of the second byte.
// After adding the 8 bit value, the crc result shall be mirrored (reflected).
// We will create
// - one table for the 5 bit lookup, which already
// regards for the initial value, and
// - one table for the 8 bit lookup, which produces a reflected result.
type crcTabs struct {
t1 []uint8
t2 []uint8
}
var crc3 crcTabs
func init() {
poly := poly3.GSM.ReversedForm()
initialValue := crcutil.WithInitialValue(5)
fiveBits := crcutil.WithDataWidth(5)
crc3.t1 = poly.MakeTable(initialValue, fiveBits)
crc3.t2 = poly.MakeTable(crcutil.WithReversedBits())
}
// Then we can calculate the checksum by performing
// a table lookup first for the 5-bit data part, XOR-ing the result
// with the 8-bit data part, and doing a lookup of this value with
// the other table.
func (tabs *crcTabs) checksum(v1, v2 uint8) uint8 {
crc := tabs.t1[v1]
return tabs.t2[crc^v2]
}
// With the 5-bit device address being 10, and a value of the second
// byte of 0b0111_0101, the checksum should be 4.
func main() {
sum := crc3.checksum(10, 0b0111_0101)
fmt.Println(sum)
}
Output: 4
func (*Poly[T]) NormalForm ¶
NormalForm returns the normal form of the polynomial.
Example ¶
This example calculates the normal representation of the x^16 + x^15 + x^2 + 1 polynomial back from its reversed and reversed reciprocal representations.
package main
import (
"fmt"
"github.com/knieriem/crcutil/poly16"
)
func main() {
r := &poly16.Poly{Word: 0x8408, Width: poly16.N, Reversed: true}
rr := &poly16.Poly{Word: 0x8810, Width: poly16.N, Reversed: true, Reciprocal: true}
fmt.Printf("%#04x %#04x", r.NormalForm().Word, rr.NormalForm().Word)
}
Output: 0x1021 0x1021
func (*Poly[T]) ReciprocalForm ¶
ReciprocalForm returns the reciprocal form of the polynomial that can be obtained by mirroring its coefficients. It returns the unchanged polynomial if it is already in its reciprocal form.
func (*Poly[T]) ReversedForm ¶
ReversedForm returns the reversed, lsbit-first form of the polynomial. It returns the unchanged polynomial if it is already in its reversed form.
type TableOption ¶
type TableOption func(*tableConf)
func WithDataWidth ¶
func WithDataWidth(n int) TableOption
WithDataWidth sets the data width to n bits, which will result in a table of 2^n entries for n-bit-wise processing. The default width is 8 bits for byte-wise processing.
func WithInitialValue ¶
func WithInitialValue(initial uint32) TableOption
WithInitialValue ensures that when a table is created the specified initial value will be applied to the calculation of each table entry. In cases where a table later is used manually, like when a CRC is calulated over some bits only, this saves one XOR operation.
func WithReversedBits ¶
func WithReversedBits() TableOption
WithReversedBits table option mirrors the bits of each table entry.
Source Files
Directories