Documentation ¶
Overview ¶
Package prefix implements bit readers and writers that use prefix encoding.
Index ¶
- func GenerateLengths(codes PrefixCodes, maxBits uint) error
- func GeneratePrefixes(codes PrefixCodes) error
- type Decoder
- type Encoder
- type PrefixCode
- type PrefixCodes
- type RangeCode
- type RangeCodes
- type RangeEncoder
- type Reader
- func (pr *Reader) BitsRead() int64
- func (pr *Reader) Flush() (int64, error)
- func (pr *Reader) Init(r io.Reader, bigEndian bool)
- func (pr *Reader) IsBufferedReader() bool
- func (pr *Reader) PullBits(nb uint) error
- func (pr *Reader) Read(buf []byte) (cnt int, err error)
- func (pr *Reader) ReadBits(nb uint) uint
- func (pr *Reader) ReadOffset(pd *Decoder, rcs RangeCodes) uint
- func (pr *Reader) ReadPads() uint
- func (pr *Reader) ReadSymbol(pd *Decoder) uint
- func (pr *Reader) TryReadBits(nb uint) (uint, bool)
- func (pr *Reader) TryReadSymbol(pd *Decoder) (uint, bool)
- type Writer
- func (pw *Writer) BitsWritten() int64
- func (pw *Writer) Flush() (int64, error)
- func (pw *Writer) Init(w io.Writer, bigEndian bool)
- func (pw *Writer) PushBits() (uint, error)
- func (pw *Writer) TryWriteBits(v, nb uint) bool
- func (pw *Writer) TryWriteSymbol(sym uint, pe *Encoder) bool
- func (pw *Writer) Write(buf []byte) (cnt int, err error)
- func (pw *Writer) WriteBits(v, nb uint)
- func (pw *Writer) WriteOffset(ofs uint, pe *Encoder, re *RangeEncoder)
- func (pw *Writer) WritePads(v uint)
- func (pw *Writer) WriteSymbol(sym uint, pe *Encoder)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func GenerateLengths ¶
func GenerateLengths(codes PrefixCodes, maxBits uint) error
GenerateLengths assigns non-zero bit-lengths to all codes. Codes with high frequency counts will be assigned shorter codes to reduce bit entropy. This function is used primarily by compressors.
The input codes must have the Cnt field populated, be sorted by count. Even if a code has a count of 0, a non-zero bit-length will be assigned.
The result will have the Len field populated. The algorithm used guarantees that Len <= maxBits and that it is a complete prefix tree. The resulting codes will remain sorted by count.
func GeneratePrefixes ¶
func GeneratePrefixes(codes PrefixCodes) error
GeneratePrefixes assigns a prefix value to all codes according to the bit-lengths. This function is used by both compressors and decompressors.
The input codes must have the Sym and Len fields populated and be sorted by symbol. The bit-lengths of each code must be properly allocated, such that it forms a complete tree.
The result will have the Val field populated and will produce a canonical prefix tree. The resulting codes will remain sorted by symbol.
Types ¶
type Decoder ¶
type Decoder struct { MinBits uint32 // The minimum number of bits to safely make progress NumSyms uint32 // Number of symbols // contains filtered or unexported fields }
func (*Decoder) Init ¶
func (pd *Decoder) Init(codes PrefixCodes)
Init initializes Decoder according to the codes provided.
type Encoder ¶
type Encoder struct { NumSyms uint32 // Number of symbols // contains filtered or unexported fields }
func (*Encoder) Init ¶
func (pe *Encoder) Init(codes PrefixCodes)
Init initializes Encoder according to the codes provided.
type PrefixCode ¶
type PrefixCode struct { Sym uint32 // The symbol being mapped Cnt uint32 // The number times this symbol is used Len uint32 // Bit-length of the prefix code Val uint32 // Value of the prefix code (must be in 0..(1<<Len)-1) }
PrefixCode is a representation of a prefix code, which is conceptually a mapping from some arbitrary symbol to some bit-string.
The Sym and Cnt fields are typically provided by the user, while the Len and Val fields are generated by this package.
type PrefixCodes ¶
type PrefixCodes []PrefixCode
func (PrefixCodes) Length ¶
func (pc PrefixCodes) Length() (nb uint)
Length computes the total bit-length using the Len and Cnt fields.
func (PrefixCodes) SortByCount ¶
func (pc PrefixCodes) SortByCount()
func (PrefixCodes) SortBySymbol ¶
func (pc PrefixCodes) SortBySymbol()
type RangeCode ¶
type RangeCodes ¶
type RangeCodes []RangeCode
func MakeRangeCodes ¶
func MakeRangeCodes(minBase uint, bits []uint) (rc RangeCodes)
MakeRangeCodes creates a RangeCodes, where each region is assumed to be contiguously stacked, without any gaps, with bit-lengths taken from bits.
func (RangeCodes) Base ¶
func (rcs RangeCodes) Base() uint32
Base reports the inclusive starting range for all ranges.
func (RangeCodes) End ¶
func (rcs RangeCodes) End() uint32
End reports the non-inclusive ending range for all ranges.
type RangeEncoder ¶
type RangeEncoder struct {
// contains filtered or unexported fields
}
func (*RangeEncoder) Encode ¶
func (re *RangeEncoder) Encode(offset uint) (sym uint)
func (*RangeEncoder) Init ¶
func (re *RangeEncoder) Init(rcs RangeCodes)
type Reader ¶
type Reader struct { Offset int64 // Number of bytes read from the underlying io.Reader // contains filtered or unexported fields }
Reader implements a prefix decoder. If the input io.Reader satisfies the compress.ByteReader or compress.BufferedReader interface, then it also guarantees that it will never read more bytes than is necessary.
For high performance, provide an io.Reader that satisfies the compress.BufferedReader interface. If the input does not satisfy either compress.ByteReader or compress.BufferedReader, then it will be internally wrapped with a bufio.Reader.
func (*Reader) Flush ¶
Flush updates the read offset of the underlying ByteReader. If reader is a compress.BufferedReader, then this calls Discard to update the read offset.
func (*Reader) Init ¶
Init initializes the bit Reader to read from r. If bigEndian is true, then bits will be read starting from the most-significant bits of a byte (as done in bzip2), otherwise it will read starting from the least-significant bits of a byte (such as for deflate and brotli).
func (*Reader) IsBufferedReader ¶
IsBufferedReader reports whether the underlying io.Reader is also a compress.BufferedReader.
func (*Reader) PullBits ¶
PullBits ensures that at least nb bits exist in the bit buffer. If the underlying reader is a compress.BufferedReader, then this will fill the bit buffer with as many bits as possible, relying on Peek and Discard to properly advance the read offset. Otherwise, it will use ReadByte to fill the buffer with just the right number of bits.
func (*Reader) ReadOffset ¶
func (pr *Reader) ReadOffset(pd *Decoder, rcs RangeCodes) uint
ReadOffset reads an offset value using the provided RangeCodes indexed by the symbol read.
func (*Reader) ReadSymbol ¶
ReadSymbol reads the next symbol using the provided prefix Decoder.
func (*Reader) TryReadBits ¶
TryReadBits attempts to read nb bits using the contents of the bit buffer alone. It returns the value and whether it succeeded.
This method is designed to be inlined for performance reasons.
func (*Reader) TryReadSymbol ¶
TryReadSymbol attempts to decode the next symbol using the contents of the bit buffer alone. It returns the decoded symbol and whether it succeeded.
This method is designed to be inlined for performance reasons.
type Writer ¶
type Writer struct { Offset int64 // Number of bytes written to the underlying io.Writer // contains filtered or unexported fields }
Writer implements a prefix encoder. For performance reasons, Writer will not write bytes immediately to the underlying stream.
func (*Writer) BitsWritten ¶
BitsWritten reports the total number of bits issued to any Write method.
func (*Writer) Flush ¶
Flush flushes all complete bytes from the bit buffer to the byte buffer, and then flushes all bytes in the byte buffer to the underlying writer. After this call, the bit Writer is will only withhold 7 bits at most.
func (*Writer) Init ¶
Init initializes the bit Writer to write to w. If bigEndian is true, then bits will be written starting from the most-significant bits of a byte (as done in bzip2), otherwise it will write starting from the least-significant bits of a byte (such as for deflate and brotli).
func (*Writer) PushBits ¶
PushBits pushes as many bytes as possible from the bit buffer to the byte buffer, reporting the number of bits pushed.
func (*Writer) TryWriteBits ¶
TryWriteBits attempts to write nb bits using the contents of the bit buffer alone. It reports whether it succeeded.
This method is designed to be inlined for performance reasons.
func (*Writer) TryWriteSymbol ¶
TryWriteSymbol attempts to encode the next symbol using the contents of the bit buffer alone. It reports whether it succeeded.
This method is designed to be inlined for performance reasons.
func (*Writer) Write ¶
Write writes bytes from buf. The bit-ordering mode does not affect this method.
func (*Writer) WriteOffset ¶
func (pw *Writer) WriteOffset(ofs uint, pe *Encoder, re *RangeEncoder)
WriteOffset writes ofs in a (sym, extra) fashion using the provided prefix Encoder and RangeEncoder.
func (*Writer) WriteSymbol ¶
WriteSymbol writes the symbol using the provided prefix Encoder.