Source file 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	}