pack.h

Go to the documentation of this file.

 
/* Copyright (C) 2009,2015,2016,2017,2018,2024 Olly Betts
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see
 * <https://www.gnu.org/licenses/>.
 */
 
#ifndef XAPIAN_INCLUDED_PACK_H
#define XAPIAN_INCLUDED_PACK_H
 
#ifndef PACKAGE
# error config.h must be included first in each C++ source file
#endif
 
#include <string>
#include <string_view>
#include <type_traits>
 
#include "omassert.h"
 
#include "xapian/types.h"
 
const unsigned int SORTABLE_UINT_LOG2_MAX_BYTES = 2;
 
const unsigned int SORTABLE_UINT_MAX_BYTES = 1 << SORTABLE_UINT_LOG2_MAX_BYTES;
 
const unsigned int SORTABLE_UINT_1ST_BYTE_MASK =
        (0xffu >> SORTABLE_UINT_LOG2_MAX_BYTES);
 
[[noreturn]]
void unpack_throw_serialisation_error(const char* p);
 
inline void
pack_bool(std::string& s, bool value)
{
    s += char('0' | static_cast<char>(value));
}
 
inline bool
unpack_bool(const char** p, const char* end, bool* result)
{
    Assert(result);
    const char*& ptr = *p;
    Assert(ptr);
    char ch;
    if (rare(ptr == end || ((ch = *ptr++ - '0') &~ 1))) {
        ptr = NULL;
        return false;
    }
    *result = static_cast<bool>(ch);
    return true;
}
 
template<class U>
inline void
pack_uint_last(std::string& s, U value)
{
    static_assert(std::is_unsigned_v<U>, "Unsigned type required");
 
    while (value) {
        s += char(value & 0xff);
        value >>= 8;
    }
}
 
template<class U>
inline bool
unpack_uint_last(const char** p, const char* end, U* result)
{
    static_assert(std::is_unsigned_v<U>, "Unsigned type required");
    Assert(result);
 
    const char* ptr = *p;
    Assert(ptr);
    *p = end;
 
    // Check for overflow.
    if (rare(end - ptr > int(sizeof(U)))) {
        return false;
    }
 
    *result = 0;
    while (end != ptr) {
        *result = (*result << 8) | U(static_cast<unsigned char>(*--end));
    }
 
    return true;
}
 
#if HAVE_DECL___BUILTIN_CLZ && \
    HAVE_DECL___BUILTIN_CLZL && \
    HAVE_DECL___BUILTIN_CLZLL
template<typename T>
inline int
do_clz(T value) {
    extern int no_clz_builtin_for_this_type(T);
    return no_clz_builtin_for_this_type(value);
}
 
template<>
inline int
do_clz(unsigned value) {
    return __builtin_clz(value);
}
 
template<>
inline int
do_clz(unsigned long value) {
    return __builtin_clzl(value);
}
 
template<>
inline int
do_clz(unsigned long long value) {
    return __builtin_clzll(value);
}
 
# define HAVE_DO_CLZ
#endif
 
template<class U>
inline void
pack_uint_preserving_sort(std::string& s, U value)
{
    static_assert(std::is_unsigned_v<U>, "Unsigned type required");
    static_assert(sizeof(U) <= 8,
                  "Template type U too wide for database format");
    // The clz() functions are undefined for 0, so handle the smallest band
    // as a special case.
    if (value < 0x8000) {
        s.resize(s.size() + 2);
        s[s.size() - 2] = static_cast<unsigned char>(value >> 8);
        Assert(s[s.size() - 2] != '\xff');
        s[s.size() - 1] = static_cast<unsigned char>(value);
        return;
    }
 
#ifdef HAVE_DO_CLZ
    size_t len = ((sizeof(U) * 8 + 5) - do_clz(value)) / 7;
#else
    size_t len = 3;
    for (auto x = value >> 22; x; x >>= 7) ++len;
#endif
    unsigned mask = 0xff << (10 - len);
 
    s.resize(s.size() + len);
    for (size_t i = 1; i != len; ++i) {
        s[s.size() - i] = static_cast<unsigned char>(value);
        value >>= 8;
    }
 
    s[s.size() - len] = static_cast<unsigned char>(value | mask);
    Assert(s[s.size() - len] != '\xff');
 
    AssertRel(len, >, 2);
    AssertRel(len, <=, 9);
}
 
