1 /* Copyright 2013 Google Inc. All Rights Reserved.
2
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5 */
6
7 /* Library for preprocessing fonts as part of the WOFF 2.0 conversion. */
8
9 #include "./transform.h"
10
11 #include <complex> // for std::abs
12
13 #include "./buffer.h"
14 #include "./font.h"
15 #include "./glyph.h"
16 #include "./table_tags.h"
17 #include "./variable_length.h"
18
19 namespace woff2 {
20
21 namespace {
22
23 const int FLAG_ARG_1_AND_2_ARE_WORDS = 1 << 0;
24 const int FLAG_WE_HAVE_INSTRUCTIONS = 1 << 8;
25
WriteBytes(std::vector<uint8_t> * out,const uint8_t * data,size_t len)26 void WriteBytes(std::vector<uint8_t>* out, const uint8_t* data, size_t len) {
27 if (len == 0) return;
28 size_t offset = out->size();
29 out->resize(offset + len);
30 memcpy(&(*out)[offset], data, len);
31 }
32
WriteBytes(std::vector<uint8_t> * out,const std::vector<uint8_t> & in)33 void WriteBytes(std::vector<uint8_t>* out, const std::vector<uint8_t>& in) {
34 for (size_t i = 0; i < in.size(); ++i) {
35 out->push_back(in[i]);
36 }
37 }
38
WriteUShort(std::vector<uint8_t> * out,int value)39 void WriteUShort(std::vector<uint8_t>* out, int value) {
40 out->push_back(value >> 8);
41 out->push_back(value & 255);
42 }
43
WriteLong(std::vector<uint8_t> * out,int value)44 void WriteLong(std::vector<uint8_t>* out, int value) {
45 out->push_back((value >> 24) & 255);
46 out->push_back((value >> 16) & 255);
47 out->push_back((value >> 8) & 255);
48 out->push_back(value & 255);
49 }
50
51 // Glyf table preprocessing, based on
52 // GlyfEncoder.java
53 class GlyfEncoder {
54 public:
GlyfEncoder(int num_glyphs)55 explicit GlyfEncoder(int num_glyphs)
56 : n_glyphs_(num_glyphs) {
57 bbox_bitmap_.resize(((num_glyphs + 31) >> 5) << 2);
58 }
59
Encode(int glyph_id,const Glyph & glyph)60 bool Encode(int glyph_id, const Glyph& glyph) {
61 if (glyph.composite_data_size > 0) {
62 WriteCompositeGlyph(glyph_id, glyph);
63 } else if (glyph.contours.size() > 0) {
64 WriteSimpleGlyph(glyph_id, glyph);
65 } else {
66 WriteUShort(&n_contour_stream_, 0);
67 }
68 return true;
69 }
70
GetTransformedGlyfBytes(std::vector<uint8_t> * result)71 void GetTransformedGlyfBytes(std::vector<uint8_t>* result) {
72 WriteLong(result, 0); // version
73 WriteUShort(result, n_glyphs_);
74 WriteUShort(result, 0); // index_format, will be set later
75 WriteLong(result, n_contour_stream_.size());
76 WriteLong(result, n_points_stream_.size());
77 WriteLong(result, flag_byte_stream_.size());
78 WriteLong(result, glyph_stream_.size());
79 WriteLong(result, composite_stream_.size());
80 WriteLong(result, bbox_bitmap_.size() + bbox_stream_.size());
81 WriteLong(result, instruction_stream_.size());
82 WriteBytes(result, n_contour_stream_);
83 WriteBytes(result, n_points_stream_);
84 WriteBytes(result, flag_byte_stream_);
85 WriteBytes(result, glyph_stream_);
86 WriteBytes(result, composite_stream_);
87 WriteBytes(result, bbox_bitmap_);
88 WriteBytes(result, bbox_stream_);
89 WriteBytes(result, instruction_stream_);
90 }
91
92 private:
WriteInstructions(const Glyph & glyph)93 void WriteInstructions(const Glyph& glyph) {
94 Write255UShort(&glyph_stream_, glyph.instructions_size);
95 WriteBytes(&instruction_stream_,
96 glyph.instructions_data, glyph.instructions_size);
97 }
98
ShouldWriteSimpleGlyphBbox(const Glyph & glyph)99 bool ShouldWriteSimpleGlyphBbox(const Glyph& glyph) {
100 if (glyph.contours.empty() || glyph.contours[0].empty()) {
101 return glyph.x_min || glyph.y_min || glyph.x_max || glyph.y_max;
102 }
103
104 int16_t x_min = glyph.contours[0][0].x;
105 int16_t y_min = glyph.contours[0][0].y;
106 int16_t x_max = x_min;
107 int16_t y_max = y_min;
108 for (const auto& contour : glyph.contours) {
109 for (const auto& point : contour) {
110 if (point.x < x_min) x_min = point.x;
111 if (point.x > x_max) x_max = point.x;
112 if (point.y < y_min) y_min = point.y;
113 if (point.y > y_max) y_max = point.y;
114 }
115 }
116
117 if (glyph.x_min != x_min)
118 return true;
119 if (glyph.y_min != y_min)
120 return true;
121 if (glyph.x_max != x_max)
122 return true;
123 if (glyph.y_max != y_max)
124 return true;
125
126 return false;
127 }
128
WriteSimpleGlyph(int glyph_id,const Glyph & glyph)129 void WriteSimpleGlyph(int glyph_id, const Glyph& glyph) {
130 int num_contours = glyph.contours.size();
131 WriteUShort(&n_contour_stream_, num_contours);
132 if (ShouldWriteSimpleGlyphBbox(glyph)) {
133 WriteBbox(glyph_id, glyph);
134 }
135 for (int i = 0; i < num_contours; i++) {
136 Write255UShort(&n_points_stream_, glyph.contours[i].size());
137 }
138 int lastX = 0;
139 int lastY = 0;
140 for (int i = 0; i < num_contours; i++) {
141 int num_points = glyph.contours[i].size();
142 for (int j = 0; j < num_points; j++) {
143 int x = glyph.contours[i][j].x;
144 int y = glyph.contours[i][j].y;
145 int dx = x - lastX;
146 int dy = y - lastY;
147 WriteTriplet(glyph.contours[i][j].on_curve, dx, dy);
148 lastX = x;
149 lastY = y;
150 }
151 }
152 if (num_contours > 0) {
153 WriteInstructions(glyph);
154 }
155 }
156
WriteCompositeGlyph(int glyph_id,const Glyph & glyph)157 void WriteCompositeGlyph(int glyph_id, const Glyph& glyph) {
158 WriteUShort(&n_contour_stream_, -1);
159 WriteBbox(glyph_id, glyph);
160 WriteBytes(&composite_stream_,
161 glyph.composite_data,
162 glyph.composite_data_size);
163 if (glyph.have_instructions) {
164 WriteInstructions(glyph);
165 }
166 }
167
WriteBbox(int glyph_id,const Glyph & glyph)168 void WriteBbox(int glyph_id, const Glyph& glyph) {
169 bbox_bitmap_[glyph_id >> 3] |= 0x80 >> (glyph_id & 7);
170 WriteUShort(&bbox_stream_, glyph.x_min);
171 WriteUShort(&bbox_stream_, glyph.y_min);
172 WriteUShort(&bbox_stream_, glyph.x_max);
173 WriteUShort(&bbox_stream_, glyph.y_max);
174 }
175
WriteTriplet(bool on_curve,int x,int y)176 void WriteTriplet(bool on_curve, int x, int y) {
177 int abs_x = std::abs(x);
178 int abs_y = std::abs(y);
179 int on_curve_bit = on_curve ? 0 : 128;
180 int x_sign_bit = (x < 0) ? 0 : 1;
181 int y_sign_bit = (y < 0) ? 0 : 1;
182 int xy_sign_bits = x_sign_bit + 2 * y_sign_bit;
183 if (x == 0 && abs_y < 1280) {
184 flag_byte_stream_.push_back(on_curve_bit +
185 ((abs_y & 0xf00) >> 7) + y_sign_bit);
186 glyph_stream_.push_back(abs_y & 0xff);
187 } else if (y == 0 && abs_x < 1280) {
188 flag_byte_stream_.push_back(on_curve_bit + 10 +
189 ((abs_x & 0xf00) >> 7) + x_sign_bit);
190 glyph_stream_.push_back(abs_x & 0xff);
191 } else if (abs_x < 65 && abs_y < 65) {
192 flag_byte_stream_.push_back(on_curve_bit + 20 +
193 ((abs_x - 1) & 0x30) +
194 (((abs_y - 1) & 0x30) >> 2) +
195 xy_sign_bits);
196 glyph_stream_.push_back((((abs_x - 1) & 0xf) << 4) | ((abs_y - 1) & 0xf));
197 } else if (abs_x < 769 && abs_y < 769) {
198 flag_byte_stream_.push_back(on_curve_bit + 84 +
199 12 * (((abs_x - 1) & 0x300) >> 8) +
200 (((abs_y - 1) & 0x300) >> 6) + xy_sign_bits);
201 glyph_stream_.push_back((abs_x - 1) & 0xff);
202 glyph_stream_.push_back((abs_y - 1) & 0xff);
203 } else if (abs_x < 4096 && abs_y < 4096) {
204 flag_byte_stream_.push_back(on_curve_bit + 120 + xy_sign_bits);
205 glyph_stream_.push_back(abs_x >> 4);
206 glyph_stream_.push_back(((abs_x & 0xf) << 4) | (abs_y >> 8));
207 glyph_stream_.push_back(abs_y & 0xff);
208 } else {
209 flag_byte_stream_.push_back(on_curve_bit + 124 + xy_sign_bits);
210 glyph_stream_.push_back(abs_x >> 8);
211 glyph_stream_.push_back(abs_x & 0xff);
212 glyph_stream_.push_back(abs_y >> 8);
213 glyph_stream_.push_back(abs_y & 0xff);
214 }
215 }
216
217 std::vector<uint8_t> n_contour_stream_;
218 std::vector<uint8_t> n_points_stream_;
219 std::vector<uint8_t> flag_byte_stream_;
220 std::vector<uint8_t> composite_stream_;
221 std::vector<uint8_t> bbox_bitmap_;
222 std::vector<uint8_t> bbox_stream_;
223 std::vector<uint8_t> glyph_stream_;
224 std::vector<uint8_t> instruction_stream_;
225 int n_glyphs_;
226 };
227
228 } // namespace
229
TransformGlyfAndLocaTables(Font * font)230 bool TransformGlyfAndLocaTables(Font* font) {
231 // no transform for CFF
232 const Font::Table* glyf_table = font->FindTable(kGlyfTableTag);
233 const Font::Table* loca_table = font->FindTable(kLocaTableTag);
234
235 // If you don't have glyf/loca this transform isn't very interesting
236 if (loca_table == NULL && glyf_table == NULL) {
237 return true;
238 }
239 // It would be best if you didn't have just one of glyf/loca
240 if ((glyf_table == NULL) != (loca_table == NULL)) {
241 return FONT_COMPRESSION_FAILURE();
242 }
243 // Must share neither or both loca & glyf
244 if (loca_table->IsReused() != glyf_table->IsReused()) {
245 return FONT_COMPRESSION_FAILURE();
246 }
247 if (loca_table->IsReused()) {
248 return true;
249 }
250
251 Font::Table* transformed_glyf = &font->tables[kGlyfTableTag ^ 0x80808080];
252 Font::Table* transformed_loca = &font->tables[kLocaTableTag ^ 0x80808080];
253
254 int num_glyphs = NumGlyphs(*font);
255 GlyfEncoder encoder(num_glyphs);
256 for (int i = 0; i < num_glyphs; ++i) {
257 Glyph glyph;
258 const uint8_t* glyph_data;
259 size_t glyph_size;
260 if (!GetGlyphData(*font, i, &glyph_data, &glyph_size) ||
261 (glyph_size > 0 && !ReadGlyph(glyph_data, glyph_size, &glyph))) {
262 return FONT_COMPRESSION_FAILURE();
263 }
264 encoder.Encode(i, glyph);
265 }
266 encoder.GetTransformedGlyfBytes(&transformed_glyf->buffer);
267
268 const Font::Table* head_table = font->FindTable(kHeadTableTag);
269 if (head_table == NULL || head_table->length < 52) {
270 return FONT_COMPRESSION_FAILURE();
271 }
272 transformed_glyf->buffer[7] = head_table->data[51]; // index_format
273
274 transformed_glyf->tag = kGlyfTableTag ^ 0x80808080;
275 transformed_glyf->length = transformed_glyf->buffer.size();
276 transformed_glyf->data = transformed_glyf->buffer.data();
277
278 transformed_loca->tag = kLocaTableTag ^ 0x80808080;
279 transformed_loca->length = 0;
280 transformed_loca->data = NULL;
281
282 return true;
283 }
284
285 // See https://www.microsoft.com/typography/otspec/hmtx.htm
286 // See WOFF2 spec, 5.4. Transformed hmtx table format
TransformHmtxTable(Font * font)287 bool TransformHmtxTable(Font* font) {
288 const Font::Table* glyf_table = font->FindTable(kGlyfTableTag);
289 const Font::Table* hmtx_table = font->FindTable(kHmtxTableTag);
290 const Font::Table* hhea_table = font->FindTable(kHheaTableTag);
291
292 // If you don't have hmtx or a glyf not much is going to happen here
293 if (hmtx_table == NULL || glyf_table == NULL) {
294 return true;
295 }
296
297 // hmtx without hhea doesn't make sense
298 if (hhea_table == NULL) {
299 return FONT_COMPRESSION_FAILURE();
300 }
301
302 // Skip 34 to reach 'hhea' numberOfHMetrics
303 Buffer hhea_buf(hhea_table->data, hhea_table->length);
304 uint16_t num_hmetrics;
305 if (!hhea_buf.Skip(34) || !hhea_buf.ReadU16(&num_hmetrics)) {
306 return FONT_COMPRESSION_FAILURE();
307 }
308
309 // Must have at least one hMetric
310 if (num_hmetrics < 1) {
311 return FONT_COMPRESSION_FAILURE();
312 }
313
314 int num_glyphs = NumGlyphs(*font);
315
316 // Most fonts can be transformed; assume it's a go until proven otherwise
317 std::vector<uint16_t> advance_widths;
318 std::vector<int16_t> proportional_lsbs;
319 std::vector<int16_t> monospace_lsbs;
320
321 bool remove_proportional_lsb = true;
322 bool remove_monospace_lsb = (num_glyphs - num_hmetrics) > 0;
323
324 Buffer hmtx_buf(hmtx_table->data, hmtx_table->length);
325 for (int i = 0; i < num_glyphs; i++) {
326 Glyph glyph;
327 const uint8_t* glyph_data;
328 size_t glyph_size;
329 if (!GetGlyphData(*font, i, &glyph_data, &glyph_size) ||
330 (glyph_size > 0 && !ReadGlyph(glyph_data, glyph_size, &glyph))) {
331 return FONT_COMPRESSION_FAILURE();
332 }
333
334 uint16_t advance_width = 0;
335 int16_t lsb = 0;
336
337 if (i < num_hmetrics) {
338 // [0, num_hmetrics) are proportional hMetrics
339 if (!hmtx_buf.ReadU16(&advance_width)) {
340 return FONT_COMPRESSION_FAILURE();
341 }
342
343 if (!hmtx_buf.ReadS16(&lsb)) {
344 return FONT_COMPRESSION_FAILURE();
345 }
346
347 if (glyph_size > 0 && glyph.x_min != lsb) {
348 remove_proportional_lsb = false;
349 }
350
351 advance_widths.push_back(advance_width);
352 proportional_lsbs.push_back(lsb);
353 } else {
354 // [num_hmetrics, num_glyphs) are monospace leftSideBearing's
355 if (!hmtx_buf.ReadS16(&lsb)) {
356 return FONT_COMPRESSION_FAILURE();
357 }
358 if (glyph_size > 0 && glyph.x_min != lsb) {
359 remove_monospace_lsb = false;
360 }
361 monospace_lsbs.push_back(lsb);
362 }
363
364 // If we know we can't optimize, bail out completely
365 if (!remove_proportional_lsb && !remove_monospace_lsb) {
366 return true;
367 }
368 }
369
370 Font::Table* transformed_hmtx = &font->tables[kHmtxTableTag ^ 0x80808080];
371
372 uint8_t flags = 0;
373 size_t transformed_size = 1 + 2 * advance_widths.size();
374 if (remove_proportional_lsb) {
375 flags |= 1;
376 } else {
377 transformed_size += 2 * proportional_lsbs.size();
378 }
379 if (remove_monospace_lsb) {
380 flags |= 1 << 1;
381 } else {
382 transformed_size += 2 * monospace_lsbs.size();
383 }
384
385 transformed_hmtx->buffer.reserve(transformed_size);
386 std::vector<uint8_t>* out = &transformed_hmtx->buffer;
387 WriteBytes(out, &flags, 1);
388 for (uint16_t advance_width : advance_widths) {
389 WriteUShort(out, advance_width);
390 }
391
392 if (!remove_proportional_lsb) {
393 for (int16_t lsb : proportional_lsbs) {
394 WriteUShort(out, lsb);
395 }
396 }
397 if (!remove_monospace_lsb) {
398 for (int16_t lsb : monospace_lsbs) {
399 WriteUShort(out, lsb);
400 }
401 }
402
403 transformed_hmtx->tag = kHmtxTableTag ^ 0x80808080;
404 transformed_hmtx->flag_byte = 1 << 6;
405 transformed_hmtx->length = transformed_hmtx->buffer.size();
406 transformed_hmtx->data = transformed_hmtx->buffer.data();
407
408
409 return true;
410 }
411
412 } // namespace woff2
413