Source/WebKit/android/jni/PictureSet.cpp

   1 /*
   2  * Copyright 2008, The Android Open Source Project
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *  * Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  *  * Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #define LOG_NDEBUG 0
  27 #define LOG_TAG "pictureset"
  28
  29 //#include <config.h>
  30 #include "CachedPrefix.h"
  31 #include "android_graphics.h"
  32 #include "PictureSet.h"
  33 #include "SkBounder.h"
  34 #include "SkCanvas.h"
  35 #include "SkPicture.h"
  36 #include "SkRect.h"
  37 #include "SkRegion.h"
  38 #include "SkStream.h"
  39 #include "TimeCounter.h"
  40
  41 #define MAX_DRAW_TIME 100
  42 #define MIN_SPLITTABLE 400
  43 #define MAX_ADDITIONAL_AREA 0.65
  44 #define MAX_ADDITIONAL_PICTURES 32
  45
  46 #define BUCKET_SIZE 512
  47
  48 #include <wtf/CurrentTime.h>
  49
  50 #include <cutils/log.h>
  51 #include <wtf/text/CString.h>
  52
  53 #undef XLOGC
  54 #define XLOGC(...) android_printLog(ANDROID_LOG_DEBUG, "PictureSet", __VA_ARGS__)
  55
  56 #ifdef DEBUG
  57
  58 #undef XLOG
  59 #define XLOG(...) android_printLog(ANDROID_LOG_DEBUG, "PictureSet", __VA_ARGS__)
  60
  61 #else
  62
  63 #undef XLOG
  64 #define XLOG(...)
  65
  66 #endif // DEBUG
  67
  68 #if PICTURE_SET_DEBUG
  69 class MeasureStream : public SkWStream {
  70 public:
  71     MeasureStream() : mTotal(0) {}
  72     virtual bool write(const void* , size_t size) {
  73         mTotal += size;
  74         return true;
  75     }
  76     size_t mTotal;
  77 };
  78 #endif
  79
  80 namespace android {
  81
  82 PictureSet::PictureSet()
  83 {
  84     mWidth = mHeight = 0;
  85     mBaseArea = mAdditionalArea = 0;
  86 }
  87
  88 PictureSet::PictureSet(SkPicture* picture)
  89 {
  90     mBaseArea = mAdditionalArea = 0;
  91     if (!picture) {
  92         mWidth = mHeight = 0;
  93         return;
  94     }
  95     mWidth = picture->width();
  96     mHeight = picture->height();
  97     mBaseArea = mWidth * mHeight;
  98 #ifdef FAST_PICTURESET
  99 #else
 100     Pictures pictureAndBounds;
 101     pictureAndBounds.mPicture = picture;
 102     SkSafeRef(pictureAndBounds.mPicture);
 103     pictureAndBounds.mEmpty = false;
 104     pictureAndBounds.mArea.setRect(0, 0, mWidth, mHeight);
 105     pictureAndBounds.mSplit = false;
 106     pictureAndBounds.mBase = true;
 107     pictureAndBounds.mElapsed = 0;
 108     pictureAndBounds.mWroteElapsed = false;
 109     mPictures.append(pictureAndBounds);
 110 #endif // FAST_PICTURESET
 111 }
 112
 113 PictureSet::~PictureSet()
 114 {
 115     clear();
 116 }
 117
 118 #ifdef FAST_PICTURESET
 119 #else
 120 void PictureSet::add(const Pictures* temp)
 121 {
 122     Pictures pictureAndBounds = *temp;
 123     SkSafeRef(pictureAndBounds.mPicture);
 124     pictureAndBounds.mWroteElapsed = false;
 125     mPictures.append(pictureAndBounds);
 126 }
 127 #endif // FAST_PICTURESET
 128
 129 void PictureSet::add(const SkRegion& area, SkPicture* picture,
 130                      uint32_t elapsed, bool split)
 131 {
 132     if (area.isRect()) {
 133 #ifdef FAST_PICTURESET
 134         splitAdd(area.getBounds());
 135 #else
 136         add(area, picture, elapsed, split, false);
 137 #endif // FAST_PICTURESET
 138     } else {
 139         SkRegion::Iterator cliperator(area);
 140         while (!cliperator.done()) {
 141             SkIRect ir = cliperator.rect();
 142 #ifdef FAST_PICTURESET
 143             splitAdd(ir);
 144 #else
 145             SkRegion newArea;
 146             newArea.setRect(ir);
 147             add(newArea, picture, elapsed, split, false);
 148 #endif // FAST_PICTURESET
 149             cliperator.next();
 150         }
 151     }
 152 }
 153
 154 #ifdef FAST_PICTURESET
 155
 156 Bucket* PictureSet::getBucket(int x, int y)
 157 {
 158     BucketPosition position(x+1, y+1);
 159     if (!mBuckets.contains(position)) {
 160         Bucket* bucket = new Bucket();
 161         mBuckets.add(position, bucket);
 162     }
 163     return mBuckets.get(position);
 164 }
 165
 166 void PictureSet::displayBucket(Bucket* bucket)
 167 {
 168     BucketPicture* first = bucket->begin();
 169     BucketPicture* last = bucket->end();
 170     for (BucketPicture* current = first; current != last; current++) {
 171         XLOGC("- in %x, bucketPicture %d,%d,%d,%d - %dx%d, picture: %x, base: %x",
 172               bucket,
 173               current->mArea.fLeft,
 174               current->mArea.fTop,
 175               current->mArea.fRight,
 176               current->mArea.fBottom,
 177               current->mArea.width(),
 178               current->mArea.height(),
 179               current->mPicture,
 180               current->mBase);
 181     }
 182 }
 183
 184 void PictureSet::displayBuckets()
 185 {
 186     XLOGC("\n\n****** DISPLAY BUCKETS ON PictureSet %x ******", this);
 187     for (BucketMap::iterator iter = mBuckets.begin(); iter != mBuckets.end(); ++iter) {
 188         XLOGC("\n*** Bucket %x for %d, %d", iter->second, iter->first.first, iter->first.second);
 189         displayBucket(iter->second);
 190     }
 191     XLOGC("\n****** END OF DISPLAY BUCKETS ******\n\n");
 192 }
 193
 194 // When we receive an inval in a Bucket, we try to see if we intersect with
 195 // existing invals/pictures in the Bucket.
 196 void PictureSet::addToBucket(Bucket* bucket, int dx, int dy, SkIRect& rect)
 197 {
 198     bool resetBase = false;
 199
 200     SkIRect totalArea = rect;
 201     BucketPicture* first = bucket->begin();
 202     BucketPicture* last = bucket->end();
 203
 204     // If the inval covers a large area of the base inval, let's repaint the
 205     // entire bucket.
 206     if (rect.width() * rect.height() > MAX_ADDITIONAL_AREA * BUCKET_SIZE * BUCKET_SIZE)
 207         resetBase = true;
 208
 209     // let's gather all the BucketPicture intersecting with the new invalidated
 210     // area, collect their area and remove their picture
 211     for (BucketPicture* current = first; current != last; current++) {
 212         bool remove = resetBase;
 213         bool intersect = false;
 214
 215         if (!remove)
 216             intersect = SkIRect::Intersects(current->mArea, rect);
 217         // If the current picture is not a base, and we intersect, remove it
 218         if (!remove && !current->mBase && intersect)
 219             remove = true;
 220         // If the current picture is a base, check if the new inval completely
 221         // contains the base, and if so remove it.
 222         if (!remove && current->mBase && rect.contains(current->mArea))
 223             remove = true;
 224         // If the current picture is a base and it intersects,
 225         // also check that it fully covers the bucket -- otherwise,
 226         // let's aggregate it with the new inval.
 227         if (!remove && current->mBase && intersect
 228             && (current->mArea.width() < BUCKET_SIZE || current->mArea.height() < BUCKET_SIZE)) {
 229             remove = true;
 230         }
 231
 232         if (remove) {
 233             totalArea.join(current->mArea);
 234             current->mBase = false;
 235             current->mArea.setEmpty();
 236             SkSafeUnref(current->mPicture);
 237             current->mPicture = 0;
 238         }
 239     }
 240
 241     // Now, let's add the new BucketPicture to the list, with the correct
 242     // area that needs to be repainted
 243     SkRegion region;
 244     SkIRect area = totalArea;
 245     area.offset(dx, dy);
 246     BucketPicture picture = { 0, totalArea, area, false };
 247
 248     bucket->append(picture);
 249
 250     first = bucket->begin();
 251     last = bucket->end();
 252
 253     // let's do a pass to collapse out empty areas
 254     BucketPicture* writer = first;
 255     for (BucketPicture* current = first; current != last; current++) {
 256         if (current && current->mArea.isEmpty())
 257             continue;
 258         *writer++ = *current;
 259     }
 260
 261     bucket->shrink(writer - first);
 262
 263     // let's recompute the bases
 264     first = bucket->begin();
 265     last = bucket->end();
 266     SkRegion drawn;
 267     drawn.setEmpty();
 268     for (BucketPicture* current = first; current != last; current++) {
 269         if (drawn.contains(current->mArea) == false) {
 270             current->mBase = true;
 271         }
 272         drawn.op(current->mArea, SkRegion::kUnion_Op);
 273     }
 274 }
 275
 276 void PictureSet::gatherBucketsForArea(WTF::Vector<Bucket*>& list, const SkIRect& rect)
 277 {
 278     int maxSize = BUCKET_SIZE;
 279
 280     int x = rect.fLeft;
 281     int y = rect.fTop;
 282     int firstTileX = rect.fLeft / maxSize;
 283     int firstTileY = rect.fTop / maxSize;
 284     int lastTileX = rect.fRight / maxSize;
 285     int lastTileY = rect.fBottom / maxSize;
 286
 287     for (int i = firstTileX; i <= lastTileX; i++) {
 288         for (int j = firstTileY; j <= lastTileY; j++) {
 289             Bucket* bucket = getBucket(i, j);
 290             XLOG("gather bucket %x for %d, %d", bucket, i+1, j+1);
 291             list.append(bucket);
 292         }
 293     }
 294 }
 295
 296 // When we receive a new inval rect, we first find the Buckets that intersect
 297 // with it; then we split the original inval into a serie of invals (one for
 298 // each Bucket we intersect with). We then send that inval to the Bucket.
 299 void PictureSet::splitAdd(const SkIRect& rect)
 300 {
 301     XLOG("\n--- splitAdd for rect %d, %d, %d, %d (%d x %d)",
 302           rect.fLeft, rect.fTop, rect.fRight, rect.fBottom,
 303           rect.width(), rect.height());
 304
 305     int maxSize = BUCKET_SIZE;
 306
 307     // TODO: reuse gatherBucketsForArea() (change Bucket to be a class)
 308     int x = rect.fLeft;
 309     int y = rect.fTop;
 310     int firstTileX = rect.fLeft / maxSize;
 311     int firstTileY = rect.fTop / maxSize;
 312     int lastTileX = rect.fRight / maxSize;
 313     int lastTileY = rect.fBottom / maxSize;
 314
 315     XLOG("--- firstTile(%d, %d) lastTile(%d, %d)",
 316           firstTileX, firstTileY,
 317           lastTileX, lastTileY);
 318
 319     for (int i = firstTileX; i <= lastTileX; i++) {
 320         for (int j = firstTileY; j <= lastTileY; j++) {
 321             Bucket* bucket = getBucket(i, j);
 322             SkIRect newRect;
 323             int deltaX = i * maxSize;
 324             int deltaY = j * maxSize;
 325             int left, top, right, bottom;
 326             if (i == firstTileX)
 327                 left = rect.fLeft;
 328             else
 329                 left = 0;
 330             if (j == firstTileY)
 331                 top = rect.fTop;
 332             else
 333                 top = 0;
 334             if (i == lastTileX)
 335                 right = rect.fRight % maxSize;
 336             else
 337                 right = maxSize;
 338             if (j == lastTileY)
 339                 bottom = rect.fBottom % maxSize;
 340             else
 341                 bottom = maxSize;
 342
 343             newRect.set(left, top, right, bottom);
 344             addToBucket(bucket, deltaX, deltaY, newRect);
 345             mUpdatedBuckets.append(bucket);
 346         }
 347     }
 348
 349     XLOG("--- splitAdd DONE\n");
 350 }
 351
 352 #endif // FAST_PICTURESET
 353
 354 // This function is used to maintain the list of Pictures.
 355 // Pictures contain an SkPicture covering a specific area; some
 356 // Pictures are "base" Pictures -- i.e. there is no Pictures
 357 // underneath them.
 358 // The idea here is to keep a balance between the number of Pictures
 359 // we have (more Pictures slow us down) and the area of Pictures that
 360 // need to be repainted (obviously, smaller areas are better).
 361 // To do so, we try to not update/repaint the base pictures -- by
 362 // construction, they usually cover a large area (the entire page).
 363 // We only reset a base picture if the new invalidated area entirely
 364 // contains it.
 365 // Most of the time we thus work on smaller pictures on top of the
 366 // base ones; We compute the total area of all pictures intersecting
 367 // with the passed invalidated area (as they would need to be invalidated),
 368 // and use that as the basis for the correct area we want to invalidate
 369 // (we then can simply delete the pictures we intersect with).
 370 // In addition, we do a couple of things to limit the total number of pictures
 371 // we keep in the list:
 372 // - if the total area of additional textures reach 65% of the base pictures,
 373 //   we delete the additional pictures and mark the base pictures as
 374 //   needing a full repaint
 375 // - we limit the number of pictures to 32 -- above that, we do the same
 376 //   things (deleting additional pictures + full repaint of base pictures)
 377 #ifdef FAST_PICTURESET
 378 #else
 379 void PictureSet::add(const SkRegion& area, SkPicture* picture,
 380     uint32_t elapsed, bool split, bool empty)
 381 {
 382     bool checkForNewBases = false;
 383
 384     Pictures* first = mPictures.begin();
 385     Pictures* last = mPictures.end();
 386 #ifdef DEBUG
 387     XLOG("--- before adding the new inval ---");
 388     for (Pictures* working = mPictures.begin(); working != mPictures.end(); working++) {
 389         SkIRect currentArea = working->mArea.getBounds();
 390         XLOG("picture %d (%d, %d, %d, %d - %d x %d) (isRect? %c) base: %c",
 391              working - first,
 392              currentArea.fLeft, currentArea.fTop, currentArea.fRight, currentArea.fBottom,
 393              currentArea.width(), currentArea.height(),
 394              working->mArea.isRect() ? 'Y' : 'N',
 395              working->mBase ? 'Y' : 'N');
 396     }
 397     XLOG("----------------------------------");
 398 #endif
 399
 400     // let's gather all the Pictures intersecting with the new invalidated
 401     // area, collect their area and remove their picture
 402     SkIRect totalArea = area.getBounds();
 403     for (Pictures* working = first; working != last; working++) {
 404         SkIRect inval = area.getBounds();
 405         bool remove = false;
 406         if (!working->mBase && working->mArea.intersects(inval))
 407             remove = true;
 408         if (working->mBase) {
 409             SkIRect baseArea = working->mArea.getBounds();
 410             if (area.contains(baseArea)) {
 411                 remove = true;
 412                 checkForNewBases = true;
 413             }
 414         }
 415
 416         if (remove) {
 417             SkIRect currentArea = working->mArea.getBounds();
 418             if (working->mBase)
 419                 mBaseArea -= currentArea.width() * currentArea.height();
 420             else
 421                 mAdditionalArea -= currentArea.width() * currentArea.height();
 422
 423             totalArea.join(currentArea);
 424             XLOG("picture %d (%d, %d, %d, %d - %d x %d) (isRect? %c) intersects with the new inval area (%d, %d, %d, %d - %d x %d) (isRect? %c, we remove it",
 425                  working - first,
 426                  currentArea.fLeft, currentArea.fTop, currentArea.fRight, currentArea.fBottom,
 427                  currentArea.width(), currentArea.height(),
 428                  working->mArea.isRect() ? 'Y' : 'N',
 429                  inval.fLeft, inval.fTop, inval.fRight, inval.fBottom,
 430                  inval.width(), inval.height(),
 431                  area.isRect() ? 'Y' : 'N');
 432             working->mArea.setEmpty();
 433             SkSafeUnref(working->mPicture);
 434             working->mPicture = 0;
 435         }
 436     }
 437
 438     // Now we can add the new Picture to the list, with the correct area
 439     // that need to be repainted
 440     SkRegion collect;
 441     collect.setRect(totalArea);
 442     Pictures pictureAndBounds = {collect, 0, collect.getBounds(),
 443         elapsed, split, false, false, empty};
 444
 445     if (mPictures.size() == 0)
 446         checkForNewBases = true;
 447
 448     mPictures.append(pictureAndBounds);
 449     mAdditionalArea += totalArea.width() * totalArea.height();
 450     last = mPictures.end();
 451     first = mPictures.begin();
 452
 453     // Then, let's see if we have to clear up the pictures in order to keep
 454     // the total number of pictures under our limit
 455     bool clearUp = false;
 456     if (last - first > MAX_ADDITIONAL_PICTURES) {
 457         XLOG("--- too many pictures, only keeping the bases : %d", last - first);
 458         clearUp = true;
 459     }
 460
 461     if (!clearUp) {
 462         if (mBaseArea > 0 && mBaseArea * MAX_ADDITIONAL_AREA <= mAdditionalArea) {
 463             XLOG("+++ the sum of the additional area is > %.2f\% of the base Area (%.2f (%.2f) <= %.2f",
 464                  MAX_ADDITIONAL_AREA * 100, mBaseArea * 0.65, mBaseArea, mAdditionalArea);
 465             clearUp = true;
 466         }
 467     }
 468
 469     if (clearUp) {
 470         for (Pictures* working = mPictures.begin(); working != mPictures.end(); working++) {
 471             if (!working->mBase)
 472                 working->mArea.setEmpty();
 473             SkSafeUnref(working->mPicture);
 474             working->mPicture = 0;
 475         }
 476     }
 477
 478 #ifdef DEBUG
 479     XLOG("--- after adding the new inval, but before collapsing ---");
 480     for (Pictures* working = mPictures.begin(); working != mPictures.end(); working++) {
 481         SkIRect currentArea = working->mArea.getBounds();
 482         XLOG("picture %d (%d, %d, %d, %d - %d x %d) (isRect? %c) base: %c",
 483              working - first,
 484              currentArea.fLeft, currentArea.fTop, currentArea.fRight, currentArea.fBottom,
 485              currentArea.width(), currentArea.height(),
 486              working->mArea.isRect() ? 'Y' : 'N',
 487              working->mBase ? 'Y' : 'N');
 488     }
 489     XLOG("----------------------------------");
 490     XLOG("let's collapse...");
 491 #endif
 492
 493     // Finally, let's do a pass to collapse out empty regions
 494     Pictures* writer = first;
 495     for (Pictures* working = first; working != last; working++) {
 496         if (working && working->mArea.isEmpty())
 497             continue;
 498         *writer++ = *working;
 499     }
 500     XLOG("shiking of %d elements", writer - first);
 501     mPictures.shrink(writer - first);
 502
 503 #ifdef DEBUG
 504     XLOG("--- after adding the new inval ---");
 505     for (Pictures* working = mPictures.begin(); working != mPictures.end(); working++) {
 506         SkIRect currentArea = working->mArea.getBounds();
 507         XLOG("picture %d (%d, %d, %d, %d - %d x %d) (isRect? %c) base: %c picture %x",
 508              working - first,
 509              currentArea.fLeft, currentArea.fTop, currentArea.fRight, currentArea.fBottom,
 510              currentArea.width(), currentArea.height(),
 511              working->mArea.isRect() ? 'Y' : 'N',
 512              working->mBase ? 'Y' : 'N', working->mPicture);
 513     }
 514     XLOG("----------------------------------");
 515 #endif
 516
 517     // Base pictures might have been removed/added -- let's recompute them
 518     SkRegion drawn;
 519     if (checkForNewBases) {
 520         drawn.setEmpty();
 521         Pictures* last = mPictures.end();
 522         XLOG("checkForNewBases...");
 523         for (Pictures* working = mPictures.begin(); working != last; working++) {
 524             SkRegion& area = working->mArea;
 525             const SkIRect& a = area.getBounds();
 526             if (drawn.contains(working->mArea) == false) {
 527                 working->mBase = true;
 528                 float area = a.width() * a.height();
 529                 mBaseArea += area;
 530                 mAdditionalArea -= area;
 531             }
 532             drawn.op(working->mArea, SkRegion::kUnion_Op);
 533         }
 534     }
 535 }
 536 #endif // FAST_PICTURESET
 537
 538 void PictureSet::checkDimensions(int width, int height, SkRegion* inval)
 539 {
 540     if (mWidth == width && mHeight == height)
 541         return;
 542     DBG_SET_LOGD("%p old:(w=%d,h=%d) new:(w=%d,h=%d)", this,
 543         mWidth, mHeight, width, height);
 544     if (mWidth == width && height > mHeight) { // only grew vertically
 545         SkIRect rect;
 546         rect.set(0, mHeight, width, height);
 547         inval->op(rect, SkRegion::kUnion_Op);
 548     } else {
 549         clear(); // if both width/height changed, clear the old cache
 550         inval->setRect(0, 0, width, height);
 551     }
 552     mWidth = width;
 553     mHeight = height;
 554 }
 555
 556 void PictureSet::clear()
 557 {
 558     DBG_SET_LOG("");
 559 #ifdef FAST_PICTURESET
 560     for (BucketMap::iterator iter = mBuckets.begin(); iter != mBuckets.end(); ++iter) {
 561          Bucket* bucket = iter->second;
 562          BucketPicture* first = bucket->begin();
 563          BucketPicture* last = bucket->end();
 564          for (BucketPicture* current = first; current != last; current++) {
 565              SkSafeUnref(current->mPicture);
 566              current->mPicture = 0;
 567          }
 568          bucket->clear();
 569     }
 570     mBuckets.clear();
 571 #else
 572     Pictures* last = mPictures.end();
 573     for (Pictures* working = mPictures.begin(); working != last; working++) {
 574         working->mArea.setEmpty();
 575         SkSafeUnref(working->mPicture);
 576     }
 577     mPictures.clear();
 578 #endif // FAST_PICTURESET
 579     mWidth = mHeight = 0;
 580 }
 581
 582 bool PictureSet::draw(SkCanvas* canvas)
 583 {
 584 #ifdef FAST_PICTURESET
 585     XLOG("PictureSet %x draw on canvas %x", this, canvas);
 586     SkRect bounds;
 587     if (canvas->getClipBounds(&bounds) == false)
 588         return false;
 589     SkIRect irect;
 590     bounds.roundOut(&irect);
 591
 592     WTF::Vector<Bucket*> list;
 593     gatherBucketsForArea(list, irect);
 594
 595     XLOG("PictureSet draw on canvas %x, we have %d buckets", canvas, list.size());
 596     for (unsigned int i = 0; i < list.size(); i++) {
 597         Bucket* bucket = list[i];
 598         XLOG("We paint using bucket %x with %d pictures", bucket, bucket->size());
 599         for (unsigned int j = 0; j < bucket->size(); j++)  {
 600             BucketPicture& picture = bucket->at(j);
 601             if (!picture.mPicture)
 602                 continue;
 603             int saved = canvas->save();
 604             SkRect pathBounds;
 605             pathBounds.set(picture.mRealArea);
 606             XLOG("[%d/%d] draw on canvas with clip %d, %d, %d, %d - %d x %d",
 607                   j, bucket->size(),
 608                   picture.mRealArea.fLeft,
 609                   picture.mRealArea.fTop,
 610                   picture.mRealArea.fRight,
 611                   picture.mRealArea.fBottom,
 612                   picture.mRealArea.width(),
 613                   picture.mRealArea.height());
 614             canvas->clipRect(pathBounds);
 615             canvas->translate(pathBounds.fLeft, pathBounds.fTop);
 616             canvas->save();
 617             canvas->drawPicture(*picture.mPicture);
 618             canvas->restoreToCount(saved);
 619         }
 620     }
 621     return false;
 622
 623 #else
 624
 625     validate(__FUNCTION__);
 626     Pictures* first = mPictures.begin();
 627     Pictures* last = mPictures.end();
 628     Pictures* working;
 629     SkRect bounds;
 630     if (canvas->getClipBounds(&bounds) == false)
 631         return false;
 632     SkIRect irect;
 633     bounds.roundOut(&irect);
 634     for (working = last; working != first; ) {
 635         --working;
 636         if (working->mArea.contains(irect)) {
 637 #if PICTURE_SET_DEBUG
 638             const SkIRect& b = working->mArea.getBounds();
 639             DBG_SET_LOGD("contains working->mArea={%d,%d,%d,%d}"
 640                 " irect={%d,%d,%d,%d}", b.fLeft, b.fTop, b.fRight, b.fBottom,
 641                 irect.fLeft, irect.fTop, irect.fRight, irect.fBottom);
 642 #endif
 643             first = working;
 644             break;
 645         }
 646     }
 647     DBG_SET_LOGD("%p first=%d last=%d", this, first - mPictures.begin(),
 648         last - mPictures.begin());
 649     uint32_t maxElapsed = 0;
 650     for (working = first; working != last; working++) {
 651         const SkRegion& area = working->mArea;
 652         if (area.quickReject(irect)) {
 653 #if PICTURE_SET_DEBUG
 654             const SkIRect& b = area.getBounds();
 655             DBG_SET_LOGD("[%d] %p quickReject working->mArea={%d,%d,%d,%d}"
 656                 " irect={%d,%d,%d,%d}", working - first, working,
 657                 b.fLeft, b.fTop, b.fRight, b.fBottom,
 658                 irect.fLeft, irect.fTop, irect.fRight, irect.fBottom);
 659 #endif
 660             working->mElapsed = 0;
 661             continue;
 662         }
 663         int saved = canvas->save();
 664         SkRect pathBounds;
 665         if (area.isComplex()) {
 666             SkPath pathClip;
 667             area.getBoundaryPath(&pathClip);
 668             canvas->clipPath(pathClip);
 669             pathBounds = pathClip.getBounds();
 670         } else {
 671             pathBounds.set(area.getBounds());
 672             canvas->clipRect(pathBounds);
 673         }
 674         canvas->translate(pathBounds.fLeft, pathBounds.fTop);
 675         canvas->save();
 676         uint32_t startTime = getThreadMsec();
 677         canvas->drawPicture(*working->mPicture);
 678         size_t elapsed = working->mElapsed = getThreadMsec() - startTime;
 679         working->mWroteElapsed = true;
 680         if (maxElapsed < elapsed && (pathBounds.width() >= MIN_SPLITTABLE ||
 681                 pathBounds.height() >= MIN_SPLITTABLE))
 682             maxElapsed = elapsed;
 683         canvas->restoreToCount(saved);
 684 #define DRAW_TEST_IMAGE 01
 685 #if DRAW_TEST_IMAGE && PICTURE_SET_DEBUG
 686         SkColor color = 0x3f000000 | (0xffffff & (unsigned) working);
 687         canvas->drawColor(color);
 688         SkPaint paint;
 689         color ^= 0x00ffffff;
 690         paint.setColor(color);
 691         char location[256];
 692         for (int x = area.getBounds().fLeft & ~0x3f;
 693                 x < area.getBounds().fRight; x += 0x40) {
 694             for (int y = area.getBounds().fTop & ~0x3f;
 695                     y < area.getBounds().fBottom; y += 0x40) {
 696                 int len = snprintf(location, sizeof(location) - 1, "(%d,%d)", x, y);
 697                 canvas->drawText(location, len, x, y, paint);
 698             }
 699         }
 700 #endif
 701         DBG_SET_LOGD("[%d] %p working->mArea={%d,%d,%d,%d} elapsed=%d base=%s",
 702             working - first, working,
 703             area.getBounds().fLeft, area.getBounds().fTop,
 704             area.getBounds().fRight, area.getBounds().fBottom,
 705             working->mElapsed, working->mBase ? "true" : "false");
 706     }
 707  //   dump(__FUNCTION__);
 708     return maxElapsed >= MAX_DRAW_TIME;
 709 #endif // FAST_PICTURESET
 710 }
 711
 712 void PictureSet::dump(const char* label) const
 713 {
 714 #if PICTURE_SET_DUMP
 715     DBG_SET_LOGD("%p %s (%d) (w=%d,h=%d)", this, label, mPictures.size(),
 716         mWidth, mHeight);
 717     const Pictures* last = mPictures.end();
 718     for (const Pictures* working = mPictures.begin(); working != last; working++) {
 719         const SkIRect& bounds = working->mArea.getBounds();
 720         const SkIRect& unsplit = working->mUnsplit;
 721         MeasureStream measure;
 722         if (working->mPicture != NULL)
 723             working->mPicture->serialize(&measure);
 724         LOGD(" [%d]"
 725             " mArea.bounds={%d,%d,r=%d,b=%d}"
 726             " mPicture=%p"
 727             " mUnsplit={%d,%d,r=%d,b=%d}"
 728             " mElapsed=%d"
 729             " mSplit=%s"
 730             " mWroteElapsed=%s"
 731             " mBase=%s"
 732             " pict-size=%d",
 733             working - mPictures.begin(),
 734             bounds.fLeft, bounds.fTop, bounds.fRight, bounds.fBottom,
 735             working->mPicture,
 736             unsplit.fLeft, unsplit.fTop, unsplit.fRight, unsplit.fBottom,
 737             working->mElapsed, working->mSplit ? "true" : "false",
 738             working->mWroteElapsed ? "true" : "false",
 739             working->mBase ? "true" : "false",
 740             measure.mTotal);
 741     }
 742 #endif
 743 }
 744
 745 class IsEmptyBounder : public SkBounder {
 746     virtual bool onIRect(const SkIRect& rect) {
 747         return false;
 748     }
 749 };
 750
 751 class IsEmptyCanvas : public SkCanvas {
 752 public:
 753     IsEmptyCanvas(SkBounder* bounder, SkPicture* picture) :
 754             mPicture(picture), mEmpty(true) {
 755         setBounder(bounder);
 756     }
 757
 758     void notEmpty() {
 759         mEmpty = false;
 760         mPicture->abortPlayback();
 761     }
 762
 763     virtual bool clipPath(const SkPath&, SkRegion::Op) {
 764         // this can be expensive to actually do, and doesn't affect the
 765         // question of emptiness, so we make it a no-op
 766         return true;
 767     }
 768
 769     virtual void commonDrawBitmap(const SkBitmap& bitmap, const SkIRect* rect,
 770             const SkMatrix& , const SkPaint& ) {
 771         if (bitmap.width() <= 1 || bitmap.height() <= 1)
 772             return;
 773         DBG_SET_LOGD("abort {%d,%d}", bitmap.width(), bitmap.height());
 774         notEmpty();
 775     }
 776
 777     virtual void drawPaint(const SkPaint& paint) {
 778     }
 779
 780     virtual void drawPath(const SkPath& , const SkPaint& paint) {
 781         DBG_SET_LOG("abort");
 782         notEmpty();
 783     }
 784
 785     virtual void drawPoints(PointMode , size_t , const SkPoint [],
 786                             const SkPaint& paint) {
 787     }
 788
 789     virtual void drawRect(const SkRect& , const SkPaint& paint) {
 790         // wait for visual content
 791         if (paint.getColor() != SK_ColorWHITE)
 792             notEmpty();
 793     }
 794
 795     virtual void drawSprite(const SkBitmap& , int , int ,
 796                             const SkPaint* paint = NULL) {
 797         DBG_SET_LOG("abort");
 798         notEmpty();
 799     }
 800
 801     virtual void drawText(const void* , size_t byteLength, SkScalar ,
 802                           SkScalar , const SkPaint& paint) {
 803         DBG_SET_LOGD("abort %d", byteLength);
 804         notEmpty();
 805     }
 806
 807     virtual void drawPosText(const void* , size_t byteLength,
 808                              const SkPoint [], const SkPaint& paint) {
 809         DBG_SET_LOGD("abort %d", byteLength);
 810         notEmpty();
 811     }
 812
 813     virtual void drawPosTextH(const void* , size_t byteLength,
 814                               const SkScalar [], SkScalar ,
 815                               const SkPaint& paint) {
 816         DBG_SET_LOGD("abort %d", byteLength);
 817         notEmpty();
 818     }
 819
 820     virtual void drawTextOnPath(const void* , size_t byteLength,
 821                                 const SkPath& , const SkMatrix* ,
 822                                 const SkPaint& paint) {
 823         DBG_SET_LOGD("abort %d", byteLength);
 824         notEmpty();
 825     }
 826
 827     virtual void drawPicture(SkPicture& picture) {
 828         SkCanvas::drawPicture(picture);
 829     }
 830
 831     SkPicture* mPicture;
 832     bool mEmpty;
 833 };
 834
 835 bool PictureSet::emptyPicture(SkPicture* picture) const
 836 {
 837     IsEmptyBounder isEmptyBounder;
 838     IsEmptyCanvas checker(&isEmptyBounder, picture);
 839     SkBitmap bitmap;
 840     bitmap.setConfig(SkBitmap::kARGB_8888_Config, mWidth, mHeight);
 841     checker.setBitmapDevice(bitmap);
 842     checker.drawPicture(*picture);
 843     return checker.mEmpty;
 844 }
 845
 846 bool PictureSet::isEmpty() const
 847 {
 848 #ifdef FAST_PICTURESET
 849     // For now, just assume the pictureset is *not* empty
 850     // if the hashmap contains something
 851     for (BucketMap::const_iterator iter = mBuckets.begin(); iter != mBuckets.end(); ++iter) {
 852         if (iter->second->size() > 0)
 853             return false;
 854     }
 855     return true;
 856 #else
 857     const Pictures* last = mPictures.end();
 858     for (const Pictures* working = mPictures.begin(); working != last; working++) {
 859         if (!working->mEmpty)
 860             return false;
 861     }
 862     return true;
 863 #endif // FAST_PICTURESET
 864 }
 865
 866 void PictureSet::set(const PictureSet& src)
 867 {
 868     DBG_SET_LOGD("start %p src=%p", this, &src);
 869     clear();
 870     mWidth = src.mWidth;
 871     mHeight = src.mHeight;
 872 #ifdef FAST_PICTURESET
 873     XLOG("\n--- set picture ---");
 874     for (BucketMap::const_iterator iter = src.mBuckets.begin();
 875          iter != src.mBuckets.end(); ++iter) {
 876          Bucket* sourceBucket = iter->second;
 877          Bucket* targetBucket = getBucket(iter->first.first-1, iter->first.second-1);
 878          BucketPicture* first = sourceBucket->begin();
 879          BucketPicture* last = sourceBucket->end();
 880          XLOG("set from bucket %x (%d, %d), %d pictures", sourceBucket,
 881               iter->first.first, iter->first.second, sourceBucket->size());
 882          for (BucketPicture* current = first; current != last; current++) {
 883              XLOG("set picture %x from bucket %x in bucket %x (%d, %d)",
 884                   current->mPicture, sourceBucket, targetBucket,
 885                   iter->first.first, iter->first.second);
 886              SkSafeRef(current->mPicture);
 887              BucketPicture picture = { current->mPicture, current->mArea,
 888                                        current->mRealArea, current->mBase };
 889              targetBucket->append(picture);
 890          }
 891     }
 892     XLOG("--- DONE set picture ---\n");
 893 #else
 894     const Pictures* last = src.mPictures.end();
 895     for (const Pictures* working = src.mPictures.begin(); working != last; working++)
 896         add(working);
 897  //   dump(__FUNCTION__);
 898     validate(__FUNCTION__);
 899     DBG_SET_LOG("end");
 900 #endif // FAST_PICTURESET
 901 }
 902
 903 #ifdef FAST_PICTURESET
 904 #else
 905
 906 bool PictureSet::reuseSubdivided(const SkRegion& inval)
 907 {
 908     validate(__FUNCTION__);
 909
 910     if (inval.isComplex())
 911         return false;
 912     Pictures* working, * last = mPictures.end();
 913     const SkIRect& invalBounds = inval.getBounds();
 914     bool steal = false;
 915     for (working = mPictures.begin(); working != last; working++) {
 916         if (working->mSplit && invalBounds == working->mUnsplit) {
 917             steal = true;
 918             continue;
 919         }
 920         if (steal == false)
 921             continue;
 922         SkRegion temp = SkRegion(inval);
 923         temp.op(working->mArea, SkRegion::kIntersect_Op);
 924         if (temp.isEmpty() || temp == working->mArea)
 925             continue;
 926         return false;
 927     }
 928     if (steal == false)
 929         return false;
 930     for (working = mPictures.begin(); working != last; working++) {
 931         if ((working->mSplit == false || invalBounds != working->mUnsplit) &&
 932                 inval.contains(working->mArea) == false)
 933             continue;
 934         SkSafeUnref(working->mPicture);
 935         working->mPicture = NULL;
 936     }
 937     return true;
 938 }
 939
 940 void PictureSet::setDrawTimes(const PictureSet& src)
 941 {
 942     validate(__FUNCTION__);
 943     if (mWidth != src.mWidth || mHeight != src.mHeight)
 944         return;
 945     Pictures* last = mPictures.end();
 946     Pictures* working = mPictures.begin();
 947     if (working == last)
 948         return;
 949     const Pictures* srcLast = src.mPictures.end();
 950     const Pictures* srcWorking = src.mPictures.begin();
 951     for (; srcWorking != srcLast; srcWorking++) {
 952         if (srcWorking->mWroteElapsed == false)
 953             continue;
 954         while ((srcWorking->mArea != working->mArea ||
 955                 srcWorking->mPicture != working->mPicture)) {
 956             if (++working == last)
 957                 return;
 958         }
 959         DBG_SET_LOGD("%p [%d] [%d] {%d,%d,r=%d,b=%d} working->mElapsed=%d <- %d",
 960             this, working - mPictures.begin(), srcWorking - src.mPictures.begin(),
 961             working->mArea.getBounds().fLeft, working->mArea.getBounds().fTop,
 962             working->mArea.getBounds().fRight, working->mArea.getBounds().fBottom,
 963             working->mElapsed, srcWorking->mElapsed);
 964         working->mElapsed = srcWorking->mElapsed;
 965     }
 966 }
 967
 968 void PictureSet::setPicture(size_t i, SkPicture* p)
 969 {
 970     SkSafeUnref(mPictures[i].mPicture);
 971     mPictures[i].mPicture = p;
 972     mPictures[i].mEmpty = emptyPicture(p);
 973 }
 974
 975 void PictureSet::split(PictureSet* out) const
 976 {
 977     dump(__FUNCTION__);
 978     DBG_SET_LOGD("%p", this);
 979     SkIRect totalBounds;
 980     out->mWidth = mWidth;
 981     out->mHeight = mHeight;
 982     totalBounds.set(0, 0, mWidth, mHeight);
 983     SkRegion* total = new SkRegion(totalBounds);
 984     const Pictures* last = mPictures.end();
 985     const Pictures* working;
 986     uint32_t balance = 0;
 987     int multiUnsplitFastPictures = 0; // > 1 has more than 1
 988     for (working = mPictures.begin(); working != last; working++) {
 989         if (working->mElapsed >= MAX_DRAW_TIME || working->mSplit)
 990             continue;
 991         if (++multiUnsplitFastPictures > 1)
 992             break;
 993     }
 994     for (working = mPictures.begin(); working != last; working++) {
 995         uint32_t elapsed = working->mElapsed;
 996         if (elapsed < MAX_DRAW_TIME) {
 997             bool split = working->mSplit;
 998             DBG_SET_LOGD("elapsed=%d working=%p total->getBounds()="
 999                 "{%d,%d,r=%d,b=%d} split=%s", elapsed, working,
1000                 total->getBounds().fLeft, total->getBounds().fTop,
1001                 total->getBounds().fRight, total->getBounds().fBottom,
1002                 split ? "true" : "false");
1003             if (multiUnsplitFastPictures <= 1 || split) {
1004                 total->op(working->mArea, SkRegion::kDifference_Op);
1005                 out->add(working->mArea, working->mPicture, elapsed, split,
1006                     working->mEmpty);
1007             } else if (balance < elapsed)
1008                 balance = elapsed;
1009             continue;
1010         }
1011         total->op(working->mArea, SkRegion::kDifference_Op);
1012         const SkIRect& bounds = working->mArea.getBounds();
1013         int width = bounds.width();
1014         int height = bounds.height();
1015         int across = 1;
1016         int down = 1;
1017         while (height >= MIN_SPLITTABLE || width >= MIN_SPLITTABLE) {
1018             if (height >= width) {
1019                 height >>= 1;
1020                 down <<= 1;
1021             } else {
1022                 width >>= 1;
1023                 across <<= 1 ;
1024             }
1025             if ((elapsed >>= 1) < MAX_DRAW_TIME)
1026                 break;
1027         }
1028         width = bounds.width();
1029         height = bounds.height();
1030         int top = bounds.fTop;
1031         for (int indexY = 0; indexY < down; ) {
1032             int bottom = bounds.fTop + height * ++indexY / down;
1033             int left = bounds.fLeft;
1034             for (int indexX = 0; indexX < across; ) {
1035                 int right = bounds.fLeft + width * ++indexX / across;
1036                 SkIRect cBounds;
1037                 cBounds.set(left, top, right, bottom);
1038                 out->add(SkRegion(cBounds), (across | down) != 1 ? NULL :
1039                     working->mPicture, elapsed, true,
1040                     (across | down) != 1 ? false : working->mEmpty);
1041                 left = right;
1042             }
1043             top = bottom;
1044         }
1045     }
1046     DBG_SET_LOGD("%p w=%d h=%d total->isEmpty()=%s multiUnsplitFastPictures=%d",
1047         this, mWidth, mHeight, total->isEmpty() ? "true" : "false",
1048         multiUnsplitFastPictures);
1049     if (!total->isEmpty() && multiUnsplitFastPictures > 1)
1050         out->add(*total, NULL, balance, false, false);
1051     delete total;
1052     validate(__FUNCTION__);
1053     out->dump("split-out");
1054 }
1055
1056 #endif // FAST_PICTURESET
1057
1058 bool PictureSet::validate(const char* funct) const
1059 {
1060 #ifdef FAST_PICTURESET
1061     return true;
1062 #else
1063     bool valid = true;
1064 #if PICTURE_SET_VALIDATE
1065     SkRegion all;
1066     const Pictures* first = mPictures.begin();
1067     for (const Pictures* working = mPictures.end(); working != first; ) {
1068         --working;
1069         const SkPicture* pict = working->mPicture;
1070         const SkRegion& area = working->mArea;
1071         const SkIRect& bounds = area.getBounds();
1072         bool localValid = false;
1073         if (working->mUnsplit.isEmpty())
1074             LOGD("%s working->mUnsplit.isEmpty()", funct);
1075         else if (working->mUnsplit.contains(bounds) == false)
1076             LOGD("%s working->mUnsplit.contains(bounds) == false", funct);
1077         else if (working->mElapsed >= 1000)
1078             LOGD("%s working->mElapsed >= 1000", funct);
1079         else if ((working->mSplit & 0xfe) != 0)
1080             LOGD("%s (working->mSplit & 0xfe) != 0", funct);
1081         else if ((working->mWroteElapsed & 0xfe) != 0)
1082             LOGD("%s (working->mWroteElapsed & 0xfe) != 0", funct);
1083         else if (pict != NULL) {
1084             int pictWidth = pict->width();
1085             int pictHeight = pict->height();
1086             if (pictWidth < bounds.width())
1087                 LOGD("%s pictWidth=%d < bounds.width()=%d", funct, pictWidth, bounds.width());
1088             else if (pictHeight < bounds.height())
1089                 LOGD("%s pictHeight=%d < bounds.height()=%d", funct, pictHeight, bounds.height());
1090             else if (working->mArea.isEmpty())
1091                 LOGD("%s working->mArea.isEmpty()", funct);
1092             else
1093                 localValid = true;
1094         } else
1095             localValid = true;
1096         working->mArea.validate();
1097         if (localValid == false) {
1098             if (all.contains(area) == true)
1099                 LOGD("%s all.contains(area) == true", funct);
1100             else
1101                 localValid = true;
1102         }
1103         valid &= localValid;
1104         all.op(area, SkRegion::kUnion_Op);
1105     }
1106     const SkIRect& allBounds = all.getBounds();
1107     if (valid) {
1108         valid = false;
1109         if (allBounds.width() != mWidth)
1110             LOGD("%s allBounds.width()=%d != mWidth=%d", funct, allBounds.width(), mWidth);
1111         else if (allBounds.height() != mHeight)
1112             LOGD("%s allBounds.height()=%d != mHeight=%d", funct, allBounds.height(), mHeight);
1113         else
1114             valid = true;
1115     }
1116     while (valid == false)
1117         ;
1118 #endif
1119     return valid;
1120 #endif // FAST_PICTURESET
1121 }
1122
1123 } /* namespace android */