1 /*
2 * fs2fast.c --
3 *
4 * Procedures dealing with a fast version of Floyd-Steinberg
5 * dithering with 2 error values propagated.
6 */
7
8 /*
9 * Copyright (c) 1995 The Regents of the University of California.
10 * All rights reserved.
11 *
12 * Permission to use, copy, modify, and distribute this software and its
13 * documentation for any purpose, without fee, and without written agreement is
14 * hereby granted, provided that the above copyright notice and the following
15 * two paragraphs appear in all copies of this software.
16 *
17 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
18 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
19 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
20 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
21 *
22 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
23 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
24 * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
25 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
26 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
27 */
28
29 #include "video.h"
30 #include "proto.h"
31 #include "dither.h"
32 #ifdef __STDC__
33 #include <stdlib.h>
34 #else
35 #include <malloc.h>
36 #endif
37
38
39 /* Arrays containing error values for floyd-steinberg dithering. */
40
41 static int deltay[256];
42 static int deltau[256];
43 static int deltav[256];
44 static int deltay2[256];
45 static int deltau2[256];
46 static int deltav2[256];
47
48 /* Definitions governing number of bits used for luminance, cr, and cb. */
49
50 #define L_BITS 3
51 #define CR_BITS 2
52 #define CB_BITS 2
53
54 /* Masks for proper quantization of lum, cr, and cb values. */
55
56 #define L_MASK 0xe0
57 #define CR_MASK 0xc0
58 #define CB_MASK 0xc0
59
60
61
62 /*
63 *--------------------------------------------------------------
64 *
65 * InitFS2FastDither --
66 *
67 * Initializes structures and arrays neeeded for fast implementation
68 * of two error F-S dithering.
69 *
70 * Results:
71 * None.
72 *
73 * Side effects:
74 * None.
75 *
76 *--------------------------------------------------------------
77 */
78
InitFS2FastDither()79 void InitFS2FastDither()
80 {
81 int i;
82 int lum_num, cr_num, cb_num;
83
84 for (i=0; i<256; i++) {
85 lum_num = (i >> (8-L_BITS));
86 cr_num = (i >> (8-CR_BITS));
87 cb_num = (i >> (8-CB_BITS));
88
89 /* These arrays contain the error values propogated for each pixel value
90 for each channel.
91 */
92
93 deltay[i] = (i - ((int) lum_values[lum_num])) / 2;
94 deltau[i] = (i-((int) cr_values[cr_num])) / 2;
95 deltav[i] = (i-((int) cb_values[cb_num])) / 2;
96 deltay2[i] = (i - ((int) lum_values[lum_num])) - deltay[i];
97 deltau2[i] = (i - ((int) cr_values[cr_num])) - deltau[i];
98 deltav2[i] = (i - ((int) cb_values[cb_num])) - deltav[i];
99
100 }
101
102 }
103
104
105 /*
106 *--------------------------------------------------------------
107 *
108 * DitherImage --
109 *
110 * Dithers an image using floyd-steinberg.
111 * Assumptions made:
112 * 1) The color space is allocated y:cr:cb = 8:4:4
113 * 2) The spatial resolution of y:cr:cb is 4:1:1
114 *
115 * Results:
116 * None.
117 *
118 * Side effects:
119 * None.
120 *
121 *--------------------------------------------------------------
122 */
123 void
FS2FastDitherImage(lum,cr,cb,out,h,w)124 FS2FastDitherImage (lum, cr, cb, out, h, w)
125 unsigned char *lum;
126 unsigned char *cr;
127 unsigned char *cb;
128 unsigned char *out;
129 int w, h;
130 {
131 int i, j, idx, idx2;
132 int y, u, v;
133 int dy, du, dv;
134 int code;
135 static int *yerr1;
136 static int *yerr2;
137 static int *uerr1;
138 static int *uerr2;
139 static int *verr1;
140 static int *verr2;
141 int *ye1, *ue1, *ve1;
142 int *ye2, *ue2, *ve2;
143 unsigned char *o, *l, *r, *b;
144 static int first = 1;
145
146 /* If first time called, allocate error arrays. */
147
148 if (first) {
149 first = 0;
150 yerr1 = (int *) malloc((w+5)*sizeof(int));
151 yerr2 = (int *) malloc((w+5)*sizeof(int));
152 uerr1 = (int *) malloc((w+5)*sizeof(int));
153 uerr2 = (int *) malloc((w+5)*sizeof(int));
154 verr1 = (int *) malloc((w+5)*sizeof(int));
155 verr2 = (int *) malloc((w+5)*sizeof(int));
156 }
157
158 /*
159 * Init error arrays and variables.
160 */
161 memset ((char *)yerr1, 0, (w+5)*sizeof(int));
162 memset ((char *)yerr2, 0, (w+5)*sizeof(int));
163 memset ((char *)uerr1, 0, (w+5)*sizeof(int));
164 memset ((char *)uerr2, 0, (w+5)*sizeof(int));
165 memset ((char *)verr1, 0, (w+5)*sizeof(int));
166 memset ((char *)verr2, 0, (w+5)*sizeof(int));
167 du = dv = dy = 0;
168
169 for (j=0; j<h; j+=2) {
170 ye1 = yerr1;
171 ue1 = uerr1;
172 ve1 = verr1;
173 ye2 = yerr2;
174 ue2 = uerr2;
175 ve2 = verr2;
176 idx = j*w;
177 idx2 = idx/4;
178 o = out+idx;
179 l = lum+idx;
180 r = cr+idx2;
181 b = cb+idx2;
182
183 /* Do the top row in forward order. */
184 for (i=0; i<w; i+=2) {
185 /* Do left side of this pair... */
186 y = *l++ + dy + *ye1++;
187 u = *r + du + *ue1++;
188 v = *b + dv + *ve1++;
189
190 if (y < 0) {
191 y = 0;
192 } else if (y > 255) {
193 y = 255;
194 }
195
196 if (u < 0) {
197 u = 0;
198 } else if (u > 255) {
199 u = 255;
200 }
201
202 if (v < 0) {
203 v = 0;
204 } else if (v > 255) {
205 v = 255;
206 }
207
208 /*
209 * Construct a code using:
210 * high order 3 bits of y,
211 * high order 2 bits of u,
212 * high order 2 bits of v
213 */
214 code = (((y & L_MASK) | ((u & CR_MASK) >> L_BITS) | (v >> (L_BITS+CR_BITS)))
215 >> (8-(L_BITS+CR_BITS+CB_BITS)));
216 *o++ = pixel[code];
217 *ye2++ = deltay[y];
218 *ue2++ = deltau[u];
219 *ve2++ = deltav[v];
220 dy = deltay2[y];
221 du = deltau2[u];
222 dv = deltav2[v];
223
224 /* Do right side of this pair... */
225 y = *l++ + dy + *ye1++;
226 u = *r++ + du + *ue1++;
227 v = *b++ + dv + *ve1++;
228
229 if (y < 0) {
230 y = 0;
231 } else if (y > 255) {
232 y = 255;
233 }
234
235 if (u < 0) {
236 u = 0;
237 } else if (u > 255) {
238 u = 255;
239 }
240
241 if (v < 0) {
242 v = 0;
243 } else if (v > 255) {
244 v = 255;
245 }
246
247 code = (((y & L_MASK) | ((u & CR_MASK) >> L_BITS) | (v >> (L_BITS+CR_BITS)))
248 >> (8-(L_BITS+CR_BITS+CB_BITS)));
249 *o++ = pixel[code];
250 *ye2++ = deltay[y];
251 *ue2++ = deltau[u];
252 *ve2++ = deltav[v];
253 dy = deltay2[y];
254 du = deltau2[u];
255 dv = deltav2[v];
256
257 }
258
259 ye1 = yerr1+w-1;
260 ue1 = uerr1+w-1;
261 ve1 = verr1+w-1;
262 ye2 = yerr2+w-1;
263 ue2 = uerr2+w-1;
264 ve2 = verr2+w-1;
265 l += w-1;
266 o += w-1;
267 r--;
268 b--;
269 dy = du = dv = 0;
270
271 /* Do bottom part of row, in right to left order. */
272 for (i=w-1; i>0; i-=2) {
273 /* Do right side of this pair... */
274 y = *l-- + dy + *ye2--;
275 u = *r + du + *ue2--;
276 v = *b + dv + *ve2--;
277
278 if (y < 0) {
279 y = 0;
280 } else if (y > 255) {
281 y = 255;
282 }
283
284 if (u < 0) {
285 u = 0;
286 } else if (u > 255) {
287 u = 255;
288 }
289
290 if (v < 0) {
291 v = 0;
292 } else if (v > 255) {
293 v = 255;
294 }
295
296 /*
297 * Construct a code using:
298 * high order 3 bits of y,
299 * high order 2 bits of u,
300 * high order 2 bits of v
301 */
302 code = (((y & L_MASK) | ((u & CR_MASK) >> L_BITS) | (v >> (L_BITS+CR_BITS)))
303 >> (8-(L_BITS+CR_BITS+CB_BITS)));
304 *o-- = pixel[code];
305 *ye1-- = deltay[y];
306 *ue1-- = deltau[u];
307 *ve1-- = deltav[v];
308 dy = deltay2[y];
309 du = deltau2[u];
310 dv = deltav2[v];
311
312 /* Do left side of this pair... */
313 y = *l-- + dy + *ye2--;
314 u = *r-- + du + *ue2--;
315 v = *b-- + dv + *ve2--;
316
317 if (y < 0) {
318 y = 0;
319 } else if (y > 255) {
320 y = 255;
321 }
322
323 if (u < 0) {
324 u = 0;
325 } else if (u > 255) {
326 u = 255;
327 }
328
329 if (v < 0) {
330 v = 0;
331 } else if (v > 255) {
332 v = 255;
333 }
334
335
336 code = (((y & L_MASK) | ((u & CR_MASK) >> L_BITS) | (v >> (L_BITS+CR_BITS)))
337 >> (8-(L_BITS+CR_BITS+CB_BITS)));
338 *o-- = pixel[code];
339 *ye1-- = deltay[y];
340 *ue1-- = deltau[u];
341 *ve1-- = deltav[v];
342 dy = deltay2[y];
343 du = deltau2[u];
344 dv = deltav2[v];
345
346 }
347 }
348 }
349
350
351
352
353
354