Zoltan Szabadka | c66e4e3 | 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 for encoding of integers into prefix codes the amount of extra |
| 16 | // bits, and the actual values of the extra bits. |
| 17 | |
| 18 | #ifndef BROTLI_ENC_PREFIX_H_ |
| 19 | #define BROTLI_ENC_PREFIX_H_ |
| 20 | |
| 21 | #include <stdint.h> |
Zoltan Szabadka | b4f39bf | 2014-10-28 13:25:22 +0100 | [diff] [blame] | 22 | #include "./fast_log.h" |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 23 | |
| 24 | namespace brotli { |
| 25 | |
| 26 | static const int kNumInsertLenPrefixes = 24; |
| 27 | static const int kNumCopyLenPrefixes = 24; |
| 28 | static const int kNumCommandPrefixes = 704; |
| 29 | static const int kNumBlockLenPrefixes = 26; |
| 30 | static const int kNumDistanceShortCodes = 16; |
| 31 | static const int kNumDistancePrefixes = 520; |
| 32 | |
Zoltan Szabadka | 467e6ee | 2014-10-28 11:53:52 +0100 | [diff] [blame] | 33 | // Represents the range of values belonging to a prefix code: |
| 34 | // [offset, offset + 2^nbits) |
| 35 | struct PrefixCodeRange { |
| 36 | int offset; |
| 37 | int nbits; |
| 38 | }; |
| 39 | |
Zoltan Szabadka | 467e6ee | 2014-10-28 11:53:52 +0100 | [diff] [blame] | 40 | static const PrefixCodeRange kBlockLengthPrefixCode[kNumBlockLenPrefixes] = { |
| 41 | { 1, 2}, { 5, 2}, { 9, 2}, { 13, 2}, |
| 42 | { 17, 3}, { 25, 3}, { 33, 3}, { 41, 3}, |
| 43 | { 49, 4}, { 65, 4}, { 81, 4}, { 97, 4}, |
| 44 | { 113, 5}, { 145, 5}, { 177, 5}, { 209, 5}, |
| 45 | { 241, 6}, { 305, 6}, { 369, 7}, { 497, 8}, |
| 46 | { 753, 9}, { 1265, 10}, {2289, 11}, {4337, 12}, |
| 47 | {8433, 13}, {16625, 24} |
| 48 | }; |
| 49 | |
| 50 | inline void GetBlockLengthPrefixCode(int len, |
| 51 | int* code, int* n_extra, int* extra) { |
| 52 | *code = 0; |
| 53 | while (*code < 25 && len >= kBlockLengthPrefixCode[*code + 1].offset) { |
| 54 | ++(*code); |
| 55 | } |
| 56 | *n_extra = kBlockLengthPrefixCode[*code].nbits; |
| 57 | *extra = len - kBlockLengthPrefixCode[*code].offset; |
| 58 | } |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 59 | |
Zoltan Szabadka | b4f39bf | 2014-10-28 13:25:22 +0100 | [diff] [blame] | 60 | inline void PrefixEncodeCopyDistance(int distance_code, |
| 61 | int num_direct_codes, |
| 62 | int postfix_bits, |
| 63 | uint16_t* code, |
| 64 | uint32_t* extra_bits) { |
Zoltan Szabadka | b4f39bf | 2014-10-28 13:25:22 +0100 | [diff] [blame] | 65 | if (distance_code < kNumDistanceShortCodes + num_direct_codes) { |
| 66 | *code = distance_code; |
| 67 | *extra_bits = 0; |
| 68 | return; |
| 69 | } |
| 70 | distance_code -= kNumDistanceShortCodes + num_direct_codes; |
| 71 | distance_code += (1 << (postfix_bits + 2)); |
| 72 | int bucket = Log2Floor(distance_code) - 1; |
| 73 | int postfix_mask = (1 << postfix_bits) - 1; |
| 74 | int postfix = distance_code & postfix_mask; |
| 75 | int prefix = (distance_code >> bucket) & 1; |
| 76 | int offset = (2 + prefix) << bucket; |
| 77 | int nbits = bucket - postfix_bits; |
| 78 | *code = kNumDistanceShortCodes + num_direct_codes + |
| 79 | ((2 * (nbits - 1) + prefix) << postfix_bits) + postfix; |
| 80 | *extra_bits = (nbits << 24) | ((distance_code - offset) >> postfix_bits); |
| 81 | } |
| 82 | |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 83 | } // namespace brotli |
| 84 | |
| 85 | #endif // BROTLI_ENC_PREFIX_H_ |