1 // Copyright 2014-2017 Ulrich Kunitz. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
12 // rangeEncoder implements range encoding of single bits. The low value can
13 // overflow therefore we need uint64. The cache value is used to handle
15 type rangeEncoder struct {
16 lbw *LimitedByteWriter
23 // maxInt64 provides the maximal value of the int64 type
24 const maxInt64 = 1<<63 - 1
26 // newRangeEncoder creates a new range encoder.
27 func newRangeEncoder(bw io.ByteWriter) (re *rangeEncoder, err error) {
28 lbw, ok := bw.(*LimitedByteWriter)
30 lbw = &LimitedByteWriter{BW: bw, N: maxInt64}
38 // Available returns the number of bytes that still can be written. The
39 // method takes the bytes that will be currently written by Close into
41 func (e *rangeEncoder) Available() int64 {
42 return e.lbw.N - (e.cacheLen + 4)
45 // writeByte writes a single byte to the underlying writer. An error is
46 // returned if the limit is reached. The written byte will be counted if
47 // the underlying writer doesn't return an error.
48 func (e *rangeEncoder) writeByte(c byte) error {
49 if e.Available() < 1 {
52 return e.lbw.WriteByte(c)
55 // DirectEncodeBit encodes the least-significant bit of b with probability 1/2.
56 func (e *rangeEncoder) DirectEncodeBit(b uint32) error {
58 e.low += uint64(e.nrange) & (0 - (uint64(b) & 1))
69 // EncodeBit encodes the least significant bit of b. The p value will be
70 // updated by the function depending on the bit encoded.
71 func (e *rangeEncoder) EncodeBit(b uint32, p *prob) error {
72 bound := p.bound(e.nrange)
77 e.low += uint64(bound)
91 // Close writes a complete copy of the low value.
92 func (e *rangeEncoder) Close() error {
93 for i := 0; i < 5; i++ {
94 if err := e.shiftLow(); err != nil {
101 // shiftLow shifts the low value for 8 bit. The shifted byte is written into
102 // the byte writer. The cache value is used to handle overflows.
103 func (e *rangeEncoder) shiftLow() error {
104 if uint32(e.low) < 0xff000000 || (e.low>>32) != 0 {
107 err := e.writeByte(tmp + byte(e.low>>32))
115 panic("negative cacheLen")
120 e.cache = byte(uint32(e.low) >> 24)
123 e.low = uint64(uint32(e.low) << 8)
127 // rangeDecoder decodes single bits of the range encoding stream.
128 type rangeDecoder struct {
134 // init initializes the range decoder, by reading from the byte reader.
135 func (d *rangeDecoder) init() error {
136 d.nrange = 0xffffffff
139 b, err := d.br.ReadByte()
144 return errors.New("newRangeDecoder: first byte not zero")
147 for i := 0; i < 4; i++ {
148 if err = d.updateCode(); err != nil {
153 if d.code >= d.nrange {
154 return errors.New("newRangeDecoder: d.code >= d.nrange")
160 // newRangeDecoder initializes a range decoder. It reads five bytes from the
161 // reader and therefore may return an error.
162 func newRangeDecoder(br io.ByteReader) (d *rangeDecoder, err error) {
163 d = &rangeDecoder{br: br, nrange: 0xffffffff}
165 b, err := d.br.ReadByte()
170 return nil, errors.New("newRangeDecoder: first byte not zero")
173 for i := 0; i < 4; i++ {
174 if err = d.updateCode(); err != nil {
179 if d.code >= d.nrange {
180 return nil, errors.New("newRangeDecoder: d.code >= d.nrange")
186 // possiblyAtEnd checks whether the decoder may be at the end of the stream.
187 func (d *rangeDecoder) possiblyAtEnd() bool {
191 // DirectDecodeBit decodes a bit with probability 1/2. The return value b will
192 // contain the bit at the least-significant position. All other bits will be
194 func (d *rangeDecoder) DirectDecodeBit() (b uint32, err error) {
197 t := 0 - (d.code >> 31)
198 d.code += d.nrange & t
201 // d.code will stay less then d.nrange
204 // assume d.code < d.nrange
210 // d.code < d.nrange will be maintained
211 return b, d.updateCode()
214 // decodeBit decodes a single bit. The bit will be returned at the
215 // least-significant position. All other bits will be zero. The probability
216 // value will be updated.
217 func (d *rangeDecoder) DecodeBit(p *prob) (b uint32, err error) {
218 bound := p.bound(d.nrange)
230 // assume d.code < d.nrange
236 // d.code < d.nrange will be maintained
237 return b, d.updateCode()
240 // updateCode reads a new byte into the code.
241 func (d *rangeDecoder) updateCode() error {
242 b, err := d.br.ReadByte()
246 d.code = (d.code << 8) | uint32(b)