Debian Codegraph @

extra/protobuf/protobuf-24.4/third_party/utf8_range/README.md

raw
1 [![Build Status](https://travis-ci.com/cyb70289/utf8.svg?branch=master)](https://travis-ci.com/cyb70289/utf8)
2
3 # Fast UTF-8 validation with Range algorithm (NEON+SSE4+AVX2)
4
5 This is a brand new algorithm to leverage SIMD for fast UTF-8 string validation. Both **NEON**(armv8a) and **SSE4** versions are implemented. **AVX2** implementation contributed by [ioioioio](https://github.com/ioioioio).
6
7 Four UTF-8 validation methods are compared on both x86 and Arm platforms. Benchmark result shows range base algorithm is the best solution on Arm, and achieves same performance as [Lemire's approach](https://lemire.me/blog/2018/05/16/validating-utf-8-strings-using-as-little-as-0-7-cycles-per-byte/) on x86.
8
9 * Range based algorithm
10 * range-neon.c: NEON version
11 * range-sse.c: SSE4 version
12 * range-avx2.c: AVX2 version
13 * range2-neon.c, range2-sse.c: Process two blocks in one iteration
14 * [Lemire's SIMD implementation](https://github.com/lemire/fastvalidate-utf-8)
15 * lemire-sse.c: SSE4 version
16 * lemire-avx2.c: AVX2 version
17 * lemire-neon.c: NEON porting
18 * naive.c: Naive UTF-8 validation byte by byte
19 * lookup.c: [Lookup-table method](http://bjoern.hoehrmann.de/utf-8/decoder/dfa/)
20
21 ## About the code
22
23 * Run "make" to build. Built and tested with gcc-7.3.
24 * Run "./utf8" to see all command line options.
25 * Benchmark
26 * Run "./utf8 bench" to bechmark all algorithms with [default test file](https://raw.githubusercontent.com/cyb70289/utf8/master/UTF-8-demo.txt).
27 * Run "./utf8 bench size NUM" to benchmark specified string size.
28 * Run "./utf8 test" to test all algorithms with positive and negative test cases.
29 * To benchmark or test specific algorithm, run something like "./utf8 bench range".
30
31 ## Benchmark result (MB/s)
32
33 ### Method
34 1. Generate UTF-8 test buffer per [test file](https://raw.githubusercontent.com/cyb70289/utf8/master/UTF-8-demo.txt) or buffer size.
35 1. Call validation sub-routines in a loop until 1G bytes are checked.
36 1. Calculate speed(MB/s) of validating UTF-8 strings.
37
38 ### NEON(armv8a)
39 Test case | naive | lookup | lemire | range | range2
40 :-------- | :---- | :----- | :----- | :---- | :-----
41 [UTF-demo.txt](https://raw.githubusercontent.com/cyb70289/utf8/master/UTF-8-demo.txt) | 562.25 | 412.84 | 1198.50 | 1411.72 | **1579.85**
42 32 bytes | 651.55 | 441.70 | 891.38 | 1003.95 | **1043.58**
43 33 bytes | 660.00 | 446.78 | 588.77 | 1009.31 | **1048.12**
44 129 bytes | 771.89 | 402.55 | 938.07 | 1283.77 | **1401.76**
45 1K bytes | 811.92 | 411.58 | 1188.96 | 1398.15 | **1560.23**
46 8K bytes | 812.25 | 412.74 | 1198.90 | 1412.18 | **1580.65**
47 64K bytes | 817.35 | 412.24 | 1200.20 | 1415.11 | **1583.86**
48 1M bytes | 815.70 | 411.93 | 1200.93 | 1415.65 | **1585.40**
49
50 ### SSE4(E5-2650)
51 Test case | naive | lookup | lemire | range | range2
52 :-------- | :---- | :----- | :----- | :---- | :-----
53 [UTF-demo.txt](https://raw.githubusercontent.com/cyb70289/utf8/master/UTF-8-demo.txt) | 753.70 | 310.41 | 3954.74 | 3945.60 | **3986.13**
54 32 bytes | 1135.76 | 364.07 | **2890.52** | 2351.81 | 2173.02
55 33 bytes | 1161.85 | 376.29 | 1352.95 | **2239.55** | 2041.43
56 129 bytes | 1161.22 | 322.47 | 2742.49 | **3315.33** | 3249.35
57 1K bytes | 1310.95 | 310.72 | 3755.88 | 3781.23 | **3874.17**
58 8K bytes | 1348.32 | 307.93 | 3860.71 | 3922.81 | **3968.93**
59 64K bytes | 1301.34 | 308.39 | 3935.15 | 3973.50 | **3983.44**
60 1M bytes | 1279.78 | 309.06 | 3923.51 | 3953.00 | **3960.49**
61
62 ## Range algorithm analysis
63
64 Basic idea:
65 * Load 16 bytes
66 * Leverage SIMD to calculate value range for each byte efficiently
67 * Validate 16 bytes at once
68
69 ### UTF-8 coding format
70
71 http://www.unicode.org/versions/Unicode6.0.0/ch03.pdf, page 94
72
73 Table 3-7. Well-Formed UTF-8 Byte Sequences
74
75 Code Points | First Byte | Second Byte | Third Byte | Fourth Byte |
76 :---------- | :--------- | :---------- | :--------- | :---------- |
77 U+0000..U+007F | 00..7F | | | |
78 U+0080..U+07FF | C2..DF | 80..BF | | |
79 U+0800..U+0FFF | E0 | ***A0***..BF| 80..BF | |
80 U+1000..U+CFFF | E1..EC | 80..BF | 80..BF | |
81 U+D000..U+D7FF | ED | 80..***9F***| 80..BF | |
82 U+E000..U+FFFF | EE..EF | 80..BF | 80..BF | |
83 U+10000..U+3FFFF | F0 | ***90***..BF| 80..BF | 80..BF |
84 U+40000..U+FFFFF | F1..F3 | 80..BF | 80..BF | 80..BF |
85 U+100000..U+10FFFF | F4 | 80..***8F***| 80..BF | 80..BF |
86
87 To summarise UTF-8 encoding:
88 * Depending on First Byte, one legal character can be 1, 2, 3, 4 bytes
89 * For First Byte within C0..DF, character length = 2
90 * For First Byte within E0..EF, character length = 3
91 * For First Byte within F0..F4, character length = 4
92 * C0, C1, F5..FF are not allowed
93 * Second,Third,Fourth Bytes must lie in 80..BF.
94 * There are four **special cases** for Second Byte, shown ***bold italic*** in above table.
95
96 ### Range table
97
98 Range table maps range index 0 ~ 15 to minimal and maximum values allowed. Our task is to observe input string, find the pattern and set correct range index for each byte, then validate input string.
99
100 Index | Min | Max | Byte type
101 :---- | :-- | :-- | :--------
102 0 | 00 | 7F | First Byte, ASCII
103 1,2,3 | 80 | BF | Second, Third, Fourth Bytes
104 4 | A0 | BF | Second Byte after E0
105 5 | 80 | 9F | Second Byte after ED
106 6 | 90 | BF | Second Byte after F0
107 7 | 80 | 8F | Second Byte after F4
108 8 | C2 | F4 | First Byte, non-ASCII
109 9..15(NEON) | FF | 00 | Illegal: unsigned char >= 255 && unsigned char <= 0
110 9..15(SSE) | 7F | 80 | Illegal: signed char >= 127 && signed char <= -128
111
112 ### Calculate byte ranges (ignore special cases)
113
114 Ignoring the four special cases(E0,ED,F0,F4), how should we set range index for each byte?
115
116 * Set range index to 0(00..7F) for all bytes by default
117 * Find non-ASCII First Byte (C0..FF), set their range index to 8(C2..F4)
118 * For First Byte within C0..DF, set next byte's range index to 1(80..BF)
119 * For First Byte within E0..EF, set next two byte's range index to 2,1(80..BF) in sequence
120 * For First Byte within F0..FF, set next three byte's range index to 3,2,1(80..BF) in sequence
121
122 To implement above operations efficiently with SIMD:
123 * For 16 input bytes, use lookup table to map C0..DF to 1, E0..EF to 2, F0..FF to 3, others to 0. Save to first_len.
124 * Map C0..FF to 8, we get range indices for First Byte.
125 * Shift first_len one byte, we get range indices for Second Byte.
126 * Saturate substract first_len by one(3->2, 2->1, 1->0, 0->0), then shift two bytes, we get range indices for Third Byte.
127 * Saturate substract first_len by two(3->1, 2->0, 1->0, 0->0), then shift three bytes, we get range indices for Fourth Byte.
128
129 Example(assume no previous data)
130
131 Input | F1 | 80 | 80 | 80 | 80 | C2 | 80 | 80 | ...
132 :---- | :- | :- | :- | :- | :- | :- | :- | :- | :--
133 *first_len* |*3* |*0* |*0* |*0* |*0* |*1* |*0* |*0* |*...*
134 First Byte | 8 | 0 | 0 | 0 | 0 | 8 | 0 | 0 | ...
135 Second Byte | 0 | 3 | 0 | 0 | 0 | 0 | 1 | 0 | ...
136 Third Byte | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | ...
137 Fourth Byte | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | ...
138 Range index | 8 | 3 | 2 | 1 | 0 | 8 | 1 | 0 | ...
139
140 ```c
141 Range_index = First_Byte | Second_Byte | Third_Byte | Fourth_Byte
142 ```
143
144 #### Error handling
145
146 * C0,C1,F5..FF are not included in range table and will always be detected.
147 * Illegal 80..BF will have range index 0(00..7F) and be detected.
148 * Based on First Byte, according Second, Third and Fourth Bytes will have range index 1/2/3, to make sure they must lie in 80..BF.
149 * If non-ASCII First Byte overlaps, above algorithm will set range index of the latter First Byte to 9,10,11, which are illegal ranges. E.g, Input = F1 80 C2 90 --> Range index = 8 3 10 1, where 10 indicates error. See table below.
150
151 Overlapped non-ASCII First Byte
152
153 Input | F1 | 80 | C2 | 90
154 :---- | :- | :- | :- | :-
155 *first_len* |*3* |*0* |*1* |*0*
156 First Byte | 8 | 0 | 8 | 0
157 Second Byte | 0 | 3 | 0 | 1
158 Third Byte | 0 | 0 | 2 | 0
159 Fourth Byte | 0 | 0 | 0 | 1
160 Range index | 8 | 3 |***10***| 1
161
162 ### Adjust Second Byte range for special cases
163
164 Range index adjustment for four special cases
165
166 First Byte | Second Byte | Before adjustment | Correct index | Adjustment |
167 :--------- | :---------- | :---------------- | :------------ | :---------
168 E0 | A0..BF | 2 | 4 | **2**
169 ED | 80..9F | 2 | 5 | **3**
170 F0 | 90..BF | 3 | 6 | **3**
171 F4 | 80..8F | 3 | 7 | **4**
172
173 Range index adjustment can be reduced to below problem:
174
175 ***Given 16 bytes, replace E0 with 2, ED with 3, F0 with 3, F4 with 4, others with 0.***
176
177 A naive SIMD approach:
178 1. Compare 16 bytes with E0, get the mask for eacy byte (FF if equal, 00 otherwise)
179 1. And the mask with 2 to get adjustment for E0
180 1. Repeat step 1,2 for ED,F0,F4
181
182 At least **eight** operations are required for naive approach.
183
184 Observing special bytes(E0,ED,F0,F4) are close to each other, we can do much better using lookup table.
185
186 #### NEON
187
188 NEON ```tbl``` instruction is very convenient for table lookup:
189 * Table can be up to 16x4 bytes in size
190 * Return zero if index is out of range
191
192 Leverage these features, we can solve the problem with as few as **two** operations:
193 * Precreate a 16x2 lookup table, where table[0]=2, table[13]=3, table[16]=3, table[20]=4, table[others]=0.
194 * Substract input bytes with E0 (E0 -> 0, ED -> 13, F0 -> 16, F4 -> 20).
195 * Use the substracted byte as index of lookup table and get range adjustment directly.
196 * For indices less than 32, we get zero or required adjustment value per input byte
197 * For out of bound indices, we get zero per ```tbl``` behaviour
198
199 #### SSE
200
201 SSE ```pshufb``` instruction is not as friendly as NEON ```tbl``` in this case:
202 * Table can only be 16 bytes in size
203 * Out of bound indices are handled this way:
204 * If 7-th bit of index is 0, least four bits are used as index (E.g, index 0x73 returns 3rd element)
205 * If 7-th bit of index is 1, return 0 (E.g, index 0x83 returns 0)
206
207 We can still leverage these features to solve the problem in **five** operations:
208 * Precreate two tables:
209 * table_df[1] = 2, table_df[14] = 3, table_df[others] = 0
210 * table_ef[1] = 3, table_ef[5] = 4, table_ef[others] = 0
211 * Substract input bytes with EF (E0 -> 241, ED -> 254, F0 -> 1, F4 -> 5) to get the temporary indices
212 * Get range index for E0,ED
213 * Saturate substract temporary indices with 240 (E0 -> 1, ED -> 14, all values below 240 becomes 0)
214 * Use substracted indices to look up table_df, get the correct adjustment
215 * Get range index for F0,F4
216 * Saturate add temporary indices with 112(0x70) (F0 -> 0x71, F4 -> 0x75, all values above 16 will be larger than 128(7-th bit set))
217 * Use added indices to look up table_ef, get the correct adjustment (index 0x71,0x75 returns 1st,5th elements, per ```pshufb``` behaviour)
218
219 #### Error handling
220
221 * For overlapped non-ASCII First Byte, range index before adjustment is 9,10,11. After adjustment (adds 2,3,4 or 0), the range index will be 9 to 15, which is still illegal in range table. So the error will be detected.
222
223 ### Handling remaining bytes
224
225 For remaining input less than 16 bytes, we will fallback to naive byte by byte approach to validate them, which is actually faster than SIMD processing.
226 * Look back last 16 bytes buffer to find First Byte. At most three bytes need to look back. Otherwise we either happen to be at character boundray, or there are some errors we already detected.
227 * Validate string byte by byte starting from the First Byte.
228
229 ## Tests
230
231 It's necessary to design test cases to cover corner cases as more as possible.
232
233 ### Positive cases
234
235 1. Prepare correct characters
236 2. Validate correct characters
237 3. Validate long strings
238 * Round concatenate characters starting from first character to 1024 bytes
239 * Validate 1024 bytes string
240 * Shift 1 byte, validate 1025 bytes string
241 * Shift 2 bytes, Validate 1026 bytes string
242 * ...
243 * Shift 16 bytes, validate 1040 bytes string
244 4. Repeat step3, test buffer starting from second character
245 5. Repeat step3, test buffer starting from third character
246 6. ...
247
248 ### Negative cases
249
250 1. Prepare bad characters and bad strings
251 * Bad character
252 * Bad character cross 16 bytes boundary
253 * Bad character cross last 16 bytes and remaining bytes boundary
254 2. Test long strings
255 * Prepare correct long strings same as positive cases
256 * Append bad characters
257 * Shift one byte for each iteration
258 * Validate each shift
259
260 ## Code breakdown
261
262 Below table shows how 16 bytes input are processed step by step. See [range-neon.c](range-neon.c) for according code.
263
264 ![Range based UTF-8 validation algorithm](https://raw.githubusercontent.com/cyb70289/utf8/master/range.png)