1 // Gmsh - Copyright (C) 1997-2021 C. Geuzaine, J.-F. Remacle
2 //
3 // See the LICENSE.txt file in the Gmsh root directory for license information.
4 // Please report all issues on https://gitlab.onelab.info/gmsh/gmsh/issues.
5
6 /*
7 * Warning: This code is really a dirty hack. It SHOULD be cleaned
8 * (and most of all, all the static variables should be removed).
9 *
10 * It is based on
11 *
12 * - libppm3.c - ppm utility library part 3
13 * - ppmquant.c - quantize the colors in a pixmap down to a specified number
14 *
15 * Copyright (C) 1989, 1991 by Jef Poskanzer.
16 *
17 * Permission to use, copy, modify, and distribute this software and its
18 * documentation for any purpose and without fee is hereby granted, provided
19 * that the above copyright notice appear in all copies and that both that
20 * copyright notice and this permission notice appear in supporting
21 * documentation. This software is provided "as is" without express or
22 * implied warranty.
23 *
24 * and
25 *
26 * - ppmtogif.c - read a portable pixmap and produce a GIF file
27 *
28 * Based on GIFENCOD by David Rowley <mgardi@watdscu.waterloo.edu>.A
29 * Lempel-Zim compression based on "compress".
30 *
31 * Modified by Marcel Wijkstra <wijkstra@fwi.uva.nl>
32 *
33 * Copyright (C) 1989 by Jef Poskanzer.
34 *
35 * Permission to use, copy, modify, and distribute this software and its
36 * documentation for any purpose and without fee is hereby granted, provided
37 * that the above copyright notice appear in all copies and that both that
38 * copyright notice and this permission notice appear in supporting
39 * documentation. This software is provided "as is" without express or
40 * implied warranty.
41 *
42 * The Graphics Interchange Format(c) is the Copyright property of
43 * CompuServe Incorporated. GIF(sm) is a Service Mark property of
44 * CompuServe Incorporated.
45 *
46 */
47
48 #include "MallocUtils.h"
49 #include "gl2gif.h"
50
51 /* PPM colormap routines */
52
53 #define HASH_SIZE 20023
54 #define ppm_hashpixel(p) (((int)(p)&0x7fffffff) % HASH_SIZE)
55
56 /* Color histogram stuff */
57 namespace {
58 typedef struct colorhist_item *colorhist_vector;
59 struct colorhist_item {
60 pixel color;
61 int value;
62 };
63
64 typedef struct colorhist_list_item *colorhist_list;
65 struct colorhist_list_item {
66 struct colorhist_item ch;
67 colorhist_list next;
68 };
69 }
70
71 /* Color hash table stuff */
72
73 typedef colorhist_list *colorhash_table;
74
75 static int static_red[MAX_GIFCOLORS];
76 static int static_green[MAX_GIFCOLORS];
77 static int static_blue[MAX_GIFCOLORS];
78 static int static_perm[MAX_GIFCOLORS], static_permi[MAX_GIFCOLORS];
79 static int static_nbcolors;
80 static pixel **static_pixels;
81 static colorhash_table static_cht;
82
ppm_alloccolorhash()83 static colorhash_table ppm_alloccolorhash()
84 {
85 colorhash_table cht;
86 int i;
87
88 cht = (colorhash_table)Malloc(HASH_SIZE * sizeof(colorhist_list));
89
90 for(i = 0; i < HASH_SIZE; ++i) cht[i] = (colorhist_list)nullptr;
91
92 return cht;
93 }
94
ppm_freecolorhash(colorhash_table cht)95 static void ppm_freecolorhash(colorhash_table cht)
96 {
97 int i;
98 colorhist_list chl, chlnext;
99
100 for(i = 0; i < HASH_SIZE; ++i)
101 for(chl = cht[i]; chl != (colorhist_list)nullptr; chl = chlnext) {
102 chlnext = chl->next;
103 Free((char *)chl);
104 }
105 Free((char *)cht);
106 }
107
ppm_computecolorhash(pixel ** const pixels,const int cols,const int rows,const int maxcolors,int * const colorsP)108 static colorhash_table ppm_computecolorhash(pixel **const pixels,
109 const int cols, const int rows,
110 const int maxcolors,
111 int *const colorsP)
112 {
113 colorhash_table cht;
114 const pixel *pP;
115 colorhist_list chl;
116 int col, row, hash;
117
118 cht = ppm_alloccolorhash();
119 *colorsP = 0;
120
121 /* Go through the entire image, building a hash table of colors. */
122 for(row = 0; row < rows; ++row)
123 for(col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
124 hash = ppm_hashpixel(*pP);
125 for(chl = cht[hash]; chl != (colorhist_list)nullptr; chl = chl->next)
126 if(PPM_EQUAL(chl->ch.color, *pP)) break;
127 if(chl != (colorhist_list)nullptr)
128 ++(chl->ch.value);
129 else {
130 if(++(*colorsP) > maxcolors) {
131 ppm_freecolorhash(cht);
132 return (colorhash_table)nullptr;
133 }
134 chl = (colorhist_list)Malloc(sizeof(struct colorhist_list_item));
135 chl->ch.color = *pP;
136 chl->ch.value = 1;
137 chl->next = cht[hash];
138 cht[hash] = chl;
139 }
140 }
141
142 return cht;
143 }
144
ppm_addtocolorhash(colorhash_table cht,const pixel * const colorP,const int value)145 static int ppm_addtocolorhash(colorhash_table cht, const pixel *const colorP,
146 const int value)
147 {
148 int hash;
149 colorhist_list chl;
150
151 chl = (colorhist_list)Malloc(sizeof(struct colorhist_list_item));
152 hash = ppm_hashpixel(*colorP);
153 chl->ch.color = *colorP;
154 chl->ch.value = value;
155 chl->next = cht[hash];
156 cht[hash] = chl;
157 return 0;
158 }
159
ppm_colorhashtocolorhist(const colorhash_table cht,const int maxcolors)160 static colorhist_vector ppm_colorhashtocolorhist(const colorhash_table cht,
161 const int maxcolors)
162 {
163 colorhist_vector chv;
164 colorhist_list chl;
165 int i, j;
166
167 /* Now collate the hash table into a simple colorhist array. */
168 chv = (colorhist_vector)Malloc(maxcolors * sizeof(struct colorhist_item));
169 /* Loop through the hash table. */
170 j = 0;
171 for(i = 0; i < HASH_SIZE; ++i)
172 for(chl = cht[i]; chl != (colorhist_list)nullptr; chl = chl->next) {
173 /* Add the new entry. */
174 chv[j] = chl->ch;
175 ++j;
176 }
177
178 /* All done. */
179 return chv;
180 }
181
ppm_colorhisttocolorhash(const colorhist_vector chv,const int colors)182 static colorhash_table ppm_colorhisttocolorhash(const colorhist_vector chv,
183 const int colors)
184 {
185 colorhash_table cht;
186 int i, hash;
187 pixel color;
188 colorhist_list chl;
189
190 cht = ppm_alloccolorhash(); /* Initializes to NULLs */
191
192 for(i = 0; i < colors; ++i) {
193 color = chv[i].color;
194 hash = ppm_hashpixel(color);
195 for(chl = cht[hash]; chl != (colorhist_list)nullptr; chl = chl->next)
196 if(PPM_EQUAL(chl->ch.color, color))
197 Msg::Error("GIF: same color found twice - %d %d %d", PPM_GETR(color),
198 PPM_GETG(color), PPM_GETB(color));
199 chl = (colorhist_list)Malloc(sizeof(struct colorhist_list_item));
200 chl->ch.color = color;
201 chl->ch.value = i;
202 chl->next = cht[hash];
203 cht[hash] = chl;
204 }
205
206 return cht;
207 }
208
ppm_computecolorhist(pixel ** const pixels,const int cols,const int rows,const int maxcolors,int * const colorsP)209 static colorhist_vector ppm_computecolorhist(pixel **const pixels,
210 const int cols, const int rows,
211 const int maxcolors,
212 int *const colorsP)
213 {
214 colorhash_table cht;
215 colorhist_vector chv;
216
217 cht = ppm_computecolorhash(pixels, cols, rows, maxcolors, colorsP);
218 if(cht == (colorhash_table)nullptr) return (colorhist_vector)nullptr;
219 chv = ppm_colorhashtocolorhist(cht, maxcolors);
220 ppm_freecolorhash(cht);
221 return chv;
222 }
223
ppm_lookupcolor(const colorhash_table cht,const pixel * const colorP)224 static int ppm_lookupcolor(const colorhash_table cht, const pixel *const colorP)
225 {
226 int hash;
227 colorhist_list chl;
228
229 hash = ppm_hashpixel(*colorP);
230 for(chl = cht[hash]; chl != (colorhist_list)nullptr; chl = chl->next)
231 if(PPM_EQUAL(chl->ch.color, *colorP)) return chl->ch.value;
232
233 return -1;
234 }
235
ppm_freecolorhist(colorhist_vector chv)236 static void ppm_freecolorhist(colorhist_vector chv) { Free((char *)chv); }
237
colorstobpp(int colors)238 static int colorstobpp(int colors)
239 {
240 int bpp;
241
242 if(colors <= 2)
243 bpp = 1;
244 else if(colors <= 4)
245 bpp = 2;
246 else if(colors <= 8)
247 bpp = 3;
248 else if(colors <= 16)
249 bpp = 4;
250 else if(colors <= 32)
251 bpp = 5;
252 else if(colors <= 64)
253 bpp = 6;
254 else if(colors <= 128)
255 bpp = 7;
256 else if(colors <= 256)
257 bpp = 8;
258 else {
259 Msg::Error("GIF: can't happen: too many colors");
260 bpp = 8;
261 }
262
263 return bpp;
264 }
265
sqr(int x)266 static int sqr(int x) { return x * x; }
267
closestcolor(pixel color)268 static int closestcolor(pixel color)
269 {
270 int i, r, g, b, d, imin = 0, dmin;
271
272 r = (int)PPM_GETR(color);
273 g = (int)PPM_GETG(color);
274 b = (int)PPM_GETB(color);
275
276 dmin = 1000000;
277 for(i = 0; i < static_nbcolors; i++) {
278 d = sqr(r - static_red[i]) + sqr(g - static_green[i]) +
279 sqr(b - static_blue[i]);
280 if(d < dmin) {
281 dmin = d;
282 imin = i;
283 }
284 }
285 ppm_addtocolorhash(static_cht, &color, static_permi[imin]);
286 return imin;
287 }
288
GetPixel(int x,int y)289 static int GetPixel(int x, int y)
290 {
291 int color;
292
293 color = ppm_lookupcolor(static_cht, &static_pixels[y][x]);
294 if(color == -1)
295 color = closestcolor(static_pixels[y][x]);
296 else
297 color = static_perm[color];
298 return color;
299 }
300
301 /* PPM quantization */
302
303 /* #define LARGE_NORM */
304 #define LARGE_LUM
305
306 /* #define REP_CENTER_BOX */
307 /* #define REP_AVERAGE_COLORS */
308 #define REP_AVERAGE_PIXELS
309
310 typedef struct box *box_vector;
311 struct box {
312 int ind;
313 int colors;
314 int sum;
315 };
316
redcompare(const void * ch1,const void * ch2)317 static int redcompare(const void *ch1, const void *ch2)
318 {
319 return (int)PPM_GETR(((colorhist_vector)ch1)->color) -
320 (int)PPM_GETR(((colorhist_vector)ch2)->color);
321 }
322
greencompare(const void * ch1,const void * ch2)323 static int greencompare(const void *ch1, const void *ch2)
324 {
325 return (int)PPM_GETG(((colorhist_vector)ch1)->color) -
326 (int)PPM_GETG(((colorhist_vector)ch2)->color);
327 }
328
bluecompare(const void * ch1,const void * ch2)329 static int bluecompare(const void *ch1, const void *ch2)
330 {
331 return (int)PPM_GETB(((colorhist_vector)ch1)->color) -
332 (int)PPM_GETB(((colorhist_vector)ch2)->color);
333 }
334
sumcompare(const void * b1,const void * b2)335 static int sumcompare(const void *b1, const void *b2)
336 {
337 return (((box_vector)b2)->sum - ((box_vector)b1)->sum);
338 }
339
340 /*
341 * Here is the fun part, the median-cut colormap generator. This is based
342 * on Paul Heckbert's paper "Color Image Quantization for Frame Buffer
343 * Display", SIGGRAPH '82 Proceedings, page 297.
344 */
345
mediancut(colorhist_vector chv,int colors,int sum,pixval maxval,int newcolors)346 static colorhist_vector mediancut(colorhist_vector chv, int colors, int sum,
347 pixval maxval, int newcolors)
348 {
349 colorhist_vector colormap;
350 box_vector bv;
351 int bi, i;
352 int boxes;
353
354 bv = (box_vector)malloc(sizeof(struct box) * newcolors);
355 colormap =
356 (colorhist_vector)malloc(sizeof(struct colorhist_item) * newcolors);
357 if(bv == (box_vector)nullptr || colormap == (colorhist_vector)nullptr)
358 Msg::Error("GIF: out of memory");
359 for(i = 0; i < newcolors; ++i) PPM_ASSIGN(colormap[i].color, 0, 0, 0);
360
361 /*
362 * Set up the initial box.
363 */
364 bv[0].ind = 0;
365 bv[0].colors = colors;
366 bv[0].sum = sum;
367 boxes = 1;
368
369 /*
370 * Main loop: split boxes until we have enough.
371 */
372 while(boxes < newcolors) {
373 int indx, clrs;
374 int sm;
375 int minr, maxr, ming, maxg, minb, maxb, v;
376 int halfsum, lowersum;
377
378 /*
379 * Find the first splittable box.
380 */
381 for(bi = 0; bi < boxes; ++bi)
382 if(bv[bi].colors >= 2) break;
383 if(bi == boxes) break; /* ran out of colors! */
384 indx = bv[bi].ind;
385 clrs = bv[bi].colors;
386 sm = bv[bi].sum;
387
388 /*
389 * Go through the box finding the minimum and maximum of each
390 * component - the boundaries of the box.
391 */
392 minr = maxr = PPM_GETR(chv[indx].color);
393 ming = maxg = PPM_GETG(chv[indx].color);
394 minb = maxb = PPM_GETB(chv[indx].color);
395 for(i = 1; i < clrs; ++i) {
396 v = PPM_GETR(chv[indx + i].color);
397 if(v < minr) minr = v;
398 if(v > maxr) maxr = v;
399 v = PPM_GETG(chv[indx + i].color);
400 if(v < ming) ming = v;
401 if(v > maxg) maxg = v;
402 v = PPM_GETB(chv[indx + i].color);
403 if(v < minb) minb = v;
404 if(v > maxb) maxb = v;
405 }
406
407 /*
408 * Find the largest dimension, and sort by that component. I have
409 * included two methods for determining the "largest" dimension;
410 * first by simply comparing the range in RGB space, and second
411 * by transforming into luminosities before the comparison. You
412 * can switch which method is used by switching the commenting on
413 * the LARGE_ defines at the beginning of this source file.
414 */
415 #ifdef LARGE_NORM
416 if(maxr - minr >= maxg - ming && maxr - minr >= maxb - minb)
417 qsort((char *)&(chv[indx]), clrs, sizeof(struct colorhist_item),
418 redcompare);
419 else if(maxg - ming >= maxb - minb)
420 qsort((char *)&(chv[indx]), clrs, sizeof(struct colorhist_item),
421 greencompare);
422 else
423 qsort((char *)&(chv[indx]), clrs, sizeof(struct colorhist_item),
424 bluecompare);
425 #endif
426
427 #ifdef LARGE_LUM
428 pixel p;
429 float rl, gl, bl;
430
431 PPM_ASSIGN(p, maxr - minr, 0, 0);
432 rl = (float)PPM_LUMIN(p);
433 PPM_ASSIGN(p, 0, maxg - ming, 0);
434 gl = (float)PPM_LUMIN(p);
435 PPM_ASSIGN(p, 0, 0, maxb - minb);
436 bl = (float)PPM_LUMIN(p);
437
438 if(rl >= gl && rl >= bl)
439 qsort((char *)&(chv[indx]), clrs, sizeof(struct colorhist_item),
440 &redcompare);
441 else if(gl >= bl)
442 qsort((char *)&(chv[indx]), clrs, sizeof(struct colorhist_item),
443 &greencompare);
444 else
445 qsort((char *)&(chv[indx]), clrs, sizeof(struct colorhist_item),
446 &bluecompare);
447 #endif
448
449 /*
450 * Now find the median based on the counts, so that about half the
451 * pixels (not colors, pixels) are in each subdivision.
452 */
453 lowersum = chv[indx].value;
454 halfsum = sm / 2;
455 for(i = 1; i < clrs - 1; ++i) {
456 if(lowersum >= halfsum) break;
457 lowersum += chv[indx + i].value;
458 }
459
460 /*
461 * Split the box, and sort to bring the biggest boxes to the top.
462 */
463 bv[bi].colors = i;
464 bv[bi].sum = lowersum;
465 bv[boxes].ind = indx + i;
466 bv[boxes].colors = clrs - i;
467 bv[boxes].sum = sm - lowersum;
468 ++boxes;
469 qsort((char *)bv, boxes, sizeof(struct box), sumcompare);
470 }
471
472 /*
473 * Ok, we've got enough boxes. Now choose a representative color for
474 * each box. There are a number of possible ways to make this choice.
475 * One would be to choose the center of the box; this ignores any structure
476 * within the boxes. Another method would be to average all the colors in
477 * the box - this is the method specified in Heckbert's paper. A third
478 * method is to average all the pixels in the box. You can switch which
479 * method is used by switching the commenting on the REP_ defines at
480 * the beginning of this source file.
481 */
482 for(bi = 0; bi < boxes; ++bi) {
483 #ifdef REP_CENTER_BOX
484 int indx = bv[bi].ind;
485 int clrs = bv[bi].colors;
486 int minr, maxr, ming, maxg, minb, maxb, v;
487
488 minr = maxr = PPM_GETR(chv[indx].color);
489 ming = maxg = PPM_GETG(chv[indx].color);
490 minb = maxb = PPM_GETB(chv[indx].color);
491 for(i = 1; i < clrs; ++i) {
492 v = PPM_GETR(chv[indx + i].color);
493 minr = min(minr, v);
494 maxr = max(maxr, v);
495 v = PPM_GETG(chv[indx + i].color);
496 ming = min(ming, v);
497 maxg = max(maxg, v);
498 v = PPM_GETB(chv[indx + i].color);
499 minb = min(minb, v);
500 maxb = max(maxb, v);
501 }
502 PPM_ASSIGN(colormap[bi].color, (minr + maxr) / 2, (ming + maxg) / 2,
503 (minb + maxb) / 2);
504 #endif
505
506 #ifdef REP_AVERAGE_COLORS
507 int indx = bv[bi].ind;
508 int clrs = bv[bi].colors;
509 long r = 0, g = 0, b = 0;
510
511 for(i = 0; i < clrs; ++i) {
512 r += PPM_GETR(chv[indx + i].color);
513 g += PPM_GETG(chv[indx + i].color);
514 b += PPM_GETB(chv[indx + i].color);
515 }
516 r = r / clrs;
517 g = g / clrs;
518 b = b / clrs;
519 PPM_ASSIGN(colormap[bi].color, r, g, b);
520 #endif
521
522 #ifdef REP_AVERAGE_PIXELS
523 int indx = bv[bi].ind;
524 int clrs = bv[bi].colors;
525 long r = 0, g = 0, b = 0, sum = 0;
526
527 for(i = 0; i < clrs; ++i) {
528 r += PPM_GETR(chv[indx + i].color) * chv[indx + i].value;
529 g += PPM_GETG(chv[indx + i].color) * chv[indx + i].value;
530 b += PPM_GETB(chv[indx + i].color) * chv[indx + i].value;
531 sum += chv[indx + i].value;
532 }
533 r = r / sum;
534 if(r > (long)maxval) r = maxval; /* avoid math errors */
535 g = g / sum;
536 if(g > (long)maxval) g = maxval;
537 b = b / sum;
538 if(b > (long)maxval) b = maxval;
539 PPM_ASSIGN(colormap[bi].color, r, g, b);
540 #endif
541 }
542
543 /*
544 * All done.
545 */
546 free(bv);
547 return colormap;
548 }
549
550 /* GIF compression routines */
551
552 #define BITS 12
553 #define HSIZE 5003 /* 80% occupancy */
554 #define TRUE 1
555 #define FALSE 0
556
557 typedef unsigned char char_type;
558 typedef int (*ifunptr)(int, int);
559
560 static int g_init_bits;
561 static FILE *g_outfile;
562 static int Width, Height;
563 static int curx, cury;
564 static long CountDown;
565 static int Pass = 0;
566 static int Interlace;
567
568 #include <ctype.h>
569
570 #define ARGVAL() (*++(*argv) || (--argc && *++argv))
571
572 static int n_bits; /* number of bits/code */
573 static int maxbits = BITS; /* user settable max # bits/code */
574 static code_int maxcode; /* maximum code, given n_bits */
575 static code_int maxmaxcode = (code_int)1 << BITS;
576 /* should NEVER generate this code */
577
578 #define MAXCODE(n_bits) (((code_int)1 << (n_bits)) - 1)
579
580 static count_int htab[HSIZE];
581 static unsigned short codetab[HSIZE];
582 #define HashTabOf(i) htab[i]
583 #define CodeTabOf(i) codetab[i]
584
585 static code_int hsize = HSIZE; /* for dynamic table sizing */
586
587 /*
588 * To save much memory, we overlay the table used by compress() with those
589 * used by decompress(). The tab_prefix table is the same size and type
590 * as the codetab. The tab_suffix table needs 2**BITS characters. We
591 * get this from the beginning of htab. The output stack uses the rest
592 * of htab, and contains characters. There is plenty of room for any
593 * possible stack (stack used to be 8000 characters).
594 */
595
596 #define tab_prefixof(i) CodeTabOf(i)
597 #define tab_suffixof(i) ((char_type *)(htab))[i]
598 #define de_stack ((char_type *)&tab_suffixof((code_int)1 << BITS))
599
600 static code_int free_ent = 0; /* first unused entry */
601
602 /*
603 * block compression parameters -- after all codes are used up,
604 * and compression rate changes, start over.
605 */
606 static int clear_flg = 0;
607
608 static long int in_count = 1; /* length of input */
609 static long int out_count = 0; /* # of codes output (for debugging) */
610 static int ClearCode;
611 static int EOFCode;
612
613 /*
614 * Number of characters so far in this 'packet'
615 */
616 static int a_count;
617
618 /*
619 * Set up the 'byte output' routine
620 */
char_init()621 static void char_init() { a_count = 0; }
622
623 /*
624 * Define the storage for the packet accumulator
625 */
626 static char accum[256];
627
628 /*
629 * Flush the packet to disk, and reset the accumulator
630 */
flush_char()631 static void flush_char()
632 {
633 if(a_count > 0) {
634 fputc(a_count, g_outfile);
635 fwrite(accum, 1, a_count, g_outfile);
636 a_count = 0;
637 }
638 }
639
640 /*
641 * Add a character to the end of the current packet, and if it is 254
642 * characters, flush the packet to disk.
643 */
char_out(int c)644 static void char_out(int c)
645 {
646 accum[a_count++] = c;
647 if(a_count >= 254) flush_char();
648 }
649
650 /*
651 * Bump the 'curx' and 'cury' to point to the next pixel
652 */
653
BumpPixel()654 static void BumpPixel()
655 {
656 /*
657 * Bump the current X position
658 */
659 ++curx;
660
661 /*
662 * If we are at the end of a scan line, set curx back to the beginning
663 * If we are interlaced, bump the cury to the appropriate spot,
664 * otherwise, just increment it.
665 */
666 if(curx == Width) {
667 curx = 0;
668
669 if(!Interlace)
670 ++cury;
671 else {
672 switch(Pass) {
673 case 0:
674 cury += 8;
675 if(cury >= Height) {
676 ++Pass;
677 cury = 4;
678 }
679 break;
680
681 case 1:
682 cury += 8;
683 if(cury >= Height) {
684 ++Pass;
685 cury = 2;
686 }
687 break;
688
689 case 2:
690 cury += 4;
691 if(cury >= Height) {
692 ++Pass;
693 cury = 1;
694 }
695 break;
696
697 case 3: cury += 2; break;
698 }
699 }
700 }
701 }
702
703 /*
704 * Return the next pixel from the image
705 */
GIFNextPixel(ifunptr getpixel)706 static int GIFNextPixel(ifunptr getpixel)
707 {
708 int r;
709
710 if(CountDown == 0) return EOF;
711
712 --CountDown;
713
714 r = (*getpixel)(curx, cury);
715
716 BumpPixel();
717
718 return r;
719 }
720
721 /*
722 * Output the given code.
723 * Inputs:
724 * code: A n_bits-bit integer. If == -1, then EOF. This assumes
725 * that n_bits =< (long)wordsize - 1.
726 * Outputs:
727 * Outputs code to the file.
728 * Assumptions:
729 * Chars are 8 bits long.
730 * Algorithm:
731 * Maintain a BITS character long buffer (so that 8 codes will
732 * fit in it exactly). Use the VAX insv instruction to insert each
733 * code in turn. When the buffer fills up empty it and start over.
734 */
735
736 static unsigned long cur_accum = 0;
737 static int cur_bits = 0;
738
739 static unsigned long masks[] = {0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F,
740 0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF,
741 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF};
742
output(code_int code)743 static void output(code_int code)
744 {
745 cur_accum &= masks[cur_bits];
746
747 if(cur_bits > 0)
748 cur_accum |= ((long)code << cur_bits);
749 else
750 cur_accum = code;
751
752 cur_bits += n_bits;
753
754 while(cur_bits >= 8) {
755 char_out((unsigned int)(cur_accum & 0xff));
756 cur_accum >>= 8;
757 cur_bits -= 8;
758 }
759
760 /*
761 * If the next entry is going to be too big for the code size,
762 * then increase it, if possible.
763 */
764 if(free_ent > maxcode || clear_flg) {
765 if(clear_flg) {
766 maxcode = MAXCODE(n_bits = g_init_bits);
767 clear_flg = 0;
768 }
769 else {
770 ++n_bits;
771 if(n_bits == maxbits)
772 maxcode = maxmaxcode;
773 else
774 maxcode = MAXCODE(n_bits);
775 }
776 }
777
778 if(code == EOFCode) {
779 /*
780 * At EOF, write the rest of the buffer.
781 */
782 while(cur_bits > 0) {
783 char_out((unsigned int)(cur_accum & 0xff));
784 cur_accum >>= 8;
785 cur_bits -= 8;
786 }
787
788 flush_char();
789
790 fflush(g_outfile);
791
792 if(ferror(g_outfile)) Msg::Error("GIF: Error writing output file");
793 }
794 }
795
796 /*
797 * compress
798 *
799 * Algorithm: use open addressing double hashing (no chaining) on the
800 * prefix code / next character combination. We do a variant of Knuth's
801 * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
802 * secondary probe. Here, the modular division first probe is gives way
803 * to a faster exclusive-or manipulation. Also do block compression with
804 * an adaptive reset, whereby the code table is cleared when the compression
805 * ratio decreases, but after the table fills. The variable-length output
806 * codes are re-sized at this point, and a special CLEAR code is generated
807 * for the decompressor. Late addition: construct the table according to
808 * file size for noticeable speed improvement on small files. Please direct
809 * questions about this implementation to ames!jaw.
810 */
811
cl_hash(count_int hsize)812 static void cl_hash(count_int hsize)
813 { /* reset code table */
814 count_int *htab_p = htab + hsize;
815
816 long i;
817 long m1 = -1;
818
819 i = hsize - 16;
820 do { /* might use Sys V memset(3) here */
821 *(htab_p - 16) = m1;
822 *(htab_p - 15) = m1;
823 *(htab_p - 14) = m1;
824 *(htab_p - 13) = m1;
825 *(htab_p - 12) = m1;
826 *(htab_p - 11) = m1;
827 *(htab_p - 10) = m1;
828 *(htab_p - 9) = m1;
829 *(htab_p - 8) = m1;
830 *(htab_p - 7) = m1;
831 *(htab_p - 6) = m1;
832 *(htab_p - 5) = m1;
833 *(htab_p - 4) = m1;
834 *(htab_p - 3) = m1;
835 *(htab_p - 2) = m1;
836 *(htab_p - 1) = m1;
837 htab_p -= 16;
838 } while((i -= 16) >= 0);
839
840 for(i += 16; i > 0; --i) *--htab_p = m1;
841 }
842
843 /*
844 * Clear out the hash table
845 */
cl_block()846 static void cl_block()
847 { /* table clear for block compress */
848
849 cl_hash((count_int)hsize);
850 free_ent = ClearCode + 2;
851 clear_flg = 1;
852
853 output((code_int)ClearCode);
854 }
855
compress(int init_bits,FILE * outfile,ifunptr ReadValue)856 static void compress(int init_bits, FILE *outfile, ifunptr ReadValue)
857 {
858 long fcode;
859 code_int i /* = 0 */;
860 int c;
861 code_int ent;
862 code_int disp;
863 code_int hsize_reg;
864 int hshift;
865
866 /*
867 * Set up the globals: g_init_bits - initial number of bits
868 * g_outfile - pointer to output file
869 */
870 g_init_bits = init_bits;
871 g_outfile = outfile;
872
873 /*
874 * Set up the necessary values
875 */
876 out_count = 0;
877 clear_flg = 0;
878 in_count = 1;
879 maxcode = MAXCODE(n_bits = g_init_bits);
880
881 ClearCode = (1 << (init_bits - 1));
882 EOFCode = ClearCode + 1;
883 free_ent = ClearCode + 2;
884
885 char_init();
886
887 ent = GIFNextPixel(ReadValue);
888
889 hshift = 0;
890 for(fcode = (long)hsize; fcode < 65536L; fcode *= 2L) ++hshift;
891 hshift = 8 - hshift; /* set hash code range bound */
892
893 hsize_reg = hsize;
894 cl_hash((count_int)hsize_reg); /* clear hash table */
895
896 output((code_int)ClearCode);
897
898 while((c = GIFNextPixel(ReadValue)) != EOF) {
899 ++in_count;
900
901 fcode = (long)(((long)c << maxbits) + ent);
902 i = (((code_int)c << hshift) ^ ent); /* xor hashing */
903
904 if(HashTabOf(i) == fcode) {
905 ent = CodeTabOf(i);
906 continue;
907 }
908 else if((long)HashTabOf(i) < 0) /* empty slot */
909 goto nomatch;
910 disp = hsize_reg - i; /* secondary hash (after G. Knott) */
911 if(i == 0) disp = 1;
912 probe:
913 if((i -= disp) < 0) i += hsize_reg;
914
915 if(HashTabOf(i) == fcode) {
916 ent = CodeTabOf(i);
917 continue;
918 }
919 if((long)HashTabOf(i) > 0) goto probe;
920 nomatch:
921 output((code_int)ent);
922 ++out_count;
923 ent = c;
924 if(free_ent < maxmaxcode) {
925 CodeTabOf(i) = free_ent++; /* code -> hashtable */
926 HashTabOf(i) = fcode;
927 }
928 else
929 cl_block();
930 }
931 /*
932 * Put out the final code.
933 */
934 output((code_int)ent);
935 ++out_count;
936 output((code_int)EOFCode);
937 }
938
939 /*
940 * Write out a word to the GIF file
941 */
Putword(int w,FILE * fp)942 static void Putword(int w, FILE *fp)
943 {
944 fputc(w & 0xff, fp);
945 fputc((w / 256) & 0xff, fp);
946 }
947
GIFEncode(FILE * fp,int GWidth,int GHeight,int GInterlace,int Background,int Transparent,int BitsPerPixel,int Red[],int Green[],int Blue[],ifunptr GetPixel)948 static void GIFEncode(FILE *fp, int GWidth, int GHeight, int GInterlace,
949 int Background, int Transparent, int BitsPerPixel,
950 int Red[], int Green[], int Blue[], ifunptr GetPixel)
951 {
952 int B;
953 int RWidth, RHeight;
954 int LeftOfs, TopOfs;
955 int Resolution;
956 int ColorMapSize;
957 int InitCodeSize;
958 int i;
959
960 /* reset stuff for output */
961 cur_accum = 0;
962 cur_bits = 0;
963 free_ent = 0;
964
965 Interlace = GInterlace;
966
967 ColorMapSize = 1 << BitsPerPixel;
968
969 RWidth = Width = GWidth;
970 RHeight = Height = GHeight;
971 LeftOfs = TopOfs = 0;
972
973 Resolution = BitsPerPixel;
974
975 /*
976 * Calculate number of bits we are expecting
977 */
978 CountDown = (long)Width * (long)Height;
979
980 /*
981 * Indicate which pass we are on (if interlace)
982 */
983 Pass = 0;
984
985 /*
986 * The initial code size
987 */
988 if(BitsPerPixel <= 1)
989 InitCodeSize = 2;
990 else
991 InitCodeSize = BitsPerPixel;
992
993 /*
994 * Set up the current x and y position
995 */
996 curx = cury = 0;
997
998 /*
999 * Write the Magic header
1000 */
1001 fwrite(Transparent < 0 ? "GIF87a" : "GIF89a", 1, 6, fp);
1002
1003 /*
1004 * Write out the screen width and height
1005 */
1006 Putword(RWidth, fp);
1007 Putword(RHeight, fp);
1008
1009 /*
1010 * Indicate that there is a global colour map
1011 */
1012 B = 0x80; /* Yes, there is a color map */
1013
1014 /*
1015 * OR in the resolution
1016 */
1017 B |= (Resolution - 1) << 5;
1018
1019 /*
1020 * OR in the Bits per Pixel
1021 */
1022 B |= (BitsPerPixel - 1);
1023
1024 /*
1025 * Write it out
1026 */
1027 fputc(B, fp);
1028
1029 /*
1030 * Write out the Background colour
1031 */
1032 fputc(Background, fp);
1033
1034 /*
1035 * Byte of 0's (future expansion)
1036 */
1037 fputc(0, fp);
1038
1039 /*
1040 * Write out the Global Colour Map
1041 */
1042 for(i = 0; i < ColorMapSize; ++i) {
1043 fputc(Red[i], fp);
1044 fputc(Green[i], fp);
1045 fputc(Blue[i], fp);
1046 }
1047
1048 /*
1049 * Write out extension for transparent colour index, if necessary.
1050 */
1051 if(Transparent >= 0) {
1052 fputc('!', fp);
1053 fputc(0xf9, fp);
1054 fputc(4, fp);
1055 fputc(1, fp);
1056 fputc(0, fp);
1057 fputc(0, fp);
1058 fputc(Transparent, fp);
1059 fputc(0, fp);
1060 }
1061
1062 /*
1063 * Write an Image separator
1064 */
1065 fputc(',', fp);
1066
1067 /*
1068 * Write the Image header
1069 */
1070
1071 Putword(LeftOfs, fp);
1072 Putword(TopOfs, fp);
1073 Putword(Width, fp);
1074 Putword(Height, fp);
1075
1076 /*
1077 * Write out whether or not the image is interlaced
1078 */
1079 if(Interlace)
1080 fputc(0x40, fp);
1081 else
1082 fputc(0x00, fp);
1083
1084 /*
1085 * Write out the initial code size
1086 */
1087 fputc(InitCodeSize, fp);
1088
1089 /*
1090 * Go and actually compress the data
1091 */
1092 compress(InitCodeSize + 1, fp, GetPixel);
1093
1094 /*
1095 * Write out a Zero-length packet (to end the series)
1096 */
1097 fputc(0, fp);
1098
1099 /*
1100 * Write the GIF file terminator
1101 */
1102 fputc(';', fp);
1103 }
1104
1105 /* gl2gif public routine */
1106
1107 #define FS_SCALE 1024
1108 #define MAXCOL2 32767
1109
create_gif(FILE * outfile,PixelBuffer * buffer,int dither,int sort,int interlace,int transparency)1110 void create_gif(FILE *outfile, PixelBuffer *buffer, int dither, int sort,
1111 int interlace, int transparency)
1112 {
1113 int i, j, k, transparent, rows, cols;
1114 pixel transcolor;
1115 colorhist_vector chv, colormap;
1116 int BitsPerPixel, usehash;
1117 pixval maxval = MAXCOL2, newmaxval;
1118 colorhash_table cht;
1119 pixel *pP;
1120 int col, row, limitcol, ind;
1121 int newcolors = 256;
1122 long *thisrerr = nullptr, *nextrerr = nullptr, *thisgerr = nullptr, *nextgerr = nullptr;
1123 long *thisberr = nullptr, *nextberr = nullptr, *temperr = nullptr;
1124 long sr = 0, sg = 0, sb = 0, err = 0;
1125 int fs_direction = 0;
1126
1127 int width = buffer->getWidth();
1128 int height = buffer->getHeight();
1129 int numcomp = buffer->getNumComp();
1130
1131 if(numcomp != 3) {
1132 Msg::Error("GIF only implemented for GL_RGB");
1133 return;
1134 }
1135
1136 static_pixels = (pixel **)Malloc(height * sizeof(pixel *));
1137 for(i = 0; i < height; i++)
1138 static_pixels[i] = (pixel *)Malloc(3 * width * sizeof(pixel));
1139
1140 unsigned char *pixels = (unsigned char *)buffer->getPixels();
1141 for(i = 0; i < height; i++)
1142 for(j = 0; j < width; j++)
1143 PPM_ASSIGN(
1144 static_pixels[height - 1 - i][j], pixels[i * width * 3 + j * 3],
1145 pixels[i * width * 3 + j * 3 + 1], pixels[i * width * 3 + j * 3 + 2]);
1146
1147 /* Try to compute color histogram */
1148
1149 chv = ppm_computecolorhist(static_pixels, width, height, MAX_GIFCOLORS,
1150 &static_nbcolors);
1151
1152 /* Fuck, there are more than 256 colors in the picture: we need to quantize */
1153
1154 if(chv == (colorhist_vector)nullptr) {
1155 Msg::Debug("GIF: too many colors in image");
1156
1157 rows = height;
1158 cols = width;
1159
1160 while(1) {
1161 Msg::Debug("GIF: making histogram...");
1162 chv = ppm_computecolorhist(static_pixels, width, height, MAXCOL2,
1163 &static_nbcolors);
1164 if(chv != (colorhist_vector)nullptr) break;
1165 Msg::Debug("GIF: still too many colors!");
1166 newmaxval = maxval / 2;
1167 Msg::Debug("GIF: scaling colors from maxval=%d to maxval=%d to improve "
1168 "clustering...",
1169 maxval, newmaxval);
1170 for(row = 0; row < rows; ++row)
1171 for(col = 0, pP = static_pixels[row]; col < cols; ++col, ++pP)
1172 PPM_DEPTH(*pP, *pP, maxval, newmaxval);
1173 maxval = newmaxval;
1174 }
1175 Msg::Debug("GIF: %d colors found", static_nbcolors);
1176 Msg::Debug("GIF: choosing %d colors...", newcolors);
1177 colormap = mediancut(chv, static_nbcolors, rows * cols, maxval, newcolors);
1178
1179 cht = ppm_alloccolorhash();
1180
1181 ppm_freecolorhist(chv);
1182
1183 /* map the colors in the image to their closest match in the new colormap */
1184 Msg::Debug("GIF: mapping image to new colors...");
1185 usehash = 1;
1186
1187 if(dither) {
1188 Msg::Debug("GIF: Floyd-Steinberg dithering is selected...");
1189 /* Initialize Floyd-Steinberg error vectors. */
1190 thisrerr = (long *)Malloc((cols + 2) * sizeof(long));
1191 nextrerr = (long *)Malloc((cols + 2) * sizeof(long));
1192 thisgerr = (long *)Malloc((cols + 2) * sizeof(long));
1193 nextgerr = (long *)Malloc((cols + 2) * sizeof(long));
1194 thisberr = (long *)Malloc((cols + 2) * sizeof(long));
1195 nextberr = (long *)Malloc((cols + 2) * sizeof(long));
1196 /* srand( (int) ( time( 0 ) ^ getpid( ) ) ); */
1197 for(col = 0; col < cols + 2; ++col) {
1198 thisrerr[col] = rand() % (FS_SCALE * 2) - FS_SCALE;
1199 thisgerr[col] = rand() % (FS_SCALE * 2) - FS_SCALE;
1200 thisberr[col] = rand() % (FS_SCALE * 2) - FS_SCALE;
1201 /* (random errors in [-1 .. 1]) */
1202 }
1203 fs_direction = 1;
1204 }
1205 for(row = 0; row < rows; ++row) {
1206 if(dither)
1207 for(col = 0; col < cols + 2; ++col)
1208 nextrerr[col] = nextgerr[col] = nextberr[col] = 0;
1209
1210 if((!dither) || fs_direction) {
1211 col = 0;
1212 limitcol = cols;
1213 pP = static_pixels[row];
1214 }
1215 else {
1216 col = cols - 1;
1217 limitcol = -1;
1218 pP = &(static_pixels[row][col]);
1219 }
1220
1221 do {
1222 if(dither) {
1223 /* Use Floyd-Steinberg errors to adjust actual color. */
1224 sr = PPM_GETR(*pP) + thisrerr[col + 1] / FS_SCALE;
1225 sg = PPM_GETG(*pP) + thisgerr[col + 1] / FS_SCALE;
1226 sb = PPM_GETB(*pP) + thisberr[col + 1] / FS_SCALE;
1227 if(sr < 0)
1228 sr = 0;
1229 else if(sr > (long)maxval)
1230 sr = maxval;
1231 if(sg < 0)
1232 sg = 0;
1233 else if(sg > (long)maxval)
1234 sg = maxval;
1235 if(sb < 0)
1236 sb = 0;
1237 else if(sb > (long)maxval)
1238 sb = maxval;
1239 PPM_ASSIGN(*pP, sr, sg, sb);
1240 }
1241
1242 /* Check hash table to see if we have already matched this color. */
1243 ind = ppm_lookupcolor(cht, pP);
1244 if(ind == -1) { /* No; search colormap for closest match. */
1245 int i, r1, g1, b1, r2, g2, b2;
1246 long dist, newdist;
1247 r1 = PPM_GETR(*pP);
1248 g1 = PPM_GETG(*pP);
1249 b1 = PPM_GETB(*pP);
1250 dist = 2000000000;
1251 for(i = 0; i < newcolors; ++i) {
1252 r2 = PPM_GETR(colormap[i].color);
1253 g2 = PPM_GETG(colormap[i].color);
1254 b2 = PPM_GETB(colormap[i].color);
1255 newdist = (r1 - r2) * (r1 - r2) + (g1 - g2) * (g1 - g2) +
1256 (b1 - b2) * (b1 - b2);
1257 if(newdist < dist) {
1258 ind = i;
1259 dist = newdist;
1260 }
1261 }
1262 if(usehash) {
1263 if(ppm_addtocolorhash(cht, pP, ind) < 0) {
1264 Msg::Warning("GIF: Out of memory adding to hash table");
1265 usehash = 0;
1266 }
1267 }
1268 }
1269
1270 if(dither) {
1271 /* Propagate Floyd-Steinberg error terms. */
1272 if(fs_direction) {
1273 err = (sr - (long)PPM_GETR(colormap[ind].color)) * FS_SCALE;
1274 thisrerr[col + 2] += (err * 7) / 16;
1275 nextrerr[col] += (err * 3) / 16;
1276 nextrerr[col + 1] += (err * 5) / 16;
1277 nextrerr[col + 2] += (err) / 16;
1278 err = (sg - (long)PPM_GETG(colormap[ind].color)) * FS_SCALE;
1279 thisgerr[col + 2] += (err * 7) / 16;
1280 nextgerr[col] += (err * 3) / 16;
1281 nextgerr[col + 1] += (err * 5) / 16;
1282 nextgerr[col + 2] += (err) / 16;
1283 err = (sb - (long)PPM_GETB(colormap[ind].color)) * FS_SCALE;
1284 thisberr[col + 2] += (err * 7) / 16;
1285 nextberr[col] += (err * 3) / 16;
1286 nextberr[col + 1] += (err * 5) / 16;
1287 nextberr[col + 2] += (err) / 16;
1288 }
1289 else {
1290 err = (sr - (long)PPM_GETR(colormap[ind].color)) * FS_SCALE;
1291 thisrerr[col] += (err * 7) / 16;
1292 nextrerr[col + 2] += (err * 3) / 16;
1293 nextrerr[col + 1] += (err * 5) / 16;
1294 nextrerr[col] += (err) / 16;
1295 err = (sg - (long)PPM_GETG(colormap[ind].color)) * FS_SCALE;
1296 thisgerr[col] += (err * 7) / 16;
1297 nextgerr[col + 2] += (err * 3) / 16;
1298 nextgerr[col + 1] += (err * 5) / 16;
1299 nextgerr[col] += (err) / 16;
1300 err = (sb - (long)PPM_GETB(colormap[ind].color)) * FS_SCALE;
1301 thisberr[col] += (err * 7) / 16;
1302 nextberr[col + 2] += (err * 3) / 16;
1303 nextberr[col + 1] += (err * 5) / 16;
1304 nextberr[col] += (err) / 16;
1305 }
1306 }
1307
1308 *pP = colormap[ind].color;
1309
1310 if((!dither) || fs_direction) {
1311 ++col;
1312 ++pP;
1313 }
1314 else {
1315 --col;
1316 --pP;
1317 }
1318 } while(col != limitcol);
1319
1320 if(dither) {
1321 temperr = thisrerr;
1322 thisrerr = nextrerr;
1323 nextrerr = temperr;
1324 temperr = thisgerr;
1325 thisgerr = nextgerr;
1326 nextgerr = temperr;
1327 temperr = thisberr;
1328 thisberr = nextberr;
1329 nextberr = temperr;
1330 fs_direction = !fs_direction;
1331 }
1332 }
1333
1334 if(cht) ppm_freecolorhash(cht);
1335 if(dither) {
1336 Free(thisrerr);
1337 Free(nextrerr);
1338 Free(thisgerr);
1339 Free(nextgerr);
1340 Free(thisberr);
1341 Free(nextberr);
1342 }
1343 chv = ppm_computecolorhist(static_pixels, width, height, MAX_GIFCOLORS,
1344 &static_nbcolors);
1345 }
1346
1347 /* We now have a colormap of maximum 256 colors */
1348
1349 for(i = 0; i < static_nbcolors; ++i) {
1350 static_red[i] = PPM_GETR(chv[i].color);
1351 static_green[i] = PPM_GETG(chv[i].color);
1352 static_blue[i] = PPM_GETB(chv[i].color);
1353 }
1354
1355 /* Sort the colormap */
1356 for(i = 0; i < static_nbcolors; i++) static_permi[i] = i;
1357 if(sort) {
1358 Msg::Debug("GIF: sorting colormap");
1359 for(i = 0; i < static_nbcolors; i++)
1360 for(j = i + 1; j < static_nbcolors; j++)
1361 if(((static_red[i] * MAX_GIFCOLORS) + static_green[i]) * MAX_GIFCOLORS +
1362 static_blue[i] >
1363 ((static_red[j] * MAX_GIFCOLORS) + static_green[j]) * MAX_GIFCOLORS +
1364 static_blue[j]) {
1365 k = static_permi[i];
1366 static_permi[i] = static_permi[j];
1367 static_permi[j] = k;
1368 k = static_red[i];
1369 static_red[i] = static_red[j];
1370 static_red[j] = k;
1371 k = static_green[i];
1372 static_green[i] = static_green[j];
1373 static_green[j] = k;
1374 k = static_blue[i];
1375 static_blue[i] = static_blue[j];
1376 static_blue[j] = k;
1377 }
1378 }
1379 for(i = 0; i < static_nbcolors; i++) static_perm[static_permi[i]] = i;
1380
1381 BitsPerPixel = colorstobpp(static_nbcolors);
1382
1383 /* And make a hash table for fast lookup. */
1384 static_cht = ppm_colorhisttocolorhash(chv, static_nbcolors);
1385 ppm_freecolorhist(chv);
1386
1387 /* figure out the transparent colour index, assuming the background is white
1388 */
1389 if(transparency) {
1390 PPM_ASSIGN(transcolor, 255, 255, 255);
1391 transparent = ppm_lookupcolor(static_cht, &transcolor);
1392 if(transparent == -1)
1393 transparent = closestcolor(transcolor);
1394 else
1395 transparent = static_perm[transparent];
1396 }
1397 else
1398 transparent = -1;
1399
1400 /* All set, let's do it. */
1401 GIFEncode(outfile, width, height, interlace, 0, transparent, BitsPerPixel,
1402 static_red, static_green, static_blue, GetPixel);
1403
1404 for(i = 0; i < height; i++) Free(static_pixels[i]);
1405 Free(static_pixels);
1406 }
1407