Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 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 | |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 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, |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 123 | 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 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, |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 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, |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 139 | }; |
| 140 | |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 141 | // Context lookup table for small signed integers. |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 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 | |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 161 | enum ContextType { |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 162 | CONTEXT_LSB6 = 0, |
| 163 | CONTEXT_MSB6 = 1, |
| 164 | CONTEXT_UTF8 = 2, |
| 165 | CONTEXT_SIGNED = 3 |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 166 | }; |
| 167 | |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 168 | static inline uint8_t Context(uint8_t p1, uint8_t p2, int mode) { |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 169 | switch (mode) { |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 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]; |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 178 | default: |
Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 179 | return 0; |
Zoltan Szabadka | 79e99af | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 180 | } |
| 181 | } |
| 182 | |
| 183 | } // namespace brotli |
| 184 | |
| 185 | #endif // BROTLI_ENC_CONTEXT_H_ |