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