diff options
Diffstat (limited to 'src/pkg/compress/flate/gen.go')
-rw-r--r-- | src/pkg/compress/flate/gen.go | 165 |
1 files changed, 165 insertions, 0 deletions
diff --git a/src/pkg/compress/flate/gen.go b/src/pkg/compress/flate/gen.go new file mode 100644 index 000000000..1427557f8 --- /dev/null +++ b/src/pkg/compress/flate/gen.go @@ -0,0 +1,165 @@ +// Copyright 2012 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. + +// +build ignore + +// This program generates fixedhuff.go +// Invoke as +// +// go run gen.go |gofmt >fixedhuff.go + +package main + +import ( + "fmt" +) + +const maxCodeLen = 16 + +// Note: the definition of the huffmanDecoder struct is copied from +// inflate.go, as it is private to the implementation. + +// chunk & 15 is number of bits +// chunk >> 4 is value, including table link + +const ( + huffmanChunkBits = 9 + huffmanNumChunks = 1 << huffmanChunkBits + huffmanCountMask = 15 + huffmanValueShift = 4 +) + +type huffmanDecoder struct { + min int // the minimum code length + chunks [huffmanNumChunks]uint32 // chunks as described above + links [][]uint32 // overflow links + linkMask uint32 // mask the width of the link table +} + +// Initialize Huffman decoding tables from array of code lengths. +func (h *huffmanDecoder) init(bits []int) bool { + // Count number of codes of each length, + // compute min and max length. + var count [maxCodeLen]int + var min, max int + for _, n := range bits { + if n == 0 { + continue + } + if min == 0 || n < min { + min = n + } + if n > max { + max = n + } + count[n]++ + } + if max == 0 { + return false + } + + h.min = min + var linkBits uint + var numLinks int + if max > huffmanChunkBits { + linkBits = uint(max) - huffmanChunkBits + numLinks = 1 << linkBits + h.linkMask = uint32(numLinks - 1) + } + code := 0 + var nextcode [maxCodeLen]int + for i := min; i <= max; i++ { + if i == huffmanChunkBits+1 { + // create link tables + link := code >> 1 + h.links = make([][]uint32, huffmanNumChunks-link) + for j := uint(link); j < huffmanNumChunks; j++ { + reverse := int(reverseByte[j>>8]) | int(reverseByte[j&0xff])<<8 + reverse >>= uint(16 - huffmanChunkBits) + off := j - uint(link) + h.chunks[reverse] = uint32(off<<huffmanValueShift + uint(i)) + h.links[off] = make([]uint32, 1<<linkBits) + } + } + n := count[i] + nextcode[i] = code + code += n + code <<= 1 + } + + for i, n := range bits { + if n == 0 { + continue + } + code := nextcode[n] + nextcode[n]++ + chunk := uint32(i<<huffmanValueShift | n) + reverse := int(reverseByte[code>>8]) | int(reverseByte[code&0xff])<<8 + reverse >>= uint(16 - n) + if n <= huffmanChunkBits { + for off := reverse; off < huffmanNumChunks; off += 1 << uint(n) { + h.chunks[off] = chunk + } + } else { + linktab := h.links[h.chunks[reverse&(huffmanNumChunks-1)]>>huffmanValueShift] + reverse >>= huffmanChunkBits + for off := reverse; off < numLinks; off += 1 << uint(n-huffmanChunkBits) { + linktab[off] = chunk + } + } + } + return true +} + +func main() { + var h huffmanDecoder + var bits [288]int + initReverseByte() + for i := 0; i < 144; i++ { + bits[i] = 8 + } + for i := 144; i < 256; i++ { + bits[i] = 9 + } + for i := 256; i < 280; i++ { + bits[i] = 7 + } + for i := 280; i < 288; i++ { + bits[i] = 8 + } + h.init(bits[:]) + fmt.Println("package flate") + fmt.Println() + fmt.Println("// autogenerated by gen.go, DO NOT EDIT") + fmt.Println() + fmt.Println("var fixedHuffmanDecoder = huffmanDecoder{") + fmt.Printf("\t%d,\n", h.min) + fmt.Println("\t[huffmanNumChunks]uint32{") + for i := 0; i < huffmanNumChunks; i++ { + if i&7 == 0 { + fmt.Printf("\t\t") + } else { + fmt.Printf(" ") + } + fmt.Printf("0x%04x,", h.chunks[i]) + if i&7 == 7 { + fmt.Println() + } + } + fmt.Println("\t},") + fmt.Println("\tnil, 0,") + fmt.Println("}") +} + +var reverseByte [256]byte + +func initReverseByte() { + for x := 0; x < 256; x++ { + var result byte + for i := uint(0); i < 8; i++ { + result |= byte(((x >> i) & 1) << (7 - i)) + } + reverseByte[x] = result + } +} |