template<class U>
inline bool
unpack_uint_preserving_sort(const char** p, const char* end, U* result)
{
    static_assert(std::is_unsigned_v<U>, "Unsigned type required");
    static_assert(sizeof(U) <= 8,
                  "Template type U too wide for database format");
    Assert(result);
 
    const char* ptr = *p;
    Assert(ptr);
 
    if (rare(ptr == end)) {
        return false;
    }
 
    unsigned char len_byte = static_cast<unsigned char>(*ptr++);
    if (len_byte < 0x80) {
        *result = (U(len_byte) << 8) | static_cast<unsigned char>(*ptr++);
        *p = ptr;
        return true;
    }
 
    if (len_byte == 0xff) {
        return false;
    }
 
    // len is how many bytes there are after the length byte.
#ifdef HAVE_DO_CLZ
    size_t len = do_clz(len_byte ^ 0xffu) + 9 - sizeof(unsigned) * 8;
#else
    size_t len = 2;
    for (unsigned char m = 0x40; len_byte & m; m >>= 1) ++len;
#endif
    if (rare(size_t(end - ptr) < len)) {
        return false;
    }
    unsigned mask = 0xff << (9 - len);
    len_byte &= ~mask;
 
    // Check for overflow.
    if (rare(len > int(sizeof(U)))) return false;
    if constexpr(sizeof(U) != 8) {
        // Need to check the top byte too.
        if (rare(len == int(sizeof(U)) && len_byte != 0)) return false;
    }
 
    end = ptr + len;
    *p = end;
 
    U r = len_byte;
    while (ptr != end) {
        r = (r << 8) | U(static_cast<unsigned char>(*ptr++));
    }
    *result = r;
 
    return true;
}
 
template<class U>
inline void
pack_uint(std::string& s, U value)
{
    static_assert(std::is_unsigned_v<U>, "Unsigned type required");
 
    while (value >= 128) {
        s += static_cast<char>(static_cast<unsigned char>(value) | 0x80);
        value >>= 7;
    }
    s += static_cast<char>(value);
}
 
template<>
inline void
pack_uint(std::string& s, bool value)
{
    s += static_cast<char>(value);
}
 
template<class U>
inline bool
unpack_uint(const char** p, const char* end, U* result)
{
    static_assert(std::is_unsigned_v<U>, "Unsigned type required");
 
    const char* ptr = *p;
    Assert(ptr);
    const char* start = ptr;
 
    // Check the length of the encoded integer first.
    do {
        if (rare(ptr == end)) {
            // Out of data.
            *p = NULL;
            return false;
        }
    } while (static_cast<unsigned char>(*ptr++) >= 128);
 
    *p = ptr;
 
    if (!result) return true;
 
    *result = U(*--ptr);
    if (ptr == start) {
        // Special case for small values.
        return true;
    }
 
    size_t maxbits = size_t(ptr - start) * 7;
    if (maxbits <= sizeof(U) * 8) {
        // No possibility of overflow.
        do {
            unsigned char chunk = static_cast<unsigned char>(*--ptr) & 0x7f;
            *result = (*result << 7) | U(chunk);
        } while (ptr != start);
        return true;
    }
 
    size_t minbits = maxbits - 6;
    if (rare(minbits > sizeof(U) * 8)) {
        // Overflow.
        return false;
    }
 
    while (--ptr != start) {
        unsigned char chunk = static_cast<unsigned char>(*--ptr) & 0x7f;
        *result = (*result << 7) | U(chunk);
    }
 
    U tmp = *result;
    *result <<= 7;
    if (rare(*result < tmp)) {
        // Overflow.
        return false;
    }
    *result |= U(static_cast<unsigned char>(*ptr) & 0x7f);
    return true;
}
 
