aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authormoneromooo-monero <moneromooo-monero@users.noreply.github.com>2018-05-29 12:39:00 +0100
committermoneromooo-monero <moneromooo-monero@users.noreply.github.com>2018-09-11 13:38:02 +0000
commit0b05a0fa74512970ceba3c15ed2cbf027ef7b6da (patch)
tree8d124229d8b6df177a1e5d37e18681803a221c45 /src
parentadd pippenger unit tests (diff)
downloadmonero-0b05a0fa74512970ceba3c15ed2cbf027ef7b6da.tar.xz
Add Pippenger cache and limit Straus cache size
Diffstat (limited to 'src')
-rw-r--r--src/ringct/bulletproofs.cc29
-rw-r--r--src/ringct/multiexp.cc76
-rw-r--r--src/ringct/multiexp.h7
3 files changed, 82 insertions, 30 deletions
diff --git a/src/ringct/bulletproofs.cc b/src/ringct/bulletproofs.cc
index 83005eaa4..4eb6d6d5b 100644
--- a/src/ringct/bulletproofs.cc
+++ b/src/ringct/bulletproofs.cc
@@ -49,6 +49,9 @@ extern "C"
#define PERF_TIMER_START_BP(x) PERF_TIMER_START_UNIT(x, 1000000)
+#define STRAUS_SIZE_LIMIT 128
+#define PIPPENGER_SIZE_LIMIT 0
+
namespace rct
{
@@ -61,8 +64,8 @@ static constexpr size_t maxN = 64;
static constexpr size_t maxM = BULLETPROOF_MAX_OUTPUTS;
static rct::key Hi[maxN*maxM], Gi[maxN*maxM];
static ge_p3 Hi_p3[maxN*maxM], Gi_p3[maxN*maxM];
-static ge_dsmp Gprecomp[maxN*maxM], Hprecomp[maxN*maxM];
-static std::shared_ptr<straus_cached_data> HiGi_cache;
+static std::shared_ptr<straus_cached_data> straus_HiGi_cache;
+static std::shared_ptr<pippenger_cached_data> pippenger_HiGi_cache;
static const rct::key TWO = { {0x02, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 , 0x00, 0x00, 0x00,0x00 } };
static const rct::keyV oneN = vector_dup(rct::identity(), maxN);
static const rct::keyV twoN = vector_powers(TWO, maxN);
@@ -73,9 +76,12 @@ static inline rct::key multiexp(const std::vector<MultiexpData> &data, bool HiGi
{
static const size_t STEP = getenv("STRAUS_STEP") ? atoi(getenv("STRAUS_STEP")) : 0;
if (HiGi)
- return data.size() <= 256 ? straus(data, HiGi_cache, STEP) : pippenger(data, get_pippenger_c(data.size()));
+ {
+ static_assert(128 <= STRAUS_SIZE_LIMIT, "Straus in precalc mode can only be calculated till STRAUS_SIZE_LIMIT");
+ return data.size() <= 128 ? straus(data, straus_HiGi_cache, STEP) : pippenger(data, pippenger_HiGi_cache, get_pippenger_c(data.size()));
+ }
else
- return data.size() <= 64 ? straus(data, NULL, STEP) : pippenger(data, get_pippenger_c(data.size()));
+ return data.size() <= 64 ? straus(data, NULL, STEP) : pippenger(data, NULL, get_pippenger_c(data.size()));
}
//addKeys3acc_p3
@@ -123,18 +129,23 @@ static void init_exponents()
for (size_t i = 0; i < maxN*maxM; ++i)
{
Hi[i] = get_exponent(rct::H, i * 2);
- rct::precomp(Hprecomp[i], Hi[i]);
CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&Hi_p3[i], Hi[i].bytes) == 0, "ge_frombytes_vartime failed");
Gi[i] = get_exponent(rct::H, i * 2 + 1);
- rct::precomp(Gprecomp[i], Gi[i]);
CHECK_AND_ASSERT_THROW_MES(ge_frombytes_vartime(&Gi_p3[i], Gi[i].bytes) == 0, "ge_frombytes_vartime failed");
data.push_back({rct::zero(), Gi[i]});
data.push_back({rct::zero(), Hi[i]});
}
- HiGi_cache = straus_init_cache(data);
- size_t cache_size = (sizeof(Hi)+sizeof(Hprecomp)+sizeof(Hi_p3))*2 + straus_get_cache_size(HiGi_cache);
- MINFO("cache size: " << cache_size/1024 << " kB");
+
+ straus_HiGi_cache = straus_init_cache(data, STRAUS_SIZE_LIMIT);
+ pippenger_HiGi_cache = pippenger_init_cache(data, PIPPENGER_SIZE_LIMIT);
+
+ MINFO("Hi/Gi cache size: " << (sizeof(Hi)+sizeof(Gi))/1024 << " kB");
+ MINFO("Hi_p3/Gi_p3 cache size: " << (sizeof(Hi_p3)+sizeof(Gi_p3))/1024 << " kB");
+ MINFO("Straus cache size: " << straus_get_cache_size(straus_HiGi_cache)/1024 << " kB");
+ MINFO("Pippenger cache size: " << pippenger_get_cache_size(pippenger_HiGi_cache)/1024 << " kB");
+ size_t cache_size = (sizeof(Hi)+sizeof(Hi_p3))*2 + straus_get_cache_size(straus_HiGi_cache) + pippenger_get_cache_size(pippenger_HiGi_cache);
+ MINFO("Total cache size: " << cache_size/1024 << "kB");
init_done = true;
}
diff --git a/src/ringct/multiexp.cc b/src/ringct/multiexp.cc
index fd2d1cbd7..f9ef9e422 100644
--- a/src/ringct/multiexp.cc
+++ b/src/ringct/multiexp.cc
@@ -343,9 +343,12 @@ struct straus_cached_data
#endif
#endif
-std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<MultiexpData> &data)
+std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<MultiexpData> &data, size_t N)
{
MULTIEXP_PERF(PERF_TIMER_START_UNIT(multiples, 1000000));
+ if (N == 0)
+ N = data.size();
+ CHECK_AND_ASSERT_THROW_MES(N <= data.size(), "Bad cache base data");
ge_cached cached;
ge_p1p1 p1;
ge_p3 p3;
@@ -353,9 +356,10 @@ std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<Multiexp
#ifdef RAW_MEMORY_BLOCK
const size_t offset = cache->size;
- cache->multiples = (ge_cached*)aligned_realloc(cache->multiples, sizeof(ge_cached) * ((1<<STRAUS_C)-1) * std::max(offset, data.size()), 4096);
- cache->size = data.size();
- for (size_t j=offset;j<data.size();++j)
+ cache->multiples = (ge_cached*)aligned_realloc(cache->multiples, sizeof(ge_cached) * ((1<<STRAUS_C)-1) * std::max(offset, N), 4096);
+ CHECK_AND_ASSERT_THROW_MES(cache->multiples, "Out of memory");
+ cache->size = N;
+ for (size_t j=offset;j<N;++j)
{
ge_p3_to_cached(&CACHE_OFFSET(cache, j, 1), &data[j].point);
for (size_t i=2;i<1<<STRAUS_C;++i)
@@ -368,8 +372,8 @@ std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<Multiexp
#else
#ifdef ALTERNATE_LAYOUT
const size_t offset = cache->multiples.size();
- cache->multiples.resize(std::max(offset, data.size()));
- for (size_t i = offset; i < data.size(); ++i)
+ cache->multiples.resize(std::max(offset, N));
+ for (size_t i = offset; i < N; ++i)
{
cache->multiples[i].resize((1<<STRAUS_C)-1);
ge_p3_to_cached(&cache->multiples[i][0], &data[i].point);
@@ -383,12 +387,12 @@ std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<Multiexp
#else
cache->multiples.resize(1<<STRAUS_C);
size_t offset = cache->multiples[1].size();
- cache->multiples[1].resize(std::max(offset, data.size()));
- for (size_t i = offset; i < data.size(); ++i)
+ cache->multiples[1].resize(std::max(offset, N));
+ for (size_t i = offset; i < N; ++i)
ge_p3_to_cached(&cache->multiples[1][i], &data[i].point);
for (size_t i=2;i<1<<STRAUS_C;++i)
- cache->multiples[i].resize(std::max(offset, data.size()));
- for (size_t j=offset;j<data.size();++j)
+ cache->multiples[i].resize(std::max(offset, N));
+ for (size_t j=offset;j<N;++j)
{
for (size_t i=2;i<1<<STRAUS_C;++i)
{
@@ -418,6 +422,7 @@ size_t straus_get_cache_size(const std::shared_ptr<straus_cached_data> &cache)
rct::key straus(const std::vector<MultiexpData> &data, const std::shared_ptr<straus_cached_data> &cache, size_t STEP)
{
+ CHECK_AND_ASSERT_THROW_MES(cache == NULL || cache->size >= data.size(), "Cache is too small");
MULTIEXP_PERF(PERF_TIMER_UNIT(straus, 1000000));
bool HiGi = cache != NULL;
STEP = STEP ? STEP : 192;
@@ -533,7 +538,8 @@ skipfirst:
size_t get_pippenger_c(size_t N)
{
-// 2:1, 4:2, 8:2, 16:3, 32:4, 64:4, 128:5, 256:6, 512:7, 1024:7, 2048:8, 4096:9
+// uncached: 2:1, 4:2, 8:2, 16:3, 32:4, 64:4, 128:5, 256:6, 512:7, 1024:7, 2048:8, 4096:9
+// cached: 2:1, 4:2, 8:2, 16:3, 32:4, 64:4, 128:5, 256:6, 512:7, 1024:7, 2048:8, 4096:9
if (N <= 2) return 1;
if (N <= 8) return 2;
if (N <= 16) return 3;
@@ -545,23 +551,55 @@ size_t get_pippenger_c(size_t N)
return 9;
}
-rct::key pippenger(const std::vector<MultiexpData> &data, size_t c)
+struct pippenger_cached_data
{
+ size_t size;
+ ge_cached *cached;
+ pippenger_cached_data(): size(0), cached(NULL) {}
+ ~pippenger_cached_data() { aligned_free(cached); }
+};
+
+std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<MultiexpData> &data, size_t N)
+{
+ MULTIEXP_PERF(PERF_TIMER_START_UNIT(pippenger_init_cache, 1000000));
+ if (N == 0)
+ N = data.size();
+ CHECK_AND_ASSERT_THROW_MES(N <= data.size(), "Bad cache base data");
+ ge_cached cached;
+ std::shared_ptr<pippenger_cached_data> cache(new pippenger_cached_data());
+
+ cache->size = N;
+ cache->cached = (ge_cached*)aligned_realloc(cache->cached, N * sizeof(ge_cached), 4096);
+ CHECK_AND_ASSERT_THROW_MES(cache->cached, "Out of memory");
+ for (size_t i = 0; i < N; ++i)
+ ge_p3_to_cached(&cache->cached[i], &data[i].point);
+
+ MULTIEXP_PERF(PERF_TIMER_STOP(pippenger_init_cache));
+ return cache;
+}
+
+size_t pippenger_get_cache_size(const std::shared_ptr<pippenger_cached_data> &cache)
+{
+ return cache->size * sizeof(*cache->cached);
+}
+
+rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache, size_t c)
+{
+ CHECK_AND_ASSERT_THROW_MES(cache == NULL || cache->size >= data.size(), "Cache is too small");
+ if (c == 0)
+ c = get_pippenger_c(data.size());
CHECK_AND_ASSERT_THROW_MES(c <= 9, "c is too large");
ge_p3 result = ge_p3_identity;
std::unique_ptr<ge_p3[]> buckets{new ge_p3[1<<c]};
- std::unique_ptr<ge_cached[]> cached_points{new ge_cached[data.size()]};
-
- for (size_t i = 0; i < data.size(); ++i)
- {
- ge_p3_to_cached(&cached_points[i], &data[i].point);
- }
+ std::shared_ptr<pippenger_cached_data> local_cache = cache == NULL ? pippenger_init_cache(data) : cache;
rct::key maxscalar = rct::zero();
for (size_t i = 0; i < data.size(); ++i)
+ {
if (maxscalar < data[i].scalar)
maxscalar = data[i].scalar;
+ }
size_t groups = 0;
while (groups < 256 && pow2(groups) < maxscalar)
++groups;
@@ -598,7 +636,7 @@ rct::key pippenger(const std::vector<MultiexpData> &data, size_t c)
CHECK_AND_ASSERT_THROW_MES(bucket < (1u<<c), "bucket overflow");
if (memcmp(&buckets[bucket], &ge_p3_identity, sizeof(ge_p3)))
{
- add(buckets[bucket], cached_points[i]);
+ add(buckets[bucket], local_cache->cached[i]);
}
else
buckets[bucket] = data[i].point;
diff --git a/src/ringct/multiexp.h b/src/ringct/multiexp.h
index 2ed8db279..559ab664a 100644
--- a/src/ringct/multiexp.h
+++ b/src/ringct/multiexp.h
@@ -54,14 +54,17 @@ struct MultiexpData {
};
struct straus_cached_data;
+struct pippenger_cached_data;
rct::key bos_coster_heap_conv(std::vector<MultiexpData> data);
rct::key bos_coster_heap_conv_robust(std::vector<MultiexpData> data);
-std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<MultiexpData> &data);
+std::shared_ptr<straus_cached_data> straus_init_cache(const std::vector<MultiexpData> &data, size_t N =0);
size_t straus_get_cache_size(const std::shared_ptr<straus_cached_data> &cache);
rct::key straus(const std::vector<MultiexpData> &data, const std::shared_ptr<straus_cached_data> &cache = NULL, size_t STEP = 0);
+std::shared_ptr<pippenger_cached_data> pippenger_init_cache(const std::vector<MultiexpData> &data, size_t N =0);
+size_t pippenger_get_cache_size(const std::shared_ptr<pippenger_cached_data> &cache);
size_t get_pippenger_c(size_t N);
-rct::key pippenger(const std::vector<MultiexpData> &data, size_t c);
+rct::key pippenger(const std::vector<MultiexpData> &data, const std::shared_ptr<pippenger_cached_data> &cache = NULL, size_t c = 0);
}