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
137. 137
138. 138
139. 139
140. 140
141. 141
142. 142
143. 143
144. 144
145. 145
146. 146
147. 147
148. 148
149. 149
150. 150
151. 151
152. 152
153. 153
154. 154
155. 155
156. 156
157. 157
158. 158
159. 159
160. 160
161. 161
162. 162
163. 163
164. 164
165. 165
166. 166
167. 167
168. 168
169. 169

package brotli

/* Copyright 2018 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* NOTE: this hasher does not search in the dictionary. It is used as
   backup-hasher, the main hasher already searches in it. */

const kRollingHashMul32 uint32 = 69069

const kInvalidPosHashRolling uint32 = 0xffffffff

/* This hasher uses a longer forward length, but returning a higher value here
   will hurt compression by the main hasher when combined with a composite
   hasher. The hasher tests for forward itself instead. */
func (*hashRolling) HashTypeLength() uint {
	return 4
}

func (*hashRolling) StoreLookahead() uint {
	return 4
}

/* Computes a code from a single byte. A lookup table of 256 values could be
   used, but simply adding 1 works about as good. */
func (*hashRolling) HashByte(b byte) uint32 {
	return uint32(b) + 1
}

func (h *hashRolling) HashRollingFunctionInitial(state uint32, add byte, factor uint32) uint32 {
	return uint32(factor*state + h.HashByte(add))
}

func (h *hashRolling) HashRollingFunction(state uint32, add byte, rem byte, factor uint32, factor_remove uint32) uint32 {
	return uint32(factor*state + h.HashByte(add) - factor_remove*h.HashByte(rem))
}

/* Rolling hash for long distance long string matches. Stores one position
   per bucket, bucket key is computed over a long region. */
type hashRolling struct {
	hasherCommon

	jump int

	state         uint32
	table         []uint32
	next_ix       uint
	chunk_len     uint32
	factor        uint32
	factor_remove uint32
}

func (h *hashRolling) Initialize(params *encoderParams) {
	h.state = 0
	h.next_ix = 0

	h.factor = kRollingHashMul32

	/* Compute the factor of the oldest byte to remove: factor**steps modulo
	   0xffffffff (the multiplications rely on 32-bit overflow) */
	h.factor_remove = 1

	for i := 0; i < 32; i += h.jump {
		h.factor_remove *= h.factor
	}

	h.table = make([]uint32, 16777216)
	for i := 0; i < 16777216; i++ {
		h.table[i] = kInvalidPosHashRolling
	}
}

func (h *hashRolling) Prepare(one_shot bool, input_size uint, data []byte) {
	/* Too small size, cannot use this hasher. */
	if input_size < 32 {
		return
	}
	h.state = 0
	for i := 0; i < 32; i += h.jump {
		h.state = h.HashRollingFunctionInitial(h.state, data[i], h.factor)
	}
}

func (*hashRolling) Store(data []byte, mask uint, ix uint) {
}

func (*hashRolling) StoreRange(data []byte, mask uint, ix_start uint, ix_end uint) {
}

func (h *hashRolling) StitchToPreviousBlock(num_bytes uint, position uint, ringbuffer []byte, ring_buffer_mask uint) {
	var position_masked uint
	/* In this case we must re-initialize the hasher from scratch from the
	   current position. */

	var available uint = num_bytes
	if position&uint(h.jump-1) != 0 {
		var diff uint = uint(h.jump) - (position & uint(h.jump-1))
		if diff > available {
			available = 0
		} else {
			available = available - diff
		}
		position += diff
	}

	position_masked = position & ring_buffer_mask

	/* wrapping around ringbuffer not handled. */
	if available > ring_buffer_mask-position_masked {
		available = ring_buffer_mask - position_masked
	}

	h.Prepare(false, available, ringbuffer[position&ring_buffer_mask:])
	h.next_ix = position
}

func (*hashRolling) PrepareDistanceCache(distance_cache []int) {
}

func (h *hashRolling) FindLongestMatch(dictionary *encoderDictionary, data []byte, ring_buffer_mask uint, distance_cache []int, cur_ix uint, max_length uint, max_backward uint, gap uint, max_distance uint, out *hasherSearchResult) {
	var cur_ix_masked uint = cur_ix & ring_buffer_mask
	var pos uint = h.next_ix

	if cur_ix&uint(h.jump-1) != 0 {
		return
	}

	/* Not enough lookahead */
	if max_length < 32 {
		return
	}

	for pos = h.next_ix; pos <= cur_ix; pos += uint(h.jump) {
		var code uint32 = h.state & ((16777216 * 64) - 1)
		var rem byte = data[pos&ring_buffer_mask]
		var add byte = data[(pos+32)&ring_buffer_mask]
		var found_ix uint = uint(kInvalidPosHashRolling)

		h.state = h.HashRollingFunction(h.state, add, rem, h.factor, h.factor_remove)

		if code < 16777216 {
			found_ix = uint(h.table[code])
			h.table[code] = uint32(pos)
			if pos == cur_ix && uint32(found_ix) != kInvalidPosHashRolling {
				/* The cast to 32-bit makes backward distances up to 4GB work even
				   if cur_ix is above 4GB, despite using 32-bit values in the table. */
				var backward uint = uint(uint32(cur_ix - found_ix))
				if backward <= max_backward {
					var found_ix_masked uint = found_ix & ring_buffer_mask
					var len uint = findMatchLengthWithLimit(data[found_ix_masked:], data[cur_ix_masked:], max_length)
					if len >= 4 && len > out.len {
						var score uint = backwardReferenceScore(uint(len), backward)
						if score > out.score {
							out.len = uint(len)
							out.distance = backward
							out.score = score
							out.len_code_delta = 0
						}
					}
				}
			}
		}
	}

	h.next_ix = cur_ix + uint(h.jump)
}