Added an Imager::log_entry() function and some extra logging
[imager.git] / quant.c
CommitLineData
02d1d628
AMH
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 "image.h"
6
7static void makemap_addi(i_quantize *, i_img **imgs, int count);
8
9static
10void
11setcol(i_color *cl,unsigned char r,unsigned char g,unsigned char b,unsigned char a) {
12 cl->rgba.r=r;
13 cl->rgba.g=g;
14 cl->rgba.b=b;
15 cl->rgba.a=a;
16}
17
18
19
20/* make a colour map overwrites mc_existing/mc_count in quant Note
21 that i_makemap will be called once for each image if mc_perimage is
22 set and the format support multiple colour maps per image.
23
24 This means we don't need any special processing at this level to
25 handle multiple colour maps.
26*/
27
28void
29quant_makemap(i_quantize *quant, i_img **imgs, int count) {
02d1d628
AMH
30#ifdef HAVE_LIBGIF
31 /* giflib does it's own color table generation */
32 if (quant->translate == pt_giflib)
33 return;
34#endif
35 switch (quant->make_colors & mc_mask) {
36 case mc_none:
37 /* use user's specified map */
38 break;
39 case mc_web_map:
40 {
41 int r, g, b;
42 int i = 0;
43 for (r = 0; r < 256; r+=0x33)
44 for (g = 0; g < 256; g+=0x33)
45 for (b = 0; b < 256; b += 0x33)
46 setcol(quant->mc_colors+i++, r, g, b, 0);
47 quant->mc_count = i;
48 }
49 break;
50
51 case mc_addi:
52 default:
53 makemap_addi(quant, imgs, count);
54 break;
55 }
56}
57
58#ifdef HAVE_LIBGIF
59static void translate_giflib(i_quantize *, i_img *, i_palidx *);
60#endif
61static void translate_closest(i_quantize *, i_img *, i_palidx *);
62static void translate_errdiff(i_quantize *, i_img *, i_palidx *);
63static void translate_addi(i_quantize *, i_img *, i_palidx *);
64
65/* Quantize the image given the palette in quant.
66
67 The giflib quantizer ignores the palette.
68*/
69i_palidx *quant_translate(i_quantize *quant, i_img *img) {
2ff8ed30
AMH
70 i_palidx *result;
71 mm_log((1, "quant_translate(quant %p, img %p)\n", quant, img));
72
73 result = mymalloc(img->xsize * img->ysize);
74
02d1d628
AMH
75 switch (quant->translate) {
76#ifdef HAVE_LIBGIF
77 case pt_giflib:
78 translate_giflib(quant, img, result);
79 break;
80#endif
81
82 case pt_closest:
83 translate_closest(quant, img, result);
84 break;
85
86 case pt_errdiff:
87 translate_errdiff(quant, img, result);
88 break;
89
90 case pt_perturb:
91 default:
92 translate_addi(quant, img, result);
93 break;
94 }
95
96 return result;
97}
98
99#ifdef HAVE_LIBGIF
100#include "gif_lib.h"
101
102#define GET_RGB(im, x, y, ri, gi, bi, col) \
103 i_gpix((im),(x),(y),&(col)); (ri)=(col).rgb.r; \
104 if((im)->channels==3) { (bi)=(col).rgb.b; (gi)=(col).rgb.g; }
105
106static int
107quant_replicate(i_img *im, i_palidx *output, i_quantize *quant);
108
109/* Use the gif_lib quantization functions to quantize the image */
110static void translate_giflib(i_quantize *quant, i_img *img, i_palidx *out) {
111 int x,y,ColorMapSize,colours_in;
112 unsigned long Size;
113 int i;
114
115 GifByteType *RedBuffer = NULL, *GreenBuffer = NULL, *BlueBuffer = NULL;
116 GifByteType *RedP, *GreenP, *BlueP;
117 ColorMapObject *OutputColorMap = NULL;
118
119 i_color col;
120
2ff8ed30 121 mm_log((1,"i_writegif(quant %p, img %p, out %p)\n", quant, img, out));
02d1d628
AMH
122
123 /*if (!(im->channels==1 || im->channels==3)) { fprintf(stderr,"Unable to write gif, improper colorspace.\n"); exit(3); }*/
124
125 ColorMapSize = quant->mc_size;
126
127 Size = ((long) img->xsize) * img->ysize * sizeof(GifByteType);
128
129
130 if ((OutputColorMap = MakeMapObject(ColorMapSize, NULL)) == NULL)
131 m_fatal(0,"Failed to allocate memory for Output colormap.");
132 /* if ((OutputBuffer = (GifByteType *) mymalloc(im->xsize * im->ysize * sizeof(GifByteType))) == NULL)
133 m_fatal(0,"Failed to allocate memory for output buffer.");*/
134
135 /* ******************************************************* */
136 /* count the number of colours in the image */
137 colours_in=i_count_colors(img, OutputColorMap->ColorCount);
138
139 if(colours_in != -1) { /* less then the number wanted */
140 /* so we copy them over as-is */
141 mm_log((2,"image has %d colours, which fits in %d. Copying\n",
142 colours_in,ColorMapSize));
143 quant_replicate(img, out, quant);
144 /* saves the colors, so don't fall through */
145 return;
146 } else {
147
148 mm_log((2,"image has %d colours, more then %d. Quantizing\n",colours_in,ColorMapSize));
149
150 if (img->channels >= 3) {
151 if ((RedBuffer = (GifByteType *) mymalloc((unsigned int) Size)) == NULL) {
152 m_fatal(0,"Failed to allocate memory required, aborted.");
153 return;
154 }
155 if ((GreenBuffer = (GifByteType *) mymalloc((unsigned int) Size)) == NULL) {
156 m_fatal(0,"Failed to allocate memory required, aborted.");
862b614c 157 myfree(RedBuffer);
02d1d628
AMH
158 return;
159 }
160
161 if ((BlueBuffer = (GifByteType *) mymalloc((unsigned int) Size)) == NULL) {
162 m_fatal(0,"Failed to allocate memory required, aborted.");
862b614c
AMH
163 myfree(RedBuffer);
164 myfree(GreenBuffer);
02d1d628
AMH
165 return;
166 }
167
168 RedP = RedBuffer;
169 GreenP = GreenBuffer;
170 BlueP = BlueBuffer;
171
172 for (y=0; y< img->ysize; y++) for (x=0; x < img->xsize; x++) {
173 i_gpix(img,x,y,&col);
174 *RedP++ = col.rgb.r;
175 *GreenP++ = col.rgb.g;
176 *BlueP++ = col.rgb.b;
177 }
178
179 } else {
180
181 if ((RedBuffer = (GifByteType *) mymalloc((unsigned int) Size))==NULL) {
182 m_fatal(0,"Failed to allocate memory required, aborted.");
183 return;
184 }
185
186 GreenBuffer=BlueBuffer=RedBuffer;
187 RedP = RedBuffer;
188 for (y=0; y< img->ysize; y++) for (x=0; x < img->xsize; x++) {
189 i_gpix(img,x,y,&col);
190 *RedP++ = col.rgb.r;
191 }
192 }
193
194 if (QuantizeBuffer(img->xsize, img->ysize, &ColorMapSize, RedBuffer, GreenBuffer, BlueBuffer,
195 out, OutputColorMap->Colors) == GIF_ERROR) {
196 mm_log((1,"Error in QuantizeBuffer, unable to write image.\n"));
197 }
198 }
199
862b614c
AMH
200 myfree(RedBuffer);
201 if (img->channels == 3) { myfree(GreenBuffer); myfree(BlueBuffer); }
02d1d628
AMH
202
203 /* copy over the color map */
204 for (i = 0; i < ColorMapSize; ++i) {
205 quant->mc_colors[i].rgb.r = OutputColorMap->Colors[i].Red;
206 quant->mc_colors[i].rgb.g = OutputColorMap->Colors[i].Green;
207 quant->mc_colors[i].rgb.b = OutputColorMap->Colors[i].Blue;
208 }
209 quant->mc_count = ColorMapSize;
210}
211
212static
213int
214quant_replicate(i_img *im, GifByteType *output, i_quantize *quant) {
215 int x, y, alloced, r, g=0, b=0, idx ;
216 i_color col;
217
218 alloced=0;
219 for(y=0; y<im->ysize; y++) {
220 for(x=0; x<im->xsize; x++) {
221
222 GET_RGB(im, x,y, r,g,b, col);
223
224 for(idx=0; idx<alloced; idx++) { /* linear search for an index */
225 if(quant->mc_colors[idx].rgb.r==r &&
226 quant->mc_colors[idx].rgb.g==g &&
227 quant->mc_colors[idx].rgb.b==b) {
228 break;
229 }
230 }
231
232 if(idx >= alloced) { /* if we haven't already, we */
233 idx=alloced++; /* add the colour to the map */
234 if(quant->mc_size < alloced) {
235 mm_log((1,"Tried to allocate more then %d colours.\n",
236 quant->mc_size));
237 return 0;
238 }
239 quant->mc_colors[idx].rgb.r=r;
240 quant->mc_colors[idx].rgb.g=g;
241 quant->mc_colors[idx].rgb.b=b;
242 }
243 *output=idx; /* fill output buffer */
244 output++; /* with colour indexes */
245 }
246 }
247 quant->mc_count = alloced;
248 return 1;
249}
250
251#endif
252
253static void translate_closest(i_quantize *quant, i_img *img, i_palidx *out) {
254 quant->perturb = 0;
255 translate_addi(quant, img, out);
256}
257
258#define PWR2(x) ((x)*(x))
259
260typedef int (*cmpfunc)(const void*, const void*);
261
262typedef struct {
263 unsigned char r,g,b;
36e67d0b
TC
264 char fixed;
265 char used;
02d1d628
AMH
266 int dr,dg,db;
267 int cdist;
268 int mcount;
269} cvec;
270
271typedef struct {
272 int cnt;
273 int vec[256];
274} hashbox;
275
276typedef struct {
277 int boxnum;
278 int pixcnt;
279 int cand;
280 int pdc;
281} pbox;
282
283static void prescan(i_img **im,int count, int cnum, cvec *clr);
284static void reorder(pbox prescan[512]);
285static int pboxcmp(const pbox *a,const pbox *b);
286static void boxcenter(int box,cvec *cv);
287static float frandn(void);
288static void boxrand(int box,cvec *cv);
289static void bbox(int box,int *r0,int *r1,int *g0,int *g1,int *b0,int *b1);
290static void cr_hashindex(cvec clr[256],int cnum,hashbox hb[512]);
291static int mindist(int boxnum,cvec *cv);
292static int maxdist(int boxnum,cvec *cv);
293
294/* Some of the simpler functions are kept here to aid the compiler -
295 maybe some of them will be inlined. */
296
297static int
298pixbox(i_color *ic) { return ((ic->channel[0] & 224)<<1)+ ((ic->channel[1]&224)>>2) + ((ic->channel[2] &224) >> 5); }
299
300static unsigned char
301g_sat(int in) {
302 if (in>255) { return 255; }
303 else if (in>0) return in;
304 return 0;
305}
306
307static
308float
309frand(void) {
310 return rand()/(RAND_MAX+1.0);
311}
312
313static
314int
315eucl_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]); }
316
317static
318int
319ceucl_d(i_color *c1, i_color *c2) { return PWR2(c1->channel[0]-c2->channel[0])+PWR2(c1->channel[1]-c2->channel[1])+PWR2(c1->channel[2]-c2->channel[2]); }
320
321/*
322
323This quantization algorithm and implementation routines are by Arnar
324M. Hrafnkelson. In case any new ideas are here they are mine since
325this was written from scratch.
326
327The algorithm uses local means in the following way:
328
329 For each point in the colormap we find which image points
330 have that point as it's closest point. We calculate the mean
331 of those points and in the next iteration it will be the new
332 entry in the colormap.
333
334In order to speed this process up (i.e. nearest neighbor problem) We
335divied the r,g,b space up in equally large 512 boxes. The boxes are
336numbered from 0 to 511. Their numbering is so that for a given vector
337it is known that it belongs to the box who is formed by concatenating the
3383 most significant bits from each component of the RGB triplet.
339
340For each box we find the list of points from the colormap who might be
341closest to any given point within the box. The exact solution
342involves finding the Voronoi map (or the dual the Delauny
343triangulation) and has many issues including numerical stability.
344
345So we use this approximation:
346
3471. Find which point has the shortest maximum distance to the box.
3482. Find all points that have a shorter minimum distance than that to the box
349
350This is a very simple task and is not computationally heavy if one
351takes into account that the minimum distances from a pixel to a box is
352always found by checking if it's inside the box or is closest to some
353side or a corner. Finding the maximum distance is also either a side
354or a corner.
355
356This approach results 2-3 times more than the actual points needed but
357is still a good gain over the complete space. Usually when one has a
358256 Colorcolor map a search over 30 is often obtained.
359
360A bit of an enhancement to this approach is to keep a seperate list
361for each side of the cube, but this will require even more memory.
362
363 Arnar M. Hrafnkelsson (addi@umich.edu);
364
365*/
366/*
367 Extracted from gifquant.c, removed dependencies on gif_lib,
368 and added support for multiple images.
369 starting from 1nov2000 by TonyC <tony@develop-help.com>.
370
371*/
372
373static void
374makemap_addi(i_quantize *quant, i_img **imgs, int count) {
375 cvec *clr;
36e67d0b 376 int cnum, i, x, y, bst_idx=0, ld, cd, iter, currhb, img_num;
02d1d628
AMH
377 i_color val;
378 float dlt, accerr;
379 hashbox hb[512];
380
381 clr = (cvec *)mymalloc(sizeof(cvec) * quant->mc_size);
382 for (i=0; i < quant->mc_count; ++i) {
383 clr[i].r = quant->mc_colors[i].rgb.r;
384 clr[i].g = quant->mc_colors[i].rgb.g;
385 clr[i].b = quant->mc_colors[i].rgb.b;
36e67d0b
TC
386 clr[i].fixed = 1;
387 clr[i].mcount = 0;
02d1d628
AMH
388 }
389 /* mymalloc doesn't clear memory, so I think we need this */
390 for (; i < quant->mc_size; ++i) {
36e67d0b
TC
391 clr[i].fixed = 0;
392 clr[i].mcount = 0;
02d1d628
AMH
393 }
394 cnum = quant->mc_size;
395 dlt = 1;
396
397 prescan(imgs, count, cnum, clr);
398 cr_hashindex(clr, cnum, hb);
399
400 for(iter=0;iter<3;iter++) {
401 accerr=0.0;
402
36e67d0b
TC
403 for (img_num = 0; img_num < count; ++img_num) {
404 i_img *im = imgs[img_num];
02d1d628
AMH
405 for(y=0;y<im->ysize;y++) for(x=0;x<im->xsize;x++) {
406 ld=196608;
407 i_gpix(im,x,y,&val);
408 currhb=pixbox(&val);
409 /* printf("box = %d \n",currhb); */
410 for(i=0;i<hb[currhb].cnt;i++) {
411 /* 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); */
412
413 cd=eucl_d(&clr[hb[currhb].vec[i]],&val);
414 if (cd<ld) {
415 ld=cd; /* shortest distance yet */
416 bst_idx=hb[currhb].vec[i]; /* index of closest vector yet */
417 }
418 }
419
420 clr[bst_idx].mcount++;
421 accerr+=(ld);
422 clr[bst_idx].dr+=val.channel[0];
423 clr[bst_idx].dg+=val.channel[1];
424 clr[bst_idx].db+=val.channel[2];
425 }
426 }
427 for(i=0;i<cnum;i++) if (clr[i].mcount) { clr[i].dr/=clr[i].mcount; clr[i].dg/=clr[i].mcount; clr[i].db/=clr[i].mcount; }
428
429 /* for(i=0;i<cnum;i++) printf("vec(%d)=(%d,%d,%d) dest=(%d,%d,%d) matchcount=%d\n",
430 i,clr[i].r,clr[i].g,clr[i].b,clr[i].dr,clr[i].dg,clr[i].db,clr[i].mcount); */
431
432 /* printf("total error: %.2f\n",sqrt(accerr)); */
433
434 for(i=0;i<cnum;i++) {
36e67d0b 435 if (clr[i].fixed) continue; /* skip reserved colors */
02d1d628
AMH
436
437 if (clr[i].mcount) {
36e67d0b 438 clr[i].used = 1;
02d1d628
AMH
439 clr[i].r=clr[i].r*(1-dlt)+dlt*clr[i].dr;
440 clr[i].g=clr[i].g*(1-dlt)+dlt*clr[i].dg;
441 clr[i].b=clr[i].b*(1-dlt)+dlt*clr[i].db;
442 } else {
36e67d0b
TC
443 /* let's try something else */
444 clr[i].used = 0;
02d1d628
AMH
445 clr[i].r=rand();
446 clr[i].g=rand();
447 clr[i].b=rand();
448 }
449
450 clr[i].dr=0;
451 clr[i].dg=0;
452 clr[i].db=0;
453 clr[i].mcount=0;
454 }
455 cr_hashindex(clr,cnum,hb);
456 }
457
458
459#ifdef NOTEF
460 for(i=0;i<cnum;i++) {
461 cd=eucl_d(&clr[i],&val);
462 if (cd<ld) {
463 ld=cd;
464 bst_idx=i;
465 }
466 }
467#endif
468
36e67d0b
TC
469 /* if defined, we only include colours with an mcount or that were
470 supplied in the fixed palette, giving us a smaller output palette */
471#define ONLY_USE_USED
472#ifdef ONLY_USE_USED
473 /* transfer the colors back */
474 quant->mc_count = 0;
475 for (i = 0; i < cnum; ++i) {
476 if (clr[i].fixed || clr[i].used) {
477 /*printf("Adding %d (%d,%d,%d)\n", i, clr[i].r, clr[i].g, clr[i].b);*/
478 quant->mc_colors[quant->mc_count].rgb.r = clr[i].r;
479 quant->mc_colors[quant->mc_count].rgb.g = clr[i].g;
480 quant->mc_colors[quant->mc_count].rgb.b = clr[i].b;
481 ++quant->mc_count;
482 }
483 }
484#else
02d1d628
AMH
485 /* transfer the colors back */
486 for (i = 0; i < cnum; ++i) {
487 quant->mc_colors[i].rgb.r = clr[i].r;
488 quant->mc_colors[i].rgb.g = clr[i].g;
489 quant->mc_colors[i].rgb.b = clr[i].b;
490 }
491 quant->mc_count = cnum;
36e67d0b 492#endif
02d1d628
AMH
493
494 /* don't want to keep this */
495 myfree(clr);
496}
497
498#define pboxjump 32
499
500/* Define one of the following 4 symbols to choose a colour search method
501 The idea is to try these out, including benchmarking, to see which
502 is fastest in a good spread of circumstances.
503 I'd expect IM_CFLINSEARCH to be fastest for very small palettes, and
504 IM_CFHASHBOX for large images with large palettes.
505
506 Some other possibilities include:
507 - search over entries sorted by luminance
508
509 Initially I was planning on testing using the macros and then
510 integrating the code directly into each function, but this means if
511 we find a bug at a late stage we will need to update N copies of
512 the same code. Also, keeping the code in the macros means that the
513 code in the translation functions is much more to the point,
514 there's no distracting colour search code to remove attention from
515 what makes _this_ translation function different. It may be
516 advisable to move the setup code into functions at some point, but
517 it should be possible to do this fairly transparently.
518
519 If IM_CF_COPTS is defined then CFLAGS must have an appropriate
520 definition.
521
522 Each option needs to define 4 macros:
523 CF_VARS - variables to define in the function
524 CF_SETUP - code to setup for the colour search, eg. allocating and
525 initializing lookup tables
526 CF_FIND - code that looks for the color in val and puts the best
527 matching index in bst_idx
528 CF_CLEANUP - code to clean up, eg. releasing memory
529*/
530#ifndef IM_CF_COPTS
531/*#define IM_CFLINSEARCH*/
532#define IM_CFHASHBOX
533/*#define IM_CFSORTCHAN*/
534/*#define IM_CFRAND2DIST*/
535#endif
536
537#ifdef IM_CFHASHBOX
538
539/* The original version I wrote for this used the sort.
540 If this is defined then we use a sort to extract the indices for
541 the hashbox */
542#define HB_SORT
543
544/* assume i is available */
545#define CF_VARS hashbox hb[512]; \
546 int currhb; \
547 long ld, cd
548
549#ifdef HB_SORT
550
551static long *gdists; /* qsort is annoying */
552/* int might be smaller than long, so we need to do a real compare
553 rather than a subtraction*/
554static int distcomp(void const *a, void const *b) {
555 long ra = gdists[*(int const *)a];
556 long rb = gdists[*(int const *)b];
557 if (ra < rb)
558 return -1;
559 else if (ra > rb)
560 return 1;
561 else
562 return 0;
563}
564
565#endif
566
567/* for each hashbox build a list of colours that are in the hb or is closer
568 than other colours
569 This is pretty involved. The original gifquant generated the hashbox
570 as part of it's normal processing, but since the map generation is now
571 separated from the translation we need to do this on the spot.
572 Any optimizations, even if they don't produce perfect results would be
573 welcome.
574 */
575static void hbsetup(i_quantize *quant, hashbox *hb) {
576 long *dists, mind, maxd, cd;
577 int cr, cb, cg, hbnum, i;
578 i_color cenc;
579#ifdef HB_SORT
580 int *indices = mymalloc(quant->mc_count * sizeof(int));
581#endif
582
583 dists = mymalloc(quant->mc_count * sizeof(long));
584 for (cr = 0; cr < 8; ++cr) {
585 for (cg = 0; cg < 8; ++cg) {
586 for (cb = 0; cb < 8; ++cb) {
587 /* centre of the hashbox */
588 cenc.channel[0] = cr*pboxjump+pboxjump/2;
589 cenc.channel[1] = cg*pboxjump+pboxjump/2;
590 cenc.channel[2] = cb*pboxjump+pboxjump/2;
591 hbnum = pixbox(&cenc);
592 hb[hbnum].cnt = 0;
593 /* order indices in the order of distance from the hashbox */
594 for (i = 0; i < quant->mc_count; ++i) {
595#ifdef HB_SORT
596 indices[i] = i;
597#endif
598 dists[i] = ceucl_d(&cenc, quant->mc_colors+i);
599 }
600#ifdef HB_SORT
601 /* it should be possible to do this without a sort
602 but so far I'm too lazy */
603 gdists = dists;
604 qsort(indices, quant->mc_count, sizeof(int), distcomp);
605 /* any colors that can match are within mind+diagonal size of
606 a hashbox */
607 mind = dists[indices[0]];
608 i = 0;
609 maxd = (sqrt(mind)+pboxjump)*(sqrt(mind)+pboxjump);
610 while (i < quant->mc_count && dists[indices[i]] < maxd) {
611 hb[hbnum].vec[hb[hbnum].cnt++] = indices[i++];
612 }
613#else
614 /* work out the minimum */
615 mind = 256*256*3;
616 for (i = 0; i < quant->mc_count; ++i) {
617 if (dists[i] < mind) mind = dists[i];
618 }
619 /* transfer any colours that might be closest to a colour in
620 this hashbox */
621 maxd = (sqrt(mind)+pboxjump)*(sqrt(mind)+pboxjump);
622 for (i = 0; i < quant->mc_count; ++i) {
623 if (dists[i] < maxd)
624 hb[hbnum].vec[hb[hbnum].cnt++] = i;
625 }
626#endif
627 }
628 }
862b614c 629 }
02d1d628
AMH
630#ifdef HB_SORT
631 myfree(indices);
632#endif
633 myfree(dists) ;
634}
635#define CF_SETUP hbsetup(quant, hb)
636
637#define CF_FIND \
638 currhb = pixbox(&val); \
639 ld = 196608; \
640 for (i = 0; i < hb[currhb].cnt; ++i) { \
641 cd = ceucl_d(quant->mc_colors+hb[currhb].vec[i], &val); \
642 if (cd < ld) { ld = cd; bst_idx = hb[currhb].vec[i]; } \
643 }
644
645#define CF_CLEANUP
646
647#endif
648
649#ifdef IM_CFLINSEARCH
650/* as simple as it gets */
651#define CF_VARS long ld, cd
652#define CF_SETUP /* none needed */
653#define CF_FIND \
654 ld = 196608; \
655 for (i = 0; i < quant->mc_count; ++i) { \
656 cd = ceucl_d(quant->mc_colors+i, &val); \
657 if (cd < ld) { ld = cd; bst_idx = i; } \
658 }
659#define CF_CLEANUP
660#endif
661
662#ifdef IM_CFSORTCHAN
663static int gsortchan;
664static i_quantize *gquant;
665static int chansort(void const *a, void const *b) {
666 return gquant->mc_colors[*(int const *)a].channel[gsortchan] -
667 gquant->mc_colors[*(int const *)b].channel[gsortchan];
668}
669#define CF_VARS int *indices, sortchan, diff; \
670 long ld, cd; \
671 int vindex[256] /* where to find value i of chan */
672
673static void chansetup(i_img *img, i_quantize *quant, int *csortchan,
674 int *vindex, int **cindices) {
675 int *indices, sortchan, chan, i, chval;
676 int chanmins[MAXCHANNELS], chanmaxs[MAXCHANNELS], maxrange;
677
678 /* find the channel with the maximum range */
679 /* the maximum stddev would probably be better */
680 for (chan = 0; chan < img->channels; ++chan) {
681 chanmins[chan] = 256; chanmaxs[chan] = 0;
682 for (i = 0; i < quant->mc_count; ++i) {
683 if (quant->mc_colors[i].channel[chan] < chanmins[chan])
684 chanmins[chan] = quant->mc_colors[i].channel[chan];
685 if (quant->mc_colors[i].channel[chan] > chanmaxs[chan])
686 chanmaxs[chan] = quant->mc_colors[i].channel[chan];
687 }
688 }
689 maxrange = -1;
690 for (chan = 0; chan < img->channels; ++chan) {
691 if (chanmaxs[chan]-chanmins[chan] > maxrange) {
692 maxrange = chanmaxs[chan]-chanmins[chan];
693 sortchan = chan;
694 }
695 }
696 indices = mymalloc(quant->mc_count * sizeof(int)) ;
697 for (i = 0; i < quant->mc_count; ++i) {
698 indices[i] = i;
699 }
700 gsortchan = sortchan;
701 gquant = quant;
702 qsort(indices, quant->mc_count, sizeof(int), chansort) ;
703 /* now a lookup table to find entries faster */
704 for (chval=0, i=0; i < quant->mc_count; ++i) {
705 while (chval < 256 &&
706 chval < quant->mc_colors[indices[i]].channel[sortchan]) {
707 vindex[chval++] = i;
708 }
709 }
710 while (chval < 256) {
711 vindex[chval++] = quant->mc_count-1;
712 }
713 *csortchan = sortchan;
714 *cindices = indices;
715}
716
717#define CF_SETUP \
718 chansetup(img, quant, &sortchan, vindex, &indices)
719
720int chanfind(i_color val, i_quantize *quant, int *indices, int *vindex,
721 int sortchan) {
722 int i, bst_idx, diff, maxdiff;
723 long ld, cd;
724
725 i = vindex[val.channel[sortchan]];
726 bst_idx = indices[i];
727 ld = 196608;
728 diff = 0;
729 maxdiff = quant->mc_count;
730 while (diff < maxdiff) {
731 if (i+diff < quant->mc_count) {
732 cd = ceucl_d(&val, quant->mc_colors+indices[i+diff]);
733 if (cd < ld) {
734 bst_idx = indices[i+diff];
735 ld = cd;
736 maxdiff = sqrt(ld);
737 }
738 }
739 if (i-diff >= 0) {
740 cd = ceucl_d(&val, quant->mc_colors+indices[i-diff]);
741 if (cd < ld) {
742 bst_idx = indices[i-diff];
743 ld = cd;
744 maxdiff = sqrt(ld);
745 }
746 }
747 ++diff;
748 }
749
750 return bst_idx;
751}
752
753#define CF_FIND \
754 bst_idx = chanfind(val, quant, indices, vindex, sortchan)
755
756
757#define CF_CLEANUP myfree(indices)
758
759#endif
760
761#ifdef IM_CFRAND2DIST
762
763/* This is based on a method described by Addi in the #imager channel
764 on the 28/2/2001. I was about 1am Sydney time at the time, so I
765 wasn't at my most cogent. Well, that's my excuse :)
766
767<TonyC> what I have at the moment is: hashboxes, with optimum hash box
768filling; simple linear search; and a lookup in the widest channel
769(currently the channel with the maximum range)
770<Addi> There is one more way that might be simple to implement.
771<Addi> You want to hear?
772<TonyC> what's that?
773<purl> somebody said that was not true
774<Addi> For each of the colors in the palette start by creating a
775sorted list of the form:
776<Addi> [distance, color]
777<Addi> Where they are sorted by distance.
778<TonyC> distance to where?
779<Addi> Where the elements in the lists are the distances and colors of
780the other colors in the palette
781<TonyC> ok
782<Addi> So if you are at color 0
783<Addi> ok - now to search for the closest color when you are creating
784the final image is done like this:
785<Addi> a) pick a random color from the palette
786<Addi> b) calculate the distance to it
787<Addi> c) only check the vectors that are within double the distance
788in the list of the color you picked from the palette.
789<Addi> Does that seem logical?
790<Addi> Lets imagine that we only have grayscale to make an example:
791<Addi> Our palette has 1 4 10 20 as colors.
792<Addi> And we want to quantize the color 11
793<Addi> lets say we picked 10 randomly
794<Addi> the double distance is 2
795<Addi> since abs(10-11)*2 is 2
796<Addi> And the list at vector 10 is this:
797<Addi> [0, 10], [6 4], [9, 1], [10, 20]
798<Addi> so we look at the first one (but not the second one since 6 is
799at a greater distance than 2.
800<Addi> Any of that make sense?
801<TonyC> yes, though are you suggesting another random jump to one of
802the colours with the possible choices? or an exhaustive search?
803<Addi> TonyC: It's possible to come up with a recursive/iterative
804enhancement but this is the 'basic' version.
805<Addi> Which would do an iterative search.
806<Addi> You can come up with conditions where it pays to switch to a new one.
807<Addi> And the 'random' start can be switched over to a small tree.
808<Addi> So you would have a little index at the start.
809<Addi> to get you into the general direction
810<Addi> Perhaps just an 8 split.
811<Addi> that is - split each dimension in half.
812<TonyC> yep
813<TonyC> I get the idea
814<Addi> But this would seem to be a good approach in our case since we
815usually have few codevectors.
816<Addi> So we only need 256*256 entries in a table.
817<Addi> We could even only index some of them that were deemed as good
818candidates.
819<TonyC> I was considering adding paletted output support for PNG and
820TIFF at some point, which support 16-bit palettes
821<Addi> ohh.
822<Addi> 'darn' ;)
823
824
825*/
826
827
828typedef struct i_dists {
829 int index;
830 long dist;
831} i_dists;
832
833#define CF_VARS \
834 i_dists *dists;
835
836static int dists_sort(void const *a, void const *b) {
837 return ((i_dists *)a)->dist - ((i_dists *)b)->dist;
838}
839
840static void rand2dist_setup(i_quantize *quant, i_dists **cdists) {
841 i_dists *dists =
842 mymalloc(sizeof(i_dists)*quant->mc_count*quant->mc_count);
843 int i, j;
844 long cd;
845 for (i = 0; i < quant->mc_count; ++i) {
846 i_dists *ldists = dists + quant->mc_count * i;
847 i_color val = quant->mc_colors[i];
848 for (j = 0; j < quant->mc_count; ++j) {
849 ldists[j].index = j;
850 ldists[j].dist = ceucl_d(&val, quant->mc_colors+j);
851 }
852 qsort(ldists, quant->mc_count, sizeof(i_dists), dists_sort);
853 }
854 *cdists = dists;
855}
856
857#define CF_SETUP \
858 bst_idx = rand() % quant->mc_count; \
859 rand2dist_setup(quant, &dists)
860
861static int rand2dist_find(i_color val, i_quantize *quant, i_dists *dists, int index) {
862 i_dists *cdists;
863 long cd, ld;
864 long maxld;
865 int i;
866 int bst_idx;
867
868 cdists = dists + index * quant->mc_count;
869 ld = 3 * 256 * 256;
870 maxld = 8 * ceucl_d(&val, quant->mc_colors+index);
871 for (i = 0; i < quant->mc_count && cdists[i].dist <= maxld; ++i) {
872 cd = ceucl_d(&val, quant->mc_colors+cdists[i].index);
873 if (cd < ld) {
874 bst_idx = cdists[i].index;
875 ld = cd;
876 }
877 }
878 return bst_idx;
879}
880
881#define CF_FIND bst_idx = rand2dist_find(val, quant, dists, bst_idx)
882
883#define CF_CLEANUP myfree(dists)
884
885
886#endif
887
888static void translate_addi(i_quantize *quant, i_img *img, i_palidx *out) {
889 int x, y, i, k, bst_idx;
890 i_color val;
891 int pixdev = quant->perturb;
892 CF_VARS;
893
894 CF_SETUP;
895
896 if (pixdev) {
897 k=0;
898 for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) {
899 i_gpix(img,x,y,&val);
900 val.channel[0]=g_sat(val.channel[0]+(int)(pixdev*frandn()));
901 val.channel[1]=g_sat(val.channel[1]+(int)(pixdev*frandn()));
902 val.channel[2]=g_sat(val.channel[2]+(int)(pixdev*frandn()));
903 CF_FIND;
904 out[k++]=bst_idx;
905 }
906 } else {
907 k=0;
908 for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) {
909 i_gpix(img,x,y,&val);
910 CF_FIND;
911 out[k++]=bst_idx;
912 }
913 }
914 CF_CLEANUP;
915}
916
917static int floyd_map[] =
918{
919 0, 0, 7,
920 3, 5, 1
921};
922
923static int jarvis_map[] =
924{
925 0, 0, 0, 7, 5,
926 3, 5, 7, 5, 3,
927 1, 3, 5, 3, 1
928};
929
930static int stucki_map[] =
931{
932 0, 0, 0, 8, 4,
933 2, 4, 8, 4, 2,
934 1, 2, 4, 2, 1
935};
936
937struct errdiff_map {
938 int *map;
939 int width, height, orig;
940};
941
942static struct errdiff_map maps[] =
943{
944 { floyd_map, 3, 2, 1 },
945 { jarvis_map, 5, 3, 2 },
946 { stucki_map, 5, 3, 2 },
947};
948
949typedef struct errdiff_tag {
950 int r, g, b;
951} errdiff_t;
952
953/* perform an error diffusion dither */
954static
955void
956translate_errdiff(i_quantize *quant, i_img *img, i_palidx *out) {
957 int *map;
958 int mapw, maph, mapo;
959 int i;
960 errdiff_t *err;
961 int errw;
962 int difftotal;
963 int x, y, dx, dy;
964 int minr, maxr, ming, maxg, minb, maxb, cr, cg, cb;
965 i_color find;
966 int bst_idx;
967 CF_VARS;
968
969 if ((quant->errdiff & ed_mask) == ed_custom) {
970 map = quant->ed_map;
971 mapw = quant->ed_width;
972 maph = quant->ed_height;
973 mapo = quant->ed_orig;
974 }
975 else {
976 int index = quant->errdiff & ed_mask;
977 if (index >= ed_custom) index = ed_floyd;
978 map = maps[index].map;
979 mapw = maps[index].width;
980 maph = maps[index].height;
981 mapo = maps[index].orig;
982 }
983
984 errw = img->xsize+mapw;
985 err = mymalloc(sizeof(*err) * maph * errw);
986 /*errp = err+mapo;*/
987 memset(err, 0, sizeof(*err) * maph * errw);
988
989 difftotal = 0;
990 for (i = 0; i < maph * mapw; ++i)
991 difftotal += map[i];
992 /*printf("map:\n");
993 for (dy = 0; dy < maph; ++dy) {
994 for (dx = 0; dx < mapw; ++dx) {
995 printf("%2d", map[dx+dy*mapw]);
996 }
997 putchar('\n');
998 }*/
999
1000 CF_SETUP;
1001
1002 for (y = 0; y < img->ysize; ++y) {
1003 for (x = 0; x < img->xsize; ++x) {
1004 i_color val;
1005 long ld, cd;
1006 errdiff_t perr;
1007 i_gpix(img, x, y, &val);
1008 perr = err[x+mapo];
1009 perr.r = perr.r < 0 ? -((-perr.r)/difftotal) : perr.r/difftotal;
1010 perr.g = perr.g < 0 ? -((-perr.g)/difftotal) : perr.g/difftotal;
1011 perr.b = perr.b < 0 ? -((-perr.b)/difftotal) : perr.b/difftotal;
1012 /*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);*/
1013 val.channel[0] = g_sat(val.channel[0]-perr.r);
1014 val.channel[1] = g_sat(val.channel[1]-perr.g);
1015 val.channel[2] = g_sat(val.channel[2]-perr.b);
1016 CF_FIND;
1017 /* save error */
1018 perr.r = quant->mc_colors[bst_idx].channel[0] - val.channel[0];
1019 perr.g = quant->mc_colors[bst_idx].channel[1] - val.channel[1];
1020 perr.b = quant->mc_colors[bst_idx].channel[2] - val.channel[2];
1021 /*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);*/
1022 for (dx = 0; dx < mapw; ++dx) {
1023 for (dy = 0; dy < maph; ++dy) {
1024 err[x+dx+dy*errw].r += perr.r * map[dx+mapw*dy];
1025 err[x+dx+dy*errw].g += perr.g * map[dx+mapw*dy];
1026 err[x+dx+dy*errw].b += perr.b * map[dx+mapw*dy];
1027 }
1028 }
1029 *out++ = bst_idx;
1030 }
1031 /* shift up the error matrix */
1032 for (dy = 0; dy < maph-1; ++dy) {
1033 memcpy(err+dy*errw, err+(dy+1)*errw, sizeof(*err)*errw);
1034 }
1035 memset(err+(maph-1)*errw, 0, sizeof(*err)*errw);
1036 }
1037 CF_CLEANUP;
1038}
1039/* Prescan finds the boxes in the image that have the highest number of colors
1040 and that result is used as the initial value for the vectores */
1041
1042
1043static void prescan(i_img **imgs,int count, int cnum, cvec *clr) {
1044 int i,k,j,x,y;
1045 i_color val;
1046
1047 pbox prebox[512];
1048 for(i=0;i<512;i++) {
1049 prebox[i].boxnum=i;
1050 prebox[i].pixcnt=0;
1051 prebox[i].cand=1;
1052 }
1053
1054 /* process each image */
1055 for (i = 0; i < count; ++i) {
1056 i_img *im = imgs[i];
1057 for(y=0;y<im->ysize;y++) for(x=0;x<im->xsize;x++) {
1058 i_gpix(im,x,y,&val);
1059 prebox[pixbox(&val)].pixcnt++;
1060 }
1061 }
1062
1063 for(i=0;i<512;i++) prebox[i].pdc=prebox[i].pixcnt;
1064 qsort(prebox,512,sizeof(pbox),(cmpfunc)pboxcmp);
1065
1066 for(i=0;i<cnum;i++) {
1067 /* printf("Color %d\n",i);
1068 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); }
1069 printf("\n\n"); */
1070 reorder(prebox);
1071 }
1072
1073 /* 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); } */
1074
1075 k=0;
1076 j=1;
1077 i=0;
1078 while(i<cnum) {
1079 /* printf("prebox[%d].cand=%d\n",k,prebox[k].cand); */
36e67d0b 1080 if (clr[i].fixed) { i++; continue; } /* reserved go to next */
02d1d628
AMH
1081 if (j>=prebox[k].cand) { k++; j=1; } else {
1082 if (prebox[k].cand == 2) boxcenter(prebox[k].boxnum,&(clr[i]));
1083 else boxrand(prebox[k].boxnum,&(clr[i]));
1084 /* 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); */
1085 j++;
1086 i++;
1087 }
1088 }
1089}
1090
1091
1092static void reorder(pbox prescan[512]) {
1093 int nidx;
1094 pbox c;
1095
1096 nidx=0;
1097 c=prescan[0];
1098
1099 c.cand++;
1100 c.pdc=c.pixcnt/(c.cand*c.cand);
1101 /* c.pdc=c.pixcnt/c.cand; */
1102 while(c.pdc < prescan[nidx+1].pdc && nidx < 511) {
1103 prescan[nidx]=prescan[nidx+1];
1104 nidx++;
1105 }
1106 prescan[nidx]=c;
1107}
1108
1109static int
1110pboxcmp(const pbox *a,const pbox *b) {
1111 if (a->pixcnt > b->pixcnt) return -1;
1112 if (a->pixcnt < b->pixcnt) return 1;
1113 return 0;
1114}
1115
1116static void
1117boxcenter(int box,cvec *cv) {
1118 cv->r=15+((box&448)>>1);
1119 cv->g=15+((box&56)<<2);
1120 cv->b=15+((box&7)<<5);
1121}
1122
1123static void
1124bbox(int box,int *r0,int *r1,int *g0,int *g1,int *b0,int *b1) {
1125 *r0=(box&448)>>1;
1126 *r1=(*r0)|31;
1127 *g0=(box&56)<<2;
1128 *g1=(*g0)|31;
1129 *b0=(box&7)<<5;
1130 *b1=(*b0)|31;
1131}
1132
1133static void
1134boxrand(int box,cvec *cv) {
1135 cv->r=6+(rand()%25)+((box&448)>>1);
1136 cv->g=6+(rand()%25)+((box&56)<<2);
1137 cv->b=6+(rand()%25)+((box&7)<<5);
1138}
1139
1140static float
1141frandn(void) {
1142
1143 float u1,u2,w;
1144
1145 w=1;
1146
1147 while (w >= 1 || w == 0) {
1148 u1 = 2 * frand() - 1;
1149 u2 = 2 * frand() - 1;
1150 w = u1*u1 + u2*u2;
1151 }
1152
1153 w = sqrt((-2*log(w))/w);
1154 return u1*w;
1155}
1156
1157/* Create hash index */
1158static
1159void
1160cr_hashindex(cvec clr[256],int cnum,hashbox hb[512]) {
1161
1162 int bx,mind,cd,cumcnt,bst_idx,i;
1163/* printf("indexing... \n");*/
1164
1165 cumcnt=0;
1166 for(bx=0; bx<512; bx++) {
1167 mind=196608;
1168 for(i=0; i<cnum; i++) {
1169 cd = maxdist(bx,&clr[i]);
1170 if (cd < mind) { mind=cd; bst_idx=i; }
1171 }
1172
1173 hb[bx].cnt=0;
1174 for(i=0;i<cnum;i++) if (mindist(bx,&clr[i])<mind) hb[bx].vec[hb[bx].cnt++]=i;
1175 /*printf("box %d -> approx -> %d\n",bx,hb[bx].cnt); */
1176 /* statbox(bx,cnum,clr); */
1177 cumcnt+=hb[bx].cnt;
1178 }
1179
1180/* printf("Average search space: %d\n",cumcnt/512); */
1181}
1182
1183static int
1184maxdist(int boxnum,cvec *cv) {
1185 int r0,r1,g0,g1,b0,b1;
1186 int r,g,b,mr,mg,mb;
1187
1188 r=cv->r;
1189 g=cv->g;
1190 b=cv->b;
1191
1192 bbox(boxnum,&r0,&r1,&g0,&g1,&b0,&b1);
1193
1194 mr=max(abs(b-b0),abs(b-b1));
1195 mg=max(abs(g-g0),abs(g-g1));
1196 mb=max(abs(r-r0),abs(r-r1));
1197
1198 return PWR2(mr)+PWR2(mg)+PWR2(mb);
1199}
1200
1201static int
1202mindist(int boxnum,cvec *cv) {
1203 int r0,r1,g0,g1,b0,b1;
1204 int r,g,b,mr,mg,mb;
1205
1206 r=cv->r;
1207 g=cv->g;
1208 b=cv->b;
1209
1210 bbox(boxnum,&r0,&r1,&g0,&g1,&b0,&b1);
1211
1212 /* printf("box %d, (%d,%d,%d)-(%d,%d,%d) vec (%d,%d,%d) ",boxnum,r0,g0,b0,r1,g1,b1,r,g,b); */
1213
1214 if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0;
1215
1216 mr=min(abs(b-b0),abs(b-b1));
1217 mg=min(abs(g-g0),abs(g-g1));
1218 mb=min(abs(r-r0),abs(r-r1));
1219
1220 mr=PWR2(mr);
1221 mg=PWR2(mg);
1222 mb=PWR2(mb);
1223
1224 if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb;
1225 if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg;
1226 if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr;
1227
1228 if (r0<=r && r<=r1) return mg+mb;
1229 if (g0<=g && g<=g1) return mr+mb;
1230 if (b0<=b && b<=b1) return mg+mr;
1231
1232 return mr+mg+mb;
1233}
1234
1235static void transparent_threshold(i_quantize *, i_palidx *, i_img *, i_palidx);
1236static void transparent_errdiff(i_quantize *, i_palidx *, i_img *, i_palidx);
1237static void transparent_ordered(i_quantize *, i_palidx *, i_img *, i_palidx);
1238
1239void quant_transparent(i_quantize *quant, i_palidx *data, i_img *img,
1240 i_palidx trans_index)
1241{
1242 switch (quant->transp) {
1243 case tr_none:
1244 break;
1245
1246 default:
1247 quant->tr_threshold = 128;
1248 /* fall through */
1249 case tr_threshold:
1250 transparent_threshold(quant, data, img, trans_index);
1251 break;
1252
1253 case tr_errdiff:
1254 transparent_errdiff(quant, data, img, trans_index);
1255 break;
1256
1257 case tr_ordered:
1258 transparent_ordered(quant, data, img, trans_index);
1259 break;
1260 }
1261}
1262
1263static void
1264transparent_threshold(i_quantize *quant, i_palidx *data, i_img *img,
1265 i_palidx trans_index)
1266{
1267 int x, y;
1268
1269 for (y = 0; y < img->ysize; ++y) {
1270 for (x = 0; x < img->xsize; ++x) {
1271 i_color val;
1272 i_gpix(img, x, y, &val);
1273 if (val.rgba.a < quant->tr_threshold)
1274 data[y*img->xsize+x] = trans_index;
1275 }
1276 }
1277}
1278
1279static void
1280transparent_errdiff(i_quantize *quant, i_palidx *data, i_img *img,
1281 i_palidx trans_index)
1282{
1283 int *map;
1284 int index;
1285 int mapw, maph, mapo;
1286 int errw, *err, *errp;
1287 int difftotal, out, error;
1288 int x, y, dx, dy, i;
1289
1290 /* no custom map for transparency (yet) */
1291 index = quant->tr_errdiff & ed_mask;
1292 if (index >= ed_custom) index = ed_floyd;
1293 map = maps[index].map;
1294 mapw = maps[index].width;
1295 maph = maps[index].height;
1296 mapo = maps[index].orig;
1297
1298 errw = img->xsize+mapw-1;
1299 err = mymalloc(sizeof(*err) * maph * errw);
1300 errp = err+mapo;
1301 memset(err, 0, sizeof(*err) * maph * errw);
1302
1303 difftotal = 0;
1304 for (i = 0; i < maph * mapw; ++i)
1305 difftotal += map[i];
1306 for (y = 0; y < img->ysize; ++y) {
1307 for (x = 0; x < img->xsize; ++x) {
1308 i_color val;
1309 i_gpix(img, x, y, &val);
1310 val.rgba.a = g_sat(val.rgba.a-errp[x]/difftotal);
1311 if (val.rgba.a < 128) {
1312 out = 0;
1313 data[y*img->xsize+x] = trans_index;
1314 }
1315 else {
1316 out = 255;
1317 }
1318 error = out - val.rgba.a;
1319 for (dx = 0; dx < mapw; ++dx) {
1320 for (dy = 0; dy < maph; ++dy) {
1321 errp[x+dx-mapo+dy*errw] += error * map[dx+mapw*dy];
1322 }
1323 }
1324 }
1325 /* shift up the error matrix */
1326 for (dy = 0; dy < maph-1; ++dy)
1327 memcpy(err+dy*errw, err+(dy+1)*errw, sizeof(*err)*errw);
1328 memset(err+(maph-1)*errw, 0, sizeof(*err)*errw);
1329 }
1330}
1331
1332/* builtin ordered dither maps */
1333unsigned char orddith_maps[][64] =
1334{
1335 { /* random
1336 this is purely random - it's pretty awful
1337 */
1338 48, 72, 196, 252, 180, 92, 108, 52,
1339 228, 176, 64, 8, 236, 40, 20, 164,
1340 120, 128, 84, 116, 24, 28, 172, 220,
1341 68, 0, 188, 124, 184, 224, 192, 104,
1342 132, 100, 240, 200, 152, 160, 244, 44,
1343 96, 204, 144, 16, 140, 56, 232, 216,
1344 208, 4, 76, 212, 136, 248, 80, 168,
1345 156, 88, 32, 112, 148, 12, 36, 60,
1346 },
1347 {
1348 /* dot8
1349 perl spot.perl '($x-3.5)*($x-3.5)+($y-3.5)*($y-3.5)'
1350 */
1351 240, 232, 200, 136, 140, 192, 228, 248,
1352 220, 148, 100, 76, 80, 104, 152, 212,
1353 180, 116, 56, 32, 36, 60, 120, 176,
1354 156, 64, 28, 0, 8, 44, 88, 160,
1355 128, 92, 24, 12, 4, 40, 68, 132,
1356 184, 96, 48, 20, 16, 52, 108, 188,
1357 216, 144, 112, 72, 84, 124, 164, 224,
1358 244, 236, 196, 168, 172, 204, 208, 252,
1359 },
1360 { /* dot4
1361 perl spot.perl \
1362 'min(dist(1.5, 1.5),dist(5.5,1.5),dist(1.5,5.5),dist(5.5,5.5))'
1363 */
1364 196, 72, 104, 220, 200, 80, 112, 224,
1365 76, 4, 24, 136, 84, 8, 32, 144,
1366 108, 28, 52, 168, 116, 36, 56, 176,
1367 216, 140, 172, 244, 228, 148, 180, 248,
1368 204, 92, 124, 236, 192, 68, 96, 208,
1369 88, 12, 44, 156, 64, 0, 16, 128,
1370 120, 40, 60, 188, 100, 20, 48, 160,
1371 232, 152, 184, 252, 212, 132, 164, 240,
1372 },
1373 { /* hline
1374 perl spot.perl '$y-3'
1375 */
1376 160, 164, 168, 172, 176, 180, 184, 188,
1377 128, 132, 136, 140, 144, 148, 152, 156,
1378 32, 36, 40, 44, 48, 52, 56, 60,
1379 0, 4, 8, 12, 16, 20, 24, 28,
1380 64, 68, 72, 76, 80, 84, 88, 92,
1381 96, 100, 104, 108, 112, 116, 120, 124,
1382 192, 196, 200, 204, 208, 212, 216, 220,
1383 224, 228, 232, 236, 240, 244, 248, 252,
1384 },
1385 { /* vline
1386 perl spot.perl '$x-3'
1387 */
1388 180, 100, 40, 12, 44, 104, 184, 232,
1389 204, 148, 60, 16, 64, 128, 208, 224,
1390 212, 144, 76, 8, 80, 132, 216, 244,
1391 160, 112, 68, 20, 84, 108, 172, 236,
1392 176, 96, 72, 28, 88, 152, 188, 228,
1393 200, 124, 92, 0, 32, 116, 164, 240,
1394 168, 120, 36, 24, 48, 136, 192, 248,
1395 196, 140, 52, 4, 56, 156, 220, 252,
1396 },
1397 { /* slashline
1398 perl spot.perl '$y+$x-7'
1399 */
1400 248, 232, 224, 192, 140, 92, 52, 28,
1401 240, 220, 196, 144, 108, 60, 12, 64,
1402 216, 180, 148, 116, 76, 20, 80, 128,
1403 204, 152, 104, 44, 16, 72, 100, 160,
1404 164, 96, 68, 24, 56, 112, 168, 176,
1405 124, 40, 8, 36, 88, 136, 184, 212,
1406 84, 4, 32, 120, 156, 188, 228, 236,
1407 0, 48, 132, 172, 200, 208, 244, 252,
1408 },
1409 { /* backline
1410 perl spot.perl '$y-$x'
1411 */
1412 0, 32, 116, 172, 184, 216, 236, 252,
1413 56, 8, 72, 132, 136, 200, 228, 240,
1414 100, 36, 12, 40, 92, 144, 204, 220,
1415 168, 120, 60, 16, 44, 96, 156, 176,
1416 180, 164, 112, 48, 28, 52, 128, 148,
1417 208, 192, 152, 88, 84, 20, 64, 104,
1418 232, 224, 196, 140, 108, 68, 24, 76,
1419 248, 244, 212, 188, 160, 124, 80, 4,
1420 },
11e7329d
TC
1421 {
1422 /* tiny
1423 good for display, bad for print
1424 hand generated
1425 */
1426 0, 128, 32, 192, 8, 136, 40, 200,
1427 224, 64, 160, 112, 232, 72, 168, 120,
1428 48, 144, 16, 208, 56, 152, 24, 216,
1429 176, 96, 240, 80, 184, 104, 248, 88,
1430 12, 140, 44, 204, 4, 132, 36, 196,
1431 236, 76, 172, 124, 228, 68, 164, 116,
1432 60, 156, 28, 220, 52, 148, 20, 212,
1433 188, 108, 252, 92, 180, 100, 244, 84,
1434 },
02d1d628
AMH
1435};
1436
1437static void
1438transparent_ordered(i_quantize *quant, i_palidx *data, i_img *img,
1439 i_palidx trans_index)
1440{
1441 unsigned char *spot;
1442 int x, y;
1443 if (quant->tr_orddith == od_custom)
1444 spot = quant->tr_custom;
1445 else
1446 spot = orddith_maps[quant->tr_orddith];
1447 for (y = 0; y < img->ysize; ++y) {
1448 for (x = 0; x < img->xsize; ++x) {
1449 i_color val;
1450 i_gpix(img, x, y, &val);
1451 if (val.rgba.a < spot[(x&7)+(y&7)*8])
1452 data[x+y*img->xsize] = trans_index;
1453 }
1454 }
1455}