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 | // This class models a sequence of literals and a backward reference copy. |
| 16 | |
| 17 | #ifndef BROTLI_ENC_COMMAND_H_ |
| 18 | #define BROTLI_ENC_COMMAND_H_ |
| 19 | |
| 20 | #include <stdint.h> |
Zoltan Szabadka | b4f39bf | 2014-10-28 13:25:22 +0100 | [diff] [blame] | 21 | #include "./fast_log.h" |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 22 | |
| 23 | namespace brotli { |
| 24 | |
Zoltan Szabadka | b4f39bf | 2014-10-28 13:25:22 +0100 | [diff] [blame] | 25 | static inline void GetDistCode(int distance_code, |
| 26 | uint16_t* code, uint32_t* extra) { |
Zoltan Szabadka | b4f39bf | 2014-10-28 13:25:22 +0100 | [diff] [blame] | 27 | if (distance_code < 16) { |
| 28 | *code = distance_code; |
| 29 | *extra = 0; |
| 30 | } else { |
| 31 | distance_code -= 12; |
| 32 | int numextra = Log2FloorNonZero(distance_code) - 1; |
| 33 | int prefix = distance_code >> numextra; |
| 34 | *code = 12 + 2 * numextra + prefix; |
| 35 | *extra = (numextra << 24) | (distance_code - (prefix << numextra)); |
| 36 | } |
| 37 | } |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 38 | |
Zoltan Szabadka | b4f39bf | 2014-10-28 13:25:22 +0100 | [diff] [blame] | 39 | static int insbase[] = { 0, 1, 2, 3, 4, 5, 6, 8, 10, 14, 18, 26, 34, 50, 66, |
| 40 | 98, 130, 194, 322, 578, 1090, 2114, 6210, 22594 }; |
| 41 | static int insextra[] = { 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, |
| 42 | 5, 6, 7, 8, 9, 10, 12, 14, 24 }; |
| 43 | static int copybase[] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 18, 22, 30, 38, |
| 44 | 54, 70, 102, 134, 198, 326, 582, 1094, 2118 }; |
| 45 | static int copyextra[] = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, |
| 46 | 4, 5, 5, 6, 7, 8, 9, 10, 24 }; |
| 47 | |
| 48 | static inline int GetInsertLengthCode(int insertlen) { |
| 49 | if (insertlen < 6) { |
| 50 | return insertlen; |
| 51 | } else if (insertlen < 130) { |
| 52 | insertlen -= 2; |
| 53 | int nbits = Log2FloorNonZero(insertlen) - 1; |
| 54 | return (nbits << 1) + (insertlen >> nbits) + 2; |
| 55 | } else if (insertlen < 2114) { |
| 56 | return Log2FloorNonZero(insertlen - 66) + 10; |
| 57 | } else if (insertlen < 6210) { |
| 58 | return 21; |
| 59 | } else if (insertlen < 22594) { |
| 60 | return 22; |
| 61 | } else { |
| 62 | return 23; |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | static inline int GetCopyLengthCode(int copylen) { |
| 67 | if (copylen < 10) { |
| 68 | return copylen - 2; |
| 69 | } else if (copylen < 134) { |
| 70 | copylen -= 6; |
| 71 | int nbits = Log2FloorNonZero(copylen) - 1; |
| 72 | return (nbits << 1) + (copylen >> nbits) + 4; |
| 73 | } else if (copylen < 2118) { |
| 74 | return Log2FloorNonZero(copylen - 70) + 12; |
| 75 | } else { |
| 76 | return 23; |
| 77 | } |
| 78 | } |
| 79 | |
| 80 | static inline int CombineLengthCodes( |
| 81 | int inscode, int copycode, int distancecode) { |
| 82 | int bits64 = (copycode & 0x7u) | ((inscode & 0x7u) << 3); |
| 83 | if (distancecode == 0 && inscode < 8 && copycode < 16) { |
| 84 | return (copycode < 8) ? bits64 : (bits64 | 64); |
| 85 | } else { |
| 86 | // "To convert an insert-and-copy length code to an insert length code and |
| 87 | // a copy length code, the following table can be used" |
| 88 | static const int cells[9] = { 2, 3, 6, 4, 5, 8, 7, 9, 10 }; |
| 89 | return (cells[(copycode >> 3) + 3 * (inscode >> 3)] << 6) | bits64; |
| 90 | } |
| 91 | } |
| 92 | |
| 93 | static inline void GetLengthCode(int insertlen, int copylen, int distancecode, |
| 94 | uint16_t* code, uint64_t* extra) { |
| 95 | int inscode = GetInsertLengthCode(insertlen); |
| 96 | int copycode = GetCopyLengthCode(copylen); |
| 97 | uint64_t insnumextra = insextra[inscode]; |
| 98 | uint64_t numextra = insnumextra + copyextra[copycode]; |
| 99 | uint64_t insextraval = insertlen - insbase[inscode]; |
| 100 | uint64_t copyextraval = copylen - copybase[copycode]; |
| 101 | *code = CombineLengthCodes(inscode, copycode, distancecode); |
| 102 | *extra = (numextra << 48) | (copyextraval << insnumextra) | insextraval; |
| 103 | } |
| 104 | |
| 105 | struct Command { |
| 106 | Command() {} |
| 107 | |
Zoltan Szabadka | 12eb9bf | 2015-05-07 17:40:00 +0200 | [diff] [blame^] | 108 | // distance_code is e.g. 0 for same-as-last short code, or 16 for offset 1. |
Zoltan Szabadka | b4f39bf | 2014-10-28 13:25:22 +0100 | [diff] [blame] | 109 | Command(int insertlen, int copylen, int copylen_code, int distance_code) |
| 110 | : insert_len_(insertlen), copy_len_(copylen) { |
| 111 | GetDistCode(distance_code, &dist_prefix_, &dist_extra_); |
| 112 | GetLengthCode(insertlen, copylen_code, dist_prefix_, |
| 113 | &cmd_prefix_, &cmd_extra_); |
| 114 | } |
| 115 | |
| 116 | Command(int insertlen) |
| 117 | : insert_len_(insertlen), copy_len_(0), dist_prefix_(16), dist_extra_(0) { |
| 118 | GetLengthCode(insertlen, 4, dist_prefix_, &cmd_prefix_, &cmd_extra_); |
| 119 | } |
| 120 | |
| 121 | int DistanceCode() const { |
| 122 | if (dist_prefix_ < 16) { |
Zoltan Szabadka | 12eb9bf | 2015-05-07 17:40:00 +0200 | [diff] [blame^] | 123 | return dist_prefix_; |
Zoltan Szabadka | b4f39bf | 2014-10-28 13:25:22 +0100 | [diff] [blame] | 124 | } |
| 125 | int nbits = dist_extra_ >> 24; |
| 126 | int extra = dist_extra_ & 0xffffff; |
| 127 | int prefix = dist_prefix_ - 12 - 2 * nbits; |
Zoltan Szabadka | 12eb9bf | 2015-05-07 17:40:00 +0200 | [diff] [blame^] | 128 | return (prefix << nbits) + extra + 12; |
Zoltan Szabadka | b4f39bf | 2014-10-28 13:25:22 +0100 | [diff] [blame] | 129 | } |
| 130 | |
| 131 | int DistanceContext() const { |
| 132 | int r = cmd_prefix_ >> 6; |
| 133 | int c = cmd_prefix_ & 7; |
| 134 | if ((r == 0 || r == 2 || r == 4 || r == 7) && (c <= 2)) { |
| 135 | return c; |
| 136 | } |
| 137 | return 3; |
| 138 | } |
| 139 | |
| 140 | int insert_len_; |
| 141 | int copy_len_; |
| 142 | uint16_t cmd_prefix_; |
| 143 | uint16_t dist_prefix_; |
| 144 | uint64_t cmd_extra_; |
| 145 | uint32_t dist_extra_; |
Zoltan Szabadka | c66e4e3 | 2013-10-23 13:06:13 +0200 | [diff] [blame] | 146 | }; |
| 147 | |
| 148 | } // namespace brotli |
| 149 | |
| 150 | #endif // BROTLI_ENC_COMMAND_H_ |