Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(587)

Delta Between Two Patch Sets: src/pkg/compress/flate/gen.go

Issue 6872063: code review 6872063: compress/flate: Performance improvement for inflate
Left Patch Set: diff -r 6e0e4077f488 https://code.google.com/p/go Created 11 years, 3 months ago
Right Patch Set: diff -r 5f9e99e3f2ea https://code.google.com/p/go Created 11 years, 2 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
Right: Side by side diff | Download
« no previous file with change/comment | « src/pkg/compress/flate/flate_test.go ('k') | src/pkg/compress/flate/inflate.go » ('j') | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
(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 }
LEFTRIGHT

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b