1 /* 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 3 % % 4 % % 5 % % 6 % CCCC OOO M M PPPP RRRR EEEEE SSSSS SSSSS % 7 % C O O MM MM P P R R E SS SS % 8 % C O O M M M PPPP RRRR EEE SSS SSS % 9 % C O O M M P R R E SS SS % 10 % CCCC OOO M M P R R EEEEE SSSSS SSSSS % 11 % % 12 % % 13 % MagickCore Image Compression/Decompression Methods % 14 % % 15 % Software Design % 16 % Cristy % 17 % May 1993 % 18 % % 19 % % 20 % Copyright 1999-2016 ImageMagick Studio LLC, a non-profit organization % 21 % dedicated to making software imaging solutions freely available. % 22 % % 23 % You may not use this file except in compliance with the License. You may % 24 % obtain a copy of the License at % 25 % % 26 % http://www.imagemagick.org/script/license.php % 27 % % 28 % Unless required by applicable law or agreed to in writing, software % 29 % distributed under the License is distributed on an "AS IS" BASIS, % 30 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. % 31 % See the License for the specific language governing permissions and % 32 % limitations under the License. % 33 % % 34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 35 % 36 % 37 % 38 */ 39 40 /* 42 Include declarations. 43 */ 44 #include "MagickCore/studio.h" 45 #include "MagickCore/attribute.h" 46 #include "MagickCore/blob.h" 47 #include "MagickCore/blob-private.h" 48 #include "MagickCore/color-private.h" 49 #include "MagickCore/cache.h" 50 #include "MagickCore/compress.h" 51 #include "MagickCore/constitute.h" 52 #include "MagickCore/exception.h" 53 #include "MagickCore/exception-private.h" 54 #include "MagickCore/image-private.h" 55 #include "MagickCore/list.h" 56 #include "MagickCore/memory_.h" 57 #include "MagickCore/monitor.h" 58 #include "MagickCore/monitor-private.h" 59 #include "MagickCore/option.h" 60 #include "MagickCore/pixel-accessor.h" 61 #include "MagickCore/resource_.h" 62 #include "MagickCore/string_.h" 63 #if defined(MAGICKCORE_ZLIB_DELEGATE) 64 #include "zlib.h" 65 #endif 66 67 /* 69 Typedef declarations. 70 */ 71 struct _Ascii85Info 72 { 73 ssize_t 74 offset, 75 line_break; 76 77 unsigned char 78 buffer[10]; 79 }; 80 81 typedef struct HuffmanTable 82 { 83 size_t 84 id, 85 code, 86 length, 87 count; 88 } HuffmanTable; 89 90 /* 92 Huffman coding declarations. 93 */ 94 #define TWId 23 95 #define MWId 24 96 #define TBId 25 97 #define MBId 26 98 #define EXId 27 99 100 static const HuffmanTable 101 MBTable[]= 102 { 103 { MBId, 0x0f, 10, 64 }, { MBId, 0xc8, 12, 128 }, 104 { MBId, 0xc9, 12, 192 }, { MBId, 0x5b, 12, 256 }, 105 { MBId, 0x33, 12, 320 }, { MBId, 0x34, 12, 384 }, 106 { MBId, 0x35, 12, 448 }, { MBId, 0x6c, 13, 512 }, 107 { MBId, 0x6d, 13, 576 }, { MBId, 0x4a, 13, 640 }, 108 { MBId, 0x4b, 13, 704 }, { MBId, 0x4c, 13, 768 }, 109 { MBId, 0x4d, 13, 832 }, { MBId, 0x72, 13, 896 }, 110 { MBId, 0x73, 13, 960 }, { MBId, 0x74, 13, 1024 }, 111 { MBId, 0x75, 13, 1088 }, { MBId, 0x76, 13, 1152 }, 112 { MBId, 0x77, 13, 1216 }, { MBId, 0x52, 13, 1280 }, 113 { MBId, 0x53, 13, 1344 }, { MBId, 0x54, 13, 1408 }, 114 { MBId, 0x55, 13, 1472 }, { MBId, 0x5a, 13, 1536 }, 115 { MBId, 0x5b, 13, 1600 }, { MBId, 0x64, 13, 1664 }, 116 { MBId, 0x65, 13, 1728 }, { MBId, 0x00, 0, 0 } 117 }; 118 119 static const HuffmanTable 120 EXTable[]= 121 { 122 { EXId, 0x08, 11, 1792 }, { EXId, 0x0c, 11, 1856 }, 123 { EXId, 0x0d, 11, 1920 }, { EXId, 0x12, 12, 1984 }, 124 { EXId, 0x13, 12, 2048 }, { EXId, 0x14, 12, 2112 }, 125 { EXId, 0x15, 12, 2176 }, { EXId, 0x16, 12, 2240 }, 126 { EXId, 0x17, 12, 2304 }, { EXId, 0x1c, 12, 2368 }, 127 { EXId, 0x1d, 12, 2432 }, { EXId, 0x1e, 12, 2496 }, 128 { EXId, 0x1f, 12, 2560 }, { EXId, 0x00, 0, 0 } 129 }; 130 131 static const HuffmanTable 132 MWTable[]= 133 { 134 { MWId, 0x1b, 5, 64 }, { MWId, 0x12, 5, 128 }, 135 { MWId, 0x17, 6, 192 }, { MWId, 0x37, 7, 256 }, 136 { MWId, 0x36, 8, 320 }, { MWId, 0x37, 8, 384 }, 137 { MWId, 0x64, 8, 448 }, { MWId, 0x65, 8, 512 }, 138 { MWId, 0x68, 8, 576 }, { MWId, 0x67, 8, 640 }, 139 { MWId, 0xcc, 9, 704 }, { MWId, 0xcd, 9, 768 }, 140 { MWId, 0xd2, 9, 832 }, { MWId, 0xd3, 9, 896 }, 141 { MWId, 0xd4, 9, 960 }, { MWId, 0xd5, 9, 1024 }, 142 { MWId, 0xd6, 9, 1088 }, { MWId, 0xd7, 9, 1152 }, 143 { MWId, 0xd8, 9, 1216 }, { MWId, 0xd9, 9, 1280 }, 144 { MWId, 0xda, 9, 1344 }, { MWId, 0xdb, 9, 1408 }, 145 { MWId, 0x98, 9, 1472 }, { MWId, 0x99, 9, 1536 }, 146 { MWId, 0x9a, 9, 1600 }, { MWId, 0x18, 6, 1664 }, 147 { MWId, 0x9b, 9, 1728 }, { MWId, 0x00, 0, 0 } 148 }; 149 150 static const HuffmanTable 151 TBTable[]= 152 { 153 { TBId, 0x37, 10, 0 }, { TBId, 0x02, 3, 1 }, { TBId, 0x03, 2, 2 }, 154 { TBId, 0x02, 2, 3 }, { TBId, 0x03, 3, 4 }, { TBId, 0x03, 4, 5 }, 155 { TBId, 0x02, 4, 6 }, { TBId, 0x03, 5, 7 }, { TBId, 0x05, 6, 8 }, 156 { TBId, 0x04, 6, 9 }, { TBId, 0x04, 7, 10 }, { TBId, 0x05, 7, 11 }, 157 { TBId, 0x07, 7, 12 }, { TBId, 0x04, 8, 13 }, { TBId, 0x07, 8, 14 }, 158 { TBId, 0x18, 9, 15 }, { TBId, 0x17, 10, 16 }, { TBId, 0x18, 10, 17 }, 159 { TBId, 0x08, 10, 18 }, { TBId, 0x67, 11, 19 }, { TBId, 0x68, 11, 20 }, 160 { TBId, 0x6c, 11, 21 }, { TBId, 0x37, 11, 22 }, { TBId, 0x28, 11, 23 }, 161 { TBId, 0x17, 11, 24 }, { TBId, 0x18, 11, 25 }, { TBId, 0xca, 12, 26 }, 162 { TBId, 0xcb, 12, 27 }, { TBId, 0xcc, 12, 28 }, { TBId, 0xcd, 12, 29 }, 163 { TBId, 0x68, 12, 30 }, { TBId, 0x69, 12, 31 }, { TBId, 0x6a, 12, 32 }, 164 { TBId, 0x6b, 12, 33 }, { TBId, 0xd2, 12, 34 }, { TBId, 0xd3, 12, 35 }, 165 { TBId, 0xd4, 12, 36 }, { TBId, 0xd5, 12, 37 }, { TBId, 0xd6, 12, 38 }, 166 { TBId, 0xd7, 12, 39 }, { TBId, 0x6c, 12, 40 }, { TBId, 0x6d, 12, 41 }, 167 { TBId, 0xda, 12, 42 }, { TBId, 0xdb, 12, 43 }, { TBId, 0x54, 12, 44 }, 168 { TBId, 0x55, 12, 45 }, { TBId, 0x56, 12, 46 }, { TBId, 0x57, 12, 47 }, 169 { TBId, 0x64, 12, 48 }, { TBId, 0x65, 12, 49 }, { TBId, 0x52, 12, 50 }, 170 { TBId, 0x53, 12, 51 }, { TBId, 0x24, 12, 52 }, { TBId, 0x37, 12, 53 }, 171 { TBId, 0x38, 12, 54 }, { TBId, 0x27, 12, 55 }, { TBId, 0x28, 12, 56 }, 172 { TBId, 0x58, 12, 57 }, { TBId, 0x59, 12, 58 }, { TBId, 0x2b, 12, 59 }, 173 { TBId, 0x2c, 12, 60 }, { TBId, 0x5a, 12, 61 }, { TBId, 0x66, 12, 62 }, 174 { TBId, 0x67, 12, 63 }, { TBId, 0x00, 0, 0 } 175 }; 176 177 static const HuffmanTable 178 TWTable[]= 179 { 180 { TWId, 0x35, 8, 0 }, { TWId, 0x07, 6, 1 }, { TWId, 0x07, 4, 2 }, 181 { TWId, 0x08, 4, 3 }, { TWId, 0x0b, 4, 4 }, { TWId, 0x0c, 4, 5 }, 182 { TWId, 0x0e, 4, 6 }, { TWId, 0x0f, 4, 7 }, { TWId, 0x13, 5, 8 }, 183 { TWId, 0x14, 5, 9 }, { TWId, 0x07, 5, 10 }, { TWId, 0x08, 5, 11 }, 184 { TWId, 0x08, 6, 12 }, { TWId, 0x03, 6, 13 }, { TWId, 0x34, 6, 14 }, 185 { TWId, 0x35, 6, 15 }, { TWId, 0x2a, 6, 16 }, { TWId, 0x2b, 6, 17 }, 186 { TWId, 0x27, 7, 18 }, { TWId, 0x0c, 7, 19 }, { TWId, 0x08, 7, 20 }, 187 { TWId, 0x17, 7, 21 }, { TWId, 0x03, 7, 22 }, { TWId, 0x04, 7, 23 }, 188 { TWId, 0x28, 7, 24 }, { TWId, 0x2b, 7, 25 }, { TWId, 0x13, 7, 26 }, 189 { TWId, 0x24, 7, 27 }, { TWId, 0x18, 7, 28 }, { TWId, 0x02, 8, 29 }, 190 { TWId, 0x03, 8, 30 }, { TWId, 0x1a, 8, 31 }, { TWId, 0x1b, 8, 32 }, 191 { TWId, 0x12, 8, 33 }, { TWId, 0x13, 8, 34 }, { TWId, 0x14, 8, 35 }, 192 { TWId, 0x15, 8, 36 }, { TWId, 0x16, 8, 37 }, { TWId, 0x17, 8, 38 }, 193 { TWId, 0x28, 8, 39 }, { TWId, 0x29, 8, 40 }, { TWId, 0x2a, 8, 41 }, 194 { TWId, 0x2b, 8, 42 }, { TWId, 0x2c, 8, 43 }, { TWId, 0x2d, 8, 44 }, 195 { TWId, 0x04, 8, 45 }, { TWId, 0x05, 8, 46 }, { TWId, 0x0a, 8, 47 }, 196 { TWId, 0x0b, 8, 48 }, { TWId, 0x52, 8, 49 }, { TWId, 0x53, 8, 50 }, 197 { TWId, 0x54, 8, 51 }, { TWId, 0x55, 8, 52 }, { TWId, 0x24, 8, 53 }, 198 { TWId, 0x25, 8, 54 }, { TWId, 0x58, 8, 55 }, { TWId, 0x59, 8, 56 }, 199 { TWId, 0x5a, 8, 57 }, { TWId, 0x5b, 8, 58 }, { TWId, 0x4a, 8, 59 }, 200 { TWId, 0x4b, 8, 60 }, { TWId, 0x32, 8, 61 }, { TWId, 0x33, 8, 62 }, 201 { TWId, 0x34, 8, 63 }, { TWId, 0x00, 0, 0 } 202 }; 203 204 /* 206 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 207 % % 208 % % 209 % % 210 % A S C I I 8 5 E n c o d e % 211 % % 212 % % 213 % % 214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 215 % 216 % ASCII85Encode() encodes data in ASCII base-85 format. ASCII base-85 217 % encoding produces five ASCII printing characters from every four bytes of 218 % binary data. 219 % 220 % The format of the ASCII85Encode method is: 221 % 222 % void Ascii85Encode(Image *image,const size_t code) 223 % 224 % A description of each parameter follows: 225 % 226 % o code: a binary unsigned char to encode to ASCII 85. 227 % 228 % o file: write the encoded ASCII character to this file. 229 % 230 % 231 */ 232 #define MaxLineExtent 36 233 234 static char *Ascii85Tuple(unsigned char *data) 235 { 236 static char 237 tuple[6]; 238 239 register ssize_t 240 i, 241 x; 242 243 size_t 244 code, 245 quantum; 246 247 code=((((size_t) data[0] << 8) | (size_t) data[1]) << 16) | 248 ((size_t) data[2] << 8) | (size_t) data[3]; 249 if (code == 0L) 250 { 251 tuple[0]='z'; 252 tuple[1]='\0'; 253 return(tuple); 254 } 255 quantum=85UL*85UL*85UL*85UL; 256 for (i=0; i < 4; i++) 257 { 258 x=(ssize_t) (code/quantum); 259 code-=quantum*x; 260 tuple[i]=(char) (x+(int) '!'); 261 quantum/=85L; 262 } 263 tuple[4]=(char) ((code % 85L)+(int) '!'); 264 tuple[5]='\0'; 265 return(tuple); 266 } 267 268 MagickExport void Ascii85Initialize(Image *image) 269 { 270 /* 271 Allocate image structure. 272 */ 273 if (image->ascii85 == (Ascii85Info *) NULL) 274 image->ascii85=(Ascii85Info *) AcquireMagickMemory(sizeof(*image->ascii85)); 275 if (image->ascii85 == (Ascii85Info *) NULL) 276 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed"); 277 (void) ResetMagickMemory(image->ascii85,0,sizeof(*image->ascii85)); 278 image->ascii85->line_break=MaxLineExtent << 1; 279 image->ascii85->offset=0; 280 } 281 282 MagickExport void Ascii85Flush(Image *image) 283 { 284 register char 285 *tuple; 286 287 assert(image != (Image *) NULL); 288 assert(image->signature == MagickCoreSignature); 289 if (image->debug != MagickFalse) 290 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 291 assert(image->ascii85 != (Ascii85Info *) NULL); 292 if (image->ascii85->offset > 0) 293 { 294 image->ascii85->buffer[image->ascii85->offset]='\0'; 295 image->ascii85->buffer[image->ascii85->offset+1]='\0'; 296 image->ascii85->buffer[image->ascii85->offset+2]='\0'; 297 tuple=Ascii85Tuple(image->ascii85->buffer); 298 (void) WriteBlob(image,(size_t) image->ascii85->offset+1, 299 (const unsigned char *) (*tuple == 'z' ? "!!!!" : tuple)); 300 } 301 (void) WriteBlobByte(image,'~'); 302 (void) WriteBlobByte(image,'>'); 303 (void) WriteBlobByte(image,'\n'); 304 } 305 306 MagickExport void Ascii85Encode(Image *image,const unsigned char code) 307 { 308 register char 309 *q; 310 311 register unsigned char 312 *p; 313 314 ssize_t 315 n; 316 317 assert(image != (Image *) NULL); 318 assert(image->signature == MagickCoreSignature); 319 assert(image->ascii85 != (Ascii85Info *) NULL); 320 image->ascii85->buffer[image->ascii85->offset]=code; 321 image->ascii85->offset++; 322 if (image->ascii85->offset < 4) 323 return; 324 p=image->ascii85->buffer; 325 for (n=image->ascii85->offset; n >= 4; n-=4) 326 { 327 for (q=Ascii85Tuple(p); *q != '\0'; q++) 328 { 329 image->ascii85->line_break--; 330 if ((image->ascii85->line_break < 0) && (*q != '%')) 331 { 332 (void) WriteBlobByte(image,'\n'); 333 image->ascii85->line_break=2*MaxLineExtent; 334 } 335 (void) WriteBlobByte(image,(unsigned char) *q); 336 } 337 p+=8; 338 } 339 image->ascii85->offset=n; 340 p-=4; 341 for (n=0; n < 4; n++) 342 image->ascii85->buffer[n]=(*p++); 343 } 344 345 /* 347 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 348 % % 349 % % 350 % % 351 % H u f f m a n D e c o d e I m a g e % 352 % % 353 % % 354 % % 355 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 356 % 357 % HuffmanDecodeImage() uncompresses an image via Huffman-coding. 358 % 359 % The format of the HuffmanDecodeImage method is: 360 % 361 % MagickBooleanType HuffmanDecodeImage(Image *image, 362 % ExceptionInfo *exception) 363 % 364 % A description of each parameter follows: 365 % 366 % o image: the image. 367 % 368 % o exception: return any errors or warnings in this structure. 369 % 370 */ 371 MagickExport MagickBooleanType HuffmanDecodeImage(Image *image, 372 ExceptionInfo *exception) 373 { 374 #define HashSize 1021 375 #define MBHashA 293 376 #define MBHashB 2695 377 #define MWHashA 3510 378 #define MWHashB 1178 379 380 #define InitializeHashTable(hash,table,a,b) \ 381 { \ 382 entry=table; \ 383 while (entry->code != 0) \ 384 { \ 385 hash[((entry->length+a)*(entry->code+b)) % HashSize]=(HuffmanTable *) entry; \ 386 entry++; \ 387 } \ 388 } 389 390 #define InputBit(bit) \ 391 { \ 392 if ((mask & 0xff) == 0) \ 393 { \ 394 byte=ReadBlobByte(image); \ 395 if (byte == EOF) \ 396 break; \ 397 mask=0x80; \ 398 } \ 399 runlength++; \ 400 bit=(size_t) ((byte & mask) != 0 ? 0x01 : 0x00); \ 401 mask>>=1; \ 402 if (bit != 0) \ 403 runlength=0; \ 404 } 405 406 CacheView 407 *image_view; 408 409 const HuffmanTable 410 *entry; 411 412 HuffmanTable 413 **mb_hash, 414 **mw_hash; 415 416 int 417 byte; 418 419 MagickBooleanType 420 proceed; 421 422 Quantum 423 index; 424 425 register ssize_t 426 i; 427 428 register unsigned char 429 *p; 430 431 size_t 432 bit, 433 code, 434 mask, 435 length, 436 null_lines, 437 runlength; 438 439 ssize_t 440 count, 441 y; 442 443 unsigned char 444 *scanline; 445 446 unsigned int 447 bail, 448 color; 449 450 /* 451 Allocate buffers. 452 */ 453 assert(image != (Image *) NULL); 454 assert(image->signature == MagickCoreSignature); 455 if (image->debug != MagickFalse) 456 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 457 mb_hash=(HuffmanTable **) AcquireQuantumMemory(HashSize,sizeof(*mb_hash)); 458 mw_hash=(HuffmanTable **) AcquireQuantumMemory(HashSize,sizeof(*mw_hash)); 459 scanline=(unsigned char *) AcquireQuantumMemory((size_t) image->columns, 460 sizeof(*scanline)); 461 if ((mb_hash == (HuffmanTable **) NULL) || 462 (mw_hash == (HuffmanTable **) NULL) || 463 (scanline == (unsigned char *) NULL)) 464 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 465 image->filename); 466 /* 467 Initialize Huffman tables. 468 */ 469 for (i=0; i < HashSize; i++) 470 { 471 mb_hash[i]=(HuffmanTable *) NULL; 472 mw_hash[i]=(HuffmanTable *) NULL; 473 } 474 InitializeHashTable(mw_hash,TWTable,MWHashA,MWHashB); 475 InitializeHashTable(mw_hash,MWTable,MWHashA,MWHashB); 476 InitializeHashTable(mw_hash,EXTable,MWHashA,MWHashB); 477 InitializeHashTable(mb_hash,TBTable,MBHashA,MBHashB); 478 InitializeHashTable(mb_hash,MBTable,MBHashA,MBHashB); 479 InitializeHashTable(mb_hash,EXTable,MBHashA,MBHashB); 480 /* 481 Uncompress 1D Huffman to runlength encoded pixels. 482 */ 483 byte=0; 484 mask=0; 485 null_lines=0; 486 runlength=0; 487 while (runlength < 11) 488 InputBit(bit); 489 do { InputBit(bit); } while ((int) bit == 0); 490 image->resolution.x=204.0; 491 image->resolution.y=196.0; 492 image->units=PixelsPerInchResolution; 493 image_view=AcquireAuthenticCacheView(image,exception); 494 for (y=0; ((y < (ssize_t) image->rows) && (null_lines < 3)); ) 495 { 496 register Quantum 497 *magick_restrict q; 498 499 register ssize_t 500 x; 501 502 /* 503 Initialize scanline to white. 504 */ 505 ResetMagickMemory(scanline,0,sizeof(*scanline)*image->columns); 506 /* 507 Decode Huffman encoded scanline. 508 */ 509 color=MagickTrue; 510 code=0; 511 count=0; 512 length=0; 513 runlength=0; 514 x=0; 515 for ( ; ; ) 516 { 517 if (byte == EOF) 518 break; 519 if (x >= (ssize_t) image->columns) 520 { 521 while (runlength < 11) 522 InputBit(bit); 523 do { InputBit(bit); } while ((int) bit == 0); 524 break; 525 } 526 bail=MagickFalse; 527 do 528 { 529 if (runlength < 11) 530 InputBit(bit) 531 else 532 { 533 InputBit(bit); 534 if ((int) bit != 0) 535 { 536 null_lines++; 537 if (x != 0) 538 null_lines=0; 539 bail=MagickTrue; 540 break; 541 } 542 } 543 code=(code << 1)+(size_t) bit; 544 length++; 545 } while (code == 0); 546 if (bail != MagickFalse) 547 break; 548 if (length > 13) 549 { 550 while (runlength < 11) 551 InputBit(bit); 552 do { InputBit(bit); } while ((int) bit == 0); 553 break; 554 } 555 if (color != MagickFalse) 556 { 557 if (length < 4) 558 continue; 559 entry=mw_hash[((length+MWHashA)*(code+MWHashB)) % HashSize]; 560 } 561 else 562 { 563 if (length < 2) 564 continue; 565 entry=mb_hash[((length+MBHashA)*(code+MBHashB)) % HashSize]; 566 } 567 if (entry == (const HuffmanTable *) NULL) 568 continue; 569 if ((entry->length != length) || (entry->code != code)) 570 continue; 571 switch (entry->id) 572 { 573 case TWId: 574 case TBId: 575 { 576 count+=(ssize_t) entry->count; 577 if ((x+count) > (ssize_t) image->columns) 578 count=(ssize_t) image->columns-x; 579 if (count > 0) 580 { 581 if (color != MagickFalse) 582 { 583 x+=count; 584 count=0; 585 } 586 else 587 for ( ; count > 0; count--) 588 scanline[x++]=(unsigned char) 1; 589 } 590 color=(unsigned int) 591 ((color == MagickFalse) ? MagickTrue : MagickFalse); 592 break; 593 } 594 case MWId: 595 case MBId: 596 case EXId: 597 { 598 count+=(ssize_t) entry->count; 599 break; 600 } 601 default: 602 break; 603 } 604 code=0; 605 length=0; 606 } 607 /* 608 Transfer scanline to image pixels. 609 */ 610 p=scanline; 611 q=QueueCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception); 612 if (q == (Quantum *) NULL) 613 break; 614 for (x=0; x < (ssize_t) image->columns; x++) 615 { 616 index=(Quantum) (*p++); 617 SetPixelIndex(image,index,q); 618 SetPixelViaPixelInfo(image,image->colormap+(ssize_t) index,q); 619 q+=GetPixelChannels(image); 620 } 621 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse) 622 break; 623 proceed=SetImageProgress(image,LoadImageTag,y,image->rows); 624 if (proceed == MagickFalse) 625 break; 626 y++; 627 } 628 image_view=DestroyCacheView(image_view); 629 image->rows=(size_t) MagickMax((size_t) y-3,1); 630 image->compression=FaxCompression; 631 /* 632 Free decoder memory. 633 */ 634 mw_hash=(HuffmanTable **) RelinquishMagickMemory(mw_hash); 635 mb_hash=(HuffmanTable **) RelinquishMagickMemory(mb_hash); 636 scanline=(unsigned char *) RelinquishMagickMemory(scanline); 637 return(MagickTrue); 638 } 639 640 /* 642 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 643 % % 644 % % 645 % % 646 % H u f f m a n E n c o d e I m a g e % 647 % % 648 % % 649 % % 650 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 651 % 652 % HuffmanEncodeImage() compresses an image via Huffman-coding. 653 % 654 % The format of the HuffmanEncodeImage method is: 655 % 656 % MagickBooleanType HuffmanEncodeImage(const ImageInfo *image_info, 657 % Image *image,Image *inject_image,ExceptionInfo *exception) 658 % 659 % A description of each parameter follows: 660 % 661 % o image_info: the image info.. 662 % 663 % o image: the image. 664 % 665 % o inject_image: inject into the image stream. 666 % 667 % o exception: return any errors or warnings in this structure. 668 % 669 */ 670 MagickExport MagickBooleanType HuffmanEncodeImage(const ImageInfo *image_info, 671 Image *image,Image *inject_image,ExceptionInfo *exception) 672 { 673 #define HuffmanOutputCode(entry) \ 674 { \ 675 mask=one << (entry->length-1); \ 676 while (mask != 0) \ 677 { \ 678 OutputBit(((entry->code & mask) != 0 ? 1 : 0)); \ 679 mask>>=1; \ 680 } \ 681 } 682 683 #define OutputBit(count) \ 684 { \ 685 DisableMSCWarning(4127) \ 686 if (count > 0) \ 687 byte=byte | bit; \ 688 RestoreMSCWarning \ 689 bit>>=1; \ 690 if ((int) (bit & 0xff) == 0) \ 691 { \ 692 if (LocaleCompare(image_info->magick,"FAX") == 0) \ 693 (void) WriteBlobByte(image,(unsigned char) byte); \ 694 else \ 695 Ascii85Encode(image,byte); \ 696 byte='\0'; \ 697 bit=(unsigned char) 0x80; \ 698 } \ 699 } 700 701 const HuffmanTable 702 *entry; 703 704 int 705 k, 706 runlength; 707 708 Image 709 *huffman_image; 710 711 MagickBooleanType 712 proceed; 713 714 register ssize_t 715 i, 716 x; 717 718 register const Quantum 719 *p; 720 721 register unsigned char 722 *q; 723 724 size_t 725 mask, 726 one, 727 width; 728 729 ssize_t 730 n, 731 y; 732 733 unsigned char 734 byte, 735 bit, 736 *scanline; 737 738 /* 739 Allocate scanline buffer. 740 */ 741 assert(image_info != (ImageInfo *) NULL); 742 assert(image_info->signature == MagickCoreSignature); 743 assert(image != (Image *) NULL); 744 assert(image->signature == MagickCoreSignature); 745 if (image->debug != MagickFalse) 746 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 747 assert(inject_image != (Image *) NULL); 748 assert(inject_image->signature == MagickCoreSignature); 749 one=1; 750 width=inject_image->columns; 751 if (LocaleCompare(image_info->magick,"FAX") == 0) 752 width=(size_t) MagickMax(inject_image->columns,1728); 753 scanline=(unsigned char *) AcquireQuantumMemory((size_t) width+1UL, 754 sizeof(*scanline)); 755 if (scanline == (unsigned char *) NULL) 756 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 757 inject_image->filename); 758 (void) ResetMagickMemory(scanline,0,width*sizeof(*scanline)); 759 huffman_image=CloneImage(inject_image,0,0,MagickTrue,exception); 760 if (huffman_image == (Image *) NULL) 761 { 762 scanline=(unsigned char *) RelinquishMagickMemory(scanline); 763 return(MagickFalse); 764 } 765 (void) SetImageType(huffman_image,BilevelType,exception); 766 byte='\0'; 767 bit=(unsigned char) 0x80; 768 if (LocaleCompare(image_info->magick,"FAX") != 0) 769 Ascii85Initialize(image); 770 else 771 { 772 /* 773 End of line. 774 */ 775 for (k=0; k < 11; k++) 776 OutputBit(0); 777 OutputBit(1); 778 } 779 /* 780 Compress to 1D Huffman pixels. 781 */ 782 q=scanline; 783 for (y=0; y < (ssize_t) huffman_image->rows; y++) 784 { 785 p=GetVirtualPixels(huffman_image,0,y,huffman_image->columns,1,exception); 786 if (p == (const Quantum *) NULL) 787 break; 788 for (x=0; x < (ssize_t) huffman_image->columns; x++) 789 { 790 *q++=(unsigned char) (GetPixelIntensity(huffman_image,p) >= 791 ((double) QuantumRange/2.0) ? 0 : 1); 792 p+=GetPixelChannels(huffman_image); 793 } 794 /* 795 Huffman encode scanline. 796 */ 797 q=scanline; 798 for (n=(ssize_t) width; n > 0; ) 799 { 800 /* 801 Output white run. 802 */ 803 for (runlength=0; ((n > 0) && (*q == 0)); n--) 804 { 805 q++; 806 runlength++; 807 } 808 if (runlength >= 64) 809 { 810 if (runlength < 1792) 811 entry=MWTable+((runlength/64)-1); 812 else 813 entry=EXTable+(MagickMin((size_t) runlength,2560)-1792)/64; 814 runlength-=(long) entry->count; 815 HuffmanOutputCode(entry); 816 } 817 entry=TWTable+MagickMin((size_t) runlength,63); 818 HuffmanOutputCode(entry); 819 if (n != 0) 820 { 821 /* 822 Output black run. 823 */ 824 for (runlength=0; ((*q != 0) && (n > 0)); n--) 825 { 826 q++; 827 runlength++; 828 } 829 if (runlength >= 64) 830 { 831 entry=MBTable+((runlength/64)-1); 832 if (runlength >= 1792) 833 entry=EXTable+(MagickMin((size_t) runlength,2560)-1792)/64; 834 runlength-=(long) entry->count; 835 HuffmanOutputCode(entry); 836 } 837 entry=TBTable+MagickMin((size_t) runlength,63); 838 HuffmanOutputCode(entry); 839 } 840 } 841 /* 842 End of line. 843 */ 844 for (k=0; k < 11; k++) 845 OutputBit(0); 846 OutputBit(1); 847 q=scanline; 848 if (GetPreviousImageInList(huffman_image) == (Image *) NULL) 849 { 850 proceed=SetImageProgress(huffman_image,LoadImageTag,y, 851 huffman_image->rows); 852 if (proceed == MagickFalse) 853 break; 854 } 855 } 856 /* 857 End of page. 858 */ 859 for (i=0; i < 6; i++) 860 { 861 for (k=0; k < 11; k++) 862 OutputBit(0); 863 OutputBit(1); 864 } 865 /* 866 Flush bits. 867 */ 868 if (((int) bit != 0x80) != 0) 869 { 870 if (LocaleCompare(image_info->magick,"FAX") == 0) 871 (void) WriteBlobByte(image,byte); 872 else 873 Ascii85Encode(image,byte); 874 } 875 if (LocaleCompare(image_info->magick,"FAX") != 0) 876 Ascii85Flush(image); 877 huffman_image=DestroyImage(huffman_image); 878 scanline=(unsigned char *) RelinquishMagickMemory(scanline); 879 return(MagickTrue); 880 } 881 882 /* 884 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 885 % % 886 % % 887 % % 888 % L Z W E n c o d e I m a g e % 889 % % 890 % % 891 % % 892 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 893 % 894 % LZWEncodeImage() compresses an image via LZW-coding specific to Postscript 895 % Level II or Portable Document Format. 896 % 897 % The format of the LZWEncodeImage method is: 898 % 899 % MagickBooleanType LZWEncodeImage(Image *image,const size_t length, 900 % unsigned char *magick_restrict pixels,ExceptionInfo *exception) 901 % 902 % A description of each parameter follows: 903 % 904 % o image: the image. 905 % 906 % o length: A value that specifies the number of pixels to compress. 907 % 908 % o pixels: the address of an unsigned array of characters containing the 909 % pixels to compress. 910 % 911 % o exception: return any errors or warnings in this structure. 912 % 913 */ 914 MagickExport MagickBooleanType LZWEncodeImage(Image *image,const size_t length, 915 unsigned char *magick_restrict pixels,ExceptionInfo *exception) 916 { 917 #define LZWClr 256UL /* Clear Table Marker */ 918 #define LZWEod 257UL /* End of Data marker */ 919 #define OutputCode(code) \ 920 { \ 921 accumulator+=code << (32-code_width-number_bits); \ 922 number_bits+=code_width; \ 923 while (number_bits >= 8) \ 924 { \ 925 (void) WriteBlobByte(image,(unsigned char) (accumulator >> 24)); \ 926 accumulator=accumulator << 8; \ 927 number_bits-=8; \ 928 } \ 929 } 930 931 typedef struct _TableType 932 { 933 ssize_t 934 prefix, 935 suffix, 936 next; 937 } TableType; 938 939 register ssize_t 940 i; 941 942 size_t 943 accumulator, 944 number_bits, 945 code_width, 946 last_code, 947 next_index; 948 949 ssize_t 950 index; 951 952 TableType 953 *table; 954 955 /* 956 Allocate string table. 957 */ 958 assert(image != (Image *) NULL); 959 assert(image->signature == MagickCoreSignature); 960 if (image->debug != MagickFalse) 961 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 962 assert(pixels != (unsigned char *) NULL); 963 assert(exception != (ExceptionInfo *) NULL); 964 assert(exception->signature == MagickCoreSignature); 965 table=(TableType *) AcquireQuantumMemory(1UL << 12,sizeof(*table)); 966 if (table == (TableType *) NULL) 967 return(MagickFalse); 968 /* 969 Initialize variables. 970 */ 971 accumulator=0; 972 code_width=9; 973 number_bits=0; 974 last_code=0; 975 OutputCode(LZWClr); 976 for (index=0; index < 256; index++) 977 { 978 table[index].prefix=(-1); 979 table[index].suffix=(short) index; 980 table[index].next=(-1); 981 } 982 next_index=LZWEod+1; 983 code_width=9; 984 last_code=(size_t) pixels[0]; 985 for (i=1; i < (ssize_t) length; i++) 986 { 987 /* 988 Find string. 989 */ 990 index=(ssize_t) last_code; 991 while (index != -1) 992 if ((table[index].prefix != (ssize_t) last_code) || 993 (table[index].suffix != (ssize_t) pixels[i])) 994 index=table[index].next; 995 else 996 { 997 last_code=(size_t) index; 998 break; 999 } 1000 if (last_code != (size_t) index) 1001 { 1002 /* 1003 Add string. 1004 */ 1005 OutputCode(last_code); 1006 table[next_index].prefix=(ssize_t) last_code; 1007 table[next_index].suffix=(short) pixels[i]; 1008 table[next_index].next=table[last_code].next; 1009 table[last_code].next=(ssize_t) next_index; 1010 next_index++; 1011 /* 1012 Did we just move up to next bit width? 1013 */ 1014 if ((next_index >> code_width) != 0) 1015 { 1016 code_width++; 1017 if (code_width > 12) 1018 { 1019 /* 1020 Did we overflow the max bit width? 1021 */ 1022 code_width--; 1023 OutputCode(LZWClr); 1024 for (index=0; index < 256; index++) 1025 { 1026 table[index].prefix=(-1); 1027 table[index].suffix=index; 1028 table[index].next=(-1); 1029 } 1030 next_index=LZWEod+1; 1031 code_width=9; 1032 } 1033 } 1034 last_code=(size_t) pixels[i]; 1035 } 1036 } 1037 /* 1038 Flush tables. 1039 */ 1040 OutputCode(last_code); 1041 OutputCode(LZWEod); 1042 if (number_bits != 0) 1043 (void) WriteBlobByte(image,(unsigned char) (accumulator >> 24)); 1044 table=(TableType *) RelinquishMagickMemory(table); 1045 return(MagickTrue); 1046 } 1047 1048 /* 1050 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1051 % % 1052 % % 1053 % % 1054 % P a c k b i t s E n c o d e I m a g e % 1055 % % 1056 % % 1057 % % 1058 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1059 % 1060 % PackbitsEncodeImage() compresses an image via Macintosh Packbits encoding 1061 % specific to Postscript Level II or Portable Document Format. To ensure 1062 % portability, the binary Packbits bytes are encoded as ASCII Base-85. 1063 % 1064 % The format of the PackbitsEncodeImage method is: 1065 % 1066 % MagickBooleanType PackbitsEncodeImage(Image *image,const size_t length, 1067 % unsigned char *magick_restrict pixels) 1068 % 1069 % A description of each parameter follows: 1070 % 1071 % o image: the image. 1072 % 1073 % o length: A value that specifies the number of pixels to compress. 1074 % 1075 % o pixels: the address of an unsigned array of characters containing the 1076 % pixels to compress. 1077 % 1078 */ 1079 MagickExport MagickBooleanType PackbitsEncodeImage(Image *image, 1080 const size_t length,unsigned char *magick_restrict pixels, 1081 ExceptionInfo *exception) 1082 { 1083 int 1084 count; 1085 1086 register ssize_t 1087 i, 1088 j; 1089 1090 unsigned char 1091 *packbits; 1092 1093 /* 1094 Compress pixels with Packbits encoding. 1095 */ 1096 assert(image != (Image *) NULL); 1097 assert(image->signature == MagickCoreSignature); 1098 if (image->debug != MagickFalse) 1099 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 1100 assert(pixels != (unsigned char *) NULL); 1101 packbits=(unsigned char *) AcquireQuantumMemory(128UL,sizeof(*packbits)); 1102 if (packbits == (unsigned char *) NULL) 1103 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 1104 image->filename); 1105 for (i=(ssize_t) length; i != 0; ) 1106 { 1107 switch (i) 1108 { 1109 case 1: 1110 { 1111 i--; 1112 (void) WriteBlobByte(image,(unsigned char) 0); 1113 (void) WriteBlobByte(image,*pixels); 1114 break; 1115 } 1116 case 2: 1117 { 1118 i-=2; 1119 (void) WriteBlobByte(image,(unsigned char) 1); 1120 (void) WriteBlobByte(image,*pixels); 1121 (void) WriteBlobByte(image,pixels[1]); 1122 break; 1123 } 1124 case 3: 1125 { 1126 i-=3; 1127 if ((*pixels == *(pixels+1)) && (*(pixels+1) == *(pixels+2))) 1128 { 1129 (void) WriteBlobByte(image,(unsigned char) ((256-3)+1)); 1130 (void) WriteBlobByte(image,*pixels); 1131 break; 1132 } 1133 (void) WriteBlobByte(image,(unsigned char) 2); 1134 (void) WriteBlobByte(image,*pixels); 1135 (void) WriteBlobByte(image,pixels[1]); 1136 (void) WriteBlobByte(image,pixels[2]); 1137 break; 1138 } 1139 default: 1140 { 1141 if ((*pixels == *(pixels+1)) && (*(pixels+1) == *(pixels+2))) 1142 { 1143 /* 1144 Packed run. 1145 */ 1146 count=3; 1147 while (((ssize_t) count < i) && (*pixels == *(pixels+count))) 1148 { 1149 count++; 1150 if (count >= 127) 1151 break; 1152 } 1153 i-=count; 1154 (void) WriteBlobByte(image,(unsigned char) ((256-count)+1)); 1155 (void) WriteBlobByte(image,*pixels); 1156 pixels+=count; 1157 break; 1158 } 1159 /* 1160 Literal run. 1161 */ 1162 count=0; 1163 while ((*(pixels+count) != *(pixels+count+1)) || 1164 (*(pixels+count+1) != *(pixels+count+2))) 1165 { 1166 packbits[count+1]=pixels[count]; 1167 count++; 1168 if (((ssize_t) count >= (i-3)) || (count >= 127)) 1169 break; 1170 } 1171 i-=count; 1172 *packbits=(unsigned char) (count-1); 1173 for (j=0; j <= (ssize_t) count; j++) 1174 (void) WriteBlobByte(image,packbits[j]); 1175 pixels+=count; 1176 break; 1177 } 1178 } 1179 } 1180 (void) WriteBlobByte(image,(unsigned char) 128); /* EOD marker */ 1181 packbits=(unsigned char *) RelinquishMagickMemory(packbits); 1182 return(MagickTrue); 1183 } 1184 1185 #if defined(MAGICKCORE_ZLIB_DELEGATE) 1187 /* 1188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1189 % % 1190 % % 1191 % % 1192 % Z L I B E n c o d e I m a g e % 1193 % % 1194 % % 1195 % % 1196 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1197 % 1198 % ZLIBEncodeImage compresses an image via ZLIB-coding specific to 1199 % Postscript Level II or Portable Document Format. 1200 % 1201 % The format of the ZLIBEncodeImage method is: 1202 % 1203 % MagickBooleanType ZLIBEncodeImage(Image *image,const size_t length, 1204 % unsigned char *magick_restrict pixels,ExceptionInfo *exception) 1205 % 1206 % A description of each parameter follows: 1207 % 1208 % o file: the address of a structure of type FILE. ZLIB encoded pixels 1209 % are written to this file. 1210 % 1211 % o length: A value that specifies the number of pixels to compress. 1212 % 1213 % o pixels: the address of an unsigned array of characters containing the 1214 % pixels to compress. 1215 % 1216 % o exception: return any errors or warnings in this structure. 1217 % 1218 */ 1219 1220 static voidpf AcquireZIPMemory(voidpf context,unsigned int items, 1221 unsigned int size) 1222 { 1223 (void) context; 1224 return((voidpf) AcquireQuantumMemory(items,size)); 1225 } 1226 1227 static void RelinquishZIPMemory(voidpf context,voidpf memory) 1228 { 1229 (void) context; 1230 memory=RelinquishMagickMemory(memory); 1231 } 1232 1233 MagickExport MagickBooleanType ZLIBEncodeImage(Image *image,const size_t length, 1234 unsigned char *magick_restrict pixels,ExceptionInfo *exception) 1235 { 1236 int 1237 status; 1238 1239 register ssize_t 1240 i; 1241 1242 size_t 1243 compress_packets; 1244 1245 unsigned char 1246 *compress_pixels; 1247 1248 z_stream 1249 stream; 1250 1251 assert(image != (Image *) NULL); 1252 assert(image->signature == MagickCoreSignature); 1253 if (image->debug != MagickFalse) 1254 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 1255 compress_packets=(size_t) (1.001*length+12); 1256 compress_pixels=(unsigned char *) AcquireQuantumMemory(compress_packets, 1257 sizeof(*compress_pixels)); 1258 if (compress_pixels == (unsigned char *) NULL) 1259 ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed", 1260 image->filename); 1261 stream.next_in=pixels; 1262 stream.avail_in=(unsigned int) length; 1263 stream.next_out=compress_pixels; 1264 stream.avail_out=(unsigned int) compress_packets; 1265 stream.zalloc=AcquireZIPMemory; 1266 stream.zfree=RelinquishZIPMemory; 1267 stream.opaque=(voidpf) NULL; 1268 status=deflateInit(&stream,(int) (image->quality == 1269 UndefinedCompressionQuality ? 7 : MagickMin(image->quality/10,9))); 1270 if (status == Z_OK) 1271 { 1272 status=deflate(&stream,Z_FINISH); 1273 if (status == Z_STREAM_END) 1274 status=deflateEnd(&stream); 1275 else 1276 (void) deflateEnd(&stream); 1277 compress_packets=(size_t) stream.total_out; 1278 } 1279 if (status != Z_OK) 1280 ThrowBinaryException(CoderError,"UnableToZipCompressImage",image->filename) 1281 for (i=0; i < (ssize_t) compress_packets; i++) 1282 (void) WriteBlobByte(image,compress_pixels[i]); 1283 compress_pixels=(unsigned char *) RelinquishMagickMemory(compress_pixels); 1284 return(MagickTrue); 1285 } 1286 #else 1287 MagickExport MagickBooleanType ZLIBEncodeImage(Image *image, 1288 const size_t magick_unused(length),unsigned char *magick_unused(pixels), 1289 ExceptionInfo *exception) 1290 { 1291 assert(image != (Image *) NULL); 1292 assert(image->signature == MagickCoreSignature); 1293 if (image->debug != MagickFalse) 1294 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 1295 (void) ThrowMagickException(exception,GetMagickModule(),MissingDelegateError, 1296 "DelegateLibrarySupportNotBuiltIn","'%s' (ZIP)",image->filename); 1297 return(MagickFalse); 1298 } 1299 #endif 1300