third_party/woff2/src/normalize.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 normalization
  16
  17 #include "./normalize.h"
  18
  19 #include <inttypes.h>
  20 #include <stddef.h>
  21
  22 #include "./buffer.h"
  23 #include "./port.h"
  24 #include "./font.h"
  25 #include "./glyph.h"
  26 #include "./round.h"
  27 #include "./store_bytes.h"
  28 #include "./table_tags.h"
  29
  30 namespace woff2 {
  31
  32 namespace {
  33
  34 void StoreLoca(int index_fmt, uint32_t value, size_t* offset, uint8_t* dst) {
  35   if (index_fmt == 0) {
  36     Store16(value >> 1, offset, dst);
  37   } else {
  38     StoreU32(value, offset, dst);
  39   }
  40 }
  41
  42 void NormalizeSimpleGlyphBoundingBox(Glyph* glyph) {
  43   if (glyph->contours.empty() || glyph->contours[0].empty()) {
  44     return;
  45   }
  46   int16_t x_min = glyph->contours[0][0].x;
  47   int16_t y_min = glyph->contours[0][0].y;
  48   int16_t x_max = x_min;
  49   int16_t y_max = y_min;
  50   for (const auto& contour : glyph->contours) {
  51     for (const auto& point : contour) {
  52       if (point.x < x_min) x_min = point.x;
  53       if (point.x > x_max) x_max = point.x;
  54       if (point.y < y_min) y_min = point.y;
  55       if (point.y > y_max) y_max = point.y;
  56     }
  57   }
  58   glyph->x_min = x_min;
  59   glyph->y_min = y_min;
  60   glyph->x_max = x_max;
  61   glyph->y_max = y_max;
  62 }
  63
  64 }  // namespace
  65
  66 namespace {
  67
  68 bool WriteNormalizedLoca(int index_fmt, int num_glyphs, Font* font) {
  69   Font::Table* glyf_table = font->FindTable(kGlyfTableTag);
  70   Font::Table* loca_table = font->FindTable(kLocaTableTag);
  71
  72   int glyph_sz = index_fmt == 0 ? 2 : 4;
  73   loca_table->buffer.resize(Round4(num_glyphs + 1) * glyph_sz);
  74   loca_table->length = (num_glyphs + 1) * glyph_sz;
  75
  76   uint8_t* glyf_dst = &glyf_table->buffer[0];
  77   uint8_t* loca_dst = &loca_table->buffer[0];
  78   uint32_t glyf_offset = 0;
  79   size_t loca_offset = 0;
  80
  81   for (int i = 0; i < num_glyphs; ++i) {
  82     StoreLoca(index_fmt, glyf_offset, &loca_offset, loca_dst);
  83     Glyph glyph;
  84     const uint8_t* glyph_data;
  85     size_t glyph_size;
  86     if (!GetGlyphData(*font, i, &glyph_data, &glyph_size) ||
  87         (glyph_size > 0 && !ReadGlyph(glyph_data, glyph_size, &glyph))) {
  88       return FONT_COMPRESSION_FAILURE();
  89     }
  90     NormalizeSimpleGlyphBoundingBox(&glyph);
  91     size_t glyf_dst_size = glyf_table->buffer.size() - glyf_offset;
  92     if (!StoreGlyph(glyph, glyf_dst + glyf_offset, &glyf_dst_size)) {
  93       return FONT_COMPRESSION_FAILURE();
  94     }
  95     glyf_dst_size = Round4(glyf_dst_size);
  96     if (glyf_dst_size > std::numeric_limits<uint32_t>::max() ||
  97         glyf_offset + static_cast<uint32_t>(glyf_dst_size) < glyf_offset ||
  98         (index_fmt == 0 && glyf_offset + glyf_dst_size >= (1UL << 17))) {
  99       return FONT_COMPRESSION_FAILURE();
 100     }
 101     glyf_offset += glyf_dst_size;
 102   }
 103   if (glyf_offset == 0) {
 104     return false;
 105   }
 106
 107   StoreLoca(index_fmt, glyf_offset, &loca_offset, loca_dst);
 108
 109   glyf_table->buffer.resize(glyf_offset);
 110   glyf_table->data = &glyf_table->buffer[0];
 111   glyf_table->length = glyf_offset;
 112   loca_table->data = &loca_table->buffer[0];
 113
 114   return true;
 115 }
 116
 117 }  // namespace
 118
 119 namespace {
 120
 121 bool MakeEditableBuffer(Font* font, int tableTag) {
 122   Font::Table* table = font->FindTable(tableTag);
 123   if (table == NULL) {
 124     return FONT_COMPRESSION_FAILURE();
 125   }
 126   int sz = Round4(table->length);
 127   table->buffer.resize(sz);
 128   uint8_t* buf = &table->buffer[0];
 129   memcpy(buf, table->data, sz);
 130   table->data = buf;
 131   return true;
 132 }
 133
 134 }  // namespace
 135
 136 bool NormalizeGlyphs(Font* font) {
 137   Font::Table* cff_table = font->FindTable(kCffTableTag);
 138   Font::Table* head_table = font->FindTable(kHeadTableTag);
 139   Font::Table* glyf_table = font->FindTable(kGlyfTableTag);
 140   Font::Table* loca_table = font->FindTable(kLocaTableTag);
 141   if (head_table == NULL) {
 142     return FONT_COMPRESSION_FAILURE();
 143   }
 144   // CFF, no loca, no glyf is OK for CFF. If so, don't normalize.
 145   if (cff_table != NULL && loca_table == NULL && glyf_table == NULL) {
 146     return true;
 147   }
 148   if (loca_table == NULL || glyf_table == NULL) {
 149     return FONT_COMPRESSION_FAILURE();
 150   }
 151   int index_fmt = head_table->data[51];
 152   int num_glyphs = NumGlyphs(*font);
 153
 154   // We need to allocate a bit more than its original length for the normalized
 155   // glyf table, since it can happen that the glyphs in the original table are
 156   // 2-byte aligned, while in the normalized table they are 4-byte aligned.
 157   // That gives a maximum of 2 bytes increase per glyph. However, there is no
 158   // theoretical guarantee that the total size of the flags plus the coordinates
 159   // is the smallest possible in the normalized version, so we have to allow
 160   // some general overhead.
 161   // TODO(user) Figure out some more precise upper bound on the size of
 162   // the overhead.
 163   size_t max_normalized_glyf_size = 1.1 * glyf_table->length + 2 * num_glyphs;
 164
 165   glyf_table->buffer.resize(max_normalized_glyf_size);
 166
 167   // if we can't write a loca using short's (index_fmt 0)
 168   // try again using longs (index_fmt 1)
 169   if (!WriteNormalizedLoca(index_fmt, num_glyphs, font)) {
 170     if (index_fmt != 0) {
 171       return FONT_COMPRESSION_FAILURE();
 172     }
 173
 174     // Rewrite loca with 4-byte entries & update head to match
 175     index_fmt = 1;
 176     if (!WriteNormalizedLoca(index_fmt, num_glyphs, font)) {
 177       return FONT_COMPRESSION_FAILURE();
 178     }
 179     head_table->buffer[51] = 1;
 180   }
 181
 182   return true;
 183 }
 184
 185 bool NormalizeOffsets(Font* font) {
 186   uint32_t offset = 12 + 16 * font->num_tables;
 187   for (auto& i : font->tables) {
 188     i.second.offset = offset;
 189     offset += Round4(i.second.length);
 190   }
 191   return true;
 192 }
 193
 194 namespace {
 195
 196 uint32_t ComputeChecksum(const uint8_t* buf, size_t size) {
 197   uint32_t checksum = 0;
 198   for (size_t i = 0; i < size; i += 4) {
 199     checksum += ((buf[i] << 24) |
 200                  (buf[i + 1] << 16) |
 201                  (buf[i + 2] << 8) |
 202                  buf[i + 3]);
 203   }
 204   return checksum;
 205 }
 206
 207 uint32_t ComputeHeaderChecksum(const Font& font) {
 208   uint32_t checksum = font.flavor;
 209   uint16_t max_pow2 = font.num_tables ? Log2Floor(font.num_tables) : 0;
 210   uint16_t search_range = max_pow2 ? 1 << (max_pow2 + 4) : 0;
 211   uint16_t range_shift = (font.num_tables << 4) - search_range;
 212   checksum += (font.num_tables << 16 | search_range);
 213   checksum += (max_pow2 << 16 | range_shift);
 214   for (const auto& i : font.tables) {
 215     checksum += i.second.tag;
 216     checksum += i.second.checksum;
 217     checksum += i.second.offset;
 218     checksum += i.second.length;
 219   }
 220   return checksum;
 221 }
 222
 223 }  // namespace
 224
 225 bool FixChecksums(Font* font) {
 226   Font::Table* head_table = font->FindTable(kHeadTableTag);
 227   if (head_table == NULL || head_table->length < 12) {
 228     return FONT_COMPRESSION_FAILURE();
 229   }
 230   uint8_t* head_buf = &head_table->buffer[0];
 231   size_t offset = 8;
 232   StoreU32(0, &offset, head_buf);
 233   uint32_t file_checksum = 0;
 234   for (auto& i : font->tables) {
 235     Font::Table* table = &i.second;
 236     table->checksum = ComputeChecksum(table->data, table->length);
 237     file_checksum += table->checksum;
 238   }
 239   file_checksum += ComputeHeaderChecksum(*font);
 240   offset = 8;
 241   StoreU32(0xb1b0afba - file_checksum, &offset, head_buf);
 242   return true;
 243 }
 244
 245 bool NormalizeFont(Font* font) {
 246   return (MakeEditableBuffer(font, kHeadTableTag) &&
 247           RemoveDigitalSignature(font) &&
 248           NormalizeGlyphs(font) &&
 249           NormalizeOffsets(font) &&
 250           FixChecksums(font));
 251 }
 252
 253 } // namespace woff2