Program Listing for File IntegerCodes.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File IntegerCodes.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/combinatorial/Bitwise.h"
#include "ADS/succinct/BitStream.h"
#include "ADS/succinct/BitVector.h"

#include <algorithm>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <vector>

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

namespace ADS {

/*---------------------------- PREPROCESSING -------------------------------*/

[[nodiscard]] constexpr int binaryLength( std::uint64_t x );

[[nodiscard]] constexpr std::uint64_t signedToNatural( std::int64_t x );

[[nodiscard]] constexpr std::int64_t naturalToSigned( std::uint64_t y );

[[nodiscard]] inline std::vector< std::uint64_t > dGaps(
                                     const std::vector< std::uint64_t > & x );

[[nodiscard]] inline std::vector< std::uint64_t > prefixSums(
                                     const std::vector< std::uint64_t > & g );

/*------------------------------ UNARY, GAMMA, DELTA -----------------------*/

inline void encodeUnary( BitWriter & w , std::uint64_t x );
[[nodiscard]] inline std::uint64_t decodeUnary( BitReader & r );
[[nodiscard]] constexpr std::uint64_t unaryLength( std::uint64_t x );

inline void encodeGamma( BitWriter & w , std::uint64_t x );
[[nodiscard]] inline std::uint64_t decodeGamma( BitReader & r );
[[nodiscard]] constexpr int gammaLength( std::uint64_t x );

inline void encodeDelta( BitWriter & w , std::uint64_t x );
[[nodiscard]] inline std::uint64_t decodeDelta( BitReader & r );
[[nodiscard]] constexpr int deltaLength( std::uint64_t x );

/*------------------------------ RICE, GOLOMB ------------------------------*/

inline void encodeRice( BitWriter & w , std::uint64_t x , int k );
[[nodiscard]] inline std::uint64_t decodeRice( BitReader & r , int k );
[[nodiscard]] constexpr std::uint64_t riceLength( std::uint64_t x , int k );

inline void encodeGolomb( BitWriter & w , std::uint64_t x , std::uint64_t b );
[[nodiscard]] inline std::uint64_t decodeGolomb( BitReader & r ,
                                                 std::uint64_t b );
[[nodiscard]] constexpr std::uint64_t golombLength( std::uint64_t x ,
                                                    std::uint64_t b );

/*-------------------------------- PFORDELTA -------------------------------*/

struct PForDeltaBlock {
 int b = 1;
 std::uint64_t base = 0;
 BitVector slots;
 std::vector< std::uint64_t > exceptions;

 [[nodiscard]] std::size_t size( void ) const;

 [[nodiscard]] std::size_t codeBits( void ) const;
 };

[[nodiscard]] inline int pforDeltaWidth(
                                    const std::vector< std::uint64_t > & x ,
                                    std::uint64_t base , double f = 0.9 );

[[nodiscard]] inline PForDeltaBlock encodePForDelta(
                                   const std::vector< std::uint64_t > & x ,
                                   int b , std::uint64_t base = 0 );
[[nodiscard]] inline std::vector< std::uint64_t > decodePForDelta(
                                                 const PForDeltaBlock & p );

/*---------------------- VARIABLE BYTE, (s,c)-DENSE ------------------------*/

inline void encodeVByte( std::vector< std::uint8_t > & out , std::uint64_t x );

[[nodiscard]] inline std::uint64_t decodeVByte(
                                      const std::vector< std::uint8_t > & in ,
                                      std::size_t & p );

[[nodiscard]] constexpr int vbyteLength( std::uint64_t x );

inline void encodeDense( std::vector< std::uint32_t > & out , std::uint64_t x ,
                         std::uint32_t s , std::uint32_t c );

[[nodiscard]] inline std::uint64_t decodeDense(
                                     const std::vector< std::uint32_t > & in ,
                                     std::size_t & p , std::uint32_t s ,
                                     std::uint32_t c );

[[nodiscard]] constexpr int denseLength( std::uint64_t x , std::uint32_t s ,
                                         std::uint32_t c );

[[nodiscard]] inline std::uint32_t denseOptimalS(
                       const std::vector< std::uint64_t > & f , int bits = 8 );

/*------------------------------ INTERPOLATIVE -----------------------------*/

inline void encodeBounded( BitWriter & w , std::uint64_t x ,
                             std::uint64_t a , std::uint64_t b );
[[nodiscard]] inline std::uint64_t decodeBounded( BitReader & r ,
                                                    std::uint64_t a ,
                                                    std::uint64_t b );

inline void encodeInterpolative( BitWriter & w ,
                                 const std::vector< std::uint64_t > & x ,
                                 std::uint64_t low , std::uint64_t hi );

[[nodiscard]] inline std::vector< std::uint64_t > decodeInterpolative(
                                       BitReader & r , std::size_t n ,
                                       std::uint64_t low , std::uint64_t hi );

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

}  // end( namespace ADS )

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

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

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

#endif  /* IntegerCodes.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File IntegerCodes.h ------------------------*/
/*--------------------------------------------------------------------------*/