bitstreams.cpp

Go to the documentation of this file.

// Copyright (C) 2016 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
 
#include "bitstreams_p.h"
#include "huffman_p.h"
 
#include <QtCore/qbytearray.h>
 
#include <limits>
 
QT_BEGIN_NAMESPACE
 
static_assert(std::numeric_limits<uchar>::digits == 8, "octets expected");
 
namespace HPack
{
 
BitOStream::BitOStream(std::vector<uchar> &b)
    : buffer(b),
      // All data 'packed' before:
      bitsSet(8 * quint64(b.size()))
{
}
 
void BitOStream::writeBits(uchar bits, quint8 bitLength)
{
    Q_ASSERT(bitLength <= 8);
 
    quint8 count = bitsSet % 8; // bits used in buffer.back(), but 0 means 8
    bits <<= 8 - bitLength; // at top of byte, lower bits clear
    if (count) { // we have a part-used byte; fill it some more:
        buffer.back() |= bits >> count;
        count = 8 - count;
    } // count bits have been consumed (and 0 now means 0)
    if (bitLength > count)
        buffer.push_back(bits << count);
 
    bitsSet += bitLength;
}
 
void BitOStream::write(quint32 src)
{
    const quint8 prefixLen = 8 - bitsSet % 8;
    const quint32 fullPrefix = (1 << prefixLen) - 1;
 
    // https://http2.github.io/http2-spec/compression.html#low-level.representation,
    // 5.1
    if (src < fullPrefix) {
        writeBits(uchar(src), prefixLen);
    } else {
        writeBits(uchar(fullPrefix), prefixLen);
        // We're on the byte boundary now,
        // so we can just 'push_back'.
        Q_ASSERT(!(bitsSet % 8));
        src -= fullPrefix;
        while (src >= 128) {
            buffer.push_back(uchar(src % 128 + 128));
            src /= 128;
            bitsSet += 8;
        }
        buffer.push_back(src);
        bitsSet += 8;
    }
}
 
void BitOStream::write(QByteArrayView src, bool compressed)
{
    quint32 byteLen = src.size();
    if (compressed && byteLen) {
        const auto bitLen = huffman_encoded_bit_length(src);
        Q_ASSERT(bitLen && std::numeric_limits<quint32>::max() >= (bitLen + 7) / 8);
        byteLen = (bitLen + 7) / 8;
        writeBits(uchar(1), 1); // bit set - compressed
    } else {
        writeBits(uchar(0), 1); // no compression.
    }
 
    write(byteLen);
 
    if (compressed) {
        huffman_encode_string(src, *this);
    } else {
        bitsSet += quint64(src.size()) * 8;
        buffer.insert(buffer.end(), src.begin(), src.end());
    }
}
 
quint64 BitOStream::bitLength() const
{
    return bitsSet;
}
 
quint64 BitOStream::byteLength() const
{
    return buffer.size();
}
 
const uchar *BitOStream::begin() const
{
    return &buffer[0];
}
 
const uchar *BitOStream::end() const
{
    return &buffer[0] + buffer.size();
}
 
void BitOStream::clear()
{
    buffer.clear();
    bitsSet = 0;
}
 
BitIStream::BitIStream()
    : first(),
      last(),
      offset(),
      streamError(Error::NoError)
{
}
 
BitIStream::BitIStream(const uchar *begin, const uchar *end)
                 : first(begin),
                   last(end),
                   offset(),
                   streamError(Error::NoError)
{
}
 
quint64 BitIStream::bitLength() const
{
    return quint64(last - first) * 8;
}
 
bool BitIStream::hasMoreBits() const
{
    return offset < bitLength();
}
 
bool BitIStream::skipBits(quint64 nBits)
{
    if (nBits > bitLength() || bitLength() - nBits < offset)
        return false;
 
    offset += nBits;
    return true;
}
 
bool BitIStream::rewindOffset(quint64 nBits)
{
    if (nBits > offset)
        return false;
 
    offset -= nBits;
    return true;
}
 
bool BitIStream::read(quint32 *dstPtr)
{
    Q_ASSERT(dstPtr);
    quint32 &dst = *dstPtr;
 
    // 5.1 Integer Representation
    //
    // Integers are used to represent name indexes, header field indexes, or string lengths.
    // An integer representation can start anywhere within an octet.
    // To allow for optimized processing, an integer representation always finishes at the end of an octet.
    // An integer is represented in two parts: a prefix that fills the current octet and an optional
    // list of octets that are used if the integer value does not fit within the prefix.
    // The number of bits of the prefix (called N) is a parameter of the integer representation.
    // If the integer value is small enough, i.e., strictly less than 2N-1, it is compressed within the N-bit prefix.
    // ...
    // The prefix size, N, is always between 1 and 8 bits. An integer
    // starting at an octet boundary will have an 8-bit prefix.
 
    // Technically, such integers can be of any size, but as we do not have arbitrary-long integers,
    // everything that does not fit into 'dst' we consider as an error (after all, try to allocate a string
    // of such size and ... hehehe - send it as a part of a header!
 
    // This function updates the offset _only_ if the read was successful.
    if (offset >= bitLength()) {
        setError(Error::NotEnoughData);
        return false;
    }
 
    setError(Error::NoError);
 
    const quint32 prefixLen = 8 - offset % 8;
    const quint32 fullPrefix = (1 << prefixLen) - 1;
 
    const uchar prefix = uchar(first[offset / 8] & fullPrefix);
    if (prefix < fullPrefix) {
        // The number fitted into the prefix bits.
        dst = prefix;
        offset += prefixLen;
        return true;
    }
 
    quint32 newOffset = offset + prefixLen;
    // We have a list of bytes representing an integer ...
    quint64 val = prefix;
    quint32 octetPower = 0;
 
    while (true) {
        if (newOffset >= bitLength()) {
            setError(Error::NotEnoughData);
            return false;
        }
 
        const uchar octet = first[newOffset / 8];
 
        if (octetPower == 28 && octet > 15) {
            qCritical("integer is too big");
            setError(Error::InvalidInteger);
            return false;
        }
 
        val += quint32(octet & 0x7f) << octetPower;
        newOffset += 8;
 
        if (!(octet & 0x80)) {
            // The most significant bit of each octet is used
            // as a continuation flag: its value is set to 1
            // except for the last octet in the list.
            break;
        }
 
        octetPower += 7;
    }
 
    dst = val;
    offset = newOffset;
    Q_ASSERT(!(offset % 8));
 
    return true;
}
 
bool BitIStream::read(QByteArray *dstPtr)
{
    Q_ASSERT(dstPtr);
    QByteArray &dst = *dstPtr;
    //5.2 String Literal Representation
    //
    // Header field names and header field values can be represented as string literals.
    // A string literal is compressed as a sequence of octets, either by directly encoding
    // the string literal's octets or by using a Huffman code.
 
    // We update the offset _only_ if the read was successful.
 
    const quint64 oldOffset = offset;
    uchar compressed = 0;
    if (peekBits(offset, 1, &compressed) != 1 || !skipBits(1)) {
        setError(Error::NotEnoughData);
        return false;
    }
 
    setError(Error::NoError);
 
    quint32 len = 0;
    if (read(&len)) {
        Q_ASSERT(!(offset % 8));
        if (len <= (bitLength() - offset) / 8) { // We have enough data to read a string ...
            if (!compressed) {
                // Now good news, integer always ends on a byte boundary.
                // We can read 'len' bytes without any bit magic.
                const char *src = reinterpret_cast<const char *>(first + offset / 8);
                dst = QByteArray(src, len);
                offset += quint64(len) * 8;
                return true;
            }
 
            BitIStream slice(first + offset / 8, first + offset / 8 + len);
            if (huffman_decode_string(slice, &dst)) {
                offset += quint64(len) * 8;
                return true;
            }
 
            setError(Error::CompressionError);
        } else {
            setError(Error::NotEnoughData);
        }
    } // else the exact reason was set by read(quint32).
 
    offset = oldOffset;
    return false;
}
 
BitIStream::Error BitIStream::error() const
{
    return streamError;
}
 
void BitIStream::setError(Error newState)
{
    streamError = newState;
}
 
} // namespace HPack
 
QT_END_NAMESPACE