Bitcoin Core  22.99.0
P2P Digital Currency
Macros | Functions
minisketch.cpp File Reference
#include <new>
#include "../include/minisketch.h"
#include "false_positives.h"
#include "fielddefines.h"
#include "sketch.h"
Include dependency graph for minisketch.cpp:

Go to the source code of this file.

Macros

#define MINISKETCH_BUILD
 

Functions

SketchConstructGeneric1Byte (int bits, int implementation)
 
SketchConstructGeneric2Bytes (int bits, int implementation)
 
SketchConstructGeneric3Bytes (int bits, int implementation)
 
SketchConstructGeneric4Bytes (int bits, int implementation)
 
SketchConstructGeneric5Bytes (int bits, int implementation)
 
SketchConstructGeneric6Bytes (int bits, int implementation)
 
SketchConstructGeneric7Bytes (int bits, int implementation)
 
SketchConstructGeneric8Bytes (int bits, int implementation)
 
int minisketch_bits_supported (uint32_t bits)
 Determine whether support for elements of bits bits was compiled in. More...
 
uint32_t minisketch_implementation_max ()
 Determine the maximum number of implementations available. More...
 
int minisketch_implementation_supported (uint32_t bits, uint32_t implementation)
 Determine if the a combination of bits and implementation number is available. More...
 
minisketchminisketch_create (uint32_t bits, uint32_t implementation, size_t capacity)
 Construct a sketch for a given element size, implementation and capacity. More...
 
uint32_t minisketch_bits (const minisketch *sketch)
 Get the element size of a sketch in bits. More...
 
size_t minisketch_capacity (const minisketch *sketch)
 Get the capacity of a sketch. More...
 
uint32_t minisketch_implementation (const minisketch *sketch)
 Get the implementation of a sketch. More...
 
minisketchminisketch_clone (const minisketch *sketch)
 Clone a sketch. More...
 
void minisketch_destroy (minisketch *sketch)
 Destroy a sketch. More...
 
size_t minisketch_serialized_size (const minisketch *sketch)
 Compute the size in bytes for serializing a given sketch. More...
 
void minisketch_serialize (const minisketch *sketch, unsigned char *output)
 Serialize a sketch to bytes. More...
 
void minisketch_deserialize (minisketch *sketch, const unsigned char *input)
 Deserialize a sketch from bytes. More...
 
void minisketch_add_uint64 (minisketch *sketch, uint64_t element)
 Add an element to a sketch. More...
 
size_t minisketch_merge (minisketch *sketch, const minisketch *other_sketch)
 Merge the elements of another sketch into this sketch. More...
 
ssize_t minisketch_decode (const minisketch *sketch, size_t max_elements, uint64_t *output)
 Decode a sketch. More...
 
void minisketch_set_seed (minisketch *sketch, uint64_t seed)
 Set the seed for randomizing algorithm choices to a fixed value. More...
 
size_t minisketch_compute_capacity (uint32_t bits, size_t max_elements, uint32_t fpbits)
 Compute the capacity needed to achieve a certain rate of false positives. More...
 
size_t minisketch_compute_max_elements (uint32_t bits, size_t capacity, uint32_t fpbits)
 Compute what max_elements can be decoded for a certain rate of false positives. More...
 

Macro Definition Documentation

◆ MINISKETCH_BUILD

#define MINISKETCH_BUILD

Definition at line 10 of file minisketch.cpp.

Function Documentation

◆ ConstructGeneric1Byte()

Sketch* ConstructGeneric1Byte ( int  bits,
int  implementation 
)

Definition at line 86 of file generic_1byte.cpp.

◆ ConstructGeneric2Bytes()

Sketch* ConstructGeneric2Bytes ( int  bits,
int  implementation 
)

Definition at line 95 of file generic_2bytes.cpp.

◆ ConstructGeneric3Bytes()

Sketch* ConstructGeneric3Bytes ( int  bits,
int  implementation 
)

Definition at line 95 of file generic_3bytes.cpp.

◆ ConstructGeneric4Bytes()

Sketch* ConstructGeneric4Bytes ( int  bits,
int  implementation 
)

Definition at line 95 of file generic_4bytes.cpp.

◆ ConstructGeneric5Bytes()

Sketch* ConstructGeneric5Bytes ( int  bits,
int  implementation 
)

