sys/src/cmd/page/nrotate.c

   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