Program Listing for File ArithmeticCoding.h

↰ Return to documentation for file (ADS/compression/ArithmeticCoding.h)

/*--------------------------------------------------------------------------*/
/*------------------------ File ArithmeticCoding.h -------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_ArithmeticCoding
 #define __ADS_ArithmeticCoding
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/compression/PackedBits.h"
#include "ADS/numeric/Rational.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <map>
#include <span>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*----------------------- THE EXACT ARITHMETIC CODE ------------------------*/
/*--------------------------------------------------------------------------*/

template< class C >
[[nodiscard]] std::pair< Rational , Rational > arithmeticInterval(
                                   std::span< const C > text ,
                                   const std::map< C , Rational > & prob );

template< class C >
[[nodiscard]] std::string arithmeticCodeExact(
                                   std::span< const C > text ,
                                   const std::map< C , Rational > & prob );

template< class C >
[[nodiscard]] std::vector< C > arithmeticDecodeExact(
                                   const std::string & bits , std::size_t n ,
                                   const std::map< C , Rational > & prob );

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS RangeEncoder ---------------------------*/
/*--------------------------------------------------------------------------*/

class RangeEncoder {

/*--------------------------------------------------------------------------*/
 public:

 explicit RangeEncoder( int w = 32 );

 [[nodiscard]] std::uint64_t maxTotal( void ) const { return( f_M / 4 ); }

 void encode( std::uint64_t low , std::uint64_t high , std::uint64_t total );

 [[nodiscard]] std::vector< std::uint8_t > finish( void );

 [[nodiscard]] std::size_t bits( void ) const { return( f_out.size() ); }

/*--------------------------------------------------------------------------*/
 private:

 void emit( bool b );

 std::uint64_t f_M;
 std::uint64_t f_low = 0;
 std::uint64_t f_high;
 std::size_t f_pending = 0;
 PackedBitWriter f_out;

 };  // end( class RangeEncoder )

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS RangeDecoder ---------------------------*/
/*--------------------------------------------------------------------------*/

class RangeDecoder {

/*--------------------------------------------------------------------------*/
 public:

 explicit RangeDecoder( std::span< const std::uint8_t > bytes , int w = 32 );

 [[nodiscard]] std::uint64_t maxTotal( void ) const { return( f_M / 4 ); }

 [[nodiscard]] std::uint64_t target( std::uint64_t total ) const;

 void consume( std::uint64_t low , std::uint64_t high ,
               std::uint64_t total );

/*--------------------------------------------------------------------------*/
 private:

 std::uint64_t f_M;
 std::uint64_t f_low = 0;
 std::uint64_t f_high;
 std::uint64_t f_v = 0;
 PackedBitReader f_in;

 };  // end( class RangeDecoder )

/*--------------------------------------------------------------------------*/
/*---------------------- THE INTEGER ARITHMETIC CODE -----------------------*/
/*--------------------------------------------------------------------------*/

template< class C >
[[nodiscard]] std::vector< std::uint8_t > arithmeticEncode(
                         std::span< const C > text ,
                         const std::map< C , std::uint64_t > & counts ,
                         int w = 32 );

template< class C >
[[nodiscard]] std::vector< C > arithmeticDecode(
                         std::span< const std::uint8_t > code , std::size_t n ,
                         const std::map< C , std::uint64_t > & counts ,
                         int w = 32 );

[[nodiscard]] inline std::vector< std::uint8_t > adaptiveArithmeticEncode(
                    std::span< const std::uint32_t > x , std::uint32_t sigma );

[[nodiscard]] inline std::vector< std::uint32_t > adaptiveArithmeticDecode(
                    std::span< const std::uint8_t > code , std::size_t n ,
                    std::uint32_t sigma );

[[nodiscard]] inline std::vector< std::uint8_t > adaptiveArithmeticEncode(
                                                         std::string_view s );

[[nodiscard]] inline std::string adaptiveArithmeticDecode(
                    std::span< const std::uint8_t > code , std::size_t n );

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/compression/impl/ArithmeticCoding.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* ArithmeticCoding.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File ArithmeticCoding.h -----------------------*/
/*--------------------------------------------------------------------------*/