14437022300

Committed 14 Apr 2025 03:47AM UTC coverage: 82.815% (+0.02%) from 82.798%

Build # 14437022300

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #1639 from evoskuil/master

Refactor and optimize (using fast streams) golomb and neutrino.

Coverage Stats

42 of 67 new or added lines in 2 files covered. (62.69%)

2 existing lines in 1 file now uncovered.

10173 of 12284 relevant lines covered (82.82%)

3825323.76 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

64.29

/src/filter/golomb.cpp

/**
 * Copyright (c) 2011-2025 libbitcoin developers (see AUTHORS)
 *
 * This file is part of libbitcoin.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 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 Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

// Sponsored in part by Digital Contract Design, LLC

#include <bitcoin/system/filter/golomb.hpp>

#include <algorithm>
#include <utility>
#include <vector>
#include <bitcoin/system/data/data.hpp>
#include <bitcoin/system/define.hpp>
#include <bitcoin/system/hash/hash.hpp>
#include <bitcoin/system/math/math.hpp>
#include <bitcoin/system/stream/stream.hpp>

namespace libbitcoin {
namespace system {

// Golomb-coded set construction
// ----------------------------------------------------------------------------

// protected
void golomb::construct(bitwriter& writer, const data_stack& items, uint8_t bits,
    const siphash_key& entropy, uint64_t target_false_positive_rate) NOEXCEPT
{
    const auto set = hashed_set_construct(items, items.size(),
        target_false_positive_rate, entropy);

    uint64_t previous = 0;
    for (const auto value: set)
    {
        encode(writer, value - previous, bits);
        previous = value;
    };
}

data_chunk golomb::construct(const data_stack& items, uint8_t bits,
    const siphash_key& entropy, uint64_t target_false_positive_rate) NOEXCEPT
{
    data_chunk out{};

    // A vector (push) stream is used because the size is not known a-priori.
    stream::out::data stream(out);
    write::bits::ostream writer(stream);
    construct(writer, items, bits, entropy, target_false_positive_rate);
    writer.flush();
    return out;
}

data_chunk golomb::construct(const data_stack& items, uint8_t bits,
    const half_hash& entropy, uint64_t target_false_positive_rate) NOEXCEPT
{
    return construct(items, bits, to_siphash_key(entropy),
        target_false_positive_rate);
}

// Single element match
// ----------------------------------------------------------------------------

// protected
bool golomb::match_single(bitreader& reader, const data_chunk& target,
    uint64_t set_size, const siphash_key& entropy, uint8_t bits,
    uint64_t target_false_positive_rate) NOEXCEPT
{
    const auto bound = target_false_positive_rate * set_size;
    const auto range = hash_to_range(target, bound, entropy);

    uint64_t previous = 0;
    for (uint64_t index = 0; index < set_size; index++)
    {
        const auto value = previous + decode(reader, bits);

        if (value == range)
            return true;

        if (value > range)
            break;

        previous = value;
    }

    return false;
}

bool golomb::match_single(const data_chunk& compressed_set,
    const data_chunk& target,  uint64_t set_size, const siphash_key& entropy,
    uint8_t bits, uint64_t target_false_positive_rate) NOEXCEPT
{
    stream::in::fast source(compressed_set);
    read::bits::fast reader(source);
    return match_single(reader, target, set_size, entropy, bits,
        target_false_positive_rate);
}

bool golomb::match_single(const data_chunk& compressed_set,
    const data_chunk& target, uint64_t set_size, const half_hash& entropy,
    uint8_t bits, uint64_t target_false_positive_rate) NOEXCEPT
{
    return match_single(compressed_set, target, set_size,
        to_siphash_key(entropy), bits, target_false_positive_rate);
}

// Intersection match
// ----------------------------------------------------------------------------

// protected
bool golomb::match_stack(bitreader& source, const data_stack& targets,
    uint64_t set_size, const siphash_key& entropy, uint8_t bits,
    uint64_t target_false_positive_rate) NOEXCEPT
{
    if (targets.empty())
        return false;

    const auto set = hashed_set_construct(targets, set_size,
        target_false_positive_rate, entropy);

    uint64_t range = 0;
    auto it = set.begin();

    for (uint64_t index = 0; index < set_size && it != set.end(); ++index)
    {
        range += decode(source, bits);

        for (auto value = *it; it != set.end(); value = *(it++))
        {
            if (value == range)
                return true;

            if (value > range)
                break;
        }
    }

    return false;
}

bool golomb::match_stack(const data_chunk& compressed_set,
    const data_stack& targets, uint64_t set_size, const siphash_key& entropy,
    uint8_t bits, uint64_t target_false_positive_rate) NOEXCEPT
{
    stream::in::fast source(compressed_set);
    read::bits::fast reader(source);
    return match_stack(reader, targets, set_size, entropy, bits,
        target_false_positive_rate);
}

bool golomb::match_stack(const data_chunk& compressed_set,
    const data_stack& targets, uint64_t set_size, const half_hash& entropy,
    uint8_t bits, uint64_t target_false_positive_rate) NOEXCEPT
{
    return match_stack(compressed_set, targets, set_size, to_siphash_key(entropy),
        bits, target_false_positive_rate);
}

// private
// ----------------------------------------------------------------------------

void golomb::encode(bitwriter& writer, uint64_t value,
    uint8_t modulo_exponent) NOEXCEPT
{
    const auto quotient = shift_right(value, modulo_exponent);
    for (uint64_t index = 0; index < quotient; ++index)
        writer.write_bit(true);

    writer.write_bit(false);
    writer.write_bits(value, modulo_exponent);
}

uint64_t golomb::decode(bitreader& reader, uint8_t modulo_exponent) NOEXCEPT
{
    uint64_t quotient = 0;
    while (reader.read_bit())
        ++quotient;

    const auto remainder = reader.read_bits(modulo_exponent);
    return shift_left(quotient, modulo_exponent) + remainder;
}

uint64_t golomb::hash_to_range(const data_slice& item, uint64_t bound,
    const siphash_key& key) NOEXCEPT
{
    constexpr auto shift = bits<uint64_t>;
    const auto product = uint128_t(siphash(key, item)) * uint128_t(bound);
    return (product >> shift).convert_to<uint64_t>();
}

std::vector<uint64_t> golomb::hashed_set_construct(const data_stack& items,
    uint64_t set_size, uint64_t target_false_positive_rate,
    const siphash_key& key) NOEXCEPT
{
    if (is_multiply_overflow(target_false_positive_rate, set_size))
        return {};

    std::vector<uint64_t> hashes(items.size());
    const auto bound = target_false_positive_rate * set_size;
    std::transform(items.begin(), items.end(), hashes.begin(),
        [&](const data_chunk& item) NOEXCEPT
        {
            return hash_to_range(item, bound, key);
        });

    return sort(std::move(hashes));
}


} // namespace system
} // namespace libbitcoin

1	/**
2	* Copyright (c) 2011-2025 libbitcoin developers (see AUTHORS)
3	*
4	* This file is part of libbitcoin.
5	*
6	* This program is free software: you can redistribute it and/or modify
7	* it under the terms of the GNU Affero General Public License as published by
8	* the Free Software Foundation, either version 3 of the License, or
9	* (at your option) any later version.
10	*
11	* This program is distributed in the hope that it will be useful,
12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	* GNU Affero General Public License for more details.
15	*
16	* You should have received a copy of the GNU Affero General Public License
17	* along with this program. If not, see <http://www.gnu.org/licenses/>.
18	*/
19
20	// Sponsored in part by Digital Contract Design, LLC
21
22	#include <bitcoin/system/filter/golomb.hpp>
23
24	#include <algorithm>
25	#include <utility>
26	#include <vector>
27	#include <bitcoin/system/data/data.hpp>
28	#include <bitcoin/system/define.hpp>
29	#include <bitcoin/system/hash/hash.hpp>
30	#include <bitcoin/system/math/math.hpp>
31	#include <bitcoin/system/stream/stream.hpp>
32
33	namespace libbitcoin {
34	namespace system {
35
36	// Golomb-coded set construction
37	// ----------------------------------------------------------------------------
38
39	// protected
40	void golomb::construct(bitwriter& writer, const data_stack& items, uint8_t bits,	23✔
41	const siphash_key& entropy, uint64_t target_false_positive_rate) NOEXCEPT
42	{
43	const auto set = hashed_set_construct(items, items.size(),	23✔
44	target_false_positive_rate, entropy);	23✔
45
46	uint64_t previous = 0;	23✔
47	for (const auto value: set)	108✔
48	{
49	encode(writer, value - previous, bits);	85✔
50	previous = value;	85✔
51	};	23✔
52	}	23✔
53
NEW 54	data_chunk golomb::construct(const data_stack& items, uint8_t bits,	×
55	const siphash_key& entropy, uint64_t target_false_positive_rate) NOEXCEPT
56	{
NEW 57	data_chunk out{};	×
58
59	// A vector (push) stream is used because the size is not known a-priori.
NEW 60	stream::out::data stream(out);	×
NEW 61	write::bits::ostream writer(stream);	×
NEW 62	construct(writer, items, bits, entropy, target_false_positive_rate);	×
NEW 63	writer.flush();	×
NEW 64	return out;	×
UNCOV 65	}	×
66
NEW 67	data_chunk golomb::construct(const data_stack& items, uint8_t bits,	×
68	const half_hash& entropy, uint64_t target_false_positive_rate) NOEXCEPT
69	{
NEW 70	return construct(items, bits, to_siphash_key(entropy),	×
UNCOV 71	target_false_positive_rate);	×
72	}
73
74	// Single element match
75	// ----------------------------------------------------------------------------
76
77	// protected
78	bool golomb::match_single(bitreader& reader, const data_chunk& target,	2✔
79	uint64_t set_size, const siphash_key& entropy, uint8_t bits,
80	uint64_t target_false_positive_rate) NOEXCEPT
81	{
82	const auto bound = target_false_positive_rate * set_size;	2✔
83	const auto range = hash_to_range(target, bound, entropy);	2✔
84
85	uint64_t previous = 0;	2✔
86	for (uint64_t index = 0; index < set_size; index++)	18✔
87	{
88	const auto value = previous + decode(reader, bits);	17✔
89
90	if (value == range)	17✔
91	return true;
92
93	if (value > range)	16✔
94	break;
95
96	previous = value;	16✔
97	}
98
99	return false;
100	}
101
NEW 102	bool golomb::match_single(const data_chunk& compressed_set,	×
103	const data_chunk& target, uint64_t set_size, const siphash_key& entropy,
104	uint8_t bits, uint64_t target_false_positive_rate) NOEXCEPT
105	{
NEW 106	stream::in::fast source(compressed_set);	×
NEW 107	read::bits::fast reader(source);	×
NEW 108	return match_single(reader, target, set_size, entropy, bits,	×
109	target_false_positive_rate);	×
110	}	×
111
NEW 112	bool golomb::match_single(const data_chunk& compressed_set,	×
113	const data_chunk& target, uint64_t set_size, const half_hash& entropy,
114	uint8_t bits, uint64_t target_false_positive_rate) NOEXCEPT
115	{
NEW 116	return match_single(compressed_set, target, set_size,	×
NEW 117	to_siphash_key(entropy), bits, target_false_positive_rate);	×
118	}
119
120	// Intersection match
121	// ----------------------------------------------------------------------------
122
123	// protected
124	bool golomb::match_stack(bitreader& source, const data_stack& targets,	2✔
125	uint64_t set_size, const siphash_key& entropy, uint8_t bits,
126	uint64_t target_false_positive_rate) NOEXCEPT
127	{
128	if (targets.empty())	2✔
129	return false;
130
131	const auto set = hashed_set_construct(targets, set_size,	2✔
132	target_false_positive_rate, entropy);	2✔
133
134	uint64_t range = 0;	2✔
135	auto it = set.begin();	2✔
136
137	for (uint64_t index = 0; index < set_size && it != set.end(); ++index)	16✔
138	{
139	range += decode(source, bits);	15✔
140
141	for (auto value = it; it != set.end(); value = (it++))	16✔
142	{
143	if (value == range)	15✔
144	return true;
145
146	if (value > range)	14✔
147	break;
148	}
149	}
150
151	return false;
152	}
153
NEW 154	bool golomb::match_stack(const data_chunk& compressed_set,	×
155	const data_stack& targets, uint64_t set_size, const siphash_key& entropy,
156	uint8_t bits, uint64_t target_false_positive_rate) NOEXCEPT
157	{
NEW 158	stream::in::fast source(compressed_set);	×
NEW 159	read::bits::fast reader(source);	×
NEW 160	return match_stack(reader, targets, set_size, entropy, bits,	×
NEW 161	target_false_positive_rate);	×
NEW 162	}	×
163
NEW 164	bool golomb::match_stack(const data_chunk& compressed_set,	×
165	const data_stack& targets, uint64_t set_size, const half_hash& entropy,
166	uint8_t bits, uint64_t target_false_positive_rate) NOEXCEPT
167	{
NEW 168	return match_stack(compressed_set, targets, set_size, to_siphash_key(entropy),	×
169	bits, target_false_positive_rate);	×
170	}
171
172	// private
173	// ----------------------------------------------------------------------------
174
175	void golomb::encode(bitwriter& writer, uint64_t value,	85✔
176	uint8_t modulo_exponent) NOEXCEPT
177	{
178	const auto quotient = shift_right(value, modulo_exponent);	85✔
179	for (uint64_t index = 0; index < quotient; ++index)	151✔
180	writer.write_bit(true);	66✔
181
182	writer.write_bit(false);	85✔
183	writer.write_bits(value, modulo_exponent);	85✔
184	}	85✔
185
186	uint64_t golomb::decode(bitreader& reader, uint8_t modulo_exponent) NOEXCEPT	32✔
187	{
188	uint64_t quotient = 0;	32✔
189	while (reader.read_bit())	68✔
190	++quotient;	36✔
191
192	const auto remainder = reader.read_bits(modulo_exponent);	32✔
193	return shift_left(quotient, modulo_exponent) + remainder;	32✔
194	}
195
196	uint64_t golomb::hash_to_range(const data_slice& item, uint64_t bound,	90✔
197	const siphash_key& key) NOEXCEPT
198	{
199	constexpr auto shift = bits<uint64_t>;	90✔
200	const auto product = uint128_t(siphash(key, item)) * uint128_t(bound);	90✔
201	return (product >> shift).convert_to<uint64_t>();	90✔
202	}
203
204	std::vector<uint64_t> golomb::hashed_set_construct(const data_stack& items,	25✔
205	uint64_t set_size, uint64_t target_false_positive_rate,
206	const siphash_key& key) NOEXCEPT
207	{
208	if (is_multiply_overflow(target_false_positive_rate, set_size))	25✔
NEW 209	return {};	×
210
211	std::vector<uint64_t> hashes(items.size());	25✔
212	const auto bound = target_false_positive_rate * set_size;	25✔
213	std::transform(items.begin(), items.end(), hashes.begin(),	25✔
214	[&](const data_chunk& item) NOEXCEPT	88✔
215	{
216	return hash_to_range(item, bound, key);	88✔
217	});
218
219	return sort(std::move(hashes));	25✔
220	}
221
222
223	} // namespace system
224	} // namespace libbitcoin

libbitcoin / libbitcoin-system / 14437022300

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous