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