1// Copyright 2011 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package bzip2
6
7// moveToFrontDecoder implements a move-to-front list. Such a list is an
8// efficient way to transform a string with repeating elements into one with
9// many small valued numbers, which is suitable for entropy encoding. It works
10// by starting with an initial list of symbols and references symbols by their
11// index into that list. When a symbol is referenced, it's moved to the front
12// of the list. Thus, a repeated symbol ends up being encoded with many zeros,
13// as the symbol will be at the front of the list after the first access.
14type moveToFrontDecoder []byte
15
16// newMTFDecoder creates a move-to-front decoder with an explicit initial list
17// of symbols.
18func newMTFDecoder(symbols []byte) moveToFrontDecoder {
19	if len(symbols) > 256 {
20		panic("too many symbols")
21	}
22	return moveToFrontDecoder(symbols)
23}
24
25// newMTFDecoderWithRange creates a move-to-front decoder with an initial
26// symbol list of 0...n-1.
27func newMTFDecoderWithRange(n int) moveToFrontDecoder {
28	if n > 256 {
29		panic("newMTFDecoderWithRange: cannot have > 256 symbols")
30	}
31
32	m := make([]byte, n)
33	for i := 0; i < n; i++ {
34		m[i] = byte(i)
35	}
36	return moveToFrontDecoder(m)
37}
38
39func (m moveToFrontDecoder) Decode(n int) (b byte) {
40	// Implement move-to-front with a simple copy. This approach
41	// beats more sophisticated approaches in benchmarking, probably
42	// because it has high locality of reference inside of a
43	// single cache line (most move-to-front operations have n < 64).
44	b = m[n]
45	copy(m[1:], m[:n])
46	m[0] = b
47	return
48}
49
50// First returns the symbol at the front of the list.
51func (m moveToFrontDecoder) First() byte {
52	return m[0]
53}
54