"Fossies" - the Fresh Open Source Software Archive 
Member "xearth-1.1/dither.c" (7 Nov 1999, 12531 Bytes) of package /linux/misc/old/xearth-1.1.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
1 /*
2 * dither.c
3 * kirk johnson
4 * july 1993
5 *
6 * Copyright (C) 1989, 1990, 1993-1995, 1999 Kirk Lauritz Johnson
7 *
8 * Parts of the source code (as marked) are:
9 * Copyright (C) 1989, 1990, 1991 by Jim Frost
10 * Copyright (C) 1992 by Jamie Zawinski <jwz@lucid.com>
11 *
12 * Permission to use, copy, modify and freely distribute xearth for
13 * non-commercial and not-for-profit purposes is hereby granted
14 * without fee, provided that both the above copyright notice and this
15 * permission notice appear in all copies and in supporting
16 * documentation.
17 *
18 * Unisys Corporation holds worldwide patent rights on the Lempel Zev
19 * Welch (LZW) compression technique employed in the CompuServe GIF
20 * image file format as well as in other formats. Unisys has made it
21 * clear, however, that it does not require licensing or fees to be
22 * paid for freely distributed, non-commercial applications (such as
23 * xearth) that employ LZW/GIF technology. Those wishing further
24 * information about licensing the LZW patent should contact Unisys
25 * directly at (lzw_info@unisys.com) or by writing to
26 *
27 * Unisys Corporation
28 * Welch Licensing Department
29 * M/S-C1SW19
30 * P.O. Box 500
31 * Blue Bell, PA 19424
32 *
33 * The author makes no representations about the suitability of this
34 * software for any purpose. It is provided "as is" without express or
35 * implied warranty.
36 *
37 * THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
38 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS,
39 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, INDIRECT
40 * OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
41 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
42 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
43 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
44 */
45
46 #include "xearth.h"
47 #include "kljcpyrt.h"
48
49 static void dither_row_ltor _P((u_char *, u16or32 *));
50 static void dither_row_rtol _P((u_char *, u16or32 *));
51 static void mono_dither_row_ltor _P((u16or32 *));
52 static void mono_dither_row_rtol _P((u16or32 *));
53
54 static u_char *level;
55 static u_short grn_idx[256];
56 static u_short blu_idx[256];
57 static s16or32 *curr;
58 static s16or32 *next;
59 static int even_row;
60
61 int dither_ncolors;
62 u_char *dither_colormap;
63
64
65 void dither_setup(ncolors)
66 int ncolors;
67 {
68 int i;
69 int val;
70 int half;
71 unsigned nbytes;
72
73 half = (ncolors - 2) / 2;
74 ncolors = half*2 + 2;
75 dither_ncolors = ncolors;
76
77 level = (u_char *) malloc((unsigned) ncolors);
78 assert(level != NULL);
79
80 nbytes = ncolors * 3;
81 dither_colormap = (u_char *) malloc(nbytes);
82 assert(dither_colormap != NULL);
83 xearth_bzero((char *) dither_colormap, nbytes);
84
85 level[0] = 0;
86 for (i=1; i<=half; i++)
87 {
88 val = (i * 255) / half;
89
90 dither_colormap[i*3+0] = 0;
91 dither_colormap[i*3+1] = val;
92 dither_colormap[i*3+2] = 0;
93 level[i] = val;
94
95 i += half;
96 dither_colormap[i*3+0] = 0;
97 dither_colormap[i*3+1] = 0;
98 dither_colormap[i*3+2] = val;
99 level[i] = val;
100 i -= half;
101 }
102
103 dither_colormap[(ncolors-1)*3+0] = 255;
104 dither_colormap[(ncolors-1)*3+1] = 255;
105 dither_colormap[(ncolors-1)*3+2] = 255;
106 level[ncolors-1] = 255;
107
108 for (i=0; i<256; i++)
109 {
110 val = (i * half + 127) / 255;
111
112 grn_idx[i] = val;
113
114 if (val == 0)
115 blu_idx[i] = val;
116 else
117 blu_idx[i] = val + half;
118 }
119
120 nbytes = (sizeof(s16or32) * 2) * (wdth+2);
121
122 curr = (s16or32 *) malloc(nbytes);
123 assert(curr != NULL);
124 xearth_bzero((char *) curr, nbytes);
125 curr += 2;
126
127 next = (s16or32 *) malloc(nbytes);
128 assert(next != NULL);
129 xearth_bzero((char *) next, nbytes);
130 next += 2;
131
132 even_row = 1;
133 }
134
135
136 void dither_row(row, rslt)
137 u_char *row;
138 u16or32 *rslt;
139 {
140 if (even_row)
141 dither_row_ltor(row, rslt);
142 else
143 dither_row_rtol(row, rslt);
144
145 even_row = !even_row;
146 }
147
148
149 void dither_cleanup()
150 {
151 free(curr-2);
152 free(next-2);
153 free(dither_colormap);
154 free(level);
155 }
156
157
158 static void dither_row_ltor(row, rslt)
159 u_char *row;
160 u16or32 *rslt;
161 {
162 int i, i_lim;
163 int grn, g_tmp;
164 int blu, b_tmp;
165 int idx;
166 u_char *rowtmp;
167 s16or32 *currtmp;
168 s16or32 *nexttmp;
169
170 rowtmp = row;
171 currtmp = curr;
172 nexttmp = next;
173
174 /* use i_lim to encourage compilers to register loop limit
175 */
176 i_lim = wdth;
177 for (i=0; i<i_lim; i++)
178 {
179 grn = rowtmp[1];
180 blu = rowtmp[2];
181
182 if ((grn == 0) && (blu == 0))
183 {
184 rslt[i] = 0;
185 }
186 else if ((grn == 255) && (blu == 255))
187 {
188 rslt[i] = dither_ncolors - 1;
189 }
190 else
191 {
192 grn += currtmp[0];
193 blu += currtmp[1];
194
195 if (grn > blu)
196 {
197 if (grn < 0)
198 grn = 0;
199 else if (grn > 255)
200 grn = 255;
201
202 idx = grn_idx[grn];
203 grn -= level[idx];
204 }
205 else
206 {
207 if (blu < 0)
208 blu = 0;
209 else if (blu > 255)
210 blu = 255;
211
212 idx = blu_idx[blu];
213 blu -= level[idx];
214 }
215
216 rslt[i] = idx;
217
218 /* conceptually, what we want here is something like
219 *
220 * g_tmp = (grn<0) ? 7 : 8;
221 * b_tmp = (blu<0) ? 7 : 8;
222 * currtmp[ 2] += ((grn * 7) + g_tmp) >> 4;
223 * currtmp[ 3] += ((blu * 7) + b_tmp) >> 4;
224 * nexttmp[ 2] += ((grn * 1) + g_tmp) >> 4;
225 * nexttmp[ 3] += ((blu * 1) + b_tmp) >> 4;
226 * nexttmp[ 0] += ((grn * 5) + g_tmp) >> 4;
227 * nexttmp[ 1] += ((blu * 5) + b_tmp) >> 4;
228 * nexttmp[-2] += ((grn * 3) + g_tmp) >> 4;
229 * nexttmp[-1] += ((blu * 3) + b_tmp) >> 4;
230 *
231 * but we can get tighter code by computing the product terms
232 * via a sequence of additions into g_tmp and b_tmp
233 */
234 g_tmp = ((grn<0) ? 7 : 8) + grn;
235 b_tmp = ((blu<0) ? 7 : 8) + blu;
236 nexttmp[2] += (g_tmp >> 4);
237 nexttmp[3] += (b_tmp >> 4);
238 grn += grn;
239 blu += blu;
240 g_tmp += grn;
241 b_tmp += blu;
242 nexttmp[-2] += (g_tmp >> 4);
243 nexttmp[-1] += (b_tmp >> 4);
244 g_tmp += grn;
245 b_tmp += blu;
246 nexttmp[0] += (g_tmp >> 4);
247 nexttmp[1] += (b_tmp >> 4);
248 g_tmp += grn;
249 b_tmp += blu;
250 currtmp[2] += (g_tmp >> 4);
251 currtmp[3] += (b_tmp >> 4);
252 }
253
254 rowtmp += 3;
255 currtmp += 2;
256 nexttmp += 2;
257 }
258
259 currtmp = curr;
260 curr = next;
261 next = currtmp;
262 xearth_bzero((char *) next, (unsigned) ((sizeof(s16or32) * 2) * wdth));
263 }
264
265
266 static void dither_row_rtol(row, rslt)
267 u_char *row;
268 u16or32 *rslt;
269 {
270 int i;
271 int grn, g_tmp;
272 int blu, b_tmp;
273 int idx;
274 u_char *rowtmp;
275 s16or32 *currtmp;
276 s16or32 *nexttmp;
277
278 rowtmp = row + 3*(wdth-1);
279 currtmp = curr + 2*(wdth-1);
280 nexttmp = next + 2*(wdth-1);
281
282 for (i=(wdth-1); i>=0; i--)
283 {
284 grn = rowtmp[1];
285 blu = rowtmp[2];
286
287 if ((grn == 0) && (blu == 0))
288 {
289 rslt[i] = 0;
290 }
291 else if ((grn == 255) && (blu == 255))
292 {
293 rslt[i] = dither_ncolors - 1;
294 }
295 else
296 {
297 grn += currtmp[0];
298 blu += currtmp[1];
299
300 if (grn > blu)
301 {
302 if (grn < 0)
303 grn = 0;
304 else if (grn > 255)
305 grn = 255;
306
307 idx = grn_idx[grn];
308 grn -= level[idx];
309 }
310 else
311 {
312 if (blu < 0)
313 blu = 0;
314 else if (blu > 255)
315 blu = 255;
316
317 idx = blu_idx[blu];
318 blu -= level[idx];
319 }
320
321 rslt[i] = idx;
322
323 /* conceptually, what we want here is something like
324 *
325 * g_tmp = (grn<0) ? 7 : 8;
326 * b_tmp = (blu<0) ? 7 : 8;
327 * currtmp[-2] += ((grn * 7) + g_tmp) >> 4;
328 * currtmp[-1] += ((blu * 7) + b_tmp) >> 4;
329 * nexttmp[-2] += ((grn * 1) + g_tmp) >> 4;
330 * nexttmp[-1] += ((blu * 1) + b_tmp) >> 4;
331 * nexttmp[ 0] += ((grn * 5) + g_tmp) >> 4;
332 * nexttmp[ 1] += ((blu * 5) + b_tmp) >> 4;
333 * nexttmp[ 2] += ((grn * 3) + g_tmp) >> 4;
334 * nexttmp[ 3] += ((blu * 3) + b_tmp) >> 4;
335 *
336 * but we can get tighter code by computing the product terms
337 * via a sequence of additions into g_tmp and b_tmp
338 */
339 g_tmp = ((grn<0) ? 7 : 8) + grn;
340 b_tmp = ((blu<0) ? 7 : 8) + blu;
341 nexttmp[-2] += (g_tmp >> 4);
342 nexttmp[-1] += (b_tmp >> 4);
343 grn += grn;
344 blu += blu;
345 g_tmp += grn;
346 b_tmp += blu;
347 nexttmp[2] += (g_tmp >> 4);
348 nexttmp[3] += (b_tmp >> 4);
349 g_tmp += grn;
350 b_tmp += blu;
351 nexttmp[0] += (g_tmp >> 4);
352 nexttmp[1] += (b_tmp >> 4);
353 g_tmp += grn;
354 b_tmp += blu;
355 currtmp[-2] += (g_tmp >> 4);
356 currtmp[-1] += (b_tmp >> 4);
357 }
358
359 rowtmp -= 3;
360 currtmp -= 2;
361 nexttmp -= 2;
362 }
363
364 currtmp = curr;
365 curr = next;
366 next = currtmp;
367 xearth_bzero((char *) next, (unsigned) ((sizeof(s16or32) * 2) * wdth));
368 }
369
370
371 void mono_dither_setup()
372 {
373 int i;
374 unsigned nbytes;
375
376 nbytes = sizeof(s16or32) * (wdth+2);
377
378 curr = (s16or32 *) malloc(nbytes);
379 assert(curr != NULL);
380 for (i=0; i<(wdth+2); i++)
381 curr[i] = (random() & ((1<<9)-1)) - (1<<8);
382 curr += 1;
383
384 next = (s16or32 *) malloc(nbytes);
385 assert(next != NULL);
386 xearth_bzero((char *) next, nbytes);
387 next += 1;
388
389 even_row = 1;
390 }
391
392
393 void mono_dither_row(row, rslt)
394 u_char *row;
395 u16or32 *rslt;
396 {
397 int i, i_lim;
398
399 /* convert row to gray scale (could save a few instructions per
400 * pixel by integrating this into the mono_dither_row_* functions)
401 */
402 i_lim = wdth;
403 for (i=0; i<i_lim; i++)
404 {
405 rslt[i] = (2 * row[0]) + (5 * row[1]) + row[2];
406 row += 3;
407 }
408
409 /* dither to 0s (black) and 1s (white)
410 */
411 if (even_row)
412 mono_dither_row_ltor(rslt);
413 else
414 mono_dither_row_rtol(rslt);
415
416 even_row = !even_row;
417 }
418
419
420 void mono_dither_cleanup()
421 {
422 free(curr-1);
423 free(next-1);
424 }
425
426
427 static void mono_dither_row_ltor(row)
428 u16or32 *row;
429 {
430 int i, i_lim;
431 int val, tmp;
432 u16or32 *rowtmp;
433 s16or32 *currtmp;
434 s16or32 *nexttmp;
435
436 rowtmp = row;
437 currtmp = curr;
438 nexttmp = next;
439
440 /* use i_lim to encourage compilers to register loop limit
441 */
442 i_lim = wdth;
443 for (i=0; i<i_lim; i++)
444 {
445 val = rowtmp[0];
446
447 if (val == 0)
448 {
449 rowtmp[0] = 0;
450 }
451 else if (val == 2040)
452 {
453 rowtmp[0] = 1;
454 }
455 else
456 {
457 val += currtmp[0];
458
459 if (val > 1020)
460 {
461 rowtmp[0] = 1;
462 val -= 2040;
463 }
464 else
465 {
466 rowtmp[0] = 0;
467 }
468
469 /* conceptually, what we want here is something like
470 *
471 * tmp = (val < 0) ? 7 : 8;
472 * currtmp[ 1] += ((val * 7) + tmp) >> 4;
473 * nexttmp[ 1] += ((val * 1) + tmp) >> 4;
474 * nexttmp[ 0] += ((val * 5) + tmp) >> 4;
475 * nexttmp[-1] += ((val * 3) + tmp) >> 4;
476 *
477 * but we can get tighter code by computing the product terms
478 * via a sequence of additions into tmp
479 */
480 tmp = ((val < 0) ? 7 : 8) + val;
481 nexttmp[1] += (tmp >> 4);
482 val += val;
483 tmp += val;
484 nexttmp[-1] += (tmp >> 4);
485 tmp += val;
486 nexttmp[0] += (tmp >> 4);
487 tmp += val;
488 currtmp[1] += (tmp >> 4);
489 }
490
491 rowtmp += 1;
492 currtmp += 1;
493 nexttmp += 1;
494 }
495
496 currtmp = curr;
497 curr = next;
498 next = currtmp;
499 xearth_bzero((char *) next, (unsigned) (sizeof(s16or32) * wdth));
500 }
501
502
503 static void mono_dither_row_rtol(row)
504 u16or32 *row;
505 {
506 int i;
507 int val, tmp;
508 u16or32 *rowtmp;
509 s16or32 *currtmp;
510 s16or32 *nexttmp;
511
512 rowtmp = row + (wdth-1);
513 currtmp = curr + (wdth-1);
514 nexttmp = next + (wdth-1);
515
516 for (i=(wdth-1); i>=0; i--)
517 {
518 val = rowtmp[0];
519
520 if (val == 0)
521 {
522 rowtmp[0] = 0;
523 }
524 else if (val == 2040)
525 {
526 rowtmp[0] = 1;
527 }
528 else
529 {
530 val += currtmp[0];
531
532 if (val > 1020)
533 {
534 rowtmp[0] = 1;
535 val -= 2040;
536 }
537 else
538 {
539 rowtmp[0] = 0;
540 }
541
542 /* conceptually, what we want here is something like
543 *
544 * tmp = (val < 0) ? 7 : 8;
545 * currtmp[-1] += ((val * 7) + tmp) >> 4;
546 * nexttmp[-1] += ((val * 1) + tmp) >> 4;
547 * nexttmp[ 0] += ((val * 5) + tmp) >> 4;
548 * nexttmp[ 1] += ((val * 3) + tmp) >> 4;
549 *
550 * but we can get tighter code by computing the product terms
551 * via a sequence of additions into tmp
552 */
553 tmp = ((val < 0) ? 7 : 8) + val;
554 nexttmp[-1] += (tmp >> 4);
555 val += val;
556 tmp += val;
557 nexttmp[1] += (tmp >> 4);
558 tmp += val;
559 nexttmp[0] += (tmp >> 4);
560 tmp += val;
561 currtmp[-1] += (tmp >> 4);
562 }
563
564 rowtmp -= 1;
565 currtmp -= 1;
566 nexttmp -= 1;
567 }
568
569 currtmp = curr;
570 curr = next;
571 next = currtmp;
572 xearth_bzero((char *) next, (unsigned) (sizeof(s16or32) * wdth));
573 }