template<class U>
inline bool
unpack_uint_backwards(const char** p, const char* start, U* result)
{
    static_assert(std::is_unsigned_v<U>, "Unsigned type required");
 
    const char* ptr = *p;
    Assert(ptr);
 
    // Check it's not empty and that the final byte is valid.
    if (rare(ptr == start || static_cast<unsigned char>(ptr[-1]) >= 128)) {
        // Out of data.
        *p = NULL;
        return false;
    }
 
    do {
        if (rare(--ptr == start))
            break;
    } while (static_cast<unsigned char>(ptr[-1]) >= 128);
 
    const char* end = *p;
    *p = ptr;
    return unpack_uint(&ptr, end, result);
}
 
inline void
pack_string(std::string& s, std::string_view value)
{
    pack_uint(s, value.size());
    s += value;
}
 
inline void
pack_string_empty(std::string& s)
{
    s += '\0';
}
 
inline bool
unpack_string(const char** p, const char* end, std::string& result)
{
    size_t len;
    if (rare(!unpack_uint(p, end, &len))) {
        return false;
    }
 
    const char*& ptr = *p;
    if (rare(len > size_t(end - ptr))) {
        ptr = NULL;
        return false;
    }
 
    result.assign(ptr, len);
    ptr += len;
    return true;
}
 
inline bool
unpack_string_append(const char** p, const char* end, std::string& result)
{
    size_t len;
    if (rare(!unpack_uint(p, end, &len))) {
        return false;
    }
 
    const char*& ptr = *p;
    if (rare(len > size_t(end - ptr))) {
        ptr = NULL;
        return false;
    }
 
    result.append(ptr, len);
    ptr += len;
    return true;
}
 
inline void
pack_string_preserving_sort(std::string& s, std::string_view value,
                            bool last = false)
{
    std::string::size_type b = 0, e;
    while ((e = value.find('\0', b)) != std::string::npos) {
        ++e;
        s.append(value, b, e - b);
        s += '\xff';
        b = e;
    }
    s.append(value, b, std::string::npos);
    if (!last) s += '\0';
}
 
inline bool
unpack_string_preserving_sort(const char** p, const char* end,
                              std::string& result)
{
    result.resize(0);
 
    const char* ptr = *p;
    Assert(ptr);
 
    while (ptr != end) {
        char ch = *ptr++;
        if (rare(ch == '\0')) {
            if (usual(ptr == end || *ptr != '\xff')) {
                break;
            }
            ++ptr;
        }
        result += ch;
    }
    *p = ptr;
    return true;
}
 
inline std::string
pack_glass_postlist_key(std::string_view term)
{
    // Special case for doclen lists.
    if (term.empty())
        return std::string("\x00\xe0", 2);
 
    std::string key;
    pack_string_preserving_sort(key, term, true);
    return key;
}
 
inline std::string
pack_glass_postlist_key(std::string_view term, Xapian::docid did)
{
    // Special case for doclen lists.
    if (term.empty()) {
        std::string key("\x00\xe0", 2);
        pack_uint_preserving_sort(key, did);
        return key;
    }
 
    std::string key;
    pack_string_preserving_sort(key, term);
    pack_uint_preserving_sort(key, did);
    return key;
}
 
inline std::string
pack_honey_postlist_key(std::string_view term)
{
    Assert(!term.empty());
    std::string key;
    pack_string_preserving_sort(key, term, true);
    return key;
}
 
inline std::string
pack_honey_postlist_key(std::string_view term, Xapian::docid did)
{
    Assert(!term.empty());
    std::string key;
    pack_string_preserving_sort(key, term);
    pack_uint_preserving_sort(key, did);
    return key;
}
 
#endif // XAPIAN_INCLUDED_PACK_H