123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423 |
- using System;
- namespace BestHTTP.Decompression.Zlib
- {
- sealed class ZTree
- {
- private static readonly int HEAP_SIZE = (2 * InternalConstants.L_CODES + 1);
-
-
- internal static readonly int[] ExtraLengthBits = new int[]
- {
- 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
- 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
- };
-
-
- internal static readonly int[] ExtraDistanceBits = new int[]
- {
- 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
- 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
- };
-
-
- internal static readonly int[] extra_blbits = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7};
-
- internal static readonly sbyte[] bl_order = new sbyte[]{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
-
-
-
-
-
-
- internal const int Buf_size = 8 * 2;
-
-
-
-
- private static readonly sbyte[] _dist_code = new sbyte[]
- {
- 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
- 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,
- 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
- 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
- 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
- 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
- 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
- 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
- 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
- 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
- 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
- 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
- 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
- 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
- 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
- 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
- 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
- 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
- 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
- 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
- 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
- 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
- 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
- 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
- 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
- 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
- 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
- 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
- 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
- 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
- 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
- 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29
- };
-
- internal static readonly sbyte[] LengthCode = new sbyte[]
- {
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11,
- 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
- 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
- 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19,
- 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
- 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
- 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
- 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
- 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
- 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
- 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
- 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
- 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
- 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
- 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
- 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28
- };
-
- internal static readonly int[] LengthBase = new int[]
- {
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28,
- 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 0
- };
-
- internal static readonly int[] DistanceBase = new int[]
- {
- 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192,
- 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576
- };
-
-
-
-
-
-
-
- internal static int DistanceCode(int dist)
- {
- return (dist < 256)
- ? _dist_code[dist]
- : _dist_code[256 + SharedUtils.URShift(dist, 7)];
- }
- internal short[] dyn_tree;
- internal int max_code;
- internal StaticTree staticTree;
-
-
-
-
-
-
-
-
-
- internal void gen_bitlen(DeflateManager s)
- {
- short[] tree = dyn_tree;
- short[] stree = staticTree.treeCodes;
- int[] extra = staticTree.extraBits;
- int base_Renamed = staticTree.extraBase;
- int max_length = staticTree.maxLength;
- int h;
- int n, m;
- int bits;
- int xbits;
- short f;
- int overflow = 0;
-
- for (bits = 0; bits <= InternalConstants.MAX_BITS; bits++)
- s.bl_count[bits] = 0;
-
-
-
- tree[s.heap[s.heap_max] * 2 + 1] = 0;
-
- for (h = s.heap_max + 1; h < HEAP_SIZE; h++)
- {
- n = s.heap[h];
- bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
- if (bits > max_length)
- {
- bits = max_length; overflow++;
- }
- tree[n * 2 + 1] = (short) bits;
-
-
- if (n > max_code)
- continue;
-
- s.bl_count[bits]++;
- xbits = 0;
- if (n >= base_Renamed)
- xbits = extra[n - base_Renamed];
- f = tree[n * 2];
- s.opt_len += f * (bits + xbits);
- if (stree != null)
- s.static_len += f * (stree[n * 2 + 1] + xbits);
- }
- if (overflow == 0)
- return ;
-
-
-
- do
- {
- bits = max_length - 1;
- while (s.bl_count[bits] == 0)
- bits--;
- s.bl_count[bits]--;
- s.bl_count[bits + 1] = (short) (s.bl_count[bits + 1] + 2);
- s.bl_count[max_length]--;
-
-
- overflow -= 2;
- }
- while (overflow > 0);
-
- for (bits = max_length; bits != 0; bits--)
- {
- n = s.bl_count[bits];
- while (n != 0)
- {
- m = s.heap[--h];
- if (m > max_code)
- continue;
- if (tree[m * 2 + 1] != bits)
- {
- s.opt_len = (int) (s.opt_len + ((long) bits - (long) tree[m * 2 + 1]) * (long) tree[m * 2]);
- tree[m * 2 + 1] = (short) bits;
- }
- n--;
- }
- }
- }
-
-
-
-
-
-
-
- internal void build_tree(DeflateManager s)
- {
- short[] tree = dyn_tree;
- short[] stree = staticTree.treeCodes;
- int elems = staticTree.elems;
- int n, m;
- int max_code = -1;
- int node;
-
-
-
-
- s.heap_len = 0;
- s.heap_max = HEAP_SIZE;
-
- for (n = 0; n < elems; n++)
- {
- if (tree[n * 2] != 0)
- {
- s.heap[++s.heap_len] = max_code = n;
- s.depth[n] = 0;
- }
- else
- {
- tree[n * 2 + 1] = 0;
- }
- }
-
-
-
-
-
- while (s.heap_len < 2)
- {
- node = s.heap[++s.heap_len] = (max_code < 2?++max_code:0);
- tree[node * 2] = 1;
- s.depth[node] = 0;
- s.opt_len--;
- if (stree != null)
- s.static_len -= stree[node * 2 + 1];
-
- }
- this.max_code = max_code;
-
-
-
-
- for (n = s.heap_len / 2; n >= 1; n--)
- s.pqdownheap(tree, n);
-
-
-
-
- node = elems;
- do
- {
-
- n = s.heap[1];
- s.heap[1] = s.heap[s.heap_len--];
- s.pqdownheap(tree, 1);
- m = s.heap[1];
-
- s.heap[--s.heap_max] = n;
- s.heap[--s.heap_max] = m;
-
-
- tree[node * 2] = unchecked((short) (tree[n * 2] + tree[m * 2]));
- s.depth[node] = (sbyte) (System.Math.Max((byte) s.depth[n], (byte) s.depth[m]) + 1);
- tree[n * 2 + 1] = tree[m * 2 + 1] = (short) node;
-
-
- s.heap[1] = node++;
- s.pqdownheap(tree, 1);
- }
- while (s.heap_len >= 2);
-
- s.heap[--s.heap_max] = s.heap[1];
-
-
-
-
- gen_bitlen(s);
-
-
- gen_codes(tree, max_code, s.bl_count);
- }
-
-
-
-
-
-
-
- internal static void gen_codes(short[] tree, int max_code, short[] bl_count)
- {
- short[] next_code = new short[InternalConstants.MAX_BITS + 1];
- short code = 0;
- int bits;
- int n;
-
-
-
- for (bits = 1; bits <= InternalConstants.MAX_BITS; bits++)
- unchecked {
- next_code[bits] = code = (short) ((code + bl_count[bits - 1]) << 1);
- }
-
-
-
-
-
-
-
- for (n = 0; n <= max_code; n++)
- {
- int len = tree[n * 2 + 1];
- if (len == 0)
- continue;
-
- tree[n * 2] = unchecked((short) (bi_reverse(next_code[len]++, len)));
- }
- }
-
-
-
-
- internal static int bi_reverse(int code, int len)
- {
- int res = 0;
- do
- {
- res |= code & 1;
- code >>= 1;
- res <<= 1;
- }
- while (--len > 0);
- return res >> 1;
- }
- }
- }
|