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 38extern "C" { 39 40static const char32_t kByteMask = 0x000000BF; 41static 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. 45static const char32_t kUnicodeSurrogateHighStart = 0x0000D800; 46// Unused, here for completeness: 47// static const char32_t kUnicodeSurrogateHighEnd = 0x0000DBFF; 48// static const char32_t kUnicodeSurrogateLowStart = 0x0000DC00; 49static const char32_t kUnicodeSurrogateLowEnd = 0x0000DFFF; 50static const char32_t kUnicodeSurrogateStart = kUnicodeSurrogateHighStart; 51static const char32_t kUnicodeSurrogateEnd = kUnicodeSurrogateLowEnd; 52static 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 64static 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 */ 76static 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 102static 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 114size_t strlen32(const char32_t *s) 115{ 116 const char32_t *ss = s; 117 while ( *ss ) 118 ss++; 119 return ss-s; 120} 121 122size_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 132static 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 156int32_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 174ssize_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 size_t char_len = utf32_codepoint_utf8_length(*src++); 184 if (SSIZE_MAX - char_len < ret) { 185 // If this happens, we would overflow the ssize_t type when 186 // returning from this function, so we cannot express how 187 // long this string is in an ssize_t. 188 android_errorWriteLog(0x534e4554, "37723026"); 189 return -1; 190 } 191 ret += char_len; 192 } 193 return ret; 194} 195 196void utf32_to_utf8(const char32_t* src, size_t src_len, char* dst, size_t dst_len) 197{ 198 if (src == NULL || src_len == 0 || dst == NULL) { 199 return; 200 } 201 202 const char32_t *cur_utf32 = src; 203 const char32_t *end_utf32 = src + src_len; 204 char *cur = dst; 205 while (cur_utf32 < end_utf32) { 206 size_t len = utf32_codepoint_utf8_length(*cur_utf32); 207 LOG_ALWAYS_FATAL_IF(dst_len < len, "%zu < %zu", dst_len, len); 208 utf32_codepoint_to_utf8((uint8_t *)cur, *cur_utf32++, len); 209 cur += len; 210 dst_len -= len; 211 } 212 LOG_ALWAYS_FATAL_IF(dst_len < 1, "dst_len < 1: %zu < 1", dst_len); 213 *cur = '\0'; 214} 215 216// -------------------------------------------------------------------------- 217// UTF-16 218// -------------------------------------------------------------------------- 219 220int strcmp16(const char16_t *s1, const char16_t *s2) 221{ 222 char16_t ch; 223 int d = 0; 224 225 while ( 1 ) { 226 d = (int)(ch = *s1++) - (int)*s2++; 227 if ( d || !ch ) 228 break; 229 } 230 231 return d; 232} 233 234int strncmp16(const char16_t *s1, const char16_t *s2, size_t n) 235{ 236 char16_t ch; 237 int d = 0; 238 239 if (n == 0) { 240 return 0; 241 } 242 243 do { 244 d = (int)(ch = *s1++) - (int)*s2++; 245 if ( d || !ch ) { 246 break; 247 } 248 } while (--n); 249 250 return d; 251} 252 253char16_t *strcpy16(char16_t *dst, const char16_t *src) 254{ 255 char16_t *q = dst; 256 const char16_t *p = src; 257 char16_t ch; 258 259 do { 260 *q++ = ch = *p++; 261 } while ( ch ); 262 263 return dst; 264} 265 266size_t strlen16(const char16_t *s) 267{ 268 const char16_t *ss = s; 269 while ( *ss ) 270 ss++; 271 return ss-s; 272} 273 274 275char16_t *strncpy16(char16_t *dst, const char16_t *src, size_t n) 276{ 277 char16_t *q = dst; 278 const char16_t *p = src; 279 char ch; 280 281 while (n) { 282 n--; 283 *q++ = ch = *p++; 284 if ( !ch ) 285 break; 286 } 287 288 *q = 0; 289 290 return dst; 291} 292 293size_t strnlen16(const char16_t *s, size_t maxlen) 294{ 295 const char16_t *ss = s; 296 297 /* Important: the maxlen test must precede the reference through ss; 298 since the byte beyond the maximum may segfault */ 299 while ((maxlen > 0) && *ss) { 300 ss++; 301 maxlen--; 302 } 303 return ss-s; 304} 305 306char16_t* strstr16(const char16_t* src, const char16_t* target) 307{ 308 const char16_t needle = *target++; 309 const size_t target_len = strlen16(target); 310 if (needle != '\0') { 311 do { 312 do { 313 if (*src == '\0') { 314 return nullptr; 315 } 316 } while (*src++ != needle); 317 } while (strncmp16(src, target, target_len) != 0); 318 src--; 319 } 320 321 return (char16_t*)src; 322} 323 324 325int strzcmp16(const char16_t *s1, size_t n1, const char16_t *s2, size_t n2) 326{ 327 const char16_t* e1 = s1+n1; 328 const char16_t* e2 = s2+n2; 329 330 while (s1 < e1 && s2 < e2) { 331 const int d = (int)*s1++ - (int)*s2++; 332 if (d) { 333 return d; 334 } 335 } 336 337 return n1 < n2 338 ? (0 - (int)*s2) 339 : (n1 > n2 340 ? ((int)*s1 - 0) 341 : 0); 342} 343 344int strzcmp16_h_n(const char16_t *s1H, size_t n1, const char16_t *s2N, size_t n2) 345{ 346 const char16_t* e1 = s1H+n1; 347 const char16_t* e2 = s2N+n2; 348 349 while (s1H < e1 && s2N < e2) { 350 const char16_t c2 = ntohs(*s2N); 351 const int d = (int)*s1H++ - (int)c2; 352 s2N++; 353 if (d) { 354 return d; 355 } 356 } 357 358 return n1 < n2 359 ? (0 - (int)ntohs(*s2N)) 360 : (n1 > n2 361 ? ((int)*s1H - 0) 362 : 0); 363} 364 365void utf16_to_utf8(const char16_t* src, size_t src_len, char* dst, size_t dst_len) 366{ 367 if (src == NULL || src_len == 0 || dst == NULL) { 368 return; 369 } 370 371 const char16_t* cur_utf16 = src; 372 const char16_t* const end_utf16 = src + src_len; 373 char *cur = dst; 374 while (cur_utf16 < end_utf16) { 375 char32_t utf32; 376 // surrogate pairs 377 if((*cur_utf16 & 0xFC00) == 0xD800 && (cur_utf16 + 1) < end_utf16 378 && (*(cur_utf16 + 1) & 0xFC00) == 0xDC00) { 379 utf32 = (*cur_utf16++ - 0xD800) << 10; 380 utf32 |= *cur_utf16++ - 0xDC00; 381 utf32 += 0x10000; 382 } else { 383 utf32 = (char32_t) *cur_utf16++; 384 } 385 const size_t len = utf32_codepoint_utf8_length(utf32); 386 LOG_ALWAYS_FATAL_IF(dst_len < len, "%zu < %zu", dst_len, len); 387 utf32_codepoint_to_utf8((uint8_t*)cur, utf32, len); 388 cur += len; 389 dst_len -= len; 390 } 391 LOG_ALWAYS_FATAL_IF(dst_len < 1, "%zu < 1", dst_len); 392 *cur = '\0'; 393} 394 395// -------------------------------------------------------------------------- 396// UTF-8 397// -------------------------------------------------------------------------- 398 399ssize_t utf8_length(const char *src) 400{ 401 const char *cur = src; 402 size_t ret = 0; 403 while (*cur != '\0') { 404 const char first_char = *cur++; 405 if ((first_char & 0x80) == 0) { // ASCII 406 ret += 1; 407 continue; 408 } 409 // (UTF-8's character must not be like 10xxxxxx, 410 // but 110xxxxx, 1110xxxx, ... or 1111110x) 411 if ((first_char & 0x40) == 0) { 412 return -1; 413 } 414 415 int32_t mask, to_ignore_mask; 416 size_t num_to_read = 0; 417 char32_t utf32 = 0; 418 for (num_to_read = 1, mask = 0x40, to_ignore_mask = 0x80; 419 num_to_read < 5 && (first_char & mask); 420 num_to_read++, to_ignore_mask |= mask, mask >>= 1) { 421 if ((*cur & 0xC0) != 0x80) { // must be 10xxxxxx 422 return -1; 423 } 424 // 0x3F == 00111111 425 utf32 = (utf32 << 6) + (*cur++ & 0x3F); 426 } 427 // "first_char" must be (110xxxxx - 11110xxx) 428 if (num_to_read == 5) { 429 return -1; 430 } 431 to_ignore_mask |= mask; 432 utf32 |= ((~to_ignore_mask) & first_char) << (6 * (num_to_read - 1)); 433 if (utf32 > kUnicodeMaxCodepoint) { 434 return -1; 435 } 436 437 ret += num_to_read; 438 } 439 return ret; 440} 441 442ssize_t utf16_to_utf8_length(const char16_t *src, size_t src_len) 443{ 444 if (src == NULL || src_len == 0) { 445 return -1; 446 } 447 448 size_t ret = 0; 449 const char16_t* const end = src + src_len; 450 while (src < end) { 451 size_t char_len; 452 if ((*src & 0xFC00) == 0xD800 && (src + 1) < end 453 && (*(src + 1) & 0xFC00) == 0xDC00) { 454 // surrogate pairs are always 4 bytes. 455 char_len = 4; 456 src += 2; 457 } else { 458 char_len = utf32_codepoint_utf8_length((char32_t)*src++); 459 } 460 if (SSIZE_MAX - char_len < ret) { 461 // If this happens, we would overflow the ssize_t type when 462 // returning from this function, so we cannot express how 463 // long this string is in an ssize_t. 464 android_errorWriteLog(0x534e4554, "37723026"); 465 return -1; 466 } 467 ret += char_len; 468 } 469 return ret; 470} 471 472/** 473 * Returns 1-4 based on the number of leading bits. 474 * 475 * 1111 -> 4 476 * 1110 -> 3 477 * 110x -> 2 478 * 10xx -> 1 479 * 0xxx -> 1 480 */ 481static inline size_t utf8_codepoint_len(uint8_t ch) 482{ 483 return ((0xe5000000 >> ((ch >> 3) & 0x1e)) & 3) + 1; 484} 485 486static inline void utf8_shift_and_mask(uint32_t* codePoint, const uint8_t byte) 487{ 488 *codePoint <<= 6; 489 *codePoint |= 0x3F & byte; 490} 491 492size_t utf8_to_utf32_length(const char *src, size_t src_len) 493{ 494 if (src == NULL || src_len == 0) { 495 return 0; 496 } 497 size_t ret = 0; 498 const char* cur; 499 const char* end; 500 size_t num_to_skip; 501 for (cur = src, end = src + src_len, num_to_skip = 1; 502 cur < end; 503 cur += num_to_skip, ret++) { 504 const char first_char = *cur; 505 num_to_skip = 1; 506 if ((first_char & 0x80) == 0) { // ASCII 507 continue; 508 } 509 int32_t mask; 510 511 for (mask = 0x40; (first_char & mask); num_to_skip++, mask >>= 1) { 512 } 513 } 514 return ret; 515} 516 517void utf8_to_utf32(const char* src, size_t src_len, char32_t* dst) 518{ 519 if (src == NULL || src_len == 0 || dst == NULL) { 520 return; 521 } 522 523 const char* cur = src; 524 const char* const end = src + src_len; 525 char32_t* cur_utf32 = dst; 526 while (cur < end) { 527 size_t num_read; 528 *cur_utf32++ = static_cast<char32_t>(utf32_at_internal(cur, &num_read)); 529 cur += num_read; 530 } 531 *cur_utf32 = 0; 532} 533 534static inline uint32_t utf8_to_utf32_codepoint(const uint8_t *src, size_t length) 535{ 536 uint32_t unicode; 537 538 switch (length) 539 { 540 case 1: 541 return src[0]; 542 case 2: 543 unicode = src[0] & 0x1f; 544 utf8_shift_and_mask(&unicode, src[1]); 545 return unicode; 546 case 3: 547 unicode = src[0] & 0x0f; 548 utf8_shift_and_mask(&unicode, src[1]); 549 utf8_shift_and_mask(&unicode, src[2]); 550 return unicode; 551 case 4: 552 unicode = src[0] & 0x07; 553 utf8_shift_and_mask(&unicode, src[1]); 554 utf8_shift_and_mask(&unicode, src[2]); 555 utf8_shift_and_mask(&unicode, src[3]); 556 return unicode; 557 default: 558 return 0xffff; 559 } 560 561 //printf("Char at %p: len=%d, utf-16=%p\n", src, length, (void*)result); 562} 563 564ssize_t utf8_to_utf16_length(const uint8_t* u8str, size_t u8len, bool overreadIsFatal) 565{ 566 const uint8_t* const u8end = u8str + u8len; 567 const uint8_t* u8cur = u8str; 568 569 /* Validate that the UTF-8 is the correct len */ 570 size_t u16measuredLen = 0; 571 while (u8cur < u8end) { 572 u16measuredLen++; 573 int u8charLen = utf8_codepoint_len(*u8cur); 574 // Malformed utf8, some characters are beyond the end. 575 // Cases: 576 // If u8charLen == 1, this becomes u8cur >= u8end, which cannot happen as u8cur < u8end, 577 // then this condition fail and we continue, as expected. 578 // If u8charLen == 2, this becomes u8cur + 1 >= u8end, which fails only if 579 // u8cur == u8end - 1, that is, there was only one remaining character to read but we need 580 // 2 of them. This condition holds and we return -1, as expected. 581 if (u8cur + u8charLen - 1 >= u8end) { 582 if (overreadIsFatal) { 583 LOG_ALWAYS_FATAL("Attempt to overread computing length of utf8 string"); 584 } else { 585 return -1; 586 } 587 } 588 uint32_t codepoint = utf8_to_utf32_codepoint(u8cur, u8charLen); 589 if (codepoint > 0xFFFF) u16measuredLen++; // this will be a surrogate pair in utf16 590 u8cur += u8charLen; 591 } 592 593 /** 594 * Make sure that we ended where we thought we would and the output UTF-16 595 * will be exactly how long we were told it would be. 596 */ 597 if (u8cur != u8end) { 598 return -1; 599 } 600 601 return u16measuredLen; 602} 603 604char16_t* utf8_to_utf16(const uint8_t* u8str, size_t u8len, char16_t* u16str, size_t u16len) { 605 // A value > SSIZE_MAX is probably a negative value returned as an error and casted. 606 LOG_ALWAYS_FATAL_IF(u16len == 0 || u16len > SSIZE_MAX, "u16len is %zu", u16len); 607 char16_t* end = utf8_to_utf16_no_null_terminator(u8str, u8len, u16str, u16len - 1); 608 *end = 0; 609 return end; 610} 611 612char16_t* utf8_to_utf16_no_null_terminator( 613 const uint8_t* src, size_t srcLen, char16_t* dst, size_t dstLen) { 614 if (dstLen == 0) { 615 return dst; 616 } 617 // A value > SSIZE_MAX is probably a negative value returned as an error and casted. 618 LOG_ALWAYS_FATAL_IF(dstLen > SSIZE_MAX, "dstLen is %zu", dstLen); 619 const uint8_t* const u8end = src + srcLen; 620 const uint8_t* u8cur = src; 621 const char16_t* const u16end = dst + dstLen; 622 char16_t* u16cur = dst; 623 624 while (u8cur < u8end && u16cur < u16end) { 625 size_t u8len = utf8_codepoint_len(*u8cur); 626 uint32_t codepoint = utf8_to_utf32_codepoint(u8cur, u8len); 627 628 // Convert the UTF32 codepoint to one or more UTF16 codepoints 629 if (codepoint <= 0xFFFF) { 630 // Single UTF16 character 631 *u16cur++ = (char16_t) codepoint; 632 } else { 633 // Multiple UTF16 characters with surrogates 634 codepoint = codepoint - 0x10000; 635 *u16cur++ = (char16_t) ((codepoint >> 10) + 0xD800); 636 if (u16cur >= u16end) { 637 // Ooops... not enough room for this surrogate pair. 638 return u16cur-1; 639 } 640 *u16cur++ = (char16_t) ((codepoint & 0x3FF) + 0xDC00); 641 } 642 643 u8cur += u8len; 644 } 645 return u16cur; 646} 647 648} 649