| 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 |
} |