src/ots.cc

// Copyright (c) 2009 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "ots.h"

#include <sys/types.h>

#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <vector>

// The OpenType Font File
// http://www.microsoft.com/opentype/otspec/otff.htm

#define F(name, capname) \
  namespace ots { \
  bool ots_##name##_parse(OpenTypeFile *f, const uint8_t *d, size_t l); \
  bool ots_##name##_should_serialise(OpenTypeFile *f); \
  bool ots_##name##_serialise(OTSStream *s, OpenTypeFile *f); \
  void ots_##name##_free(OpenTypeFile *f); \
  }
  // TODO(yusukes): change these function names to follow the coding rule.
FOR_EACH_TABLE_TYPE
#undef F

namespace {

bool g_debug_output = true;

struct OpenTypeTable {
  uint32_t tag;
  uint32_t chksum;
  uint32_t offset;
  uint32_t length;
};

// Round a value up to the nearest multiple of 4. Note that this can overflow
// and return zero.
template<typename T> T Round4(T value) {
  return (value + 3) & ~3;
}

uint32_t Tag(const char *tag_str) {
  uint32_t ret;
  std::memcpy(&ret, tag_str, 4);
  return ret;
}

bool CheckTag(uint32_t tag_value) {
  for (unsigned i = 0; i < 4; ++i) {
    const uint32_t check = tag_value & 0xff;
    if (check < 32 || check > 126) {
      return false;  // non-ASCII character found.
    }
    tag_value >>= 8;
  }
  return true;
}

struct OutputTable {
  uint32_t tag;
  size_t offset;
  size_t length;
  uint32_t chksum;

