Colin Cross | 7bb052a | 2015-02-03 12:59:37 -0800 | [diff] [blame^] | 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 | } |