1// Copyright 2018 The Wuffs Authors. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// https://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15// +build ignore 16 17package main 18 19// make-artificial.go makes test data in various formats. 20// 21// See test/data/artificial/*.make.txt for examples. 22// 23// Usage: go run make-artificial.go < foo.make.txt 24 25import ( 26 "bytes" 27 "compress/lzw" 28 "fmt" 29 "io/ioutil" 30 "os" 31 "strconv" 32 "strings" 33) 34 35type stateFunc func(line string) (stateFunc, error) 36 37type repeat struct { 38 count uint32 39 remaining string 40} 41 42var ( 43 state stateFunc 44 repeats []repeat 45 out []byte 46 formats = map[string]stateFunc{} 47) 48 49func main() { 50 if err := main1(); err != nil { 51 os.Stderr.WriteString(err.Error() + "\n") 52 os.Exit(1) 53 } 54} 55 56func main1() error { 57 stdin, err := ioutil.ReadAll(os.Stdin) 58 if err != nil { 59 return err 60 } 61 s := string(stdin) 62 for remaining := ""; len(s) > 0; s, remaining = remaining, "" { 63 if i := strings.IndexByte(s, '\n'); i >= 0 { 64 s, remaining = s[:i], s[i+1:] 65 } 66 s = strings.TrimSpace(s) 67 if s == "" || s[0] == '#' { 68 continue 69 } 70 71 if state == nil { 72 const m = "make " 73 if !strings.HasPrefix(s, m) { 74 return fmt.Errorf(`input must start with "make foo"`) 75 } 76 s = s[len(m):] 77 state = formats[s] 78 if state == nil { 79 return fmt.Errorf("unsupported format %q", s) 80 } 81 continue 82 } 83 84 const rep = "repeat " 85 if strings.HasPrefix(s, rep) { 86 args := s[len(rep):] 87 count, args, ok := parseNum(args) 88 if !ok || count <= 0 || args != "[" { 89 return fmt.Errorf("bad repeat command: %q", s) 90 } 91 repeats = append(repeats, repeat{ 92 count: count, 93 remaining: remaining, 94 }) 95 continue 96 } 97 98 if s == "]" { 99 if len(repeats) <= 0 { 100 return fmt.Errorf(`unbalanced close-repeat command: "]"`) 101 } 102 i := len(repeats) - 1 103 repeats[i].count-- 104 if repeats[i].count == 0 { 105 repeats = repeats[:i] 106 } else { 107 remaining = repeats[i].remaining 108 } 109 continue 110 } 111 112 state, err = state(s) 113 if err != nil { 114 return err 115 } 116 if state == nil { 117 return fmt.Errorf("bad state transition") 118 } 119 } 120 121 if state == nil { 122 return fmt.Errorf("no 'make' line") 123 } else { 124 state, err = state("") 125 if err != nil { 126 return err 127 } 128 } 129 130 _, err = os.Stdout.Write(out) 131 return err 132} 133 134// ---- 135 136func appendU16LE(b []byte, u uint16) []byte { 137 return append(b, uint8(u), uint8(u>>8)) 138} 139 140func log2(u uint32) (i int32) { 141 for i, pow := uint32(0), uint32(1); i < 32; i, pow = i+1, pow<<1 { 142 if u == pow { 143 return int32(i) 144 } 145 if u < pow { 146 break 147 } 148 } 149 return -1 150} 151 152func parseHex(s string) (num uint32, remaining string, ok bool) { 153 if i := strings.IndexByte(s, ' '); i >= 0 { 154 s, remaining = s[:i], s[i+1:] 155 for len(remaining) > 0 && remaining[0] == ' ' { 156 remaining = remaining[1:] 157 } 158 } 159 160 if len(s) < 2 || s[0] != '0' || s[1] != 'x' { 161 return 0, "", false 162 } 163 s = s[2:] 164 165 u, err := strconv.ParseUint(s, 16, 32) 166 if err != nil { 167 return 0, "", false 168 } 169 return uint32(u), remaining, true 170} 171 172func parseNum(s string) (num uint32, remaining string, ok bool) { 173 if i := strings.IndexByte(s, ' '); i >= 0 { 174 s, remaining = s[:i], s[i+1:] 175 for len(remaining) > 0 && remaining[0] == ' ' { 176 remaining = remaining[1:] 177 } 178 } 179 180 u, err := strconv.ParseUint(s, 10, 32) 181 if err != nil { 182 return 0, "", false 183 } 184 return uint32(u), remaining, true 185} 186 187func reverse(x uint32, n uint32) uint32 { 188 x = uint32(reverse8[0xFF&(x>>0)])<<24 | 189 uint32(reverse8[0xFF&(x>>8)])<<16 | 190 uint32(reverse8[0xFF&(x>>16)])<<8 | 191 uint32(reverse8[0xFF&(x>>24)])<<0 192 return x >> (32 - n) 193} 194 195var reverse8 = [256]byte{ 196 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, // 0x00 - 0x07 197 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, // 0x08 - 0x0F 198 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, // 0x10 - 0x17 199 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, // 0x18 - 0x1F 200 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, // 0x20 - 0x27 201 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, // 0x28 - 0x2F 202 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, // 0x30 - 0x37 203 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, // 0x38 - 0x3F 204 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, // 0x40 - 0x47 205 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, // 0x48 - 0x4F 206 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, // 0x50 - 0x57 207 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, // 0x58 - 0x5F 208 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, // 0x60 - 0x67 209 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, // 0x68 - 0x6F 210 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, // 0x70 - 0x77 211 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, // 0x78 - 0x7F 212 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, // 0x80 - 0x87 213 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, // 0x88 - 0x8F 214 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, // 0x90 - 0x97 215 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, // 0x98 - 0x9F 216 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, // 0xA0 - 0xA7 217 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, // 0xA8 - 0xAF 218 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, // 0xB0 - 0xB7 219 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, // 0xB8 - 0xBF 220 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, // 0xC0 - 0xC7 221 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, // 0xC8 - 0xCF 222 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, // 0xD0 - 0xD7 223 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, // 0xD8 - 0xDF 224 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, // 0xE0 - 0xE7 225 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, // 0xE8 - 0xEF 226 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, // 0xF0 - 0xF7 227 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF, // 0xF8 - 0xFF 228} 229 230// ---- 231 232func init() { 233 formats["deflate"] = stateDeflate 234} 235 236var deflateCodeOrder = [19]uint32{ 237 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15, 238} 239 240type deflateHuffmanTable map[uint32]string 241 242var deflateGlobals struct { 243 bncData []byte 244 stream deflateBitStream 245 246 // Dynamic Huffman state. 247 numLCodes uint32 248 numDCodes uint32 249 numCLCodeLengths uint32 250 whichHuffman uint32 251 // 0=Unused, 1=CodeLength, 2=Length/Literal, 3=Distance. 252 huffmans [4]deflateHuffmanTable 253} 254 255func deflateGlobalsClearDynamicHuffmanState() { 256 deflateGlobals.numLCodes = 0 257 deflateGlobals.numDCodes = 0 258 deflateGlobals.numCLCodeLengths = 0 259 deflateGlobals.whichHuffman = 0 260 deflateGlobals.huffmans = [4]deflateHuffmanTable{} 261} 262 263func deflateGlobalsWriteDynamicHuffmanTables() error { 264 g := &deflateGlobals 265 if (g.numLCodes < 257) || (257+31 < g.numLCodes) { 266 return fmt.Errorf("bad numLCodes: %d", g.numLCodes) 267 } 268 g.stream.writeBits(g.numLCodes-257, 5) 269 if (g.numDCodes < 1) || (1+31 < g.numDCodes) { 270 return fmt.Errorf("bad numDCodes: %d", g.numDCodes) 271 } 272 g.stream.writeBits(g.numDCodes-1, 5) 273 if (g.numCLCodeLengths < 4) || (4+15 < g.numCLCodeLengths) { 274 return fmt.Errorf("bad numCLCodeLengths: %d", g.numCLCodeLengths) 275 } 276 g.stream.writeBits(g.numCLCodeLengths-4, 4) 277 278 // Write the Huffman table for CodeLength. 279 { 280 for i := uint32(0); i < g.numCLCodeLengths; i++ { 281 n := len(g.huffmans[1][deflateCodeOrder[i]]) 282 g.stream.writeBits(uint32(n), 3) 283 } 284 for i := g.numCLCodeLengths; i < uint32(len(deflateCodeOrder)); i++ { 285 n := len(g.huffmans[1][deflateCodeOrder[i]]) 286 if n > 0 { 287 return fmt.Errorf("short numCLCodeLengths: %d", g.numCLCodeLengths) 288 } 289 } 290 } 291 292 // Write the Huffman tables for Length/Literal and Distance. 293 { 294 numZeroes := uint32(0) 295 for i := uint32(0); i < g.numLCodes+g.numDCodes; i++ { 296 s := "" 297 if i < g.numLCodes { 298 s = g.huffmans[2][i] 299 } else { 300 s = g.huffmans[3][i-g.numLCodes] 301 } 302 if s == "" { 303 numZeroes++ 304 continue 305 } 306 307 if err := deflateGlobalsWriteDynamicHuffmanZeroes(numZeroes); err != nil { 308 return err 309 } 310 numZeroes = 0 311 312 deflateGlobalsWriteDynamicHuffmanBits(g.huffmans[1][uint32(len(s))]) 313 } 314 if err := deflateGlobalsWriteDynamicHuffmanZeroes(numZeroes); err != nil { 315 return err 316 } 317 } 318 319 return nil 320} 321 322func deflateGlobalsWriteDynamicHuffmanZeroes(numZeroes uint32) error { 323 g := &deflateGlobals 324 if numZeroes == 0 { 325 return nil 326 } 327 328 if s := g.huffmans[1][18]; s != "" { 329 for numZeroes >= 11 { 330 extra := numZeroes - 11 331 if extra > 127 { 332 extra = 127 333 } 334 deflateGlobalsWriteDynamicHuffmanBits(s) 335 g.stream.writeBits(extra, 7) 336 numZeroes -= 11 + extra 337 } 338 } 339 340 if s := g.huffmans[1][17]; s != "" { 341 for numZeroes >= 3 { 342 extra := numZeroes - 3 343 if extra > 7 { 344 extra = 7 345 } 346 deflateGlobalsWriteDynamicHuffmanBits(s) 347 g.stream.writeBits(extra, 3) 348 numZeroes -= 3 + extra 349 } 350 } 351 352 if s := g.huffmans[1][0]; s != "" { 353 for ; numZeroes > 0; numZeroes-- { 354 deflateGlobalsWriteDynamicHuffmanBits(s) 355 } 356 } 357 358 if numZeroes > 0 { 359 return fmt.Errorf("could not write a run of zero-valued code lengths") 360 } 361 return nil 362} 363 364func deflateGlobalsWriteDynamicHuffmanBits(s string) { 365 g := &deflateGlobals 366 for i := 0; i < len(s); i++ { 367 g.stream.writeBits(uint32(s[i]&1), 1) 368 } 369} 370 371func parseDeflateWhichHuffman(s string) (num uint32, remaining string, ok bool) { 372 if i := strings.IndexByte(s, ' '); i >= 0 { 373 s, remaining = s[:i], s[i+1:] 374 for len(remaining) > 0 && remaining[0] == ' ' { 375 remaining = remaining[1:] 376 } 377 } 378 379 switch s { 380 case "CodeLength": 381 return 1, remaining, true 382 case "Length/Literal": 383 return 2, remaining, true 384 case "Distance": 385 return 3, remaining, true 386 } 387 return 0, "", false 388} 389 390func stateDeflate(line string) (stateFunc, error) { 391 g := &deflateGlobals 392 const ( 393 cmdB = "bytes " 394 cmdBDH = "blockDynamicHuffman " 395 cmdBFH = "blockFixedHuffman " 396 cmdBNC = "blockNoCompression " 397 ) 398 bits := uint32(0) 399 s := "" 400 401 retState := stateFunc(nil) 402 switch { 403 case line == "": 404 g.stream.flush() 405 return stateDeflate, nil 406 407 case strings.HasPrefix(line, cmdB): 408 s := line[len(cmdB):] 409 for s != "" { 410 x, ok := uint32(0), false 411 x, s, ok = parseHex(s) 412 if !ok { 413 return nil, fmt.Errorf("bad stateDeflate command: %q", line) 414 } 415 out = append(out, uint8(x)) 416 } 417 return stateDeflate, nil 418 419 case strings.HasPrefix(line, cmdBNC): 420 s = line[len(cmdBNC):] 421 retState = stateDeflateNoCompression 422 bits |= 0 << 1 423 case strings.HasPrefix(line, cmdBFH): 424 s = line[len(cmdBFH):] 425 retState = stateDeflateFixedHuffman 426 bits |= 1 << 1 427 case strings.HasPrefix(line, cmdBDH): 428 s = line[len(cmdBDH):] 429 retState = stateDeflateDynamicHuffman 430 bits |= 2 << 1 431 default: 432 return nil, fmt.Errorf("bad stateDeflate command: %q", line) 433 } 434 435 switch s { 436 case "(final) {": 437 bits |= 1 438 case "(nonFinal) {": 439 // No-op. 440 default: 441 return nil, fmt.Errorf("bad stateDeflate command: %q", line) 442 } 443 444 g.stream.writeBits(bits, 3) 445 return retState, nil 446} 447 448func stateDeflateNoCompression(line string) (stateFunc, error) { 449 g := &deflateGlobals 450 if line == "}" { 451 if len(g.bncData) > 0xFFFF { 452 return nil, fmt.Errorf("bncData is too long") 453 } 454 n := uint32(len(g.bncData)) 455 g.stream.flush() 456 g.stream.writeBits(n, 16) 457 g.stream.writeBits(0xFFFF-n, 16) 458 g.stream.writeBytes(g.bncData) 459 g.bncData = g.bncData[:0] 460 return stateDeflate, nil 461 } 462 463 if lit, ok := deflateParseLiteral(line); ok { 464 g.bncData = append(g.bncData, lit...) 465 return stateDeflateNoCompression, nil 466 } 467 468 return nil, fmt.Errorf("bad blockNoCompression command: %q", line) 469} 470 471func stateDeflateFixedHuffman(line string) (stateFunc, error) { 472 g := &deflateGlobals 473 if line == "}" { 474 return stateDeflate, nil 475 } 476 477 if line == "endOfBlock" { 478 g.stream.writeBits(0, 7) 479 return stateDeflateFixedHuffman, nil 480 } 481 482 if lit, ok := deflateParseLiteral(line); ok { 483 for i := 0; i < len(lit); i++ { 484 g.stream.writeFixedHuffmanLCode(uint32(lit[i])) 485 } 486 return stateDeflateFixedHuffman, nil 487 } 488 489 if line == "len 3 distCode 31" { 490 lCode, lExtra, lNExtra := deflateEncodeLength(3) 491 g.stream.writeFixedHuffmanLCode(lCode) 492 g.stream.writeBits(lExtra, lNExtra) 493 dCode, dExtra, dNExtra := uint32(31), uint32(0), uint32(0) 494 g.stream.writeBits(reverse(dCode, 5), 5) 495 g.stream.writeBits(dExtra, dNExtra) 496 return stateDeflateFixedHuffman, nil 497 } 498 499 if l, d, ok := deflateParseLenDist(line); ok { 500 lCode, lExtra, lNExtra := deflateEncodeLength(l) 501 g.stream.writeFixedHuffmanLCode(lCode) 502 g.stream.writeBits(lExtra, lNExtra) 503 dCode, dExtra, dNExtra := deflateEncodeDistance(d) 504 g.stream.writeBits(reverse(dCode, 5), 5) 505 g.stream.writeBits(dExtra, dNExtra) 506 return stateDeflateFixedHuffman, nil 507 } 508 509 return nil, fmt.Errorf("bad stateDeflateFixedHuffman command: %q", line) 510} 511 512func stateDeflateDynamicHuffman(line string) (stateFunc, error) { 513 g := &deflateGlobals 514 const ( 515 cmdH = "huffman " 516 cmdNCLCL = "numCLCodeLengths " 517 cmdNDC = "numDCodes " 518 cmdNLC = "numLCodes " 519 ) 520 switch { 521 case line == "}": 522 deflateGlobalsClearDynamicHuffmanState() 523 return stateDeflate, nil 524 525 case strings.HasPrefix(line, cmdH): 526 s := line[len(cmdH):] 527 n, s, ok := parseDeflateWhichHuffman(s) 528 if !ok { 529 break 530 } 531 g.whichHuffman = n 532 return stateDeflateDynamicHuffmanHuffman, nil 533 534 case strings.HasPrefix(line, cmdNLC): 535 s := line[len(cmdNLC):] 536 n, s, ok := parseNum(s) 537 if !ok { 538 break 539 } 540 g.numLCodes = n 541 return stateDeflateDynamicHuffman, nil 542 543 case strings.HasPrefix(line, cmdNDC): 544 s := line[len(cmdNDC):] 545 n, s, ok := parseNum(s) 546 if !ok { 547 break 548 } 549 g.numDCodes = n 550 return stateDeflateDynamicHuffman, nil 551 552 case strings.HasPrefix(line, cmdNCLCL): 553 s := line[len(cmdNCLCL):] 554 n, s, ok := parseNum(s) 555 if !ok { 556 break 557 } 558 g.numCLCodeLengths = n 559 return stateDeflateDynamicHuffman, nil 560 } 561 562 if lit, ok := deflateParseLiteral(line); ok { 563 for i := 0; i < len(lit); i++ { 564 s := g.huffmans[2][uint32(lit[i])] 565 if s == "" { 566 return nil, fmt.Errorf("no code for literal %q (%d)", lit[i:i+1], lit[i]) 567 } 568 deflateGlobalsWriteDynamicHuffmanBits(s) 569 } 570 return stateDeflateDynamicHuffman, nil 571 } else if line == "endOfBlock" { 572 s := g.huffmans[2][256] 573 if s == "" { 574 return nil, fmt.Errorf("no code for end-of-block (256)") 575 } 576 deflateGlobalsWriteDynamicHuffmanBits(s) 577 return stateDeflateDynamicHuffman, nil 578 } 579 580 return nil, fmt.Errorf("bad stateDeflateDynamicHuffman command: %q", line) 581} 582 583func stateDeflateDynamicHuffmanHuffman(line string) (stateFunc, error) { 584 g := &deflateGlobals 585outer: 586 switch { 587 case line == "}": 588 g.whichHuffman = 0 589 590 // If we have all three Huffman tables, write them. 591 for i := 1; ; i++ { 592 if i == 4 { 593 if err := deflateGlobalsWriteDynamicHuffmanTables(); err != nil { 594 return nil, err 595 } 596 break 597 } 598 if g.huffmans[i] == nil { 599 break 600 } 601 } 602 603 return stateDeflateDynamicHuffman, nil 604 605 default: 606 s := line 607 n, s, ok := parseNum(s) 608 if !ok || s == "" { 609 break 610 } 611 for i := 0; i < len(s); i++ { 612 if c := s[i]; c != '0' && c != '1' { 613 break outer 614 } 615 } 616 if g.huffmans[g.whichHuffman] == nil { 617 g.huffmans[g.whichHuffman] = deflateHuffmanTable{} 618 } 619 g.huffmans[g.whichHuffman][n] = s 620 return stateDeflateDynamicHuffmanHuffman, nil 621 } 622 623 return nil, fmt.Errorf("bad stateDeflateDynamicHuffmanHuffman command: %q", line) 624} 625 626type deflateBitStream struct { 627 bits uint32 628 nBits uint32 // Always within [0, 7]. 629} 630 631// writeBits writes the low n bits of b to z. 632func (z *deflateBitStream) writeBits(b uint32, n uint32) { 633 if n > 24 { 634 panic("writeBits: n is too large") 635 } 636 z.bits |= b << z.nBits 637 z.nBits += n 638 for z.nBits >= 8 { 639 out = append(out, uint8(z.bits)) 640 z.bits >>= 8 641 z.nBits -= 8 642 } 643} 644 645func (z *deflateBitStream) writeBytes(b []byte) { 646 z.flush() 647 out = append(out, b...) 648} 649 650func (z *deflateBitStream) writeFixedHuffmanLCode(lCode uint32) { 651 switch { 652 case lCode < 144: // 0b._0011_0000 through 0b._1011_1111 653 lCode += 0x030 654 z.writeBits(reverse(lCode, 8), 8) 655 case lCode < 256: // 0b1_1001_0000 through 0b1_1111_1111 656 lCode += 0x190 - 144 657 z.writeBits(reverse(lCode, 9), 9) 658 case lCode < 280: // 0b._.000_0000 through 0b._.001_0111 659 lCode -= 256 - 0x000 660 z.writeBits(reverse(lCode, 7), 7) 661 default: // 0b._1100_0000 through 0b._1100_0111 662 lCode -= 280 - 0x0C0 663 z.writeBits(reverse(lCode, 8), 8) 664 } 665} 666 667func (z *deflateBitStream) flush() { 668 if z.nBits > 0 { 669 out = append(out, uint8(z.bits)) 670 z.bits = 0 671 z.nBits = 0 672 } 673} 674 675func deflateEncodeLength(l uint32) (code uint32, extra uint32, nExtra uint32) { 676 switch { 677 case l < 3: 678 // No-op. 679 case l < 11: 680 l -= 3 681 return (l >> 0) + 257, l & 0x0000, 0 682 case l < 19: 683 l -= 11 684 return (l >> 1) + 265, l & 0x0001, 1 685 case l < 35: 686 l -= 19 687 return (l >> 2) + 269, l & 0x0003, 2 688 case l < 67: 689 l -= 35 690 return (l >> 3) + 273, l & 0x0007, 3 691 case l < 131: 692 l -= 67 693 return (l >> 4) + 277, l & 0x000F, 4 694 case l < 258: 695 l -= 131 696 return (l >> 5) + 281, l & 0x001F, 5 697 case l == 258: 698 return 285, 0, 0 699 } 700 panic(fmt.Sprintf("deflateEncodeLength: l=%d", l)) 701} 702 703func deflateEncodeDistance(d uint32) (code uint32, extra uint32, nExtra uint32) { 704 switch { 705 case d < 1: 706 // No-op. 707 case d < 5: 708 d -= 1 709 return (d >> 0) + 0, d & 0x0000, 0 710 case d < 9: 711 d -= 5 712 return (d >> 1) + 4, d & 0x0001, 1 713 case d < 17: 714 d -= 9 715 return (d >> 2) + 6, d & 0x0003, 2 716 case d < 33: 717 d -= 17 718 return (d >> 3) + 8, d & 0x0007, 3 719 case d < 65: 720 d -= 33 721 return (d >> 4) + 10, d & 0x000F, 4 722 case d < 129: 723 d -= 65 724 return (d >> 5) + 12, d & 0x001F, 5 725 case d < 257: 726 d -= 129 727 return (d >> 6) + 14, d & 0x003F, 6 728 case d < 513: 729 d -= 257 730 return (d >> 7) + 16, d & 0x007F, 7 731 case d < 1025: 732 d -= 513 733 return (d >> 8) + 18, d & 0x00FF, 8 734 case d < 2049: 735 d -= 1025 736 return (d >> 9) + 20, d & 0x01FF, 9 737 case d < 4097: 738 d -= 2049 739 return (d >> 10) + 22, d & 0x03FF, 10 740 case d < 8193: 741 d -= 4097 742 return (d >> 11) + 24, d & 0x07FF, 11 743 case d < 16385: 744 d -= 8193 745 return (d >> 12) + 26, d & 0x0FFF, 12 746 case d < 32769: 747 d -= 16385 748 return (d >> 13) + 28, d & 0x1FFF, 13 749 } 750 panic(fmt.Sprintf("deflateEncodeDistance: d=%d", d)) 751} 752 753func deflateParseLiteral(s string) (lit string, ok bool) { 754 // TODO: support "\xAB" escape codes in the script? 755 const ( 756 prefix = `literal "` 757 suffix = `"` 758 ) 759 if strings.HasPrefix(s, prefix) { 760 s = s[len(prefix):] 761 if strings.HasSuffix(s, suffix) { 762 return s[:len(s)-len(suffix)], true 763 } 764 } 765 return "", false 766} 767 768func deflateParseLenDist(line string) (l uint32, d uint32, ok bool) { 769 const ( 770 lStr = "len " 771 dStr = "dist " 772 ) 773 s := line 774 if strings.HasPrefix(s, lStr) { 775 s = s[len(lStr):] 776 if l, s, ok := parseNum(s); ok && 3 <= l && l <= 258 { 777 if strings.HasPrefix(s, dStr) { 778 s = s[len(dStr):] 779 if d, s, ok := parseNum(s); ok && 1 <= d && d <= 32768 && s == "" { 780 return l, d, true 781 } 782 } 783 } 784 } 785 return 0, 0, false 786} 787 788// ---- 789 790func init() { 791 formats["gif"] = stateGif 792} 793 794var gifGlobals struct { 795 imageWidth uint32 796 imageHeight uint32 797 imageBackgroundColorIndex uint32 798 799 frameLeft uint32 800 frameTop uint32 801 frameWidth uint32 802 frameHeight uint32 803 804 globalPalette [][4]uint8 805 localPalette [][4]uint8 806} 807 808func stateGif(line string) (stateFunc, error) { 809 const ( 810 cmdB = "bytes " 811 cmdGC = "graphicControl " 812 cmdL = "lzw " 813 cmdLC = "loopCount " 814 ) 815outer: 816 switch { 817 case line == "": 818 return stateGif, nil 819 820 case line == "frame {": 821 gifGlobals.localPalette = nil 822 out = append(out, 0x2C) 823 return stateGifFrame, nil 824 825 case line == "header": 826 out = append(out, "GIF89a"...) 827 return stateGif, nil 828 829 case line == "image {": 830 return stateGifImage, nil 831 832 case line == "trailer": 833 out = append(out, 0x3B) 834 return stateGif, nil 835 836 case strings.HasPrefix(line, cmdB): 837 s := line[len(cmdB):] 838 for s != "" { 839 x, ok := uint32(0), false 840 x, s, ok = parseHex(s) 841 if !ok { 842 break outer 843 } 844 out = append(out, uint8(x)) 845 } 846 return stateGif, nil 847 848 case strings.HasPrefix(line, cmdGC): 849 s := line[len(cmdGC):] 850 851 flags := uint8(0) 852 if i := strings.IndexByte(s, ' '); i < 0 { 853 break 854 } else { 855 switch s[:i] { 856 case "animationDisposalNone": 857 flags |= 0x00 858 case "animationDisposalRestoreBackground": 859 flags |= 0x08 860 case "animationDisposalRestorePrevious": 861 flags |= 0x0C 862 default: 863 break outer 864 } 865 s = s[i+1:] 866 } 867 868 if !strings.HasSuffix(s, "ms") { 869 break 870 } 871 s = s[:len(s)-2] 872 duration, s, ok := parseNum(s) 873 if !ok || s != "" { 874 break 875 } 876 duration /= 10 // GIF's unit of time is 10ms. 877 878 transparentIndex := uint8(0) 879 880 out = append(out, 881 0x21, 0xF9, 0x04, 882 flags, 883 uint8(duration>>0), 884 uint8(duration>>8), 885 transparentIndex, 886 0x00, 887 ) 888 return stateGif, nil 889 890 case strings.HasPrefix(line, cmdL): 891 s := line[len(cmdL):] 892 litWidth, s, ok := parseNum(s) 893 if !ok || litWidth < 2 || 8 < litWidth { 894 break 895 } 896 out = append(out, uint8(litWidth)) 897 898 uncompressed := []byte(nil) 899 for s != "" { 900 x := uint32(0) 901 x, s, ok = parseHex(s) 902 if !ok { 903 break outer 904 } 905 uncompressed = append(uncompressed, uint8(x)) 906 } 907 908 buf := bytes.NewBuffer(nil) 909 w := lzw.NewWriter(buf, lzw.LSB, int(litWidth)) 910 if _, err := w.Write(uncompressed); err != nil { 911 return nil, err 912 } 913 if err := w.Close(); err != nil { 914 return nil, err 915 } 916 compressed := buf.Bytes() 917 918 for len(compressed) > 0 { 919 if len(compressed) <= 0xFF { 920 out = append(out, uint8(len(compressed))) 921 out = append(out, compressed...) 922 compressed = nil 923 } else { 924 out = append(out, 0xFF) 925 out = append(out, compressed[:0xFF]...) 926 compressed = compressed[0xFF:] 927 } 928 } 929 out = append(out, 0x00) 930 return stateGif, nil 931 932 case strings.HasPrefix(line, cmdLC): 933 s := line[len(cmdLC):] 934 loopCount, _, ok := parseNum(s) 935 if !ok || 0xFFFF < loopCount { 936 break 937 } 938 out = append(out, 939 0x21, // Extension Introducer. 940 0xFF, // Application Extension Label. 941 0x0B, // Block Size. 942 ) 943 out = append(out, "NETSCAPE2.0"...) 944 out = append(out, 945 0x03, // Block Size. 946 0x01, // Magic Number. 947 byte(loopCount), 948 byte(loopCount>>8), 949 0x00, // Block Terminator. 950 ) 951 return stateGif, nil 952 } 953 954 return nil, fmt.Errorf("bad stateGif command: %q", line) 955} 956 957func stateGifImage(line string) (stateFunc, error) { 958 g := &gifGlobals 959 if line == "}" { 960 out = appendU16LE(out, uint16(g.imageWidth)) 961 out = appendU16LE(out, uint16(g.imageHeight)) 962 if g.globalPalette == nil { 963 out = append(out, 0x00) 964 } else if n := log2(uint32(len(g.globalPalette))); n < 2 || 8 < n { 965 return nil, fmt.Errorf("bad len(g.globalPalette): %d", len(g.globalPalette)) 966 } else { 967 out = append(out, 0x80|uint8(n-1)) 968 } 969 out = append(out, uint8(g.imageBackgroundColorIndex)) 970 out = append(out, 0x00) 971 for _, x := range g.globalPalette { 972 out = append(out, x[0], x[1], x[2]) 973 } 974 return stateGif, nil 975 } 976 977 const ( 978 cmdBCI = "backgroundColorIndex " 979 cmdIWH = "imageWidthHeight " 980 cmdP = "palette {" 981 ) 982 switch { 983 case strings.HasPrefix(line, cmdBCI): 984 s := line[len(cmdBCI):] 985 if i, _, ok := parseNum(s); ok { 986 g.imageBackgroundColorIndex = i 987 } 988 return stateGifImage, nil 989 990 case strings.HasPrefix(line, cmdIWH): 991 s := line[len(cmdIWH):] 992 if w, s, ok := parseNum(s); ok { 993 if h, _, ok := parseNum(s); ok { 994 g.imageWidth = w 995 g.imageHeight = h 996 return stateGifImage, nil 997 } 998 } 999 1000 case strings.HasPrefix(line, cmdP): 1001 return stateGifImagePalette, nil 1002 } 1003 1004 return nil, fmt.Errorf("bad stateGifImage command: %q", line) 1005} 1006 1007func stateGifFrame(line string) (stateFunc, error) { 1008 g := &gifGlobals 1009 if line == "}" { 1010 out = appendU16LE(out, uint16(g.frameLeft)) 1011 out = appendU16LE(out, uint16(g.frameTop)) 1012 out = appendU16LE(out, uint16(g.frameWidth)) 1013 out = appendU16LE(out, uint16(g.frameHeight)) 1014 if g.localPalette == nil { 1015 out = append(out, 0x00) 1016 } else if n := log2(uint32(len(g.localPalette))); n < 2 || 8 < n { 1017 return nil, fmt.Errorf("bad len(g.localPalette): %d", len(g.localPalette)) 1018 } else { 1019 out = append(out, 0x80|uint8(n-1)) 1020 } 1021 for _, x := range g.localPalette { 1022 out = append(out, x[0], x[1], x[2]) 1023 } 1024 return stateGif, nil 1025 } 1026 1027 const ( 1028 cmdFLTWH = "frameLeftTopWidthHeight " 1029 cmdP = "palette {" 1030 ) 1031 switch { 1032 case strings.HasPrefix(line, cmdFLTWH): 1033 s := line[len(cmdFLTWH):] 1034 if l, s, ok := parseNum(s); ok { 1035 if t, s, ok := parseNum(s); ok { 1036 if w, s, ok := parseNum(s); ok { 1037 if h, _, ok := parseNum(s); ok { 1038 g.frameLeft = l 1039 g.frameTop = t 1040 g.frameWidth = w 1041 g.frameHeight = h 1042 return stateGifFrame, nil 1043 } 1044 } 1045 } 1046 } 1047 1048 case strings.HasPrefix(line, cmdP): 1049 return stateGifFramePalette, nil 1050 } 1051 1052 return nil, fmt.Errorf("bad stateGifFrame command: %q", line) 1053} 1054 1055func stateGifImagePalette(line string) (stateFunc, error) { 1056 g := &gifGlobals 1057 if line == "}" { 1058 return stateGifImage, nil 1059 } 1060 1061 s := line 1062 if rgb0, s, ok := parseHex(s); ok { 1063 if rgb1, s, ok := parseHex(s); ok { 1064 if rgb2, _, ok := parseHex(s); ok { 1065 g.globalPalette = append(g.globalPalette, 1066 [4]uint8{uint8(rgb0), uint8(rgb1), uint8(rgb2), 0xFF}) 1067 return stateGifImagePalette, nil 1068 } 1069 } 1070 } 1071 1072 return nil, fmt.Errorf("bad stateGifImagePalette command: %q", line) 1073} 1074 1075func stateGifFramePalette(line string) (stateFunc, error) { 1076 g := &gifGlobals 1077 if line == "}" { 1078 return stateGifFrame, nil 1079 } 1080 1081 s := line 1082 if rgb0, s, ok := parseHex(s); ok { 1083 if rgb1, s, ok := parseHex(s); ok { 1084 if rgb2, _, ok := parseHex(s); ok { 1085 g.localPalette = append(g.localPalette, 1086 [4]uint8{uint8(rgb0), uint8(rgb1), uint8(rgb2), 0xFF}) 1087 return stateGifFramePalette, nil 1088 } 1089 } 1090 } 1091 1092 return nil, fmt.Errorf("bad stateGifFramePalette command: %q", line) 1093} 1094