Glyf.cpp 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501
  1. /*
  2. * Copyright (c) 2020, Srimanta Barua <srimanta.barua1@gmail.com>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <LibGfx/Path.h>
  7. #include <LibGfx/Point.h>
  8. #include <LibTTF/Glyf.h>
  9. namespace TTF {
  10. extern u16 be_u16(const u8* ptr);
  11. extern u32 be_u32(const u8* ptr);
  12. extern i16 be_i16(const u8* ptr);
  13. extern float be_fword(const u8* ptr);
  14. enum class SimpleGlyfFlags {
  15. // From spec.
  16. OnCurve = 0x01,
  17. XShortVector = 0x02,
  18. YShortVector = 0x04,
  19. RepeatFlag = 0x08,
  20. XIsSameOrPositiveXShortVector = 0x10,
  21. YIsSameOrPositiveYShortVector = 0x20,
  22. // Combinations
  23. XMask = 0x12,
  24. YMask = 0x24,
  25. XLongVector = 0x00,
  26. YLongVector = 0x00,
  27. XNegativeShortVector = 0x02,
  28. YNegativeShortVector = 0x04,
  29. XPositiveShortVector = 0x12,
  30. YPositiveShortVector = 0x24,
  31. };
  32. enum class CompositeGlyfFlags {
  33. Arg1AndArg2AreWords = 0x0001,
  34. ArgsAreXYValues = 0x0002,
  35. RoundXYToGrid = 0x0004,
  36. WeHaveAScale = 0x0008,
  37. MoreComponents = 0x0020,
  38. WeHaveAnXAndYScale = 0x0040,
  39. WeHaveATwoByTwo = 0x0080,
  40. WeHaveInstructions = 0x0100,
  41. UseMyMetrics = 0x0200,
  42. OverlapCompound = 0x0400, // Not relevant - can overlap without this set
  43. ScaledComponentOffset = 0x0800,
  44. UnscaledComponentOffset = 0x1000,
  45. };
  46. class PointIterator {
  47. public:
  48. struct Item {
  49. bool on_curve;
  50. Gfx::FloatPoint point;
  51. };
  52. PointIterator(const ReadonlyBytes& slice, u16 num_points, u32 flags_offset, u32 x_offset, u32 y_offset, Gfx::AffineTransform affine)
  53. : m_slice(slice)
  54. , m_points_remaining(num_points)
  55. , m_flags_offset(flags_offset)
  56. , m_x_offset(x_offset)
  57. , m_y_offset(y_offset)
  58. , m_affine(affine)
  59. {
  60. }
  61. Optional<Item> next()
  62. {
  63. if (m_points_remaining == 0) {
  64. return {};
  65. }
  66. if (m_flags_remaining > 0) {
  67. m_flags_remaining--;
  68. } else {
  69. m_flag = m_slice[m_flags_offset++];
  70. if (m_flag & (u8)SimpleGlyfFlags::RepeatFlag) {
  71. m_flags_remaining = m_slice[m_flags_offset++];
  72. }
  73. }
  74. switch (m_flag & (u8)SimpleGlyfFlags::XMask) {
  75. case (u8)SimpleGlyfFlags::XLongVector:
  76. m_last_point.set_x(m_last_point.x() + be_i16(m_slice.offset_pointer(m_x_offset)));
  77. m_x_offset += 2;
  78. break;
  79. case (u8)SimpleGlyfFlags::XNegativeShortVector:
  80. m_last_point.set_x(m_last_point.x() - m_slice[m_x_offset++]);
  81. break;
  82. case (u8)SimpleGlyfFlags::XPositiveShortVector:
  83. m_last_point.set_x(m_last_point.x() + m_slice[m_x_offset++]);
  84. break;
  85. default:
  86. break;
  87. }
  88. switch (m_flag & (u8)SimpleGlyfFlags::YMask) {
  89. case (u8)SimpleGlyfFlags::YLongVector:
  90. m_last_point.set_y(m_last_point.y() + be_i16(m_slice.offset_pointer(m_y_offset)));
  91. m_y_offset += 2;
  92. break;
  93. case (u8)SimpleGlyfFlags::YNegativeShortVector:
  94. m_last_point.set_y(m_last_point.y() - m_slice[m_y_offset++]);
  95. break;
  96. case (u8)SimpleGlyfFlags::YPositiveShortVector:
  97. m_last_point.set_y(m_last_point.y() + m_slice[m_y_offset++]);
  98. break;
  99. default:
  100. break;
  101. }
  102. m_points_remaining--;
  103. Item ret = {
  104. .on_curve = (m_flag & (u8)SimpleGlyfFlags::OnCurve) != 0,
  105. .point = m_affine.map(m_last_point),
  106. };
  107. return ret;
  108. }
  109. private:
  110. ReadonlyBytes m_slice;
  111. u16 m_points_remaining;
  112. u8 m_flag { 0 };
  113. Gfx::FloatPoint m_last_point = { 0.0f, 0.0f };
  114. u32 m_flags_remaining = { 0 };
  115. u32 m_flags_offset;
  116. u32 m_x_offset;
  117. u32 m_y_offset;
  118. Gfx::AffineTransform m_affine;
  119. };
  120. Optional<Glyf::Glyph::ComponentIterator::Item> Glyf::Glyph::ComponentIterator::next()
  121. {
  122. if (!m_has_more) {
  123. return {};
  124. }
  125. u16 flags = be_u16(m_slice.offset_pointer(m_offset));
  126. m_offset += 2;
  127. u16 glyph_id = be_u16(m_slice.offset_pointer(m_offset));
  128. m_offset += 2;
  129. i16 arg1 = 0, arg2 = 0;
  130. if (flags & (u16)CompositeGlyfFlags::Arg1AndArg2AreWords) {
  131. arg1 = be_i16(m_slice.offset_pointer(m_offset));
  132. m_offset += 2;
  133. arg2 = be_i16(m_slice.offset_pointer(m_offset));
  134. m_offset += 2;
  135. } else {
  136. arg1 = (i8)m_slice[m_offset++];
  137. arg2 = (i8)m_slice[m_offset++];
  138. }
  139. float a = 1.0, b = 0.0, c = 0.0, d = 1.0, e = 0.0, f = 0.0;
  140. if (flags & (u16)CompositeGlyfFlags::WeHaveATwoByTwo) {
  141. a = be_fword(m_slice.offset_pointer(m_offset));
  142. m_offset += 2;
  143. b = be_fword(m_slice.offset_pointer(m_offset));
  144. m_offset += 2;
  145. c = be_fword(m_slice.offset_pointer(m_offset));
  146. m_offset += 2;
  147. d = be_fword(m_slice.offset_pointer(m_offset));
  148. m_offset += 2;
  149. } else if (flags & (u16)CompositeGlyfFlags::WeHaveAnXAndYScale) {
  150. a = be_fword(m_slice.offset_pointer(m_offset));
  151. m_offset += 2;
  152. d = be_fword(m_slice.offset_pointer(m_offset));
  153. m_offset += 2;
  154. } else if (flags & (u16)CompositeGlyfFlags::WeHaveAScale) {
  155. a = be_fword(m_slice.offset_pointer(m_offset));
  156. m_offset += 2;
  157. d = a;
  158. }
  159. // FIXME: Handle UseMyMetrics, ScaledComponentOffset, UnscaledComponentOffset, non-ArgsAreXYValues
  160. if (flags & (u16)CompositeGlyfFlags::ArgsAreXYValues) {
  161. e = arg1;
  162. f = arg2;
  163. } else {
  164. TODO();
  165. }
  166. if (flags & (u16)CompositeGlyfFlags::UseMyMetrics) {
  167. TODO();
  168. }
  169. if (flags & (u16)CompositeGlyfFlags::ScaledComponentOffset) {
  170. TODO();
  171. }
  172. if (flags & (u16)CompositeGlyfFlags::UnscaledComponentOffset) {
  173. TODO();
  174. }
  175. m_has_more = (flags & (u16)CompositeGlyfFlags::MoreComponents);
  176. return Item {
  177. .glyph_id = glyph_id,
  178. .affine = Gfx::AffineTransform(a, b, c, d, e, f),
  179. };
  180. }
  181. Rasterizer::Rasterizer(Gfx::IntSize size)
  182. : m_size(size)
  183. {
  184. m_data.resize(m_size.width() * m_size.height());
  185. for (int i = 0; i < m_size.width() * m_size.height(); i++) {
  186. m_data[i] = 0.0f;
  187. }
  188. }
  189. void Rasterizer::draw_path(Gfx::Path& path)
  190. {
  191. for (auto& line : path.split_lines()) {
  192. draw_line(line.from, line.to);
  193. }
  194. }
  195. RefPtr<Gfx::Bitmap> Rasterizer::accumulate()
  196. {
  197. auto bitmap = Gfx::Bitmap::create(Gfx::BitmapFormat::BGRA8888, m_size);
  198. Color base_color = Color::from_rgb(0xffffff);
  199. for (int y = 0; y < m_size.height(); y++) {
  200. float accumulator = 0.0;
  201. for (int x = 0; x < m_size.width(); x++) {
  202. accumulator += m_data[y * m_size.width() + x];
  203. float value = accumulator;
  204. if (value < 0.0f) {
  205. value = -value;
  206. }
  207. if (value > 1.0f) {
  208. value = 1.0;
  209. }
  210. u8 alpha = value * 255.0f;
  211. bitmap->set_pixel(x, y, base_color.with_alpha(alpha));
  212. }
  213. }
  214. return bitmap;
  215. }
  216. void Rasterizer::draw_line(Gfx::FloatPoint p0, Gfx::FloatPoint p1)
  217. {
  218. // FIXME: Shift x and y according to dy/dx
  219. if (p0.x() < 0.0f) {
  220. p0.set_x(roundf(p0.x()));
  221. }
  222. if (p0.y() < 0.0f) {
  223. p0.set_y(roundf(p0.y()));
  224. }
  225. if (p1.x() < 0.0f) {
  226. p1.set_x(roundf(p1.x()));
  227. }
  228. if (p1.y() < 0.0f) {
  229. p1.set_y(roundf(p1.y()));
  230. }
  231. if (!(p0.x() >= 0.0f && p0.y() >= 0.0f && p0.x() <= m_size.width() && p0.y() <= m_size.height())) {
  232. dbgln("!P0({},{})", p0.x(), p0.y());
  233. return;
  234. }
  235. if (!(p1.x() >= 0.0f && p1.y() >= 0.0f && p1.x() <= m_size.width() && p1.y() <= m_size.height())) {
  236. dbgln("!P1({},{})", p1.x(), p1.y());
  237. return;
  238. }
  239. VERIFY(p0.x() >= 0.0f && p0.y() >= 0.0f && p0.x() <= m_size.width() && p0.y() <= m_size.height());
  240. VERIFY(p1.x() >= 0.0f && p1.y() >= 0.0f && p1.x() <= m_size.width() && p1.y() <= m_size.height());
  241. // If we're on the same Y, there's no need to draw
  242. if (p0.y() == p1.y()) {
  243. return;
  244. }
  245. float direction = -1.0;
  246. if (p1.y() < p0.y()) {
  247. direction = 1.0;
  248. auto tmp = p0;
  249. p0 = p1;
  250. p1 = tmp;
  251. }
  252. float dxdy = (p1.x() - p0.x()) / (p1.y() - p0.y());
  253. u32 y0 = floorf(p0.y());
  254. u32 y1 = ceilf(p1.y());
  255. float x_cur = p0.x();
  256. for (u32 y = y0; y < y1; y++) {
  257. u32 line_offset = m_size.width() * y;
  258. float dy = min(y + 1.0f, p1.y()) - max((float)y, p0.y());
  259. float directed_dy = dy * direction;
  260. float x_next = x_cur + dy * dxdy;
  261. if (x_next < 0.0f) {
  262. x_next = 0.0f;
  263. }
  264. float x0 = x_cur;
  265. float x1 = x_next;
  266. if (x1 < x0) {
  267. x1 = x_cur;
  268. x0 = x_next;
  269. }
  270. float x0_floor = floorf(x0);
  271. float x1_ceil = ceilf(x1);
  272. u32 x0i = x0_floor;
  273. if (x1_ceil <= x0_floor + 1.0f) {
  274. // If x0 and x1 are within the same pixel, then area to the right is (1 - (mid(x0, x1) - x0_floor)) * dy
  275. float area = ((x0 + x1) * 0.5f) - x0_floor;
  276. m_data[line_offset + x0i] += directed_dy * (1.0f - area);
  277. m_data[line_offset + x0i + 1] += directed_dy * area;
  278. } else {
  279. float dydx = 1.0f / dxdy;
  280. if (dydx < 0)
  281. dydx = -dydx;
  282. float x0_right = 1.0f - (x0 - x0_floor);
  283. u32 x1_floor_i = floorf(x1);
  284. float area_upto_here = 0.5f * x0_right * x0_right * dydx;
  285. m_data[line_offset + x0i] += direction * area_upto_here;
  286. for (u32 x = x0i + 1; x < x1_floor_i; x++) {
  287. m_data[line_offset + x] += direction * dydx;
  288. area_upto_here += dydx;
  289. }
  290. float remaining_area = (dy - area_upto_here);
  291. m_data[line_offset + x1_floor_i] += direction * remaining_area;
  292. }
  293. x_cur = x_next;
  294. }
  295. }
  296. Optional<Loca> Loca::from_slice(const ReadonlyBytes& slice, u32 num_glyphs, IndexToLocFormat index_to_loc_format)
  297. {
  298. switch (index_to_loc_format) {
  299. case IndexToLocFormat::Offset16:
  300. if (slice.size() < num_glyphs * 2) {
  301. return {};
  302. }
  303. break;
  304. case IndexToLocFormat::Offset32:
  305. if (slice.size() < num_glyphs * 4) {
  306. return {};
  307. }
  308. break;
  309. }
  310. return Loca(slice, num_glyphs, index_to_loc_format);
  311. }
  312. u32 Loca::get_glyph_offset(u32 glyph_id) const
  313. {
  314. VERIFY(glyph_id < m_num_glyphs);
  315. switch (m_index_to_loc_format) {
  316. case IndexToLocFormat::Offset16:
  317. return ((u32)be_u16(m_slice.offset_pointer(glyph_id * 2))) * 2;
  318. case IndexToLocFormat::Offset32:
  319. return be_u32(m_slice.offset_pointer(glyph_id * 4));
  320. default:
  321. VERIFY_NOT_REACHED();
  322. }
  323. }
  324. static void get_ttglyph_offsets(const ReadonlyBytes& slice, u32 num_points, u32 flags_offset, u32* x_offset, u32* y_offset)
  325. {
  326. u32 flags_size = 0;
  327. u32 x_size = 0;
  328. u32 repeat_count;
  329. while (num_points > 0) {
  330. u8 flag = slice[flags_offset + flags_size];
  331. if (flag & (u8)SimpleGlyfFlags::RepeatFlag) {
  332. flags_size++;
  333. repeat_count = slice[flags_offset + flags_size] + 1;
  334. } else {
  335. repeat_count = 1;
  336. }
  337. flags_size++;
  338. switch (flag & (u8)SimpleGlyfFlags::XMask) {
  339. case (u8)SimpleGlyfFlags::XLongVector:
  340. x_size += repeat_count * 2;
  341. break;
  342. case (u8)SimpleGlyfFlags::XNegativeShortVector:
  343. case (u8)SimpleGlyfFlags::XPositiveShortVector:
  344. x_size += repeat_count;
  345. break;
  346. default:
  347. break;
  348. }
  349. num_points -= repeat_count;
  350. }
  351. *x_offset = flags_offset + flags_size;
  352. *y_offset = *x_offset + x_size;
  353. }
  354. void Glyf::Glyph::raster_inner(Rasterizer& rasterizer, Gfx::AffineTransform& affine) const
  355. {
  356. // Get offset for flags, x, and y.
  357. u16 num_points = be_u16(m_slice.offset_pointer((m_num_contours - 1) * 2)) + 1;
  358. u16 num_instructions = be_u16(m_slice.offset_pointer(m_num_contours * 2));
  359. u32 flags_offset = m_num_contours * 2 + 2 + num_instructions;
  360. u32 x_offset = 0;
  361. u32 y_offset = 0;
  362. get_ttglyph_offsets(m_slice, num_points, flags_offset, &x_offset, &y_offset);
  363. // Prepare to render glyph.
  364. Gfx::Path path;
  365. PointIterator point_iterator(m_slice, num_points, flags_offset, x_offset, y_offset, affine);
  366. int last_contour_end = -1;
  367. i32 contour_index = 0;
  368. u32 contour_size = 0;
  369. Optional<Gfx::FloatPoint> contour_start = {};
  370. Optional<Gfx::FloatPoint> last_offcurve_point = {};
  371. // Render glyph
  372. while (true) {
  373. if (!contour_start.has_value()) {
  374. if (contour_index >= m_num_contours) {
  375. break;
  376. }
  377. int current_contour_end = be_u16(m_slice.offset_pointer(contour_index++ * 2));
  378. contour_size = current_contour_end - last_contour_end;
  379. last_contour_end = current_contour_end;
  380. auto opt_item = point_iterator.next();
  381. VERIFY(opt_item.has_value());
  382. contour_start = opt_item.value().point;
  383. path.move_to(contour_start.value());
  384. contour_size--;
  385. } else if (!last_offcurve_point.has_value()) {
  386. if (contour_size > 0) {
  387. auto opt_item = point_iterator.next();
  388. // FIXME: Should we draw a line to the first point here?
  389. if (!opt_item.has_value()) {
  390. break;
  391. }
  392. auto item = opt_item.value();
  393. contour_size--;
  394. if (item.on_curve) {
  395. path.line_to(item.point);
  396. } else if (contour_size > 0) {
  397. auto opt_next_item = point_iterator.next();
  398. // FIXME: Should we draw a quadratic bezier to the first point here?
  399. if (!opt_next_item.has_value()) {
  400. break;
  401. }
  402. auto next_item = opt_next_item.value();
  403. contour_size--;
  404. if (next_item.on_curve) {
  405. path.quadratic_bezier_curve_to(item.point, next_item.point);
  406. } else {
  407. auto mid_point = (item.point + next_item.point) * 0.5f;
  408. path.quadratic_bezier_curve_to(item.point, mid_point);
  409. last_offcurve_point = next_item.point;
  410. }
  411. } else {
  412. path.quadratic_bezier_curve_to(item.point, contour_start.value());
  413. contour_start = {};
  414. }
  415. } else {
  416. path.line_to(contour_start.value());
  417. contour_start = {};
  418. }
  419. } else {
  420. auto point0 = last_offcurve_point.value();
  421. last_offcurve_point = {};
  422. if (contour_size > 0) {
  423. auto opt_item = point_iterator.next();
  424. // FIXME: Should we draw a quadratic bezier to the first point here?
  425. if (!opt_item.has_value()) {
  426. break;
  427. }
  428. auto item = opt_item.value();
  429. contour_size--;
  430. if (item.on_curve) {
  431. path.quadratic_bezier_curve_to(point0, item.point);
  432. } else {
  433. auto mid_point = (point0 + item.point) * 0.5f;
  434. path.quadratic_bezier_curve_to(point0, mid_point);
  435. last_offcurve_point = item.point;
  436. }
  437. } else {
  438. path.quadratic_bezier_curve_to(point0, contour_start.value());
  439. contour_start = {};
  440. }
  441. }
  442. }
  443. rasterizer.draw_path(path);
  444. }
  445. RefPtr<Gfx::Bitmap> Glyf::Glyph::raster_simple(float x_scale, float y_scale) const
  446. {
  447. u32 width = (u32)(ceilf((m_xmax - m_xmin) * x_scale)) + 2;
  448. u32 height = (u32)(ceilf((m_ymax - m_ymin) * y_scale)) + 2;
  449. Rasterizer rasterizer(Gfx::IntSize(width, height));
  450. auto affine = Gfx::AffineTransform().scale(x_scale, -y_scale).translate(-m_xmin, -m_ymax);
  451. raster_inner(rasterizer, affine);
  452. return rasterizer.accumulate();
  453. }
  454. Glyf::Glyph Glyf::glyph(u32 offset) const
  455. {
  456. VERIFY(m_slice.size() >= offset + (u32)Sizes::GlyphHeader);
  457. i16 num_contours = be_i16(m_slice.offset_pointer(offset));
  458. i16 xmin = be_i16(m_slice.offset_pointer(offset + (u32)Offsets::XMin));
  459. i16 ymin = be_i16(m_slice.offset_pointer(offset + (u32)Offsets::YMin));
  460. i16 xmax = be_i16(m_slice.offset_pointer(offset + (u32)Offsets::XMax));
  461. i16 ymax = be_i16(m_slice.offset_pointer(offset + (u32)Offsets::YMax));
  462. auto slice = ReadonlyBytes(m_slice.offset_pointer(offset + (u32)Sizes::GlyphHeader), m_slice.size() - offset - (u32)Sizes::GlyphHeader);
  463. return Glyph(slice, xmin, ymin, xmax, ymax, num_contours);
  464. }
  465. }