huffman.hpp

Go to the documentation of this file.

//==================================================================================================
/// \file
/// This header file is part of module \alib_bitbuffer of the \aliblong.
///
/// \emoji :copyright: 2013-2024 A-Worx GmbH, Germany.
/// Published under \ref mainpage_license "Boost Software License".
//==================================================================================================
#ifndef HPP_ALIB_BITBUFFER_AC_V1_HUFFMAN
#define HPP_ALIB_BITBUFFER_AC_V1_HUFFMAN 1
#pragma once
#include "alib/bitbuffer/bitbuffer.hpp"
#include "alib/strings/localstring.hpp"
 
namespace alib {  namespace bitbuffer { namespace ac_v1 {
 
/// This class, together with sibling \alib{bitbuffer::ac_v1;HuffmanDecoder} implements the well known
/// \https{Huffman compression,en.wikipedia.org/wiki/Huffman_coding}.
/// The class uses type \alib{bitbuffer;BitWriter} to write the bit stream into an underlying
/// \alib{bitbuffer;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
///   \alib{bitbuffer::ac_v1::HuffmanEncoder;CountSymbol}
/// - Invoke method \alib{bitbuffer::ac_v1::HuffmanEncoder;Generate}
/// - Feed all data a second time using method
///   \alib{bitbuffer::ac_v1::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 enaugh
        /// 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 \alib{bitbuffer::ac_v1::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.
        ALIB_FORCE_INLINE
        void CountSymbol(uint8_t symbol)
        {
            ALIB_WARNINGS_ALLOW_UNSAFE_BUFFER_USAGE
            symbols[symbol].frequency++;
            ALIB_WARNINGS_RESTORE
        }
 
    /// Generates the huffman encoding table and writes this information to the bit writer.
    ALIB_API
    void Generate();
 
    /// Writes the given \p symbol to the bit stream.
    /// @param symbol The symbol to write.
    void Write(uint8_t symbol)
    {
        ALIB_WARNINGS_ALLOW_UNSAFE_BUFFER_USAGE
        auto& rec     = symbols[symbol];
        int   bitsLeft= rec.wordLength;
        #if ALIB_STRINGS
            ALIB_ASSERT_ERROR( (bitsLeft != 0) | dbgAllValuesAreSame, "BITBUFFER/AC/HFMN",
                               NString256("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.Write<32>( *word );
            word++;
            bitsLeft-= 32;
        }
        ALIB_WARNINGS_RESTORE
 
        bw.Write(bitsLeft, *word );
    }
 
}; // HuffmanEncoder
 
/// This class, together with sibling \alib{bitbuffer::ac_v1;HuffmanEncoder} implements the well known
/// \https{Huffman compression,en.wikipedia.org/wiki/Huffman_coding}.
/// The class uses type \alib{bitbuffer;BitReader} to read the bit stream from an underlying
/// \alib{bitbuffer;BitBuffer}.
///
/// The use of this class is quite straight forward:
/// - Prepare a \b BitReader to point to the beginning of the bit stream generated with
///   class \b HuffmanEncoder.
/// - Invoke method \alib{bitbuffer::ac_v1::HuffmanDecoder;ReadTree} once.
/// - For each encoded byte, invoke \alib{bitbuffer::ac_v1::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
                                ///< 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_API
    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.Read<1>();
            node= v ? node->right
                    : node->left;
        }
    }
 
}; // HuffmanDecoder
 
}}} // namespace [alib::bitbuffer::ac_v1]
 
#endif // HPP_ALIB_BITBUFFER_AC_V1_HUFFMAN