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. 4 5package lzma 6 7import "errors" 8 9// maxPosBits defines the number of bits of the position value that are used to 10// to compute the posState value. The value is used to select the tree codec 11// for length encoding and decoding. 12const maxPosBits = 4 13 14// minMatchLen and maxMatchLen give the minimum and maximum values for 15// encoding and decoding length values. minMatchLen is also used as base 16// for the encoded length values. 17const ( 18 minMatchLen = 2 19 maxMatchLen = minMatchLen + 16 + 256 - 1 20) 21 22// lengthCodec support the encoding of the length value. 23type lengthCodec struct { 24 choice [2]prob 25 low [1 << maxPosBits]treeCodec 26 mid [1 << maxPosBits]treeCodec 27 high treeCodec 28} 29 30// deepcopy initializes the lc value as deep copy of the source value. 31func (lc *lengthCodec) deepcopy(src *lengthCodec) { 32 if lc == src { 33 return 34 } 35 lc.choice = src.choice 36 for i := range lc.low { 37 lc.low[i].deepcopy(&src.low[i]) 38 } 39 for i := range lc.mid { 40 lc.mid[i].deepcopy(&src.mid[i]) 41 } 42 lc.high.deepcopy(&src.high) 43} 44 45// init initializes a new length codec. 46func (lc *lengthCodec) init() { 47 for i := range lc.choice { 48 lc.choice[i] = probInit 49 } 50 for i := range lc.low { 51 lc.low[i] = makeTreeCodec(3) 52 } 53 for i := range lc.mid { 54 lc.mid[i] = makeTreeCodec(3) 55 } 56 lc.high = makeTreeCodec(8) 57} 58 59// lBits gives the number of bits used for the encoding of the l value 60// provided to the range encoder. 61func lBits(l uint32) int { 62 switch { 63 case l < 8: 64 return 4 65 case l < 16: 66 return 5 67 default: 68 return 10 69 } 70} 71 72// Encode encodes the length offset. The length offset l can be compute by 73// subtracting minMatchLen (2) from the actual length. 74// 75// l = length - minMatchLen 76// 77func (lc *lengthCodec) Encode(e *rangeEncoder, l uint32, posState uint32, 78) (err error) { 79 if l > maxMatchLen-minMatchLen { 80 return errors.New("lengthCodec.Encode: l out of range") 81 } 82 if l < 8 { 83 if err = lc.choice[0].Encode(e, 0); err != nil { 84 return 85 } 86 return lc.low[posState].Encode(e, l) 87 } 88 if err = lc.choice[0].Encode(e, 1); err != nil { 89 return 90 } 91 if l < 16 { 92 if err = lc.choice[1].Encode(e, 0); err != nil { 93 return 94 } 95 return lc.mid[posState].Encode(e, l-8) 96 } 97 if err = lc.choice[1].Encode(e, 1); err != nil { 98 return 99 } 100 if err = lc.high.Encode(e, l-16); err != nil { 101 return 102 } 103 return nil 104} 105 106// Decode reads the length offset. Add minMatchLen to compute the actual length 107// to the length offset l. 108func (lc *lengthCodec) Decode(d *rangeDecoder, posState uint32, 109) (l uint32, err error) { 110 var b uint32 111 if b, err = lc.choice[0].Decode(d); err != nil { 112 return 113 } 114 if b == 0 { 115 l, err = lc.low[posState].Decode(d) 116 return 117 } 118 if b, err = lc.choice[1].Decode(d); err != nil { 119 return 120 } 121 if b == 0 { 122 l, err = lc.mid[posState].Decode(d) 123 l += 8 124 return 125 } 126 l, err = lc.high.Decode(d) 127 l += 16 128 return 129} 130