Subversion Repositories openrisc

// 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

import "sort"

// A huffmanTree is a binary tree which is navigated, bit-by-bit to reach a

// symbol.

type huffmanTree struct {

        // nodes contains all the non-leaf nodes in the tree. nodes[0] is the

        // root of the tree and nextNode contains the index of the next element

        // of nodes to use when the tree is being constructed.

        nodes    []huffmanNode

        nextNode int

}

// A huffmanNode is a node in the tree. left and right contain indexes into the

// nodes slice of the tree. If left or right is invalidNodeValue then the child

// is a left node and its value is in leftValue/rightValue.

//

// The symbols are uint16s because bzip2 encodes not only MTF indexes in the

// tree, but also two magic values for run-length encoding and an EOF symbol.

// Thus there are more than 256 possible symbols.

type huffmanNode struct {

        left, right           uint16

        leftValue, rightValue uint16

}

// invalidNodeValue is an invalid index which marks a leaf node in the tree.

const invalidNodeValue = 0xffff

// Decode reads bits from the given bitReader and navigates the tree until a

// symbol is found.

func (t huffmanTree) Decode(br *bitReader) (v uint16) {

        nodeIndex := uint16(0) // node 0 is the root of the tree.

        for {

                node := &t.nodes[nodeIndex]

                bit := br.ReadBit()

                // bzip2 encodes left as a true bit.

                if bit {

                        // left

                        if node.left == invalidNodeValue {

                                return node.leftValue

                        }

                        nodeIndex = node.left

                } else {

                        // right

                        if node.right == invalidNodeValue {

                                return node.rightValue

                        }

                        nodeIndex = node.right

                }

        }

        panic("unreachable")

}

// newHuffmanTree builds a Huffman tree from a slice containing the code

// lengths of each symbol. The maximum code length is 32 bits.

func newHuffmanTree(lengths []uint8) (huffmanTree, error) {

        // There are many possible trees that assign the same code length to

        // each symbol (consider reflecting a tree down the middle, for

        // example). Since the code length assignments determine the

        // efficiency of the tree, each of these trees is equally good. In

        // order to minimize the amount of information needed to build a tree

        // bzip2 uses a canonical tree so that it can be reconstructed given

        // only the code length assignments.

        if len(lengths) < 2 {

                panic("newHuffmanTree: too few symbols")

        }

        var t huffmanTree

        // First we sort the code length assignments by ascending code length,

        // using the symbol value to break ties.

        pairs := huffmanSymbolLengthPairs(make([]huffmanSymbolLengthPair, len(lengths)))

        for i, length := range lengths {

                pairs[i].value = uint16(i)

                pairs[i].length = length

        }

        sort.Sort(pairs)

        // Now we assign codes to the symbols, starting with the longest code.

        // We keep the codes packed into a uint32, at the most-significant end.

        // So branches are taken from the MSB downwards. This makes it easy to

        // sort them later.

        code := uint32(0)

        length := uint8(32)

        codes := huffmanCodes(make([]huffmanCode, len(lengths)))

        for i := len(pairs) - 1; i >= 0; i-- {

                if length > pairs[i].length {

                        // If the code length decreases we shift in order to

                        // zero any bits beyond the end of the code.

                        length >>= 32 - pairs[i].length

                        length <<= 32 - pairs[i].length

                        length = pairs[i].length

                }

                codes[i].code = code

                codes[i].codeLen = length

                codes[i].value = pairs[i].value

                // We need to 'increment' the code, which means treating |code|

                // like a |length| bit number.

                code += 1 << (32 - length)

        }

        // Now we can sort by the code so that the left half of each branch are

        // grouped together, recursively.

        sort.Sort(codes)

        t.nodes = make([]huffmanNode, len(codes))

        _, err := buildHuffmanNode(&t, codes, 0)

        return t, err

}

// huffmanSymbolLengthPair contains a symbol and its code length.

type huffmanSymbolLengthPair struct {

        value  uint16

        length uint8

}

// huffmanSymbolLengthPair is used to provide an interface for sorting.

type huffmanSymbolLengthPairs []huffmanSymbolLengthPair

func (h huffmanSymbolLengthPairs) Len() int {

        return len(h)

}

func (h huffmanSymbolLengthPairs) Less(i, j int) bool {

        if h[i].length < h[j].length {

                return true

        }

        if h[i].length > h[j].length {

                return false

        }

        if h[i].value < h[j].value {

                return true

        }

        return false

}

func (h huffmanSymbolLengthPairs) Swap(i, j int) {

        h[i], h[j] = h[j], h[i]

}

// huffmanCode contains a symbol, its code and code length.

type huffmanCode struct {

        code    uint32

        codeLen uint8

        value   uint16

}

// huffmanCodes is used to provide an interface for sorting.

type huffmanCodes []huffmanCode

func (n huffmanCodes) Len() int {

        return len(n)

}

func (n huffmanCodes) Less(i, j int) bool {

        return n[i].code < n[j].code

}

func (n huffmanCodes) Swap(i, j int) {

        n[i], n[j] = n[j], n[i]

}

// buildHuffmanNode takes a slice of sorted huffmanCodes and builds a node in

// the Huffman tree at the given level. It returns the index of the newly

// constructed node.

func buildHuffmanNode(t *huffmanTree, codes []huffmanCode, level uint32) (nodeIndex uint16, err error) {

        test := uint32(1) << (31 - level)

        // We have to search the list of codes to find the divide between the left and right sides.

        firstRightIndex := len(codes)

        for i, code := range codes {

                if code.code&test != 0 {

                        firstRightIndex = i

                        break

                }

        }

        left := codes[:firstRightIndex]

        right := codes[firstRightIndex:]

        if len(left) == 0 || len(right) == 0 {

                return 0, StructuralError("superfluous level in Huffman tree")

        }

        nodeIndex = uint16(t.nextNode)

        node := &t.nodes[t.nextNode]

        t.nextNode++

        if len(left) == 1 {

                // leaf node

                node.left = invalidNodeValue

                node.leftValue = left[0].value

        } else {

                node.left, err = buildHuffmanNode(t, left, level+1)

        }

        if err != nil {

                return

        }

        if len(right) == 1 {

                // leaf node

                node.right = invalidNodeValue

                node.rightValue = right[0].value

        } else {

                node.right, err = buildHuffmanNode(t, right, level+1)

        }

        return

}