1 /********************************************************************************
2 * *
3 * G I F I n p u t / O u t p u t *
4 * *
5 *********************************************************************************
6 * Copyright (C) 1998,2006 by Jeroen van der Zijp. All Rights Reserved. *
7 *********************************************************************************
8 * This library is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU Lesser General Public *
10 * License as published by the Free Software Foundation; either *
11 * version 2.1 of the License, or (at your option) any later version. *
12 * *
13 * This library is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
16 * Lesser General Public License for more details. *
17 * *
18 * You should have received a copy of the GNU Lesser General Public *
19 * License along with this library; if not, write to the Free Software *
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. *
21 *********************************************************************************
22 * $Id: fxgifio.cpp,v 1.79 2006/01/22 17:58:52 fox Exp $ *
23 ********************************************************************************/
24 #include "xincs.h"
25 #include "fxver.h"
26 #include "fxdefs.h"
27 #include "FXHash.h"
28 #include "FXStream.h"
29 #include "fxpriv.h"
30
31
32 /*
33 Notes:
34
35 - "The Graphics Interchange Format(c) is the Copyright property of
36 CompuServe Incorporated. GIF(sm) is a Service Mark property of
37 CompuServe Incorporated."
38
39 - Make sure reading and writing GIF transfers same number of bytes
40 from/to the stream.
41
42 - For a transparent pixel, we zero out the alpha channel but leave
43 the RGB intact; this way, we can maintain the original RGB data.
44
45 - The interleaving works as follows:
46
47 Pass1 Pass2 Pass3 Pass4
48 Start 0 4 3 1
49 Step 8 8 4 2
50
51 - LZW Patent has expired 6/20/2003; so compression now implemented.
52 */
53
54
55 using namespace FX;
56
57 /*******************************************************************************/
58
59 namespace FX {
60
61
62 extern FXAPI bool fxcheckGIF(FXStream& store);
63 extern FXAPI bool fxloadGIF(FXStream& store,FXColor*& data,FXint& width,FXint& height);
64 extern FXAPI bool fxsaveGIF(FXStream& store,const FXColor *data,FXint width,FXint height,bool fast=true);
65
66
67 // Codes found in the GIF specification
68 const FXuchar TAG_EXTENSION = 0x21; // Extension block
69 const FXuchar TAG_GRAPHIC = 0xF9; // Graphic control block
70 const FXuchar TAG_IMAGE = 0x2c; // Image separator
71 const FXuchar TAG_TERMINATOR = 0x00; // Block terminator
72 const FXuchar TAG_GRAPHICSIZE = 0x04; // Graphic block size
73 const FXuchar TAG_IMAGEFLAGS = 0x00; // Image flags
74 const FXuchar TAG_ZERO = 0x00; // Just a zero
75 const FXuchar TAG_ENDFILE = 0x3B; // End of file
76 const FXuchar TAG_TRANSPARENT = 0x01; // Transparent flag
77 const FXuchar TAG_SIG1 = 0x47; // Signature G
78 const FXuchar TAG_SIG2 = 0x49; // Signature I
79 const FXuchar TAG_SIG3 = 0x46; // Signature F
80 const FXuchar TAG_VER = 0x38; // Version byte
81 const FXuchar TAG_NEW = 0x39; // New version
82 const FXuchar TAG_OLD = 0x37; // Old version
83 const FXuchar TAG_SUF = 0x61; // Version suffix
84
85
86 // Check if stream contains a GIF
fxcheckGIF(FXStream & store)87 bool fxcheckGIF(FXStream& store){
88 FXuchar signature[3];
89 store.load(signature,3);
90 store.position(-3,FXFromCurrent);
91 return signature[0]==TAG_SIG1 && signature[1]==TAG_SIG2 && signature[2]==TAG_SIG3;
92 }
93
94
95 // Load image from stream
fxloadGIF(FXStream & store,FXColor * & data,FXint & width,FXint & height)96 bool fxloadGIF(FXStream& store,FXColor*& data,FXint& width,FXint& height){
97 const FXint Yinit[4]={0,4,2,1};
98 const FXint Yinc[4]={8,8,4,2};
99 FXint imwidth,imheight,interlace,ncolors,npixels,maxpixels,i;
100 FXuchar c1,c2,c3,sbsize,flags,alpha,*ptr,*buf,*pix;
101 FXColor colormap[256];
102 FXint BitOffset; // Bit Offset of next code
103 FXint ByteOffset; // Byte offset of next code
104 FXint XC,YC; // Output X and Y coords of current pixel
105 FXint Pass; // Used by output routine if interlaced pic
106 FXint OutCount; // Decompressor output 'stack count'
107 FXint CodeSize; // Code size, read from GIF header
108 FXint InitCodeSize; // Starting code size, used during Clear
109 FXint Code; // Value returned by ReadCode
110 FXint MaxCode; // limiting value for current code size
111 FXint ClearCode; // GIF clear code
112 FXint EOFCode; // GIF end-of-information code
113 FXint CurCode,OldCode,InCode; // Decompressor variables
114 FXint FirstFree; // First free code, generated per GIF spec
115 FXint FreeCode; // Decompressor,next free slot in hash table
116 FXint FinChar; // Decompressor variable
117 FXint BitMask; // AND mask for data size
118 FXint ReadMask; // Code AND mask for current code size
119 FXint Prefix[4096]; // The hash table used by the decompressor
120 FXint Suffix[4096]; // The hash table used by the decompressor
121 FXint OutCode[4097]; // An output array used by the decompressor
122
123 // Null out
124 data=NULL;
125 width=0;
126 height=0;
127
128 // Load signature
129 store >> c1;
130 store >> c2;
131 store >> c3;
132
133 // Check signature
134 if(c1!=TAG_SIG1 || c2!=TAG_SIG2 || c3!=TAG_SIG3) return false;
135
136 // Load version
137 store >> c1;
138 store >> c2;
139 store >> c3;
140
141 // Check version
142 if(c1!=TAG_VER || (c2!=TAG_OLD && c2!=TAG_NEW) || c3!=TAG_SUF) return false;
143
144 // Get screen descriptor
145 store >> c1 >> c2; // Skip screen width
146 store >> c1 >> c2; // Skip screen height
147 store >> flags; // Get flags
148 store >> alpha; // Background
149 store >> c2; // Skip aspect ratio
150
151 // Determine number of colors
152 ncolors=2<<(flags&7);
153 BitMask=ncolors-1;
154
155 // If no colormap, spec says first 2 colors are black and white
156 colormap[0]=FXRGB(0,0,0);
157 colormap[1]=FXRGB(255,255,255);
158
159 // Read global map if there is one
160 if(flags&0x80){
161 for(i=0; i<ncolors; i++){
162 store >> ((FXuchar*)(colormap+i))[0]; // Blue
163 store >> ((FXuchar*)(colormap+i))[1]; // Green
164 store >> ((FXuchar*)(colormap+i))[2]; // Red
165 ((FXuchar*)(colormap+i))[3]=255; // Alpha
166 }
167 }
168
169 // Process it
170 while(1){
171 store >> c1;
172 if(c1==TAG_EXTENSION){
173
174 // Read extension code
175 store >> c2;
176
177 // Graphic Control Extension
178 if(c2==TAG_GRAPHIC){
179 store >> sbsize;
180 if(sbsize!=TAG_GRAPHICSIZE) return false;
181 store >> flags; // Flags
182 store >> c3 >> c3; // Delay time
183 store >> alpha; // Alpha color index; we suspect alpha<ncolors not always true...
184 store >> c3;
185 if(flags&1){ // Clear alpha channel of alpha color
186 colormap[alpha]&=FXRGBA(255,255,255,0); // Clear the alpha channel but keep the RGB
187 }
188 continue;
189 }
190
191 // Other extension
192 do{
193 store >> sbsize;
194 store.position(store.position()+sbsize);
195 }
196 while(sbsize>0 && !store.eof()); // FIXME this logic still flawed
197 continue;
198 }
199
200 // Image separator
201 if(c1==TAG_IMAGE){
202 store >> c1 >> c2;
203 store >> c1 >> c2;
204
205 // Get image width
206 store >> c1 >> c2;
207 imwidth=(c2<<8)+c1;
208
209 // Get image height
210 store >> c1 >> c2;
211 imheight=(c2<<8)+c1;
212
213 // Get image flags
214 store >> flags;
215
216 // Read local map if there is one
217 if(flags&0x80){
218 ncolors=2<<(flags&7);
219 for(i=0; i<ncolors; i++){
220 store >> ((FXuchar*)(colormap+i))[0]; // Red
221 store >> ((FXuchar*)(colormap+i))[1]; // Green
222 store >> ((FXuchar*)(colormap+i))[2]; // Blue
223 ((FXuchar*)(colormap+i))[3]=255; // Alpha
224 }
225 }
226
227 // Interlaced image
228 interlace=(flags&0x40);
229
230 // Total pixels expected
231 maxpixels=imwidth*imheight;
232
233 // Allocate memory
234 if(!FXMALLOC(&data,FXColor,maxpixels)) return false;
235
236 // Set up pointers; we're using the first 3/4 of the
237 // data array for the compressed data, and the latter 1/4 for
238 // the 8-bit pixel data. At the end of the decompression, we
239 // overwrite the data array with the 32-bit RGBA data.
240 // Note that the unGIF "compressed" data may be larger than
241 // the uncompressed data, hence the large safety factor...
242 buf=(FXuchar*)data;
243 pix=buf+maxpixels+maxpixels+maxpixels;
244
245 // Start reading the raster data. First we get the intial code size
246 // and compute decompressor constant values, based on this code size.
247 store >> c1;
248 CodeSize=c1;
249
250 ClearCode=1<<CodeSize;
251 EOFCode=ClearCode+1;
252 FreeCode=FirstFree=ClearCode+2;
253
254 // The GIF spec has it that the code size is the code size used to
255 // compute the above values is the code size given in the file, but the
256 // code size used in compression/decompression is the code size given in
257 // the file plus one.
258 CodeSize++;
259 InitCodeSize=CodeSize;
260 MaxCode=1<<CodeSize;
261 ReadMask=MaxCode-1;
262
263 // Maximum code should not exceed 4096
264 if(MaxCode>=4096){ FXFREE(&data); return false; }
265
266 // Read all blocks of compressed data into one single buffer.
267 // We have an extra test to make sure we don't write past 3/4
268 // of the buffer:- this could happen in malicious GIF images!
269 ptr=buf;
270 do{
271 store >> sbsize;
272 if(ptr+sbsize>pix){ FXFREE(&data); return false; }
273 store.load(ptr,sbsize);
274 ptr+=sbsize;
275 }
276 while(sbsize>0 && !store.eof()); // FIXME this logic still flawed
277
278 // Initialize
279 BitOffset=XC=YC=Pass=OutCount=OldCode=FinChar=npixels=0;
280
281 // Drop 8-bit pixels in the upper part
282 ptr=pix;
283
284 // Decompress the file, continuing until you see the GIF EOF code.
285 // One obvious enhancement is to add checking for corrupt files here.
286 while(1){
287
288 // Fetch the next code from the raster data stream. The codes can be
289 // any length from 3 to 12 bits, packed into 8-bit bytes, so we have to
290 // maintain our location in the source array as a BIT Offset. We compute
291 // the byte Offset into the raster array by dividing this by 8, pick up
292 // three bytes, compute the bit Offset into our 24-bit chunk, shift to
293 // bring the desired code to the bottom, then mask it off and return it.
294 ByteOffset=BitOffset>>3;
295 Code=(FXuint)buf[ByteOffset]+(((FXuint)buf[ByteOffset+1])<<8)+(((FXuint)buf[ByteOffset+2])<<16);
296 Code>>=(BitOffset&7);
297 BitOffset+=CodeSize;
298 Code&=ReadMask;
299
300 // Are we done?
301 if(Code==EOFCode || npixels>=maxpixels) break;
302
303 // Clear code sets everything back to its initial value, then reads the
304 // immediately subsequent code as uncompressed data.
305 if(Code==ClearCode){
306 CodeSize=InitCodeSize;
307 MaxCode=1<<CodeSize;
308 ReadMask=MaxCode-1;
309 FreeCode=FirstFree;
310
311 // Get next code
312 ByteOffset=BitOffset>>3;
313 Code=(FXuint)buf[ByteOffset]+(((FXuint)buf[ByteOffset+1])<<8)+(((FXuint)buf[ByteOffset+2])<<16);
314 Code>>=(BitOffset&7);
315 BitOffset+=CodeSize;
316 Code&=ReadMask;
317
318 CurCode=OldCode=Code;
319 FinChar=CurCode&BitMask;
320
321 if(!interlace){
322 *ptr++=FinChar;
323 }
324 else{
325 FXASSERT(0<=YC && YC<imheight);
326 FXASSERT(0<=XC && XC<imwidth);
327 ptr[YC*imwidth+XC]=FinChar;
328 XC+=1;
329 if(XC>=imwidth){
330 XC=0;
331 YC+=Yinc[Pass];
332 if(YC>=imheight){
333 Pass++;
334 YC=Yinit[Pass&3];
335 }
336 }
337 }
338 npixels++;
339 }
340
341 // If not a clear code, must be data: save same as CurCode and InCode
342 else{
343
344 // If we're at maxcode and didn't get a clear, stop loading
345 if(FreeCode>=4096){ FXFREE(&data); return false; }
346
347 CurCode=InCode=Code;
348
349 // If greater or equal to FreeCode, not in the hash table yet; repeat the last character decoded
350 if(CurCode>=FreeCode){
351 CurCode=OldCode;
352 if(OutCount>4096){ FXFREE(&data); return false; }
353 OutCode[OutCount++]=FinChar;
354 }
355
356 // Unless this code is raw data, pursue the chain pointed to by CurCode
357 // through the hash table to its end; each code in the chain puts its
358 // associated output code on the output queue.
359 while(CurCode>=ClearCode){
360 if(OutCount>4096 || CurCode>=FreeCode){ FXFREE(&data); return false; }
361 OutCode[OutCount++]=Suffix[CurCode];
362 CurCode=Prefix[CurCode];
363 }
364
365 if(OutCount>4096){ FXFREE(&data); return false; }
366
367 // The last code in the chain is treated as raw data
368 FinChar=CurCode&BitMask;
369 OutCode[OutCount++]=FinChar;
370
371 // Now we put the data out to the Output routine.
372 // It's been stacked LIFO, so deal with it that way...
373
374 // safety thing: prevent exceeding range
375 if(npixels+OutCount>maxpixels) OutCount=maxpixels-npixels;
376
377 npixels+=OutCount;
378 if(!interlace){
379 for(i=OutCount-1; i>=0; i--){
380 *ptr++=OutCode[i];
381 }
382 }
383 else{
384 for(i=OutCount-1; i>=0; i--){
385 FXASSERT(0<=YC && YC<imheight);
386 FXASSERT(0<=XC && XC<imwidth);
387 ptr[YC*imwidth+XC]=OutCode[i];
388 XC+=1;
389 if(XC>=imwidth){
390 XC=0;
391 YC+=Yinc[Pass];
392 if(YC>=imheight){
393 Pass++;
394 YC=Yinit[Pass&3];
395 }
396 }
397 }
398 }
399 OutCount=0;
400
401 // Build the hash table on-the-fly. No table is stored in the file
402 Prefix[FreeCode]=OldCode;
403 Suffix[FreeCode]=FinChar;
404 OldCode=InCode;
405
406 // Point to the next slot in the table. If we exceed the current
407 // MaxCode value, increment the code size unless it's already 12. If it
408 // is, do nothing: the next code decompressed better be CLEAR
409 FreeCode++;
410 if(FreeCode>=MaxCode){
411 if(CodeSize<12){
412 CodeSize++;
413 MaxCode*=2;
414 ReadMask=(1<<CodeSize)-1;
415 }
416 }
417 }
418 }
419
420 // Did the stream stop prematurely?
421 if(npixels!=maxpixels){
422 fxwarning("fxloadGIF: image truncated\n");
423 }
424
425 width=imwidth;
426 height=imheight;
427
428 // Technically, this is incorrect; but we have so
429 // many GIF87a's that we have to keep doing this!
430 colormap[alpha]&=FXRGBA(255,255,255,0);
431
432 // Apply colormap
433 for(i=0; i<maxpixels; i++){
434 data[i]=colormap[pix[i]];
435 }
436
437 // Skip image terminator to fully read all bytes
438 store >> c1;
439
440 return true;
441 }
442
443 // Non of the above, we fail!
444 return false;
445 }
446
447 // Shouldn't get here, but to satisfy compiler
448 return false;
449 }
450
451
452 /*******************************************************************************/
453
454
455 // Save a gif file to a stream
fxsaveGIF(FXStream & store,const FXColor * data,FXint width,FXint height,bool fast)456 bool fxsaveGIF(FXStream& store,const FXColor *data,FXint width,FXint height,bool fast){
457 FXuint clearcode,endcode,freecode,findcode,prefix,current,outaccu,initcodesize,codesize,hash,step;
458 FXint maxpixels,ncolors,bitsperpixel,colormapsize,outbits,src,dst,i;
459 FXuchar c1,c2,alpha,*pixels,*output;
460 FXColor colormap[256];
461 FXuint hashtab[5003];
462 FXushort codetab[5003];
463
464 // Must make sense
465 if(!data || width<=0 || height<=0) return false;
466
467 // How many pixels
468 maxpixels=width*height;
469
470 // Allocate temp buffer for pixels
471 if(!FXMALLOC(&output,FXuchar,(maxpixels<<1))) return false;
472 pixels=output+maxpixels;
473
474 // First, try EZ quantization, because it is exact; a previously
475 // loaded GIF will be re-saved with exactly the same colors.
476 if(!fxezquantize(pixels,data,colormap,ncolors,width,height,256)){
477 if(fast){
478 fxfsquantize(pixels,data,colormap,ncolors,width,height,256);
479 }
480 else{
481 fxwuquantize(pixels,data,colormap,ncolors,width,height,256);
482 }
483 }
484
485 // File signature
486 store << TAG_SIG1;
487 store << TAG_SIG2;
488 store << TAG_SIG3;
489
490 // File version
491 store << TAG_VER;
492 store << TAG_NEW;
493 store << TAG_SUF;
494
495 // Figure out bits per pixel
496 for(bitsperpixel=1; ncolors>(1<<bitsperpixel); bitsperpixel++);
497
498 // Colormap size
499 colormapsize=1<<bitsperpixel;
500
501 // Screen header
502 c1=width;
503 c2=width>>8;
504 store << c1 << c2; // Width
505 c1=height;
506 c2=height>>8;
507 store << c1 << c2; // Height
508 c1=0x80; // There is a color map
509 c1|=(bitsperpixel-1)<<4; // Number of bits of color resolution
510 c1|=(bitsperpixel-1); // The size (in bits) of the colormap
511 store << c1; // Flags
512 store << TAG_ZERO; // Background color
513 store << TAG_ZERO; // Aspect Ratio is none
514
515 // Output colormap
516 for(i=0; i<colormapsize; i++){
517 store << ((FXuchar*)(colormap+i))[0]; // Blue
518 store << ((FXuchar*)(colormap+i))[1]; // Green
519 store << ((FXuchar*)(colormap+i))[2]; // Red
520 }
521
522 // Output Graphics Control Extension, if alpha is present
523 for(i=0,alpha=0; i<ncolors; i++){
524 if(((FXuchar*)(colormap+i))[3]==0){
525 alpha=i;
526 store << TAG_EXTENSION; // Extension Introducer
527 store << TAG_GRAPHIC; // Graphic Control Label
528 store << TAG_GRAPHICSIZE; // Block Size
529 store << TAG_TRANSPARENT; // Disposal Method
530 store << TAG_ZERO; // Delay Time
531 store << TAG_ZERO;
532 store << alpha; // Transparent color index
533 store << TAG_TERMINATOR; // Block Terminator
534 break;
535 }
536 }
537
538 // Image descriptor
539 store << TAG_IMAGE; // Image separator
540 store << TAG_ZERO; // Image offset X
541 store << TAG_ZERO;
542 store << TAG_ZERO; // Image offset Y
543 store << TAG_ZERO;
544 c1=width;
545 c2=width>>8;
546 store << c1 << c2; // Width
547 c1=height;
548 c2=height>>8;
549 store << c1 << c2; // Height
550 store << TAG_IMAGEFLAGS; // Flags: no local map, no interlace
551
552 // Figure out code size and stuff
553 initcodesize=(bitsperpixel<=1)?2:bitsperpixel;
554 codesize=initcodesize+1;
555 clearcode=1<<(codesize-1);
556 endcode=clearcode+1;
557
558 // Now for the beef...
559 c1=initcodesize;
560 store << c1; // Write the Code size
561
562 // Clear hash table
563 memset(hashtab,0xff,sizeof(hashtab));
564 freecode=clearcode+2;
565
566 // Output clear code
567 FXASSERT(clearcode<(1u<<codesize));
568 outaccu=clearcode;
569 outbits=codesize;
570
571 // Compress image
572 src=dst=0;
573 prefix=pixels[src++];
574 while(1){
575
576 // Flush filled out bytes
577 while(outbits>=8){
578 output[dst++]=(FXuchar)outaccu;
579 outaccu>>=8;
580 outbits-=8;
581 }
582
583 // Done yet
584 if(src>=maxpixels) break;
585
586 // Get next pixel
587 current=pixels[src++];
588
589 // Check if in hash table
590 findcode=(current<<12)+prefix;
591 hash=findcode%5003; // 0<=hash<=5002
592 step=findcode%4999+1; // 1<=step<=4999
593 while(hashtab[hash]!=0xffffffff){ // Occupied slot?
594 if(hashtab[hash]==findcode){ // Existing prefix
595 prefix=codetab[hash]; // Code for prefix
596 goto nxt;
597 }
598 hash=(hash+step)%5003;
599 }
600
601 // Output prefix code
602 FXASSERT(prefix<(1u<<codesize));
603 FXASSERT(outbits+codesize<=32);
604 outaccu|=prefix<<outbits;
605 outbits+=codesize;
606
607 // New prefix code
608 prefix=current;
609
610 // If still room, enter into hash table
611 if(freecode<4096){ // Add to hash table
612 if(freecode>=(1u<<codesize) && codesize<12u) codesize++;
613 codetab[hash]=freecode++;
614 hashtab[hash]=findcode;
615 }
616
617 // Else issue clear code
618 else{
619 FXASSERT(clearcode<(1u<<codesize));
620 FXASSERT(outbits+codesize<=32);
621 outaccu|=clearcode<<outbits;
622 outbits+=codesize;
623
624 // Clear hash table
625 memset(hashtab,0xff,sizeof(hashtab));
626 freecode=clearcode+2;
627 codesize=initcodesize+1;
628 }
629
630 // Next pixel
631 nxt:continue;
632 }
633
634 // Output final prefix code
635 FXASSERT(prefix<(1u<<codesize));
636 FXASSERT(outbits+codesize<=32);
637 outaccu|=prefix<<outbits;
638 outbits+=codesize;
639
640 // Output end code
641 FXASSERT(endcode<(1u<<codesize));
642 FXASSERT(outbits+codesize<=32);
643 outaccu|=endcode<<outbits;
644 outbits+=codesize;
645
646 // FLush remaining bits out
647 while(outbits>0){
648 output[dst++]=(FXuchar)outaccu;
649 outaccu>>=8;
650 outbits-=8;
651 }
652
653 // Write blocks
654 for(src=0; src<dst; src+=c1){
655 c1=FXMIN(255,(dst-src));
656 store << c1;
657 store.save(&output[src],c1);
658 }
659
660 // Trailer
661 store << TAG_TERMINATOR; // Block terminator
662 store << TAG_ENDFILE; // File terminator
663
664 // Free storage
665 FXFREE(&output);
666 return true;
667 }
668
669
670 }
671
672