Compile with clang when C++11 support is enabled
[profile/ivi/qtbase.git] / src / gui / text / qfontsubset.cpp
1 /****************************************************************************
2 **
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/
5 **
6 ** This file is part of the QtGui module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** GNU Lesser General Public License Usage
10 ** This file may be used under the terms of the GNU Lesser General Public
11 ** License version 2.1 as published by the Free Software Foundation and
12 ** appearing in the file LICENSE.LGPL included in the packaging of this
13 ** file. Please review the following information to ensure the GNU Lesser
14 ** General Public License version 2.1 requirements will be met:
15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
16 **
17 ** In addition, as a special exception, Nokia gives you certain additional
18 ** rights. These rights are described in the Nokia Qt LGPL Exception
19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
20 **
21 ** GNU General Public License Usage
22 ** Alternatively, this file may be used under the terms of the GNU General
23 ** Public License version 3.0 as published by the Free Software Foundation
24 ** and appearing in the file LICENSE.GPL included in the packaging of this
25 ** file. Please review the following information to ensure the GNU General
26 ** Public License version 3.0 requirements will be met:
27 ** http://www.gnu.org/copyleft/gpl.html.
28 **
29 ** Other Usage
30 ** Alternatively, this file may be used in accordance with the terms and
31 ** conditions contained in a signed written agreement between you and Nokia.
32 **
33 **
34 **
35 **
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 #include <qdebug.h>
42 #include "qfontsubset_p.h"
43 #include <qendian.h>
44 #include <qpainterpath.h>
45 #include "private/qpdf_p.h"
46 #include "private/qfunctions_p.h"
47
48 QT_BEGIN_NAMESPACE
49
50 static const char * const agl =
51 ".notdef\0space\0exclam\0quotedbl\0numbersign\0dollar\0percent\0ampersand\0"
52 "quotesingle\0parenleft\0parenright\0asterisk\0plus\0comma\0hyphen\0period\0"
53 "slash\0zero\0one\0two\0three\0four\0five\0six\0seven\0eight\0nine\0colon\0"
54 "semicolon\0less\0equal\0greater\0question\0at\0A\0B\0C\0D\0E\0F\0G\0H\0I\0J\0"
55 "K\0L\0M\0N\0O\0P\0Q\0R\0S\0T\0U\0V\0W\0X\0Y\0Z\0bracketleft\0backslash\0"
56 "bracketright\0asciicircum\0underscore\0grave\0a\0b\0c\0d\0e\0f\0g\0h\0i\0j\0"
57 "k\0l\0m\0n\0o\0p\0q\0r\0s\0t\0u\0v\0w\0x\0y\0z\0braceleft\0bar\0braceright\0"
58 "asciitilde\0space\0exclamdown\0cent\0sterling\0currency\0yen\0brokenbar\0"
59 "section\0dieresis\0copyright\0ordfeminine\0guillemotleft\0logicalnot\0"
60 "hyphen\0registered\0macron\0degree\0plusminus\0twosuperior\0threesuperior\0"
61 "acute\0mu\0paragraph\0periodcentered\0cedilla\0onesuperior\0ordmasculine\0"
62 "guillemotright\0onequarter\0onehalf\0threequarters\0questiondown\0Agrave\0"
63 "Aacute\0Acircumflex\0Atilde\0Adieresis\0Aring\0AE\0Ccedilla\0Egrave\0Eacute\0"
64 "Ecircumflex\0Edieresis\0Igrave\0Iacute\0Icircumflex\0Idieresis\0Eth\0Ntilde\0"
65 "Ograve\0Oacute\0Ocircumflex\0Otilde\0Odieresis\0multiply\0Oslash\0Ugrave\0"
66 "Uacute\0Ucircumflex\0Udieresis\0Yacute\0Thorn\0germandbls\0agrave\0aacute\0"
67 "acircumflex\0atilde\0adieresis\0aring\0ae\0ccedilla\0egrave\0eacute\0"
68 "ecircumflex\0edieresis\0igrave\0iacute\0icircumflex\0idieresis\0eth\0ntilde\0"
69 "ograve\0oacute\0ocircumflex\0otilde\0odieresis\0divide\0oslash\0ugrave\0"
70 "uacute\0ucircumflex\0udieresis\0yacute\0thorn\0ydieresis\0Amacron\0amacron\0"
71 "Abreve\0abreve\0Aogonek\0aogonek\0Cacute\0cacute\0Ccircumflex\0ccircumflex\0"
72 "Cdotaccent\0cdotaccent\0Ccaron\0ccaron\0Dcaron\0dcaron\0Dcroat\0dcroat\0"
73 "Emacron\0emacron\0Ebreve\0ebreve\0Edotaccent\0edotaccent\0Eogonek\0eogonek\0"
74 "Ecaron\0ecaron\0Gcircumflex\0gcircumflex\0Gbreve\0gbreve\0Gdotaccent\0"
75 "gdotaccent\0Gcommaaccent\0gcommaaccent\0Hcircumflex\0hcircumflex\0Hbar\0"
76 "hbar\0Itilde\0itilde\0Imacron\0imacron\0Ibreve\0ibreve\0Iogonek\0iogonek\0"
77 "Idotaccent\0dotlessi\0IJ\0ij\0Jcircumflex\0jcircumflex\0Kcommaaccent\0"
78 "kcommaaccent\0kgreenlandic\0Lacute\0lacute\0Lcommaaccent\0lcommaaccent\0"
79 "Lcaron\0lcaron\0Ldot\0ldot\0Lslash\0lslash\0Nacute\0nacute\0Ncommaaccent\0"
80 "ncommaaccent\0Ncaron\0ncaron\0napostrophe\0Eng\0eng\0Omacron\0omacron\0"
81 "Obreve\0obreve\0Ohungarumlaut\0ohungarumlaut\0OE\0oe\0Racute\0racute\0"
82 "Rcommaaccent\0rcommaaccent\0Rcaron\0rcaron\0Sacute\0sacute\0Scircumflex\0"
83 "scircumflex\0Scedilla\0scedilla\0Scaron\0scaron\0Tcaron\0tcaron\0Tbar\0tbar\0"
84 "Utilde\0utilde\0Umacron\0umacron\0Ubreve\0ubreve\0Uring\0uring\0"
85 "Uhungarumlaut\0uhungarumlaut\0Uogonek\0uogonek\0Wcircumflex\0wcircumflex\0"
86 "Ycircumflex\0ycircumflex\0Ydieresis\0Zacute\0zacute\0Zdotaccent\0zdotaccent\0"
87 "Zcaron\0zcaron\0longs\0florin\0Ohorn\0ohorn\0Uhorn\0uhorn\0Gcaron\0gcaron\0"
88 "Aringacute\0aringacute\0AEacute\0aeacute\0Oslashacute\0oslashacute\0"
89 "Scommaaccent\0scommaaccent\0Tcommaaccent\0tcommaaccent\0afii57929\0"
90 "afii64937\0circumflex\0caron\0breve\0dotaccent\0ring\0ogonek\0tilde\0"
91 "hungarumlaut\0gravecomb\0acutecomb\0tildecomb\0hookabovecomb\0dotbelowcomb\0"
92 "tonos\0dieresistonos\0Alphatonos\0anoteleia\0Epsilontonos\0Etatonos\0"
93 "Iotatonos\0Omicrontonos\0Upsilontonos\0Omegatonos\0iotadieresistonos\0Alpha\0"
94 "Beta\0Gamma\0Delta\0Epsilon\0Zeta\0Eta\0Theta\0Iota\0Kappa\0Lambda\0Mu\0Nu\0"
95 "Xi\0Omicron\0Pi\0Rho\0Sigma\0Tau\0Upsilon\0Phi\0Chi\0Psi\0Omega\0"
96 "Iotadieresis\0Upsilondieresis\0alphatonos\0epsilontonos\0etatonos\0"
97 "iotatonos\0upsilondieresistonos\0alpha\0beta\0gamma\0delta\0epsilon\0zeta\0"
98 "eta\0theta\0iota\0kappa\0lambda\0mu\0nu\0xi\0omicron\0pi\0rho\0sigma1\0"
99 "sigma\0tau\0upsilon\0phi\0chi\0psi\0omega\0iotadieresis\0upsilondieresis\0"
100 ;
101
102 static const struct { quint16 u; quint16 index; } unicode_to_aglindex[] = {
103     {0x0000, 0}, {0x0020, 8}, {0x0021, 14}, {0x0022, 21},
104     {0x0023, 30}, {0x0024, 41}, {0x0025, 48}, {0x0026, 56},
105     {0x0027, 66}, {0x0028, 78}, {0x0029, 88}, {0x002A, 99},
106     {0x002B, 108}, {0x002C, 113}, {0x002D, 119}, {0x002E, 126},
107     {0x002F, 133}, {0x0030, 139}, {0x0031, 144}, {0x0032, 148},
108     {0x0033, 152}, {0x0034, 158}, {0x0035, 163}, {0x0036, 168},
109     {0x0037, 172}, {0x0038, 178}, {0x0039, 184}, {0x003A, 189},
110     {0x003B, 195}, {0x003C, 205}, {0x003D, 210}, {0x003E, 216},
111     {0x003F, 224}, {0x0040, 233}, {0x0041, 236}, {0x0042, 238},
112     {0x0043, 240}, {0x0044, 242}, {0x0045, 244}, {0x0046, 246},
113     {0x0047, 248}, {0x0048, 250}, {0x0049, 252}, {0x004A, 254},
114     {0x004B, 256}, {0x004C, 258}, {0x004D, 260}, {0x004E, 262},
115     {0x004F, 264}, {0x0050, 266}, {0x0051, 268}, {0x0052, 270},
116     {0x0053, 272}, {0x0054, 274}, {0x0055, 276}, {0x0056, 278},
117     {0x0057, 280}, {0x0058, 282}, {0x0059, 284}, {0x005A, 286},
118     {0x005B, 288}, {0x005C, 300}, {0x005D, 310}, {0x005E, 323},
119     {0x005F, 335}, {0x0060, 346}, {0x0061, 352}, {0x0062, 354},
120     {0x0063, 356}, {0x0064, 358}, {0x0065, 360}, {0x0066, 362},
121     {0x0067, 364}, {0x0068, 366}, {0x0069, 368}, {0x006A, 370},
122     {0x006B, 372}, {0x006C, 374}, {0x006D, 376}, {0x006E, 378},
123     {0x006F, 380}, {0x0070, 382}, {0x0071, 384}, {0x0072, 386},
124     {0x0073, 388}, {0x0074, 390}, {0x0075, 392}, {0x0076, 394},
125     {0x0077, 396}, {0x0078, 398}, {0x0079, 400}, {0x007A, 402},
126     {0x007B, 404}, {0x007C, 414}, {0x007D, 418}, {0x007E, 429},
127     {0x00A0, 440}, {0x00A1, 446}, {0x00A2, 457}, {0x00A3, 462},
128     {0x00A4, 471}, {0x00A5, 480}, {0x00A6, 484}, {0x00A7, 494},
129     {0x00A8, 502}, {0x00A9, 511}, {0x00AA, 521}, {0x00AB, 533},
130     {0x00AC, 547}, {0x00AD, 558}, {0x00AE, 565}, {0x00AF, 576},
131     {0x00B0, 583}, {0x00B1, 590}, {0x00B2, 600}, {0x00B3, 612},
132     {0x00B4, 626}, {0x00B5, 632}, {0x00B6, 635}, {0x00B7, 645},
133     {0x00B8, 660}, {0x00B9, 668}, {0x00BA, 680}, {0x00BB, 693},
134     {0x00BC, 708}, {0x00BD, 719}, {0x00BE, 727}, {0x00BF, 741},
135     {0x00C0, 754}, {0x00C1, 761}, {0x00C2, 768}, {0x00C3, 780},
136     {0x00C4, 787}, {0x00C5, 797}, {0x00C6, 803}, {0x00C7, 806},
137     {0x00C8, 815}, {0x00C9, 822}, {0x00CA, 829}, {0x00CB, 841},
138     {0x00CC, 851}, {0x00CD, 858}, {0x00CE, 865}, {0x00CF, 877},
139     {0x00D0, 887}, {0x00D1, 891}, {0x00D2, 898}, {0x00D3, 905},
140     {0x00D4, 912}, {0x00D5, 924}, {0x00D6, 931}, {0x00D7, 941},
141     {0x00D8, 950}, {0x00D9, 957}, {0x00DA, 964}, {0x00DB, 971},
142     {0x00DC, 983}, {0x00DD, 993}, {0x00DE, 1000}, {0x00DF, 1006},
143     {0x00E0, 1017}, {0x00E1, 1024}, {0x00E2, 1031}, {0x00E3, 1043},
144     {0x00E4, 1050}, {0x00E5, 1060}, {0x00E6, 1066}, {0x00E7, 1069},
145     {0x00E8, 1078}, {0x00E9, 1085}, {0x00EA, 1092}, {0x00EB, 1104},
146     {0x00EC, 1114}, {0x00ED, 1121}, {0x00EE, 1128}, {0x00EF, 1140},
147     {0x00F0, 1150}, {0x00F1, 1154}, {0x00F2, 1161}, {0x00F3, 1168},
148     {0x00F4, 1175}, {0x00F5, 1187}, {0x00F6, 1194}, {0x00F7, 1204},
149     {0x00F8, 1211}, {0x00F9, 1218}, {0x00FA, 1225}, {0x00FB, 1232},
150     {0x00FC, 1244}, {0x00FD, 1254}, {0x00FE, 1261}, {0x00FF, 1267},
151     {0x0100, 1277}, {0x0101, 1285}, {0x0102, 1293}, {0x0103, 1300},
152     {0x0104, 1307}, {0x0105, 1315}, {0x0106, 1323}, {0x0107, 1330},
153     {0x0108, 1337}, {0x0109, 1349}, {0x010A, 1361}, {0x010B, 1372},
154     {0x010C, 1383}, {0x010D, 1390}, {0x010E, 1397}, {0x010F, 1404},
155     {0x0110, 1411}, {0x0111, 1418}, {0x0112, 1425}, {0x0113, 1433},
156     {0x0114, 1441}, {0x0115, 1448}, {0x0116, 1455}, {0x0117, 1466},
157     {0x0118, 1477}, {0x0119, 1485}, {0x011A, 1493}, {0x011B, 1500},
158     {0x011C, 1507}, {0x011D, 1519}, {0x011E, 1531}, {0x011F, 1538},
159     {0x0120, 1545}, {0x0121, 1556}, {0x0122, 1567}, {0x0123, 1580},
160     {0x0124, 1593}, {0x0125, 1605}, {0x0126, 1617}, {0x0127, 1622},
161     {0x0128, 1627}, {0x0129, 1634}, {0x012A, 1641}, {0x012B, 1649},
162     {0x012C, 1657}, {0x012D, 1664}, {0x012E, 1671}, {0x012F, 1679},
163     {0x0130, 1687}, {0x0131, 1698}, {0x0132, 1707}, {0x0133, 1710},
164     {0x0134, 1713}, {0x0135, 1725}, {0x0136, 1737}, {0x0137, 1750},
165     {0x0138, 1763}, {0x0139, 1776}, {0x013A, 1783}, {0x013B, 1790},
166     {0x013C, 1803}, {0x013D, 1816}, {0x013E, 1823}, {0x013F, 1830},
167     {0x0140, 1835}, {0x0141, 1840}, {0x0142, 1847}, {0x0143, 1854},
168     {0x0144, 1861}, {0x0145, 1868}, {0x0146, 1881}, {0x0147, 1894},
169     {0x0148, 1901}, {0x0149, 1908}, {0x014A, 1920}, {0x014B, 1924},
170     {0x014C, 1928}, {0x014D, 1936}, {0x014E, 1944}, {0x014F, 1951},
171     {0x0150, 1958}, {0x0151, 1972}, {0x0152, 1986}, {0x0153, 1989},
172     {0x0154, 1992}, {0x0155, 1999}, {0x0156, 2006}, {0x0157, 2019},
173     {0x0158, 2032}, {0x0159, 2039}, {0x015A, 2046}, {0x015B, 2053},
174     {0x015C, 2060}, {0x015D, 2072}, {0x015E, 2084}, {0x015F, 2093},
175     {0x0160, 2102}, {0x0161, 2109}, {0x0164, 2116}, {0x0165, 2123},
176     {0x0166, 2130}, {0x0167, 2135}, {0x0168, 2140}, {0x0169, 2147},
177     {0x016A, 2154}, {0x016B, 2162}, {0x016C, 2170}, {0x016D, 2177},
178     {0x016E, 2184}, {0x016F, 2190}, {0x0170, 2196}, {0x0171, 2210},
179     {0x0172, 2224}, {0x0173, 2232}, {0x0174, 2240}, {0x0175, 2252},
180     {0x0176, 2264}, {0x0177, 2276}, {0x0178, 2288}, {0x0179, 2298},
181     {0x017A, 2305}, {0x017B, 2312}, {0x017C, 2323}, {0x017D, 2334},
182     {0x017E, 2341}, {0x017F, 2348}, {0x0192, 2354}, {0x01A0, 2361},
183     {0x01A1, 2367}, {0x01AF, 2373}, {0x01B0, 2379}, {0x01E6, 2385},
184     {0x01E7, 2392}, {0x01FA, 2399}, {0x01FB, 2410}, {0x01FC, 2421},
185     {0x01FD, 2429}, {0x01FE, 2437}, {0x01FF, 2449}, {0x0218, 2461},
186     {0x0219, 2474}, {0x021A, 2487}, {0x021B, 2500}, {0x02BC, 2513},
187     {0x02BD, 2523}, {0x02C6, 2533}, {0x02C7, 2544}, {0x02D8, 2550},
188     {0x02D9, 2556}, {0x02DA, 2566}, {0x02DB, 2571}, {0x02DC, 2578},
189     {0x02DD, 2584}, {0x0300, 2597}, {0x0301, 2607}, {0x0303, 2617},
190     {0x0309, 2627}, {0x0323, 2641}, {0x0384, 2654}, {0x0385, 2660},
191     {0x0386, 2674}, {0x0387, 2685}, {0x0388, 2695}, {0x0389, 2708},
192     {0x038A, 2717}, {0x038C, 2727}, {0x038E, 2740}, {0x038F, 2753},
193     {0x0390, 2764}, {0x0391, 2782}, {0x0392, 2788}, {0x0393, 2793},
194     {0x0394, 2799}, {0x0395, 2805}, {0x0396, 2813}, {0x0397, 2818},
195     {0x0398, 2822}, {0x0399, 2828}, {0x039A, 2833}, {0x039B, 2839},
196     {0x039C, 2846}, {0x039D, 2849}, {0x039E, 2852}, {0x039F, 2855},
197     {0x03A0, 2863}, {0x03A1, 2866}, {0x03A3, 2870}, {0x03A4, 2876},
198     {0x03A5, 2880}, {0x03A6, 2888}, {0x03A7, 2892}, {0x03A8, 2896},
199     {0x03A9, 2900}, {0x03AA, 2906}, {0x03AB, 2919}, {0x03AC, 2935},
200     {0x03AD, 2946}, {0x03AE, 2959}, {0x03AF, 2968}, {0x03B0, 2978},
201     {0x03B1, 2999}, {0x03B2, 3005}, {0x03B3, 3010}, {0x03B4, 3016},
202     {0x03B5, 3022}, {0x03B6, 3030}, {0x03B7, 3035}, {0x03B8, 3039},
203     {0x03B9, 3045}, {0x03BA, 3050}, {0x03BB, 3056}, {0x03BC, 3063},
204     {0x03BD, 3066}, {0x03BE, 3069}, {0x03BF, 3072}, {0x03C0, 3080},
205     {0x03C1, 3083}, {0x03C2, 3087}, {0x03C3, 3094}, {0x03C4, 3100},
206     {0x03C5, 3104}, {0x03C6, 3112}, {0x03C7, 3116}, {0x03C8, 3120},
207     {0x03C9, 3124}, {0x03CA, 3130}, {0x03CB, 3143}, {0x03CC, 3159},
208     {0x03CD, 3172}, {0x03CE, 3185}, {0x03D1, 3196}, {0x03D2, 3203},
209     {0x03D5, 3212}, {0x03D6, 3217}, {0xFFFF, 3224}
210 };
211
212 // This map is used for symbol fonts to get the correct glyph names for the latin range
213 static const unsigned short symbol_map[0x100] = {
214     0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007,
215     0x0008, 0x0009, 0x000a, 0x000b, 0x000c, 0x000d, 0x000e, 0x000f,
216     0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016, 0x0017,
217     0x0018, 0x0019, 0x001a, 0x001b, 0x001c, 0x001d, 0x001e, 0x001f,
218     0x0020, 0x0021, 0x2200, 0x0023, 0x2203, 0x0025, 0x0026, 0x220b,
219     0x0028, 0x0029, 0x2217, 0x002b, 0x002c, 0x2212, 0x002e, 0x002f,
220     0x0030, 0x0031, 0x0032, 0x0033, 0x0034, 0x0035, 0x0036, 0x0037,
221     0x0038, 0x0039, 0x003a, 0x003b, 0x003c, 0x003d, 0x003e, 0x003f,
222
223     0x2245, 0x0391, 0x0392, 0x03a7, 0x0394, 0x0395, 0x03a6, 0x0393,
224     0x0397, 0x0399, 0x03d1, 0x039a, 0x039b, 0x039c, 0x039d, 0x039f,
225     0x03a0, 0x0398, 0x03a1, 0x03a3, 0x03a4, 0x03a5, 0x03c2, 0x03a9,
226     0x039e, 0x03a8, 0x0396, 0x005b, 0x2234, 0x005d, 0x22a5, 0x005f,
227     0xf8e5, 0x03b1, 0x03b2, 0x03c7, 0x03b4, 0x03b5, 0x03c6, 0x03b3,
228     0x03b7, 0x03b9, 0x03d5, 0x03ba, 0x03bb, 0x03bc, 0x03bd, 0x03bf,
229     0x03c0, 0x03b8, 0x03c1, 0x03c3, 0x03c4, 0x03c5, 0x03d6, 0x03c9,
230     0x03be, 0x03c8, 0x03b6, 0x007b, 0x007c, 0x007d, 0x223c, 0x007f,
231
232     0x0080, 0x0081, 0x0082, 0x0083, 0x0084, 0x0085, 0x0086, 0x0087,
233     0x0088, 0x0089, 0x008a, 0x008b, 0x008c, 0x008d, 0x008e, 0x008f,
234     0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095, 0x0096, 0x0097,
235     0x0098, 0x0099, 0x009a, 0x009b, 0x009c, 0x009d, 0x009e, 0x009f,
236     0x20ac, 0x03d2, 0x2023, 0x2264, 0x2044, 0x221e, 0x0192, 0x2263,
237     0x2666, 0x2665, 0x2660, 0x2194, 0x2190, 0x2191, 0x2192, 0x2193,
238     0x00b0, 0x00b1, 0x2033, 0x2265, 0x00d7, 0x221d, 0x2202, 0x2022,
239     0x00f7, 0x2260, 0x2261, 0x2248, 0x2026, 0xf8e6, 0xf8e7, 0x21b5,
240
241     0x2135, 0x2111, 0x211c, 0x2118, 0x2297, 0x2295, 0x2205, 0x2229,
242     0x222a, 0x2283, 0x2287, 0x2284, 0x2282, 0x2286, 0x2208, 0x2209,
243     0x2220, 0x2207, 0xf6da, 0xf6d9, 0xf6db, 0x220f, 0x221a, 0x22c5,
244     0x00ac, 0x2227, 0x2228, 0x21d4, 0x21d0, 0x21d1, 0x21d2, 0x21d3,
245     0x25ca, 0x2329, 0xf8e8, 0xf8e9, 0xf8ea, 0x2211, 0xf8eb, 0xf8ec,
246     0xf8ed, 0xf8ee, 0xf8ef, 0xf8f0, 0xf8f1, 0xf8f2, 0xf8f3, 0xf8f4,
247     0x0000, 0x232a, 0x222b, 0x2320, 0xf8f5, 0x2321, 0xf8f6, 0xf8f7,
248     0xf8f8, 0xf8f9, 0xf8fa, 0xf8fb, 0xf8fc, 0xf8fd, 0xf8fe, 0x0000,
249 };
250
251 // ---------------------------- PS/PDF helper methods -----------------------------------
252
253 QByteArray QFontSubset::glyphName(unsigned short unicode, bool symbol)
254 {
255     if (symbol && unicode < 0x100)
256         // map from latin1 to symbol
257         unicode = symbol_map[unicode];
258
259     int l = 0;
260     while(unicode_to_aglindex[l].u < unicode)
261         l++;
262     if (unicode_to_aglindex[l].u == unicode)
263         return agl + unicode_to_aglindex[l].index;
264
265     char buffer[8];
266     buffer[0] = 'u';
267     buffer[1] = 'n';
268     buffer[2] = 'i';
269     QPdf::toHex(unicode, buffer+3);
270     return buffer;
271 }
272
273 QByteArray QFontSubset::glyphName(unsigned int glyph, const QVector<int> reverseMap) const
274 {
275     uint glyphIndex = glyph_indices[glyph];
276
277     if (glyphIndex == 0)
278         return "/.notdef";
279
280     QByteArray ba;
281     QPdf::ByteStream s(&ba);
282     if (reverseMap[glyphIndex] && reverseMap[glyphIndex] < 0x10000) {
283         s << '/' << glyphName(reverseMap[glyphIndex], false);
284     } else {
285         s << "/gl" << (int)glyphIndex;
286     }
287     return ba;
288 }
289
290
291 QByteArray QFontSubset::widthArray() const
292 {
293     Q_ASSERT(!widths.isEmpty());
294
295     QFontEngine::Properties properties = fontEngine->properties();
296
297     QByteArray width;
298     QPdf::ByteStream s(&width);
299     QFixed scale = QFixed(1000)/emSquare;
300
301     QFixed defWidth = widths[0];
302     //qDebug("defWidth=%d, scale=%f", defWidth.toInt(), scale.toReal());
303     for (int i = 0; i < nGlyphs(); ++i) {
304         if (defWidth != widths[i])
305             defWidth = 0;
306     }
307     if (defWidth > 0) {
308         s << "/DW " << (defWidth*scale).toInt();
309     } else {
310         s << "/W [";
311         for (int g = 0; g < nGlyphs();) {
312             QFixed w = widths[g];
313             int start = g;
314             int startLinear = 0;
315             ++g;
316             while (g < nGlyphs()) {
317                 QFixed nw = widths[g];
318                 if (nw == w) {
319                 if (!startLinear)
320                     startLinear = g - 1;
321                 } else {
322                     if (startLinear > 0 && g - startLinear >= 10)
323                         break;
324                     startLinear = 0;
325                 }
326                 w = nw;
327                 ++g;
328             }
329             // qDebug("start=%x startLinear=%x g-1=%x",start,startLinear,g-1);
330             if (g - startLinear < 10)
331                 startLinear = 0;
332             int endnonlinear = startLinear ? startLinear : g;
333             // qDebug("    startLinear=%x endnonlinear=%x", startLinear,endnonlinear);
334             if (endnonlinear > start) {
335                 s << start << '[';
336                 for (int i = start; i < endnonlinear; ++i)
337                     s << (widths[i]*scale).toInt();
338                 s << "]\n";
339             }
340             if (startLinear)
341                 s << startLinear << g - 1 << (widths[startLinear]*scale).toInt() << '\n';
342         }
343         s << "]\n";
344     }
345     return width;
346 }
347
348 static void checkRanges(QPdf::ByteStream &ts, QByteArray &ranges, int &nranges)
349 {
350     if (++nranges > 100) {
351         ts << nranges << "beginbfrange\n"
352            << ranges << "endbfrange\n";
353         ranges = QByteArray();
354         nranges = 0;
355     }
356 }
357
358 QVector<int> QFontSubset::getReverseMap() const
359 {
360     QVector<int> reverseMap;
361     reverseMap.resize(0x10000);
362     for (uint i = 0; i < 0x10000; ++i)
363         reverseMap[i] = 0;
364     QGlyphLayoutArray<10> glyphs;
365     for (uint uc = 0; uc < 0x10000; ++uc) {
366         QChar ch(uc);
367         int nglyphs = 10;
368         fontEngine->stringToCMap(&ch, 1, &glyphs, &nglyphs, QTextEngine::GlyphIndicesOnly);
369         int idx = glyph_indices.indexOf(glyphs.glyphs[0]);
370         if (idx >= 0 && !reverseMap.at(idx))
371             reverseMap[idx] = uc;
372     }
373     return reverseMap;
374 }
375
376 QByteArray QFontSubset::createToUnicodeMap() const
377 {
378     QVector<int> reverseMap = getReverseMap();
379
380     QByteArray touc;
381     QPdf::ByteStream ts(&touc);
382     ts << "/CIDInit /ProcSet findresource begin\n"
383         "12 dict begin\n"
384         "begincmap\n"
385         "/CIDSystemInfo << /Registry (Adobe) /Ordering (UCS) /Supplement 0 >> def\n"
386         "/CMapName /Adobe-Identity-UCS def\n"
387         "/CMapType 2 def\n"
388         "1 begincodespacerange\n"
389         "<0000> <FFFF>\n"
390         "endcodespacerange\n";
391
392     int nranges = 1;
393     QByteArray ranges = "<0000> <0000> <0000>\n";
394     QPdf::ByteStream s(&ranges);
395
396     char buf[5];
397     for (int g = 1; g < nGlyphs(); ) {
398         int uc0 = reverseMap.at(g);
399         if (!uc0) {
400             ++g;
401             continue;
402         }
403         int start = g;
404         int startLinear = 0;
405         ++g;
406         while (g < nGlyphs()) {
407             int uc = reverseMap[g];
408             // cmaps can't have the high byte changing within one range, so we need to break on that as well
409             if (!uc || (g>>8) != (start >> 8))
410                 break;
411             if (uc == uc0 + 1) {
412                 if (!startLinear)
413                     startLinear = g - 1;
414             } else {
415                 if (startLinear > 0 && g - startLinear >= 10)
416                     break;
417                 startLinear = 0;
418             }
419             uc0 = uc;
420             ++g;
421         }
422         // qDebug("start=%x startLinear=%x g-1=%x",start,startLinear,g-1);
423         if (g - startLinear < 10)
424             startLinear = 0;
425         int endnonlinear = startLinear ? startLinear : g;
426         // qDebug("    startLinear=%x endnonlinear=%x", startLinear,endnonlinear);
427         if (endnonlinear > start) {
428             s << '<' << QPdf::toHex((ushort)start, buf) << "> <";
429             s << QPdf::toHex((ushort)(endnonlinear - 1), buf) << "> ";
430             if (endnonlinear == start + 1) {
431                 s << '<' << QPdf::toHex((ushort)reverseMap[start], buf) << ">\n";
432             } else {
433                 s << '[';
434                 for (int i = start; i < endnonlinear; ++i) {
435                     s << '<' << QPdf::toHex((ushort)reverseMap[i], buf) << "> ";
436                 }
437                 s << "]\n";
438             }
439             checkRanges(ts, ranges, nranges);
440         }
441         if (startLinear) {
442             while (startLinear < g) {
443                 int len = g - startLinear;
444                 int uc_start = reverseMap[startLinear];
445                 int uc_end = uc_start + len - 1;
446                 if ((uc_end >> 8) != (uc_start >> 8))
447                     len = 256 - (uc_start & 0xff);
448                 s << '<' << QPdf::toHex((ushort)startLinear, buf) << "> <";
449                 s << QPdf::toHex((ushort)(startLinear + len - 1), buf) << "> ";
450                 s << '<' << QPdf::toHex((ushort)reverseMap[startLinear], buf) << ">\n";
451                 checkRanges(ts, ranges, nranges);
452                 startLinear += len;
453             }
454         }
455     }
456     if (nranges) {
457         ts << nranges << "beginbfrange\n"
458            << ranges << "endbfrange\n";
459     }
460     ts << "endcmap\n"
461         "CMapName currentdict /CMap defineresource pop\n"
462         "end\n"
463         "end\n";
464
465     return touc;
466 }
467
468 int QFontSubset::addGlyph(int index)
469 {
470     int idx = glyph_indices.indexOf(index);
471     if (idx < 0) {
472         idx = glyph_indices.size();
473         glyph_indices.append(index);
474     }
475     return idx;
476 }
477
478
479 // ------------------------------ Truetype generation ----------------------------------------------
480
481 typedef qint16 F2DOT14;
482 typedef quint32 Tag;
483 typedef quint16 GlyphID;
484 typedef quint16 Offset;
485
486
487 class QTtfStream {
488 public:
489     QTtfStream(QByteArray &ba) : data((uchar *)ba.data()) { start = data; }
490     QTtfStream &operator <<(quint8 v) { *data = v; ++data; return *this; }
491     QTtfStream &operator <<(quint16 v) { qToBigEndian(v, data); data += sizeof(v); return *this; }
492     QTtfStream &operator <<(quint32 v) { qToBigEndian(v, data); data += sizeof(v); return *this; }
493     QTtfStream &operator <<(qint8 v) { *data = quint8(v); ++data; return *this; }
494     QTtfStream &operator <<(qint16 v) { qToBigEndian(v, data); data += sizeof(v); return *this; }
495     QTtfStream &operator <<(qint32 v) { qToBigEndian(v, data); data += sizeof(v); return *this; }
496     QTtfStream &operator <<(qint64 v) { qToBigEndian(v, data); data += sizeof(v); return *this; }
497
498     int offset() const { return data - start; }
499     void setOffset(int o) { data = start + o; }
500     void align4() { while (offset() & 3) { *data = '\0'; ++data; } }
501 private:
502     uchar *data;
503     uchar *start;
504 };
505
506 struct QTtfTable {
507     Tag tag;
508     QByteArray data;
509 };
510 Q_DECLARE_TYPEINFO(QTtfTable, Q_MOVABLE_TYPE);
511
512
513 struct qttf_head_table {
514     qint32 font_revision;
515     quint16 flags;
516     qint64 created;
517     qint64 modified;
518     qint16 xMin;
519     qint16 yMin;
520     qint16 xMax;
521     qint16 yMax;
522     quint16 macStyle;
523     qint16 indexToLocFormat;
524 };
525
526
527 struct qttf_hhea_table {
528     qint16 ascender;
529     qint16 descender;
530     qint16 lineGap;
531     quint16 maxAdvanceWidth;
532     qint16 minLeftSideBearing;
533     qint16 minRightSideBearing;
534     qint16 xMaxExtent;
535     quint16 numberOfHMetrics;
536 };
537
538
539 struct qttf_maxp_table {
540     quint16 numGlyphs;
541     quint16 maxPoints;
542     quint16 maxContours;
543     quint16 maxCompositePoints;
544     quint16 maxCompositeContours;
545     quint16 maxComponentElements;
546     quint16 maxComponentDepth;
547 };
548
549 struct qttf_name_table {
550     QString copyright;
551     QString family;
552     QString subfamily;
553     QString postscript_name;
554 };
555
556
557 static QTtfTable generateHead(const qttf_head_table &head);
558 static QTtfTable generateHhea(const qttf_hhea_table &hhea);
559 static QTtfTable generateMaxp(const qttf_maxp_table &maxp);
560 static QTtfTable generateName(const qttf_name_table &name);
561
562 struct qttf_font_tables
563 {
564     qttf_head_table head;
565     qttf_hhea_table hhea;
566     qttf_maxp_table maxp;
567 };
568
569
570 struct QTtfGlyph {
571     quint16 index;
572     qint16 xMin;
573     qint16 xMax;
574     qint16 yMin;
575     qint16 yMax;
576     quint16 advanceWidth;
577     qint16 lsb;
578     quint16 numContours;
579     quint16 numPoints;
580     QByteArray data;
581 };
582 Q_DECLARE_TYPEINFO(QTtfGlyph, Q_MOVABLE_TYPE);
583
584 static QTtfGlyph generateGlyph(int index, const QPainterPath &path, qreal advance, qreal lsb, qreal ppem);
585 // generates glyf, loca and hmtx
586 static QList<QTtfTable> generateGlyphTables(qttf_font_tables &tables, const QList<QTtfGlyph> &_glyphs);
587
588 static QByteArray bindFont(const QList<QTtfTable>& _tables);
589
590
591 static quint32 checksum(const QByteArray &table)
592 {
593     quint32 sum = 0;
594     int offset = 0;
595     const uchar *d = (uchar *)table.constData();
596     while (offset <= table.size()-3) {
597         sum += qFromBigEndian<quint32>(d + offset);
598         offset += 4;
599     }
600     int shift = 24;
601     quint32 x = 0;
602     while (offset < table.size()) {
603         x |= ((quint32)d[offset]) << shift;
604         ++offset;
605         shift -= 8;
606     }
607     sum += x;
608
609     return sum;
610 }
611
612 static QTtfTable generateHead(const qttf_head_table &head)
613 {
614     const int head_size = 54;
615     QTtfTable t;
616     t.tag = MAKE_TAG('h', 'e', 'a', 'd');
617     t.data.resize(head_size);
618
619     QTtfStream s(t.data);
620
621 // qint32  Table version number  0x00010000 for version 1.0.
622 // qint32  fontRevision  Set by font manufacturer.
623     s << qint32(0x00010000)
624       << head.font_revision
625 // quint32  checkSumAdjustment  To compute: set it to 0, sum the entire font as quint32, then store 0xB1B0AFBA - sum.
626       << quint32(0)
627 // quint32  magicNumber  Set to 0x5F0F3CF5.
628       << quint32(0x5F0F3CF5)
629 // quint16  flags  Bit 0: Baseline for font at y=0;
630 // Bit 1: Left sidebearing point at x=0;
631 // Bit 2: Instructions may depend on point size;
632 // Bit 3: Force ppem to integer values for all internal scaler math; may use fractional ppem sizes if this bit is clear;
633 // Bit 4: Instructions may alter advance width (the advance widths might not scale linearly);
634 // Bits 5-10: These should be set according to  Apple's specification . However, they are not implemented in OpenType.
635 // Bit 11: Font data is 'lossless,' as a result of having been compressed and decompressed with the Agfa MicroType Express engine.
636 // Bit 12: Font converted (produce compatible metrics)
637 // Bit 13: Font optimized for ClearType
638 // Bit 14: Reserved, set to 0
639 // Bit 15: Reserved, set to 0
640       << quint16(0)
641
642 // quint16  unitsPerEm  Valid range is from 16 to 16384. This value should be a power of 2 for fonts that have TrueType outlines.
643       << quint16(2048)
644 // qint64  created  Number of seconds since 12:00 midnight, January 1, 1904. 64-bit integer
645       << head.created
646 // qint64  modified  Number of seconds since 12:00 midnight, January 1, 1904. 64-bit integer
647       << head.modified
648 // qint16  xMin  For all glyph bounding boxes.
649 // qint16  yMin  For all glyph bounding boxes.
650 // qint16  xMax  For all glyph bounding boxes.
651 // qint16  yMax  For all glyph bounding boxes.
652       << head.xMin
653       << head.yMin
654       << head.xMax
655       << head.yMax
656 // quint16  macStyle  Bit 0: Bold (if set to 1);
657 // Bit 1: Italic (if set to 1)
658 // Bit 2: Underline (if set to 1)
659 // Bit 3: Outline (if set to 1)
660 // Bit 4: Shadow (if set to 1)
661 // Bit 5: Condensed (if set to 1)
662 // Bit 6: Extended (if set to 1)
663 // Bits 7-15: Reserved (set to 0).
664       << head.macStyle
665 // quint16  lowestRecPPEM  Smallest readable size in pixels.
666       << quint16(6) // just a wild guess
667 // qint16  fontDirectionHint   0: Fully mixed directional glyphs;
668       << qint16(0)
669 // 1: Only strongly left to right;
670 // 2: Like 1 but also contains neutrals;
671 // -1: Only strongly right to left;
672 // -2: Like -1 but also contains neutrals. 1
673 // qint16  indexToLocFormat  0 for short offsets, 1 for long.
674       << head.indexToLocFormat
675 // qint16  glyphDataFormat  0 for current format.
676       << qint16(0);
677
678     Q_ASSERT(s.offset() == head_size);
679     return t;
680 }
681
682
683 static QTtfTable generateHhea(const qttf_hhea_table &hhea)
684 {
685     const int hhea_size = 36;
686     QTtfTable t;
687     t.tag = MAKE_TAG('h', 'h', 'e', 'a');
688     t.data.resize(hhea_size);
689
690     QTtfStream s(t.data);
691 // qint32  Table version number  0x00010000 for version 1.0.
692     s << qint32(0x00010000)
693 // qint16  Ascender  Typographic ascent.  (Distance from baseline of highest ascender)
694       << hhea.ascender
695 // qint16  Descender  Typographic descent.  (Distance from baseline of lowest descender)
696       << hhea.descender
697 // qint16  LineGap  Typographic line gap.
698 // Negative LineGap values are treated as zero
699 // in Windows 3.1, System 6, and
700 // System 7.
701       << hhea.lineGap
702 // quint16  advanceWidthMax  Maximum advance width value in 'hmtx' table.
703       << hhea.maxAdvanceWidth
704 // qint16  minLeftSideBearing  Minimum left sidebearing value in 'hmtx' table.
705       << hhea.minLeftSideBearing
706 // qint16  minRightSideBearing  Minimum right sidebearing value; calculated as Min(aw - lsb - (xMax - xMin)).
707       << hhea.minRightSideBearing
708 // qint16  xMaxExtent  Max(lsb + (xMax - xMin)).
709       << hhea.xMaxExtent
710 // qint16  caretSlopeRise  Used to calculate the slope of the cursor (rise/run); 1 for vertical.
711       << qint16(1)
712 // qint16  caretSlopeRun  0 for vertical.
713       << qint16(0)
714 // qint16  caretOffset  The amount by which a slanted highlight on a glyph needs to be shifted to produce the best appearance. Set to 0 for non-slanted fonts
715       << qint16(0)
716 // qint16  (reserved)  set to 0
717       << qint16(0)
718 // qint16  (reserved)  set to 0
719       << qint16(0)
720 // qint16  (reserved)  set to 0
721       << qint16(0)
722 // qint16  (reserved)  set to 0
723       << qint16(0)
724 // qint16  metricDataFormat  0 for current format.
725       << qint16(0)
726 // quint16  numberOfHMetrics  Number of hMetric entries in 'hmtx' table
727       << hhea.numberOfHMetrics;
728
729     Q_ASSERT(s.offset() == hhea_size);
730     return t;
731 }
732
733
734 static QTtfTable generateMaxp(const qttf_maxp_table &maxp)
735 {
736     const int maxp_size = 32;
737     QTtfTable t;
738     t.tag = MAKE_TAG('m', 'a', 'x', 'p');
739     t.data.resize(maxp_size);
740
741     QTtfStream s(t.data);
742
743 // qint32  Table version number  0x00010000 for version 1.0.
744     s << qint32(0x00010000)
745 // quint16  numGlyphs  The number of glyphs in the font.
746       << maxp.numGlyphs
747 // quint16  maxPoints  Maximum points in a non-composite glyph.
748       << maxp.maxPoints
749 // quint16  maxContours  Maximum contours in a non-composite glyph.
750       << maxp.maxContours
751 // quint16  maxCompositePoints  Maximum points in a composite glyph.
752       << maxp.maxCompositePoints
753 // quint16  maxCompositeContours  Maximum contours in a composite glyph.
754       << maxp.maxCompositeContours
755 // quint16  maxZones  1 if instructions do not use the twilight zone (Z0), or 2 if instructions do use Z0; should be set to 2 in most cases.
756       << quint16(1) // we do not embed instructions
757 // quint16  maxTwilightPoints  Maximum points used in Z0.
758       << quint16(0)
759 // quint16  maxStorage  Number of Storage Area locations.
760       << quint16(0)
761 // quint16  maxFunctionDefs  Number of FDEFs.
762       << quint16(0)
763 // quint16  maxInstructionDefs  Number of IDEFs.
764       << quint16(0)
765 // quint16  maxStackElements  Maximum stack depth2.
766       << quint16(0)
767 // quint16  maxSizeOfInstructions  Maximum byte count for glyph instructions.
768       << quint16(0)
769 // quint16  maxComponentElements  Maximum number of components referenced at "top level" for any composite glyph.
770       << maxp.maxComponentElements
771 // quint16  maxComponentDepth  Maximum levels of recursion; 1 for simple components.
772       << maxp.maxComponentDepth;
773
774     Q_ASSERT(s.offset() == maxp_size);
775     return t;
776 }
777
778 struct QTtfNameRecord {
779     quint16 nameId;
780     QString value;
781 };
782
783 static QTtfTable generateName(const QList<QTtfNameRecord> &name);
784
785 static QTtfTable generateName(const qttf_name_table &name)
786 {
787     QList<QTtfNameRecord> list;
788     QTtfNameRecord rec;
789     rec.nameId = 0;
790     rec.value = name.copyright;
791     list.append(rec);
792     rec.nameId = 1;
793     rec.value = name.family;
794     list.append(rec);
795     rec.nameId = 2;
796     rec.value = name.subfamily;
797     list.append(rec);
798     rec.nameId = 4;
799     rec.value = name.family;
800     if (name.subfamily != QLatin1String("Regular"))
801         rec.value += QLatin1Char(' ') + name.subfamily;
802     list.append(rec);
803     rec.nameId = 6;
804     rec.value = name.postscript_name;
805     list.append(rec);
806
807     return generateName(list);
808 }
809
810 // ####### should probably generate Macintosh/Roman name entries as well
811 static QTtfTable generateName(const QList<QTtfNameRecord> &name)
812 {
813     const int char_size = 2;
814
815     QTtfTable t;
816     t.tag = MAKE_TAG('n', 'a', 'm', 'e');
817
818     const int name_size = 6 + 12*name.size();
819     int string_size = 0;
820     for (int i = 0; i < name.size(); ++i) {
821         string_size += name.at(i).value.length()*char_size;
822     }
823     t.data.resize(name_size + string_size);
824
825     QTtfStream s(t.data);
826 // quint16  format  Format selector (=0).
827     s << quint16(0)
828 // quint16  count  Number of name records.
829       << quint16(name.size())
830 // quint16  stringOffset  Offset to start of string storage (from start of table).
831       << quint16(name_size);
832 // NameRecord  nameRecord[count]  The name records where count is the number of records.
833 // (Variable)
834
835     int off = 0;
836     for (int i = 0; i < name.size(); ++i) {
837         int len = name.at(i).value.length()*char_size;
838 // quint16  platformID  Platform ID.
839 // quint16  encodingID  Platform-specific encoding ID.
840 // quint16  languageID  Language ID.
841         s << quint16(3)
842           << quint16(1)
843           << quint16(0x0409) // en_US
844 // quint16  nameId  Name ID.
845           << name.at(i).nameId
846 // quint16  length  String length (in bytes).
847           << quint16(len)
848 // quint16  offset  String offset from start of storage area (in bytes).
849           << quint16(off);
850         off += len;
851     }
852     for (int i = 0; i < name.size(); ++i) {
853         const QString &n = name.at(i).value;
854         const ushort *uc = n.utf16();
855         for (int i = 0; i < n.length(); ++i) {
856             s << quint16(*uc);
857             ++uc;
858         }
859     }
860     return t;
861 }
862
863
864 enum Flags {
865     OffCurve = 0,
866     OnCurve = (1 << 0),
867     XShortVector = (1 << 1),
868     YShortVector = (1 << 2),
869     Repeat = (1 << 3),
870     XSame = (1 << 4),
871     XShortPositive = (1 << 4),
872     YSame = (1 << 5),
873     YShortPositive = (1 << 5)
874 };
875 struct TTF_POINT {
876     qint16 x;
877     qint16 y;
878     quint8 flags;
879 };
880 Q_DECLARE_TYPEINFO(TTF_POINT, Q_PRIMITIVE_TYPE);
881
882 static void convertPath(const QPainterPath &path, QList<TTF_POINT> *points, QList<int> *endPoints, qreal ppem)
883 {
884     int numElements = path.elementCount();
885     for (int i = 0; i < numElements - 1; ++i) {
886         const QPainterPath::Element &e = path.elementAt(i);
887         TTF_POINT p;
888         p.x = qRound(e.x * 2048. / ppem);
889         p.y = qRound(-e.y * 2048. / ppem);
890         p.flags = 0;
891
892         switch(e.type) {
893         case QPainterPath::MoveToElement:
894             if (i != 0) {
895                 // see if start and end points of the last contour agree
896                 int start = endPoints->size() ? endPoints->at(endPoints->size()-1) - 1 : 0;
897                 int end = points->size() - 1;
898                 if (points->at(end).x == points->at(start).x
899                     && points->at(end).y == points->at(start).y)
900                     points->takeLast();
901                 endPoints->append(points->size() - 1);
902             }
903             // fall through
904         case QPainterPath::LineToElement:
905             p.flags = OnCurve;
906             break;
907         case QPainterPath::CurveToElement: {
908             // cubic bezier curve, we need to reduce to a list of quadratic curves
909             TTF_POINT list[3*16 + 4]; // we need max 16 subdivisions
910             list[3] = points->at(points->size() - 1);
911             list[2] = p;
912             const QPainterPath::Element &e2 = path.elementAt(++i);
913             list[1].x = qRound(e2.x * 2048. / ppem);
914             list[1].y = qRound(-e2.y * 2048. / ppem);
915             const QPainterPath::Element &e3 = path.elementAt(++i);
916             list[0].x = qRound(e3.x * 2048. / ppem);
917             list[0].y = qRound(-e3.y * 2048. / ppem);
918
919             TTF_POINT *base = list;
920
921             bool try_reduce = points->size() > 1
922                               && points->at(points->size() - 1).flags == OnCurve
923                               && points->at(points->size() - 2).flags == OffCurve;
924 //             qDebug("generating beziers:");
925             while (base >= list) {
926                 const int split_limit = 3;
927 //                 {
928 //                     qDebug("iteration:");
929 //                     TTF_POINT *x = list;
930 //                     while (x <= base + 3) {
931 //                         qDebug() << "    " << QPoint(x->x, x->y);
932 //                         ++x;
933 //                     }
934 //                 }
935                 Q_ASSERT(base - list < 3*16 + 1);
936                 // first see if we can easily reduce the cubic to a quadratic bezier curve
937                 int i1_x = base[1].x + ((base[1].x - base[0].x) >> 1);
938                 int i1_y = base[1].y + ((base[1].y - base[0].y) >> 1);
939                 int i2_x = base[2].x + ((base[2].x - base[3].x) >> 1);
940                 int i2_y = base[2].y + ((base[2].y - base[3].y) >> 1);
941 //                 qDebug() << "checking: i1=" << QPoint(i1_x, i1_y) << " i2=" << QPoint(i2_x, i2_y);
942                 if (qAbs(i1_x - i2_x) <= split_limit && qAbs(i1_y - i2_y) <= split_limit) {
943                     // got a quadratic bezier curve
944                     TTF_POINT np;
945                     np.x = (i1_x + i2_x) >> 1;
946                     np.y = (i1_y + i2_y) >> 1;
947                     if (try_reduce) {
948                         // see if we can optimize out the last onCurve point
949                         int mx = (points->at(points->size() - 2).x + base[2].x) >> 1;
950                         int my = (points->at(points->size() - 2).y + base[2].y) >> 1;
951                         if (qAbs(mx - base[3].x) <= split_limit && qAbs(my = base[3].y) <= split_limit)
952                             points->takeLast();
953                         try_reduce = false;
954                     }
955                     np.flags = OffCurve;
956                     points->append(np);
957 //                     qDebug() << "   appending offcurve point " << QPoint(np.x, np.y);
958                     base -= 3;
959                 } else {
960                     // need to split
961 //                     qDebug() << "  -> splitting";
962                     qint16 a, b, c, d;
963                     base[6].x = base[3].x;
964                     c = base[1].x;
965                     d = base[2].x;
966                     base[1].x = a = ( base[0].x + c ) >> 1;
967                     base[5].x = b = ( base[3].x + d ) >> 1;
968                     c = ( c + d ) >> 1;
969                     base[2].x = a = ( a + c ) >> 1;
970                     base[4].x = b = ( b + c ) >> 1;
971                     base[3].x = ( a + b ) >> 1;
972
973                     base[6].y = base[3].y;
974                     c = base[1].y;
975                     d = base[2].y;
976                     base[1].y = a = ( base[0].y + c ) >> 1;
977                     base[5].y = b = ( base[3].y + d ) >> 1;
978                     c = ( c + d ) >> 1;
979                     base[2].y = a = ( a + c ) >> 1;
980                     base[4].y = b = ( b + c ) >> 1;
981                     base[3].y = ( a + b ) >> 1;
982                     base += 3;
983                 }
984             }
985             p = list[0];
986             p.flags = OnCurve;
987             break;
988         }
989         case QPainterPath::CurveToDataElement:
990             Q_ASSERT(false);
991             break;
992         }
993 //         qDebug() << "   appending oncurve point " << QPoint(p.x, p.y);
994         points->append(p);
995     }
996     int start = endPoints->size() ? endPoints->at(endPoints->size()-1) + 1 : 0;
997     int end = points->size() - 1;
998     if (points->at(end).x == points->at(start).x
999         && points->at(end).y == points->at(start).y)
1000         points->takeLast();
1001     endPoints->append(points->size() - 1);
1002 }
1003
1004 static void getBounds(const QList<TTF_POINT> &points, qint16 *xmin, qint16 *xmax, qint16 *ymin, qint16 *ymax)
1005 {
1006     *xmin = points.at(0).x;
1007     *xmax = *xmin;
1008     *ymin = points.at(0).y;
1009     *ymax = *ymin;
1010
1011     for (int i = 1; i < points.size(); ++i) {
1012         *xmin = qMin(*xmin, points.at(i).x);
1013         *xmax = qMax(*xmax, points.at(i).x);
1014         *ymin = qMin(*ymin, points.at(i).y);
1015         *ymax = qMax(*ymax, points.at(i).y);
1016     }
1017 }
1018
1019 static int convertToRelative(QList<TTF_POINT> *points)
1020 {
1021     // convert points to relative and setup flags
1022 //     qDebug() << "relative points:";
1023     qint16 prev_x = 0;
1024     qint16 prev_y = 0;
1025     int point_array_size = 0;
1026     for (int i = 0; i < points->size(); ++i) {
1027         const int x = points->at(i).x;
1028         const int y = points->at(i).y;
1029         TTF_POINT rel;
1030         rel.x = x - prev_x;
1031         rel.y = y - prev_y;
1032         rel.flags = points->at(i).flags;
1033         Q_ASSERT(rel.flags < 2);
1034         if (!rel.x) {
1035             rel.flags |= XSame;
1036         } else if (rel.x > 0 && rel.x < 256) {
1037             rel.flags |= XShortVector|XShortPositive;
1038             point_array_size++;
1039         } else if (rel.x < 0 && rel.x > -256) {
1040             rel.flags |= XShortVector;
1041             rel.x = -rel.x;
1042             point_array_size++;
1043         } else {
1044             point_array_size += 2;
1045         }
1046         if (!rel.y) {
1047             rel.flags |= YSame;
1048         } else if (rel.y > 0 && rel.y < 256) {
1049             rel.flags |= YShortVector|YShortPositive;
1050             point_array_size++;
1051         } else if (rel.y < 0 && rel.y > -256) {
1052             rel.flags |= YShortVector;
1053             rel.y = -rel.y;
1054             point_array_size++;
1055         } else {
1056             point_array_size += 2;
1057         }
1058         (*points)[i] = rel;
1059 // #define toString(x) ((rel.flags & x) ? #x : "")
1060 //         qDebug() << "    " << QPoint(rel.x, rel.y) << "flags="
1061 //                  << toString(OnCurve) << toString(XShortVector)
1062 //                  << (rel.flags & XShortVector ? toString(XShortPositive) : toString(XSame))
1063 //                  << toString(YShortVector)
1064 //                  << (rel.flags & YShortVector ? toString(YShortPositive) : toString(YSame));
1065
1066         prev_x = x;
1067         prev_y = y;
1068     }
1069     return point_array_size;
1070 }
1071
1072 static void getGlyphData(QTtfGlyph *glyph, const QList<TTF_POINT> &points, const QList<int> &endPoints, int point_array_size)
1073 {
1074     const int max_size = 5*sizeof(qint16) // header
1075                          + endPoints.size()*sizeof(quint16) // end points of contours
1076                          + sizeof(quint16) // instruction length == 0
1077                          + points.size()*(1) // flags
1078                          + point_array_size; // coordinates
1079
1080     glyph->data.resize(max_size);
1081
1082     QTtfStream s(glyph->data);
1083     s << qint16(endPoints.size())
1084       << glyph->xMin << glyph->yMin << glyph->xMax << glyph->yMax;
1085
1086     for (int i = 0; i < endPoints.size(); ++i)
1087         s << quint16(endPoints.at(i));
1088     s << quint16(0); // instruction length
1089
1090     // emit flags
1091     for (int i = 0; i < points.size(); ++i)
1092         s << quint8(points.at(i).flags);
1093     // emit points
1094     for (int i = 0; i < points.size(); ++i) {
1095         quint8 flags = points.at(i).flags;
1096         qint16 x = points.at(i).x;
1097
1098         if (flags & XShortVector)
1099             s << quint8(x);
1100         else if (!(flags & XSame))
1101             s << qint16(x);
1102     }
1103     for (int i = 0; i < points.size(); ++i) {
1104         quint8 flags = points.at(i).flags;
1105         qint16 y = points.at(i).y;
1106
1107         if (flags & YShortVector)
1108             s << quint8(y);
1109         else if (!(flags & YSame))
1110             s << qint16(y);
1111     }
1112
1113 //     qDebug() << "offset=" << s.offset() << "max_size=" << max_size << "point_array_size=" << point_array_size;
1114     Q_ASSERT(s.offset() == max_size);
1115
1116     glyph->numContours = endPoints.size();
1117     glyph->numPoints = points.size();
1118 }
1119
1120 static QTtfGlyph generateGlyph(int index, const QPainterPath &path, qreal advance, qreal lsb, qreal ppem)
1121 {
1122     QList<TTF_POINT> points;
1123     QList<int> endPoints;
1124     QTtfGlyph glyph;
1125     glyph.index = index;
1126     glyph.advanceWidth = qRound(advance * 2048. / ppem);
1127     glyph.lsb = qRound(lsb * 2048. / ppem);
1128
1129     if (!path.elementCount()) {
1130         //qDebug("glyph %d is empty", index);
1131         lsb = 0;
1132         glyph.xMin = glyph.xMax = glyph.yMin = glyph.yMax = 0;
1133         glyph.numContours = 0;
1134         glyph.numPoints = 0;
1135         return glyph;
1136     }
1137
1138     convertPath(path, &points, &endPoints, ppem);
1139
1140 //     qDebug() << "number of contours=" << endPoints.size();
1141 //     for (int i = 0; i < points.size(); ++i)
1142 //         qDebug() << "  point[" << i << "] = " << QPoint(points.at(i).x, points.at(i).y) << " flags=" << points.at(i).flags;
1143 //     qDebug() << "endPoints:";
1144 //     for (int i = 0; i < endPoints.size(); ++i)
1145 //         qDebug() << endPoints.at(i);
1146
1147     getBounds(points, &glyph.xMin, &glyph.xMax, &glyph.yMin, &glyph.yMax);
1148     int point_array_size = convertToRelative(&points);
1149     getGlyphData(&glyph, points, endPoints, point_array_size);
1150     return glyph;
1151 }
1152
1153 Q_STATIC_GLOBAL_OPERATOR bool operator <(const QTtfGlyph &g1, const QTtfGlyph &g2)
1154 {
1155     return g1.index < g2.index;
1156 }
1157
1158 static QList<QTtfTable> generateGlyphTables(qttf_font_tables &tables, const QList<QTtfGlyph> &_glyphs)
1159 {
1160     const int max_size_small = 65536*2;
1161     QList<QTtfGlyph> glyphs = _glyphs;
1162     qSort(glyphs);
1163
1164     Q_ASSERT(tables.maxp.numGlyphs == glyphs.at(glyphs.size()-1).index + 1);
1165     int nGlyphs = tables.maxp.numGlyphs;
1166
1167     int glyf_size = 0;
1168     for (int i = 0; i < glyphs.size(); ++i)
1169         glyf_size += (glyphs.at(i).data.size() + 3) & ~3;
1170
1171     tables.head.indexToLocFormat = glyf_size < max_size_small ? 0 : 1;
1172     tables.hhea.numberOfHMetrics = nGlyphs;
1173
1174     QTtfTable glyf;
1175     glyf.tag = MAKE_TAG('g', 'l', 'y', 'f');
1176
1177     QTtfTable loca;
1178     loca.tag = MAKE_TAG('l', 'o', 'c', 'a');
1179     loca.data.resize(glyf_size < max_size_small ? (nGlyphs+1)*sizeof(quint16) : (nGlyphs+1)*sizeof(quint32));
1180     QTtfStream ls(loca.data);
1181
1182     QTtfTable hmtx;
1183     hmtx.tag = MAKE_TAG('h', 'm', 't', 'x');
1184     hmtx.data.resize(nGlyphs*4);
1185     QTtfStream hs(hmtx.data);
1186
1187     int pos = 0;
1188     for (int i = 0; i < nGlyphs; ++i) {
1189         int gpos = glyf.data.size();
1190         quint16 advance = 0;
1191         qint16 lsb = 0;
1192
1193         if (glyphs[pos].index == i) {
1194             // emit glyph
1195 //             qDebug("emitting glyph %d: size=%d", i, glyphs.at(i).data.size());
1196             glyf.data += glyphs.at(pos).data;
1197             while (glyf.data.size() & 1)
1198                 glyf.data.append('\0');
1199             advance = glyphs.at(pos).advanceWidth;
1200             lsb = glyphs.at(pos).lsb;
1201             ++pos;
1202         }
1203         if (glyf_size < max_size_small) {
1204             // use short loca format
1205             ls << quint16(gpos>>1);
1206         } else {
1207             // use long loca format
1208             ls << quint32(gpos);
1209         }
1210         hs << advance
1211            << lsb;
1212     }
1213     if (glyf_size < max_size_small) {
1214         // use short loca format
1215         ls << quint16(glyf.data.size()>>1);
1216     } else {
1217         // use long loca format
1218         ls << quint32(glyf.data.size());
1219     }
1220
1221     Q_ASSERT(loca.data.size() == ls.offset());
1222     Q_ASSERT(hmtx.data.size() == hs.offset());
1223
1224     QList<QTtfTable> list;
1225     list.append(glyf);
1226     list.append(loca);
1227     list.append(hmtx);
1228     return list;
1229 }
1230
1231 Q_STATIC_GLOBAL_OPERATOR bool operator <(const QTtfTable &t1, const QTtfTable &t2)
1232 {
1233     return t1.tag < t2.tag;
1234 }
1235
1236 static QByteArray bindFont(const QList<QTtfTable>& _tables)
1237 {
1238     QList<QTtfTable> tables = _tables;
1239
1240     qSort(tables);
1241
1242     QByteArray font;
1243     const int header_size = sizeof(qint32) + 4*sizeof(quint16);
1244     const int directory_size = 4*sizeof(quint32)*tables.size();
1245     font.resize(header_size + directory_size);
1246
1247     int log2 = 0;
1248     int pow = 1;
1249     int n = tables.size() >> 1;
1250     while (n) {
1251         ++log2;
1252         pow <<= 1;
1253         n >>= 1;
1254     }
1255
1256     quint32 head_offset = 0;
1257     {
1258         QTtfStream f(font);
1259 // Offset Table
1260 // Type  Name  Description
1261 //   qint32  sfnt version  0x00010000 for version 1.0.
1262 //   quint16   numTables  Number of tables.
1263 //   quint16   searchRange  (Maximum power of 2 <= numTables) x 16.
1264 //   quint16   entrySelector  Log2(maximum power of 2 <= numTables).
1265 //   quint16   rangeShift  NumTables x 16-searchRange.
1266         f << qint32(0x00010000)
1267           << quint16(tables.size())
1268           << quint16(16*pow)
1269           << quint16(log2)
1270           << quint16(16*(tables.size() - pow));
1271
1272 // Table Directory
1273 // Type  Name  Description
1274 //   quint32  tag  4 -byte identifier.
1275 //   quint32  checkSum  CheckSum for this table.
1276 //   quint32  offset  Offset from beginning of TrueType font file.
1277 //   quint32  length  Length of this table.
1278         quint32 table_offset = header_size + directory_size;
1279         for (int i = 0; i < tables.size(); ++i) {
1280             const QTtfTable &t = tables.at(i);
1281             const quint32 size = (t.data.size() + 3) & ~3;
1282             if (t.tag == MAKE_TAG('h', 'e', 'a', 'd'))
1283                 head_offset = table_offset;
1284             f << t.tag
1285               << checksum(t.data)
1286               << table_offset
1287               << t.data.size();
1288             table_offset += size;
1289 #define TAG(x) char(t.tag >> 24) << char((t.tag >> 16) & 0xff) << char((t.tag >> 8) & 0xff) << char(t.tag & 0xff)
1290             //qDebug() << "table " << TAG(t.tag) << "has size " << t.data.size() << "stream at " << f.offset();
1291         }
1292     }
1293     for (int i = 0; i < tables.size(); ++i) {
1294         const QByteArray &t = tables.at(i).data;
1295         font += t;
1296         int s = t.size();
1297         while (s & 3) { font += '\0'; ++s; }
1298     }
1299
1300     if (!head_offset) {
1301         qWarning("QFontSubset: Font misses 'head' table");
1302         return QByteArray();
1303     }
1304
1305     // calculate the fonts checksum and qToBigEndian into 'head's checksum_adjust
1306     quint32 checksum_adjust = 0xB1B0AFBA - checksum(font);
1307     qToBigEndian(checksum_adjust, (uchar *)font.data() + head_offset + 8);
1308
1309     return font;
1310 }
1311
1312
1313 /*
1314   PDF requires the following tables:
1315
1316   head, hhea, loca, maxp, cvt , prep, glyf, hmtx, fpgm
1317
1318   This means we don't have to add a os/2, post or name table. cvt , prep and fpgm could be empty
1319   if really required.
1320 */
1321
1322 QByteArray QFontSubset::toTruetype() const
1323 {
1324     qttf_font_tables font;
1325     memset(&font, 0, sizeof(qttf_font_tables));
1326
1327     qreal ppem = fontEngine->fontDef.pixelSize;
1328 #define TO_TTF(x) qRound(x * 2048. / ppem)
1329     QList<QTtfGlyph> glyphs;
1330
1331     QFontEngine::Properties properties = fontEngine->properties();
1332     // initialize some stuff needed in createWidthArray
1333     emSquare = 2048;
1334     widths.resize(nGlyphs());
1335
1336     // head table
1337     font.head.font_revision = 0x00010000;
1338     font.head.flags = (1 << 2) | (1 << 4);
1339     font.head.created = 0; // ###
1340     font.head.modified = 0; // ###
1341     font.head.xMin = SHRT_MAX;
1342     font.head.xMax = SHRT_MIN;
1343     font.head.yMin = SHRT_MAX;
1344     font.head.yMax = SHRT_MIN;
1345     font.head.macStyle = (fontEngine->fontDef.weight > QFont::Normal) ? 1 : 0;
1346     font.head.macStyle |= (fontEngine->fontDef.styleHint != QFont::StyleNormal) ? 1 : 0;
1347
1348     // hhea table
1349     font.hhea.ascender = qRound(properties.ascent);
1350     font.hhea.descender = -qRound(properties.descent);
1351     font.hhea.lineGap = qRound(properties.leading);
1352     font.hhea.maxAdvanceWidth = TO_TTF(fontEngine->maxCharWidth());
1353     font.hhea.minLeftSideBearing = TO_TTF(fontEngine->minLeftBearing());
1354     font.hhea.minRightSideBearing = TO_TTF(fontEngine->minRightBearing());
1355     font.hhea.xMaxExtent = SHRT_MIN;
1356
1357     font.maxp.numGlyphs = 0;
1358     font.maxp.maxPoints = 0;
1359     font.maxp.maxContours = 0;
1360     font.maxp.maxCompositePoints = 0;
1361     font.maxp.maxCompositeContours = 0;
1362     font.maxp.maxComponentElements = 0;
1363     font.maxp.maxComponentDepth = 0;
1364     font.maxp.numGlyphs = nGlyphs();
1365
1366
1367
1368     uint sumAdvances = 0;
1369     for (int i = 0; i < nGlyphs(); ++i) {
1370         glyph_t g = glyph_indices.at(i);
1371         QPainterPath path;
1372         glyph_metrics_t metric;
1373         fontEngine->getUnscaledGlyph(g, &path, &metric);
1374         if (noEmbed) {
1375             path = QPainterPath();
1376             if (g == 0)
1377                 path.addRect(QRectF(0, 0, 1000, 1000));
1378         }
1379         QTtfGlyph glyph = generateGlyph(i, path, metric.xoff.toReal(), metric.x.toReal(), properties.emSquare.toReal());
1380
1381         font.head.xMin = qMin(font.head.xMin, glyph.xMin);
1382         font.head.xMax = qMax(font.head.xMax, glyph.xMax);
1383         font.head.yMin = qMin(font.head.yMin, glyph.yMin);
1384         font.head.yMax = qMax(font.head.yMax, glyph.yMax);
1385
1386         font.hhea.xMaxExtent = qMax(font.hhea.xMaxExtent, (qint16)(glyph.lsb + glyph.xMax - glyph.xMin));
1387
1388         font.maxp.maxPoints = qMax(font.maxp.maxPoints, glyph.numPoints);
1389         font.maxp.maxContours = qMax(font.maxp.maxContours, glyph.numContours);
1390
1391         if (glyph.xMax > glyph.xMin)
1392             sumAdvances += glyph.xMax - glyph.xMin;
1393
1394 //         qDebug("adding glyph %d size=%d", glyph.index, glyph.data.size());
1395         glyphs.append(glyph);
1396         widths[i] = glyph.advanceWidth;
1397     }
1398
1399
1400     QList<QTtfTable> tables = generateGlyphTables(font, glyphs);
1401     tables.append(generateHead(font.head));
1402     tables.append(generateHhea(font.hhea));
1403     tables.append(generateMaxp(font.maxp));
1404     // name
1405     QTtfTable name_table;
1406     name_table.tag = MAKE_TAG('n', 'a', 'm', 'e');
1407     if (!noEmbed)
1408         name_table.data = fontEngine->getSfntTable(name_table.tag);
1409     if (name_table.data.isEmpty()) {
1410         qttf_name_table name;
1411         if (noEmbed)
1412             name.copyright = QLatin1String("Fake font");
1413         else
1414             name.copyright = QLatin1String(properties.copyright);
1415         name.family = fontEngine->fontDef.family;
1416         name.subfamily = QLatin1String("Regular"); // ######
1417         name.postscript_name = QLatin1String(properties.postscriptName);
1418         name_table = generateName(name);
1419     }
1420     tables.append(name_table);
1421
1422     if (!noEmbed) {
1423         QTtfTable os2;
1424         os2.tag = MAKE_TAG('O', 'S', '/', '2');
1425         os2.data = fontEngine->getSfntTable(os2.tag);
1426         if (!os2.data.isEmpty())
1427             tables.append(os2);
1428     }
1429
1430     return bindFont(tables);
1431 }
1432
1433 QT_END_NAMESPACE