mirror of https://github.com/bitcoin/bitcoin.git
369 lines
15 KiB
C++
369 lines
15 KiB
C++
#ifndef _MINISKETCH_H_
|
|
#define _MINISKETCH_H_ 1
|
|
|
|
#include <stdint.h>
|
|
#include <stdlib.h>
|
|
|
|
#ifdef _MSC_VER
|
|
# include <BaseTsd.h>
|
|
typedef SSIZE_T ssize_t;
|
|
#else
|
|
# include <unistd.h>
|
|
#endif
|
|
|
|
#ifndef MINISKETCH_API
|
|
# if defined(_WIN32)
|
|
# ifdef MINISKETCH_BUILD
|
|
# define MINISKETCH_API __declspec(dllexport)
|
|
# else
|
|
# define MINISKETCH_API
|
|
# endif
|
|
# elif defined(__GNUC__) && (__GNUC__ >= 4) && defined(MINISKETCH_BUILD)
|
|
# define MINISKETCH_API __attribute__ ((visibility ("default")))
|
|
# else
|
|
# define MINISKETCH_API
|
|
# endif
|
|
#endif
|
|
|
|
#ifdef __cplusplus
|
|
# if __cplusplus >= 201103L
|
|
# include <memory>
|
|
# include <vector>
|
|
# include <cassert>
|
|
# if __cplusplus >= 201703L
|
|
# include <optional>
|
|
# endif // __cplusplus >= 201703L
|
|
# endif // __cplusplus >= 201103L
|
|
extern "C" {
|
|
#endif // __cplusplus
|
|
|
|
/** Opaque type for decoded sketches. */
|
|
typedef struct minisketch minisketch;
|
|
|
|
/** Determine whether support for elements of `bits` bits was compiled in. */
|
|
MINISKETCH_API int minisketch_bits_supported(uint32_t bits);
|
|
|
|
/** Determine the maximum number of implementations available.
|
|
*
|
|
* Multiple implementations may be available for a given element size, with
|
|
* different performance characteristics on different hardware.
|
|
*
|
|
* Each implementation is identified by a number from 0 to the output of this
|
|
* function call, inclusive. Note that not every combination of implementation
|
|
* and element size may exist (see further).
|
|
*/
|
|
MINISKETCH_API uint32_t minisketch_implementation_max(void);
|
|
|
|
/** Determine if the a combination of bits and implementation number is available.
|
|
*
|
|
* Returns 1 if it is, 0 otherwise.
|
|
*/
|
|
MINISKETCH_API int minisketch_implementation_supported(uint32_t bits, uint32_t implementation);
|
|
|
|
/** Construct a sketch for a given element size, implementation and capacity.
|
|
*
|
|
* If the combination of `bits` and `implementation` is unavailable, or when
|
|
* OOM occurs, NULL is returned. If minisketch_implementation_supported
|
|
* returns 1 for the specified bits and implementation, this will always succeed
|
|
* (except when allocation fails).
|
|
*
|
|
* If the result is not NULL, it must be destroyed using minisketch_destroy.
|
|
*/
|
|
MINISKETCH_API minisketch* minisketch_create(uint32_t bits, uint32_t implementation, size_t capacity);
|
|
|
|
/** Get the element size of a sketch in bits. */
|
|
MINISKETCH_API uint32_t minisketch_bits(const minisketch* sketch);
|
|
|
|
/** Get the capacity of a sketch. */
|
|
MINISKETCH_API size_t minisketch_capacity(const minisketch* sketch);
|
|
|
|
/** Get the implementation of a sketch. */
|
|
MINISKETCH_API uint32_t minisketch_implementation(const minisketch* sketch);
|
|
|
|
/** Set the seed for randomizing algorithm choices to a fixed value.
|
|
*
|
|
* By default, sketches are initialized with a random seed. This is important
|
|
* to avoid scenarios where an attacker could force worst-case behavior.
|
|
*
|
|
* This function initializes the seed to a user-provided value (any 64-bit
|
|
* integer is acceptable, regardless of field size).
|
|
*
|
|
* When seed is -1, a fixed internal value with predictable behavior is
|
|
* used. It is only intended for testing.
|
|
*/
|
|
MINISKETCH_API void minisketch_set_seed(minisketch* sketch, uint64_t seed);
|
|
|
|
/** Clone a sketch.
|
|
*
|
|
* The result must be destroyed using minisketch_destroy.
|
|
*/
|
|
MINISKETCH_API minisketch* minisketch_clone(const minisketch* sketch);
|
|
|
|
/** Destroy a sketch.
|
|
*
|
|
* The pointer that was passed in may not be used anymore afterwards.
|
|
*/
|
|
MINISKETCH_API void minisketch_destroy(minisketch* sketch);
|
|
|
|
/** Compute the size in bytes for serializing a given sketch. */
|
|
MINISKETCH_API size_t minisketch_serialized_size(const minisketch* sketch);
|
|
|
|
/** Serialize a sketch to bytes. */
|
|
MINISKETCH_API void minisketch_serialize(const minisketch* sketch, unsigned char* output);
|
|
|
|
/** Deserialize a sketch from bytes. */
|
|
MINISKETCH_API void minisketch_deserialize(minisketch* sketch, const unsigned char* input);
|
|
|
|
/** Add an element to a sketch.
|
|
*
|
|
* If the element to be added is too large for the sketch, the most significant
|
|
* bits of the element are dropped. More precisely, if the element size of
|
|
* `sketch` is b bits, then this function adds the unsigned integer represented
|
|
* by the b least significant bits of `element` to `sketch`.
|
|
*
|
|
* If the element to be added is 0 (after potentially dropping the most significant
|
|
* bits), then this function is a no-op. Sketches cannot contain an element with
|
|
* the value 0.
|
|
*
|
|
* Note that adding the same element a second time removes it again.
|
|
*/
|
|
MINISKETCH_API void minisketch_add_uint64(minisketch* sketch, uint64_t element);
|
|
|
|
/** Merge the elements of another sketch into this sketch.
|
|
*
|
|
* After merging, `sketch` will contain every element that existed in one but not
|
|
* both of the input sketches. It can be seen as an exclusive or operation on
|
|
* the set elements. If the capacity of `other_sketch` is lower than `sketch`'s,
|
|
* merging reduces the capacity of `sketch` to that of `other_sketch`.
|
|
*
|
|
* This function returns the capacity of `sketch` after merging has been performed
|
|
* (where this capacity is at least 1), or 0 to indicate that merging has failed because
|
|
* the two input sketches differ in their element size or implementation. If 0 is
|
|
* returned, `sketch` (and its capacity) have not been modified.
|
|
*
|
|
* It is also possible to perform this operation directly on the serializations
|
|
* of two sketches with the same element size and capacity by performing a bitwise XOR
|
|
* of the serializations.
|
|
*/
|
|
MINISKETCH_API size_t minisketch_merge(minisketch* sketch, const minisketch* other_sketch);
|
|
|
|
/** Decode a sketch.
|
|
*
|
|
* `output` is a pointer to an array of `max_element` uint64_t's, which will be
|
|
* filled with the elements in this sketch.
|
|
*
|
|
* The return value is the number of decoded elements, or -1 if decoding failed.
|
|
*/
|
|
MINISKETCH_API ssize_t minisketch_decode(const minisketch* sketch, size_t max_elements, uint64_t* output);
|
|
|
|
/** Compute the capacity needed to achieve a certain rate of false positives.
|
|
*
|
|
* A sketch with capacity c and no more than c elements can always be decoded
|
|
* correctly. However, if it has more than c elements, or contains just random
|
|
* bytes, it is possible that it will still decode, but the result will be
|
|
* nonsense. This can be counteracted by increasing the capacity slightly.
|
|
*
|
|
* Given a field size bits, an intended number of elements that can be decoded
|
|
* max_elements, and a false positive probability of 1 in 2**fpbits, this
|
|
* function computes the necessary capacity. It is only guaranteed to be
|
|
* accurate up to fpbits=256.
|
|
*/
|
|
MINISKETCH_API size_t minisketch_compute_capacity(uint32_t bits, size_t max_elements, uint32_t fpbits);
|
|
|
|
/** Compute what max_elements can be decoded for a certain rate of false positives.
|
|
*
|
|
* This is the inverse operation of minisketch_compute_capacity. It determines,
|
|
* given a field size bits, a capacity of a sketch, and an acceptable false
|
|
* positive probability of 1 in 2**fpbits, what the maximum allowed
|
|
* max_elements value is. If no value of max_elements would give the desired
|
|
* false positive probability, 0 is returned.
|
|
*
|
|
* Note that this is not an exact inverse of minisketch_compute_capacity. For
|
|
* example, with bits=32, fpbits=16, and max_elements=8,
|
|
* minisketch_compute_capacity will return 9, as capacity 8 would only have a
|
|
* false positive chance of 1 in 2^15.3. Increasing the capacity to 9 however
|
|
* decreases the fp chance to 1 in 2^47.3, enough for max_elements=9 (with fp
|
|
* chance of 1 in 2^18.5). Therefore, minisketch_compute_max_elements with
|
|
* capacity=9 will return 9.
|
|
*/
|
|
MINISKETCH_API size_t minisketch_compute_max_elements(uint32_t bits, size_t capacity, uint32_t fpbits);
|
|
|
|
#ifdef __cplusplus
|
|
}
|
|
|
|
#if __cplusplus >= 201103L
|
|
/** Simple RAII C++11 wrapper around the minisketch API. */
|
|
class Minisketch
|
|
{
|
|
struct Deleter
|
|
{
|
|
void operator()(minisketch* ptr) const
|
|
{
|
|
minisketch_destroy(ptr);
|
|
}
|
|
};
|
|
|
|
std::unique_ptr<minisketch, Deleter> m_minisketch;
|
|
|
|
public:
|
|
/** Check whether the library supports fields of the given size. */
|
|
static bool BitsSupported(uint32_t bits) noexcept { return minisketch_bits_supported(bits); }
|
|
|
|
/** Get the highest supported implementation number. */
|
|
static uint32_t MaxImplementation() noexcept { return minisketch_implementation_max(); }
|
|
|
|
/** Check whether the library supports fields with a given size and implementation number.
|
|
* If a particular field size `bits` is supported, implementation 0 is always supported for it.
|
|
* Higher implementation numbers may or may not be available as well, up to MaxImplementation().
|
|
*/
|
|
static bool ImplementationSupported(uint32_t bits, uint32_t implementation) noexcept { return minisketch_implementation_supported(bits, implementation); }
|
|
|
|
/** Given field size and a maximum number of decodable elements n, compute what capacity c to
|
|
* use so that sketches with more elements than n have a chance no higher than 2^-fpbits of
|
|
* being decoded incorrectly (and will instead fail when decoding for up to n elements).
|
|
*
|
|
* See minisketch_compute_capacity for more details. */
|
|
static size_t ComputeCapacity(uint32_t bits, size_t max_elements, uint32_t fpbits) noexcept { return minisketch_compute_capacity(bits, max_elements, fpbits); }
|
|
|
|
/** Reverse operation of ComputeCapacity. See minisketch_compute_max_elements. */
|
|
static size_t ComputeMaxElements(uint32_t bits, size_t capacity, uint32_t fpbits) noexcept { return minisketch_compute_max_elements(bits, capacity, fpbits); }
|
|
|
|
/** Construct a clone of the specified sketch. */
|
|
Minisketch(const Minisketch& sketch) noexcept
|
|
{
|
|
if (sketch.m_minisketch) {
|
|
m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_clone(sketch.m_minisketch.get()));
|
|
}
|
|
}
|
|
|
|
/** Make this Minisketch a clone of the specified one. */
|
|
Minisketch& operator=(const Minisketch& sketch) noexcept
|
|
{
|
|
if (sketch.m_minisketch) {
|
|
m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_clone(sketch.m_minisketch.get()));
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
/** Check whether this Minisketch object is valid. */
|
|
explicit operator bool() const noexcept { return bool{m_minisketch}; }
|
|
|
|
/** Construct an (invalid) Minisketch object. */
|
|
Minisketch() noexcept = default;
|
|
|
|
/** Move constructor. */
|
|
Minisketch(Minisketch&&) noexcept = default;
|
|
|
|
/** Move assignment. */
|
|
Minisketch& operator=(Minisketch&&) noexcept = default;
|
|
|
|
/** Construct a Minisketch object with the specified parameters.
|
|
*
|
|
* If bits is not BitsSupported(), or the combination of bits and capacity is not
|
|
* ImplementationSupported(), or OOM occurs internally, an invalid Minisketch
|
|
* object will be constructed. Use operator bool() to check that this isn't the
|
|
* case before performing any other operations. */
|
|
Minisketch(uint32_t bits, uint32_t implementation, size_t capacity) noexcept
|
|
{
|
|
m_minisketch = std::unique_ptr<minisketch, Deleter>(minisketch_create(bits, implementation, capacity));
|
|
}
|
|
|
|
/** Create a Minisketch object sufficiently large for the specified number of elements at given fpbits.
|
|
* It may construct an invalid object, which you may need to check for. */
|
|
static Minisketch CreateFP(uint32_t bits, uint32_t implementation, size_t max_elements, uint32_t fpbits) noexcept
|
|
{
|
|
return Minisketch(bits, implementation, ComputeCapacity(bits, max_elements, fpbits));
|
|
}
|
|
|
|
/** Return the field size for a (valid) Minisketch object. */
|
|
uint32_t GetBits() const noexcept { return minisketch_bits(m_minisketch.get()); }
|
|
|
|
/** Return the capacity for a (valid) Minisketch object. */
|
|
size_t GetCapacity() const noexcept { return minisketch_capacity(m_minisketch.get()); }
|
|
|
|
/** Return the implementation number for a (valid) Minisketch object. */
|
|
uint32_t GetImplementation() const noexcept { return minisketch_implementation(m_minisketch.get()); }
|
|
|
|
/** Set the seed for a (valid) Minisketch object. See minisketch_set_seed(). */
|
|
Minisketch& SetSeed(uint64_t seed) noexcept
|
|
{
|
|
minisketch_set_seed(m_minisketch.get(), seed);
|
|
return *this;
|
|
}
|
|
|
|
/** Add (or remove, if already present) an element to a (valid) Minisketch object.
|
|
* See minisketch_add_uint64(). */
|
|
Minisketch& Add(uint64_t element) noexcept
|
|
{
|
|
minisketch_add_uint64(m_minisketch.get(), element);
|
|
return *this;
|
|
}
|
|
|
|
/** Merge sketch into *this; both have to be valid Minisketch objects.
|
|
* See minisketch_merge for details. */
|
|
Minisketch& Merge(const Minisketch& sketch) noexcept
|
|
{
|
|
minisketch_merge(m_minisketch.get(), sketch.m_minisketch.get());
|
|
return *this;
|
|
}
|
|
|
|
/** Decode this (valid) Minisketch object into the result vector, up to as many elements as the
|
|
* vector's size permits. */
|
|
bool Decode(std::vector<uint64_t>& result) const
|
|
{
|
|
ssize_t ret = minisketch_decode(m_minisketch.get(), result.size(), result.data());
|
|
if (ret == -1) return false;
|
|
result.resize(ret);
|
|
return true;
|
|
}
|
|
|
|
/** Get the serialized size in bytes for this (valid) Minisketch object.. */
|
|
size_t GetSerializedSize() const noexcept { return minisketch_serialized_size(m_minisketch.get()); }
|
|
|
|
/** Serialize this (valid) Minisketch object as a byte vector. */
|
|
std::vector<unsigned char> Serialize() const
|
|
{
|
|
std::vector<unsigned char> result(GetSerializedSize());
|
|
minisketch_serialize(m_minisketch.get(), result.data());
|
|
return result;
|
|
}
|
|
|
|
/** Deserialize into this (valid) Minisketch from an object containing its bytes (which has data()
|
|
* and size() members). */
|
|
template<typename T>
|
|
Minisketch& Deserialize(
|
|
const T& obj,
|
|
typename std::enable_if<
|
|
std::is_convertible<typename std::remove_pointer<decltype(obj.data())>::type (*)[], const unsigned char (*)[]>::value &&
|
|
std::is_convertible<decltype(obj.size()), std::size_t>::value,
|
|
std::nullptr_t
|
|
>::type = nullptr) noexcept
|
|
{
|
|
assert(GetSerializedSize() == obj.size());
|
|
minisketch_deserialize(m_minisketch.get(), obj.data());
|
|
return *this;
|
|
}
|
|
|
|
#if __cplusplus >= 201703L
|
|
/** C++17 only: like Decode(), but up to a specified number of elements into an optional vector. */
|
|
std::optional<std::vector<uint64_t>> Decode(size_t max_elements) const
|
|
{
|
|
std::vector<uint64_t> result(max_elements);
|
|
ssize_t ret = minisketch_decode(m_minisketch.get(), max_elements, result.data());
|
|
if (ret == -1) return {};
|
|
result.resize(ret);
|
|
return result;
|
|
}
|
|
|
|
/** C++17 only: similar to Decode(), but with specified false positive probability. */
|
|
std::optional<std::vector<uint64_t>> DecodeFP(uint32_t fpbits) const
|
|
{
|
|
return Decode(ComputeMaxElements(GetBits(), GetCapacity(), fpbits));
|
|
}
|
|
#endif // __cplusplus >= 201703L
|
|
};
|
|
#endif // __cplusplus >= 201103L
|
|
#endif // __cplusplus
|
|
|
|
#endif // _MINISKETCH_H_
|