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