/*
Zlib – библиотека сжатия данных общего назначения. Версия 1.1.0
Это изменённая объектно-ориентированная версия библиотеки, полностью
совместимая с оригинальной библиотекой.
Copyright © 1995–2005 Jean-loup Gailly и Mark Adler
Copyright © 2000–2011 ymnk, JCraft, Inc.
Copyright © 2016, 2019 Малик Разработчик
Эта библиотека поставляется «как есть», без каких-либо явных или
подразумеваемых гарантий. Ни при каких обстоятельствах авторы не
несут какой-либо ответственности в случае потери данных вследствие
использования данной библиотеки.
Разрешается всем использовать эту библиотеку для любых целей, в том
числе и для коммерческих приложений, а также изменять её и
распространять свободно при соблюдении следующих условий:
1. Оригинал библиотеки не должен быть искажён; вы не должны
заявлять, что именно вы написали оригинальную библиотеку. Если вы
используете эту библиотеку в своём программном продукте, то ссылка
на авторов библиотеки была бы желательна, но это не является
обязательным требованием.
2. Изменённые версии исходных текстов должны быть отчётливо
маркированы и не должны выдаваться за оригинал библиотеки.
3. Эти замечания не могут быть удалены либо изменены при
каком-либо варианте распространения исходных текстов.
*/
package malik.emulator.compression.zlib;
final class Tree extends Zlib
{
private static final int MAX_BITS = 15;
private static final int LITERALS = 256;
private static final int LENGTH_CODES = 29;
private static final int L_CODES = LITERALS + 1 + LENGTH_CODES;
private static final int HEAP_SIZE = 2 * L_CODES + 1;
private static void genCodes(int[] tree, int maxCode, int[] blCount)
{
int[] nextCode = new int[MAX_BITS + 1];
int code = 0;
int bits;
int n;
for(bits = 1; bits <= MAX_BITS; bits++)
{
nextCode[bits] = code = (short) ((code + blCount[bits - 1]) << 1);
}
for(n = 0; n <= maxCode; n++)
{
int len = tree[n * 2 + 1];
if(len == 0)
{
continue;
}
tree[n * 2] = (short) (biReverse(nextCode[len]++, len));
}
}
private static int biReverse(int code, int len)
{
int res = 0;
do
{
res |= code & 1;
code >>>= 1;
res <<= 1;
} while(--len > 0);
return res >>> 1;
}
public int maxCode;
public int[] dynTree;
public StaticTree statDesc;
Tree()
{
}
public void buildTree(Deflate s)
{
int elems = statDesc.elems;
int n;
int m;
int maxCodeLocal = -1;
int node;
int[] tree = dynTree;
int[] stree = statDesc.staticTree;
s.heapLen = 0;
s.heapMax = HEAP_SIZE;
for(n = 0; n < elems; n++)
{
if(tree[n * 2] != 0)
{
s.heap[++s.heapLen] = maxCodeLocal = n;
s.depth[n] = 0;
} else
{
tree[n * 2 + 1] = 0;
}
}
while(s.heapLen < 2)
{
node = s.heap[++s.heapLen] = (maxCodeLocal < 2 ? ++maxCodeLocal : 0);
tree[node * 2] = 1;
s.depth[node] = 0;
s.optLen--;
if(stree != null)
{
s.staticLen -= stree[node * 2 + 1];
}
}
this.maxCode = maxCodeLocal;
for(n = s.heapLen / 2; n >= 1; n--)
{
s.pqDownHeap(tree, n);
}
node = elems;
do
{
n = s.heap[1];
s.heap[1] = s.heap[s.heapLen--];
s.pqDownHeap(tree, 1);
m = s.heap[1];
s.heap[--s.heapMax] = n;
s.heap[--s.heapMax] = m;
tree[node * 2] = (short) (tree[n * 2] + tree[m * 2]);
s.depth[node] = (byte) (Math.max(s.depth[n], s.depth[m]) + 1);
tree[n * 2 + 1] = tree[m * 2 + 1] = (short) node;
s.heap[1] = node++;
s.pqDownHeap(tree, 1);
} while(s.heapLen >= 2);
s.heap[--s.heapMax] = s.heap[1];
genBitlen(s);
genCodes(tree, maxCodeLocal, s.blCount);
}
private void genBitlen(Deflate s)
{
int f;
int base = statDesc.extraBase;
int maxLength = statDesc.maxLength;
int h;
int n;
int m;
int bits;
int xbits;
int overflow = 0;
int[] tree = dynTree;
int[] stree = statDesc.staticTree;
int[] extra = statDesc.extraBits;
for(bits = 0; bits <= MAX_BITS; bits++)
{
s.blCount[bits] = 0;
}
tree[s.heap[s.heapMax] * 2 + 1] = 0;
for(h = s.heapMax + 1; h < HEAP_SIZE; h++)
{
n = s.heap[h];
bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
if(bits > maxLength)
{
bits = maxLength;
overflow++;
}
tree[n * 2 + 1] = (short) bits;
if(n > maxCode)
{
continue;
}
s.blCount[bits]++;
xbits = 0;
if(n >= base)
{
xbits = extra[n - base];
}
f = tree[n * 2];
s.optLen += f * (bits + xbits);
if(stree != null)
{
s.staticLen += f * (stree[n * 2 + 1] + xbits);
}
}
if(overflow == 0)
{
return;
}
do
{
bits = maxLength - 1;
while(s.blCount[bits] == 0)
{
bits--;
}
s.blCount[bits]--;
s.blCount[bits + 1] += 2;
s.blCount[maxLength]--;
overflow -= 2;
} while(overflow > 0);
for(bits = maxLength; bits != 0; bits--)
{
n = s.blCount[bits];
while(n != 0)
{
m = s.heap[--h];
if(m > maxCode)
{
continue;
}
if(tree[m * 2 + 1] != bits)
{
s.optLen += (((long) bits) - (long) tree[m * 2 + 1]) * (long) tree[m * 2];
tree[m * 2 + 1] = (short) bits;
}
n--;
}
}
}
}
