diff options
Diffstat (limited to 'vendor/github.com/andybalholm/brotli/h5.go')
| -rw-r--r-- | vendor/github.com/andybalholm/brotli/h5.go | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/vendor/github.com/andybalholm/brotli/h5.go b/vendor/github.com/andybalholm/brotli/h5.go new file mode 100644 index 0000000000..f391b73fdd --- /dev/null +++ b/vendor/github.com/andybalholm/brotli/h5.go @@ -0,0 +1,214 @@ +package brotli + +import "encoding/binary" + +/* Copyright 2010 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +/* A (forgetful) hash table to the data seen by the compressor, to + help create backward references to previous data. + + This is a hash map of fixed size (bucket_size_) to a ring buffer of + fixed size (block_size_). The ring buffer contains the last block_size_ + index positions of the given hash key in the compressed data. */ +func (*h5) HashTypeLength() uint { + return 4 +} + +func (*h5) StoreLookahead() uint { + return 4 +} + +/* HashBytes is the function that chooses the bucket to place the address in. */ +func hashBytesH5(data []byte, shift int) uint32 { + var h uint32 = binary.LittleEndian.Uint32(data) * kHashMul32 + + /* The higher bits contain more mixture from the multiplication, + so we take our results from there. */ + return uint32(h >> uint(shift)) +} + +type h5 struct { + hasherCommon + bucket_size_ uint + block_size_ uint + hash_shift_ int + block_mask_ uint32 + num []uint16 + buckets []uint32 +} + +func (h *h5) Initialize(params *encoderParams) { + h.hash_shift_ = 32 - h.params.bucket_bits + h.bucket_size_ = uint(1) << uint(h.params.bucket_bits) + h.block_size_ = uint(1) << uint(h.params.block_bits) + h.block_mask_ = uint32(h.block_size_ - 1) + h.num = make([]uint16, h.bucket_size_) + h.buckets = make([]uint32, h.block_size_*h.bucket_size_) +} + +func (h *h5) Prepare(one_shot bool, input_size uint, data []byte) { + var num []uint16 = h.num + var partial_prepare_threshold uint = h.bucket_size_ >> 6 + /* Partial preparation is 100 times slower (per socket). */ + if one_shot && input_size <= partial_prepare_threshold { + var i uint + for i = 0; i < input_size; i++ { + var key uint32 = hashBytesH5(data[i:], h.hash_shift_) + num[key] = 0 + } + } else { + for i := 0; i < int(h.bucket_size_); i++ { + num[i] = 0 + } + } +} + +/* Look at 4 bytes at &data[ix & mask]. + Compute a hash from these, and store the value of ix at that position. */ +func (h *h5) Store(data []byte, mask uint, ix uint) { + var num []uint16 = h.num + var key uint32 = hashBytesH5(data[ix&mask:], h.hash_shift_) + var minor_ix uint = uint(num[key]) & uint(h.block_mask_) + var offset uint = minor_ix + uint(key<<uint(h.params.block_bits)) + h.buckets[offset] = uint32(ix) + num[key]++ +} + +func (h *h5) StoreRange(data []byte, mask uint, ix_start uint, ix_end uint) { + var i uint + for i = ix_start; i < ix_end; i++ { + h.Store(data, mask, i) + } +} + +func (h *h5) StitchToPreviousBlock(num_bytes uint, position uint, ringbuffer []byte, ringbuffer_mask uint) { + if num_bytes >= h.HashTypeLength()-1 && position >= 3 { + /* Prepare the hashes for three last bytes of the last write. + These could not be calculated before, since they require knowledge + of both the previous and the current block. */ + h.Store(ringbuffer, ringbuffer_mask, position-3) + h.Store(ringbuffer, ringbuffer_mask, position-2) + h.Store(ringbuffer, ringbuffer_mask, position-1) + } +} + +func (h *h5) PrepareDistanceCache(distance_cache []int) { + prepareDistanceCache(distance_cache, h.params.num_last_distances_to_check) +} + +/* Find a longest backward match of &data[cur_ix] up to the length of + max_length and stores the position cur_ix in the hash table. + + REQUIRES: PrepareDistanceCacheH5 must be invoked for current distance cache + values; if this method is invoked repeatedly with the same distance + cache values, it is enough to invoke PrepareDistanceCacheH5 once. + + Does not look for matches longer than max_length. + Does not look for matches further away than max_backward. + Writes the best match into |out|. + |out|->score is updated only if a better match is found. */ +func (h *h5) 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 num []uint16 = h.num + var buckets []uint32 = h.buckets + var cur_ix_masked uint = cur_ix & ring_buffer_mask + var min_score uint = out.score + var best_score uint = out.score + var best_len uint = out.len + var i uint + var bucket []uint32 + /* Don't accept a short copy from far away. */ + out.len = 0 + + out.len_code_delta = 0 + + /* Try last distance first. */ + for i = 0; i < uint(h.params.num_last_distances_to_check); i++ { + var backward uint = uint(distance_cache[i]) + var prev_ix uint = uint(cur_ix - backward) + if prev_ix >= cur_ix { + continue + } + + if backward > max_backward { + continue + } + + prev_ix &= ring_buffer_mask + + if cur_ix_masked+best_len > ring_buffer_mask || prev_ix+best_len > ring_buffer_mask || data[cur_ix_masked+best_len] != data[prev_ix+best_len] { + continue + } + { + var len uint = findMatchLengthWithLimit(data[prev_ix:], data[cur_ix_masked:], max_length) + if len >= 3 || (len == 2 && i < 2) { + /* Comparing for >= 2 does not change the semantics, but just saves for + a few unnecessary binary logarithms in backward reference score, + since we are not interested in such short matches. */ + var score uint = backwardReferenceScoreUsingLastDistance(uint(len)) + if best_score < score { + if i != 0 { + score -= backwardReferencePenaltyUsingLastDistance(i) + } + if best_score < score { + best_score = score + best_len = uint(len) + out.len = best_len + out.distance = backward + out.score = best_score + } + } + } + } + } + { + var key uint32 = hashBytesH5(data[cur_ix_masked:], h.hash_shift_) + bucket = buckets[key<<uint(h.params.block_bits):] + var down uint + if uint(num[key]) > h.block_size_ { + down = uint(num[key]) - h.block_size_ + } else { + down = 0 + } + for i = uint(num[key]); i > down; { + var prev_ix uint + i-- + prev_ix = uint(bucket[uint32(i)&h.block_mask_]) + var backward uint = cur_ix - prev_ix + if backward > max_backward { + break + } + + prev_ix &= ring_buffer_mask + if cur_ix_masked+best_len > ring_buffer_mask || prev_ix+best_len > ring_buffer_mask || data[cur_ix_masked+best_len] != data[prev_ix+best_len] { + continue + } + { + var len uint = findMatchLengthWithLimit(data[prev_ix:], data[cur_ix_masked:], max_length) + if len >= 4 { + /* Comparing for >= 3 does not change the semantics, but just saves + for a few unnecessary binary logarithms in backward reference + score, since we are not interested in such short matches. */ + var score uint = backwardReferenceScore(uint(len), backward) + if best_score < score { + best_score = score + best_len = uint(len) + out.len = best_len + out.distance = backward + out.score = best_score + } + } + } + } + + bucket[uint32(num[key])&h.block_mask_] = uint32(cur_ix) + num[key]++ + } + + if min_score == out.score { + searchInStaticDictionary(dictionary, h, data[cur_ix_masked:], max_length, max_backward+gap, max_distance, out, false) + } +} |