1178dddacb4c91a96fc0793d53b6793dc0c20200
[WebKit-https.git] / Source / WebCore / svg / SVGToOTFFontConversion.cpp
1 /*
2  * Copyright (C) 2014 Apple Inc. All rights reserved.
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  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. 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 APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "SVGToOTFFontConversion.h"
28
29 #include "CSSStyleDeclaration.h"
30 #include "ElementChildIterator.h"
31 #include "SVGFontElement.h"
32 #include "SVGFontFaceElement.h"
33 #include "SVGGlyphElement.h"
34 #include "SVGHKernElement.h"
35 #include "SVGMissingGlyphElement.h"
36 #include "SVGPathBuilder.h"
37 #include "SVGPathParser.h"
38 #include "SVGPathStringSource.h"
39 #include "SVGVKernElement.h"
40
41 namespace WebCore {
42
43 template <typename V>
44 static inline void append32(V& result, uint32_t value)
45 {
46     result.append(value >> 24);
47     result.append(value >> 16);
48     result.append(value >> 8);
49     result.append(value);
50 }
51
52 class SVGToOTFFontConverter {
53 public:
54     SVGToOTFFontConverter(const SVGFontElement&);
55     void convertSVGToOTFFont();
56
57     Vector<char> releaseResult()
58     {
59         return WTF::move(m_result);
60     }
61
62 private:
63     struct GlyphData {
64         GlyphData(Vector<char>&& charString, const SVGGlyphElement* glyphElement, float horizontalAdvance, float verticalAdvance, FloatRect boundingBox, const String& codepoints)
65             : boundingBox(boundingBox)
66             , charString(charString)
67             , codepoints(codepoints)
68             , glyphElement(glyphElement)
69             , horizontalAdvance(horizontalAdvance)
70             , verticalAdvance(verticalAdvance)
71         {
72         }
73         FloatRect boundingBox;
74         Vector<char> charString;
75         String codepoints;
76         const SVGGlyphElement* glyphElement;
77         float horizontalAdvance;
78         float verticalAdvance;
79     };
80
81     class Placeholder {
82     public:
83         Placeholder(SVGToOTFFontConverter& converter, size_t baseOfOffset)
84             : m_converter(converter)
85             , m_baseOfOffset(baseOfOffset)
86             , m_location(m_converter.m_result.size())
87         {
88             m_converter.append16(0);
89         }
90
91         Placeholder(Placeholder&& other)
92             : m_converter(other.m_converter)
93             , m_baseOfOffset(other.m_baseOfOffset)
94             , m_location(other.m_location)
95 #if !ASSERT_DISABLED
96             , m_active(other.m_active)
97 #endif
98         {
99 #if !ASSERT_DISABLED
100             other.m_active = false;
101 #endif
102         }
103
104         void populate()
105         {
106             ASSERT(m_active);
107             size_t delta = m_converter.m_result.size() - m_baseOfOffset;
108             ASSERT(delta < std::numeric_limits<uint16_t>::max());
109             m_converter.overwrite16(m_location, delta);
110 #if !ASSERT_DISABLED
111             m_active = false;
112 #endif
113         }
114
115         ~Placeholder()
116         {
117             ASSERT(!m_active);
118         }
119
120     private:
121         SVGToOTFFontConverter& m_converter;
122         const size_t m_baseOfOffset;
123         const size_t m_location;
124 #if !ASSERT_DISABLED
125         bool m_active = { true };
126 #endif
127     };
128
129     struct KerningData {
130         KerningData(uint16_t glyph1, uint16_t glyph2, int16_t adjustment)
131             : glyph1(glyph1)
132             , glyph2(glyph2)
133             , adjustment(adjustment)
134         {
135         }
136         uint16_t glyph1;
137         uint16_t glyph2;
138         int16_t adjustment;
139     };
140
141     Placeholder placeholder(size_t baseOfOffset)
142     {
143         return Placeholder(*this, baseOfOffset);
144     }
145
146     void append32(uint32_t value)
147     {
148         WebCore::append32(m_result, value);
149     }
150
151     void append32BitCode(const char code[4])
152     {
153         m_result.append(code[0]);
154         m_result.append(code[1]);
155         m_result.append(code[2]);
156         m_result.append(code[3]);
157     }
158
159     void append16(uint16_t value)
160     {
161         m_result.append(value >> 8);
162         m_result.append(value);
163     }
164
165     void grow(size_t delta)
166     {
167         m_result.grow(m_result.size() + delta);
168     }
169
170     void overwrite32(unsigned location, uint32_t value)
171     {
172         ASSERT(m_result.size() >= location + 4);
173         m_result[location] = value >> 24;
174         m_result[location + 1] = value >> 16;
175         m_result[location + 2] = value >> 8;
176         m_result[location + 3] = value;
177     }
178
179     void overwrite16(unsigned location, uint16_t value)
180     {
181         ASSERT(m_result.size() >= location + 2);
182         m_result[location] = value >> 8;
183         m_result[location + 1] = value;
184     }
185
186     static const size_t headerSize = 12;
187     static const size_t directoryEntrySize = 16;
188
189     uint32_t calculateChecksum(size_t startingOffset, size_t endingOffset) const;
190
191     void processGlyphElement(const SVGElement& glyphOrMissingGlyphElement, const SVGGlyphElement*, float defaultHorizontalAdvance, float defaultVerticalAdvance, const String& codepoints, bool& initialGlyph);
192
193     typedef void (SVGToOTFFontConverter::*FontAppendingFunction)();
194     void appendTable(const char identifier[4], FontAppendingFunction);
195     void appendCMAPTable();
196     void appendGSUBTable();
197     void appendHEADTable();
198     void appendHHEATable();
199     void appendHMTXTable();
200     void appendVHEATable();
201     void appendVMTXTable();
202     void appendKERNTable();
203     void appendMAXPTable();
204     void appendNAMETable();
205     void appendOS2Table();
206     void appendPOSTTable();
207     void appendCFFTable();
208     void appendVORGTable();
209
210     void appendLigatureGlyphs();
211     static bool compareCodepointsLexicographically(const GlyphData&, const GlyphData&);
212
213     void appendValidCFFString(const String&);
214
215     Vector<char> transcodeGlyphPaths(float width, const SVGElement& glyphOrMissingGlyphElement, FloatRect& boundingBox) const;
216
217     void addCodepointRanges(const UnicodeRanges&, HashSet<Glyph>& glyphSet) const;
218     void addCodepoints(const HashSet<String>& codepoints, HashSet<Glyph>& glyphSet) const;
219     void addGlyphNames(const HashSet<String>& glyphNames, HashSet<Glyph>& glyphSet) const;
220     void addKerningPair(Vector<KerningData>&, const SVGKerningPair&) const;
221     template<typename T> size_t appendKERNSubtable(bool (T::*buildKerningPair)(SVGKerningPair&) const, uint16_t coverage);
222     size_t finishAppendingKERNSubtable(Vector<KerningData>, uint16_t coverage);
223
224     void appendLigatureSubtable(size_t subtableRecordLocation);
225     void appendArabicReplacementSubtable(size_t subtableRecordLocation, const char arabicForm[]);
226     void appendScriptSubtable(unsigned featureCount);
227     Vector<Glyph, 1> glyphsForCodepoint(UChar32) const;
228     Glyph firstGlyph(const Vector<Glyph, 1>&, UChar32) const;
229
230     Vector<GlyphData> m_glyphs;
231     HashMap<String, Glyph> m_glyphNameToIndexMap; // SVG 1.1: "It is recommended that glyph names be unique within a font."
232     HashMap<String, Vector<Glyph, 1>> m_codepointsToIndicesMap;
233     Vector<char> m_result;
234     Vector<char, 17> m_emptyGlyphCharString;
235     FloatRect m_boundingBox;
236     const SVGFontElement& m_fontElement;
237     const SVGFontFaceElement* m_fontFaceElement;
238     const SVGMissingGlyphElement* m_missingGlyphElement;
239     String m_fontFamily;
240     float m_advanceWidthMax;
241     float m_advanceHeightMax;
242     float m_minRightSideBearing;
243     unsigned m_unitsPerEm;
244     unsigned m_featureCountGSUB;
245     int m_tablesAppendedCount;
246     char m_weight;
247     bool m_italic;
248 };
249
250 static uint16_t roundDownToPowerOfTwo(uint16_t x)
251 {
252     x |= x >> 1;
253     x |= x >> 2;
254     x |= x >> 4;
255     x |= x >> 8;
256     return (x >> 1) + 1;
257 }
258
259 static uint16_t integralLog2(uint16_t x)
260 {
261     uint16_t result = 0;
262     while (x >>= 1)
263         ++result;
264     return result;
265 }
266
267 void SVGToOTFFontConverter::appendCMAPTable()
268 {
269     auto startingOffset = m_result.size();
270     append16(0);
271     append16(1); // Number subtables
272
273     append16(0); // Unicode
274     append16(3); // Unicode version 2.2+
275     append32(m_result.size() - startingOffset + sizeof(uint32_t)); // Byte offset of subtable
276
277     // Braindead scheme: One segment for each character
278     ASSERT(m_glyphs.size() < 0xFFFF);
279     auto subtableLocation = m_result.size();
280     append32(12 << 16); // Format 12
281     append32(0); // Placeholder for byte length
282     append32(0); // Language independent
283     append32(0); // Placeholder for nGroups
284
285     uint16_t nGroups = 0;
286     UChar32 previousCodepoint = std::numeric_limits<UChar32>::max();
287     for (size_t i = 0; i < m_glyphs.size(); ++i) {
288         auto& glyph = m_glyphs[i];
289         UChar32 codepoint;
290         auto codePoints = StringView(glyph.codepoints).codePoints();
291         auto iterator = codePoints.begin();
292         if (iterator == codePoints.end())
293             codepoint = 0;
294         else {
295             codepoint = *iterator;
296             ++iterator;
297             // Don't map ligatures here.
298             if (iterator != codePoints.end() || codepoint == previousCodepoint)
299                 continue;
300         }
301
302         append32(codepoint); // startCharCode
303         append32(codepoint); // endCharCode
304         append32(i); // startGlyphCode
305         ++nGroups;
306         previousCodepoint = codepoint;
307     }
308     overwrite32(subtableLocation + 4, m_result.size() - subtableLocation);
309     overwrite32(subtableLocation + 12, nGroups);
310 }
311
312 void SVGToOTFFontConverter::appendHEADTable()
313 {
314     append32(0x00010000); // Version
315     append32(0x00010000); // Revision
316     append32(0); // Checksum placeholder; to be overwritten by the caller.
317     append32(0x5F0F3CF5); // Magic number.
318     append16((1 << 9) | 1);
319
320     append16(m_unitsPerEm);
321     append32(0); // First half of creation date
322     append32(0); // Last half of creation date
323     append32(0); // First half of modification date
324     append32(0); // Last half of modification date
325     append16(m_boundingBox.x()); // Minimum X
326     append16(m_boundingBox.y()); // Minimum Y
327     append16(m_boundingBox.maxX()); // Maximum X
328     append16(m_boundingBox.maxY()); // Maximum Y
329     append16((m_italic ? 1 << 1 : 0) | (m_weight >= 7 ? 1 : 0));
330     append16(3); // Smallest readable size in pixels
331     append16(0); // Might contain LTR or RTL glyphs
332     append16(0); // Short offsets in the 'loca' table. However, OTF fonts don't have a 'loca' table so this is irrelevant
333     append16(0); // Glyph data format
334 }
335
336 // Assumption: T2 can hold every value that a T1 can hold.
337 template<typename T1, typename T2> static inline T1 clampTo(T2 x)
338 {
339     x = std::min(x, static_cast<T2>(std::numeric_limits<T1>::max()));
340     x = std::max(x, static_cast<T2>(std::numeric_limits<T1>::min()));
341     return static_cast<T1>(x);
342 }
343
344 void SVGToOTFFontConverter::appendHHEATable()
345 {
346     int16_t ascent;
347     int16_t descent;
348     if (!m_fontFaceElement) {
349         ascent = m_unitsPerEm;
350         descent = 1;
351     } else {
352         ascent = m_fontFaceElement->ascent();
353         descent = m_fontFaceElement->descent();
354
355         // Some platforms, including OS X, use 0 ascent and descent to mean that the platform should synthesize
356         // a value based on a heuristic. However, SVG fonts can legitimately have 0 for ascent or descent.
357         // Specifing a single FUnit gets us as close to 0 as we can without triggering the synthesis.
358         if (!ascent)
359             ascent = 1;
360         if (!descent)
361             descent = 1;
362     }
363
364     append32(0x00010000); // Version
365     append16(ascent);
366     append16(descent);
367     // WebKit SVG font rendering has hard coded the line gap to be 1/10th of the font size since 2008 (see r29719).
368     append16(m_unitsPerEm / 10); // Line gap
369     append16(clampTo<uint16_t>(m_advanceWidthMax));
370     append16(clampTo<int16_t>(m_boundingBox.x())); // Minimum left side bearing
371     append16(clampTo<int16_t>(m_minRightSideBearing)); // Minimum right side bearing
372     append16(clampTo<int16_t>(m_boundingBox.maxX())); // X maximum extent
373     // Since WebKit draws the caret and ignores the following values, it doesn't matter what we set them to.
374     append16(1); // Vertical caret
375     append16(0); // Vertical caret
376     append16(0); // "Set value to 0 for non-slanted fonts"
377     append32(0); // Reserved
378     append32(0); // Reserved
379     append16(0); // Current format
380     append16(m_glyphs.size()); // Number of advance widths in HMTX table
381 }
382
383 void SVGToOTFFontConverter::appendHMTXTable()
384 {
385     for (auto& glyph : m_glyphs) {
386         append16(clampTo<uint16_t>(glyph.horizontalAdvance));
387         append16(clampTo<int16_t>(glyph.boundingBox.x()));
388     }
389 }
390
391 void SVGToOTFFontConverter::appendMAXPTable()
392 {
393     append32(0x00010000); // Version
394     append16(m_glyphs.size());
395     append16(0xFFFF); // Maximum number of points in non-compound glyph
396     append16(0xFFFF); // Maximum number of contours in non-compound glyph
397     append16(0xFFFF); // Maximum number of points in compound glyph
398     append16(0xFFFF); // Maximum number of contours in compound glyph
399     append16(2); // Maximum number of zones
400     append16(0); // Maximum number of points used in zone 0
401     append16(0); // Maximum number of storage area locations
402     append16(0); // Maximum number of function definitions
403     append16(0); // Maximum number of instruction definitions
404     append16(0); // Maximum stack depth
405     append16(0); // Maximum size of instructions
406     append16(m_glyphs.size()); // Maximum number of glyphs referenced at top level
407     append16(0); // No compound glyphs
408 }
409
410 void SVGToOTFFontConverter::appendNAMETable()
411 {
412     append16(0); // Format selector
413     append16(1); // Number of name records in table
414     append16(18); // Offset in bytes to the beginning of name character strings
415
416     append16(0); // Unicode
417     append16(3); // Unicode version 2.0 or later
418     append16(0); // Language
419     append16(1); // Name identifier. 1 = Font family
420     append16(m_fontFamily.length());
421     append16(0); // Offset into name data
422
423     for (auto codeUnit : StringView(m_fontFamily).codeUnits())
424         append16(codeUnit);
425 }
426
427 void SVGToOTFFontConverter::appendOS2Table()
428 {
429     int16_t averageAdvance = m_unitsPerEm;
430     bool ok;
431     int value = m_fontElement.fastGetAttribute(SVGNames::horiz_adv_xAttr).toInt(&ok);
432     if (!ok && m_missingGlyphElement)
433         value = m_missingGlyphElement->fastGetAttribute(SVGNames::horiz_adv_xAttr).toInt(&ok);
434     if (ok)
435         averageAdvance = clampTo<int16_t>(value);
436
437     append16(0); // Version
438     append16(averageAdvance);
439     append16(m_weight); // Weight class
440     append16(5); // Width class
441     append16(0); // Protected font
442     // WebKit handles these superscripts and subscripts
443     append16(0); // Subscript X Size
444     append16(0); // Subscript Y Size
445     append16(0); // Subscript X Offset
446     append16(0); // Subscript Y Offset
447     append16(0); // Superscript X Size
448     append16(0); // Superscript Y Size
449     append16(0); // Superscript X Offset
450     append16(0); // Superscript Y Offset
451     append16(0); // Strikeout width
452     append16(0); // Strikeout Position
453     append16(0); // No classification
454
455     unsigned numPanoseBytes = 0;
456     const unsigned panoseSize = 10;
457     char panoseBytes[panoseSize];
458     if (m_fontFaceElement) {
459         Vector<String> segments;
460         m_fontFaceElement->fastGetAttribute(SVGNames::panose_1Attr).string().split(' ', segments);
461         if (segments.size() == panoseSize) {
462             for (auto& segment : segments) {
463                 bool ok;
464                 int value = segment.toInt(&ok);
465                 if (ok && value >= 0 && value <= 0xFF)
466                     panoseBytes[numPanoseBytes++] = value;
467             }
468         }
469     }
470     if (numPanoseBytes != panoseSize)
471         memset(panoseBytes, 0, panoseSize);
472     m_result.append(panoseBytes, panoseSize);
473
474     for (int i = 0; i < 4; ++i)
475         append32(0); // "Bit assignments are pending. Set to 0"
476     append32(0x544B4257); // Font Vendor. "WBKT"
477     append16((m_weight >= 7 ? 1 << 5 : 0) | (m_italic ? 1 : 0)); // Font Patterns.
478     append16(0); // First unicode index
479     append16(0xFFFF); // Last unicode index
480 }
481
482 void SVGToOTFFontConverter::appendPOSTTable()
483 {
484     append32(0x00030000); // Format. Printing is undefined
485     append32(0); // Italic angle in degrees
486     append16(0); // Underline position
487     append16(0); // Underline thickness
488     append32(0); // Monospaced
489     append32(0); // "Minimum memory usage when a TrueType font is downloaded as a Type 42 font"
490     append32(0); // "Maximum memory usage when a TrueType font is downloaded as a Type 42 font"
491     append32(0); // "Minimum memory usage when a TrueType font is downloaded as a Type 1 font"
492     append32(0); // "Maximum memory usage when a TrueType font is downloaded as a Type 1 font"
493 }
494
495 static bool isValidStringForCFF(const String& string)
496 {
497     for (auto c : StringView(string).codeUnits()) {
498         if (c < 33 || c > 126)
499             return false;
500     }
501     return true;
502 }
503
504 void SVGToOTFFontConverter::appendValidCFFString(const String& string)
505 {
506     ASSERT(isValidStringForCFF(string));
507     for (auto c : StringView(string).codeUnits())
508         m_result.append(c);
509 }
510
511 void SVGToOTFFontConverter::appendCFFTable()
512 {
513     auto startingOffset = m_result.size();
514
515     // Header
516     m_result.append(1); // Major version
517     m_result.append(0); // Minor version
518     m_result.append(4); // Header size
519     m_result.append(4); // Offsets within CFF table are 4 bytes long
520
521     // Name INDEX
522     String fontName;
523     if (m_fontFaceElement) {
524         // FIXME: fontFamily() here might not be quite what we want.
525         String potentialFontName = m_fontFamily;
526         if (isValidStringForCFF(potentialFontName))
527             fontName = potentialFontName;
528     }
529     append16(1); // INDEX contains 1 element
530     m_result.append(4); // Offsets in this INDEX are 4 bytes long
531     append32(1); // 1-index offset of name data
532     append32(fontName.length() + 1); // 1-index offset just past end of name data
533     appendValidCFFString(fontName);
534
535     String weight;
536     if (m_fontFaceElement) {
537         auto& potentialWeight = m_fontFaceElement->fastGetAttribute(SVGNames::font_weightAttr);
538         if (isValidStringForCFF(potentialWeight))
539             weight = potentialWeight;
540     }
541
542     bool hasWeight = !weight.isNull();
543
544     const char operand32Bit = 29;
545     const char fullNameKey = 2;
546     const char familyNameKey = 3;
547     const char weightKey = 4;
548     const char fontBBoxKey = 5;
549     const char charsetIndexKey = 15;
550     const char charstringsIndexKey = 17;
551     const uint32_t userDefinedStringStartIndex = 391;
552     const unsigned sizeOfTopIndex = 45 + (hasWeight ? 6 : 0);
553
554     // Top DICT INDEX.
555     append16(1); // INDEX contains 1 element
556     m_result.append(4); // Offsets in this INDEX are 4 bytes long
557     append32(1); // 1-index offset of DICT data
558     append32(1 + sizeOfTopIndex); // 1-index offset just past end of DICT data
559
560     // DICT information
561 #if !ASSERT_DISABLED
562     unsigned topDictStart = m_result.size();
563 #endif
564     m_result.append(operand32Bit);
565     append32(userDefinedStringStartIndex);
566     m_result.append(fullNameKey);
567     m_result.append(operand32Bit);
568     append32(userDefinedStringStartIndex);
569     m_result.append(familyNameKey);
570     if (hasWeight) {
571         m_result.append(operand32Bit);
572         append32(userDefinedStringStartIndex + 1);
573         m_result.append(weightKey);
574     }
575     m_result.append(operand32Bit);
576     append32(clampTo<int32_t>(m_boundingBox.x()));
577     m_result.append(operand32Bit);
578     append32(clampTo<int32_t>(m_boundingBox.maxX()));
579     m_result.append(operand32Bit);
580     append32(clampTo<int32_t>(m_boundingBox.y()));
581     m_result.append(operand32Bit);
582     append32(clampTo<int32_t>(m_boundingBox.maxY()));
583     m_result.append(fontBBoxKey);
584     m_result.append(operand32Bit);
585     unsigned charsetOffsetLocation = m_result.size();
586     append32(0); // Offset of Charset info. Will be overwritten later.
587     m_result.append(charsetIndexKey);
588     m_result.append(operand32Bit);
589     unsigned charstringsOffsetLocation = m_result.size();
590     append32(0); // Offset of CharStrings INDEX. Will be overwritten later.
591     m_result.append(charstringsIndexKey);
592     ASSERT(m_result.size() == topDictStart + sizeOfTopIndex);
593
594     // String INDEX
595     append16(1 + (hasWeight ? 1 : 0)); // Number of elements in INDEX
596     m_result.append(4); // Offsets in this INDEX are 4 bytes long
597     uint32_t offset = 1;
598     append32(offset);
599     offset += fontName.length();
600     append32(offset);
601     if (hasWeight) {
602         offset += weight.length();
603         append32(offset);
604     }
605     appendValidCFFString(fontName);
606     appendValidCFFString(weight);
607
608     append16(0); // Empty subroutine INDEX
609
610     // Charset info
611     overwrite32(charsetOffsetLocation, m_result.size() - startingOffset);
612     m_result.append(0);
613     for (Glyph i = 1; i < m_glyphs.size(); ++i)
614         append16(i);
615
616     // CharStrings INDEX
617     overwrite32(charstringsOffsetLocation, m_result.size() - startingOffset);
618     append16(m_glyphs.size());
619     m_result.append(4); // Offsets in this INDEX are 4 bytes long
620     offset = 1;
621     append32(offset);
622     for (auto& glyph : m_glyphs) {
623         offset += glyph.charString.size();
624         append32(offset);
625     }
626     for (auto& glyph : m_glyphs)
627         m_result.appendVector(glyph.charString);
628 }
629
630 Glyph SVGToOTFFontConverter::firstGlyph(const Vector<Glyph, 1>& v, UChar32 codepoint) const
631 {
632 #if ASSERT_DISABLED
633     UNUSED_PARAM(codepoint);
634 #endif
635     ASSERT(!v.isEmpty());
636     if (v.isEmpty())
637         return 0;
638 #if !ASSERT_DISABLED
639     auto codePoints = StringView(m_glyphs[v[0]].codepoints).codePoints();
640     auto codePointsIterator = codePoints.begin();
641     ASSERT(codePointsIterator != codePoints.end());
642     ASSERT(codepoint = *codePointsIterator);
643 #endif
644     return v[0];
645 }
646
647 void SVGToOTFFontConverter::appendLigatureSubtable(size_t subtableRecordLocation)
648 {
649     typedef std::pair<Vector<Glyph, 3>, Glyph> LigaturePair;
650     Vector<LigaturePair> ligaturePairs;
651     for (Glyph glyphIndex = 0; glyphIndex < m_glyphs.size(); ++glyphIndex) {
652         ligaturePairs.append(LigaturePair(Vector<Glyph, 3>(), glyphIndex));
653         Vector<Glyph, 3>& ligatureGlyphs = ligaturePairs.last().first;
654         auto codePoints = StringView(m_glyphs[glyphIndex].codepoints).codePoints();
655         // FIXME: https://bugs.webkit.org/show_bug.cgi?id=138592 This needs to be done in codepoint space, not glyph space
656         for (auto codePoint : codePoints)
657             ligatureGlyphs.append(firstGlyph(glyphsForCodepoint(codePoint), codePoint));
658         if (ligatureGlyphs.size() < 2)
659             ligaturePairs.removeLast();
660     }
661     if (ligaturePairs.size() > std::numeric_limits<uint16_t>::max())
662         ligaturePairs.clear();
663     std::sort(ligaturePairs.begin(), ligaturePairs.end(), [](LigaturePair& lhs, LigaturePair& rhs) {
664         return lhs.first[0] < rhs.first[0];
665     });
666     Vector<size_t> overlappingFirstGlyphSegmentLengths;
667     if (!ligaturePairs.isEmpty()) {
668         Glyph previousFirstGlyph = ligaturePairs[0].first[0];
669         size_t segmentStart = 0;
670         for (size_t i = 0; i < ligaturePairs.size(); ++i) {
671             auto& ligaturePair = ligaturePairs[i];
672             if (ligaturePair.first[0] != previousFirstGlyph) {
673                 overlappingFirstGlyphSegmentLengths.append(i - segmentStart);
674                 segmentStart = i;
675                 previousFirstGlyph = ligaturePairs[0].first[0];
676             }
677         }
678         overlappingFirstGlyphSegmentLengths.append(ligaturePairs.size() - segmentStart);
679     }
680
681     overwrite16(subtableRecordLocation + 6, m_result.size() - subtableRecordLocation);
682     auto subtableLocation = m_result.size();
683     append16(1); // Format 1
684     append16(0); // Placeholder for offset to coverage table, relative to beginning of substitution table
685     append16(ligaturePairs.size()); // Number of LigatureSet tables
686     grow(overlappingFirstGlyphSegmentLengths.size() * 2); // Placeholder for offset to LigatureSet table
687
688     Vector<size_t> ligatureSetTableLocations;
689     for (size_t i = 0; i < overlappingFirstGlyphSegmentLengths.size(); ++i) {
690         overwrite16(subtableLocation + 6 + 2 * i, m_result.size() - subtableLocation);
691         ligatureSetTableLocations.append(m_result.size());
692         append16(overlappingFirstGlyphSegmentLengths[i]); // LigatureCount
693         grow(overlappingFirstGlyphSegmentLengths[i] * 2); // Placeholder for offset to Ligature table
694     }
695     ASSERT(ligatureSetTableLocations.size() == overlappingFirstGlyphSegmentLengths.size());
696
697     size_t ligaturePairIndex = 0;
698     for (size_t i = 0; i < overlappingFirstGlyphSegmentLengths.size(); ++i) {
699         for (size_t j = 0; j < overlappingFirstGlyphSegmentLengths[i]; ++j) {
700             overwrite16(ligatureSetTableLocations[i] + 2 + 2 * j, m_result.size() - ligatureSetTableLocations[i]);
701             auto& ligaturePair = ligaturePairs[ligaturePairIndex];
702             append16(ligaturePair.second);
703             append16(ligaturePair.first.size());
704             for (size_t k = 1; k < ligaturePair.first.size(); ++k)
705                 append16(ligaturePair.first[k]);
706             ++ligaturePairIndex;
707         }
708     }
709     ASSERT(ligaturePairIndex == ligaturePairs.size());
710
711     // Coverage table
712     overwrite16(subtableLocation + 2, m_result.size() - subtableLocation);
713     append16(1); // CoverageFormat
714     append16(ligatureSetTableLocations.size()); // GlyphCount
715     ligaturePairIndex = 0;
716     for (auto segmentLength : overlappingFirstGlyphSegmentLengths) {
717         auto& ligaturePair = ligaturePairs[ligaturePairIndex];
718         ASSERT(ligaturePair.first.size() > 1);
719         append16(ligaturePair.first[0]);
720         ligaturePairIndex += segmentLength;
721     }
722 }
723
724 void SVGToOTFFontConverter::appendArabicReplacementSubtable(size_t subtableRecordLocation, const char arabicForm[])
725 {
726     Vector<std::pair<Glyph, Glyph>> arabicFinalReplacements;
727     for (auto& pair : m_codepointsToIndicesMap) {
728         for (auto glyphIndex : pair.value) {
729             auto& glyph = m_glyphs[glyphIndex];
730             if (glyph.glyphElement && equalIgnoringCase(glyph.glyphElement->fastGetAttribute(SVGNames::arabic_formAttr), arabicForm))
731                 arabicFinalReplacements.append(std::make_pair(pair.value[0], glyphIndex));
732         }
733     }
734     if (arabicFinalReplacements.size() > std::numeric_limits<uint16_t>::max())
735         arabicFinalReplacements.clear();
736
737     overwrite16(subtableRecordLocation + 6, m_result.size() - subtableRecordLocation);
738     auto subtableLocation = m_result.size();
739     append16(2); // Format 2
740     Placeholder toCoverageTable = placeholder(subtableLocation);
741     append16(arabicFinalReplacements.size()); // GlyphCount
742     for (auto& pair : arabicFinalReplacements)
743         append16(pair.second);
744
745     toCoverageTable.populate();
746     append16(1); // CoverageFormat
747     append16(arabicFinalReplacements.size()); // GlyphCount
748     for (auto& pair : arabicFinalReplacements)
749         append16(pair.first);
750 }
751
752 void SVGToOTFFontConverter::appendScriptSubtable(unsigned featureCount)
753 {
754     auto dfltScriptTableLocation = m_result.size();
755     append16(0); // Placeholder for offset of default language system table, relative to beginning of Script table
756     append16(0); // Number of following language system tables
757
758     // LangSys table
759     overwrite16(dfltScriptTableLocation, m_result.size() - dfltScriptTableLocation);
760     append16(0); // LookupOrder "= NULL ... reserved"
761     append16(0xFFFF); // No features are required
762     append16(featureCount); // Number of FeatureIndex values
763     for (uint16_t i = 0; i < featureCount; ++i)
764         append16(m_featureCountGSUB++); // Features indices
765 }
766
767 void SVGToOTFFontConverter::appendGSUBTable()
768 {
769     auto tableLocation = m_result.size();
770     auto headerSize = 10;
771
772     append32(0x00010000); // Version
773     append16(headerSize); // Offset to ScriptList
774     Placeholder toFeatureList = placeholder(tableLocation);
775     Placeholder toLookupList = placeholder(tableLocation);
776     ASSERT(tableLocation + headerSize == m_result.size());
777
778     // ScriptList
779     auto scriptListLocation = m_result.size();
780     append16(2); // Number of ScriptRecords
781     append32BitCode("DFLT");
782     append16(0); // Placeholder for offset of Script table, relative to beginning of ScriptList
783     append32BitCode("arab");
784     append16(0); // Placeholder for offset of Script table, relative to beginning of ScriptList
785
786     overwrite16(scriptListLocation + 6, m_result.size() - scriptListLocation);
787     appendScriptSubtable(1);
788     overwrite16(scriptListLocation + 12, m_result.size() - scriptListLocation);
789     appendScriptSubtable(4);
790
791     unsigned featureCount = 5;
792
793     // FeatureList
794     toFeatureList.populate();
795     auto featureListLocation = m_result.size();
796     size_t featureListSize = 2 + 6 * featureCount;
797     size_t featureTableSize = 6;
798     append16(featureCount); // FeatureCount
799     append32BitCode("liga");
800     append16(featureListSize + featureTableSize * 0); // Offset of feature table, relative to beginning of FeatureList table
801     append32BitCode("fina");
802     append16(featureListSize + featureTableSize * 1); // Offset of feature table, relative to beginning of FeatureList table
803     append32BitCode("medi");
804     append16(featureListSize + featureTableSize * 2); // Offset of feature table, relative to beginning of FeatureList table
805     append32BitCode("init");
806     append16(featureListSize + featureTableSize * 3); // Offset of feature table, relative to beginning of FeatureList table
807     append32BitCode("rlig");
808     append16(featureListSize + featureTableSize * 4); // Offset of feature table, relative to beginning of FeatureList table
809     ASSERT_UNUSED(featureListLocation, featureListLocation + featureListSize == m_result.size());
810
811     for (unsigned i = 0; i < featureCount; ++i) {
812         auto featureTableStart = m_result.size();
813         append16(0); // FeatureParams "= NULL ... reserved"
814         append16(1); // LookupCount
815         append16(i); // LookupListIndex
816         ASSERT_UNUSED(featureTableStart, featureTableStart + featureTableSize == m_result.size());
817     }
818
819     // LookupList
820     toLookupList.populate();
821     auto lookupListLocation = m_result.size();
822     append16(featureCount); // LookupCount
823     for (unsigned i = 0; i < featureCount; ++i)
824         append16(0); // Placeholder for offset to feature table, relative to beginning of LookupList
825     size_t subtableRecordLocations[featureCount];
826     for (unsigned i = 0; i < featureCount; ++i) {
827         subtableRecordLocations[i] = m_result.size();
828         overwrite16(lookupListLocation + 2 + 2 * i, m_result.size() - lookupListLocation);
829         switch (i) {
830         case 4:
831             append16(3); // Type 3: "Replace one glyph with one of many glyphs"
832             break;
833         case 0:
834             append16(4); // Type 4: "Replace multiple glyphs with one glyph"
835             break;
836         default:
837             append16(1); // Type 1: "Replace one glyph with one glyph"
838             break;
839         }
840         append16(0); // LookupFlag
841         append16(1); // SubTableCount
842         append16(0); // Placeholder for offset to subtable, relative to beginning of Lookup table
843     }
844
845     appendLigatureSubtable(subtableRecordLocations[0]);
846     appendArabicReplacementSubtable(subtableRecordLocations[1], "terminal");
847     appendArabicReplacementSubtable(subtableRecordLocations[2], "medial");
848     appendArabicReplacementSubtable(subtableRecordLocations[3], "initial");
849
850     // Manually append empty "rlig" subtable
851     overwrite16(subtableRecordLocations[4] + 6, m_result.size() - subtableRecordLocations[4]);
852     append16(1); // Format 1
853     append16(6); // offset to coverage table, relative to beginning of substitution table
854     append16(0); // AlternateSetCount
855     append16(1); // CoverageFormat
856     append16(0); // GlyphCount
857 }
858
859 void SVGToOTFFontConverter::appendVORGTable()
860 {
861     append16(1); // Major version
862     append16(0); // Minor version
863
864     bool ok;
865     int16_t defaultVerticalOriginY = clampTo<int16_t>(m_fontElement.fastGetAttribute(SVGNames::vert_origin_yAttr).toInt(&ok));
866     if (!ok && m_missingGlyphElement)
867         defaultVerticalOriginY = clampTo<int16_t>(m_missingGlyphElement->fastGetAttribute(SVGNames::vert_origin_yAttr).toInt());
868     append16(defaultVerticalOriginY);
869
870     auto tableSizeOffset = m_result.size();
871     append16(0); // Place to write table size.
872     for (Glyph i = 0; i < m_glyphs.size(); ++i) {
873         if (auto* glyph = m_glyphs[i].glyphElement) {
874             if (int16_t verticalOriginY = clampTo<int16_t>(glyph->fastGetAttribute(SVGNames::vert_origin_yAttr).toInt())) {
875                 append16(i);
876                 append16(verticalOriginY);
877             }
878         }
879     }
880     ASSERT(!((m_result.size() - tableSizeOffset - 2) % 4));
881     overwrite16(tableSizeOffset, (m_result.size() - tableSizeOffset - 2) / 4);
882 }
883
884 void SVGToOTFFontConverter::appendVHEATable()
885 {
886     append32(0x00011000); // Version
887     append16(m_unitsPerEm / 2); // Vertical typographic ascender (vertical baseline to the right)
888     append16(clampTo<int16_t>(-static_cast<int>(m_unitsPerEm / 2))); // Vertical typographic descender
889     append16(m_unitsPerEm / 10); // Vertical typographic line gap
890     append16(clampTo<int16_t>(m_advanceHeightMax));
891     append16(clampTo<int16_t>(m_unitsPerEm - m_boundingBox.maxY())); // Minimum top side bearing
892     append16(clampTo<int16_t>(m_boundingBox.y())); // Minimum bottom side bearing
893     append16(clampTo<int16_t>(m_unitsPerEm - m_boundingBox.y())); // Y maximum extent
894     // Since WebKit draws the caret and ignores the following values, it doesn't matter what we set them to.
895     append16(1); // Vertical caret
896     append16(0); // Vertical caret
897     append16(0); // "Set value to 0 for non-slanted fonts"
898     append32(0); // Reserved
899     append32(0); // Reserved
900     append16(0); // "Set to 0"
901     append16(m_glyphs.size()); // Number of advance heights in VMTX table
902 }
903
904 void SVGToOTFFontConverter::appendVMTXTable()
905 {
906     for (auto& glyph : m_glyphs) {
907         append16(clampTo<uint16_t>(glyph.verticalAdvance));
908         append16(clampTo<int16_t>(m_unitsPerEm - glyph.boundingBox.maxY())); // top side bearing
909     }
910 }
911
912 static String codepointToString(UChar32 codepoint)
913 {
914     UChar buffer[2];
915     uint8_t length = 0;
916     UBool error = false;
917     U16_APPEND(buffer, length, 2, codepoint, error);
918     return error ? String() : String(buffer, length);
919 }
920
921 Vector<Glyph, 1> SVGToOTFFontConverter::glyphsForCodepoint(UChar32 codepoint) const
922 {
923     return m_codepointsToIndicesMap.get(codepointToString(codepoint));
924 }
925
926 void SVGToOTFFontConverter::addCodepointRanges(const UnicodeRanges& unicodeRanges, HashSet<Glyph>& glyphSet) const
927 {
928     for (auto& unicodeRange : unicodeRanges) {
929         for (auto codepoint = unicodeRange.first; codepoint <= unicodeRange.second; ++codepoint) {
930             for (auto index : glyphsForCodepoint(codepoint))
931                 glyphSet.add(index);
932         }
933     }
934 }
935
936 void SVGToOTFFontConverter::addCodepoints(const HashSet<String>& codepoints, HashSet<Glyph>& glyphSet) const
937 {
938     for (auto& codepointString : codepoints) {
939         for (auto index : m_codepointsToIndicesMap.get(codepointString))
940             glyphSet.add(index);
941     }
942 }
943
944 void SVGToOTFFontConverter::addGlyphNames(const HashSet<String>& glyphNames, HashSet<Glyph>& glyphSet) const
945 {
946     for (auto& glyphName : glyphNames) {
947         if (Glyph glyph = m_glyphNameToIndexMap.get(glyphName))
948             glyphSet.add(glyph);
949     }
950 }
951
952 void SVGToOTFFontConverter::addKerningPair(Vector<KerningData>& data, const SVGKerningPair& kerningPair) const
953 {
954     HashSet<Glyph> glyphSet1;
955     HashSet<Glyph> glyphSet2;
956
957     addCodepointRanges(kerningPair.unicodeRange1, glyphSet1);
958     addCodepointRanges(kerningPair.unicodeRange2, glyphSet2);
959     addGlyphNames(kerningPair.glyphName1, glyphSet1);
960     addGlyphNames(kerningPair.glyphName2, glyphSet2);
961     addCodepoints(kerningPair.unicodeName1, glyphSet1);
962     addCodepoints(kerningPair.unicodeName2, glyphSet2);
963
964     // FIXME: Use table format 2 so we don't have to append each of these one by one.
965     for (auto& glyph1 : glyphSet1) {
966         for (auto& glyph2 : glyphSet2)
967             data.append(KerningData(glyph1, glyph2, clampTo<int16_t>(-kerningPair.kerning)));
968     }
969 }
970
971 template<typename T> inline size_t SVGToOTFFontConverter::appendKERNSubtable(bool (T::*buildKerningPair)(SVGKerningPair&) const, uint16_t coverage)
972 {
973     Vector<KerningData> kerningData;
974     for (auto& element : childrenOfType<T>(m_fontElement)) {
975         SVGKerningPair kerningPair;
976         if ((element.*buildKerningPair)(kerningPair))
977             addKerningPair(kerningData, kerningPair);
978     }
979     return finishAppendingKERNSubtable(WTF::move(kerningData), coverage);
980 }
981
982 size_t SVGToOTFFontConverter::finishAppendingKERNSubtable(Vector<KerningData> kerningData, uint16_t coverage)
983 {
984     std::sort(kerningData.begin(), kerningData.end(), [](const KerningData& a, const KerningData& b) {
985         return a.glyph1 < b.glyph1 || (a.glyph1 == b.glyph1 && a.glyph2 < b.glyph2);
986     });
987
988     size_t sizeOfKerningDataTable = 14 + 6 * kerningData.size();
989     if (sizeOfKerningDataTable > std::numeric_limits<uint16_t>::max()) {
990         kerningData.clear();
991         sizeOfKerningDataTable = 14;
992     }
993
994     append16(0); // Version of subtable
995     append16(sizeOfKerningDataTable); // Length of this subtable
996     append16(coverage); // Table coverage bitfield
997
998     uint16_t roundedNumKerningPairs = roundDownToPowerOfTwo(kerningData.size());
999
1000     append16(kerningData.size());
1001     append16(roundedNumKerningPairs * 6); // searchRange: "The largest power of two less than or equal to the value of nPairs, multiplied by the size in bytes of an entry in the table."
1002     append16(integralLog2(roundedNumKerningPairs)); // entrySelector: "log2 of the largest power of two less than or equal to the value of nPairs."
1003     append16((kerningData.size() - roundedNumKerningPairs) * 6); // rangeShift: "The value of nPairs minus the largest power of two less than or equal to nPairs,
1004                                                                         // and then multiplied by the size in bytes of an entry in the table."
1005
1006     for (auto& kerningData : kerningData) {
1007         append16(kerningData.glyph1);
1008         append16(kerningData.glyph2);
1009         append16(kerningData.adjustment);
1010     }
1011
1012     return sizeOfKerningDataTable;
1013 }
1014
1015 void SVGToOTFFontConverter::appendKERNTable()
1016 {
1017     append16(0); // Version
1018     append16(2); // Number of subtables
1019
1020 #if !ASSERT_DISABLED
1021     auto subtablesOffset = m_result.size();
1022 #endif
1023
1024     size_t sizeOfHorizontalSubtable = appendKERNSubtable<SVGHKernElement>(&SVGHKernElement::buildHorizontalKerningPair, 1);
1025     ASSERT_UNUSED(sizeOfHorizontalSubtable, subtablesOffset + sizeOfHorizontalSubtable == m_result.size());
1026     size_t sizeOfVerticalSubtable = appendKERNSubtable<SVGVKernElement>(&SVGVKernElement::buildVerticalKerningPair, 0);
1027     ASSERT_UNUSED(sizeOfVerticalSubtable, subtablesOffset + sizeOfHorizontalSubtable + sizeOfVerticalSubtable == m_result.size());
1028
1029     // Work around a bug in Apple's font parser by adding some padding bytes. <rdar://problem/18401901>
1030     for (int i = 0; i < 6; ++i)
1031         m_result.append(0);
1032 }
1033
1034 template <typename V>
1035 static void writeCFFEncodedNumber(V& vector, float number)
1036 {
1037     vector.append(0xFF);
1038     append32(vector, number * 0x10000);
1039 }
1040
1041 static const char rLineTo = 0x05;
1042 static const char rrCurveTo = 0x08;
1043 static const char endChar = 0x0e;
1044 static const char rMoveTo = 0x15;
1045
1046 class CFFBuilder : public SVGPathBuilder {
1047 public:
1048     CFFBuilder(Vector<char>& cffData, float width, FloatPoint origin)
1049         : m_cffData(cffData)
1050         , m_hasBoundingBox(false)
1051     {
1052         writeCFFEncodedNumber(m_cffData, width);
1053         writeCFFEncodedNumber(m_cffData, origin.x());
1054         writeCFFEncodedNumber(m_cffData, origin.y());
1055         m_cffData.append(rMoveTo);
1056     }
1057
1058     FloatRect boundingBox() const
1059     {
1060         return m_boundingBox;
1061     }
1062
1063 private:
1064     void updateBoundingBox(FloatPoint point)
1065     {
1066         if (!m_hasBoundingBox) {
1067             m_boundingBox = FloatRect(point, FloatSize());
1068             m_hasBoundingBox = true;
1069             return;
1070         }
1071         m_boundingBox.extend(point);
1072     }
1073
1074     void writePoint(FloatPoint destination)
1075     {
1076         updateBoundingBox(destination);
1077
1078         FloatSize delta = destination - m_current;
1079         writeCFFEncodedNumber(m_cffData, delta.width());
1080         writeCFFEncodedNumber(m_cffData, delta.height());
1081
1082         m_current = destination;
1083     }
1084
1085     virtual void moveTo(const FloatPoint& targetPoint, bool closed, PathCoordinateMode mode) override
1086     {
1087         if (closed && !m_cffData.isEmpty())
1088             closePath();
1089
1090         FloatPoint destination = mode == AbsoluteCoordinates ? targetPoint : m_current + targetPoint;
1091
1092         writePoint(destination);
1093         m_cffData.append(rMoveTo);
1094
1095         m_startingPoint = m_current;
1096     }
1097
1098     virtual void lineTo(const FloatPoint& targetPoint, PathCoordinateMode mode) override
1099     {
1100         FloatPoint destination = mode == AbsoluteCoordinates ? targetPoint : m_current + targetPoint;
1101
1102         writePoint(destination);
1103         m_cffData.append(rLineTo);
1104     }
1105
1106     virtual void curveToCubic(const FloatPoint& point1, const FloatPoint& point2, const FloatPoint& targetPoint, PathCoordinateMode mode) override
1107     {
1108         FloatPoint destination1 = point1;
1109         FloatPoint destination2 = point2;
1110         FloatPoint destination3 = targetPoint;
1111         if (mode == RelativeCoordinates) {
1112             destination1 += m_current;
1113             destination2 += m_current;
1114             destination3 += m_current;
1115         }
1116
1117         writePoint(destination1);
1118         writePoint(destination2);
1119         writePoint(destination3);
1120         m_cffData.append(rrCurveTo);
1121     }
1122
1123     virtual void closePath() override
1124     {
1125         if (m_current != m_startingPoint)
1126             lineTo(m_startingPoint, AbsoluteCoordinates);
1127     }
1128
1129     Vector<char>& m_cffData;
1130     FloatPoint m_startingPoint;
1131     FloatRect m_boundingBox;
1132     bool m_hasBoundingBox;
1133 };
1134
1135 Vector<char> SVGToOTFFontConverter::transcodeGlyphPaths(float width, const SVGElement& glyphOrMissingGlyphElement, FloatRect& boundingBox) const
1136 {
1137     Vector<char> result;
1138
1139     auto& dAttribute = glyphOrMissingGlyphElement.fastGetAttribute(SVGNames::dAttr);
1140     if (dAttribute.isEmpty()) {
1141         writeCFFEncodedNumber(result, width);
1142         writeCFFEncodedNumber(result, 0);
1143         writeCFFEncodedNumber(result, 0);
1144         result.append(rMoveTo);
1145         result.append(endChar);
1146         return result;
1147     }
1148
1149     // FIXME: If we are vertical, use vert_origin_x and vert_origin_y
1150     bool ok;
1151     float horizontalOriginX = glyphOrMissingGlyphElement.fastGetAttribute(SVGNames::horiz_origin_xAttr).toFloat(&ok);
1152     if (!ok)
1153         horizontalOriginX = m_fontFaceElement ? m_fontFaceElement->horizontalOriginX() : 0;
1154     float horizontalOriginY = glyphOrMissingGlyphElement.fastGetAttribute(SVGNames::horiz_origin_yAttr).toFloat(&ok);
1155     if (!ok && m_fontFaceElement)
1156         horizontalOriginY = m_fontFaceElement ? m_fontFaceElement->horizontalOriginY() : 0;
1157
1158     CFFBuilder builder(result, width, FloatPoint(horizontalOriginX, horizontalOriginY));
1159     SVGPathStringSource source(dAttribute);
1160
1161     SVGPathParser parser;
1162     parser.setCurrentSource(&source);
1163     parser.setCurrentConsumer(&builder);
1164
1165     ok = parser.parsePathDataFromSource(NormalizedParsing);
1166     parser.cleanup();
1167
1168     if (!ok)
1169         result.clear();
1170
1171     boundingBox = builder.boundingBox();
1172
1173     result.append(endChar);
1174     return result;
1175 }
1176
1177 void SVGToOTFFontConverter::processGlyphElement(const SVGElement& glyphOrMissingGlyphElement, const SVGGlyphElement* glyphElement, float defaultHorizontalAdvance, float defaultVerticalAdvance, const String& codepoints, bool& initialGlyph)
1178 {
1179     bool ok;
1180     float horizontalAdvance = glyphOrMissingGlyphElement.fastGetAttribute(SVGNames::horiz_adv_xAttr).toFloat(&ok);
1181     if (!ok)
1182         horizontalAdvance = defaultHorizontalAdvance;
1183     m_advanceWidthMax = std::max(m_advanceWidthMax, horizontalAdvance);
1184     float verticalAdvance = glyphOrMissingGlyphElement.fastGetAttribute(SVGNames::vert_adv_yAttr).toFloat(&ok);
1185     if (!ok)
1186         verticalAdvance = defaultVerticalAdvance;
1187     m_advanceHeightMax = std::max(m_advanceHeightMax, verticalAdvance);
1188
1189     FloatRect glyphBoundingBox;
1190     auto path = transcodeGlyphPaths(horizontalAdvance, glyphOrMissingGlyphElement, glyphBoundingBox);
1191     if (initialGlyph)
1192         m_boundingBox = glyphBoundingBox;
1193     else
1194         m_boundingBox.unite(glyphBoundingBox);
1195     m_minRightSideBearing = std::min(m_minRightSideBearing, horizontalAdvance - glyphBoundingBox.maxX());
1196     initialGlyph = false;
1197
1198     m_glyphs.append(GlyphData(WTF::move(path), glyphElement, horizontalAdvance, verticalAdvance, m_boundingBox, codepoints));
1199 }
1200
1201 void SVGToOTFFontConverter::appendLigatureGlyphs()
1202 {
1203     HashSet<UChar32> ligatureCodepoints;
1204     HashSet<UChar32> nonLigatureCodepoints;
1205     for (auto& glyph : m_glyphs) {
1206         auto codePoints = StringView(glyph.codepoints).codePoints();
1207         auto codePointsIterator = codePoints.begin();
1208         if (codePointsIterator == codePoints.end())
1209             continue;
1210         UChar32 codepoint = *codePointsIterator;
1211         ++codePointsIterator;
1212         if (codePointsIterator == codePoints.end())
1213             nonLigatureCodepoints.add(codepoint);
1214         else {
1215             ligatureCodepoints.add(codepoint);
1216             for (; codePointsIterator != codePoints.end(); ++codePointsIterator)
1217                 ligatureCodepoints.add(*codePointsIterator);
1218         }
1219     }
1220
1221     for (auto codepoint : nonLigatureCodepoints)
1222         ligatureCodepoints.remove(codepoint);
1223     for (auto codepoint : ligatureCodepoints) {
1224         auto codepoints = codepointToString(codepoint);
1225         if (!codepoints.isNull())
1226             m_glyphs.append(GlyphData(Vector<char, 17>(m_emptyGlyphCharString), nullptr, m_unitsPerEm, m_unitsPerEm, FloatRect(), codepoints));
1227     }
1228 }
1229
1230 bool SVGToOTFFontConverter::compareCodepointsLexicographically(const GlyphData& data1, const GlyphData& data2)
1231 {
1232     auto codePoints1 = StringView(data1.codepoints).codePoints();
1233     auto codePoints2 = StringView(data2.codepoints).codePoints();
1234     auto iterator1 = codePoints1.begin();
1235     auto iterator2 = codePoints2.begin();
1236     unsigned length1 = data1.codepoints.length();
1237     unsigned length2 = data2.codepoints.length();
1238     while (iterator1 != codePoints1.end() && iterator2 != codePoints2.end()) {
1239         UChar32 codepoint1, codepoint2;
1240         codepoint1 = *iterator1;
1241         codepoint2 = *iterator2;
1242
1243         if (codepoint1 < codepoint2)
1244             return true;
1245         if (codepoint1 > codepoint2)
1246             return false;
1247
1248         ++iterator1;
1249         ++iterator2;
1250     }
1251
1252     if (length1 == length2 && data1.glyphElement
1253         && equalIgnoringCase(data1.glyphElement->fastGetAttribute(SVGNames::arabic_formAttr), "isolated"))
1254         return true;
1255     return length1 < length2;
1256 }
1257
1258 static void populateEmptyGlyphCharString(Vector<char, 17>& o, unsigned unitsPerEm)
1259 {
1260     writeCFFEncodedNumber(o, unitsPerEm);
1261     writeCFFEncodedNumber(o, 0);
1262     writeCFFEncodedNumber(o, 0);
1263     o.append(rMoveTo);
1264     o.append(endChar);
1265 }
1266
1267 SVGToOTFFontConverter::SVGToOTFFontConverter(const SVGFontElement& fontElement)
1268     : m_fontElement(fontElement)
1269     , m_fontFaceElement(childrenOfType<SVGFontFaceElement>(m_fontElement).first())
1270     , m_missingGlyphElement(childrenOfType<SVGMissingGlyphElement>(m_fontElement).first())
1271     , m_advanceWidthMax(0)
1272     , m_advanceHeightMax(0)
1273     , m_minRightSideBearing(std::numeric_limits<float>::max())
1274     , m_unitsPerEm(0)
1275     , m_featureCountGSUB(0)
1276     , m_tablesAppendedCount(0)
1277     , m_weight(5)
1278     , m_italic(false)
1279 {
1280
1281     float defaultHorizontalAdvance = m_fontFaceElement ? m_fontFaceElement->horizontalAdvanceX() : 0;
1282     float defaultVerticalAdvance = m_fontFaceElement ? m_fontFaceElement->verticalAdvanceY() : 0;
1283     bool initialGlyph = true;
1284
1285     if (m_fontFaceElement)
1286         m_unitsPerEm = m_fontFaceElement->unitsPerEm();
1287
1288     populateEmptyGlyphCharString(m_emptyGlyphCharString, m_unitsPerEm);
1289
1290     if (m_missingGlyphElement)
1291         processGlyphElement(*m_missingGlyphElement, nullptr, defaultHorizontalAdvance, defaultVerticalAdvance, String(), initialGlyph);
1292     else
1293         m_glyphs.append(GlyphData(Vector<char, 17>(m_emptyGlyphCharString), nullptr, m_unitsPerEm, m_unitsPerEm, FloatRect(), String()));
1294
1295     for (auto& glyphElement : childrenOfType<SVGGlyphElement>(m_fontElement)) {
1296         auto& unicodeAttribute = glyphElement.fastGetAttribute(SVGNames::unicodeAttr);
1297         if (!unicodeAttribute.isEmpty()) // If we can never actually trigger this glyph, ignore it completely
1298             processGlyphElement(glyphElement, &glyphElement, defaultHorizontalAdvance, defaultVerticalAdvance, unicodeAttribute, initialGlyph);
1299     }
1300
1301     appendLigatureGlyphs();
1302
1303     if (m_glyphs.size() > std::numeric_limits<Glyph>::max()) {
1304         m_glyphs.clear();
1305         return;
1306     }
1307
1308     std::sort(m_glyphs.begin(), m_glyphs.end(), &compareCodepointsLexicographically);
1309
1310     for (Glyph i = 0; i < m_glyphs.size(); ++i) {
1311         GlyphData& glyph = m_glyphs[i];
1312         if (glyph.glyphElement) {
1313             auto& glyphName = glyph.glyphElement->fastGetAttribute(SVGNames::glyph_nameAttr);
1314             if (!glyphName.isNull())
1315                 m_glyphNameToIndexMap.add(glyphName, i);
1316         }
1317         if (m_codepointsToIndicesMap.isValidKey(glyph.codepoints)) {
1318             auto& glyphVector = m_codepointsToIndicesMap.add(glyph.codepoints, Vector<Glyph>()).iterator->value;
1319             // Prefer isolated arabic forms
1320             if (glyph.glyphElement && equalIgnoringCase(glyph.glyphElement->fastGetAttribute(SVGNames::arabic_formAttr), "isolated"))
1321                 glyphVector.insert(0, i);
1322             else
1323                 glyphVector.append(i);
1324         }
1325     }
1326
1327     // FIXME: Handle commas.
1328     if (m_fontFaceElement) {
1329         Vector<String> segments;
1330         m_fontFaceElement->fastGetAttribute(SVGNames::font_weightAttr).string().split(' ', segments);
1331         for (auto& segment : segments) {
1332             if (equalIgnoringCase(segment, "bold")) {
1333                 m_weight = 7;
1334                 break;
1335             }
1336             bool ok;
1337             int value = segment.toInt(&ok);
1338             if (ok && value >= 0 && value < 1000) {
1339                 m_weight = (value + 50) / 100;
1340                 break;
1341             }
1342         }
1343         m_fontFaceElement->fastGetAttribute(SVGNames::font_styleAttr).string().split(' ', segments);
1344         for (auto& segment : segments) {
1345             if (equalIgnoringCase(segment, "italic") || equalIgnoringCase(segment, "oblique")) {
1346                 m_italic = true;
1347                 break;
1348             }
1349         }
1350     }
1351
1352     if (m_fontFaceElement)
1353         m_fontFamily = m_fontFaceElement->fontFamily();
1354 }
1355
1356 static inline bool isFourByteAligned(size_t x)
1357 {
1358     return !(x & 3);
1359 }
1360
1361 uint32_t SVGToOTFFontConverter::calculateChecksum(size_t startingOffset, size_t endingOffset) const
1362 {
1363     ASSERT(isFourByteAligned(endingOffset - startingOffset));
1364     uint32_t sum = 0;
1365     for (size_t offset = startingOffset; offset < endingOffset; offset += 4) {
1366         sum += (static_cast<unsigned char>(m_result[offset + 3]) << 24)
1367             | (static_cast<unsigned char>(m_result[offset + 2]) << 16)
1368             | (static_cast<unsigned char>(m_result[offset + 1]) << 8)
1369             | static_cast<unsigned char>(m_result[offset]);
1370     }
1371     return sum;
1372 }
1373
1374 void SVGToOTFFontConverter::appendTable(const char identifier[4], FontAppendingFunction appendingFunction)
1375 {
1376     size_t offset = m_result.size();
1377     ASSERT(isFourByteAligned(offset));
1378     (this->*appendingFunction)();
1379     size_t unpaddedSize = m_result.size() - offset;
1380     while (!isFourByteAligned(m_result.size()))
1381         m_result.append(0);
1382     ASSERT(isFourByteAligned(m_result.size()));
1383     size_t directoryEntryOffset = headerSize + m_tablesAppendedCount * directoryEntrySize;
1384     m_result[directoryEntryOffset] = identifier[0];
1385     m_result[directoryEntryOffset + 1] = identifier[1];
1386     m_result[directoryEntryOffset + 2] = identifier[2];
1387     m_result[directoryEntryOffset + 3] = identifier[3];
1388     overwrite32(directoryEntryOffset + 4, calculateChecksum(offset, m_result.size()));
1389     overwrite32(directoryEntryOffset + 8, offset);
1390     overwrite32(directoryEntryOffset + 12, unpaddedSize);
1391     ++m_tablesAppendedCount;
1392 }
1393
1394 void SVGToOTFFontConverter::convertSVGToOTFFont()
1395 {
1396     if (m_glyphs.isEmpty())
1397         return;
1398
1399     uint16_t numTables = 14;
1400     uint16_t roundedNumTables = roundDownToPowerOfTwo(numTables);
1401     uint16_t searchRange = roundedNumTables * 16; // searchRange: "(Maximum power of 2 <= numTables) x 16."
1402
1403     m_result.append('O');
1404     m_result.append('T');
1405     m_result.append('T');
1406     m_result.append('O');
1407     append16(numTables);
1408     append16(searchRange);
1409     append16(integralLog2(roundedNumTables)); // entrySelector: "Log2(maximum power of 2 <= numTables)."
1410     append16(numTables * 16 - searchRange); // rangeShift: "NumTables x 16-searchRange."
1411
1412     ASSERT(m_result.size() == headerSize);
1413
1414     // Leave space for the directory entries.
1415     for (size_t i = 0; i < directoryEntrySize * numTables; ++i)
1416         m_result.append(0);
1417
1418     appendTable("CFF ", &SVGToOTFFontConverter::appendCFFTable);
1419     appendTable("GSUB", &SVGToOTFFontConverter::appendGSUBTable);
1420     appendTable("OS/2", &SVGToOTFFontConverter::appendOS2Table);
1421     appendTable("VORG", &SVGToOTFFontConverter::appendVORGTable);
1422     appendTable("cmap", &SVGToOTFFontConverter::appendCMAPTable);
1423     auto headTableOffset = m_result.size();
1424     appendTable("head", &SVGToOTFFontConverter::appendHEADTable);
1425     appendTable("hhea", &SVGToOTFFontConverter::appendHHEATable);
1426     appendTable("hmtx", &SVGToOTFFontConverter::appendHMTXTable);
1427     appendTable("kern", &SVGToOTFFontConverter::appendKERNTable);
1428     appendTable("maxp", &SVGToOTFFontConverter::appendMAXPTable);
1429     appendTable("name", &SVGToOTFFontConverter::appendNAMETable);
1430     appendTable("post", &SVGToOTFFontConverter::appendPOSTTable);
1431     appendTable("vhea", &SVGToOTFFontConverter::appendVHEATable);
1432     appendTable("vmtx", &SVGToOTFFontConverter::appendVMTXTable);
1433
1434     ASSERT(numTables == m_tablesAppendedCount);
1435
1436     // checksumAdjustment: "To compute: set it to 0, calculate the checksum for the 'head' table and put it in the table directory,
1437     // sum the entire font as uint32, then store B1B0AFBA - sum. The checksum for the 'head' table will now be wrong. That is OK."
1438     overwrite32(headTableOffset + 8, 0xB1B0AFBAU - calculateChecksum(0, m_result.size()));
1439 }
1440
1441 Vector<char> convertSVGToOTFFont(const SVGFontElement& element)
1442 {
1443     SVGToOTFFontConverter converter(element);
1444     converter.convertSVGToOTFFont();
1445     return converter.releaseResult();
1446 }
1447
1448 }