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