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

// 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 internal is a collection of common compression algorithms.
//
// For performance reasons, these packages lack strong error checking and
// require that the caller to ensure that strict invariants are kept.
package internal

var (
	// IdentityLUT returns the input key itself.
	IdentityLUT = func() (lut [256]byte) {
		for i := range lut {
			lut[i] = uint8(i)
		}
		return lut
	}()

	// ReverseLUT returns the input key with its bits reversed.
	ReverseLUT = func() (lut [256]byte) {
		for i := range lut {
			b := uint8(i)
			b = (b&0xaa)>>1 | (b&0x55)<<1
			b = (b&0xcc)>>2 | (b&0x33)<<2
			b = (b&0xf0)>>4 | (b&0x0f)<<4
			lut[i] = b
		}
		return lut
	}()
)

// ReverseUint32 reverses all bits of v.
func ReverseUint32(v uint32) (x uint32) {
	x |= uint32(ReverseLUT[byte(v>>0)]) << 24
	x |= uint32(ReverseLUT[byte(v>>8)]) << 16
	x |= uint32(ReverseLUT[byte(v>>16)]) << 8
	x |= uint32(ReverseLUT[byte(v>>24)]) << 0
	return x
}

// ReverseUint32N reverses the lower n bits of v.
func ReverseUint32N(v uint32, n uint) (x uint32) {
	return ReverseUint32(v << (32 - n))
}

// ReverseUint64 reverses all bits of v.
func ReverseUint64(v uint64) (x uint64) {
	x |= uint64(ReverseLUT[byte(v>>0)]) << 56
	x |= uint64(ReverseLUT[byte(v>>8)]) << 48
	x |= uint64(ReverseLUT[byte(v>>16)]) << 40
	x |= uint64(ReverseLUT[byte(v>>24)]) << 32
	x |= uint64(ReverseLUT[byte(v>>32)]) << 24
	x |= uint64(ReverseLUT[byte(v>>40)]) << 16
	x |= uint64(ReverseLUT[byte(v>>48)]) << 8
	x |= uint64(ReverseLUT[byte(v>>56)]) << 0
	return x
}

// ReverseUint64N reverses the lower n bits of v.
func ReverseUint64N(v uint64, n uint) (x uint64) {
	return ReverseUint64(v << (64 - n))
}

// MoveToFront is a data structure that allows for more efficient move-to-front
// transformations. This specific implementation assumes that the alphabet is
// densely packed within 0..255.
type MoveToFront struct {
	dict [256]uint8 // Mapping from indexes to values
	tail int        // Number of tail bytes that are already ordered
}

func (m *MoveToFront) Encode(vals []uint8) {
	copy(m.dict[:], IdentityLUT[:256-m.tail]) // Reset dict to be identity

	var max int
	for i, val := range vals {
		var idx uint8 // Reverse lookup idx in dict
		for di, dv := range m.dict {
			if dv == val {
				idx = uint8(di)
				break
			}
		}
		vals[i] = idx

		max |= int(idx)
		copy(m.dict[1:], m.dict[:idx])
		m.dict[0] = val
	}
	m.tail = 256 - max - 1
}

func (m *MoveToFront) Decode(idxs []uint8) {
	copy(m.dict[:], IdentityLUT[:256-m.tail]) // Reset dict to be identity

	var max int
	for i, idx := range idxs {
		val := m.dict[idx] // Forward lookup val in dict
		idxs[i] = val

		max |= int(idx)
		copy(m.dict[1:], m.dict[:idx])
		m.dict[0] = val
	}
	m.tail = 256 - max - 1
}