← Back to branch summary

~john-koepi/ubuntu/trusty/golang/default

« back to all changes in this revision

Viewing changes to src/pkg/compress/bzip2/move_to_front.go

  • Committer: Bazaar Package Importer
  • Author(s): Ondřej Surý
  • Date: 2011-04-20 17:36:48 UTC
  • Revision ID: james.westby@ubuntu.com-20110420173648-ifergoxyrm832trd
Tags: upstream-2011.03.07.1
Import upstream version 2011.03.07.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/compress/bzip2/move_to_front.go
 
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 struct {
 
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 []byte
 
19
        next    []uint8
 
20
        prev    []uint8
 
21
        head    uint8
 
22
}
 
23
 
 
24
// newMTFDecoder creates a move-to-front decoder with an explicit initial list
 
25
// of symbols.
 
26
func newMTFDecoder(symbols []byte) *moveToFrontDecoder {
 
27
        if len(symbols) > 256 {
 
28
                panic("too many symbols")
 
29
        }
 
30
 
 
31
        m := &moveToFrontDecoder{
 
32
                symbols: symbols,
 
33
                next:    make([]uint8, len(symbols)),
 
34
                prev:    make([]uint8, len(symbols)),
 
35
        }
 
36
 
 
37
        m.threadLinkedList()
 
38
        return m
 
39
}
 
40
 
 
41
// newMTFDecoderWithRange creates a move-to-front decoder with an initial
 
42
// symbol list of 0...n-1.
 
43
func newMTFDecoderWithRange(n int) *moveToFrontDecoder {
 
44
        if n > 256 {
 
45
                panic("newMTFDecoderWithRange: cannot have > 256 symbols")
 
46
        }
 
47
 
 
48
        m := &moveToFrontDecoder{
 
49
                symbols: make([]uint8, n),
 
50
                next:    make([]uint8, n),
 
51
                prev:    make([]uint8, n),
 
52
        }
 
53
 
 
54
        for i := 0; i < n; i++ {
 
55
                m.symbols[i] = byte(i)
 
56
        }
 
57
 
 
58
        m.threadLinkedList()
 
59
        return m
 
60
}
 
61
 
 
62
// threadLinkedList creates the initial linked-list pointers.
 
63
func (m *moveToFrontDecoder) threadLinkedList() {
 
64
        if len(m.symbols) == 0 {
 
65
                return
 
66
        }
 
67
 
 
68
        m.prev[0] = uint8(len(m.symbols) - 1)
 
69
 
 
70
        for i := 0; i < len(m.symbols)-1; i++ {
 
71
                m.next[i] = uint8(i + 1)
 
72
                m.prev[i+1] = uint8(i)
 
73
        }
 
74
 
 
75
        m.next[len(m.symbols)-1] = 0
 
76
}
 
77
 
 
78
func (m *moveToFrontDecoder) Decode(n int) (b byte) {
 
79
        // Most of the time, n will be zero so it's worth dealing with this
 
80
        // simple case.
 
81
        if n == 0 {
 
82
                return m.symbols[m.head]
 
83
        }
 
84
 
 
85
        i := m.head
 
86
        for j := 0; j < n; j++ {
 
87
                i = m.next[i]
 
88
        }
 
89
        b = m.symbols[i]
 
90
 
 
91
        m.next[m.prev[i]] = m.next[i]
 
92
        m.prev[m.next[i]] = m.prev[i]
 
93
        m.next[i] = m.head
 
94
        m.prev[i] = m.prev[m.head]
 
95
        m.next[m.prev[m.head]] = i
 
96
        m.prev[m.head] = i
 
97
        m.head = i
 
98
 
 
99
        return
 
100
}
 
101
 
 
102
// First returns the symbol at the front of the list.
 
103
func (m *moveToFrontDecoder) First() byte {
 
104
        return m.symbols[m.head]
 
105
}