Documentation
¶
Overview ¶
Package ldc implements CCSDS Lossless Data Compression per CCSDS 121.0-B-3, the Rice adaptive entropy coder.
This is the most widely used CCSDS compression standard, and the shape of it is simple: decorrelate, then entropy code.
samples ──► preprocessor ──► adaptive entropy coder ──► coded data sets
Clause 4 clause 3 clause 5
The preprocessor subtracts a prediction from each sample and folds the signed residual onto the non-negative integers. The entropy coder then takes the residuals in blocks, prices every code option it has against the block, and writes the cheapest with an identifier saying which it chose. Nothing here is approximate: it is integer arithmetic throughout, and every step inverts exactly.
Using it ¶
p := ldc.DefaultParams() p.Resolution = 12 file, err := ldc.CompressFile(samples, p, 1) back, err := ldc.DecompressFile(file)
CompressFile writes the file format of section 7, whose header carries the parameters and the sample count. Compress and Decompress are the barer pair for callers who already share a configuration. A mission putting coded data sets straight into space packets, say, where clause 5.3 leaves the framing to the packetizer.
Choosing parameters ¶
Resolution must match the data. Everything else is a trade:
BlockSize smaller blocks adapt faster to changing statistics and
pay more identifier bits; 16 is a common choice
Predictor unit delay for correlated data, bypass for data already
decorrelated but signed, none for neither
ReferenceInterval how often an uncoded sample is inserted, bounding how
far a bit error can propagate
What is here and what is not ¶
All five code options are implemented, encoder and decoder: fundamental sequence, the split-sample family, second extension, zero block, and no compression. So are both predictors the standard specifies, the file format, and the restricted option set for four-bit and narrower samples.
Not here: the compression identification packet of section 6, insertion into space packets (clause 5.3, which the caller does), and the application-specific predictor and mapper the standard names but does not define. See docs/content/conformance/ldc.md.
Index ¶
- Constants
- Variables
- func Compress(samples []uint32, p Params) ([]byte, error)
- func CompressFile(samples []uint32, p Params, wordSize int) ([]byte, error)
- func Decompress(data []byte, p Params) ([]uint32, error)
- func DecompressCount(data []byte, p Params, count int) ([]uint32, error)
- func DecompressFile(data []byte) ([]uint32, error)
- func FileBody(data []byte) ([]byte, error)
- func Preprocess(samples []uint32, p Params) []uint32
- func Unpreprocess(mapped []uint32, references map[int]uint32, p Params) []uint32
- type BitReader
- type BitWriter
- type BlockInfo
- type FileHeader
- type Option
- type Params
- type Predictor
Constants ¶
const FileHeaderSize = 12
FileHeaderSize is the fixed width of the file header, per clause 7.2.2.
Variables ¶
var ( // ErrDataTooShort indicates the input ended before a field it must contain. ErrDataTooShort = errors.New("data too short: the coded bit stream ended early") // ErrInvalidBlockSize indicates a block size outside the four CCSDS // 121.0-B-3 clause 3.1.6 allows. ErrInvalidBlockSize = errors.New("invalid block size: must be 8, 16, 32 or 64 samples") // ErrInvalidResolution indicates a sample resolution outside 1 to 32 bits, // per CCSDS 121.0-B-3 clause 3.1.6. ErrInvalidResolution = errors.New("invalid sample resolution: must be 1 to 32 bits") // ErrInvalidReferenceInterval indicates a reference sample interval outside // 1 to 4096 blocks, per CCSDS 121.0-B-3 clause 4.3. ErrInvalidReferenceInterval = errors.New("invalid reference sample interval: must be 1 to 4096 blocks") // ErrRestrictedNotAllowed indicates the restricted code option set at a // resolution above 4 bits. CCSDS 121.0-B-3 clause 5.2.1.1 allows it only when // n <= 4. ErrRestrictedNotAllowed = errors.New("the restricted code option set requires a resolution of 4 bits or fewer") // ErrSampleOutOfRange indicates a sample that does not fit the configured // resolution. ErrSampleOutOfRange = errors.New("sample does not fit the configured resolution") // ErrInvalidOptionID indicates an option identifier the code option table // of CCSDS 121.0-B-3 clause 5.2 does not define at this resolution. ErrInvalidOptionID = errors.New("invalid code option identifier") // ErrInvalidWordSize indicates an output word size outside 1 to 8 octets, // per CCSDS 121.0-B-3 clause 7.2.1.2. ErrInvalidWordSize = errors.New("invalid output word size: must be 1 to 8 octets") // ErrTruncatedFile indicates a compressed file shorter than its 12-octet // header. ErrTruncatedFile = errors.New("compressed file is shorter than its header") // ErrReservedFieldSet indicates a reserved header field that is not zero, // which CCSDS 121.0-B-3 table 7-1 requires it to be. ErrReservedFieldSet = errors.New("a reserved header field is not zero") // ErrUnsupportedPredictor indicates a predictor type this package does not // implement, such as the application-specific one. ErrUnsupportedPredictor = errors.New("unsupported predictor type") // ErrUnsupportedMapper indicates a mapper type this package does not // implement. ErrUnsupportedMapper = errors.New("unsupported mapper type") // ErrTooManySamples indicates a sample count past what the file header's // 48-bit field can hold. ErrTooManySamples = errors.New("too many samples for the file header") // ErrSampleCountMismatch indicates a coded stream that did not yield the // number of samples its header promised. ErrSampleCountMismatch = errors.New("the coded data did not yield the promised number of samples") )
Sentinel errors returned by the compressor and decompressor.
Functions ¶
func Compress ¶
Compress codes samples into a coded data set stream.
The output is the concatenation of coded data sets with zero fill to the next octet, which is the file body of clause 7.2.3. It does not carry the parameters: Decompress needs the same Params, and CompressFile is the self-describing form.
func CompressFile ¶
CompressFile codes samples into the self-describing file format of section 7: a twelve-octet header, the coded data sets, then zero fill to the next output word boundary.
wordSize is B in octets, 1 to 8. Pass 1 for no padding beyond the octet.
func Decompress ¶
Decompress reads a coded data set stream back into samples.
It decodes until the input is exhausted, treating a trailing run of fewer than eight zero bits as the fill of clause 7.2.3.2. That works because fill is always zeros and every coded data set needs a one bit to terminate its first codeword, so fill can never be mistaken for another set.
The eight-bit bound is deliberate, and it is a limitation: a file written with an output word size B above one octet (clause 7.2.1.2) may carry up to 8B-1 bits of zero fill, and Decompress cannot tell such a tail from a truncated coded data set. It returns an error rather than guessing. That is the safe failure: only a decode that knows the sample count can skip longer fill, which is what DecompressCount and DecompressFile do.
It also cannot recover a partial final block, because nothing in the stream says the block was short. Use DecompressCount or DecompressFile when the sample count is not a whole number of blocks.
func DecompressCount ¶
DecompressCount reads exactly count samples, which allows a partial final block.
func DecompressFile ¶
DecompressFile reads a file written by CompressFile, taking every parameter from its header.
func Preprocess ¶
Preprocess turns input samples into the non-negative values the entropy coder takes.
blockSize and referenceInterval decide where reference samples fall: the first sample of every reference interval is a reference, and clause 4.2.5 gives it a predicted value equal to itself, so its prediction error is zero. The returned slice has one entry per input sample; the reference positions hold zero and the caller emits the raw sample instead.
Types ¶
type BitReader ¶
type BitReader struct {
// contains filtered or unexported fields
}
BitReader reads MSB first and reports exhaustion rather than panicking.
func NewBitReader ¶
NewBitReader prepares a reader over data.
func (*BitReader) Align ¶
func (r *BitReader) Align()
Align advances to the next octet boundary, discarding fill bits.
func (*BitReader) ReadBits ¶
ReadBits reads the next n bits as an unsigned value, most significant first.
n must be 0 to 64. Running out of input is ErrDataTooShort, never a panic: this reader is the only thing standing between a hostile compressed stream and the decoder.
func (*BitReader) ReadFS ¶
ReadFS reads one fundamental-sequence codeword and returns the value it encodes: the number of zeros before the terminating one.
Table 3-1 makes an FS codeword m zeros followed by a one, so decoding is just counting zeros. limit caps how many zeros are tolerated before the stream is called malformed. Without it, a run of zero octets would be read as an enormous sample value and the caller would allocate on it.
type BitWriter ¶
type BitWriter struct {
// contains filtered or unexported fields
}
BitWriter packs values MSB first into a growing octet slice.
The zero value is ready to use.
func (*BitWriter) Bytes ¶
Bytes returns the written bits, padding the last octet with zero fill.
Clause 7.2.3.2 requires fill bits to be zeros. This pads only to the next octet; padding to the output word size is the file writer's job, because only it knows B.
func (*BitWriter) WriteBits ¶
WriteBits appends the low n bits of v, most significant first.
n must be 0 to 64. Bits above the low n of v are ignored.
func (*BitWriter) WriteZeros ¶
WriteZeros appends n zero bits. It is what an FS codeword is mostly made of, and writing them a run at a time avoids looping per bit at the caller.
type BlockInfo ¶
type BlockInfo struct {
// Block is the index of the first block this coded data set covers.
Block int
// Option is the coding option used.
Option Option
// K is the split-sample parameter, meaningful only for OptionSplitSample.
K int
// ZeroRun is how many blocks a zero-block set covers, 1 for every other
// option.
ZeroRun int
// IsROS says a zero-block set used the remainder-of-segment codeword.
IsROS bool
// Bits is the coded length of the whole set, identifier included.
Bits int
// HasReference says the set carries an uncoded reference sample.
HasReference bool
}
BlockInfo describes one coded data set as the decoder found it.
This is what makes a compressed stream inspectable: which option won each block, and how many bits it cost. Useful for checking a mission's parameter choices against real data, and for the tests that pin option selection.
type FileHeader ¶
type FileHeader struct {
// WordSize is B, the output word size in octets, 1 to 8. The file is
// padded to a multiple of it (clause 7.2.1.2, clause 7.2.3.2).
WordSize int
// Params are the compression parameters the body was coded with.
Params Params
// SampleCount is N, the number of samples the body holds.
SampleCount uint64
}
FileHeader is the twelve-octet header of table 7-1.
func DecodeFileHeader ¶
func DecodeFileHeader(data []byte) (FileHeader, error)
DecodeFileHeader parses a file header.
func (FileHeader) Encode ¶
func (h FileHeader) Encode() ([]byte, error)
Encode serializes the header.
func (FileHeader) Humanize ¶
func (h FileHeader) Humanize() string
Humanize returns a human-readable summary.
type Option ¶
type Option int
Option names a code option.
const ( // OptionZeroBlock encodes a run of all-zero blocks, clause 3.5. OptionZeroBlock Option = iota // OptionSecondExtension pairs samples before coding them, clause 3.4. OptionSecondExtension // OptionSplitSample is the family of split-sample options, clause 3.3. The FS // option of clause 3.2 is the member with k=0. OptionSplitSample // OptionNoCompression sends the block unaltered, clause 3.6. OptionNoCompression )
type Params ¶
type Params struct {
// BlockSize is J, the number of samples the coder treats as one block.
// Clause 3.1.6 allows 8, 16, 32 and 64.
BlockSize int
// Resolution is n, the number of bits per input sample, 1 to 32 (clause 3.1.6).
Resolution uint
// Signed says whether samples are two's complement. Clause 4.4 gives the sample
// range either as [-2^(n-1), 2^(n-1)-1] or [0, 2^n-1], and the mapper
// needs to know which.
//
// Table 7-1's Data Sense field requires this to be false when the
// preprocessor is absent or bypassed.
Signed bool
// Predictor selects the preprocessing, per section 4.
Predictor Predictor
// ReferenceInterval is r, the number of blocks between reference samples,
// 1 to 4096 (clause 4.3).
//
// It matters even without reference samples: Clause 3.5.2 uses it to bound the
// segments the zero-block option counts within.
ReferenceInterval int
// Restricted selects the restricted set of code options. Clause 5.2.1.1 allows
// it only when the resolution is 4 bits or fewer, where it buys shorter
// option identifiers at the cost of dropping most of the split-sample
// options.
Restricted bool
}
Params holds the compression parameters CCSDS 121.0-B-3 leaves to the user.
None of these travel with a coded data set, so a decoder must be told them. That is why the standard defines a file header (clause 7.2.2) and an optional compression identification packet (clause 6): both exist to carry this struct's worth of information alongside the data.
func DefaultParams ¶
func DefaultParams() Params
DefaultParams returns a workable starting point: 8-bit unsigned samples, blocks of 16, unit-delay prediction, a reference every 256 blocks.
type Predictor ¶
type Predictor int
Predictor says how the preprocessor predicts each sample.
const ( // PredictorNone means no preprocessor at all: samples go to the entropy // coder as they are. Clause 4.1 allows this when the data is already suitable. PredictorNone Predictor = iota // PredictorUnitDelay predicts each sample from the one before, per clause 4.2.5. // This is the only predictor the standard specifies. PredictorUnitDelay // PredictorBypass predicts zero and keeps the mapper, per clause 4.2.3. PredictorBypass )
func (Predictor) NeedsReferenceSamples ¶
NeedsReferenceSamples reports whether the decoder needs uncoded reference samples to invert the preprocessing.
Clause 4.2.6: reference samples are required "when, and only when, a Unit-Delay Predictor or other higher-order predictor that bases its predictions on previous sample values is used. Otherwise, reference samples shall not be employed." So the bypass predictor, which looks at nothing, needs none.
Source Files