1/*
2 *
3 * mediancut algorithm implementation is imported from pnmcolormap.c
4 * in netpbm library.
5 * http://netpbm.sourceforge.net/
6 *
7 * *******************************************************************************
8 * original license block of pnmcolormap.c
9 * *******************************************************************************
10 *
11 * Derived from ppmquant, originally by Jef Poskanzer.
12 *
13 * Copyright (C) 1989, 1991 by Jef Poskanzer.
14 * Copyright (C) 2001 by Bryan Henderson.
15 *
16 * Permission to use, copy, modify, and distribute this software and its
17 * documentation for any purpose and without fee is hereby granted, provided
18 * that the above copyright notice appear in all copies and that both that
19 * copyright notice and this permission notice appear in supporting
20 * documentation. This software is provided "as is" without express or
21 * implied warranty.
22 *
23 * ******************************************************************************
24 *
25 * Copyright (c) 2014-2018 Hayaki Saito
26 *
27 * Permission is hereby granted, free of charge, to any person obtaining a copy of
28 * this software and associated documentation files (the "Software"), to deal in
29 * the Software without restriction, including without limitation the rights to
30 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
31 * the Software, and to permit persons to whom the Software is furnished to do so,
32 * subject to the following conditions:
33 *
34 * The above copyright notice and this permission notice shall be included in all
35 * copies or substantial portions of the Software.
36 *
37 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
38 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
39 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
40 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
41 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
42 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
43 *
44 *
45 */
46
47#include "config.h"
48
49/* STDC_HEADERS */
50#include <stdlib.h>
51#include <stdio.h>
52
53#if HAVE_STRING_H
54# include <string.h>
55#endif /* HAVE_STRING_H */
56#if HAVE_MATH_H
57#include <math.h>
58#endif /* HAVE_MATH_H */
59#if HAVE_LIMITS_H
60# include <limits.h>
61#endif /* HAVE_MATH_H */
62#if HAVE_INTTYPES_H
63# include <inttypes.h>
64#endif /* HAVE_MATH_H */
65
66#include "quant.h"
67
68#if HAVE_DEBUG
69#define quant_trace fprintf
70#else
71static inline void quant_trace(FILE *f, ...) { (void) f; }
72#endif
73
74/*****************************************************************************
75 *
76 * quantization
77 *
78 *****************************************************************************/
79
80typedef struct box* boxVector;
81struct box {
82 unsigned int ind;
83 unsigned int colors;
84 unsigned int sum;
85};
86
87typedef unsigned long sample;
88typedef sample * tuple;
89
90struct tupleint {
91 /* An ordered pair of a tuple value and an integer, such as you
92 would find in a tuple table or tuple hash.
93 Note that this is a variable length structure.
94 */
95 unsigned int value;
96 sample tuple[1];
97 /* This is actually a variable size array -- its size is the
98 depth of the tuple in question. Some compilers do not let us
99 declare a variable length array.
100 */
101};
102typedef struct tupleint ** tupletable;
103
104typedef struct {
105 unsigned int size;
106 tupletable table;
107} tupletable2;
108
109static unsigned int compareplanePlane;
110 /* This is a parameter to compareplane(). We use this global variable
111 so that compareplane() can be called by qsort(), to compare two
112 tuples. qsort() doesn't pass any arguments except the two tuples.
113 */
114static int
115compareplane(const void * const arg1,
116 const void * const arg2)
117{
118 int lhs, rhs;
119
120 typedef const struct tupleint * const * const sortarg;
121 sortarg comparandPP = (sortarg) arg1;
122 sortarg comparatorPP = (sortarg) arg2;
123 lhs = (int)(*comparandPP)->tuple[compareplanePlane];
124 rhs = (int)(*comparatorPP)->tuple[compareplanePlane];
125
126 return lhs - rhs;
127}
128
129
130static int
131sumcompare(const void * const b1, const void * const b2)
132{
133 return (int)((boxVector)b2)->sum - (int)((boxVector)b1)->sum;
134}
135
136
137static SIXELSTATUS
138alloctupletable(
139 tupletable /* out */ *result,
140 unsigned int const /* in */ depth,
141 unsigned int const /* in */ size,
142 sixel_allocator_t /* in */ *allocator)
143{
144 SIXELSTATUS status = SIXEL_FALSE;
145 enum { message_buffer_size = 256 };
146 char message[message_buffer_size];
147 int nwrite;
148 unsigned int mainTableSize;
149 unsigned int tupleIntSize;
150 unsigned int allocSize;
151 void * pool;
152 tupletable tbl;
153 unsigned int i;
154
155 if (UINT_MAX / sizeof(struct tupleint) < size) {
156 nwrite = sprintf(message,
157 "size %u is too big for arithmetic",
158 size);
159 if (nwrite > 0) {
160 sixel_helper_set_additional_message(message);
161 }
162 status = SIXEL_RUNTIME_ERROR;
163 goto end;
164 }
165
166 mainTableSize = size * sizeof(struct tupleint *);
167 tupleIntSize = sizeof(struct tupleint) - sizeof(sample)
168 + depth * sizeof(sample);
169
170 /* To save the enormous amount of time it could take to allocate
171 each individual tuple, we do a trick here and allocate everything
172 as a single malloc block and suballocate internally.
173 */
174 if ((UINT_MAX - mainTableSize) / tupleIntSize < size) {
175 nwrite = sprintf(message,
176 "size %u is too big for arithmetic",
177 size);
178 if (nwrite > 0) {
179 sixel_helper_set_additional_message(message);
180 }
181 status = SIXEL_RUNTIME_ERROR;
182 goto end;
183 }
184
185 allocSize = mainTableSize + size * tupleIntSize;
186
187 pool = sixel_allocator_malloc(allocator, allocSize);
188 if (pool == NULL) {
189 sprintf(message,
190 "unable to allocate %u bytes for a %u-entry "
191 "tuple table",
192 allocSize, size);
193 sixel_helper_set_additional_message(message);
194 status = SIXEL_BAD_ALLOCATION;
195 goto end;
196 }
197 tbl = (tupletable) pool;
198
199 for (i = 0; i < size; ++i)
200 tbl[i] = (struct tupleint *)
201 ((char*)pool + mainTableSize + i * tupleIntSize);
202
203 *result = tbl;
204
205 status = SIXEL_OK;
206
207end:
208 return status;
209}
210
211
212/*
213** Here is the fun part, the median-cut colormap generator. This is based
214** on Paul Heckbert's paper "Color Image Quantization for Frame Buffer
215** Display", SIGGRAPH '82 Proceedings, page 297.
216*/
217
218static tupletable2
219newColorMap(unsigned int const newcolors, unsigned int const depth, sixel_allocator_t *allocator)
220{
221 SIXELSTATUS status = SIXEL_FALSE;
222 tupletable2 colormap;
223 unsigned int i;
224
225 colormap.size = 0;
226 status = alloctupletable(&colormap.table, depth, newcolors, allocator);
227 if (SIXEL_FAILED(status)) {
228 goto end;
229 }
230 if (colormap.table) {
231 for (i = 0; i < newcolors; ++i) {
232 unsigned int plane;
233 for (plane = 0; plane < depth; ++plane)
234 colormap.table[i]->tuple[plane] = 0;
235 }
236 colormap.size = newcolors;
237 }
238
239end:
240 return colormap;
241}
242
243
244static boxVector
245newBoxVector(
246 unsigned int const /* in */ colors,
247 unsigned int const /* in */ sum,
248 unsigned int const /* in */ newcolors,
249 sixel_allocator_t /* in */ *allocator)
250{
251 boxVector bv;
252
253 bv = (boxVector)sixel_allocator_malloc(allocator,
254 sizeof(struct box) * (size_t)newcolors);
255 if (bv == NULL) {
256 quant_trace(stderr, "out of memory allocating box vector table\n");
257 return NULL;
258 }
259
260 /* Set up the initial box. */
261 bv[0].ind = 0;
262 bv[0].colors = colors;
263 bv[0].sum = sum;
264
265 return bv;
266}
267
268
269static void
270findBoxBoundaries(tupletable2 const colorfreqtable,
271 unsigned int const depth,
272 unsigned int const boxStart,
273 unsigned int const boxSize,
274 sample minval[],
275 sample maxval[])
276{
277/*----------------------------------------------------------------------------
278 Go through the box finding the minimum and maximum of each
279 component - the boundaries of the box.
280-----------------------------------------------------------------------------*/
281 unsigned int plane;
282 unsigned int i;
283
284 for (plane = 0; plane < depth; ++plane) {
285 minval[plane] = colorfreqtable.table[boxStart]->tuple[plane];
286 maxval[plane] = minval[plane];
287 }
288
289 for (i = 1; i < boxSize; ++i) {
290 for (plane = 0; plane < depth; ++plane) {
291 sample const v = colorfreqtable.table[boxStart + i]->tuple[plane];
292 if (v < minval[plane]) minval[plane] = v;
293 if (v > maxval[plane]) maxval[plane] = v;
294 }
295 }
296}
297
298
299
300static unsigned int
301largestByNorm(sample minval[], sample maxval[], unsigned int const depth)
302{
303
304 unsigned int largestDimension;
305 unsigned int plane;
306 sample largestSpreadSoFar;
307
308 largestSpreadSoFar = 0;
309 largestDimension = 0;
310 for (plane = 0; plane < depth; ++plane) {
311 sample const spread = maxval[plane]-minval[plane];
312 if (spread > largestSpreadSoFar) {
313 largestDimension = plane;
314 largestSpreadSoFar = spread;
315 }
316 }
317 return largestDimension;
318}
319
320
321
322static unsigned int
323largestByLuminosity(sample minval[], sample maxval[], unsigned int const depth)
324{
325/*----------------------------------------------------------------------------
326 This subroutine presumes that the tuple type is either
327 BLACKANDWHITE, GRAYSCALE, or RGB (which implies pamP->depth is 1 or 3).
328 To save time, we don't actually check it.
329-----------------------------------------------------------------------------*/
330 unsigned int retval;
331
332 double lumin_factor[3] = {0.2989, 0.5866, 0.1145};
333
334 if (depth == 1) {
335 retval = 0;
336 } else {
337 /* An RGB tuple */
338 unsigned int largestDimension;
339 unsigned int plane;
340 double largestSpreadSoFar;
341
342 largestSpreadSoFar = 0.0;
343 largestDimension = 0;
344
345 for (plane = 0; plane < 3; ++plane) {
346 double const spread =
347 lumin_factor[plane] * (maxval[plane]-minval[plane]);
348 if (spread > largestSpreadSoFar) {
349 largestDimension = plane;
350 largestSpreadSoFar = spread;
351 }
352 }
353 retval = largestDimension;
354 }
355 return retval;
356}
357
358
359
360static void
361centerBox(unsigned int const boxStart,
362 unsigned int const boxSize,
363 tupletable2 const colorfreqtable,
364 unsigned int const depth,
365 tuple const newTuple)
366{
367
368 unsigned int plane;
369 sample minval, maxval;
370 unsigned int i;
371
372 for (plane = 0; plane < depth; ++plane) {
373 minval = maxval = colorfreqtable.table[boxStart]->tuple[plane];
374
375 for (i = 1; i < boxSize; ++i) {
376 sample v = colorfreqtable.table[boxStart + i]->tuple[plane];
377 minval = minval < v ? minval: v;
378 maxval = maxval > v ? maxval: v;
379 }
380 newTuple[plane] = (minval + maxval) / 2;
381 }
382}
383
384
385
386static void
387averageColors(unsigned int const boxStart,
388 unsigned int const boxSize,
389 tupletable2 const colorfreqtable,
390 unsigned int const depth,
391 tuple const newTuple)
392{
393 unsigned int plane;
394 sample sum;
395 unsigned int i;
396
397 for (plane = 0; plane < depth; ++plane) {
398 sum = 0;
399
400 for (i = 0; i < boxSize; ++i) {
401 sum += colorfreqtable.table[boxStart + i]->tuple[plane];
402 }
403
404 newTuple[plane] = sum / boxSize;
405 }
406}
407
408
409
410static void
411averagePixels(unsigned int const boxStart,
412 unsigned int const boxSize,
413 tupletable2 const colorfreqtable,
414 unsigned int const depth,
415 tuple const newTuple)
416{
417
418 unsigned int n;
419 /* Number of tuples represented by the box */
420 unsigned int plane;
421 unsigned int i;
422
423 /* Count the tuples in question */
424 n = 0; /* initial value */
425 for (i = 0; i < boxSize; ++i) {
426 n += (unsigned int)colorfreqtable.table[boxStart + i]->value;
427 }
428
429 for (plane = 0; plane < depth; ++plane) {
430 sample sum;
431
432 sum = 0;
433
434 for (i = 0; i < boxSize; ++i) {
435 sum += colorfreqtable.table[boxStart + i]->tuple[plane]
436 * (unsigned int)colorfreqtable.table[boxStart + i]->value;
437 }
438
439 newTuple[plane] = sum / n;
440 }
441}
442
443
444
445static tupletable2
446colormapFromBv(unsigned int const newcolors,
447 boxVector const bv,
448 unsigned int const boxes,
449 tupletable2 const colorfreqtable,
450 unsigned int const depth,
451 int const methodForRep,
452 sixel_allocator_t *allocator)
453{
454 /*
455 ** Ok, we've got enough boxes. Now choose a representative color for
456 ** each box. There are a number of possible ways to make this choice.
457 ** One would be to choose the center of the box; this ignores any structure
458 ** within the boxes. Another method would be to average all the colors in
459 ** the box - this is the method specified in Heckbert's paper. A third
460 ** method is to average all the pixels in the box.
461 */
462 tupletable2 colormap;
463 unsigned int bi;
464
465 colormap = newColorMap(newcolors, depth, allocator);
466 if (!colormap.size) {
467 return colormap;
468 }
469
470 for (bi = 0; bi < boxes; ++bi) {
471 switch (methodForRep) {
472 case SIXEL_REP_CENTER_BOX:
473 centerBox(bv[bi].ind, bv[bi].colors,
474 colorfreqtable, depth,
475 colormap.table[bi]->tuple);
476 break;
477 case SIXEL_REP_AVERAGE_COLORS:
478 averageColors(bv[bi].ind, bv[bi].colors,
479 colorfreqtable, depth,
480 colormap.table[bi]->tuple);
481 break;
482 case SIXEL_REP_AVERAGE_PIXELS:
483 averagePixels(bv[bi].ind, bv[bi].colors,
484 colorfreqtable, depth,
485 colormap.table[bi]->tuple);
486 break;
487 default:
488 quant_trace(stderr, "Internal error: "
489 "invalid value of methodForRep: %d\n",
490 methodForRep);
491 }
492 }
493 return colormap;
494}
495
496
497static SIXELSTATUS
498splitBox(boxVector const bv,
499 unsigned int *const boxesP,
500 unsigned int const bi,
501 tupletable2 const colorfreqtable,
502 unsigned int const depth,
503 int const methodForLargest)
504{
505/*----------------------------------------------------------------------------
506 Split Box 'bi' in the box vector bv (so that bv contains one more box
507 than it did as input). Split it so that each new box represents about
508 half of the pixels in the distribution given by 'colorfreqtable' for
509 the colors in the original box, but with distinct colors in each of the
510 two new boxes.
511
512 Assume the box contains at least two colors.
513-----------------------------------------------------------------------------*/
514 SIXELSTATUS status = SIXEL_FALSE;
515 unsigned int const boxStart = bv[bi].ind;
516 unsigned int const boxSize = bv[bi].colors;
517 unsigned int const sm = bv[bi].sum;
518
519 enum { max_depth= 16 };
520 sample minval[max_depth];
521 sample maxval[max_depth];
522
523 /* assert(max_depth >= depth); */
524
525 unsigned int largestDimension;
526 /* number of the plane with the largest spread */
527 unsigned int medianIndex;
528 unsigned int lowersum;
529 /* Number of pixels whose value is "less than" the median */
530
531 findBoxBoundaries(colorfreqtable, depth, boxStart, boxSize,
532 minval, maxval);
533
534 /* Find the largest dimension, and sort by that component. I have
535 included two methods for determining the "largest" dimension;
536 first by simply comparing the range in RGB space, and second by
537 transforming into luminosities before the comparison.
538 */
539 switch (methodForLargest) {
540 case SIXEL_LARGE_NORM:
541 largestDimension = largestByNorm(minval, maxval, depth);
542 break;
543 case SIXEL_LARGE_LUM:
544 largestDimension = largestByLuminosity(minval, maxval, depth);
545 break;
546 default:
547 sixel_helper_set_additional_message(
548 "Internal error: invalid value of methodForLargest.");
549 status = SIXEL_LOGIC_ERROR;
550 goto end;
551 }
552
553 /* TODO: I think this sort should go after creating a box,
554 not before splitting. Because you need the sort to use
555 the SIXEL_REP_CENTER_BOX method of choosing a color to
556 represent the final boxes
557 */
558
559 /* Set the gross global variable 'compareplanePlane' as a
560 parameter to compareplane(), which is called by qsort().
561 */
562 compareplanePlane = largestDimension;
563 qsort((char*) &colorfreqtable.table[boxStart], boxSize,
564 sizeof(colorfreqtable.table[boxStart]),
565 compareplane);
566
567 {
568 /* Now find the median based on the counts, so that about half
569 the pixels (not colors, pixels) are in each subdivision. */
570
571 unsigned int i;
572
573 lowersum = colorfreqtable.table[boxStart]->value; /* initial value */
574 for (i = 1; i < boxSize - 1 && lowersum < sm / 2; ++i) {
575 lowersum += colorfreqtable.table[boxStart + i]->value;
576 }
577 medianIndex = i;
578 }
579 /* Split the box, and sort to bring the biggest boxes to the top. */
580
581 bv[bi].colors = medianIndex;
582 bv[bi].sum = lowersum;
583 bv[*boxesP].ind = boxStart + medianIndex;
584 bv[*boxesP].colors = boxSize - medianIndex;
585 bv[*boxesP].sum = sm - lowersum;
586 ++(*boxesP);
587 qsort((char*) bv, *boxesP, sizeof(struct box), sumcompare);
588
589 status = SIXEL_OK;
590
591end:
592 return status;
593}
594
595
596
597static SIXELSTATUS
598mediancut(tupletable2 const colorfreqtable,
599 unsigned int const depth,
600 unsigned int const newcolors,
601 int const methodForLargest,
602 int const methodForRep,
603 tupletable2 *const colormapP,
604 sixel_allocator_t *allocator)
605{
606/*----------------------------------------------------------------------------
607 Compute a set of only 'newcolors' colors that best represent an
608 image whose pixels are summarized by the histogram
609 'colorfreqtable'. Each tuple in that table has depth 'depth'.
610 colorfreqtable.table[i] tells the number of pixels in the subject image
611 have a particular color.
612
613 As a side effect, sort 'colorfreqtable'.
614-----------------------------------------------------------------------------*/
615 boxVector bv;
616 unsigned int bi;
617 unsigned int boxes;
618 int multicolorBoxesExist;
619 unsigned int i;
620 unsigned int sum;
621 SIXELSTATUS status = SIXEL_FALSE;
622
623 sum = 0;
624
625 for (i = 0; i < colorfreqtable.size; ++i) {
626 sum += colorfreqtable.table[i]->value;
627 }
628
629 /* There is at least one box that contains at least 2 colors; ergo,
630 there is more splitting we can do. */
631 bv = newBoxVector(colorfreqtable.size, sum, newcolors, allocator);
632 if (bv == NULL) {
633 goto end;
634 }
635 boxes = 1;
636 multicolorBoxesExist = (colorfreqtable.size > 1);
637
638 /* Main loop: split boxes until we have enough. */
639 while (boxes < newcolors && multicolorBoxesExist) {
640 /* Find the first splittable box. */
641 for (bi = 0; bi < boxes && bv[bi].colors < 2; ++bi)
642 ;
643 if (bi >= boxes) {
644 multicolorBoxesExist = 0;
645 } else {
646 status = splitBox(bv, &boxes, bi,
647 colorfreqtable, depth,
648 methodForLargest);
649 if (SIXEL_FAILED(status)) {
650 goto end;
651 }
652 }
653 }
654 *colormapP = colormapFromBv(newcolors, bv, boxes,
655 colorfreqtable, depth,
656 methodForRep, allocator);
657
658 sixel_allocator_free(allocator, bv);
659
660 status = SIXEL_OK;
661
662end:
663 return status;
664}
665
666
667static unsigned int
668computeHash(unsigned char const *data, unsigned int const depth)
669{
670 unsigned int hash = 0;
671 unsigned int n;
672
673 for (n = 0; n < depth; n++) {
674 hash |= (unsigned int)(data[depth - 1 - n] >> 3) << n * 5;
675 }
676
677 return hash;
678}
679
680
681static SIXELSTATUS
682computeHistogram(unsigned char const /* in */ *data,
683 unsigned int /* in */ length,
684 unsigned long const /* in */ depth,
685 tupletable2 * const /* out */ colorfreqtableP,
686 int const /* in */ qualityMode,
687 sixel_allocator_t /* in */ *allocator)
688{
689 SIXELSTATUS status = SIXEL_FALSE;
690 typedef unsigned short unit_t;
691 unsigned int i, n;
692 unit_t *histogram = NULL;
693 unit_t *refmap = NULL;
694 unit_t *ref;
695 unit_t *it;
696 unsigned int bucket_index;
697 unsigned int step;
698 unsigned int max_sample;
699
700 switch (qualityMode) {
701 case SIXEL_QUALITY_LOW:
702 max_sample = 18383;
703 break;
704 case SIXEL_QUALITY_HIGH:
705 max_sample = 1118383;
706 break;
707 case SIXEL_QUALITY_FULL:
708 default:
709 max_sample = 4003079;
710 break;
711 }
712
713 step = length / depth / max_sample * depth;
714 if (step <= 0) {
715 step = depth;
716 }
717
718 quant_trace(stderr, "making histogram...\n");
719
720 histogram = (unit_t *)sixel_allocator_calloc(allocator,
721 (size_t)(1 << depth * 5),
722 sizeof(unit_t));
723 if (histogram == NULL) {
724 sixel_helper_set_additional_message(
725 "unable to allocate memory for histogram.");
726 status = SIXEL_BAD_ALLOCATION;
727 goto end;
728 }
729 it = ref = refmap
730 = (unsigned short *)sixel_allocator_malloc(allocator,
731 (size_t)(1 << depth * 5) * sizeof(unit_t));
732 if (!it) {
733 sixel_helper_set_additional_message(
734 "unable to allocate memory for lookup table.");
735 status = SIXEL_BAD_ALLOCATION;
736 goto end;
737 }
738
739 for (i = 0; i < length; i += step) {
740 bucket_index = computeHash(data + i, 3);
741 if (histogram[bucket_index] == 0) {
742 *ref++ = bucket_index;
743 }
744 if (histogram[bucket_index] < (unsigned int)(1 << sizeof(unsigned short) * 8) - 1) {
745 histogram[bucket_index]++;
746 }
747 }
748
749 colorfreqtableP->size = (unsigned int)(ref - refmap);
750
751 status = alloctupletable(&colorfreqtableP->table, depth, (unsigned int)(ref - refmap), allocator);
752 if (SIXEL_FAILED(status)) {
753 goto end;
754 }
755 for (i = 0; i < colorfreqtableP->size; ++i) {
756 if (histogram[refmap[i]] > 0) {
757 colorfreqtableP->table[i]->value = histogram[refmap[i]];
758 for (n = 0; n < depth; n++) {
759 colorfreqtableP->table[i]->tuple[depth - 1 - n]
760 = (sample)((*it >> n * 5 & 0x1f) << 3);
761 }
762 }
763 it++;
764 }
765
766 quant_trace(stderr, "%u colors found\n", colorfreqtableP->size);
767
768 status = SIXEL_OK;
769
770end:
771 sixel_allocator_free(allocator, refmap);
772 sixel_allocator_free(allocator, histogram);
773
774 return status;
775}
776
777
778static int
779computeColorMapFromInput(unsigned char const *data,
780 unsigned int const length,
781 unsigned int const depth,
782 unsigned int const reqColors,
783 int const methodForLargest,
784 int const methodForRep,
785 int const qualityMode,
786 tupletable2 * const colormapP,
787 unsigned int *origcolors,
788 sixel_allocator_t *allocator)
789{
790/*----------------------------------------------------------------------------
791 Produce a colormap containing the best colors to represent the
792 image stream in file 'ifP'. Figure it out using the median cut
793 technique.
794
795 The colormap will have 'reqcolors' or fewer colors in it, unless
796 'allcolors' is true, in which case it will have all the colors that
797 are in the input.
798
799 The colormap has the same maxval as the input.
800
801 Put the colormap in newly allocated storage as a tupletable2
802 and return its address as *colormapP. Return the number of colors in
803 it as *colorsP and its maxval as *colormapMaxvalP.
804
805 Return the characteristics of the input file as
806 *formatP and *freqPamP. (This information is not really
807 relevant to our colormap mission; just a fringe benefit).
808-----------------------------------------------------------------------------*/
809 SIXELSTATUS status = SIXEL_FALSE;
810 tupletable2 colorfreqtable = {0, NULL};
811 unsigned int i;
812 unsigned int n;
813
814 status = computeHistogram(data, length, depth,
815 &colorfreqtable, qualityMode, allocator);
816 if (SIXEL_FAILED(status)) {
817 goto end;
818 }
819 if (origcolors) {
820 *origcolors = colorfreqtable.size;
821 }
822
823 if (colorfreqtable.size <= reqColors) {
824 quant_trace(stderr,
825 "Image already has few enough colors (<=%d). "
826 "Keeping same colors.\n", reqColors);
827 /* *colormapP = colorfreqtable; */
828 colormapP->size = colorfreqtable.size;
829 status = alloctupletable(&colormapP->table, depth, colorfreqtable.size, allocator);
830 if (SIXEL_FAILED(status)) {
831 goto end;
832 }
833 for (i = 0; i < colorfreqtable.size; ++i) {
834 colormapP->table[i]->value = colorfreqtable.table[i]->value;
835 for (n = 0; n < depth; ++n) {
836 colormapP->table[i]->tuple[n] = colorfreqtable.table[i]->tuple[n];
837 }
838 }
839 } else {
840 quant_trace(stderr, "choosing %d colors...\n", reqColors);
841 status = mediancut(colorfreqtable, depth, reqColors,
842 methodForLargest, methodForRep, colormapP, allocator);
843 if (SIXEL_FAILED(status)) {
844 goto end;
845 }
846 quant_trace(stderr, "%d colors are choosed.\n", colorfreqtable.size);
847 }
848
849 status = SIXEL_OK;
850
851end:
852 sixel_allocator_free(allocator, colorfreqtable.table);
853 return status;
854}
855
856
857/* diffuse error energy to surround pixels */
858static void
859error_diffuse(unsigned char /* in */ *data, /* base address of pixel buffer */
860 int /* in */ pos, /* address of the destination pixel */
861 int /* in */ depth, /* color depth in bytes */
862 int /* in */ error, /* error energy */
863 int /* in */ numerator, /* numerator of diffusion coefficient */
864 int /* in */ denominator /* denominator of diffusion coefficient */)
865{
866 int c;
867
868 data += pos * depth;
869
870 c = *data + error * numerator / denominator;
871 if (c < 0) {
872 c = 0;
873 }
874 if (c >= 1 << 8) {
875 c = (1 << 8) - 1;
876 }
877 *data = (unsigned char)c;
878}
879
880
881static void
882diffuse_none(unsigned char *data, int width, int height,
883 int x, int y, int depth, int error)
884{
885 /* unused */ (void) data;
886 /* unused */ (void) width;
887 /* unused */ (void) height;
888 /* unused */ (void) x;
889 /* unused */ (void) y;
890 /* unused */ (void) depth;
891 /* unused */ (void) error;
892}
893
894
895static void
896diffuse_fs(unsigned char *data, int width, int height,
897 int x, int y, int depth, int error)
898{
899 int pos;
900
901 pos = y * width + x;
902
903 /* Floyd Steinberg Method
904 * curr 7/16
905 * 3/16 5/48 1/16
906 */
907 if (x < width - 1 && y < height - 1) {
908 /* add error to the right cell */
909 error_diffuse(data, pos + width * 0 + 1, depth, error, 7, 16);
910 /* add error to the left-bottom cell */
911 error_diffuse(data, pos + width * 1 - 1, depth, error, 3, 16);
912 /* add error to the bottom cell */
913 error_diffuse(data, pos + width * 1 + 0, depth, error, 5, 16);
914 /* add error to the right-bottom cell */
915 error_diffuse(data, pos + width * 1 + 1, depth, error, 1, 16);
916 }
917}
918
919
920static void
921diffuse_atkinson(unsigned char *data, int width, int height,
922 int x, int y, int depth, int error)
923{
924 int pos;
925
926 pos = y * width + x;
927
928 /* Atkinson's Method
929 * curr 1/8 1/8
930 * 1/8 1/8 1/8
931 * 1/8
932 */
933 if (y < height - 2) {
934 /* add error to the right cell */
935 error_diffuse(data, pos + width * 0 + 1, depth, error, 1, 8);
936 /* add error to the 2th right cell */
937 error_diffuse(data, pos + width * 0 + 2, depth, error, 1, 8);
938 /* add error to the left-bottom cell */
939 error_diffuse(data, pos + width * 1 - 1, depth, error, 1, 8);
940 /* add error to the bottom cell */
941 error_diffuse(data, pos + width * 1 + 0, depth, error, 1, 8);
942 /* add error to the right-bottom cell */
943 error_diffuse(data, pos + width * 1 + 1, depth, error, 1, 8);
944 /* add error to the 2th bottom cell */
945 error_diffuse(data, pos + width * 2 + 0, depth, error, 1, 8);
946 }
947}
948
949
950static void
951diffuse_jajuni(unsigned char *data, int width, int height,
952 int x, int y, int depth, int error)
953{
954 int pos;
955
956 pos = y * width + x;
957
958 /* Jarvis, Judice & Ninke Method
959 * curr 7/48 5/48
960 * 3/48 5/48 7/48 5/48 3/48
961 * 1/48 3/48 5/48 3/48 1/48
962 */
963 if (pos < (height - 2) * width - 2) {
964 error_diffuse(data, pos + width * 0 + 1, depth, error, 7, 48);
965 error_diffuse(data, pos + width * 0 + 2, depth, error, 5, 48);
966 error_diffuse(data, pos + width * 1 - 2, depth, error, 3, 48);
967 error_diffuse(data, pos + width * 1 - 1, depth, error, 5, 48);
968 error_diffuse(data, pos + width * 1 + 0, depth, error, 7, 48);
969 error_diffuse(data, pos + width * 1 + 1, depth, error, 5, 48);
970 error_diffuse(data, pos + width * 1 + 2, depth, error, 3, 48);
971 error_diffuse(data, pos + width * 2 - 2, depth, error, 1, 48);
972 error_diffuse(data, pos + width * 2 - 1, depth, error, 3, 48);
973 error_diffuse(data, pos + width * 2 + 0, depth, error, 5, 48);
974 error_diffuse(data, pos + width * 2 + 1, depth, error, 3, 48);
975 error_diffuse(data, pos + width * 2 + 2, depth, error, 1, 48);
976 }
977}
978
979
980static void
981diffuse_stucki(unsigned char *data, int width, int height,
982 int x, int y, int depth, int error)
983{
984 int pos;
985
986 pos = y * width + x;
987
988 /* Stucki's Method
989 * curr 8/48 4/48
990 * 2/48 4/48 8/48 4/48 2/48
991 * 1/48 2/48 4/48 2/48 1/48
992 */
993 if (pos < (height - 2) * width - 2) {
994 error_diffuse(data, pos + width * 0 + 1, depth, error, 1, 6);
995 error_diffuse(data, pos + width * 0 + 2, depth, error, 1, 12);
996 error_diffuse(data, pos + width * 1 - 2, depth, error, 1, 24);
997 error_diffuse(data, pos + width * 1 - 1, depth, error, 1, 12);
998 error_diffuse(data, pos + width * 1 + 0, depth, error, 1, 6);
999 error_diffuse(data, pos + width * 1 + 1, depth, error, 1, 12);
1000 error_diffuse(data, pos + width * 1 + 2, depth, error, 1, 24);
1001 error_diffuse(data, pos + width * 2 - 2, depth, error, 1, 48);
1002 error_diffuse(data, pos + width * 2 - 1, depth, error, 1, 24);
1003 error_diffuse(data, pos + width * 2 + 0, depth, error, 1, 12);
1004 error_diffuse(data, pos + width * 2 + 1, depth, error, 1, 24);
1005 error_diffuse(data, pos + width * 2 + 2, depth, error, 1, 48);
1006 }
1007}
1008
1009
1010static void
1011diffuse_burkes(unsigned char *data, int width, int height,
1012 int x, int y, int depth, int error)
1013{
1014 int pos;
1015
1016 pos = y * width + x;
1017
1018 /* Burkes' Method
1019 * curr 4/16 2/16
1020 * 1/16 2/16 4/16 2/16 1/16
1021 */
1022 if (pos < (height - 1) * width - 2) {
1023 error_diffuse(data, pos + width * 0 + 1, depth, error, 1, 4);
1024 error_diffuse(data, pos + width * 0 + 2, depth, error, 1, 8);
1025 error_diffuse(data, pos + width * 1 - 2, depth, error, 1, 16);
1026 error_diffuse(data, pos + width * 1 - 1, depth, error, 1, 8);
1027 error_diffuse(data, pos + width * 1 + 0, depth, error, 1, 4);
1028 error_diffuse(data, pos + width * 1 + 1, depth, error, 1, 8);
1029 error_diffuse(data, pos + width * 1 + 2, depth, error, 1, 16);
1030 }
1031}
1032
1033static float
1034mask_a (int x, int y, int c)
1035{
1036 return ((((x + c * 67) + y * 236) * 119) & 255 ) / 128.0 - 1.0;
1037}
1038
1039static float
1040mask_x (int x, int y, int c)
1041{
1042 return ((((x + c * 29) ^ y* 149) * 1234) & 511 ) / 256.0 - 1.0;
1043}
1044
1045/* lookup closest color from palette with "normal" strategy */
1046static int
1047lookup_normal(unsigned char const * const pixel,
1048 int const depth,
1049 unsigned char const * const palette,
1050 int const reqcolor,
1051 unsigned short * const cachetable,
1052 int const complexion)
1053{
1054 int result;
1055 int diff;
1056 int r;
1057 int i;
1058 int n;
1059 int distant;
1060
1061 result = (-1);
1062 diff = INT_MAX;
1063
1064 /* don't use cachetable in 'normal' strategy */
1065 (void) cachetable;
1066
1067 for (i = 0; i < reqcolor; i++) {
1068 distant = 0;
1069 r = pixel[0] - palette[i * depth + 0];
1070 distant += r * r * complexion;
1071 for (n = 1; n < depth; ++n) {
1072 r = pixel[n] - palette[i * depth + n];
1073 distant += r * r;
1074 }
1075 if (distant < diff) {
1076 diff = distant;
1077 result = i;
1078 }
1079 }
1080
1081 return result;
1082}
1083
1084
1085/* lookup closest color from palette with "fast" strategy */
1086static int
1087lookup_fast(unsigned char const * const pixel,
1088 int const depth,
1089 unsigned char const * const palette,
1090 int const reqcolor,
1091 unsigned short * const cachetable,
1092 int const complexion)
1093{
1094 int result;
1095 unsigned int hash;
1096 int diff;
1097 int cache;
1098 int i;
1099 int distant;
1100
1101 /* don't use depth in 'fast' strategy because it's always 3 */
1102 (void) depth;
1103
1104 result = (-1);
1105 diff = INT_MAX;
1106 hash = computeHash(pixel, 3);
1107
1108 cache = cachetable[hash];
1109 if (cache) { /* fast lookup */
1110 return cache - 1;
1111 }
1112 /* collision */
1113 for (i = 0; i < reqcolor; i++) {
1114 distant = 0;
1115#if 0
1116 for (n = 0; n < 3; ++n) {
1117 r = pixel[n] - palette[i * 3 + n];
1118 distant += r * r;
1119 }
1120#elif 1 /* complexion correction */
1121 distant = (pixel[0] - palette[i * 3 + 0]) * (pixel[0] - palette[i * 3 + 0]) * complexion
1122 + (pixel[1] - palette[i * 3 + 1]) * (pixel[1] - palette[i * 3 + 1])
1123 + (pixel[2] - palette[i * 3 + 2]) * (pixel[2] - palette[i * 3 + 2])
1124 ;
1125#endif
1126 if (distant < diff) {
1127 diff = distant;
1128 result = i;
1129 }
1130 }
1131 cachetable[hash] = result + 1;
1132
1133 return result;
1134}
1135
1136
1137static int
1138lookup_mono_darkbg(unsigned char const * const pixel,
1139 int const depth,
1140 unsigned char const * const palette,
1141 int const reqcolor,
1142 unsigned short * const cachetable,
1143 int const complexion)
1144{
1145 int n;
1146 int distant;
1147
1148 /* unused */ (void) palette;
1149 /* unused */ (void) cachetable;
1150 /* unused */ (void) complexion;
1151
1152 distant = 0;
1153 for (n = 0; n < depth; ++n) {
1154 distant += pixel[n];
1155 }
1156 return distant >= 128 * reqcolor ? 1: 0;
1157}
1158
1159
1160static int
1161lookup_mono_lightbg(unsigned char const * const pixel,
1162 int const depth,
1163 unsigned char const * const palette,
1164 int const reqcolor,
1165 unsigned short * const cachetable,
1166 int const complexion)
1167{
1168 int n;
1169 int distant;
1170
1171 /* unused */ (void) palette;
1172 /* unused */ (void) cachetable;
1173 /* unused */ (void) complexion;
1174
1175 distant = 0;
1176 for (n = 0; n < depth; ++n) {
1177 distant += pixel[n];
1178 }
1179 return distant < 128 * reqcolor ? 1: 0;
1180}
1181
1182
1183/* choose colors using median-cut method */
1184SIXELSTATUS
1185sixel_quant_make_palette(
1186 unsigned char /* out */ **result,
1187 unsigned char const /* in */ *data,
1188 unsigned int /* in */ length,
1189 int /* in */ pixelformat,
1190 unsigned int /* in */ reqcolors,
1191 unsigned int /* in */ *ncolors,
1192 unsigned int /* in */ *origcolors,
1193 int /* in */ methodForLargest,
1194 int /* in */ methodForRep,
1195 int /* in */ qualityMode,
1196 sixel_allocator_t /* in */ *allocator)
1197{
1198 SIXELSTATUS status = SIXEL_FALSE;
1199 unsigned int i;
1200 unsigned int n;
1201 int ret;
1202 tupletable2 colormap;
1203 unsigned int depth;
1204 int result_depth;
1205
1206 result_depth = sixel_helper_compute_depth(pixelformat);
1207 if (result_depth <= 0) {
1208 *result = NULL;
1209 goto end;
1210 }
1211
1212 depth = (unsigned int)result_depth;
1213
1214 ret = computeColorMapFromInput(data, length, depth,
1215 reqcolors, methodForLargest,
1216 methodForRep, qualityMode,
1217 &colormap, origcolors, allocator);
1218 if (ret != 0) {
1219 *result = NULL;
1220 goto end;
1221 }
1222 *ncolors = colormap.size;
1223 quant_trace(stderr, "tupletable size: %d\n", *ncolors);
1224 *result = (unsigned char *)sixel_allocator_malloc(allocator, *ncolors * depth);
1225 for (i = 0; i < *ncolors; i++) {
1226 for (n = 0; n < depth; ++n) {
1227 (*result)[i * depth + n] = colormap.table[i]->tuple[n];
1228 }
1229 }
1230
1231 sixel_allocator_free(allocator, colormap.table);
1232
1233 status = SIXEL_OK;
1234
1235end:
1236 return status;
1237}
1238
1239
1240/* apply color palette into specified pixel buffers */
1241SIXELSTATUS
1242sixel_quant_apply_palette(
1243 sixel_index_t /* out */ *result,
1244 unsigned char /* in */ *data,
1245 int /* in */ width,
1246 int /* in */ height,
1247 int /* in */ depth,
1248 unsigned char /* in */ *palette,
1249 int /* in */ reqcolor,
1250 int /* in */ methodForDiffuse,
1251 int /* in */ foptimize,
1252 int /* in */ foptimize_palette,
1253 int /* in */ complexion,
1254 unsigned short /* in */ *cachetable,
1255 int /* in */ *ncolors,
1256 sixel_allocator_t /* in */ *allocator)
1257{
1258 typedef int component_t;
1259 enum { max_depth = 4 };
1260 enum { max_channel_diff_sq = 255 * 255 };
1261 SIXELSTATUS status = SIXEL_FALSE;
1262 int pos, n, x, y, sum1, sum2;
1263 int non_weighted_components;
1264 component_t offset;
1265 int color_index;
1266 long long max_complexion;
1267 unsigned short *indextable;
1268 unsigned char new_palette[SIXEL_PALETTE_MAX * 4];
1269 unsigned short migration_map[SIXEL_PALETTE_MAX];
1270 float (*f_mask) (int x, int y, int c) = NULL;
1271 void (*f_diffuse)(unsigned char *data, int width, int height,
1272 int x, int y, int depth, int offset);
1273 int (*f_lookup)(unsigned char const * const pixel,
1274 int const depth,
1275 unsigned char const * const palette,
1276 int const reqcolor,
1277 unsigned short * const cachetable,
1278 int const complexion);
1279
1280 /* check bad reqcolor */
1281 if (reqcolor < 1) {
1282 status = SIXEL_BAD_ARGUMENT;
1283 sixel_helper_set_additional_message(
1284 "sixel_quant_apply_palette: "
1285 "a bad argument is detected, reqcolor < 0.");
1286 goto end;
1287 }
1288
1289 /* NOTE: diffuse_jajuni, diffuse_stucki, and diffuse_burkes reference at
1290 * minimum the position pos + width * 1 - 2, so width must be at least 2
1291 * to avoid underflow.
1292 * On the other hand, diffuse_fs and diffuse_atkinson
1293 * reference pos + width * 1 - 1, but since these functions are only called
1294 * when width >= 1, they do not cause underflow.
1295 */
1296 if (depth != 3) {
1297 f_diffuse = diffuse_none;
1298 } else {
1299 switch (methodForDiffuse) {
1300 case SIXEL_DIFFUSE_NONE:
1301 f_diffuse = diffuse_none;
1302 break;
1303 case SIXEL_DIFFUSE_ATKINSON:
1304 f_diffuse = diffuse_atkinson;
1305 break;
1306 case SIXEL_DIFFUSE_FS:
1307 f_diffuse = diffuse_fs;
1308 break;
1309 case SIXEL_DIFFUSE_JAJUNI:
1310 /* fallback to diffuse_none if width < 2 */
1311 f_diffuse = width >= 2 ? diffuse_jajuni: diffuse_none;
1312 break;
1313 case SIXEL_DIFFUSE_STUCKI:
1314 /* fallback to diffuse_none if width < 2 */
1315 f_diffuse = width >= 2 ? diffuse_stucki: diffuse_none;
1316 break;
1317 case SIXEL_DIFFUSE_BURKES:
1318 /* fallback to diffuse_none if width < 2 */
1319 f_diffuse = width >= 2 ? diffuse_burkes: diffuse_none;
1320 break;
1321 case SIXEL_DIFFUSE_A_DITHER:
1322 f_diffuse = diffuse_none;
1323 f_mask = mask_a;
1324 break;
1325 case SIXEL_DIFFUSE_X_DITHER:
1326 f_diffuse = diffuse_none;
1327 f_mask = mask_x;
1328 break;
1329 default:
1330 quant_trace(stderr, "Internal error: invalid value of"
1331 " methodForDiffuse: %d\n",
1332 methodForDiffuse);
1333 f_diffuse = diffuse_none;
1334 break;
1335 }
1336 }
1337
1338 f_lookup = NULL;
1339 if (reqcolor == 2) {
1340 sum1 = 0;
1341 sum2 = 0;
1342 for (n = 0; n < depth; ++n) {
1343 sum1 += palette[n];
1344 }
1345 for (n = depth; n < depth + depth; ++n) {
1346 sum2 += palette[n];
1347 }
1348 if (sum1 == 0 && sum2 == 255 * 3) {
1349 f_lookup = lookup_mono_darkbg;
1350 } else if (sum1 == 255 * 3 && sum2 == 0) {
1351 f_lookup = lookup_mono_lightbg;
1352 }
1353 }
1354 if (f_lookup == NULL) {
1355 if (foptimize && depth == 3) {
1356 f_lookup = lookup_fast;
1357 } else {
1358 f_lookup = lookup_normal;
1359 }
1360 }
1361
1362 if ((f_lookup == lookup_fast || f_lookup == lookup_normal) && complexion > 1) {
1363 non_weighted_components = depth > 1 ? depth - 1 : 0;
1364 max_complexion = (INT_MAX - (long long)max_channel_diff_sq
1365 * (long long)non_weighted_components)
1366 / (long long)max_channel_diff_sq;
1367 if ((long long)complexion > max_complexion) {
1368 status = SIXEL_BAD_ARGUMENT;
1369 sixel_helper_set_additional_message(
1370 "sixel_quant_apply_palette: complexion parameter is too large.");
1371 goto end;
1372 }
1373 }
1374
1375 indextable = cachetable;
1376 if (cachetable == NULL && f_lookup == lookup_fast) {
1377 indextable = (unsigned short *)sixel_allocator_calloc(allocator,
1378 (size_t)(1 << depth * 5),
1379 sizeof(unsigned short));
1380 if (!indextable) {
1381 quant_trace(stderr, "Unable to allocate memory for indextable.\n");
1382 goto end;
1383 }
1384 }
1385
1386 if (foptimize_palette) {
1387 *ncolors = 0;
1388
1389 memset(new_palette, 0x00, sizeof(SIXEL_PALETTE_MAX * depth));
1390 memset(migration_map, 0x00, sizeof(migration_map));
1391
1392 if (f_mask) {
1393 for (y = 0; y < height; ++y) {
1394 for (x = 0; x < width; ++x) {
1395 unsigned char copy[max_depth];
1396 int d;
1397 int val;
1398
1399 pos = y * width + x;
1400 for (d = 0; d < depth; d ++) {
1401 val = data[pos * depth + d] + f_mask(x, y, d) * 32;
1402 copy[d] = val < 0 ? 0 : val > 255 ? 255 : val;
1403 }
1404 color_index = f_lookup(copy, depth,
1405 palette, reqcolor, indextable, complexion);
1406 if (migration_map[color_index] == 0) {
1407 result[pos] = *ncolors;
1408 for (n = 0; n < depth; ++n) {
1409 new_palette[*ncolors * depth + n] = palette[color_index * depth + n];
1410 }
1411 ++*ncolors;
1412 migration_map[color_index] = *ncolors;
1413 } else {
1414 result[pos] = migration_map[color_index] - 1;
1415 }
1416 }
1417 }
1418 memcpy(palette, new_palette, (size_t)(*ncolors * depth));
1419 } else {
1420 for (y = 0; y < height; ++y) {
1421 for (x = 0; x < width; ++x) {
1422 pos = y * width + x;
1423 color_index = f_lookup(data + (pos * depth), depth,
1424 palette, reqcolor, indextable, complexion);
1425 if (migration_map[color_index] == 0) {
1426 result[pos] = *ncolors;
1427 for (n = 0; n < depth; ++n) {
1428 new_palette[*ncolors * depth + n] = palette[color_index * depth + n];
1429 }
1430 ++*ncolors;
1431 migration_map[color_index] = *ncolors;
1432 } else {
1433 result[pos] = migration_map[color_index] - 1;
1434 }
1435 for (n = 0; n < depth; ++n) {
1436 offset = data[pos * depth + n] - palette[color_index * depth + n];
1437 f_diffuse(data + n, width, height, x, y, depth, offset);
1438 }
1439 }
1440 }
1441 memcpy(palette, new_palette, (size_t)(*ncolors * depth));
1442 }
1443 } else {
1444 if (f_mask) {
1445 for (y = 0; y < height; ++y) {
1446 for (x = 0; x < width; ++x) {
1447 unsigned char copy[max_depth];
1448 int d;
1449 int val;
1450
1451 pos = y * width + x;
1452 for (d = 0; d < depth; d ++) {
1453 val = data[pos * depth + d] + f_mask(x, y, d) * 32;
1454 copy[d] = val < 0 ? 0 : val > 255 ? 255 : val;
1455 }
1456 result[pos] = f_lookup(copy, depth,
1457 palette, reqcolor, indextable, complexion);
1458 }
1459 }
1460 } else {
1461 for (y = 0; y < height; ++y) {
1462 for (x = 0; x < width; ++x) {
1463 pos = y * width + x;
1464 color_index = f_lookup(data + (pos * depth), depth,
1465 palette, reqcolor, indextable, complexion);
1466 result[pos] = color_index;
1467 for (n = 0; n < depth; ++n) {
1468 offset = data[pos * depth + n] - palette[color_index * depth + n];
1469 f_diffuse(data + n, width, height, x, y, depth, offset);
1470 }
1471 }
1472 }
1473 }
1474 *ncolors = reqcolor;
1475 }
1476
1477 if (cachetable == NULL) {
1478 sixel_allocator_free(allocator, indextable);
1479 }
1480
1481 status = SIXEL_OK;
1482
1483end:
1484 return status;
1485}
1486
1487
1488void
1489sixel_quant_free_palette(
1490 unsigned char /* in */ *data,
1491 sixel_allocator_t /* in */ *allocator)
1492{
1493 sixel_allocator_free(allocator, data);
1494}
1495
1496
1497#if HAVE_TESTS
1498static int
1499test1(void)
1500{
1501 int nret = EXIT_FAILURE;
1502 sample minval[1] = { 1 };
1503 sample maxval[1] = { 2 };
1504 unsigned int retval;
1505
1506 retval = largestByLuminosity(minval, maxval, 1);
1507 if (retval != 0) {
1508 goto error;
1509 }
1510 nret = EXIT_SUCCESS;
1511
1512error:
1513 return nret;
1514}
1515
1516
1517SIXELAPI int
1518sixel_quant_tests_main(void)
1519{
1520 int nret = EXIT_FAILURE;
1521 size_t i;
1522 typedef int (* testcase)(void);
1523
1524 static testcase const testcases[] = {
1525 test1,
1526 };
1527
1528 for (i = 0; i < sizeof(testcases) / sizeof(testcase); ++i) {
1529 nret = testcases[i]();
1530 if (nret != EXIT_SUCCESS) {
1531 goto error;
1532 }
1533 }
1534
1535 nret = EXIT_SUCCESS;
1536
1537error:
1538 return nret;
1539}
1540#endif /* HAVE_TESTS */
1541
1542/* emacs Local Variables: */
1543/* emacs mode: c */
1544/* emacs tab-width: 4 */
1545/* emacs indent-tabs-mode: nil */
1546/* emacs c-basic-offset: 4 */
1547/* emacs End: */
1548/* vim: set expandtab ts=4 sts=4 sw=4 : */
1549/* EOF */