main
1// Copyright 2014-2022 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.
4
5package lzma
6
7import (
8 "errors"
9 "io"
10)
11
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
14// overflows.
15type rangeEncoder struct {
16 lbw *LimitedByteWriter
17 nrange uint32
18 low uint64
19 cacheLen int64
20 cache byte
21}
22
23// maxInt64 provides the maximal value of the int64 type
24const maxInt64 = 1<<63 - 1
25
26// newRangeEncoder creates a new range encoder.
27func newRangeEncoder(bw io.ByteWriter) (re *rangeEncoder, err error) {
28 lbw, ok := bw.(*LimitedByteWriter)
29 if !ok {
30 lbw = &LimitedByteWriter{BW: bw, N: maxInt64}
31 }
32 return &rangeEncoder{
33 lbw: lbw,
34 nrange: 0xffffffff,
35 cacheLen: 1}, nil
36}
37
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
40// account.
41func (e *rangeEncoder) Available() int64 {
42 return e.lbw.N - (e.cacheLen + 4)
43}
44
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.
48func (e *rangeEncoder) writeByte(c byte) error {
49 if e.Available() < 1 {
50 return ErrLimit
51 }
52 return e.lbw.WriteByte(c)
53}
54
55// DirectEncodeBit encodes the least-significant bit of b with probability 1/2.
56func (e *rangeEncoder) DirectEncodeBit(b uint32) error {
57 e.nrange >>= 1
58 e.low += uint64(e.nrange) & (0 - (uint64(b) & 1))
59
60 // normalize
61 const top = 1 << 24
62 if e.nrange >= top {
63 return nil
64 }
65 e.nrange <<= 8
66 return e.shiftLow()
67}
68
69// EncodeBit encodes the least significant bit of b. The p value will be
70// updated by the function depending on the bit encoded.
71func (e *rangeEncoder) EncodeBit(b uint32, p *prob) error {
72 bound := p.bound(e.nrange)
73 if b&1 == 0 {
74 e.nrange = bound
75 p.inc()
76 } else {
77 e.low += uint64(bound)
78 e.nrange -= bound
79 p.dec()
80 }
81
82 // normalize
83 const top = 1 << 24
84 if e.nrange >= top {
85 return nil
86 }
87 e.nrange <<= 8
88 return e.shiftLow()
89}
90
91// Close writes a complete copy of the low value.
92func (e *rangeEncoder) Close() error {
93 for i := 0; i < 5; i++ {
94 if err := e.shiftLow(); err != nil {
95 return err
96 }
97 }
98 return nil
99}
100
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.
103func (e *rangeEncoder) shiftLow() error {
104 if uint32(e.low) < 0xff000000 || (e.low>>32) != 0 {
105 tmp := e.cache
106 for {
107 err := e.writeByte(tmp + byte(e.low>>32))
108 if err != nil {
109 return err
110 }
111 tmp = 0xff
112 e.cacheLen--
113 if e.cacheLen <= 0 {
114 if e.cacheLen < 0 {
115 panic("negative cacheLen")
116 }
117 break
118 }
119 }
120 e.cache = byte(uint32(e.low) >> 24)
121 }
122 e.cacheLen++
123 e.low = uint64(uint32(e.low) << 8)
124 return nil
125}
126
127// rangeDecoder decodes single bits of the range encoding stream.
128type rangeDecoder struct {
129 br io.ByteReader
130 nrange uint32
131 code uint32
132}
133
134// newRangeDecoder initializes a range decoder. It reads five bytes from the
135// reader and therefore may return an error.
136func newRangeDecoder(br io.ByteReader) (d *rangeDecoder, err error) {
137 d = &rangeDecoder{br: br, nrange: 0xffffffff}
138
139 b, err := d.br.ReadByte()
140 if err != nil {
141 return nil, err
142 }
143 if b != 0 {
144 return nil, errors.New("newRangeDecoder: first byte not zero")
145 }
146
147 for i := 0; i < 4; i++ {
148 if err = d.updateCode(); err != nil {
149 return nil, err
150 }
151 }
152
153 if d.code >= d.nrange {
154 return nil, errors.New("newRangeDecoder: d.code >= d.nrange")
155 }
156
157 return d, nil
158}
159
160// possiblyAtEnd checks whether the decoder may be at the end of the stream.
161func (d *rangeDecoder) possiblyAtEnd() bool {
162 return d.code == 0
163}
164
165// DirectDecodeBit decodes a bit with probability 1/2. The return value b will
166// contain the bit at the least-significant position. All other bits will be
167// zero.
168func (d *rangeDecoder) DirectDecodeBit() (b uint32, err error) {
169 d.nrange >>= 1
170 d.code -= d.nrange
171 t := 0 - (d.code >> 31)
172 d.code += d.nrange & t
173 b = (t + 1) & 1
174
175 // d.code will stay less then d.nrange
176
177 // normalize
178 // assume d.code < d.nrange
179 const top = 1 << 24
180 if d.nrange >= top {
181 return b, nil
182 }
183 d.nrange <<= 8
184 // d.code < d.nrange will be maintained
185 return b, d.updateCode()
186}
187
188// decodeBit decodes a single bit. The bit will be returned at the
189// least-significant position. All other bits will be zero. The probability
190// value will be updated.
191func (d *rangeDecoder) DecodeBit(p *prob) (b uint32, err error) {
192 bound := p.bound(d.nrange)
193 if d.code < bound {
194 d.nrange = bound
195 p.inc()
196 b = 0
197 } else {
198 d.code -= bound
199 d.nrange -= bound
200 p.dec()
201 b = 1
202 }
203 // normalize
204 // assume d.code < d.nrange
205 const top = 1 << 24
206 if d.nrange >= top {
207 return b, nil
208 }
209 d.nrange <<= 8
210 // d.code < d.nrange will be maintained
211 return b, d.updateCode()
212}
213
214// updateCode reads a new byte into the code.
215func (d *rangeDecoder) updateCode() error {
216 b, err := d.br.ReadByte()
217 if err != nil {
218 return err
219 }
220 d.code = (d.code << 8) | uint32(b)
221 return nil
222}