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 δ; 133 134 δ = 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, δ, mtmp, divpt(δ,-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 rmask.max.x = gran; 193 drawop(mask, rmask, display->opaque, nil, ZP, S); 194 // writefile("mask", mask, gran); 195 shuffle(im, tmp, Xaxis, Dx(im->r), mask, gran, 0); 196 freeimage(mask); 197 freeimage(mtmp); 198 199 for(gran=1; gran<Dy(im->r); gran *= 2) 200 ; 201 gran /= 4; 202 rmask.max = (Point){100, 2*gran}; 203 mask = xallocimage(display, rmask, GREY1, 1, DTransparent); 204 mtmp = xallocimage(display, rmask, GREY1, 1, DTransparent); 205 rmask.max.y = gran; 206 drawop(mask, rmask, display->opaque, nil, ZP, S); 207 shuffle(im, tmp, Yaxis, Dy(im->r), mask, gran, 0); 208 freeimage(mask); 209 freeimage(mtmp); 210 freeimage(tmp); 211 if(tmp0 != im) 212 freeimage(tmp0); 213 } 214