diff options
| -rw-r--r-- | Tests/LibCore/TestLibCoreStream.cpp | 115 | ||||
| -rw-r--r-- | Userland/Libraries/LibCore/BitStream.h | 166 |
2 files changed, 281 insertions, 0 deletions
diff --git a/Tests/LibCore/TestLibCoreStream.cpp b/Tests/LibCore/TestLibCoreStream.cpp index 945302791a..f5c7b66044 100644 --- a/Tests/LibCore/TestLibCoreStream.cpp +++ b/Tests/LibCore/TestLibCoreStream.cpp @@ -6,6 +6,7 @@ #include <AK/Format.h> #include <AK/String.h> +#include <LibCore/BitStream.h> #include <LibCore/EventLoop.h> #include <LibCore/LocalServer.h> #include <LibCore/MemoryStream.h> @@ -559,3 +560,117 @@ TEST_CASE(allocating_memory_stream_10kb) offset += file_span.size(); } } + +// Bit stream tests + +// Note: This does not do any checks on the internal representation, it just ensures that the behavior of the input and output streams match. +TEST_CASE(little_endian_bit_stream_input_output_match) +{ + auto memory_stream = make<Core::Stream::AllocatingMemoryStream>(); + + // Note: The bit stream only ever reads from/writes to the underlying stream in one byte chunks, + // so testing with sizes that will not trigger a write will yield unexpected results. + auto bit_write_stream = MUST(Core::Stream::LittleEndianOutputBitStream::construct(Core::Stream::Handle<Core::Stream::Stream>(*memory_stream))); + auto bit_read_stream = MUST(Core::Stream::LittleEndianInputBitStream::construct(Core::Stream::Handle<Core::Stream::Stream>(*memory_stream))); + + // Test two mirrored chunks of a fully mirrored pattern to check that we are not dropping bits. + { + MUST(bit_write_stream->write_bits(0b1111u, 4)); + MUST(bit_write_stream->write_bits(0b1111u, 4)); + auto result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b1111u, result); + result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b1111u, result); + } + { + MUST(bit_write_stream->write_bits(0b0000u, 4)); + MUST(bit_write_stream->write_bits(0b0000u, 4)); + auto result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b0000u, result); + result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b0000u, result); + } + + // Test two mirrored chunks of a non-mirrored pattern to check that we are writing bits within a pattern in the correct order. + { + MUST(bit_write_stream->write_bits(0b1000u, 4)); + MUST(bit_write_stream->write_bits(0b1000u, 4)); + auto result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b1000u, result); + result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b1000u, result); + } + + // Test two different chunks to check that we are not confusing their order. + { + MUST(bit_write_stream->write_bits(0b1000u, 4)); + MUST(bit_write_stream->write_bits(0b0100u, 4)); + auto result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b1000u, result); + result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b0100u, result); + } + + // Test a pattern that spans multiple bytes. + { + MUST(bit_write_stream->write_bits(0b1101001000100001u, 16)); + auto result = MUST(bit_read_stream->read_bits(16)); + EXPECT_EQ(0b1101001000100001u, result); + } +} + +// Note: This does not do any checks on the internal representation, it just ensures that the behavior of the input and output streams match. +TEST_CASE(big_endian_bit_stream_input_output_match) +{ + auto memory_stream = make<Core::Stream::AllocatingMemoryStream>(); + + // Note: The bit stream only ever reads from/writes to the underlying stream in one byte chunks, + // so testing with sizes that will not trigger a write will yield unexpected results. + auto bit_write_stream = MUST(Core::Stream::BigEndianOutputBitStream::construct(Core::Stream::Handle<Core::Stream::Stream>(*memory_stream))); + auto bit_read_stream = MUST(Core::Stream::BigEndianInputBitStream::construct(Core::Stream::Handle<Core::Stream::Stream>(*memory_stream))); + + // Test two mirrored chunks of a fully mirrored pattern to check that we are not dropping bits. + { + MUST(bit_write_stream->write_bits(0b1111u, 4)); + MUST(bit_write_stream->write_bits(0b1111u, 4)); + auto result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b1111u, result); + result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b1111u, result); + } + { + MUST(bit_write_stream->write_bits(0b0000u, 4)); + MUST(bit_write_stream->write_bits(0b0000u, 4)); + auto result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b0000u, result); + result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b0000u, result); + } + + // Test two mirrored chunks of a non-mirrored pattern to check that we are writing bits within a pattern in the correct order. + { + MUST(bit_write_stream->write_bits(0b1000u, 4)); + MUST(bit_write_stream->write_bits(0b1000u, 4)); + auto result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b1000u, result); + result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b1000u, result); + } + + // Test two different chunks to check that we are not confusing their order. + { + MUST(bit_write_stream->write_bits(0b1000u, 4)); + MUST(bit_write_stream->write_bits(0b0100u, 4)); + auto result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b1000u, result); + result = MUST(bit_read_stream->read_bits(4)); + EXPECT_EQ(0b0100u, result); + } + + // Test a pattern that spans multiple bytes. + { + MUST(bit_write_stream->write_bits(0b1101001000100001u, 16)); + auto result = MUST(bit_read_stream->read_bits(16)); + EXPECT_EQ(0b1101001000100001u, result); + } +} diff --git a/Userland/Libraries/LibCore/BitStream.h b/Userland/Libraries/LibCore/BitStream.h index f78877508a..e1067c9514 100644 --- a/Userland/Libraries/LibCore/BitStream.h +++ b/Userland/Libraries/LibCore/BitStream.h @@ -237,4 +237,170 @@ private: Handle<Stream> m_stream; }; +/// A stream wrapper class that allows you to write arbitrary amounts of bits +/// in big-endian order to another stream. +class BigEndianOutputBitStream : public Stream { +public: + static ErrorOr<NonnullOwnPtr<BigEndianOutputBitStream>> construct(Handle<Stream> stream) + { + return adopt_nonnull_own_or_enomem<BigEndianOutputBitStream>(new BigEndianOutputBitStream(move(stream))); + } + + virtual ErrorOr<Bytes> read(Bytes) override + { + return Error::from_errno(EBADF); + } + + virtual ErrorOr<size_t> write(ReadonlyBytes bytes) override + { + VERIFY(m_bit_offset == 0); + return m_stream->write(bytes); + } + + template<Unsigned T> + ErrorOr<void> write_bits(T value, size_t bit_count) + { + VERIFY(m_bit_offset <= 7); + + while (bit_count > 0) { + u8 next_bit = (value >> (bit_count - 1)) & 1; + bit_count--; + + m_current_byte <<= 1; + m_current_byte |= next_bit; + m_bit_offset++; + + if (m_bit_offset > 7) { + TRY(m_stream->write({ &m_current_byte, sizeof(m_current_byte) })); + m_bit_offset = 0; + m_current_byte = 0; + } + } + + return {}; + } + + virtual bool is_eof() const override + { + return true; + } + + virtual bool is_open() const override + { + return m_stream->is_open(); + } + + virtual void close() override + { + } + + size_t bit_offset() const + { + return m_bit_offset; + } + + ErrorOr<void> align_to_byte_boundary() + { + if (m_bit_offset == 0) + return {}; + + TRY(write_bits(0u, 8 - m_bit_offset)); + VERIFY(m_bit_offset == 0); + return {}; + } + +private: + BigEndianOutputBitStream(Handle<Stream> stream) + : m_stream(move(stream)) + { + } + + Handle<Stream> m_stream; + u8 m_current_byte { 0 }; + size_t m_bit_offset { 0 }; +}; + +/// A stream wrapper class that allows you to write arbitrary amounts of bits +/// in little-endian order to another stream. +class LittleEndianOutputBitStream : public Stream { +public: + static ErrorOr<NonnullOwnPtr<LittleEndianOutputBitStream>> construct(Handle<Stream> stream) + { + return adopt_nonnull_own_or_enomem<LittleEndianOutputBitStream>(new LittleEndianOutputBitStream(move(stream))); + } + + virtual ErrorOr<Bytes> read(Bytes) override + { + return Error::from_errno(EBADF); + } + + virtual ErrorOr<size_t> write(ReadonlyBytes bytes) override + { + VERIFY(m_bit_offset == 0); + return m_stream->write(bytes); + } + + template<Unsigned T> + ErrorOr<void> write_bits(T value, size_t bit_count) + { + VERIFY(m_bit_offset <= 7); + + size_t input_offset = 0; + while (input_offset < bit_count) { + u8 next_bit = (value >> input_offset) & 1; + input_offset++; + + m_current_byte |= next_bit << m_bit_offset; + m_bit_offset++; + + if (m_bit_offset > 7) { + TRY(m_stream->write({ &m_current_byte, sizeof(m_current_byte) })); + m_bit_offset = 0; + m_current_byte = 0; + } + } + + return {}; + } + + virtual bool is_eof() const override + { + return true; + } + + virtual bool is_open() const override + { + return m_stream->is_open(); + } + + virtual void close() override + { + } + + size_t bit_offset() const + { + return m_bit_offset; + } + + ErrorOr<void> align_to_byte_boundary() + { + if (m_bit_offset == 0) + return {}; + + TRY(write_bits(0u, 8 - m_bit_offset)); + VERIFY(m_bit_offset == 0); + return {}; + } + +private: + LittleEndianOutputBitStream(Handle<Stream> stream) + : m_stream(move(stream)) + { + } + + Handle<Stream> m_stream; + u8 m_current_byte { 0 }; + size_t m_bit_offset { 0 }; +}; + } |