1 /*
2 * Copyright 2017 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7 #include "include/core/SkVertices.h"
8
9 #include "include/core/SkTypes.h"
10 #include "include/private/base/SkDebug.h"
11 #include "include/private/base/SkMalloc.h"
12 #include "include/private/base/SkTo.h"
13 #include "src/base/SkSafeMath.h"
14 #include "src/base/SkVx.h"
15 #include "src/core/SkPicturePriv.h"
16 #include "src/core/SkReadBuffer.h"
17 #include "src/core/SkSafeRange.h"
18 #include "src/core/SkVerticesPriv.h"
19 #include "src/core/SkWriteBuffer.h"
20
21 #include <algorithm>
22 #include <atomic>
23 #include <cstdint>
24 #include <new>
25 #include <utility>
26
next_id()27 static uint32_t next_id() {
28 static std::atomic<uint32_t> nextID{1};
29
30 uint32_t id;
31 do {
32 id = nextID.fetch_add(1, std::memory_order_relaxed);
33 } while (id == SK_InvalidGenID);
34 return id;
35 }
36
37 struct SkVertices::Desc {
38 VertexMode fMode;
39 int fVertexCount,
40 fIndexCount;
41 bool fHasTexs,
42 fHasColors;
43 };
44
45 struct SkVertices::Sizes {
SizesSkVertices::Sizes46 Sizes(const Desc& desc) {
47 SkSafeMath safe;
48
49 fVSize = safe.mul(desc.fVertexCount, sizeof(SkPoint));
50 fTSize = desc.fHasTexs ? safe.mul(desc.fVertexCount, sizeof(SkPoint)) : 0;
51 fCSize = desc.fHasColors ? safe.mul(desc.fVertexCount, sizeof(SkColor)) : 0;
52
53 fBuilderTriFanISize = 0;
54 fISize = safe.mul(desc.fIndexCount, sizeof(uint16_t));
55 if (kTriangleFan_VertexMode == desc.fMode) {
56 int numFanTris = 0;
57 if (desc.fIndexCount) {
58 fBuilderTriFanISize = fISize;
59 numFanTris = desc.fIndexCount - 2;
60 } else {
61 numFanTris = desc.fVertexCount - 2;
62 // By forcing this to become indexed we are adding a constraint to the maximum
63 // number of vertices.
64 if (desc.fVertexCount > (SkTo<int>(UINT16_MAX) + 1)) {
65 sk_bzero(this, sizeof(*this));
66 return;
67 }
68 }
69 if (numFanTris <= 0) {
70 sk_bzero(this, sizeof(*this));
71 return;
72 }
73 fISize = safe.mul(numFanTris, 3 * sizeof(uint16_t));
74 }
75
76 fTotal = safe.add(sizeof(SkVertices),
77 safe.add(fVSize,
78 safe.add(fTSize,
79 safe.add(fCSize,
80 fISize))));
81
82 if (safe.ok()) {
83 fArrays = fVSize + fTSize + fCSize + fISize; // just the sum of the arrays
84 } else {
85 sk_bzero(this, sizeof(*this));
86 }
87 }
88
isValidSkVertices::Sizes89 bool isValid() const {
90 SkASSERT(fTotal >= fVSize);
91 return fVSize > 0;
92 }
93
94 size_t fTotal = 0; // size of entire SkVertices allocation (obj + arrays)
95 size_t fArrays; // size of all the data arrays (V + D + T + C + I)
96 size_t fVSize;
97 size_t fTSize;
98 size_t fCSize;
99 size_t fISize;
100
101 // For indexed tri-fans this is the number of amount of space fo indices needed in the builder
102 // before conversion to indexed triangles (or zero if not indexed or not a triangle fan).
103 size_t fBuilderTriFanISize;
104 };
105
Builder(VertexMode mode,int vertexCount,int indexCount,uint32_t builderFlags)106 SkVertices::Builder::Builder(VertexMode mode, int vertexCount, int indexCount,
107 uint32_t builderFlags) {
108 bool hasTexs = SkToBool(builderFlags & SkVertices::kHasTexCoords_BuilderFlag);
109 bool hasColors = SkToBool(builderFlags & SkVertices::kHasColors_BuilderFlag);
110 this->init({mode, vertexCount, indexCount, hasTexs, hasColors});
111 }
112
Builder(const Desc & desc)113 SkVertices::Builder::Builder(const Desc& desc) {
114 this->init(desc);
115 }
116
init(const Desc & desc)117 void SkVertices::Builder::init(const Desc& desc) {
118 Sizes sizes(desc);
119 if (!sizes.isValid()) {
120 SkASSERT(!this->isValid());
121 return;
122 }
123
124 void* storage = ::operator new (sizes.fTotal);
125 if (sizes.fBuilderTriFanISize) {
126 fIntermediateFanIndices.reset(new uint8_t[sizes.fBuilderTriFanISize]);
127 }
128
129 fVertices.reset(new (storage) SkVertices);
130
131 // need to point past the object to store the arrays
132 char* ptr = (char*)storage + sizeof(SkVertices);
133
134 // return the original ptr (or null), but then advance it by size
135 auto advance = [&ptr](size_t size) {
136 char* new_ptr = size ? ptr : nullptr;
137 ptr += size;
138 return new_ptr;
139 };
140
141 fVertices->fPositions = (SkPoint*) advance(sizes.fVSize);
142 fVertices->fTexs = (SkPoint*) advance(sizes.fTSize);
143 fVertices->fColors = (SkColor*) advance(sizes.fCSize);
144 fVertices->fIndices = (uint16_t*)advance(sizes.fISize);
145
146 fVertices->fVertexCount = desc.fVertexCount;
147 fVertices->fIndexCount = desc.fIndexCount;
148 fVertices->fMode = desc.fMode;
149
150 // We defer assigning fBounds and fUniqueID until detach() is called
151 }
152
detach()153 sk_sp<SkVertices> SkVertices::Builder::detach() {
154 if (fVertices) {
155 fVertices->fBounds.setBounds(fVertices->fPositions, fVertices->fVertexCount);
156 if (fVertices->fMode == kTriangleFan_VertexMode) {
157 if (fIntermediateFanIndices) {
158 SkASSERT(fVertices->fIndexCount);
159 auto tempIndices = this->indices();
160 for (int t = 0; t < fVertices->fIndexCount - 2; ++t) {
161 fVertices->fIndices[3 * t + 0] = tempIndices[0];
162 fVertices->fIndices[3 * t + 1] = tempIndices[t + 1];
163 fVertices->fIndices[3 * t + 2] = tempIndices[t + 2];
164 }
165 fVertices->fIndexCount = 3 * (fVertices->fIndexCount - 2);
166 } else {
167 SkASSERT(!fVertices->fIndexCount);
168 for (int t = 0; t < fVertices->fVertexCount - 2; ++t) {
169 fVertices->fIndices[3 * t + 0] = 0;
170 fVertices->fIndices[3 * t + 1] = SkToU16(t + 1);
171 fVertices->fIndices[3 * t + 2] = SkToU16(t + 2);
172 }
173 fVertices->fIndexCount = 3 * (fVertices->fVertexCount - 2);
174 }
175 fVertices->fMode = kTriangles_VertexMode;
176 }
177 fVertices->fUniqueID = next_id();
178 return std::move(fVertices); // this will null fVertices after the return
179 }
180 return nullptr;
181 }
182
positions()183 SkPoint* SkVertices::Builder::positions() {
184 return fVertices ? const_cast<SkPoint*>(fVertices->fPositions) : nullptr;
185 }
186
texCoords()187 SkPoint* SkVertices::Builder::texCoords() {
188 return fVertices ? const_cast<SkPoint*>(fVertices->fTexs) : nullptr;
189 }
190
colors()191 SkColor* SkVertices::Builder::colors() {
192 return fVertices ? const_cast<SkColor*>(fVertices->fColors) : nullptr;
193 }
194
indices()195 uint16_t* SkVertices::Builder::indices() {
196 if (!fVertices) {
197 return nullptr;
198 }
199 if (fIntermediateFanIndices) {
200 return reinterpret_cast<uint16_t*>(fIntermediateFanIndices.get());
201 }
202 return const_cast<uint16_t*>(fVertices->fIndices);
203 }
204
205 ///////////////////////////////////////////////////////////////////////////////////////////////////
206
MakeCopy(VertexMode mode,int vertexCount,const SkPoint pos[],const SkPoint texs[],const SkColor colors[],int indexCount,const uint16_t indices[])207 sk_sp<SkVertices> SkVertices::MakeCopy(VertexMode mode, int vertexCount,
208 const SkPoint pos[], const SkPoint texs[],
209 const SkColor colors[],
210 int indexCount, const uint16_t indices[]) {
211 auto desc = Desc{mode, vertexCount, indexCount, !!texs, !!colors};
212 Builder builder(desc);
213 if (!builder.isValid()) {
214 return nullptr;
215 }
216
217 Sizes sizes(desc);
218 SkASSERT(sizes.isValid());
219 sk_careful_memcpy(builder.positions(), pos, sizes.fVSize);
220 sk_careful_memcpy(builder.texCoords(), texs, sizes.fTSize);
221 sk_careful_memcpy(builder.colors(), colors, sizes.fCSize);
222
223 // The builder can update the number of indices.
224 const size_t isize = ((mode == kTriangleFan_VertexMode) ? sizes.fBuilderTriFanISize
225 : sizes.fISize),
226 icount = isize / sizeof(uint16_t);
227
228 // Ensure that indices are valid for the given vertex count.
229 SkASSERT(vertexCount > 0);
230 const uint16_t max_index = SkToU16(vertexCount - 1);
231
232 size_t i = 0;
233 for (; i + 8 <= icount; i += 8) {
234 const skvx::ushort8 ind8 = skvx::ushort8::Load(indices + i),
235 clamped_ind8 = skvx::min(ind8, max_index);
236 clamped_ind8.store(builder.indices() + i);
237 }
238 if (i + 4 <= icount) {
239 const skvx::ushort4 ind4 = skvx::ushort4::Load(indices + i),
240 clamped_ind4 = skvx::min(ind4, max_index);
241 clamped_ind4.store(builder.indices() + i);
242
243 i += 4;
244 }
245 if (i + 2 <= icount) {
246 const skvx::ushort2 ind2 = skvx::ushort2::Load(indices + i),
247 clamped_ind2 = skvx::min(ind2, max_index);
248 clamped_ind2.store(builder.indices() + i);
249
250 i += 2;
251 }
252 if (i < icount) {
253 builder.indices()[i] = std::min(indices[i], max_index);
254 SkDEBUGCODE(i += 1);
255 }
256 SkASSERT(i == icount);
257
258 return builder.detach();
259 }
260
approximateSize() const261 size_t SkVertices::approximateSize() const {
262 return this->getSizes().fTotal;
263 }
264
getSizes() const265 SkVertices::Sizes SkVertices::getSizes() const {
266 Sizes sizes({fMode, fVertexCount, fIndexCount, !!fTexs, !!fColors});
267 SkASSERT(sizes.isValid());
268 return sizes;
269 }
270
271 ///////////////////////////////////////////////////////////////////////////////////////////////////
272
273 // storage = packed | vertex_count | index_count | attr_count
274 // | pos[] | custom[] | texs[] | colors[] | indices[]
275
276 #define kMode_Mask 0x0FF
277 #define kHasTexs_Mask 0x100
278 #define kHasColors_Mask 0x200
279
encode(SkWriteBuffer & buffer) const280 void SkVerticesPriv::encode(SkWriteBuffer& buffer) const {
281 // packed has room for additional flags in the future
282 uint32_t packed = static_cast<uint32_t>(fVertices->fMode);
283 SkASSERT((packed & ~kMode_Mask) == 0); // our mode fits in the mask bits
284 if (fVertices->fTexs) {
285 packed |= kHasTexs_Mask;
286 }
287 if (fVertices->fColors) {
288 packed |= kHasColors_Mask;
289 }
290
291 SkVertices::Sizes sizes = fVertices->getSizes();
292 SkASSERT(!sizes.fBuilderTriFanISize);
293
294 // Header
295 buffer.writeUInt(packed);
296 buffer.writeInt(fVertices->fVertexCount);
297 buffer.writeInt(fVertices->fIndexCount);
298
299 // Data arrays
300 buffer.writeByteArray(fVertices->fPositions, sizes.fVSize);
301 buffer.writeByteArray(fVertices->fTexs, sizes.fTSize);
302 buffer.writeByteArray(fVertices->fColors, sizes.fCSize);
303 // if index-count is odd, we won't be 4-bytes aligned, so we call the pad version
304 buffer.writeByteArray(fVertices->fIndices, sizes.fISize);
305 }
306
Decode(SkReadBuffer & buffer)307 sk_sp<SkVertices> SkVerticesPriv::Decode(SkReadBuffer& buffer) {
308 auto decode = [](SkReadBuffer& buffer) -> sk_sp<SkVertices> {
309 SkSafeRange safe;
310 bool hasCustomData = buffer.isVersionLT(SkPicturePriv::kVerticesRemoveCustomData_Version);
311
312 const uint32_t packed = buffer.readUInt();
313 const int vertexCount = safe.checkGE(buffer.readInt(), 0);
314 const int indexCount = safe.checkGE(buffer.readInt(), 0);
315 const int attrCount = hasCustomData ? safe.checkGE(buffer.readInt(), 0) : 0;
316 const SkVertices::VertexMode mode = safe.checkLE<SkVertices::VertexMode>(
317 packed & kMode_Mask, SkVertices::kLast_VertexMode);
318 const bool hasTexs = SkToBool(packed & kHasTexs_Mask);
319 const bool hasColors = SkToBool(packed & kHasColors_Mask);
320
321 // Check that the header fields and buffer are valid. If this is data with the experimental
322 // custom attributes feature - we don't support that any more.
323 // We also don't support serialized triangle-fan data. We stopped writing that long ago,
324 // so it should never appear in valid encoded data.
325 if (!safe || !buffer.isValid() || attrCount ||
326 mode == SkVertices::kTriangleFan_VertexMode) {
327 return nullptr;
328 }
329
330 const SkVertices::Desc desc{mode, vertexCount, indexCount, hasTexs, hasColors};
331 SkVertices::Sizes sizes(desc);
332 if (!sizes.isValid() || sizes.fArrays > buffer.available()) {
333 return nullptr;
334 }
335
336 SkVertices::Builder builder(desc);
337 if (!builder.isValid()) {
338 return nullptr;
339 }
340
341 buffer.readByteArray(builder.positions(), sizes.fVSize);
342 if (hasCustomData) {
343 size_t customDataSize = 0;
344 buffer.skipByteArray(&customDataSize);
345 if (customDataSize != 0) {
346 return nullptr;
347 }
348 }
349 buffer.readByteArray(builder.texCoords(), sizes.fTSize);
350 buffer.readByteArray(builder.colors(), sizes.fCSize);
351 buffer.readByteArray(builder.indices(), sizes.fISize);
352
353 if (!buffer.isValid()) {
354 return nullptr;
355 }
356
357 if (indexCount > 0) {
358 // validate that the indices are in range
359 const uint16_t* indices = builder.indices();
360 for (int i = 0; i < indexCount; ++i) {
361 if (indices[i] >= (unsigned)vertexCount) {
362 return nullptr;
363 }
364 }
365 }
366
367 return builder.detach();
368 };
369
370 if (auto verts = decode(buffer)) {
371 return verts;
372 }
373 buffer.validate(false);
374 return nullptr;
375 }
376
operator delete(void * p)377 void SkVertices::operator delete(void* p) {
378 ::operator delete(p);
379 }
380