7 static int im_check_for_small_amount_of_colors(PICINFO
& pic
, int max_colors
,
10 unsigned long colors
[256],color
;
19 for (i
=pic
.w
*pic
.h
,p
=pic
.pic
; i
>0; i
--)
21 //construct RGB 24 bit color
22 color
= (((u_long
) *p
++) << 16);
23 color
+= (((u_long
) *p
++) << 8);
26 for(j
=0;j
<num_color
;j
++)
30 if(j
<num_color
) //We found color -> goto next pixel
33 if (num_color
>= max_colors
)
36 colors
[num_color
++]=color
;
40 //Now convert pixmap with our pallete
41 for (i
=pic
.w
*pic
.h
,p
=pic
.pic
,pix
=pic8_buf
; i
>0; i
--,pix
++)
43 color
= (((u_long
) *p
++) << 16);
44 color
+= (((u_long
) *p
++) << 8);
47 for(j
=0;j
<num_color
;j
++)
56 for (i
=0; i
<num_color
; i
++) {
57 pic
.pal
[i
*3] = colors
[i
]>>16;
58 pic
.pal
[i
*3+1] = (colors
[i
]>>8) & 0xff;
59 pic
.pal
[i
*3+2] = colors
[i
] & 0xff;
67 static int slow_quant(byte
* pic24
, int w
, int h
, byte
* pic8
,
68 byte
* rm
,byte
*gm
,byte
*bm
, int max_colors
);
70 static int im_do_convertion_to_num_colors(PICINFO
& pic
, int max_colors
,
73 byte
*redmap
,*greenmap
,*bluemap
;
76 redmap
= new byte
[256];
77 greenmap
= new byte
[256];
78 bluemap
= new byte
[256];
80 slow_quant(pic
.pic
,pic
.w
,pic
.h
,pic8_buf
,
81 redmap
, greenmap
, bluemap
, max_colors
);
83 for(i
=0;i
<max_colors
;i
++)
85 pic
.pal
[i
*3] =redmap
[i
];
86 pic
.pal
[i
*3+1]=greenmap
[i
];
87 pic
.pal
[i
*3+2]=bluemap
[i
];
98 int im_convert_true_to_pseudo(PICINFO
& pic
,int max_colors
)
101 byte
*pic8_buf
,*pic24_buf
;
102 pic8_buf
= new byte
[pic
.w
*pic
.h
];
105 if(im_check_for_small_amount_of_colors(pic
,max_colors
,pic8_buf
))
110 ret
=im_do_convertion_to_num_colors(pic
,max_colors
,pic8_buf
);
120 /////////////////////////////////////////////////////////////////////////
121 /////////////////////////////////////////////////////////////////////////
123 /***************************************************************/
124 /* The following is based on jquant2.c from version 5 */
125 /* of the IJG JPEG software, which is */
126 /* Copyright (C) 1991-1994, Thomas G. Lane. */
127 /***************************************************************/
130 #define MAXNUMCOLORS 256 /* maximum size of colormap */
132 #define C0_SCALE 2 /* scale R distances by this much */
133 #define C1_SCALE 3 /* scale G distances by this much */
134 #define C2_SCALE 1 /* and B by this much */
136 #define HIST_C0_BITS 5 /* bits of precision in R histogram */
137 #define HIST_C1_BITS 6 /* bits of precision in G histogram */
138 #define HIST_C2_BITS 5 /* bits of precision in B histogram */
140 /* Number of elements along histogram axes. */
141 #define HIST_C0_ELEMS (1<<HIST_C0_BITS)
142 #define HIST_C1_ELEMS (1<<HIST_C1_BITS)
143 #define HIST_C2_ELEMS (1<<HIST_C2_BITS)
145 /* These are the amounts to shift an input value to get a histogram index. */
146 #define C0_SHIFT (8-HIST_C0_BITS)
147 #define C1_SHIFT (8-HIST_C1_BITS)
148 #define C2_SHIFT (8-HIST_C2_BITS)
151 typedef unsigned char JSAMPLE
;
152 typedef JSAMPLE
* JSAMPROW
;
154 typedef u_short histcell
; /* histogram cell; prefer an unsigned type */
156 typedef histcell
* histptr
; /* for pointers to histogram cells */
158 typedef histcell hist1d
[HIST_C2_ELEMS
]; /* typedefs for the histogram array */
159 typedef hist1d hist2d
[HIST_C1_ELEMS
];
160 typedef hist2d hist3d
[HIST_C0_ELEMS
];
162 typedef short FSERROR
; /* 16 bits should be enough */
163 typedef int LOCFSERROR
; /* use 'int' for calculation temps */
165 typedef FSERROR
*FSERRPTR
; /* pointer to error array */
169 /* The bounds of the box (inclusive); expressed as histogram indexes */
173 /* The volume (actually 2-norm) of the box */
175 /* The number of nonzero histogram cells within this box */
178 typedef box
* boxptr
;
180 /* Local state for the IJG quantizer */
182 static hist2d
* sl_histogram
; /* pointer to the 3D histogram array */
183 static FSERRPTR sl_fserrors
; /* accumulated-errors array */
184 static int * sl_error_limiter
; /* table for clamping the applied error */
185 static int sl_on_odd_row
; /* flag to remember which row we are on */
186 static JSAMPROW sl_colormap
[3]; /* selected colormap */
187 static int sl_num_colors
; /* number of selected colors */
190 static void slow_fill_histogram (byte
*, int);
191 static boxptr
find_biggest_color_pop (boxptr
, int);
192 static boxptr
find_biggest_volume (boxptr
, int);
193 static void update_box (boxptr
);
194 static int median_cut (boxptr
, int, int);
195 static void compute_color (boxptr
, int);
196 static void slow_select_colors (int);
197 static int find_nearby_colors (int, int, int, JSAMPLE
[]);
198 static void find_best_colors (int,int,int,int, JSAMPLE
[], JSAMPLE
[]);
199 static void fill_inverse_cmap (int, int, int);
200 static void slow_map_pixels (byte
*, int, int, byte
*);
201 static void init_error_limit(void);
204 /* Master control for slow quantizer. */
205 static int slow_quant(byte
* pic24
, int w
, int h
, byte
* pic8
,
206 byte
* rm
,byte
*gm
,byte
*bm
, int max_colors
)
208 size_t fs_arraysize
= (w
+ 2) * (3 * sizeof(FSERROR
));
210 /* Allocate all the temporary storage needed */
211 if (sl_error_limiter
== NULL
)
213 sl_histogram
= (hist2d
*) malloc(sizeof(hist3d
));
214 sl_fserrors
= (FSERRPTR
) malloc(fs_arraysize
);
216 if (! sl_error_limiter
|| ! sl_histogram
|| ! sl_fserrors
) {
217 /* we never free sl_error_limiter once acquired */
218 if (sl_histogram
) free(sl_histogram
);
219 if (sl_fserrors
) free(sl_fserrors
);
220 fprintf(stderr
,"Slow_quant() - failed to allocate workspace\n");
224 sl_colormap
[0] = (JSAMPROW
) rm
;
225 sl_colormap
[1] = (JSAMPROW
) gm
;
226 sl_colormap
[2] = (JSAMPROW
) bm
;
228 /* Compute the color histogram */
229 slow_fill_histogram(pic24
, w
*h
);
231 /* Select the colormap */
232 slow_select_colors(max_colors
);
234 /* Zero the histogram: now to be used as inverse color map */
235 im_setzero((char *) sl_histogram
, sizeof(hist3d
));
237 /* Initialize the propagated errors to zero. */
238 im_setzero((char *) sl_fserrors
, fs_arraysize
);
239 sl_on_odd_row
= FALSE
;
242 slow_map_pixels(pic24
, w
, h
, pic8
);
244 /* Release working memory. */
245 /* we never free sl_error_limiter once acquired */
253 static void slow_fill_histogram (byte
* pic24
,int numpixels
)
256 hist2d
* histogram
= sl_histogram
;
258 im_setzero((char *) histogram
, sizeof(hist3d
));
260 while (numpixels
-- > 0)
262 /* get pixel value and index into the histogram */
263 histp
= & histogram
[pic24
[0] >> C0_SHIFT
]
264 [pic24
[1] >> C1_SHIFT
]
265 [pic24
[2] >> C2_SHIFT
];
266 /* increment, check for overflow and undo increment if so. */
274 static boxptr
find_biggest_color_pop (boxptr boxlist
, int numboxes
)
276 register boxptr boxp
;
278 register long maxc
= 0;
281 for (i
= 0, boxp
= boxlist
; i
< numboxes
; i
++, boxp
++) {
282 if (boxp
->colorcount
> maxc
&& boxp
->volume
> 0) {
284 maxc
= boxp
->colorcount
;
291 static boxptr
find_biggest_volume (boxptr boxlist
, int numboxes
)
293 register boxptr boxp
;
295 register INT32 maxv
= 0;
298 for (i
= 0, boxp
= boxlist
; i
< numboxes
; i
++, boxp
++) {
299 if (boxp
->volume
> maxv
) {
308 static void update_box (boxptr boxp
)
310 hist2d
* histogram
= sl_histogram
;
313 int c0min
,c0max
,c1min
,c1max
,c2min
,c2max
;
314 INT32 dist0
,dist1
,dist2
;
317 c0min
= boxp
->c0min
; c0max
= boxp
->c0max
;
318 c1min
= boxp
->c1min
; c1max
= boxp
->c1max
;
319 c2min
= boxp
->c2min
; c2max
= boxp
->c2max
;
322 for (c0
= c0min
; c0
<= c0max
; c0
++)
323 for (c1
= c1min
; c1
<= c1max
; c1
++) {
324 histp
= & histogram
[c0
][c1
][c2min
];
325 for (c2
= c2min
; c2
<= c2max
; c2
++)
327 boxp
->c0min
= c0min
= c0
;
333 for (c0
= c0max
; c0
>= c0min
; c0
--)
334 for (c1
= c1min
; c1
<= c1max
; c1
++) {
335 histp
= & histogram
[c0
][c1
][c2min
];
336 for (c2
= c2min
; c2
<= c2max
; c2
++)
338 boxp
->c0max
= c0max
= c0
;
344 for (c1
= c1min
; c1
<= c1max
; c1
++)
345 for (c0
= c0min
; c0
<= c0max
; c0
++) {
346 histp
= & histogram
[c0
][c1
][c2min
];
347 for (c2
= c2min
; c2
<= c2max
; c2
++)
349 boxp
->c1min
= c1min
= c1
;
355 for (c1
= c1max
; c1
>= c1min
; c1
--)
356 for (c0
= c0min
; c0
<= c0max
; c0
++) {
357 histp
= & histogram
[c0
][c1
][c2min
];
358 for (c2
= c2min
; c2
<= c2max
; c2
++)
360 boxp
->c1max
= c1max
= c1
;
366 for (c2
= c2min
; c2
<= c2max
; c2
++)
367 for (c0
= c0min
; c0
<= c0max
; c0
++) {
368 histp
= & histogram
[c0
][c1min
][c2
];
369 for (c1
= c1min
; c1
<= c1max
; c1
++, histp
+= HIST_C2_ELEMS
)
371 boxp
->c2min
= c2min
= c2
;
377 for (c2
= c2max
; c2
>= c2min
; c2
--)
378 for (c0
= c0min
; c0
<= c0max
; c0
++) {
379 histp
= & histogram
[c0
][c1min
][c2
];
380 for (c1
= c1min
; c1
<= c1max
; c1
++, histp
+= HIST_C2_ELEMS
)
382 boxp
->c2max
= c2max
= c2
;
388 dist0
= ((c0max
- c0min
) << C0_SHIFT
) * C0_SCALE
;
389 dist1
= ((c1max
- c1min
) << C1_SHIFT
) * C1_SCALE
;
390 dist2
= ((c2max
- c2min
) << C2_SHIFT
) * C2_SCALE
;
391 boxp
->volume
= dist0
*dist0
+ dist1
*dist1
+ dist2
*dist2
;
394 for (c0
= c0min
; c0
<= c0max
; c0
++)
395 for (c1
= c1min
; c1
<= c1max
; c1
++) {
396 histp
= & histogram
[c0
][c1
][c2min
];
397 for (c2
= c2min
; c2
<= c2max
; c2
++, histp
++)
402 boxp
->colorcount
= ccount
;
406 static int median_cut (boxptr boxlist
, int numboxes
, int desired_colors
)
410 register boxptr b1
,b2
;
412 while (numboxes
< desired_colors
) {
413 /* Select box to split.
414 * Current algorithm: by population for first half, then by volume.
416 if (numboxes
*2 <= desired_colors
) {
417 b1
= find_biggest_color_pop(boxlist
, numboxes
);
419 b1
= find_biggest_volume(boxlist
, numboxes
);
421 if (b1
== NULL
) /* no splittable boxes left! */
423 b2
= &boxlist
[numboxes
]; /* where new box will go */
424 /* Copy the color bounds to the new box. */
425 b2
->c0max
= b1
->c0max
; b2
->c1max
= b1
->c1max
; b2
->c2max
= b1
->c2max
;
426 b2
->c0min
= b1
->c0min
; b2
->c1min
= b1
->c1min
; b2
->c2min
= b1
->c2min
;
427 /* Choose which axis to split the box on.
429 c0
= ((b1
->c0max
- b1
->c0min
) << C0_SHIFT
) * C0_SCALE
;
430 c1
= ((b1
->c1max
- b1
->c1min
) << C1_SHIFT
) * C1_SCALE
;
431 c2
= ((b1
->c2max
- b1
->c2min
) << C2_SHIFT
) * C2_SCALE
;
433 if (c0
> cmax
) { cmax
= c0
; n
= 0; }
434 if (c2
> cmax
) { n
= 2; }
437 lb
= (b1
->c0max
+ b1
->c0min
) / 2;
442 lb
= (b1
->c1max
+ b1
->c1min
) / 2;
447 lb
= (b1
->c2max
+ b1
->c2min
) / 2;
452 /* Update stats for boxes */
461 static void compute_color (boxptr boxp
,int icolor
)
463 /* Current algorithm: mean weighted by pixels (not colors) */
464 /* Note it is important to get the rounding correct! */
465 hist2d
* histogram
= sl_histogram
;
468 int c0min
,c0max
,c1min
,c1max
,c2min
,c2max
;
475 c0min
= boxp
->c0min
; c0max
= boxp
->c0max
;
476 c1min
= boxp
->c1min
; c1max
= boxp
->c1max
;
477 c2min
= boxp
->c2min
; c2max
= boxp
->c2max
;
479 for (c0
= c0min
; c0
<= c0max
; c0
++)
480 for (c1
= c1min
; c1
<= c1max
; c1
++) {
481 histp
= & histogram
[c0
][c1
][c2min
];
482 for (c2
= c2min
; c2
<= c2max
; c2
++) {
483 if ((count
= *histp
++) != 0) {
485 c0total
+= ((c0
<< C0_SHIFT
) + ((1<<C0_SHIFT
)>>1)) * count
;
486 c1total
+= ((c1
<< C1_SHIFT
) + ((1<<C1_SHIFT
)>>1)) * count
;
487 c2total
+= ((c2
<< C2_SHIFT
) + ((1<<C2_SHIFT
)>>1)) * count
;
492 sl_colormap
[0][icolor
] = (JSAMPLE
) ((c0total
+ (total
>>1)) / total
);
493 sl_colormap
[1][icolor
] = (JSAMPLE
) ((c1total
+ (total
>>1)) / total
);
494 sl_colormap
[2][icolor
] = (JSAMPLE
) ((c2total
+ (total
>>1)) / total
);
498 static void slow_select_colors (int descolors
)
499 /* Master routine for color selection */
501 box boxlist
[MAXNUMCOLORS
];
505 /* Initialize one box containing whole space */
507 boxlist
[0].c0min
= 0;
508 boxlist
[0].c0max
= 255 >> C0_SHIFT
;
509 boxlist
[0].c1min
= 0;
510 boxlist
[0].c1max
= 255 >> C1_SHIFT
;
511 boxlist
[0].c2min
= 0;
512 boxlist
[0].c2max
= 255 >> C2_SHIFT
;
513 /* Shrink it to actually-used volume and set its statistics */
514 update_box(& boxlist
[0]);
515 /* Perform median-cut to produce final box list */
516 numboxes
= median_cut(boxlist
, numboxes
, descolors
);
517 /* Compute the representative color for each box, fill colormap */
518 for (i
= 0; i
< numboxes
; i
++)
519 compute_color(& boxlist
[i
], i
);
520 sl_num_colors
= numboxes
;
524 /* log2(histogram cells in update box) for each axis; this can be adjusted */
525 #define BOX_C0_LOG (HIST_C0_BITS-3)
526 #define BOX_C1_LOG (HIST_C1_BITS-3)
527 #define BOX_C2_LOG (HIST_C2_BITS-3)
529 #define BOX_C0_ELEMS (1<<BOX_C0_LOG) /* # of hist cells in update box */
530 #define BOX_C1_ELEMS (1<<BOX_C1_LOG)
531 #define BOX_C2_ELEMS (1<<BOX_C2_LOG)
533 #define BOX_C0_SHIFT (C0_SHIFT + BOX_C0_LOG)
534 #define BOX_C1_SHIFT (C1_SHIFT + BOX_C1_LOG)
535 #define BOX_C2_SHIFT (C2_SHIFT + BOX_C2_LOG)
538 static int find_nearby_colors (int minc0
, int minc1
, int minc2
,
541 int numcolors
= sl_num_colors
;
542 int maxc0
, maxc1
, maxc2
;
543 int centerc0
, centerc1
, centerc2
;
545 INT32 minmaxdist
, min_dist
, max_dist
, tdist
;
546 INT32 mindist
[MAXNUMCOLORS
]; /* min distance to colormap entry i */
548 maxc0
= minc0
+ ((1 << BOX_C0_SHIFT
) - (1 << C0_SHIFT
));
549 centerc0
= (minc0
+ maxc0
) >> 1;
550 maxc1
= minc1
+ ((1 << BOX_C1_SHIFT
) - (1 << C1_SHIFT
));
551 centerc1
= (minc1
+ maxc1
) >> 1;
552 maxc2
= minc2
+ ((1 << BOX_C2_SHIFT
) - (1 << C2_SHIFT
));
553 centerc2
= (minc2
+ maxc2
) >> 1;
555 minmaxdist
= 0x7FFFFFFFL
;
557 for (i
= 0; i
< numcolors
; i
++) {
558 /* We compute the squared-c0-distance term, then add in the other two. */
559 x
= sl_colormap
[0][i
];
561 tdist
= (x
- minc0
) * C0_SCALE
;
562 min_dist
= tdist
*tdist
;
563 tdist
= (x
- maxc0
) * C0_SCALE
;
564 max_dist
= tdist
*tdist
;
565 } else if (x
> maxc0
) {
566 tdist
= (x
- maxc0
) * C0_SCALE
;
567 min_dist
= tdist
*tdist
;
568 tdist
= (x
- minc0
) * C0_SCALE
;
569 max_dist
= tdist
*tdist
;
571 /* within cell range so no contribution to min_dist */
574 tdist
= (x
- maxc0
) * C0_SCALE
;
575 max_dist
= tdist
*tdist
;
577 tdist
= (x
- minc0
) * C0_SCALE
;
578 max_dist
= tdist
*tdist
;
582 x
= sl_colormap
[1][i
];
584 tdist
= (x
- minc1
) * C1_SCALE
;
585 min_dist
+= tdist
*tdist
;
586 tdist
= (x
- maxc1
) * C1_SCALE
;
587 max_dist
+= tdist
*tdist
;
588 } else if (x
> maxc1
) {
589 tdist
= (x
- maxc1
) * C1_SCALE
;
590 min_dist
+= tdist
*tdist
;
591 tdist
= (x
- minc1
) * C1_SCALE
;
592 max_dist
+= tdist
*tdist
;
594 /* within cell range so no contribution to min_dist */
596 tdist
= (x
- maxc1
) * C1_SCALE
;
597 max_dist
+= tdist
*tdist
;
599 tdist
= (x
- minc1
) * C1_SCALE
;
600 max_dist
+= tdist
*tdist
;
604 x
= sl_colormap
[2][i
];
606 tdist
= (x
- minc2
) * C2_SCALE
;
607 min_dist
+= tdist
*tdist
;
608 tdist
= (x
- maxc2
) * C2_SCALE
;
609 max_dist
+= tdist
*tdist
;
610 } else if (x
> maxc2
) {
611 tdist
= (x
- maxc2
) * C2_SCALE
;
612 min_dist
+= tdist
*tdist
;
613 tdist
= (x
- minc2
) * C2_SCALE
;
614 max_dist
+= tdist
*tdist
;
616 /* within cell range so no contribution to min_dist */
618 tdist
= (x
- maxc2
) * C2_SCALE
;
619 max_dist
+= tdist
*tdist
;
621 tdist
= (x
- minc2
) * C2_SCALE
;
622 max_dist
+= tdist
*tdist
;
626 mindist
[i
] = min_dist
; /* save away the results */
627 if (max_dist
< minmaxdist
)
628 minmaxdist
= max_dist
;
632 for (i
= 0; i
< numcolors
; i
++) {
633 if (mindist
[i
] <= minmaxdist
)
634 colorlist
[ncolors
++] = (JSAMPLE
) i
;
640 static void find_best_colors (int minc0
,int minc1
,int minc2
,int numcolors
,
641 JSAMPLE colorlist
[], JSAMPLE bestcolor
[])
645 register INT32
* bptr
; /* pointer into bestdist[] array */
646 JSAMPLE
* cptr
; /* pointer into bestcolor[] array */
647 INT32 dist0
, dist1
; /* initial distance values */
648 register INT32 dist2
; /* current distance in inner loop */
649 INT32 xx0
, xx1
; /* distance increments */
651 INT32 inc0
, inc1
, inc2
; /* initial values for increments */
652 /* This array holds the distance to the nearest-so-far color for each cell */
653 INT32 bestdist
[BOX_C0_ELEMS
* BOX_C1_ELEMS
* BOX_C2_ELEMS
];
655 /* Initialize best-distance for each cell of the update box */
657 for (i
= BOX_C0_ELEMS
*BOX_C1_ELEMS
*BOX_C2_ELEMS
-1; i
>= 0; i
--)
658 *bptr
++ = 0x7FFFFFFFL
;
660 /* Nominal steps between cell centers ("x" in Thomas article) */
661 #define STEP_C0 ((1 << C0_SHIFT) * C0_SCALE)
662 #define STEP_C1 ((1 << C1_SHIFT) * C1_SCALE)
663 #define STEP_C2 ((1 << C2_SHIFT) * C2_SCALE)
665 for (i
= 0; i
< numcolors
; i
++) {
666 icolor
= colorlist
[i
];
667 /* Compute (square of) distance from minc0/c1/c2 to this color */
668 inc0
= (minc0
- (int) sl_colormap
[0][icolor
]) * C0_SCALE
;
670 inc1
= (minc1
- (int) sl_colormap
[1][icolor
]) * C1_SCALE
;
672 inc2
= (minc2
- (int) sl_colormap
[2][icolor
]) * C2_SCALE
;
674 /* Form the initial difference increments */
675 inc0
= inc0
* (2 * STEP_C0
) + STEP_C0
* STEP_C0
;
676 inc1
= inc1
* (2 * STEP_C1
) + STEP_C1
* STEP_C1
;
677 inc2
= inc2
* (2 * STEP_C2
) + STEP_C2
* STEP_C2
;
678 /* Now loop over all cells in box, updating distance per Thomas method */
682 for (ic0
= BOX_C0_ELEMS
-1; ic0
>= 0; ic0
--) {
685 for (ic1
= BOX_C1_ELEMS
-1; ic1
>= 0; ic1
--) {
688 for (ic2
= BOX_C2_ELEMS
-1; ic2
>= 0; ic2
--) {
691 *cptr
= (JSAMPLE
) icolor
;
694 xx2
+= 2 * STEP_C2
* STEP_C2
;
699 xx1
+= 2 * STEP_C1
* STEP_C1
;
702 xx0
+= 2 * STEP_C0
* STEP_C0
;
708 static void fill_inverse_cmap (int c0
, int c1
, int c2
)
710 hist2d
* histogram
= sl_histogram
;
711 int minc0
, minc1
, minc2
; /* lower left corner of update box */
713 register JSAMPLE
* cptr
; /* pointer into bestcolor[] array */
714 register histptr cachep
; /* pointer into main cache array */
715 /* This array lists the candidate colormap indexes. */
716 JSAMPLE colorlist
[MAXNUMCOLORS
];
717 int numcolors
; /* number of candidate colors */
718 /* This array holds the actually closest colormap index for each cell. */
719 JSAMPLE bestcolor
[BOX_C0_ELEMS
* BOX_C1_ELEMS
* BOX_C2_ELEMS
];
721 /* Convert cell coordinates to update box ID */
726 minc0
= (c0
<< BOX_C0_SHIFT
) + ((1 << C0_SHIFT
) >> 1);
727 minc1
= (c1
<< BOX_C1_SHIFT
) + ((1 << C1_SHIFT
) >> 1);
728 minc2
= (c2
<< BOX_C2_SHIFT
) + ((1 << C2_SHIFT
) >> 1);
730 numcolors
= find_nearby_colors(minc0
, minc1
, minc2
, colorlist
);
732 /* Determine the actually nearest colors. */
733 find_best_colors(minc0
, minc1
, minc2
, numcolors
, colorlist
, bestcolor
);
735 /* Save the best color numbers (plus 1) in the main cache array */
736 c0
<<= BOX_C0_LOG
; /* convert ID back to base cell indexes */
740 for (ic0
= 0; ic0
< BOX_C0_ELEMS
; ic0
++) {
741 for (ic1
= 0; ic1
< BOX_C1_ELEMS
; ic1
++) {
742 cachep
= & histogram
[c0
+ic0
][c1
+ic1
][c2
];
743 for (ic2
= 0; ic2
< BOX_C2_ELEMS
; ic2
++) {
744 *cachep
++ = (histcell
) (*cptr
++ + 1);
750 static void slow_map_pixels (byte
*pic24
,int width
,int height
, byte
* pic8
)
752 register LOCFSERROR cur0
, cur1
, cur2
; /* current error or pixel value */
753 LOCFSERROR belowerr0
, belowerr1
, belowerr2
; /* error for pixel below cur */
754 LOCFSERROR bpreverr0
, bpreverr1
, bpreverr2
; /* error for below/prev col */
755 register FSERRPTR errorptr
; /* => fserrors[] at column before current */
756 JSAMPROW inptr
; /* => current input pixel */
757 JSAMPROW outptr
; /* => current output pixel */
759 int dir
; /* +1 or -1 depending on direction */
760 int dir3
; /* 3*dir, for advancing inptr & errorptr */
762 int *error_limit
= sl_error_limiter
;
763 JSAMPROW colormap0
= sl_colormap
[0];
764 JSAMPROW colormap1
= sl_colormap
[1];
765 JSAMPROW colormap2
= sl_colormap
[2];
766 hist2d
* histogram
= sl_histogram
;
768 for (row
= 0; row
< height
; row
++) {
770 /* if ((row&0x3f) == 0) WaitCursor();
771 ProgressMeter(0, height-1, row, "Dither");*/
773 inptr
= & pic24
[row
* width
* 3];
774 outptr
= & pic8
[row
* width
];
776 /* work right to left in this row */
777 inptr
+= (width
-1) * 3; /* so point to rightmost pixel */
781 errorptr
= sl_fserrors
+ (width
+1)*3; /* => entry after last column */
782 sl_on_odd_row
= FALSE
; /* flip for next time */
784 /* work left to right in this row */
787 errorptr
= sl_fserrors
; /* => entry before first real column */
788 sl_on_odd_row
= TRUE
; /* flip for next time */
790 /* Preset error values: no error propagated to first pixel from left */
791 cur0
= cur1
= cur2
= 0;
792 /* and no error propagated to row below yet */
793 belowerr0
= belowerr1
= belowerr2
= 0;
794 bpreverr0
= bpreverr1
= bpreverr2
= 0;
796 for (col
= width
; col
> 0; col
--)
798 cur0
= (cur0
+ errorptr
[dir3
+0] + 8) >> 4;
799 cur1
= (cur1
+ errorptr
[dir3
+1] + 8) >> 4;
800 cur2
= (cur2
+ errorptr
[dir3
+2] + 8) >> 4;
801 cur0
= error_limit
[cur0
];
802 cur1
= error_limit
[cur1
];
803 cur2
= error_limit
[cur2
];
810 /* Index into the cache with adjusted pixel value */
811 cachep
= & histogram
[cur0
>>C0_SHIFT
][cur1
>>C1_SHIFT
][cur2
>>C2_SHIFT
];
812 /* If we have not seen this color before, find nearest colormap */
813 /* entry and update the cache */
815 fill_inverse_cmap(cur0
>>C0_SHIFT
, cur1
>>C1_SHIFT
, cur2
>>C2_SHIFT
);
816 /* Now emit the colormap index for this cell */
817 { register int pixcode
= *cachep
- 1;
818 *outptr
= (JSAMPLE
) pixcode
;
819 /* Compute representation error for this pixel */
820 cur0
-= (int) colormap0
[pixcode
];
821 cur1
-= (int) colormap1
[pixcode
];
822 cur2
-= (int) colormap2
[pixcode
];
824 /* Compute error fractions to be propagated to adjacent pixels.
825 * Add these into the running sums, and simultaneously shift the
826 * next-line error sums left by 1 column.
828 { register LOCFSERROR bnexterr
, delta
;
830 bnexterr
= cur0
; /* Process component 0 */
832 cur0
+= delta
; /* form error * 3 */
833 errorptr
[0] = (FSERROR
) (bpreverr0
+ cur0
);
834 cur0
+= delta
; /* form error * 5 */
835 bpreverr0
= belowerr0
+ cur0
;
836 belowerr0
= bnexterr
;
837 cur0
+= delta
; /* form error * 7 */
838 bnexterr
= cur1
; /* Process component 1 */
840 cur1
+= delta
; /* form error * 3 */
841 errorptr
[1] = (FSERROR
) (bpreverr1
+ cur1
);
842 cur1
+= delta
; /* form error * 5 */
843 bpreverr1
= belowerr1
+ cur1
;
844 belowerr1
= bnexterr
;
845 cur1
+= delta
; /* form error * 7 */
846 bnexterr
= cur2
; /* Process component 2 */
848 cur2
+= delta
; /* form error * 3 */
849 errorptr
[2] = (FSERROR
) (bpreverr2
+ cur2
);
850 cur2
+= delta
; /* form error * 5 */
851 bpreverr2
= belowerr2
+ cur2
;
852 belowerr2
= bnexterr
;
853 cur2
+= delta
; /* form error * 7 */
855 /* At this point curN contains the 7/16 error value to be propagated
856 * to the next pixel on the current line, and all the errors for the
857 * next line have been shifted over. We are therefore ready to move on.
859 inptr
+= dir3
; /* Advance pixel pointers to next column */
861 errorptr
+= dir3
; /* advance errorptr to current column */
863 /* Post-loop cleanup: we must unload the final error values into the
864 * final fserrors[] entry. Note we need not unload belowerrN because
865 * it is for the dummy column before or after the actual array.
867 errorptr
[0] = (FSERROR
) bpreverr0
; /* unload prev errs into array */
868 errorptr
[1] = (FSERROR
) bpreverr1
;
869 errorptr
[2] = (FSERROR
) bpreverr2
;
874 static void init_error_limit ()
875 /* Allocate and fill in the error_limiter table */
876 /* Note this should be done only once. */
881 table
= (int *) malloc((size_t) ((255*2+1) * sizeof(int)));
884 table
+= 255; /* so can index -255 .. +255 */
885 sl_error_limiter
= table
;
887 #define STEPSIZE ((255+1)/16)
888 /* Map errors 1:1 up to +- 255/16 */
890 for (in
= 0; in
< STEPSIZE
; in
++, out
++) {
891 table
[in
] = out
; table
[-in
] = -out
;
893 /* Map errors 1:2 up to +- 3*255/16 */
894 for (; in
< STEPSIZE
*3; in
++, out
+= (in
&1) ? 0 : 1) {
895 table
[in
] = out
; table
[-in
] = -out
;
897 /* Clamp the rest to final out value (which is (255+1)/8) */
898 for (; in
<= 255; in
++) {
899 table
[in
] = out
; table
[-in
] = -out
;