1 ////////////////////////////////////////////////////////////////////////////////
2 //
3 // File: GIFSave.cpp
4 //
5 // Date: December 1999
6 //
7 // Author: Daniel Switkin
8 //
9 // Copyright 2003 (c) by Daniel Switkin. This file is made publically available
10 // under the BSD license, with the stipulations that this complete header must
11 // remain at the top of the file indefinitely, and credit must be given to the
12 // original author in any about box using this software.
13 //
14 ////////////////////////////////////////////////////////////////////////////////
15
16 // Additional authors: Stephan Aßmus, <superstippi@gmx.de>
17 // Philippe Saint-Pierre, <stpere@gmail.com>
18 // John Scipione, <jscipione@gmail.com>
19
20
21 #include "GIFSave.h"
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <syslog.h>
26
27 #include <new>
28
29 #include "GIFPrivate.h"
30
31
32 const int gs_pass_starts_at[] = {0, 4, 2, 1, 0};
33 const int gs_increment_pass_by[] = {8, 8, 4, 2, 0};
34 const int32 one_sixteenth = (int32)((1.0 / 16.0) * 32768);
35 const int32 three_sixteenth = (int32)((3.0 / 16.0) * 32768);
36 const int32 five_sixteenth = (int32)((5.0 / 16.0) * 32768);
37 const int32 seven_sixteenth = (int32)((7.0 / 16.0) * 32768);
38
39 extern bool debug;
40
41
42 class ColorCache : public HashItem {
43 public:
44 unsigned char index;
45 };
46
47
GIFSave(BBitmap * bitmap,BPositionIO * output,TranslatorSettings * settings)48 GIFSave::GIFSave(BBitmap* bitmap, BPositionIO* output,
49 TranslatorSettings* settings)
50 {
51 fSettings = settings;
52 color_space colorSpace = bitmap->ColorSpace();
53 if (colorSpace != B_RGB32 && colorSpace != B_RGBA32
54 && colorSpace != B_RGB32_BIG && colorSpace != B_RGBA32_BIG) {
55 if (debug)
56 syslog(LOG_ERR, "GIFSave::GIFSave() - Unknown color space\n");
57
58 fatalerror = true;
59 return;
60 }
61
62 fatalerror = false;
63 if (fSettings->SetGetInt32(GIF_SETTING_PALETTE_MODE) == OPTIMAL_PALETTE) {
64 palette = new(std::nothrow) SavePalette(bitmap,
65 fSettings->SetGetInt32(GIF_SETTING_PALETTE_SIZE));
66 } else {
67 palette = new(std::nothrow) SavePalette(
68 fSettings->SetGetInt32(GIF_SETTING_PALETTE_MODE));
69 }
70
71 if (palette == NULL) {
72 fatalerror = true;
73 return;
74 }
75
76 if (!palette->IsValid()) {
77 delete palette;
78 fatalerror = true;
79 return;
80 }
81
82 width = bitmap->Bounds().IntegerWidth() + 1;
83 height = bitmap->Bounds().IntegerHeight() + 1;
84 if (debug) {
85 syslog(LOG_INFO, "GIFSave::GIFSave() - "
86 "Image dimensions are %d by %d\n", width, height);
87 }
88
89 if (fSettings->SetGetBool(GIF_SETTING_USE_DITHERING)) {
90 if (debug)
91 syslog(LOG_INFO, "GIFSave::GIFSave() - Using dithering\n");
92
93 red_error = new(std::nothrow) int32[width + 2];
94 if (red_error == NULL) {
95 delete palette;
96 fatalerror = true;
97 return;
98 }
99 red_error = &red_error[1];
100 // Allow index of -1 too
101
102 green_error = new(std::nothrow) int32[width + 2];
103 if (green_error == NULL) {
104 delete palette;
105 delete[] &red_error[-1];
106 fatalerror = true;
107 return;
108 }
109 green_error = &green_error[1];
110 // Allow index of -1 too
111
112 blue_error = new(std::nothrow) int32[width + 2];
113 if (blue_error == NULL) {
114 delete palette;
115 delete[] &red_error[-1];
116 delete[] &green_error[-1];
117 fatalerror = true;
118 return;
119 }
120 blue_error = &blue_error[1];
121 // Allow index of -1 too
122
123 red_side_error = green_side_error = blue_side_error = 0;
124 for (int32 x = -1; x < width + 1; x++) {
125 red_error[x] = 0;
126 green_error[x] = 0;
127 blue_error[x] = 0;
128 }
129 } else if (debug)
130 syslog(LOG_INFO, "GIFSave::GIFSave() - Not using dithering\n");
131
132 if (debug) {
133 if (fSettings->SetGetBool(GIF_SETTING_INTERLACED))
134 syslog(LOG_INFO, "GIFSave::GIFSave() - Interlaced, ");
135 else
136 syslog(LOG_INFO, "GIFSave::GIFSave() - Not interlaced, ");
137
138 switch (fSettings->SetGetInt32(GIF_SETTING_PALETTE_MODE)) {
139 case WEB_SAFE_PALETTE:
140 syslog(LOG_INFO, "web safe palette\n");
141 break;
142
143 case BEOS_SYSTEM_PALETTE:
144 syslog(LOG_INFO, "BeOS system palette\n");
145 break;
146
147 case GREYSCALE_PALETTE:
148 syslog(LOG_INFO, "greyscale palette\n");
149 break;
150
151 case OPTIMAL_PALETTE:
152 default:
153 syslog(LOG_INFO, "optimal palette\n");
154 }
155 }
156
157 if (fSettings->SetGetBool(GIF_SETTING_USE_TRANSPARENT)) {
158 if (fSettings->SetGetBool(GIF_SETTING_USE_TRANSPARENT_AUTO)) {
159 palette->PrepareForAutoTransparency();
160 if (debug) {
161 syslog(LOG_INFO, "GIFSave::GIFSave() - "
162 "Using transparent index %d\n",
163 palette->TransparentIndex());
164 }
165 } else {
166 palette->SetTransparentColor(
167 (uint8)fSettings->SetGetInt32(GIF_SETTING_TRANSPARENT_RED),
168 (uint8)fSettings->SetGetInt32(GIF_SETTING_TRANSPARENT_GREEN),
169 (uint8)fSettings->SetGetInt32(GIF_SETTING_TRANSPARENT_BLUE));
170 if (debug) {
171 syslog(LOG_INFO, "GIFSave::GIFSave() - "
172 "Found transparent color %d,%d,%d at index %d\n",
173 fSettings->SetGetInt32(GIF_SETTING_TRANSPARENT_RED),
174 fSettings->SetGetInt32(GIF_SETTING_TRANSPARENT_GREEN),
175 fSettings->SetGetInt32(GIF_SETTING_TRANSPARENT_BLUE),
176 palette->TransparentIndex());
177 }
178 }
179 } else {
180 if (debug)
181 syslog(LOG_INFO, "GIFSave::GIFSave() - Not using transparency\n");
182 }
183
184 this->output = output;
185 this->bitmap = bitmap;
186
187 if (WriteGIFHeader() != B_OK) {
188 delete palette;
189 delete[] &red_error[-1];
190 delete[] &green_error[-1];
191 delete[] &blue_error[-1];
192 fatalerror = true;
193 return;
194 }
195
196 if (debug)
197 syslog(LOG_INFO, "GIFSave::GIFSave() - Wrote gif header\n");
198
199 hash = new(std::nothrow) SFHash(1 << 16);
200 if (hash == NULL) {
201 delete palette;
202 delete[] &red_error[-1];
203 delete[] &green_error[-1];
204 delete[] &blue_error[-1];
205 fatalerror = true;
206 return;
207 }
208
209 WriteGIFControlBlock();
210 if (debug)
211 syslog(LOG_INFO, "GIFSave::GIFSave() - Wrote gif control block\n");
212
213 WriteGIFImageHeader();
214 if (debug)
215 syslog(LOG_INFO, "GIFSave::GIFSave() - Wrote gif image header\n");
216
217 WriteGIFImageData();
218 if (debug)
219 syslog(LOG_INFO, "GIFSave::GIFSave() - Wrote gif image data\n");
220
221 if (fSettings->SetGetBool(GIF_SETTING_USE_DITHERING)) {
222 delete[] &red_error[-1];
223 delete[] &green_error[-1];
224 delete[] &blue_error[-1];
225 }
226 delete hash;
227
228 // Terminating character
229 char t = TERMINATOR_INTRODUCER;
230 output->Write(&t, 1);
231 }
232
233
~GIFSave()234 GIFSave::~GIFSave()
235 {
236 delete palette;
237 fSettings->Release();
238 }
239
240
241 status_t
WriteGIFHeader()242 GIFSave::WriteGIFHeader()
243 {
244 // Standard header
245 unsigned char header[]
246 = { 'G', 'I', 'F', '8', '9', 'a', 0, 0, 0, 0, 0, 0, 0 };
247 header[6] = width & 0xff;
248 header[7] = (width & 0xff00) >> 8;
249 header[8] = height & 0xff;
250 header[9] = (height & 0xff00) >> 8;
251 header[10] = 0xf0 | (palette->SizeInBits() - 1);
252 header[11] = palette->BackgroundIndex();
253 if (output->Write(header, 13) < 13)
254 return B_IO_ERROR;
255
256 // global palette
257 int size = (1 << palette->SizeInBits()) * 3;
258 // can't be bigger than this
259 uint8* buffer = new(std::nothrow) uint8[size];
260 if (buffer == NULL)
261 return B_NO_MEMORY;
262
263 palette->GetColors(buffer, size);
264 if (output->Write(buffer, size) < size) {
265 delete[] buffer;
266 return B_IO_ERROR;
267 }
268 delete[] buffer;
269
270 return B_OK;
271 }
272
273
274 status_t
WriteGIFControlBlock()275 GIFSave::WriteGIFControlBlock()
276 {
277 unsigned char b[8] = {
278 EXTENSION_INTRODUCER, GRAPHIC_CONTROL_LABEL, 0x04, 0x00, 0x00, 0x00,
279 0x00, BLOCK_TERMINATOR
280 };
281 if (palette->UseTransparent()) {
282 b[3] = b[3] | 1;
283 b[6] = palette->TransparentIndex();
284 }
285 return output->Write(b, 8) < 8 ? B_IO_ERROR : B_OK;
286 }
287
288
289 status_t
WriteGIFImageHeader()290 GIFSave::WriteGIFImageHeader()
291 {
292 unsigned char header[10];
293 header[0] = DESCRIPTOR_INTRODUCER;
294 header[1] = header[2] = 0;
295 header[3] = header[4] = 0;
296
297 header[5] = width & 0xff;
298 header[6] = (width & 0xff00) >> 8;
299 header[7] = height & 0xff;
300 header[8] = (height & 0xff00) >> 8;
301
302 if (fSettings->SetGetBool(GIF_SETTING_INTERLACED))
303 header[9] = 0x40;
304 else
305 header[9] = BLOCK_TERMINATOR;
306
307 return output->Write(header, 10) < 10 ? B_IO_ERROR : B_OK;
308 }
309
310
311 status_t
WriteGIFImageData()312 GIFSave::WriteGIFImageData()
313 {
314 InitFrame();
315
316 status_t result = B_OK;
317
318 code_value = (short*)malloc(HASHSIZE * 2);
319 if (code_value == NULL)
320 return B_NO_MEMORY;
321
322 prefix_code = (short*)malloc(HASHSIZE * 2);
323 if (prefix_code == NULL) {
324 free(code_value);
325
326 return B_NO_MEMORY;
327 }
328
329 append_char = (unsigned char*)malloc(HASHSIZE);
330 if (append_char == NULL) {
331 free(code_value);
332 free(prefix_code);
333
334 return B_NO_MEMORY;
335 }
336
337 ResetHashtable();
338
339 if (output->Write(&code_size, 1) < 1) {
340 free(code_value);
341 free(prefix_code);
342 free(append_char);
343
344 return B_IO_ERROR;
345 }
346
347 result = OutputCode(clear_code, BITS);
348 if (result != B_OK) {
349 free(code_value);
350 free(prefix_code);
351 free(append_char);
352
353 return B_IO_ERROR;
354 }
355
356 string_code = NextPixel(0);
357 int area = height * width;
358
359 for (int x = 1; x < area; x++) {
360 character = NextPixel(x);
361 int y = 0;
362 if ((y = CheckHashtable(string_code, character)) != -1)
363 string_code = y;
364 else {
365 AddToHashtable(string_code, character);
366 result = OutputCode(string_code, BITS);
367 if (result != B_OK) {
368 free(code_value);
369 free(prefix_code);
370 free(append_char);
371
372 return B_IO_ERROR;
373 }
374
375 if (next_code > max_code) {
376 BITS++;
377 if (BITS > LZ_MAX_BITS) {
378 result = OutputCode(clear_code, LZ_MAX_BITS);
379 if (result != B_OK) {
380 free(code_value);
381 free(prefix_code);
382 free(append_char);
383
384 return B_IO_ERROR;
385 }
386
387 BITS = code_size + 1;
388 ResetHashtable();
389 next_code = clear_code + 1;
390 // this is different
391 }
392 max_code = (1 << BITS) - 1;
393 }
394 string_code = character;
395 next_code++;
396 }
397 }
398
399 result = OutputCode(string_code, BITS);
400 if (result != B_OK) {
401 free(code_value);
402 free(prefix_code);
403 free(append_char);
404
405 return B_IO_ERROR;
406 }
407
408 result = OutputCode(end_code, BITS);
409 if (result != B_OK) {
410 free(code_value);
411 free(prefix_code);
412 free(append_char);
413
414 return B_IO_ERROR;
415 }
416
417 result = OutputCode(0, BITS, true);
418 if (result != B_OK) {
419 free(code_value);
420 free(prefix_code);
421 free(append_char);
422
423 return B_IO_ERROR;
424 }
425
426 char t = BLOCK_TERMINATOR;
427 if (output->Write(&t, 1) < 1) {
428 free(code_value);
429 free(prefix_code);
430 free(append_char);
431
432 return B_IO_ERROR;
433 }
434
435 free(code_value);
436 free(prefix_code);
437 free(append_char);
438
439 return result;
440 }
441
442
443 status_t
OutputCode(short code,int BITS,bool flush)444 GIFSave::OutputCode(short code, int BITS, bool flush)
445 {
446 if (!flush) {
447 bit_buffer |= (unsigned int)code << bit_count;
448 bit_count += BITS;
449 while (bit_count >= 8) {
450 byte_buffer[byte_count + 1] = (unsigned char)(bit_buffer & 0xff);
451 byte_count++;
452 bit_buffer >>= 8;
453 bit_count -= 8;
454 }
455 if (byte_count >= 255) {
456 byte_buffer[0] = 255;
457 if (output->Write(byte_buffer, 256) < 256)
458 return B_IO_ERROR;
459
460 if (byte_count == 256) {
461 byte_buffer[1] = byte_buffer[256];
462 byte_count = 1;
463 } else
464 byte_count = 0;
465 }
466 } else {
467 bit_buffer |= (unsigned int) code << bit_count;
468 bit_count += BITS;
469 while (bit_count > 0) {
470 byte_buffer[byte_count + 1] = (unsigned char)(bit_buffer & 0xff);
471 byte_count++;
472 bit_buffer >>= 8;
473 bit_count -= 8;
474 }
475 if (byte_count > 0) {
476 byte_buffer[0] = (unsigned char)byte_count;
477 if (output->Write(byte_buffer, byte_count + 1) < byte_count + 1)
478 return B_IO_ERROR;
479 }
480 }
481
482 return B_OK;
483 }
484
485
486 void
ResetHashtable()487 GIFSave::ResetHashtable()
488 {
489 for (int q = 0; q < HASHSIZE; q++) {
490 code_value[q] = -1;
491 prefix_code[q] = 0;
492 append_char[q] = 0;
493 }
494 }
495
496
497 int
CheckHashtable(int s,unsigned char c)498 GIFSave::CheckHashtable(int s, unsigned char c)
499 {
500 if (s == -1)
501 return c;
502
503 int hashindex = HASH(s, c);
504 int nextindex;
505 while ((nextindex = code_value[hashindex]) != -1) {
506 if (prefix_code[nextindex] == s && append_char[nextindex] == c)
507 return nextindex;
508
509 hashindex = (hashindex + HASHSTEP) % HASHSIZE;
510 }
511
512 return -1;
513 }
514
515
516 void
AddToHashtable(int s,unsigned char c)517 GIFSave::AddToHashtable(int s, unsigned char c)
518 {
519 int hashindex = HASH(s, c);
520 while (code_value[hashindex] != -1)
521 hashindex = (hashindex + HASHSTEP) % HASHSIZE;
522
523 code_value[hashindex] = next_code;
524 prefix_code[next_code] = s;
525 append_char[next_code] = c;
526 }
527
528
529 unsigned char
NextPixel(int pixel)530 GIFSave::NextPixel(int pixel)
531 {
532 int bpr = bitmap->BytesPerRow();
533 color_space colorSpace = bitmap->ColorSpace();
534 bool useAlphaForTransparency = colorSpace == B_RGBA32_BIG
535 || (fSettings->SetGetBool(GIF_SETTING_USE_TRANSPARENT_AUTO)
536 && colorSpace == B_RGBA32);
537 unsigned char r;
538 unsigned char g;
539 unsigned char b;
540 unsigned char a;
541
542 if (colorSpace == B_RGB32 || colorSpace == B_RGBA32) {
543 b = gifbits[0];
544 g = gifbits[1];
545 r = gifbits[2];
546 a = gifbits[3];
547 } else {
548 a = gifbits[0];
549 r = gifbits[1];
550 g = gifbits[2];
551 b = gifbits[3];
552 }
553 gifbits += 4;
554 pos += 4;
555
556 if (!fSettings->SetGetBool(GIF_SETTING_USE_TRANSPARENT)
557 || fSettings->SetGetBool(GIF_SETTING_USE_TRANSPARENT_AUTO)
558 || r != fSettings->SetGetInt32(GIF_SETTING_TRANSPARENT_RED)
559 || g != fSettings->SetGetInt32(GIF_SETTING_TRANSPARENT_GREEN)
560 || b != fSettings->SetGetInt32(GIF_SETTING_TRANSPARENT_BLUE)) {
561 if (fSettings->SetGetBool(GIF_SETTING_USE_DITHERING)) {
562 if (pixel % width == 0)
563 red_side_error = green_side_error = blue_side_error = 0;
564
565 b = min_c(255, max_c(0, b - blue_side_error));
566 g = min_c(255, max_c(0, g - green_side_error));
567 r = min_c(255, max_c(0, r - red_side_error));
568 }
569 }
570
571 if (fSettings->SetGetBool(GIF_SETTING_INTERLACED)) {
572 if (pos >= bpr) {
573 pos = 0;
574 row += gs_increment_pass_by[pass];
575 while (row >= height) {
576 pass++;
577 row = gs_pass_starts_at[pass];
578 }
579 gifbits = (unsigned char*)bitmap->Bits() + (bpr * row);
580 }
581 }
582 #if 0
583 unsigned int key = (r << 16) + (g << 8) + b;
584 ColorCache* cc = (ColorCache*)hash->GetItem(key);
585 if (cc == NULL) {
586 cc = new ColorCache();
587 cc->key = key;
588 cc->index = palette->IndexForColor(r, g, b);
589 hash->AddItem((HashItem*)cc);
590 }
591
592 if (prefs->usedithering) {
593 int x = pixel % width;
594 // Don't carry error on to next line when interlaced because
595 // that line won't be adjacent, hence error is meaningless
596 if (prefs->interlaced && x == width - 1) {
597 for (int32 y = -1; y < width + 1; y++) {
598 red_error[y] = 0;
599 green_error[y] = 0;
600 blue_error[y] = 0;
601 }
602 }
603
604 int32 red_total_error = palette->pal[cc->index].red - r;
605 int32 green_total_error = palette->pal[cc->index].green - g;
606 int32 blue_total_error = palette->pal[cc->index].blue - b;
607
608 red_side_error = (red_error[x + 1]
609 + (red_total_error * seven_sixteenth)) >> 15;
610 blue_side_error = (blue_error[x + 1]
611 + (blue_total_error * seven_sixteenth)) >> 15;
612 green_side_error = (green_error[x + 1]
613 + (green_total_error * seven_sixteenth)) >> 15;
614
615 red_error[x - 1] += (red_total_error * three_sixteenth);
616 green_error[x - 1] += (green_total_error * three_sixteenth);
617 blue_error[x - 1] += (blue_total_error * three_sixteenth);
618
619 red_error[x] += (red_total_error * five_sixteenth);
620 green_error[x] += (green_total_error * five_sixteenth);
621 blue_error[x] += (blue_total_error * five_sixteenth);
622
623 red_error[x + 1] = (red_total_error * one_sixteenth);
624 green_error[x + 1] = (green_total_error * one_sixteenth);
625 blue_error[x + 1] = (blue_total_error * one_sixteenth);
626 }
627
628 return cc->index;
629 #endif
630
631 int index = palette->IndexForColor(r, g, b, useAlphaForTransparency
632 ? a : 255);
633
634 if (index != palette->TransparentIndex()
635 && fSettings->SetGetBool(GIF_SETTING_USE_DITHERING)) {
636 int x = pixel % width;
637 // don't carry error on to next line when interlaced because
638 // that line won't be adjacent, hence error is meaningless
639 if (fSettings->SetGetBool(GIF_SETTING_INTERLACED) && x == width - 1) {
640 for (int32 y = -1; y < width + 1; y++) {
641 red_error[y] = 0;
642 green_error[y] = 0;
643 blue_error[y] = 0;
644 }
645 }
646
647 int32 red_total_error = palette->pal[index].red - r;
648 int32 green_total_error = palette->pal[index].green - g;
649 int32 blue_total_error = palette->pal[index].blue - b;
650
651 red_side_error = (red_error[x + 1]
652 + (red_total_error * seven_sixteenth)) >> 15;
653 blue_side_error = (blue_error[x + 1]
654 + (blue_total_error * seven_sixteenth)) >> 15;
655 green_side_error = (green_error[x + 1]
656 + (green_total_error * seven_sixteenth)) >> 15;
657
658 red_error[x - 1] += (red_total_error * three_sixteenth);
659 green_error[x - 1] += (green_total_error * three_sixteenth);
660 blue_error[x - 1] += (blue_total_error * three_sixteenth);
661
662 red_error[x] += (red_total_error * five_sixteenth);
663 green_error[x] += (green_total_error * five_sixteenth);
664 blue_error[x] += (blue_total_error * five_sixteenth);
665
666 red_error[x + 1] = (red_total_error * one_sixteenth);
667 green_error[x + 1] = (green_total_error * one_sixteenth);
668 blue_error[x + 1] = (blue_total_error * one_sixteenth);
669 }
670
671 return index;
672 }
673
674
675 void
InitFrame()676 GIFSave::InitFrame()
677 {
678 code_size = palette->SizeInBits();
679 if (code_size == 1)
680 code_size++;
681
682 BITS = code_size + 1;
683 clear_code = 1 << code_size;
684 end_code = clear_code + 1;
685 next_code = clear_code + 2;
686 max_code = (1 << BITS) - 1;
687 string_code = 0;
688 character = 0;
689 table_size = 1 << LZ_MAX_BITS;
690
691 bit_count = 0;
692 bit_buffer = 0;
693 byte_count = 0;
694
695 pass = pos = 0;
696 row = gs_pass_starts_at[0];
697
698 gifbits = (unsigned char*)bitmap->Bits();
699 }
700