LEFT | RIGHT |
(no file at all) | |
| 1 // Copyright 2012 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 // +build ignore |
| 6 |
| 7 // This program generates fixedhuff.go |
| 8 // Invoke as |
| 9 // |
| 10 // go run gen.go |gofmt >fixedhuff.go |
| 11 |
| 12 package main |
| 13 |
| 14 import ( |
| 15 "fmt" |
| 16 ) |
| 17 |
| 18 const maxCodeLen = 16 |
| 19 |
| 20 // Note: the definition of the huffmanDecoder struct is copied from |
| 21 // inflate.go, as it is private to the implementation. |
| 22 |
| 23 // chunk & 15 is number of bits |
| 24 // chunk >> 4 is value, including table link |
| 25 |
| 26 const ( |
| 27 huffmanChunkBits = 9 |
| 28 huffmanNumChunks = 1 << huffmanChunkBits |
| 29 huffmanCountMask = 15 |
| 30 huffmanValueShift = 4 |
| 31 ) |
| 32 |
| 33 type huffmanDecoder struct { |
| 34 min int // the minimum code length |
| 35 chunks [huffmanNumChunks]uint32 // chunks as described above |
| 36 links [][]uint32 // overflow links |
| 37 linkMask uint32 // mask the width of the link table· |
| 38 } |
| 39 |
| 40 // Initialize Huffman decoding tables from array of code lengths. |
| 41 func (h *huffmanDecoder) init(bits []int) bool { |
| 42 // Count number of codes of each length, |
| 43 // compute min and max length. |
| 44 var count [maxCodeLen]int |
| 45 var min, max int |
| 46 for _, n := range bits { |
| 47 if n == 0 { |
| 48 continue |
| 49 } |
| 50 if min == 0 || n < min { |
| 51 min = n |
| 52 } |
| 53 if n > max { |
| 54 max = n |
| 55 } |
| 56 count[n]++ |
| 57 } |
| 58 if max == 0 { |
| 59 return false |
| 60 } |
| 61 |
| 62 h.min = min |
| 63 var linkBits uint |
| 64 var numLinks int |
| 65 if max > huffmanChunkBits { |
| 66 linkBits = uint(max) - huffmanChunkBits |
| 67 numLinks = 1 << linkBits |
| 68 h.linkMask = uint32(numLinks - 1) |
| 69 } |
| 70 code := 0 |
| 71 var nextcode [maxCodeLen]int |
| 72 for i := min; i <= max; i++ { |
| 73 if i == huffmanChunkBits+1 { |
| 74 // create link tables |
| 75 link := code >> 1 |
| 76 h.links = make([][]uint32, huffmanNumChunks-link) |
| 77 for j := uint(link); j < huffmanNumChunks; j++ { |
| 78 reverse := int(reverseByte[j>>8]) | int(reverseB
yte[j&0xff])<<8 |
| 79 reverse >>= uint(16 - huffmanChunkBits) |
| 80 off := j - uint(link) |
| 81 h.chunks[reverse] = uint32(off<<huffmanValueShif
t + uint(i)) |
| 82 h.links[off] = make([]uint32, 1<<linkBits) |
| 83 } |
| 84 } |
| 85 n := count[i] |
| 86 nextcode[i] = code |
| 87 code += n |
| 88 code <<= 1 |
| 89 } |
| 90 |
| 91 for i, n := range bits { |
| 92 if n == 0 { |
| 93 continue |
| 94 } |
| 95 code := nextcode[n] |
| 96 nextcode[n]++ |
| 97 chunk := uint32(i<<huffmanValueShift | n) |
| 98 reverse := int(reverseByte[code>>8]) | int(reverseByte[code&0xff
])<<8 |
| 99 reverse >>= uint(16 - n) |
| 100 if n <= huffmanChunkBits { |
| 101 for off := reverse; off < huffmanNumChunks; off += 1 <<
uint(n) { |
| 102 h.chunks[off] = chunk |
| 103 } |
| 104 } else { |
| 105 linktab := h.links[h.chunks[reverse&(huffmanNumChunks-1)
]>>huffmanValueShift] |
| 106 reverse >>= huffmanChunkBits |
| 107 for off := reverse; off < numLinks; off += 1 << uint(n-h
uffmanChunkBits) { |
| 108 linktab[off] = chunk |
| 109 } |
| 110 } |
| 111 } |
| 112 return true |
| 113 } |
| 114 |
| 115 func main() { |
| 116 var h huffmanDecoder |
| 117 var bits [288]int |
| 118 initReverseByte() |
| 119 for i := 0; i < 144; i++ { |
| 120 bits[i] = 8 |
| 121 } |
| 122 for i := 144; i < 256; i++ { |
| 123 bits[i] = 9 |
| 124 } |
| 125 for i := 256; i < 280; i++ { |
| 126 bits[i] = 7 |
| 127 } |
| 128 for i := 280; i < 288; i++ { |
| 129 bits[i] = 8 |
| 130 } |
| 131 h.init(bits[:]) |
| 132 fmt.Println("package flate") |
| 133 fmt.Println() |
| 134 fmt.Println("// autogenerated by gen.go, DO NOT EDIT") |
| 135 fmt.Println() |
| 136 fmt.Println("var fixedHuffmanDecoder = huffmanDecoder{") |
| 137 fmt.Printf("\t%d,\n", h.min) |
| 138 fmt.Println("\t[huffmanNumChunks]uint32{") |
| 139 for i := 0; i < huffmanNumChunks; i++ { |
| 140 if i&7 == 0 { |
| 141 fmt.Printf("\t\t") |
| 142 } else { |
| 143 fmt.Printf(" ") |
| 144 } |
| 145 fmt.Printf("0x%04x,", h.chunks[i]) |
| 146 if i&7 == 7 { |
| 147 fmt.Println() |
| 148 } |
| 149 } |
| 150 fmt.Println("\t},") |
| 151 fmt.Println("\tnil, 0,") |
| 152 fmt.Println("}") |
| 153 } |
| 154 |
| 155 var reverseByte [256]byte |
| 156 |
| 157 func initReverseByte() { |
| 158 for x := 0; x < 256; x++ { |
| 159 var result byte |
| 160 for i := uint(0); i < 8; i++ { |
| 161 result |= byte(((x >> i) & 1) << (7 - i)) |
| 162 } |
| 163 reverseByte[x] = result |
| 164 } |
| 165 } |
LEFT | RIGHT |