path: root/src/corelib/serialization/qbinaryjson_p.h

/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Copyright (C) 2016 Intel Corporation.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/

#ifndef QBINARYJSON_P_H
#define QBINARYJSON_P_H

//
//  W A R N I N G
//  -------------
//
// This file is not part of the Qt API.  It exists purely as an
// implementation detail.  This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.
//

#include <private/qbinaryjsonvalue_p.h>
#include <private/qendian_p.h>

#include <qjsondocument.h>

#include <limits>

QT_REQUIRE_CONFIG(binaryjson);

QT_BEGIN_NAMESPACE

// in qstring.cpp
void qt_to_latin1_unchecked(uchar *dst, const ushort *uc, qsizetype len);
void qt_from_latin1(ushort *dst, const char *str, size_t size) noexcept;

/*
  This defines a binary data structure for Json data. The data structure is optimised for fast reading
  and minimum allocations. The whole data structure can be mmap'ed and used directly.

  In most cases the binary structure is not as space efficient as a utf8 encoded text representation, but
  much faster to access.

  The size requirements are:

  String:
    Latin1 data: 2 bytes header + string.length()
    Full Unicode: 4 bytes header + 2*(string.length())

  Values: 4 bytes + size of data (size can be 0 for some data)
    bool: 0 bytes
    double: 8 bytes (0 if integer with less than 27bits)
    string: see above
    array: size of array
    object: size of object
  Array: 12 bytes + 4*length + size of Value data
  Object: 12 bytes + 8*length + size of Key Strings + size of Value data

  For an example such as

    {                                           // object: 12 + 5*8                   = 52
         "firstName": "John",                   // key 12, value 8                    = 20
         "lastName" : "Smith",                  // key 12, value 8                    = 20
         "age"      : 25,                       // key 8, value 0                     = 8
         "address"  :                           // key 12, object below               = 140
         {                                      // object: 12 + 4*8
             "streetAddress": "21 2nd Street",  // key 16, value 16
             "city"         : "New York",       // key 8, value 12
             "state"        : "NY",             // key 8, value 4
             "postalCode"   : "10021"           // key 12, value 8
         },                                     // object total: 128
         "phoneNumber":                         // key: 16, value array below         = 172
         [                                      // array: 12 + 2*4 + values below: 156
             {                                  // object 12 + 2*8
               "type"  : "home",                // key 8, value 8
               "number": "212 555-1234"         // key 8, value 16
             },                                 // object total: 68
             {                                  // object 12 + 2*8
               "type"  : "fax",                 // key 8, value 8
               "number": "646 555-4567"         // key 8, value 16
             }                                  // object total: 68
         ]                                      // array total: 156
    }                                           // great total:                         412 bytes

    The uncompressed text file used roughly 500 bytes, so in this case we end up using about
    the same space as the text representation.

    Other measurements have shown a slightly bigger binary size than a compact text
    representation where all possible whitespace was stripped out.
*/
namespace QBinaryJsonPrivate {

class Array;
class Object;
class Value;
class Entry;

template<typename T>
using q_littleendian = QLEInteger<T>;

using qle_short = q_littleendian<short>;
using qle_ushort = q_littleendian<unsigned short>;
using qle_int = q_littleendian<int>;
using qle_uint = q_littleendian<unsigned int>;

template<int pos, int width>
using qle_bitfield = QLEIntegerBitfield<uint, pos, width>;

template<int pos, int width>
using qle_signedbitfield = QLEIntegerBitfield<int, pos, width>;

using offset = qle_uint;

// round the size up to the next 4 byte boundary
inline uint alignedSize(uint size) { return (size + 3) & ~3; }

const int MaxLatin1Length = 0x7fff;

static inline bool useCompressed(QStringView s)
{
    if (s.length() > MaxLatin1Length)
        return false;
    return QtPrivate::isLatin1(s);
}

static inline bool useCompressed(QLatin1String s)
{
    return s.size() <= MaxLatin1Length;
}

static inline uint qStringSize(const QString &string, bool compress)
{
    uint l = 2 + string.size();
    if (!compress)
        l *= 2;
    return alignedSize(l);
}

// returns INT_MAX if it can't compress it into 28 bits
static inline int compressedNumber(double d)
{
    // this relies on details of how ieee floats are represented
    const int exponent_off = 52;
    const quint64 fraction_mask = 0x000fffffffffffffULL;
    const quint64 exponent_mask = 0x7ff0000000000000ULL;

    quint64 val;
    memcpy (&val, &d, sizeof(double));
    int exp = (int)((val & exponent_mask) >> exponent_off) - 1023;
    if (exp < 0 || exp > 25)
        return std::numeric_limits<int>::max();

    quint64 non_int = val & (fraction_mask >> exp);
    if (non_int)
        return std::numeric_limits<int>::max();

    bool neg = (val >> 63) != 0;
    val &= fraction_mask;
    val |= ((quint64)1 << 52);
    int res = (int)(val >> (52 - exp));
    return neg ? -res : res;
}

class Latin1String;

class String
{
public:
    explicit String(const char *data) : d(reinterpret_cast<const Data *>(data)) {}

