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 5 package 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.
14 type moveToFrontDecoder []byte
15 16 // newMTFDecoder creates a move-to-front decoder with an explicit initial list
17 // of symbols.
18 func 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.
27 func newMTFDecoderWithRange(n int) moveToFrontDecoder {
28 if n > 256 {
29 panic("newMTFDecoderWithRange: cannot have > 256 symbols")
30 }
31 32 m := []byte{:n}
33 for i := 0; i < n; i++ {
34 m[i] = byte(i)
35 }
36 return moveToFrontDecoder(m)
37 }
38 39 func (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.
51 func (m moveToFrontDecoder) First() byte {
52 return m[0]
53 }
54