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 if(mask == nil || mtmp == nil) { 193 fprint(2, "out of memory during rot180: %r\n"); 194 wexits("memory"); 195 } 196 rmask.max.x = gran; 197 drawop(mask, rmask, display->opaque, nil, ZP, S); 198 // writefile("mask", mask, gran); 199 shuffle(im, tmp, Xaxis, Dx(im->r), mask, gran, 0); 200 freeimage(mask); 201 freeimage(mtmp); 202 203 for(gran=1; gran<Dy(im->r); gran *= 2) 204 ; 205 gran /= 4; 206 rmask.max = (Point){100, 2*gran}; 207 mask = xallocimage(display, rmask, GREY1, 1, DTransparent); 208 mtmp = xallocimage(display, rmask, GREY1, 1, DTransparent); 209 if(mask == nil || mtmp == nil) { 210 fprint(2, "out of memory during rot180: %r\n"); 211 wexits("memory"); 212 } 213 rmask.max.y = gran; 214 drawop(mask, rmask, display->opaque, nil, ZP, S); 215 shuffle(im, tmp, Yaxis, Dy(im->r), mask, gran, 0); 216 freeimage(mask); 217 freeimage(mtmp); 218 freeimage(tmp); 219 if(tmp0 != im) 220 freeimage(tmp0); 221 } 222 223 /* rotates an image 90 degrees clockwise */ 224 Image * 225 rot90(Image *im) 226 { 227 Image *tmp; 228 int i, j, dx, dy; 229 230 dx = Dx(im->r); 231 dy = Dy(im->r); 232 tmp = xallocimage(display, Rect(0, 0, dy, dx), im->chan, 0, DCyan); 233 if(tmp == nil) { 234 fprint(2, "out of memory during rot90: %r\n"); 235 wexits("memory"); 236 } 237 238 for(j = 0; j < dx; j++) { 239 for(i = 0; i < dy; i++) { 240 drawop(tmp, Rect(i, j, i+1, j+1), im, nil, Pt(j, dy-(i+1)), S); 241 } 242 } 243 freeimage(im); 244 245 return(tmp); 246 } 247 248 /* from resample.c -- resize from → to using interpolation */ 249 250 251 #define K2 7 /* from -.7 to +.7 inclusive, meaning .2 into each adjacent pixel */ 252 #define NK (2*K2+1) 253 double K[NK]; 254 255 double 256 fac(int L) 257 { 258 int i, f; 259 260 f = 1; 261 for(i=L; i>1; --i) 262 f *= i; 263 return f; 264 } 265 266 /* 267 * i0(x) is the modified Bessel function, Σ (x/2)^2L / (L!)² 268 * There are faster ways to calculate this, but we precompute 269 * into a table so let's keep it simple. 270 */ 271 double 272 i0(double x) 273 { 274 double v; 275 int L; 276 277 v = 1.0; 278 for(L=1; L<10; L++) 279 v += pow(x/2., 2*L)/pow(fac(L), 2); 280 return v; 281 } 282 283 double 284 kaiser(double x, double τ, double α) 285 { 286 if(fabs(x) > τ) 287 return 0.; 288 return i0(α*sqrt(1-(x*x/(τ*τ))))/i0(α); 289 } 290 291 292 void 293 resamplex(uchar *in, int off, int d, int inx, uchar *out, int outx) 294 { 295 int i, x, k; 296 double X, xx, v, rat; 297 298 299 rat = (double)inx/(double)outx; 300 for(x=0; x<outx; x++){ 301 if(inx == outx){ 302 /* don't resample if size unchanged */ 303 out[off+x*d] = in[off+x*d]; 304 continue; 305 } 306 v = 0.0; 307 X = x*rat; 308 for(k=-K2; k<=K2; k++){ 309 xx = X + rat*k/10.; 310 i = xx; 311 if(i < 0) 312 i = 0; 313 if(i >= inx) 314 i = inx-1; 315 v += in[off+i*d] * K[K2+k]; 316 } 317 out[off+x*d] = v; 318 } 319 } 320 321 void 322 resampley(uchar **in, int off, int iny, uchar **out, int outy) 323 { 324 int y, i, k; 325 double Y, yy, v, rat; 326 327 rat = (double)iny/(double)outy; 328 for(y=0; y<outy; y++){ 329 if(iny == outy){ 330 /* don't resample if size unchanged */ 331 out[y][off] = in[y][off]; 332 continue; 333 } 334 v = 0.0; 335 Y = y*rat; 336 for(k=-K2; k<=K2; k++){ 337 yy = Y + rat*k/10.; 338 i = yy; 339 if(i < 0) 340 i = 0; 341 if(i >= iny) 342 i = iny-1; 343 v += in[i][off] * K[K2+k]; 344 } 345 out[y][off] = v; 346 } 347 348 } 349 350 Image* 351 resample(Image *from, Image *to) 352 { 353 int i, j, bpl, nchan; 354 uchar **oscan, **nscan; 355 char tmp[20]; 356 int xsize, ysize; 357 double v; 358 Image *t1, *t2; 359 ulong tchan; 360 361 for(i=-K2; i<=K2; i++){ 362 K[K2+i] = kaiser(i/10., K2/10., 4.); 363 } 364 365 /* normalize */ 366 v = 0.0; 367 for(i=0; i<NK; i++) 368 v += K[i]; 369 for(i=0; i<NK; i++) 370 K[i] /= v; 371 372 switch(from->chan){ 373 case GREY8: 374 case RGB24: 375 case RGBA32: 376 case ARGB32: 377 case XRGB32: 378 break; 379 380 case CMAP8: 381 case RGB15: 382 case RGB16: 383 tchan = RGB24; 384 goto Convert; 385 386 case GREY1: 387 case GREY2: 388 case GREY4: 389 tchan = GREY8; 390 Convert: 391 /* use library to convert to byte-per-chan form, then convert back */ 392 t1 = xallocimage(display, Rect(0, 0, Dx(from->r), Dy(from->r)), tchan, 0, DNofill); 393 if(t1 == nil) { 394 fprint(2, "out of memory for temp image 1 in resample: %r\n"); 395 wexits("memory"); 396 } 397 drawop(t1, t1->r, from, nil, ZP, S); 398 t2 = xallocimage(display, to->r, tchan, 0, DNofill); 399 if(t2 == nil) { 400 fprint(2, "out of memory temp image 2 in resample: %r\n"); 401 wexits("memory"); 402 } 403 resample(t1, t2); 404 drawop(to, to->r, t2, nil, ZP, S); 405 freeimage(t1); 406 freeimage(t2); 407 return to; 408 409 default: 410 sysfatal("can't handle channel type %s", chantostr(tmp, from->chan)); 411 } 412 413 xsize = Dx(to->r); 414 ysize = Dy(to->r); 415 oscan = malloc(Dy(from->r)*sizeof(uchar*)); 416 nscan = malloc(max(ysize, Dy(from->r))*sizeof(uchar*)); 417 if(oscan == nil || nscan == nil) 418 sysfatal("can't allocate: %r"); 419 420 /* unload original image into scan lines */ 421 bpl = bytesperline(from->r, from->depth); 422 for(i=0; i<Dy(from->r); i++){ 423 oscan[i] = malloc(bpl); 424 if(oscan[i] == nil) 425 sysfatal("can't allocate: %r"); 426 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); 427 if(j != bpl) 428 sysfatal("unloadimage"); 429 } 430 431 /* allocate scan lines for destination. we do y first, so need at least Dy(from->r) lines */ 432 bpl = bytesperline(Rect(0, 0, xsize, Dy(from->r)), from->depth); 433 for(i=0; i<max(ysize, Dy(from->r)); i++){ 434 nscan[i] = malloc(bpl); 435 if(nscan[i] == nil) 436 sysfatal("can't allocate: %r"); 437 } 438 439 /* resample in X */ 440 nchan = from->depth/8; 441 for(i=0; i<Dy(from->r); i++){ 442 for(j=0; j<nchan; j++){ 443 if(j==0 && from->chan==XRGB32) 444 continue; 445 resamplex(oscan[i], j, nchan, Dx(from->r), nscan[i], xsize); 446 } 447 free(oscan[i]); 448 oscan[i] = nscan[i]; 449 nscan[i] = malloc(bpl); 450 if(nscan[i] == nil) 451 sysfatal("can't allocate: %r"); 452 } 453 454 /* resample in Y */ 455 for(i=0; i<xsize; i++) 456 for(j=0; j<nchan; j++) 457 resampley(oscan, nchan*i+j, Dy(from->r), nscan, ysize); 458 459 /* pack data into destination */ 460 bpl = bytesperline(to->r, from->depth); 461 for(i=0; i<ysize; i++){ 462 j = loadimage(to, Rect(0, i, xsize, i+1), nscan[i], bpl); 463 if(j != bpl) 464 sysfatal("loadimage: %r"); 465 } 466 467 for(i=0; i<Dy(from->r); i++){ 468 free(oscan[i]); 469 free(nscan[i]); 470 } 471 free(oscan); 472 free(nscan); 473 474 return to; 475 } 476