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