1/*
2 * this file is derived from "sixel" original version (2014-3-2)
3 * http://nanno.dip.jp/softlib/man/rlogin/sixel.tar.gz
4 *
5 * Initial developer of this file is kmiya@culti.
6 *
7 * He distributes it under very permissive license which permits
8 * useing, copying, modification, redistribution, and all other
9 * public activities without any restrictions.
10 *
11 * He declares this is compatible with MIT/BSD/GPL.
12 *
13 * Hayaki Saito (saitoha@me.com) modified this and re-licensed
14 * it under the MIT license.
15 *
16 * Araki Ken added high-color encoding mode(sixel_encode_highcolor)
17 * extension.
18 *
19 */
20#include "config.h"
21
22/* STDC_HEADERS */
23#include <stdio.h>
24#include <stdlib.h>
25
26#if HAVE_STRING_H
27# include <string.h>
28#endif /* HAVE_STRING_H */
29#if HAVE_LIMITS_H
30# include <limits.h>
31#endif /* HAVE_LIMITS_H */
32#if HAVE_INTTYPES_H
33# include <inttypes.h>
34#endif /* HAVE_INTTYPES_H */
35
36#include <sixel.h>
37#include "output.h"
38#include "dither.h"
39
40#define DCS_START_7BIT "\033P"
41#define DCS_START_7BIT_SIZE (sizeof(DCS_START_7BIT) - 1)
42#define DCS_START_8BIT "\220"
43#define DCS_START_8BIT_SIZE (sizeof(DCS_START_8BIT) - 1)
44#define DCS_END_7BIT "\033\\"
45#define DCS_END_7BIT_SIZE (sizeof(DCS_END_7BIT) - 1)
46#define DCS_END_8BIT "\234"
47#define DCS_END_8BIT_SIZE (sizeof(DCS_END_8BIT) - 1)
48#define DCS_7BIT(x) DCS_START_7BIT x DCS_END_7BIT
49#define DCS_8BIT(x) DCS_START_8BIT x DCS_END_8BIT
50#define SCREEN_PACKET_SIZE 256
51
52enum {
53 PALETTE_HIT = 1,
54 PALETTE_CHANGE = 2
55};
56
57/* implementation */
58
59/* GNU Screen penetration */
60static void
61sixel_penetrate(
62 sixel_output_t /* in */ *output, /* output context */
63 int /* in */ nwrite, /* output size */
64 char const /* in */ *dcs_start, /* DCS introducer */
65 char const /* in */ *dcs_end, /* DCS terminator */
66 int const /* in */ dcs_start_size, /* size of DCS introducer */
67 int const /* in */ dcs_end_size) /* size of DCS terminator */
68{
69 int pos;
70 int const splitsize = SCREEN_PACKET_SIZE
71 - dcs_start_size - dcs_end_size;
72
73 for (pos = 0; pos < nwrite; pos += splitsize) {
74 output->fn_write((char *)dcs_start, dcs_start_size, output->priv);
75 output->fn_write(((char *)output->buffer) + pos,
76 nwrite - pos < splitsize ? nwrite - pos: splitsize,
77 output->priv);
78 output->fn_write((char *)dcs_end, dcs_end_size, output->priv);
79 }
80}
81
82
83static void
84sixel_advance(sixel_output_t *output, int nwrite)
85{
86 if ((output->pos += nwrite) >= SIXEL_OUTPUT_PACKET_SIZE) {
87 if (output->penetrate_multiplexer) {
88 sixel_penetrate(output,
89 SIXEL_OUTPUT_PACKET_SIZE,
90 DCS_START_7BIT,
91 DCS_END_7BIT,
92 DCS_START_7BIT_SIZE,
93 DCS_END_7BIT_SIZE);
94 } else {
95 output->fn_write((char *)output->buffer,
96 SIXEL_OUTPUT_PACKET_SIZE, output->priv);
97 }
98 memcpy(output->buffer,
99 output->buffer + SIXEL_OUTPUT_PACKET_SIZE,
100 (size_t)(output->pos -= SIXEL_OUTPUT_PACKET_SIZE));
101 }
102}
103
104
105static void
106sixel_putc(unsigned char *buffer, unsigned char value)
107{
108 *buffer = value;
109}
110
111
112static void
113sixel_puts(unsigned char *buffer, char const *value, int size)
114{
115 memcpy(buffer, (void *)value, (size_t)size);
116}
117
118
119#if HAVE_LDIV
120static int
121sixel_putnum_impl(char *buffer, long value, int pos)
122{
123 ldiv_t r;
124
125 r = ldiv(value, 10);
126 if (r.quot > 0) {
127 pos = sixel_putnum_impl(buffer, r.quot, pos);
128 }
129 *(buffer + pos) = '0' + r.rem;
130 return pos + 1;
131}
132#endif /* HAVE_LDIV */
133
134
135static int
136sixel_putnum(char *buffer, int value)
137{
138 int pos;
139
140#if HAVE_LDIV
141 pos = sixel_putnum_impl(buffer, value, 0);
142#else
143 pos = sprintf(buffer, "%d", value);
144#endif /* HAVE_LDIV */
145
146 return pos;
147}
148
149
150static SIXELSTATUS
151sixel_put_flash(sixel_output_t *const output)
152{
153 int n;
154 int nwrite;
155
156 if (output->has_gri_arg_limit) { /* VT240 Max 255 ? */
157 while (output->save_count > 255) {
158 /* argument of DECGRI('!') is limitted to 255 in real VT */
159 sixel_puts(output->buffer + output->pos, "!255", 4);
160 sixel_advance(output, 4);
161 sixel_putc(output->buffer + output->pos, output->save_pixel);
162 sixel_advance(output, 1);
163 output->save_count -= 255;
164 }
165 }
166
167 if (output->save_count > 3) {
168 /* DECGRI Graphics Repeat Introducer ! Pn Ch */
169 sixel_putc(output->buffer + output->pos, '!');
170 sixel_advance(output, 1);
171 nwrite = sixel_putnum((char *)output->buffer + output->pos, output->save_count);
172 sixel_advance(output, nwrite);
173 sixel_putc(output->buffer + output->pos, output->save_pixel);
174 sixel_advance(output, 1);
175 } else {
176 for (n = 0; n < output->save_count; n++) {
177 output->buffer[output->pos] = output->save_pixel;
178 sixel_advance(output, 1);
179 }
180 }
181
182 output->save_pixel = 0;
183 output->save_count = 0;
184
185 return 0;
186}
187
188
189static SIXELSTATUS
190sixel_put_pixel(sixel_output_t *const output, int pix)
191{
192 SIXELSTATUS status = SIXEL_FALSE;
193
194 if (pix < 0 || pix > '?') {
195 pix = 0;
196 }
197
198 pix += '?';
199
200 if (pix == output->save_pixel) {
201 output->save_count++;
202 } else {
203 status = sixel_put_flash(output);
204 if (SIXEL_FAILED(status)) {
205 goto end;
206 }
207 output->save_pixel = pix;
208 output->save_count = 1;
209 }
210
211 status = SIXEL_OK;
212
213end:
214 return status;
215}
216
217static SIXELSTATUS
218sixel_node_new(sixel_node_t **np, sixel_allocator_t *allocator)
219{
220 SIXELSTATUS status = SIXEL_FALSE;
221
222 *np = (sixel_node_t *)sixel_allocator_malloc(allocator,
223 sizeof(sixel_node_t));
224 if (np == NULL) {
225 sixel_helper_set_additional_message(
226 "sixel_node_new: sixel_allocator_malloc() failed.");
227 status = SIXEL_BAD_ALLOCATION;
228 goto end;
229 }
230
231 status = SIXEL_OK;
232
233end:
234 return status;
235}
236
237static void
238sixel_node_del(sixel_output_t *output, sixel_node_t *np)
239{
240 sixel_node_t *tp;
241
242 if ((tp = output->node_top) == np) {
243 output->node_top = np->next;
244 } else {
245 while (tp->next != NULL) {
246 if (tp->next == np) {
247 tp->next = np->next;
248 break;
249 }
250 tp = tp->next;
251 }
252 }
253
254 np->next = output->node_free;
255 output->node_free = np;
256}
257
258
259static SIXELSTATUS
260sixel_put_node(
261 sixel_output_t /* in */ *output, /* output context */
262 int /* in/out */ *x, /* header position */
263 sixel_node_t /* in */ *np, /* node object */
264 int /* in */ ncolors, /* number of palette colors */
265 int /* in */ keycolor) /* transparent color number */
266{
267 SIXELSTATUS status = SIXEL_FALSE;
268 int nwrite;
269
270 if (ncolors != 2 || keycolor == (-1)) {
271 /* designate palette index */
272 if (output->active_palette != np->pal) {
273 sixel_putc(output->buffer + output->pos, '#');
274 sixel_advance(output, 1);
275 nwrite = sixel_putnum((char *)output->buffer + output->pos, np->pal);
276 sixel_advance(output, nwrite);
277 output->active_palette = np->pal;
278 }
279 }
280
281 for (; *x < np->sx; ++*x) {
282 status = sixel_put_pixel(output, 0);
283 if (SIXEL_FAILED(status)) {
284 goto end;
285 }
286 }
287
288 for (; *x < np->mx; ++*x) {
289 status = sixel_put_pixel(output, np->map[*x]);
290 if (SIXEL_FAILED(status)) {
291 goto end;
292 }
293 }
294
295 status = sixel_put_flash(output);
296 if (SIXEL_FAILED(status)) {
297 goto end;
298 }
299
300end:
301 return status;
302}
303
304
305static SIXELSTATUS
306sixel_encode_header(int width, int height, sixel_output_t *output)
307{
308 SIXELSTATUS status = SIXEL_FALSE;
309 int nwrite;
310
311 /* fastfetch: P2 = 1 asks for a transparent background, so a pixel we leave unset keeps
312 * whatever the terminal already had there. Upstream leaves it at 0, which tells the terminal
313 * to fill unset pixels with colour-table entry 0 instead -- and that entry is defined by the
314 * image's own palette, so a keycolor image comes out with a solid rectangle behind it rather
315 * than transparency. Measured on Windows Terminal, which implements the VT340 semantics;
316 * ImageMagick's SIXEL coder emits "0;1;0" here and chafa emits the same.
317 * The trimming below drops the trailing zero, so the envelope is "0;1" -- P3 defaults to 0. */
318 int p[3] = {0, 1, 0};
319 int pcount = 3;
320 int use_raster_attributes = 1;
321
322 output->pos = 0;
323
324 if (!output->skip_dcs_envelope) {
325 if (output->has_8bit_control) {
326 sixel_puts(output->buffer + output->pos,
327 DCS_START_8BIT,
328 DCS_START_8BIT_SIZE);
329 sixel_advance(output, DCS_START_8BIT_SIZE);
330 } else {
331 sixel_puts(output->buffer + output->pos,
332 DCS_START_7BIT,
333 DCS_START_7BIT_SIZE);
334 sixel_advance(output, DCS_START_7BIT_SIZE);
335 }
336 }
337
338 if (p[2] == 0) {
339 pcount--;
340 if (p[1] == 0) {
341 pcount--;
342 if (p[0] == 0) {
343 pcount--;
344 }
345 }
346 }
347
348 if (pcount > 0) {
349 nwrite = sixel_putnum((char *)output->buffer + output->pos, p[0]);
350 sixel_advance(output, nwrite);
351 if (pcount > 1) {
352 sixel_putc(output->buffer + output->pos, ';');
353 sixel_advance(output, 1);
354 nwrite = sixel_putnum((char *)output->buffer + output->pos, p[1]);
355 sixel_advance(output, nwrite);
356 if (pcount > 2) {
357 sixel_putc(output->buffer + output->pos, ';');
358 sixel_advance(output, 1);
359 nwrite = sixel_putnum((char *)output->buffer + output->pos, p[2]);
360 sixel_advance(output, nwrite);
361 }
362 }
363 }
364
365 sixel_putc(output->buffer + output->pos, 'q');
366 sixel_advance(output, 1);
367
368 if (use_raster_attributes) {
369 sixel_puts(output->buffer + output->pos, "\"1;1;", 5);
370 sixel_advance(output, 5);
371 nwrite = sixel_putnum((char *)output->buffer + output->pos, width);
372 sixel_advance(output, nwrite);
373 sixel_putc(output->buffer + output->pos, ';');
374 sixel_advance(output, 1);
375 nwrite = sixel_putnum((char *)output->buffer + output->pos, height);
376 sixel_advance(output, nwrite);
377 }
378
379 status = SIXEL_OK;
380
381 return status;
382}
383
384
385static SIXELSTATUS
386output_rgb_palette_definition(
387 sixel_output_t /* in */ *output,
388 unsigned char /* in */ *palette,
389 int /* in */ n,
390 int /* in */ keycolor
391)
392{
393 SIXELSTATUS status = SIXEL_FALSE;
394 int nwrite;
395
396 if (n != keycolor) {
397 /* DECGCI Graphics Color Introducer # Pc ; Pu; Px; Py; Pz */
398 sixel_putc(output->buffer + output->pos, '#');
399 sixel_advance(output, 1);
400 nwrite = sixel_putnum((char *)output->buffer + output->pos, n);
401 sixel_advance(output, nwrite);
402 sixel_puts(output->buffer + output->pos, ";2;", 3);
403 sixel_advance(output, 3);
404 nwrite = sixel_putnum((char *)output->buffer + output->pos,
405 (palette[n * 3 + 0] * 100 + 127) / 255);
406 sixel_advance(output, nwrite);
407 sixel_putc(output->buffer + output->pos, ';');
408 sixel_advance(output, 1);
409 nwrite = sixel_putnum((char *)output->buffer + output->pos,
410 (palette[n * 3 + 1] * 100 + 127) / 255);
411 sixel_advance(output, nwrite);
412 sixel_putc(output->buffer + output->pos, ';');
413 sixel_advance(output, 1);
414 nwrite = sixel_putnum((char *)output->buffer + output->pos,
415 (palette[n * 3 + 2] * 100 + 127) / 255);
416 sixel_advance(output, nwrite);
417 }
418
419 status = SIXEL_OK;
420
421 return status;
422}
423
424
425static SIXELSTATUS
426output_hls_palette_definition(
427 sixel_output_t /* in */ *output,
428 unsigned char /* in */ *palette,
429 int /* in */ n,
430 int /* in */ keycolor
431)
432{
433 SIXELSTATUS status = SIXEL_FALSE;
434 int h;
435 int l;
436 int s;
437 int r;
438 int g;
439 int b;
440 int max;
441 int min;
442 int nwrite;
443
444 if (n != keycolor) {
445 r = palette[n * 3 + 0];
446 g = palette[n * 3 + 1];
447 b = palette[n * 3 + 2];
448 max = r > g ? (r > b ? r: b): (g > b ? g: b);
449 min = r < g ? (r < b ? r: b): (g < b ? g: b);
450 l = ((max + min) * 100 + 255) / 510;
451 if (max == min) {
452 h = s = 0;
453 } else {
454 if (l < 50) {
455 s = ((max - min) * 100) / (max + min);
456 } else {
457 s = ((max - min) * 100) / ((255 - max) + (255 - min));
458 }
459 if (r == max) {
460 h = 120 + (g - b) * 60 / (max - min);
461 } else if (g == max) {
462 h = 240 + (b - r) * 60 / (max - min);
463 } else if (r < g) /* if (b == max) */ {
464 h = 360 + (r - g) * 60 / (max - min);
465 } else {
466 h = 0 + (r - g) * 60 / (max - min);
467 }
468 }
469 /* DECGCI Graphics Color Introducer # Pc ; Pu; Px; Py; Pz */
470 sixel_putc(output->buffer + output->pos, '#');
471 sixel_advance(output, 1);
472 nwrite = sixel_putnum((char *)output->buffer + output->pos, n);
473 sixel_advance(output, nwrite);
474 sixel_puts(output->buffer + output->pos, ";1;", 3);
475 sixel_advance(output, 3);
476 nwrite = sixel_putnum((char *)output->buffer + output->pos, h);
477 sixel_advance(output, nwrite);
478 sixel_putc(output->buffer + output->pos, ';');
479 sixel_advance(output, 1);
480 nwrite = sixel_putnum((char *)output->buffer + output->pos, l);
481 sixel_advance(output, nwrite);
482 sixel_putc(output->buffer + output->pos, ';');
483 sixel_advance(output, 1);
484 nwrite = sixel_putnum((char *)output->buffer + output->pos, s);
485 sixel_advance(output, nwrite);
486 }
487
488 status = SIXEL_OK;
489 return status;
490}
491
492
493static SIXELSTATUS
494sixel_encode_body(
495 sixel_index_t /* in */ *pixels,
496 int /* in */ width,
497 int /* in */ height,
498 unsigned char /* in */ *palette,
499 int /* in */ ncolors,
500 int /* in */ keycolor,
501 int /* in */ bodyonly,
502 sixel_output_t /* in */ *output,
503 unsigned char /* in */ *palstate,
504 sixel_allocator_t /* in */ *allocator)
505{
506 SIXELSTATUS status = SIXEL_FALSE;
507 int x;
508 int y;
509 int i;
510 int n;
511 int c;
512 int sx;
513 int mx;
514 int len;
515 int pix;
516 char *map = NULL;
517 int check_integer_overflow;
518 sixel_node_t *np, *tp, top;
519 int fillable;
520
521 if (ncolors < 1) {
522 status = SIXEL_BAD_ARGUMENT;
523 goto end;
524 }
525 len = ncolors * width;
526 output->active_palette = (-1);
527
528 map = (char *)sixel_allocator_calloc(allocator,
529 (size_t)len,
530 sizeof(char));
531 if (map == NULL) {
532 sixel_helper_set_additional_message(
533 "sixel_encode_body: sixel_allocator_calloc() failed.");
534 status = SIXEL_BAD_ALLOCATION;
535 goto end;
536 }
537
538 if (!bodyonly && (ncolors != 2 || keycolor == (-1))) {
539 if (output->palette_type == SIXEL_PALETTETYPE_HLS) {
540 for (n = 0; n < ncolors; n++) {
541 status = output_hls_palette_definition(output, palette, n, keycolor);
542 if (SIXEL_FAILED(status)) {
543 goto end;
544 }
545 }
546 } else {
547 for (n = 0; n < ncolors; n++) {
548 status = output_rgb_palette_definition(output, palette, n, keycolor);
549 if (SIXEL_FAILED(status)) {
550 goto end;
551 }
552 }
553 }
554 }
555
556 for (y = i = 0; y < height; y++) {
557 if (output->encode_policy != SIXEL_ENCODEPOLICY_SIZE) {
558 fillable = 0;
559 } else if (palstate) {
560 /* high color sixel */
561 pix = pixels[(y - i) * width];
562 if (pix >= ncolors) {
563 fillable = 0;
564 } else {
565 fillable = 1;
566 }
567 } else {
568 /* normal sixel */
569 fillable = 1;
570 }
571 for (x = 0; x < width; x++) {
572 if (y > INT_MAX / width) {
573 /* integer overflow */
574 sixel_helper_set_additional_message(
575 "sixel_encode_body: integer overflow detected."
576 " (y > INT_MAX)");
577 status = SIXEL_BAD_INTEGER_OVERFLOW;
578 goto end;
579 }
580 check_integer_overflow = y * width;
581 if (check_integer_overflow > INT_MAX - x) {
582 /* integer overflow */
583 sixel_helper_set_additional_message(
584 "sixel_encode_body: integer overflow detected."
585 " (y * width > INT_MAX - x)");
586 status = SIXEL_BAD_INTEGER_OVERFLOW;
587 goto end;
588 }
589 pix = pixels[check_integer_overflow + x]; /* color index */
590 if (pix >= 0 && pix < ncolors && pix != keycolor) {
591 if (pix > INT_MAX / width) {
592 /* integer overflow */
593 sixel_helper_set_additional_message(
594 "sixel_encode_body: integer overflow detected."
595 " (pix > INT_MAX / width)");
596 status = SIXEL_BAD_INTEGER_OVERFLOW;
597 goto end;
598 }
599 check_integer_overflow = pix * width;
600 if (check_integer_overflow > INT_MAX - x) {
601 /* integer overflow */
602 sixel_helper_set_additional_message(
603 "sixel_encode_body: integer overflow detected."
604 " (pix * width > INT_MAX - x)");
605 status = SIXEL_BAD_INTEGER_OVERFLOW;
606 goto end;
607 }
608 map[pix * width + x] |= (1 << i);
609 }
610 else if (!palstate) {
611 fillable = 0;
612 }
613 }
614
615 if (++i < 6 && (y + 1) < height) {
616 continue;
617 }
618
619 for (c = 0; c < ncolors; c++) {
620 for (sx = 0; sx < width; sx++) {
621 if (*(map + c * width + sx) == 0) {
622 continue;
623 }
624
625 for (mx = sx + 1; mx < width; mx++) {
626 if (*(map + c * width + mx) != 0) {
627 continue;
628 }
629
630 for (n = 1; (mx + n) < width; n++) {
631 if (*(map + c * width + mx + n) != 0) {
632 break;
633 }
634 }
635
636 if (n >= 10 || (mx + n) >= width) {
637 break;
638 }
639 mx = mx + n - 1;
640 }
641
642 if ((np = output->node_free) != NULL) {
643 output->node_free = np->next;
644 } else {
645 status = sixel_node_new(&np, allocator);
646 if (SIXEL_FAILED(status)) {
647 goto end;
648 }
649 }
650
651 np->pal = c;
652 np->sx = sx;
653 np->mx = mx;
654 np->map = map + c * width;
655
656 top.next = output->node_top;
657 tp = ⊤
658
659 while (tp->next != NULL) {
660 if (np->sx < tp->next->sx) {
661 break;
662 } else if (np->sx == tp->next->sx && np->mx > tp->next->mx) {
663 break;
664 }
665 tp = tp->next;
666 }
667
668 np->next = tp->next;
669 tp->next = np;
670 output->node_top = top.next;
671
672 sx = mx - 1;
673 }
674
675 }
676
677 if (y != 5) {
678 /* DECGNL Graphics Next Line */
679 output->buffer[output->pos] = '-';
680 sixel_advance(output, 1);
681 }
682
683 for (x = 0; (np = output->node_top) != NULL;) {
684 sixel_node_t *next;
685 if (x > np->sx) {
686 /* DECGCR Graphics Carriage Return */
687 output->buffer[output->pos] = '$';
688 sixel_advance(output, 1);
689 x = 0;
690 }
691
692 if (fillable) {
693 memset(np->map + np->sx, (1 << i) - 1, (size_t)(np->mx - np->sx));
694 }
695 status = sixel_put_node(output, &x, np, ncolors, keycolor);
696 if (SIXEL_FAILED(status)) {
697 goto end;
698 }
699 next = np->next;
700 sixel_node_del(output, np);
701 np = next;
702
703 while (np != NULL) {
704 if (np->sx < x) {
705 np = np->next;
706 continue;
707 }
708
709 if (fillable) {
710 memset(np->map + np->sx, (1 << i) - 1, (size_t)(np->mx - np->sx));
711 }
712 status = sixel_put_node(output, &x, np, ncolors, keycolor);
713 if (SIXEL_FAILED(status)) {
714 goto end;
715 }
716 next = np->next;
717 sixel_node_del(output, np);
718 np = next;
719 }
720
721 fillable = 0;
722 }
723
724 i = 0;
725 memset(map, 0, (size_t)len);
726 }
727
728 if (palstate) {
729 output->buffer[output->pos] = '$';
730 sixel_advance(output, 1);
731 }
732
733 status = SIXEL_OK;
734
735end:
736 /* free nodes */
737 while ((np = output->node_free) != NULL) {
738 output->node_free = np->next;
739 sixel_allocator_free(allocator, np);
740 }
741 output->node_top = NULL;
742
743 sixel_allocator_free(allocator, map);
744
745 return status;
746}
747
748
749static SIXELSTATUS
750sixel_encode_footer(sixel_output_t *output)
751{
752 SIXELSTATUS status = SIXEL_FALSE;
753
754 if (!output->skip_dcs_envelope && !output->penetrate_multiplexer) {
755 if (output->has_8bit_control) {
756 sixel_puts(output->buffer + output->pos,
757 DCS_END_8BIT, DCS_END_8BIT_SIZE);
758 sixel_advance(output, DCS_END_8BIT_SIZE);
759 } else {
760 sixel_puts(output->buffer + output->pos,
761 DCS_END_7BIT, DCS_END_7BIT_SIZE);
762 sixel_advance(output, DCS_END_7BIT_SIZE);
763 }
764 }
765
766 /* flush buffer */
767 if (output->pos > 0) {
768 if (output->penetrate_multiplexer) {
769 sixel_penetrate(output, output->pos,
770 DCS_START_7BIT,
771 DCS_END_7BIT,
772 DCS_START_7BIT_SIZE,
773 DCS_END_7BIT_SIZE);
774 output->fn_write((char *)DCS_7BIT("\033") DCS_7BIT("\\"),
775 (DCS_START_7BIT_SIZE + 1 + DCS_END_7BIT_SIZE) * 2,
776 output->priv);
777 } else {
778 output->fn_write((char *)output->buffer, output->pos, output->priv);
779 }
780 }
781
782 status = SIXEL_OK;
783
784 return status;
785}
786
787
788static SIXELSTATUS
789sixel_encode_dither(
790 unsigned char /* in */ *pixels, /* pixel bytes to be encoded */
791 int /* in */ width, /* width of source image */
792 int /* in */ height, /* height of source image */
793 sixel_dither_t /* in */ *dither, /* dither context */
794 sixel_output_t /* in */ *output) /* output context */
795{
796 SIXELSTATUS status = SIXEL_FALSE;
797 sixel_index_t *paletted_pixels = NULL;
798 sixel_index_t *input_pixels;
799 size_t bufsize;
800
801 switch (dither->pixelformat) {
802 case SIXEL_PIXELFORMAT_PAL1:
803 case SIXEL_PIXELFORMAT_PAL2:
804 case SIXEL_PIXELFORMAT_PAL4:
805 case SIXEL_PIXELFORMAT_G1:
806 case SIXEL_PIXELFORMAT_G2:
807 case SIXEL_PIXELFORMAT_G4:
808 bufsize = (sizeof(sixel_index_t) * (size_t)width * (size_t)height * 3UL);
809 paletted_pixels = (sixel_index_t *)sixel_allocator_malloc(dither->allocator, bufsize);
810 if (paletted_pixels == NULL) {
811 sixel_helper_set_additional_message(
812 "sixel_encode_dither: sixel_allocator_malloc() failed.");
813 status = SIXEL_BAD_ALLOCATION;
814 goto end;
815 }
816 status = sixel_helper_normalize_pixelformat(paletted_pixels,
817 &dither->pixelformat,
818 pixels,
819 dither->pixelformat,
820 width, height);
821 if (SIXEL_FAILED(status)) {
822 goto end;
823 }
824 input_pixels = paletted_pixels;
825 break;
826 case SIXEL_PIXELFORMAT_PAL8:
827 case SIXEL_PIXELFORMAT_G8:
828 case SIXEL_PIXELFORMAT_GA88:
829 case SIXEL_PIXELFORMAT_AG88:
830 input_pixels = pixels;
831 break;
832 default:
833 /* apply palette */
834 paletted_pixels = sixel_dither_apply_palette(dither, pixels,
835 width, height);
836 if (paletted_pixels == NULL) {
837 status = SIXEL_RUNTIME_ERROR;
838 goto end;
839 }
840 input_pixels = paletted_pixels;
841 break;
842 }
843
844 status = sixel_encode_header(width, height, output);
845 if (SIXEL_FAILED(status)) {
846 goto end;
847 }
848
849 status = sixel_encode_body(input_pixels,
850 width,
851 height,
852 dither->palette,
853 dither->ncolors,
854 dither->keycolor,
855 dither->bodyonly,
856 output,
857 NULL,
858 dither->allocator);
859 if (SIXEL_FAILED(status)) {
860 goto end;
861 }
862
863 status = sixel_encode_footer(output);
864 if (SIXEL_FAILED(status)) {
865 goto end;
866 }
867
868end:
869 sixel_allocator_free(dither->allocator, paletted_pixels);
870
871 return status;
872}
873
874static void
875dither_func_none(unsigned char *data, int width)
876{
877 (void) data; /* unused */
878 (void) width; /* unused */
879}
880
881
882static void
883dither_func_fs(unsigned char *data, int width)
884{
885 int r, g, b;
886 int error_r = data[0] & 0x7;
887 int error_g = data[1] & 0x7;
888 int error_b = data[2] & 0x7;
889
890 /* Floyd Steinberg Method
891 * curr 7/16
892 * 3/16 5/48 1/16
893 */
894 r = (data[3 + 0] + (error_r * 5 >> 4));
895 g = (data[3 + 1] + (error_g * 5 >> 4));
896 b = (data[3 + 2] + (error_b * 5 >> 4));
897 data[3 + 0] = r > 0xff ? 0xff: r;
898 data[3 + 1] = g > 0xff ? 0xff: g;
899 data[3 + 2] = b > 0xff ? 0xff: b;
900 r = data[width * 3 - 3 + 0] + (error_r * 3 >> 4);
901 g = data[width * 3 - 3 + 1] + (error_g * 3 >> 4);
902 b = data[width * 3 - 3 + 2] + (error_b * 3 >> 4);
903 data[width * 3 - 3 + 0] = r > 0xff ? 0xff: r;
904 data[width * 3 - 3 + 1] = g > 0xff ? 0xff: g;
905 data[width * 3 - 3 + 2] = b > 0xff ? 0xff: b;
906 r = data[width * 3 + 0] + (error_r * 5 >> 4);
907 g = data[width * 3 + 1] + (error_g * 5 >> 4);
908 b = data[width * 3 + 2] + (error_b * 5 >> 4);
909 data[width * 3 + 0] = r > 0xff ? 0xff: r;
910 data[width * 3 + 1] = g > 0xff ? 0xff: g;
911 data[width * 3 + 2] = b > 0xff ? 0xff: b;
912}
913
914
915static void
916dither_func_atkinson(unsigned char *data, int width)
917{
918 int r, g, b;
919 int error_r = data[0] & 0x7;
920 int error_g = data[1] & 0x7;
921 int error_b = data[2] & 0x7;
922
923 error_r += 4;
924 error_g += 4;
925 error_b += 4;
926
927 /* Atkinson's Method
928 * curr 1/8 1/8
929 * 1/8 1/8 1/8
930 * 1/8
931 */
932 r = data[(width * 0 + 1) * 3 + 0] + (error_r >> 3);
933 g = data[(width * 0 + 1) * 3 + 1] + (error_g >> 3);
934 b = data[(width * 0 + 1) * 3 + 2] + (error_b >> 3);
935 data[(width * 0 + 1) * 3 + 0] = r > 0xff ? 0xff: r;
936 data[(width * 0 + 1) * 3 + 1] = g > 0xff ? 0xff: g;
937 data[(width * 0 + 1) * 3 + 2] = b > 0xff ? 0xff: b;
938 r = data[(width * 0 + 2) * 3 + 0] + (error_r >> 3);
939 g = data[(width * 0 + 2) * 3 + 1] + (error_g >> 3);
940 b = data[(width * 0 + 2) * 3 + 2] + (error_b >> 3);
941 data[(width * 0 + 2) * 3 + 0] = r > 0xff ? 0xff: r;
942 data[(width * 0 + 2) * 3 + 1] = g > 0xff ? 0xff: g;
943 data[(width * 0 + 2) * 3 + 2] = b > 0xff ? 0xff: b;
944 r = data[(width * 1 - 1) * 3 + 0] + (error_r >> 3);
945 g = data[(width * 1 - 1) * 3 + 1] + (error_g >> 3);
946 b = data[(width * 1 - 1) * 3 + 2] + (error_b >> 3);
947 data[(width * 1 - 1) * 3 + 0] = r > 0xff ? 0xff: r;
948 data[(width * 1 - 1) * 3 + 1] = g > 0xff ? 0xff: g;
949 data[(width * 1 - 1) * 3 + 2] = b > 0xff ? 0xff: b;
950 r = data[(width * 1 + 0) * 3 + 0] + (error_r >> 3);
951 g = data[(width * 1 + 0) * 3 + 1] + (error_g >> 3);
952 b = data[(width * 1 + 0) * 3 + 2] + (error_b >> 3);
953 data[(width * 1 + 0) * 3 + 0] = r > 0xff ? 0xff: r;
954 data[(width * 1 + 0) * 3 + 1] = g > 0xff ? 0xff: g;
955 data[(width * 1 + 0) * 3 + 2] = b > 0xff ? 0xff: b;
956 r = (data[(width * 1 + 1) * 3 + 0] + (error_r >> 3));
957 g = (data[(width * 1 + 1) * 3 + 1] + (error_g >> 3));
958 b = (data[(width * 1 + 1) * 3 + 2] + (error_b >> 3));
959 data[(width * 1 + 1) * 3 + 0] = r > 0xff ? 0xff: r;
960 data[(width * 1 + 1) * 3 + 1] = g > 0xff ? 0xff: g;
961 data[(width * 1 + 1) * 3 + 2] = b > 0xff ? 0xff: b;
962 r = (data[(width * 2 + 0) * 3 + 0] + (error_r >> 3));
963 g = (data[(width * 2 + 0) * 3 + 1] + (error_g >> 3));
964 b = (data[(width * 2 + 0) * 3 + 2] + (error_b >> 3));
965 data[(width * 2 + 0) * 3 + 0] = r > 0xff ? 0xff: r;
966 data[(width * 2 + 0) * 3 + 1] = g > 0xff ? 0xff: g;
967 data[(width * 2 + 0) * 3 + 2] = b > 0xff ? 0xff: b;
968}
969
970
971static void
972dither_func_jajuni(unsigned char *data, int width)
973{
974 int r, g, b;
975 int error_r = data[0] & 0x7;
976 int error_g = data[1] & 0x7;
977 int error_b = data[2] & 0x7;
978
979 error_r += 4;
980 error_g += 4;
981 error_b += 4;
982
983 /* Jarvis, Judice & Ninke Method
984 * curr 7/48 5/48
985 * 3/48 5/48 7/48 5/48 3/48
986 * 1/48 3/48 5/48 3/48 1/48
987 */
988 r = data[(width * 0 + 1) * 3 + 0] + (error_r * 7 / 48);
989 g = data[(width * 0 + 1) * 3 + 1] + (error_g * 7 / 48);
990 b = data[(width * 0 + 1) * 3 + 2] + (error_b * 7 / 48);
991 data[(width * 0 + 1) * 3 + 0] = r > 0xff ? 0xff: r;
992 data[(width * 0 + 1) * 3 + 1] = g > 0xff ? 0xff: g;
993 data[(width * 0 + 1) * 3 + 2] = b > 0xff ? 0xff: b;
994 r = data[(width * 0 + 2) * 3 + 0] + (error_r * 5 / 48);
995 g = data[(width * 0 + 2) * 3 + 1] + (error_g * 5 / 48);
996 b = data[(width * 0 + 2) * 3 + 2] + (error_b * 5 / 48);
997 data[(width * 0 + 2) * 3 + 0] = r > 0xff ? 0xff: r;
998 data[(width * 0 + 2) * 3 + 1] = g > 0xff ? 0xff: g;
999 data[(width * 0 + 2) * 3 + 2] = b > 0xff ? 0xff: b;
1000 r = data[(width * 1 - 2) * 3 + 0] + (error_r * 3 / 48);
1001 g = data[(width * 1 - 2) * 3 + 1] + (error_g * 3 / 48);
1002 b = data[(width * 1 - 2) * 3 + 2] + (error_b * 3 / 48);
1003 data[(width * 1 - 2) * 3 + 0] = r > 0xff ? 0xff: r;
1004 data[(width * 1 - 2) * 3 + 1] = g > 0xff ? 0xff: g;
1005 data[(width * 1 - 2) * 3 + 2] = b > 0xff ? 0xff: b;
1006 r = data[(width * 1 - 1) * 3 + 0] + (error_r * 5 / 48);
1007 g = data[(width * 1 - 1) * 3 + 1] + (error_g * 5 / 48);
1008 b = data[(width * 1 - 1) * 3 + 2] + (error_b * 5 / 48);
1009 data[(width * 1 - 1) * 3 + 0] = r > 0xff ? 0xff: r;
1010 data[(width * 1 - 1) * 3 + 1] = g > 0xff ? 0xff: g;
1011 data[(width * 1 - 1) * 3 + 2] = b > 0xff ? 0xff: b;
1012 r = data[(width * 1 + 0) * 3 + 0] + (error_r * 7 / 48);
1013 g = data[(width * 1 + 0) * 3 + 1] + (error_g * 7 / 48);
1014 b = data[(width * 1 + 0) * 3 + 2] + (error_b * 7 / 48);
1015 data[(width * 1 + 0) * 3 + 0] = r > 0xff ? 0xff: r;
1016 data[(width * 1 + 0) * 3 + 1] = g > 0xff ? 0xff: g;
1017 data[(width * 1 + 0) * 3 + 2] = b > 0xff ? 0xff: b;
1018 r = data[(width * 1 + 1) * 3 + 0] + (error_r * 5 / 48);
1019 g = data[(width * 1 + 1) * 3 + 1] + (error_g * 5 / 48);
1020 b = data[(width * 1 + 1) * 3 + 2] + (error_b * 5 / 48);
1021 data[(width * 1 + 1) * 3 + 0] = r > 0xff ? 0xff: r;
1022 data[(width * 1 + 1) * 3 + 1] = g > 0xff ? 0xff: g;
1023 data[(width * 1 + 1) * 3 + 2] = b > 0xff ? 0xff: b;
1024 r = data[(width * 1 + 2) * 3 + 0] + (error_r * 3 / 48);
1025 g = data[(width * 1 + 2) * 3 + 1] + (error_g * 3 / 48);
1026 b = data[(width * 1 + 2) * 3 + 2] + (error_b * 3 / 48);
1027 data[(width * 1 + 2) * 3 + 0] = r > 0xff ? 0xff: r;
1028 data[(width * 1 + 2) * 3 + 1] = g > 0xff ? 0xff: g;
1029 data[(width * 1 + 2) * 3 + 2] = b > 0xff ? 0xff: b;
1030 r = data[(width * 2 - 2) * 3 + 0] + (error_r * 1 / 48);
1031 g = data[(width * 2 - 2) * 3 + 1] + (error_g * 1 / 48);
1032 b = data[(width * 2 - 2) * 3 + 2] + (error_b * 1 / 48);
1033 data[(width * 2 - 2) * 3 + 0] = r > 0xff ? 0xff: r;
1034 data[(width * 2 - 2) * 3 + 1] = g > 0xff ? 0xff: g;
1035 data[(width * 2 - 2) * 3 + 2] = b > 0xff ? 0xff: b;
1036 r = data[(width * 2 - 1) * 3 + 0] + (error_r * 3 / 48);
1037 g = data[(width * 2 - 1) * 3 + 1] + (error_g * 3 / 48);
1038 b = data[(width * 2 - 1) * 3 + 2] + (error_b * 3 / 48);
1039 data[(width * 2 - 1) * 3 + 0] = r > 0xff ? 0xff: r;
1040 data[(width * 2 - 1) * 3 + 1] = g > 0xff ? 0xff: g;
1041 data[(width * 2 - 1) * 3 + 2] = b > 0xff ? 0xff: b;
1042 r = data[(width * 2 + 0) * 3 + 0] + (error_r * 5 / 48);
1043 g = data[(width * 2 + 0) * 3 + 1] + (error_g * 5 / 48);
1044 b = data[(width * 2 + 0) * 3 + 2] + (error_b * 5 / 48);
1045 data[(width * 2 + 0) * 3 + 0] = r > 0xff ? 0xff: r;
1046 data[(width * 2 + 0) * 3 + 1] = g > 0xff ? 0xff: g;
1047 data[(width * 2 + 0) * 3 + 2] = b > 0xff ? 0xff: b;
1048 r = data[(width * 2 + 1) * 3 + 0] + (error_r * 3 / 48);
1049 g = data[(width * 2 + 1) * 3 + 1] + (error_g * 3 / 48);
1050 b = data[(width * 2 + 1) * 3 + 2] + (error_b * 3 / 48);
1051 data[(width * 2 + 1) * 3 + 0] = r > 0xff ? 0xff: r;
1052 data[(width * 2 + 1) * 3 + 1] = g > 0xff ? 0xff: g;
1053 data[(width * 2 + 1) * 3 + 2] = b > 0xff ? 0xff: b;
1054 r = data[(width * 2 + 2) * 3 + 0] + (error_r * 1 / 48);
1055 g = data[(width * 2 + 2) * 3 + 1] + (error_g * 1 / 48);
1056 b = data[(width * 2 + 2) * 3 + 2] + (error_b * 1 / 48);
1057 data[(width * 2 + 2) * 3 + 0] = r > 0xff ? 0xff: r;
1058 data[(width * 2 + 2) * 3 + 1] = g > 0xff ? 0xff: g;
1059 data[(width * 2 + 2) * 3 + 2] = b > 0xff ? 0xff: b;
1060}
1061
1062
1063static void
1064dither_func_stucki(unsigned char *data, int width)
1065{
1066 int r, g, b;
1067 int error_r = data[0] & 0x7;
1068 int error_g = data[1] & 0x7;
1069 int error_b = data[2] & 0x7;
1070
1071 error_r += 4;
1072 error_g += 4;
1073 error_b += 4;
1074
1075 /* Stucki's Method
1076 * curr 8/48 4/48
1077 * 2/48 4/48 8/48 4/48 2/48
1078 * 1/48 2/48 4/48 2/48 1/48
1079 */
1080 r = data[(width * 0 + 1) * 3 + 0] + (error_r * 8 / 48);
1081 g = data[(width * 0 + 1) * 3 + 1] + (error_g * 8 / 48);
1082 b = data[(width * 0 + 1) * 3 + 2] + (error_b * 8 / 48);
1083 data[(width * 0 + 1) * 3 + 0] = r > 0xff ? 0xff: r;
1084 data[(width * 0 + 1) * 3 + 1] = g > 0xff ? 0xff: g;
1085 data[(width * 0 + 1) * 3 + 2] = b > 0xff ? 0xff: b;
1086 r = data[(width * 0 + 2) * 3 + 0] + (error_r * 4 / 48);
1087 g = data[(width * 0 + 2) * 3 + 1] + (error_g * 4 / 48);
1088 b = data[(width * 0 + 2) * 3 + 2] + (error_b * 4 / 48);
1089 data[(width * 0 + 2) * 3 + 0] = r > 0xff ? 0xff: r;
1090 data[(width * 0 + 2) * 3 + 1] = g > 0xff ? 0xff: g;
1091 data[(width * 0 + 2) * 3 + 2] = b > 0xff ? 0xff: b;
1092 r = data[(width * 1 - 2) * 3 + 0] + (error_r * 2 / 48);
1093 g = data[(width * 1 - 2) * 3 + 1] + (error_g * 2 / 48);
1094 b = data[(width * 1 - 2) * 3 + 2] + (error_b * 2 / 48);
1095 data[(width * 1 - 2) * 3 + 0] = r > 0xff ? 0xff: r;
1096 data[(width * 1 - 2) * 3 + 1] = g > 0xff ? 0xff: g;
1097 data[(width * 1 - 2) * 3 + 2] = b > 0xff ? 0xff: b;
1098 r = data[(width * 1 - 1) * 3 + 0] + (error_r * 4 / 48);
1099 g = data[(width * 1 - 1) * 3 + 1] + (error_g * 4 / 48);
1100 b = data[(width * 1 - 1) * 3 + 2] + (error_b * 4 / 48);
1101 data[(width * 1 - 1) * 3 + 0] = r > 0xff ? 0xff: r;
1102 data[(width * 1 - 1) * 3 + 1] = g > 0xff ? 0xff: g;
1103 data[(width * 1 - 1) * 3 + 2] = b > 0xff ? 0xff: b;
1104 r = data[(width * 1 + 0) * 3 + 0] + (error_r * 8 / 48);
1105 g = data[(width * 1 + 0) * 3 + 1] + (error_g * 8 / 48);
1106 b = data[(width * 1 + 0) * 3 + 2] + (error_b * 8 / 48);
1107 data[(width * 1 + 0) * 3 + 0] = r > 0xff ? 0xff: r;
1108 data[(width * 1 + 0) * 3 + 1] = g > 0xff ? 0xff: g;
1109 data[(width * 1 + 0) * 3 + 2] = b > 0xff ? 0xff: b;
1110 r = data[(width * 1 + 1) * 3 + 0] + (error_r * 4 / 48);
1111 g = data[(width * 1 + 1) * 3 + 1] + (error_g * 4 / 48);
1112 b = data[(width * 1 + 1) * 3 + 2] + (error_b * 4 / 48);
1113 data[(width * 1 + 1) * 3 + 0] = r > 0xff ? 0xff: r;
1114 data[(width * 1 + 1) * 3 + 1] = g > 0xff ? 0xff: g;
1115 data[(width * 1 + 1) * 3 + 2] = b > 0xff ? 0xff: b;
1116 r = data[(width * 1 + 2) * 3 + 0] + (error_r * 2 / 48);
1117 g = data[(width * 1 + 2) * 3 + 1] + (error_g * 2 / 48);
1118 b = data[(width * 1 + 2) * 3 + 2] + (error_b * 2 / 48);
1119 data[(width * 1 + 2) * 3 + 0] = r > 0xff ? 0xff: r;
1120 data[(width * 1 + 2) * 3 + 1] = g > 0xff ? 0xff: g;
1121 data[(width * 1 + 2) * 3 + 2] = b > 0xff ? 0xff: b;
1122 r = data[(width * 2 - 2) * 3 + 0] + (error_r * 1 / 48);
1123 g = data[(width * 2 - 2) * 3 + 1] + (error_g * 1 / 48);
1124 b = data[(width * 2 - 2) * 3 + 2] + (error_b * 1 / 48);
1125 data[(width * 2 - 2) * 3 + 0] = r > 0xff ? 0xff: r;
1126 data[(width * 2 - 2) * 3 + 1] = g > 0xff ? 0xff: g;
1127 data[(width * 2 - 2) * 3 + 2] = b > 0xff ? 0xff: b;
1128 r = data[(width * 2 - 1) * 3 + 0] + (error_r * 2 / 48);
1129 g = data[(width * 2 - 1) * 3 + 1] + (error_g * 2 / 48);
1130 b = data[(width * 2 - 1) * 3 + 2] + (error_b * 2 / 48);
1131 data[(width * 2 - 1) * 3 + 0] = r > 0xff ? 0xff: r;
1132 data[(width * 2 - 1) * 3 + 1] = g > 0xff ? 0xff: g;
1133 data[(width * 2 - 1) * 3 + 2] = b > 0xff ? 0xff: b;
1134 r = data[(width * 2 + 0) * 3 + 0] + (error_r * 4 / 48);
1135 g = data[(width * 2 + 0) * 3 + 1] + (error_g * 4 / 48);
1136 b = data[(width * 2 + 0) * 3 + 2] + (error_b * 4 / 48);
1137 data[(width * 2 + 0) * 3 + 0] = r > 0xff ? 0xff: r;
1138 data[(width * 2 + 0) * 3 + 1] = g > 0xff ? 0xff: g;
1139 data[(width * 2 + 0) * 3 + 2] = b > 0xff ? 0xff: b;
1140 r = data[(width * 2 + 1) * 3 + 0] + (error_r * 2 / 48);
1141 g = data[(width * 2 + 1) * 3 + 1] + (error_g * 2 / 48);
1142 b = data[(width * 2 + 1) * 3 + 2] + (error_b * 2 / 48);
1143 data[(width * 2 + 1) * 3 + 0] = r > 0xff ? 0xff: r;
1144 data[(width * 2 + 1) * 3 + 1] = g > 0xff ? 0xff: g;
1145 data[(width * 2 + 1) * 3 + 2] = b > 0xff ? 0xff: b;
1146 r = data[(width * 2 + 2) * 3 + 0] + (error_r * 1 / 48);
1147 g = data[(width * 2 + 2) * 3 + 1] + (error_g * 1 / 48);
1148 b = data[(width * 2 + 2) * 3 + 2] + (error_b * 1 / 48);
1149 data[(width * 2 + 2) * 3 + 0] = r > 0xff ? 0xff: r;
1150 data[(width * 2 + 2) * 3 + 1] = g > 0xff ? 0xff: g;
1151 data[(width * 2 + 2) * 3 + 2] = b > 0xff ? 0xff: b;
1152}
1153
1154
1155static void
1156dither_func_burkes(unsigned char *data, int width)
1157{
1158 int r, g, b;
1159 int error_r = data[0] & 0x7;
1160 int error_g = data[1] & 0x7;
1161 int error_b = data[2] & 0x7;
1162
1163 error_r += 2;
1164 error_g += 2;
1165 error_b += 2;
1166
1167 /* Burkes' Method
1168 * curr 4/16 2/16
1169 * 1/16 2/16 4/16 2/16 1/16
1170 */
1171 r = data[(width * 0 + 1) * 3 + 0] + (error_r * 4 / 16);
1172 g = data[(width * 0 + 1) * 3 + 1] + (error_g * 4 / 16);
1173 b = data[(width * 0 + 1) * 3 + 2] + (error_b * 4 / 16);
1174 data[(width * 0 + 1) * 3 + 0] = r > 0xff ? 0xff: r;
1175 data[(width * 0 + 1) * 3 + 1] = g > 0xff ? 0xff: g;
1176 data[(width * 0 + 1) * 3 + 2] = b > 0xff ? 0xff: b;
1177 r = data[(width * 0 + 2) * 3 + 0] + (error_r * 2 / 16);
1178 g = data[(width * 0 + 2) * 3 + 1] + (error_g * 2 / 16);
1179 b = data[(width * 0 + 2) * 3 + 2] + (error_b * 2 / 16);
1180 data[(width * 0 + 2) * 3 + 0] = r > 0xff ? 0xff: r;
1181 data[(width * 0 + 2) * 3 + 1] = g > 0xff ? 0xff: g;
1182 data[(width * 0 + 2) * 3 + 2] = b > 0xff ? 0xff: b;
1183 r = data[(width * 1 - 2) * 3 + 0] + (error_r * 1 / 16);
1184 g = data[(width * 1 - 2) * 3 + 1] + (error_g * 1 / 16);
1185 b = data[(width * 1 - 2) * 3 + 2] + (error_b * 1 / 16);
1186 data[(width * 1 - 2) * 3 + 0] = r > 0xff ? 0xff: r;
1187 data[(width * 1 - 2) * 3 + 1] = g > 0xff ? 0xff: g;
1188 data[(width * 1 - 2) * 3 + 2] = b > 0xff ? 0xff: b;
1189 r = data[(width * 1 - 1) * 3 + 0] + (error_r * 2 / 16);
1190 g = data[(width * 1 - 1) * 3 + 1] + (error_g * 2 / 16);
1191 b = data[(width * 1 - 1) * 3 + 2] + (error_b * 2 / 16);
1192 data[(width * 1 - 1) * 3 + 0] = r > 0xff ? 0xff: r;
1193 data[(width * 1 - 1) * 3 + 1] = g > 0xff ? 0xff: g;
1194 data[(width * 1 - 1) * 3 + 2] = b > 0xff ? 0xff: b;
1195 r = data[(width * 1 + 0) * 3 + 0] + (error_r * 4 / 16);
1196 g = data[(width * 1 + 0) * 3 + 1] + (error_g * 4 / 16);
1197 b = data[(width * 1 + 0) * 3 + 2] + (error_b * 4 / 16);
1198 data[(width * 1 + 0) * 3 + 0] = r > 0xff ? 0xff: r;
1199 data[(width * 1 + 0) * 3 + 1] = g > 0xff ? 0xff: g;
1200 data[(width * 1 + 0) * 3 + 2] = b > 0xff ? 0xff: b;
1201 r = data[(width * 1 + 1) * 3 + 0] + (error_r * 2 / 16);
1202 g = data[(width * 1 + 1) * 3 + 1] + (error_g * 2 / 16);
1203 b = data[(width * 1 + 1) * 3 + 2] + (error_b * 2 / 16);
1204 data[(width * 1 + 1) * 3 + 0] = r > 0xff ? 0xff: r;
1205 data[(width * 1 + 1) * 3 + 1] = g > 0xff ? 0xff: g;
1206 data[(width * 1 + 1) * 3 + 2] = b > 0xff ? 0xff: b;
1207 r = data[(width * 1 + 2) * 3 + 0] + (error_r * 1 / 16);
1208 g = data[(width * 1 + 2) * 3 + 1] + (error_g * 1 / 16);
1209 b = data[(width * 1 + 2) * 3 + 2] + (error_b * 1 / 16);
1210 data[(width * 1 + 2) * 3 + 0] = r > 0xff ? 0xff: r;
1211 data[(width * 1 + 2) * 3 + 1] = g > 0xff ? 0xff: g;
1212 data[(width * 1 + 2) * 3 + 2] = b > 0xff ? 0xff: b;
1213}
1214
1215
1216static void
1217dither_func_a_dither(unsigned char *data, int width, int x, int y)
1218{
1219 int c;
1220 float value;
1221 float mask;
1222
1223 (void) width; /* unused */
1224
1225 for (c = 0; c < 3; c ++) {
1226 mask = (((x + c * 17) + y * 236) * 119) & 255;
1227 mask = ((mask - 128) / 256.0f) ;
1228 value = data[c] + mask;
1229 if (value < 0) {
1230 value = 0;
1231 }
1232 value = value > 255 ? 255 : value;
1233 data[c] = value;
1234 }
1235}
1236
1237
1238static void
1239dither_func_x_dither(unsigned char *data, int width, int x, int y)
1240{
1241 int c;
1242 float value;
1243 float mask;
1244
1245 (void) width; /* unused */
1246
1247 for (c = 0; c < 3; c ++) {
1248 mask = (((x + c * 17) ^ y * 236) * 1234) & 511;
1249 mask = ((mask - 128) / 512.0f) ;
1250 value = data[c] + mask;
1251 if (value < 0) {
1252 value = 0;
1253 }
1254 value = value > 255 ? 255 : value;
1255 data[c] = value;
1256 }
1257}
1258
1259
1260static void
1261sixel_apply_15bpp_dither(
1262 unsigned char *pixels,
1263 int x, int y, int width, int height,
1264 int method_for_diffuse)
1265{
1266 /* apply floyd steinberg dithering */
1267 switch (method_for_diffuse) {
1268 case SIXEL_DIFFUSE_FS:
1269 if (x < width - 1 && y < height - 1) {
1270 dither_func_fs(pixels, width);
1271 }
1272 break;
1273 case SIXEL_DIFFUSE_ATKINSON:
1274 if (x < width - 2 && y < height - 2) {
1275 dither_func_atkinson(pixels, width);
1276 }
1277 break;
1278 case SIXEL_DIFFUSE_JAJUNI:
1279 if (x < width - 2 && y < height - 2) {
1280 dither_func_jajuni(pixels, width);
1281 }
1282 break;
1283 case SIXEL_DIFFUSE_STUCKI:
1284 if (x < width - 2 && y < height - 2) {
1285 dither_func_stucki(pixels, width);
1286 }
1287 break;
1288 case SIXEL_DIFFUSE_BURKES:
1289 if (x < width - 2 && y < height - 1) {
1290 dither_func_burkes(pixels, width);
1291 }
1292 break;
1293 case SIXEL_DIFFUSE_A_DITHER:
1294 dither_func_a_dither(pixels, width, x, y);
1295 break;
1296 case SIXEL_DIFFUSE_X_DITHER:
1297 dither_func_x_dither(pixels, width, x, y);
1298 break;
1299 case SIXEL_DIFFUSE_NONE:
1300 default:
1301 dither_func_none(pixels, width);
1302 break;
1303 }
1304}
1305
1306
1307static SIXELSTATUS
1308sixel_encode_highcolor(
1309 unsigned char *pixels, int width, int height,
1310 sixel_dither_t *dither, sixel_output_t *output
1311 )
1312{
1313 SIXELSTATUS status = SIXEL_FALSE;
1314 sixel_index_t *paletted_pixels = NULL;
1315 unsigned char *normalized_pixels = NULL;
1316 /* Mark sixel line pixels which have been already drawn. */
1317 unsigned char *marks;
1318 unsigned char *rgbhit;
1319 unsigned char *rgb2pal;
1320 unsigned char palhitcount[SIXEL_PALETTE_MAX];
1321 unsigned char palstate[SIXEL_PALETTE_MAX];
1322 int output_count;
1323 int const maxcolors = 1 << 15;
1324 size_t image_size;
1325 size_t marks_size;
1326 size_t normalized_size;
1327 size_t whole_size;
1328 size_t maxcolors_size;
1329 int x, y;
1330 unsigned char *dst;
1331 unsigned char *mptr;
1332 int dirty;
1333 int mod_y;
1334 int nextpal;
1335 int threshold;
1336 int pix;
1337 int orig_height;
1338 unsigned char *pal;
1339
1340 /*
1341 * The high-color encoder keeps one palette index per input pixel
1342 * followed by color lookup tables and six scanlines of mark bytes.
1343 * Calculate all derived sizes in size_t and reject arithmetic
1344 * overflow before a wrapped value can reach the allocator.
1345 */
1346 maxcolors_size = (size_t)maxcolors;
1347 if ((size_t)height > ((size_t)-1) / (size_t)width) {
1348 sixel_helper_set_additional_message(
1349 "sixel_encode_highcolor: image size overflow.");
1350 status = SIXEL_BAD_INPUT;
1351 goto error;
1352 }
1353 image_size = (size_t)width * (size_t)height;
1354
1355 if (image_size > ((size_t)-1) / 3UL) {
1356 sixel_helper_set_additional_message(
1357 "sixel_encode_highcolor: normalized size overflow.");
1358 status = SIXEL_BAD_INPUT;
1359 goto error;
1360 }
1361 normalized_size = image_size * 3UL;
1362
1363 if ((size_t)width > ((size_t)-1) / 6UL) {
1364 sixel_helper_set_additional_message(
1365 "sixel_encode_highcolor: marks size overflow.");
1366 status = SIXEL_BAD_INPUT;
1367 goto error;
1368 }
1369 marks_size = (size_t)width * 6UL;
1370
1371 if (image_size > (size_t)-1 - maxcolors_size ||
1372 image_size + maxcolors_size > (size_t)-1 - maxcolors_size ||
1373 image_size + maxcolors_size + maxcolors_size
1374 > (size_t)-1 - marks_size) {
1375 sixel_helper_set_additional_message(
1376 "sixel_encode_highcolor: whole size overflow.");
1377 status = SIXEL_BAD_INPUT;
1378 goto error;
1379 }
1380 whole_size = image_size /* for paletted_pixels */
1381 + maxcolors_size /* for rgbhit */
1382 + maxcolors_size /* for rgb2pal */
1383 + marks_size; /* for marks */
1384
1385 if (dither->pixelformat != SIXEL_PIXELFORMAT_RGB888) {
1386 /* normalize pixelfromat */
1387 normalized_pixels = (unsigned char *)sixel_allocator_malloc(
1388 dither->allocator, normalized_size);
1389 if (normalized_pixels == NULL) {
1390 goto error;
1391 }
1392 status = sixel_helper_normalize_pixelformat(normalized_pixels,
1393 &dither->pixelformat,
1394 pixels,
1395 dither->pixelformat,
1396 width, height);
1397 if (SIXEL_FAILED(status)) {
1398 goto error;
1399 }
1400 pixels = normalized_pixels;
1401 }
1402 paletted_pixels = (sixel_index_t *)sixel_allocator_malloc(dither->allocator,
1403 whole_size);
1404 if (paletted_pixels == NULL) {
1405 goto error;
1406 }
1407 rgbhit = paletted_pixels + image_size;
1408 memset(rgbhit, 0, maxcolors_size * 2UL + marks_size);
1409 rgb2pal = rgbhit + maxcolors;
1410 marks = rgb2pal + maxcolors;
1411 output_count = 0;
1412
1413next:
1414 dst = paletted_pixels;
1415 nextpal = 0;
1416 threshold = 1;
1417 dirty = 0;
1418 mptr = marks;
1419 memset(palstate, 0, sizeof(palstate));
1420 y = mod_y = 0;
1421
1422 while (1) {
1423 for (x = 0; x < width; x++, mptr++, dst++, pixels += 3) {
1424 if (*mptr) {
1425 *dst = 255;
1426 } else {
1427 sixel_apply_15bpp_dither(pixels,
1428 x, y, width, height,
1429 dither->method_for_diffuse);
1430 pix = ((pixels[0] & 0xf8) << 7) |
1431 ((pixels[1] & 0xf8) << 2) |
1432 ((pixels[2] >> 3) & 0x1f);
1433
1434 if (!rgbhit[pix]) {
1435 while (1) {
1436 if (nextpal >= 255) {
1437 if (threshold >= 255) {
1438 break;
1439 } else {
1440 threshold = (threshold == 1) ? 9: 255;
1441 nextpal = 0;
1442 }
1443 } else if (palstate[nextpal] ||
1444 palhitcount[nextpal] > threshold) {
1445 nextpal++;
1446 } else {
1447 break;
1448 }
1449 }
1450
1451 if (nextpal >= 255) {
1452 dirty = 1;
1453 *dst = 255;
1454 } else {
1455 pal = dither->palette + (nextpal * 3);
1456
1457 rgbhit[pix] = 1;
1458 if (output_count > 0) {
1459 rgbhit[((pal[0] & 0xf8) << 7) |
1460 ((pal[1] & 0xf8) << 2) |
1461 ((pal[2] >> 3) & 0x1f)] = 0;
1462 }
1463 *dst = rgb2pal[pix] = nextpal++;
1464 *mptr = 1;
1465 palstate[*dst] = PALETTE_CHANGE;
1466 palhitcount[*dst] = 1;
1467 *(pal++) = pixels[0];
1468 *(pal++) = pixels[1];
1469 *(pal++) = pixels[2];
1470 }
1471 } else {
1472 *dst = rgb2pal[pix];
1473 *mptr = 1;
1474 if (!palstate[*dst]) {
1475 palstate[*dst] = PALETTE_HIT;
1476 }
1477 if (palhitcount[*dst] < 255) {
1478 palhitcount[*dst]++;
1479 }
1480 }
1481 }
1482 }
1483
1484 if (++y >= height) {
1485 if (dirty) {
1486 mod_y = 5;
1487 } else {
1488 goto end;
1489 }
1490 }
1491 if (dirty && (mod_y == 5 || y >= height)) {
1492 orig_height = height;
1493
1494 if (output_count++ == 0) {
1495 status = sixel_encode_header(width, height, output);
1496 if (SIXEL_FAILED(status)) {
1497 goto error;
1498 }
1499 }
1500 height = y;
1501 status = sixel_encode_body(paletted_pixels,
1502 width,
1503 height,
1504 dither->palette,
1505 255,
1506 255,
1507 dither->bodyonly,
1508 output,
1509 palstate,
1510 dither->allocator);
1511 if (SIXEL_FAILED(status)) {
1512 goto error;
1513 }
1514 if (y >= orig_height) {
1515 goto end;
1516 }
1517 pixels -= (6 * width * 3);
1518 height = orig_height - height + 6;
1519 goto next;
1520 }
1521
1522 if (++mod_y == 6) {
1523 mptr = (unsigned char *)memset(marks, 0, marks_size);
1524 mod_y = 0;
1525 }
1526 }
1527
1528 goto next;
1529
1530end:
1531 if (output_count == 0) {
1532 status = sixel_encode_header(width, height, output);
1533 if (SIXEL_FAILED(status)) {
1534 goto error;
1535 }
1536 }
1537 status = sixel_encode_body(paletted_pixels,
1538 width,
1539 height,
1540 dither->palette,
1541 255,
1542 255,
1543 dither->bodyonly,
1544 output,
1545 palstate,
1546 dither->allocator);
1547 if (SIXEL_FAILED(status)) {
1548 goto error;
1549 }
1550
1551 status = sixel_encode_footer(output);
1552 if (SIXEL_FAILED(status)) {
1553 goto error;
1554 }
1555
1556error:
1557 sixel_allocator_free(dither->allocator, paletted_pixels);
1558 sixel_allocator_free(dither->allocator, normalized_pixels);
1559
1560 return status;
1561}
1562
1563
1564SIXELAPI SIXELSTATUS
1565sixel_encode(
1566 unsigned char /* in */ *pixels, /* pixel bytes */
1567 int /* in */ width, /* image width */
1568 int /* in */ height, /* image height */
1569 int const /* in */ depth, /* color depth */
1570 sixel_dither_t /* in */ *dither, /* dither context */
1571 sixel_output_t /* in */ *output) /* output context */
1572{
1573 SIXELSTATUS status = SIXEL_FALSE;
1574
1575 (void) depth;
1576
1577 /* TODO: reference counting should be thread-safe */
1578 sixel_dither_ref(dither);
1579 sixel_output_ref(output);
1580
1581 if (width < 1) {
1582 sixel_helper_set_additional_message(
1583 "sixel_encode: bad width parameter."
1584 " (width < 1)");
1585 status = SIXEL_BAD_INPUT;
1586 goto end;
1587 }
1588
1589 if (height < 1) {
1590 sixel_helper_set_additional_message(
1591 "sixel_encode: bad height parameter."
1592 " (height < 1)");
1593 status = SIXEL_BAD_INPUT;
1594 goto end;
1595 }
1596
1597 if (width > SIXEL_WIDTH_LIMIT) {
1598 sixel_helper_set_additional_message(
1599 "sixel_encode: bad width parameter."
1600 " (width > SIXEL_WIDTH_LIMIT)");
1601 status = SIXEL_BAD_INPUT;
1602 goto end;
1603 }
1604
1605 if (height > SIXEL_HEIGHT_LIMIT) {
1606 sixel_helper_set_additional_message(
1607 "sixel_encode: bad height parameter."
1608 " (height > SIXEL_HEIGHT_LIMIT)");
1609 status = SIXEL_BAD_INPUT;
1610 goto end;
1611 }
1612
1613 if (dither->quality_mode == SIXEL_QUALITY_HIGHCOLOR) {
1614 status = sixel_encode_highcolor(pixels, width, height,
1615 dither, output);
1616 } else {
1617 status = sixel_encode_dither(pixels, width, height,
1618 dither, output);
1619 }
1620
1621end:
1622 sixel_output_unref(output);
1623 sixel_dither_unref(dither);
1624
1625 return status;
1626}
1627
1628/* emacs Local Variables: */
1629/* emacs mode: c */
1630/* emacs tab-width: 4 */
1631/* emacs indent-tabs-mode: nil */
1632/* emacs c-basic-offset: 4 */
1633/* emacs End: */
1634/* vim: set expandtab ts=4 sts=4 sw=4 : */
1635/* EOF */