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 #include "./prefix.h"
19
20 #include "./fast_log.h"
21
22 namespace brotli {
23
24 // Represents the range of values belonging to a prefix code:
25 // [offset, offset + 2^nbits)
26 struct PrefixCodeRange {
27 int offset;
28 int nbits;
29 };
30
31 static const PrefixCodeRange kBlockLengthPrefixCode[kNumBlockLenPrefixes] = {
32 { 1, 2}, { 5, 2}, { 9, 2}, { 13, 2},
33 { 17, 3}, { 25, 3}, { 33, 3}, { 41, 3},
34 { 49, 4}, { 65, 4}, { 81, 4}, { 97, 4},
35 { 113, 5}, { 145, 5}, { 177, 5}, { 209, 5},
36 { 241, 6}, { 305, 6}, { 369, 7}, { 497, 8},
37 { 753, 9}, { 1265, 10}, {2289, 11}, {4337, 12},
38 {8433, 13}, {16625, 24}
39 };
40
41 static const PrefixCodeRange kInsertLengthPrefixCode[kNumInsertLenPrefixes] = {
42 { 0, 0}, { 1, 0}, { 2, 0}, { 3, 0},
43 { 4, 0}, { 5, 0}, { 6, 1}, { 8, 1},
44 { 10, 2}, { 14, 2}, { 18, 3}, { 26, 3},
45 { 34, 4}, { 50, 4}, { 66, 5}, { 98, 5},
46 { 130, 6}, { 194, 7}, { 322, 8}, { 578, 9},
47 {1090, 10}, {2114, 12}, {6210, 14}, {22594, 24},
48 };
49
50 static const PrefixCodeRange kCopyLengthPrefixCode[kNumCopyLenPrefixes] = {
51 { 2, 0}, { 3, 0}, { 4, 0}, { 5, 0},
52 { 6, 0}, { 7, 0}, { 8, 0}, { 9, 0},
53 { 10, 1}, { 12, 1}, { 14, 2}, { 18, 2},
54 { 22, 3}, { 30, 3}, { 38, 4}, { 54, 4},
55 { 70, 5}, { 102, 5}, { 134, 6}, { 198, 7},
56 {326, 8}, { 582, 9}, {1094, 10}, {2118, 24},
57 };
58
59 static const int kInsertAndCopyRangeLut[9] = {
60 0, 1, 4, 2, 3, 6, 5, 7, 8,
61 };
62
63 static const int kInsertRangeLut[9] = {
64 0, 0, 1, 1, 0, 2, 1, 2, 2,
65 };
66
67 static const int kCopyRangeLut[9] = {
68 0, 1, 0, 1, 2, 0, 2, 1, 2,
69 };
70
InsertLengthPrefix(int length)71 int InsertLengthPrefix(int length) {
72 for (int i = 0; i < kNumInsertLenPrefixes; ++i) {
73 const PrefixCodeRange& range = kInsertLengthPrefixCode[i];
74 if (length >= range.offset && length < range.offset + (1 << range.nbits)) {
75 return i;
76 }
77 }
78 return -1;
79 }
80
CopyLengthPrefix(int length)81 int CopyLengthPrefix(int length) {
82 for (int i = 0; i < kNumCopyLenPrefixes; ++i) {
83 const PrefixCodeRange& range = kCopyLengthPrefixCode[i];
84 if (length >= range.offset && length < range.offset + (1 << range.nbits)) {
85 return i;
86 }
87 }
88 return -1;
89 }
90
CommandPrefix(int insert_length,int copy_length)91 int CommandPrefix(int insert_length, int copy_length) {
92 if (copy_length == 0) {
93 copy_length = 4;
94 }
95 int insert_prefix = InsertLengthPrefix(insert_length);
96 int copy_prefix = CopyLengthPrefix(copy_length);
97 int range_idx = 3 * (insert_prefix >> 3) + (copy_prefix >> 3);
98 return ((kInsertAndCopyRangeLut[range_idx] << 6) +
99 ((insert_prefix & 7) << 3) + (copy_prefix & 7));
100 }
101
InsertLengthExtraBits(int code)102 int InsertLengthExtraBits(int code) {
103 int insert_code = (kInsertRangeLut[code >> 6] << 3) + ((code >> 3) & 7);
104 return kInsertLengthPrefixCode[insert_code].nbits;
105 }
106
InsertLengthOffset(int code)107 int InsertLengthOffset(int code) {
108 int insert_code = (kInsertRangeLut[code >> 6] << 3) + ((code >> 3) & 7);
109 return kInsertLengthPrefixCode[insert_code].offset;
110 }
111
CopyLengthExtraBits(int code)112 int CopyLengthExtraBits(int code) {
113 int copy_code = (kCopyRangeLut[code >> 6] << 3) + (code & 7);
114 return kCopyLengthPrefixCode[copy_code].nbits;
115 }
116
CopyLengthOffset(int code)117 int CopyLengthOffset(int code) {
118 int copy_code = (kCopyRangeLut[code >> 6] << 3) + (code & 7);
119 return kCopyLengthPrefixCode[copy_code].offset;
120 }
121
PrefixEncodeCopyDistance(int distance_code,int num_direct_codes,int postfix_bits,uint16_t * code,int * nbits,uint32_t * extra_bits)122 void PrefixEncodeCopyDistance(int distance_code,
123 int num_direct_codes,
124 int postfix_bits,
125 uint16_t* code,
126 int* nbits,
127 uint32_t* extra_bits) {
128 distance_code -= 1;
129 if (distance_code < kNumDistanceShortCodes + num_direct_codes) {
130 *code = distance_code;
131 *nbits = 0;
132 *extra_bits = 0;
133 return;
134 }
135 distance_code -= kNumDistanceShortCodes + num_direct_codes;
136 distance_code += (1 << (postfix_bits + 2));
137 int bucket = Log2Floor(distance_code) - 1;
138 int postfix_mask = (1 << postfix_bits) - 1;
139 int postfix = distance_code & postfix_mask;
140 int prefix = (distance_code >> bucket) & 1;
141 int offset = (2 + prefix) << bucket;
142 *nbits = bucket - postfix_bits;
143 *code = kNumDistanceShortCodes + num_direct_codes +
144 ((2 * (*nbits - 1) + prefix) << postfix_bits) + postfix;
145 *extra_bits = (distance_code - offset) >> postfix_bits;
146 }
147
BlockLengthPrefix(int length)148 int BlockLengthPrefix(int length) {
149 for (int i = 0; i < kNumBlockLenPrefixes; ++i) {
150 const PrefixCodeRange& range = kBlockLengthPrefixCode[i];
151 if (length >= range.offset && length < range.offset + (1 << range.nbits)) {
152 return i;
153 }
154 }
155 return -1;
156 }
157
BlockLengthExtraBits(int length_code)158 int BlockLengthExtraBits(int length_code) {
159 return kBlockLengthPrefixCode[length_code].nbits;
160 }
161
BlockLengthOffset(int length_code)162 int BlockLengthOffset(int length_code) {
163 return kBlockLengthPrefixCode[length_code].offset;
164 }
165
166 } // namespace brotli
167