1/* 2 * Copyright 2008-2010 Stephan Aßmus <superstippi@gmx.de> 3 * Distributed under the terms of the MIT license. 4 */ 5//---------------------------------------------------------------------------- 6// Anti-Grain Geometry - Version 2.4 7// Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com) 8// 9// Permission to copy, use, modify, sell and distribute this software 10// is granted provided this copyright notice appears in all copies. 11// This software is provided "as is" without express or implied 12// warranty, and with no claim as to its suitability for any purpose. 13// 14//---------------------------------------------------------------------------- 15// Contact: mcseem@antigrain.com 16// mcseemagg@yahoo.com 17// http://www.antigrain.com 18//---------------------------------------------------------------------------- 19// 20// The Stack Blur Algorithm was invented by Mario Klingemann, 21// mario@quasimondo.com and described here: 22// http://incubator.quasimondo.com/processing/fast_blur_deluxe.php 23// (search phrase "Stackblur: Fast But Goodlooking"). 24// The major improvement is that there's no more division table 25// that was very expensive to create for large blur radii. Insted, 26// for 8-bit per channel and radius not exceeding 254 the division is 27// replaced by multiplication and shift. 28// 29//---------------------------------------------------------------------------- 30 31 32#include "StackBlurFilter.h" 33 34#include <stdio.h> 35 36#include <Bitmap.h> 37 38#include <agg_array.h> 39 40 41template<class T> struct stack_blur_tables 42{ 43 static uint16 const g_stack_blur8_mul[255]; 44 static uint8 const g_stack_blur8_shr[255]; 45}; 46 47 48template<class T> 49uint16 const stack_blur_tables<T>::g_stack_blur8_mul[255] = 50{ 51 512,512,456,512,328,456,335,512,405,328,271,456,388,335,292,512, 52 454,405,364,328,298,271,496,456,420,388,360,335,312,292,273,512, 53 482,454,428,405,383,364,345,328,312,298,284,271,259,496,475,456, 54 437,420,404,388,374,360,347,335,323,312,302,292,282,273,265,512, 55 497,482,468,454,441,428,417,405,394,383,373,364,354,345,337,328, 56 320,312,305,298,291,284,278,271,265,259,507,496,485,475,465,456, 57 446,437,428,420,412,404,396,388,381,374,367,360,354,347,341,335, 58 329,323,318,312,307,302,297,292,287,282,278,273,269,265,261,512, 59 505,497,489,482,475,468,461,454,447,441,435,428,422,417,411,405, 60 399,394,389,383,378,373,368,364,359,354,350,345,341,337,332,328, 61 324,320,316,312,309,305,301,298,294,291,287,284,281,278,274,271, 62 268,265,262,259,257,507,501,496,491,485,480,475,470,465,460,456, 63 451,446,442,437,433,428,424,420,416,412,408,404,400,396,392,388, 64 385,381,377,374,370,367,363,360,357,354,350,347,344,341,338,335, 65 332,329,326,323,320,318,315,312,310,307,304,302,299,297,294,292, 66 289,287,285,282,280,278,275,273,271,269,267,265,263,261,259 67}; 68 69 70template<class T> 71uint8 const stack_blur_tables<T>::g_stack_blur8_shr[255] = 72{ 73 9, 11, 12, 13, 13, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 17, 74 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 75 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 76 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 77 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 78 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 79 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 80 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 81 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 82 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 83 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 84 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 85 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 86 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 87 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 88 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24 89}; 90 91 92#if __GNUC__ < 4 93static inline float 94roundf(float v) 95{ 96 return floorf(v + 0.5); 97} 98#endif 99 100 101StackBlurFilter::StackBlurFilter() 102{ 103} 104 105 106StackBlurFilter::~StackBlurFilter() 107{ 108} 109 110 111void 112StackBlurFilter::Filter(BBitmap* bitmap, double radius) 113{ 114 if (radius < 1.0) 115 return; 116 117 int32 width = bitmap->Bounds().IntegerWidth() + 1; 118 int32 height = bitmap->Bounds().IntegerHeight() + 1; 119 uint32 bpr = bitmap->BytesPerRow(); 120 uint8* bits = (uint8*)bitmap->Bits(); 121 122 unsigned r = (unsigned)roundf(radius); 123 124 if (bitmap->ColorSpace() == B_RGBA32 125 || bitmap->ColorSpace() == B_RGB32) { 126 127 _Filter32(bits, width, height, bpr, r, r); 128 129 } else if (bitmap->ColorSpace() == B_GRAY8) { 130 131 _Filter8(bits, width, height, bpr, r, r); 132 133 } else 134 printf("StackBlurFilter::Filter() - unsupported color space\n"); 135} 136 137 138// #pragma mark - 139 140 141struct rgba { 142 uint8 r; 143 uint8 g; 144 uint8 b; 145 uint8 a; 146}; 147 148 149void 150StackBlurFilter::_Filter32(uint8* buffer, unsigned width, unsigned height, 151 int32 bpr, unsigned rx, unsigned ry) const 152{ 153 typedef rgba color_type; 154 155 unsigned x, y, xp, yp, i; 156 unsigned stack_ptr; 157 unsigned stack_start; 158 159 const uint8* src_pix_ptr; 160 uint8* dst_pix_ptr; 161 color_type* stack_pix_ptr; 162 163 unsigned sum_r; 164 unsigned sum_g; 165 unsigned sum_b; 166 unsigned sum_a; 167 unsigned sum_in_r; 168 unsigned sum_in_g; 169 unsigned sum_in_b; 170 unsigned sum_in_a; 171 unsigned sum_out_r; 172 unsigned sum_out_g; 173 unsigned sum_out_b; 174 unsigned sum_out_a; 175 176 unsigned w = width; 177 unsigned h = height; 178 unsigned wm = w - 1; 179 unsigned hm = h - 1; 180 181 unsigned div; 182 unsigned mul_sum; 183 unsigned shr_sum; 184 185 agg::pod_vector<color_type> stack; 186 187 if (rx > 0) { 188 if (rx > 254) 189 rx = 254; 190 div = rx * 2 + 1; 191 mul_sum = stack_blur_tables<int>::g_stack_blur8_mul[rx]; 192 shr_sum = stack_blur_tables<int>::g_stack_blur8_shr[rx]; 193 stack.allocate(div); 194 195 for (y = 0; y < h; y++) { 196 sum_r = 197 sum_g = 198 sum_b = 199 sum_a = 200 sum_in_r = 201 sum_in_g = 202 sum_in_b = 203 sum_in_a = 204 sum_out_r = 205 sum_out_g = 206 sum_out_b = 207 sum_out_a = 0; 208 209 src_pix_ptr = buffer + bpr * y; 210 for (i = 0; i <= rx; i++) { 211 stack_pix_ptr = &stack[i]; 212 stack_pix_ptr->r = src_pix_ptr[2]; 213 stack_pix_ptr->g = src_pix_ptr[1]; 214 stack_pix_ptr->b = src_pix_ptr[0]; 215 stack_pix_ptr->a = src_pix_ptr[3]; 216 sum_r += src_pix_ptr[2] * (i + 1); 217 sum_g += src_pix_ptr[1] * (i + 1); 218 sum_b += src_pix_ptr[0] * (i + 1); 219 sum_a += src_pix_ptr[3] * (i + 1); 220 sum_out_r += src_pix_ptr[2]; 221 sum_out_g += src_pix_ptr[1]; 222 sum_out_b += src_pix_ptr[0]; 223 sum_out_a += src_pix_ptr[3]; 224 } 225 for (i = 1; i <= rx; i++) { 226 if (i <= wm) 227 src_pix_ptr += 4; 228 stack_pix_ptr = &stack[i + rx]; 229 stack_pix_ptr->r = src_pix_ptr[2]; 230 stack_pix_ptr->g = src_pix_ptr[1]; 231 stack_pix_ptr->b = src_pix_ptr[0]; 232 stack_pix_ptr->a = src_pix_ptr[3]; 233 sum_r += src_pix_ptr[2] * (rx + 1 - i); 234 sum_g += src_pix_ptr[1] * (rx + 1 - i); 235 sum_b += src_pix_ptr[0] * (rx + 1 - i); 236 sum_a += src_pix_ptr[3] * (rx + 1 - i); 237 sum_in_r += src_pix_ptr[2]; 238 sum_in_g += src_pix_ptr[1]; 239 sum_in_b += src_pix_ptr[0]; 240 sum_in_a += src_pix_ptr[3]; 241 } 242 243 stack_ptr = rx; 244 xp = rx; 245 if (xp > wm) 246 xp = wm; 247 src_pix_ptr = buffer + xp * 4 + y * bpr; 248 dst_pix_ptr = buffer + y * bpr; 249 for (x = 0; x < w; x++) { 250 dst_pix_ptr[2] = (sum_r * mul_sum) >> shr_sum; 251 dst_pix_ptr[1] = (sum_g * mul_sum) >> shr_sum; 252 dst_pix_ptr[0] = (sum_b * mul_sum) >> shr_sum; 253 dst_pix_ptr[3] = (sum_a * mul_sum) >> shr_sum; 254 dst_pix_ptr += 4; 255 256 sum_r -= sum_out_r; 257 sum_g -= sum_out_g; 258 sum_b -= sum_out_b; 259 sum_a -= sum_out_a; 260 261 stack_start = stack_ptr + div - rx; 262 if(stack_start >= div) stack_start -= div; 263 stack_pix_ptr = &stack[stack_start]; 264 265 sum_out_r -= stack_pix_ptr->r; 266 sum_out_g -= stack_pix_ptr->g; 267 sum_out_b -= stack_pix_ptr->b; 268 sum_out_a -= stack_pix_ptr->a; 269 270 if (xp < wm) { 271 src_pix_ptr += 4; 272 ++xp; 273 } 274 275 stack_pix_ptr->r = src_pix_ptr[2]; 276 stack_pix_ptr->g = src_pix_ptr[1]; 277 stack_pix_ptr->b = src_pix_ptr[0]; 278 stack_pix_ptr->a = src_pix_ptr[3]; 279 280 sum_in_r += src_pix_ptr[2]; 281 sum_in_g += src_pix_ptr[1]; 282 sum_in_b += src_pix_ptr[0]; 283 sum_in_a += src_pix_ptr[3]; 284 sum_r += sum_in_r; 285 sum_g += sum_in_g; 286 sum_b += sum_in_b; 287 sum_a += sum_in_a; 288 289 ++stack_ptr; 290 if (stack_ptr >= div) 291 stack_ptr = 0; 292 stack_pix_ptr = &stack[stack_ptr]; 293 294 sum_out_r += stack_pix_ptr->r; 295 sum_out_g += stack_pix_ptr->g; 296 sum_out_b += stack_pix_ptr->b; 297 sum_out_a += stack_pix_ptr->a; 298 sum_in_r -= stack_pix_ptr->r; 299 sum_in_g -= stack_pix_ptr->g; 300 sum_in_b -= stack_pix_ptr->b; 301 sum_in_a -= stack_pix_ptr->a; 302 } 303 } 304 } 305 306 if (ry > 0) { 307 if (ry > 254) 308 ry = 254; 309 div = ry * 2 + 1; 310 mul_sum = stack_blur_tables<int>::g_stack_blur8_mul[ry]; 311 shr_sum = stack_blur_tables<int>::g_stack_blur8_shr[ry]; 312 stack.allocate(div); 313 314 int stride = bpr; 315 for(x = 0; x < w; x++) { 316 sum_r = 317 sum_g = 318 sum_b = 319 sum_a = 320 sum_in_r = 321 sum_in_g = 322 sum_in_b = 323 sum_in_a = 324 sum_out_r = 325 sum_out_g = 326 sum_out_b = 327 sum_out_a = 0; 328 329 src_pix_ptr = buffer + x * 4; 330 for (i = 0; i <= ry; i++) { 331 stack_pix_ptr = &stack[i]; 332 stack_pix_ptr->r = src_pix_ptr[2]; 333 stack_pix_ptr->g = src_pix_ptr[1]; 334 stack_pix_ptr->b = src_pix_ptr[0]; 335 stack_pix_ptr->a = src_pix_ptr[3]; 336 sum_r += src_pix_ptr[2] * (i + 1); 337 sum_g += src_pix_ptr[1] * (i + 1); 338 sum_b += src_pix_ptr[0] * (i + 1); 339 sum_a += src_pix_ptr[3] * (i + 1); 340 sum_out_r += src_pix_ptr[2]; 341 sum_out_g += src_pix_ptr[1]; 342 sum_out_b += src_pix_ptr[0]; 343 sum_out_a += src_pix_ptr[3]; 344 } 345 for (i = 1; i <= ry; i++) { 346 if (i <= hm) 347 src_pix_ptr += stride; 348 stack_pix_ptr = &stack[i + ry]; 349 stack_pix_ptr->r = src_pix_ptr[2]; 350 stack_pix_ptr->g = src_pix_ptr[1]; 351 stack_pix_ptr->b = src_pix_ptr[0]; 352 stack_pix_ptr->a = src_pix_ptr[3]; 353 sum_r += src_pix_ptr[2] * (ry + 1 - i); 354 sum_g += src_pix_ptr[1] * (ry + 1 - i); 355 sum_b += src_pix_ptr[0] * (ry + 1 - i); 356 sum_a += src_pix_ptr[3] * (ry + 1 - i); 357 sum_in_r += src_pix_ptr[2]; 358 sum_in_g += src_pix_ptr[1]; 359 sum_in_b += src_pix_ptr[0]; 360 sum_in_a += src_pix_ptr[3]; 361 } 362 363 stack_ptr = ry; 364 yp = ry; 365 if (yp > hm) 366 yp = hm; 367 src_pix_ptr = buffer + x * 4 + yp * bpr; 368 dst_pix_ptr = buffer + x * 4; 369 for (y = 0; y < h; y++) { 370 dst_pix_ptr[2] = (sum_r * mul_sum) >> shr_sum; 371 dst_pix_ptr[1] = (sum_g * mul_sum) >> shr_sum; 372 dst_pix_ptr[0] = (sum_b * mul_sum) >> shr_sum; 373 dst_pix_ptr[3] = (sum_a * mul_sum) >> shr_sum; 374 dst_pix_ptr += stride; 375 376 sum_r -= sum_out_r; 377 sum_g -= sum_out_g; 378 sum_b -= sum_out_b; 379 sum_a -= sum_out_a; 380 381 stack_start = stack_ptr + div - ry; 382 if (stack_start >= div) 383 stack_start -= div; 384 385 stack_pix_ptr = &stack[stack_start]; 386 sum_out_r -= stack_pix_ptr->r; 387 sum_out_g -= stack_pix_ptr->g; 388 sum_out_b -= stack_pix_ptr->b; 389 sum_out_a -= stack_pix_ptr->a; 390 391 if (yp < hm) { 392 src_pix_ptr += stride; 393 ++yp; 394 } 395 396 stack_pix_ptr->r = src_pix_ptr[2]; 397 stack_pix_ptr->g = src_pix_ptr[1]; 398 stack_pix_ptr->b = src_pix_ptr[0]; 399 stack_pix_ptr->a = src_pix_ptr[3]; 400 401 sum_in_r += src_pix_ptr[2]; 402 sum_in_g += src_pix_ptr[1]; 403 sum_in_b += src_pix_ptr[0]; 404 sum_in_a += src_pix_ptr[3]; 405 sum_r += sum_in_r; 406 sum_g += sum_in_g; 407 sum_b += sum_in_b; 408 sum_a += sum_in_a; 409 410 ++stack_ptr; 411 if (stack_ptr >= div) 412 stack_ptr = 0; 413 stack_pix_ptr = &stack[stack_ptr]; 414 415 sum_out_r += stack_pix_ptr->r; 416 sum_out_g += stack_pix_ptr->g; 417 sum_out_b += stack_pix_ptr->b; 418 sum_out_a += stack_pix_ptr->a; 419 sum_in_r -= stack_pix_ptr->r; 420 sum_in_g -= stack_pix_ptr->g; 421 sum_in_b -= stack_pix_ptr->b; 422 sum_in_a -= stack_pix_ptr->a; 423 } 424 } 425 } 426} 427 428 429void 430StackBlurFilter::_Filter8(uint8* buffer, unsigned width, unsigned height, 431 int32 bpr, unsigned rx, unsigned ry) const 432{ 433 unsigned x, y, xp, yp, i; 434 unsigned stack_ptr; 435 unsigned stack_start; 436 437 const uint8* src_pix_ptr; 438 uint8* dst_pix_ptr; 439 unsigned pix; 440 unsigned stack_pix; 441 unsigned sum; 442 unsigned sum_in; 443 unsigned sum_out; 444 445 unsigned w = width; 446 unsigned h = height; 447 unsigned wm = w - 1; 448 unsigned hm = h - 1; 449 450 unsigned div; 451 unsigned mul_sum; 452 unsigned shr_sum; 453 454 agg::pod_vector<uint8> stack; 455 456 if(rx > 0) 457 { 458 if(rx > 254) rx = 254; 459 div = rx * 2 + 1; 460 mul_sum = stack_blur_tables<int>::g_stack_blur8_mul[rx]; 461 shr_sum = stack_blur_tables<int>::g_stack_blur8_shr[rx]; 462 stack.allocate(div); 463 464 for(y = 0; y < h; y++) 465 { 466 sum = sum_in = sum_out = 0; 467 468 src_pix_ptr = buffer + y * bpr; 469 pix = *src_pix_ptr; 470 for(i = 0; i <= rx; i++) 471 { 472 stack[i] = pix; 473 sum += pix * (i + 1); 474 sum_out += pix; 475 } 476 for(i = 1; i <= rx; i++) 477 { 478 if(i <= wm) src_pix_ptr += 1; 479 pix = *src_pix_ptr; 480 stack[i + rx] = pix; 481 sum += pix * (rx + 1 - i); 482 sum_in += pix; 483 } 484 485 stack_ptr = rx; 486 xp = rx; 487 if(xp > wm) xp = wm; 488 src_pix_ptr = buffer + xp + y * bpr; 489 dst_pix_ptr = buffer + y * bpr; 490 for(x = 0; x < w; x++) 491 { 492 *dst_pix_ptr = (sum * mul_sum) >> shr_sum; 493 dst_pix_ptr += 1; 494 495 sum -= sum_out; 496 497 stack_start = stack_ptr + div - rx; 498 if(stack_start >= div) stack_start -= div; 499 sum_out -= stack[stack_start]; 500 501 if(xp < wm) 502 { 503 src_pix_ptr += 1; 504 pix = *src_pix_ptr; 505 ++xp; 506 } 507 508 stack[stack_start] = pix; 509 510 sum_in += pix; 511 sum += sum_in; 512 513 ++stack_ptr; 514 if(stack_ptr >= div) stack_ptr = 0; 515 stack_pix = stack[stack_ptr]; 516 517 sum_out += stack_pix; 518 sum_in -= stack_pix; 519 } 520 } 521 } 522 523 if(ry > 0) 524 { 525 if(ry > 254) ry = 254; 526 div = ry * 2 + 1; 527 mul_sum = stack_blur_tables<int>::g_stack_blur8_mul[ry]; 528 shr_sum = stack_blur_tables<int>::g_stack_blur8_shr[ry]; 529 stack.allocate(div); 530 531 int stride = bpr; 532 for(x = 0; x < w; x++) 533 { 534 sum = sum_in = sum_out = 0; 535 536 src_pix_ptr = buffer + x; 537 pix = *src_pix_ptr; 538 for(i = 0; i <= ry; i++) 539 { 540 stack[i] = pix; 541 sum += pix * (i + 1); 542 sum_out += pix; 543 } 544 for(i = 1; i <= ry; i++) 545 { 546 if(i <= hm) src_pix_ptr += stride; 547 pix = *src_pix_ptr; 548 stack[i + ry] = pix; 549 sum += pix * (ry + 1 - i); 550 sum_in += pix; 551 } 552 553 stack_ptr = ry; 554 yp = ry; 555 if(yp > hm) yp = hm; 556 src_pix_ptr = buffer + x + yp * bpr; 557 dst_pix_ptr = buffer + x; 558 for(y = 0; y < h; y++) 559 { 560 *dst_pix_ptr = (sum * mul_sum) >> shr_sum; 561 dst_pix_ptr += stride; 562 563 sum -= sum_out; 564 565 stack_start = stack_ptr + div - ry; 566 if(stack_start >= div) stack_start -= div; 567 sum_out -= stack[stack_start]; 568 569 if(yp < hm) 570 { 571 src_pix_ptr += stride; 572 pix = *src_pix_ptr; 573 ++yp; 574 } 575 576 stack[stack_start] = pix; 577 578 sum_in += pix; 579 sum += sum_in; 580 581 ++stack_ptr; 582 if(stack_ptr >= div) stack_ptr = 0; 583 stack_pix = stack[stack_ptr]; 584 585 sum_out += stack_pix; 586 sum_in -= stack_pix; 587 } 588 } 589 } 590} 591 592