1 /*
2 * hybriderr.c --
3 *
4 * Procedures dealing with hybrid2 dithering, which is hybrid
5 * dithering with error propagation among pixels.
6 *
7 */
8
9 /*
10 * Copyright (c) 1995 The Regents of the University of California.
11 * All rights reserved.
12 *
13 * Permission to use, copy, modify, and distribute this software and its
14 * documentation for any purpose, without fee, and without written agreement is
15 * hereby granted, provided that the above copyright notice and the following
16 * two paragraphs appear in all copies of this software.
17 *
18 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
19 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
20 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
21 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22 *
23 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
24 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
25 * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
26 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
27 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
28 */
29
30 /* This file contains C code to implement an ordered dither in the
31 luminance channel and F-S error diffusion on chrominance.
32 */
33
34 #include "video.h"
35 #include "proto.h"
36 #include "dither.h"
37
38 #define DITH_SIZE 16
39
40 /* Structures used for hybrid dither with errors propogated. */
41
42 static unsigned char *l_darrays[DITH_SIZE];
43 static unsigned char *l_darrays0, *l_darrays1, *l_darrays2, *l_darrays3;
44 static unsigned char *l_darrays4, *l_darrays5, *l_darrays6, *l_darrays7;
45 static unsigned char *l_darrays8, *l_darrays9, *l_darrays10, *l_darrays11;
46 static unsigned char *l_darrays12, *l_darrays13, *l_darrays14, *l_darrays15;
47 static unsigned char cr_fsarray[256*256][4];
48 static unsigned char cb_fsarray[256*256][4];
49 static unsigned short c_fserr[256*256][2];
50
51
52 /*
53 *--------------------------------------------------------------
54 *
55 * InitHybridErrorDither--
56 *
57 * Initializes structures used for hybrid dither algorithm
58 * with errors propogated on Cr and Cb.
59 *
60 * Results:
61 * None.
62 *
63 * Side effects:
64 * None.
65 *
66 *--------------------------------------------------------------
67 */
68
69 void
InitHybridErrorDither()70 InitHybridErrorDither()
71 {
72 int i, j, k, err_range, threshval;
73 unsigned char *lmark;
74
75
76 for (i=0; i<DITH_SIZE; i++) {
77 lmark = l_darrays[i] = (unsigned char *) malloc(256);
78
79 for (j=0; j<lum_values[0]; j++) {
80 *lmark++ = 0;
81 }
82
83 for (j=0; j<(LUM_RANGE-1); j++) {
84 err_range = lum_values[j+1] - lum_values[j];
85 threshval = ((i * err_range) / DITH_SIZE)+lum_values[j];
86
87 for (k=lum_values[j]; k<lum_values[j+1]; k++) {
88 if (k > threshval) *lmark++ = ((j+1) * (CR_RANGE * CB_RANGE));
89 else *lmark++ = (j * (CR_RANGE * CB_RANGE));
90 }
91 }
92
93 for (j=lum_values[LUM_RANGE-1]; j <256; j++) {
94 *lmark++ = (LUM_RANGE-1)*(CR_RANGE * CB_RANGE);
95 }
96 }
97 l_darrays0 = l_darrays[0]; l_darrays8 = l_darrays[8];
98 l_darrays1 = l_darrays[1]; l_darrays9 = l_darrays[9];
99 l_darrays2 = l_darrays[2]; l_darrays10 = l_darrays[10];
100 l_darrays3 = l_darrays[3]; l_darrays11 = l_darrays[11];
101 l_darrays4 = l_darrays[4]; l_darrays12 = l_darrays[12];
102 l_darrays5 = l_darrays[5]; l_darrays13 = l_darrays[13];
103 l_darrays6 = l_darrays[6]; l_darrays14 = l_darrays[14];
104 l_darrays7 = l_darrays[7]; l_darrays15 = l_darrays[15];
105 {
106 int cr1, cr2, cr3, cr4, err1, err2;
107 int cb1, cb2, cb3, cb4, val, nval;
108 int outerr1, outerr2, outerr3, outerr4;
109 int inerr1, inerr2, inerr3, inerr4;
110 unsigned short oe1, oe2, oe3, oe4;
111
112 for (j=0; j<65536; j+= 256) {
113
114 inerr1 = (((j & 0xc000) >> 14)*8) - 12;
115 inerr2 = (((j & 0x3000) >> 12)*8) - 12;
116 inerr3 = (((j & 0x0c00) >> 10)*8) - 12;
117 inerr4 = (((j & 0x0300) >> 8) *8) - 12;
118
119 for (i=0; i<256; i++) {
120 val = i;
121
122 nval = val+inerr1+inerr3;
123 if (nval < 0) nval = 0; else if (nval > 255) nval = 255;
124 cr1 = ((nval) * CR_RANGE) / 256;
125 err1 = ((nval) - cr_values[cr1])/2;
126 err2 = ((nval) - cr_values[cr1]) - err1;
127
128 nval = val+err1+inerr2;
129 if (nval < 0) nval = 0; else if (nval > 255) nval = 255;
130 cr2 = ((nval) * CR_RANGE) / 256;
131 err1 = ((nval) - cr_values[cr2])/2;
132 outerr3 = ((nval) - cr_values[cr2])-err1;
133
134 nval = val+err2+inerr4;
135 if (nval < 0) nval = 0; else if (nval > 255) nval = 255;
136 cr3 = ((nval) * CR_RANGE) / 256;
137 err2 = ((nval) - cr_values[cr3])/2;
138 outerr1 = ((nval) - cr_values[cr3]) - err2;
139
140 nval = val+err1+err2;
141 if (nval < 0) nval = 0; else if (nval > 255) nval = 255;
142 cr4 = ((nval) * CR_RANGE) / 256;
143 outerr2 = ((nval) - cr_values[cr4])/2;
144 outerr4 = ((nval) - cr_values[cr4])-outerr2;
145
146 cr_fsarray[i+j][0] = cr1*CB_RANGE;
147 cr_fsarray[i+j][1] = cr2*CB_RANGE;
148 cr_fsarray[i+j][2] = cr3*CB_RANGE;
149 cr_fsarray[i+j][3] = cr4*CB_RANGE;
150
151 if (outerr1 < -16) outerr1++;
152 else if (outerr1 > 15) outerr1--;
153 if (outerr2 < -16) outerr2++;
154 else if (outerr2 > 15) outerr2--;
155 if (outerr3 < -16) outerr3++;
156 else if (outerr3 > 15) outerr3--;
157 if (outerr4 < -16) outerr4++;
158 else if (outerr4 > 15) outerr4--;
159
160 oe1 = (outerr1 + 16) / 8;
161 oe2 = (outerr2 + 16) / 8;
162 oe3 = (outerr3 + 16) / 8;
163 oe4 = (outerr4 + 16) / 8;
164
165 /* This is a debugging check and should be removed if not needed. */
166 if ((oe1 > 3) || (oe2 > 3) || (oe3 > 3) || (oe4 > 3))
167 fprintf(stderr, "OE error!!!!\n");
168
169
170 c_fserr[i+j][0] = ((oe1 << 14) | (oe2 << 12));
171
172 c_fserr[i+j][1] = ((oe3 << 10) | (oe4 << 8));
173 }
174
175 for (i=0; i<256; i++) {
176 val = i;
177 nval = val+inerr1+inerr3;
178 if (nval < 0) nval = 0; else if (nval > 255) nval = 255;
179 cb1 = ((nval) * CB_RANGE) / 256;
180 err1 = ((nval) - cb_values[cb1])/2;
181 err2 = ((nval) - cb_values[cb1]) - err1;
182
183 nval = val+err1+inerr2;
184 if (nval < 0) nval = 0; else if (nval > 255) nval = 255;
185 cb2 = ((nval) * CB_RANGE) / 256;
186 err1 = ((nval) - cb_values[cb2])/2;
187
188 nval = val+err2+inerr4;
189 if (nval < 0) nval = 0; else if (nval > 255) nval = 255;
190 cb3 = ((nval) * CB_RANGE) / 256;
191 err2 = ((nval) - cb_values[cb3])/2;
192
193 nval = val+err1+err2;
194 if (nval < 0) nval = 0; else if (nval > 255) nval = 255;
195 cb4 = ((nval) * CB_RANGE) / 256;
196
197 cb_fsarray[i+j][0] = cb1;
198 cb_fsarray[i+j][1] = cb2;
199 cb_fsarray[i+j][2] = cb3;
200 cb_fsarray[i+j][3] = cb4;
201 }
202 }
203 }
204 }
205
206
207 /*
208 *--------------------------------------------------------------
209 *
210 * HybridErrorDitherImage --
211 *
212 * Dithers an image using a hybrid ordered/floyd-steinberg dither.
213 * Assumptions made:
214 * 1) The color space is allocated y:cr:cb = 8:4:4
215 * 2) The spatial resolution of y:cr:cb is 4:1:1
216 * This dither is almost exactly like the dither implemented in the
217 * file odith.c (i.e. hybrid dithering) except a quantized amount of
218 * error is propogated between 2x2 pixel areas in Cr and Cb.
219 *
220 * Results:
221 * None.
222 *
223 * Side effects:
224 * None.
225 *
226 *--------------------------------------------------------------
227 */
228 void
HybridErrorDitherImage(lum,cr,cb,out,h,w)229 HybridErrorDitherImage (lum, cr, cb, out, h, w)
230 unsigned char *lum;
231 unsigned char *cr;
232 unsigned char *cb;
233 unsigned char *out;
234 int w, h;
235 {
236 unsigned char *l, *r, *b, *o1, *o2;
237 unsigned char *l2;
238 static int *cr_row_errs;
239 static int *cb_row_errs;
240 int *cr_r_err;
241 int *cb_r_err;
242 int cr_c_err;
243 int cb_c_err;
244 unsigned char *cr_fsptr;
245 unsigned char *cb_fsptr;
246 static int first = 1;
247 int cr_code, cb_code;
248
249 int i, j;
250 int row_advance, row_advance2;
251 int half_row_advance, half_row_advance2;
252
253 /* If first time called, allocate error arrays. */
254
255 if (first) {
256 cr_row_errs = (int *) malloc((w+5)*sizeof(int));
257 cb_row_errs = (int *) malloc((w+5)*sizeof(int));
258 first = 0;
259 }
260
261 row_advance = (w << 1) - 1;
262 row_advance2 = row_advance+2;
263 half_row_advance = (w>>1)-1;
264 half_row_advance2 = half_row_advance+2;
265
266 l = lum;
267 l2 = lum+w;
268 r = cr;
269 b = cb;
270 o1 = out;
271 o2 = out+w;
272
273 memset( (char *) cr_row_errs, 0, (w+5)*sizeof(int));
274 cr_r_err = cr_row_errs;
275 cr_c_err = 0;
276 memset( (char *) cb_row_errs, 0, (w+5)*sizeof(int));
277 cb_r_err = cb_row_errs;
278 cb_c_err = 0;
279
280 for (i=0; i<h; i+=4) {
281
282 for (j=w; j>0; j-=4) {
283
284 cr_code = (*cr_r_err | cr_c_err | *r++);
285 cb_code = (*cb_r_err | cb_c_err | *b++);
286
287 cr_fsptr = cr_fsarray[cr_code];
288 cb_fsptr = cb_fsarray[cb_code];
289
290 *o1++ = pixel[(l_darrays0[*l++] | *cr_fsptr++ | *cb_fsptr++)];
291 *o1++ = pixel[(l_darrays8[*l++] | *cr_fsptr++ | *cb_fsptr++)];
292 *o2++ = pixel[(l_darrays12[*l2++] | *cr_fsptr++ | *cb_fsptr++)];
293 *o2++ = pixel[(l_darrays4[*l2++] | *cr_fsptr++ | *cb_fsptr++)];
294
295 cr_c_err = c_fserr[cr_code][1];
296 cb_c_err = c_fserr[cb_code][1];
297 *cr_r_err++ = c_fserr[cr_code][0];
298 *cb_r_err++ = c_fserr[cb_code][0];
299 cr_code = (*cr_r_err | cr_c_err | *r++);
300 cb_code = (*cb_r_err | cb_c_err | *b++);
301
302 cr_fsptr = cr_fsarray[cr_code];
303 cb_fsptr = cb_fsarray[cb_code];
304
305 *o1++ = pixel[(l_darrays2[*l++] | *cr_fsptr++ | *cb_fsptr++)];
306 *o1++ = pixel[(l_darrays10[*l++] | *cr_fsptr++ | *cb_fsptr++)];
307 *o2++ = pixel[(l_darrays14[*l2++] | *cr_fsptr++ | *cb_fsptr++)];
308 *o2++ = pixel[(l_darrays6[*l2++] | *cr_fsptr++ | *cb_fsptr++)];
309
310 cr_c_err = c_fserr[cr_code][1];
311 cb_c_err = c_fserr[cb_code][1];
312 *cr_r_err++ = c_fserr[cr_code][0];
313 *cb_r_err++ = c_fserr[cb_code][0];
314 }
315
316 l += row_advance; l2 += row_advance;
317 o1 += row_advance; o2 += row_advance;
318 cr_c_err = 0;
319 cb_c_err = 0;
320 cr_r_err--; cb_r_err--;
321 r += half_row_advance; b += half_row_advance;
322
323 for (j=w; j>0; j-=4) {
324
325 cr_code = (*cr_r_err | cr_c_err | *r--);
326 cb_code = (*cb_r_err | cb_c_err | *b--);
327 cr_fsptr = cr_fsarray[cr_code];
328 cb_fsptr = cb_fsarray[cb_code];
329
330 *o1-- = pixel[(l_darrays9[*l--] | *cr_fsptr++ | *cb_fsptr++)];
331 *o1-- = pixel[(l_darrays1[*l--] | *cr_fsptr++ | *cb_fsptr++)];
332 *o2-- = pixel[(l_darrays5[*l2--] | *cr_fsptr++ | *cb_fsptr++)];
333 *o2-- = pixel[(l_darrays13[*l2--] | *cr_fsptr++ | *cb_fsptr++)];
334
335 cr_c_err = c_fserr[cr_code][1];
336 cb_c_err = c_fserr[cb_code][1];
337 *cr_r_err-- = c_fserr[cr_code][0];
338 *cb_r_err-- = c_fserr[cb_code][0];
339 cr_code = (*cr_r_err | cr_c_err | *r--);
340 cb_code = (*cb_r_err | cb_c_err | *b--);
341 cr_fsptr = cr_fsarray[cr_code];
342 cb_fsptr = cb_fsarray[cb_code];
343
344 *o1-- = pixel[(l_darrays11[*l--] | *cr_fsptr++ | *cb_fsptr++)];
345 *o1-- = pixel[(l_darrays3[*l--] | *cr_fsptr++ | *cb_fsptr++)];
346 *o2-- = pixel[(l_darrays7[*l2--] | *cr_fsptr++ | *cb_fsptr++)];
347 *o2-- = pixel[(l_darrays15[*l2--] | *cr_fsptr++ | *cb_fsptr++)];
348
349 cr_c_err = c_fserr[cr_code][1];
350 cb_c_err = c_fserr[cb_code][1];
351 *cr_r_err-- = c_fserr[cr_code][0];
352 *cb_r_err-- = c_fserr[cb_code][0];
353
354 }
355
356 l += row_advance2; l2 += row_advance2;
357 o1 += row_advance2; o2 += row_advance2;
358 cr_c_err = 0; cb_c_err = 0;
359 cr_r_err++; cb_r_err++;
360 r += half_row_advance2; b += half_row_advance2;
361 }
362 }
363
364
365
366