source: code/trunk/vendor/github.com/andybalholm/brotli/hash_rolling.go@ 145

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
        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)
}