1// Copyright 2019 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
7package main
8
9import (
10 "bytes"
11 "flag"
12 "fmt"
13 "go/format"
14 "io/ioutil"
15 "log"
16 "os"
17)
18
19var debug = flag.Bool("debug", false, "")
20
21func main() {
22 flag.Parse()
23
24 // Generate table.go.
25 {
26 w := &bytes.Buffer{}
27 w.WriteString(header)
28 w.WriteString(decodeHeaderComment)
29 writeDecodeTable(w, build(modeCodes[:], 0), "modeDecodeTable",
30 "// modeDecodeTable represents Table 1 and the End-of-Line code.\n")
31 writeDecodeTable(w, build(whiteCodes[:], 0), "whiteDecodeTable",
32 "// whiteDecodeTable represents Tables 2 and 3 for a white run.\n")
33 writeDecodeTable(w, build(blackCodes[:], 0), "blackDecodeTable",
34 "// blackDecodeTable represents Tables 2 and 3 for a black run.\n")
35 writeMaxCodeLength(w, modeCodes[:], whiteCodes[:], blackCodes[:])
36 w.WriteString(encodeHeaderComment)
37 w.WriteString(bitStringTypeDef)
38 writeEncodeTable(w, modeCodes[:], "modeEncodeTable",
39 "// modeEncodeTable represents Table 1 and the End-of-Line code.\n")
40 writeEncodeTable(w, whiteCodes[:64], "whiteEncodeTable2",
41 "// whiteEncodeTable2 represents Table 2 for a white run.\n")
42 writeEncodeTable(w, whiteCodes[64:], "whiteEncodeTable3",
43 "// whiteEncodeTable3 represents Table 3 for a white run.\n")
44 writeEncodeTable(w, blackCodes[:64], "blackEncodeTable2",
45 "// blackEncodeTable2 represents Table 2 for a black run.\n")
46 writeEncodeTable(w, blackCodes[64:], "blackEncodeTable3",
47 "// blackEncodeTable3 represents Table 3 for a black run.\n")
48 finish(w, "table.go")
49 }
50
51 // Generate table_test.go.
52 {
53 w := &bytes.Buffer{}
54 w.WriteString(header)
55 finish(w, "table_test.go")
56 }
57}
58
59const header = `// generated by "go run gen.go". DO NOT EDIT.
60
61package ccitt
62
63`
64
65const decodeHeaderComment = `
66// Each decodeTable is represented by an array of [2]int16's: a binary tree.
67// Each array element (other than element 0, which means invalid) is a branch
68// node in that tree. The root node is always element 1 (the second element).
69//
70// To walk the tree, look at the next bit in the bit stream, using it to select
71// the first or second element of the [2]int16. If that int16 is 0, we have an
72// invalid code. If it is positive, go to that branch node. If it is negative,
73// then we have a leaf node, whose value is the bitwise complement (the ^
74// operator) of that int16.
75//
76// Comments above each decodeTable also show the same structure visually. The
77// "b123" lines show the 123'rd branch node. The "=XXXXX" lines show an invalid
78// code. The "=v1234" lines show a leaf node with value 1234. When reading the
79// bit stream, a 0 or 1 bit means to go up or down, as you move left to right.
80//
81// For example, in modeDecodeTable, branch node b005 is three steps up from the
82// root node, meaning that we have already seen "000". If the next bit is "0"
83// then we move to branch node b006. Otherwise, the next bit is "1", and we
84// move to the leaf node v0000 (also known as the modePass constant). Indeed,
85// the bits that encode modePass are "0001".
86//
87// Tables 1, 2 and 3 come from the "ITU-T Recommendation T.6: FACSIMILE CODING
88// SCHEMES AND CODING CONTROL FUNCTIONS FOR GROUP 4 FACSIMILE APPARATUS"
89// specification:
90//
91// https://www.itu.int/rec/dologin_pub.asp?lang=e&id=T-REC-T.6-198811-I!!PDF-E&type=items
92
93
94`
95
96const encodeHeaderComment = `
97// Each encodeTable is represented by an array of bitStrings.
98
99
100`
101
102type node struct {
103 children [2]*node
104 val uint32
105 branchIndex int32
106}
107
108func (n *node) isBranch() bool {
109 return (n != nil) && ((n.children[0] != nil) || (n.children[1] != nil))
110}
111
112func (n *node) String() string {
113 if n == nil {
114 return "0"
115 }
116 if n.branchIndex > 0 {
117 return fmt.Sprintf("%d", n.branchIndex)
118 }
119 return fmt.Sprintf("^%d", n.val)
120}
121
122func build(codes []code, prefixLen int) *node {
123 if len(codes) == 0 {
124 return nil
125 }
126
127 if prefixLen == len(codes[0].str) {
128 if len(codes) != 1 {
129 panic("ambiguous codes")
130 }
131 return &node{
132 val: codes[0].val,
133 }
134 }
135
136 childrenCodes := [2][]code{}
137 for _, code := range codes {
138 bit := code.str[prefixLen] & 1
139 childrenCodes[bit] = append(childrenCodes[bit], code)
140 }
141 return &node{
142 children: [2]*node{
143 build(childrenCodes[0], prefixLen+1),
144 build(childrenCodes[1], prefixLen+1),
145 },
146 }
147}
148
149func writeDecodeTable(w *bytes.Buffer, root *node, varName, comment string) {
150 assignBranchIndexes(root)
151
152 w.WriteString(comment)
153 w.WriteString("//\n")
154 writeComment(w, root, " ", false)
155 fmt.Fprintf(w, "var %s = [...][2]int16{\n", varName)
156 fmt.Fprintf(w, "0: {0, 0},\n")
157
158 // Walk the tree in breadth-first order.
159 for queue := []*node{root}; len(queue) > 0; {
160 n := queue[0]
161 queue = queue[1:]
162
163 if n.isBranch() {
164 fmt.Fprintf(w, "%d: {%v, %v},\n", n.branchIndex, n.children[0], n.children[1])
165 queue = append(queue, n.children[0], n.children[1])
166 }
167 }
168
169 fmt.Fprintf(w, "}\n\n")
170}
171
172const bitStringTypeDef = `
173// bitString is a pair of uint32 values representing a bit code.
174// The nBits low bits of bits make up the actual bit code.
175// Eg. bitString{0x0004, 8} represents the bitcode "00000100".
176type bitString struct {
177 bits uint32
178 nBits uint32
179}
180
181`
182
183func writeEncodeTable(w *bytes.Buffer, codes []code, varName, comment string) {
184 w.WriteString(comment)
185 fmt.Fprintf(w, "var %s = [...]bitString{\n", varName)
186 for i, code := range codes {
187 s := code.str
188 n := uint32(len(s))
189 c := uint32(0)
190 for j := uint32(0); j < n; j++ {
191 c |= uint32(s[j]&1) << (n - j - 1)
192 }
193 fmt.Fprintf(w, "%d: {0x%04x, %v}, // %q \n", i, c, n, s)
194 }
195 fmt.Fprintf(w, "}\n\n")
196}
197
198func assignBranchIndexes(root *node) {
199 // 0 is reserved for an invalid value.
200 branchIndex := int32(1)
201
202 // Walk the tree in breadth-first order.
203 for queue := []*node{root}; len(queue) > 0; {
204 n := queue[0]
205 queue = queue[1:]
206
207 if n.isBranch() {
208 n.branchIndex = branchIndex
209 branchIndex++
210 queue = append(queue, n.children[0], n.children[1])
211 }
212 }
213}
214
215func writeComment(w *bytes.Buffer, n *node, prefix string, down bool) {
216 if n.isBranch() {
217 prefixUp := prefix[:len(prefix)-2] + " | "
218 prefixDown := prefix + "| "
219 if down {
220 prefixUp, prefixDown = prefixDown, prefixUp
221 }
222
223 writeComment(w, n.children[0], prefixUp, false)
224 defer writeComment(w, n.children[1], prefixDown, true)
225
226 fmt.Fprintf(w, "// b%03d ", n.branchIndex)
227 } else {
228 fmt.Fprintf(w, "// ")
229 }
230
231 w.WriteString(prefix[:len(prefix)-2])
232
233 if n == nil {
234 fmt.Fprintf(w, "+=XXXXX\n")
235 return
236 }
237 if !n.isBranch() {
238 fmt.Fprintf(w, "+=v%04d\n", n.val)
239 return
240 }
241 w.WriteString("+-+\n")
242}
243
244func writeMaxCodeLength(w *bytes.Buffer, codesList ...[]code) {
245 maxCodeLength := 0
246 for _, codes := range codesList {
247 for _, code := range codes {
248 if n := len(code.str); maxCodeLength < n {
249 maxCodeLength = n
250 }
251 }
252 }
253 fmt.Fprintf(w, "const maxCodeLength = %d\n\n", maxCodeLength)
254}
255
256func finish(w *bytes.Buffer, filename string) {
257 copyPaste(w, filename)
258 if *debug {
259 os.Stdout.Write(w.Bytes())
260 return
261 }
262 out, err := format.Source(w.Bytes())
263 if err != nil {
264 log.Fatalf("format.Source: %v", err)
265 }
266 if err := ioutil.WriteFile(filename, out, 0660); err != nil {
267 log.Fatalf("ioutil.WriteFile: %v", err)
268 }
269}
270
271func copyPaste(w *bytes.Buffer, filename string) {
272 b, err := ioutil.ReadFile("gen.go")
273 if err != nil {
274 log.Fatalf("ioutil.ReadFile: %v", err)
275 }
276 begin := []byte("\n// COPY PASTE " + filename + " BEGIN\n\n")
277 end := []byte("\n// COPY PASTE " + filename + " END\n\n")
278
279 for len(b) > 0 {
280 i := bytes.Index(b, begin)
281 if i < 0 {
282 break
283 }
284 b = b[i:]
285
286 j := bytes.Index(b, end)
287 if j < 0 {
288 break
289 }
290 j += len(end)
291
292 w.Write(b[:j])
293 b = b[j:]
294 }
295}
296
297// COPY PASTE table.go BEGIN
298
299const (
300 modePass = iota // Pass
301 modeH // Horizontal
302 modeV0 // Vertical-0
303 modeVR1 // Vertical-Right-1
304 modeVR2 // Vertical-Right-2
305 modeVR3 // Vertical-Right-3
306 modeVL1 // Vertical-Left-1
307 modeVL2 // Vertical-Left-2
308 modeVL3 // Vertical-Left-3
309 modeExt // Extension
310 modeEOL // End-of-Line
311)
312
313// COPY PASTE table.go END
314
315// The data that is the rest of this file is taken from Tables 1, 2 and 3 from
316// the "ITU-T Recommendation T.6" spec.
317
318// COPY PASTE table_test.go BEGIN
319
320type code struct {
321 val uint32
322 str string
323}
324
325var modeCodes = []code{
326 {modePass, "0001"},
327 {modeH, "001"},
328 {modeV0, "1"},
329 {modeVR1, "011"},
330 {modeVR2, "000011"},
331 {modeVR3, "0000011"},
332 {modeVL1, "010"},
333 {modeVL2, "000010"},
334 {modeVL3, "0000010"},
335 {modeExt, "0000001"},
336
337 // End-of-Line is not in Table 1, but we look for it at the same time that
338 // we look for other mode codes.
339 {modeEOL, "000000000001"},
340}
341
342var whiteCodes = []code{
343 // Terminating codes (0-63).
344 {0x0000, "00110101"},
345 {0x0001, "000111"},
346 {0x0002, "0111"},
347 {0x0003, "1000"},
348 {0x0004, "1011"},
349 {0x0005, "1100"},
350 {0x0006, "1110"},
351 {0x0007, "1111"},
352 {0x0008, "10011"},
353 {0x0009, "10100"},
354 {0x000A, "00111"},
355 {0x000B, "01000"},
356 {0x000C, "001000"},
357 {0x000D, "000011"},
358 {0x000E, "110100"},
359 {0x000F, "110101"},
360 {0x0010, "101010"},
361 {0x0011, "101011"},
362 {0x0012, "0100111"},
363 {0x0013, "0001100"},
364 {0x0014, "0001000"},
365 {0x0015, "0010111"},
366 {0x0016, "0000011"},
367 {0x0017, "0000100"},
368 {0x0018, "0101000"},
369 {0x0019, "0101011"},
370 {0x001A, "0010011"},
371 {0x001B, "0100100"},
372 {0x001C, "0011000"},
373 {0x001D, "00000010"},
374 {0x001E, "00000011"},
375 {0x001F, "00011010"},
376 {0x0020, "00011011"},
377 {0x0021, "00010010"},
378 {0x0022, "00010011"},
379 {0x0023, "00010100"},
380 {0x0024, "00010101"},
381 {0x0025, "00010110"},
382 {0x0026, "00010111"},
383 {0x0027, "00101000"},
384 {0x0028, "00101001"},
385 {0x0029, "00101010"},
386 {0x002A, "00101011"},
387 {0x002B, "00101100"},
388 {0x002C, "00101101"},
389 {0x002D, "00000100"},
390 {0x002E, "00000101"},
391 {0x002F, "00001010"},
392 {0x0030, "00001011"},
393 {0x0031, "01010010"},
394 {0x0032, "01010011"},
395 {0x0033, "01010100"},
396 {0x0034, "01010101"},
397 {0x0035, "00100100"},
398 {0x0036, "00100101"},
399 {0x0037, "01011000"},
400 {0x0038, "01011001"},
401 {0x0039, "01011010"},
402 {0x003A, "01011011"},
403 {0x003B, "01001010"},
404 {0x003C, "01001011"},
405 {0x003D, "00110010"},
406 {0x003E, "00110011"},
407 {0x003F, "00110100"},
408
409 // Make-up codes between 64 and 1728.
410 {0x0040, "11011"},
411 {0x0080, "10010"},
412 {0x00C0, "010111"},
413 {0x0100, "0110111"},
414 {0x0140, "00110110"},
415 {0x0180, "00110111"},
416 {0x01C0, "01100100"},
417 {0x0200, "01100101"},
418 {0x0240, "01101000"},
419 {0x0280, "01100111"},
420 {0x02C0, "011001100"},
421 {0x0300, "011001101"},
422 {0x0340, "011010010"},
423 {0x0380, "011010011"},
424 {0x03C0, "011010100"},
425 {0x0400, "011010101"},
426 {0x0440, "011010110"},
427 {0x0480, "011010111"},
428 {0x04C0, "011011000"},
429 {0x0500, "011011001"},
430 {0x0540, "011011010"},
431 {0x0580, "011011011"},
432 {0x05C0, "010011000"},
433 {0x0600, "010011001"},
434 {0x0640, "010011010"},
435 {0x0680, "011000"},
436 {0x06C0, "010011011"},
437
438 // Make-up codes between 1792 and 2560.
439 {0x0700, "00000001000"},
440 {0x0740, "00000001100"},
441 {0x0780, "00000001101"},
442 {0x07C0, "000000010010"},
443 {0x0800, "000000010011"},
444 {0x0840, "000000010100"},
445 {0x0880, "000000010101"},
446 {0x08C0, "000000010110"},
447 {0x0900, "000000010111"},
448 {0x0940, "000000011100"},
449 {0x0980, "000000011101"},
450 {0x09C0, "000000011110"},
451 {0x0A00, "000000011111"},
452}
453
454var blackCodes = []code{
455 // Terminating codes (0-63).
456 {0x0000, "0000110111"},
457 {0x0001, "010"},
458 {0x0002, "11"},
459 {0x0003, "10"},
460 {0x0004, "011"},
461 {0x0005, "0011"},
462 {0x0006, "0010"},
463 {0x0007, "00011"},
464 {0x0008, "000101"},
465 {0x0009, "000100"},
466 {0x000A, "0000100"},
467 {0x000B, "0000101"},
468 {0x000C, "0000111"},
469 {0x000D, "00000100"},
470 {0x000E, "00000111"},
471 {0x000F, "000011000"},
472 {0x0010, "0000010111"},
473 {0x0011, "0000011000"},
474 {0x0012, "0000001000"},
475 {0x0013, "00001100111"},
476 {0x0014, "00001101000"},
477 {0x0015, "00001101100"},
478 {0x0016, "00000110111"},
479 {0x0017, "00000101000"},
480 {0x0018, "00000010111"},
481 {0x0019, "00000011000"},
482 {0x001A, "000011001010"},
483 {0x001B, "000011001011"},
484 {0x001C, "000011001100"},
485 {0x001D, "000011001101"},
486 {0x001E, "000001101000"},
487 {0x001F, "000001101001"},
488 {0x0020, "000001101010"},
489 {0x0021, "000001101011"},
490 {0x0022, "000011010010"},
491 {0x0023, "000011010011"},
492 {0x0024, "000011010100"},
493 {0x0025, "000011010101"},
494 {0x0026, "000011010110"},
495 {0x0027, "000011010111"},
496 {0x0028, "000001101100"},
497 {0x0029, "000001101101"},
498 {0x002A, "000011011010"},
499 {0x002B, "000011011011"},
500 {0x002C, "000001010100"},
501 {0x002D, "000001010101"},
502 {0x002E, "000001010110"},
503 {0x002F, "000001010111"},
504 {0x0030, "000001100100"},
505 {0x0031, "000001100101"},
506 {0x0032, "000001010010"},
507 {0x0033, "000001010011"},
508 {0x0034, "000000100100"},
509 {0x0035, "000000110111"},
510 {0x0036, "000000111000"},
511 {0x0037, "000000100111"},
512 {0x0038, "000000101000"},
513 {0x0039, "000001011000"},
514 {0x003A, "000001011001"},
515 {0x003B, "000000101011"},
516 {0x003C, "000000101100"},
517 {0x003D, "000001011010"},
518 {0x003E, "000001100110"},
519 {0x003F, "000001100111"},
520
521 // Make-up codes between 64 and 1728.
522 {0x0040, "0000001111"},
523 {0x0080, "000011001000"},
524 {0x00C0, "000011001001"},
525 {0x0100, "000001011011"},
526 {0x0140, "000000110011"},
527 {0x0180, "000000110100"},
528 {0x01C0, "000000110101"},
529 {0x0200, "0000001101100"},
530 {0x0240, "0000001101101"},
531 {0x0280, "0000001001010"},
532 {0x02C0, "0000001001011"},
533 {0x0300, "0000001001100"},
534 {0x0340, "0000001001101"},
535 {0x0380, "0000001110010"},
536 {0x03C0, "0000001110011"},
537 {0x0400, "0000001110100"},
538 {0x0440, "0000001110101"},
539 {0x0480, "0000001110110"},
540 {0x04C0, "0000001110111"},
541 {0x0500, "0000001010010"},
542 {0x0540, "0000001010011"},
543 {0x0580, "0000001010100"},
544 {0x05C0, "0000001010101"},
545 {0x0600, "0000001011010"},
546 {0x0640, "0000001011011"},
547 {0x0680, "0000001100100"},
548 {0x06C0, "0000001100101"},
549
550 // Make-up codes between 1792 and 2560.
551 {0x0700, "00000001000"},
552 {0x0740, "00000001100"},
553 {0x0780, "00000001101"},
554 {0x07C0, "000000010010"},
555 {0x0800, "000000010011"},
556 {0x0840, "000000010100"},
557 {0x0880, "000000010101"},
558 {0x08C0, "000000010110"},
559 {0x0900, "000000010111"},
560 {0x0940, "000000011100"},
561 {0x0980, "000000011101"},
562 {0x09C0, "000000011110"},
563 {0x0A00, "000000011111"},
564}
565
566// COPY PASTE table_test.go END
567
568// This final comment makes the "END" above be followed by "\n\n".