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

// 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"
)

type Encoder struct {
	chunks    []uint32 // First-level lookup map
	chunkMask uint32   // Mask the length of the chunks table

	NumSyms uint32 // Number of symbols
}

// Init initializes Encoder according to the codes provided.
func (pe *Encoder) Init(codes PrefixCodes) {
	// Handle special case trees.
	if len(codes) <= 1 {
		switch {
		case len(codes) == 0: // Empty tree (should error if used later)
			*pe = Encoder{chunks: pe.chunks[:0], NumSyms: 0}
		case len(codes) == 1 && codes[0].Len == 0: // Single code tree (bit-length of zero)
			pe.chunks = append(pe.chunks[:0], codes[0].Val<<countBits|0)
			*pe = Encoder{chunks: pe.chunks[:1], 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")
	}

	// Enough chunks to contain all the symbols.
	numChunks := 1
	for n := len(codes) - 1; n > 0; n >>= 1 {
		numChunks <<= 1
	}
	pe.NumSyms = uint32(len(codes))

retry:
	// Allocate and reset chunks.
	pe.chunks = allocUint32s(pe.chunks, numChunks)
	pe.chunkMask = uint32(numChunks - 1)
	for i := range pe.chunks {
		pe.chunks[i] = 0 // Logic below relies on zero value as uninitialized
	}

	// Insert each symbol, checking that there are no conflicts.
	for _, c := range codes {
		if pe.chunks[c.Sym&pe.chunkMask] > 0 {
			// Collision found our "hash" table, so grow and try again.
			numChunks <<= 1
			goto retry
		}
		pe.chunks[c.Sym&pe.chunkMask] = c.Val<<countBits | c.Len
	}
}