Tree
using System;
namespace Org.BouncyCastle.Utilities.Zlib
{
internal sealed class Tree
{
private const int MAX_BITS = 15;
private const int BL_CODES = 19;
private const int D_CODES = 30;
private const int LITERALS = 256;
private const int LENGTH_CODES = 29;
private const int L_CODES = 286;
private const int HEAP_SIZE = 573;
internal const int MAX_BL_BITS = 7;
internal const int END_BLOCK = 256;
internal const int REP_3_6 = 16;
internal const int REPZ_3_10 = 17;
internal const int REPZ_11_138 = 18;
internal static readonly int[] extra_lbits = new int[29] {
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[] extra_dbits = new int[30] {
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[19] {
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
2,
3,
7
};
internal static readonly byte[] bl_order = new byte[19] {
16,
17,
18,
0,
8,
7,
9,
6,
10,
5,
11,
4,
12,
3,
13,
2,
14,
1,
15
};
internal const int Buf_size = 16;
internal const int DIST_CODE_LEN = 512;
internal static readonly byte[] _dist_code = new byte[512] {
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 byte[] _length_code = new byte[256] {
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[] base_length = new int[29] {
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[] base_dist = new int[30] {
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 short[] dyn_tree;
internal int max_code;
internal StaticTree stat_desc;
internal static int d_code(int dist)
{
if (dist >= 256)
return _dist_code[256 + (dist >> 7)];
return _dist_code[dist];
}
internal void gen_bitlen(Deflate s)
{
short[] array = dyn_tree;
short[] static_tree = stat_desc.static_tree;
int[] extra_bits = stat_desc.extra_bits;
int extra_base = stat_desc.extra_base;
int max_length = stat_desc.max_length;
int num = 0;
for (int i = 0; i <= 15; i++) {
s.bl_count[i] = 0;
}
array[s.heap[s.heap_max] * 2 + 1] = 0;
int j;
for (j = s.heap_max + 1; j < 573; j++) {
int num2 = s.heap[j];
int i = array[array[num2 * 2 + 1] * 2 + 1] + 1;
if (i > max_length) {
i = max_length;
num++;
}
array[num2 * 2 + 1] = (short)i;
if (num2 <= max_code) {
s.bl_count[i]++;
int num3 = 0;
if (num2 >= extra_base)
num3 = extra_bits[num2 - extra_base];
short num4 = array[num2 * 2];
s.opt_len += num4 * (i + num3);
if (static_tree != null)
s.static_len += num4 * (static_tree[num2 * 2 + 1] + num3);
}
}
if (num != 0) {
do {
int i = max_length - 1;
while (s.bl_count[i] == 0) {
i--;
}
s.bl_count[i]--;
s.bl_count[i + 1] += 2;
s.bl_count[max_length]--;
num -= 2;
} while (num > 0);
for (int i = max_length; i != 0; i--) {
int num2 = s.bl_count[i];
while (num2 != 0) {
int num5 = s.heap[--j];
if (num5 <= max_code) {
if (array[num5 * 2 + 1] != i) {
s.opt_len += (int)(((long)i - (long)array[num5 * 2 + 1]) * array[num5 * 2]);
array[num5 * 2 + 1] = (short)i;
}
num2--;
}
}
}
}
}
internal void build_tree(Deflate s)
{
short[] array = dyn_tree;
short[] static_tree = stat_desc.static_tree;
int elems = stat_desc.elems;
int num = -1;
s.heap_len = 0;
s.heap_max = 573;
for (int i = 0; i < elems; i++) {
if (array[i * 2] != 0) {
num = (s.heap[++s.heap_len] = i);
s.depth[i] = 0;
} else
array[i * 2 + 1] = 0;
}
int num2;
while (s.heap_len < 2) {
num2 = (s.heap[++s.heap_len] = ((num < 2) ? (++num) : 0));
array[num2 * 2] = 1;
s.depth[num2] = 0;
s.opt_len--;
if (static_tree != null)
s.static_len -= static_tree[num2 * 2 + 1];
}
max_code = num;
for (int i = s.heap_len / 2; i >= 1; i--) {
s.pqdownheap(array, i);
}
num2 = elems;
do {
int i = s.heap[1];
s.heap[1] = s.heap[s.heap_len--];
s.pqdownheap(array, 1);
int num3 = s.heap[1];
s.heap[--s.heap_max] = i;
s.heap[--s.heap_max] = num3;
array[num2 * 2] = (short)(array[i * 2] + array[num3 * 2]);
s.depth[num2] = (byte)(System.Math.Max(s.depth[i], s.depth[num3]) + 1);
array[i * 2 + 1] = (array[num3 * 2 + 1] = (short)num2);
s.heap[1] = num2++;
s.pqdownheap(array, 1);
} while (s.heap_len >= 2);
s.heap[--s.heap_max] = s.heap[1];
gen_bitlen(s);
gen_codes(array, num, s.bl_count);
}
internal static void gen_codes(short[] tree, int max_code, short[] bl_count)
{
short[] array = new short[16];
short num = 0;
for (int i = 1; i <= 15; i++) {
num = (array[i] = (short)(num + bl_count[i - 1] << 1));
}
for (int j = 0; j <= max_code; j++) {
int num2 = tree[j * 2 + 1];
if (num2 != 0)
tree[j * 2] = (short)bi_reverse(array[num2]++, num2);
}
}
internal static int bi_reverse(int code, int len)
{
int num = 0;
do {
num |= (code & 1);
code >>= 1;
num <<= 1;
} while (--len > 0);
return num >> 1;
}
}
}