    struct Data {
        qle_uint length;
        qle_ushort utf16[1];
    };
    const Data *d;

    uint byteSize() const { return sizeof(uint) + sizeof(ushort) * d->length; }
    bool isValid(uint maxSize) const
    {
        // Check byteSize() <= maxSize, avoiding integer overflow
        return maxSize >= sizeof(uint)
                && uint(d->length) <= (maxSize - sizeof(uint)) / sizeof(ushort);
    }

    static void copy(char *dest, QStringView str)
    {
        Data *data = reinterpret_cast<Data *>(dest);
        data->length = str.length();
        qToLittleEndian<quint16>(str.utf16(), str.length(), data->utf16);
        fillTrailingZeros(data);
    }

    static void fillTrailingZeros(Data *data)
    {
        if (data->length & 1)
            data->utf16[data->length] = 0;
    }

    bool operator ==(QStringView str) const
    {
        int slen = str.length();
        int l = d->length;
        if (slen != l)
            return false;
        const auto *s = reinterpret_cast<const ushort *>(str.utf16());
        const qle_ushort *a = d->utf16;
        const ushort *b = s;
        while (l-- && *a == *b)
            a++,b++;
        return (l == -1);
    }

    bool operator ==(const String &str) const
    {
        if (d->length != str.d->length)
            return false;
        return !memcmp(d->utf16, str.d->utf16, d->length * sizeof(ushort));
    }

    QString toString() const
    {
#if Q_BYTE_ORDER == Q_LITTLE_ENDIAN
        return QString(reinterpret_cast<const QChar *>(d->utf16), d->length);
#else
        const uint l = d->length;
        QString str(l, Qt::Uninitialized);
        QChar *ch = str.data();
        for (uint i = 0; i < l; ++i)
            ch[i] = QChar(d->utf16[i]);
        return str;
#endif
    }
};

class Latin1String
{
public:
    explicit Latin1String(const char *data) : d(reinterpret_cast<const Data *>(data)) {}

    struct Data {
        qle_ushort length;
        char latin1[1];
    };
    const Data *d;

    uint byteSize() const { return sizeof(ushort) + sizeof(char) * (d->length); }
    bool isValid(uint maxSize) const { return byteSize() <= maxSize; }

    static void copy(char *dest, QStringView src)
    {
        Data *data = reinterpret_cast<Data *>(dest);
        data->length = src.length();
        auto *l = reinterpret_cast<uchar *>(data->latin1);
        const auto *uc = reinterpret_cast<const ushort *>(src.utf16());
        qt_to_latin1_unchecked(l, uc, data->length);

        for (uint len = data->length; quintptr(l + len) & 0x3; ++len)
            l[len] = 0;
    }

    QLatin1String toQLatin1String() const noexcept { return QLatin1String(d->latin1, d->length); }
    QString toString() const { return QString::fromLatin1(d->latin1, d->length); }
};

static inline void copyString(char *dest, QStringView str, bool compress)
{
    if (compress)
        Latin1String::copy(dest, str);
    else
        String::copy(dest, str);
}

/*
 Base is the base class for both Object and Array. Both classes work more or less the same way.
 The class starts with a header (defined by the struct below), then followed by data (the data for
 values in the Array case and Entry's (see below) for objects.

 After the data a table follows (tableOffset points to it) containing Value objects for Arrays, and
 offsets from the beginning of the object to Entry's in the case of Object.

 Entry's in the Object's table are lexicographically sorted by key in the table(). This allows the usage
 of a binary search over the keys in an Object.
 */
class Base
{
public:
    qle_uint size;
    union {
        uint _dummy;
        qle_bitfield<0, 1> is_object;
        qle_bitfield<1, 31> length;
    };
    offset tableOffset;
    // content follows here

