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 := make([]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
