MdeModulePkg BrotliLib: Fix the regression logic issue in loop
[mirror_edk2.git] / MdeModulePkg / Library / BrotliCustomDecompressLib / dec / context.h
CommitLineData
36ff6d80
SB
1/* Copyright 2013 Google Inc. All Rights Reserved.\r
2\r
3 Distributed under MIT license.\r
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
5*/\r
6\r
7/* Lookup table to map the previous two bytes to a context id.\r
8\r
9 There are four different context modeling modes defined here:\r
10 CONTEXT_LSB6: context id is the least significant 6 bits of the last byte,\r
11 CONTEXT_MSB6: context id is the most significant 6 bits of the last byte,\r
12 CONTEXT_UTF8: second-order context model tuned for UTF8-encoded text,\r
13 CONTEXT_SIGNED: second-order context model tuned for signed integers.\r
14\r
15 The context id for the UTF8 context model is calculated as follows. If p1\r
16 and p2 are the previous two bytes, we calculate the context as\r
17\r
18 context = kContextLookup[p1] | kContextLookup[p2 + 256].\r
19\r
20 If the previous two bytes are ASCII characters (i.e. < 128), this will be\r
21 equivalent to\r
22\r
23 context = 4 * context1(p1) + context2(p2),\r
24\r
25 where context1 is based on the previous byte in the following way:\r
26\r
27 0 : non-ASCII control\r
28 1 : \t, \n, \r\r
29 2 : space\r
30 3 : other punctuation\r
31 4 : " '\r
32 5 : %\r
33 6 : ( < [ {\r
34 7 : ) > ] }\r
35 8 : , ; :\r
36 9 : .\r
37 10 : =\r
38 11 : number\r
39 12 : upper-case vowel\r
40 13 : upper-case consonant\r
41 14 : lower-case vowel\r
42 15 : lower-case consonant\r
43\r
44 and context2 is based on the second last byte:\r
45\r
46 0 : control, space\r
47 1 : punctuation\r
48 2 : upper-case letter, number\r
49 3 : lower-case letter\r
50\r
51 If the last byte is ASCII, and the second last byte is not (in a valid UTF8\r
52 stream it will be a continuation byte, value between 128 and 191), the\r
53 context is the same as if the second last byte was an ASCII control or space.\r
54\r
55 If the last byte is a UTF8 lead byte (value >= 192), then the next byte will\r
56 be a continuation byte and the context id is 2 or 3 depending on the LSB of\r
57 the last byte and to a lesser extent on the second last byte if it is ASCII.\r
58\r
59 If the last byte is a UTF8 continuation byte, the second last byte can be:\r
60 - continuation byte: the next byte is probably ASCII or lead byte (assuming\r
61 4-byte UTF8 characters are rare) and the context id is 0 or 1.\r
62 - lead byte (192 - 207): next byte is ASCII or lead byte, context is 0 or 1\r
63 - lead byte (208 - 255): next byte is continuation byte, context is 2 or 3\r
64\r
65 The possible value combinations of the previous two bytes, the range of\r
66 context ids and the type of the next byte is summarized in the table below:\r
67\r
68 |--------\-----------------------------------------------------------------|\r
69 | \ Last byte |\r
70 | Second \---------------------------------------------------------------|\r
71 | last byte \ ASCII | cont. byte | lead byte |\r
72 | \ (0-127) | (128-191) | (192-) |\r
73 |=============|===================|=====================|==================|\r
74 | ASCII | next: ASCII/lead | not valid | next: cont. |\r
75 | (0-127) | context: 4 - 63 | | context: 2 - 3 |\r
76 |-------------|-------------------|---------------------|------------------|\r
77 | cont. byte | next: ASCII/lead | next: ASCII/lead | next: cont. |\r
78 | (128-191) | context: 4 - 63 | context: 0 - 1 | context: 2 - 3 |\r
79 |-------------|-------------------|---------------------|------------------|\r
80 | lead byte | not valid | next: ASCII/lead | not valid |\r
81 | (192-207) | | context: 0 - 1 | |\r
82 |-------------|-------------------|---------------------|------------------|\r
83 | lead byte | not valid | next: cont. | not valid |\r
84 | (208-) | | context: 2 - 3 | |\r
85 |-------------|-------------------|---------------------|------------------|\r
86\r
87 The context id for the signed context mode is calculated as:\r
88\r
89 context = (kContextLookup[512 + p1] << 3) | kContextLookup[512 + p2].\r
90\r
91 For any context modeling modes, the context ids can be calculated by |-ing\r
92 together two lookups from one table using context model dependent offsets:\r
93\r
94 context = kContextLookup[offset1 + p1] | kContextLookup[offset2 + p2].\r
95\r
96 where offset1 and offset2 are dependent on the context mode.\r
97*/\r
98\r
99#ifndef BROTLI_DEC_CONTEXT_H_\r
100#define BROTLI_DEC_CONTEXT_H_\r
101\r
102#include "../common/types.h"\r
103\r
104enum ContextType {\r
105 CONTEXT_LSB6 = 0,\r
106 CONTEXT_MSB6 = 1,\r
107 CONTEXT_UTF8 = 2,\r
108 CONTEXT_SIGNED = 3\r
109};\r
110\r
111/* Common context lookup table for all context modes. */\r
112static const uint8_t kContextLookup[1792] = {\r
113 /* CONTEXT_UTF8, last byte. */\r
114 /* ASCII range. */\r
115 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 0, 0, 4, 0, 0,\r
116 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
117 8, 12, 16, 12, 12, 20, 12, 16, 24, 28, 12, 12, 32, 12, 36, 12,\r
118 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 32, 32, 24, 40, 28, 12,\r
119 12, 48, 52, 52, 52, 48, 52, 52, 52, 48, 52, 52, 52, 52, 52, 48,\r
120 52, 52, 52, 52, 52, 48, 52, 52, 52, 52, 52, 24, 12, 28, 12, 12,\r
121 12, 56, 60, 60, 60, 56, 60, 60, 60, 56, 60, 60, 60, 60, 60, 56,\r
122 60, 60, 60, 60, 60, 56, 60, 60, 60, 60, 60, 24, 12, 28, 12, 0,\r
123 /* UTF8 continuation byte range. */\r
124 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,\r
125 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,\r
126 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,\r
127 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,\r
128 /* UTF8 lead byte range. */\r
129 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,\r
130 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,\r
131 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,\r
132 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,\r
133 /* CONTEXT_UTF8 second last byte. */\r
134 /* ASCII range. */\r
135 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
136 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
137 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\r
138 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1,\r
139 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\r
140 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,\r
141 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,\r
142 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 0,\r
143 /* UTF8 continuation byte range. */\r
144 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
145 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
146 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
147 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
148 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
149 /* UTF8 lead byte range. */\r
150 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
151 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\r
152 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\r
153 /* CONTEXT_SIGNED, second last byte. */\r
154 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\r
155 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\r
156 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\r
157 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\r
158 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,\r
159 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,\r
160 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,\r
161 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,\r
162 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,\r
163 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,\r
164 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,\r
165 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,\r
166 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,\r
167 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,\r
168 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,\r
169 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7,\r
170 /* CONTEXT_SIGNED, last byte, same as the above values shifted by 3 bits. */\r
171 0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,\r
172 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,\r
173 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,\r
174 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,\r
175 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,\r
176 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,\r
177 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,\r
178 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,\r
179 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,\r
180 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,\r
181 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,\r
182 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,\r
183 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,\r
184 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,\r
185 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,\r
186 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 56,\r
187 /* CONTEXT_LSB6, last byte. */\r
188 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,\r
189 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,\r
190 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,\r
191 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,\r
192 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,\r
193 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,\r
194 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,\r
195 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,\r
196 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,\r
197 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,\r
198 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,\r
199 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,\r
200 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,\r
201 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,\r
202 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,\r
203 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,\r
204 /* CONTEXT_MSB6, last byte. */\r
205 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,\r
206 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,\r
207 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,\r
208 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,\r
209 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,\r
210 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,\r
211 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,\r
212 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,\r
213 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,\r
214 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,\r
215 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,\r
216 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,\r
217 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,\r
218 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,\r
219 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,\r
220 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63,\r
221 /* CONTEXT_{M,L}SB6, second last byte, */\r
222 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
223 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
224 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
225 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
226 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
227 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
228 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
229 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
230 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
231 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
232 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
233 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
234 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
235 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
236 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
237 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\r
238};\r
239\r
240static const int kContextLookupOffsets[8] = {\r
241 /* CONTEXT_LSB6 */\r
242 1024, 1536,\r
243 /* CONTEXT_MSB6 */\r
244 1280, 1536,\r
245 /* CONTEXT_UTF8 */\r
246 0, 256,\r
247 /* CONTEXT_SIGNED */\r
248 768, 512,\r
249};\r
250\r
251#endif /* BROTLI_DEC_CONTEXT_H_ */\r