1
2
3
4
5
6
7 package main
8
9 import (
10 "bytes"
11 "flag"
12 "fmt"
13 "go/format"
14 "io/ioutil"
15 "log"
16 "os"
17 )
18
19 var debug = flag.Bool("debug", false, "")
20
21 func main() {
22 flag.Parse()
23
24
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
52 {
53 w := &bytes.Buffer{}
54 w.WriteString(header)
55 finish(w, "table_test.go")
56 }
57 }
58
59 const header = `// generated by "go run gen.go". DO NOT EDIT.
60
61 package ccitt
62
63 `
64
65 const 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
96 const encodeHeaderComment = `
97 // Each encodeTable is represented by an array of bitStrings.
98
99
100 `
101
102 type node struct {
103 children [2]*node
104 val uint32
105 branchIndex int32
106 }
107
108 func (n *node) isBranch() bool {
109 return (n != nil) && ((n.children[0] != nil) || (n.children[1] != nil))
110 }
111
112 func (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
122 func 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
149 func 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
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
172 const 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".
176 type bitString struct {
177 bits uint32
178 nBits uint32
179 }
180
181 `
182
183 func 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
198 func assignBranchIndexes(root *node) {
199
200 branchIndex := int32(1)
201
202
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
215 func 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, "//\tb%03d ", n.branchIndex)
227 } else {
228 fmt.Fprintf(w, "//\t ")
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
244 func 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
256 func 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
271 func 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
298
299 const (
300 modePass = iota
301 modeH
302 modeV0
303 modeVR1
304 modeVR2
305 modeVR3
306 modeVL1
307 modeVL2
308 modeVL3
309 modeExt
310 )
311
312
313
314
315
316
317
318
319 type code struct {
320 val uint32
321 str string
322 }
323
324 var modeCodes = []code{
325 {modePass, "0001"},
326 {modeH, "001"},
327 {modeV0, "1"},
328 {modeVR1, "011"},
329 {modeVR2, "000011"},
330 {modeVR3, "0000011"},
331 {modeVL1, "010"},
332 {modeVL2, "000010"},
333 {modeVL3, "0000010"},
334 {modeExt, "0000001"},
335 }
336
337 var whiteCodes = []code{
338
339 {0x0000, "00110101"},
340 {0x0001, "000111"},
341 {0x0002, "0111"},
342 {0x0003, "1000"},
343 {0x0004, "1011"},
344 {0x0005, "1100"},
345 {0x0006, "1110"},
346 {0x0007, "1111"},
347 {0x0008, "10011"},
348 {0x0009, "10100"},
349 {0x000A, "00111"},
350 {0x000B, "01000"},
351 {0x000C, "001000"},
352 {0x000D, "000011"},
353 {0x000E, "110100"},
354 {0x000F, "110101"},
355 {0x0010, "101010"},
356 {0x0011, "101011"},
357 {0x0012, "0100111"},
358 {0x0013, "0001100"},
359 {0x0014, "0001000"},
360 {0x0015, "0010111"},
361 {0x0016, "0000011"},
362 {0x0017, "0000100"},
363 {0x0018, "0101000"},
364 {0x0019, "0101011"},
365 {0x001A, "0010011"},
366 {0x001B, "0100100"},
367 {0x001C, "0011000"},
368 {0x001D, "00000010"},
369 {0x001E, "00000011"},
370 {0x001F, "00011010"},
371 {0x0020, "00011011"},
372 {0x0021, "00010010"},
373 {0x0022, "00010011"},
374 {0x0023, "00010100"},
375 {0x0024, "00010101"},
376 {0x0025, "00010110"},
377 {0x0026, "00010111"},
378 {0x0027, "00101000"},
379 {0x0028, "00101001"},
380 {0x0029, "00101010"},
381 {0x002A, "00101011"},
382 {0x002B, "00101100"},
383 {0x002C, "00101101"},
384 {0x002D, "00000100"},
385 {0x002E, "00000101"},
386 {0x002F, "00001010"},
387 {0x0030, "00001011"},
388 {0x0031, "01010010"},
389 {0x0032, "01010011"},
390 {0x0033, "01010100"},
391 {0x0034, "01010101"},
392 {0x0035, "00100100"},
393 {0x0036, "00100101"},
394 {0x0037, "01011000"},
395 {0x0038, "01011001"},
396 {0x0039, "01011010"},
397 {0x003A, "01011011"},
398 {0x003B, "01001010"},
399 {0x003C, "01001011"},
400 {0x003D, "00110010"},
401 {0x003E, "00110011"},
402 {0x003F, "00110100"},
403
404
405 {0x0040, "11011"},
406 {0x0080, "10010"},
407 {0x00C0, "010111"},
408 {0x0100, "0110111"},
409 {0x0140, "00110110"},
410 {0x0180, "00110111"},
411 {0x01C0, "01100100"},
412 {0x0200, "01100101"},
413 {0x0240, "01101000"},
414 {0x0280, "01100111"},
415 {0x02C0, "011001100"},
416 {0x0300, "011001101"},
417 {0x0340, "011010010"},
418 {0x0380, "011010011"},
419 {0x03C0, "011010100"},
420 {0x0400, "011010101"},
421 {0x0440, "011010110"},
422 {0x0480, "011010111"},
423 {0x04C0, "011011000"},
424 {0x0500, "011011001"},
425 {0x0540, "011011010"},
426 {0x0580, "011011011"},
427 {0x05C0, "010011000"},
428 {0x0600, "010011001"},
429 {0x0640, "010011010"},
430 {0x0680, "011000"},
431 {0x06C0, "010011011"},
432
433
434 {0x0700, "00000001000"},
435 {0x0740, "00000001100"},
436 {0x0780, "00000001101"},
437 {0x07C0, "000000010010"},
438 {0x0800, "000000010011"},
439 {0x0840, "000000010100"},
440 {0x0880, "000000010101"},
441 {0x08C0, "000000010110"},
442 {0x0900, "000000010111"},
443 {0x0940, "000000011100"},
444 {0x0980, "000000011101"},
445 {0x09C0, "000000011110"},
446 {0x0A00, "000000011111"},
447 }
448
449 var blackCodes = []code{
450
451 {0x0000, "0000110111"},
452 {0x0001, "010"},
453 {0x0002, "11"},
454 {0x0003, "10"},
455 {0x0004, "011"},
456 {0x0005, "0011"},
457 {0x0006, "0010"},
458 {0x0007, "00011"},
459 {0x0008, "000101"},
460 {0x0009, "000100"},
461 {0x000A, "0000100"},
462 {0x000B, "0000101"},
463 {0x000C, "0000111"},
464 {0x000D, "00000100"},
465 {0x000E, "00000111"},
466 {0x000F, "000011000"},
467 {0x0010, "0000010111"},
468 {0x0011, "0000011000"},
469 {0x0012, "0000001000"},
470 {0x0013, "00001100111"},
471 {0x0014, "00001101000"},
472 {0x0015, "00001101100"},
473 {0x0016, "00000110111"},
474 {0x0017, "00000101000"},
475 {0x0018, "00000010111"},
476 {0x0019, "00000011000"},
477 {0x001A, "000011001010"},
478 {0x001B, "000011001011"},
479 {0x001C, "000011001100"},
480 {0x001D, "000011001101"},
481 {0x001E, "000001101000"},
482 {0x001F, "000001101001"},
483 {0x0020, "000001101010"},
484 {0x0021, "000001101011"},
485 {0x0022, "000011010010"},
486 {0x0023, "000011010011"},
487 {0x0024, "000011010100"},
488 {0x0025, "000011010101"},
489 {0x0026, "000011010110"},
490 {0x0027, "000011010111"},
491 {0x0028, "000001101100"},
492 {0x0029, "000001101101"},
493 {0x002A, "000011011010"},
494 {0x002B, "000011011011"},
495 {0x002C, "000001010100"},
496 {0x002D, "000001010101"},
497 {0x002E, "000001010110"},
498 {0x002F, "000001010111"},
499 {0x0030, "000001100100"},
500 {0x0031, "000001100101"},
501 {0x0032, "000001010010"},
502 {0x0033, "000001010011"},
503 {0x0034, "000000100100"},
504 {0x0035, "000000110111"},
505 {0x0036, "000000111000"},
506 {0x0037, "000000100111"},
507 {0x0038, "000000101000"},
508 {0x0039, "000001011000"},
509 {0x003A, "000001011001"},
510 {0x003B, "000000101011"},
511 {0x003C, "000000101100"},
512 {0x003D, "000001011010"},
513 {0x003E, "000001100110"},
514 {0x003F, "000001100111"},
515
516
517 {0x0040, "0000001111"},
518 {0x0080, "000011001000"},
519 {0x00C0, "000011001001"},
520 {0x0100, "000001011011"},
521 {0x0140, "000000110011"},
522 {0x0180, "000000110100"},
523 {0x01C0, "000000110101"},
524 {0x0200, "0000001101100"},
525 {0x0240, "0000001101101"},
526 {0x0280, "0000001001010"},
527 {0x02C0, "0000001001011"},
528 {0x0300, "0000001001100"},
529 {0x0340, "0000001001101"},
530 {0x0380, "0000001110010"},
531 {0x03C0, "0000001110011"},
532 {0x0400, "0000001110100"},
533 {0x0440, "0000001110101"},
534 {0x0480, "0000001110110"},
535 {0x04C0, "0000001110111"},
536 {0x0500, "0000001010010"},
537 {0x0540, "0000001010011"},
538 {0x0580, "0000001010100"},
539 {0x05C0, "0000001010101"},
540 {0x0600, "0000001011010"},
541 {0x0640, "0000001011011"},
542 {0x0680, "0000001100100"},
543 {0x06C0, "0000001100101"},
544
545
546 {0x0700, "00000001000"},
547 {0x0740, "00000001100"},
548 {0x0780, "00000001101"},
549 {0x07C0, "000000010010"},
550 {0x0800, "000000010011"},
551 {0x0840, "000000010100"},
552 {0x0880, "000000010101"},
553 {0x08C0, "000000010110"},
554 {0x0900, "000000010111"},
555 {0x0940, "000000011100"},
556 {0x0980, "000000011101"},
557 {0x09C0, "000000011110"},
558 {0x0A00, "000000011111"},
559 }
560
561
562
563
564
View as plain text