1 /*
2  * Rotate an image 180° in O(log Dx + log Dy)
3  * draw calls, using an extra buffer the same size
4  * as the image.
5  *
6  * The basic concept is that you can invert an array by
7  * inverting the top half, inverting the bottom half, and
8  * then swapping them.
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 
23 enum {
24 	Xaxis,
25 	Yaxis,
26 };
27 
28 static void reverse(Image*, Image*, int);
29 static void shuffle(Image*, Image*, int, int, Image*, int, int);
30 static void writefile(char *name, Image *im, int gran);
31 static void halvemaskdim(Image*);
32 static void swapranges(Image*, Image*, int, int, int, int);
33 
34 /*
35  * Rotate the image 180° by reflecting first
36  * along the X axis, and then along the Y axis.
37  */
38 void
39 rot180(Image *img)
40 {
41 	Image *tmp;
42 
43 	tmp = xallocimage(display, img->r, img->chan, 0, DNofill);
44 	if(tmp == nil)
45 		return;
46 
47 	reverse(img, tmp, Xaxis);
48 	reverse(img, tmp, Yaxis);
49 
50 	freeimage(tmp);
51 }
52 
53 Image *mtmp;
54 
55 static void
56 reverse(Image *img, Image *tmp, int axis)
57 {
58 	Image *mask;
59 	Rectangle r;
60 	int i, d;
61 
62 	/*
63 	 * We start by swapping large chunks at a time.
64 	 * The chunk size should be the largest power of
65 	 * two that fits in the dimension.
66 	 */
67 	d = axis==Xaxis ? Dx(img) : Dy(img);
68 	for(i = 1; i*2 <= d; i *= 2)
69 		;
70 
71 	r = axis==Xaxis ? Rect(0,0, i,100) : Rect(0,0, 100,i);
72 	mask = xallocimage(display, r, GREY1, 1, DTransparent);
73 	mtmp = xallocimage(display, r, GREY1, 1, DTransparent);
74 
75 	/*
76 	 * Now color the bottom (or left) half of the mask opaque.
77 	 */
78 	if(axis==Xaxis)
79 		r.max.x /= 2;
80 	else
81 		r.max.y /= 2;
82 
83 	draw(mask, r, display->opaque, nil, ZP);
84 	writefile("mask", mask, i);
85 
86 	/*
87 	 * Shuffle will recur, shuffling the pieces as necessary
88 	 * and making the mask a finer and finer grating.
89 	 */
90 	shuffle(img, tmp, axis, d, mask, i, 0);
91 
92 	freeimage(mask);
93 }
94 
95 /*
96  * Shuffle the image by swapping pieces of size maskdim.
97  */
98 static void
99 shuffle(Image *img, Image *tmp, int axis, int imgdim, Image *mask, int maskdim)
100 {
101 	int slop;
102 
103 	if(maskdim == 0)
104 		return;
105 
106 	/*
107 	 * Figure out how much will be left over that needs to be
108 	 * shifted specially to the bottom.
109 	 */
110 	slop = imgdim % maskdim;
111 
112 	/*
113 	 * Swap adjacent grating lines as per mask.
114 	 */
115 	swapadjacent(img, tmp, axis, imgdim - slop, mask, maskdim);
116 
117 	/*
118 	 * Calculate the mask with gratings half as wide and recur.
119 	 */
120 	halvemaskdim(mask, maskdim, axis);
121 	writefile("mask", mask, maskdim/2);
122 
123 	shuffle(img, tmp, axis, imgdim, mask, maskdim/2);
124 
125 	/*
126 	 * Move the slop down to the bottom of the image.
127 	 */
128 	swapranges(img, tmp, 0, imgdim-slop, imgdim, axis);
129 	moveup(im, tmp, lastnn, nn, n, axis);
130 }
131 
132 /*
133  * Halve the grating period in the mask.
134  * The grating currently looks like 
135  * ####____####____####____####____
136  * where #### is opacity.
137  *
138  * We want
139  * ##__##__##__##__##__##__##__##__
140  * which is achieved by shifting the mask
141  * and drawing on itself through itself.
142  * Draw doesn't actually allow this, so 
143  * we have to copy it first.
144  *
145  *     ####____####____####____####____ (dst)
146  * +   ____####____####____####____#### (src)
147  * in  __####____####____####____####__ (mask)
148  * ===========================================
149  *     ##__##__##__##__##__##__##__##__
150  */
151 static void
152 halvemaskdim(Image *m, int maskdim, int axis)
153 {
154 	Point δ;
155 
156 	δ = axis==Xaxis ? Pt(maskdim,0) : Pt(0,maskdim);
157 	draw(mtmp, mtmp->r, mask, nil, mask->r.min);
158 	gendraw(mask, mask->r, mtmp, δ, mtmp, divpt(δ,2));
159 	writefile("mask", mask, maskdim/2);
160 }
161 
162 /*
163  * Swap the regions [a,b] and [b,c]
164  */
165 static void
166 swapranges(Image *img, Image *tmp, int a, int b, int c, int axis)
167 {
168 	Rectangle r;
169 	Point δ;
170 
171 	if(a == b || b == c)
172 		return;
173 
174 	writefile("swap", img, 0);
175 	draw(tmp, tmp->r, im, nil, im->r.min);
176 
177 	/* [a,a+(c-b)] gets [b,c] */
178 	r = img->r;
179 	if(axis==Xaxis){
180 		δ = Pt(1,0);
181 		r.min.x = img->r.min.x + a;
182 		r.max.x = img->r.min.x + a + (c-b);
183 	}else{
184 		δ = Pt(0,1);
185 		r.min.y = img->r.min.y + a;
186 		r.max.y = img->r.min.y + a + (c-b);
187 	}
188 	draw(img, r, tmp, nil, addpt(tmp->r.min, mulpt(δ, b)));
189 
190 	/* [a+(c-b), c] gets [a,b] */
191 	r = img->r;
192 	if(axis==Xaxis){
193 		r.min.x = img->r.min.x + a + (c-b);
194 		r.max.x = img->r.min.x + c;
195 	}else{
196 		r.min.y = img->r.min.y + a + (c-b);
197 		r.max.y = img->r.min.y + c;
198 	}
199 	draw(img, r, tmp, nil, addpt(tmp->r.min, mulpt(δ, a)));
200 	writefile("swap", img, 1);
201 }
202 
203 /*
204  * Swap adjacent regions as specified by the grating.
205  * We do this by copying the image through the mask twice,
206  * once aligned with the grading and once 180° out of phase.
207  */
208 static void
209 swapadjacent(Image *img, Image *tmp, int axis, int imgdim, Image *mask, int maskdim)
210 {
211 	Point δ;
212 	Rectangle r0, r1;
213 
214 	δ = axis==Xaxis ? Pt(1,0) : Pt(0,1);
215 
216 	r0 = img->r;
217 	r1 = img->r;
218 	switch(axis){
219 	case Xaxis:
220 		r0.max.x = imgdim;
221 		r1.min.x = imgdim;
222 		break;
223 	case Yaxis:
224 		r0.max.y = imgdim;
225 		r1.min.y = imgdim;
226 	}
227 
228 	/*
229 	 * r0 is the lower rectangle, while r1 is the upper one.
230 	 */
231 	draw(tmp, tmp->r, img, nil, 
232 }
233 
234 void
235 interlace(Image *im, Image *tmp, int axis, int n, Image *mask, int gran)
236 {
237 	Point p0, p1;
238 	Rectangle r0, r1;
239 
240 	r0 = im->r;
241 	r1 = im->r;
242 	switch(axis) {
243 	case Xaxis:
244 		r0.max.x = n;
245 		r1.min.x = n;
246 		p0 = (Point){gran, 0};
247 		p1 = (Point){-gran, 0};
248 		break;
249 	case Yaxis:
250 		r0.max.y = n;
251 		r1.min.y = n;
252 		p0 = (Point){0, gran};
253 		p1 = (Point){0, -gran};
254 		break;
255 	}
256 
257 	draw(tmp, im->r, im, display->black, im->r.min);
258 	gendraw(im, r0, tmp, p0, mask, mask->r.min);
259 	gendraw(im, r0, tmp, p1, mask, p1);
260 }
261 
262 
263 static void
264 writefile(char *name, Image *im, int gran)
265 {
266 	static int c = 100;
267 	int fd;
268 	char buf[200];
269 
270 	snprint(buf, sizeof buf, "%d%s%d", c++, name, gran);
271 	fd = create(buf, OWRITE, 0666);
272 	if(fd < 0)
273 		return;	
274 	writeimage(fd, im, 0);
275 	close(fd);
276 }
277