third_party/woff2/src/glyph.cc

   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
  24 namespace woff2 {
  25
  26 static const int32_t kFLAG_ONCURVE = 1;
  27 static const int32_t kFLAG_XSHORT = 1 << 1;
  28 static const int32_t kFLAG_YSHORT = 1 << 2;
  29 static const int32_t kFLAG_REPEAT = 1 << 3;
  30 static const int32_t kFLAG_XREPEATSIGN = 1 << 4;
  31 static const int32_t kFLAG_YREPEATSIGN = 1 << 5;
  32 static const int32_t kFLAG_ARG_1_AND_2_ARE_WORDS = 1 << 0;
  33 static const int32_t kFLAG_WE_HAVE_A_SCALE = 1 << 3;
  34 static const int32_t kFLAG_MORE_COMPONENTS = 1 << 5;
  35 static const int32_t kFLAG_WE_HAVE_AN_X_AND_Y_SCALE = 1 << 6;
  36 static const int32_t kFLAG_WE_HAVE_A_TWO_BY_TWO = 1 << 7;
  37 static const int32_t kFLAG_WE_HAVE_INSTRUCTIONS = 1 << 8;
  38
  39 bool 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
  73 bool 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
 219 namespace {
 220
 221 void 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
 228 void 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
 233 bool 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
 246 bool 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
 342 bool 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