Debian Codegraph @

utf-8-validate/deps/is_utf8/tests/unit.cpp

raw
1 #include "is_utf8.h"
2 #include <cstdint>
3 #include <cstdio>
4 #include <cstdlib>
5 #include <cstring>
6 #include <iostream>
7 #include <random>
8 #include <vector>
9
10 bool hard_coded() {
11 std::cout << "hard coded tests." << std::endl;
12 // additional tests are from autobahn websocket testsuite
13 // https://github.com/crossbario/autobahn-testsuite/tree/master/autobahntestsuite/autobahntestsuite/case
14 const char *goodsequences[] = {"a", "abcde12345", "\x71", "\x75\x4c",
15 "\x7f\x4c\x23\x3c\x3a\x6f\x5d\x44\x13\x70"};
16 const char *badsequences[] = {
17 "\xc3\x28", // 0
18 "\xa0\xa1", // 1
19 "\xe2\x28\xa1", // 2
20 "\xe2\x82\x28", // 3
21 "\xf0\x28\x8c\xbc", // 4
22 "\xf0\x90\x28\xbc", // 5
23 "\xf0\x28\x8c\x28", // 6
24 "\xc0\x9f", // 7
25 "\xf5\xff\xff\xff", // 8
26 "\xed\xa0\x81", // 9
27 "\xf8\x90\x80\x80\x80", // 10
28 "123456789012345\xed",
29 "123456789012345\xf1",
30 "123456789012345\xc2",
31 "\xC2\x7F",
32 "\xce",
33 "\xce\xba\xe1",
34 "\xce\xba\xe1\xbd",
35 "\xce\xba\xe1\xbd\xb9\xcf",
36 "\xce\xba\xe1\xbd\xb9\xcf\x83\xce",
37 "\xce\xba\xe1\xbd\xb9\xcf\x83\xce\xbc\xce",
38 "\xdf",
39 "\xef\xbf",
40 "\x80",
41 "\x91\x85\x95\x9e",
42 "\x6c\x02\x8e\x18",
43 "\x25\x5b\x6e\x2c\x32\x2c\x5b\x5b\x33\x2c\x34\x2c\x05\x29\x2c\x33\x01\x01"
44 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
45 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
46 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
47 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b"
48 "\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5d\x2c\x35\x2e\x33\x2c\x39\x2e\x33"
49 "\x2c\x37\x2e\x33\x2c\x39\x2e\x34\x2c\x37\x2e\x33\x2c\x39\x2e\x33\x2c\x37"
50 "\x2e\x33\x2c\x39\x2e\x34\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d"
51 "\x5d\x5d\x5d\x5d\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
52 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x20\x01\x01"
53 "\x01\x01\x01\x02\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
54 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
55 "\x01\x23\x0a\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
56 "\x01\x01\x01\x01\x01\x01\x01\x01\x7e\x7e\x0a\x0a\x01\x01\x01\x01\x01\x01"
57 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x5b\x5b"
58 "\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5d\x2c\x37"
59 "\x2e\x33\x2c\x39\x2e\x33\x2c\x37\x2e\x33\x2c\x39\x2e\x34\x2c\x37\x2e\x33"
60 "\x2c\x39\x2e\x33\x2c\x37\x2e\x33\x2c\x39\x2e\x34\x5d\x5d\x5d\x5d\x5d\x5d"
61 "\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x5d\x01\x01\x80\x01\x01\x01\x79\x01\x01"
62 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
63 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
64 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
65 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
66 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
67 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
68 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
69 "\x01\x01\x01\x01\x01\x01\x01\x01\x01",
70 "[[[[[[[[[[[[[[["
71 "\x80\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
72 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
73 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
74 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
75 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
76 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x010\x01\x01\x01\x01\x01\x01"
77 "\x01\x01\x01\x01\x01",
78 "\x20\x0b\x01\x01\x01\x64\x3a\x64\x3a\x64\x3a\x5b\x5b\x5b\x5b\x5b\x5b\x5b"
79 "\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b"
80 "\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x5b\x30\x01"
81 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
82 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
83 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
84 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
85 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
86 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
87 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x80\x01\x01\x01\x01\x01\x01\x01"
88 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
89 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
90 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
91 "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
92 "\x01\x01\x01\x01\x01",
93 "\x80",
94 "\x90",
95 "\xa1",
96 "\xb2",
97 "\xc3",
98 "\xd4",
99 "\xe5",
100 "\xf6"
101 "\xc3\xb1"};
102 size_t number_good = sizeof(goodsequences) / sizeof(goodsequences[0]);
103 printf("Testing %zu good sequences.\n", number_good);
104 for (size_t i = 0; i < number_good; i++) {
105 size_t len = std::strlen(goodsequences[i]);
106 if (!is_utf8(goodsequences[i], len)) {
107 printf("bug goodsequences[%zu]\n", i);
108 return false;
109 }
110 }
111 size_t number_bad = sizeof(badsequences) / sizeof(badsequences[0]);
112 printf("Testing %zu bad sequences.\n", number_bad);
113 for (size_t i = 0; i < number_bad; i++) {
114 size_t len = std::strlen(badsequences[i]);
115 if (is_utf8(badsequences[i], len)) {
116 printf("bug badsequences[%zu]\n", i);
117 return false;
118 }
119 }
120 printf("Success.\n");
121 return true;
122 }
123
124 class random_utf8 final {
125 public:
126 random_utf8(uint32_t seed, int prob_1byte, int prob_2bytes, int prob_3bytes,
127 int prob_4bytes);
128
129 std::vector<uint8_t> generate(size_t output_bytes);
130 // include the number of code points
131 std::pair<std::vector<uint8_t>, size_t> generate_counted(size_t output_bytes);
132 std::vector<uint8_t> generate(size_t output_bytes, long seed);
133
134 private:
135 uint32_t generate();
136
137 std::mt19937 gen;
138 std::discrete_distribution<> bytes_count;
139 std::uniform_int_distribution<int> val_7bit{0x00, 0x7f}; // 0b0xxxxxxx
140 std::uniform_int_distribution<int> val_6bit{0x00, 0x3f}; // 0b10xxxxxx
141 std::uniform_int_distribution<int> val_5bit{0x00, 0x1f}; // 0b110xxxxx
142 std::uniform_int_distribution<int> val_4bit{0x00, 0x0f}; // 0b1110xxxx
143 std::uniform_int_distribution<int> val_3bit{0x00, 0x07}; // 0b11110xxx
144 };
145
146 random_utf8::random_utf8(uint32_t seed, int prob_1byte, int prob_2bytes,
147 int prob_3bytes, int prob_4bytes)
148 : gen(seed), bytes_count({double(prob_1byte), double(prob_2bytes),
149 double(prob_3bytes), double(prob_4bytes)}) {}
150
151 std::pair<std::vector<uint8_t>, size_t>
152 random_utf8::generate_counted(size_t output_bytes) {
153 std::vector<uint8_t> result;
154 result.reserve(output_bytes);
155 uint8_t candidate, head;
156 size_t count{0};
157 while (result.size() < output_bytes) {
158 count++;
159 switch (bytes_count(gen)) {
160 case 0: // 1 byte
161 candidate = uint8_t(val_7bit(gen));
162 while (candidate == 0) { // though strictly speaking, a stream of nulls is
163 // UTF8, it tends to break some code
164 candidate = uint8_t(val_7bit(gen));
165 }
166 result.push_back(candidate);
167 break;
168 case 1: // 2 bytes
169 candidate = 0xc0 | uint8_t(val_5bit(gen));
170 while (candidate < 0xC2) {
171 candidate = 0xc0 | uint8_t(val_5bit(gen));
172 }
173 result.push_back(candidate);
174 result.push_back(0x80 | uint8_t(val_6bit(gen)));
175 break;
176 case 2: // 3 bytes
177 head = 0xe0 | uint8_t(val_4bit(gen));
178 result.push_back(head);
179 candidate = 0x80 | uint8_t(val_6bit(gen));
180 if (head == 0xE0) {
181 while (candidate < 0xA0) {
182 candidate = 0x80 | uint8_t(val_6bit(gen));
183 }
184 } else if (head == 0xED) {
185 while (candidate > 0x9F) {
186 candidate = 0x80 | uint8_t(val_6bit(gen));
187 }
188 }
189 result.push_back(candidate);
190 result.push_back(0x80 | uint8_t(val_6bit(gen)));
191 break;
192 case 3: // 4 bytes
193 head = 0xf0 | uint8_t(val_3bit(gen));
194 while (head > 0xF4) {
195 head = 0xf0 | uint8_t(val_3bit(gen));
196 }
197 result.push_back(head);
198 candidate = 0x80 | uint8_t(val_6bit(gen));
199 if (head == 0xF0) {
200 while (candidate < 0x90) {
201 candidate = 0x80 | uint8_t(val_6bit(gen));
202 }
203 } else if (head == 0xF4) {
204 while (candidate > 0x8F) {
205 candidate = 0x80 | uint8_t(val_6bit(gen));
206 }
207 }
208 result.push_back(candidate);
209 result.push_back(0x80 | uint8_t(val_6bit(gen)));
210 result.push_back(0x80 | uint8_t(val_6bit(gen)));
211 break;
212 }
213 }
214 result.push_back(0); // EOS for scalar code
215
216 return make_pair(result, count);
217 }
218
219 std::vector<uint8_t> random_utf8::generate(size_t output_bytes) {
220 return generate_counted(output_bytes).first;
221 }
222
223 std::vector<uint8_t> random_utf8::generate(size_t output_bytes, long seed) {
224 gen.seed(uint32_t(seed));
225 return generate(output_bytes);
226 }
227
228 // credit: based on code from Google Fuchsia (Apache Licensed)
229 bool reference_validate_utf8(const char *buf, size_t len) noexcept {
230 const uint8_t *data = (const uint8_t *)buf;
231 uint64_t pos = 0;
232 uint64_t next_pos = 0;
233 uint32_t code_point = 0;
234 while (pos < len) {
235 unsigned char byte = data[pos];
236 if (byte < 0b10000000) {
237 pos++;
238 continue;
239 } else if ((byte & 0b11100000) == 0b11000000) {
240 next_pos = pos + 2;
241 if (next_pos > len) {
242 return false;
243 }
244 if ((data[pos + 1] & 0b11000000) != 0b10000000) {
245 return false;
246 }
247 // range check
248 code_point = (byte & 0b00011111) << 6 | (data[pos + 1] & 0b00111111);
249 if (code_point < 0x80 || 0x7ff < code_point) {
250 return false;
251 }
252 } else if ((byte & 0b11110000) == 0b11100000) {
253 next_pos = pos + 3;
254 if (next_pos > len) {
255 return false;
256 }
257 if ((data[pos + 1] & 0b11000000) != 0b10000000) {
258 return false;
259 }
260 if ((data[pos + 2] & 0b11000000) != 0b10000000) {
261 return false;
262 }
263 // range check
264 code_point = (byte & 0b00001111) << 12 |
265 (data[pos + 1] & 0b00111111) << 6 |
266 (data[pos + 2] & 0b00111111);
267 if (code_point < 0x800 || 0xffff < code_point ||
268 (0xd7ff < code_point && code_point < 0xe000)) {
269 return false;
270 }
271 } else if ((byte & 0b11111000) == 0b11110000) { // 0b11110000
272 next_pos = pos + 4;
273 if (next_pos > len) {
274 return false;
275 }
276 if ((data[pos + 1] & 0b11000000) != 0b10000000) {
277 return false;
278 }
279 if ((data[pos + 2] & 0b11000000) != 0b10000000) {
280 return false;
281 }
282 if ((data[pos + 3] & 0b11000000) != 0b10000000) {
283 return false;
284 }
285 // range check
286 code_point =
287 (byte & 0b00000111) << 18 | (data[pos + 1] & 0b00111111) << 12 |
288 (data[pos + 2] & 0b00111111) << 6 | (data[pos + 3] & 0b00111111);
289 if (code_point < 0xffff || 0x10ffff < code_point) {
290 return false;
291 }
292 } else {
293 // we may have a continuation
294 return false;
295 }
296 pos = next_pos;
297 }
298 return true;
299 }
300 bool brute_force() {
301
302 std::cout << "brute force tests." << std::endl;
303 uint32_t seed{1234};
304 random_utf8 gen_1_2_3_4(seed, 1, 1, 1, 1);
305 size_t total = 10000;
306 for (size_t i = 0; i < total; i++) {
307 if ((i % 1000) == 0) {
308 printf(".");
309 fflush(NULL);
310 }
311
312 auto UTF8 = gen_1_2_3_4.generate(rand() % 1024);
313 if (!is_utf8((const char *)UTF8.data(), UTF8.size())) {
314 std::cerr << "bug" << std::endl;
315 return false;
316 }
317 for (size_t flip = 0; flip < 1000; ++flip) {
318 // we are going to hack the string as long as it is UTF-8
319 const int bitflip{1 << (rand() % 8)};
320 UTF8[rand() % UTF8.size()] = uint8_t(bitflip); // we flip exactly one bit
321 bool is_ok = is_utf8((const char *)UTF8.data(), UTF8.size());
322 bool is_ok_basic =
323 reference_validate_utf8((const char *)UTF8.data(), UTF8.size());
324 if (is_ok != is_ok_basic) {
325 std::cerr << "bug" << std::endl;
326 return false;
327 }
328 }
329 }
330 printf("\n");
331 printf("Success.\n");
332 return true;
333 }
334
335 int main() {
336 bool results = hard_coded() & brute_force();
337 return results ? EXIT_SUCCESS : EXIT_FAILURE;
338 }