// Copyright 2011 The Go Authors. All rights reserved.
|
// Use of this source code is governed by a BSD-style
|
// license that can be found in the LICENSE file.
|
|
package bzip2
|
|
// moveToFrontDecoder implements a move-to-front list. Such a list is an
|
// efficient way to transform a string with repeating elements into one with
|
// many small valued numbers, which is suitable for entropy encoding. It works
|
// by starting with an initial list of symbols and references symbols by their
|
// index into that list. When a symbol is referenced, it's moved to the front
|
// of the list. Thus, a repeated symbol ends up being encoded with many zeros,
|
// as the symbol will be at the front of the list after the first access.
|
type moveToFrontDecoder []byte
|
|
// newMTFDecoder creates a move-to-front decoder with an explicit initial list
|
// of symbols.
|
func newMTFDecoder(symbols []byte) moveToFrontDecoder {
|
if len(symbols) > 256 {
|
panic("too many symbols")
|
}
|
return moveToFrontDecoder(symbols)
|
}
|
|
// newMTFDecoderWithRange creates a move-to-front decoder with an initial
|
// symbol list of 0...n-1.
|
func newMTFDecoderWithRange(n int) moveToFrontDecoder {
|
if n > 256 {
|
panic("newMTFDecoderWithRange: cannot have > 256 symbols")
|
}
|
|
m := make([]byte, n)
|
for i := 0; i < n; i++ {
|
m[i] = byte(i)
|
}
|
return moveToFrontDecoder(m)
|
}
|
|
func (m moveToFrontDecoder) Decode(n int) (b byte) {
|
// Implement move-to-front with a simple copy. This approach
|
// beats more sophisticated approaches in benchmarking, probably
|
// because it has high locality of reference inside of a
|
// single cache line (most move-to-front operations have n < 64).
|
b = m[n]
|
copy(m[1:], m[:n])
|
m[0] = b
|
return
|
}
|
|
// First returns the symbol at the front of the list.
|
func (m moveToFrontDecoder) First() byte {
|
return m[0]
|
}
|
