// 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_tree.h"

// Suppress any -Wdeprecated-declarations warning that might be emitted by

// GCC or Clang by std::stable_sort in C++17 or later mode

#ifdef __clang__

#pragma clang diagnostic push

#pragma clang diagnostic ignored "-Wdeprecated-declarations"

#elif defined(__GNUC__)

#pragma GCC push_options

#pragma GCC diagnostic ignored "-Wdeprecated-declarations"

#endif

#include <algorithm>

#ifdef __clang__

#pragma clang diagnostic pop

#elif defined(__GNUC__)

#pragma GCC pop_options

#endif

#include <limits>

#include <vector>

#include "lib/jxl/base/status.h"

namespace jxl {

void SetDepth(const HuffmanTree& p, HuffmanTree* pool, uint8_t* depth,

              uint8_t level) {

  if (p.index_left >= 0) {

    ++level;

    SetDepth(pool[p.index_left], pool, depth, level);

    SetDepth(pool[p.index_right_or_value], pool, depth, level);

  } else {

    depth[p.index_right_or_value] = level;

  }

}

// Sort the root nodes, least popular first.

static JXL_INLINE bool Compare(const HuffmanTree& v0, const HuffmanTree& v1) {

  return v0.total_count < v1.total_count;

}

// This function will create a Huffman tree.

//

// The catch here is that the tree cannot be arbitrarily deep.

// Brotli specifies a maximum depth of 15 bits for "code trees"

// and 7 bits for "code length code trees."

//

// count_limit is the value that is to be faked as the minimum value

// and this minimum value is raised until the tree matches the

// maximum length requirement.

//

// This algorithm is not of excellent performance for very long data blocks,

// especially when population counts are longer than 2**tree_limit, but

// we are not planning to use this with extremely long blocks.

//

// See http://en.wikipedia.org/wiki/Huffman_coding

void CreateHuffmanTree(const uint32_t* data, const size_t length,

                       const int tree_limit, uint8_t* depth) {

  // For block sizes below 64 kB, we never need to do a second iteration

  // of this loop. Probably all of our block sizes will be smaller than

  // that, so this loop is mostly of academic interest. If we actually

  // would need this, we would be better off with the Katajainen algorithm.

  for (uint32_t count_limit = 1;; count_limit *= 2) {

    std::vector<HuffmanTree> tree;

    tree.reserve(2 * length + 1);

    for (size_t i = length; i != 0;) {

      --i;

      if (data[i]) {

        const uint32_t count = std::max(data[i], count_limit - 1);

        tree.emplace_back(count, -1, static_cast<int16_t>(i));

      }

    }

    const size_t n = tree.size();

    if (n == 1) {

      // Fake value; will be fixed on upper level.

      depth[tree[0].index_right_or_value] = 1;

      break;

    }

    std::stable_sort(tree.begin(), tree.end(), Compare);

    // The nodes are:

    // [0, n): the sorted leaf nodes that we start with.

    // [n]: we add a sentinel here.

    // [n + 1, 2n): new parent nodes are added here, starting from

    //              (n+1). These are naturally in ascending order.

    // [2n]: we add a sentinel at the end as well.

    // There will be (2n+1) elements at the end.

    const HuffmanTree sentinel(std::numeric_limits<uint32_t>::max(), -1, -1);

    tree.push_back(sentinel);

    tree.push_back(sentinel);

    size_t i = 0;      // Points to the next leaf node.

    size_t j = n + 1;  // Points to the next non-leaf node.

    for (size_t k = n - 1; k != 0; --k) {

      size_t left;

      size_t right;

      if (tree[i].total_count <= tree[j].total_count) {

        left = i;

        ++i;

      } else {

        left = j;

        ++j;

      }

      if (tree[i].total_count <= tree[j].total_count) {

        right = i;

        ++i;

      } else {

        right = j;

        ++j;

      }

      // The sentinel node becomes the parent node.

      size_t j_end = tree.size() - 1;

      tree[j_end].total_count =

          tree[left].total_count + tree[right].total_count;

      tree[j_end].index_left = static_cast<int16_t>(left);

      tree[j_end].index_right_or_value = static_cast<int16_t>(right);

      // Add back the last sentinel node.

      tree.push_back(sentinel);

    }

    JXL_DASSERT(tree.size() == 2 * n + 1);

    SetDepth(tree[2 * n - 1], tree.data(), depth, 0);

    // We need to pack the Huffman tree in tree_limit bits.

    // If this was not successful, add fake entities to the lowest values

    // and retry.

    if (*std::max_element(&depth[0], &depth[length]) <= tree_limit) {

      break;

    }

  }

}

void Reverse(uint8_t* v, size_t start, size_t end) {

  --end;

  while (start < end) {

    uint8_t tmp = v[start];

    v[start] = v[end];

    v[end] = tmp;

    ++start;

    --end;

  }

}

void WriteHuffmanTreeRepetitions(const uint8_t previous_value,

                                 const uint8_t value, size_t repetitions,

                                 size_t* tree_size, uint8_t* tree,

                                 uint8_t* extra_bits_data) {

  JXL_DASSERT(repetitions > 0);

  if (previous_value != value) {

    tree[*tree_size] = value;

    extra_bits_data[*tree_size] = 0;

    ++(*tree_size);

    --repetitions;

  }

  if (repetitions == 7) {

    tree[*tree_size] = value;

    extra_bits_data[*tree_size] = 0;

    ++(*tree_size);

    --repetitions;

  }

  if (repetitions < 3) {

    for (size_t i = 0; i < repetitions; ++i) {

      tree[*tree_size] = value;

      extra_bits_data[*tree_size] = 0;

      ++(*tree_size);

    }

  } else {

    repetitions -= 3;

    size_t start = *tree_size;

    while (true) {

      tree[*tree_size] = 16;

      extra_bits_data[*tree_size] = repetitions & 0x3;

      ++(*tree_size);

      repetitions >>= 2;

      if (repetitions == 0) {

        break;

      }

      --repetitions;

    }

    Reverse(tree, start, *tree_size);

    Reverse(extra_bits_data, start, *tree_size);

  }

}

void WriteHuffmanTreeRepetitionsZeros(size_t repetitions, size_t* tree_size,

                                      uint8_t* tree, uint8_t* extra_bits_data) {

  if (repetitions == 11) {

    tree[*tree_size] = 0;

    extra_bits_data[*tree_size] = 0;

    ++(*tree_size);

    --repetitions;

  }

  if (repetitions < 3) {

    for (size_t i = 0; i < repetitions; ++i) {

      tree[*tree_size] = 0;

      extra_bits_data[*tree_size] = 0;

      ++(*tree_size);

    }

  } else {

    repetitions -= 3;

    size_t start = *tree_size;

    while (true) {

      tree[*tree_size] = 17;

      extra_bits_data[*tree_size] = repetitions & 0x7;

      ++(*tree_size);

      repetitions >>= 3;

      if (repetitions == 0) {

        break;

      }

      --repetitions;

    }

    Reverse(tree, start, *tree_size);

    Reverse(extra_bits_data, start, *tree_size);

  }

}

static void DecideOverRleUse(const uint8_t* depth, const size_t length,

                             bool* use_rle_for_non_zero,

                             bool* use_rle_for_zero) {

  size_t total_reps_zero = 0;

  size_t total_reps_non_zero = 0;

  size_t count_reps_zero = 1;

  size_t count_reps_non_zero = 1;

  for (size_t i = 0; i < length;) {

    const uint8_t value = depth[i];

    size_t reps = 1;

    for (size_t k = i + 1; k < length && depth[k] == value; ++k) {

      ++reps;

    }

    if (reps >= 3 && value == 0) {

      total_reps_zero += reps;

      ++count_reps_zero;

    }

    if (reps >= 4 && value != 0) {

      total_reps_non_zero += reps;

      ++count_reps_non_zero;

    }

    i += reps;

  }

  *use_rle_for_non_zero = total_reps_non_zero > count_reps_non_zero * 2;

  *use_rle_for_zero = total_reps_zero > count_reps_zero * 2;

}

void WriteHuffmanTree(const uint8_t* depth, size_t length, size_t* tree_size,

                      uint8_t* tree, uint8_t* extra_bits_data) {

  uint8_t previous_value = 8;

  // Throw away trailing zeros.

  size_t new_length = length;

  for (size_t i = 0; i < length; ++i) {

    if (depth[length - i - 1] == 0) {

      --new_length;

    } else {

      break;

    }

  }

  // First gather statistics on if it is a good idea to do rle.

  bool use_rle_for_non_zero = false;

  bool use_rle_for_zero = false;

  if (length > 50) {

    // Find rle coding for longer codes.

    // Shorter codes seem not to benefit from rle.

    DecideOverRleUse(depth, new_length, &use_rle_for_non_zero,

                     &use_rle_for_zero);

  }

  // Actual rle coding.

  for (size_t i = 0; i < new_length;) {

    const uint8_t value = depth[i];

    size_t reps = 1;

    if ((value != 0 && use_rle_for_non_zero) ||

        (value == 0 && use_rle_for_zero)) {

      for (size_t k = i + 1; k < new_length && depth[k] == value; ++k) {

        ++reps;

      }

    }

    if (value == 0) {

      WriteHuffmanTreeRepetitionsZeros(reps, tree_size, tree, extra_bits_data);

    } else {

      WriteHuffmanTreeRepetitions(previous_value, value, reps, tree_size, tree,

                                  extra_bits_data);

      previous_value = value;

    }

    i += reps;

  }

}

namespace {

uint16_t ReverseBits(int num_bits, uint16_t bits) {

  static const size_t kLut[16] = {// Pre-reversed 4-bit values.

                                  0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,

                                  0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf};

  size_t retval = kLut[bits & 0xf];

  for (int i = 4; i < num_bits; i += 4) {

    retval <<= 4;

    bits = static_cast<uint16_t>(bits >> 4);

    retval |= kLut[bits & 0xf];

  }

  retval >>= (-num_bits & 0x3);

  return static_cast<uint16_t>(retval);

}

}  // namespace

void ConvertBitDepthsToSymbols(const uint8_t* depth, size_t len,

                               uint16_t* bits) {

  // In Brotli, all bit depths are [1..15]

  // 0 bit depth means that the symbol does not exist.

  const int kMaxBits = 16;  // 0..15 are values for bits

  uint16_t bl_count[kMaxBits] = {0};

  {

    for (size_t i = 0; i < len; ++i) {

      ++bl_count[depth[i]];

    }

    bl_count[0] = 0;

  }

  uint16_t next_code[kMaxBits];

  next_code[0] = 0;

  {

    int code = 0;

    for (size_t i = 1; i < kMaxBits; ++i) {

      code = (code + bl_count[i - 1]) << 1;

      next_code[i] = static_cast<uint16_t>(code);

    }

  }

  for (size_t i = 0; i < len; ++i) {

    if (depth[i]) {

      bits[i] = ReverseBits(depth[i], next_code[depth[i]]++);

    }

  }

}

}  // namespace jxl