op public repos

Blob

Date:: Tue Jan 4 21:23:50 2005 UTC
Message:: placeholder; does not yet build
Actions:: History | Blame | Raw File
1 /*
2  * rotate an image 180° in O(log Dx + log Dy) /dev/draw writes,
3  * using an extra buffer same size as the image.
4  * 
5  * the basic concept is that you can invert an array by inverting
6  * the top half, inverting the bottom half, and then swapping them.
7  * the code does this slightly backwards to ensure O(log n) runtime.
8  * (If you do it wrong, you can get O(log² n) runtime.)
9  * 
10  * This is usually overkill, but it speeds up slow remote
11  * connections quite a bit.
12  */
13 
14 #include <u.h>
15 #include <libc.h>
16 #include <bio.h>
17 #include <draw.h>
18 #include <event.h>
19 #include "page.h"
20 
21 int ndraw = 0;
22 enum {
23 	Xaxis = 0,
24 	Yaxis = 1,
25 };
26 
27 Image *mtmp;
28 
29 void
30 writefile(char *name, Image *im, int gran)
31 {
32 	static int c = 100;
33 	int fd;
34 	char buf[200];
35 
36 	snprint(buf, sizeof buf, "%d%s%d", c++, name, gran);
37 	fd = create(buf, OWRITE, 0666);
38 	if(fd < 0)
39 		return;	
40 	writeimage(fd, im, 0);
41 	close(fd);
42 }
43 
44 void
45 moveup(Image *im, Image *tmp, int a, int b, int c, int axis)
46 {
47 	Rectangle range;
48 	Rectangle dr0, dr1;
49 	Point p0, p1;
50 
51 	if(a == b || b == c)
52 		return;
53 
54 	drawop(tmp, tmp->r, im, nil, im->r.min, S);
55 
56 	switch(axis){
57 	case Xaxis:
58 		range = Rect(a, im->r.min.y,  c, im->r.max.y);
59 		dr0 = range;
60 		dr0.max.x = dr0.min.x+(c-b);
61 		p0 = Pt(b, im->r.min.y);
62 
63 		dr1 = range;
64 		dr1.min.x = dr1.max.x-(b-a);
65 		p1 = Pt(a, im->r.min.y);
66 		break;
67 	case Yaxis:
68 		range = Rect(im->r.min.x, a,  im->r.max.x, c);
69 		dr0 = range;
70 		dr0.max.y = dr0.min.y+(c-b);
71 		p0 = Pt(im->r.min.x, b);
72 
73 		dr1 = range;
74 		dr1.min.y = dr1.max.y-(b-a);
75 		p1 = Pt(im->r.min.x, a);
76 		break;
77 	}
78 	drawop(im, dr0, tmp, nil, p0, S);
79 	drawop(im, dr1, tmp, nil, p1, S);
80 }
81 
82 void
83 interlace(Image *im, Image *tmp, int axis, int n, Image *mask, int gran)
84 {
85 	Point p0, p1;
86 	Rectangle r0, r1;
87 
88 	r0 = im->r;
89 	r1 = im->r;
90 	switch(axis) {
91 	case Xaxis:
92 		r0.max.x = n;
93 		r1.min.x = n;
94 		p0 = (Point){gran, 0};
95 		p1 = (Point){-gran, 0};
96 		break;
97 	case Yaxis:
98 		r0.max.y = n;
99 		r1.min.y = n;
100 		p0 = (Point){0, gran};
101 		p1 = (Point){0, -gran};
102 		break;
103 	}
104 
105 	drawop(tmp, im->r, im, display->opaque, im->r.min, S);
106 	gendrawop(im, r0, tmp, p0, mask, mask->r.min, S);
107 	gendrawop(im, r0, tmp, p1, mask, p1, S);
108 }
109 
110 /*
111  * Halve the grating period in the mask.
112  * The grating currently looks like 
113  * ####____####____####____####____
114  * where #### is opacity.
115  *
116  * We want
117  * ##__##__##__##__##__##__##__##__
118  * which is achieved by shifting the mask
119  * and drawing on itself through itself.
120  * Draw doesn't actually allow this, so 
121  * we have to copy it first.
122  *
123  *     ####____####____####____####____ (dst)
124  * +   ____####____####____####____#### (src)
125  * in  __####____####____####____####__ (mask)
126  * ===========================================
127  *     ##__##__##__##__##__##__##__##__
128  */
129 int
130 nextmask(Image *mask, int axis, int maskdim)
131 {
132 	Point delta;
133 
134 	delta = axis==Xaxis ? Pt(maskdim,0) : Pt(0,maskdim);
135 	drawop(mtmp, mtmp->r, mask, nil, mask->r.min, S);
136 	gendrawop(mask, mask->r, mtmp, delta, mtmp, divpt(delta,-2), S);
137 //	writefile("mask", mask, maskdim/2);
138 	return maskdim/2;
139 }
140 
141 void
142 shuffle(Image *im, Image *tmp, int axis, int n, Image *mask, int gran,
143 	int lastnn)
144 {
145 	int nn, left;
146 
147 	if(gran == 0)
148 		return;
149 	left = n%(2*gran);
150 	nn = n - left;
151 
152 	interlace(im, tmp, axis, nn, mask, gran);
153 //	writefile("interlace", im, gran);
154 	
155 	gran = nextmask(mask, axis, gran);
156 	shuffle(im, tmp, axis, n, mask, gran, nn);
157 //	writefile("shuffle", im, gran);
158 	moveup(im, tmp, lastnn, nn, n, axis);
159 //	writefile("move", im, gran);
160 }
161 
162 void
163 rot180(Image *im)
164 {
165 	Image *tmp, *tmp0;
166 	Image *mask;
167 	Rectangle rmask;
168 	int gran;
169 
170 	if(chantodepth(im->chan) < 8){
171 		/* this speeds things up dramatically; draw is too slow on sub-byte pixel sizes */
172 		tmp0 = xallocimage(display, im->r, CMAP8, 0, DNofill);
173 		drawop(tmp0, tmp0->r, im, nil, im->r.min, S);
174 	}else
175 		tmp0 = im;
176 
177 	tmp = xallocimage(display, tmp0->r, tmp0->chan, 0, DNofill);
178 	if(tmp == nil){
179 		if(tmp0 != im)
180 			freeimage(tmp0);
181 		return;
182 	}
183 	for(gran=1; gran<Dx(im->r); gran *= 2)
184 		;
185 	gran /= 4;
186 
187 	rmask.min = ZP;
188 	rmask.max = (Point){2*gran, 100};
189 
190 	mask = xallocimage(display, rmask, GREY1, 1, DTransparent);
191 	mtmp = xallocimage(display, rmask, GREY1, 1, DTransparent);
192 	if(mask == nil || mtmp == nil) {
193 		fprint(2, "out of memory during rot180: %r\n");
194 		wexits("memory");
195 	}
196 	rmask.max.x = gran;
197 	drawop(mask, rmask, display->opaque, nil, ZP, S);
198 //	writefile("mask", mask, gran);
199 	shuffle(im, tmp, Xaxis, Dx(im->r), mask, gran, 0);
200 	freeimage(mask);
201 	freeimage(mtmp);
202 
203 	for(gran=1; gran<Dy(im->r); gran *= 2)
204 		;
205 	gran /= 4;
206 	rmask.max = (Point){100, 2*gran};
207 	mask = xallocimage(display, rmask, GREY1, 1, DTransparent);
208 	mtmp = xallocimage(display, rmask, GREY1, 1, DTransparent);
209 	if(mask == nil || mtmp == nil) {
210 		fprint(2, "out of memory during rot180: %r\n");
211 		wexits("memory");
212 	}
213 	rmask.max.y = gran;
214 	drawop(mask, rmask, display->opaque, nil, ZP, S);
215 	shuffle(im, tmp, Yaxis, Dy(im->r), mask, gran, 0);
216 	freeimage(mask);
217 	freeimage(mtmp);
218 	freeimage(tmp);
219 	if(tmp0 != im)
220 		freeimage(tmp0);
221 }
222 
223 /* rotates an image 90 degrees clockwise */
224 Image *
225 rot90(Image *im)
226 {
227 	Image *tmp;
228 	int i, j, dx, dy;
229 
230 	dx = Dx(im->r);
231 	dy = Dy(im->r);
232 	tmp = xallocimage(display, Rect(0, 0, dy, dx), im->chan, 0, DCyan);
233 	if(tmp == nil) {
234 		fprint(2, "out of memory during rot90: %r\n");
235 		wexits("memory");
236 	}
237 
238 	for(j = 0; j < dx; j++) {
239 		for(i = 0; i < dy; i++) {
240 			drawop(tmp, Rect(i, j, i+1, j+1), im, nil, Pt(j, dy-(i+1)), S);
241 		}
242 	}
243 	freeimage(im);
244 
245 	return(tmp);
246 }
247 
248 /* from resample.c -- resize from → to using interpolation */
249 
250 
251 #define K2 7	/* from -.7 to +.7 inclusive, meaning .2 into each adjacent pixel */
252 #define NK (2*K2+1)
253 double K[NK];
254 
255 double
256 fac(int L)
257 {
258 	int i, f;
259 
260 	f = 1;
261 	for(i=L; i>1; --i)
262 		f *= i;
263 	return f;
264 }
265 
266 /* 
267  * i0(x) is the modified Bessel function, Σ (x/2)^2L / (L!)²
268  * There are faster ways to calculate this, but we precompute
269  * into a table so let's keep it simple.
270  */
271 double
272 i0(double x)
273 {
274 	double v;
275 	int L;
276 
277 	v = 1.0;
278 	for(L=1; L<10; L++)
279 		v += pow(x/2., 2*L)/pow(fac(L), 2);
280 	return v;
281 }
282 
283 double
284 kaiser(double x, double tau, double alpha)
285 {
286 	if(fabs(x) > tau)
287 		return 0.;
288 	return i0(alpha*sqrt(1-(x*x/(tau*tau))))/i0(alpha);
289 }
290 
291 void
292 resamplex(uchar *in, int off, int d, int inx, uchar *out, int outx)
293 {
294 	int i, x, k;
295 	double X, xx, v, rat;
296 
297 
298 	rat = (double)inx/(double)outx;
299 	for(x=0; x<outx; x++){
300 		if(inx == outx){
301 			/* don't resample if size unchanged */
302 			out[off+x*d] = in[off+x*d];
303 			continue;
304 		}
305 		v = 0.0;
306 		X = x*rat;
307 		for(k=-K2; k<=K2; k++){
308 			xx = X + rat*k/10.;
309 			i = xx;
310 			if(i < 0)
311 				i = 0;
312 			if(i >= inx)
313 				i = inx-1;
314 			v += in[off+i*d] * K[K2+k];
315 		}
316 		out[off+x*d] = v;
317 	}
318 }
319 
320 void
321 resampley(uchar **in, int off, int iny, uchar **out, int outy)
322 {
323 	int y, i, k;
324 	double Y, yy, v, rat;
325 
326 	rat = (double)iny/(double)outy;
327 	for(y=0; y<outy; y++){
328 		if(iny == outy){
329 			/* don't resample if size unchanged */
330 			out[y][off] = in[y][off];
331 			continue;
332 		}
333 		v = 0.0;
334 		Y = y*rat;
335 		for(k=-K2; k<=K2; k++){
336 			yy = Y + rat*k/10.;
337 			i = yy;
338 			if(i < 0)
339 				i = 0;
340 			if(i >= iny)
341 				i = iny-1;
342 			v += in[i][off] * K[K2+k];
343 		}
344 		out[y][off] = v;
345 	}
346 
347 }
348 
349 Image*
350 resample(Image *from, Image *to)
351 {
352 	int i, j, bpl, nchan;
353 	uchar **oscan, **nscan;
354 	char tmp[20];
355 	int xsize, ysize;
356 	double v;
357 	Image *t1, *t2;
358 	ulong tchan;
359 
360 	for(i=-K2; i<=K2; i++){
361 		K[K2+i] = kaiser(i/10., K2/10., 4.);
362 	}
363 
364 	/* normalize */
365 	v = 0.0;
366 	for(i=0; i<NK; i++)
367 		v += K[i];
368 	for(i=0; i<NK; i++)
369 		K[i] /= v;
370 
371 	switch(from->chan){
372 	case GREY8:
373 	case RGB24:
374 	case RGBA32:
375 	case ARGB32:
376 	case XRGB32:
377 		break;
378 
379 	case CMAP8:
380 	case RGB15:
381 	case RGB16:
382 		tchan = RGB24;
383 		goto Convert;
384 
385 	case GREY1:
386 	case GREY2:
387 	case GREY4:
388 		tchan = GREY8;
389 	Convert:
390 		/* use library to convert to byte-per-chan form, then convert back */
391 		t1 = xallocimage(display, Rect(0, 0, Dx(from->r), Dy(from->r)), tchan, 0, DNofill);
392 		if(t1 == nil) {
393 			fprint(2, "out of memory for temp image 1 in resample: %r\n");
394 			wexits("memory");
395 		}
396 		drawop(t1, t1->r, from, nil, ZP, S);
397 		t2 = xallocimage(display, to->r, tchan, 0, DNofill);
398 		if(t2 == nil) {
399 			fprint(2, "out of memory temp image 2 in resample: %r\n");
400 			wexits("memory");
401 		}
402 		resample(t1, t2);
403 		drawop(to, to->r, t2, nil, ZP, S);
404 		freeimage(t1);
405 		freeimage(t2);
406 		return to;
407 
408 	default:
409 		sysfatal("can't handle channel type %s", chantostr(tmp, from->chan));
410 	}
411 
412 	xsize = Dx(to->r);
413 	ysize = Dy(to->r);
414 	oscan = malloc(Dy(from->r)*sizeof(uchar*));
415 	nscan = malloc(max(ysize, Dy(from->r))*sizeof(uchar*));
416 	if(oscan == nil || nscan == nil)
417 		sysfatal("can't allocate: %r");
418 
419 	/* unload original image into scan lines */
420 	bpl = bytesperline(from->r, from->depth);
421 	for(i=0; i<Dy(from->r); i++){
422 		oscan[i] = malloc(bpl);
423 		if(oscan[i] == nil)
424 			sysfatal("can't allocate: %r");
425 		j = unloadimage(from, Rect(from->r.min.x, from->r.min.y+i, from->r.max.x, from->r.min.y+i+1), oscan[i], bpl);
426 		if(j != bpl)
427 			sysfatal("unloadimage");
428 	}
429 
430 	/* allocate scan lines for destination. we do y first, so need at least Dy(from->r) lines */
431 	bpl = bytesperline(Rect(0, 0, xsize, Dy(from->r)), from->depth);
432 	for(i=0; i<max(ysize, Dy(from->r)); i++){
433 		nscan[i] = malloc(bpl);
434 		if(nscan[i] == nil)
435 			sysfatal("can't allocate: %r");
436 	}
437 
438 	/* resample in X */
439 	nchan = from->depth/8;
440 	for(i=0; i<Dy(from->r); i++){
441 		for(j=0; j<nchan; j++){
442 			if(j==0 && from->chan==XRGB32)
443 				continue;
444 			resamplex(oscan[i], j, nchan, Dx(from->r), nscan[i], xsize);
445 		}
446 		free(oscan[i]);
447 		oscan[i] = nscan[i];
448 		nscan[i] = malloc(bpl);
449 		if(nscan[i] == nil)
450 			sysfatal("can't allocate: %r");
451 	}
452 
453 	/* resample in Y */
454 	for(i=0; i<xsize; i++)
455 		for(j=0; j<nchan; j++)
456 			resampley(oscan, nchan*i+j, Dy(from->r), nscan, ysize);
457 
458 	/* pack data into destination */
459 	bpl = bytesperline(to->r, from->depth);
460 	for(i=0; i<ysize; i++){
461 		j = loadimage(to, Rect(0, i, xsize, i+1), nscan[i], bpl);
462 		if(j != bpl)
463 			sysfatal("loadimage: %r");
464 	}
465 
466 	for(i=0; i<Dy(from->r); i++){
467 		free(oscan[i]);
468 		free(nscan[i]);
469 	}
470 	free(oscan);
471 	free(nscan);
472 
473 	return to;
474 }