SkTextBlob.cpp revision 2af858354d913397a6c316ef46a5d52d686e10ab 
1/*
2 * Copyright 2014 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
8#include "SkTextBlob.h"
9
10#include "SkReadBuffer.h"
11#include "SkTypeface.h"
12#include "SkWriteBuffer.h"
13
14//
15// Textblob data is laid out into externally-managed storage as follows:
16//
17//    -----------------------------------------------------------------------------
18//   | SkTextBlob | RunRecord | Glyphs[] | Pos[] | RunRecord | Glyphs[] | Pos[] | ...
19//    -----------------------------------------------------------------------------
20//
21//  Each run record describes a text blob run, and can be used to determine the (implicit)
22//  location of the following record.
23
24SkDEBUGCODE(static const unsigned kRunRecordMagic = 0xb10bcafe;)
25
26class SkTextBlob::RunRecord {
27public:
28    RunRecord(uint32_t count, const SkPoint& offset, const SkPaint& font, GlyphPositioning pos)
29        : fCount(count)
30        , fOffset(offset)
31        , fFont(font)
32        , fPositioning(pos) {
33        SkDEBUGCODE(fMagic = kRunRecordMagic);
34    }
35
36    uint32_t glyphCount() const {
37        return fCount;
38    }
39
40    const SkPoint& offset() const {
41        return fOffset;
42    }
43
44    const SkPaint& font() const {
45        return fFont;
46    }
47
48    GlyphPositioning positioning() const {
49        return fPositioning;
50    }
51
52    uint16_t* glyphBuffer() const {
53        // Glyph are stored immediately following the record.
54        return reinterpret_cast<uint16_t*>(const_cast<RunRecord*>(this) + 1);
55    }
56
57    SkScalar* posBuffer() const {
58        // Position scalars follow the (aligned) glyph buffer.
59        return reinterpret_cast<SkScalar*>(reinterpret_cast<uint8_t*>(this->glyphBuffer()) +
60                                           SkAlign4(fCount * sizeof(uint16_t)));
61    }
62
63    static size_t StorageSize(int glyphCount, SkTextBlob::GlyphPositioning positioning) {
64        // RunRecord object + (aligned) glyph buffer + position buffer
65        return SkAlignPtr(sizeof(SkTextBlob::RunRecord)
66                        + SkAlign4(glyphCount* sizeof(uint16_t))
67                        + glyphCount * sizeof(SkScalar) * ScalarsPerGlyph(positioning));
68    }
69
70    static const RunRecord* First(const SkTextBlob* blob) {
71        // The first record (if present) is stored following the blob object.
72        return reinterpret_cast<const RunRecord*>(blob + 1);
73    }
74
75    static const RunRecord* Next(const RunRecord* run) {
76        return reinterpret_cast<const RunRecord*>(reinterpret_cast<const uint8_t*>(run)
77            + StorageSize(run->glyphCount(), run->positioning()));
78    }
79
80    void validate(uint8_t* storageTop) const {
81        SkASSERT(kRunRecordMagic == fMagic);
82        SkASSERT((uint8_t*)Next(this) <= storageTop);
83        SkASSERT(glyphBuffer() + fCount <= (uint16_t*)posBuffer());
84        SkASSERT(posBuffer() + fCount * ScalarsPerGlyph(fPositioning) <= (SkScalar*)Next(this));
85    }
86
87private:
88    friend class SkTextBlobBuilder;
89
90    void grow(uint32_t count) {
91        SkScalar* initialPosBuffer = posBuffer();
92        uint32_t initialCount = fCount;
93        fCount += count;
94
95        // Move the initial pos scalars to their new location.
96        size_t copySize = initialCount * sizeof(SkScalar) * ScalarsPerGlyph(fPositioning);
97        SkASSERT((uint8_t*)posBuffer() + copySize <= (uint8_t*)Next(this));
98
99        // memmove, as the buffers may overlap
100        memmove(posBuffer(), initialPosBuffer, copySize);
101    }
102
103    uint32_t         fCount;
104    SkPoint          fOffset;
105    SkPaint          fFont;
106    GlyphPositioning fPositioning;
107
108    SkDEBUGCODE(unsigned fMagic;)
109};
110
111static int32_t gNextID = 1;
112static int32_t next_id() {
113    int32_t id;
114    do {
115        id = sk_atomic_inc(&gNextID);
116    } while (id == SK_InvalidGenID);
117    return id;
118}
119
120SkTextBlob::SkTextBlob(int runCount, const SkRect& bounds)
121    : fRunCount(runCount)
122    , fBounds(bounds)
123    , fUniqueID(next_id()) {
124}
125
126SkTextBlob::~SkTextBlob() {
127    const RunRecord* run = RunRecord::First(this);
128    for (int i = 0; i < fRunCount; ++i) {
129        const RunRecord* nextRun = RunRecord::Next(run);
130        SkDEBUGCODE(run->validate((uint8_t*)this + fStorageSize);)
131        run->~RunRecord();
132        run = nextRun;
133    }
134}
135
136void SkTextBlob::flatten(SkWriteBuffer& buffer) const {
137    int runCount = fRunCount;
138
139    buffer.write32(runCount);
140    buffer.writeRect(fBounds);
141
142    SkPaint runPaint;
143    RunIterator it(this);
144    while (!it.done()) {
145        SkASSERT(it.glyphCount() > 0);
146
147        buffer.write32(it.glyphCount());
148        buffer.write32(it.positioning());
149        buffer.writePoint(it.offset());
150        // This should go away when switching to SkFont
151        it.applyFontToPaint(&runPaint);
152        buffer.writePaint(runPaint);
153
154        buffer.writeByteArray(it.glyphs(), it.glyphCount() * sizeof(uint16_t));
155        buffer.writeByteArray(it.pos(),
156            it.glyphCount() * sizeof(SkScalar) * ScalarsPerGlyph(it.positioning()));
157
158        it.next();
159        SkDEBUGCODE(runCount--);
160    }
161    SkASSERT(0 == runCount);
162}
163
164const SkTextBlob* SkTextBlob::CreateFromBuffer(SkReadBuffer& reader) {
165    int runCount = reader.read32();
166    if (runCount < 0) {
167        return NULL;
168    }
169
170    SkRect bounds;
171    reader.readRect(&bounds);
172
173    SkTextBlobBuilder blobBuilder;
174    for (int i = 0; i < runCount; ++i) {
175        int glyphCount = reader.read32();
176        GlyphPositioning pos = static_cast<GlyphPositioning>(reader.read32());
177        if (glyphCount <= 0 || pos > kFull_Positioning) {
178            return NULL;
179        }
180
181        SkPoint offset;
182        reader.readPoint(&offset);
183        SkPaint font;
184        reader.readPaint(&font);
185
186        const SkTextBlobBuilder::RunBuffer* buf = NULL;
187        switch (pos) {
188        case kDefault_Positioning:
189            buf = &blobBuilder.allocRun(font, glyphCount, offset.x(), offset.y(), &bounds);
190            break;
191        case kHorizontal_Positioning:
192            buf = &blobBuilder.allocRunPosH(font, glyphCount, offset.y(), &bounds);
193            break;
194        case kFull_Positioning:
195            buf = &blobBuilder.allocRunPos(font, glyphCount, &bounds);
196            break;
197        default:
198            return NULL;
199        }
200
201        if (!reader.readByteArray(buf->glyphs, glyphCount * sizeof(uint16_t)) ||
202            !reader.readByteArray(buf->pos,
203                                  glyphCount * sizeof(SkScalar) * ScalarsPerGlyph(pos))) {
204            return NULL;
205        }
206    }
207
208    return blobBuilder.build();
209}
210
211unsigned SkTextBlob::ScalarsPerGlyph(GlyphPositioning pos) {
212    // GlyphPositioning values are directly mapped to scalars-per-glyph.
213    SkASSERT(pos <= 2);
214    return pos;
215}
216
217SkTextBlob::RunIterator::RunIterator(const SkTextBlob* blob)
218    : fCurrentRun(RunRecord::First(blob))
219    , fRemainingRuns(blob->fRunCount) {
220    SkDEBUGCODE(fStorageTop = (uint8_t*)blob + blob->fStorageSize;)
221}
222
223bool SkTextBlob::RunIterator::done() const {
224    return fRemainingRuns <= 0;
225}
226
227void SkTextBlob::RunIterator::next() {
228    SkASSERT(!this->done());
229
230    if (!this->done()) {
231        SkDEBUGCODE(fCurrentRun->validate(fStorageTop);)
232        fCurrentRun = RunRecord::Next(fCurrentRun);
233        fRemainingRuns--;
234    }
235}
236
237uint32_t SkTextBlob::RunIterator::glyphCount() const {
238    SkASSERT(!this->done());
239    return fCurrentRun->glyphCount();
240}
241
242const uint16_t* SkTextBlob::RunIterator::glyphs() const {
243    SkASSERT(!this->done());
244    return fCurrentRun->glyphBuffer();
245}
246
247const SkScalar* SkTextBlob::RunIterator::pos() const {
248    SkASSERT(!this->done());
249    return fCurrentRun->posBuffer();
250}
251
252const SkPoint& SkTextBlob::RunIterator::offset() const {
253    SkASSERT(!this->done());
254    return fCurrentRun->offset();
255}
256
257SkTextBlob::GlyphPositioning SkTextBlob::RunIterator::positioning() const {
258    SkASSERT(!this->done());
259    return fCurrentRun->positioning();
260}
261
262void SkTextBlob::RunIterator::applyFontToPaint(SkPaint* paint) const {
263    SkASSERT(!this->done());
264
265    const SkPaint& font = fCurrentRun->font();
266
267    paint->setTypeface(font.getTypeface());
268    paint->setTextEncoding(font.getTextEncoding());
269    paint->setTextSize(font.getTextSize());
270    paint->setTextScaleX(font.getTextScaleX());
271    paint->setTextSkewX(font.getTextSkewX());
272    paint->setHinting(font.getHinting());
273
274    uint32_t flagsMask = SkPaint::kAntiAlias_Flag
275                       | SkPaint::kUnderlineText_Flag
276                       | SkPaint::kStrikeThruText_Flag
277                       | SkPaint::kFakeBoldText_Flag
278                       | SkPaint::kLinearText_Flag
279                       | SkPaint::kSubpixelText_Flag
280                       | SkPaint::kDevKernText_Flag
281                       | SkPaint::kLCDRenderText_Flag
282                       | SkPaint::kEmbeddedBitmapText_Flag
283                       | SkPaint::kAutoHinting_Flag
284                       | SkPaint::kVerticalText_Flag
285                       | SkPaint::kGenA8FromLCD_Flag
286                       | SkPaint::kDistanceFieldTextTEMP_Flag;
287    paint->setFlags((paint->getFlags() & ~flagsMask) | (font.getFlags() & flagsMask));
288}
289
290SkTextBlobBuilder::SkTextBlobBuilder()
291    : fStorageSize(0)
292    , fStorageUsed(0)
293    , fRunCount(0)
294    , fDeferredBounds(false)
295    , fLastRun(0) {
296    fBounds.setEmpty();
297}
298
299SkTextBlobBuilder::~SkTextBlobBuilder() {
300    if (NULL != fStorage.get()) {
301        // We are abandoning runs and must destruct the associated font data.
302        // The easiest way to accomplish that is to use the blob destructor.
303        build()->unref();
304    }
305}
306
307SkRect SkTextBlobBuilder::TightRunBounds(const SkTextBlob::RunRecord& run) {
308    SkASSERT(SkTextBlob::kDefault_Positioning == run.positioning());
309
310    SkRect bounds;
311    run.font().measureText(run.glyphBuffer(), run.glyphCount() * sizeof(uint16_t), &bounds);
312
313    return bounds.makeOffset(run.offset().x(), run.offset().y());
314}
315
316SkRect SkTextBlobBuilder::ConservativeRunBounds(const SkTextBlob::RunRecord& run) {
317    SkASSERT(run.glyphCount() > 0);
318    SkASSERT(SkTextBlob::kFull_Positioning == run.positioning() ||
319             SkTextBlob::kHorizontal_Positioning == run.positioning());
320
321    // First, compute the glyph position bbox.
322    SkRect bounds;
323    switch (run.positioning()) {
324    case SkTextBlob::kHorizontal_Positioning: {
325        const SkScalar* glyphPos = run.posBuffer();
326        SkASSERT((void*)(glyphPos + run.glyphCount()) <= SkTextBlob::RunRecord::Next(&run));
327
328        SkScalar minX = *glyphPos;
329        SkScalar maxX = *glyphPos;
330        for (unsigned i = 1; i < run.glyphCount(); ++i) {
331            SkScalar x = glyphPos[i];
332            minX = SkMinScalar(x, minX);
333            maxX = SkMaxScalar(x, maxX);
334        }
335
336        bounds.setLTRB(minX, 0, maxX, 0);
337    } break;
338    case SkTextBlob::kFull_Positioning: {
339        const SkPoint* glyphPosPts = reinterpret_cast<const SkPoint*>(run.posBuffer());
340        SkASSERT((void*)(glyphPosPts + run.glyphCount()) <= SkTextBlob::RunRecord::Next(&run));
341
342        bounds.setBounds(glyphPosPts, run.glyphCount());
343    } break;
344    default:
345        SkFAIL("unsupported positioning mode");
346    }
347
348    // Expand by typeface glyph bounds.
349    const SkRect fontBounds = run.font().getFontBounds();
350    bounds.fLeft   += fontBounds.left();
351    bounds.fTop    += fontBounds.top();
352    bounds.fRight  += fontBounds.right();
353    bounds.fBottom += fontBounds.bottom();
354
355    // Offset by run position.
356    return bounds.makeOffset(run.offset().x(), run.offset().y());
357}
358
359void SkTextBlobBuilder::updateDeferredBounds() {
360    SkASSERT(!fDeferredBounds || fRunCount > 0);
361
362    if (!fDeferredBounds) {
363        return;
364    }
365
366    SkASSERT(fLastRun >= sizeof(SkTextBlob));
367    SkTextBlob::RunRecord* run = reinterpret_cast<SkTextBlob::RunRecord*>(fStorage.get() +
368                                                                          fLastRun);
369    SkASSERT(SkPaint::kGlyphID_TextEncoding == run->font().getTextEncoding());
370
371    // FIXME: we should also use conservative bounds for kDefault_Positioning.
372    SkRect runBounds = SkTextBlob::kDefault_Positioning == run->positioning() ?
373                       TightRunBounds(*run) : ConservativeRunBounds(*run);
374    fBounds.join(runBounds);
375    fDeferredBounds = false;
376}
377
378void SkTextBlobBuilder::reserve(size_t size) {
379    // We don't currently pre-allocate, but maybe someday...
380    if (fStorageUsed + size <= fStorageSize) {
381        return;
382    }
383
384    if (0 == fRunCount) {
385        SkASSERT(NULL == fStorage.get());
386        SkASSERT(0 == fStorageSize);
387        SkASSERT(0 == fStorageUsed);
388
389        // the first allocation also includes blob storage
390        fStorageUsed += sizeof(SkTextBlob);
391    }
392
393    fStorageSize = fStorageUsed + size;
394    // FYI: This relies on everything we store being relocatable, particularly SkPaint.
395    fStorage.realloc(fStorageSize);
396}
397
398bool SkTextBlobBuilder::mergeRun(const SkPaint &font, SkTextBlob::GlyphPositioning positioning,
399                                 int count, SkPoint offset) {
400    if (0 == fLastRun) {
401        SkASSERT(0 == fRunCount);
402        return false;
403    }
404
405    SkASSERT(fLastRun >= sizeof(SkTextBlob));
406    SkTextBlob::RunRecord* run = reinterpret_cast<SkTextBlob::RunRecord*>(fStorage.get() +
407                                                                          fLastRun);
408    SkASSERT(run->glyphCount() > 0);
409
410    if (run->positioning() != positioning
411        || run->font() != font
412        || (run->glyphCount() + count < run->glyphCount())) {
413        return false;
414    }
415
416    // we can merge same-font/same-positioning runs in the following cases:
417    //   * fully positioned run following another fully positioned run
418    //   * horizontally postioned run following another horizontally positioned run with the same
419    //     y-offset
420    if (SkTextBlob::kFull_Positioning != positioning
421        && (SkTextBlob::kHorizontal_Positioning != positioning
422            || run->offset().y() != offset.y())) {
423        return false;
424    }
425
426    size_t sizeDelta = SkTextBlob::RunRecord::StorageSize(run->glyphCount() + count, positioning) -
427                       SkTextBlob::RunRecord::StorageSize(run->glyphCount(), positioning);
428    this->reserve(sizeDelta);
429
430    // reserve may have realloced
431    run = reinterpret_cast<SkTextBlob::RunRecord*>(fStorage.get() + fLastRun);
432    uint32_t preMergeCount = run->glyphCount();
433    run->grow(count);
434
435    // Callers expect the buffers to point at the newly added slice, ant not at the beginning.
436    fCurrentRunBuffer.glyphs = run->glyphBuffer() + preMergeCount;
437    fCurrentRunBuffer.pos = run->posBuffer()
438                          + preMergeCount * SkTextBlob::ScalarsPerGlyph(positioning);
439
440    fStorageUsed += sizeDelta;
441
442    SkASSERT(fStorageUsed <= fStorageSize);
443    run->validate(fStorage.get() + fStorageUsed);
444
445    return true;
446}
447
448void SkTextBlobBuilder::allocInternal(const SkPaint &font,
449                                      SkTextBlob::GlyphPositioning positioning,
450                                      int count, SkPoint offset, const SkRect* bounds) {
451    SkASSERT(count > 0);
452    SkASSERT(SkPaint::kGlyphID_TextEncoding == font.getTextEncoding());
453
454    if (!this->mergeRun(font, positioning, count, offset)) {
455        this->updateDeferredBounds();
456
457        size_t runSize = SkTextBlob::RunRecord::StorageSize(count, positioning);
458        this->reserve(runSize);
459
460        SkASSERT(fStorageUsed >= sizeof(SkTextBlob));
461        SkASSERT(fStorageUsed + runSize <= fStorageSize);
462
463        SkTextBlob::RunRecord* run = new (fStorage.get() + fStorageUsed)
464                                         SkTextBlob::RunRecord(count, offset, font, positioning);
465
466        fCurrentRunBuffer.glyphs = run->glyphBuffer();
467        fCurrentRunBuffer.pos = run->posBuffer();
468
469        fLastRun = fStorageUsed;
470        fStorageUsed += runSize;
471        fRunCount++;
472
473        SkASSERT(fStorageUsed <= fStorageSize);
474        run->validate(fStorage.get() + fStorageUsed);
475    }
476
477    if (!fDeferredBounds) {
478        if (bounds) {
479            fBounds.join(*bounds);
480        } else {
481            fDeferredBounds = true;
482        }
483    }
484}
485
486const SkTextBlobBuilder::RunBuffer& SkTextBlobBuilder::allocRun(const SkPaint& font, int count,
487                                                                SkScalar x, SkScalar y,
488                                                                const SkRect* bounds) {
489    this->allocInternal(font, SkTextBlob::kDefault_Positioning, count, SkPoint::Make(x, y), bounds);
490
491    return fCurrentRunBuffer;
492}
493
494const SkTextBlobBuilder::RunBuffer& SkTextBlobBuilder::allocRunPosH(const SkPaint& font, int count,
495                                                                    SkScalar y,
496                                                                    const SkRect* bounds) {
497    this->allocInternal(font, SkTextBlob::kHorizontal_Positioning, count, SkPoint::Make(0, y),
498                        bounds);
499
500    return fCurrentRunBuffer;
501}
502
503const SkTextBlobBuilder::RunBuffer& SkTextBlobBuilder::allocRunPos(const SkPaint& font, int count,
504                                                                   const SkRect *bounds) {
505    this->allocInternal(font, SkTextBlob::kFull_Positioning, count, SkPoint::Make(0, 0), bounds);
506
507    return fCurrentRunBuffer;
508}
509
510const SkTextBlob* SkTextBlobBuilder::build() {
511    SkASSERT((fRunCount > 0) == (NULL != fStorage.get()));
512
513    this->updateDeferredBounds();
514
515    if (0 == fRunCount) {
516        SkASSERT(NULL == fStorage.get());
517        fStorageUsed = sizeof(SkTextBlob);
518        fStorage.realloc(fStorageUsed);
519    }
520
521    SkDEBUGCODE(
522        size_t validateSize = sizeof(SkTextBlob);
523        const SkTextBlob::RunRecord* run =
524            SkTextBlob::RunRecord::First(reinterpret_cast<const SkTextBlob*>(fStorage.get()));
525        for (int i = 0; i < fRunCount; ++i) {
526            validateSize += SkTextBlob::RunRecord::StorageSize(run->fCount, run->fPositioning);
527            run->validate(fStorage.get() + fStorageUsed);
528            run = SkTextBlob::RunRecord::Next(run);
529        }
530        SkASSERT(validateSize == fStorageUsed);
531    )
532
533    const SkTextBlob* blob = new (fStorage.detach()) SkTextBlob(fRunCount, fBounds);
534    SkDEBUGCODE(const_cast<SkTextBlob*>(blob)->fStorageSize = fStorageSize;)
535
536    fStorageUsed = 0;
537    fStorageSize = 0;
538    fRunCount = 0;
539    fLastRun = 0;
540    fBounds.setEmpty();
541
542    return blob;
543}
544
545