base/i18n/build_utf8_validator_tables.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // Create a state machine for validating UTF-8. The algorithm in brief:
   6 // 1. Convert the complete unicode range of code points, except for the
   7 //    surrogate code points, to an ordered array of sequences of bytes in
   8 //    UTF-8.
   9 // 2. Convert individual bytes to ranges, starting from the right of each byte
  10 //    sequence. For each range, ensure the bytes on the left and the ranges
  11 //    on the right are the identical.
  12 // 3. Convert the resulting list of ranges into a state machine, collapsing
  13 //    identical states.
  14 // 4. Convert the state machine to an array of bytes.
  15 // 5. Output as a C++ file.
  16 //
  17 // To use:
  18 //  $ ninja -C out/Release build_utf8_validator_tables
  19 //  $ out/Release/build_utf8_validator_tables
  20 //                                   --output=base/i18n/utf8_validator_tables.cc
  21 //  $ git add base/i18n/utf8_validator_tables.cc
  22 //
  23 // Because the table is not expected to ever change, it is checked into the
  24 // repository rather than being regenerated at build time.
  25 //
  26 // This code uses type uint8_t throughout to represent bytes, to avoid
  27 // signed/unsigned char confusion.
  28
  29 #include <stddef.h>
  30 #include <stdint.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 #include <algorithm>
  36 #include <map>
  37 #include <string>
  38 #include <vector>
  39
  40 #include "base/command_line.h"
  41 #include "base/files/file_path.h"
  42 #include "base/files/file_util.h"
  43 #include "base/logging.h"
  44 #include "base/macros.h"
  45 #include "base/numerics/safe_conversions.h"
  46 #include "base/strings/stringprintf.h"
  47 #include "third_party/icu/source/common/unicode/utf8.h"
  48
  49 namespace {
  50
  51 const char kHelpText[] =
  52     "Usage: build_utf8_validator_tables [ --help ] [ --output=<file> ]\n";
  53
  54 const char kProlog[] =
  55     "// Copyright 2013 The Chromium Authors. All rights reserved.\n"
  56     "// Use of this source code is governed by a BSD-style license that can "
  57     "be\n"
  58     "// found in the LICENSE file.\n"
  59     "\n"
  60     "// This file is auto-generated by build_utf8_validator_tables.\n"
  61     "// DO NOT EDIT.\n"
  62     "\n"
  63     "#include \"base/i18n/utf8_validator_tables.h\"\n"
  64     "\n"
  65     "namespace base {\n"
  66     "namespace internal {\n"
  67     "\n"
  68     "const uint8_t kUtf8ValidatorTables[] = {\n";
  69
  70 const char kEpilog[] =
  71     "};\n"
  72     "\n"
  73     "const size_t kUtf8ValidatorTablesSize = arraysize(kUtf8ValidatorTables);\n"
  74     "\n"
  75     "}  // namespace internal\n"
  76     "}  // namespace base\n";
  77
  78 // Ranges are inclusive at both ends--they represent [from, to]
  79 class Range {
  80  public:
  81   // Ranges always start with just one byte.
  82   explicit Range(uint8_t value) : from_(value), to_(value) {}
  83
  84   // Range objects are copyable and assignable to be used in STL
  85   // containers. Since they only contain non-pointer POD types, the default copy
  86   // constructor, assignment operator and destructor will work.
  87
  88   // Add a byte to the range. We intentionally only support adding a byte at the
  89   // end, since that is the only operation the code needs.
  90   void AddByte(uint8_t to) {
  91     CHECK(to == to_ + 1);
  92     to_ = to;
  93   }
  94
  95   uint8_t from() const { return from_; }
  96   uint8_t to() const { return to_; }
  97
  98   bool operator<(const Range& rhs) const {
  99     return (from() < rhs.from() || (from() == rhs.from() && to() < rhs.to()));
 100   }
 101
 102   bool operator==(const Range& rhs) const {
 103     return from() == rhs.from() && to() == rhs.to();
 104   }
 105
 106  private:
 107   uint8_t from_;
 108   uint8_t to_;
 109 };
 110
 111 // A vector of Ranges is like a simple regular expression--it corresponds to
 112 // a set of strings of the same length that have bytes in each position in
 113 // the appropriate range.
 114 typedef std::vector<Range> StringSet;
 115
 116 // A UTF-8 "character" is represented by a sequence of bytes.
 117 typedef std::vector<uint8_t> Character;
 118
 119 // In the second stage of the algorithm, we want to convert a large list of
 120 // Characters into a small list of StringSets.
 121 struct Pair {
 122   Character character;
 123   StringSet set;
 124 };
 125
 126 typedef std::vector<Pair> PairVector;
 127
 128 // A class to print a table of numbers in the same style as clang-format.
 129 class TablePrinter {
 130  public:
 131   explicit TablePrinter(FILE* stream)
 132       : stream_(stream), values_on_this_line_(0), current_offset_(0) {}
 133
 134   void PrintValue(uint8_t value) {
 135     if (values_on_this_line_ == 0) {
 136       fputs("   ", stream_);
 137     } else if (values_on_this_line_ == kMaxValuesPerLine) {
 138       fprintf(stream_, "  // 0x%02x\n   ", current_offset_);
 139       values_on_this_line_ = 0;
 140     }
 141     fprintf(stream_, " 0x%02x,", static_cast<int>(value));
 142     ++values_on_this_line_;
 143     ++current_offset_;
 144   }
 145
 146   void NewLine() {
 147     while (values_on_this_line_ < kMaxValuesPerLine) {
 148       fputs("      ", stream_);
 149       ++values_on_this_line_;
 150     }
 151     fprintf(stream_, "  // 0x%02x\n", current_offset_);
 152     values_on_this_line_ = 0;
 153   }
 154
 155  private:
 156   // stdio stream. Not owned.
 157   FILE* stream_;
 158
 159   // Number of values so far printed on this line.
 160   int values_on_this_line_;
 161
 162   // Total values printed so far.
 163   int current_offset_;
 164
 165   static const int kMaxValuesPerLine = 8;
 166
 167   DISALLOW_COPY_AND_ASSIGN(TablePrinter);
 168 };
 169
 170 // Start by filling a PairVector with characters. The resulting vector goes from
 171 // "\x00" to "\xf4\x8f\xbf\xbf".
 172 PairVector InitializeCharacters() {
 173   PairVector vector;
 174   for (int i = 0; i <= 0x10FFFF; ++i) {
 175     if (i >= 0xD800 && i < 0xE000) {
 176       // Surrogate codepoints are not permitted. Non-character code points are
 177       // explicitly permitted.
 178       continue;
 179     }
 180     uint8_t bytes[4];
 181     unsigned int offset = 0;
 182     UBool is_error = false;
 183     U8_APPEND(bytes, offset, arraysize(bytes), i, is_error);
 184     DCHECK(!is_error);
 185     DCHECK_GT(offset, 0u);
 186     DCHECK_LE(offset, arraysize(bytes));
 187     Pair pair = {Character(bytes, bytes + offset), StringSet()};
 188     vector.push_back(pair);
 189   }
 190   return vector;
 191 }
 192
 193 // Construct a new Pair from |character| and the concatenation of |new_range|
 194 // and |existing_set|, and append it to |pairs|.
 195 void ConstructPairAndAppend(const Character& character,
 196                             const Range& new_range,
 197                             const StringSet& existing_set,
 198                             PairVector* pairs) {
 199   Pair new_pair = {character, StringSet(1, new_range)};
 200   new_pair.set.insert(
 201       new_pair.set.end(), existing_set.begin(), existing_set.end());
 202   pairs->push_back(new_pair);
 203 }
 204
 205 // Each pass over the PairVector strips one byte off the right-hand-side of the
 206 // characters and adds a range to the set on the right. For example, the first
 207 // pass converts the range from "\xe0\xa0\x80" to "\xe0\xa0\xbf" to ("\xe0\xa0",
 208 // [\x80-\xbf]), then the second pass converts the range from ("\xe0\xa0",
 209 // [\x80-\xbf]) to ("\xe0\xbf", [\x80-\xbf]) to ("\xe0",
 210 // [\xa0-\xbf][\x80-\xbf]).
 211 void MoveRightMostCharToSet(PairVector* pairs) {
 212   PairVector new_pairs;
 213   PairVector::const_iterator it = pairs->begin();
 214   while (it != pairs->end() && it->character.empty()) {
 215     new_pairs.push_back(*it);
 216     ++it;
 217   }
 218   CHECK(it != pairs->end());
 219   Character unconverted_bytes(it->character.begin(), it->character.end() - 1);
 220   Range new_range(it->character.back());
 221   StringSet converted = it->set;
 222   ++it;
 223   while (it != pairs->end()) {
 224     const Pair& current_pair = *it++;
 225     if (current_pair.character.size() == unconverted_bytes.size() + 1 &&
 226         std::equal(unconverted_bytes.begin(),
 227                    unconverted_bytes.end(),
 228                    current_pair.character.begin()) &&
 229         converted == current_pair.set) {
 230       // The particular set of UTF-8 codepoints we are validating guarantees
 231       // that each byte range will be contiguous. This would not necessarily be
 232       // true for an arbitrary set of UTF-8 codepoints.
 233       DCHECK_EQ(new_range.to() + 1, current_pair.character.back());
 234       new_range.AddByte(current_pair.character.back());
 235       continue;
 236     }
 237     ConstructPairAndAppend(unconverted_bytes, new_range, converted, &new_pairs);
 238     unconverted_bytes = Character(current_pair.character.begin(),
 239                                   current_pair.character.end() - 1);
 240     new_range = Range(current_pair.character.back());
 241     converted = current_pair.set;
 242   }
 243   ConstructPairAndAppend(unconverted_bytes, new_range, converted, &new_pairs);
 244   new_pairs.swap(*pairs);
 245 }
 246
 247 void MoveAllCharsToSets(PairVector* pairs) {
 248   // Since each pass of the function moves one character, and UTF-8 sequences
 249   // are at most 4 characters long, this simply runs the algorithm four times.
 250   for (int i = 0; i < 4; ++i) {
 251     MoveRightMostCharToSet(pairs);
 252   }
 253 #if DCHECK_IS_ON()
 254   for (PairVector::const_iterator it = pairs->begin(); it != pairs->end();
 255        ++it) {
 256     DCHECK(it->character.empty());
 257   }
 258 #endif
 259 }
 260
 261 // Logs the generated string sets in regular-expression style, ie. [\x00-\x7f],
 262 // [\xc2-\xdf][\x80-\xbf], etc. This can be a useful sanity-check that the
 263 // algorithm is working. Use the command-line option
 264 // --vmodule=build_utf8_validator_tables=1 to see this output.
 265 void LogStringSets(const PairVector& pairs) {
 266   for (auto pair_it = pairs.begin(); pair_it != pairs.end(); ++pair_it) {
 267     std::string set_as_string;
 268     for (auto set_it = pair_it->set.begin(); set_it != pair_it->set.end();
 269          ++set_it) {
 270       set_as_string += base::StringPrintf("[\\x%02x-\\x%02x]",
 271                                           static_cast<int>(set_it->from()),
 272                                           static_cast<int>(set_it->to()));
 273     }
 274     VLOG(1) << set_as_string;
 275   }
 276 }
 277
 278 // A single state in the state machine is represented by a sorted vector of
 279 // start bytes and target states. All input bytes in the range between the start
 280 // byte and the next entry in the vector (or 0xFF) result in a transition to the
 281 // target state.
 282 struct StateRange {
 283   uint8_t from;
 284   uint8_t target_state;
 285 };
 286
 287 typedef std::vector<StateRange> State;
 288
 289 // Generates a state where all bytes go to state 1 (invalid). This is also used
 290 // as an initialiser for other states (since bytes from outside the desired
 291 // range are invalid).
 292 State GenerateInvalidState() {
 293   const StateRange range = {0, 1};
 294   return State(1, range);
 295 }
 296
 297 // A map from a state (ie. a set of strings which will match from this state) to
 298 // a number (which is an index into the array of states).
 299 typedef std::map<StringSet, uint8_t> StateMap;
 300
 301 // Create a new state corresponding to |set|, add it |states| and |state_map|
 302 // and return the index it was given in |states|.
 303 uint8_t MakeState(const StringSet& set,
 304                   std::vector<State>* states,
 305                   StateMap* state_map) {
 306   DCHECK(!set.empty());
 307   const Range& range = set.front();
 308   const StringSet rest(set.begin() + 1, set.end());
 309   const StateMap::const_iterator where = state_map->find(rest);
 310   const uint8_t target_state = where == state_map->end()
 311                                    ? MakeState(rest, states, state_map)
 312                                    : where->second;
 313   DCHECK_LT(0, range.from());
 314   DCHECK_LT(range.to(), 0xFF);
 315   const StateRange new_state_initializer[] = {
 316       {0, 1},
 317       {range.from(), target_state},
 318       {static_cast<uint8_t>(range.to() + 1), 1}};
 319   states->push_back(
 320       State(new_state_initializer,
 321             new_state_initializer + arraysize(new_state_initializer)));
 322   const uint8_t new_state_number =
 323       base::checked_cast<uint8_t>(states->size() - 1);
 324   CHECK(state_map->insert(std::make_pair(set, new_state_number)).second);
 325   return new_state_number;
 326 }
 327
 328 std::vector<State> GenerateStates(const PairVector& pairs) {
 329   // States 0 and 1 are the initial/valid state and invalid state, respectively.
 330   std::vector<State> states(2, GenerateInvalidState());
 331   StateMap state_map;
 332   state_map.insert(std::make_pair(StringSet(), 0));
 333   for (auto it = pairs.begin(); it != pairs.end(); ++it) {
 334     DCHECK(it->character.empty());
 335     DCHECK(!it->set.empty());
 336     const Range& range = it->set.front();
 337     const StringSet rest(it->set.begin() + 1, it->set.end());
 338     const StateMap::const_iterator where = state_map.find(rest);
 339     const uint8_t target_state = where == state_map.end()
 340                                      ? MakeState(rest, &states, &state_map)
 341                                      : where->second;
 342     if (states[0].back().from == range.from()) {
 343       DCHECK_EQ(1, states[0].back().target_state);
 344       states[0].back().target_state = target_state;
 345       DCHECK_LT(range.to(), 0xFF);
 346       const StateRange new_range = {static_cast<uint8_t>(range.to() + 1), 1};
 347       states[0].push_back(new_range);
 348     } else {
 349       DCHECK_LT(range.to(), 0xFF);
 350       const StateRange new_range_initializer[] = {
 351           {range.from(), target_state},
 352           {static_cast<uint8_t>(range.to() + 1), 1}};
 353       states[0]
 354           .insert(states[0].end(),
 355                   new_range_initializer,
 356                   new_range_initializer + arraysize(new_range_initializer));
 357     }
 358   }
 359   return states;
 360 }
 361
 362 // Output the generated states as a C++ table. Two tricks are used to compact
 363 // the table: each state in the table starts with a shift value which indicates
 364 // how many bits we can discard from the right-hand-side of the byte before
 365 // doing the table lookup. Secondly, only the state-transitions for bytes
 366 // with the top-bit set are included in the table; bytes without the top-bit set
 367 // are just ASCII and are handled directly by the code.
 368 void PrintStates(const std::vector<State>& states, FILE* stream) {
 369   // First calculate the start-offset of each state. This allows the state
 370   // machine to jump directly to the correct offset, avoiding an extra
 371   // indirection. State 0 starts at offset 0.
 372   std::vector<uint8_t> state_offset(1, 0);
 373   std::vector<uint8_t> shifts;
 374   uint8_t pos = 0;
 375
 376   for (auto state_it = states.begin(); state_it != states.end(); ++state_it) {
 377     // We want to set |shift| to the (0-based) index of the least-significant
 378     // set bit in any of the ranges for this state, since this tells us how many
 379     // bits we can discard and still determine what range a byte lies in. Sadly
 380     // it appears that ffs() is not portable, so we do it clumsily.
 381     uint8_t shift = 7;
 382     for (auto range_it = state_it->begin(); range_it != state_it->end();
 383          ++range_it) {
 384       while (shift > 0 && range_it->from % (1 << shift) != 0) {
 385         --shift;
 386       }
 387     }
 388     shifts.push_back(shift);
 389     pos += 1 + (1 << (7 - shift));
 390     state_offset.push_back(pos);
 391   }
 392
 393   DCHECK_EQ(129, state_offset[1]);
 394
 395   fputs(kProlog, stream);
 396   TablePrinter table_printer(stream);
 397
 398   for (uint8_t state_index = 0; state_index < states.size(); ++state_index) {
 399     const uint8_t shift = shifts[state_index];
 400     uint8_t next_range = 0;
 401     uint8_t target_state = 1;
 402     fprintf(stream,
 403             "    // State %d, offset 0x%02x\n",
 404             static_cast<int>(state_index),
 405             static_cast<int>(state_offset[state_index]));
 406     table_printer.PrintValue(shift);
 407     for (int i = 0; i < 0x100; i += (1 << shift)) {
 408       if (next_range < states[state_index].size() &&
 409           states[state_index][next_range].from == i) {
 410         target_state = states[state_index][next_range].target_state;
 411         ++next_range;
 412       }
 413       if (i >= 0x80) {
 414         table_printer.PrintValue(state_offset[target_state]);
 415       }
 416     }
 417     table_printer.NewLine();
 418   }
 419
 420   fputs(kEpilog, stream);
 421 }
 422
 423 }  // namespace
 424
 425 int main(int argc, char* argv[]) {
 426   base::CommandLine::Init(argc, argv);
 427   logging::LoggingSettings settings;
 428   settings.logging_dest = logging::LOG_TO_SYSTEM_DEBUG_LOG;
 429   logging::InitLogging(settings);
 430   if (base::CommandLine::ForCurrentProcess()->HasSwitch("help")) {
 431     fwrite(kHelpText, 1, arraysize(kHelpText), stdout);
 432     exit(EXIT_SUCCESS);
 433   }
 434   base::FilePath filename =
 435       base::CommandLine::ForCurrentProcess()->GetSwitchValuePath("output");
 436
 437   FILE* output = stdout;
 438   if (!filename.empty()) {
 439     output = base::OpenFile(filename, "wb");
 440     if (!output)
 441       PLOG(FATAL) << "Couldn't open '" << filename.AsUTF8Unsafe()
 442                   << "' for writing";
 443   }
 444
 445   // Step 1: Enumerate the characters
 446   PairVector pairs = InitializeCharacters();
 447   // Step 2: Convert to sets.
 448   MoveAllCharsToSets(&pairs);
 449   if (VLOG_IS_ON(1)) {
 450     LogStringSets(pairs);
 451   }
 452   // Step 3: Generate states.
 453   std::vector<State> states = GenerateStates(pairs);
 454   // Step 4/5: Print output
 455   PrintStates(states, output);
 456
 457   if (!filename.empty()) {
 458     if (!base::CloseFile(output))
 459       PLOG(FATAL) << "Couldn't finish writing '" << filename.AsUTF8Unsafe()
 460                   << "'";
 461   }
 462
 463   return EXIT_SUCCESS;
 464 }