1 /*
2 Copyright 2016 Google Inc. All Rights Reserved.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15
16 Author: lode.vandevenne@gmail.com (Lode Vandevenne)
17 Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala)
18 */
19
20 /*
21 Utilities for using the lz77 symbols of the deflate spec.
22 */
23
24 #ifndef ZOPFLI_SYMBOLS_H_
25 #define ZOPFLI_SYMBOLS_H_
26
27 /* __has_builtin available in clang */
28 #ifdef __has_builtin
29 # if __has_builtin(__builtin_clz)
30 # define ZOPFLI_HAS_BUILTIN_CLZ
31 # endif
32 /* __builtin_clz available beginning with GCC 3.4 */
33 #elif __GNUC__ * 100 + __GNUC_MINOR__ >= 304
34 # define ZOPFLI_HAS_BUILTIN_CLZ
35 #endif
36
37 /* Gets the amount of extra bits for the given dist, cfr. the DEFLATE spec. */
ZopfliGetDistExtraBits(int dist)38 static int ZopfliGetDistExtraBits(int dist) {
39 #ifdef ZOPFLI_HAS_BUILTIN_CLZ
40 if (dist < 5) return 0;
41 return (31 ^ __builtin_clz(dist - 1)) - 1; /* log2(dist - 1) - 1 */
42 #else
43 if (dist < 5) return 0;
44 else if (dist < 9) return 1;
45 else if (dist < 17) return 2;
46 else if (dist < 33) return 3;
47 else if (dist < 65) return 4;
48 else if (dist < 129) return 5;
49 else if (dist < 257) return 6;
50 else if (dist < 513) return 7;
51 else if (dist < 1025) return 8;
52 else if (dist < 2049) return 9;
53 else if (dist < 4097) return 10;
54 else if (dist < 8193) return 11;
55 else if (dist < 16385) return 12;
56 else return 13;
57 #endif
58 }
59
60 /* Gets value of the extra bits for the given dist, cfr. the DEFLATE spec. */
ZopfliGetDistExtraBitsValue(int dist)61 static int ZopfliGetDistExtraBitsValue(int dist) {
62 #ifdef ZOPFLI_HAS_BUILTIN_CLZ
63 if (dist < 5) {
64 return 0;
65 } else {
66 int l = 31 ^ __builtin_clz(dist - 1); /* log2(dist - 1) */
67 return (dist - (1 + (1 << l))) & ((1 << (l - 1)) - 1);
68 }
69 #else
70 if (dist < 5) return 0;
71 else if (dist < 9) return (dist - 5) & 1;
72 else if (dist < 17) return (dist - 9) & 3;
73 else if (dist < 33) return (dist - 17) & 7;
74 else if (dist < 65) return (dist - 33) & 15;
75 else if (dist < 129) return (dist - 65) & 31;
76 else if (dist < 257) return (dist - 129) & 63;
77 else if (dist < 513) return (dist - 257) & 127;
78 else if (dist < 1025) return (dist - 513) & 255;
79 else if (dist < 2049) return (dist - 1025) & 511;
80 else if (dist < 4097) return (dist - 2049) & 1023;
81 else if (dist < 8193) return (dist - 4097) & 2047;
82 else if (dist < 16385) return (dist - 8193) & 4095;
83 else return (dist - 16385) & 8191;
84 #endif
85 }
86
87 /* Gets the symbol for the given dist, cfr. the DEFLATE spec. */
ZopfliGetDistSymbol(int dist)88 static int ZopfliGetDistSymbol(int dist) {
89 #ifdef ZOPFLI_HAS_BUILTIN_CLZ
90 if (dist < 5) {
91 return dist - 1;
92 } else {
93 int l = (31 ^ __builtin_clz(dist - 1)); /* log2(dist - 1) */
94 int r = ((dist - 1) >> (l - 1)) & 1;
95 return l * 2 + r;
96 }
97 #else
98 if (dist < 193) {
99 if (dist < 13) { /* dist 0..13. */
100 if (dist < 5) return dist - 1;
101 else if (dist < 7) return 4;
102 else if (dist < 9) return 5;
103 else return 6;
104 } else { /* dist 13..193. */
105 if (dist < 17) return 7;
106 else if (dist < 25) return 8;
107 else if (dist < 33) return 9;
108 else if (dist < 49) return 10;
109 else if (dist < 65) return 11;
110 else if (dist < 97) return 12;
111 else if (dist < 129) return 13;
112 else return 14;
113 }
114 } else {
115 if (dist < 2049) { /* dist 193..2049. */
116 if (dist < 257) return 15;
117 else if (dist < 385) return 16;
118 else if (dist < 513) return 17;
119 else if (dist < 769) return 18;
120 else if (dist < 1025) return 19;
121 else if (dist < 1537) return 20;
122 else return 21;
123 } else { /* dist 2049..32768. */
124 if (dist < 3073) return 22;
125 else if (dist < 4097) return 23;
126 else if (dist < 6145) return 24;
127 else if (dist < 8193) return 25;
128 else if (dist < 12289) return 26;
129 else if (dist < 16385) return 27;
130 else if (dist < 24577) return 28;
131 else return 29;
132 }
133 }
134 #endif
135 }
136
137 /* Gets the amount of extra bits for the given length, cfr. the DEFLATE spec. */
ZopfliGetLengthExtraBits(int l)138 static int ZopfliGetLengthExtraBits(int l) {
139 static const int table[259] = {
140 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
141 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
142 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
143 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
144 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
145 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
146 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
147 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
148 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
149 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
150 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
151 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
152 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
153 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
154 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
155 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0
156 };
157 return table[l];
158 }
159
160 /* Gets value of the extra bits for the given length, cfr. the DEFLATE spec. */
ZopfliGetLengthExtraBitsValue(int l)161 static int ZopfliGetLengthExtraBitsValue(int l) {
162 static const int table[259] = {
163 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 3, 0,
164 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5,
165 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6,
166 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
167 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2,
168 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
169 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
170 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
171 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6,
172 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
173 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
174 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 0
175 };
176 return table[l];
177 }
178
179 /*
180 Gets the symbol for the given length, cfr. the DEFLATE spec.
181 Returns the symbol in the range [257-285] (inclusive)
182 */
ZopfliGetLengthSymbol(int l)183 static int ZopfliGetLengthSymbol(int l) {
184 static const int table[259] = {
185 0, 0, 0, 257, 258, 259, 260, 261, 262, 263, 264,
186 265, 265, 266, 266, 267, 267, 268, 268,
187 269, 269, 269, 269, 270, 270, 270, 270,
188 271, 271, 271, 271, 272, 272, 272, 272,
189 273, 273, 273, 273, 273, 273, 273, 273,
190 274, 274, 274, 274, 274, 274, 274, 274,
191 275, 275, 275, 275, 275, 275, 275, 275,
192 276, 276, 276, 276, 276, 276, 276, 276,
193 277, 277, 277, 277, 277, 277, 277, 277,
194 277, 277, 277, 277, 277, 277, 277, 277,
195 278, 278, 278, 278, 278, 278, 278, 278,
196 278, 278, 278, 278, 278, 278, 278, 278,
197 279, 279, 279, 279, 279, 279, 279, 279,
198 279, 279, 279, 279, 279, 279, 279, 279,
199 280, 280, 280, 280, 280, 280, 280, 280,
200 280, 280, 280, 280, 280, 280, 280, 280,
201 281, 281, 281, 281, 281, 281, 281, 281,
202 281, 281, 281, 281, 281, 281, 281, 281,
203 281, 281, 281, 281, 281, 281, 281, 281,
204 281, 281, 281, 281, 281, 281, 281, 281,
205 282, 282, 282, 282, 282, 282, 282, 282,
206 282, 282, 282, 282, 282, 282, 282, 282,
207 282, 282, 282, 282, 282, 282, 282, 282,
208 282, 282, 282, 282, 282, 282, 282, 282,
209 283, 283, 283, 283, 283, 283, 283, 283,
210 283, 283, 283, 283, 283, 283, 283, 283,
211 283, 283, 283, 283, 283, 283, 283, 283,
212 283, 283, 283, 283, 283, 283, 283, 283,
213 284, 284, 284, 284, 284, 284, 284, 284,
214 284, 284, 284, 284, 284, 284, 284, 284,
215 284, 284, 284, 284, 284, 284, 284, 284,
216 284, 284, 284, 284, 284, 284, 284, 285
217 };
218 return table[l];
219 }
220
221 /* Gets the amount of extra bits for the given length symbol. */
ZopfliGetLengthSymbolExtraBits(int s)222 static int ZopfliGetLengthSymbolExtraBits(int s) {
223 static const int table[29] = {
224 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
225 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
226 };
227 return table[s - 257];
228 }
229
230 /* Gets the amount of extra bits for the given distance symbol. */
ZopfliGetDistSymbolExtraBits(int s)231 static int ZopfliGetDistSymbolExtraBits(int s) {
232 static const int table[30] = {
233 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
234 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
235 };
236 return table[s];
237 }
238
239 #endif /* ZOPFLI_SYMBOLS_H_ */
240