• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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  */
utf32_codepoint_utf8_length(char32_t srcChar)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 
utf32_codepoint_to_utf8(uint8_t * dstP,char32_t srcChar,size_t bytes)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 
strlen32(const char32_t * s)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 
strnlen32(const char32_t * s,size_t maxlen)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 
utf32_at_internal(const char * cur,size_t * num_read)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 
utf32_from_utf8_at(const char * src,size_t src_len,size_t index,size_t * next_index)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 
utf32_to_utf8_length(const char32_t * src,size_t src_len)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         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 
utf32_to_utf8(const char32_t * src,size_t src_len,char * dst,size_t dst_len)196 void 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 
strcmp16(const char16_t * s1,const char16_t * s2)220 int 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 
strncmp16(const char16_t * s1,const char16_t * s2,size_t n)234 int 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 
strcpy16(char16_t * dst,const char16_t * src)253 char16_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 
strlen16(const char16_t * s)266 size_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 
strncpy16(char16_t * dst,const char16_t * src,size_t n)275 char16_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 
strnlen16(const char16_t * s,size_t maxlen)293 size_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 
strstr16(const char16_t * src,const char16_t * target)306 char16_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 
strzcmp16(const char16_t * s1,size_t n1,const char16_t * s2,size_t n2)325 int 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 
strzcmp16_h_n(const char16_t * s1H,size_t n1,const char16_t * s2N,size_t n2)344 int 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 
utf16_to_utf8(const char16_t * src,size_t src_len,char * dst,size_t dst_len)365 void 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 
utf8_length(const char * src)399 ssize_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 
utf16_to_utf8_length(const char16_t * src,size_t src_len)442 ssize_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  */
utf8_codepoint_len(uint8_t ch)481 static inline size_t utf8_codepoint_len(uint8_t ch)
482 {
483     return ((0xe5000000 >> ((ch >> 3) & 0x1e)) & 3) + 1;
484 }
485 
utf8_shift_and_mask(uint32_t * codePoint,const uint8_t byte)486 static inline void utf8_shift_and_mask(uint32_t* codePoint, const uint8_t byte)
487 {
488     *codePoint <<= 6;
489     *codePoint |= 0x3F & byte;
490 }
491 
utf8_to_utf32_length(const char * src,size_t src_len)492 size_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 
utf8_to_utf32(const char * src,size_t src_len,char32_t * dst)517 void 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 
utf8_to_utf32_codepoint(const uint8_t * src,size_t length)534 static 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 
utf8_to_utf16_length(const uint8_t * u8str,size_t u8len,bool overreadIsFatal)564 ssize_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 
utf8_to_utf16(const uint8_t * u8str,size_t u8len,char16_t * u16str,size_t u16len)604 char16_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 
utf8_to_utf16_no_null_terminator(const uint8_t * src,size_t srcLen,char16_t * dst,size_t dstLen)612 char16_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