1/* l1lzw.psm 2 * by pts@fazekas.hu at Sun Sep 22 01:23:57 CEST 2002 3 * formerly lzwdecode.psm -- a real, effective implementation of PostScript 4 * LanguageLevel2 and PDF /LZWDecode filters (same as the LZW 5 * compression used in TIFF raster image files), in PostScript Level1 6 * derived from lzwdecode.c by pts@fazekas.hu (at Wed Sep 4 11:11:45 CEST 2002) 7 * by pts@fazekas.hu at Wed Sep 4 11:30:18 CEST 2002 8 * first run at Wed Sep 4 14:18:43 CEST 2002 9 * linux-2.2.8 fine at Wed Sep 4 14:46:05 CEST 2002 10 * rets linux-2.2.8 fine at Wed Sep 4 15:58:24 CEST 2002 11 * works at Wed Sep 4 16:41:29 CEST 2002 12 * linux-2.2.8 58388480 uncompressed: 13 * lzwdecode.c: 17s user time (*1) 14 * lzw_codec.c: 6s user time (*0.353) 15 * lzwdecode.psm: 1080s user time (*63.53) 16 * stack-reorg works at Thu Sep 5 12:31:23 CEST 2002 17 * lzwdecode.psm: 980s user time (*57.65) 18 * lzwdecode.eps works at Thu Sep 5 14:31:23 CEST 2002 19 * last non-` at Sat Sep 21 23:40:03 CEST 2002 20 * 21 * Note that the LZW compression (but not uncompression) is patented by 22 * Unisys (patent number #4,558,302), so use this program at your own legal 23 * risk! 24 * 25 * This program is free software; you can redistribute it and/or modify 26 * it under the terms of the GNU General Public License as published by 27 * the Free Software Foundation; either version 2 of the License, or 28 * (at your option) any later version. 29 * 30 * This program is distributed in the hope that it will be useful, 31 * but WITHOUT ANY WARRANTY; without even the implied warranty of 32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 33 * GNU General Public License for more details. 34 * 35 * You should have received a copy of the GNU General Public License 36 * along with this program; if not, write to the Free Software 37 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 38 */ 39 40% OK: test with aaaaaaaaaaaa (stack overflow) 41 42#include "psmlib.psm" 43 44#if USE_A85D 45#else 46 #if USE_HEXD 47 #else 48 #define USE_BINARY 1 49 #endif 50#endif 51 52#if USE_NO_BIND 53 #define BIND_DEF def 54#else 55 #define BIND_DEF bind def 56#endif 57 58#if USE_PIN 59/* --- .pin begins */ 60 61%<Head> 62%!PS-Adobe-3.0`E 63%%Inflater: pts@fazekas.hu l1lzw.psm 64%%Pages: 1 65`X%%DocumentData: `B 66%%LanguageLevel: 1 67`I%%EndComments 68%%Page: 1 1 69%</Head> 70 71%<Open> 72save`s `R 73%</Open> 74 75% vvv 50 76%<Abbr acount=26 xcount=30> 77begin 78%</Abbr> 79 80%<A x "load def"/> % best to make it first 81%<A E def/> % best to make it second 82% K: .toksubs. 83%<D T .stream./> 84%<D F .stream./> 85 86%<A + add/> 87%<A , and/> 88%<A - sub/> 89%<A . lt/> 90%<A : for/> 91%<A ; getinterval/> 92%<A * gt/> 93%<A = eq/> 94%<A @ loop/> 95%<A A currentfile/> 96%C! 97%D! 98%<A H index/> 99%<A J 4096/> 100%<A L length/> 101%<A O pop/> 102%S! 103%<A X exit/> 104%<A a packedarray/> 105%<A b bitshift/> 106%<A c exch/> 107%d! 108%<A g get/> 109%<A y copy/> 110%<A i ifelse/> 111%<A j if/> 112%<A r read/> 113%<A s string/> 114%<A t put/> 115%<A u dup/> 116% %<A | -1670420001/> -- not needed, long enough 117%<A ~ ne/> 118#if USE_SHORT_NAMES 119%<D e Flzwdecode_init/> 120%<D f Flzwdecode_do/> 121%<D I Fclear/> 122%<D k prefix/> 123%<D l suffix/> 124%<D m stack/> 125%<D n preread/> 126%<D o past/> 127%<D p nentry/> 128%<D q had_eof/> 129%<D v nentrybig/> 130%<D w nentryb/> 131%<D h stackslice/> 132%<D z gcode/> 133%<D B Fmain/> 134#endif 135#if USE_A85D 136%<D d a85_getc/> 137%<D S xS/> 138%<D D xD/> 139%<D C xC/> 140#endif 141#if USE_HEXD 142%<D d .hexd.un/> 143%<A S readhexstring/> 144%<D D .hexd.un/> 145%<D C .hexd./> 146#endif 147#if USE_BINARY 148%<D d .binary.un/> 149#if USE_PALETTE 150%<D S readstring/> 151#endif 152%<D D .binary.un/> 153%<D C .binary.un/> 154#endif 155 156%<TokSubs name=K inlining=0/> 157 158%<Test> 159#if USE_BINARY 160 /F /filter where {pop false}{true} ifelse def 161#else 162 #if USE_A85D 163 {mark currentfile/ASCII85Decode filter/T exch def}stopped 164 #endif 165 #if USE_HEXD 166 {mark currentfile/ASCIIHexDecode filter/T exch def}stopped 167 #endif 168 /F exch def cleartomark 169#endif 170`w `h `b[1 0 0 -1 0 `h] 171#if USE_TRUE 172true 173#else 174F 175#endif 176%</Test> 177 178%<S len=4096> 1794096 string 180%</S> 181 182#if USE_SHORT_NAMES_OLD 183 #define a85_getc d 184 #define Flzwdecode_init e 185 #define Flzwdecode_do f 186 #define Fclear I 187#endif 188 189#if USE_CURRENTFILE 190 #define STDIN currentfile 191#endif 192 193%<True> 194 % Fmain 195 % ^^^ must call it here, because _now_ `currentfile fileposition` is at the real image data 196 % vvv avoid Fmain here because of the substituted constant 4717 (and also size increase!) 197 Flzwdecode_init 198 % !! Imp: less code here, init as a macro 199 /Fmain 4096 string def 200 { Fmain Flzwdecode_do } `i 201 Fmain Flzwdecode_do pop % make sure that mEOD has been read 202 TE_read_eod 203%</True> 204 205%<False> 206#if USE_BINARY 207/F currentfile/LZWDecode filter def 208#else 209/F T/LZWDecode filter def 210#endif 211F `i 212F closefile 213#if !USE_BINARY 214T closefile 215#endif 216%</False> 217 218%<Defs> 219#else 22040 dict begin % LZWDict 221#endif 222 223#if 0 224% (a) () 0 1 225% DumpStack 226% TYPE_STACK(-str -int) 227% ZZZZZZZZZ 228% (a) 3 229% ASSERT_STACK(-str -int,(1)) 230% pop pop 231#endif 232 233 234% Defaults: /EarlyChange 1 /UnitLength 8 /LowBitFirst false 235#if !USE_EARLYCHANGE_1 236/EarlyChange 1 def 237#endif 238#if !USE_UNITLENGTH_8 239/UnitLength 8 def 240#endif 241#if !USE_LOWBITFIRST_FALSE 242/LowBitFirst false def 243#endif 244 245/* OK: test with aaaaaaaaaaaa (stack overflow) */ 246#define STACKSIZE 4096 247#define STACKSIZE_M1 4095 248 249#if USE_SHORT_NAMES_OLD 250#endif 251 252% Uninitialized const-vars 253/prefix 4096 array def % array[0..4095] of 0..4095 254/suffix 4096 string def 255/stack STACKSIZE string def 256#if USE_CURRENTFILE 257#else 258 /STDIN (%stdin) (r) file def 259 /STDOUT (%stdout) (w) file def % Fmain 260#endif 261#if USE_HEXD 262 /C(.)def 263#endif 264 265% Uninitialized vars 266#if USE_UNITLENGTH_8 267 #define mClear 256 268 #define mEOD 257 269#endif 270#if !USE_NO_NULLDEF 271 /preread null def 272 /past null def 273 /nentry null def 274 /had_eof null def % 0..2 275 #if !USE_UNITLENGTH_8 276 /mEOD null def 277 /mClear null def 278 #endif 279 /nentrybig null def 280 /nentryb null def 281 /gcode null def % Flzwdecode_do 282 /stackslice null def % Flzwdecode_do 283 #if USE_A85D 284 /S null def 285 /D null def 286 /C null def 287 #endif 288#endif 289 290#if USE_PIN 291{ 292#endif 293 294#if USE_A85D 295 /a85_getc{ % Simple getchar() of ASCII85Decode filter :-)), formerly /d 296 PSM_A85_GETC 297 }BIND_DEF 298#endif 299 300%** - Fclear - 301/Fclear { 302 #if USE_UNITLENGTH_8 303 /nentry 258 def 304 /nentryb 9 def 305 #if USE_EARLYCHANGE_1 306 /nentrybig 512 def 307 #else 308 /nentrybig 513 EarlyChange sub def 309 #endif 310 #else 311 /nentry 1 UnitLength bitshift 2 add def 312 /nentryb UnitLength 1 add def 313 /nentrybig 1 nentryb bitshift 314 #if !USE_EARLYCHANGE_1 315 1 EarlyChange sub add 316 #endif 317 def 318 #endif 319 0 1 nentry 3 sub { 320 % Stack: code(0..255) 321 dup prefix exch dup 322 % Stack: code prefix code code 323 put 324 suffix exch dup put 325 } for 326} BIND_DEF 327 328%** - Flzwdecode_init - 329%** The caller should have modified /EarlyChange, /UnitLength and /LowBitFirst 330/Flzwdecode_init { 331 TE_init 332 /past 8 def 333 /preread 0 def 334 /had_eof 0 def 335 #if !USE_EARLYCHANGE_1 336 ASSERT_TRUE(EarlyChange 0 INT_EQ EarlyChange 1 INT_EQ BOOL_BIN(or,(ora1)), (lsp->EarlyChange==0 || lsp->EarlyChange==1)) 337 #endif 338 #if USE_UNITLENGTH_8 339 Fclear 340 #else 341 ASSERT_TRUE(3 UnitLength INT_LE UnitLength 8 INT_LE and, (3<=lsp->UnitLength && lsp->UnitLength<=8)) 342 Fclear 343 /mClear 1 UnitLength bitshift def 344 /mEOD 1 UnitLength bitshift 1 add def 345 #endif 346 /stackslice stack 0 0 getinterval def 347 /gcode {} def 348} BIND_DEF 349 350%** <str> Flzwdecode_do <str.pre> 351%** The caller should have called Flzwdecode_init. Flzwdecode_do fills the 352%** entire str.pre unless EOF on input prevents this. str.pre can have any 353%** length. Doesn`t depend of str.pre passed to it on the previous invocation. 354/Flzwdecode_do { 355 ASSERT_TRUE(10 nentry INT_LE,(lsp->nentry>=10)) 356 dup % Silently leave on stack 357 stackslice had_eof 358 % Stack: reto rets==reto stackslice had_eof 359 { % W2:WHILE(1) 360 % Stack: len++ stackslice had_eof* 361 dup 0 INT_NE { 362 /had_eof exch def 363 pop 364 /stackslice stack 0 0 getinterval def 365 exit % exit(W2) 366 }if % return(len) 367 ASSERT_STACK(-str -str -str -int,(W2.in)) 368 pop 369 % Stack: len++ stackslice 370 % Stack: reto rets stackslice 371 ASSERT_STACK(-str -str -str,(3)) 372 /* Flush stack. */ 373 2 copy length exch length ge { % return from the stack (rets.length<=stackslice.length 374 % Stack: reto rets stackslice 375 dup 0 3 index length getinterval 376 % Stack: reto rets stackslice stackslice[0.. rets.length] 377 2 index copy pop 378 % Stack: reto rets stackslice 379 /stackslice exch 2 index length dup 380 % Stack: reto rets /stackslice stackslice rets.length rets.length 381 2 index length exch sub 382 % Stack: reto rets /stackslice stackslice rets.length stackslice.length-rets.length 383 getinterval def 384 0 0 getinterval 385 % Stack: reto rets[0,0] 386 ASSERT_STACK(-str -str,(4)) 387 exit % exit(W2) 388 }if 389 % vvv flush the whole stack into rets 390 2 copy exch 391 copy pop % stackslice -> rets 392 length dup 393 % Stack: reto rets stackslice.length stackslice.length 394 2 index length exch sub 395 % Stack: reto rets stackslice.length rets.length-stackslice.length 396 getinterval 397 % Stack: reto rets 398 ASSERT_STACK(-str -str,(5)) 399 ASSERT_TRUE(dup length 1 exch INT_LE,(len>=1)) 400 % Stack: len++ 401 402 /* Read next code (0..4095) from input to `code` */ 403 nentry nentrybig INT_EQ { 404 /nentryb nentryb 1 add def 405 /nentrybig 1 nentryb bitshift 406 #if !USE_EARLYCHANGE_1 407 1 EarlyChange sub add 408 #endif 409 def 410 }if 411 ASSERT_TRUE(4 nentryb INT_LE nentryb 12 INT_LE and, (4<=nentryb && nentryb<=12)) 412 ASSERT_STACK(-str -str,(6)) 413 414 { % W1:WHILE(1) 415 ASSERT_STACK(-str -str,(7)) 416 % Stack: len++ 417 % assert(had_eof==0); -- cannot check this right here... 418 ASSERT_TRUE(1 past INT_LE past 8 INT_LE and,(1<=past && past<=8)) 419 ASSERT_TRUE(1 nentryb INT_LE nentryb 13 INT_LE and,(1<=nentryb && nentryb<=13)) 420 #if !USE_LOWBITFIRST_FALSE 421 LowBitFirst { 422 % Dat: this is untested, even the stack 423 /code 0 def 424 0 1 netryb 1 sub { 425 % Stack: len++ i 426 past 8 INT_EQ { 427 /preread TE_read(def /past 0 def) 428 #if !USE_NO_EOF 429 { 430 TE_read_pop pop 431 /had_eof 2 def exit % exit from inner `for` 432 }ifelse 433 #endif 434 }if 435 preread 1 and 0 INT_NE { 436 1 exch bitshift code INT_BIN(add,(ora2)) /code exch def 437 }{pop}ifelse 438 % Stack: len++ 439 /preread preread -1 bitshift def 440 /past past 1 add def 441 }for 442 had_eof 0 INT_NE {0 had_eof exit}if % exit(W1) 443 code 444 }{ % else: !LowBitFirst 445 #endif 446 past nentryb add 447 % Stack: len++ past* 448 ASSERT_STACK(-str -str -int,(8)) 449 dup 7 INT_GT { 450 dup 16 INT_GT { 451 16 sub 452 preread 8 bitshift 453 % Stack: len++ past* code 454 /preread TE_read(def) 455 #if !USE_NO_EOF 456 { 457 TE_read_pop pop 458 % Stack: len++ past* code 459 pop 460 /past exch def 461 0 2 462 % Stack: len++ garbage had_eof* 463 exit % exit(W1) 464 }ifelse 465 #endif 466 }{ 467 8 sub 468 0 % /code 469 }ifelse 470 % Stack: len++ past* code 471 ASSERT_STACK(-str -str -int -int,(9)) 472 ASSERT_TRUE(1 index 1 exch INT_LE 2 index 8 INT_LE and,(1<=lsp->past && lsp->past<=8)) 473 preread INT_BIN(add,(or1)) 474 % Stack: len++ past* code|preread 475 1 index bitshift 476 % Stack: len++ past* code*==(code|preread)<<past* 477 /preread TE_read(def) 478 #if !USE_NO_EOF 479 { 480 TE_read_pop pop 481 % Stack: len++ past* code 482 pop 483 /past exch def 484 0 2 485 % Stack: len++ garbage had_eof* 486 exit % exit(W1) 487 }ifelse 488 #endif 489 ASSERT_STACK(-str -str -int -int,(10)) 490 }{ 491 0 % /code 492 }ifelse 493 exch 494 % Stack: len++ code past* 495 ASSERT_STACK(-str -str -int -int,(11)) 496 preread exch 2 copy 497 % Stack: len++ code preread0 past* preread past* 498 { 255 127 63 31 15 7 3 1 0 } % cAnd 499 exch get and 500 % Stack: len++ code preread0 past* preread&cAnd[past*] 501 /preread exch def % lsp->preread&=(1<<(8-lsp->past))-1; /* do PCLEAR */ 502 % Stack: len++ code preread0 past* 503 dup /past exch def 504 8 sub bitshift INT_BIN(add,(or2)) 505 % Stack: len++ code*==code|(preread>>(8-past)) 506 ASSERT_STACK(-str -str -int,(12)) 507 #if !USE_LOWBITFIRST_FALSE 508 }ifelse % if: /LowBitFirst 509 #endif 510 % Stack: len++ code 511 ASSERT_STACK(-str -str -int,(13)) 512 513 dup mClear INT_LT{ 514 /* Speed-up: process normal literal data code in `code` */ 515 % Stack: len++ code 516 ASSERT_STACK(-str -str -int,(15b)) 517 ASSERT_TRUE(dup 1 add mClear INT_LE,(code too high2)) /* /ioerror */ 518 ASSERT_TRUE(nentry 4095 INT_LE,(table full2)) /* /ioerror */ 519 prefix nentry 2 index put 520 suffix nentry 1 sub 2 index put 521 stack exch STACKSIZE_M1 exch put 522 % Stack: len++ 523 ASSERT_STACK(-str -str,(15c)) 524 /nentry nentry 1 add def 525 stack STACKSIZE_M1 1 getinterval 526 % Stack: len++ stackslice 527 0 % /had_eof 528 ASSERT_STACK(-str -str -str -int,(20b)) 529 exit % exit(W1) 530 }if 531 532 dup mEOD INT_GT{ 533 /* Process normal data code (either literal or above-mEOD) in `code` */ 534 % Stack: len++ code 535 ASSERT_STACK(-str -str -int,(15)) 536 ASSERT_TRUE(dup 1 add nentry INT_LE,(code too high)) /* /ioerror */ 537 ASSERT_TRUE(nentry 4095 INT_LE,(table full)) /* /ioerror */ 538 prefix nentry 2 index put 539 % ASSERT_TRUE(0 stacklen INT_EQ,(lsp->stacklen==0)) 540 % Stack: len++ code 541 stack exch dup STACKSIZE_M1 exch 542 nentry 1 sub 543 % Stack: len++ stack code STACKSIZE_M1 code nentry-1 544 ASSERT_STACK(-str -str -aryb -int -int -int -int,(16)) 545 INT_EQ { 546 % the rightmost char of this entry will be equal to the leftmost 547 % side, as soon as we calculate the leftmost side 548 /gcode { stack STACKSIZE_M1 2 index put /gcode {} def } def 549 }if 550 %{ 551 % ASSERT_TRUE(1 index nentry 2 sub INT_LE,(code<lsp->nentry-1)) 552 % % /gcode { } def 553 %}ifelse 554 -1 0 555 % Stack: len++ -{...} stack code STACKSIZE-1|STACKSIZE-2 -1 0 556 { 557 % 1 index (code=) print === 558 % Stack: len -{...} stack code putidx 559 ASSERT_STACK(-str -str -aryb -int -int,(17)) 560 exch dup prefix exch get 2 copy 561 % Stack: len -{...} stack putidx code prefix[code] code prefix[code] 562 INT_EQ{pop exit}if % exit from inner for 563 % Stack: len -{...} stack putidx code prefix[code] 564 4 copy pop suffix exch get 565 % Stack: len -{...} stack putidx code prefix[code] stack putidx suffix[code] 566 put 567 exch pop 568 exch pop 569 % Stack: len -{...} stack prefix[code] 570 }for 571 % Stack: len stack unused_putidx code 572 ASSERT_STACK(-str -str -aryb -int -int,(18)) 573 dup suffix exch get 574 % dup (sufcode=) print === 575 gcode 576 suffix nentry 1 sub 2 index put pop 577 % Stack: len stack unused_putidx suffix[code] 578 3 copy put pop 579 % Stack: len stack unused_putidx 580 dup STACKSIZE exch sub 581 % Stack: len stack putidx STACKSIZE-putidx 582 ASSERT_STACK(-str -str -aryb -int -int,(19)) 583 getinterval 584 ASSERT_TRUE(1 index length 0 INT_NE,(len!=0)) 585 /nentry nentry 1 add def 586 % Stack: len++ stackslice 587 0 % /had_eof 588 ASSERT_STACK(-str -str -str -int,(20)) 589 exit % exit(W1) 590 }if 591 592 dup mEOD INT_EQ{ 593 % Stack: len++ code==mEOD 594 pop 0 1 595 % Stack: len++ garbage had_eof* 596 ASSERT_STACK(-str -str -int -int,(14)) 597 exit % exit(W1) 598 }if 599 600 ASSERT_TRUE(dup mClear INT_EQ,(code==mClear)) 601 pop Fclear 602 % Stack: len++ 603 ASSERT_STACK(-str -str,(21)) 604 }loop % /W1:WHILE(1) 605 % Stack: len++ stackslice|garbage had_eof* 606 ASSERT_TRUE(TYPE_STACK(-str -str -str -int) TYPE_STACK(-str -str -int -int -bool) BOOL_BIN(or,(ora4)),(stack leaving W2)) 607 } loop % /W2:WHILE(1) 608 % Stack: len++ 609 % Stack: reto rets(buffer-not-read) 610 ASSERT_STACK(-str -str,(22)) 611 length 1 index length exch sub 612 % Stack: reto reto.length-rets.length 613 0 exch getinterval 614 % Stack: reto.pre(return-value) 615} BIND_DEF % Flzwdecode_do 616 617#if USE_PIN 618%/Fmain { 619%} BIND_DEF 620} % close the function defs section 621%</Defs> 622 623%<Data> 624%%BeginData: 625exec 626`S 627%%EndData 628end restore showpage 629%%Trailer 630%%EOF 631%</Data> 632#else 633 634#if !USE_CURRENTFILE 635% --- Main 636 637%** - Fmain - 638/Fmain { 639 /mys 8192 string def 640 Flzwdecode_init 641 { mys Flzwdecode_do 642 % Stack: mys.pre 643 dup length 0 INT_EQ{exit}if 644 STDOUT exch writestring 645 } loop 646 had_eof 1 INT_EQ { 647 { STDIN read {pop}{exit}ifelse }loop 648 }if 649} BIND_DEF 650Fmain 651#endif 652 653end % LZWDict 654#endif 655 656%%EOF 657