123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500 |
- /*
- * rotate an image 180° in O(log Dx + log Dy) /dev/draw writes,
- * using an extra buffer 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.
- * the code does this slightly backwards to ensure O(log n) runtime.
- * (If you do it wrong, you can get O(log² n) runtime.)
- *
- * 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 = 0,
- Yaxis = 1,
- };
- Image *mtmp;
- 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);
- }
- void
- moveup(Image *im, Image *tmp, int a, int b, int c, int axis)
- {
- Rectangle range;
- Rectangle dr0, dr1;
- Point p0, p1;
- if(a == b || b == c)
- return;
- drawop(tmp, tmp->r, im, nil, im->r.min, S);
- switch(axis){
- case Xaxis:
- range = Rect(a, im->r.min.y, c, im->r.max.y);
- dr0 = range;
- dr0.max.x = dr0.min.x+(c-b);
- p0 = Pt(b, im->r.min.y);
- dr1 = range;
- dr1.min.x = dr1.max.x-(b-a);
- p1 = Pt(a, im->r.min.y);
- break;
- case Yaxis:
- range = Rect(im->r.min.x, a, im->r.max.x, c);
- dr0 = range;
- dr0.max.y = dr0.min.y+(c-b);
- p0 = Pt(im->r.min.x, b);
- dr1 = range;
- dr1.min.y = dr1.max.y-(b-a);
- p1 = Pt(im->r.min.x, a);
- break;
- }
- drawop(im, dr0, tmp, nil, p0, S);
- drawop(im, dr1, tmp, nil, p1, S);
- }
- 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;
- }
- drawop(tmp, im->r, im, display->opaque, im->r.min, S);
- gendrawop(im, r0, tmp, p0, mask, mask->r.min, S);
- gendrawop(im, r0, tmp, p1, mask, p1, S);
- }
- /*
- * 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)
- * ===========================================
- * ##__##__##__##__##__##__##__##__
- */
- int
- nextmask(Image *mask, int axis, int maskdim)
- {
- Point δ;
- δ = axis==Xaxis ? Pt(maskdim,0) : Pt(0,maskdim);
- drawop(mtmp, mtmp->r, mask, nil, mask->r.min, S);
- gendrawop(mask, mask->r, mtmp, δ, mtmp, divpt(δ,-2), S);
- // writefile("mask", mask, maskdim/2);
- return maskdim/2;
- }
- void
- shuffle(Image *im, Image *tmp, int axis, int n, Image *mask, int gran,
- int lastnn)
- {
- int nn, left;
- if(gran == 0)
- return;
- left = n%(2*gran);
- nn = n - left;
- interlace(im, tmp, axis, nn, mask, gran);
- // writefile("interlace", im, gran);
-
- gran = nextmask(mask, axis, gran);
- shuffle(im, tmp, axis, n, mask, gran, nn);
- // writefile("shuffle", im, gran);
- moveup(im, tmp, lastnn, nn, n, axis);
- // writefile("move", im, gran);
- }
- void
- rot180(Image *im)
- {
- Image *tmp, *tmp0;
- Image *mask;
- Rectangle rmask;
- int gran;
- if(chantodepth(im->chan) < 8){
- /* this speeds things up dramatically; draw is too slow on sub-byte pixel sizes */
- tmp0 = xallocimage(display, im->r, CMAP8, 0, DNofill);
- drawop(tmp0, tmp0->r, im, nil, im->r.min, S);
- }else
- tmp0 = im;
- tmp = xallocimage(display, tmp0->r, tmp0->chan, 0, DNofill);
- if(tmp == nil){
- if(tmp0 != im)
- freeimage(tmp0);
- return;
- }
- for(gran=1; gran<Dx(im->r); gran *= 2)
- ;
- gran /= 4;
- rmask.min = ZP;
- rmask.max = (Point){2*gran, 100};
- mask = xallocimage(display, rmask, GREY1, 1, DTransparent);
- mtmp = xallocimage(display, rmask, GREY1, 1, DTransparent);
- if(mask == nil || mtmp == nil) {
- fprint(2, "out of memory during rot180: %r\n");
- wexits("memory");
- }
- rmask.max.x = gran;
- drawop(mask, rmask, display->opaque, nil, ZP, S);
- // writefile("mask", mask, gran);
- shuffle(im, tmp, Xaxis, Dx(im->r), mask, gran, 0);
- freeimage(mask);
- freeimage(mtmp);
- for(gran=1; gran<Dy(im->r); gran *= 2)
- ;
- gran /= 4;
- rmask.max = (Point){100, 2*gran};
- mask = xallocimage(display, rmask, GREY1, 1, DTransparent);
- mtmp = xallocimage(display, rmask, GREY1, 1, DTransparent);
- if(mask == nil || mtmp == nil) {
- fprint(2, "out of memory during rot180: %r\n");
- wexits("memory");
- }
- rmask.max.y = gran;
- drawop(mask, rmask, display->opaque, nil, ZP, S);
- shuffle(im, tmp, Yaxis, Dy(im->r), mask, gran, 0);
- freeimage(mask);
- freeimage(mtmp);
- freeimage(tmp);
- if(tmp0 != im)
- freeimage(tmp0);
- }
- /* rotates an image 90 degrees clockwise */
- Image *
- rot90(Image *im)
- {
- Image *tmp;
- int i, j, dx, dy;
- dx = Dx(im->r);
- dy = Dy(im->r);
- tmp = xallocimage(display, Rect(0, 0, dy, dx), im->chan, 0, DCyan);
- if(tmp == nil) {
- fprint(2, "out of memory during rot90: %r\n");
- wexits("memory");
- }
- for(j = 0; j < dx; j++) {
- for(i = 0; i < dy; i++) {
- drawop(tmp, Rect(i, j, i+1, j+1), im, nil, Pt(j, dy-(i+1)), S);
- }
- }
- freeimage(im);
- return(tmp);
- }
- /* rotates an image 270 degrees clockwise */
- Image *
- rot270(Image *im)
- {
- Image *tmp;
- int i, j, dx, dy;
- dx = Dx(im->r);
- dy = Dy(im->r);
- tmp = xallocimage(display, Rect(0, 0, dy, dx), im->chan, 0, DCyan);
- if(tmp == nil) {
- fprint(2, "out of memory during rot270: %r\n");
- wexits("memory");
- }
- for(i = 0; i < dy; i++) {
- for(j = 0; j < dx; j++) {
- drawop(tmp, Rect(i, j, i+1, j+1), im, nil, Pt(dx-(j+1), i), S);
- }
- }
- freeimage(im);
- return(tmp);
- }
- /* from resample.c -- resize from → to using interpolation */
- #define K2 7 /* from -.7 to +.7 inclusive, meaning .2 into each adjacent pixel */
- #define NK (2*K2+1)
- double K[NK];
- double
- fac(int L)
- {
- int i, f;
- f = 1;
- for(i=L; i>1; --i)
- f *= i;
- return f;
- }
- /*
- * i0(x) is the modified Bessel function, Σ (x/2)^2L / (L!)²
- * There are faster ways to calculate this, but we precompute
- * into a table so let's keep it simple.
- */
- double
- i0(double x)
- {
- double v;
- int L;
- v = 1.0;
- for(L=1; L<10; L++)
- v += pow(x/2., 2*L)/pow(fac(L), 2);
- return v;
- }
- double
- kaiser(double x, double τ, double α)
- {
- if(fabs(x) > τ)
- return 0.;
- return i0(α*sqrt(1-(x*x/(τ*τ))))/i0(α);
- }
- void
- resamplex(uchar *in, int off, int d, int inx, uchar *out, int outx)
- {
- int i, x, k;
- double X, xx, v, rat;
- rat = (double)inx/(double)outx;
- for(x=0; x<outx; x++){
- if(inx == outx){
- /* don't resample if size unchanged */
- out[off+x*d] = in[off+x*d];
- continue;
- }
- v = 0.0;
- X = x*rat;
- for(k=-K2; k<=K2; k++){
- xx = X + rat*k/10.;
- i = xx;
- if(i < 0)
- i = 0;
- if(i >= inx)
- i = inx-1;
- v += in[off+i*d] * K[K2+k];
- }
- out[off+x*d] = v;
- }
- }
- void
- resampley(uchar **in, int off, int iny, uchar **out, int outy)
- {
- int y, i, k;
- double Y, yy, v, rat;
- rat = (double)iny/(double)outy;
- for(y=0; y<outy; y++){
- if(iny == outy){
- /* don't resample if size unchanged */
- out[y][off] = in[y][off];
- continue;
- }
- v = 0.0;
- Y = y*rat;
- for(k=-K2; k<=K2; k++){
- yy = Y + rat*k/10.;
- i = yy;
- if(i < 0)
- i = 0;
- if(i >= iny)
- i = iny-1;
- v += in[i][off] * K[K2+k];
- }
- out[y][off] = v;
- }
- }
- Image*
- resample(Image *from, Image *to)
- {
- int i, j, bpl, nchan;
- uchar **oscan, **nscan;
- char tmp[20];
- int xsize, ysize;
- double v;
- Image *t1, *t2;
- ulong tchan;
- for(i=-K2; i<=K2; i++){
- K[K2+i] = kaiser(i/10., K2/10., 4.);
- }
- /* normalize */
- v = 0.0;
- for(i=0; i<NK; i++)
- v += K[i];
- for(i=0; i<NK; i++)
- K[i] /= v;
- switch(from->chan){
- case GREY8:
- case RGB24:
- case RGBA32:
- case ARGB32:
- case XRGB32:
- break;
- case CMAP8:
- case RGB15:
- case RGB16:
- tchan = RGB24;
- goto Convert;
- case GREY1:
- case GREY2:
- case GREY4:
- tchan = GREY8;
- Convert:
- /* use library to convert to byte-per-chan form, then convert back */
- t1 = xallocimage(display, Rect(0, 0, Dx(from->r), Dy(from->r)), tchan, 0, DNofill);
- if(t1 == nil) {
- fprint(2, "out of memory for temp image 1 in resample: %r\n");
- wexits("memory");
- }
- drawop(t1, t1->r, from, nil, ZP, S);
- t2 = xallocimage(display, to->r, tchan, 0, DNofill);
- if(t2 == nil) {
- fprint(2, "out of memory temp image 2 in resample: %r\n");
- wexits("memory");
- }
- resample(t1, t2);
- drawop(to, to->r, t2, nil, ZP, S);
- freeimage(t1);
- freeimage(t2);
- return to;
- default:
- sysfatal("can't handle channel type %s", chantostr(tmp, from->chan));
- }
- xsize = Dx(to->r);
- ysize = Dy(to->r);
- oscan = malloc(Dy(from->r)*sizeof(uchar*));
- nscan = malloc(max(ysize, Dy(from->r))*sizeof(uchar*));
- if(oscan == nil || nscan == nil)
- sysfatal("can't allocate: %r");
- /* unload original image into scan lines */
- bpl = bytesperline(from->r, from->depth);
- for(i=0; i<Dy(from->r); i++){
- oscan[i] = malloc(bpl);
- if(oscan[i] == nil)
- sysfatal("can't allocate: %r");
- j = unloadimage(from, Rect(from->r.min.x, from->r.min.y+i, from->r.max.x, from->r.min.y+i+1), oscan[i], bpl);
- if(j != bpl)
- sysfatal("unloadimage");
- }
- /* allocate scan lines for destination. we do y first, so need at least Dy(from->r) lines */
- bpl = bytesperline(Rect(0, 0, xsize, Dy(from->r)), from->depth);
- for(i=0; i<max(ysize, Dy(from->r)); i++){
- nscan[i] = malloc(bpl);
- if(nscan[i] == nil)
- sysfatal("can't allocate: %r");
- }
- /* resample in X */
- nchan = from->depth/8;
- for(i=0; i<Dy(from->r); i++){
- for(j=0; j<nchan; j++){
- if(j==0 && from->chan==XRGB32)
- continue;
- resamplex(oscan[i], j, nchan, Dx(from->r), nscan[i], xsize);
- }
- free(oscan[i]);
- oscan[i] = nscan[i];
- nscan[i] = malloc(bpl);
- if(nscan[i] == nil)
- sysfatal("can't allocate: %r");
- }
- /* resample in Y */
- for(i=0; i<xsize; i++)
- for(j=0; j<nchan; j++)
- resampley(oscan, nchan*i+j, Dy(from->r), nscan, ysize);
- /* pack data into destination */
- bpl = bytesperline(to->r, from->depth);
- for(i=0; i<ysize; i++){
- j = loadimage(to, Rect(0, i, xsize, i+1), nscan[i], bpl);
- if(j != bpl)
- sysfatal("loadimage: %r");
- }
- for(i=0; i<Dy(from->r); i++){
- free(oscan[i]);
- free(nscan[i]);
- }
- free(oscan);
- free(nscan);
- return to;
- }
|