src/compress/flate/gen.go

// 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 -output fixedhuff.go

package main

import (
	"bytes"
	"flag"
	"fmt"
	"go/format"
	"io/ioutil"
	"log"
)

var filename = flag.String("output", "fixedhuff.go", "output file name")

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() {
	flag.Parse()

	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[:])

	var buf bytes.Buffer

	fmt.Fprintf(&buf, `// Copyright 2013 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.`+"\n\n")

	fmt.Fprintln(&buf, "package flate")
	fmt.Fprintln(&buf)
	fmt.Fprintln(&buf, "// autogenerated by go run gen.go -output fixedhuff.go, DO NOT EDIT")
	fmt.Fprintln(&buf)
	fmt.Fprintln(&buf, "var fixedHuffmanDecoder = huffmanDecoder{")
	fmt.Fprintf(&buf, "\t%d,\n", h.min)
	fmt.Fprintln(&buf, "\t[huffmanNumChunks]uint32{")
	for i := 0; i < huffmanNumChunks; i++ {
		if i&7 == 0 {
			fmt.Fprintf(&buf, "\t\t")
		} else {
			fmt.Fprintf(&buf, " ")
		}
		fmt.Fprintf(&buf, "0x%04x,", h.chunks[i])
		if i&7 == 7 {
			fmt.Fprintln(&buf)
		}
	}
	fmt.Fprintln(&buf, "\t},")
	fmt.Fprintln(&buf, "\tnil, 0,")
	fmt.Fprintln(&buf, "}")

	data, err := format.Source(buf.Bytes())
	if err != nil {
		log.Fatal(err)
	}
	err = ioutil.WriteFile(*filename, data, 0644)
	if err != nil {
		log.Fatal(err)
	}
}

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