1/*
2Copyright 2011 Google Inc. All Rights Reserved.
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8    http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15
16Author: lode.vandevenne@gmail.com (Lode Vandevenne)
17Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala)
18*/
19
20#include "util.h"
21
22#include "zopfli.h"
23
24#include <assert.h>
25#include <stdio.h>
26#include <stdlib.h>
27
28int ZopfliGetDistExtraBits(int dist) {
29#ifdef __GNUC__
30  if (dist < 5) return 0;
31  return (31 ^ __builtin_clz(dist - 1)) - 1; /* log2(dist - 1) - 1 */
32#else
33  if (dist < 5) return 0;
34  else if (dist < 9) return 1;
35  else if (dist < 17) return 2;
36  else if (dist < 33) return 3;
37  else if (dist < 65) return 4;
38  else if (dist < 129) return 5;
39  else if (dist < 257) return 6;
40  else if (dist < 513) return 7;
41  else if (dist < 1025) return 8;
42  else if (dist < 2049) return 9;
43  else if (dist < 4097) return 10;
44  else if (dist < 8193) return 11;
45  else if (dist < 16385) return 12;
46  else return 13;
47#endif
48}
49
50int ZopfliGetDistExtraBitsValue(int dist) {
51#ifdef __GNUC__
52  if (dist < 5) {
53    return 0;
54  } else {
55    int l = 31 ^ __builtin_clz(dist - 1); /* log2(dist - 1) */
56    return (dist - (1 + (1 << l))) & ((1 << (l - 1)) - 1);
57  }
58#else
59  if (dist < 5) return 0;
60  else if (dist < 9) return (dist - 5) & 1;
61  else if (dist < 17) return (dist - 9) & 3;
62  else if (dist < 33) return (dist - 17) & 7;
63  else if (dist < 65) return (dist - 33) & 15;
64  else if (dist < 129) return (dist - 65) & 31;
65  else if (dist < 257) return (dist - 129) & 63;
66  else if (dist < 513) return (dist - 257) & 127;
67  else if (dist < 1025) return (dist - 513) & 255;
68  else if (dist < 2049) return (dist - 1025) & 511;
69  else if (dist < 4097) return (dist - 2049) & 1023;
70  else if (dist < 8193) return (dist - 4097) & 2047;
71  else if (dist < 16385) return (dist - 8193) & 4095;
72  else return (dist - 16385) & 8191;
73#endif
74}
75
76int ZopfliGetDistSymbol(int dist) {
77#ifdef __GNUC__
78  if (dist < 5) {
79    return dist - 1;
80  } else {
81    int l = (31 ^ __builtin_clz(dist - 1)); /* log2(dist - 1) */
82    int r = ((dist - 1) >> (l - 1)) & 1;
83    return l * 2 + r;
84  }
85#else
86  if (dist < 193) {
87    if (dist < 13) {  /* dist 0..13. */
88      if (dist < 5) return dist - 1;
89      else if (dist < 7) return 4;
90      else if (dist < 9) return 5;
91      else return 6;
92    } else {  /* dist 13..193. */
93      if (dist < 17) return 7;
94      else if (dist < 25) return 8;
95      else if (dist < 33) return 9;
96      else if (dist < 49) return 10;
97      else if (dist < 65) return 11;
98      else if (dist < 97) return 12;
99      else if (dist < 129) return 13;
100      else return 14;
101    }
102  } else {
103    if (dist < 2049) {  /* dist 193..2049. */
104      if (dist < 257) return 15;
105      else if (dist < 385) return 16;
106      else if (dist < 513) return 17;
107      else if (dist < 769) return 18;
108      else if (dist < 1025) return 19;
109      else if (dist < 1537) return 20;
110      else return 21;
111    } else {  /* dist 2049..32768. */
112      if (dist < 3073) return 22;
113      else if (dist < 4097) return 23;
114      else if (dist < 6145) return 24;
115      else if (dist < 8193) return 25;
116      else if (dist < 12289) return 26;
117      else if (dist < 16385) return 27;
118      else if (dist < 24577) return 28;
119      else return 29;
120    }
121  }
122#endif
123}
124
125int ZopfliGetLengthExtraBits(int l) {
126  static const int table[259] = {
127    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
128    2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
129    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
130    3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
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    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
134    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
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, 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, 0
143  };
144  return table[l];
145}
146
147int ZopfliGetLengthExtraBitsValue(int l) {
148  static const int table[259] = {
149    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 3, 0,
150    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,
151    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,
152    7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
153    13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2,
154    3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
155    10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
156    29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
157    18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6,
158    7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
159    27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
160    16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 0
161  };
162  return table[l];
163}
164
165/*
166Returns symbol in range [257-285] (inclusive).
167*/
168int ZopfliGetLengthSymbol(int l) {
169  static const int table[259] = {
170    0, 0, 0, 257, 258, 259, 260, 261, 262, 263, 264,
171    265, 265, 266, 266, 267, 267, 268, 268,
172    269, 269, 269, 269, 270, 270, 270, 270,
173    271, 271, 271, 271, 272, 272, 272, 272,
174    273, 273, 273, 273, 273, 273, 273, 273,
175    274, 274, 274, 274, 274, 274, 274, 274,
176    275, 275, 275, 275, 275, 275, 275, 275,
177    276, 276, 276, 276, 276, 276, 276, 276,
178    277, 277, 277, 277, 277, 277, 277, 277,
179    277, 277, 277, 277, 277, 277, 277, 277,
180    278, 278, 278, 278, 278, 278, 278, 278,
181    278, 278, 278, 278, 278, 278, 278, 278,
182    279, 279, 279, 279, 279, 279, 279, 279,
183    279, 279, 279, 279, 279, 279, 279, 279,
184    280, 280, 280, 280, 280, 280, 280, 280,
185    280, 280, 280, 280, 280, 280, 280, 280,
186    281, 281, 281, 281, 281, 281, 281, 281,
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    282, 282, 282, 282, 282, 282, 282, 282,
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    283, 283, 283, 283, 283, 283, 283, 283,
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    284, 284, 284, 284, 284, 284, 284, 284,
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, 285
202  };
203  return table[l];
204}
205
206void ZopfliInitOptions(ZopfliOptions* options) {
207  options->verbose = 0;
208  options->verbose_more = 0;
209  options->numiterations = 15;
210  options->blocksplitting = 1;
211  options->blocksplittinglast = 0;
212  options->blocksplittingmax = 15;
213}
214