// Copyright 2019 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
package main
import (
"bytes"
"flag"
"fmt"
"go/format"
"io/ioutil"
"log"
"os"
)
var debug = flag.Bool("debug", false, "")
func main() {
flag.Parse()
// Generate table.go.
{
w := &bytes.Buffer{}
w.WriteString(header)
w.WriteString(decodeHeaderComment)
writeDecodeTable(w, build(modeCodes[:], 0), "modeDecodeTable",
"// modeDecodeTable represents Table 1 and the End-of-Line code.\n")
writeDecodeTable(w, build(whiteCodes[:], 0), "whiteDecodeTable",
"// whiteDecodeTable represents Tables 2 and 3 for a white run.\n")
writeDecodeTable(w, build(blackCodes[:], 0), "blackDecodeTable",
"// blackDecodeTable represents Tables 2 and 3 for a black run.\n")
writeMaxCodeLength(w, modeCodes[:], whiteCodes[:], blackCodes[:])
w.WriteString(encodeHeaderComment)
w.WriteString(bitStringTypeDef)
writeEncodeTable(w, modeCodes[:], "modeEncodeTable",
"// modeEncodeTable represents Table 1 and the End-of-Line code.\n")
writeEncodeTable(w, whiteCodes[:64], "whiteEncodeTable2",
"// whiteEncodeTable2 represents Table 2 for a white run.\n")
writeEncodeTable(w, whiteCodes[64:], "whiteEncodeTable3",
"// whiteEncodeTable3 represents Table 3 for a white run.\n")
writeEncodeTable(w, blackCodes[:64], "blackEncodeTable2",
"// blackEncodeTable2 represents Table 2 for a black run.\n")
writeEncodeTable(w, blackCodes[64:], "blackEncodeTable3",
"// blackEncodeTable3 represents Table 3 for a black run.\n")
finish(w, "table.go")
}
// Generate table_test.go.
{
w := &bytes.Buffer{}
w.WriteString(header)
finish(w, "table_test.go")
}
}
const header = `// generated by "go run gen.go". DO NOT EDIT.
package ccitt
`
const decodeHeaderComment = `
// Each decodeTable is represented by an array of [2]int16's: a binary tree.
// Each array element (other than element 0, which means invalid) is a branch
// node in that tree. The root node is always element 1 (the second element).
//
// To walk the tree, look at the next bit in the bit stream, using it to select
// the first or second element of the [2]int16. If that int16 is 0, we have an
// invalid code. If it is positive, go to that branch node. If it is negative,
// then we have a leaf node, whose value is the bitwise complement (the ^
// operator) of that int16.
//
// Comments above each decodeTable also show the same structure visually. The
// "b123" lines show the 123'rd branch node. The "=XXXXX" lines show an invalid
// code. The "=v1234" lines show a leaf node with value 1234. When reading the
// bit stream, a 0 or 1 bit means to go up or down, as you move left to right.
//
// For example, in modeDecodeTable, branch node b005 is three steps up from the
// root node, meaning that we have already seen "000". If the next bit is "0"
// then we move to branch node b006. Otherwise, the next bit is "1", and we
// move to the leaf node v0000 (also known as the modePass constant). Indeed,
// the bits that encode modePass are "0001".
//
// Tables 1, 2 and 3 come from the "ITU-T Recommendation T.6: FACSIMILE CODING
// SCHEMES AND CODING CONTROL FUNCTIONS FOR GROUP 4 FACSIMILE APPARATUS"
// specification:
//
// https://www.itu.int/rec/dologin_pub.asp?lang=e&id=T-REC-T.6-198811-I!!PDF-E&type=items
`
const encodeHeaderComment = `
// Each encodeTable is represented by an array of bitStrings.
`
type node struct {
children [2]*node
val uint32
branchIndex int32
}
func (n *node) isBranch() bool {
return (n != nil) && ((n.children[0] != nil) || (n.children[1] != nil))
}
func (n *node) String() string {
if n == nil {
return "0"
}
if n.branchIndex > 0 {
return fmt.Sprintf("%d", n.branchIndex)
}
return fmt.Sprintf("^%d", n.val)
}
func build(codes []code, prefixLen int) *node {
if len(codes) == 0 {
return nil
}
if prefixLen == len(codes[0].str) {
if len(codes) != 1 {
panic("ambiguous codes")
}
return &node{
val: codes[0].val,
}
}
childrenCodes := [2][]code{}
for _, code := range codes {
bit := code.str[prefixLen] & 1
childrenCodes[bit] = append(childrenCodes[bit], code)
}
return &node{
children: [2]*node{
build(childrenCodes[0], prefixLen+1),
build(childrenCodes[1], prefixLen+1),
},
}
}
func writeDecodeTable(w *bytes.Buffer, root *node, varName, comment string) {
assignBranchIndexes(root)
w.WriteString(comment)
w.WriteString("//\n")
writeComment(w, root, " ", false)
fmt.Fprintf(w, "var %s = [...][2]int16{\n", varName)
fmt.Fprintf(w, "0: {0, 0},\n")
// Walk the tree in breadth-first order.
for queue := []*node{root}; len(queue) > 0; {
n := queue[0]
queue = queue[1:]
if n.isBranch() {
fmt.Fprintf(w, "%d: {%v, %v},\n", n.branchIndex, n.children[0], n.children[1])
queue = append(queue, n.children[0], n.children[1])
}
}
fmt.Fprintf(w, "}\n\n")
}
const bitStringTypeDef = `
// bitString is a pair of uint32 values representing a bit code.
// The nBits low bits of bits make up the actual bit code.
// Eg. bitString{0x0004, 8} represents the bitcode "00000100".
type bitString struct {
bits uint32
nBits uint32
}
`
func writeEncodeTable(w *bytes.Buffer, codes []code, varName, comment string) {
w.WriteString(comment)
fmt.Fprintf(w, "var %s = [...]bitString{\n", varName)
for i, code := range codes {
s := code.str
n := uint32(len(s))
c := uint32(0)
for j := uint32(0); j < n; j++ {
c |= uint32(s[j]&1) << (n - j - 1)
}
fmt.Fprintf(w, "%d: {0x%04x, %v}, // %q \n", i, c, n, s)
}
fmt.Fprintf(w, "}\n\n")
}
func assignBranchIndexes(root *node) {
// 0 is reserved for an invalid value.
branchIndex := int32(1)
// Walk the tree in breadth-first order.
for queue := []*node{root}; len(queue) > 0; {
n := queue[0]
queue = queue[1:]
if n.isBranch() {
n.branchIndex = branchIndex
branchIndex++
queue = append(queue, n.children[0], n.children[1])
}
}
}
func writeComment(w *bytes.Buffer, n *node, prefix string, down bool) {
if n.isBranch() {
prefixUp := prefix[:len(prefix)-2] + " | "
prefixDown := prefix + "| "
if down {
prefixUp, prefixDown = prefixDown, prefixUp
}
writeComment(w, n.children[0], prefixUp, false)
defer writeComment(w, n.children[1], prefixDown, true)
fmt.Fprintf(w, "// b%03d ", n.branchIndex)
} else {
fmt.Fprintf(w, "// ")
}
w.WriteString(prefix[:len(prefix)-2])
if n == nil {
fmt.Fprintf(w, "+=XXXXX\n")
return
}
if !n.isBranch() {
fmt.Fprintf(w, "+=v%04d\n", n.val)
return
}
w.WriteString("+-+\n")
}
func writeMaxCodeLength(w *bytes.Buffer, codesList ...[]code) {
maxCodeLength := 0
for _, codes := range codesList {
for _, code := range codes {
if n := len(code.str); maxCodeLength < n {
maxCodeLength = n
}
}
}
fmt.Fprintf(w, "const maxCodeLength = %d\n\n", maxCodeLength)
}
func finish(w *bytes.Buffer, filename string) {
copyPaste(w, filename)
if *debug {
os.Stdout.Write(w.Bytes())
return
}
out, err := format.Source(w.Bytes())
if err != nil {
log.Fatalf("format.Source: %v", err)
}
if err := ioutil.WriteFile(filename, out, 0660); err != nil {
log.Fatalf("ioutil.WriteFile: %v", err)
}
}
func copyPaste(w *bytes.Buffer, filename string) {
b, err := ioutil.ReadFile("gen.go")
if err != nil {
log.Fatalf("ioutil.ReadFile: %v", err)
}
begin := []byte("\n// COPY PASTE " + filename + " BEGIN\n\n")
end := []byte("\n// COPY PASTE " + filename + " END\n\n")
for len(b) > 0 {
i := bytes.Index(b, begin)
if i < 0 {
break
}
b = b[i:]
j := bytes.Index(b, end)
if j < 0 {
break
}
j += len(end)
w.Write(b[:j])
b = b[j:]
}
}
// COPY PASTE table.go BEGIN
const (
modePass = iota // Pass
modeH // Horizontal
modeV0 // Vertical-0
modeVR1 // Vertical-Right-1
modeVR2 // Vertical-Right-2
modeVR3 // Vertical-Right-3
modeVL1 // Vertical-Left-1
modeVL2 // Vertical-Left-2
modeVL3 // Vertical-Left-3
modeExt // Extension
)
// COPY PASTE table.go END
// The data that is the rest of this file is taken from Tables 1, 2 and 3 from
// the "ITU-T Recommendation T.6" spec.
// COPY PASTE table_test.go BEGIN
type code struct {
val uint32
str string
}
var modeCodes = []code{
{modePass, "0001"},
{modeH, "001"},
{modeV0, "1"},
{modeVR1, "011"},
{modeVR2, "000011"},
{modeVR3, "0000011"},
{modeVL1, "010"},
{modeVL2, "000010"},
{modeVL3, "0000010"},
{modeExt, "0000001"},
}
var whiteCodes = []code{
// Terminating codes (0-63).
{0x0000, "00110101"},
{0x0001, "000111"},
{0x0002, "0111"},
{0x0003, "1000"},
{0x0004, "1011"},
{0x0005, "1100"},
{0x0006, "1110"},
{0x0007, "1111"},
{0x0008, "10011"},
{0x0009, "10100"},
{0x000A, "00111"},
{0x000B, "01000"},
{0x000C, "001000"},
{0x000D, "000011"},
{0x000E, "110100"},
{0x000F, "110101"},
{0x0010, "101010"},
{0x0011, "101011"},
{0x0012, "0100111"},
{0x0013, "0001100"},
{0x0014, "0001000"},
{0x0015, "0010111"},
{0x0016, "0000011"},
{0x0017, "0000100"},
{0x0018, "0101000"},
{0x0019, "0101011"},
{0x001A, "0010011"},
{0x001B, "0100100"},
{0x001C, "0011000"},
{0x001D, "00000010"},
{0x001E, "00000011"},
{0x001F, "00011010"},
{0x0020, "00011011"},
{0x0021, "00010010"},
{0x0022, "00010011"},
{0x0023, "00010100"},
{0x0024, "00010101"},
{0x0025, "00010110"},
{0x0026, "00010111"},
{0x0027, "00101000"},
{0x0028, "00101001"},
{0x0029, "00101010"},
{0x002A, "00101011"},
{0x002B, "00101100"},
{0x002C, "00101101"},
{0x002D, "00000100"},
{0x002E, "00000101"},
{0x002F, "00001010"},
{0x0030, "00001011"},
{0x0031, "01010010"},
{0x0032, "01010011"},
{0x0033, "01010100"},
{0x0034, "01010101"},
{0x0035, "00100100"},
{0x0036, "00100101"},
{0x0037, "01011000"},
{0x0038, "01011001"},
{0x0039, "01011010"},
{0x003A, "01011011"},
{0x003B, "01001010"},
{0x003C, "01001011"},
{0x003D, "00110010"},
{0x003E, "00110011"},
{0x003F, "00110100"},
// Make-up codes between 64 and 1728.
{0x0040, "11011"},
{0x0080, "10010"},
{0x00C0, "010111"},
{0x0100, "0110111"},
{0x0140, "00110110"},
{0x0180, "00110111"},
{0x01C0, "01100100"},
{0x0200, "01100101"},
{0x0240, "01101000"},
{0x0280, "01100111"},
{0x02C0, "011001100"},
{0x0300, "011001101"},
{0x0340, "011010010"},
{0x0380, "011010011"},
{0x03C0, "011010100"},
{0x0400, "011010101"},
{0x0440, "011010110"},
{0x0480, "011010111"},
{0x04C0, "011011000"},
{0x0500, "011011001"},
{0x0540, "011011010"},
{0x0580, "011011011"},
{0x05C0, "010011000"},
{0x0600, "010011001"},
{0x0640, "010011010"},
{0x0680, "011000"},
{0x06C0, "010011011"},
// Make-up codes between 1792 and 2560.
{0x0700, "00000001000"},
{0x0740, "00000001100"},
{0x0780, "00000001101"},
{0x07C0, "000000010010"},
{0x0800, "000000010011"},
{0x0840, "000000010100"},
{0x0880, "000000010101"},
{0x08C0, "000000010110"},
{0x0900, "000000010111"},
{0x0940, "000000011100"},
{0x0980, "000000011101"},
{0x09C0, "000000011110"},
{0x0A00, "000000011111"},
}
var blackCodes = []code{
// Terminating codes (0-63).
{0x0000, "0000110111"},
{0x0001, "010"},
{0x0002, "11"},
{0x0003, "10"},
{0x0004, "011"},
{0x0005, "0011"},
{0x0006, "0010"},
{0x0007, "00011"},
{0x0008, "000101"},
{0x0009, "000100"},
{0x000A, "0000100"},
{0x000B, "0000101"},
{0x000C, "0000111"},
{0x000D, "00000100"},
{0x000E, "00000111"},
{0x000F, "000011000"},
{0x0010, "0000010111"},
{0x0011, "0000011000"},
{0x0012, "0000001000"},
{0x0013, "00001100111"},
{0x0014, "00001101000"},
{0x0015, "00001101100"},
{0x0016, "00000110111"},
{0x0017, "00000101000"},
{0x0018, "00000010111"},
{0x0019, "00000011000"},
{0x001A, "000011001010"},
{0x001B, "000011001011"},
{0x001C, "000011001100"},
{0x001D, "000011001101"},
{0x001E, "000001101000"},
{0x001F, "000001101001"},
{0x0020, "000001101010"},
{0x0021, "000001101011"},
{0x0022, "000011010010"},
{0x0023, "000011010011"},
{0x0024, "000011010100"},
{0x0025, "000011010101"},
{0x0026, "000011010110"},
{0x0027, "000011010111"},
{0x0028, "000001101100"},
{0x0029, "000001101101"},
{0x002A, "000011011010"},
{0x002B, "000011011011"},
{0x002C, "000001010100"},
{0x002D, "000001010101"},
{0x002E, "000001010110"},
{0x002F, "000001010111"},
{0x0030, "000001100100"},
{0x0031, "000001100101"},
{0x0032, "000001010010"},
{0x0033, "000001010011"},
{0x0034, "000000100100"},
{0x0035, "000000110111"},
{0x0036, "000000111000"},
{0x0037, "000000100111"},
{0x0038, "000000101000"},
{0x0039, "000001011000"},
{0x003A, "000001011001"},
{0x003B, "000000101011"},
{0x003C, "000000101100"},
{0x003D, "000001011010"},
{0x003E, "000001100110"},
{0x003F, "000001100111"},
// Make-up codes between 64 and 1728.
{0x0040, "0000001111"},
{0x0080, "000011001000"},
{0x00C0, "000011001001"},
{0x0100, "000001011011"},
{0x0140, "000000110011"},
{0x0180, "000000110100"},
{0x01C0, "000000110101"},
{0x0200, "0000001101100"},
{0x0240, "0000001101101"},
{0x0280, "0000001001010"},
{0x02C0, "0000001001011"},
{0x0300, "0000001001100"},
{0x0340, "0000001001101"},
{0x0380, "0000001110010"},
{0x03C0, "0000001110011"},
{0x0400, "0000001110100"},
{0x0440, "0000001110101"},
{0x0480, "0000001110110"},
{0x04C0, "0000001110111"},
{0x0500, "0000001010010"},
{0x0540, "0000001010011"},
{0x0580, "0000001010100"},
{0x05C0, "0000001010101"},
{0x0600, "0000001011010"},
{0x0640, "0000001011011"},
{0x0680, "0000001100100"},
{0x06C0, "0000001100101"},
// Make-up codes between 1792 and 2560.
{0x0700, "00000001000"},
{0x0740, "00000001100"},
{0x0780, "00000001101"},
{0x07C0, "000000010010"},
{0x0800, "000000010011"},
{0x0840, "000000010100"},
{0x0880, "000000010101"},
{0x08C0, "000000010110"},
{0x0900, "000000010111"},
{0x0940, "000000011100"},
{0x0980, "000000011101"},
{0x09C0, "000000011110"},
{0x0A00, "000000011111"},
}
// COPY PASTE table_test.go END
// This final comment makes the "END" above be followed by "\n\n".
