...
Run Format

Source file src/compress/bzip2/move_to_front.go

Documentation: compress/bzip2

  // Copyright 2011 The Go Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style
  // license that can be found in the LICENSE file.
  
  package bzip2
  
  // moveToFrontDecoder implements a move-to-front list. Such a list is an
  // efficient way to transform a string with repeating elements into one with
  // many small valued numbers, which is suitable for entropy encoding. It works
  // by starting with an initial list of symbols and references symbols by their
  // index into that list. When a symbol is referenced, it's moved to the front
  // of the list. Thus, a repeated symbol ends up being encoded with many zeros,
  // as the symbol will be at the front of the list after the first access.
  type moveToFrontDecoder []byte
  
  // newMTFDecoder creates a move-to-front decoder with an explicit initial list
  // of symbols.
  func newMTFDecoder(symbols []byte) moveToFrontDecoder {
  	if len(symbols) > 256 {
  		panic("too many symbols")
  	}
  	return moveToFrontDecoder(symbols)
  }
  
  // newMTFDecoderWithRange creates a move-to-front decoder with an initial
  // symbol list of 0...n-1.
  func newMTFDecoderWithRange(n int) moveToFrontDecoder {
  	if n > 256 {
  		panic("newMTFDecoderWithRange: cannot have > 256 symbols")
  	}
  
  	m := make([]byte, n)
  	for i := 0; i < n; i++ {
  		m[i] = byte(i)
  	}
  	return moveToFrontDecoder(m)
  }
  
  func (m moveToFrontDecoder) Decode(n int) (b byte) {
  	// Implement move-to-front with a simple copy. This approach
  	// beats more sophisticated approaches in benchmarking, probably
  	// because it has high locality of reference inside of a
  	// single cache line (most move-to-front operations have n < 64).
  	b = m[n]
  	copy(m[1:], m[:n])
  	m[0] = b
  	return
  }
  
  // First returns the symbol at the front of the list.
  func (m moveToFrontDecoder) First() byte {
  	return m[0]
  }
  

View as plain text