LCOV - code coverage report
Current view: top level - utilities/source - bitstream.cpp (source / functions) Hit Total Coverage
Test: mcrl2_coverage.info.cleaned Lines: 79 88 89.8 %
Date: 2020-02-28 00:44:21 Functions: 15 16 93.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // Author(s): Maurice Laveaux
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //
       9             : 
      10             : #include "mcrl2/utilities/bitstream.h"
      11             : 
      12             : #include "mcrl2/utilities/exception.h"
      13             : #include "mcrl2/utilities/logger.h"
      14             : #include "mcrl2/utilities/unused.h"
      15             : #include "mcrl2/utilities/power_of_two.h"
      16             : 
      17             : #ifdef MCRL2_PLATFORM_WINDOWS
      18             : #include <io.h>
      19             : #include <fcntl.h>
      20             : #endif
      21             : 
      22             : using namespace mcrl2::utilities;
      23             : 
      24             : /// \brief Encodes an unsigned variable-length integer using the most significant bit (MSB) algorithm.
      25             : ///        This function assumes that the value is stored as little endian.
      26             : /// \param value The input value. Any standard integer type is allowed.
      27             : /// \param output A pointer to a piece of reserved memory. Must have a minimum size dependent on the input size (32 bit = 5 bytes, 64 bit = 10 bytes).
      28             : /// \returns The number of bytes used in the output.
      29             : /// \details Implementation taken from https://techoverflow.net/2013/01/25/efficiently-encoding-variable-length-integers-in-cc/
      30             : template<typename int_t = std::size_t>
      31       11507 : static size_t encode_variablesize_int(int_t value, uint8_t* output)
      32             : {
      33       11507 :   size_t outputSize = 0;
      34             : 
      35             :   // While more than 7 bits of data are left, occupy the last output byte
      36             :   // and set the next byte flag.
      37       11521 :   while (value > 127)
      38             :   {
      39             :     // | 128: Sets the next byte flag.
      40           7 :     output[outputSize] = (static_cast<uint8_t>(value & 127)) | 128;
      41             : 
      42             :     // Remove the seven bits we just wrote from value.
      43           7 :     value >>= 7;
      44           7 :     outputSize++;
      45             :   }
      46             : 
      47       11507 :   output[outputSize] = (static_cast<uint8_t>(value));
      48       11507 :   return outputSize + 1;
      49             : }
      50             : 
      51             : /// \brief Decodes an unsigned variable-length integer using the MSB algorithm.
      52             : /// \param stream The stream from which the bytes for this value are read.
      53             : /// \details Implementation taken from https://techoverflow.net/2013/01/25/efficiently-encoding-variable-length-integers-in-cc/, but converted to a streaming
      54             : ///          method.
      55             : template<typename int_t = std::size_t>
      56       11739 : int_t decode_variablesize_int(ibitstream& stream)
      57             : {
      58       11739 :   int_t value = 0;
      59       11746 :   for (size_t i = 0; i < integer_encoding_size<int_t>(); i++)
      60             :   {
      61             :     // Read the next byte from the stream.
      62       11746 :     std::size_t byte = stream.read_bits(8);
      63             : 
      64             :     // Take 7 bits (mask 0x01111111) from byte and shift it before the bits already written to value.
      65       11746 :     value |= (static_cast<int_t>(byte) & 127) << (7 * i);
      66             : 
      67       11746 :     if (!(byte & 128))
      68             :     {
      69             :       // If the next-byte flag is not set then we are finished.
      70       11739 :       break;
      71             :     }
      72           7 :     else if (i == sizeof(int_t))
      73             :     {
      74             :       // The next-byte flag was set, but we cannot represent it using int_t.
      75           0 :       throw std::runtime_error("Fail to read an int from the input");
      76             :     }
      77             :   }
      78             : 
      79       11739 :   return value;
      80             : }
      81             : 
      82             : /// \brief Change the current stream to binary mode (no handle of newline characters),
      83           0 : static void set_stream_binary(const std::string& name, FILE* handle)
      84             : {
      85           0 :   mcrl2::utilities::mcrl2_unused(name, handle);
      86             : #ifdef MCRL2_PLATFORM_WINDOWS
      87             :   if (_setmode(_fileno(handle), _O_BINARY) == -1)
      88             :   {
      89             :     mCRL2log(mcrl2::log::warning) << "Cannot set " << name << " to binary mode.\n";
      90             :   }
      91             :   else
      92             :   {
      93             :     mCRL2log(mcrl2::log::debug) << "Converted " << name << " to binary mode.\n";
      94             :   }
      95             : 
      96             :   fflush(stderr);
      97             : #endif // MCRL2_PLATFORM_WINDOWS
      98           0 : }
      99             : 
     100         131 : obitstream::obitstream(std::ostream& stream)
     101         131 :   : stream(stream)
     102             : {
     103             :   // Ensures that the given stream is changed to binary mode.
     104         131 :   if (stream.rdbuf() == std::cout.rdbuf())
     105             :   {
     106           0 :     set_stream_binary("cout", stdout);
     107             :   }
     108         131 :   else if (stream.rdbuf() == std::cerr.rdbuf())
     109             :   {
     110           0 :     set_stream_binary("cerr", stderr);
     111             :   }
     112         131 : }
     113             : 
     114      125882 : void obitstream::write_bits(std::size_t value, unsigned int number_of_bits)
     115             : {
     116             :   // Add val to the buffer by masking out additional bits and put them at left-most position free in the buffer.
     117      125882 :   write_buffer |= std::bitset<128>(value & ((static_cast<std::size_t>(1) << number_of_bits) - 1)) << ((128 - bits_in_buffer) - number_of_bits);
     118      125882 :   bits_in_buffer += number_of_bits;
     119             : 
     120             :   // Write 8 bytes if available
     121      125882 :   if (bits_in_buffer >= 64)
     122             :   {
     123       12273 :     unsigned long long write_value = (write_buffer >> 64).to_ullong();
     124       12273 :     write_buffer <<= 64;
     125       12273 :     bits_in_buffer -= 64;
     126             : 
     127      110457 :     for (int32_t i = 7; i >= 0; --i)
     128             :     {
     129             :       // Write the 8 * i most significant bits and mask out the other values.
     130       98184 :       stream.put(static_cast<char>((write_value >> (8 * i)) & 255));
     131             :     }
     132             :   }
     133      125882 : }
     134             : 
     135        4896 : void obitstream::write_string(const std::string& string)
     136             : {
     137             :   // Write length.
     138        4896 :   write_integer(string.size());
     139             : 
     140             :   // Write actual string.
     141        4896 :   write(reinterpret_cast<const std::uint8_t*>(string.c_str()), string.size());
     142        4896 : }
     143             : 
     144       11507 : void obitstream::write_integer(std::size_t val)
     145             : {
     146       11507 :   std::size_t nr_bytes = encode_variablesize_int(val, integer_buffer);
     147             : 
     148       11507 :   write(integer_buffer, nr_bytes);
     149       11507 : }
     150             : 
     151         133 : ibitstream::ibitstream(std::istream& stream)
     152         133 :   : stream(stream)
     153             : {
     154             :   // Ensures that the given stream is changed to binary mode.
     155         133 :   if (stream.rdbuf() == std::cin.rdbuf())
     156             :   {
     157           0 :     set_stream_binary("cin", stdin);
     158             :   }
     159         133 : }
     160             : 
     161        5077 : const char* ibitstream::read_string()
     162             : {
     163             :   std::size_t length;
     164             : 
     165             :   // Get length of string.
     166        5077 :   length = read_integer();
     167             : 
     168             :   // Assure buffer can hold the string.
     169        5077 :   if (m_text_buffer.size() < (length + 1))
     170             :   {
     171         263 :     m_text_buffer.resize(round_up_to_power_of_two(length + 1));
     172             :   }
     173             : 
     174             :   // Read the actual string.
     175        5077 :   read(length, reinterpret_cast<std::uint8_t*>(m_text_buffer.data()));
     176        5077 :   m_text_buffer[length] = '\0';
     177             : 
     178        5077 :   return m_text_buffer.data();
     179             : }
     180             : 
     181      129828 : std::size_t ibitstream::read_bits(unsigned int number_of_bits)
     182             : {
     183             :   // Read at most the number of bits of a std::size_t.
     184      129828 :   assert(number_of_bits <= std::numeric_limits<std::size_t>::digits);
     185             : 
     186      331768 :   while (bits_in_buffer < number_of_bits)
     187             :   {
     188             :     // Read bytes until the buffer is sufficiently full.
     189      100970 :     int byte = stream.get();
     190             : 
     191      100970 :     if(stream.fail())
     192             :     {
     193           0 :       throw mcrl2::runtime_error("Failed to read bytes from the input file/stream.");
     194             :     }
     195             : 
     196             :     // Shift the 8 bits to the first free (120 - bits_in_buffer) position in the buffer.
     197      100970 :     read_buffer |= std::bitset<128>(static_cast<std::size_t>(byte)) << (56 + 64 - bits_in_buffer);
     198      100970 :     bits_in_buffer += 8;
     199             :   }
     200             : 
     201             :   // Read nr_bits from the buffer by shifting them to the least significant bits and masking out the remaining bits.
     202      129828 :   std::size_t value = (read_buffer >> (128 - number_of_bits)).to_ullong();
     203             : 
     204             :   // Shift the first bit to the first position in the buffer.
     205      129828 :   read_buffer <<= number_of_bits;
     206      129828 :   bits_in_buffer -= number_of_bits;
     207             : 
     208      129828 :   return value;
     209             : }
     210             : 
     211       11739 : std::size_t ibitstream::read_integer()
     212             : {
     213       11739 :   return decode_variablesize_int(*this);
     214             : }
     215             : 
     216             : // Private functions
     217             : 
     218         131 : void obitstream::flush()
     219             : {
     220             :   // Writing the buffer full to 64 bits should flush it internally, this also guarantees that the unnecessary bits are zeroed out.
     221         131 :   write_bits(0, 64 - bits_in_buffer);
     222         131 :   assert(bits_in_buffer == 0);
     223             : 
     224         131 :   if (stream.fail())
     225             :   {
     226           0 :     throw mcrl2::runtime_error("Failed to write the last byte to the output file/stream.");
     227             :   }
     228             : 
     229         131 :   stream.flush();
     230         131 : }
     231             : 
     232       16403 : void obitstream::write(const uint8_t* buffer, std::size_t size)
     233             : {
     234       64278 :   for (std::size_t index = 0; index < size; ++index)
     235             :   {
     236             :     // Write a single byte for every entry in the buffer that was filled (size).
     237       47875 :     write_bits(buffer[index], 8);
     238             :   }
     239       16403 : }
     240             : 
     241        5077 : void ibitstream::read(std::size_t size, std::uint8_t* buffer)
     242             : {
     243       42445 :   for (std::size_t index = 0; index < size; ++index)
     244             :   {
     245             :     // Read a single byte for every entry into the buffer that was filled (size).
     246       37368 :     std::size_t value = read_bits(8);
     247       37368 :     buffer[index] = static_cast<std::uint8_t>(value);
     248             :   }
     249        5515 : }

Generated by: LCOV version 1.13