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
7// Constants used by the distance codec.
8const (
9 // minimum supported distance
10 minDistance = 1
11 // maximum supported distance, value is used for the eos marker.
12 maxDistance = 1 << 32
13 // number of the supported len states
14 lenStates = 4
15 // start for the position models
16 startPosModel = 4
17 // first index with align bits support
18 endPosModel = 14
19 // bits for the position slots
20 posSlotBits = 6
21 // number of align bits
22 alignBits = 4
23)
24
25// distCodec provides encoding and decoding of distance values.
26type distCodec struct {
27 posSlotCodecs [lenStates]treeCodec
28 posModel [endPosModel - startPosModel]treeReverseCodec
29 alignCodec treeReverseCodec
30}
31
32// deepcopy initializes dc as deep copy of the source.
33func (dc *distCodec) deepcopy(src *distCodec) {
34 if dc == src {
35 return
36 }
37 for i := range dc.posSlotCodecs {
38 dc.posSlotCodecs[i].deepcopy(&src.posSlotCodecs[i])
39 }
40 for i := range dc.posModel {
41 dc.posModel[i].deepcopy(&src.posModel[i])
42 }
43 dc.alignCodec.deepcopy(&src.alignCodec)
44}
45
46// newDistCodec creates a new distance codec.
47func (dc *distCodec) init() {
48 for i := range dc.posSlotCodecs {
49 dc.posSlotCodecs[i] = makeTreeCodec(posSlotBits)
50 }
51 for i := range dc.posModel {
52 posSlot := startPosModel + i
53 bits := (posSlot >> 1) - 1
54 dc.posModel[i] = makeTreeReverseCodec(bits)
55 }
56 dc.alignCodec = makeTreeReverseCodec(alignBits)
57}
58
59// lenState converts the value l to a supported lenState value.
60func lenState(l uint32) uint32 {
61 if l >= lenStates {
62 l = lenStates - 1
63 }
64 return l
65}
66
67// Encode encodes the distance using the parameter l. Dist can have values from
68// the full range of uint32 values. To get the distance offset the actual match
69// distance has to be decreased by 1. A distance offset of 0xffffffff (eos)
70// indicates the end of the stream.
71func (dc *distCodec) Encode(e *rangeEncoder, dist uint32, l uint32) (err error) {
72 // Compute the posSlot using nlz32
73 var posSlot uint32
74 var bits uint32
75 if dist < startPosModel {
76 posSlot = dist
77 } else {
78 bits = uint32(30 - nlz32(dist))
79 posSlot = startPosModel - 2 + (bits << 1)
80 posSlot += (dist >> uint(bits)) & 1
81 }
82
83 if err = dc.posSlotCodecs[lenState(l)].Encode(e, posSlot); err != nil {
84 return
85 }
86
87 switch {
88 case posSlot < startPosModel:
89 return nil
90 case posSlot < endPosModel:
91 tc := &dc.posModel[posSlot-startPosModel]
92 return tc.Encode(dist, e)
93 }
94 dic := directCodec(bits - alignBits)
95 if err = dic.Encode(e, dist>>alignBits); err != nil {
96 return
97 }
98 return dc.alignCodec.Encode(dist, e)
99}
100
101// Decode decodes the distance offset using the parameter l. The dist value
102// 0xffffffff (eos) indicates the end of the stream. Add one to the distance
103// offset to get the actual match distance.
104func (dc *distCodec) Decode(d *rangeDecoder, l uint32) (dist uint32, err error) {
105 posSlot, err := dc.posSlotCodecs[lenState(l)].Decode(d)
106 if err != nil {
107 return
108 }
109
110 // posSlot equals distance
111 if posSlot < startPosModel {
112 return posSlot, nil
113 }
114
115 // posSlot uses the individual models
116 bits := (posSlot >> 1) - 1
117 dist = (2 | (posSlot & 1)) << bits
118 var u uint32
119 if posSlot < endPosModel {
120 tc := &dc.posModel[posSlot-startPosModel]
121 if u, err = tc.Decode(d); err != nil {
122 return 0, err
123 }
124 dist += u
125 return dist, nil
126 }
127
128 // posSlots use direct encoding and a single model for the four align
129 // bits.
130 dic := directCodec(bits - alignBits)
131 if u, err = dic.Decode(d); err != nil {
132 return 0, err
133 }
134 dist += u << alignBits
135 if u, err = dc.alignCodec.Decode(d); err != nil {
136 return 0, err
137 }
138 dist += u
139 return dist, nil
140}