huffman.hpp

Go to the documentation of this file.

//==================================================================================================
/// \file
/// This header-file is part of module \alib_bitbuffer of the \aliblong.
///
/// Copyright 2013-2026 A-Worx GmbH, Germany.
/// Published under #"mainpage_license".
//==================================================================================================
ALIB_EXPORT namespace alib {  namespace bitbuffer { namespace ac_v1 {
 
/// This class, together with sibling #"ac_v1::HuffmanDecoder" implements the well known
/// \https{Huffman compression,en.wikipedia.org/wiki/Huffman_coding}.
/// The class uses type #"BitWriter" to write the bit stream into an underlying
/// #"BitBuffer".
///
/// The use of this class is quite straight forward:
/// - Create an instance of this class
/// - Feed the data to be compressed once to the algorithm using method
///   #"HuffmanEncoder;CountSymbol"
/// - Invoke method #"HuffmanEncoder;Generate"
/// - Feed all data a second time using method
///   #"HuffmanEncoder;Write".
class HuffmanEncoder {
  public:
    static constexpr int   WORD_SIZE      = 32; ///< Codes are stored in two words of size 32
                                                ///< (this constant)
    static constexpr int   MAX_WORDS      = 2;  ///< Codes are stored in two (this constant) words
                                                ///< of size 32.
 
    /// The maximum length of a huffman code.
    /// In theory, with 256 symbols, a maximum code length of 255 could occur. For this, each
    /// next symbol needed to have the double frequency than the previous. Hence, setting the
    /// value to 64, limits the encoded data size to 2^64 symbols, which should be more than
    /// enough for the next decades.
    static constexpr int   MAX_CODE_LENGTH   = 64;
 
    /// Information about the encoding of symbols. The symbol's value (between \c 0 and \c 255)
    /// is not included, but deduced from the objects' position in the symbol array found in
    /// field #"HuffmanEncoder;symbols".
    struct Symbol {
        std::size_t        frequency        =  0;     ///< The number of occurrences of the symbol.
        alib::ShiftOpRHS   wordLength       =  0;     ///< 0: symbol not used, otherwise between 1 and 255.
        uint32_t           words[MAX_WORDS] = {0,0};  ///< The bitcode of the symbol.
    };
 
  protected:
 
    BitWriter&      bw;             ///< The bit writer to use for encoding the data.
    Symbol          symbols[256];   ///< The symbol table.
 
ALIB_DBG( bool      dbgAllValuesAreSame;  )
 
  public:
    /// Constructor.
    /// @param bitWriter  The bit writer to write the encoding information as well as the encoded
    ///                   symbols to. (Stored in field #"bw".)
    HuffmanEncoder( BitWriter& bitWriter )
    : bw(bitWriter)                                                                               {}
 
    /// Counts a symbol.
    /// This method has to be invoked for each byte to compress later.
    /// @param symbol  The symbol to count.
    void CountSymbol(uint8_t symbol)                                { symbols[symbol].frequency++; }
 
    /// Generates the huffman encoding table and writes this information to the bit writer.
    ALIB_DLL
    void Generate();
 
    /// Writes the given \p{symbol} to the bit stream.
    /// @param symbol The symbol to write.
    void Write(uint8_t symbol) {
        auto& rec     = symbols[symbol];
        int   bitsLeft= rec.wordLength;
        #if ALIB_STRINGS
            ALIB_ASSERT_ERROR( (bitsLeft != 0) | dbgAllValuesAreSame, "BITBUFFER/AC/HFMN",
                 "Try to write symbol unknown to Huffman table: {}, ", symbol, bitsLeft )
        #else
            ALIB_ASSERT_ERROR( bitsLeft | dbgAllValuesAreSame, "BITBUFFER/AC/HFMN",
                 "Try to write symbol unknown to Huffman table: ",  symbol )
        #endif
 
 
        auto* word= rec.words;
        if( bitsLeft > 32) {
            bw.WriteBits<32>( *word );
            word++;
            bitsLeft-= 32;
        }
 
        bw.WriteBits(bitsLeft, *word );
    }
 
}; // HuffmanEncoder
 
/// This class, together with sibling #"ac_v1::HuffmanEncoder" implements the well known
/// \https{Huffman compression,en.wikipedia.org/wiki/Huffman_coding}.
/// The class uses type #"BitReader" to read the bit stream from an underlying
/// #"BitBuffer".
///
/// The use of this class is quite straight forward:
/// - Prepare a #"%BitReader" to point to the beginning of the bit stream generated with
///   class #"%HuffmanEncoder".
/// - Invoke method #"HuffmanDecoder;ReadTree" once.
/// - For each encoded byte, invoke #"HuffmanDecoder;Read".
///
/// Note, that the length of the stream (the number of bytes to be decompressed) have to be
/// known by the using software. This class is not responsible for storing this piece of information.
class HuffmanDecoder {
  protected:
    /// Internal struct representing nodes of the huffman code tree.
    struct Node {
        Node*    left;      ///< The left child node.
        Node*    right;     ///< The right child node.
        uint8_t  symbol;    ///< If this is a leaf node (neither #".left" nor #".right" are set,
                            ///< then this is the symbol found.
 
        /// Constructor.
        Node()
        : left      (nullptr)
        , right     (nullptr)                                                                     {}
    };
 
    static constexpr int    MAX_NODES= 511;      ///< The maximum number of nodes in the tree.
 
    BitReader&              br;                  ///< The bit reader given in the constructor.
    Node                    tree;                ///< The root node of the symbol tree.
    Node                    nodePool[MAX_NODES]; ///< Pre-allocated node objects.
    int                     npNext= 0;           ///< The next node in #".nodePool" to use.
 
  public:
    /// Constructor.
    /// @param bitReader The bit reader to read the huffman encoding table and then the encoded
    ///                  symbols from. (Stored in field #".br".)
    HuffmanDecoder( BitReader& bitReader )
    :br(bitReader)                                                                                {}
 
    /// Reads the information to decode the data from the beginning of the bit stream.
    /// This method has to be invoked once before reading the symbols with method #".Read".
    ALIB_DLL
    void ReadTree();
 
    /// Reads a symbol from the bit stream.
    /// This method has to be invoked for every symbol stored, after once reading the encoding
    /// information with method #".ReadTree".
    /// @return The symbol read.
    uint8_t  Read() {
        Node* node= &tree;
        while(true) {
            if( node->left == nullptr) // (could also test on right)
                return node->symbol;
 
            auto v= br.ReadBits<1>();
            node= v ? node->right
                    : node->left;
    }   }
 
}; // HuffmanDecoder
 
}}} // namespace [alib::bitbuffer::ac_v1]