1 /* 2 * Copyright (C) 2005 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #define LOG_TAG "unicode" 18 19 #include <utils/Unicode.h> 20 #include <limits.h> 21 22 #include <log/log.h> 23 24 #if defined(_WIN32) 25 # undef nhtol 26 # undef htonl 27 # undef nhtos 28 # undef htons 29 30 # define ntohl(x) ( ((x) << 24) | (((x) >> 24) & 255) | (((x) << 8) & 0xff0000) | (((x) >> 8) & 0xff00) ) 31 # define htonl(x) ntohl(x) 32 # define ntohs(x) ( (((x) << 8) & 0xff00) | (((x) >> 8) & 255) ) 33 # define htons(x) ntohs(x) 34 #else 35 # include <netinet/in.h> 36 #endif 37 38 extern "C" { 39 40 static const char32_t kByteMask = 0x000000BF; 41 static const char32_t kByteMark = 0x00000080; 42 43 // Surrogates aren't valid for UTF-32 characters, so define some 44 // constants that will let us screen them out. 45 static const char32_t kUnicodeSurrogateHighStart = 0x0000D800; 46 // Unused, here for completeness: 47 // static const char32_t kUnicodeSurrogateHighEnd = 0x0000DBFF; 48 // static const char32_t kUnicodeSurrogateLowStart = 0x0000DC00; 49 static const char32_t kUnicodeSurrogateLowEnd = 0x0000DFFF; 50 static const char32_t kUnicodeSurrogateStart = kUnicodeSurrogateHighStart; 51 static const char32_t kUnicodeSurrogateEnd = kUnicodeSurrogateLowEnd; 52 static const char32_t kUnicodeMaxCodepoint = 0x0010FFFF; 53 54 // Mask used to set appropriate bits in first byte of UTF-8 sequence, 55 // indexed by number of bytes in the sequence. 56 // 0xxxxxxx 57 // -> (00-7f) 7bit. Bit mask for the first byte is 0x00000000 58 // 110yyyyx 10xxxxxx 59 // -> (c0-df)(80-bf) 11bit. Bit mask is 0x000000C0 60 // 1110yyyy 10yxxxxx 10xxxxxx 61 // -> (e0-ef)(80-bf)(80-bf) 16bit. Bit mask is 0x000000E0 62 // 11110yyy 10yyxxxx 10xxxxxx 10xxxxxx 63 // -> (f0-f7)(80-bf)(80-bf)(80-bf) 21bit. Bit mask is 0x000000F0 64 static const char32_t kFirstByteMark[] = { 65 0x00000000, 0x00000000, 0x000000C0, 0x000000E0, 0x000000F0 66 }; 67 68 // -------------------------------------------------------------------------- 69 // UTF-32 70 // -------------------------------------------------------------------------- 71 72 /** 73 * Return number of UTF-8 bytes required for the character. If the character 74 * is invalid, return size of 0. 75 */ 76 static inline size_t utf32_codepoint_utf8_length(char32_t srcChar) 77 { 78 // Figure out how many bytes the result will require. 79 if (srcChar < 0x00000080) { 80 return 1; 81 } else if (srcChar < 0x00000800) { 82 return 2; 83 } else if (srcChar < 0x00010000) { 84 if ((srcChar < kUnicodeSurrogateStart) || (srcChar > kUnicodeSurrogateEnd)) { 85 return 3; 86 } else { 87 // Surrogates are invalid UTF-32 characters. 88 return 0; 89 } 90 } 91 // Max code point for Unicode is 0x0010FFFF. 92 else if (srcChar <= kUnicodeMaxCodepoint) { 93 return 4; 94 } else { 95 // Invalid UTF-32 character. 96 return 0; 97 } 98 } 99 100 // Write out the source character to <dstP>. 101 102 static inline void utf32_codepoint_to_utf8(uint8_t* dstP, char32_t srcChar, size_t bytes) 103 { 104 dstP += bytes; 105 switch (bytes) 106 { /* note: everything falls through. */ 107 case 4: *--dstP = (uint8_t)((srcChar | kByteMark) & kByteMask); srcChar >>= 6; 108 case 3: *--dstP = (uint8_t)((srcChar | kByteMark) & kByteMask); srcChar >>= 6; 109 case 2: *--dstP = (uint8_t)((srcChar | kByteMark) & kByteMask); srcChar >>= 6; 110 case 1: *--dstP = (uint8_t)(srcChar | kFirstByteMark[bytes]); 111 } 112 } 113 114 size_t strlen32(const char32_t *s) 115 { 116 const char32_t *ss = s; 117 while ( *ss ) 118 ss++; 119 return ss-s; 120 } 121 122 size_t strnlen32(const char32_t *s, size_t maxlen) 123 { 124 const char32_t *ss = s; 125 while ((maxlen > 0) && *ss) { 126 ss++; 127 maxlen--; 128 } 129 return ss-s; 130 } 131 132 static inline int32_t utf32_at_internal(const char* cur, size_t *num_read) 133 { 134 const char first_char = *cur; 135 if ((first_char & 0x80) == 0) { // ASCII 136 *num_read = 1; 137 return *cur; 138 } 139 cur++; 140 char32_t mask, to_ignore_mask; 141 size_t num_to_read = 0; 142 char32_t utf32 = first_char; 143 for (num_to_read = 1, mask = 0x40, to_ignore_mask = 0xFFFFFF80; 144 (first_char & mask); 145 num_to_read++, to_ignore_mask |= mask, mask >>= 1) { 146 // 0x3F == 00111111 147 utf32 = (utf32 << 6) + (*cur++ & 0x3F); 148 } 149 to_ignore_mask |= mask; 150 utf32 &= ~(to_ignore_mask << (6 * (num_to_read - 1))); 151 152 *num_read = num_to_read; 153 return static_cast<int32_t>(utf32); 154 } 155 156 int32_t utf32_from_utf8_at(const char *src, size_t src_len, size_t index, size_t *next_index) 157 { 158 if (index >= src_len) { 159 return -1; 160 } 161 size_t dummy_index; 162 if (next_index == NULL) { 163 next_index = &dummy_index; 164 } 165 size_t num_read; 166 int32_t ret = utf32_at_internal(src + index, &num_read); 167 if (ret >= 0) { 168 *next_index = index + num_read; 169 } 170 171 return ret; 172 } 173 174 ssize_t utf32_to_utf8_length(const char32_t *src, size_t src_len) 175 { 176 if (src == NULL || src_len == 0) { 177 return -1; 178 } 179 180 size_t ret = 0; 181 const char32_t *end = src + src_len; 182 while (src < end) { 183 ret += utf32_codepoint_utf8_length(*src++); 184 } 185 return ret; 186 } 187 188 void utf32_to_utf8(const char32_t* src, size_t src_len, char* dst, size_t dst_len) 189 { 190 if (src == NULL || src_len == 0 || dst == NULL) { 191 return; 192 } 193 194 const char32_t *cur_utf32 = src; 195 const char32_t *end_utf32 = src + src_len; 196 char *cur = dst; 197 while (cur_utf32 < end_utf32) { 198 size_t len = utf32_codepoint_utf8_length(*cur_utf32); 199 LOG_ALWAYS_FATAL_IF(dst_len < len, "%zu < %zu", dst_len, len); 200 utf32_codepoint_to_utf8((uint8_t *)cur, *cur_utf32++, len); 201 cur += len; 202 dst_len -= len; 203 } 204 LOG_ALWAYS_FATAL_IF(dst_len < 1, "dst_len < 1: %zu < 1", dst_len); 205 *cur = '\0'; 206 } 207 208 // -------------------------------------------------------------------------- 209 // UTF-16 210 // -------------------------------------------------------------------------- 211 212 int strcmp16(const char16_t *s1, const char16_t *s2) 213 { 214 char16_t ch; 215 int d = 0; 216 217 while ( 1 ) { 218 d = (int)(ch = *s1++) - (int)*s2++; 219 if ( d || !ch ) 220 break; 221 } 222 223 return d; 224 } 225 226 int strncmp16(const char16_t *s1, const char16_t *s2, size_t n) 227 { 228 char16_t ch; 229 int d = 0; 230 231 if (n == 0) { 232 return 0; 233 } 234 235 do { 236 d = (int)(ch = *s1++) - (int)*s2++; 237 if ( d || !ch ) { 238 break; 239 } 240 } while (--n); 241 242 return d; 243 } 244 245 char16_t *strcpy16(char16_t *dst, const char16_t *src) 246 { 247 char16_t *q = dst; 248 const char16_t *p = src; 249 char16_t ch; 250 251 do { 252 *q++ = ch = *p++; 253 } while ( ch ); 254 255 return dst; 256 } 257 258 size_t strlen16(const char16_t *s) 259 { 260 const char16_t *ss = s; 261 while ( *ss ) 262 ss++; 263 return ss-s; 264 } 265 266 267 char16_t *strncpy16(char16_t *dst, const char16_t *src, size_t n) 268 { 269 char16_t *q = dst; 270 const char16_t *p = src; 271 char ch; 272 273 while (n) { 274 n--; 275 *q++ = ch = *p++; 276 if ( !ch ) 277 break; 278 } 279 280 *q = 0; 281 282 return dst; 283 } 284 285 size_t strnlen16(const char16_t *s, size_t maxlen) 286 { 287 const char16_t *ss = s; 288 289 /* Important: the maxlen test must precede the reference through ss; 290 since the byte beyond the maximum may segfault */ 291 while ((maxlen > 0) && *ss) { 292 ss++; 293 maxlen--; 294 } 295 return ss-s; 296 } 297 298 char16_t* strstr16(const char16_t* src, const char16_t* target) 299 { 300 const char16_t needle = *target++; 301 const size_t target_len = strlen16(target); 302 if (needle != '\0') { 303 do { 304 do { 305 if (*src == '\0') { 306 return nullptr; 307 } 308 } while (*src++ != needle); 309 } while (strncmp16(src, target, target_len) != 0); 310 src--; 311 } 312 313 return (char16_t*)src; 314 } 315 316 317 int strzcmp16(const char16_t *s1, size_t n1, const char16_t *s2, size_t n2) 318 { 319 const char16_t* e1 = s1+n1; 320 const char16_t* e2 = s2+n2; 321 322 while (s1 < e1 && s2 < e2) { 323 const int d = (int)*s1++ - (int)*s2++; 324 if (d) { 325 return d; 326 } 327 } 328 329 return n1 < n2 330 ? (0 - (int)*s2) 331 : (n1 > n2 332 ? ((int)*s1 - 0) 333 : 0); 334 } 335 336 int strzcmp16_h_n(const char16_t *s1H, size_t n1, const char16_t *s2N, size_t n2) 337 { 338 const char16_t* e1 = s1H+n1; 339 const char16_t* e2 = s2N+n2; 340 341 while (s1H < e1 && s2N < e2) { 342 const char16_t c2 = ntohs(*s2N); 343 const int d = (int)*s1H++ - (int)c2; 344 s2N++; 345 if (d) { 346 return d; 347 } 348 } 349 350 return n1 < n2 351 ? (0 - (int)ntohs(*s2N)) 352 : (n1 > n2 353 ? ((int)*s1H - 0) 354 : 0); 355 } 356 357 void utf16_to_utf8(const char16_t* src, size_t src_len, char* dst, size_t dst_len) 358 { 359 if (src == NULL || src_len == 0 || dst == NULL) { 360 return; 361 } 362 363 const char16_t* cur_utf16 = src; 364 const char16_t* const end_utf16 = src + src_len; 365 char *cur = dst; 366 while (cur_utf16 < end_utf16) { 367 char32_t utf32; 368 // surrogate pairs 369 if((*cur_utf16 & 0xFC00) == 0xD800 && (cur_utf16 + 1) < end_utf16 370 && (*(cur_utf16 + 1) & 0xFC00) == 0xDC00) { 371 utf32 = (*cur_utf16++ - 0xD800) << 10; 372 utf32 |= *cur_utf16++ - 0xDC00; 373 utf32 += 0x10000; 374 } else { 375 utf32 = (char32_t) *cur_utf16++; 376 } 377 const size_t len = utf32_codepoint_utf8_length(utf32); 378 LOG_ALWAYS_FATAL_IF(dst_len < len, "%zu < %zu", dst_len, len); 379 utf32_codepoint_to_utf8((uint8_t*)cur, utf32, len); 380 cur += len; 381 dst_len -= len; 382 } 383 LOG_ALWAYS_FATAL_IF(dst_len < 1, "%zu < 1", dst_len); 384 *cur = '\0'; 385 } 386 387 // -------------------------------------------------------------------------- 388 // UTF-8 389 // -------------------------------------------------------------------------- 390 391 ssize_t utf8_length(const char *src) 392 { 393 const char *cur = src; 394 size_t ret = 0; 395 while (*cur != '\0') { 396 const char first_char = *cur++; 397 if ((first_char & 0x80) == 0) { // ASCII 398 ret += 1; 399 continue; 400 } 401 // (UTF-8's character must not be like 10xxxxxx, 402 // but 110xxxxx, 1110xxxx, ... or 1111110x) 403 if ((first_char & 0x40) == 0) { 404 return -1; 405 } 406 407 int32_t mask, to_ignore_mask; 408 size_t num_to_read = 0; 409 char32_t utf32 = 0; 410 for (num_to_read = 1, mask = 0x40, to_ignore_mask = 0x80; 411 num_to_read < 5 && (first_char & mask); 412 num_to_read++, to_ignore_mask |= mask, mask >>= 1) { 413 if ((*cur & 0xC0) != 0x80) { // must be 10xxxxxx 414 return -1; 415 } 416 // 0x3F == 00111111 417 utf32 = (utf32 << 6) + (*cur++ & 0x3F); 418 } 419 // "first_char" must be (110xxxxx - 11110xxx) 420 if (num_to_read == 5) { 421 return -1; 422 } 423 to_ignore_mask |= mask; 424 utf32 |= ((~to_ignore_mask) & first_char) << (6 * (num_to_read - 1)); 425 if (utf32 > kUnicodeMaxCodepoint) { 426 return -1; 427 } 428 429 ret += num_to_read; 430 } 431 return ret; 432 } 433 434 ssize_t utf16_to_utf8_length(const char16_t *src, size_t src_len) 435 { 436 if (src == NULL || src_len == 0) { 437 return -1; 438 } 439 440 size_t ret = 0; 441 const char16_t* const end = src + src_len; 442 while (src < end) { 443 if ((*src & 0xFC00) == 0xD800 && (src + 1) < end 444 && (*(src + 1) & 0xFC00) == 0xDC00) { 445 // surrogate pairs are always 4 bytes. 446 ret += 4; 447 src += 2; 448 } else { 449 ret += utf32_codepoint_utf8_length((char32_t) *src++); 450 } 451 } 452 return ret; 453 } 454 455 /** 456 * Returns 1-4 based on the number of leading bits. 457 * 458 * 1111 -> 4 459 * 1110 -> 3 460 * 110x -> 2 461 * 10xx -> 1 462 * 0xxx -> 1 463 */ 464 static inline size_t utf8_codepoint_len(uint8_t ch) 465 { 466 return ((0xe5000000 >> ((ch >> 3) & 0x1e)) & 3) + 1; 467 } 468 469 static inline void utf8_shift_and_mask(uint32_t* codePoint, const uint8_t byte) 470 { 471 *codePoint <<= 6; 472 *codePoint |= 0x3F & byte; 473 } 474 475 size_t utf8_to_utf32_length(const char *src, size_t src_len) 476 { 477 if (src == NULL || src_len == 0) { 478 return 0; 479 } 480 size_t ret = 0; 481 const char* cur; 482 const char* end; 483 size_t num_to_skip; 484 for (cur = src, end = src + src_len, num_to_skip = 1; 485 cur < end; 486 cur += num_to_skip, ret++) { 487 const char first_char = *cur; 488 num_to_skip = 1; 489 if ((first_char & 0x80) == 0) { // ASCII 490 continue; 491 } 492 int32_t mask; 493 494 for (mask = 0x40; (first_char & mask); num_to_skip++, mask >>= 1) { 495 } 496 } 497 return ret; 498 } 499 500 void utf8_to_utf32(const char* src, size_t src_len, char32_t* dst) 501 { 502 if (src == NULL || src_len == 0 || dst == NULL) { 503 return; 504 } 505 506 const char* cur = src; 507 const char* const end = src + src_len; 508 char32_t* cur_utf32 = dst; 509 while (cur < end) { 510 size_t num_read; 511 *cur_utf32++ = static_cast<char32_t>(utf32_at_internal(cur, &num_read)); 512 cur += num_read; 513 } 514 *cur_utf32 = 0; 515 } 516 517 static inline uint32_t utf8_to_utf32_codepoint(const uint8_t *src, size_t length) 518 { 519 uint32_t unicode; 520 521 switch (length) 522 { 523 case 1: 524 return src[0]; 525 case 2: 526 unicode = src[0] & 0x1f; 527 utf8_shift_and_mask(&unicode, src[1]); 528 return unicode; 529 case 3: 530 unicode = src[0] & 0x0f; 531 utf8_shift_and_mask(&unicode, src[1]); 532 utf8_shift_and_mask(&unicode, src[2]); 533 return unicode; 534 case 4: 535 unicode = src[0] & 0x07; 536 utf8_shift_and_mask(&unicode, src[1]); 537 utf8_shift_and_mask(&unicode, src[2]); 538 utf8_shift_and_mask(&unicode, src[3]); 539 return unicode; 540 default: 541 return 0xffff; 542 } 543 544 //printf("Char at %p: len=%d, utf-16=%p\n", src, length, (void*)result); 545 } 546 547 ssize_t utf8_to_utf16_length(const uint8_t* u8str, size_t u8len, bool overreadIsFatal) 548 { 549 const uint8_t* const u8end = u8str + u8len; 550 const uint8_t* u8cur = u8str; 551 552 /* Validate that the UTF-8 is the correct len */ 553 size_t u16measuredLen = 0; 554 while (u8cur < u8end) { 555 u16measuredLen++; 556 int u8charLen = utf8_codepoint_len(*u8cur); 557 // Malformed utf8, some characters are beyond the end. 558 // Cases: 559 // If u8charLen == 1, this becomes u8cur >= u8end, which cannot happen as u8cur < u8end, 560 // then this condition fail and we continue, as expected. 561 // If u8charLen == 2, this becomes u8cur + 1 >= u8end, which fails only if 562 // u8cur == u8end - 1, that is, there was only one remaining character to read but we need 563 // 2 of them. This condition holds and we return -1, as expected. 564 if (u8cur + u8charLen - 1 >= u8end) { 565 if (overreadIsFatal) { 566 LOG_ALWAYS_FATAL("Attempt to overread computing length of utf8 string"); 567 } else { 568 return -1; 569 } 570 } 571 uint32_t codepoint = utf8_to_utf32_codepoint(u8cur, u8charLen); 572 if (codepoint > 0xFFFF) u16measuredLen++; // this will be a surrogate pair in utf16 573 u8cur += u8charLen; 574 } 575 576 /** 577 * Make sure that we ended where we thought we would and the output UTF-16 578 * will be exactly how long we were told it would be. 579 */ 580 if (u8cur != u8end) { 581 return -1; 582 } 583 584 return u16measuredLen; 585 } 586 587 char16_t* utf8_to_utf16(const uint8_t* u8str, size_t u8len, char16_t* u16str, size_t u16len) { 588 // A value > SSIZE_MAX is probably a negative value returned as an error and casted. 589 LOG_ALWAYS_FATAL_IF(u16len == 0 || u16len > SSIZE_MAX, "u16len is %zu", u16len); 590 char16_t* end = utf8_to_utf16_no_null_terminator(u8str, u8len, u16str, u16len - 1); 591 *end = 0; 592 return end; 593 } 594 595 char16_t* utf8_to_utf16_no_null_terminator( 596 const uint8_t* src, size_t srcLen, char16_t* dst, size_t dstLen) { 597 if (dstLen == 0) { 598 return dst; 599 } 600 // A value > SSIZE_MAX is probably a negative value returned as an error and casted. 601 LOG_ALWAYS_FATAL_IF(dstLen > SSIZE_MAX, "dstLen is %zu", dstLen); 602 const uint8_t* const u8end = src + srcLen; 603 const uint8_t* u8cur = src; 604 const char16_t* const u16end = dst + dstLen; 605 char16_t* u16cur = dst; 606 607 while (u8cur < u8end && u16cur < u16end) { 608 size_t u8len = utf8_codepoint_len(*u8cur); 609 uint32_t codepoint = utf8_to_utf32_codepoint(u8cur, u8len); 610 611 // Convert the UTF32 codepoint to one or more UTF16 codepoints 612 if (codepoint <= 0xFFFF) { 613 // Single UTF16 character 614 *u16cur++ = (char16_t) codepoint; 615 } else { 616 // Multiple UTF16 characters with surrogates 617 codepoint = codepoint - 0x10000; 618 *u16cur++ = (char16_t) ((codepoint >> 10) + 0xD800); 619 if (u16cur >= u16end) { 620 // Ooops... not enough room for this surrogate pair. 621 return u16cur-1; 622 } 623 *u16cur++ = (char16_t) ((codepoint & 0x3FF) + 0xDC00); 624 } 625 626 u8cur += u8len; 627 } 628 return u16cur; 629 } 630 631 } 632