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