1package brotli
2
3/* Copyright 2018 Google Inc. All Rights Reserved.
4
5   Distributed under MIT license.
6   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
7*/
8
9/* NOTE: this hasher does not search in the dictionary. It is used as
10   backup-hasher, the main hasher already searches in it. */
11
12const kRollingHashMul32 uint32 = 69069
13
14const kInvalidPosHashRolling uint32 = 0xffffffff
15
16/* This hasher uses a longer forward length, but returning a higher value here
17   will hurt compression by the main hasher when combined with a composite
18   hasher. The hasher tests for forward itself instead. */
19func (*hashRolling) HashTypeLength() uint {
20	return 4
21}
22
23func (*hashRolling) StoreLookahead() uint {
24	return 4
25}
26
27/* Computes a code from a single byte. A lookup table of 256 values could be
28   used, but simply adding 1 works about as good. */
29func (*hashRolling) HashByte(b byte) uint32 {
30	return uint32(b) + 1
31}
32
33func (h *hashRolling) HashRollingFunctionInitial(state uint32, add byte, factor uint32) uint32 {
34	return uint32(factor*state + h.HashByte(add))
35}
36
37func (h *hashRolling) HashRollingFunction(state uint32, add byte, rem byte, factor uint32, factor_remove uint32) uint32 {
38	return uint32(factor*state + h.HashByte(add) - factor_remove*h.HashByte(rem))
39}
40
41/* Rolling hash for long distance long string matches. Stores one position
42   per bucket, bucket key is computed over a long region. */
43type hashRolling struct {
44	hasherCommon
45
46	jump int
47
48	state         uint32
49	table         []uint32
50	next_ix       uint
51	chunk_len     uint32
52	factor        uint32
53	factor_remove uint32
54}
55
56func (h *hashRolling) Initialize(params *encoderParams) {
57	h.state = 0
58	h.next_ix = 0
59
60	h.factor = kRollingHashMul32
61
62	/* Compute the factor of the oldest byte to remove: factor**steps modulo
63	   0xffffffff (the multiplications rely on 32-bit overflow) */
64	h.factor_remove = 1
65
66	for i := 0; i < 32; i += h.jump {
67		h.factor_remove *= h.factor
68	}
69
70	h.table = make([]uint32, 16777216)
71	for i := 0; i < 16777216; i++ {
72		h.table[i] = kInvalidPosHashRolling
73	}
74}
75
76func (h *hashRolling) Prepare(one_shot bool, input_size uint, data []byte) {
77	/* Too small size, cannot use this hasher. */
78	if input_size < 32 {
79		return
80	}
81	h.state = 0
82	for i := 0; i < 32; i += h.jump {
83		h.state = h.HashRollingFunctionInitial(h.state, data[i], h.factor)
84	}
85}
86
87func (*hashRolling) Store(data []byte, mask uint, ix uint) {
88}
89
90func (*hashRolling) StoreRange(data []byte, mask uint, ix_start uint, ix_end uint) {
91}
92
93func (h *hashRolling) StitchToPreviousBlock(num_bytes uint, position uint, ringbuffer []byte, ring_buffer_mask uint) {
94	var position_masked uint
95	/* In this case we must re-initialize the hasher from scratch from the
96	   current position. */
97
98	var available uint = num_bytes
99	if position&uint(h.jump-1) != 0 {
100		var diff uint = uint(h.jump) - (position & uint(h.jump-1))
101		if diff > available {
102			available = 0
103		} else {
104			available = available - diff
105		}
106		position += diff
107	}
108
109	position_masked = position & ring_buffer_mask
110
111	/* wrapping around ringbuffer not handled. */
112	if available > ring_buffer_mask-position_masked {
113		available = ring_buffer_mask - position_masked
114	}
115
116	h.Prepare(false, available, ringbuffer[position&ring_buffer_mask:])
117	h.next_ix = position
118}
119
120func (*hashRolling) PrepareDistanceCache(distance_cache []int) {
121}
122
123func (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) {
124	var cur_ix_masked uint = cur_ix & ring_buffer_mask
125	var pos uint = h.next_ix
126
127	if cur_ix&uint(h.jump-1) != 0 {
128		return
129	}
130
131	/* Not enough lookahead */
132	if max_length < 32 {
133		return
134	}
135
136	for pos = h.next_ix; pos <= cur_ix; pos += uint(h.jump) {
137		var code uint32 = h.state & ((16777216 * 64) - 1)
138		var rem byte = data[pos&ring_buffer_mask]
139		var add byte = data[(pos+32)&ring_buffer_mask]
140		var found_ix uint = uint(kInvalidPosHashRolling)
141
142		h.state = h.HashRollingFunction(h.state, add, rem, h.factor, h.factor_remove)
143
144		if code < 16777216 {
145			found_ix = uint(h.table[code])
146			h.table[code] = uint32(pos)
147			if pos == cur_ix && uint32(found_ix) != kInvalidPosHashRolling {
148				/* The cast to 32-bit makes backward distances up to 4GB work even
149				   if cur_ix is above 4GB, despite using 32-bit values in the table. */
150				var backward uint = uint(uint32(cur_ix - found_ix))
151				if backward <= max_backward {
152					var found_ix_masked uint = found_ix & ring_buffer_mask
153					var len uint = findMatchLengthWithLimit(data[found_ix_masked:], data[cur_ix_masked:], max_length)
154					if len >= 4 && len > out.len {
155						var score uint = backwardReferenceScore(uint(len), backward)
156						if score > out.score {
157							out.len = uint(len)
158							out.distance = backward
159							out.score = score
160							out.len_code_delta = 0
161						}
162					}
163				}
164			}
165		}
166	}
167
168	h.next_ix = cur_ix + uint(h.jump)
169}
170