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
  7// treeCodec encodes or decodes values with a fixed bit size. It is using a
  8// tree of probability value. The root of the tree is the most-significant bit.
  9type treeCodec struct {
 10	probTree
 11}
 12
 13// makeTreeCodec makes a tree codec. The bits value must be inside the range
 14// [1,32].
 15func makeTreeCodec(bits int) treeCodec {
 16	return treeCodec{makeProbTree(bits)}
 17}
 18
 19// deepcopy initializes tc as a deep copy of the source.
 20func (tc *treeCodec) deepcopy(src *treeCodec) {
 21	tc.probTree.deepcopy(&src.probTree)
 22}
 23
 24// Encode uses the range encoder to encode a fixed-bit-size value.
 25func (tc *treeCodec) Encode(e *rangeEncoder, v uint32) (err error) {
 26	m := uint32(1)
 27	for i := int(tc.bits) - 1; i >= 0; i-- {
 28		b := (v >> uint(i)) & 1
 29		if err := e.EncodeBit(b, &tc.probs[m]); err != nil {
 30			return err
 31		}
 32		m = (m << 1) | b
 33	}
 34	return nil
 35}
 36
 37// Decodes uses the range decoder to decode a fixed-bit-size value. Errors may
 38// be caused by the range decoder.
 39func (tc *treeCodec) Decode(d *rangeDecoder) (v uint32, err error) {
 40	m := uint32(1)
 41	for j := 0; j < int(tc.bits); j++ {
 42		b, err := d.DecodeBit(&tc.probs[m])
 43		if err != nil {
 44			return 0, err
 45		}
 46		m = (m << 1) | b
 47	}
 48	return m - (1 << uint(tc.bits)), nil
 49}
 50
 51// treeReverseCodec is another tree codec, where the least-significant bit is
 52// the start of the probability tree.
 53type treeReverseCodec struct {
 54	probTree
 55}
 56
 57// deepcopy initializes the treeReverseCodec as a deep copy of the
 58// source.
 59func (tc *treeReverseCodec) deepcopy(src *treeReverseCodec) {
 60	tc.probTree.deepcopy(&src.probTree)
 61}
 62
 63// makeTreeReverseCodec creates treeReverseCodec value. The bits argument must
 64// be in the range [1,32].
 65func makeTreeReverseCodec(bits int) treeReverseCodec {
 66	return treeReverseCodec{makeProbTree(bits)}
 67}
 68
 69// Encode uses range encoder to encode a fixed-bit-size value. The range
 70// encoder may cause errors.
 71func (tc *treeReverseCodec) Encode(v uint32, e *rangeEncoder) (err error) {
 72	m := uint32(1)
 73	for i := uint(0); i < uint(tc.bits); i++ {
 74		b := (v >> i) & 1
 75		if err := e.EncodeBit(b, &tc.probs[m]); err != nil {
 76			return err
 77		}
 78		m = (m << 1) | b
 79	}
 80	return nil
 81}
 82
 83// Decodes uses the range decoder to decode a fixed-bit-size value. Errors
 84// returned by the range decoder will be returned.
 85func (tc *treeReverseCodec) Decode(d *rangeDecoder) (v uint32, err error) {
 86	m := uint32(1)
 87	for j := uint(0); j < uint(tc.bits); j++ {
 88		b, err := d.DecodeBit(&tc.probs[m])
 89		if err != nil {
 90			return 0, err
 91		}
 92		m = (m << 1) | b
 93		v |= b << j
 94	}
 95	return v, nil
 96}
 97
 98// probTree stores enough probability values to be used by the treeEncode and
 99// treeDecode methods of the range coder types.
100type probTree struct {
101	probs []prob
102	bits  byte
103}
104
105// deepcopy initializes the probTree value as a deep copy of the source.
106func (t *probTree) deepcopy(src *probTree) {
107	if t == src {
108		return
109	}
110	t.probs = make([]prob, len(src.probs))
111	copy(t.probs, src.probs)
112	t.bits = src.bits
113}
114
115// makeProbTree initializes a probTree structure.
116func makeProbTree(bits int) probTree {
117	if !(1 <= bits && bits <= 32) {
118		panic("bits outside of range [1,32]")
119	}
120	t := probTree{
121		bits:  byte(bits),
122		probs: make([]prob, 1<<uint(bits)),
123	}
124	for i := range t.probs {
125		t.probs[i] = probInit
126	}
127	return t
128}
129
130// Bits provides the number of bits for the values to de- or encode.
131func (t *probTree) Bits() int {
132	return int(t.bits)
133}