build_utf8_validator_tables.cc 16 KB

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