Definition at line 95 of file generic_5bytes.cpp.

◆ ConstructGeneric6Bytes()

Sketch* ConstructGeneric6Bytes ( int  bits,
int  implementation 
)

Definition at line 95 of file generic_6bytes.cpp.

◆ ConstructGeneric7Bytes()

Sketch* ConstructGeneric7Bytes ( int  bits,
int  implementation 
)

Definition at line 95 of file generic_7bytes.cpp.

◆ ConstructGeneric8Bytes()

Sketch* ConstructGeneric8Bytes ( int  bits,
int  implementation 
)

Definition at line 95 of file generic_8bytes.cpp.

◆ minisketch_add_uint64()

void minisketch_add_uint64 ( minisketch sketch,
uint64_t  element 
)

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.

Definition at line 454 of file minisketch.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ minisketch_bits()

uint32_t minisketch_bits ( const minisketch sketch)

Get the element size of a sketch in bits.

Definition at line 398 of file minisketch.cpp.

Here is the call graph for this function:

◆ minisketch_bits_supported()

int minisketch_bits_supported ( uint32_t  bits)

Determine whether support for elements of bits bits was compiled in.

Definition at line 165 of file minisketch.cpp.

Here is the caller graph for this function:

◆ minisketch_capacity()

size_t minisketch_capacity ( const minisketch sketch)

Get the capacity of a sketch.

Definition at line 404 of file minisketch.cpp.

Here is the call graph for this function:

◆ minisketch_clone()

minisketch* minisketch_clone ( const minisketch sketch)

Clone a sketch.

The result must be destroyed using minisketch_destroy.

Definition at line 416 of file minisketch.cpp.

Here is the call graph for this function:

◆ minisketch_compute_capacity()

size_t minisketch_compute_capacity ( uint32_t  bits,
size_t  max_elements,
uint32_t  fpbits 
)

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.

Definition at line 482 of file minisketch.cpp.

◆ minisketch_compute_max_elements()

size_t minisketch_compute_max_elements ( uint32_t  bits,
size_t  capacity,
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.

Definition at line 486 of file minisketch.cpp.

◆ minisketch_create()

minisketch* minisketch_create ( uint32_t  bits,
uint32_t  implementation,
size_t  capacity 
)

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.

Definition at line 380 of file minisketch.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ minisketch_decode()

ssize_t minisketch_decode ( const minisketch sketch,
size_t  max_elements,
uint64_t *  output 
)

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.

Definition at line 470 of file minisketch.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ minisketch_deserialize()

void minisketch_deserialize ( minisketch sketch,
const unsigned char *  input 
)

Deserialize a sketch from bytes.

Definition at line 448 of file minisketch.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ minisketch_destroy()

void minisketch_destroy ( minisketch sketch)

Destroy a sketch.

The pointer that was passed in may not be used anymore afterwards.

Definition at line 426 of file minisketch.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ minisketch_implementation()

uint32_t minisketch_implementation ( const minisketch sketch)

Get the implementation of a sketch.

Definition at line 410 of file minisketch.cpp.

Here is the call graph for this function:

◆ minisketch_implementation_max()

uint32_t minisketch_implementation_max ( void  )

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).

Definition at line 358 of file minisketch.cpp.

Here is the caller graph for this function:

◆ minisketch_implementation_supported()

int minisketch_implementation_supported ( uint32_t  bits,
uint32_t  implementation 
)

Determine if the a combination of bits and implementation number is available.

Returns 1 if it is, 0 otherwise.

Definition at line 366 of file minisketch.cpp.

Here is the call graph for this function:

◆ minisketch_merge()

size_t minisketch_merge ( minisketch sketch,
const minisketch other_sketch 
)

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.

Definition at line 460 of file minisketch.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ minisketch_serialize()

void minisketch_serialize ( const minisketch sketch,
unsigned char *  output 
)

Serialize a sketch to bytes.

Definition at line 442 of file minisketch.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ minisketch_serialized_size()

size_t minisketch_serialized_size ( const minisketch sketch)

Compute the size in bytes for serializing a given sketch.

Definition at line 434 of file minisketch.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ minisketch_set_seed()

void minisketch_set_seed ( minisketch sketch,
uint64_t  seed 
)

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.

Definition at line 476 of file minisketch.cpp.

Here is the call graph for this function: