Blame | Last modification | View Log | RSS feed
/*
* 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;
}