1 // Copyright 2013 Google Inc. All Rights Reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // Functions to map previous bytes into a context id. 16 17 #ifndef BROTLI_ENC_CONTEXT_H_ 18 #define BROTLI_ENC_CONTEXT_H_ 19 20 #include <stdint.h> 21 22 namespace brotli { 23 24 // Second-order context lookup table for UTF8 byte streams. 25 // 26 // If p1 and p2 are the previous two bytes, we calcualte the context as 27 // 28 // context = kUTF8ContextLookup[p1] | kUTF8ContextLookup[p2 + 256]. 29 // 30 // If the previous two bytes are ASCII characters (i.e. < 128), this will be 31 // equivalent to 32 // 33 // context = 4 * context1(p1) + context2(p2), 34 // 35 // where context1 is based on the previous byte in the following way: 36 // 37 // 0 : non-ASCII control 38 // 1 : \t, \n, \r 39 // 2 : space 40 // 3 : other punctuation 41 // 4 : " ' 42 // 5 : % 43 // 6 : ( < [ { 44 // 7 : ) > ] } 45 // 8 : , ; : 46 // 9 : . 47 // 10 : = 48 // 11 : number 49 // 12 : upper-case vowel 50 // 13 : upper-case consonant 51 // 14 : lower-case vowel 52 // 15 : lower-case consonant 53 // 54 // and context2 is based on the second last byte: 55 // 56 // 0 : control, space 57 // 1 : punctuation 58 // 2 : upper-case letter, number 59 // 3 : lower-case letter 60 // 61 // If the last byte is ASCII, and the second last byte is not (in a valid UTF8 62 // stream it will be a continuation byte, value between 128 and 191), the 63 // context is the same as if the second last byte was an ASCII control or space. 64 // 65 // If the last byte is a UTF8 lead byte (value >= 192), then the next byte will 66 // be a continuation byte and the context id is 2 or 3 depending on the LSB of 67 // the last byte and to a lesser extent on the second last byte if it is ASCII. 68 // 69 // If the last byte is a UTF8 continuation byte, the second last byte can be: 70 // - continuation byte: the next byte is probably ASCII or lead byte (assuming 71 // 4-byte UTF8 characters are rare) and the context id is 0 or 1. 72 // - lead byte (192 - 207): next byte is ASCII or lead byte, context is 0 or 1 73 // - lead byte (208 - 255): next byte is continuation byte, context is 2 or 3 74 // 75 // The possible value combinations of the previous two bytes, the range of 76 // context ids and the type of the next byte is summarized in the table below: 77 // 78 // |--------\-----------------------------------------------------------------| 79 // | \ Last byte | 80 // | Second \---------------------------------------------------------------| 81 // | last byte \ ASCII | cont. byte | lead byte | 82 // | \ (0-127) | (128-191) | (192-) | 83 // |=============|===================|=====================|==================| 84 // | ASCII | next: ASCII/lead | not valid | next: cont. | 85 // | (0-127) | context: 4 - 63 | | context: 2 - 3 | 86 // |-------------|-------------------|---------------------|------------------| 87 // | cont. byte | next: ASCII/lead | next: ASCII/lead | next: cont. | 88 // | (128-191) | context: 4 - 63 | context: 0 - 1 | context: 2 - 3 | 89 // |-------------|-------------------|---------------------|------------------| 90 // | lead byte | not valid | next: ASCII/lead | not valid | 91 // | (192-207) | | context: 0 - 1 | | 92 // |-------------|-------------------|---------------------|------------------| 93 // | lead byte | not valid | next: cont. | not valid | 94 // | (208-) | | context: 2 - 3 | | 95 // |-------------|-------------------|---------------------|------------------| 96 static const uint8_t kUTF8ContextLookup[512] = { 97 // Last byte. 98 // 99 // ASCII range. 100 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 0, 0, 4, 0, 0, 101 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 102 8, 12, 16, 12, 12, 20, 12, 16, 24, 28, 12, 12, 32, 12, 36, 12, 103 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 32, 32, 24, 40, 28, 12, 104 12, 48, 52, 52, 52, 48, 52, 52, 52, 48, 52, 52, 52, 52, 52, 48, 105 52, 52, 52, 52, 52, 48, 52, 52, 52, 52, 52, 24, 12, 28, 12, 12, 106 12, 56, 60, 60, 60, 56, 60, 60, 60, 56, 60, 60, 60, 60, 60, 56, 107 60, 60, 60, 60, 60, 56, 60, 60, 60, 60, 60, 24, 12, 28, 12, 0, 108 // UTF8 continuation byte range. 109 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 110 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 111 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 112 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 113 // UTF8 lead byte range. 114 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 115 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 116 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 117 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 118 // Second last byte. 119 // 120 // ASCII range. 121 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 122 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 123 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 124 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 125 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 126 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 127 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 128 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 0, 129 // UTF8 continuation byte range. 130 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 131 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 132 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 133 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 134 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 135 // UTF8 lead byte range. 136 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 137 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 138 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 139 }; 140 141 // Context lookup table for small signed integers. 142 static const int kSigned3BitContextLookup[] = { 143 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 144 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 145 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 146 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 147 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 148 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 149 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 150 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 151 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 152 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 153 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 154 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 155 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 156 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 157 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 158 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 159 }; 160 161 enum ContextType { 162 CONTEXT_LSB6 = 0, 163 CONTEXT_MSB6 = 1, 164 CONTEXT_UTF8 = 2, 165 CONTEXT_SIGNED = 3 166 }; 167 168 static inline uint8_t Context(uint8_t p1, uint8_t p2, int mode) { 169 switch (mode) { 170 case CONTEXT_LSB6: 171 return p1 & 0x3f; 172 case CONTEXT_MSB6: 173 return p1 >> 2; 174 case CONTEXT_UTF8: 175 return kUTF8ContextLookup[p1] | kUTF8ContextLookup[p2 + 256]; 176 case CONTEXT_SIGNED: 177 return (kSigned3BitContextLookup[p1] << 3) + kSigned3BitContextLookup[p2]; 178 default: 179 return 0; 180 } 181 } 182 183 } // namespace brotli 184 185 #endif // BROTLI_ENC_CONTEXT_H_ 186