  static bool SortByTag(const OutputTable& a, const OutputTable& b) {
    const uint32_t atag = ntohl(a.tag);
    const uint32_t btag = ntohl(b.tag);
    return atag < btag;
  }
};

struct BypassTable {
  uint32_t tag;
  size_t offset;  // offset into input data
  size_t length;
};

const struct {
  uint32_t tag;
  bool (*parse)(ots::OpenTypeFile *otf, const uint8_t *data, size_t length);
  bool (*serialise)(ots::OTSStream *out, ots::OpenTypeFile *file);
  bool (*should_serialise)(ots::OpenTypeFile *file);
  void (*free)(ots::OpenTypeFile *file);
  bool required;
  bool bypass;
} table_parsers[] = {
  { Tag("maxp"), ots::ots_maxp_parse, ots::ots_maxp_serialise,
    ots::ots_maxp_should_serialise, ots::ots_maxp_free, 1, 0 },
  { Tag("cmap"), ots::ots_cmap_parse, ots::ots_cmap_serialise,
    ots::ots_cmap_should_serialise, ots::ots_cmap_free, 1, 0 },
  { Tag("head"), ots::ots_head_parse, ots::ots_head_serialise,
    ots::ots_head_should_serialise, ots::ots_head_free, 1, 0 },
  { Tag("hhea"), ots::ots_hhea_parse, ots::ots_hhea_serialise,
    ots::ots_hhea_should_serialise, ots::ots_hhea_free, 1, 0 },
  { Tag("hmtx"), ots::ots_hmtx_parse, ots::ots_hmtx_serialise,
    ots::ots_hmtx_should_serialise, ots::ots_hmtx_free, 1, 0 },
  { Tag("name"), ots::ots_name_parse, ots::ots_name_serialise,
    ots::ots_name_should_serialise, ots::ots_name_free, 1, 0 },
  { Tag("OS/2"), ots::ots_os2_parse, ots::ots_os2_serialise,
    ots::ots_os2_should_serialise, ots::ots_os2_free, 1, 0 },
  { Tag("post"), ots::ots_post_parse, ots::ots_post_serialise,
    ots::ots_post_should_serialise, ots::ots_post_free, 1, 0 },
  { Tag("loca"), ots::ots_loca_parse, ots::ots_loca_serialise,
    ots::ots_loca_should_serialise, ots::ots_loca_free, 0, 0 },
  { Tag("glyf"), ots::ots_glyf_parse, ots::ots_glyf_serialise,
    ots::ots_glyf_should_serialise, ots::ots_glyf_free, 0, 0 },
  { Tag("CFF "), ots::ots_cff_parse, ots::ots_cff_serialise,
    ots::ots_cff_should_serialise, ots::ots_cff_free, 0, 0 },
  { Tag("VDMX"), ots::ots_vdmx_parse, ots::ots_vdmx_serialise,
    ots::ots_vdmx_should_serialise, ots::ots_vdmx_free, 0, 0 },
  { Tag("hdmx"), ots::ots_hdmx_parse, ots::ots_hdmx_serialise,
    ots::ots_hdmx_should_serialise, ots::ots_hdmx_free, 0, 0 },
  { Tag("gasp"), ots::ots_gasp_parse, ots::ots_gasp_serialise,
    ots::ots_gasp_should_serialise, ots::ots_gasp_free, 0, 0 },
  { Tag("cvt "), ots::ots_cvt_parse, ots::ots_cvt_serialise,
    ots::ots_cvt_should_serialise, ots::ots_cvt_free, 0, 0 },
  { Tag("fpgm"), ots::ots_fpgm_parse, ots::ots_fpgm_serialise,
    ots::ots_fpgm_should_serialise, ots::ots_fpgm_free, 0, 0 },
  { Tag("prep"), ots::ots_prep_parse, ots::ots_prep_serialise,
    ots::ots_prep_should_serialise, ots::ots_prep_free, 0, 0 },
  { Tag("LTSH"), ots::ots_ltsh_parse, ots::ots_ltsh_serialise,
    ots::ots_ltsh_should_serialise, ots::ots_ltsh_free, 0, 0 },
  { Tag("VORG"), ots::ots_vorg_parse, ots::ots_vorg_serialise,
    ots::ots_vorg_should_serialise, ots::ots_vorg_free, 0, 0 },
  { 0, NULL, NULL, NULL, 0, 0, 0 },
};

bool DoProcess(ots::OpenTypeFile *header,
               ots::OTSStream *output, const uint8_t *data, size_t length) {
  ots::Buffer file(data, length);

  // we disallow all files > 1GB in size for sanity.
  if (length > 1024 * 1024 * 1024) {
    return OTS_FAILURE();
  }

  if (!file.ReadTag(&header->version)) {
    return OTS_FAILURE();
  }
  if ((header->version != Tag("\x00\x01\x00\x00")) &&
      // OpenType fonts with CFF data have 'OTTO' tag.
      (header->version != Tag("OTTO")) &&
      // Older Mac fonts might have 'true' or 'typ1' tag.
      (header->version != Tag("true")) && (header->version != Tag("typ1"))) {
    return OTS_FAILURE();
  }

  if (!file.ReadU16(&header->num_tables) ||
      !file.ReadU16(&header->search_range) ||
      !file.ReadU16(&header->entry_selector) ||
      !file.ReadU16(&header->range_shift)) {
    return OTS_FAILURE();
  }

  // search_range is (Maximum power of 2 <= numTables) x 16. Thus, to avoid
  // overflow num_tables is, at most, 2^16 / 16 = 2^12
  if (header->num_tables >= 4096 || header->num_tables < 1) {
    return OTS_FAILURE();
  }

  unsigned max_pow2 = 0;
  while (1u << (max_pow2 + 1) <= header->num_tables) {
    max_pow2++;
  }
  const uint16_t expected_search_range = (1u << max_pow2) << 4;

  // Don't call ots_failure() here since ~25% of fonts (250+ fonts) in
  // http://www.princexml.com/fonts/ have bad search_range value.
  if (header->search_range != expected_search_range) {
    OTS_WARNING("bad search range");
    header->search_range = expected_search_range;  // Fix the value.
  }

  // entry_selector is Log2(maximum power of 2 <= numTables)
  if (header->entry_selector != max_pow2) {
    return OTS_FAILURE();
  }

  // range_shift is NumTables x 16-searchRange. We know that 16*num_tables
  // doesn't over flow because we range checked it above. Also, we know that
  // it's > header->search_range by construction of search_range.
  const uint32_t expected_range_shift
      = 16 * header->num_tables - header->search_range;
  if (header->range_shift != expected_range_shift) {
    OTS_WARNING("bad range shift");
    header->range_shift = expected_range_shift;  // the same as above.
  }

  // Next up is the list of tables.
  std::vector<OpenTypeTable> tables;

  for (unsigned i = 0; i < header->num_tables; ++i) {
    OpenTypeTable table;
    if (!file.ReadTag(&table.tag) ||
        !file.ReadU32(&table.chksum) ||
        !file.ReadU32(&table.offset) ||
        !file.ReadU32(&table.length)) {
      return OTS_FAILURE();
    }

    tables.push_back(table);
  }

  const size_t data_offset = file.offset();

  for (unsigned i = 0; i < header->num_tables; ++i) {
    // the tables must be sorted by tag (when taken as big-endian numbers).
    // This also remove the possibility of duplicate tables.
    if (i) {
      const uint32_t this_tag = ntohl(tables[i].tag);
      const uint32_t prev_tag = ntohl(tables[i - 1].tag);
      if (this_tag <= prev_tag) {
        return OTS_FAILURE();
      }
    }

    // all tag names must be built from printing characters
    if (!CheckTag(tables[i].tag)) {
      return OTS_FAILURE();
    }

    // tables must be 4-byte aligned
    if (tables[i].offset & 3) {
      return OTS_FAILURE();
    }

    // and must be within the file
    if (tables[i].offset < data_offset || tables[i].offset >= length) {
      return OTS_FAILURE();
    }
    // disallow all tables with a zero length
    if (tables[i].length < 1) {
      // Note: malayalam.ttf has zero length CVT table...
      return OTS_FAILURE();
    }
    // disallow all tables with a length > 1GB
    if (tables[i].length > 1024 * 1024 * 1024) {
      return OTS_FAILURE();
    }
    // since we required that the file be < 1GB in length, and that the table
    // length is < 1GB, the following addtion doesn't overflow
    const uint32_t end_byte = Round4(tables[i].offset + tables[i].length);
    if (!end_byte || end_byte > length) {
      return OTS_FAILURE();
    }
  }

  std::map<uint32_t, OpenTypeTable> table_map;
  for (unsigned i = 0; i < header->num_tables; ++i) {
    table_map[tables[i].tag] = tables[i];
  }

  // check that the tables are not overlapping.
  std::vector<std::pair<uint32_t, uint8_t> > overlap_checker;
  for (unsigned i = 0; i < header->num_tables; ++i) {
    overlap_checker.push_back(
        std::make_pair(tables[i].offset, 1 /* start */));
    overlap_checker.push_back(
        std::make_pair(tables[i].offset + tables[i].length, 0 /* end */));
  }
  std::sort(overlap_checker.begin(), overlap_checker.end());
  int overlap_count = 0;
  for (unsigned i = 0; i < overlap_checker.size(); ++i) {
    overlap_count += (overlap_checker[i].second ? 1 : -1);
    if (overlap_count > 1) {
      return OTS_FAILURE();
    }
  }

  std::vector<BypassTable> bypass_tables;

  for (unsigned i = 0; ; ++i) {
    if (table_parsers[i].parse == NULL) break;

    const std::map<uint32_t, OpenTypeTable>::const_iterator it
        = table_map.find(table_parsers[i].tag);

    if (it == table_map.end()) {
      if (table_parsers[i].required) {
        return OTS_FAILURE();
      }
      continue;
    }

    if (table_parsers[i].bypass) {
      BypassTable bypass;
      bypass.offset = it->second.offset;
      bypass.length = it->second.length;
      bypass.tag = table_parsers[i].tag;
      bypass_tables.push_back(bypass);
    }

    if (!table_parsers[i].parse(
        header, data + it->second.offset, it->second.length)) {
      return OTS_FAILURE();
    }
  }

  if (header->cff) {
    // font with PostScript glyph
    if (header->version != Tag("OTTO")) {
      return OTS_FAILURE();
    }
    if (header->glyf || header->loca) {
      // mixing outline formats are not recommended
      return OTS_FAILURE();
    }
  } else {
    if (!header->glyf || !header->loca) {
      // No TrueType glyph found.
      // Note: bitmap-only fonts are not supported.
      return OTS_FAILURE();
    }
  }

  unsigned num_output_tables = 0;
  for (unsigned i = 0; ; ++i) {
    if (table_parsers[i].parse == NULL) {
      break;
    }

    if (table_parsers[i].bypass) {
      continue;
    }

    if (table_parsers[i].should_serialise(header)) {
      num_output_tables++;
    }
  }

  num_output_tables += bypass_tables.size();

  max_pow2 = 0;
  while (1u << (max_pow2 + 1) <= num_output_tables) {
    max_pow2++;
  }
  const uint16_t output_search_range = (1u << max_pow2) << 4;

  output->ResetChecksum();
  if (!output->WriteTag(header->version) ||
      !output->WriteU16(num_output_tables) ||
      !output->WriteU16(output_search_range) ||
      !output->WriteU16(max_pow2) ||
      !output->WriteU16((num_output_tables << 4) - output_search_range)) {
    return OTS_FAILURE();
  }
  const uint32_t offset_table_chksum = output->chksum();

  const size_t table_record_offset = output->Tell();
  if (!output->Pad(16 * num_output_tables)) {
    return OTS_FAILURE();
  }

  std::vector<OutputTable> out_tables;

  size_t head_table_offset = 0;
  for (unsigned i = 0; i < bypass_tables.size(); ++i) {
    const BypassTable &bypass = bypass_tables[i];

    OutputTable out;
    out.tag = bypass.tag;
    out.offset = output->Tell();

    output->ResetChecksum();
    if (bypass.tag == Tag("head")) {
      head_table_offset = out.offset;
    }
    if (!output->Write(data + bypass.offset, bypass.length)) {
      return OTS_FAILURE();
    }
    const size_t end_offset = output->Tell();
    out.length = end_offset - out.offset;

    // align tables to four bytes
    if (!output->Pad((4 - (end_offset & 3)) % 4)) {
      return OTS_FAILURE();
    }
    out.chksum = output->chksum();
    out_tables.push_back(out);
  }

  for (unsigned i = 0; ; ++i) {
    if (table_parsers[i].parse == NULL) {
      break;
    }

    if (table_parsers[i].bypass) {
      continue;
    }

    if (!table_parsers[i].should_serialise(header)) {
      continue;
    }

    OutputTable out;
    out.tag = table_parsers[i].tag;
    out.offset = output->Tell();

    output->ResetChecksum();
    if (table_parsers[i].tag == Tag("head")) {
      head_table_offset = out.offset;
    }
    if (!table_parsers[i].serialise(output, header)) {
      return OTS_FAILURE();
    }

    const size_t end_offset = output->Tell();
    out.length = end_offset - out.offset;

    // align tables to four bytes
    if (!output->Pad((4 - (end_offset & 3)) % 4)) {
      return OTS_FAILURE();
    }
    out.chksum = output->chksum();
    out_tables.push_back(out);
  }

  const size_t end_of_file = output->Tell();

  // Need to sort the output tables for inclusion in the file
  std::sort(out_tables.begin(), out_tables.end(), OutputTable::SortByTag);
  if (!output->Seek(table_record_offset)) {
    return OTS_FAILURE();
  }

  output->ResetChecksum();
  uint32_t tables_chksum = 0;
  for (unsigned i = 0; i < out_tables.size(); ++i) {
    if (!output->WriteTag(out_tables[i].tag) ||
        !output->WriteU32(out_tables[i].chksum) ||
        !output->WriteU32(out_tables[i].offset) ||
        !output->WriteU32(out_tables[i].length)) {
      return OTS_FAILURE();
    }
    tables_chksum += out_tables[i].chksum;
  }
  const uint32_t table_record_chksum = output->chksum();

  // http://www.microsoft.com/typography/otspec/otff.htm
  const uint32_t file_chksum
      = offset_table_chksum + tables_chksum + table_record_chksum;
  const uint32_t chksum_magic = static_cast<uint32_t>(0xb1b0afba) - file_chksum;

  // seek into the 'head' table and write in the checksum magic value
  assert(head_table_offset != 0);
  if (!output->Seek(head_table_offset + 8)) {
    return OTS_FAILURE();
  }
  if (!output->WriteU32(chksum_magic)) {
    return OTS_FAILURE();
  }

  if (!output->Seek(end_of_file)) {
    return OTS_FAILURE();
  }

  return true;
}

}  // namespace

namespace ots {

void DisableDebugOutput() {
  g_debug_output = false;
}

bool Process(OTSStream *output, const uint8_t *data, size_t length) {
  OpenTypeFile header;
  const bool result = DoProcess(&header, output, data, length);

  for (unsigned i = 0; ; ++i) {
    if (table_parsers[i].parse == NULL) break;
    table_parsers[i].free(&header);
  }
  return result;
}

#if !defined(_MSC_VER) && defined(OTS_DEBUG)
bool Failure(const char *f, int l, const char *fn) {
  if (g_debug_output) {
    std::fprintf(stderr, "ERROR at %s:%d (%s)\n", f, l, fn);
    std::fflush(stderr);
  }
  return false;
}

void Warning(const char *f, int l, const char *format, ...) {
  if (g_debug_output) {
    std::fprintf(stderr, "WARNING at %s:%d: ", f, l);
    std::va_list va;
    va_start(va, format);
    std::vfprintf(stderr, format, va);
    va_end(va);
    std::fprintf(stderr, "\n");
    std::fflush(stderr);
  }
}
#endif

}  // namespace ots