1// Copyright 2013 Google Inc. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// Glyph manipulation
16
17#include "./glyph.h"
18
19#include <stdlib.h>
20#include <limits>
21#include "./buffer.h"
22#include "./store_bytes.h"
23
24namespace woff2 {
25
26static const int32_t kFLAG_ONCURVE = 1;
27static const int32_t kFLAG_XSHORT = 1 << 1;
28static const int32_t kFLAG_YSHORT = 1 << 2;
29static const int32_t kFLAG_REPEAT = 1 << 3;
30static const int32_t kFLAG_XREPEATSIGN = 1 << 4;
31static const int32_t kFLAG_YREPEATSIGN = 1 << 5;
32static const int32_t kFLAG_ARG_1_AND_2_ARE_WORDS = 1 << 0;
33static const int32_t kFLAG_WE_HAVE_A_SCALE = 1 << 3;
34static const int32_t kFLAG_MORE_COMPONENTS = 1 << 5;
35static const int32_t kFLAG_WE_HAVE_AN_X_AND_Y_SCALE = 1 << 6;
36static const int32_t kFLAG_WE_HAVE_A_TWO_BY_TWO = 1 << 7;
37static const int32_t kFLAG_WE_HAVE_INSTRUCTIONS = 1 << 8;
38
39bool ReadCompositeGlyphData(Buffer* buffer, Glyph* glyph) {
40  glyph->have_instructions = false;
41  glyph->composite_data = buffer->buffer() + buffer->offset();
42  size_t start_offset = buffer->offset();
43  uint16_t flags = kFLAG_MORE_COMPONENTS;
44  while (flags & kFLAG_MORE_COMPONENTS) {
45    if (!buffer->ReadU16(&flags)) {
46      return FONT_COMPRESSION_FAILURE();
47    }
48    glyph->have_instructions |= (flags & kFLAG_WE_HAVE_INSTRUCTIONS) != 0;
49    size_t arg_size = 2;  // glyph index
50    if (flags & kFLAG_ARG_1_AND_2_ARE_WORDS) {
51      arg_size += 4;
52    } else {
53      arg_size += 2;
54    }
55    if (flags & kFLAG_WE_HAVE_A_SCALE) {
56      arg_size += 2;
57    } else if (flags & kFLAG_WE_HAVE_AN_X_AND_Y_SCALE) {
58      arg_size += 4;
59    } else if (flags & kFLAG_WE_HAVE_A_TWO_BY_TWO) {
60      arg_size += 8;
61    }
62    if (!buffer->Skip(arg_size)) {
63      return FONT_COMPRESSION_FAILURE();
64    }
65  }
66  if (buffer->offset() - start_offset > std::numeric_limits<uint32_t>::max()) {
67    return FONT_COMPRESSION_FAILURE();
68  }
69  glyph->composite_data_size = buffer->offset() - start_offset;
70  return true;
71}
72
73bool ReadGlyph(const uint8_t* data, size_t len, Glyph* glyph) {
74  Buffer buffer(data, len);
75
76  int16_t num_contours;
77  if (!buffer.ReadS16(&num_contours)) {
78    return FONT_COMPRESSION_FAILURE();
79  }
80
81  if (num_contours == 0) {
82    // Empty glyph.
83    return true;
84  }
85
86  // Read the bounding box.
87  if (!buffer.ReadS16(&glyph->x_min) ||
88      !buffer.ReadS16(&glyph->y_min) ||
89      !buffer.ReadS16(&glyph->x_max) ||
90      !buffer.ReadS16(&glyph->y_max)) {
91    return FONT_COMPRESSION_FAILURE();
92  }
93
94  if (num_contours > 0) {
95    // Simple glyph.
96    glyph->contours.resize(num_contours);
97
98    // Read the number of points per contour.
99    uint16_t last_point_index = 0;
100    for (int i = 0; i < num_contours; ++i) {
101      uint16_t point_index;
102      if (!buffer.ReadU16(&point_index)) {
103        return FONT_COMPRESSION_FAILURE();
104      }
105      uint16_t num_points = point_index - last_point_index + (i == 0 ? 1 : 0);
106      glyph->contours[i].resize(num_points);
107      last_point_index = point_index;
108    }
109
110    // Read the instructions.
111    if (!buffer.ReadU16(&glyph->instructions_size)) {
112      return FONT_COMPRESSION_FAILURE();
113    }
114    glyph->instructions_data = data + buffer.offset();
115    if (!buffer.Skip(glyph->instructions_size)) {
116      return FONT_COMPRESSION_FAILURE();
117    }
118
119    // Read the run-length coded flags.
120    std::vector<std::vector<uint8_t> > flags(num_contours);
121    uint8_t flag = 0;
122    uint8_t flag_repeat = 0;
123    for (int i = 0; i < num_contours; ++i) {
124      flags[i].resize(glyph->contours[i].size());
125      for (int j = 0; j < glyph->contours[i].size(); ++j) {
126        if (flag_repeat == 0) {
127          if (!buffer.ReadU8(&flag)) {
128            return FONT_COMPRESSION_FAILURE();
129          }
130          if (flag & kFLAG_REPEAT) {
131            if (!buffer.ReadU8(&flag_repeat)) {
132              return FONT_COMPRESSION_FAILURE();
133            }
134          }
135        } else {
136          flag_repeat--;
137        }
138        flags[i][j] = flag;
139        glyph->contours[i][j].on_curve = flag & kFLAG_ONCURVE;
140      }
141    }
142
143    // Read the x coordinates.
144    int prev_x = 0;
145    for (int i = 0; i < num_contours; ++i) {
146      for (int j = 0; j < glyph->contours[i].size(); ++j) {
147        uint8_t flag = flags[i][j];
148        if (flag & kFLAG_XSHORT) {
149          // single byte x-delta coord value
150          uint8_t x_delta;
151          if (!buffer.ReadU8(&x_delta)) {
152            return FONT_COMPRESSION_FAILURE();
153          }
154          int sign = (flag & kFLAG_XREPEATSIGN) ? 1 : -1;
155          glyph->contours[i][j].x = prev_x + sign * x_delta;
156        } else {
157          // double byte x-delta coord value
158          int16_t x_delta = 0;
159          if (!(flag & kFLAG_XREPEATSIGN)) {
160            if (!buffer.ReadS16(&x_delta)) {
161              return FONT_COMPRESSION_FAILURE();
162            }
163          }
164          glyph->contours[i][j].x = prev_x + x_delta;
165        }
166        prev_x = glyph->contours[i][j].x;
167      }
168    }
169
170    // Read the y coordinates.
171    int prev_y = 0;
172    for (int i = 0; i < num_contours; ++i) {
173      for (int j = 0; j < glyph->contours[i].size(); ++j) {
174        uint8_t flag = flags[i][j];
175        if (flag & kFLAG_YSHORT) {
176          // single byte y-delta coord value
177          uint8_t y_delta;
178          if (!buffer.ReadU8(&y_delta)) {
179            return FONT_COMPRESSION_FAILURE();
180          }
181          int sign = (flag & kFLAG_YREPEATSIGN) ? 1 : -1;
182          glyph->contours[i][j].y = prev_y + sign * y_delta;
183        } else {
184          // double byte y-delta coord value
185          int16_t y_delta = 0;
186          if (!(flag & kFLAG_YREPEATSIGN)) {
187            if (!buffer.ReadS16(&y_delta)) {
188              return FONT_COMPRESSION_FAILURE();
189            }
190          }
191          glyph->contours[i][j].y = prev_y + y_delta;
192        }
193        prev_y = glyph->contours[i][j].y;
194      }
195    }
196  } else if (num_contours == -1) {
197    // Composite glyph.
198    if (!ReadCompositeGlyphData(&buffer, glyph)) {
199      return FONT_COMPRESSION_FAILURE();
200    }
201    // Read the instructions.
202    if (glyph->have_instructions) {
203      if (!buffer.ReadU16(&glyph->instructions_size)) {
204        return FONT_COMPRESSION_FAILURE();
205      }
206      glyph->instructions_data = data + buffer.offset();
207      if (!buffer.Skip(glyph->instructions_size)) {
208        return FONT_COMPRESSION_FAILURE();
209      }
210    } else {
211      glyph->instructions_size = 0;
212    }
213  } else {
214    return FONT_COMPRESSION_FAILURE();
215  }
216  return true;
217}
218
219namespace {
220
221void StoreBbox(const Glyph& glyph, size_t* offset, uint8_t* dst) {
222  Store16(glyph.x_min, offset, dst);
223  Store16(glyph.y_min, offset, dst);
224  Store16(glyph.x_max, offset, dst);
225  Store16(glyph.y_max, offset, dst);
226}
227
228void StoreInstructions(const Glyph& glyph, size_t* offset, uint8_t* dst) {
229  Store16(glyph.instructions_size, offset, dst);
230  StoreBytes(glyph.instructions_data, glyph.instructions_size, offset, dst);
231}
232
233bool StoreEndPtsOfContours(const Glyph& glyph, size_t* offset, uint8_t* dst) {
234  int end_point = -1;
235  for (const auto& contour : glyph.contours) {
236    end_point += contour.size();
237    if (contour.size() > std::numeric_limits<uint16_t>::max() ||
238        end_point > std::numeric_limits<uint16_t>::max()) {
239      return FONT_COMPRESSION_FAILURE();
240    }
241    Store16(end_point, offset, dst);
242  }
243  return true;
244}
245
246bool StorePoints(const Glyph& glyph, size_t* offset,
247                 uint8_t* dst, size_t dst_size) {
248  int last_flag = -1;
249  int repeat_count = 0;
250  int last_x = 0;
251  int last_y = 0;
252  size_t x_bytes = 0;
253  size_t y_bytes = 0;
254
255  // Store the flags and calculate the total size of the x and y coordinates.
256  for (const auto& contour : glyph.contours) {
257    for (const auto& point : contour) {
258      int flag = point.on_curve ? kFLAG_ONCURVE : 0;
259      int dx = point.x - last_x;
260      int dy = point.y - last_y;
261      if (dx == 0) {
262        flag |= kFLAG_XREPEATSIGN;
263      } else if (dx > -256 && dx < 256) {
264        flag |= kFLAG_XSHORT | (dx > 0 ? kFLAG_XREPEATSIGN : 0);
265        x_bytes += 1;
266      } else {
267        x_bytes += 2;
268      }
269      if (dy == 0) {
270        flag |= kFLAG_YREPEATSIGN;
271      } else if (dy > -256 && dy < 256) {
272        flag |= kFLAG_YSHORT | (dy > 0 ? kFLAG_YREPEATSIGN : 0);
273        y_bytes += 1;
274      } else {
275        y_bytes += 2;
276      }
277      if (flag == last_flag && repeat_count != 255) {
278        dst[*offset - 1] |= kFLAG_REPEAT;
279        repeat_count++;
280      } else {
281        if (repeat_count != 0) {
282          if (*offset >= dst_size) {
283            return FONT_COMPRESSION_FAILURE();
284          }
285          dst[(*offset)++] = repeat_count;
286        }
287        if (*offset >= dst_size) {
288          return FONT_COMPRESSION_FAILURE();
289        }
290        dst[(*offset)++] = flag;
291        repeat_count = 0;
292      }
293      last_x = point.x;
294      last_y = point.y;
295      last_flag = flag;
296    }
297  }
298  if (repeat_count != 0) {
299    if (*offset >= dst_size) {
300      return FONT_COMPRESSION_FAILURE();
301    }
302    dst[(*offset)++] = repeat_count;
303  }
304
305  if (*offset + x_bytes + y_bytes > dst_size) {
306    return FONT_COMPRESSION_FAILURE();
307  }
308
309  // Store the x and y coordinates.
310  size_t x_offset = *offset;
311  size_t y_offset = *offset + x_bytes;
312  last_x = 0;
313  last_y = 0;
314  for (const auto& contour : glyph.contours) {
315    for (const auto& point : contour) {
316      int dx = point.x - last_x;
317      int dy = point.y - last_y;
318      if (dx == 0) {
319        // pass
320      } else if (dx > -256 && dx < 256) {
321        dst[x_offset++] = std::abs(dx);
322      } else {
323        Store16(dx, &x_offset, dst);
324      }
325      if (dy == 0) {
326        // pass
327      } else if (dy > -256 && dy < 256) {
328        dst[y_offset++] = std::abs(dy);
329      } else {
330        Store16(dy, &y_offset, dst);
331      }
332      last_x += dx;
333      last_y += dy;
334    }
335  }
336  *offset = y_offset;
337  return true;
338}
339
340}  // namespace
341
342bool StoreGlyph(const Glyph& glyph, uint8_t* dst, size_t* dst_size) {
343  size_t offset = 0;
344  if (glyph.composite_data_size > 0) {
345    // Composite glyph.
346    if (*dst_size < ((10ULL + glyph.composite_data_size) +
347                     ((glyph.have_instructions ? 2ULL : 0) +
348                      glyph.instructions_size))) {
349      return FONT_COMPRESSION_FAILURE();
350    }
351    Store16(-1, &offset, dst);
352    StoreBbox(glyph, &offset, dst);
353    StoreBytes(glyph.composite_data, glyph.composite_data_size, &offset, dst);
354    if (glyph.have_instructions) {
355      StoreInstructions(glyph, &offset, dst);
356    }
357  } else if (glyph.contours.size() > 0) {
358    // Simple glyph.
359    if (glyph.contours.size() > std::numeric_limits<int16_t>::max()) {
360      return FONT_COMPRESSION_FAILURE();
361    }
362    if (*dst_size < ((12ULL + 2 * glyph.contours.size()) +
363                     glyph.instructions_size)) {
364      return FONT_COMPRESSION_FAILURE();
365    }
366    Store16(glyph.contours.size(), &offset, dst);
367    StoreBbox(glyph, &offset, dst);
368    if (!StoreEndPtsOfContours(glyph, &offset, dst)) {
369      return FONT_COMPRESSION_FAILURE();
370    }
371    StoreInstructions(glyph, &offset, dst);
372    if (!StorePoints(glyph, &offset, dst, *dst_size)) {
373      return FONT_COMPRESSION_FAILURE();
374    }
375  }
376  *dst_size = offset;
377  return true;
378}
379
380} // namespace woff2
381