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