| | 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 |
| | 104 | enum 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 |
| | 112 | static 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 |
| | 240 | static 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 |
projects / mirror_edk2.git / blame_incremental