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