ufont_ttf.c 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849
  1. /* Minimal fixed-point TrueType parser and rasterizer.
  2. *
  3. * No floats, no hinting, no CFF. Supports the tables and glyph forms that the
  4. * Latin-1 Arimo/Liberation subsets use: simple and composite glyphs, cmap
  5. * format 4, short/long loca, hmtx advances. Coordinates are scaled to 26.6
  6. * pixels; coverage is 4x vertical supersampling with exact horizontal spans.
  7. */
  8. #include "ufont_internal.h"
  9. #include <string.h>
  10. #define TTF_MAX_EDGES 2048
  11. struct ttf_point {
  12. int x, y;
  13. unsigned char on;
  14. };
  15. struct ttf_outline {
  16. int npoints;
  17. int ncontours;
  18. unsigned short ends[UFONT_MAX_CONTOURS];
  19. struct ttf_point points[UFONT_MAX_POINTS];
  20. };
  21. struct ttf_seq_point {
  22. int x, y;
  23. unsigned char on;
  24. };
  25. struct ttf_edge {
  26. int x0, y0, x1, y1;
  27. signed char dir;
  28. };
  29. static struct ttf_outline comp_outline[4];
  30. static struct ttf_seq_point seq_points[UFONT_MAX_POINTS * 2];
  31. static struct ttf_edge edges[TTF_MAX_EDGES];
  32. static int n_edges;
  33. static unsigned int be16(const unsigned char *p)
  34. {
  35. return ((unsigned int)p[0] << 8) | p[1];
  36. }
  37. static int sbe16(const unsigned char *p)
  38. {
  39. return (int)(short)be16(p);
  40. }
  41. static unsigned int be32(const unsigned char *p)
  42. {
  43. return ((unsigned int)p[0] << 24) | ((unsigned int)p[1] << 16) |
  44. ((unsigned int)p[2] << 8) | p[3];
  45. }
  46. static int tag_eq(const unsigned char *p, const char *tag)
  47. {
  48. return p[0] == (unsigned char)tag[0] &&
  49. p[1] == (unsigned char)tag[1] &&
  50. p[2] == (unsigned char)tag[2] &&
  51. p[3] == (unsigned char)tag[3];
  52. }
  53. static const unsigned char *find_table(const unsigned char *data,
  54. unsigned int len, const char *tag,
  55. unsigned int *out_len)
  56. {
  57. unsigned int n, i;
  58. const unsigned char *dir;
  59. if (len < 12)
  60. return 0;
  61. n = be16(data + 4);
  62. dir = data + 12;
  63. if (n > 64 || 12u + n * 16u > len)
  64. return 0;
  65. for (i = 0; i < n; i++) {
  66. const unsigned char *r = dir + i * 16;
  67. unsigned int off = be32(r + 8);
  68. unsigned int l = be32(r + 12);
  69. if (!tag_eq(r, tag))
  70. continue;
  71. if (off > len || l > len - off)
  72. return 0;
  73. if (out_len)
  74. *out_len = l;
  75. return data + off;
  76. }
  77. return 0;
  78. }
  79. int ufont_ttf_load(struct ufont_face *f, const unsigned char *data,
  80. unsigned int len)
  81. {
  82. const unsigned char *head, *maxp, *hhea, *hmtx, *loca, *glyf, *cmap;
  83. unsigned int head_len, maxp_len, hhea_len, hmtx_len, loca_len;
  84. unsigned int glyf_len, cmap_len, i, nrec;
  85. unsigned int cmap4_off = 0, cmap12_off = 0;
  86. if (len < 12)
  87. return -1;
  88. /* 0x00010000 is TrueType; "true" also appears in older files. */
  89. if (!((data[0] == 0 && data[1] == 1 && data[2] == 0 && data[3] == 0) ||
  90. (data[0] == 't' && data[1] == 'r' && data[2] == 'u' &&
  91. data[3] == 'e')))
  92. return -1;
  93. head = find_table(data, len, "head", &head_len);
  94. maxp = find_table(data, len, "maxp", &maxp_len);
  95. hhea = find_table(data, len, "hhea", &hhea_len);
  96. hmtx = find_table(data, len, "hmtx", &hmtx_len);
  97. loca = find_table(data, len, "loca", &loca_len);
  98. glyf = find_table(data, len, "glyf", &glyf_len);
  99. cmap = find_table(data, len, "cmap", &cmap_len);
  100. if (!head || !maxp || !hhea || !hmtx || !loca || !glyf || !cmap)
  101. return -1;
  102. if (head_len < 54 || maxp_len < 6 || hhea_len < 36)
  103. return -1;
  104. if (be32(head + 12) != 0x5F0F3CF5u) /* head.magicNumber */
  105. return -1;
  106. f->data = data;
  107. f->len = len;
  108. f->upem = be16(head + 18);
  109. f->loca_short = sbe16(head + 50) == 0;
  110. f->num_glyphs = be16(maxp + 4);
  111. f->ascent = sbe16(hhea + 4);
  112. f->descent = sbe16(hhea + 6);
  113. f->line_gap = sbe16(hhea + 8);
  114. f->num_hmetrics = be16(hhea + 34);
  115. if (f->upem < 16 || f->upem > 16384 || f->num_glyphs < 1 ||
  116. f->num_glyphs > 65535)
  117. return -1;
  118. if (f->num_hmetrics < 1 || f->num_hmetrics > f->num_glyphs)
  119. return -1;
  120. if (loca_len < (f->loca_short ? (unsigned int)f->num_glyphs * 2u + 2u
  121. : (unsigned int)f->num_glyphs * 4u + 4u))
  122. return -1;
  123. if (hmtx_len < (unsigned int)f->num_hmetrics * 4u)
  124. return -1;
  125. /* Pick a format 4 Unicode cmap and/or a format 12 cmap for emoji and
  126. * other supplementary-plane codepoints. */
  127. if (cmap_len < 4)
  128. return -1;
  129. nrec = be16(cmap + 2);
  130. if (nrec > 64 || 4u + nrec * 8u > cmap_len)
  131. return -1;
  132. for (i = 0; i < nrec; i++) {
  133. const unsigned char *r = cmap + 4 + i * 8;
  134. unsigned int off = be32(r + 4);
  135. unsigned int plat = be16(r);
  136. unsigned int enc = be16(r + 2);
  137. unsigned int fmt;
  138. if (off + 2 > cmap_len)
  139. continue;
  140. fmt = be16(cmap + off);
  141. if (fmt == 4) {
  142. if (!cmap4_off ||
  143. (plat == 3 && (enc == 0 || enc == 1)))
  144. cmap4_off = off;
  145. } else if (fmt == 12) {
  146. if (!cmap12_off ||
  147. (plat == 3 && enc == 10) ||
  148. (plat == 0 && enc == 4))
  149. cmap12_off = off;
  150. }
  151. }
  152. if (!cmap4_off && !cmap12_off)
  153. return -1;
  154. if (cmap4_off) {
  155. if (cmap4_off + 16 > cmap_len ||
  156. be16(cmap + cmap4_off + 2) > cmap_len - cmap4_off)
  157. return -1;
  158. }
  159. if (cmap12_off) {
  160. unsigned int groups;
  161. if (cmap12_off + 16 > cmap_len ||
  162. be32(cmap + cmap12_off + 4) > cmap_len - cmap12_off)
  163. return -1;
  164. groups = be32(cmap + cmap12_off + 12);
  165. if (groups > 65535u ||
  166. 16u + groups * 12u > cmap_len - cmap12_off)
  167. return -1;
  168. f->cmap12 = cmap + cmap12_off;
  169. f->cmap12_len = be32(cmap + cmap12_off + 4);
  170. f->cmap12_groups = groups;
  171. }
  172. f->loca = loca;
  173. f->glyf = glyf;
  174. f->glyf_len = glyf_len;
  175. f->hmtx = hmtx;
  176. f->cmap4 = cmap4_off ? cmap + cmap4_off : 0;
  177. f->cmap4_len = cmap4_off ? be16(cmap + cmap4_off + 2) : 0;
  178. return 0;
  179. }
  180. static int cmap4_lookup(const struct ufont_face *f, unsigned int cp)
  181. {
  182. const unsigned char *c = f->cmap4;
  183. unsigned int seg, i, end, start, delta, range;
  184. if (!c || f->cmap4_len < 16 || cp > 0xFFFFu)
  185. return 0;
  186. seg = be16(c + 6) / 2u;
  187. if (seg == 0 || 16u + seg * 8u > f->cmap4_len)
  188. return 0;
  189. for (i = 0; i < seg; i++) {
  190. end = be16(c + 14 + i * 2);
  191. if (cp > end)
  192. continue;
  193. start = be16(c + 16 + seg * 2 + i * 2);
  194. if (cp < start)
  195. return 0;
  196. delta = be16(c + 16 + seg * 4 + i * 2);
  197. range = be16(c + 16 + seg * 6 + i * 2);
  198. if (range == 0)
  199. return (int)((cp + delta) & 0xFFFFu);
  200. {
  201. unsigned int ro = 16u + seg * 6u + i * 2u;
  202. unsigned int addr = ro + range + (cp - start) * 2u;
  203. unsigned int g;
  204. if (addr + 2u > f->cmap4_len)
  205. return 0;
  206. g = be16(c + addr);
  207. if (g)
  208. g = (g + delta) & 0xFFFFu;
  209. return (int)g;
  210. }
  211. }
  212. return 0;
  213. }
  214. static int cmap12_lookup(const struct ufont_face *f, unsigned int cp)
  215. {
  216. const unsigned char *c = f->cmap12;
  217. unsigned int lo = 0, hi;
  218. if (!c || f->cmap12_len < 16)
  219. return 0;
  220. hi = f->cmap12_groups;
  221. while (lo < hi) {
  222. unsigned int mid = lo + (hi - lo) / 2;
  223. const unsigned char *g = c + 16u + mid * 12u;
  224. unsigned int start = be32(g);
  225. unsigned int end = be32(g + 4);
  226. unsigned int glyph = be32(g + 8);
  227. if (cp < start) {
  228. hi = mid;
  229. } else if (cp > end) {
  230. lo = mid + 1;
  231. } else {
  232. unsigned int id = glyph + (cp - start);
  233. return id <= 0xFFFFu ? (int)id : 0;
  234. }
  235. }
  236. return 0;
  237. }
  238. int ufont_ttf_glyph_index(const struct ufont_face *f, unsigned int cp)
  239. {
  240. int g;
  241. if (!f)
  242. return 0;
  243. if (cp <= 0xFFFFu) {
  244. g = cmap4_lookup(f, cp);
  245. if (g)
  246. return g;
  247. }
  248. return cmap12_lookup(f, cp);
  249. }
  250. static const unsigned char *glyph_data(const struct ufont_face *f, int glyph,
  251. unsigned int *size)
  252. {
  253. unsigned int a, b;
  254. if (glyph < 0 || glyph >= f->num_glyphs)
  255. return 0;
  256. if (f->loca_short) {
  257. a = be16(f->loca + glyph * 2u) * 2u;
  258. b = be16(f->loca + glyph * 2u + 2u) * 2u;
  259. } else {
  260. a = be32(f->loca + glyph * 4u);
  261. b = be32(f->loca + glyph * 4u + 4u);
  262. }
  263. if (b <= a || b > f->glyf_len)
  264. return 0;
  265. if (size)
  266. *size = b - a;
  267. return f->glyf + a;
  268. }
  269. int ufont_ttf_advance(const struct ufont_face *f, int glyph, int px)
  270. {
  271. unsigned int units;
  272. if (glyph < 0 || glyph >= f->num_glyphs)
  273. glyph = 0;
  274. if (glyph >= f->num_hmetrics)
  275. glyph = f->num_hmetrics - 1;
  276. units = be16(f->hmtx + glyph * 4u);
  277. return (int)((units * (unsigned int)px * 64u + (unsigned int)f->upem / 2u)
  278. / (unsigned int)f->upem);
  279. }
  280. static int load_simple(const struct ufont_face *f, const unsigned char *g,
  281. unsigned int glen, struct ttf_outline *out)
  282. {
  283. int ncontours = sbe16(g);
  284. (void)f;
  285. int i, j, npoints, flags, repeats;
  286. unsigned int off;
  287. unsigned char flag;
  288. int x, y;
  289. if (ncontours < 0 || ncontours > UFONT_MAX_CONTOURS)
  290. return -1;
  291. if (glen < 12u + (unsigned int)ncontours * 2u)
  292. return -1;
  293. out->ncontours = ncontours;
  294. for (i = 0; i < ncontours; i++)
  295. out->ends[i] = be16(g + 10 + i * 2);
  296. npoints = ncontours ? (int)out->ends[ncontours - 1] + 1 : 0;
  297. if (npoints < 0 || npoints > UFONT_MAX_POINTS)
  298. return -1;
  299. off = 10u + (unsigned int)ncontours * 2u;
  300. if (off + 2u > glen)
  301. return -1;
  302. off += 2u + be16(g + off); /* skip instructions */
  303. if (off > glen)
  304. return -1;
  305. /* Flags, with the repeat bit expanded. */
  306. {
  307. unsigned char flags_buf[UFONT_MAX_POINTS];
  308. int n = 0;
  309. while (n < npoints) {
  310. if (off >= glen)
  311. return -1;
  312. flag = g[off++];
  313. flags_buf[n++] = flag;
  314. if (flag & 0x08) {
  315. if (off >= glen)
  316. return -1;
  317. repeats = g[off++];
  318. while (repeats-- > 0 && n < npoints)
  319. flags_buf[n++] = flag;
  320. }
  321. }
  322. for (i = 0; i < npoints; i++) {
  323. flags = flags_buf[i];
  324. out->points[i].on = (flags & 0x01) != 0;
  325. out->points[i].x = 0;
  326. out->points[i].y = 0;
  327. }
  328. /* X deltas. */
  329. x = 0;
  330. for (i = 0; i < npoints; i++) {
  331. flags = flags_buf[i];
  332. if (flags & 0x02) {
  333. if (off >= glen)
  334. return -1;
  335. j = g[off++];
  336. x += (flags & 0x10) ? j : -j;
  337. } else if (!(flags & 0x10)) {
  338. if (off + 2u > glen)
  339. return -1;
  340. x += sbe16(g + off);
  341. off += 2;
  342. }
  343. out->points[i].x = x;
  344. }
  345. /* Y deltas. */
  346. y = 0;
  347. for (i = 0; i < npoints; i++) {
  348. flags = flags_buf[i];
  349. if (flags & 0x04) {
  350. if (off >= glen)
  351. return -1;
  352. j = g[off++];
  353. y += (flags & 0x20) ? j : -j;
  354. } else if (!(flags & 0x20)) {
  355. if (off + 2u > glen)
  356. return -1;
  357. y += sbe16(g + off);
  358. off += 2;
  359. }
  360. out->points[i].y = y;
  361. }
  362. }
  363. out->npoints = npoints;
  364. return 0;
  365. }
  366. static int load_glyph(const struct ufont_face *f, int glyph,
  367. struct ttf_outline *out, int depth);
  368. static int load_composite(const struct ufont_face *f, const unsigned char *g,
  369. unsigned int glen, struct ttf_outline *out, int depth)
  370. {
  371. unsigned int off = 10;
  372. int any = 0;
  373. out->npoints = 0;
  374. out->ncontours = 0;
  375. if (depth >= 4)
  376. return -1;
  377. for (;;) {
  378. unsigned int flags, comp, args[2];
  379. int dx, dy, i, a, b, c, d;
  380. struct ttf_outline *co;
  381. if (off + 4u > glen)
  382. return -1;
  383. flags = be16(g + off);
  384. comp = be16(g + off + 2);
  385. off += 4;
  386. if (flags & 0x0001) {
  387. if (off + 4u > glen)
  388. return -1;
  389. args[0] = (unsigned int)sbe16(g + off);
  390. args[1] = (unsigned int)sbe16(g + off + 2);
  391. off += 4;
  392. } else {
  393. if (off + 2u > glen)
  394. return -1;
  395. args[0] = (unsigned int)(signed char)g[off];
  396. args[1] = (unsigned int)(signed char)g[off + 1];
  397. off += 2;
  398. }
  399. a = 0x10000; b = 0; c = 0; d = 0x10000;
  400. if (flags & 0x0008) {
  401. if (off + 2u > glen)
  402. return -1;
  403. a = d = sbe16(g + off) * 4; /* F2Dot14 -> 16.16 */
  404. off += 2;
  405. } else if (flags & 0x0040) {
  406. if (off + 4u > glen)
  407. return -1;
  408. a = sbe16(g + off) * 4;
  409. d = sbe16(g + off + 2) * 4;
  410. off += 4;
  411. } else if (flags & 0x0080) {
  412. if (off + 8u > glen)
  413. return -1;
  414. a = sbe16(g + off) * 4;
  415. b = sbe16(g + off + 2) * 4;
  416. c = sbe16(g + off + 4) * 4;
  417. d = sbe16(g + off + 6) * 4;
  418. off += 8;
  419. }
  420. if (comp >= (unsigned int)f->num_glyphs ||
  421. depth + 1 >= 4)
  422. return -1;
  423. co = &comp_outline[depth + 1];
  424. if (load_glyph(f, (int)comp, co, depth + 1) != 0)
  425. return -1;
  426. /* Apply the component transform in font units. */
  427. for (i = 0; i < co->npoints; i++) {
  428. int x = co->points[i].x;
  429. int y = co->points[i].y;
  430. co->points[i].x = (a * x + c * y) >> 16;
  431. co->points[i].y = (b * x + d * y) >> 16;
  432. }
  433. dx = 0;
  434. dy = 0;
  435. if (flags & 0x0002) {
  436. dx = (int)args[0];
  437. dy = (int)args[1];
  438. if ((flags & 0x0800) && !(flags & 0x1000)) {
  439. int tx = (a * dx + c * dy) >> 16;
  440. int ty = (b * dx + d * dy) >> 16;
  441. dx = tx;
  442. dy = ty;
  443. }
  444. } else {
  445. int p1 = (int)args[0];
  446. int p2 = (int)args[1];
  447. if (p1 >= 0 && p1 < out->npoints &&
  448. p2 >= 0 && p2 < co->npoints) {
  449. dx = out->points[p1].x - co->points[p2].x;
  450. dy = out->points[p1].y - co->points[p2].y;
  451. }
  452. }
  453. if (out->npoints + co->npoints > UFONT_MAX_POINTS ||
  454. out->ncontours + co->ncontours > UFONT_MAX_CONTOURS)
  455. return -1;
  456. for (i = 0; i < co->npoints; i++) {
  457. out->points[out->npoints + i] = co->points[i];
  458. out->points[out->npoints + i].x += dx;
  459. out->points[out->npoints + i].y += dy;
  460. }
  461. for (i = 0; i < co->ncontours; i++)
  462. out->ends[out->ncontours + i] =
  463. (unsigned short)(co->ends[i] + out->npoints);
  464. out->npoints += co->npoints;
  465. out->ncontours += co->ncontours;
  466. any = 1;
  467. if (!(flags & 0x0020))
  468. break;
  469. }
  470. return any ? 0 : -1;
  471. }
  472. static int load_glyph(const struct ufont_face *f, int glyph,
  473. struct ttf_outline *out, int depth)
  474. {
  475. const unsigned char *g;
  476. unsigned int glen;
  477. int ncontours;
  478. g = glyph_data(f, glyph, &glen);
  479. if (!g)
  480. return -1;
  481. if (glen < 10)
  482. return -1;
  483. ncontours = sbe16(g);
  484. if (ncontours >= 0)
  485. return load_simple(f, g, glen, out);
  486. return load_composite(f, g, glen, out, depth);
  487. }
  488. static int scale_coord(const struct ufont_face *f, int v, int px)
  489. {
  490. return (int)(((long)v * (long)px * 64L +
  491. (long)f->upem / 2L) / (long)f->upem);
  492. }
  493. static int floor_div64(int v)
  494. {
  495. return v >= 0 ? v / 64 : -((-v + 63) / 64);
  496. }
  497. static int ceil_div64(int v)
  498. {
  499. return v >= 0 ? (v + 63) / 64 : -((-v) / 64);
  500. }
  501. int ufont_ttf_bbox(const struct ufont_face *f, int glyph, int px,
  502. int *xoff, int *yoff, int *w, int *h)
  503. {
  504. static struct ttf_outline out;
  505. int i, minx, miny, maxx, maxy, x0, y0, x1, y1;
  506. *xoff = 0;
  507. *yoff = 0;
  508. *w = 0;
  509. *h = 0;
  510. if (load_glyph(f, glyph, &out, 0) != 0 || out.npoints == 0)
  511. return 0;
  512. minx = maxx = scale_coord(f, out.points[0].x, px);
  513. miny = maxy = -scale_coord(f, out.points[0].y, px);
  514. for (i = 1; i < out.npoints; i++) {
  515. int x = scale_coord(f, out.points[i].x, px);
  516. int y = -scale_coord(f, out.points[i].y, px);
  517. if (x < minx) minx = x;
  518. if (x > maxx) maxx = x;
  519. if (y < miny) miny = y;
  520. if (y > maxy) maxy = y;
  521. }
  522. x0 = floor_div64(minx);
  523. y0 = floor_div64(miny);
  524. x1 = ceil_div64(maxx);
  525. y1 = ceil_div64(maxy);
  526. if (x1 <= x0) x1 = x0 + 1;
  527. if (y1 <= y0) y1 = y0 + 1;
  528. *xoff = x0;
  529. *yoff = y0;
  530. *w = x1 - x0;
  531. *h = y1 - y0;
  532. if (*w > 512 || *h > 512) {
  533. *w = *h = 0;
  534. return 0;
  535. }
  536. return 0;
  537. }
  538. static void add_edge(int x0, int y0, int x1, int y1)
  539. {
  540. signed char dir;
  541. if (y0 == y1 || n_edges >= TTF_MAX_EDGES)
  542. return;
  543. dir = 1;
  544. if (y0 > y1) {
  545. int t;
  546. t = x0; x0 = x1; x1 = t;
  547. t = y0; y0 = y1; y1 = t;
  548. dir = -1;
  549. }
  550. edges[n_edges].x0 = x0;
  551. edges[n_edges].y0 = y0;
  552. edges[n_edges].x1 = x1;
  553. edges[n_edges].y1 = y1;
  554. edges[n_edges].dir = dir;
  555. n_edges++;
  556. }
  557. static void flatten_quad(int x0, int y0, int cx, int cy, int x1, int y1,
  558. int depth)
  559. {
  560. long dx = (long)x1 - x0;
  561. long dy = (long)y1 - y0;
  562. long cross = dx * ((long)cy - y0) - dy * ((long)cx - x0);
  563. long lim = (dx < 0 ? -dx : dx) + (dy < 0 ? -dy : dy);
  564. if (lim < 1)
  565. lim = 1;
  566. if (cross < 0)
  567. cross = -cross;
  568. if (depth >= 8 || cross <= lim * 2L) {
  569. add_edge(x0, y0, x1, y1);
  570. return;
  571. }
  572. {
  573. int q0x = (x0 + cx) / 2, q0y = (y0 + cy) / 2;
  574. int q1x = (cx + x1) / 2, q1y = (cy + y1) / 2;
  575. int mx = (q0x + q1x) / 2, my = (q0y + q1y) / 2;
  576. flatten_quad(x0, y0, q0x, q0y, mx, my, depth + 1);
  577. flatten_quad(mx, my, q1x, q1y, x1, y1, depth + 1);
  578. }
  579. }
  580. static void build_edges(const struct ufont_face *f, int px,
  581. const struct ttf_outline *out)
  582. {
  583. int c, start = 0;
  584. n_edges = 0;
  585. for (c = 0; c < out->ncontours; c++) {
  586. int end = out->ends[c];
  587. int count = end - start + 1;
  588. int first_on = -1, i, n = 0;
  589. if (count <= 1) {
  590. start = end + 1;
  591. continue;
  592. }
  593. for (i = 0; i < count; i++)
  594. if (out->points[start + i].on) {
  595. first_on = i;
  596. break;
  597. }
  598. if (first_on < 0) {
  599. /* All off-curve: insert a midpoint between every pair
  600. * and start at the midpoint before the first point. */
  601. for (i = 0; i < count; i++) {
  602. int a = start + i;
  603. int b = start + ((i + 1) % count);
  604. if (n < (int)(sizeof(seq_points) /
  605. sizeof(seq_points[0]))) {
  606. seq_points[n].x =
  607. (out->points[a].x +
  608. out->points[b].x) / 2;
  609. seq_points[n].y =
  610. (out->points[a].y +
  611. out->points[b].y) / 2;
  612. seq_points[n].on = 1;
  613. n++;
  614. }
  615. if (n < (int)(sizeof(seq_points) /
  616. sizeof(seq_points[0]))) {
  617. seq_points[n] = (struct ttf_seq_point){
  618. out->points[b].x,
  619. out->points[b].y,
  620. out->points[b].on
  621. };
  622. n++;
  623. }
  624. }
  625. } else {
  626. /* Rotate to the first on-curve point and insert
  627. * midpoints between consecutive off-curve points. */
  628. for (i = 0; i < count; i++) {
  629. int idx = start + (first_on + i) % count;
  630. struct ttf_seq_point p;
  631. p.x = out->points[idx].x;
  632. p.y = out->points[idx].y;
  633. p.on = out->points[idx].on;
  634. if (n > 0 && !seq_points[n - 1].on && !p.on) {
  635. seq_points[n].x =
  636. (seq_points[n - 1].x + p.x) / 2;
  637. seq_points[n].y =
  638. (seq_points[n - 1].y + p.y) / 2;
  639. seq_points[n].on = 1;
  640. n++;
  641. }
  642. seq_points[n++] = p;
  643. if (n >= (int)(sizeof(seq_points) /
  644. sizeof(seq_points[0])))
  645. break;
  646. }
  647. }
  648. for (i = 0; i < n; i++) {
  649. struct ttf_seq_point a = seq_points[i];
  650. struct ttf_seq_point b = seq_points[(i + 1) % n];
  651. int ax = scale_coord(f, a.x, px);
  652. int ay = -scale_coord(f, a.y, px);
  653. int bx = scale_coord(f, b.x, px);
  654. int by = -scale_coord(f, b.y, px);
  655. if (b.on) {
  656. add_edge(ax, ay, bx, by);
  657. } else {
  658. struct ttf_seq_point d =
  659. seq_points[(i + 2) % n];
  660. int cx = bx, cy = by;
  661. int dx = scale_coord(f, d.x, px);
  662. int dy = -scale_coord(f, d.y, px);
  663. flatten_quad(ax, ay, cx, cy, dx, dy, 0);
  664. i++; /* the next point is consumed */
  665. }
  666. }
  667. start = end + 1;
  668. }
  669. }
  670. /* Add horizontal coverage of [xa, xb] (26.6, relative to xoff) to mask. */
  671. static void add_span(unsigned char *mask, int w, int h, int row,
  672. int xa, int xb)
  673. {
  674. int pa, pb, p;
  675. (void)h;
  676. if (xa < 0)
  677. xa = 0;
  678. if (xb > w * 64)
  679. xb = w * 64;
  680. if (xb <= xa)
  681. return;
  682. pa = xa / 64;
  683. pb = (xb + 63) / 64;
  684. if (pa < 0)
  685. pa = 0;
  686. if (pb > w)
  687. pb = w;
  688. for (p = pa; p < pb; p++) {
  689. int l = p * 64;
  690. int r = (p + 1) * 64;
  691. int cov;
  692. int v;
  693. if (l < xa) l = xa;
  694. if (r > xb) r = xb;
  695. cov = r - l;
  696. if (cov <= 0)
  697. continue;
  698. v = mask[row * w + p] + cov;
  699. if (v > 255)
  700. v = 255;
  701. mask[row * w + p] = (unsigned char)v;
  702. }
  703. }
  704. int ufont_ttf_raster(const struct ufont_face *f, int glyph, int px,
  705. int xoff, int yoff, int w, int h, unsigned char *mask)
  706. {
  707. static struct ttf_outline out;
  708. int row, sub;
  709. if (w <= 0 || h <= 0 || !mask)
  710. return 0;
  711. if (load_glyph(f, glyph, &out, 0) != 0 || out.npoints == 0)
  712. return 0;
  713. build_edges(f, px, &out);
  714. if (n_edges == 0)
  715. return 0;
  716. for (row = 0; row < h; row++) {
  717. for (sub = 0; sub < 4; sub++) {
  718. int sy = ((yoff + row) * 64) + sub * 16 + 8;
  719. static int xs[TTF_MAX_EDGES];
  720. static signed char dirs[TTF_MAX_EDGES];
  721. int n = 0, i, j, wind = 0, span = 0, span_x = 0;
  722. for (i = 0; i < n_edges; i++) {
  723. const struct ttf_edge *e = &edges[i];
  724. long dy, num, x;
  725. if (sy < e->y0 || sy >= e->y1)
  726. continue;
  727. dy = (long)e->y1 - e->y0;
  728. if (dy == 0)
  729. continue;
  730. num = (long)(sy - e->y0) *
  731. ((long)e->x1 - e->x0);
  732. x = e->x0 + num / dy;
  733. if (n < TTF_MAX_EDGES) {
  734. xs[n] = (int)x;
  735. dirs[n] = e->dir;
  736. n++;
  737. }
  738. }
  739. /* Insertion sort by x. */
  740. for (i = 1; i < n; i++) {
  741. int xv = xs[i];
  742. signed char dv = dirs[i];
  743. j = i - 1;
  744. while (j >= 0 && xs[j] > xv) {
  745. xs[j + 1] = xs[j];
  746. dirs[j + 1] = dirs[j];
  747. j--;
  748. }
  749. xs[j + 1] = xv;
  750. dirs[j + 1] = dv;
  751. }
  752. wind = 0;
  753. span = 0;
  754. span_x = 0;
  755. for (i = 0; i < n; i++) {
  756. if (wind == 0) {
  757. span_x = xs[i];
  758. span = 1;
  759. }
  760. wind += dirs[i];
  761. if (wind == 0 && span) {
  762. int xa = span_x - (xoff * 64);
  763. int xb = xs[i] - (xoff * 64);
  764. if (xb > xa)
  765. add_span(mask, w, h, row,
  766. xa, xb);
  767. span = 0;
  768. }
  769. }
  770. }
  771. }
  772. return 0;
  773. }