| | 1 | | using System; |
| | 2 | |
|
| | 3 | | namespace ICSharpCode.SharpZipLib.Zip.Compression |
| | 4 | | { |
| | 5 | | /// <summary> |
| | 6 | | /// This is the DeflaterHuffman class. |
| | 7 | | /// |
| | 8 | | /// This class is <i>not</i> thread safe. This is inherent in the API, due |
| | 9 | | /// to the split of Deflate and SetInput. |
| | 10 | | /// |
| | 11 | | /// author of the original java version : Jochen Hoenicke |
| | 12 | | /// </summary> |
| | 13 | | public class DeflaterHuffman |
| | 14 | | { |
| | 15 | | const int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6); |
| | 16 | | const int LITERAL_NUM = 286; |
| | 17 | |
|
| | 18 | | // Number of distance codes |
| | 19 | | const int DIST_NUM = 30; |
| | 20 | | // Number of codes used to transfer bit lengths |
| | 21 | | const int BITLEN_NUM = 19; |
| | 22 | |
|
| | 23 | | // repeat previous bit length 3-6 times (2 bits of repeat count) |
| | 24 | | const int REP_3_6 = 16; |
| | 25 | | // repeat a zero length 3-10 times (3 bits of repeat count) |
| | 26 | | const int REP_3_10 = 17; |
| | 27 | | // repeat a zero length 11-138 times (7 bits of repeat count) |
| | 28 | | const int REP_11_138 = 18; |
| | 29 | |
|
| | 30 | | const int EOF_SYMBOL = 256; |
| | 31 | |
|
| | 32 | | // The lengths of the bit length codes are sent in order of decreasing |
| | 33 | | // probability, to avoid transmitting the lengths for unused bit length codes. |
| 1 | 34 | | static readonly int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; |
| | 35 | |
|
| 1 | 36 | | static readonly byte[] bit4Reverse = { |
| 1 | 37 | | 0, |
| 1 | 38 | | 8, |
| 1 | 39 | | 4, |
| 1 | 40 | | 12, |
| 1 | 41 | | 2, |
| 1 | 42 | | 10, |
| 1 | 43 | | 6, |
| 1 | 44 | | 14, |
| 1 | 45 | | 1, |
| 1 | 46 | | 9, |
| 1 | 47 | | 5, |
| 1 | 48 | | 13, |
| 1 | 49 | | 3, |
| 1 | 50 | | 11, |
| 1 | 51 | | 7, |
| 1 | 52 | | 15 |
| 1 | 53 | | }; |
| | 54 | |
|
| | 55 | | static short[] staticLCodes; |
| | 56 | | static byte[] staticLLength; |
| | 57 | | static short[] staticDCodes; |
| | 58 | | static byte[] staticDLength; |
| | 59 | |
|
| | 60 | | class Tree |
| | 61 | | { |
| | 62 | | #region Instance Fields |
| | 63 | | public short[] freqs; |
| | 64 | |
|
| | 65 | | public byte[] length; |
| | 66 | |
|
| | 67 | | public int minNumCodes; |
| | 68 | |
|
| | 69 | | public int numCodes; |
| | 70 | |
|
| | 71 | | short[] codes; |
| | 72 | | readonly int[] bl_counts; |
| | 73 | | readonly int maxLength; |
| | 74 | | DeflaterHuffman dh; |
| | 75 | | #endregion |
| | 76 | |
|
| | 77 | | #region Constructors |
| 819 | 78 | | public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength) |
| | 79 | | { |
| 819 | 80 | | this.dh = dh; |
| 819 | 81 | | this.minNumCodes = minCodes; |
| 819 | 82 | | this.maxLength = maxLength; |
| 819 | 83 | | freqs = new short[elems]; |
| 819 | 84 | | bl_counts = new int[maxLength]; |
| 819 | 85 | | } |
| | 86 | |
|
| | 87 | | #endregion |
| | 88 | |
|
| | 89 | | /// <summary> |
| | 90 | | /// Resets the internal state of the tree |
| | 91 | | /// </summary> |
| | 92 | | public void Reset() |
| | 93 | | { |
| 623948 | 94 | | for (int i = 0; i < freqs.Length; i++) { |
| 309205 | 95 | | freqs[i] = 0; |
| | 96 | | } |
| 2769 | 97 | | codes = null; |
| 2769 | 98 | | length = null; |
| 2769 | 99 | | } |
| | 100 | |
|
| | 101 | | public void WriteSymbol(int code) |
| | 102 | | { |
| | 103 | | // if (DeflaterConstants.DEBUGGING) { |
| | 104 | | // freqs[code]--; |
| | 105 | | // // Console.Write("writeSymbol("+freqs.length+","+code+"): "); |
| | 106 | | // } |
| 8298 | 107 | | dh.pending.WriteBits(codes[code] & 0xffff, length[code]); |
| 8298 | 108 | | } |
| | 109 | |
|
| | 110 | | /// <summary> |
| | 111 | | /// Check that all frequencies are zero |
| | 112 | | /// </summary> |
| | 113 | | /// <exception cref="SharpZipBaseException"> |
| | 114 | | /// At least one frequency is non-zero |
| | 115 | | /// </exception> |
| | 116 | | public void CheckEmpty() |
| | 117 | | { |
| 0 | 118 | | bool empty = true; |
| 0 | 119 | | for (int i = 0; i < freqs.Length; i++) { |
| 0 | 120 | | empty &= freqs[i] == 0; |
| | 121 | | } |
| | 122 | |
|
| 0 | 123 | | if (!empty) { |
| 0 | 124 | | throw new SharpZipBaseException("!Empty"); |
| | 125 | | } |
| 0 | 126 | | } |
| | 127 | |
|
| | 128 | | /// <summary> |
| | 129 | | /// Set static codes and length |
| | 130 | | /// </summary> |
| | 131 | | /// <param name="staticCodes">new codes</param> |
| | 132 | | /// <param name="staticLengths">length for new codes</param> |
| | 133 | | public void SetStaticCodes(short[] staticCodes, byte[] staticLengths) |
| | 134 | | { |
| 474 | 135 | | codes = staticCodes; |
| 474 | 136 | | length = staticLengths; |
| 474 | 137 | | } |
| | 138 | |
|
| | 139 | | /// <summary> |
| | 140 | | /// Build dynamic codes and lengths |
| | 141 | | /// </summary> |
| | 142 | | public void BuildCodes() |
| | 143 | | { |
| 3 | 144 | | int numSymbols = freqs.Length; |
| 3 | 145 | | int[] nextCode = new int[maxLength]; |
| 3 | 146 | | int code = 0; |
| | 147 | |
|
| 3 | 148 | | codes = new short[freqs.Length]; |
| | 149 | |
|
| | 150 | | // if (DeflaterConstants.DEBUGGING) { |
| | 151 | | // //Console.WriteLine("buildCodes: "+freqs.Length); |
| | 152 | | // } |
| | 153 | |
|
| 80 | 154 | | for (int bits = 0; bits < maxLength; bits++) { |
| 37 | 155 | | nextCode[bits] = code; |
| 37 | 156 | | code += bl_counts[bits] << (15 - bits); |
| | 157 | |
|
| | 158 | | // if (DeflaterConstants.DEBUGGING) { |
| | 159 | | // //Console.WriteLine("bits: " + ( bits + 1) + " count: " + bl_counts[bits] |
| | 160 | | // +" nextCode: "+code); |
| | 161 | | // } |
| | 162 | | } |
| | 163 | |
|
| | 164 | | #if DebugDeflation |
| | 165 | | if ( DeflaterConstants.DEBUGGING && (code != 65536) ) |
| | 166 | | { |
| | 167 | | throw new SharpZipBaseException("Inconsistent bl_counts!"); |
| | 168 | | } |
| | 169 | | #endif |
| 576 | 170 | | for (int i = 0; i < numCodes; i++) { |
| 285 | 171 | | int bits = length[i]; |
| 285 | 172 | | if (bits > 0) { |
| | 173 | |
|
| | 174 | | // if (DeflaterConstants.DEBUGGING) { |
| | 175 | | // //Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+"), |
| | 176 | | // +bits); |
| | 177 | | // } |
| | 178 | |
|
| 38 | 179 | | codes[i] = BitReverse(nextCode[bits - 1]); |
| 38 | 180 | | nextCode[bits - 1] += 1 << (16 - bits); |
| | 181 | | } |
| | 182 | | } |
| 3 | 183 | | } |
| | 184 | |
|
| | 185 | | public void BuildTree() |
| | 186 | | { |
| 1530 | 187 | | int numSymbols = freqs.Length; |
| | 188 | |
|
| | 189 | | /* heap is a priority queue, sorted by frequency, least frequent |
| | 190 | | * nodes first. The heap is a binary tree, with the property, that |
| | 191 | | * the parent node is smaller than both child nodes. This assures |
| | 192 | | * that the smallest node is the first parent. |
| | 193 | | * |
| | 194 | | * The binary tree is encoded in an array: 0 is root node and |
| | 195 | | * the nodes 2*n+1, 2*n+2 are the child nodes of node n. |
| | 196 | | */ |
| 1530 | 197 | | int[] heap = new int[numSymbols]; |
| 1530 | 198 | | int heapLen = 0; |
| 1530 | 199 | | int maxCode = 0; |
| 344760 | 200 | | for (int n = 0; n < numSymbols; n++) { |
| 170850 | 201 | | int freq = freqs[n]; |
| 170850 | 202 | | if (freq != 0) { |
| | 203 | | // Insert n into heap |
| 81797 | 204 | | int pos = heapLen++; |
| | 205 | | int ppos; |
| 161994 | 206 | | while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) { |
| 80197 | 207 | | heap[pos] = heap[ppos]; |
| 80197 | 208 | | pos = ppos; |
| | 209 | | } |
| 81797 | 210 | | heap[pos] = n; |
| | 211 | |
|
| 81797 | 212 | | maxCode = n; |
| | 213 | | } |
| | 214 | | } |
| | 215 | |
|
| | 216 | | /* We could encode a single literal with 0 bits but then we |
| | 217 | | * don't see the literals. Therefore we force at least two |
| | 218 | | * literals to avoid this case. We don't care about order in |
| | 219 | | * this case, both literals get a 1 bit code. |
| | 220 | | */ |
| 2077 | 221 | | while (heapLen < 2) { |
| 547 | 222 | | int node = maxCode < 2 ? ++maxCode : 0; |
| 547 | 223 | | heap[heapLen++] = node; |
| | 224 | | } |
| | 225 | |
|
| 1530 | 226 | | numCodes = Math.Max(maxCode + 1, minNumCodes); |
| | 227 | |
|
| 1530 | 228 | | int numLeafs = heapLen; |
| 1530 | 229 | | int[] childs = new int[4 * heapLen - 2]; |
| 1530 | 230 | | int[] values = new int[2 * heapLen - 1]; |
| 1530 | 231 | | int numNodes = numLeafs; |
| 167748 | 232 | | for (int i = 0; i < heapLen; i++) { |
| 82344 | 233 | | int node = heap[i]; |
| 82344 | 234 | | childs[2 * i] = node; |
| 82344 | 235 | | childs[2 * i + 1] = -1; |
| 82344 | 236 | | values[i] = freqs[node] << 8; |
| 82344 | 237 | | heap[i] = i; |
| | 238 | | } |
| | 239 | |
|
| | 240 | | /* Construct the Huffman tree by repeatedly combining the least two |
| | 241 | | * frequent nodes. |
| | 242 | | */ |
| | 243 | | do { |
| 80814 | 244 | | int first = heap[0]; |
| 80814 | 245 | | int last = heap[--heapLen]; |
| | 246 | |
|
| | 247 | | // Propagate the hole to the leafs of the heap |
| 80814 | 248 | | int ppos = 0; |
| 80814 | 249 | | int path = 1; |
| | 250 | |
|
| 507013 | 251 | | while (path < heapLen) { |
| 426199 | 252 | | if (path + 1 < heapLen && values[heap[path]] > values[heap[path + 1]]) { |
| 191359 | 253 | | path++; |
| | 254 | | } |
| | 255 | |
|
| 426199 | 256 | | heap[ppos] = heap[path]; |
| 426199 | 257 | | ppos = path; |
| 426199 | 258 | | path = path * 2 + 1; |
| | 259 | | } |
| | 260 | |
|
| | 261 | | /* Now propagate the last element down along path. Normally |
| | 262 | | * it shouldn't go too deep. |
| | 263 | | */ |
| 80814 | 264 | | int lastVal = values[last]; |
| 103741 | 265 | | while ((path = ppos) > 0 && values[heap[ppos = (path - 1) / 2]] > lastVal) { |
| 22927 | 266 | | heap[path] = heap[ppos]; |
| | 267 | | } |
| 80814 | 268 | | heap[path] = last; |
| | 269 | |
|
| | 270 | |
|
| 80814 | 271 | | int second = heap[0]; |
| | 272 | |
|
| | 273 | | // Create a new node father of first and second |
| 80814 | 274 | | last = numNodes++; |
| 80814 | 275 | | childs[2 * last] = first; |
| 80814 | 276 | | childs[2 * last + 1] = second; |
| 80814 | 277 | | int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff); |
| 80814 | 278 | | values[last] = lastVal = values[first] + values[second] - mindepth + 1; |
| | 279 | |
|
| | 280 | | // Again, propagate the hole to the leafs |
| 80814 | 281 | | ppos = 0; |
| 80814 | 282 | | path = 1; |
| | 283 | |
|
| 507819 | 284 | | while (path < heapLen) { |
| 427005 | 285 | | if (path + 1 < heapLen && values[heap[path]] > values[heap[path + 1]]) { |
| 193052 | 286 | | path++; |
| | 287 | | } |
| | 288 | |
|
| 427005 | 289 | | heap[ppos] = heap[path]; |
| 427005 | 290 | | ppos = path; |
| 427005 | 291 | | path = ppos * 2 + 1; |
| | 292 | | } |
| | 293 | |
|
| | 294 | | // Now propagate the new element down along path |
| 86039 | 295 | | while ((path = ppos) > 0 && values[heap[ppos = (path - 1) / 2]] > lastVal) { |
| 5225 | 296 | | heap[path] = heap[ppos]; |
| | 297 | | } |
| 80814 | 298 | | heap[path] = last; |
| 80814 | 299 | | } while (heapLen > 1); |
| | 300 | |
|
| 1530 | 301 | | if (heap[0] != childs.Length / 2 - 1) { |
| 0 | 302 | | throw new SharpZipBaseException("Heap invariant violated"); |
| | 303 | | } |
| | 304 | |
|
| 1530 | 305 | | BuildLength(childs); |
| 1530 | 306 | | } |
| | 307 | |
|
| | 308 | | /// <summary> |
| | 309 | | /// Get encoded length |
| | 310 | | /// </summary> |
| | 311 | | /// <returns>Encoded length, the sum of frequencies * lengths</returns> |
| | 312 | | public int GetEncodedLength() |
| | 313 | | { |
| 1530 | 314 | | int len = 0; |
| 344760 | 315 | | for (int i = 0; i < freqs.Length; i++) { |
| 170850 | 316 | | len += freqs[i] * length[i]; |
| | 317 | | } |
| 1530 | 318 | | return len; |
| | 319 | | } |
| | 320 | |
|
| | 321 | | /// <summary> |
| | 322 | | /// Scan a literal or distance tree to determine the frequencies of the codes |
| | 323 | | /// in the bit length tree. |
| | 324 | | /// </summary> |
| | 325 | | public void CalcBLFreq(Tree blTree) |
| | 326 | | { |
| | 327 | | int max_count; /* max repeat count */ |
| | 328 | | int min_count; /* min repeat count */ |
| | 329 | | int count; /* repeat count of the current code */ |
| 1020 | 330 | | int curlen = -1; /* length of current code */ |
| | 331 | |
|
| 1020 | 332 | | int i = 0; |
| 26206 | 333 | | while (i < numCodes) { |
| 25186 | 334 | | count = 1; |
| 25186 | 335 | | int nextlen = length[i]; |
| 25186 | 336 | | if (nextlen == 0) { |
| 2966 | 337 | | max_count = 138; |
| 2966 | 338 | | min_count = 3; |
| 2966 | 339 | | } else { |
| 22220 | 340 | | max_count = 6; |
| 22220 | 341 | | min_count = 3; |
| 22220 | 342 | | if (curlen != nextlen) { |
| 12628 | 343 | | blTree.freqs[nextlen]++; |
| 12628 | 344 | | count = 0; |
| | 345 | | } |
| | 346 | | } |
| 25186 | 347 | | curlen = nextlen; |
| 25186 | 348 | | i++; |
| | 349 | |
|
| 129433 | 350 | | while (i < numCodes && curlen == length[i]) { |
| 114222 | 351 | | i++; |
| 114222 | 352 | | if (++count >= max_count) { |
| | 353 | | break; |
| | 354 | | } |
| | 355 | | } |
| | 356 | |
|
| 25186 | 357 | | if (count < min_count) { |
| 13100 | 358 | | blTree.freqs[curlen] += (short)count; |
| 25186 | 359 | | } else if (curlen != 0) { |
| 10711 | 360 | | blTree.freqs[REP_3_6]++; |
| 12086 | 361 | | } else if (count <= 10) { |
| 319 | 362 | | blTree.freqs[REP_3_10]++; |
| 319 | 363 | | } else { |
| 1056 | 364 | | blTree.freqs[REP_11_138]++; |
| | 365 | | } |
| | 366 | | } |
| 1020 | 367 | | } |
| | 368 | |
|
| | 369 | | /// <summary> |
| | 370 | | /// Write tree values |
| | 371 | | /// </summary> |
| | 372 | | /// <param name="blTree">Tree to write</param> |
| | 373 | | public void WriteTree(Tree blTree) |
| | 374 | | { |
| | 375 | | int max_count; // max repeat count |
| | 376 | | int min_count; // min repeat count |
| | 377 | | int count; // repeat count of the current code |
| 2 | 378 | | int curlen = -1; // length of current code |
| | 379 | |
|
| 2 | 380 | | int i = 0; |
| 42 | 381 | | while (i < numCodes) { |
| 40 | 382 | | count = 1; |
| 40 | 383 | | int nextlen = length[i]; |
| 40 | 384 | | if (nextlen == 0) { |
| 14 | 385 | | max_count = 138; |
| 14 | 386 | | min_count = 3; |
| 14 | 387 | | } else { |
| 26 | 388 | | max_count = 6; |
| 26 | 389 | | min_count = 3; |
| 26 | 390 | | if (curlen != nextlen) { |
| 26 | 391 | | blTree.WriteSymbol(nextlen); |
| 26 | 392 | | count = 0; |
| | 393 | | } |
| | 394 | | } |
| 40 | 395 | | curlen = nextlen; |
| 40 | 396 | | i++; |
| | 397 | |
|
| 266 | 398 | | while (i < numCodes && curlen == length[i]) { |
| 226 | 399 | | i++; |
| 226 | 400 | | if (++count >= max_count) { |
| | 401 | | break; |
| | 402 | | } |
| | 403 | | } |
| | 404 | |
|
| 40 | 405 | | if (count < min_count) { |
| 41 | 406 | | while (count-- > 0) { |
| 10 | 407 | | blTree.WriteSymbol(curlen); |
| | 408 | | } |
| 40 | 409 | | } else if (curlen != 0) { |
| 0 | 410 | | blTree.WriteSymbol(REP_3_6); |
| 0 | 411 | | dh.pending.WriteBits(count - 3, 2); |
| 9 | 412 | | } else if (count <= 10) { |
| 4 | 413 | | blTree.WriteSymbol(REP_3_10); |
| 4 | 414 | | dh.pending.WriteBits(count - 3, 3); |
| 4 | 415 | | } else { |
| 5 | 416 | | blTree.WriteSymbol(REP_11_138); |
| 5 | 417 | | dh.pending.WriteBits(count - 11, 7); |
| | 418 | | } |
| | 419 | | } |
| 2 | 420 | | } |
| | 421 | |
|
| | 422 | | void BuildLength(int[] childs) |
| | 423 | | { |
| 1530 | 424 | | this.length = new byte[freqs.Length]; |
| 1530 | 425 | | int numNodes = childs.Length / 2; |
| 1530 | 426 | | int numLeafs = (numNodes + 1) / 2; |
| 1530 | 427 | | int overflow = 0; |
| | 428 | |
|
| 40800 | 429 | | for (int i = 0; i < maxLength; i++) { |
| 18870 | 430 | | bl_counts[i] = 0; |
| | 431 | | } |
| | 432 | |
|
| | 433 | | // First calculate optimal bit lengths |
| 1530 | 434 | | int[] lengths = new int[numNodes]; |
| 1530 | 435 | | lengths[numNodes - 1] = 0; |
| | 436 | |
|
| 329376 | 437 | | for (int i = numNodes - 1; i >= 0; i--) { |
| 163158 | 438 | | if (childs[2 * i + 1] != -1) { |
| 80814 | 439 | | int bitLength = lengths[i] + 1; |
| 80814 | 440 | | if (bitLength > maxLength) { |
| 2 | 441 | | bitLength = maxLength; |
| 2 | 442 | | overflow++; |
| | 443 | | } |
| 80814 | 444 | | lengths[childs[2 * i]] = lengths[childs[2 * i + 1]] = bitLength; |
| 80814 | 445 | | } else { |
| | 446 | | // A leaf node |
| 82344 | 447 | | int bitLength = lengths[i]; |
| 82344 | 448 | | bl_counts[bitLength - 1]++; |
| 82344 | 449 | | this.length[childs[2 * i]] = (byte)lengths[i]; |
| | 450 | | } |
| | 451 | | } |
| | 452 | |
|
| | 453 | | // if (DeflaterConstants.DEBUGGING) { |
| | 454 | | // //Console.WriteLine("Tree "+freqs.Length+" lengths:"); |
| | 455 | | // for (int i=0; i < numLeafs; i++) { |
| | 456 | | // //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]] |
| | 457 | | // + " len: "+length[childs[2*i]]); |
| | 458 | | // } |
| | 459 | | // } |
| | 460 | |
|
| 1530 | 461 | | if (overflow == 0) { |
| 1528 | 462 | | return; |
| | 463 | | } |
| | 464 | |
|
| 2 | 465 | | int incrBitLen = maxLength - 1; |
| | 466 | | do { |
| | 467 | | // Find the first bit length which could increase: |
| 2 | 468 | | while (bl_counts[--incrBitLen] == 0) { |
| | 469 | | } |
| | 470 | |
|
| | 471 | | // Move this node one down and remove a corresponding |
| | 472 | | // number of overflow nodes. |
| | 473 | | do { |
| 2 | 474 | | bl_counts[incrBitLen]--; |
| 2 | 475 | | bl_counts[++incrBitLen]++; |
| 2 | 476 | | overflow -= 1 << (maxLength - 1 - incrBitLen); |
| 2 | 477 | | } while (overflow > 0 && incrBitLen < maxLength - 1); |
| 2 | 478 | | } while (overflow > 0); |
| | 479 | |
|
| | 480 | | /* We may have overshot above. Move some nodes from maxLength to |
| | 481 | | * maxLength-1 in that case. |
| | 482 | | */ |
| 2 | 483 | | bl_counts[maxLength - 1] += overflow; |
| 2 | 484 | | bl_counts[maxLength - 2] -= overflow; |
| | 485 | |
|
| | 486 | | /* Now recompute all bit lengths, scanning in increasing |
| | 487 | | * frequency. It is simpler to reconstruct all lengths instead of |
| | 488 | | * fixing only the wrong ones. This idea is taken from 'ar' |
| | 489 | | * written by Haruhiko Okumura. |
| | 490 | | * |
| | 491 | | * The nodes were inserted with decreasing frequency into the childs |
| | 492 | | * array. |
| | 493 | | */ |
| 2 | 494 | | int nodePtr = 2 * numLeafs; |
| 32 | 495 | | for (int bits = maxLength; bits != 0; bits--) { |
| 14 | 496 | | int n = bl_counts[bits - 1]; |
| 44 | 497 | | while (n > 0) { |
| 30 | 498 | | int childPtr = 2 * childs[nodePtr++]; |
| 30 | 499 | | if (childs[childPtr + 1] == -1) { |
| | 500 | | // We found another leaf |
| 18 | 501 | | length[childs[childPtr]] = (byte)bits; |
| 18 | 502 | | n--; |
| | 503 | | } |
| | 504 | | } |
| | 505 | | } |
| | 506 | | // if (DeflaterConstants.DEBUGGING) { |
| | 507 | | // //Console.WriteLine("*** After overflow elimination. ***"); |
| | 508 | | // for (int i=0; i < numLeafs; i++) { |
| | 509 | | // //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]] |
| | 510 | | // + " len: "+length[childs[2*i]]); |
| | 511 | | // } |
| | 512 | | // } |
| 2 | 513 | | } |
| | 514 | |
|
| | 515 | | } |
| | 516 | |
|
| | 517 | | #region Instance Fields |
| | 518 | | /// <summary> |
| | 519 | | /// Pending buffer to use |
| | 520 | | /// </summary> |
| | 521 | | public DeflaterPending pending; |
| | 522 | |
|
| | 523 | | Tree literalTree; |
| | 524 | | Tree distTree; |
| | 525 | | Tree blTree; |
| | 526 | |
|
| | 527 | | // Buffer for distances |
| | 528 | | short[] d_buf; |
| | 529 | | byte[] l_buf; |
| | 530 | | int last_lit; |
| | 531 | | int extra_bits; |
| | 532 | | #endregion |
| | 533 | |
|
| | 534 | | static DeflaterHuffman() |
| | 535 | | { |
| | 536 | | // See RFC 1951 3.2.6 |
| | 537 | | // Literal codes |
| 1 | 538 | | staticLCodes = new short[LITERAL_NUM]; |
| 1 | 539 | | staticLLength = new byte[LITERAL_NUM]; |
| | 540 | |
|
| 1 | 541 | | int i = 0; |
| 145 | 542 | | while (i < 144) { |
| 144 | 543 | | staticLCodes[i] = BitReverse((0x030 + i) << 8); |
| 144 | 544 | | staticLLength[i++] = 8; |
| | 545 | | } |
| | 546 | |
|
| 113 | 547 | | while (i < 256) { |
| 112 | 548 | | staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7); |
| 112 | 549 | | staticLLength[i++] = 9; |
| | 550 | | } |
| | 551 | |
|
| 25 | 552 | | while (i < 280) { |
| 24 | 553 | | staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9); |
| 24 | 554 | | staticLLength[i++] = 7; |
| | 555 | | } |
| | 556 | |
|
| 7 | 557 | | while (i < LITERAL_NUM) { |
| 6 | 558 | | staticLCodes[i] = BitReverse((0x0c0 - 280 + i) << 8); |
| 6 | 559 | | staticLLength[i++] = 8; |
| | 560 | | } |
| | 561 | |
|
| | 562 | | // Distance codes |
| 1 | 563 | | staticDCodes = new short[DIST_NUM]; |
| 1 | 564 | | staticDLength = new byte[DIST_NUM]; |
| 62 | 565 | | for (i = 0; i < DIST_NUM; i++) { |
| 30 | 566 | | staticDCodes[i] = BitReverse(i << 11); |
| 30 | 567 | | staticDLength[i] = 5; |
| | 568 | | } |
| 1 | 569 | | } |
| | 570 | |
|
| | 571 | | /// <summary> |
| | 572 | | /// Construct instance with pending buffer |
| | 573 | | /// </summary> |
| | 574 | | /// <param name="pending">Pending buffer to use</param> |
| 273 | 575 | | public DeflaterHuffman(DeflaterPending pending) |
| | 576 | | { |
| 273 | 577 | | this.pending = pending; |
| | 578 | |
|
| 273 | 579 | | literalTree = new Tree(this, LITERAL_NUM, 257, 15); |
| 273 | 580 | | distTree = new Tree(this, DIST_NUM, 1, 15); |
| 273 | 581 | | blTree = new Tree(this, BITLEN_NUM, 4, 7); |
| | 582 | |
|
| 273 | 583 | | d_buf = new short[BUFSIZE]; |
| 273 | 584 | | l_buf = new byte[BUFSIZE]; |
| 273 | 585 | | } |
| | 586 | |
|
| | 587 | | /// <summary> |
| | 588 | | /// Reset internal state |
| | 589 | | /// </summary> |
| | 590 | | public void Reset() |
| | 591 | | { |
| 923 | 592 | | last_lit = 0; |
| 923 | 593 | | extra_bits = 0; |
| 923 | 594 | | literalTree.Reset(); |
| 923 | 595 | | distTree.Reset(); |
| 923 | 596 | | blTree.Reset(); |
| 923 | 597 | | } |
| | 598 | |
|
| | 599 | | /// <summary> |
| | 600 | | /// Write all trees to pending buffer |
| | 601 | | /// </summary> |
| | 602 | | /// <param name="blTreeCodes">The number/rank of treecodes to send.</param> |
| | 603 | | public void SendAllTrees(int blTreeCodes) |
| | 604 | | { |
| 1 | 605 | | blTree.BuildCodes(); |
| 1 | 606 | | literalTree.BuildCodes(); |
| 1 | 607 | | distTree.BuildCodes(); |
| 1 | 608 | | pending.WriteBits(literalTree.numCodes - 257, 5); |
| 1 | 609 | | pending.WriteBits(distTree.numCodes - 1, 5); |
| 1 | 610 | | pending.WriteBits(blTreeCodes - 4, 4); |
| 38 | 611 | | for (int rank = 0; rank < blTreeCodes; rank++) { |
| 18 | 612 | | pending.WriteBits(blTree.length[BL_ORDER[rank]], 3); |
| | 613 | | } |
| 1 | 614 | | literalTree.WriteTree(blTree); |
| 1 | 615 | | distTree.WriteTree(blTree); |
| | 616 | |
|
| | 617 | | #if DebugDeflation |
| | 618 | | if (DeflaterConstants.DEBUGGING) { |
| | 619 | | blTree.CheckEmpty(); |
| | 620 | | } |
| | 621 | | #endif |
| 1 | 622 | | } |
| | 623 | |
|
| | 624 | | /// <summary> |
| | 625 | | /// Compress current buffer writing data to pending buffer |
| | 626 | | /// </summary> |
| | 627 | | public void CompressBlock() |
| | 628 | | { |
| 16324 | 629 | | for (int i = 0; i < last_lit; i++) { |
| 7924 | 630 | | int litlen = l_buf[i] & 0xff; |
| 7924 | 631 | | int dist = d_buf[i]; |
| 7924 | 632 | | if (dist-- != 0) { |
| | 633 | | // if (DeflaterConstants.DEBUGGING) { |
| | 634 | | // Console.Write("["+(dist+1)+","+(litlen+3)+"]: "); |
| | 635 | | // } |
| | 636 | |
|
| 91 | 637 | | int lc = Lcode(litlen); |
| 91 | 638 | | literalTree.WriteSymbol(lc); |
| | 639 | |
|
| 91 | 640 | | int bits = (lc - 261) / 4; |
| 91 | 641 | | if (bits > 0 && bits <= 5) { |
| 25 | 642 | | pending.WriteBits(litlen & ((1 << bits) - 1), bits); |
| | 643 | | } |
| | 644 | |
|
| 91 | 645 | | int dc = Dcode(dist); |
| 91 | 646 | | distTree.WriteSymbol(dc); |
| | 647 | |
|
| 91 | 648 | | bits = dc / 2 - 1; |
| 91 | 649 | | if (bits > 0) { |
| 70 | 650 | | pending.WriteBits(dist & ((1 << bits) - 1), bits); |
| | 651 | | } |
| 70 | 652 | | } else { |
| | 653 | | // if (DeflaterConstants.DEBUGGING) { |
| | 654 | | // if (litlen > 32 && litlen < 127) { |
| | 655 | | // Console.Write("("+(char)litlen+"): "); |
| | 656 | | // } else { |
| | 657 | | // Console.Write("{"+litlen+"}: "); |
| | 658 | | // } |
| | 659 | | // } |
| 7833 | 660 | | literalTree.WriteSymbol(litlen); |
| | 661 | | } |
| | 662 | | } |
| | 663 | |
|
| | 664 | | #if DebugDeflation |
| | 665 | | if (DeflaterConstants.DEBUGGING) { |
| | 666 | | Console.Write("EOF: "); |
| | 667 | | } |
| | 668 | | #endif |
| 238 | 669 | | literalTree.WriteSymbol(EOF_SYMBOL); |
| | 670 | |
|
| | 671 | | #if DebugDeflation |
| | 672 | | if (DeflaterConstants.DEBUGGING) { |
| | 673 | | literalTree.CheckEmpty(); |
| | 674 | | distTree.CheckEmpty(); |
| | 675 | | } |
| | 676 | | #endif |
| 238 | 677 | | } |
| | 678 | |
|
| | 679 | | /// <summary> |
| | 680 | | /// Flush block to output with no compression |
| | 681 | | /// </summary> |
| | 682 | | /// <param name="stored">Data to write</param> |
| | 683 | | /// <param name="storedOffset">Index of first byte to write</param> |
| | 684 | | /// <param name="storedLength">Count of bytes to write</param> |
| | 685 | | /// <param name="lastBlock">True if this is the last block</param> |
| | 686 | | public void FlushStoredBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock) |
| | 687 | | { |
| | 688 | | #if DebugDeflation |
| | 689 | | // if (DeflaterConstants.DEBUGGING) { |
| | 690 | | // //Console.WriteLine("Flushing stored block "+ storedLength); |
| | 691 | | // } |
| | 692 | | #endif |
| 293 | 693 | | pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1) + (lastBlock ? 1 : 0), 3); |
| 293 | 694 | | pending.AlignToByte(); |
| 293 | 695 | | pending.WriteShort(storedLength); |
| 293 | 696 | | pending.WriteShort(~storedLength); |
| 293 | 697 | | pending.WriteBlock(stored, storedOffset, storedLength); |
| 293 | 698 | | Reset(); |
| 293 | 699 | | } |
| | 700 | |
|
| | 701 | | /// <summary> |
| | 702 | | /// Flush block to output with compression |
| | 703 | | /// </summary> |
| | 704 | | /// <param name="stored">Data to flush</param> |
| | 705 | | /// <param name="storedOffset">Index of first byte to flush</param> |
| | 706 | | /// <param name="storedLength">Count of bytes to flush</param> |
| | 707 | | /// <param name="lastBlock">True if this is the last block</param> |
| | 708 | | public void FlushBlock(byte[] stored, int storedOffset, int storedLength, bool lastBlock) |
| | 709 | | { |
| 510 | 710 | | literalTree.freqs[EOF_SYMBOL]++; |
| | 711 | |
|
| | 712 | | // Build trees |
| 510 | 713 | | literalTree.BuildTree(); |
| 510 | 714 | | distTree.BuildTree(); |
| | 715 | |
|
| | 716 | | // Calculate bitlen frequency |
| 510 | 717 | | literalTree.CalcBLFreq(blTree); |
| 510 | 718 | | distTree.CalcBLFreq(blTree); |
| | 719 | |
|
| | 720 | | // Build bitlen tree |
| 510 | 721 | | blTree.BuildTree(); |
| | 722 | |
|
| 510 | 723 | | int blTreeCodes = 4; |
| 3556 | 724 | | for (int i = 18; i > blTreeCodes; i--) { |
| 1268 | 725 | | if (blTree.length[BL_ORDER[i]] > 0) { |
| 510 | 726 | | blTreeCodes = i + 1; |
| | 727 | | } |
| | 728 | | } |
| 510 | 729 | | int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() + |
| 510 | 730 | | literalTree.GetEncodedLength() + distTree.GetEncodedLength() + |
| 510 | 731 | | extra_bits; |
| | 732 | |
|
| 510 | 733 | | int static_len = extra_bits; |
| 292740 | 734 | | for (int i = 0; i < LITERAL_NUM; i++) { |
| 145860 | 735 | | static_len += literalTree.freqs[i] * staticLLength[i]; |
| | 736 | | } |
| 31620 | 737 | | for (int i = 0; i < DIST_NUM; i++) { |
| 15300 | 738 | | static_len += distTree.freqs[i] * staticDLength[i]; |
| | 739 | | } |
| 510 | 740 | | if (opt_len >= static_len) { |
| | 741 | | // Force static trees |
| 270 | 742 | | opt_len = static_len; |
| | 743 | | } |
| | 744 | |
|
| 510 | 745 | | if (storedOffset >= 0 && storedLength + 4 < opt_len >> 3) { |
| | 746 | | // Store Block |
| | 747 | |
|
| | 748 | | // if (DeflaterConstants.DEBUGGING) { |
| | 749 | | // //Console.WriteLine("Storing, since " + storedLength + " < " + opt_len |
| | 750 | | // + " <= " + static_len); |
| | 751 | | // } |
| 272 | 752 | | FlushStoredBlock(stored, storedOffset, storedLength, lastBlock); |
| 510 | 753 | | } else if (opt_len == static_len) { |
| | 754 | | // Encode with static tree |
| 237 | 755 | | pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3); |
| 237 | 756 | | literalTree.SetStaticCodes(staticLCodes, staticLLength); |
| 237 | 757 | | distTree.SetStaticCodes(staticDCodes, staticDLength); |
| 237 | 758 | | CompressBlock(); |
| 237 | 759 | | Reset(); |
| 237 | 760 | | } else { |
| | 761 | | // Encode with dynamic tree |
| 1 | 762 | | pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3); |
| 1 | 763 | | SendAllTrees(blTreeCodes); |
| 1 | 764 | | CompressBlock(); |
| 1 | 765 | | Reset(); |
| | 766 | | } |
| 1 | 767 | | } |
| | 768 | |
|
| | 769 | | /// <summary> |
| | 770 | | /// Get value indicating if internal buffer is full |
| | 771 | | /// </summary> |
| | 772 | | /// <returns>true if buffer is full</returns> |
| | 773 | | public bool IsFull() |
| | 774 | | { |
| 7208362 | 775 | | return last_lit >= BUFSIZE; |
| | 776 | | } |
| | 777 | |
|
| | 778 | | /// <summary> |
| | 779 | | /// Add literal to buffer |
| | 780 | | /// </summary> |
| | 781 | | /// <param name="literal">Literal value to add to buffer.</param> |
| | 782 | | /// <returns>Value indicating internal buffer is full</returns> |
| | 783 | | public bool TallyLit(int literal) |
| | 784 | | { |
| | 785 | | // if (DeflaterConstants.DEBUGGING) { |
| | 786 | | // if (lit > 32 && lit < 127) { |
| | 787 | | // //Console.WriteLine("("+(char)lit+")"); |
| | 788 | | // } else { |
| | 789 | | // //Console.WriteLine("{"+lit+"}"); |
| | 790 | | // } |
| | 791 | | // } |
| 3602142 | 792 | | d_buf[last_lit] = 0; |
| 3602142 | 793 | | l_buf[last_lit++] = (byte)literal; |
| 3602142 | 794 | | literalTree.freqs[literal]++; |
| 3602142 | 795 | | return IsFull(); |
| | 796 | | } |
| | 797 | |
|
| | 798 | | /// <summary> |
| | 799 | | /// Add distance code and length to literal and distance trees |
| | 800 | | /// </summary> |
| | 801 | | /// <param name="distance">Distance code</param> |
| | 802 | | /// <param name="length">Length</param> |
| | 803 | | /// <returns>Value indicating if internal buffer is full</returns> |
| | 804 | | public bool TallyDist(int distance, int length) |
| | 805 | | { |
| | 806 | | // if (DeflaterConstants.DEBUGGING) { |
| | 807 | | // //Console.WriteLine("[" + distance + "," + length + "]"); |
| | 808 | | // } |
| | 809 | |
|
| 2828 | 810 | | d_buf[last_lit] = (short)distance; |
| 2828 | 811 | | l_buf[last_lit++] = (byte)(length - 3); |
| | 812 | |
|
| 2828 | 813 | | int lc = Lcode(length - 3); |
| 2828 | 814 | | literalTree.freqs[lc]++; |
| 2828 | 815 | | if (lc >= 265 && lc < 285) { |
| 25 | 816 | | extra_bits += (lc - 261) / 4; |
| | 817 | | } |
| | 818 | |
|
| 2828 | 819 | | int dc = Dcode(distance - 1); |
| 2828 | 820 | | distTree.freqs[dc]++; |
| 2828 | 821 | | if (dc >= 4) { |
| 2807 | 822 | | extra_bits += dc / 2 - 1; |
| | 823 | | } |
| 2828 | 824 | | return IsFull(); |
| | 825 | | } |
| | 826 | |
|
| | 827 | |
|
| | 828 | | /// <summary> |
| | 829 | | /// Reverse the bits of a 16 bit value. |
| | 830 | | /// </summary> |
| | 831 | | /// <param name="toReverse">Value to reverse bits</param> |
| | 832 | | /// <returns>Value with bits reversed</returns> |
| | 833 | | public static short BitReverse(int toReverse) |
| | 834 | | { |
| 712 | 835 | | return (short)(bit4Reverse[toReverse & 0xF] << 12 | |
| 712 | 836 | | bit4Reverse[(toReverse >> 4) & 0xF] << 8 | |
| 712 | 837 | | bit4Reverse[(toReverse >> 8) & 0xF] << 4 | |
| 712 | 838 | | bit4Reverse[toReverse >> 12]); |
| | 839 | | } |
| | 840 | |
|
| | 841 | | static int Lcode(int length) |
| | 842 | | { |
| 2919 | 843 | | if (length == 255) { |
| 82 | 844 | | return 285; |
| | 845 | | } |
| | 846 | |
|
| 2837 | 847 | | int code = 257; |
| 3067 | 848 | | while (length >= 8) { |
| 230 | 849 | | code += 4; |
| 230 | 850 | | length >>= 1; |
| | 851 | | } |
| 2837 | 852 | | return code + length; |
| | 853 | | } |
| | 854 | |
|
| | 855 | | static int Dcode(int distance) |
| | 856 | | { |
| 2919 | 857 | | int code = 0; |
| 34328 | 858 | | while (distance >= 4) { |
| 31409 | 859 | | code += 2; |
| 31409 | 860 | | distance >>= 1; |
| | 861 | | } |
| 2919 | 862 | | return code + distance; |
| | 863 | | } |
| | 864 | | } |
| | 865 | | } |