src/imageeffects.cpp

   1 /*
   2   Copyright (c) 2006 Maurizio Monge <maurizio.monge@kdemail.net>
   3
   4   This program is free software; you can redistribute it and/or modify
   5   it under the terms of the GNU General Public License as published by
   6   the Free Software Foundation; either version 2 of the License, or
   7   (at your option) any later version.
   8
   9   Part of the code been contributed by Jani Huhtanen.
  10   Copyright (c) 2006 Jani Huhtanen.
  11 */
  12
  13
  14 #include <cmath>
  15 #include <QPainter>
  16 #include "imageeffects.h"
  17
  18 #ifdef HAVE_X86_MMX
  19 #include <inttypes.h>
  20 #include <mmintrin.h>
  21 #include <kcpuinfo.h>
  22 #endif //HAVE_X86_MMX
  23
  24 #if defined(__x86_64__) || defined(HAVE_X86_SSE)
  25 #include <inttypes.h>
  26 #include <xmmintrin.h>
  27 #include <kcpuinfo.h>
  28 #endif //defined(__x86_64__) || defined(HAVE_X86_SSE)
  29
  30
  31 #ifndef __x86_64__
  32
  33 template<int aprec, int zprec>
  34 static inline void blurinner(unsigned char *bptr, int &zR,
  35                              int &zG, int &zB, int &zA, int alpha);
  36
  37 template<int aprec,int zprec>
  38 static inline void blurrow(QImage & im, int line, int alpha);
  39
  40 template<int aprec, int zprec>
  41 static inline void blurcol(QImage & im, int col, int alpha);
  42
  43 /*
  44  *  expblur(QImage &img, int radius)
  45  *
  46  *  In-place blur of image 'img' with kernel
  47  *  of approximate radius 'radius'.
  48  *
  49  *  Blurs with two sided exponential impulse
  50  *  response.
  51  *
  52  *  aprec = precision of alpha parameter
  53  *  in fixed-point format 0.aprec
  54  *
  55  *  zprec = precision of state parameters
  56  *  zR,zG,zB and zA in fp format 8.zprec
  57  */
  58 template<int aprec,int zprec>
  59 static void expblur(QImage &img, int radius )
  60 {
  61     if (radius < 1)
  62         return;
  63
  64     /* Calculate the alpha such that 90% of
  65        the kernel is within the radius.
  66        (Kernel extends to infinity)
  67     */
  68     int alpha = (int)((1<<aprec)*(1.0f-expf(-2.3f/(radius+1.f))));
  69
  70     for(int row=0;row<img.height();row++) {
  71         blurrow<aprec,zprec>(img,row,alpha);
  72     }
  73
  74     for(int col=0;col<img.width();col++) {
  75         blurcol<aprec,zprec>(img,col,alpha);
  76     }
  77     return;
  78 }
  79
  80 template<int aprec, int zprec>
  81 static inline void blurinner(unsigned char *bptr,
  82                              int &zR, int &zG, int &zB, int &zA, int alpha)
  83 {
  84     int R,G,B,A;
  85     R = *bptr;
  86     G = *(bptr+1);
  87     B = *(bptr+2);
  88     A = *(bptr+3);
  89
  90     zR += (alpha * ((R<<zprec)-zR))>>aprec;
  91     zG += (alpha * ((G<<zprec)-zG))>>aprec;
  92     zB += (alpha * ((B<<zprec)-zB))>>aprec;
  93     zA += (alpha * ((A<<zprec)-zA))>>aprec;
  94
  95     *bptr =     zR>>zprec;
  96     *(bptr+1) = zG>>zprec;
  97     *(bptr+2) = zB>>zprec;
  98     *(bptr+3) = zA>>zprec;
  99 }
 100
 101 template<int aprec,int zprec>
 102 static inline void blurrow( QImage & im, int line, int alpha)
 103 {
 104     int zR,zG,zB,zA;
 105
 106     QRgb *ptr = (QRgb *)im.scanLine(line);
 107
 108     zR = *((unsigned char *)ptr    )<<zprec;
 109     zG = *((unsigned char *)ptr + 1)<<zprec;
 110     zB = *((unsigned char *)ptr + 2)<<zprec;
 111     zA = *((unsigned char *)ptr + 3)<<zprec;
 112
 113     for(int index=1; index<im.width(); index++) {
 114         blurinner<aprec,zprec>((unsigned char *)&ptr[index],
 115                                zR, zG, zB, zA, alpha);
 116     }
 117     for(int index=im.width()-2; index>=0; index--) {
 118         blurinner<aprec,zprec>((unsigned char *)&ptr[index],
 119                                zR, zG, zB, zA, alpha);
 120     }
 121
 122
 123 }
 124
 125 template<int aprec, int zprec>
 126 static inline void blurcol(QImage & im, int col, int alpha)
 127 {
 128     int zR,zG,zB,zA;
 129
 130     QRgb *ptr = (QRgb *)im.bits();
 131     ptr+=col;
 132
 133     zR = *((unsigned char *)ptr    )<<zprec;
 134     zG = *((unsigned char *)ptr + 1)<<zprec;
 135     zB = *((unsigned char *)ptr + 2)<<zprec;
 136     zA = *((unsigned char *)ptr + 3)<<zprec;
 137
 138     for(int index=im.width(); index<(im.height()-1)*im.width();
 139         index+=im.width()) {
 140         blurinner<aprec,zprec>((unsigned char *)&ptr[index],
 141                                zR, zG, zB, zA, alpha);
 142     }
 143
 144     for(int index=(im.height()-2)*im.width(); index>=0;
 145         index-=im.width()) {
 146         blurinner<aprec,zprec>((unsigned char *)&ptr[index],
 147                                zR, zG, zB, zA, alpha);
 148     }
 149
 150 }
 151
 152 #endif //__x86_64__
 153
 154
 155
 156 #if defined(HAVE_X86_SSE) || defined(__x86_64__)
 157
 158 union vec4i
 159 {
 160   uint16_t i[8];
 161   __m128i v;
 162 };
 163
 164 static inline void blur_sse_near(void* pixels, __m128i& state, __m128i alpha)
 165 {
 166   uint64_t z1 = 0ULL;
 167   uint64_t z2 = 0ULL;
 168   uint64_t z3 = 0ULL;
 169
 170   asm(
 171     "movq %[ppix], %[pixels]\n"
 172     "punpcklbw %[pixels], %[aux1]\n"           // unpack two pixels setting their bytes
 173                                                // as the most significant in the corr. word
 174     "psrlw $1, %[aux1]\n"                      // shift right by 1, i.e. shift the colour
 175                                                // bytes left by 7
 176     "psubw %[state], %[aux1]\n"                // - state
 177     "pmulhw %[alpha], %[aux1]\n"               // * alpha, and take the 16 most significant bits
 178     "psllw $1, %[aux1]\n"                      // shift left (we trade 1 bit for performance, here)
 179     "paddw %[aux1], %[state]\n"                // sum result to state
 180     "movdqa %[state], %[aux2]\n"                 // copy state to the aux2 register
 181     "psrlw $7, %[aux2]\n"                      // shift right by 7: this is the new pixel value
 182     "packuswb %[aux2], %[aux2]\n"              // pack pixels as 8 bits
 183     "movq %[aux2], %[ppix]\n"
 184   : [state] "+x"(state)
 185   , [ppix] "+m"(*(uint64_t*)pixels)
 186   , [aux1] "+x"(z1)
 187   , [aux2] "+x"(z2)
 188   , [pixels] "+x"(z3)
 189   : [alpha] "x"(alpha)
 190   );
 191 }
 192
 193 static inline void blur_sse_sep(void* pixel1, void* pixel2, __m128i& state, __m128i alpha)
 194 {
 195   uint64_t z1 = 0ULL;
 196   uint64_t z2 = 0ULL;
 197   uint64_t z3 = 0ULL;
 198   uint64_t z4 = 0ULL;
 199
 200   asm(
 201     "movd %[ppix1], %[pixels]\n"             // load the first pixel
 202     "movd %[ppix2], %[tmp]\n"                // load the second pixel in [tmp]
 203     "pslldq $4, %[tmp]\n"                      // shift left the second pixel
 204     "paddd %[tmp], %[pixels]\n"                // now both pixel are packed in [pixels]
 205
 206     "punpcklbw %[pixels], %[aux1]\n"           // unpack two pixels setting their bytes
 207                                                // as the most significant in the corr. word
 208     "psrlw $1, %[aux1]\n"                      // shift right by 1, i.e. shift the colour
 209                                                // bytes left by 7
 210     "psubw %[state], %[aux1]\n"                // - state
 211     "pmulhw %[alpha], %[aux1]\n"               // * alpha, and take the 16 most significant bits
 212     "psllw $1, %[aux1]\n"                      // shift left (we trade 1 bit for performance, here)
 213     "paddw %[aux1], %[state]\n"                // sum result to state
 214     "movdqa %[state], %[aux2]\n"                 // copy state to the aux2 register
 215     "psrlw $7, %[aux2]\n"                      // shift right by 7: this is the new pixel value
 216     "packuswb %[aux2], %[aux2]\n"              // pack pixels as 8 bits
 217
 218     "movd %[aux2], %[ppix1]\n"
 219     "psrldq $4, %[aux2]\n"
 220     "movd %[aux2], %[ppix2]\n"
 221   : [state] "+x"(state)
 222   , [ppix1] "+m"(*(uint32_t*)pixel1)
 223   , [ppix2] "+m"(*(uint32_t*)pixel2)
 224   , [aux1] "+x"(z1)
 225   , [aux2] "+x"(z2)
 226   , [tmp]  "+x"(z3)
 227   , [pixels] "+x"(z4)
 228   : [alpha] "x"(alpha)
 229   );
 230 }
 231
 232 static void expblur_sse( QImage &img, int radius )
 233 {
 234   if(radius<1)
 235     return;
 236
 237   /* Calculate the alpha such that 90% of
 238      the kernel is within the radius.
 239      (Kernel extends to infinity)
 240   */
 241   uint16_t alpha = (uint16_t)((1<<15)*(1.0f-expf(-2.3f/(radius+1.f))));
 242
 243   vec4i a;
 244   QRgb *ptr = (QRgb *)img.bits();
 245   int h = img.height();
 246   int w = img.width();
 247   int hw = (img.height()-1)*img.width();
 248   for(int i=0;i<8;i++)
 249     a.i[i] = alpha;
 250
 251   for(int row=0;row<h-1;row+=2)
 252   {
 253     vec4i z;
 254     uint8_t *cptr = (uint8_t*)(ptr+row*w);
 255     for(int i=0;i<4;i++)
 256       z.i[i] = cptr[i]<<7;
 257     for(int i=0;i<4;i++)
 258       z.i[4+i] = cptr[w*4+i]<<7;
 259
 260     for(int index=1; index<w; index++)
 261       blur_sse_sep(&cptr[index*4], &cptr[(index+w)*4], z.v, a.v);
 262
 263     for(int index=w-2; index>=0; index--)
 264       blur_sse_sep(&cptr[index*4], &cptr[(index+w)*4] , z.v, a.v);
 265   }
 266
 267   if(h & 1)
 268   {
 269     vec4i z;
 270     int dummy;
 271     uint8_t *cptr = (uint8_t*)(ptr+(h-1)*w);
 272     for(int i=0;i<4;i++)
 273       z.i[i] = cptr[i]<<7;
 274
 275     for(int index=1; index<w; index++)
 276       blur_sse_sep(&cptr[index*4], &dummy, z.v, a.v);
 277
 278     for(int index=w-2; index>=0; index--)
 279       blur_sse_sep(&cptr[index*4], &dummy, z.v, a.v);
 280   }
 281
 282   for(int col=0;col<w-1;col+=2)
 283   {
 284     vec4i z;
 285     uint8_t *cptr = (uint8_t*)(ptr+col);
 286
 287     for(int i=0;i<8;i++)
 288       z.i[i] = cptr[i]<<7;
 289
 290     for(int index=w; index<hw; index+=w)
 291       blur_sse_near(&cptr[index*4], z.v, a.v);
 292
 293     for(int index=hw-2*w; index>=0; index-=w)
 294       blur_sse_near(&cptr[index*4], z.v, a.v);
 295   }
 296
 297   if(w & 1)
 298   {
 299     vec4i z;
 300     int dummy;
 301     uint8_t *cptr = (uint8_t*)(ptr+w-1);
 302
 303     for(int i=0;i<4;i++)
 304       z.i[i] = cptr[i]<<7;
 305
 306     for(int index=w; index<hw; index+=w)
 307       blur_sse_sep(&cptr[index*4], &dummy, z.v, a.v);
 308
 309     for(int index=hw-w; index>=0; index-=w)
 310       blur_sse_sep(&cptr[index*4], &dummy, z.v, a.v);
 311   }
 312
 313   return;
 314 }
 315 #endif //defined(HAVE_X86_SSE) || defined(__x86_64__)
 316
 317
 318
 319 #ifdef HAVE_X86_MMX
 320
 321 union vec4s
 322 {
 323   uint16_t i[4];
 324   __m64 v;
 325 };
 326
 327 static inline void blur_mmx(void *px, __m64& v, __m64& alpha)
 328 {
 329   uint64_t z1 = 0ULL;
 330   uint64_t z2 = 0ULL;
 331   asm(
 332     "movd %[pixel], %[t1]\n"
 333     "punpcklbw %[t1], %[t2]\n"
 334     "psrlw $1, %[t2]\n"
 335     "psubw %[accum], %[t2]\n"
 336     "pmulhw %[alpha], %[t2]\n"
 337     "psllw $1, %[t2]\n"
 338     "paddw %[t2], %[accum]\n"
 339     "movq %[accum], %[t1]\n"
 340     "psrlw $7, %[t1]\n"
 341        // "pand %[mask], %[t1]\n"
 342     "packuswb %[t1], %[t1]\n"
 343     "movd %[t1], %[pixel]\n"
 344     :  [pixel] "+m"(*(uint32_t*)px)
 345      , [accum] "+y"(v)
 346      , [t1] "+y"(z1)
 347      , [t2] "+y"(z2)
 348     :  [alpha] "y"(alpha)
 349      // , [mask] "y"(0x00ff00ff00ff00ffULL)
 350   );
 351 }
 352
 353 static void expblur_mmx( QImage &img, int radius )
 354 {
 355   if(radius<1)
 356     return;
 357
 358   /* Calculate the alpha such that 90% of
 359      the kernel is within the radius.
 360      (Kernel extends to infinity)
 361   */
 362   uint16_t alpha = (uint16_t)((1<<15)*(1.0f-expf(-2.3f/(radius+1.f))));
 363
 364   vec4s a;
 365   QRgb *ptr = (QRgb *)img.bits();
 366   int h = img.height();
 367   int w = img.width();
 368   int hw = (img.height()-1)*img.width();
 369   for(int i=0;i<4;i++)
 370     a.i[i] = alpha;
 371
 372   for(int row=0;row<h;row++)
 373   {
 374     vec4s z;
 375     uint8_t *cptr = (uint8_t*)(ptr+row*w);
 376     for(int i=0;i<4;i++)
 377       z.i[i] = cptr[i]<<7;
 378
 379     for(int index=1; index<w; index++)
 380       blur_mmx(&cptr[index*4], z.v, a.v);
 381
 382     for(int index=w-2; index>=0; index--)
 383       blur_mmx(&cptr[index*4], z.v, a.v);
 384   }
 385
 386   for(int col=0;col<w;col++)
 387   {
 388     vec4s z;
 389     uint8_t *cptr = (uint8_t*)(ptr+col);
 390
 391     for(int i=0;i<4;i++)
 392       z.i[i] = cptr[i]<<7;
 393
 394     for(int index=w; index<hw; index+=w)
 395       blur_mmx(&cptr[index*4], z.v, a.v);
 396
 397     for(int index=hw-w; index>=0; index-=w)
 398       blur_mmx(&cptr[index*4], z.v, a.v);
 399   }
 400
 401   asm("emms");
 402   return;
 403 }
 404 #endif //HAVE_X86_MMX
 405
 406
 407
 408
 409 namespace ImageEffects {
 410
 411 void expBlur(QImage& img, int radius) {
 412 #ifdef __x86_64__
 413   return expblur_sse(img, radius);
 414 #else //__x86_64__
 415   #ifdef HAVE_X86_SSE
 416     if(KCPUInfo::haveExtension( KCPUInfo::IntelSSE ) )
 417       return expblur_sse(img, radius);
 418   #endif //HAVE_X86_SSE
 419   #ifdef HAVE_X86_MMX
 420     if(KCPUInfo::haveExtension( KCPUInfo::IntelMMX ) )
 421       return expblur_mmx(img, radius);
 422   #endif //HAVE_X86_MMX
 423     return expblur<15,7>(img, radius);
 424 #endif //__x86_64__
 425 }
 426
 427 QImage addShadow(const QImage& image, int r, QColor color,
 428                          int offx, int offy, int growx, int growy) {
 429   QPainter p;
 430   QImage retv(image.width()+growx, image.height()+growy, QImage::Format_ARGB32_Premultiplied);
 431   int dx = (growx-offx)/2, dy = (growy-offy)/2;
 432
 433   p.begin(&retv);
 434   p.setCompositionMode(QPainter::CompositionMode_Source);
 435   p.fillRect(0,0,retv.width(), retv.height(), QColor(0,0,0,0));
 436   p.fillRect(dx+offx, dy+offy, image.width(), image.height(), color);
 437   p.setCompositionMode(QPainter::CompositionMode_DestinationAtop );
 438   p.drawImage(dx+offx, dy+offy, image);
 439   p.end();
 440
 441   expBlur(retv, r);
 442
 443   p.begin(&retv);
 444   p.drawImage(dx, dy, image);
 445   p.end();
 446
 447   return retv;
 448 }
 449
 450 QImage growBorder(const QImage& image) {
 451   int w = image.width();
 452   int h = image.height();
 453   QPainter p;
 454   QImage retv(w+2, h+2, QImage::Format_ARGB32_Premultiplied);
 455
 456   p.begin(&retv);
 457   p.setCompositionMode(QPainter::CompositionMode_Source);
 458   p.drawImage(0, 0, image, 0, 0, 1, 1);
 459   p.drawImage(w+1, 0, image, w-1, 0, 1, 1);
 460   p.drawImage(0, h+1, image, 0, h-1, 1, 1);
 461   p.drawImage(w+1, h+1, image, w-1, h-1, 1, 1);
 462   p.drawImage(1, 0, image, 0, 0, w, 1);
 463   p.drawImage(1, h+1, image, 0, h-1, w, 1);
 464   p.drawImage(0, 1, image, 0, 0, 1, h);
 465   p.drawImage(w+1, 1, image, w-1, 0, 1, h);
 466   p.drawImage(1, 1, image);
 467   p.end();
 468
 469   return retv;
 470 }
 471
 472 struct Line {
 473   int y, x1, x2;
 474   Line(){}
 475   Line(int _y, int _x1, int _x2)
 476     : y(_y), x1(_x1), x2(_x2) {}
 477 };
 478
 479 void floodFill(QImage& image, QPoint point, QColor color,
 480                 bool invade_border, std::vector<QPoint>* border) {
 481
 482   int* ptr = (int*)image.bits();
 483   int h = image.height();
 484   int w = image.width();
 485   int newcol = color.rgba();
 486   int oldcol = ptr[point.x()+point.y()*w];
 487   std::vector<Line> lines;
 488
 489   {
 490   Line l(point.y(), point.x(), point.x()+1);
 491   int *scanline = ptr+point.y()*w;
 492   scanline[l.x1] = newcol;
 493   while(l.x1 > 0 && scanline[l.x1-1] == oldcol)
 494     scanline[--l.x1] = newcol;
 495   while(l.x2 < w && scanline[l.x2] == oldcol)
 496     scanline[l.x2++] = newcol;
 497   lines.push_back(l);
 498   }
 499
 500   while(!lines.empty()) {
 501     Line ll = lines[lines.size()-1];
 502     lines.pop_back();
 503
 504     if(ll.x1>0) {
 505       if(invade_border)
 506         ptr[ll.y*w + ll.x1 - 1] = newcol;
 507       if(border)
 508         border->push_back(QPoint(ll.x1-1, ll.y));
 509     }
 510     if(ll.x2<w) {
 511       if(invade_border)
 512         ptr[ll.y*w + ll.x2] = newcol;
 513       if(border)
 514         border->push_back(QPoint(ll.x2, ll.y));
 515     }
 516
 517     for(int d=-1; d<=1; d+=2)
 518     if( (d == -1) ? (ll.y > 0) : (ll.y < h-1) ) {
 519       int *scanline = ptr + (ll.y+d)*w;
 520
 521       for(int i=ll.x1;i<ll.x2;i++){
 522         if(scanline[i]==oldcol) {
 523           Line l(ll.y+d, i, i+1);
 524
 525           scanline[l.x1] = newcol;
 526           while(l.x1 > 0 && scanline[l.x1-1] == oldcol)
 527             scanline[--l.x1] = newcol;
 528           while(l.x2 < w && scanline[l.x2] == oldcol)
 529             scanline[l.x2++] = newcol;
 530           lines.push_back(l);
 531           i = l.x2;
 532         }
 533         if(i<ll.x2 && scanline[i]!=newcol) {
 534           if(invade_border)
 535             scanline[i]=newcol;
 536           if(border)
 537             border->push_back(QPoint(i, ll.y+d));
 538         }
 539       }
 540     }
 541   }
 542 }
 543
 544 void floodFillBlueThreshold(QImage& image, QPoint point, QColor color, unsigned int thresh,
 545                           bool invade_border, std::vector<QPoint>* border) {
 546
 547   unsigned int* ptr = (unsigned int*)image.bits();
 548   int h = image.height();
 549   int w = image.width();
 550   unsigned int newcol = color.rgba();
 551   std::vector<Line> lines;
 552
 553   #define TEST(x) ((((x) & 0xff) < thresh) && ((x) != newcol))
 554   {
 555   Line l(point.y(), point.x(), point.x()+1);
 556   unsigned int *scanline = ptr+point.y()*w;
 557   scanline[l.x1] = newcol;
 558   while(l.x1 > 0 && TEST(scanline[l.x1-1]))
 559     scanline[--l.x1] = newcol;
 560   while(l.x2 < w && TEST(scanline[l.x2]))
 561     scanline[l.x2++] = newcol;
 562   lines.push_back(l);
 563   }
 564
 565   while(!lines.empty()) {
 566     Line ll = lines[lines.size()-1];
 567     lines.pop_back();
 568
 569     if(ll.x1>0) {
 570       if(invade_border)
 571         ptr[ll.y*w + ll.x1 - 1] = newcol;
 572       if(border)
 573         border->push_back(QPoint(ll.x1-1, ll.y));
 574     }
 575     if(ll.x2<w) {
 576       if(invade_border)
 577         ptr[ll.y*w + ll.x2] = newcol;
 578       if(border)
 579         border->push_back(QPoint(ll.x2, ll.y));
 580     }
 581
 582     for(int d=-1; d<=1; d+=2)
 583     if( (d == -1) ? (ll.y > 0) : (ll.y < h-1) ) {
 584       unsigned int *scanline = ptr + (ll.y+d)*w;
 585
 586       for(int i=ll.x1;i<ll.x2;i++){
 587         if(TEST(scanline[i])) {
 588           Line l(ll.y+d, i, i+1);
 589
 590           scanline[l.x1] = newcol;
 591           while(l.x1 > 0 && TEST(scanline[l.x1-1]))
 592             scanline[--l.x1] = newcol;
 593           while(l.x2 < w && TEST(scanline[l.x2]))
 594             scanline[l.x2++] = newcol;
 595           lines.push_back(l);
 596           i = l.x2;
 597         }
 598         if(i<ll.x2 && scanline[i]!=newcol) {
 599           if(invade_border)
 600             scanline[i]=newcol;
 601           if(border)
 602             border->push_back(QPoint(i, ll.y+d));
 603         }
 604       }
 605     }
 606   }
 607 }
 608
 609 }