    bool isObject() const { return !!is_object; }
    bool isArray() const { return !isObject(); }

    offset *table()
    {
        return reinterpret_cast<offset *>(reinterpret_cast<char *>(this) + tableOffset);
    }

    const offset *table() const
    {
        return reinterpret_cast<const offset *>(reinterpret_cast<const char *>(this) + tableOffset);
    }

    uint reserveSpace(uint dataSize, uint posInTable, uint numItems, bool replace);
};

class Object : public Base
{
public:
    const Entry *entryAt(uint i) const
    {
        return reinterpret_cast<const Entry *>(reinterpret_cast<const char *>(this) + table()[i]);
    }

    Entry *entryAt(uint i)
    {
        return reinterpret_cast<Entry *>(reinterpret_cast<char *>(this) + table()[i]);
    }

    uint indexOf(QStringView key, bool *exists) const;
    QJsonObject toJsonObject() const;
    bool isValid(uint maxSize) const;
};

class Array : public Base
{
public:
    const Value *at(uint i) const { return reinterpret_cast<const Value *>(table() + i); }
    Value *at(uint i) { return reinterpret_cast<Value *>(table() + i); }

    QJsonArray toJsonArray() const;
    bool isValid(uint maxSize) const;
};

class Value
{
public:
    enum {
        MaxSize = (1 << 27) - 1
    };
    union {
        uint _dummy;
        qle_bitfield<0, 3> type;
        qle_bitfield<3, 1> latinOrIntValue;
        qle_bitfield<4, 1> latinKey;
        qle_bitfield<5, 27> value;
        qle_signedbitfield<5, 27> int_value;
    };

    inline const char *data(const Base *b) const
    {
        return reinterpret_cast<const char *>(b) + value;
    }

    uint usedStorage(const Base *b) const;

    bool toBoolean() const
    {
        Q_ASSERT(type == QJsonValue::Bool);
        return value != 0;
    }

    double toDouble(const Base *b) const
    {
        Q_ASSERT(type == QJsonValue::Double);
        if (latinOrIntValue)
            return int_value;

        auto i = qFromLittleEndian<quint64>(reinterpret_cast<const uchar *>(b) + value);
        double d;
        memcpy(&d, &i, sizeof(double));
        return d;
    }

    QString toString(const Base *b) const
    {
        return latinOrIntValue
                ? asLatin1String(b).toString()
                : asString(b).toString();
    }

    String asString(const Base *b) const
    {
        Q_ASSERT(type == QJsonValue::String && !latinOrIntValue);
        return String(data(b));
    }

    Latin1String asLatin1String(const Base *b) const
    {
        Q_ASSERT(type == QJsonValue::String && latinOrIntValue);
        return Latin1String(data(b));
    }

    const Base *base(const Base *b) const
    {
        Q_ASSERT(type == QJsonValue::Array || type == QJsonValue::Object);
        return reinterpret_cast<const Base *>(data(b));
    }

    QJsonValue toJsonValue(const Base *b) const;
    bool isValid(const Base *b) const;

    static uint requiredStorage(const QBinaryJsonValue &v, bool *compressed);
    static uint valueToStore(const QBinaryJsonValue &v, uint offset);
    static void copyData(const QBinaryJsonValue &v, char *dest, bool compressed);
};

class Entry {
public:
    Value value;
    // key
    // value data follows key

    uint size() const
    {
        uint s = sizeof(Entry);
        if (value.latinKey)
            s += shallowLatin1Key().byteSize();
        else
            s += shallowKey().byteSize();
        return alignedSize(s);
    }

    uint usedStorage(Base *b) const
    {
        return size() + value.usedStorage(b);
    }

