1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89
90. 90
91. 91
92. 92
93. 93
94. 94
95. 95
96. 96
97. 97
98. 98
99. 99
100. 100
101. 101
102. 102
103. 103
104. 104
105. 105
106. 106
107. 107
108. 108
109. 109
110. 110
111. 111
112. 112
113. 113
114. 114
115. 115
116. 116
117. 117
118. 118
119. 119
120. 120
121. 121
122. 122
123. 123
124. 124
125. 125
126. 126
127. 127
128. 128
129. 129
130. 130
131. 131
132. 132
133. 133
134. 134
135. 135
136. 136

// Copyright 2015, Joe Tsai. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE.md file.

package prefix

import (
	"sort"

	"github.com/dsnet/compress/internal"
)

// The algorithm used to decode variable length codes is based on the lookup
// method in zlib. If the code is less-than-or-equal to maxChunkBits,
// then the symbol can be decoded using a single lookup into the chunks table.
// Otherwise, the links table will be used for a second level lookup.
//
// The chunks slice is keyed by the contents of the bit buffer ANDed with
// the chunkMask to avoid a out-of-bounds lookup. The value of chunks is a tuple
// that is decoded as follow:
//
//	var length = chunks[bitBuffer&chunkMask] & countMask
//	var symbol = chunks[bitBuffer&chunkMask] >> countBits
//
// If the decoded length is larger than chunkBits, then an overflow link table
// must be used for further decoding. In this case, the symbol is actually the
// index into the links tables. The second-level links table returned is
// processed in the same way as the chunks table.
//
//	if length > chunkBits {
//		var index = symbol // Previous symbol is index into links tables
//		length = links[index][bitBuffer>>chunkBits & linkMask] & countMask
//		symbol = links[index][bitBuffer>>chunkBits & linkMask] >> countBits
//	}
//
// See the following:
//	http://www.gzip.org/algorithm.txt

type Decoder struct {
	chunks    []uint32   // First-level lookup map
	links     [][]uint32 // Second-level lookup map
	chunkMask uint32     // Mask the length of the chunks table
	linkMask  uint32     // Mask the length of the link table
	chunkBits uint32     // Bit-length of the chunks table

	MinBits uint32 // The minimum number of bits to safely make progress
	NumSyms uint32 // Number of symbols
}

// Init initializes Decoder according to the codes provided.
func (pd *Decoder) Init(codes PrefixCodes) {
	// Handle special case trees.
	if len(codes) <= 1 {
		switch {
		case len(codes) == 0: // Empty tree (should error if used later)
			*pd = Decoder{chunks: pd.chunks[:0], links: pd.links[:0], NumSyms: 0}
		case len(codes) == 1 && codes[0].Len == 0: // Single code tree (bit-length of zero)
			pd.chunks = append(pd.chunks[:0], codes[0].Sym<<countBits|0)
			*pd = Decoder{chunks: pd.chunks[:1], links: pd.links[:0], NumSyms: 1}
		default:
			panic("invalid codes")
		}
		return
	}
	if internal.Debug && !sort.IsSorted(prefixCodesBySymbol(codes)) {
		panic("input codes is not sorted")
	}
	if internal.Debug && !(codes.checkLengths() && codes.checkPrefixes()) {
		panic("detected incomplete or overlapping codes")
	}

	var minBits, maxBits uint32 = valueBits, 0
	for _, c := range codes {
		if minBits > c.Len {
			minBits = c.Len
		}
		if maxBits < c.Len {
			maxBits = c.Len
		}
	}

	// Allocate chunks table as needed.
	const maxChunkBits = 9 // This can be tuned for better performance
	pd.NumSyms = uint32(len(codes))
	pd.MinBits = minBits
	pd.chunkBits = maxBits
	if pd.chunkBits > maxChunkBits {
		pd.chunkBits = maxChunkBits
	}
	numChunks := 1 << pd.chunkBits
	pd.chunks = allocUint32s(pd.chunks, numChunks)
	pd.chunkMask = uint32(numChunks - 1)

	// Allocate links tables as needed.
	pd.links = pd.links[:0]
	pd.linkMask = 0
	if pd.chunkBits < maxBits {
		numLinks := 1 << (maxBits - pd.chunkBits)
		pd.linkMask = uint32(numLinks - 1)

		var linkIdx uint32
		for i := range pd.chunks {
			pd.chunks[i] = 0 // Logic below relies on zero value as uninitialized
		}
		for _, c := range codes {
			if c.Len > pd.chunkBits && pd.chunks[c.Val&pd.chunkMask] == 0 {
				pd.chunks[c.Val&pd.chunkMask] = (linkIdx << countBits) | (pd.chunkBits + 1)
				linkIdx++
			}
		}

		pd.links = extendSliceUint32s(pd.links, int(linkIdx))
		linksFlat := allocUint32s(pd.links[0], numLinks*int(linkIdx))
		for i, j := 0, 0; i < len(pd.links); i, j = i+1, j+numLinks {
			pd.links[i] = linksFlat[j : j+numLinks]
		}
	}

	// Fill out chunks and links tables with values.
	for _, c := range codes {
		chunk := c.Sym<<countBits | c.Len
		if c.Len <= pd.chunkBits {
			skip := 1 << uint(c.Len)
			for j := int(c.Val); j < len(pd.chunks); j += skip {
				pd.chunks[j] = chunk
			}
		} else {
			linkIdx := pd.chunks[c.Val&pd.chunkMask] >> countBits
			links := pd.links[linkIdx]
			skip := 1 << uint(c.Len-pd.chunkBits)
			for j := int(c.Val >> pd.chunkBits); j < len(links); j += skip {
				links[j] = chunk
			}
		}
	}
}