// Copyright (c) the JPEG XL Project Authors. All rights reserved.
//
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
#include "lib/jxl/enc_huffman.h"
#include <algorithm>
#include <memory>
#include "lib/jxl/base/status.h"
#include "lib/jxl/enc_huffman_tree.h"
namespace jxl {
namespace {
constexpr
int kCodeLengthCodes = 18;
void StoreHuffmanTreeOfHuffmanTreeToBitMask(
const int num_codes,
const uint8_t* code_length_bitdepth,
BitWriter* writer) {
static const uint8_t kStorageOrder[kCodeLengthCodes] = {
1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15};
// The bit lengths of the Huffman code over the code length alphabet
// are compressed with the following static Huffman code:
// Symbol Code
// ------ ----
// 0 00
// 1 1110
// 2 110
// 3 01
// 4 10
// 5 1111
static const uint8_t kHuffmanBitLengthHuffmanCodeSymbols[6] = {0, 7, 3,
2, 1, 15};
static const uint8_t kHuffmanBitLengthHuffmanCodeBitLengths[6] = {2, 4, 3,
2, 2, 4};
// Throw away trailing zeros:
size_t codes_to_store = kCodeLengthCodes;
if (num_codes > 1) {
for (; codes_to_store > 0; --codes_to_store) {
if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) {
break;
}
}
}
size_t skip_some = 0;
// skips none.
if (code_length_bitdepth[kStorageOrder[0]] == 0 &&
code_length_bitdepth[kStorageOrder[1]] == 0) {
skip_some = 2;
// skips two.
if (code_length_bitdepth[kStorageOrder[2]] == 0) {
skip_some = 3;
// skips three.
}
}
writer->Write(2, skip_some);
for (size_t i = skip_some; i < codes_to_store; ++i) {
size_t l = code_length_bitdepth[kStorageOrder[i]];
writer->Write(kHuffmanBitLengthHuffmanCodeBitLengths[l],
kHuffmanBitLengthHuffmanCodeSymbols[l]);
}
}
Status StoreHuffmanTreeToBitMask(
const size_t huffman_tree_size,
const uint8_t* huffman_tree,
const uint8_t* huffman_tree_extra_bits,
const uint8_t* code_length_bitdepth,
const uint16_t* code_length_bitdepth_symbols,
BitWriter* writer) {
for (size_t i = 0; i < huffman_tree_size; ++i) {
size_t ix = huffman_tree[i];
writer->Write(code_length_bitdepth[ix], code_length_bitdepth_symbols[ix]);
JXL_ENSURE(ix <= 17);
// Extra bits
switch (ix) {
case 16:
writer->Write(2, huffman_tree_extra_bits[i]);
break;
case 17:
writer->Write(3, huffman_tree_extra_bits[i]);
break;
default:
// no-op
break;
}
}
return true;
}
void StoreSimpleHuffmanTree(
const uint8_t* depths, size_t symbols[4],
size_t num_symbols, size_t max_bits,
BitWriter* writer) {
// value of 1 indicates a simple Huffman code
writer->Write(2, 1);
writer->Write(2, num_symbols - 1);
// NSYM - 1
// Sort
for (size_t i = 0; i < num_symbols; i++) {
for (size_t j = i + 1; j < num_symbols; j++) {
if (depths[symbols[j]] < depths[symbols[i]]) {
std::swap(symbols[j], symbols[i]);
}
}
}
if (num_symbols == 2) {
writer->Write(max_bits, symbols[0]);
writer->Write(max_bits, symbols[1]);
}
else if (num_symbols == 3) {
writer->Write(max_bits, symbols[0]);
writer->Write(max_bits, symbols[1]);
writer->Write(max_bits, symbols[2]);
}
else {
writer->Write(max_bits, symbols[0]);
writer->Write(max_bits, symbols[1]);
writer->Write(max_bits, symbols[2]);
writer->Write(max_bits, symbols[3]);
// tree-select
writer->Write(1, depths[symbols[0]] == 1 ? 1 : 0);
}
}
// num = alphabet size
// depths = symbol depths
Status StoreHuffmanTree(
const uint8_t* depths, size_t num, BitWriter* writer) {
// Write the Huffman tree into the compact representation.
std::unique_ptr<uint8_t[]> arena(
new uint8_t[2 * num]);
uint8_t* huffman_tree = arena.get();
uint8_t* huffman_tree_extra_bits = arena.get() + num;
size_t huffman_tree_size = 0;
WriteHuffmanTree(depths, num, &huffman_tree_size, huffman_tree,
huffman_tree_extra_bits);
// Calculate the statistics of the Huffman tree in the compact representation.
uint32_t huffman_tree_histogram[kCodeLengthCodes] = {0};
for (size_t i = 0; i < huffman_tree_size; ++i) {
++huffman_tree_histogram[huffman_tree[i]];
}
int num_codes = 0;
int code = 0;
for (
int i = 0; i < kCodeLengthCodes; ++i) {
if (huffman_tree_histogram[i]) {
if (num_codes == 0) {
code = i;
num_codes = 1;
}
else if (num_codes == 1) {
num_codes = 2;
break;
}
}
}
// Calculate another Huffman tree to use for compressing both the
// earlier Huffman tree with.
uint8_t code_length_bitdepth[kCodeLengthCodes] = {0};
uint16_t code_length_bitdepth_symbols[kCodeLengthCodes] = {0};
CreateHuffmanTree(&huffman_tree_histogram[0], kCodeLengthCodes, 5,
&code_length_bitdepth[0]);
ConvertBitDepthsToSymbols(code_length_bitdepth, kCodeLengthCodes,
&code_length_bitdepth_symbols[0]);
// Now, we have all the data, let's start storing it
StoreHuffmanTreeOfHuffmanTreeToBitMask(num_codes, code_length_bitdepth,
writer);
if (num_codes == 1) {
code_length_bitdepth[code] = 0;
}
// Store the real huffman tree now.
JXL_RETURN_IF_ERROR(StoreHuffmanTreeToBitMask(
huffman_tree_size, huffman_tree, huffman_tree_extra_bits,
&code_length_bitdepth[0], code_length_bitdepth_symbols, writer));
return true;
}
}
// namespace
Status BuildAndStoreHuffmanTree(
const uint32_t* histogram,
const size_t length,
uint8_t* depth, uint16_t* bits,
BitWriter* writer) {
size_t count = 0;
size_t s4[4] = {0};
for (size_t i = 0; i < length; i++) {
if (histogram[i]) {
if (count < 4) {
s4[count] = i;
}
else if (count > 4) {
break;
}
count++;
}
}
size_t max_bits_counter = length - 1;
size_t max_bits = 0;
while (max_bits_counter) {
max_bits_counter >>= 1;
++max_bits;
}
if (count <= 1) {
// Output symbol bits and depths are initialized with 0, nothing to do.
writer->Write(4, 1);
writer->Write(max_bits, s4[0]);
return true;
}
CreateHuffmanTree(histogram, length, 15, depth);
ConvertBitDepthsToSymbols(depth, length, bits);
if (count <= 4) {
StoreSimpleHuffmanTree(depth, s4, count, max_bits, writer);
}
else {
JXL_RETURN_IF_ERROR(StoreHuffmanTree(depth, length, writer));
}
return true;
}
}
// namespace jxl
