Home | History | Annotate | Download | only in zopfli
      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 (at) gmail.com (Lode Vandevenne)
     17 Author: jyrki.alakuijala (at) 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 
     28 int 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 
     50 int 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 
     76 int 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 
    125 int 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 
    147 int 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 /*
    166 Returns symbol in range [257-285] (inclusive).
    167 */
    168 int 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 
    206 void 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