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 #include "symbols.h"
21 
22 /* __has_builtin available in clang */
23 #ifdef __has_builtin
24 # if __has_builtin(__builtin_clz)
25 #   define ZOPFLI_HAS_BUILTIN_CLZ
26 # endif
27 /* __builtin_clz available beginning with GCC 3.4 */
28 #elif __GNUC__ * 100 + __GNUC_MINOR__ >= 304
29 # define ZOPFLI_HAS_BUILTIN_CLZ
30 #endif
31 
ZopfliGetDistExtraBits(int dist)32 int ZopfliGetDistExtraBits(int dist) {
33 #ifdef ZOPFLI_HAS_BUILTIN_CLZ
34   if (dist < 5) return 0;
35   return (31 ^ __builtin_clz(dist - 1)) - 1; /* log2(dist - 1) - 1 */
36 #else
37   if (dist < 5) return 0;
38   else if (dist < 9) return 1;
39   else if (dist < 17) return 2;
40   else if (dist < 33) return 3;
41   else if (dist < 65) return 4;
42   else if (dist < 129) return 5;
43   else if (dist < 257) return 6;
44   else if (dist < 513) return 7;
45   else if (dist < 1025) return 8;
46   else if (dist < 2049) return 9;
47   else if (dist < 4097) return 10;
48   else if (dist < 8193) return 11;
49   else if (dist < 16385) return 12;
50   else return 13;
51 #endif
52 }
53 
ZopfliGetDistExtraBitsValue(int dist)54 int ZopfliGetDistExtraBitsValue(int dist) {
55 #ifdef ZOPFLI_HAS_BUILTIN_CLZ
56   if (dist < 5) {
57     return 0;
58   } else {
59     int l = 31 ^ __builtin_clz(dist - 1); /* log2(dist - 1) */
60     return (dist - (1 + (1 << l))) & ((1 << (l - 1)) - 1);
61   }
62 #else
63   if (dist < 5) return 0;
64   else if (dist < 9) return (dist - 5) & 1;
65   else if (dist < 17) return (dist - 9) & 3;
66   else if (dist < 33) return (dist - 17) & 7;
67   else if (dist < 65) return (dist - 33) & 15;
68   else if (dist < 129) return (dist - 65) & 31;
69   else if (dist < 257) return (dist - 129) & 63;
70   else if (dist < 513) return (dist - 257) & 127;
71   else if (dist < 1025) return (dist - 513) & 255;
72   else if (dist < 2049) return (dist - 1025) & 511;
73   else if (dist < 4097) return (dist - 2049) & 1023;
74   else if (dist < 8193) return (dist - 4097) & 2047;
75   else if (dist < 16385) return (dist - 8193) & 4095;
76   else return (dist - 16385) & 8191;
77 #endif
78 }
79 
ZopfliGetDistSymbol(int dist)80 int ZopfliGetDistSymbol(int dist) {
81 #ifdef ZOPFLI_HAS_BUILTIN_CLZ
82   if (dist < 5) {
83     return dist - 1;
84   } else {
85     int l = (31 ^ __builtin_clz(dist - 1)); /* log2(dist - 1) */
86     int r = ((dist - 1) >> (l - 1)) & 1;
87     return l * 2 + r;
88   }
89 #else
90   if (dist < 193) {
91     if (dist < 13) {  /* dist 0..13. */
92       if (dist < 5) return dist - 1;
93       else if (dist < 7) return 4;
94       else if (dist < 9) return 5;
95       else return 6;
96     } else {  /* dist 13..193. */
97       if (dist < 17) return 7;
98       else if (dist < 25) return 8;
99       else if (dist < 33) return 9;
100       else if (dist < 49) return 10;
101       else if (dist < 65) return 11;
102       else if (dist < 97) return 12;
103       else if (dist < 129) return 13;
104       else return 14;
105     }
106   } else {
107     if (dist < 2049) {  /* dist 193..2049. */
108       if (dist < 257) return 15;
109       else if (dist < 385) return 16;
110       else if (dist < 513) return 17;
111       else if (dist < 769) return 18;
112       else if (dist < 1025) return 19;
113       else if (dist < 1537) return 20;
114       else return 21;
115     } else {  /* dist 2049..32768. */
116       if (dist < 3073) return 22;
117       else if (dist < 4097) return 23;
118       else if (dist < 6145) return 24;
119       else if (dist < 8193) return 25;
120       else if (dist < 12289) return 26;
121       else if (dist < 16385) return 27;
122       else if (dist < 24577) return 28;
123       else return 29;
124     }
125   }
126 #endif
127 }
128 
ZopfliGetLengthExtraBits(int l)129 int ZopfliGetLengthExtraBits(int l) {
130   static const int table[259] = {
131     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
132     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
133     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
134     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
135     4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
136     4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
137     4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
138     4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
139     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
140     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
141     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
142     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
143     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
144     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
145     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
146     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0
147   };
148   return table[l];
149 }
150 
ZopfliGetLengthExtraBitsValue(int l)151 int ZopfliGetLengthExtraBitsValue(int l) {
152   static const int table[259] = {
153     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 3, 0,
154     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,
155     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,
156     7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
157     13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2,
158     3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
159     10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
160     29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
161     18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6,
162     7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
163     27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
164     16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 0
165   };
166   return table[l];
167 }
168 
ZopfliGetLengthSymbol(int l)169 int ZopfliGetLengthSymbol(int l) {
170   static const int table[259] = {
171     0, 0, 0, 257, 258, 259, 260, 261, 262, 263, 264,
172     265, 265, 266, 266, 267, 267, 268, 268,
173     269, 269, 269, 269, 270, 270, 270, 270,
174     271, 271, 271, 271, 272, 272, 272, 272,
175     273, 273, 273, 273, 273, 273, 273, 273,
176     274, 274, 274, 274, 274, 274, 274, 274,
177     275, 275, 275, 275, 275, 275, 275, 275,
178     276, 276, 276, 276, 276, 276, 276, 276,
179     277, 277, 277, 277, 277, 277, 277, 277,
180     277, 277, 277, 277, 277, 277, 277, 277,
181     278, 278, 278, 278, 278, 278, 278, 278,
182     278, 278, 278, 278, 278, 278, 278, 278,
183     279, 279, 279, 279, 279, 279, 279, 279,
184     279, 279, 279, 279, 279, 279, 279, 279,
185     280, 280, 280, 280, 280, 280, 280, 280,
186     280, 280, 280, 280, 280, 280, 280, 280,
187     281, 281, 281, 281, 281, 281, 281, 281,
188     281, 281, 281, 281, 281, 281, 281, 281,
189     281, 281, 281, 281, 281, 281, 281, 281,
190     281, 281, 281, 281, 281, 281, 281, 281,
191     282, 282, 282, 282, 282, 282, 282, 282,
192     282, 282, 282, 282, 282, 282, 282, 282,
193     282, 282, 282, 282, 282, 282, 282, 282,
194     282, 282, 282, 282, 282, 282, 282, 282,
195     283, 283, 283, 283, 283, 283, 283, 283,
196     283, 283, 283, 283, 283, 283, 283, 283,
197     283, 283, 283, 283, 283, 283, 283, 283,
198     283, 283, 283, 283, 283, 283, 283, 283,
199     284, 284, 284, 284, 284, 284, 284, 284,
200     284, 284, 284, 284, 284, 284, 284, 284,
201     284, 284, 284, 284, 284, 284, 284, 284,
202     284, 284, 284, 284, 284, 284, 284, 285
203   };
204   return table[l];
205 }
206 
ZopfliGetLengthSymbolExtraBits(int s)207 int ZopfliGetLengthSymbolExtraBits(int s) {
208   static const int table[29] = {
209     0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
210     3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
211   };
212   return table[s - 257];
213 }
214 
ZopfliGetDistSymbolExtraBits(int s)215 int ZopfliGetDistSymbolExtraBits(int s) {
216   static const int table[30] = {
217     0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
218     9, 9, 10, 10, 11, 11, 12, 12, 13, 13
219   };
220   return table[s];
221 }
222