diff options
Diffstat (limited to 'src/cmd/page/nrotate.c')
-rw-r--r-- | src/cmd/page/nrotate.c | 277 |
1 files changed, 277 insertions, 0 deletions
diff --git a/src/cmd/page/nrotate.c b/src/cmd/page/nrotate.c new file mode 100644 index 00000000..2225ec3f --- /dev/null +++ b/src/cmd/page/nrotate.c @@ -0,0 +1,277 @@ +/* + * Rotate an image 180° in O(log Dx + log Dy) + * draw calls, using an extra buffer the same size + * as the image. + * + * The basic concept is that you can invert an array by + * inverting the top half, inverting the bottom half, and + * then swapping them. + * + * This is usually overkill, but it speeds up slow remote + * connections quite a bit. + */ + +#include <u.h> +#include <libc.h> +#include <bio.h> +#include <draw.h> +#include <event.h> +#include "page.h" + +int ndraw = 0; + +enum { + Xaxis, + Yaxis, +}; + +static void reverse(Image*, Image*, int); +static void shuffle(Image*, Image*, int, int, Image*, int, int); +static void writefile(char *name, Image *im, int gran); +static void halvemaskdim(Image*); +static void swapranges(Image*, Image*, int, int, int, int); + +/* + * Rotate the image 180° by reflecting first + * along the X axis, and then along the Y axis. + */ +void +rot180(Image *img) +{ + Image *tmp; + + tmp = xallocimage(display, img->r, img->chan, 0, DNofill); + if(tmp == nil) + return; + + reverse(img, tmp, Xaxis); + reverse(img, tmp, Yaxis); + + freeimage(tmp); +} + +Image *mtmp; + +static void +reverse(Image *img, Image *tmp, int axis) +{ + Image *mask; + Rectangle r; + int i, d; + + /* + * We start by swapping large chunks at a time. + * The chunk size should be the largest power of + * two that fits in the dimension. + */ + d = axis==Xaxis ? Dx(img) : Dy(img); + for(i = 1; i*2 <= d; i *= 2) + ; + + r = axis==Xaxis ? Rect(0,0, i,100) : Rect(0,0, 100,i); + mask = xallocimage(display, r, GREY1, 1, DTransparent); + mtmp = xallocimage(display, r, GREY1, 1, DTransparent); + + /* + * Now color the bottom (or left) half of the mask opaque. + */ + if(axis==Xaxis) + r.max.x /= 2; + else + r.max.y /= 2; + + draw(mask, r, display->opaque, nil, ZP); + writefile("mask", mask, i); + + /* + * Shuffle will recur, shuffling the pieces as necessary + * and making the mask a finer and finer grating. + */ + shuffle(img, tmp, axis, d, mask, i, 0); + + freeimage(mask); +} + +/* + * Shuffle the image by swapping pieces of size maskdim. + */ +static void +shuffle(Image *img, Image *tmp, int axis, int imgdim, Image *mask, int maskdim) +{ + int slop; + + if(maskdim == 0) + return; + + /* + * Figure out how much will be left over that needs to be + * shifted specially to the bottom. + */ + slop = imgdim % maskdim; + + /* + * Swap adjacent grating lines as per mask. + */ + swapadjacent(img, tmp, axis, imgdim - slop, mask, maskdim); + + /* + * Calculate the mask with gratings half as wide and recur. + */ + halvemaskdim(mask, maskdim, axis); + writefile("mask", mask, maskdim/2); + + shuffle(img, tmp, axis, imgdim, mask, maskdim/2); + + /* + * Move the slop down to the bottom of the image. + */ + swapranges(img, tmp, 0, imgdim-slop, imgdim, axis); + moveup(im, tmp, lastnn, nn, n, axis); +} + +/* + * Halve the grating period in the mask. + * The grating currently looks like + * ####____####____####____####____ + * where #### is opacity. + * + * We want + * ##__##__##__##__##__##__##__##__ + * which is achieved by shifting the mask + * and drawing on itself through itself. + * Draw doesn't actually allow this, so + * we have to copy it first. + * + * ####____####____####____####____ (dst) + * + ____####____####____####____#### (src) + * in __####____####____####____####__ (mask) + * =========================================== + * ##__##__##__##__##__##__##__##__ + */ +static void +halvemaskdim(Image *m, int maskdim, int axis) +{ + Point δ; + + δ = axis==Xaxis ? Pt(maskdim,0) : Pt(0,maskdim); + draw(mtmp, mtmp->r, mask, nil, mask->r.min); + gendraw(mask, mask->r, mtmp, δ, mtmp, divpt(δ,2)); + writefile("mask", mask, maskdim/2); +} + +/* + * Swap the regions [a,b] and [b,c] + */ +static void +swapranges(Image *img, Image *tmp, int a, int b, int c, int axis) +{ + Rectangle r; + Point δ; + + if(a == b || b == c) + return; + + writefile("swap", img, 0); + draw(tmp, tmp->r, im, nil, im->r.min); + + /* [a,a+(c-b)] gets [b,c] */ + r = img->r; + if(axis==Xaxis){ + δ = Pt(1,0); + r.min.x = img->r.min.x + a; + r.max.x = img->r.min.x + a + (c-b); + }else{ + δ = Pt(0,1); + r.min.y = img->r.min.y + a; + r.max.y = img->r.min.y + a + (c-b); + } + draw(img, r, tmp, nil, addpt(tmp->r.min, mulpt(δ, b))); + + /* [a+(c-b), c] gets [a,b] */ + r = img->r; + if(axis==Xaxis){ + r.min.x = img->r.min.x + a + (c-b); + r.max.x = img->r.min.x + c; + }else{ + r.min.y = img->r.min.y + a + (c-b); + r.max.y = img->r.min.y + c; + } + draw(img, r, tmp, nil, addpt(tmp->r.min, mulpt(δ, a))); + writefile("swap", img, 1); +} + +/* + * Swap adjacent regions as specified by the grating. + * We do this by copying the image through the mask twice, + * once aligned with the grading and once 180° out of phase. + */ +static void +swapadjacent(Image *img, Image *tmp, int axis, int imgdim, Image *mask, int maskdim) +{ + Point δ; + Rectangle r0, r1; + + δ = axis==Xaxis ? Pt(1,0) : Pt(0,1); + + r0 = img->r; + r1 = img->r; + switch(axis){ + case Xaxis: + r0.max.x = imgdim; + r1.min.x = imgdim; + break; + case Yaxis: + r0.max.y = imgdim; + r1.min.y = imgdim; + } + + /* + * r0 is the lower rectangle, while r1 is the upper one. + */ + draw(tmp, tmp->r, img, nil, +} + +void +interlace(Image *im, Image *tmp, int axis, int n, Image *mask, int gran) +{ + Point p0, p1; + Rectangle r0, r1; + + r0 = im->r; + r1 = im->r; + switch(axis) { + case Xaxis: + r0.max.x = n; + r1.min.x = n; + p0 = (Point){gran, 0}; + p1 = (Point){-gran, 0}; + break; + case Yaxis: + r0.max.y = n; + r1.min.y = n; + p0 = (Point){0, gran}; + p1 = (Point){0, -gran}; + break; + } + + draw(tmp, im->r, im, display->black, im->r.min); + gendraw(im, r0, tmp, p0, mask, mask->r.min); + gendraw(im, r0, tmp, p1, mask, p1); +} + + +static void +writefile(char *name, Image *im, int gran) +{ + static int c = 100; + int fd; + char buf[200]; + + snprint(buf, sizeof buf, "%d%s%d", c++, name, gran); + fd = create(buf, OWRITE, 0666); + if(fd < 0) + return; + writeimage(fd, im, 0); + close(fd); +} + |