src/SDL2/external/libwebp-0.3.0/src/utils/huffman.h

   1 // Copyright 2012 Google Inc. All Rights Reserved.
   2 //
   3 // This code is licensed under the same terms as WebM:
   4 //  Software License Agreement:  http://www.webmproject.org/license/software/
   5 //  Additional IP Rights Grant:  http://www.webmproject.org/license/additional/
   6 // -----------------------------------------------------------------------------
   7 //
   8 // Utilities for building and looking up Huffman trees.
   9 //
  10 // Author: Urvang Joshi (urvang@google.com)
  11
  12 #ifndef WEBP_UTILS_HUFFMAN_H_
  13 #define WEBP_UTILS_HUFFMAN_H_
  14
  15 #include <assert.h>
  16 #include "../webp/types.h"
  17
  18 #if defined(__cplusplus) || defined(c_plusplus)
  19 extern "C" {
  20 #endif
  21
  22 // A node of a Huffman tree.
  23 typedef struct {
  24   int symbol_;
  25   int children_;  // delta offset to both children (contiguous) or 0 if leaf.
  26 } HuffmanTreeNode;
  27
  28 // Huffman Tree.
  29 typedef struct HuffmanTree HuffmanTree;
  30 struct HuffmanTree {
  31   HuffmanTreeNode* root_;   // all the nodes, starting at root.
  32   int max_nodes_;           // max number of nodes
  33   int num_nodes_;           // number of currently occupied nodes
  34 };
  35
  36 // Returns true if the given node is a leaf of the Huffman tree.
  37 static WEBP_INLINE int HuffmanTreeNodeIsLeaf(
  38     const HuffmanTreeNode* const node) {
  39   return (node->children_ == 0);
  40 }
  41
  42 // Go down one level. Most critical function. 'right_child' must be 0 or 1.
  43 static WEBP_INLINE const HuffmanTreeNode* HuffmanTreeNextNode(
  44     const HuffmanTreeNode* node, int right_child) {
  45   return node + node->children_ + right_child;
  46 }
  47
  48 // Releases the nodes of the Huffman tree.
  49 // Note: It does NOT free 'tree' itself.
  50 void HuffmanTreeRelease(HuffmanTree* const tree);
  51
  52 // Builds Huffman tree assuming code lengths are implicitly in symbol order.
  53 // Returns false in case of error (invalid tree or memory error).
  54 int HuffmanTreeBuildImplicit(HuffmanTree* const tree,
  55                              const int* const code_lengths,
  56                              int code_lengths_size);
  57
  58 // Build a Huffman tree with explicitly given lists of code lengths, codes
  59 // and symbols. Verifies that all symbols added are smaller than max_symbol.
  60 // Returns false in case of an invalid symbol, invalid tree or memory error.
  61 int HuffmanTreeBuildExplicit(HuffmanTree* const tree,
  62                              const int* const code_lengths,
  63                              const int* const codes,
  64                              const int* const symbols, int max_symbol,
  65                              int num_symbols);
  66
  67 // Utility: converts Huffman code lengths to corresponding Huffman codes.
  68 // 'huff_codes' should be pre-allocated.
  69 // Returns false in case of error (memory allocation, invalid codes).
  70 int HuffmanCodeLengthsToCodes(const int* const code_lengths,
  71                               int code_lengths_size, int* const huff_codes);
  72
  73
  74 #if defined(__cplusplus) || defined(c_plusplus)
  75 }    // extern "C"
  76 #endif
  77
  78 #endif  // WEBP_UTILS_HUFFMAN_H_