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