git.iko.soy/streamly
on 8927d11 help sign in
streamly/docs/Developer/utf8-decoder.md
603 lines 25 kB history raw
1Flexible and Economical UTF-8 Decoder
2=====================================
4Systems with elaborate Unicode support usually confront programmers with
5a multitude of different functions and macros to process UTF-8 encoded
6strings, often with different ideas on handling buffer boundaries, state
7between calls, error conditions, and performance characteristics, making
8them difficult to use correctly and efficiently. Implementations also
9tend to be very long and complicated; one popular library has over 500
10lines of code just for one version of the decoder. This page presents
11one that is very easy to use correctly, short, small, fast, and free.
13Implementation in C (C99)
14-------------------------
16 // Copyright (c) 2008-2009 Bjoern Hoehrmann <bjoern@hoehrmann.de>
17 // See http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ for details.
19 #define UTF8_ACCEPT 0
20 #define UTF8_REJECT 1
22 static const uint8_t utf8d[] = {
23 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 00..1f
24 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 20..3f
25 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 40..5f
26 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 60..7f
27 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9, // 80..9f
28 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, // a0..bf
29 8,8,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // c0..df
30 0xa,0x3,0x3,0x3,0x3,0x3,0x3,0x3,0x3,0x3,0x3,0x3,0x3,0x4,0x3,0x3, // e0..ef
31 0xb,0x6,0x6,0x6,0x5,0x8,0x8,0x8,0x8,0x8,0x8,0x8,0x8,0x8,0x8,0x8, // f0..ff
32 0x0,0x1,0x2,0x3,0x5,0x8,0x7,0x1,0x1,0x1,0x4,0x6,0x1,0x1,0x1,0x1, // s0..s0
33 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1, // s1..s2
34 1,2,1,1,1,1,1,2,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1, // s3..s4
35 1,2,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,3,1,3,1,1,1,1,1,1, // s5..s6
36 1,3,1,1,1,1,1,3,1,3,1,1,1,1,1,1,1,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // s7..s8
37 };
39 uint32_t inline
40 decode(uint32_t* state, uint32_t* codep, uint32_t byte) {
41 uint32_t type = utf8d[byte];
43 *codep = (*state != UTF8_ACCEPT) ?
44 (byte & 0x3fu) | (*codep << 6) :
45 (0xff >> type) & (byte);
47 *state = utf8d[256 + *state*16 + type];
48 return *state;
49 }
51Usage
52-----
54UTF-8 is a variable length character encoding. To decode a character one
55or more bytes have to be read from a string. The `decode` function
56implements a single step in this process. It takes two parameters
57maintaining state and a byte, and returns the state achieved after
58processing the byte. Specifically, it returns the value `UTF8_ACCEPT`
59(0) if enough bytes have been read for a character, `UTF8_REJECT` (1) if
60the byte is not allowed to occur at its position, and some other
61positive value if more bytes have to be read.
63When decoding the first byte of a string, the caller must set the state
64variable to `UTF8_ACCEPT`. If, after decoding one or more bytes the
65state `UTF8_ACCEPT` is reached again, then the decoded Unicode character
66value is available through the `codep` parameter. If the state
67`UTF8_REJECT` is entered, that state will never be exited unless the
68caller intervenes. See the examples below for more information on usage
69and error handling, and the section on implementation details for how
70the decoder is constructed.
72Examples
73--------
75### Validating and counting characters
77This function checks if a null-terminated string is a well-formed UTF-8
78sequence and counts how many code points are in the string.
80 int
81 countCodePoints(uint8_t* s, size_t* count) {
82 uint32_t codepoint;
83 uint32_t state = 0;
85 for (*count = 0; *s; ++s)
86 if (!decode(&state, &codepoint, *s))
87 *count += 1;
89 return state != UTF8_ACCEPT;
90 }
92It could be used like so:
94 if (countCodePoints(s, &count)) {
95 printf("The string is malformed\n");
96 } else {
97 printf("The string is %u characters long\n", count);
98 }
100### Printing code point values
102This function prints out all code points in the string and an error
103message if unexpected bytes are encountered, or if the string ends with
104an incomplete sequence.
106 void
107 printCodePoints(uint8_t* s) {
108 uint32_t codepoint;
109 uint32_t state = 0;
111 for (; *s; ++s)
112 if (!decode(&state, &codepoint, *s))
113 printf("U+%04X\n", codepoint);
115 if (state != UTF8_ACCEPT)
116 printf("The string is not well-formed\n");
118 }
120### Printing UTF-16 code units
122This loop prints out UTF-16 code units for the characters in a
123null-terminated UTF-8 encoded string.
125 for (; *s; ++s) {
127 if (decode(&state, &codepoint, *s))
128 continue;
130 if (codepoint <= 0xFFFF) {
131 printf("0x%04X\n", codepoint);
132 continue;
133 }
135 // Encode code points above U+FFFF as surrogate pair.
136 printf("0x%04X\n", (0xD7C0 + (codepoint >> 10)));
137 printf("0x%04X\n", (0xDC00 + (codepoint & 0x3FF)));
138 }
140### Error recovery
142It is sometimes desirable to recover from errors when decoding strings
143that are supposed to be UTF-8 encoded. Programmers should be aware that
144this can negatively affect the security properties of their application.
145A common recovery method is to replace malformed sequences with a
146substitute character like `U+FFFD REPLACEMENT CHARACTER`.
148Decoder implementations differ in which octets they replace and where
149they restart. Consider for instance the sequence `0xED 0xA0 0x80`. It
150encodes a surrogate code point which is prohibited in UTF-8. A
151recovering decoder may replace the whole sequence and restart with the
152next byte, or it may replace the first byte and restart with the second
153byte, replace it, restart with the third, and replace the third byte
154aswell.
156The following code implements one such recovery strategy. When an
157unexpected byte is encountered, the sequence up to that point will be
158replaced and, if the error occurred in the middle of a sequence, will
159retry the byte as if it occurred at the beginning of a string. Note that
160the decode function detects errors as early as possible, so the sequence
161`0xED 0xA0 0x80` would result in three replacement characters.
163 for (prev = 0, current = 0; *s; prev = current, ++s) {
165 switch (decode(&current, &codepoint, *s)) {
166 case UTF8_ACCEPT:
167 // A properly encoded character has been found.
168 printf("U+%04X\n", codepoint);
169 break;
171 case UTF8_REJECT:
172 // The byte is invalid, replace it and restart.
173 printf("U+FFFD (Bad UTF-8 sequence)\n");
174 current = UTF8_ACCEPT;
175 if (prev != UTF8_ACCEPT)
176 s--;
177 break;
178 ...
180For some recovery strategies it may be useful to determine the number of
181bytes expected. The states in the automaton are numbered such that,
182assuming C\'s division operator, `state / 3 + 1` is that number. Of
183course, this will only work for states other than `UTF8_ACCEPT` and
184`UTF8_REJECT`. This number could then be used, for instance, to skip the
185continuation octets in the illegal sequence `0xED 0xA0 0x80` so it will
186be replaced by a single replacement character.
188### Transcoding to UTF-16 buffer
190This is a rough outline of a UTF-16 transcoder. Actual applications
191would add code for error reporting, reporting of words written, required
192buffer size in the case of a small buffer, and possibly other things.
193Note that in order to avoid checking for free space in the inner loop,
194we determine how many bytes can be read without running out of space.
195This is one utf-8 byte per available utf-16 word, with one exception: if
196the last byte read was the third byte in a four byte sequence we would
197get two words for the next byte; so we read one byte less than we have
198words available. This additional word is also needed for
199null-termination, so it\'s never wrong to read one less.
201 int
202 toUtf16(uint8_t* src, size_t srcBytes, uint16_t* dst, size_t dstWords, ...) {
204 uint8_t* src_actual_end = src + srcBytes;
205 uint8_t* s = src;
206 uint16_t* d = dst;
207 uint32_t codepoint;
208 uint32_t state = 0;
210 while (s < src_actual_end) {
212 size_t dst_words_free = dstWords - (d - dst);
213 uint8_t* src_current_end = s + dst_words_free - 1;
215 if (src_actual_end < src_current_end)
216 src_current_end = src_actual_end;
218 if (src_current_end <= s)
219 goto toosmall;
221 while (s < src_current_end) {
223 if (decode(&state, &codepoint, *s++))
224 continue;
226 if (codepoint > 0xffff) {
227 *d++ = (uint16_t)(0xD7C0 + (codepoint >> 10));
228 *d++ = (uint16_t)(0xDC00 + (codepoint & 0x3FF));
229 } else {
230 *d++ = (uint16_t)codepoint;
231 }
232 }
233 }
235 if (state != UTF8_ACCEPT) {
236 ...
237 }
239 if ((dstWords - (d - dst)) == 0)
240 goto toosmall;
242 *d++ = 0;
243 ...
245 toosmall:
246 ...
247 }
249Implementation details
250----------------------
252The `utf8d` table consists of two parts. The first part maps bytes to
253character classes, the second part encodes a deterministic finite
254automaton using these character classes as transitions. This section
255details the composition of the table.
257### Canonical UTF-8 automaton
259UTF-8 is a variable length character encoding. That means state has to
260be maintained while processing a string. The following transition graph
261illustrates the process. We start in state zero, and whenever we come
262back to it, we\'ve seen a whole Unicode character. Transitions not in
263the graph are disallowed; they all lead to state one, which has been
264omitted for readability.
266![DFA with range transitions](/docs/Developer/dfa-bytes.png)
268### Automaton with character class transitions
270The byte ranges in the transition graph above are not easily encoded in
271the automaton in a manner that would allow fast lookup. Instead of
272encoding the ranges directly, the ranges are split such that each byte
273belongs to exactly one character class. Then the transitions go over
274these character classes.
276![DFA with class transitions](/docs/Developer/dfa-classes.png)
278### Mapping bytes to character classes
280Primarily to save space in the transition table, bytes are mapped to
281character classes. This is the mapping:
283|||||
284|-|-|-|-|
285| 00..7f | 0 | 80..8f | 1 |
286| 90..9f | 9 | a0..bf | 7 |
287| c0..c1 | 8 | c2..df | 2 |
288| e0..e0 | 10 | e1..ec | 3 |
289| ed..ed | 4 | ee..ef | 3 |
290| f0..f0 | 11 | f1..f3 | 6 |
291| f4..f4 | 5 | f5..ff | 8 |
294For bytes that may occur at the beginning of a multibyte sequence, the
295character class number is also used to remove the most significant bits
296from the byte, which do not contribute to the actual code point value.
297Note that `0xc0`, `0xc1`, and `0xf5` .. `0xff` have all their bits
298removed. These bytes cannot occur in well-formed sequences, so it does
299not matter which bits, if any, are retained.
301|||||||||||||
302|-|-|-|-|-|-|-|-|-|-|-|-|
303| c0 | 8 | **11000000** | d0 | 2 | **11**010000 | e0 | 10 | **11100000** | f0 | 11 | **11110000** |
304| c1 | 8 | **11000001** | d1 | 2 | **11**010001 | e1 | 3 | **111**00001 | f1 | 6 | **111100**01 |
305| c2 | 2 | **11**000010 | d2 | 2 | **11**010010 | e2 | 3 | **111**00010 | f2 | 6 | **111100**10 |
306| c3 | 2 | **11**000011 | d3 | 2 | **11**010011 | e3 | 3 | **111**00011 | f3 | 6 | **111100**11 |
307| c4 | 2 | **11**000100 | d4 | 2 | **11**010100 | e4 | 3 | **111**00100 | f4 | 5 | **11110**100 |
308| c5 | 2 | **11**000101 | d5 | 2 | **11**010101 | e5 | 3 | **111**00101 | f5 | 8 | **11110101** |
309| c6 | 2 | **11**000110 | d6 | 2 | **11**010110 | e6 | 3 | **111**00110 | f6 | 8 | **11110110** |
310| c7 | 2 | **11**000111 | d7 | 2 | **11**010111 | e7 | 3 | **111**00111 | f7 | 8 | **11110111** |
311| c8 | 2 | **11**001000 | d8 | 2 | **11**011000 | e8 | 3 | **111**01000 | f8 | 8 | **11111000** |
312| c9 | 2 | **11**001001 | d9 | 2 | **11**011001 | e9 | 3 | **111**01001 | f9 | 8 | **11111001** |
313| ca | 2 | **11**001010 | da | 2 | **11**011010 | ea | 3 | **111**01010 | fa | 8 | **11111010** |
314| cb | 2 | **11**001011 | db | 2 | **11**011011 | eb | 3 | **111**01011 | fb | 8 | **11111011** |
315| cc | 2 | **11**001100 | dc | 2 | **11**011100 | ec | 3 | **111**01100 | fc | 8 | **11111100** |
316| cd | 2 | **11**001101 | dd | 2 | **11**011101 | ed | 4 | **1110**1101 | fd | 8 | **11111101** |
317| ce | 2 | **11**001110 | de | 2 | **11**011110 | ee | 3 | **111**01110 | fe | 8 | **11111110** |
318| cf | 2 | **11**001111 | df | 2 | **11**011111 | ef | 3 | **111**01111 | ff | 8 | **11111111** |
321Notes on Variations
322-------------------
324There are several ways to change the implementation of this decoder. For
325example, the size of the data table can be reduced, at the cost of a
326couple more instructions, so it omits the mapping of bytes in the
327US-ASCII range, and since all entries in the table are 4 bit values, two
328values could be stored in a single byte.
330In some situations it may be beneficial to have a separate start state.
331This is easily achieved by copying the s0 state in the array to the end,
332and using the new state 9 as start state as needed.
334Where callers require the code point values, compilers tend to generate
335slightly better code if the state calculation is moved into the
336branches, for example
338 if (*state != UTF8_ACCEPT) {
339 *state = utf8d[256 + *state*16 + type];
340 *codep = (*codep << 6) | (byte & 63);
341 } else {
342 *state = utf8d[256 + *state*16 + type];
343 *codep = (byte) & (255 >> type);
344 }
346As the state will be zero in the else branch, this saves a shift and an
347addition for each starter. Unfortunately, compilers will then typically
348generate worse code if the codepoint value is not needed. Naturally,
349then, two functions could be used, one that only calculates the states
350for validation, counting, and similar applications, and one for full
351decoding. For the sample UTF-16 transcoder a more substantial increase
352in performance can be achieved by manually including the decode code in
353the inner loop; then it is also worthwhile to make code points in the
354US-ASCII range a special case:
356 while (s < src_current_end) {
358 uint32_t byte = *s++;
359 uint32_t type = utf8d[byte];
361 if (state != UTF8_ACCEPT) {
362 codep = (codep << 6) | (byte & 63);
363 state = utf8d[256 + state*16 + type];
365 if (state)
366 continue;
368 } else if (byte > 0x7f) {
369 codep = (byte) & (255 >> type);
370 state = utf8d[256 + type];
371 continue;
373 } else {
374 *d++ = (uint16_t)byte;
375 continue;
376 }
377 ...
379Another variation worth of note is changing the comparison when setting
380the code point value to this:
382 *codep = (*state > UTF8_REJECT) ?
383 (byte & 0x3fu) | (*codep << 6) :
384 (0xff >> type) & (byte);
386This ensures that the code point value does not exceed the value `0xff`
387after some malformed sequence is encountered.
389As written, the decoder disallows encoding of surrogate code points,
390overlong 2, 3, and 4 byte sequences, and 4 byte sequences outside the
391Unicode range. Allowing them can have serious security implications, but
392can easily be achieved by changing the character class assignments in
393the table.
395The code samples have generally been written to perform well on my
396system when compiled with Visual C++ 7.1 and GCC 3.4.5. Slight changes
397may improve performance, for example, Visual C++ 7.1 will produce
398slightly faster code when, in the manually inlined version of the
399transcoder discussed above, the type assignment is moved into the
400branches where it is needed, and the state and codepoint assignments in
401the non-ASCII starter is swapped (approximately a 5% increase), but GCC
4023.4.5 will produce considerably slower code (approximately 10%).
404I have experimented with various rearrangements of states and character
405classes. A seemingly promising one is the following:
407![Re-arranged DFA with class transitions](/docs/Developer/dfa-rearr.png)
409One of the continuation ranges has been split into two, the other
410changes are just renamings. This arrangement allows, when a continuation
411octet is expected, to compute the character class with a shift instead
412of a table lookup, and when looking at a non-ASCII starter, the next
413state is simply the character class. On my system the change in
414performance is in the area of +/- 1%. This encoding would have a number
415of downsides: more rejecting states are required to account for
416continuation octets where starters are expected, the table formatting
417would use more hex notation making it longer, and calculating the number
418of expected continuation octets from a given state is more difficult.
419One thing I\'d still like to try out is if, perhaps by adding a couple
420of additional states, for continuation states the next state can be
421computed without any table lookup with a few easily paired instructions.
423On 24th June 2010 Rich Felker pointed out that the state values in the
424transition table can be pre-multiplied with 16 which would save a shift
425instruction for every byte. D\'oh! We actually just need 12 and can
426throw away the filler values previously in the table making the table 36
427bytes shorter and save the shift in the code.
429 // Copyright (c) 2008-2010 Bjoern Hoehrmann <bjoern@hoehrmann.de>
430 // See http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ for details.
432 #define UTF8_ACCEPT 0
433 #define UTF8_REJECT 12
435 static const uint8_t utf8d[] = {
436 // The first part of the table maps bytes to character classes that
437 // to reduce the size of the transition table and create bitmasks.
438 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
439 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
440 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
441 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
442 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
443 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
444 8,8,2,2,2,2,2,2,2,2,2,2,2,2,2,2, 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
445 10,3,3,3,3,3,3,3,3,3,3,3,3,4,3,3, 11,6,6,6,5,8,8,8,8,8,8,8,8,8,8,8,
447 // The second part is a transition table that maps a combination
448 // of a state of the automaton and a character class to a state.
449 0,12,24,36,60,96,84,12,12,12,48,72, 12,12,12,12,12,12,12,12,12,12,12,12,
450 12, 0,12,12,12,12,12, 0,12, 0,12,12, 12,24,12,12,12,12,12,24,12,24,12,12,
451 12,12,12,12,12,12,12,24,12,12,12,12, 12,24,12,12,12,12,12,12,12,24,12,12,
452 12,12,12,12,12,12,12,36,12,36,12,12, 12,36,12,12,12,12,12,36,12,36,12,12,
453 12,36,12,12,12,12,12,12,12,12,12,12,
454 };
456 uint32_t inline
457 decode(uint32_t* state, uint32_t* codep, uint32_t byte) {
458 uint32_t type = utf8d[byte];
460 *codep = (*state != UTF8_ACCEPT) ?
461 (byte & 0x3fu) | (*codep << 6) :
462 (0xff >> type) & (byte);
464 *state = utf8d[256 + *state + type];
465 return *state;
466 }
468Notes on performance
469--------------------
471To conduct some ad-hoc performance testing I\'ve used three different
472UTF-8 encoded buffers and passed them through a couple of UTF-8 to
473UTF-16 transcoders. The large buffer is a April 2009 Hindi Wikipedia
474article XML dump, the medium buffer Markus Kuhn\'s UTF-8-demo.txt, and
475the tiny buffer my name, each about the number of times required for
476about 1GB of data. All tests ran on a [Intel Prescott
477Celeron](http://en.wikipedia.org/wiki/Celeron#Prescott-256) at 2666 MHz.
478See [Changes](#changes) for some additional details.
480 | | Large | Medium | Tiny |
481 |---------------------------------------------------------------------------|---------| ---------|----------|
482 |`NS_CStringToUTF16()` Mozilla 1.9 (*includes malloc/free time*) | 36924ms| 39773ms| 107958ms|
483 |`iconv()` 1.9 compiled with Visual C++ (Cygwin iconv 1.11 similar) | 22740ms| 21765ms| 32595ms|
484 |`g_utf8_to_utf16()` Cygwin Glib 2.0 (*includes malloc/free time*) | 21599ms| 20345ms| 98782ms|
485 |`ConvertUTF8toUTF16()` Unicode Inc., Visual C++ 7.1 -Ox -Ot -G7 | 11183ms| 11251ms| 19453ms|
486 |`MultiByteToWideChar()` Windows API (Server 2003 SP2) | 9857ms| 10779ms| 12771ms|
487 |`u_strFromUTF8` from ICU 4.0.1 (Visual Studio 2008, web site distribution) | 8778ms| 5223ms| 5419ms|
488 |`PyUnicode_DecodeUTF8Stateful` (3.1a2), Visual C++ 7.1 -Ox -Ot -G7 | 4523ms| 5686ms| 3138ms|
489 |Example section transcoder, Visual C++ 7.1 -Ox -Ot -G7 | 5397ms| 5789ms| 6250ms|
490 |Manually inlined transcoder (see above), Visual C++ 7.1 -Ox -Ot -G7 | 4277ms| 4998ms| 4640ms|
491 |Same, Cygwin GCC 3.4.5 -march=prescott -fomit-frame-pointer -O3 | 4492ms| 5154ms| 4432ms|
492 |Same, Cygwin GCC 4.3.2 -march=prescott -fomit-frame-pointer -O3 | 5439ms| 6322ms| 5567ms|
493 |Same, Visual C++ 6.0 -TP -O2 | 5398ms| 6259ms| 6446ms|
494 |Same, Visual C++ 7.1 -Ox -Ot -G7 (*includes malloc/free time*) | 5498ms| 5086ms| 25852ms|
496I have also timed functions that `xor` all code points in the large
497buffer. In Visual Studio 2008 ICU\'s `U8_NEXT` macro comes out at
498\~8000ms, the `U8_NEXT_UNSAFE` macro, which requires complete and
499well-formed input, at \~4000ms, and the `decode` function is at
500\~5900ms. Using the same manual inlining as for the transcode function,
501Cygwin GCC 3.4.5 -march=prescott -O3 -fomit-frame-pointer brings it down
502to roughly the same times as the transcode function for all three
503buffers.
505While these results do not model real-world applications well, it seems
506reasonable to suggest that the reduced complexity does not come at the
507price of reduced performance. Note that instructions that compute the
508code point values will generally be optimized away when not needed. For
509example, checking if a null-terminated string is properly UTF-8 encoded
510\...
512 int
513 IsUTF8(uint8_t* s) {
514 uint32_t codepoint, state = 0;
516 while (*s)
517 decode(&state, &codepoint, *s++);
519 return state == UTF8_ACCEPT;
520 }
522\... does not require the individual code point values, and so the loop
523becomes something like this:
525 l1: movzx eax,al
526 shl edx,4
527 add ecx,1
528 movzx eax,byte ptr [eax+404000h]
529 movzx edx,byte ptr [eax+edx+256+404000h]
530 movzx eax,byte ptr [ecx]
531 test al,al
532 jne l1
534For comparison, this is a typical `strlen` loop:
536 l1: mov cl,byte ptr [eax]
537 add eax,1
538 test cl,cl
539 jne l1
541With the large buffer and the same number of times as above, `strlen`
542takes 1507ms while `IsUTF8` takes 2514ms.
544License
545-------
547Copyright (c) 2008-2009 [Bjoern Hoehrmann](http://bjoern.hoehrmann.de/)
548\<<bjoern@hoehrmann.de>\>
550Permission is hereby granted, free of charge, to any person obtaining a
551copy of this software and associated documentation files (the
552\"Software\"), to deal in the Software without restriction, including
553without limitation the rights to use, copy, modify, merge, publish,
554distribute, sublicense, and/or sell copies of the Software, and to
555permit persons to whom the Software is furnished to do so, subject to
556the following conditions:
558The above copyright notice and this permission notice shall be included
559in all copies or substantial portions of the Software.
561THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND,
562EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
563MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
564IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
565CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
566TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
567SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
568:::
570Changes
571-------
57325 Jun 2010
574: Added an improved variation based on an observation from Rich
575 Felker.
57730 April 2009
578: Added some more items to the performance table: the manually inlined
579 transcoder allocating worst case memory for each run and freeing it
580 before the next run; and results for Mozilla\'s NS\_CStringToUTF16
581 (a new nsAutoString is created for each run, and truncated before
582 the next). This used the XULRunner SDK 1.9.0.7 binary distribution
583 from the Mozilla website.
58518 April 2009
586: Added notes to the Variations section on handling malformed
587 sequences and failed optimization attempts.
58914 April 2009
590: Added PyUnicode\_DecodeUTF8Stateful times; the function has been
591 modified slightly so it works outside Python and so it uses a
592 pre-allocated buffer. Normally does not check output buffer
593 boundaries but rather allocates a worst case buffer, then resizes
594 it. Apparently the decoder [allows encodings of surrogate code
595 points](http://bugs.python.org/issue3672).
597Author
598------
600[Björn Höhrmann](http://bjoern.hoehrmann.de) <bjoern@hoehrmann.de>
601([Donate via
602SourceForge](http://sourceforge.net/developer/user_donations.php?user_id=188003),
603[PayPal](https://www.paypal.com/cgi-bin/webscr?cmd=_xclick&business=bjoern@hoehrmann.de&item_name=Support+Bjoern+Hoehrmann))