Revision control
++ // Copyright (C) 2016 The Qt Company Ltd.
++ // Copyright (C) 2016 Intel Corporation.
++ // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
++ // Qt-Security score:critical reason:data-parser
++
++ #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 "qbinaryjson.h"
++
++ #include <QtCore/qjsonarray.h>
++ #include <QtCore/qjsonobject.h>
++
++ #include <private/qbinaryjsonvalue_p.h>
++ #include <private/qendian_p.h>
++
++ #include <limits>
++
++ QT_BEGIN_NAMESPACE
++
++ /*
++ 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<typename... Accessors>
++ using qle_bitfield = QLEIntegerBitfieldUnion<uint, Accessors...>;
++
++ template<int pos, int width>
++ using qle_bitfield_accessor
++ = QSpecialIntegerAccessor<QLittleEndianStorageType<uint>, pos, width>;
++
++ template<int pos, int width>
++ using qle_signedbitfield_accessor
++ = QSpecialIntegerAccessor<QLittleEndianStorageType<uint>, pos, width, int>;
++
++ using offset = qle_uint;
++
++ // round the size up to the next 4 byte boundary
++ inline uint alignedSize(uint size) { return (size + 3) & ~3; }
++
++ // Every structure in the binary format (Base, Entry, Value, offset, String::Data,
++ // Latin1String::Data) is placed at a 4 byte boundary, and the writer only ever emits
++ // offsets that are multiples of 4. Offsets read from untrusted data must be checked
++ // against that invariant before they are turned into pointers, or we dereference
++ // misaligned pointers (undefined behavior) while validating the data.
++ inline bool isAlignedOffset(uint offset) { return (offset & 3) == 0; }
++
++ const int MaxLatin1Length = 0x7fff;
++
++ static inline bool useCompressed(QStringView s)
++ {
++ if (s.size() > 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.size();
++ qToLittleEndian<quint16>(str.utf16(), str.size(), 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.size();
++ 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 constexpr (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] = char16_t(d->utf16[i]);
++ return str;
++ }
++ }
++ };
++
++ 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.size(); // ### narrows from int to ushort
++ auto *l = data->latin1;
++ const auto srcData = src.utf16();
++ for (qsizetype i = 0; i < src.size(); ++i)
++ l[i] = char(srcData[i]);
++
++ 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
++ {
++ private:
++ using IsObjectAccessor = qle_bitfield_accessor<0, 1>;
++ using LengthAccessor = qle_bitfield_accessor<1, 31>;
++ public:
++ qle_uint size;
++ qle_bitfield<IsObjectAccessor, LengthAccessor> isObjectAndLength;
++ offset tableOffset;
++ // content follows here
++
++ void setIsObject() { isObjectAndLength.set<IsObjectAccessor>(1); }
++ bool isObject() const { return !!isObjectAndLength.get<IsObjectAccessor>(); }
++
++ void setIsArray() { isObjectAndLength.set<IsObjectAccessor>(0); }
++ bool isArray() const { return !isObject(); }
++
++ void setLength(uint length) { isObjectAndLength.set<LengthAccessor>(length); }
++ uint length() const { return isObjectAndLength.get<LengthAccessor>(); }
++
++ 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);
++ };
++
++ // A frame to iteratively check if the binary representation is valid or not.
++ struct IsValidFrame
++ {
++ explicit IsValidFrame(const Base *b, uint sz) : base(b), size(sz)
++ {}
++
++ const Base *base;
++ uint size;
++ };
++ using IsValidStack = QVarLengthArray<IsValidFrame, 16>;
++
++
++ // A frame to construct the JSON document from a binary representation in
++ // an iterative way.
++ // It should maintain the object/array that is currently constructed.
++ // We store both QJsonObject and QJsonArray, because it allow to avoid
++ // manual memory management with a union.
++ // We could use std::variant, but that would be the same in terms of
++ // memory (each of QJsonObject and QJsonArray is 8 bytes), and
++ // std::variant<QJsonObject, QJsonArray> is 16 bytes on its own.
++ struct DocumentFrame
++ {
++ explicit DocumentFrame(const Base *b, QString k = {})
++ : base(b), key(std::move(k)), isObject(b->isObject())
++ {}
++
++ const Base *base;
++ QString key;
++ QJsonObject object;
++ QJsonArray array;
++ uint index = 0;
++ bool isObject;
++ };
++ using DocumentStack = QVarLengthArray<DocumentFrame, 16>;
++
++ 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;
++ bool isValidHelper(uint maxSize, IsValidStack &stack) 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); }
++
++ bool isValidHelper(uint maxSize, IsValidStack &stack) const;
++ };
++
++ class Value
++ {
++ private:
++ using TypeAccessor = qle_bitfield_accessor<0, 3>;
++ using LatinOrIntValueAccessor = qle_bitfield_accessor<3, 1>;
++ using LatinKeyAccessor = qle_bitfield_accessor<4, 1>;
++ using ValueAccessor = qle_bitfield_accessor<5, 27>;
++ using IntValueAccessor = qle_signedbitfield_accessor<5, 27>;
++
++ qle_bitfield<
++ TypeAccessor,
++ LatinOrIntValueAccessor,
++ LatinKeyAccessor,
++ ValueAccessor,
++ IntValueAccessor
++ > m_data;
++
++
++ int intValue() const { return m_data.get<IntValueAccessor>(); }
++
++ public:
++ enum {
++ MaxSize = (1 << 27) - 1
++ };
++
++ 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 (isLatinOrIntValue())
++ return intValue();
++
++ 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 isLatinOrIntValue()
++ ? asLatin1String(b).toString()
++ : asString(b).toString();
++ }
++
++ String asString(const Base *b) const
++ {
++ Q_ASSERT(type() == QJsonValue::String && !isLatinOrIntValue());
++ return String(data(b));
++ }
++
++ Latin1String asLatin1String(const Base *b) const
++ {
++ Q_ASSERT(type() == QJsonValue::String && isLatinOrIntValue());
++ 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 toScalarJsonValue(const Base *b) const;
++ bool isValidHelper(const Base *b, IsValidStack &stack) 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);
++
++ void setIsLatinKey(bool isLatinKey) { m_data.set<LatinKeyAccessor>(isLatinKey); }
++ bool isLatinKey() const { return m_data.get<LatinKeyAccessor>(); }
++
++ void setIsLatinOrIntValue(bool v) { m_data.set<LatinOrIntValueAccessor>(v); }
++ bool isLatinOrIntValue() const { return m_data.get<LatinOrIntValueAccessor>(); }
++
++ void setType(uint type) { m_data.set<TypeAccessor>(type); }
++ uint type() const { return m_data.get<TypeAccessor>(); }
++
++ void setValue(uint value) { m_data.set<ValueAccessor>(value); }
++ uint value() const { return m_data.get<ValueAccessor>(); }
++ };
++
++ class Entry {
++ public:
++ Value value;
++ // key
++ // value data follows key
++
++ uint size() const
++ {
++ uint s = sizeof(Entry);
++ if (value.isLatinKey())
++ 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.isLatinKey());
++ return String(reinterpret_cast<const char *>(this) + sizeof(Entry));
++ }
++
++ Latin1String shallowLatin1Key() const
++ {
++ Q_ASSERT(value.isLatinKey());
++ return Latin1String(reinterpret_cast<const char *>(this) + sizeof(Entry));
++ }
++
++ QString key() const
++ {
++ return value.isLatinKey()
++ ? shallowLatin1Key().toString()
++ : shallowKey().toString();
++ }
++
++ bool isValid(uint maxSize) const
++ {
++ if (maxSize < sizeof(Entry))
++ return false;
++ maxSize -= sizeof(Entry);
++ return value.isLatinKey()
++ ? shallowLatin1Key().isValid(maxSize)
++ : shallowKey().isValid(maxSize);
++ }
++
++ bool operator ==(QStringView key) const
++ {
++ return value.isLatinKey()
++ ? (shallowLatin1Key().toQLatin1String() == key)
++ : (shallowKey() == key);
++ }
++
++ bool operator >=(QStringView key) const
++ {
++ return value.isLatinKey()
++ ? (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);
++ void *mem = malloc(alloc);
++ Q_CHECK_PTR(mem);
++ header = new (mem) Header;
++ header->tag = QJsonDocument::BinaryFormatTag;
++ header->version = 1;
++ Base *b = new (static_cast<void *>(header->root())) Base{
++ qle_uint{sizeof(Base)},
++ {}, // isObject == false && length == 0
++ offset{sizeof(Base)}
++ };
++ if (valueType == QJsonValue::Object)
++ b->setIsObject();
++ }
++
++ ~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::IsValidFrame, Q_PRIMITIVE_TYPE);
++ Q_DECLARE_TYPEINFO(QBinaryJsonPrivate::DocumentFrame, Q_RELOCATABLE_TYPE);
++
++ Q_DECLARE_TYPEINFO(QBinaryJsonPrivate::Value, Q_PRIMITIVE_TYPE);
++
++ QT_END_NAMESPACE
++
++ #endif // QBINARYJSON_P_H