1 #include "simdjson.h"
2 #include <cstddef>
3 #include <cstdint>
4 #include <random>
5
6 class RandomUTF8 final {
7 public:
8 RandomUTF8(std::random_device &rd, int prob_1byte, int prob_2bytes,
9 int prob_3bytes, int prob_4bytes);
10
11 std::vector<uint8_t> generate(size_t output_bytes);
12 std::vector<uint8_t> generate(size_t output_bytes, long seed);
13
14 private:
15 uint32_t generate();
16
17 std::mt19937 gen;
18 std::discrete_distribution<> bytes_count;
19 std::uniform_int_distribution<int> val_7bit{0x00, 0x7f}; // 0b0xxxxxxx
20 std::uniform_int_distribution<int> val_6bit{0x00, 0x3f}; // 0b10xxxxxx
21 std::uniform_int_distribution<int> val_5bit{0x00, 0x1f}; // 0b110xxxxx
22 std::uniform_int_distribution<int> val_4bit{0x00, 0x0f}; // 0b1110xxxx
23 std::uniform_int_distribution<int> val_3bit{0x00, 0x07}; // 0b11110xxx
24 };
25
RandomUTF8(std::random_device & rd,int prob_1byte,int prob_2bytes,int prob_3bytes,int prob_4bytes)26 RandomUTF8::RandomUTF8(std::random_device &rd, int prob_1byte, int prob_2bytes,
27 int prob_3bytes, int prob_4bytes)
28 : gen(rd()), bytes_count({double(prob_1byte), double(prob_2bytes),
29 double(prob_3bytes), double(prob_4bytes)}) {}
30
generate(size_t output_bytes)31 std::vector<uint8_t> RandomUTF8::generate(size_t output_bytes) {
32 std::vector<uint8_t> result;
33 result.reserve(output_bytes);
34 uint8_t candidate, head;
35 while (result.size() < output_bytes) {
36 switch (bytes_count(gen)) {
37 case 0: // 1 byte
38 candidate = uint8_t(val_7bit(gen));
39 while (candidate == 0) { // though strictly speaking, a stream of nulls is
40 // UTF8, it tends to break some code
41 candidate = uint8_t(val_7bit(gen));
42 }
43 result.push_back(candidate);
44 break;
45 case 1: // 2 bytes
46 candidate = 0xc0 | uint8_t(val_5bit(gen));
47 while (candidate < 0xC2) {
48 candidate = 0xc0 | uint8_t(val_5bit(gen));
49 }
50 result.push_back(candidate);
51 result.push_back(0x80 | uint8_t(val_6bit(gen)));
52 break;
53 case 2: // 3 bytes
54 head = 0xe0 | uint8_t(val_4bit(gen));
55 result.push_back(head);
56 candidate = 0x80 | uint8_t(val_6bit(gen));
57 if (head == 0xE0) {
58 while (candidate < 0xA0) {
59 candidate = 0x80 | uint8_t(val_6bit(gen));
60 }
61 } else if (head == 0xED) {
62 while (candidate > 0x9F) {
63 candidate = 0x80 | uint8_t(val_6bit(gen));
64 }
65 }
66 result.push_back(candidate);
67 result.push_back(0x80 | uint8_t(val_6bit(gen)));
68 break;
69 case 3: // 4 bytes
70 head = 0xf0 | uint8_t(val_3bit(gen));
71 while (head > 0xF4) {
72 head = 0xf0 | uint8_t(val_3bit(gen));
73 }
74 result.push_back(head);
75 candidate = 0x80 | uint8_t(val_6bit(gen));
76 if (head == 0xF0) {
77 while (candidate < 0x90) {
78 candidate = 0x80 | uint8_t(val_6bit(gen));
79 }
80 } else if (head == 0xF4) {
81 while (candidate > 0x8F) {
82 candidate = 0x80 | uint8_t(val_6bit(gen));
83 }
84 }
85 result.push_back(candidate);
86 result.push_back(0x80 | uint8_t(val_6bit(gen)));
87 result.push_back(0x80 | uint8_t(val_6bit(gen)));
88 break;
89 }
90 }
91 result.push_back(0); // EOS for scalar code
92
93 return result;
94 }
95
generate(size_t output_bytes,long seed)96 std::vector<uint8_t> RandomUTF8::generate(size_t output_bytes, long seed) {
97 gen.seed(uint32_t(seed));
98 return generate(output_bytes);
99 }
100
101 // credit: based on code from Google Fuchsia (Apache Licensed)
basic_validate_utf8(const char * buf,size_t len)102 simdjson_warn_unused bool basic_validate_utf8(const char *buf, size_t len) noexcept {
103 const uint8_t *data = (const uint8_t *)buf;
104 uint64_t pos = 0;
105 uint64_t next_pos = 0;
106 uint32_t code_point = 0;
107 while (pos < len) {
108 unsigned char byte = data[pos];
109 if (byte < 0b10000000) {
110 pos++;
111 continue;
112 } else if ((byte & 0b11100000) == 0b11000000) {
113 next_pos = pos + 2;
114 if (next_pos > len) { return false; }
115 if ((data[pos + 1] & 0b11000000) != 0b10000000) {
116 return false;
117 }
118 // range check
119 code_point = (byte & 0b00011111) << 6 | (data[pos + 1] & 0b00111111);
120 if (code_point < 0x80 || 0x7ff < code_point) { return false; }
121 } else if ((byte & 0b11110000) == 0b11100000) {
122 next_pos = pos + 3;
123 if (next_pos > len) { return false; }
124 if ((data[pos + 1] & 0b11000000) != 0b10000000) { return false; }
125 if ((data[pos + 2] & 0b11000000) != 0b10000000) { return false; }
126 // range check
127 code_point = (byte & 0b00001111) << 12 |
128 (data[pos + 1] & 0b00111111) << 6 |
129 (data[pos + 2] & 0b00111111);
130 if (code_point < 0x800 || 0xffff < code_point ||
131 (0xd7ff < code_point && code_point < 0xe000)) {
132 return false;
133 }
134 } else if ((byte & 0b11111000) == 0b11110000) { // 0b11110000
135 next_pos = pos + 4;
136 if (next_pos > len) { return false; }
137 if ((data[pos + 1] & 0b11000000) != 0b10000000) { return false; }
138 if ((data[pos + 2] & 0b11000000) != 0b10000000) { return false; }
139 if ((data[pos + 3] & 0b11000000) != 0b10000000) { return false; }
140 // range check
141 code_point =
142 (byte & 0b00000111) << 18 | (data[pos + 1] & 0b00111111) << 12 |
143 (data[pos + 2] & 0b00111111) << 6 | (data[pos + 3] & 0b00111111);
144 if (code_point < 0xffff || 0x10ffff < code_point) {
145 return false;
146 }
147 } else {
148 // we may have a continuation
149 return false;
150 }
151 pos = next_pos;
152 }
153 return true;
154 }
155
brute_force_tests()156 void brute_force_tests() {
157 printf("running brute-force UTF-8 tests... ");
158 fflush(NULL);
159 std::random_device rd{};
160 RandomUTF8 gen_1_2_3_4(rd, 1, 1, 1, 1);
161 size_t total = 1000;
162 for (size_t i = 0; i < total; i++) {
163
164 auto UTF8 = gen_1_2_3_4.generate(rand() % 256);
165 if (!simdjson::validate_utf8((const char *)UTF8.data(), UTF8.size())) {
166 std::cerr << "bug" << std::endl;
167 abort();
168 }
169 for (size_t flip = 0; flip < 1000; ++flip) {
170 // we are going to hack the string as long as it is UTF-8
171 const int bitflip{1 << (rand() % 8)};
172 UTF8[rand() % UTF8.size()] = uint8_t(bitflip); // we flip exactly one bit
173 bool is_ok =
174 simdjson::validate_utf8((const char *)UTF8.data(), UTF8.size());
175 bool is_ok_basic =
176 basic_validate_utf8((const char *)UTF8.data(), UTF8.size());
177 if (is_ok != is_ok_basic) {
178 std::cerr << "bug" << std::endl;
179 abort();
180 }
181 }
182 }
183 printf("tests ok.\n");
184 }
185
test()186 void test() {
187 printf("running hard-coded UTF-8 tests... ");
188 fflush(NULL);
189 // additional tests are from autobahn websocket testsuite
190 // https://github.com/crossbario/autobahn-testsuite/tree/master/autobahntestsuite/autobahntestsuite/case
191 const char *goodsequences[] = {"a",
192 "\xc3\xb1",
193 "\xe2\x82\xa1",
194 "\xf0\x90\x8c\xbc",
195 "\xc2\x80", // 6.7.2
196 "\xf0\x90\x80\x80", // 6.7.4
197 "\xee\x80\x80", // 6.11.2
198 "\xef\xbb\xbf"};
199 const char *badsequences[] = {
200 "\xc3\x28", // 0
201 "\xa0\xa1", // 1
202 "\xe2\x28\xa1", // 2
203 "\xe2\x82\x28", // 3
204 "\xf0\x28\x8c\xbc", // 4
205 "\xf0\x90\x28\xbc", // 5
206 "\xf0\x28\x8c\x28", // 6
207 "\xc0\x9f", // 7
208 "\xf5\xff\xff\xff", // 8
209 "\xed\xa0\x81", // 9
210 "\xf8\x90\x80\x80\x80", // 10
211 "123456789012345\xed", // 11
212 "123456789012345\xf1", // 12
213 "123456789012345\xc2", // 13
214 "\xC2\x7F", // 14
215 "\xce", // 6.6.1
216 "\xce\xba\xe1", // 6.6.3
217 "\xce\xba\xe1\xbd", // 6.6.4
218 "\xce\xba\xe1\xbd\xb9\xcf", // 6.6.6
219 "\xce\xba\xe1\xbd\xb9\xcf\x83\xce", // 6.6.8
220 "\xce\xba\xe1\xbd\xb9\xcf\x83\xce\xbc\xce", // 6.6.10
221 "\xdf", // 6.14.6
222 "\xef\xbf", // 6.14.7
223 "\x80",
224 "\x91\x85\x95\x9e",
225 "\x6c\x02\x8e\x18",
226 "\x25\x5b\x6e\x2c\x32\x2c\x5b\x5b\x33\x2c\x34\x2c\x05\x29\x2c\x33\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5d\x2c\x35\x2e\x33\x2c\x39\x2e\x33\x2c\x37\x2e\x33\x2c\x39\x2e\x34\x2c\x37\x2e\x33\x2c\x39\x2e\x33\x2c\x37\x2e\x33\x2c\x39\x2e\x34\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x20\x01\x01\x01\x01\x01\x02\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x23\x0a\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x7e\x7e\x0a\x0a\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5d\x2c\x37\x2e\x33\x2c\x39\x2e\x33\x2c\x37\x2e\x33\x2c\x39\x2e\x34\x2c\x37\x2e\x33\x2c\x39\x2e\x33\x2c\x37\x2e\x33\x2c\x39\x2e\x34\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x01\x01\x80\x01\x01\x01\x79\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01",
227 "[[[[[[[[[[[[[[[\x80\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x010\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01",
228 "\x20\x0b\x01\x01\x01\x64\x3a\x64\x3a\x64\x3a\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x30\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x80\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"};
229 for (size_t i = 0; i < sizeof(goodsequences)/sizeof(goodsequences[0]); i++) {
230 size_t len = std::strlen(goodsequences[i]);
231 if (!simdjson::validate_utf8(goodsequences[i], len)) {
232 printf("bug goodsequences[%zu]\n", i);
233 abort();
234 }
235 }
236 for (size_t i = 0; i < sizeof(badsequences)/sizeof(badsequences[0]); i++) {
237 size_t len = std::strlen(badsequences[i]);
238 if (simdjson::validate_utf8(badsequences[i], len)) {
239 printf("bug lookup2 badsequences[%zu]\n", i);
240 abort();
241 }
242 }
243 printf("tests ok.\n");
244 }
245
246 // This is an attempt at reproducing an issue with the utf8 fuzzer
puzzler()247 void puzzler() {
248 std::cout << "running puzzler... " << std::endl;
249 const char* bad64 = "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x1c\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00";
250 size_t length = 64;
251 std::cout << "Input: \"";
252 for(size_t j = 0; j < length; j++) {
253 std::cout << "\\x" << std::hex << std::setw(2) << std::setfill('0') << uint32_t(bad64[j]);
254 }
255 std::cout << "\"" << std::endl;
256 bool is_ok{true};
257 for(const auto& e: simdjson::available_implementations) {
258 if(!e->supported_by_runtime_system()) { continue; }
259 const bool current = e->validate_utf8(bad64, length);
260 std::cout << e->name() << " returns " << current << std::endl;
261 if(current) { is_ok = false; }
262 }
263 if(!is_ok) { abort(); }
264 std::cout << "Ok!" << std::endl;
265 }
266
main()267 int main() {
268 puzzler();
269 brute_force_tests();
270 test();
271 return EXIT_SUCCESS;
272 }
273