LEFT | RIGHT |
(no file at all) | |
1 // Copyright 2011 The Go Authors. All rights reserved. | 1 // Copyright 2011 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 package bzip2 | 5 package bzip2 |
6 | 6 |
7 // moveToFrontDecoder implements a move-to-front list. Such a list is an | 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 | 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 | 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 | 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 | 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, | 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. | 13 // as the symbol will be at the front of the list after the first access. |
14 type moveToFrontDecoder struct { | 14 type moveToFrontDecoder []byte |
15 » // Rather than actually keep the list in memory, the symbols are stored | |
16 » // as a circular, double linked list with the symbol indexed by head | |
17 » // at the front of the list. | |
18 » symbols [256]byte | |
19 » next [256]uint8 | |
20 » prev [256]uint8 | |
21 » head uint8 | |
22 » len int | |
23 } | |
24 | 15 |
25 // newMTFDecoder creates a move-to-front decoder with an explicit initial list | 16 // newMTFDecoder creates a move-to-front decoder with an explicit initial list |
26 // of symbols. | 17 // of symbols. |
27 func newMTFDecoder(symbols []byte) *moveToFrontDecoder { | 18 func newMTFDecoder(symbols []byte) moveToFrontDecoder { |
28 if len(symbols) > 256 { | 19 if len(symbols) > 256 { |
29 panic("too many symbols") | 20 panic("too many symbols") |
30 } | 21 } |
31 | 22 » return moveToFrontDecoder(symbols) |
32 » m := new(moveToFrontDecoder) | |
33 » copy(m.symbols[:], symbols) | |
34 » m.len = len(symbols) | |
35 » m.threadLinkedList() | |
36 » return m | |
37 } | 23 } |
38 | 24 |
39 // newMTFDecoderWithRange creates a move-to-front decoder with an initial | 25 // newMTFDecoderWithRange creates a move-to-front decoder with an initial |
40 // symbol list of 0...n-1. | 26 // symbol list of 0...n-1. |
41 func newMTFDecoderWithRange(n int) *moveToFrontDecoder { | 27 func newMTFDecoderWithRange(n int) moveToFrontDecoder { |
42 if n > 256 { | 28 if n > 256 { |
43 panic("newMTFDecoderWithRange: cannot have > 256 symbols") | 29 panic("newMTFDecoderWithRange: cannot have > 256 symbols") |
44 } | 30 } |
45 | 31 |
46 » m := new(moveToFrontDecoder) | 32 » m := make([]byte, n) |
47 for i := 0; i < n; i++ { | 33 for i := 0; i < n; i++ { |
48 » » m.symbols[byte(i)] = byte(i) | 34 » » m[i] = byte(i) |
49 } | 35 } |
50 » m.len = n | 36 » return moveToFrontDecoder(m) |
51 » m.threadLinkedList() | |
52 » return m | |
53 } | 37 } |
54 | 38 |
55 // threadLinkedList creates the initial linked-list pointers. | 39 func (m moveToFrontDecoder) Decode(n int) (b byte) { |
56 func (m *moveToFrontDecoder) threadLinkedList() { | 40 » // Implement move-to-front with a simple copy. This approach |
57 » if m.len == 0 { | 41 » // beats more sophisticated approaches in benchmarking, probably |
58 » » return | 42 » // because it has high locality of reference inside of a |
59 » } | 43 » // single cache line (most move-to-front operations have n < 64). |
60 | 44 » b = m[n] |
61 » m.prev[0] = uint8(m.len - 1) | 45 » copy(m[1:], m[:n]) |
62 | 46 » m[0] = b |
63 » for i := byte(0); int(i) < m.len-1; i++ { | |
64 » » m.next[i] = uint8(i + 1) | |
65 » » m.prev[i+1] = uint8(i) | |
66 » } | |
67 | |
68 » m.next[m.len-1] = 0 | |
69 } | |
70 | |
71 func (m *moveToFrontDecoder) Decode(n int) (b byte) { | |
72 » // Most of the time, n will be zero so it's worth dealing with this | |
73 » // simple case. | |
74 » if n == 0 { | |
75 » » return m.symbols[m.head] | |
76 » } | |
77 | |
78 » i := m.head | |
79 » for j := 0; j < n; j++ { | |
80 » » i = m.next[i] | |
81 » } | |
82 » b = m.symbols[i] | |
83 | |
84 » m.next[m.prev[i]] = m.next[i] | |
85 » m.prev[m.next[i]] = m.prev[i] | |
86 » m.next[i] = m.head | |
87 » m.prev[i] = m.prev[m.head] | |
88 » m.next[m.prev[m.head]] = i | |
89 » m.prev[m.head] = i | |
90 » m.head = i | |
91 | |
92 return | 47 return |
93 } | 48 } |
94 | 49 |
95 // First returns the symbol at the front of the list. | 50 // First returns the symbol at the front of the list. |
96 func (m *moveToFrontDecoder) First() byte { | 51 func (m moveToFrontDecoder) First() byte { |
97 » return m.symbols[m.head] | 52 » return m[0] |
98 } | 53 } |
LEFT | RIGHT |