The Tor Browser / file comparison
comparison: gfx/skia/trunk/src/core/SkRegion_rects.cpp
gfx/skia/trunk/src/core/SkRegion_rects.cpp
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:f03d81b60e64 |
|---|---|
| 1 | |
| 2 /* | |
| 3 * Copyright 2011 Google Inc. | |
| 4 * | |
| 5 * Use of this source code is governed by a BSD-style license that can be | |
| 6 * found in the LICENSE file. | |
| 7 */ | |
| 8 #include "SkRegion.h" | |
| 9 #include "SkChunkAlloc.h" | |
| 10 #include "SkTDArray.h" | |
| 11 #include "SkTemplates.h" | |
| 12 | |
| 13 #if 0 | |
| 14 | |
| 15 struct VEdge { | |
| 16 VEdge* fPrev; | |
| 17 VEdge* fNext; | |
| 18 | |
| 19 SkRegion::RunType fX; | |
| 20 SkRegion::RunType fTop; | |
| 21 SkRegion::RunType fBottom; | |
| 22 int fWinding; | |
| 23 | |
| 24 void removeFromList() { | |
| 25 fPrev->fNext = fNext; | |
| 26 fNext->fPrev = fPrev; | |
| 27 } | |
| 28 | |
| 29 void backwardsInsert() { | |
| 30 while (fPrev->fX > fX) { | |
| 31 VEdge* prev = fPrev; | |
| 32 VEdge* next = this; | |
| 33 | |
| 34 // remove prev from the list | |
| 35 prev->fPrev->fNext = next; | |
| 36 next->fPrev = prev->fPrev; | |
| 37 | |
| 38 // insert prev after next | |
| 39 prev->fNext = next->fNext; | |
| 40 next->fNext->fPrev = prev; | |
| 41 next->fNext = prev; | |
| 42 prev->fPrev = next; | |
| 43 } | |
| 44 } | |
| 45 | |
| 46 static void SetFromRect(VEdge edges[], const SkIRect& r) { | |
| 47 edges[0].fX = r.fLeft; | |
| 48 edges[0].fTop = r.fTop; | |
| 49 edges[0].fBottom = r.fBottom; | |
| 50 edges[0].fWinding = -1; | |
| 51 | |
| 52 edges[1].fX = r.fRight; | |
| 53 edges[1].fTop = r.fTop; | |
| 54 edges[1].fBottom = r.fBottom; | |
| 55 edges[1].fWinding = 1; | |
| 56 } | |
| 57 }; | |
| 58 | |
| 59 class Accumulator { | |
| 60 public: | |
| 61 Accumulator(SkRegion::RunType top, int numRects); | |
| 62 ~Accumulator() {} | |
| 63 | |
| 64 SkRegion::RunType append(SkRegion::RunType top, const VEdge* edge); | |
| 65 | |
| 66 int count() const { return fTotalCount; } | |
| 67 void copyTo(SkRegion::RunType dst[]); | |
| 68 | |
| 69 private: | |
| 70 struct Row { | |
| 71 SkRegion::RunType* fPtr; | |
| 72 SkRegion::RunType fBottom; | |
| 73 int fCount; // just [L R] count | |
| 74 }; | |
| 75 SkChunkAlloc fAlloc; | |
| 76 SkTDArray<Row> fRows; | |
| 77 SkRegion::RunType fTop; | |
| 78 int fTotalCount; | |
| 79 int fRectCount; | |
| 80 }; | |
| 81 | |
| 82 Accumulator::Accumulator(SkRegion::RunType top, int numRects) | |
| 83 : fAlloc((1 + numRects * 2 + 1) * sizeof(int32_t)) { | |
| 84 fRectCount = numRects; | |
| 85 fTop = top; | |
| 86 fTotalCount = 2; // Top + final sentinel | |
| 87 } | |
| 88 | |
| 89 //#define TRACE_ROW(code) code | |
| 90 #define TRACE_ROW(code) | |
| 91 | |
| 92 SkRegion::RunType Accumulator::append(SkRegion::RunType currY, const VEdge* edge) { | |
| 93 // worst-case size | |
| 94 size_t size = fRectCount * 2 * sizeof(SkRegion::RunType); | |
| 95 SkRegion::RunType* row = (SkRegion::RunType*)fAlloc.allocThrow(size); | |
| 96 SkRegion::RunType* rowHead = row; | |
| 97 | |
| 98 SkRegion::RunType nextY = SkRegion::kRunTypeSentinel; | |
| 99 int winding = edge->fWinding; | |
| 100 | |
| 101 // record the L R values for this row | |
| 102 | |
| 103 if (edge->fTop > currY) { | |
| 104 nextY = SkMin32(nextY, edge->fTop); | |
| 105 TRACE_ROW(SkDebugf("Y %d\n", currY);) | |
| 106 } else { | |
| 107 SkRegion::RunType currR; | |
| 108 *row++ = edge->fX; | |
| 109 TRACE_ROW(SkDebugf("Y %d [%d", currY, edge->fX);) | |
| 110 edge = edge->fNext; | |
| 111 for (;;) { | |
| 112 if (edge->fTop > currY) { | |
| 113 nextY = SkMin32(nextY, edge->fTop); | |
| 114 break; | |
| 115 } | |
| 116 | |
| 117 int prevWinding = winding; | |
| 118 winding += edge->fWinding; | |
| 119 if (0 == winding) { // we finished an interval | |
| 120 currR = edge->fX; | |
| 121 } else if (0 == prevWinding && edge->fX > currR) { | |
| 122 *row++ = currR; | |
| 123 *row++ = edge->fX; | |
| 124 TRACE_ROW(SkDebugf(" %d] [%d", currR, edge->fX);) | |
| 125 } | |
| 126 | |
| 127 nextY = SkMin32(nextY, edge->fBottom); | |
| 128 edge = edge->fNext; | |
| 129 } | |
| 130 SkASSERT(0 == winding); | |
| 131 *row++ = currR; | |
| 132 TRACE_ROW(SkDebugf(" %d]\n", currR);) | |
| 133 } | |
| 134 int rowCount = row - rowHead; | |
| 135 | |
| 136 // now see if we have already seen this row, or if its unique | |
| 137 | |
| 138 Row* r = fRows.count() ? &fRows[fRows.count() - 1] : NULL; | |
| 139 if (r && (r->fCount == rowCount) && | |
| 140 !memcmp(r->fPtr, rowHead, | |
| 141 rowCount * sizeof(SkRegion::RunType))) { | |
| 142 r->fBottom = nextY; // update bottom | |
| 143 fAlloc.unalloc(rowHead); | |
| 144 } else { | |
| 145 Row* r = fRows.append(); | |
| 146 r->fPtr = rowHead; | |
| 147 r->fBottom = nextY; | |
| 148 r->fCount = rowCount; | |
| 149 fTotalCount += 1 + rowCount + 1; | |
| 150 } | |
| 151 | |
| 152 return nextY; | |
| 153 } | |
| 154 | |
| 155 void Accumulator::copyTo(SkRegion::RunType dst[]) { | |
| 156 SkDEBUGCODE(SkRegion::RunType* startDst = dst;) | |
| 157 | |
| 158 *dst++ = fTop; | |
| 159 | |
| 160 const Row* curr = fRows.begin(); | |
| 161 const Row* stop = fRows.end(); | |
| 162 while (curr < stop) { | |
| 163 *dst++ = curr->fBottom; | |
| 164 memcpy(dst, curr->fPtr, curr->fCount * sizeof(SkRegion::RunType)); | |
| 165 dst += curr->fCount; | |
| 166 *dst++ = SkRegion::kRunTypeSentinel; | |
| 167 curr += 1; | |
| 168 } | |
| 169 *dst++ = SkRegion::kRunTypeSentinel; | |
| 170 SkASSERT(dst - startDst == fTotalCount); | |
| 171 } | |
| 172 | |
| 173 /////////////////////////////////////////////////////////////////////////////// | |
| 174 | |
| 175 template <typename T> int SkTCmp2Int(const T& a, const T& b) { | |
| 176 return (a < b) ? -1 : ((b < a) ? 1 : 0); | |
| 177 } | |
| 178 | |
| 179 static inline int SkCmp32(int32_t a, int32_t b) { | |
| 180 return (a < b) ? -1 : ((b < a) ? 1 : 0); | |
| 181 } | |
| 182 | |
| 183 static int compare_edgeptr(const void* p0, const void* p1) { | |
| 184 const VEdge* e0 = *static_cast<VEdge*const*>(p0); | |
| 185 const VEdge* e1 = *static_cast<VEdge*const*>(p1); | |
| 186 | |
| 187 SkRegion::RunType v0 = e0->fTop; | |
| 188 SkRegion::RunType v1 = e1->fTop; | |
| 189 | |
| 190 if (v0 == v1) { | |
| 191 v0 = e0->fX; | |
| 192 v1 = e1->fX; | |
| 193 } | |
| 194 return SkCmp32(v0, v1); | |
| 195 } | |
| 196 | |
| 197 // fillout edge[] from rects[], sorted. Return the head, and set the tail | |
| 198 // | |
| 199 static VEdge* sort_edges(VEdge** edgePtr, VEdge edge[], const SkIRect rects[], | |
| 200 int rectCount, VEdge** edgeTail) { | |
| 201 int i; | |
| 202 VEdge** ptr = edgePtr; | |
| 203 for (int i = 0; i < rectCount; i++) { | |
| 204 if (!rects[i].isEmpty()) { | |
| 205 VEdge::SetFromRect(edge, rects[i]); | |
| 206 *ptr++ = edge++; | |
| 207 *ptr++ = edge++; | |
| 208 } | |
| 209 } | |
| 210 | |
| 211 int edgeCount = ptr - edgePtr; | |
| 212 if (0 == edgeCount) { | |
| 213 // all the rects[] were empty | |
| 214 return NULL; | |
| 215 } | |
| 216 | |
| 217 qsort(edgePtr, edgeCount, sizeof(*edgePtr), compare_edgeptr); | |
| 218 for (i = 1; i < edgeCount; i++) { | |
| 219 edgePtr[i - 1]->fNext = edgePtr[i]; | |
| 220 edgePtr[i]->fPrev = edgePtr[i - 1]; | |
| 221 } | |
| 222 *edgeTail = edgePtr[edgeCount - 1]; | |
| 223 return edgePtr[0]; | |
| 224 } | |
| 225 | |
| 226 bool SkRegion::setRects(const SkIRect rects[], int rectCount) { | |
| 227 if (0 == rectCount) { | |
| 228 return this->setEmpty(); | |
| 229 } | |
| 230 if (1 == rectCount) { | |
| 231 return this->setRect(rects[0]); | |
| 232 } | |
| 233 | |
| 234 int edgeCount = rectCount * 2; | |
| 235 SkAutoMalloc memory((sizeof(VEdge) + sizeof(VEdge*)) * edgeCount); | |
| 236 VEdge** edgePtr = (VEdge**)memory.get(); | |
| 237 VEdge* tail, *head = (VEdge*)(edgePtr + edgeCount); | |
| 238 head = sort_edges(edgePtr, head, rects, rectCount, &tail); | |
| 239 // check if we have no edges | |
| 240 if (NULL == head) { | |
| 241 return this->setEmpty(); | |
| 242 } | |
| 243 | |
| 244 // at this stage, we don't really care about edgeCount, or if rectCount is | |
| 245 // larger that it should be (since sort_edges might have skipped some | |
| 246 // empty rects[]). rectCount now is just used for worst-case allocations | |
| 247 | |
| 248 VEdge headEdge, tailEdge; | |
| 249 headEdge.fPrev = NULL; | |
| 250 headEdge.fNext = head; | |
| 251 headEdge.fTop = SK_MinS32; | |
| 252 headEdge.fX = SK_MinS32; | |
| 253 head->fPrev = &headEdge; | |
| 254 | |
| 255 tailEdge.fPrev = tail; | |
| 256 tailEdge.fNext = NULL; | |
| 257 tailEdge.fTop = SK_MaxS32; | |
| 258 tail->fNext = &tailEdge; | |
| 259 | |
| 260 int32_t currY = head->fTop; | |
| 261 Accumulator accum(currY, rectCount); | |
| 262 | |
| 263 while (head->fNext) { | |
| 264 VEdge* edge = head; | |
| 265 // accumulate the current | |
| 266 SkRegion::RunType nextY = accum.append(currY, edge); | |
| 267 // remove the old | |
| 268 while (edge->fTop <= currY) { | |
| 269 VEdge* next = edge->fNext; | |
| 270 if (edge->fBottom <= nextY) { | |
| 271 edge->removeFromList(); | |
| 272 } | |
| 273 edge = next; | |
| 274 } | |
| 275 // insert (sorted) the new | |
| 276 while (edge->fTop == nextY) { | |
| 277 VEdge* next = edge->fNext; | |
| 278 edge->backwardsInsert(); | |
| 279 edge = next; | |
| 280 } | |
| 281 currY = nextY; | |
| 282 head = headEdge.fNext; | |
| 283 } | |
| 284 | |
| 285 SkAutoTArray<RunType> runs(accum.count()); | |
| 286 accum.copyTo(runs.get()); | |
| 287 return this->setRuns(runs.get(), accum.count()); | |
| 288 } | |
| 289 | |
| 290 #endif |