    String shallowKey() const
    {
        Q_ASSERT(!value.latinKey);
        return String(reinterpret_cast<const char *>(this) + sizeof(Entry));
    }

    Latin1String shallowLatin1Key() const
    {
        Q_ASSERT(value.latinKey);
        return Latin1String(reinterpret_cast<const char *>(this) + sizeof(Entry));
    }

    QString key() const
    {
        return value.latinKey
                ? shallowLatin1Key().toString()
                : shallowKey().toString();
    }

    bool isValid(uint maxSize) const
    {
        if (maxSize < sizeof(Entry))
            return false;
        maxSize -= sizeof(Entry);
        return value.latinKey
                ? shallowLatin1Key().isValid(maxSize)
                : shallowKey().isValid(maxSize);
    }

    bool operator ==(QStringView key) const
    {
        return value.latinKey
                ? (shallowLatin1Key().toQLatin1String() == key)
                : (shallowKey() == key);
    }

    bool operator >=(QStringView key) const
    {
        return value.latinKey
                ? (shallowLatin1Key().toQLatin1String() >= key)
                : (shallowKey().toString() >= key);
    }
};

class Header {
public:
    qle_uint tag; // 'qbjs'
    qle_uint version; // 1
    Base *root() { return reinterpret_cast<Base *>(this + 1); }
    const Base *root() const { return reinterpret_cast<const Base *>(this + 1); }
};

class ConstData
{
    Q_DISABLE_COPY_MOVE(ConstData)
public:
    const uint alloc;
    union {
        const char *rawData;
        const Header *header;
    };

    ConstData(const char *raw, uint a) : alloc(a), rawData(raw) {}
    bool isValid() const;
    QJsonDocument toJsonDocument() const;
};

class MutableData
{
    Q_DISABLE_COPY_MOVE(MutableData)
public:
    QAtomicInt ref;
    uint alloc;
    union {
        char *rawData;
        Header *header;
    };
    uint compactionCounter : 31;

    MutableData(char *raw, uint a)
        : alloc(a), rawData(raw), compactionCounter(0)
    {
    }

    MutableData(uint reserved, QJsonValue::Type valueType)
        : rawData(nullptr), compactionCounter(0)
    {
        Q_ASSERT(valueType == QJsonValue::Array || valueType == QJsonValue::Object);

        alloc = sizeof(Header) + sizeof(Base) + reserved + sizeof(offset);
        header = reinterpret_cast<Header *>(malloc(alloc));
        Q_CHECK_PTR(header);
        header->tag = QJsonDocument::BinaryFormatTag;
        header->version = 1;
        Base *b = header->root();
        b->size = sizeof(Base);
        b->is_object = (valueType == QJsonValue::Object);
        b->tableOffset = sizeof(Base);
        b->length = 0;
    }

    ~MutableData()
    {
        free(rawData);
    }

    MutableData *clone(const Base *b, uint reserve = 0)
    {
        uint size = sizeof(Header) + b->size;
        if (b == header->root() && ref.loadRelaxed() == 1 && alloc >= size + reserve)
            return this;

        if (reserve) {
            if (reserve < 128)
                reserve = 128;
            size = qMax(size + reserve, qMin(size *2, uint(Value::MaxSize)));
            if (size > Value::MaxSize) {
                qWarning("QJson: Document too large to store in data structure");
                return nullptr;
            }
        }
        char *raw = reinterpret_cast<char *>(malloc(size));
        Q_CHECK_PTR(raw);
        memcpy(raw + sizeof(Header), b, b->size);
        auto *h = reinterpret_cast<Header *>(raw);
        h->tag = QJsonDocument::BinaryFormatTag;
        h->version = 1;
        auto *d = new MutableData(raw, size);
        d->compactionCounter = (b == header->root()) ? compactionCounter : 0;
        return d;
    }

    char *takeRawData(uint *size)
    {
        *size = alloc;
        char *result = rawData;
        rawData = nullptr;
        alloc = 0;
        return result;
    }

    void compact();
};

} // namespace QBinaryJsonPrivate

Q_DECLARE_TYPEINFO(QBinaryJsonPrivate::Value, Q_PRIMITIVE_TYPE);

QT_END_NAMESPACE

#endif // QBINARYJSON_P_H