gen.go 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265
  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. // +build ignore
  5. // This program generates fixedhuff.go
  6. // Invoke as
  7. //
  8. // go run gen.go -output fixedhuff.go
  9. package main
  10. import (
  11. "bytes"
  12. "flag"
  13. "fmt"
  14. "go/format"
  15. "io/ioutil"
  16. "log"
  17. )
  18. var filename = flag.String("output", "fixedhuff.go", "output file name")
  19. const maxCodeLen = 16
  20. // Note: the definition of the huffmanDecoder struct is copied from
  21. // inflate.go, as it is private to the implementation.
  22. // chunk & 15 is number of bits
  23. // chunk >> 4 is value, including table link
  24. const (
  25. huffmanChunkBits = 9
  26. huffmanNumChunks = 1 << huffmanChunkBits
  27. huffmanCountMask = 15
  28. huffmanValueShift = 4
  29. )
  30. type huffmanDecoder struct {
  31. min int // the minimum code length
  32. chunks [huffmanNumChunks]uint32 // chunks as described above
  33. links [][]uint32 // overflow links
  34. linkMask uint32 // mask the width of the link table
  35. }
  36. // Initialize Huffman decoding tables from array of code lengths.
  37. // Following this function, h is guaranteed to be initialized into a complete
  38. // tree (i.e., neither over-subscribed nor under-subscribed). The exception is a
  39. // degenerate case where the tree has only a single symbol with length 1. Empty
  40. // trees are permitted.
  41. func (h *huffmanDecoder) init(bits []int) bool {
  42. // Sanity enables additional runtime tests during Huffman
  43. // table construction. It's intended to be used during
  44. // development to supplement the currently ad-hoc unit tests.
  45. const sanity = false
  46. if h.min != 0 {
  47. *h = huffmanDecoder{}
  48. }
  49. // Count number of codes of each length,
  50. // compute min and max length.
  51. var count [maxCodeLen]int
  52. var min, max int
  53. for _, n := range bits {
  54. if n == 0 {
  55. continue
  56. }
  57. if min == 0 || n < min {
  58. min = n
  59. }
  60. if n > max {
  61. max = n
  62. }
  63. count[n]++
  64. }
  65. // Empty tree. The decompressor.huffSym function will fail later if the tree
  66. // is used. Technically, an empty tree is only valid for the HDIST tree and
  67. // not the HCLEN and HLIT tree. However, a stream with an empty HCLEN tree
  68. // is guaranteed to fail since it will attempt to use the tree to decode the
  69. // codes for the HLIT and HDIST trees. Similarly, an empty HLIT tree is
  70. // guaranteed to fail later since the compressed data section must be
  71. // composed of at least one symbol (the end-of-block marker).
  72. if max == 0 {
  73. return true
  74. }
  75. code := 0
  76. var nextcode [maxCodeLen]int
  77. for i := min; i <= max; i++ {
  78. code <<= 1
  79. nextcode[i] = code
  80. code += count[i]
  81. }
  82. // Check that the coding is complete (i.e., that we've
  83. // assigned all 2-to-the-max possible bit sequences).
  84. // Exception: To be compatible with zlib, we also need to
  85. // accept degenerate single-code codings. See also
  86. // TestDegenerateHuffmanCoding.
  87. if code != 1<<uint(max) && !(code == 1 && max == 1) {
  88. return false
  89. }
  90. h.min = min
  91. if max > huffmanChunkBits {
  92. numLinks := 1 << (uint(max) - huffmanChunkBits)
  93. h.linkMask = uint32(numLinks - 1)
  94. // create link tables
  95. link := nextcode[huffmanChunkBits+1] >> 1
  96. h.links = make([][]uint32, huffmanNumChunks-link)
  97. for j := uint(link); j < huffmanNumChunks; j++ {
  98. reverse := int(reverseByte[j>>8]) | int(reverseByte[j&0xff])<<8
  99. reverse >>= uint(16 - huffmanChunkBits)
  100. off := j - uint(link)
  101. if sanity && h.chunks[reverse] != 0 {
  102. panic("impossible: overwriting existing chunk")
  103. }
  104. h.chunks[reverse] = uint32(off<<huffmanValueShift | (huffmanChunkBits + 1))
  105. h.links[off] = make([]uint32, numLinks)
  106. }
  107. }
  108. for i, n := range bits {
  109. if n == 0 {
  110. continue
  111. }
  112. code := nextcode[n]
  113. nextcode[n]++
  114. chunk := uint32(i<<huffmanValueShift | n)
  115. reverse := int(reverseByte[code>>8]) | int(reverseByte[code&0xff])<<8
  116. reverse >>= uint(16 - n)
  117. if n <= huffmanChunkBits {
  118. for off := reverse; off < len(h.chunks); off += 1 << uint(n) {
  119. // We should never need to overwrite
  120. // an existing chunk. Also, 0 is
  121. // never a valid chunk, because the
  122. // lower 4 "count" bits should be
  123. // between 1 and 15.
  124. if sanity && h.chunks[off] != 0 {
  125. panic("impossible: overwriting existing chunk")
  126. }
  127. h.chunks[off] = chunk
  128. }
  129. } else {
  130. j := reverse & (huffmanNumChunks - 1)
  131. if sanity && h.chunks[j]&huffmanCountMask != huffmanChunkBits+1 {
  132. // Longer codes should have been
  133. // associated with a link table above.
  134. panic("impossible: not an indirect chunk")
  135. }
  136. value := h.chunks[j] >> huffmanValueShift
  137. linktab := h.links[value]
  138. reverse >>= huffmanChunkBits
  139. for off := reverse; off < len(linktab); off += 1 << uint(n-huffmanChunkBits) {
  140. if sanity && linktab[off] != 0 {
  141. panic("impossible: overwriting existing chunk")
  142. }
  143. linktab[off] = chunk
  144. }
  145. }
  146. }
  147. if sanity {
  148. // Above we've sanity checked that we never overwrote
  149. // an existing entry. Here we additionally check that
  150. // we filled the tables completely.
  151. for i, chunk := range h.chunks {
  152. if chunk == 0 {
  153. // As an exception, in the degenerate
  154. // single-code case, we allow odd
  155. // chunks to be missing.
  156. if code == 1 && i%2 == 1 {
  157. continue
  158. }
  159. panic("impossible: missing chunk")
  160. }
  161. }
  162. for _, linktab := range h.links {
  163. for _, chunk := range linktab {
  164. if chunk == 0 {
  165. panic("impossible: missing chunk")
  166. }
  167. }
  168. }
  169. }
  170. return true
  171. }
  172. func main() {
  173. flag.Parse()
  174. var h huffmanDecoder
  175. var bits [288]int
  176. initReverseByte()
  177. for i := 0; i < 144; i++ {
  178. bits[i] = 8
  179. }
  180. for i := 144; i < 256; i++ {
  181. bits[i] = 9
  182. }
  183. for i := 256; i < 280; i++ {
  184. bits[i] = 7
  185. }
  186. for i := 280; i < 288; i++ {
  187. bits[i] = 8
  188. }
  189. h.init(bits[:])
  190. if h.links != nil {
  191. log.Fatal("Unexpected links table in fixed Huffman decoder")
  192. }
  193. var buf bytes.Buffer
  194. fmt.Fprintf(&buf, `// Copyright 2013 The Go Authors. All rights reserved.
  195. // Use of this source code is governed by a BSD-style
  196. // license that can be found in the LICENSE file.`+"\n\n")
  197. fmt.Fprintln(&buf, "package flate")
  198. fmt.Fprintln(&buf)
  199. fmt.Fprintln(&buf, "// autogenerated by go run gen.go -output fixedhuff.go, DO NOT EDIT")
  200. fmt.Fprintln(&buf)
  201. fmt.Fprintln(&buf, "var fixedHuffmanDecoder = huffmanDecoder{")
  202. fmt.Fprintf(&buf, "\t%d,\n", h.min)
  203. fmt.Fprintln(&buf, "\t[huffmanNumChunks]uint32{")
  204. for i := 0; i < huffmanNumChunks; i++ {
  205. if i&7 == 0 {
  206. fmt.Fprintf(&buf, "\t\t")
  207. } else {
  208. fmt.Fprintf(&buf, " ")
  209. }
  210. fmt.Fprintf(&buf, "0x%04x,", h.chunks[i])
  211. if i&7 == 7 {
  212. fmt.Fprintln(&buf)
  213. }
  214. }
  215. fmt.Fprintln(&buf, "\t},")
  216. fmt.Fprintln(&buf, "\tnil, 0,")
  217. fmt.Fprintln(&buf, "}")
  218. data, err := format.Source(buf.Bytes())
  219. if err != nil {
  220. log.Fatal(err)
  221. }
  222. err = ioutil.WriteFile(*filename, data, 0644)
  223. if err != nil {
  224. log.Fatal(err)
  225. }
  226. }
  227. var reverseByte [256]byte
  228. func initReverseByte() {
  229. for x := 0; x < 256; x++ {
  230. var result byte
  231. for i := uint(0); i < 8; i++ {
  232. result |= byte(((x >> i) & 1) << (7 - i))
  233. }
  234. reverseByte[x] = result
  235. }
  236. }