| // 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 |
| modeEOL // End-of-Line |
| ) |
| |
| // 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"}, |
| |
| // End-of-Line is not in Table 1, but we look for it at the same time that |
| // we look for other mode codes. |
| {modeEOL, "000000000001"}, |
| } |
| |
| 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". |