OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [compress/] [bzip2/] [move_to_front.go] - Blame information for rev 774

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 747 jeremybenn 
// 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 
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.