quant.c

filter: Statementstmt 36.5% 234 / 641 Branchbran 26.7% 102 / 382 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 32.8% 336 / 1023 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« imext.c ↑ Summary context.c »
1 /* quant.c - provides general image quantization
2 currently only used by gif.c, but maybe we'll support producing
3 8-bit (or bigger indexed) png files at some point
4 */
5 #include "imager.h"
6 #include "imageri.h"
7  
8 static void makemap_webmap(i_quantize *);
9 static void makemap_addi(i_quantize *, i_img **imgs, int count);
10 static void makemap_mediancut(i_quantize *, i_img **imgs, int count);
11 static void makemap_mono(i_quantize *);
12 static void makemap_gray(i_quantize *, int step);
13  
14 static int makemap_palette(i_quantize *, i_img **imgs, int count);
15  
16 static
17 void
18 1140 setcol(i_color *cl,unsigned char r,unsigned char g,unsigned char b,unsigned char a) {
19 1140 cl->rgba.r=r;
20 1140 cl->rgba.g=g;
21 1140 cl->rgba.b=b;
22 1140 cl->rgba.a=a;
23 1140 }
24  
25  
26  
27 /* make a colour map overwrites mc_existing/mc_count in quant Note
28 that i_makemap will be called once for each image if mc_perimage is
29 set and the format support multiple colour maps per image.
30  
31 This means we don't need any special processing at this level to
32 handle multiple colour maps.
33 */
34  
35 /*
36 =item i_quant_makemap(C<quant>, C<imgs>, C<count>)
37  
38 =category Image quantization
39  
40 Analyzes the C<count> images in C<imgs> according to the rules in
41 C<quant> to build a color map (optimal or not depending on
42 C<< quant->make_colors >>).
43  
44 =cut
45 */
46  
47 void
48 22 i_quant_makemap(i_quantize *quant, i_img **imgs, int count) {
49  
50 22 ▶ if (quant->translate == pt_giflib) {
Branch: 1 branch
BranchTrueFalseTotal
if (quant->translate == pt_giflib) { 0 22 22
51 /* giflib does it's own color table generation */
52 /* previously we used giflib's quantizer, but it didn't handle multiple
53 images, which made it hard to build a global color map
54 We've implemented our own median cut code so we can ignore
55 the giflib version */
56 0 makemap_mediancut(quant, imgs, count);
57 0 return;
58 }
59  
60 22 switch (quant->make_colors & mc_mask) {
61 7 case mc_none:
62 /* use user's specified map */
63 7 break;
64 4 case mc_web_map:
65 4 makemap_webmap(quant);
66 4 break;
67  
68 5 case mc_median_cut:
69 5 makemap_mediancut(quant, imgs, count);
70 5 break;
71  
72 3 case mc_mono:
73 3 makemap_mono(quant);
74 3 break;
75  
76 1 case mc_gray:
77 1 makemap_gray(quant, 1);
78 1 break;
79  
80 1 case mc_gray4:
81 1 makemap_gray(quant, 85);
82 1 break;
83  
84 1 case mc_gray16:
85 1 makemap_gray(quant, 17);
86 1 break;
87  
88 0 case mc_addi:
89 default:
90 0 makemap_addi(quant, imgs, count);
91 0 break;
92 }
93 }
94  
95 static void translate_closest(i_quantize *, i_img *, i_palidx *);
96 static int translate_errdiff(i_quantize *, i_img *, i_palidx *);
97 static void translate_addi(i_quantize *, i_img *, i_palidx *);
98  
99 /*
100 =item i_quant_translate(C<quant>, C<img>)
101  
102 =category Image quantization
103  
104 Quantize the image given the palette in C<quant>.
105  
106 On success returns a pointer to a memory block of C<< img->xsize *
107 img->ysize >> C<i_palidx> entries.
108  
109 On failure returns NULL.
110  
111 You should call myfree() on the returned block when you're done with
112 it.
113  
114 This function will fail if the supplied palette contains no colors.
115  
116 =cut
117 */
118 i_palidx *
119 18 i_quant_translate(i_quantize *quant, i_img *img) {
120 i_palidx *result;
121 size_t bytes;
122  
123 18 mm_log((1, "quant_translate(quant %p, img %p)\n", quant, img));
124  
125 /* there must be at least one color in the paletted (though even that
126 isn't very useful */
127 18 ▶ if (quant->mc_count == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (quant->mc_count == 0) { 1 17 18
128 1 i_push_error(0, "no colors available for translation");
129 1 return NULL;
130 }
131  
132 17 bytes = (size_t)img->xsize * (size_t)img->ysize;
133 17 ▶ if (bytes / img->ysize != (size_t)img->xsize) {
Branch: 1 branch
BranchTrueFalseTotal
if (bytes / img->ysize != (size_t)img->xsize) { 0 17 17
134 0 i_push_error(0, "integer overflow calculating memory allocation");
135 0 return NULL;
136 }
137 17 result = mymalloc(bytes);
138  
139 17 switch (quant->translate) {
140 12 case pt_closest:
141 case pt_giflib:
142 12 translate_closest(quant, img, result);
143 12 break;
144
145 5 case pt_errdiff:
146 5 ▶ if (!translate_errdiff(quant, img, result)) {
Branch: 1 branch
BranchTrueFalseTotal
if (!translate_errdiff(quant, img, result)) { 0 5 5
147 0 myfree(result);
148 0 return NULL;
149 }
150 5 break;
151
152 0 case pt_perturb:
153 default:
154 0 translate_addi(quant, img, result);
155 0 break;
156 }
157
158 17 return result;
159 }
160  
161 12 static void translate_closest(i_quantize *quant, i_img *img, i_palidx *out) {
162 12 quant->perturb = 0;
163 12 translate_addi(quant, img, out);
164 12 }
165  
166 #define PWR2(x) ((x)*(x))
167  
168 typedef int (*cmpfunc)(const void*, const void*);
169  
170 typedef struct {
171 unsigned char r,g,b;
172 char fixed;
173 char used;
174 int dr,dg,db;
175 int cdist;
176 int mcount;
177 } cvec;
178  
179 typedef struct {
180 int cnt;
181 int vec[256];
182 } hashbox;
183  
184 typedef struct {
185 int boxnum;
186 int pixcnt;
187 int cand;
188 int pdc;
189 } pbox;
190  
191 static void prescan(i_img **im,int count, int cnum, cvec *clr, i_sample_t *line);
192 static void reorder(pbox prescan[512]);
193 static int pboxcmp(const pbox *a,const pbox *b);
194 static void boxcenter(int box,cvec *cv);
195 static float frandn(void);
196 static void boxrand(int box,cvec *cv);
197 static void bbox(int box,int *r0,int *r1,int *g0,int *g1,int *b0,int *b1);
198 static void cr_hashindex(cvec clr[256],int cnum,hashbox hb[512]);
199 static int mindist(int boxnum,cvec *cv);
200 static int maxdist(int boxnum,cvec *cv);
201  
202 /* Some of the simpler functions are kept here to aid the compiler -
203 maybe some of them will be inlined. */
204  
205 static int
206 296878 pixbox(i_color *ic) { return ((ic->channel[0] & 224)<<1)+ ((ic->channel[1]&224)>>2) + ((ic->channel[2] &224) >> 5); }
207  
208 static int
209 0 pixbox_ch(i_sample_t *chans) { return ((chans[0] & 224)<<1)+ ((chans[1]&224)>>2) + ((chans[2] &224) >> 5); }
210  
211 static unsigned char
212 270300 g_sat(int in) {
213 270300 ▶ if (in>255) { return 255; }
Branch: 1 branch
BranchTrueFalseTotal
if (in>255) { return 255; } 22380 247920 270300
214 247920 ▶ else if (in>0) return in;
Branch: 1 branch
BranchTrueFalseTotal
else if (in>0) return in; 43265 204655 247920
215 204655 return 0;
216 }
217  
218 static
219 float
220 0 frand(void) {
221 0 return rand()/(RAND_MAX+1.0);
222 }
223  
224 #ifdef NOTEF
225 static
226 int
227 eucl_d(cvec* cv,i_color *cl) { return PWR2(cv->r-cl->channel[0])+PWR2(cv->g-cl->channel[1])+PWR2(cv->b-cl->channel[2]); }
228 #endif
229  
230 static
231 int
232 0 eucl_d_ch(cvec* cv,i_sample_t *chans) {
233 0 return PWR2(cv->r - chans[0]) + PWR2(cv->g - chans[1])
234 0 + PWR2(cv->b - chans[2]);
235 }
236  
237 static int
238 2192846 ceucl_d(i_color *c1, i_color *c2) {
239 2192846 return PWR2(c1->channel[0]-c2->channel[0])
240 2192846 +PWR2(c1->channel[1]-c2->channel[1])
241 2192846 +PWR2(c1->channel[2]-c2->channel[2]);
242 }
243  
244 static const int
245 gray_samples[] = { 0, 0, 0 };
246  
247 /*
248  
249 This quantization algorithm and implementation routines are by Arnar
250 M. Hrafnkelson. In case any new ideas are here they are mine since
251 this was written from scratch.
252  
253 The algorithm uses local means in the following way:
254  
255 For each point in the colormap we find which image points
256 have that point as it's closest point. We calculate the mean
257 of those points and in the next iteration it will be the new
258 entry in the colormap.
259
260 In order to speed this process up (i.e. nearest neighbor problem) We
261 divied the r,g,b space up in equally large 512 boxes. The boxes are
262 numbered from 0 to 511. Their numbering is so that for a given vector
263 it is known that it belongs to the box who is formed by concatenating the
264 3 most significant bits from each component of the RGB triplet.
265  
266 For each box we find the list of points from the colormap who might be
267 closest to any given point within the box. The exact solution
268 involves finding the Voronoi map (or the dual the Delauny
269 triangulation) and has many issues including numerical stability.
270  
271 So we use this approximation:
272  
273 1. Find which point has the shortest maximum distance to the box.
274 2. Find all points that have a shorter minimum distance than that to the box
275  
276 This is a very simple task and is not computationally heavy if one
277 takes into account that the minimum distances from a pixel to a box is
278 always found by checking if it's inside the box or is closest to some
279 side or a corner. Finding the maximum distance is also either a side
280 or a corner.
281  
282 This approach results 2-3 times more than the actual points needed but
283 is still a good gain over the complete space. Usually when one has a
284 256 Colorcolor map a search over 30 is often obtained.
285  
286 A bit of an enhancement to this approach is to keep a seperate list
287 for each side of the cube, but this will require even more memory.
288  
289 Arnar M. Hrafnkelsson (addi@umich.edu);
290  
291 */
292 /*
293 Extracted from gifquant.c, removed dependencies on gif_lib,
294 and added support for multiple images.
295 starting from 1nov2000 by TonyC <tony@develop-help.com>.
296  
297 */
298  
299 static void
300 0 makemap_addi(i_quantize *quant, i_img **imgs, int count) {
301 cvec *clr;
302 0 int cnum, i, bst_idx=0, ld, cd, iter, currhb, img_num;
303 i_img_dim x, y;
304 i_sample_t *val;
305 float dlt;
306 hashbox *hb;
307 i_mempool mp;
308 0 i_img_dim maxwidth = 0;
309 i_sample_t *line;
310 const int *sample_indices;
311  
312 0 mm_log((1, "makemap_addi(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n",
313 quant, quant->mc_count, quant->mc_colors, imgs, count));
314  
315 0 ▶ if (makemap_palette(quant, imgs, count))
Branch: 1 branch
BranchTrueFalseTotal
if (makemap_palette(quant, imgs, count)) 0 0 0
316 0 return;
317
318 0 i_mempool_init(&mp);
319  
320 0 clr = i_mempool_alloc(&mp, sizeof(cvec) * quant->mc_size);
321 0 hb = i_mempool_alloc(&mp, sizeof(hashbox) * 512);
322 0 ▶ for (i=0; i < quant->mc_count; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i=0; i < quant->mc_count; ++i) { 0 0 0
323 0 clr[i].r = quant->mc_colors[i].rgb.r;
324 0 clr[i].g = quant->mc_colors[i].rgb.g;
325 0 clr[i].b = quant->mc_colors[i].rgb.b;
326 0 clr[i].fixed = 1;
327 0 clr[i].mcount = 0;
328 }
329 /* mymalloc doesn't clear memory, so I think we need this */
330 0 ▶ for (; i < quant->mc_size; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (; i < quant->mc_size; ++i) { 0 0 0
331 /*clr[i].r = clr[i].g = clr[i].b = 0;*/
332 0 clr[i].dr = 0;
333 0 clr[i].dg = 0;
334 0 clr[i].db = 0;
335 0 clr[i].fixed = 0;
336 0 clr[i].mcount = 0;
337 }
338 0 cnum = quant->mc_size;
339 0 dlt = 1;
340  
341 0 ▶ for (img_num = 0; img_num < count; ++img_num) {
Branch: 1 branch
BranchTrueFalseTotal
for (img_num = 0; img_num < count; ++img_num) { 0 0 0
342 0 ▶ if (imgs[img_num]->xsize > maxwidth)
Branch: 1 branch
BranchTrueFalseTotal
if (imgs[img_num]->xsize > maxwidth) 0 0 0
343 0 maxwidth = imgs[img_num]->xsize;
344 }
345 0 line = i_mempool_alloc(&mp, 3 * maxwidth * sizeof(*line));
346  
347 0 prescan(imgs, count, cnum, clr, line);
348 0 cr_hashindex(clr, cnum, hb);
349  
350 0 ▶ for(iter=0;iter<3;iter++) {
Branch: 1 branch
BranchTrueFalseTotal
for(iter=0;iter<3;iter++) { 0 0 0
351 0 ▶ for (img_num = 0; img_num < count; ++img_num) {
Branch: 1 branch
BranchTrueFalseTotal
for (img_num = 0; img_num < count; ++img_num) { 0 0 0
352 0 i_img *im = imgs[img_num];
353 0 ▶ sample_indices = im->channels >= 3 ? NULL : gray_samples;
Branch: 1 branch
BranchTrueFalseTotal
sample_indices = im->channels >= 3 ? NULL : gray_samples; 0 0 0
354 0 ▶ for(y=0;y<im->ysize;y++) {
Branch: 1 branch
BranchTrueFalseTotal
for(y=0;y<im->ysize;y++) { 0 0 0
355 0 i_gsamp(im, 0, im->xsize, y, line, sample_indices, 3);
356 0 val = line;
357 0 ▶ for(x=0;x<im->xsize;x++) {
Branch: 1 branch
BranchTrueFalseTotal
for(x=0;x<im->xsize;x++) { 0 0 0
358 0 ld=196608;
359 /*i_gpix(im,x,y,&val);*/
360 0 currhb=pixbox_ch(val);
361 /* printf("box = %d \n",currhb); */
362 0 ▶ for(i=0;i<hb[currhb].cnt;i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i=0;i<hb[currhb].cnt;i++) { 0 0 0
363 /* printf("comparing: pix (%d,%d,%d) vec (%d,%d,%d)\n",val.channel[0],val.channel[1],val.channel[2],clr[hb[currhb].vec[i]].r,clr[hb[currhb].vec[i]].g,clr[hb[currhb].vec[i]].b); */
364
365 0 cd=eucl_d_ch(&clr[hb[currhb].vec[i]],val);
366 0 ▶ if (cd<ld) {
Branch: 1 branch
BranchTrueFalseTotal
if (cd<ld) { 0 0 0
367 0 ld=cd; /* shortest distance yet */
368 0 bst_idx=hb[currhb].vec[i]; /* index of closest vector yet */
369 }
370 }
371
372 0 clr[bst_idx].mcount++;
373 0 clr[bst_idx].dr+=val[0];
374 0 clr[bst_idx].dg+=val[1];
375 0 clr[bst_idx].db+=val[2];
376
377 0 val += 3; /* next 3 samples (next pixel) */
378 }
379 }
380 }
381
382 0 ▶ for(i=0;i<cnum;i++)
Branch: 1 branch
BranchTrueFalseTotal
for(i=0;i<cnum;i++) 0 0 0
383 0 ▶ if (clr[i].mcount) {
Branch: 1 branch
BranchTrueFalseTotal
if (clr[i].mcount) { 0 0 0
384 0 clr[i].dr/=clr[i].mcount;
385 0 clr[i].dg/=clr[i].mcount;
386 0 clr[i].db/=clr[i].mcount;
387 }
388
389 /* for(i=0;i<cnum;i++) printf("vec(%d)=(%d,%d,%d) dest=(%d,%d,%d) matchcount=%d\n",
390 i,clr[i].r,clr[i].g,clr[i].b,clr[i].dr,clr[i].dg,clr[i].db,clr[i].mcount); */
391
392 /* printf("total error: %.2f\n",sqrt(accerr)); */
393
394 0 ▶ for(i=0;i<cnum;i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i=0;i<cnum;i++) { 0 0 0
395 0 ▶ if (clr[i].fixed) continue; /* skip reserved colors */
Branch: 1 branch
BranchTrueFalseTotal
if (clr[i].fixed) continue; /* skip reserved colors */ 0 0 0
396
397 0 ▶ if (clr[i].mcount) {
Branch: 1 branch
BranchTrueFalseTotal
if (clr[i].mcount) { 0 0 0
398 0 clr[i].used = 1;
399 0 clr[i].r=clr[i].r*(1-dlt)+dlt*clr[i].dr;
400 0 clr[i].g=clr[i].g*(1-dlt)+dlt*clr[i].dg;
401 0 clr[i].b=clr[i].b*(1-dlt)+dlt*clr[i].db;
402 } else {
403 /* let's try something else */
404 0 clr[i].used = 0;
405 /* the " & 0xFF" prevents "uncontrolled value" warnings from CodeQL */
406 0 clr[i].r = rand() & 0xFF;
407 0 clr[i].g = rand() & 0xFF;
408 0 clr[i].b = rand() & 0xFF;
409 }
410
411 0 clr[i].dr=0;
412 0 clr[i].dg=0;
413 0 clr[i].db=0;
414 0 clr[i].mcount=0;
415 }
416 0 cr_hashindex(clr,cnum,hb);
417 }
418  
419  
420 #ifdef NOTEF
421 for(i=0;i<cnum;i++) {
422 cd=eucl_d(&clr[i],&val);
423 if (cd<ld) {
424 ld=cd;
425 bst_idx=i;
426 }
427 }
428 #endif
429  
430 /* if defined, we only include colours with an mcount or that were
431 supplied in the fixed palette, giving us a smaller output palette */
432 #define ONLY_USE_USED
433 #ifdef ONLY_USE_USED
434 /* transfer the colors back */
435 0 quant->mc_count = 0;
436 0 ▶ for (i = 0; i < cnum; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < cnum; ++i) { 0 0 0
437 0 ▶ if (clr[i].fixed || clr[i].used) {
Branch: 2 branches
BranchTrueFalseTotal
if (clr[i].fixed || clr[i].used) { 0 0 0
if (clr[i].fixed || clr[i].used) { 0 0 0
438 /*printf("Adding %d (%d,%d,%d)\n", i, clr[i].r, clr[i].g, clr[i].b);*/
439 0 quant->mc_colors[quant->mc_count].rgb.r = clr[i].r;
440 0 quant->mc_colors[quant->mc_count].rgb.g = clr[i].g;
441 0 quant->mc_colors[quant->mc_count].rgb.b = clr[i].b;
442 0 ++quant->mc_count;
443 }
444 }
445 #else
446 /* transfer the colors back */
447 for (i = 0; i < cnum; ++i) {
448 quant->mc_colors[i].rgb.r = clr[i].r;
449 quant->mc_colors[i].rgb.g = clr[i].g;
450 quant->mc_colors[i].rgb.b = clr[i].b;
451 }
452 quant->mc_count = cnum;
453 #endif
454  
455 #if 0
456 mm_log((1, "makemap_addi returns - quant.mc_count = %d\n", quant->mc_count));
457 for (i = 0; i < quant->mc_count; ++i)
458 mm_log((5, " map entry %d: (%d, %d, %d)\n", i, clr[i].r, clr[i].g, clr[i].b));
459 #endif
460  
461 0 i_mempool_destroy(&mp);
462  
463 0 mm_log((1, "makemap_addi() - %d colors\n", quant->mc_count));
464 }
465  
466 typedef struct {
467 i_sample_t rgb[3];
468 i_img_dim count;
469 } quant_color_entry;
470  
471 #define MEDIAN_CUT_COLORS 32768
472  
473 #define MED_CUT_INDEX(c) ((((c).rgb.r & 0xF8) << 7) | \
474 (((c).rgb.g & 0xF8) << 2) | (((c).rgb.b & 0xF8) >> 3))
475  
476 #define MED_CUT_GRAY_INDEX(c) ((((c).rgb.r & 0xF8) << 7) | \
477 (((c).rgb.r & 0xF8) << 2) | (((c).rgb.r & 0xF8) >> 3))
478  
479 /* scale these to cover the whole range */
480 #define MED_CUT_RED(index) ((((index) & 0x7C00) >> 10) * 255 / 31)
481 #define MED_CUT_GREEN(index) ((((index) & 0x3E0) >> 5) * 255 / 31)
482 #define MED_CUT_BLUE(index) (((index) & 0x1F) * 255 / 31)
483  
484 typedef struct {
485 i_sample_t min[3]; /* minimum for each channel */
486 i_sample_t max[3]; /* maximum for each channel */
487 i_sample_t width[3]; /* width for each channel */
488 int start, size; /* beginning and size of the partition */
489 i_img_dim pixels; /* number of pixels represented by this partition */
490 } medcut_partition;
491  
492 /*
493 =item calc_part(part, colors)
494  
495 Calculates the new color limits for the given partition.
496  
497 Giflib assumes that the limits for the non-split channels stay the
498 same, but this strikes me as incorrect, especially if the colors tend
499 to be color ramps.
500  
501 Of course this could be optimized by not recalculating the channel we
502 just sorted on, but it's not worth the effort right now.
503  
504 =cut
505 */
506 0 static void calc_part(medcut_partition *part, quant_color_entry *colors) {
507 int i, ch;
508
509 0 ▶ for (ch = 0; ch < 3; ++ch) {
Branch: 1 branch
BranchTrueFalseTotal
for (ch = 0; ch < 3; ++ch) { 0 0 0
510 0 part->min[ch] = 255;
511 0 part->max[ch] = 0;
512 }
513 0 ▶ for (i = part->start; i < part->start + part->size; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = part->start; i < part->start + part->size; ++i) { 0 0 0
514 0 ▶ for (ch = 0; ch < 3; ++ch) {
Branch: 1 branch
BranchTrueFalseTotal
for (ch = 0; ch < 3; ++ch) { 0 0 0
515 0 ▶ if (part->min[ch] > colors[i].rgb[ch])
Branch: 1 branch
BranchTrueFalseTotal
if (part->min[ch] > colors[i].rgb[ch]) 0 0 0
516 0 part->min[ch] = colors[i].rgb[ch];
517 0 ▶ if (part->max[ch] < colors[i].rgb[ch])
Branch: 1 branch
BranchTrueFalseTotal
if (part->max[ch] < colors[i].rgb[ch]) 0 0 0
518 0 part->max[ch] = colors[i].rgb[ch];
519 }
520 }
521 0 ▶ for (ch = 0; ch < 3; ++ch) {
Branch: 1 branch
BranchTrueFalseTotal
for (ch = 0; ch < 3; ++ch) { 0 0 0
522 0 part->width[ch] = part->max[ch] - part->min[ch];
523 }
524 0 }
525  
526 /* simple functions to sort by each channel - we could use a global, but
527 that would be bad */
528  
529 static int
530 0 color_sort_red(void const *left, void const *right) {
531 0 return ((quant_color_entry *)left)->rgb[0] - ((quant_color_entry *)right)->rgb[0];
532 }
533  
534 static int
535 0 color_sort_green(void const *left, void const *right) {
536 0 return ((quant_color_entry *)left)->rgb[1] - ((quant_color_entry *)right)->rgb[1];
537 }
538  
539 static int
540 0 color_sort_blue(void const *left, void const *right) {
541 0 return ((quant_color_entry *)left)->rgb[2] - ((quant_color_entry *)right)->rgb[2];
542 }
543  
544 static int (*sorters[])(void const *, void const *) =
545 {
546 color_sort_red,
547 color_sort_green,
548 color_sort_blue,
549 };
550  
551 static void
552 5 makemap_mediancut(i_quantize *quant, i_img **imgs, int count) {
553 quant_color_entry *colors;
554 i_mempool mp;
555 int imgn, i, ch;
556 i_img_dim x, y, max_width;
557 i_color *line;
558 int color_count;
559 i_img_dim total_pixels;
560 medcut_partition *parts;
561 int part_num;
562 int in, out;
563 /* number of channels we search for the best channel to partition
564 this isn't terribly efficient, but it should work */
565 int chan_count;
566  
567 5 mm_log((1, "makemap_mediancut(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n",
568 quant, quant->mc_count, quant->mc_colors, imgs, count));
569  
570 5 ▶ if (makemap_palette(quant, imgs, count))
Branch: 1 branch
BranchTrueFalseTotal
if (makemap_palette(quant, imgs, count)) 0 5 5
571 0 return;
572  
573 5 i_mempool_init(&mp);
574  
575 5 colors = i_mempool_alloc(&mp, sizeof(*colors) * MEDIAN_CUT_COLORS);
576 163845 ▶ for (i = 0; i < MEDIAN_CUT_COLORS; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < MEDIAN_CUT_COLORS; ++i) { 163840 5 163845
577 163840 colors[i].rgb[0] = MED_CUT_RED(i);
578 163840 colors[i].rgb[1] = MED_CUT_GREEN(i);
579 163840 colors[i].rgb[2] = MED_CUT_BLUE(i);
580 163840 colors[i].count = 0;
581 }
582  
583 5 max_width = -1;
584 10 ▶ for (imgn = 0; imgn < count; ++imgn) {
Branch: 1 branch
BranchTrueFalseTotal
for (imgn = 0; imgn < count; ++imgn) { 5 5 10
585 5 ▶ if (imgs[imgn]->xsize > max_width)
Branch: 1 branch
BranchTrueFalseTotal
if (imgs[imgn]->xsize > max_width) 5 0 5
586 5 max_width = imgs[imgn]->xsize;
587 }
588 5 line = i_mempool_alloc(&mp, sizeof(i_color) * max_width);
589  
590 /* build the stats */
591 5 total_pixels = 0;
592 5 chan_count = 1; /* assume we just have grayscale */
593 10 ▶ for (imgn = 0; imgn < count; ++imgn) {
Branch: 1 branch
BranchTrueFalseTotal
for (imgn = 0; imgn < count; ++imgn) { 5 5 10
594 5 total_pixels += imgs[imgn]->xsize * imgs[imgn]->ysize;
595 452 ▶ for (y = 0; y < imgs[imgn]->ysize; ++y) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < imgs[imgn]->ysize; ++y) { 447 5 452
596 447 i_glin(imgs[imgn], 0, imgs[imgn]->xsize, y, line);
597 447 ▶ if (imgs[imgn]->channels > 2) {
Branch: 1 branch
BranchTrueFalseTotal
if (imgs[imgn]->channels > 2) { 447 0 447
598 447 chan_count = 3;
599 58121 ▶ for (x = 0; x < imgs[imgn]->xsize; ++x) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < imgs[imgn]->xsize; ++x) { 57674 447 58121
600 57674 ++colors[MED_CUT_INDEX(line[x])].count;
601 }
602 }
603 else {
604 /* a gray-scale image, just use the first channel */
605 0 ▶ for (x = 0; x < imgs[imgn]->xsize; ++x) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < imgs[imgn]->xsize; ++x) { 0 0 0
606 0 ++colors[MED_CUT_GRAY_INDEX(line[x])].count;
607 }
608 }
609 }
610 }
611  
612 /* eliminate the empty colors */
613 5 out = 0;
614 163845 ▶ for (in = 0; in < MEDIAN_CUT_COLORS; ++in) {
Branch: 1 branch
BranchTrueFalseTotal
for (in = 0; in < MEDIAN_CUT_COLORS; ++in) { 163840 5 163845
615 163840 ▶ if (colors[in].count) {
Branch: 1 branch
BranchTrueFalseTotal
if (colors[in].count) { 374 163466 163840
616 374 colors[out++] = colors[in];
617 }
618 }
619 /*printf("out %d\n", out);
620  
621 for (i = 0; i < out; ++i) {
622 if (colors[i].count) {
623 printf("%d: (%d,%d,%d) -> %d\n", i, colors[i].rgb[0], colors[i].rgb[1],
624 colors[i].rgb[2], colors[i].count);
625 }
626 }*/
627  
628 5 ▶ if (out < quant->mc_size) {
Branch: 1 branch
BranchTrueFalseTotal
if (out < quant->mc_size) { 5 0 5
629 /* just copy them into the color table */
630 379 ▶ for (i = 0; i < out; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < out; ++i) { 374 5 379
631 1496 ▶ for (ch = 0; ch < 3; ++ch) {
Branch: 1 branch
BranchTrueFalseTotal
for (ch = 0; ch < 3; ++ch) { 1122 374 1496
632 1122 quant->mc_colors[i].channel[ch] = colors[i].rgb[ch];
633 }
634 374 quant->mc_colors[i].rgba.a = 255;
635 }
636 5 quant->mc_count = out;
637 }
638 else {
639 /* build the starting partition */
640 0 parts = i_mempool_alloc(&mp, sizeof(*parts) * quant->mc_size);
641 0 parts[0].start = 0;
642 0 parts[0].size = out;
643 0 parts[0].pixels = total_pixels;
644 0 calc_part(parts, colors);
645 0 color_count = 1;
646
647 0 ▶ while (color_count < quant->mc_size) {
Branch: 1 branch
BranchTrueFalseTotal
while (color_count < quant->mc_size) { 0 0 0
648 /* initialized to avoid compiler warnings */
649 0 int max_index = 0, max_ch = 0; /* index/channel with biggest spread */
650 int max_size;
651 medcut_partition *workpart;
652 i_img_dim cum_total;
653 i_img_dim half;
654
655 /* find the partition with the most biggest span with more than
656 one color */
657 0 max_size = -1;
658 0 ▶ for (i = 0; i < color_count; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < color_count; ++i) { 0 0 0
659 0 ▶ for (ch = 0; ch < chan_count; ++ch) {
Branch: 1 branch
BranchTrueFalseTotal
for (ch = 0; ch < chan_count; ++ch) { 0 0 0
660 0 ▶ if (parts[i].width[ch] > max_size
Branch: 1 branch
BranchTrueFalseTotal
if (parts[i].width[ch] > max_size 0 0 0
661 0 ▶ && parts[i].size > 1) {
Branch: 1 branch
BranchTrueFalseTotal
&& parts[i].size > 1) { 0 0 0
662 0 max_index = i;
663 0 max_ch = ch;
664 0 max_size = parts[i].width[ch];
665 }
666 }
667 }
668
669 /* nothing else we can split */
670 0 ▶ if (max_size == -1)
Branch: 1 branch
BranchTrueFalseTotal
if (max_size == -1) 0 0 0
671 0 break;
672
673 0 workpart = parts+max_index;
674 /*printf("splitting partition %d (pixels %ld, start %d, size %d)\n", max_index, workpart->pixels, workpart->start, workpart->size);*/
675 0 qsort(colors + workpart->start, workpart->size, sizeof(*colors),
676 sorters[max_ch]);
677
678 /* find the median or something like it we need to make sure both
679 sides of the split have at least one color in them, so we don't
680 test at the first or last entry */
681 0 i = workpart->start;
682 0 cum_total = colors[i].count;
683 0 ++i;
684 0 half = workpart->pixels / 2;
685 0 while (i < workpart->start + workpart->size - 1
686 0 ▶ && cum_total < half) {
Branch: 2 branches
BranchTrueFalseTotal
&& cum_total < half) { 0 0 0
&& cum_total < half) { 0 0 0
687 0 cum_total += colors[i++].count;
688 }
689 /*printf("Split at %d to make %d (half %ld, cumtotal %ld)\n", i, color_count, half, cum_total);*/
690
691 /* found the spot to split */
692 0 parts[color_count].start = i;
693 0 parts[color_count].size = workpart->start + workpart->size - i;
694 0 workpart->size = i - workpart->start;
695 0 parts[color_count].pixels = workpart->pixels - cum_total;
696 0 workpart->pixels = cum_total;
697
698 /* recalculate the limits */
699 0 calc_part(workpart, colors);
700 0 calc_part(parts+color_count, colors);
701 0 ++color_count;
702 }
703
704 /* fill in the color table - since we could still have partitions
705 that have more than one color, we need to average the colors */
706 0 ▶ for (part_num = 0; part_num < color_count; ++part_num) {
Branch: 1 branch
BranchTrueFalseTotal
for (part_num = 0; part_num < color_count; ++part_num) { 0 0 0
707 double sums[3];
708 medcut_partition *workpart;
709
710 0 workpart = parts+part_num;
711 0 ▶ for (ch = 0; ch < 3; ++ch)
Branch: 1 branch
BranchTrueFalseTotal
for (ch = 0; ch < 3; ++ch) 0 0 0
712 0 sums[ch] = 0;
713
714 0 ▶ for (i = workpart->start; i < workpart->start + workpart->size; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = workpart->start; i < workpart->start + workpart->size; ++i) { 0 0 0
715 0 ▶ for (ch = 0; ch < 3; ++ch) {
Branch: 1 branch
BranchTrueFalseTotal
for (ch = 0; ch < 3; ++ch) { 0 0 0
716 0 sums[ch] += (int)(colors[i].rgb[ch]) * colors[i].count;
717 }
718 }
719 0 ▶ for (ch = 0; ch < 3; ++ch) {
Branch: 1 branch
BranchTrueFalseTotal
for (ch = 0; ch < 3; ++ch) { 0 0 0
720 0 quant->mc_colors[part_num].channel[ch] = sums[ch] / workpart->pixels;
721 }
722 0 quant->mc_colors[part_num].rgba.a = 255;
723 }
724 0 quant->mc_count = color_count;
725 }
726 /*printf("out %d colors\n", quant->mc_count);*/
727 5 i_mempool_destroy(&mp);
728  
729 5 mm_log((1, "makemap_mediancut() - %d colors\n", quant->mc_count));
730 }
731  
732 static void
733 3 makemap_mono(i_quantize *quant) {
734 3 quant->mc_colors[0].rgba.r = 0;
735 3 quant->mc_colors[0].rgba.g = 0;
736 3 quant->mc_colors[0].rgba.b = 0;
737 3 quant->mc_colors[0].rgba.a = 255;
738 3 quant->mc_colors[1].rgba.r = 255;
739 3 quant->mc_colors[1].rgba.g = 255;
740 3 quant->mc_colors[1].rgba.b = 255;
741 3 quant->mc_colors[1].rgba.a = 255;
742 3 quant->mc_count = 2;
743 3 }
744  
745 static void
746 3 makemap_gray(i_quantize *quant, int step) {
747 3 int gray = 0;
748 3 int i = 0;
749  
750 279 ▶ while (gray < 256) {
Branch: 1 branch
BranchTrueFalseTotal
while (gray < 256) { 276 3 279
751 276 setcol(quant->mc_colors+i, gray, gray, gray, 255);
752 276 ++i;
753 276 gray += step;
754 }
755 3 quant->mc_count = i;
756 3 }
757  
758 static void
759 4 makemap_webmap(i_quantize *quant) {
760 int r, g, b;
761  
762 4 int i = 0;
763 28 ▶ for (r = 0; r < 256; r+=0x33)
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r < 256; r+=0x33) 24 4 28
764 168 ▶ for (g = 0; g < 256; g+=0x33)
Branch: 1 branch
BranchTrueFalseTotal
for (g = 0; g < 256; g+=0x33) 144 24 168
765 1008 ▶ for (b = 0; b < 256; b += 0x33)
Branch: 1 branch
BranchTrueFalseTotal
for (b = 0; b < 256; b += 0x33) 864 144 1008
766 864 setcol(quant->mc_colors+i++, r, g, b, 255);
767 4 quant->mc_count = i;
768 4 }
769  
770 static int
771 0 in_palette(i_color *c, i_quantize *quant, int size) {
772 int i;
773  
774 0 ▶ for (i = 0; i < size; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < size; ++i) { 0 0 0
775 0 ▶ if (c->channel[0] == quant->mc_colors[i].channel[0]
Branch: 1 branch
BranchTrueFalseTotal
if (c->channel[0] == quant->mc_colors[i].channel[0] 0 0 0
776 0 ▶ && c->channel[1] == quant->mc_colors[i].channel[1]
Branch: 1 branch
BranchTrueFalseTotal
&& c->channel[1] == quant->mc_colors[i].channel[1] 0 0 0
777 0 ▶ && c->channel[2] == quant->mc_colors[i].channel[2]) {
Branch: 1 branch
BranchTrueFalseTotal
&& c->channel[2] == quant->mc_colors[i].channel[2]) { 0 0 0
778 0 return i;
779 }
780 }
781  
782 0 return -1;
783 }
784  
785 /*
786 =item makemap_palette(quant, imgs, count)
787  
788 Tests if all the given images are paletted and have a common palette,
789 if they do it builds that palette.
790  
791 A possible improvement might be to eliminate unused colors in the
792 images palettes.
793  
794 =cut
795 */
796  
797 static int
798 5 makemap_palette(i_quantize *quant, i_img **imgs, int count) {
799 5 int size = quant->mc_count;
800 int i;
801 int imgn;
802 char used[256];
803 int col_count;
804  
805 5 mm_log((1, "makemap_palette(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n",
806 quant, quant->mc_count, quant->mc_colors, imgs, count));
807 /* we try to build a common palette here, if we can manage that, then
808 that's the palette we use */
809 5 ▶ for (imgn = 0; imgn < count; ++imgn) {
Branch: 1 branch
BranchTrueFalseTotal
for (imgn = 0; imgn < count; ++imgn) { 5 0 5
810 int eliminate_unused;
811 5 ▶ if (imgs[imgn]->type != i_palette_type) {
Branch: 1 branch
BranchTrueFalseTotal
if (imgs[imgn]->type != i_palette_type) { 5 0 5
812 5 mm_log((1, "makemap_palette() -> 0 (non-palette image)\n"));
813 5 return 0;
814 }
815  
816 0 ▶ if (!i_tags_get_int(&imgs[imgn]->tags, "gif_eliminate_unused", 0,
Branch: 1 branch
BranchTrueFalseTotal
if (!i_tags_get_int(&imgs[imgn]->tags, "gif_eliminate_unused", 0, 0 0 0
817 &eliminate_unused)) {
818 0 eliminate_unused = 1;
819 }
820  
821 0 ▶ if (eliminate_unused) {
Branch: 1 branch
BranchTrueFalseTotal
if (eliminate_unused) { 0 0 0
822 0 i_palidx *line = mymalloc(sizeof(i_palidx) * imgs[imgn]->xsize);
823 i_img_dim x, y;
824 0 memset(used, 0, sizeof(used));
825  
826 0 ▶ for (y = 0; y < imgs[imgn]->ysize; ++y) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < imgs[imgn]->ysize; ++y) { 0 0 0
827 0 ▶ i_gpal(imgs[imgn], 0, imgs[imgn]->xsize, y, line);
Branch: 1 branch
BranchTrueFalseTotal
i_gpal(imgs[imgn], 0, imgs[imgn]->xsize, y, line); 0 0 0
828 0 ▶ for (x = 0; x < imgs[imgn]->xsize; ++x)
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < imgs[imgn]->xsize; ++x) 0 0 0
829 0 used[line[x]] = 1;
830 }
831  
832 0 myfree(line);
833 }
834 else {
835 /* assume all are in use */
836 0 memset(used, 1, sizeof(used));
837 }
838  
839 0 ▶ col_count = i_colorcount(imgs[imgn]);
Branch: 1 branch
BranchTrueFalseTotal
col_count = i_colorcount(imgs[imgn]); 0 0 0
840 0 ▶ for (i = 0; i < col_count; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < col_count; ++i) { 0 0 0
841 i_color c;
842
843 0 ▶ i_getcolors(imgs[imgn], i, &c, 1);
Branch: 1 branch
BranchTrueFalseTotal
i_getcolors(imgs[imgn], i, &c, 1); 0 0 0
844 0 ▶ if (used[i]) {
Branch: 1 branch
BranchTrueFalseTotal
if (used[i]) { 0 0 0
845 0 ▶ if (in_palette(&c, quant, size) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (in_palette(&c, quant, size) < 0) { 0 0 0
846 0 ▶ if (size < quant->mc_size) {
Branch: 1 branch
BranchTrueFalseTotal
if (size < quant->mc_size) { 0 0 0
847 0 quant->mc_colors[size++] = c;
848 }
849 else {
850 0 mm_log((1, "makemap_palette() -> 0 (too many colors)\n"));
851 0 return 0;
852 }
853 }
854 }
855 }
856 }
857  
858 0 mm_log((1, "makemap_palette() -> 1 (%d total colors)\n", size));
859 0 quant->mc_count = size;
860  
861 0 return 1;
862 }
863  
864 #define pboxjump 32
865  
866 /* Define one of the following 4 symbols to choose a colour search method
867 The idea is to try these out, including benchmarking, to see which
868 is fastest in a good spread of circumstances.
869 I'd expect IM_CFLINSEARCH to be fastest for very small palettes, and
870 IM_CFHASHBOX for large images with large palettes.
871  
872 Some other possibilities include:
873 - search over entries sorted by luminance
874  
875 Initially I was planning on testing using the macros and then
876 integrating the code directly into each function, but this means if
877 we find a bug at a late stage we will need to update N copies of
878 the same code. Also, keeping the code in the macros means that the
879 code in the translation functions is much more to the point,
880 there's no distracting colour search code to remove attention from
881 what makes _this_ translation function different. It may be
882 advisable to move the setup code into functions at some point, but
883 it should be possible to do this fairly transparently.
884  
885 If IM_CF_COPTS is defined then CFLAGS must have an appropriate
886 definition.
887  
888 Each option needs to define 4 macros:
889 CF_VARS - variables to define in the function
890 CF_SETUP - code to setup for the colour search, eg. allocating and
891 initializing lookup tables
892 CF_FIND - code that looks for the color in val and puts the best
893 matching index in bst_idx
894 CF_CLEANUP - code to clean up, eg. releasing memory
895 */
896 #ifndef IM_CF_COPTS
897 /*#define IM_CFLINSEARCH*/
898 #define IM_CFHASHBOX
899 /*#define IM_CFSORTCHAN*/
900 /*#define IM_CFRAND2DIST*/
901 #endif
902  
903 /* return true if the color map contains only grays */
904 static int
905 5 is_gray_map(const i_quantize *quant) {
906 int i;
907  
908 11 ▶ for (i = 0; i < quant->mc_count; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < quant->mc_count; ++i) { 10 1 11
909 10 ▶ if (quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.g
Branch: 1 branch
BranchTrueFalseTotal
if (quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.g 8 2 10
910 8 ▶ || quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.b) {
Branch: 1 branch
BranchTrueFalseTotal
|| quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.b) { 2 6 8
911 4 mm_log((1, " not a gray map\n"));
912 4 return 0;
913 }
914 }
915  
916 1 mm_log((1, " is a gray map\n"));
917 1 return 1;
918 }
919  
920 #ifdef IM_CFHASHBOX
921  
922 /* The original version I wrote for this used the sort.
923 If this is defined then we use a sort to extract the indices for
924 the hashbox */
925 #define HB_SORT
926  
927 /* assume i is available */
928 #define CF_VARS hashbox *hb = mymalloc(sizeof(hashbox) * 512); \
929 int currhb; \
930 long ld, cd
931  
932 #ifdef HB_SORT
933  
934 static long *gdists; /* qsort is annoying */
935 /* int might be smaller than long, so we need to do a real compare
936 rather than a subtraction*/
937 3787328 static int distcomp(void const *a, void const *b) {
938 3787328 long ra = gdists[*(int const *)a];
939 3787328 long rb = gdists[*(int const *)b];
940 3787328 ▶ if (ra < rb)
Branch: 1 branch
BranchTrueFalseTotal
if (ra < rb) 1740270 2047058 3787328
941 1740270 return -1;
942 2047058 ▶ else if (ra > rb)
Branch: 1 branch
BranchTrueFalseTotal
else if (ra > rb) 1944402 102656 2047058
943 1944402 return 1;
944 else
945 102656 return 0;
946 }
947  
948 #endif
949  
950 /* for each hashbox build a list of colours that are in the hb or is closer
951 than other colours
952 This is pretty involved. The original gifquant generated the hashbox
953 as part of it's normal processing, but since the map generation is now
954 separated from the translation we need to do this on the spot.
955 Any optimizations, even if they don't produce perfect results would be
956 welcome.
957 */
958 17 static void hbsetup(i_quantize *quant, hashbox *hb) {
959 long *dists, mind, maxd;
960 int cr, cb, cg, hbnum, i;
961 i_color cenc;
962 #ifdef HB_SORT
963 17 int *indices = mymalloc(quant->mc_count * sizeof(int));
964 #endif
965  
966 17 dists = mymalloc(quant->mc_count * sizeof(long));
967 153 ▶ for (cr = 0; cr < 8; ++cr) {
Branch: 1 branch
BranchTrueFalseTotal
for (cr = 0; cr < 8; ++cr) { 136 17 153
968 1224 ▶ for (cg = 0; cg < 8; ++cg) {
Branch: 1 branch
BranchTrueFalseTotal
for (cg = 0; cg < 8; ++cg) { 1088 136 1224
969 9792 ▶ for (cb = 0; cb < 8; ++cb) {
Branch: 1 branch
BranchTrueFalseTotal
for (cb = 0; cb < 8; ++cb) { 8704 1088 9792
970 /* centre of the hashbox */
971 8704 cenc.channel[0] = cr*pboxjump+pboxjump/2;
972 8704 cenc.channel[1] = cg*pboxjump+pboxjump/2;
973 8704 cenc.channel[2] = cb*pboxjump+pboxjump/2;
974 8704 hbnum = pixbox(&cenc);
975 8704 hb[hbnum].cnt = 0;
976 /* order indices in the order of distance from the hashbox */
977 662528 ▶ for (i = 0; i < quant->mc_count; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < quant->mc_count; ++i) { 653824 8704 662528
978 #ifdef HB_SORT
979 653824 indices[i] = i;
980 #endif
981 653824 dists[i] = ceucl_d(&cenc, quant->mc_colors+i);
982 }
983 #ifdef HB_SORT
984 /* it should be possible to do this without a sort
985 but so far I'm too lazy */
986 8704 gdists = dists;
987 8704 qsort(indices, quant->mc_count, sizeof(int), distcomp);
988 /* any colors that can match are within mind+diagonal size of
989 a hashbox */
990 8704 mind = dists[indices[0]];
991 8704 i = 0;
992 8704 maxd = (sqrt(mind)+pboxjump)*(sqrt(mind)+pboxjump);
993 50213 ▶ while (i < quant->mc_count && dists[indices[i]] < maxd) {
Branch: 2 branches
BranchTrueFalseTotal
while (i < quant->mc_count && dists[indices[i]] < maxd) { 49753 460 50213
while (i < quant->mc_count && dists[indices[i]] < maxd) { 41509 8244 49753
994 41509 hb[hbnum].vec[hb[hbnum].cnt++] = indices[i++];
995 }
996 #else
997 /* work out the minimum */
998 mind = 256*256*3;
999 for (i = 0; i < quant->mc_count; ++i) {
1000 if (dists[i] < mind) mind = dists[i];
1001 }
1002 /* transfer any colours that might be closest to a colour in
1003 this hashbox */
1004 maxd = (sqrt(mind)+pboxjump)*(sqrt(mind)+pboxjump);
1005 for (i = 0; i < quant->mc_count; ++i) {
1006 if (dists[i] < maxd)
1007 hb[hbnum].vec[hb[hbnum].cnt++] = i;
1008 }
1009 #endif
1010 }
1011 }
1012 }
1013 #ifdef HB_SORT
1014 17 myfree(indices);
1015 #endif
1016 17 myfree(dists) ;
1017 17 }
1018 #define CF_SETUP hbsetup(quant, hb)
1019  
1020 #define CF_FIND \
1021 currhb = pixbox(&val); \
1022 ld = 196608; \
1023 for (i = 0; i < hb[currhb].cnt; ++i) { \
1024 cd = ceucl_d(quant->mc_colors+hb[currhb].vec[i], &val); \
1025 if (cd < ld) { ld = cd; bst_idx = hb[currhb].vec[i]; } \
1026 }
1027  
1028 #define CF_CLEANUP myfree(hb)
1029
1030 #endif
1031  
1032 #ifdef IM_CFLINSEARCH
1033 /* as simple as it gets */
1034 #define CF_VARS long ld, cd
1035 #define CF_SETUP /* none needed */
1036 #define CF_FIND \
1037 ld = 196608; \
1038 for (i = 0; i < quant->mc_count; ++i) { \
1039 cd = ceucl_d(quant->mc_colors+i, &val); \
1040 if (cd < ld) { ld = cd; bst_idx = i; } \
1041 }
1042 #define CF_CLEANUP
1043 #endif
1044  
1045 #ifdef IM_CFSORTCHAN
1046 static int gsortchan;
1047 static i_quantize *gquant;
1048 static int chansort(void const *a, void const *b) {
1049 return gquant->mc_colors[*(int const *)a].channel[gsortchan] -
1050 gquant->mc_colors[*(int const *)b].channel[gsortchan];
1051 }
1052 #define CF_VARS int *indices, sortchan, diff; \
1053 long ld, cd; \
1054 int vindex[256] /* where to find value i of chan */
1055  
1056 static void chansetup(i_img *img, i_quantize *quant, int *csortchan,
1057 int *vindex, int **cindices) {
1058 int *indices, sortchan, chan, i, chval;
1059 int chanmins[MAXCHANNELS], chanmaxs[MAXCHANNELS], maxrange;
1060  
1061 /* find the channel with the maximum range */
1062 /* the maximum stddev would probably be better */
1063 for (chan = 0; chan < img->channels; ++chan) {
1064 chanmins[chan] = 256; chanmaxs[chan] = 0;
1065 for (i = 0; i < quant->mc_count; ++i) {
1066 if (quant->mc_colors[i].channel[chan] < chanmins[chan])
1067 chanmins[chan] = quant->mc_colors[i].channel[chan];
1068 if (quant->mc_colors[i].channel[chan] > chanmaxs[chan])
1069 chanmaxs[chan] = quant->mc_colors[i].channel[chan];
1070 }
1071 }
1072 maxrange = -1;
1073 for (chan = 0; chan < img->channels; ++chan) {
1074 if (chanmaxs[chan]-chanmins[chan] > maxrange) {
1075 maxrange = chanmaxs[chan]-chanmins[chan];
1076 sortchan = chan;
1077 }
1078 }
1079 indices = mymalloc(quant->mc_count * sizeof(int)) ;
1080 for (i = 0; i < quant->mc_count; ++i) {
1081 indices[i] = i;
1082 }
1083 gsortchan = sortchan;
1084 gquant = quant;
1085 qsort(indices, quant->mc_count, sizeof(int), chansort) ;
1086 /* now a lookup table to find entries faster */
1087 for (chval=0, i=0; i < quant->mc_count; ++i) {
1088 while (chval < 256 &&
1089 chval < quant->mc_colors[indices[i]].channel[sortchan]) {
1090 vindex[chval++] = i;
1091 }
1092 }
1093 while (chval < 256) {
1094 vindex[chval++] = quant->mc_count-1;
1095 }
1096 *csortchan = sortchan;
1097 *cindices = indices;
1098 }
1099  
1100 #define CF_SETUP \
1101 chansetup(img, quant, &sortchan, vindex, &indices)
1102  
1103 int chanfind(i_color val, i_quantize *quant, int *indices, int *vindex,
1104 int sortchan) {
1105 int i, bst_idx, diff, maxdiff;
1106 long ld, cd;
1107  
1108 i = vindex[val.channel[sortchan]];
1109 bst_idx = indices[i];
1110 ld = 196608;
1111 diff = 0;
1112 maxdiff = quant->mc_count;
1113 while (diff < maxdiff) {
1114 if (i+diff < quant->mc_count) {
1115 cd = ceucl_d(&val, quant->mc_colors+indices[i+diff]);
1116 if (cd < ld) {
1117 bst_idx = indices[i+diff];
1118 ld = cd;
1119 maxdiff = sqrt(ld);
1120 }
1121 }
1122 if (i-diff >= 0) {
1123 cd = ceucl_d(&val, quant->mc_colors+indices[i-diff]);
1124 if (cd < ld) {
1125 bst_idx = indices[i-diff];
1126 ld = cd;
1127 maxdiff = sqrt(ld);
1128 }
1129 }
1130 ++diff;
1131 }
1132  
1133 return bst_idx;
1134 }
1135  
1136 #define CF_FIND \
1137 bst_idx = chanfind(val, quant, indices, vindex, sortchan)
1138
1139  
1140 #define CF_CLEANUP myfree(indices)
1141  
1142 #endif
1143  
1144 #ifdef IM_CFRAND2DIST
1145  
1146 /* This is based on a method described by Addi in the #imager channel
1147 on the 28/2/2001. I was about 1am Sydney time at the time, so I
1148 wasn't at my most cogent. Well, that's my excuse :)
1149  
1150 <TonyC> what I have at the moment is: hashboxes, with optimum hash box
1151 filling; simple linear search; and a lookup in the widest channel
1152 (currently the channel with the maximum range)
1153 <Addi> There is one more way that might be simple to implement.
1154 <Addi> You want to hear?
1155 <TonyC> what's that?
1156 <purl> somebody said that was not true
1157 <Addi> For each of the colors in the palette start by creating a
1158 sorted list of the form:
1159 <Addi> [distance, color]
1160 <Addi> Where they are sorted by distance.
1161 <TonyC> distance to where?
1162 <Addi> Where the elements in the lists are the distances and colors of
1163 the other colors in the palette
1164 <TonyC> ok
1165 <Addi> So if you are at color 0
1166 <Addi> ok - now to search for the closest color when you are creating
1167 the final image is done like this:
1168 <Addi> a) pick a random color from the palette
1169 <Addi> b) calculate the distance to it
1170 <Addi> c) only check the vectors that are within double the distance
1171 in the list of the color you picked from the palette.
1172 <Addi> Does that seem logical?
1173 <Addi> Lets imagine that we only have grayscale to make an example:
1174 <Addi> Our palette has 1 4 10 20 as colors.
1175 <Addi> And we want to quantize the color 11
1176 <Addi> lets say we picked 10 randomly
1177 <Addi> the double distance is 2
1178 <Addi> since abs(10-11)*2 is 2
1179 <Addi> And the list at vector 10 is this:
1180 <Addi> [0, 10], [6 4], [9, 1], [10, 20]
1181 <Addi> so we look at the first one (but not the second one since 6 is
1182 at a greater distance than 2.
1183 <Addi> Any of that make sense?
1184 <TonyC> yes, though are you suggesting another random jump to one of
1185 the colours with the possible choices? or an exhaustive search?
1186 <Addi> TonyC: It's possible to come up with a recursive/iterative
1187 enhancement but this is the 'basic' version.
1188 <Addi> Which would do an iterative search.
1189 <Addi> You can come up with conditions where it pays to switch to a new one.
1190 <Addi> And the 'random' start can be switched over to a small tree.
1191 <Addi> So you would have a little index at the start.
1192 <Addi> to get you into the general direction
1193 <Addi> Perhaps just an 8 split.
1194 <Addi> that is - split each dimension in half.
1195 <TonyC> yep
1196 <TonyC> I get the idea
1197 <Addi> But this would seem to be a good approach in our case since we
1198 usually have few codevectors.
1199 <Addi> So we only need 256*256 entries in a table.
1200 <Addi> We could even only index some of them that were deemed as good
1201 candidates.
1202 <TonyC> I was considering adding paletted output support for PNG and
1203 TIFF at some point, which support 16-bit palettes
1204 <Addi> ohh.
1205 <Addi> 'darn' ;)
1206  
1207  
1208 */
1209  
1210  
1211 typedef struct i_dists {
1212 int index;
1213 long dist;
1214 } i_dists;
1215  
1216 #define CF_VARS \
1217 i_dists *dists;
1218  
1219 static int dists_sort(void const *a, void const *b) {
1220 return ((i_dists *)a)->dist - ((i_dists *)b)->dist;
1221 }
1222  
1223 static void rand2dist_setup(i_quantize *quant, i_dists **cdists) {
1224 i_dists *dists =
1225 mymalloc(sizeof(i_dists)*quant->mc_count*quant->mc_count);
1226 int i, j;
1227 long cd;
1228 for (i = 0; i < quant->mc_count; ++i) {
1229 i_dists *ldists = dists + quant->mc_count * i;
1230 i_color val = quant->mc_colors[i];
1231 for (j = 0; j < quant->mc_count; ++j) {
1232 ldists[j].index = j;
1233 ldists[j].dist = ceucl_d(&val, quant->mc_colors+j);
1234 }
1235 qsort(ldists, quant->mc_count, sizeof(i_dists), dists_sort);
1236 }
1237 *cdists = dists;
1238 }
1239  
1240 #define CF_SETUP \
1241 bst_idx = rand() % quant->mc_count; \
1242 rand2dist_setup(quant, &dists)
1243  
1244 static int rand2dist_find(i_color val, i_quantize *quant, i_dists *dists, int index) {
1245 i_dists *cdists;
1246 long cd, ld;
1247 long maxld;
1248 int i;
1249 int bst_idx;
1250  
1251 cdists = dists + index * quant->mc_count;
1252 ld = 3 * 256 * 256;
1253 maxld = 8 * ceucl_d(&val, quant->mc_colors+index);
1254 for (i = 0; i < quant->mc_count && cdists[i].dist <= maxld; ++i) {
1255 cd = ceucl_d(&val, quant->mc_colors+cdists[i].index);
1256 if (cd < ld) {
1257 bst_idx = cdists[i].index;
1258 ld = cd;
1259 }
1260 }
1261 return bst_idx;
1262 }
1263  
1264 #define CF_FIND bst_idx = rand2dist_find(val, quant, dists, bst_idx)
1265  
1266 #define CF_CLEANUP myfree(dists)
1267  
1268  
1269 #endif
1270  
1271 12 static void translate_addi(i_quantize *quant, i_img *img, i_palidx *out) {
1272 i_img_dim x, y, k;
1273 12 int i, bst_idx = 0;
1274 i_color val;
1275 12 int pixdev = quant->perturb;
1276 12 CF_VARS;
1277  
1278 12 CF_SETUP;
1279  
1280 12 ▶ if (img->channels >= 3) {
Branch: 1 branch
BranchTrueFalseTotal
if (img->channels >= 3) { 12 0 12
1281 12 ▶ if (pixdev) {
Branch: 1 branch
BranchTrueFalseTotal
if (pixdev) { 0 12 12
1282 0 k=0;
1283 0 ▶ for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) {
Branch: 2 branches
BranchTrueFalseTotal
for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { 0 0 0
for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { 0 0 0
1284 0 i_gpix(img,x,y,&val);
1285 0 val.channel[0]=g_sat(val.channel[0]+(int)(pixdev*frandn()));
1286 0 val.channel[1]=g_sat(val.channel[1]+(int)(pixdev*frandn()));
1287 0 val.channel[2]=g_sat(val.channel[2]+(int)(pixdev*frandn()));
1288 0 ▶ CF_FIND;
Branch: 2 branches
BranchTrueFalseTotal
CF_FIND; 0 0 0
CF_FIND; 0 0 0
1289 0 out[k++]=bst_idx;
1290 }
1291 } else {
1292 12 k=0;
1293 199445 ▶ for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) {
Branch: 2 branches
BranchTrueFalseTotal
for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { 198074 1359 199433
for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { 1359 12 1371
1294 198074 i_gpix(img,x,y,&val);
1295 1357746 ▶ CF_FIND;
Branch: 2 branches
BranchTrueFalseTotal
CF_FIND; 317121 842551 1159672
CF_FIND; 1159672 198074 1357746
1296 198074 out[k++]=bst_idx;
1297 }
1298 }
1299 }
1300 else {
1301 0 ▶ if (pixdev) {
Branch: 1 branch
BranchTrueFalseTotal
if (pixdev) { 0 0 0
1302 0 k=0;
1303 0 ▶ for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) {
Branch: 2 branches
BranchTrueFalseTotal
for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { 0 0 0
for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { 0 0 0
1304 0 i_gpix(img,x,y,&val);
1305 0 val.channel[1] = val.channel[2] =
1306 0 val.channel[0]=g_sat(val.channel[0]+(int)(pixdev*frandn()));
1307 0 ▶ CF_FIND;
Branch: 2 branches
BranchTrueFalseTotal
CF_FIND; 0 0 0
CF_FIND; 0 0 0
1308 0 out[k++]=bst_idx;
1309 }
1310 } else {
1311 0 k=0;
1312 0 ▶ for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) {
Branch: 2 branches
BranchTrueFalseTotal
for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { 0 0 0
for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) { 0 0 0
1313 0 i_gpix(img,x,y,&val);
1314 0 val.channel[1] = val.channel[2] = val.channel[0];
1315 0 ▶ CF_FIND;
Branch: 2 branches
BranchTrueFalseTotal
CF_FIND; 0 0 0
CF_FIND; 0 0 0
1316 0 out[k++]=bst_idx;
1317 }
1318 }
1319 }
1320 12 CF_CLEANUP;
1321 12 }
1322  
1323 static int floyd_map[] =
1324 {
1325 0, 0, 7,
1326 3, 5, 1
1327 };
1328  
1329 static int jarvis_map[] =
1330 {
1331 0, 0, 0, 7, 5,
1332 3, 5, 7, 5, 3,
1333 1, 3, 5, 3, 1
1334 };
1335  
1336 static int stucki_map[] =
1337 {
1338 0, 0, 0, 8, 4,
1339 2, 4, 8, 4, 2,
1340 1, 2, 4, 2, 1
1341 };
1342  
1343 struct errdiff_map {
1344 int *map;
1345 int width, height, orig;
1346 };
1347  
1348 static struct errdiff_map maps[] =
1349 {
1350 { floyd_map, 3, 2, 1 },
1351 { jarvis_map, 5, 3, 2 },
1352 { stucki_map, 5, 3, 2 },
1353 };
1354  
1355 typedef struct errdiff_tag {
1356 int r, g, b;
1357 } errdiff_t;
1358  
1359 /* perform an error diffusion dither */
1360 static int
1361 5 translate_errdiff(i_quantize *quant, i_img *img, i_palidx *out) {
1362 int *map;
1363 int mapw, maph, mapo;
1364 int i;
1365 errdiff_t *err;
1366 i_img_dim errw;
1367 int difftotal;
1368 i_img_dim x, y, dx, dy;
1369 5 int bst_idx = 0;
1370 5 int is_gray = is_gray_map(quant);
1371 5 CF_VARS;
1372  
1373 5 ▶ if ((quant->errdiff & ed_mask) == ed_custom) {
Branch: 1 branch
BranchTrueFalseTotal
if ((quant->errdiff & ed_mask) == ed_custom) { 0 5 5
1374 0 map = quant->ed_map;
1375 0 mapw = quant->ed_width;
1376 0 maph = quant->ed_height;
1377 0 mapo = quant->ed_orig;
1378 }
1379 else {
1380 5 int index = quant->errdiff & ed_mask;
1381 5 ▶ if (index >= ed_custom) index = ed_floyd;
Branch: 1 branch
BranchTrueFalseTotal
if (index >= ed_custom) index = ed_floyd; 0 5 5
1382 5 map = maps[index].map;
1383 5 mapw = maps[index].width;
1384 5 maph = maps[index].height;
1385 5 mapo = maps[index].orig;
1386 }
1387
1388 5 difftotal = 0;
1389 35 ▶ for (i = 0; i < maph * mapw; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < maph * mapw; ++i) { 30 5 35
1390 30 ▶ if (map[i] < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (map[i] < 0) { 0 30 30
1391 0 i_push_errorf(0, "errdiff_map values must be non-negative, errdiff[%d] is negative", i);
1392 0 goto fail;
1393 }
1394 30 difftotal += map[i];
1395 }
1396  
1397 5 ▶ if (!difftotal) {
Branch: 1 branch
BranchTrueFalseTotal
if (!difftotal) { 0 5 5
1398 0 i_push_error(0, "error diffusion map must contain some non-zero values");
1399 0 goto fail;
1400 }
1401  
1402 5 errw = img->xsize+mapw;
1403 5 err = mymalloc(sizeof(*err) * maph * errw);
1404 /*errp = err+mapo;*/
1405 5 memset(err, 0, sizeof(*err) * maph * errw);
1406
1407 /*printf("map:\n");
1408 for (dy = 0; dy < maph; ++dy) {
1409 for (dx = 0; dx < mapw; ++dx) {
1410 printf("%2d", map[dx+dy*mapw]);
1411 }
1412 putchar('\n');
1413 }*/
1414  
1415 5 CF_SETUP;
1416  
1417 615 ▶ for (y = 0; y < img->ysize; ++y) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < img->ysize; ++y) { 610 5 615
1418 90710 ▶ for (x = 0; x < img->xsize; ++x) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < img->xsize; ++x) { 90100 610 90710
1419 i_color val;
1420 errdiff_t perr;
1421 90100 i_gpix(img, x, y, &val);
1422 90100 ▶ if (img->channels < 3) {
Branch: 1 branch
BranchTrueFalseTotal
if (img->channels < 3) { 0 90100 90100
1423 0 val.channel[1] = val.channel[2] = val.channel[0];
1424 }
1425 90100 ▶ else if (is_gray) {
Branch: 1 branch
BranchTrueFalseTotal
else if (is_gray) { 100 90000 90100
1426 100 int gray = 0.5 + color_to_grey(&val);
1427 100 val.channel[0] = val.channel[1] = val.channel[2] = gray;
1428 }
1429 90100 perr = err[x+mapo];
1430 90100 ▶ perr.r = perr.r < 0 ? -((-perr.r)/difftotal) : perr.r/difftotal;
Branch: 1 branch
BranchTrueFalseTotal
perr.r = perr.r < 0 ? -((-perr.r)/difftotal) : perr.r/difftotal; 9002 81098 90100
1431 90100 ▶ perr.g = perr.g < 0 ? -((-perr.g)/difftotal) : perr.g/difftotal;
Branch: 1 branch
BranchTrueFalseTotal
perr.g = perr.g < 0 ? -((-perr.g)/difftotal) : perr.g/difftotal; 18200 71900 90100
1432 90100 ▶ perr.b = perr.b < 0 ? -((-perr.b)/difftotal) : perr.b/difftotal;
Branch: 1 branch
BranchTrueFalseTotal
perr.b = perr.b < 0 ? -((-perr.b)/difftotal) : perr.b/difftotal; 17780 72320 90100
1433 /*printf("x %3d y %3d in(%3d, %3d, %3d) di(%4d,%4d,%4d)\n", x, y, val.channel[0], val.channel[1], val.channel[2], perr.r, perr.g, perr.b);*/
1434 90100 val.channel[0] = g_sat(val.channel[0]-perr.r);
1435 90100 val.channel[1] = g_sat(val.channel[1]-perr.g);
1436 90100 val.channel[2] = g_sat(val.channel[2]-perr.b);
1437 469450 ▶ CF_FIND;
Branch: 2 branches
BranchTrueFalseTotal
CF_FIND; 104242 275108 379350
CF_FIND; 379350 90100 469450
1438 /* save error */
1439 90100 perr.r = quant->mc_colors[bst_idx].channel[0] - val.channel[0];
1440 90100 perr.g = quant->mc_colors[bst_idx].channel[1] - val.channel[1];
1441 90100 perr.b = quant->mc_colors[bst_idx].channel[2] - val.channel[2];
1442 /*printf(" out(%3d, %3d, %3d) er(%4d, %4d, %4d)\n", quant->mc_colors[bst_idx].channel[0], quant->mc_colors[bst_idx].channel[1], quant->mc_colors[bst_idx].channel[2], perr.r, perr.g, perr.b);*/
1443 360400 ▶ for (dx = 0; dx < mapw; ++dx) {
Branch: 1 branch
BranchTrueFalseTotal
for (dx = 0; dx < mapw; ++dx) { 270300 90100 360400
1444 810900 ▶ for (dy = 0; dy < maph; ++dy) {
Branch: 1 branch
BranchTrueFalseTotal
for (dy = 0; dy < maph; ++dy) { 540600 270300 810900
1445 540600 err[x+dx+dy*errw].r += perr.r * map[dx+mapw*dy];
1446 540600 err[x+dx+dy*errw].g += perr.g * map[dx+mapw*dy];
1447 540600 err[x+dx+dy*errw].b += perr.b * map[dx+mapw*dy];
1448 }
1449 }
1450 90100 *out++ = bst_idx;
1451 }
1452 /* shift up the error matrix */
1453 1220 ▶ for (dy = 0; dy < maph-1; ++dy) {
Branch: 1 branch
BranchTrueFalseTotal
for (dy = 0; dy < maph-1; ++dy) { 610 610 1220
1454 610 memcpy(err+dy*errw, err+(dy+1)*errw, sizeof(*err)*errw);
1455 }
1456 610 memset(err+(maph-1)*errw, 0, sizeof(*err)*errw);
1457 }
1458 5 CF_CLEANUP;
1459 5 myfree(err);
1460  
1461 5 return 1;
1462  
1463 0 fail:
1464 0 CF_CLEANUP;
1465  
1466 0 return 0;
1467 }
1468 /* Prescan finds the boxes in the image that have the highest number of colors
1469 and that result is used as the initial value for the vectores */
1470  
1471  
1472 0 static void prescan(i_img **imgs,int count, int cnum, cvec *clr, i_sample_t *line) {
1473 int i,k,j;
1474 i_img_dim x,y;
1475 i_sample_t *val;
1476 const int *chans;
1477  
1478 pbox prebox[512];
1479 0 ▶ for(i=0;i<512;i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i=0;i<512;i++) { 0 0 0
1480 0 prebox[i].boxnum=i;
1481 0 prebox[i].pixcnt=0;
1482 0 prebox[i].cand=1;
1483 }
1484  
1485 /* process each image */
1486 0 ▶ for (i = 0; i < count; ++i) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < count; ++i) { 0 0 0
1487 0 i_img *im = imgs[i];
1488 0 ▶ chans = im->channels >= 3 ? NULL : gray_samples;
Branch: 1 branch
BranchTrueFalseTotal
chans = im->channels >= 3 ? NULL : gray_samples; 0 0 0
1489 0 ▶ for(y=0;y<im->ysize;y++) {
Branch: 1 branch
BranchTrueFalseTotal
for(y=0;y<im->ysize;y++) { 0 0 0
1490 0 i_gsamp(im, 0, im->xsize, y, line, chans, 3);
1491 0 val = line;
1492 0 ▶ for(x=0;x<im->xsize;x++) {
Branch: 1 branch
BranchTrueFalseTotal
for(x=0;x<im->xsize;x++) { 0 0 0
1493 0 prebox[pixbox_ch(val)].pixcnt++;
1494 }
1495 }
1496 }
1497  
1498 0 ▶ for(i=0;i<512;i++) prebox[i].pdc=prebox[i].pixcnt;
Branch: 1 branch
BranchTrueFalseTotal
for(i=0;i<512;i++) prebox[i].pdc=prebox[i].pixcnt; 0 0 0
1499 0 qsort(prebox,512,sizeof(pbox),(cmpfunc)pboxcmp);
1500  
1501 0 ▶ for(i=0;i<cnum;i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i=0;i<cnum;i++) { 0 0 0
1502 /* printf("Color %d\n",i);
1503 for(k=0;k<10;k++) { printf("box=%03d %04d %d %04d \n",prebox[k].boxnum,prebox[k].pixcnt,prebox[k].cand,prebox[k].pdc); }
1504 printf("\n\n"); */
1505 0 reorder(prebox);
1506 }
1507
1508 /* for(k=0;k<cnum;k++) { printf("box=%03d %04d %d %04d \n",prebox[k].boxnum,prebox[k].pixcnt,prebox[k].cand,prebox[k].pdc); } */
1509
1510 0 k=0;
1511 0 j=1;
1512 0 i=0;
1513 0 ▶ while(i<cnum) {
Branch: 1 branch
BranchTrueFalseTotal
while(i<cnum) { 0 0 0
1514 /* printf("prebox[%d].cand=%d\n",k,prebox[k].cand); */
1515 0 ▶ if (clr[i].fixed) { i++; continue; } /* reserved go to next */
Branch: 1 branch
BranchTrueFalseTotal
if (clr[i].fixed) { i++; continue; } /* reserved go to next */ 0 0 0
1516 0 ▶ if (j>=prebox[k].cand) { k++; j=1; } else {
Branch: 1 branch
BranchTrueFalseTotal
if (j>=prebox[k].cand) { k++; j=1; } else { 0 0 0
1517 0 ▶ if (prebox[k].cand == 2) boxcenter(prebox[k].boxnum,&(clr[i]));
Branch: 1 branch
BranchTrueFalseTotal
if (prebox[k].cand == 2) boxcenter(prebox[k].boxnum,&(clr[i])); 0 0 0
1518 0 else boxrand(prebox[k].boxnum,&(clr[i]));
1519 /* printf("(%d,%d) %d %d -> (%d,%d,%d)\n",k,j,prebox[k].boxnum,prebox[k].pixcnt,clr[i].r,clr[i].g,clr[i].b); */
1520 0 j++;
1521 0 i++;
1522 }
1523 }
1524 0 }
1525
1526  
1527 0 static void reorder(pbox prescan[512]) {
1528 int nidx;
1529 pbox c;
1530  
1531 0 nidx=0;
1532 0 c=prescan[0];
1533
1534 0 c.cand++;
1535 0 c.pdc=c.pixcnt/(c.cand*c.cand);
1536 /* c.pdc=c.pixcnt/c.cand; */
1537 0 ▶ while(nidx < 511 && c.pdc < prescan[nidx+1].pdc) {
Branch: 2 branches
BranchTrueFalseTotal
while(nidx < 511 && c.pdc < prescan[nidx+1].pdc) { 0 0 0
while(nidx < 511 && c.pdc < prescan[nidx+1].pdc) { 0 0 0
1538 0 prescan[nidx]=prescan[nidx+1];
1539 0 nidx++;
1540 }
1541 0 prescan[nidx]=c;
1542 0 }
1543  
1544 static int
1545 0 pboxcmp(const pbox *a,const pbox *b) {
1546 0 ▶ if (a->pixcnt > b->pixcnt) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (a->pixcnt > b->pixcnt) return -1; 0 0 0
1547 0 ▶ if (a->pixcnt < b->pixcnt) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (a->pixcnt < b->pixcnt) return 1; 0 0 0
1548 0 return 0;
1549 }
1550  
1551 static void
1552 0 boxcenter(int box,cvec *cv) {
1553 0 cv->r=15+((box&448)>>1);
1554 0 cv->g=15+((box&56)<<2);
1555 0 cv->b=15+((box&7)<<5);
1556 0 }
1557  
1558 static void
1559 0 bbox(int box,int *r0,int *r1,int *g0,int *g1,int *b0,int *b1) {
1560 0 *r0=(box&448)>>1;
1561 0 *r1=(*r0)|31;
1562 0 *g0=(box&56)<<2;
1563 0 *g1=(*g0)|31;
1564 0 *b0=(box&7)<<5;
1565 0 *b1=(*b0)|31;
1566 0 }
1567  
1568 static void
1569 0 boxrand(int box,cvec *cv) {
1570 0 cv->r=6+(rand()%25)+((box&448)>>1);
1571 0 cv->g=6+(rand()%25)+((box&56)<<2);
1572 0 cv->b=6+(rand()%25)+((box&7)<<5);
1573 0 }
1574  
1575 static float
1576 0 frandn(void) {
1577  
1578 float u1,u2,w;
1579
1580 0 w=1;
1581
1582 0 ▶ while (w >= 1 || w == 0) {
Branch: 2 branches
BranchTrueFalseTotal
while (w >= 1 || w == 0) { 0 0 0
while (w >= 1 || w == 0) { 0 0 0
1583 0 u1 = 2 * frand() - 1;
1584 0 u2 = 2 * frand() - 1;
1585 0 w = u1*u1 + u2*u2;
1586 }
1587
1588 0 w = sqrt((-2*log(w))/w);
1589 0 return u1*w;
1590 }
1591  
1592 /* Create hash index */
1593 static
1594 void
1595 0 cr_hashindex(cvec clr[256],int cnum,hashbox hb[512]) {
1596
1597 int bx,mind,cd,i;
1598 /* printf("indexing... \n");*/
1599
1600 0 ▶ for(bx=0; bx<512; bx++) {
Branch: 1 branch
BranchTrueFalseTotal
for(bx=0; bx<512; bx++) { 0 0 0
1601 0 mind=196608;
1602 0 ▶ for(i=0; i<cnum; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i=0; i<cnum; i++) { 0 0 0
1603 0 cd = maxdist(bx,&clr[i]);
1604 0 ▶ if (cd < mind) { mind=cd; }
Branch: 1 branch
BranchTrueFalseTotal
if (cd < mind) { mind=cd; } 0 0 0
1605 }
1606
1607 0 hb[bx].cnt=0;
1608 0 ▶ for(i=0;i<cnum;i++) if (mindist(bx,&clr[i])<mind) hb[bx].vec[hb[bx].cnt++]=i;
Branch: 2 branches
BranchTrueFalseTotal
for(i=0;i<cnum;i++) if (mindist(bx,&clr[i])<mind) hb[bx].vec[hb[bx].cnt++]=i; 0 0 0
for(i=0;i<cnum;i++) if (mindist(bx,&clr[i])<mind) hb[bx].vec[hb[bx].cnt++]=i; 0 0 0
1609 /*printf("box %d -> approx -> %d\n",bx,hb[bx].cnt); */
1610 /* statbox(bx,cnum,clr); */
1611 }
1612
1613 /* printf("Average search space: %d\n",cumcnt/512); */
1614 0 }
1615  
1616 static int
1617 0 maxdist(int boxnum,cvec *cv) {
1618 int r0,r1,g0,g1,b0,b1;
1619 int r,g,b,mr,mg,mb;
1620  
1621 0 r=cv->r;
1622 0 g=cv->g;
1623 0 b=cv->b;
1624
1625 0 bbox(boxnum,&r0,&r1,&g0,&g1,&b0,&b1);
1626  
1627 0 mr=i_max(abs(b-b0),abs(b-b1));
1628 0 mg=i_max(abs(g-g0),abs(g-g1));
1629 0 mb=i_max(abs(r-r0),abs(r-r1));
1630
1631 0 return PWR2(mr)+PWR2(mg)+PWR2(mb);
1632 }
1633  
1634 static int
1635 0 mindist(int boxnum,cvec *cv) {
1636 int r0,r1,g0,g1,b0,b1;
1637 int r,g,b,mr,mg,mb;
1638  
1639 0 r=cv->r;
1640 0 g=cv->g;
1641 0 b=cv->b;
1642
1643 0 bbox(boxnum,&r0,&r1,&g0,&g1,&b0,&b1);
1644  
1645 /* printf("box %d, (%d,%d,%d)-(%d,%d,%d) vec (%d,%d,%d) ",boxnum,r0,g0,b0,r1,g1,b1,r,g,b); */
1646  
1647 0 ▶ if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0;
Branch: 6 branches
BranchTrueFalseTotal
if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; 0 0 0
if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; 0 0 0
if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; 0 0 0
if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; 0 0 0
if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; 0 0 0
if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0; 0 0 0
1648  
1649 0 mr=i_min(abs(b-b0),abs(b-b1));
1650 0 mg=i_min(abs(g-g0),abs(g-g1));
1651 0 mb=i_min(abs(r-r0),abs(r-r1));
1652
1653 0 mr=PWR2(mr);
1654 0 mg=PWR2(mg);
1655 0 mb=PWR2(mb);
1656  
1657 0 ▶ if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb;
Branch: 4 branches
BranchTrueFalseTotal
if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb; 0 0 0
if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb; 0 0 0
if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb; 0 0 0
if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb; 0 0 0
1658 0 ▶ if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg;
Branch: 4 branches
BranchTrueFalseTotal
if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg; 0 0 0
if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg; 0 0 0
if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg; 0 0 0
if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg; 0 0 0
1659 0 ▶ if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr;
Branch: 4 branches
BranchTrueFalseTotal
if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr; 0 0 0
if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr; 0 0 0
if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr; 0 0 0
if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr; 0 0 0
1660  
1661 0 ▶ if (r0<=r && r<=r1) return mg+mb;
Branch: 2 branches
BranchTrueFalseTotal
if (r0<=r && r<=r1) return mg+mb; 0 0 0
if (r0<=r && r<=r1) return mg+mb; 0 0 0
1662 0 ▶ if (g0<=g && g<=g1) return mr+mb;
Branch: 2 branches
BranchTrueFalseTotal
if (g0<=g && g<=g1) return mr+mb; 0 0 0
if (g0<=g && g<=g1) return mr+mb; 0 0 0
1663 0 ▶ if (b0<=b && b<=b1) return mg+mr;
Branch: 2 branches
BranchTrueFalseTotal
if (b0<=b && b<=b1) return mg+mr; 0 0 0
if (b0<=b && b<=b1) return mg+mr; 0 0 0
1664  
1665 0 return mr+mg+mb;
1666 }
1667  
1668 static void transparent_threshold(i_quantize *, i_palidx *, i_img *, i_palidx);
1669 static void transparent_errdiff(i_quantize *, i_palidx *, i_img *, i_palidx);
1670 static void transparent_ordered(i_quantize *, i_palidx *, i_img *, i_palidx);
1671  
1672 /*
1673 =item i_quant_transparent(C<quant>, C<data>, C<img>, C<trans_index>)
1674  
1675 =category Image quantization
1676  
1677 Dither the alpha channel on C<img> into the palette indexes in
1678 C<data>. Pixels to be transparent are replaced with C<trans_pixel>.
1679  
1680 The method used depends on the tr_* members of C<quant>.
1681  
1682 =cut
1683 */
1684  
1685 void
1686 0 i_quant_transparent(i_quantize *quant, i_palidx *data, i_img *img,
1687 i_palidx trans_index)
1688 {
1689 0 switch (quant->transp) {
1690 0 case tr_none:
1691 0 break;
1692
1693 0 default:
1694 0 quant->tr_threshold = 128;
1695 /* fall through */
1696 0 case tr_threshold:
1697 0 transparent_threshold(quant, data, img, trans_index);
1698 0 break;
1699
1700 0 case tr_errdiff:
1701 0 transparent_errdiff(quant, data, img, trans_index);
1702 0 break;
1703  
1704 0 case tr_ordered:
1705 0 transparent_ordered(quant, data, img, trans_index);
1706 0 break;
1707 }
1708 0 }
1709  
1710 static void
1711 0 transparent_threshold(i_quantize *quant, i_palidx *data, i_img *img,
1712 i_palidx trans_index)
1713 {
1714 i_img_dim x, y;
1715 0 i_sample_t *line = mymalloc(img->xsize * sizeof(i_sample_t));
1716 0 ▶ int trans_chan = img->channels > 2 ? 3 : 1;
Branch: 1 branch
BranchTrueFalseTotal
int trans_chan = img->channels > 2 ? 3 : 1; 0 0 0
1717
1718 0 ▶ for (y = 0; y < img->ysize; ++y) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < img->ysize; ++y) { 0 0 0
1719 0 i_gsamp(img, 0, img->xsize, y, line, &trans_chan, 1);
1720 0 ▶ for (x = 0; x < img->xsize; ++x) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < img->xsize; ++x) { 0 0 0
1721 0 ▶ if (line[x] < quant->tr_threshold)
Branch: 1 branch
BranchTrueFalseTotal
if (line[x] < quant->tr_threshold) 0 0 0
1722 0 data[y*img->xsize+x] = trans_index;
1723 }
1724 }
1725 0 myfree(line);
1726 0 }
1727  
1728 static void
1729 0 transparent_errdiff(i_quantize *quant, i_palidx *data, i_img *img,
1730 i_palidx trans_index)
1731 {
1732 int *map;
1733 int index;
1734 int mapw, maph, mapo;
1735 int errw, *err, *errp;
1736 int difftotal, out, error;
1737 i_img_dim x, y, dx, dy;
1738 int i;
1739 i_sample_t *line;
1740 0 ▶ int trans_chan = img->channels > 2 ? 3 : 1;
Branch: 1 branch
BranchTrueFalseTotal
int trans_chan = img->channels > 2 ? 3 : 1; 0 0 0
1741  
1742 /* no custom map for transparency (yet) */
1743 0 index = quant->tr_errdiff & ed_mask;
1744 0 ▶ if (index >= ed_custom) index = ed_floyd;
Branch: 1 branch
BranchTrueFalseTotal
if (index >= ed_custom) index = ed_floyd; 0 0 0
1745 0 map = maps[index].map;
1746 0 mapw = maps[index].width;
1747 0 maph = maps[index].height;
1748 0 mapo = maps[index].orig;
1749  
1750 0 errw = img->xsize+mapw-1;
1751 0 err = mymalloc(sizeof(*err) * maph * errw);
1752 0 errp = err+mapo;
1753 0 memset(err, 0, sizeof(*err) * maph * errw);
1754  
1755 0 line = mymalloc(img->xsize * sizeof(i_sample_t));
1756 0 difftotal = 0;
1757 0 ▶ for (i = 0; i < maph * mapw; ++i)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < maph * mapw; ++i) 0 0 0
1758 0 difftotal += map[i];
1759 0 ▶ for (y = 0; y < img->ysize; ++y) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < img->ysize; ++y) { 0 0 0
1760 0 i_gsamp(img, 0, img->xsize, y, line, &trans_chan, 1);
1761 0 ▶ for (x = 0; x < img->xsize; ++x) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < img->xsize; ++x) { 0 0 0
1762 0 line[x] = g_sat(line[x]-errp[x]/difftotal);
1763 0 ▶ if (line[x] < 128) {
Branch: 1 branch
BranchTrueFalseTotal
if (line[x] < 128) { 0 0 0
1764 0 out = 0;
1765 0 data[y*img->xsize+x] = trans_index;
1766 }
1767 else {
1768 0 out = 255;
1769 }
1770 0 error = out - line[x];
1771 0 ▶ for (dx = 0; dx < mapw; ++dx) {
Branch: 1 branch
BranchTrueFalseTotal
for (dx = 0; dx < mapw; ++dx) { 0 0 0
1772 0 ▶ for (dy = 0; dy < maph; ++dy) {
Branch: 1 branch
BranchTrueFalseTotal
for (dy = 0; dy < maph; ++dy) { 0 0 0
1773 0 errp[x+dx-mapo+dy*errw] += error * map[dx+mapw*dy];
1774 }
1775 }
1776 }
1777 /* shift up the error matrix */
1778 0 ▶ for (dy = 0; dy < maph-1; ++dy)
Branch: 1 branch
BranchTrueFalseTotal
for (dy = 0; dy < maph-1; ++dy) 0 0 0
1779 0 memcpy(err+dy*errw, err+(dy+1)*errw, sizeof(*err)*errw);
1780 0 memset(err+(maph-1)*errw, 0, sizeof(*err)*errw);
1781 }
1782 0 myfree(err);
1783 0 myfree(line);
1784 0 }
1785  
1786 /* builtin ordered dither maps */
1787 static unsigned char
1788 orddith_maps[][64] =
1789 {
1790 { /* random
1791 this is purely random - it's pretty awful
1792 */
1793 48, 72, 196, 252, 180, 92, 108, 52,
1794 228, 176, 64, 8, 236, 40, 20, 164,
1795 120, 128, 84, 116, 24, 28, 172, 220,
1796 68, 0, 188, 124, 184, 224, 192, 104,
1797 132, 100, 240, 200, 152, 160, 244, 44,
1798 96, 204, 144, 16, 140, 56, 232, 216,
1799 208, 4, 76, 212, 136, 248, 80, 168,
1800 156, 88, 32, 112, 148, 12, 36, 60,
1801 },
1802 {
1803 /* dot8
1804 perl spot.perl '($x-3.5)*($x-3.5)+($y-3.5)*($y-3.5)'
1805 */
1806 240, 232, 200, 136, 140, 192, 228, 248,
1807 220, 148, 100, 76, 80, 104, 152, 212,
1808 180, 116, 56, 32, 36, 60, 120, 176,
1809 156, 64, 28, 0, 8, 44, 88, 160,
1810 128, 92, 24, 12, 4, 40, 68, 132,
1811 184, 96, 48, 20, 16, 52, 108, 188,
1812 216, 144, 112, 72, 84, 124, 164, 224,
1813 244, 236, 196, 168, 172, 204, 208, 252,
1814 },
1815 { /* dot4
1816 perl spot.perl \
1817 'min(dist(1.5, 1.5),dist(5.5,1.5),dist(1.5,5.5),dist(5.5,5.5))'
1818 */
1819 196, 72, 104, 220, 200, 80, 112, 224,
1820 76, 4, 24, 136, 84, 8, 32, 144,
1821 108, 28, 52, 168, 116, 36, 56, 176,
1822 216, 140, 172, 244, 228, 148, 180, 248,
1823 204, 92, 124, 236, 192, 68, 96, 208,
1824 88, 12, 44, 156, 64, 0, 16, 128,
1825 120, 40, 60, 188, 100, 20, 48, 160,
1826 232, 152, 184, 252, 212, 132, 164, 240,
1827 },
1828 { /* hline
1829 perl spot.perl '$y-3'
1830 */
1831 160, 164, 168, 172, 176, 180, 184, 188,
1832 128, 132, 136, 140, 144, 148, 152, 156,
1833 32, 36, 40, 44, 48, 52, 56, 60,
1834 0, 4, 8, 12, 16, 20, 24, 28,
1835 64, 68, 72, 76, 80, 84, 88, 92,
1836 96, 100, 104, 108, 112, 116, 120, 124,
1837 192, 196, 200, 204, 208, 212, 216, 220,
1838 224, 228, 232, 236, 240, 244, 248, 252,
1839 },
1840 { /* vline
1841 perl spot.perl '$x-3'
1842 */
1843 180, 100, 40, 12, 44, 104, 184, 232,
1844 204, 148, 60, 16, 64, 128, 208, 224,
1845 212, 144, 76, 8, 80, 132, 216, 244,
1846 160, 112, 68, 20, 84, 108, 172, 236,
1847 176, 96, 72, 28, 88, 152, 188, 228,
1848 200, 124, 92, 0, 32, 116, 164, 240,
1849 168, 120, 36, 24, 48, 136, 192, 248,
1850 196, 140, 52, 4, 56, 156, 220, 252,
1851 },
1852 { /* slashline
1853 perl spot.perl '$y+$x-7'
1854 */
1855 248, 232, 224, 192, 140, 92, 52, 28,
1856 240, 220, 196, 144, 108, 60, 12, 64,
1857 216, 180, 148, 116, 76, 20, 80, 128,
1858 204, 152, 104, 44, 16, 72, 100, 160,
1859 164, 96, 68, 24, 56, 112, 168, 176,
1860 124, 40, 8, 36, 88, 136, 184, 212,
1861 84, 4, 32, 120, 156, 188, 228, 236,
1862 0, 48, 132, 172, 200, 208, 244, 252,
1863 },
1864 { /* backline
1865 perl spot.perl '$y-$x'
1866 */
1867 0, 32, 116, 172, 184, 216, 236, 252,
1868 56, 8, 72, 132, 136, 200, 228, 240,
1869 100, 36, 12, 40, 92, 144, 204, 220,
1870 168, 120, 60, 16, 44, 96, 156, 176,
1871 180, 164, 112, 48, 28, 52, 128, 148,
1872 208, 192, 152, 88, 84, 20, 64, 104,
1873 232, 224, 196, 140, 108, 68, 24, 76,
1874 248, 244, 212, 188, 160, 124, 80, 4,
1875 },
1876 {
1877 /* tiny
1878 good for display, bad for print
1879 hand generated
1880 */
1881 0, 128, 32, 192, 8, 136, 40, 200,
1882 224, 64, 160, 112, 232, 72, 168, 120,
1883 48, 144, 16, 208, 56, 152, 24, 216,
1884 176, 96, 240, 80, 184, 104, 248, 88,
1885 12, 140, 44, 204, 4, 132, 36, 196,
1886 236, 76, 172, 124, 228, 68, 164, 116,
1887 60, 156, 28, 220, 52, 148, 20, 212,
1888 188, 108, 252, 92, 180, 100, 244, 84,
1889 },
1890 };
1891  
1892 static void
1893 0 transparent_ordered(i_quantize *quant, i_palidx *data, i_img *img,
1894 i_palidx trans_index)
1895 {
1896 unsigned char *spot;
1897 i_img_dim x, y;
1898 i_sample_t *line;
1899 0 ▶ int trans_chan = img->channels > 2 ? 3 : 1;
Branch: 1 branch
BranchTrueFalseTotal
int trans_chan = img->channels > 2 ? 3 : 1; 0 0 0
1900 0 ▶ if (quant->tr_orddith == od_custom)
Branch: 1 branch
BranchTrueFalseTotal
if (quant->tr_orddith == od_custom) 0 0 0
1901 0 spot = quant->tr_custom;
1902 else
1903 0 spot = orddith_maps[quant->tr_orddith];
1904  
1905 0 line = mymalloc(img->xsize * sizeof(i_sample_t));
1906 0 ▶ for (y = 0; y < img->ysize; ++y) {
Branch: 1 branch
BranchTrueFalseTotal
for (y = 0; y < img->ysize; ++y) { 0 0 0
1907 0 i_gsamp(img, 0, img->xsize, y, line, &trans_chan, 1);
1908 0 ▶ for (x = 0; x < img->xsize; ++x) {
Branch: 1 branch
BranchTrueFalseTotal
for (x = 0; x < img->xsize; ++x) { 0 0 0
1909 0 ▶ if (line[x] < spot[(x&7)+(y&7)*8])
Branch: 1 branch
BranchTrueFalseTotal
if (line[x] < spot[(x&7)+(y&7)*8]) 0 0 0
1910 0 data[x+y*img->xsize] = trans_index;
1911 }
1912 }
1913 0 myfree(line);
1914 0 }
1915  
« imext.c ↑ Summary context.c »