in java/src/main/java/com/epam/deltix/zstd/Huffman.java [45:117]
public int readTable(final ByteBuffer inputBase, final int inputAddress, final int size) {
Arrays.fill(ranks, 0);
int input = inputAddress;
// read table header
verify(size > 0, input, "Not enough input bytes");
int inputSize = inputBase.get(input++) & 0xFF;
final int outputSize;
if (inputSize >= 128) {
outputSize = inputSize - 127;
inputSize = ((outputSize + 1) / 2);
verify(inputSize + 1 <= size, input, "Not enough input bytes");
verify(outputSize <= MAX_SYMBOL + 1, input, "Input is corrupted");
for (int i = 0; i < outputSize; i += 2) {
final int value = inputBase.get(input + i / 2) & 0xFF;
weights[i] = (byte) (value >>> 4);
weights[i + 1] = (byte) (value & 0b1111);
}
} else {
verify(inputSize + 1 <= size, input, "Not enough input bytes");
outputSize = finiteStateEntropy.decompress(inputBase, input, input + inputSize, weights);
}
int totalWeight = 0;
for (int i = 0; i < outputSize; i++) {
ranks[weights[i]]++;
totalWeight += (1 << weights[i]) >> 1; // TODO same as 1 << (weights[n] - 1)?
}
verify(totalWeight != 0, input, "Input is corrupted");
tableLog = Util.highestBit(totalWeight) + 1;
verify(tableLog <= MAX_TABLE_LOG, input, "Input is corrupted");
final int total = 1 << tableLog;
final int rest = total - totalWeight;
verify(isPowerOf2(rest), input, "Input is corrupted");
final int lastWeight = Util.highestBit(rest) + 1;
weights[outputSize] = (byte) lastWeight;
ranks[lastWeight]++;
final int numberOfSymbols = outputSize + 1;
// populate table
int nextRankStart = 0;
for (int i = 1; i < tableLog + 1; ++i) {
final int current = nextRankStart;
nextRankStart += ranks[i] << (i - 1);
ranks[i] = current;
}
for (int n = 0; n < numberOfSymbols; n++) {
final int weight = weights[n];
final int length = (1 << weight) >> 1; // TODO: 1 << (weight - 1) ??
final byte symbol = (byte) n;
final byte numberOfBits = (byte) (tableLog + 1 - weight);
for (int i = ranks[weight]; i < ranks[weight] + length; i++) {
symbols[i] = symbol;
numbersOfBits[i] = numberOfBits;
}
ranks[weight] += length;
}
verify(ranks[1] >= 2 && (ranks[1] & 1) == 0, input, "Input is corrupted");
return inputSize + 1;
}