diff options
Diffstat (limited to 'src/corelib/serialization/qbinaryjson_p.h')
| -rw-r--r-- | src/corelib/serialization/qbinaryjson_p.h | 617 |
1 files changed, 617 insertions, 0 deletions
diff --git a/src/corelib/serialization/qbinaryjson_p.h b/src/corelib/serialization/qbinaryjson_p.h new file mode 100644 index 0000000000..132c36f227 --- /dev/null +++ b/src/corelib/serialization/qbinaryjson_p.h @@ -0,0 +1,617 @@ +/**************************************************************************** +** +** 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 |