diff options
36 files changed, 910 insertions, 110 deletions
diff --git a/cmake/FindBacktrace.cmake b/cmake/FindBacktrace.cmake index 89bbad07c..8137125ab 100644 --- a/cmake/FindBacktrace.cmake +++ b/cmake/FindBacktrace.cmake @@ -83,6 +83,14 @@ else() set(_Backtrace_STD_ARGS Backtrace_LIBRARY ${_Backtrace_STD_ARGS}) endif() +message(STATUS "Backtrace_LIBRARY: ${Backtrace_LIBRARY}") +if(Backtrace_LIBRARY STREQUAL "NOTFOUND") + set(Backtrace_LIBRARY "") +endif() +if(Backtrace_LIBRARY STREQUAL "Backtrace_LIBRARY-NOTFOUND") + set(Backtrace_LIBRARY "") +endif() + set(Backtrace_LIBRARIES ${Backtrace_LIBRARY}) set(Backtrace_HEADER "${_Backtrace_HEADER_TRY}" CACHE STRING "Header providing backtrace(3) facility") diff --git a/contrib/depends/Makefile b/contrib/depends/Makefile index afa61b93b..6ab602ac0 100644 --- a/contrib/depends/Makefile +++ b/contrib/depends/Makefile @@ -22,9 +22,16 @@ host_toolchain:=$(HOST)- endif ifneq ($(DEBUG),) -release_type=debug +release_type=Debug else -release_type=release +release_type=Release +endif + +ifneq ($(TESTS),) +build_tests=ON +release_type=Debug +else +build_tests=OFF endif base_build_dir=$(BASEDIR)/work/build @@ -164,6 +171,8 @@ $(host_prefix)/share/toolchain.cmake : toolchain.cmake.in $(host_prefix)/.stamp_ -e 's|@LDFLAGS@|$(strip $(host_LDFLAGS) $(host_$(release_type)_LDFLAGS))|' \ -e 's|@allow_host_packages@|$(ALLOW_HOST_PACKAGES)|' \ -e 's|@debug@|$(DEBUG)|' \ + -e 's|@release_type@|$(release_type)|' \ + -e 's|@build_tests@|$(build_tests)|' \ -e 's|@depends@|$(host_cmake)|' \ -e 's|@prefix@|$($(host_arch)_$(host_os)_prefix)|'\ -e 's|@sdk@|$(SDK_PATH)|'\ diff --git a/contrib/depends/packages/gtest.mk b/contrib/depends/packages/gtest.mk new file mode 100644 index 000000000..5df07a32e --- /dev/null +++ b/contrib/depends/packages/gtest.mk @@ -0,0 +1,38 @@ +package=gtest +$(package)_version=1.8.1 +$(package)_download_path=https://github.com/google/googletest/archive/ +$(package)_file_name=release-$($(package)_version).tar.gz +$(package)_sha256_hash=9bf1fe5182a604b4135edc1a425ae356c9ad15e9b23f9f12a02e80184c3a249c +$(package)_cxxflags=-std=c++11 +$(package)_cxxflags_linux=-fPIC + +define $(package)_config_cmds + cd googletest && \ + CC="$(host_prefix)/native/bin/$($(package)_cc)" \ + CXX="$(host_prefix)/native/bin/$($(package)_cxx)" \ + AR="$(host_prefix)/native/bin/$($(package)_ar)" \ + RANLIB="$(host_prefix)/native/bin/$($(package)_ranlib)" \ + LIBTOOL="$(host_prefix)/native/bin/$($(package)_libtool)" \ + CXXFLAGS="$($(package)_cxxflags)" \ + CCFLAGS="$($(package)_ccflags)" \ + CPPFLAGS="$($(package)_cppflags)" \ + CFLAGS="$($(package)_cflags) $($(package)_cppflags)" \ + LDLAGS="$($(package)_ldflags)" \ + cmake -DCMAKE_INSTALL_PREFIX=$(build_prefix) \ + -DTOOLCHAIN_PREFIX=$(host_toolchain) \ + -DCMAKE_AR="$(host_prefix)/native/bin/$($(package)_ar)" \ + -DCMAKE_RANLIB="$(host_prefix)/native/bin/$($(package)_ranlib)" \ + -DCMAKE_CXX_FLAGS_DEBUG=ON +endef +# -DCMAKE_TOOLCHAIN_FILE=$(HOST)/share/toolchain.cmake + +define $(package)_build_cmds + cd googletest && CC="$(host_prefix)/native/bin/$($(package)_cc)" $(MAKE) +endef + +define $(package)_stage_cmds + mkdir $($(package)_staging_prefix_dir)/lib $($(package)_staging_prefix_dir)/include &&\ + cp googletest/libgtest.a $($(package)_staging_prefix_dir)/lib/ &&\ + cp googletest/libgtest_main.a $($(package)_staging_prefix_dir)/lib/ &&\ + cp -a googletest/include/* $($(package)_staging_prefix_dir)/include/ +endef diff --git a/contrib/depends/packages/native_cctools.mk b/contrib/depends/packages/native_cctools.mk index 44d238cc4..bcfe1af6b 100644 --- a/contrib/depends/packages/native_cctools.mk +++ b/contrib/depends/packages/native_cctools.mk @@ -52,6 +52,7 @@ endef define $(package)_stage_cmds $(MAKE) DESTDIR=$($(package)_staging_dir) install && \ + cp $($(package)_extract_dir)/cctools/misc/install_name_tool $($(package)_staging_prefix_dir)/bin/ &&\ cd $($(package)_extract_dir)/toolchain && \ mkdir -p $($(package)_staging_prefix_dir)/lib/clang/$($(package)_clang_version)/include && \ mkdir -p $($(package)_staging_prefix_dir)/bin $($(package)_staging_prefix_dir)/include && \ diff --git a/contrib/depends/packages/native_cmake-unused.mk b/contrib/depends/packages/native_cmake-unused.mk new file mode 100644 index 000000000..c9ab75711 --- /dev/null +++ b/contrib/depends/packages/native_cmake-unused.mk @@ -0,0 +1,23 @@ +package=native_cmake +$(package)_version=3.14.0 +$(package)_version_dot=v3.14 +$(package)_download_path=https://cmake.org/files/$($(package)_version_dot)/ +$(package)_file_name=cmake-$($(package)_version).tar.gz +$(package)_sha256_hash=aa76ba67b3c2af1946701f847073f4652af5cbd9f141f221c97af99127e75502 + +define $(package)_set_vars +$(package)_config_opts= +endef + +define $(package)_config_cmds + ./bootstrap &&\ + ./configure $($(package)_config_opts) +endef + +define $(package)_build_cmd + $(MAKE) +endef + +define $(package)_stage_cmds + $(MAKE) DESTDIR=$($(package)_staging_dir) install +endef diff --git a/contrib/depends/packages/packages.mk b/contrib/depends/packages/packages.mk index 1db50580b..a38819337 100644 --- a/contrib/depends/packages/packages.mk +++ b/contrib/depends/packages/packages.mk @@ -7,6 +7,10 @@ darwin_packages = sodium-darwin linux_packages = eudev qt_packages = qt +ifeq ($(build_tests),ON) +packages += gtest +endif + ifeq ($(host_os),linux) packages += unwind packages += sodium diff --git a/contrib/depends/toolchain.cmake.in b/contrib/depends/toolchain.cmake.in index b0af7bd6b..6b5434751 100644 --- a/contrib/depends/toolchain.cmake.in +++ b/contrib/depends/toolchain.cmake.in @@ -1,9 +1,16 @@ # Set the system name, either Darwin, Linux, or Windows SET(CMAKE_SYSTEM_NAME @depends@) -SET(CMAKE_BUILD_TYPE release) +SET(CMAKE_BUILD_TYPE @release_type@) -SET(STATIC true) -SET(UNBOUND_STATIC true) +OPTION(STATIC "Link libraries statically" ON) +OPTION(TREZOR_DEBUG "Main trezor debugging switch" OFF) +OPTION(BUILD_TESTS "Build tests." OFF) + +SET(STATIC ON) +SET(UNBOUND_STATIC ON) + +SET(BUILD_TESTS @build_tests@) +SET(TREZOR_DEBUG @build_tests@) # where is the target environment SET(CMAKE_FIND_ROOT_PATH @prefix@ /usr) diff --git a/contrib/epee/include/rolling_median.h b/contrib/epee/include/rolling_median.h new file mode 100644 index 000000000..8b5a82a84 --- /dev/null +++ b/contrib/epee/include/rolling_median.h @@ -0,0 +1,236 @@ +// Copyright (c) 2019, The Monero Project +// +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without modification, are +// permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this list of +// conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, this list +// of conditions and the following disclaimer in the documentation and/or other +// materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its contributors may be +// used to endorse or promote products derived from this software without specific +// prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY +// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF +// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// +// Adapted from source by AShelly: +// Copyright (c) 2011 ashelly.myopenid.com, licenced under the MIT licence +// https://stackoverflow.com/questions/5527437/rolling-median-in-c-turlach-implementation +// https://stackoverflow.com/questions/1309263/rolling-median-algorithm-in-c +// https://ideone.com/XPbl6 + +#pragma once + +#include <stdlib.h> +#include <stdint.h> + +namespace epee +{ +namespace misc_utils +{ + +template<typename Item> +struct rolling_median_t +{ +private: + Item* data; //circular queue of values + int* pos; //index into `heap` for each value + int* heap; //max/median/min heap holding indexes into `data`. + int N; //allocated size. + int idx; //position in circular queue + int minCt; //count of items in min heap + int maxCt; //count of items in max heap + int sz; //count of items in heap + +private: + + //returns true if heap[i] < heap[j] + bool mmless(int i, int j) const + { + return data[heap[i]] < data[heap[j]]; + } + + //swaps items i&j in heap, maintains indexes + bool mmexchange(int i, int j) + { + const int t = heap[i]; + heap[i] = heap[j]; + heap[j] = t; + pos[heap[i]] = i; + pos[heap[j]] = j; + return 1; + } + + //swaps items i&j if i<j; returns true if swapped + bool mmCmpExch(int i, int j) + { + return mmless(i, j) && mmexchange(i, j); + } + + //maintains minheap property for all items below i. + void minSortDown(int i) + { + for (i *= 2; i <= minCt; i *= 2) + { + if (i < minCt && mmless(i + 1, i)) + ++i; + if (!mmCmpExch(i, i / 2)) + break; + } + } + + //maintains maxheap property for all items below i. (negative indexes) + void maxSortDown(int i) + { + for (i *= 2; i >= -maxCt; i *= 2) + { + if (i > -maxCt && mmless(i, i - 1)) + --i; + if (!mmCmpExch(i / 2, i)) + break; + } + } + + //maintains minheap property for all items above i, including median + //returns true if median changed + bool minSortUp(int i) + { + while (i > 0 && mmCmpExch(i, i / 2)) + i /= 2; + return i == 0; + } + + //maintains maxheap property for all items above i, including median + //returns true if median changed + bool maxSortUp(int i) + { + while (i < 0 && mmCmpExch(i / 2, i)) + i /= 2; + return i == 0; + } + +protected: + rolling_median_t &operator=(const rolling_median_t&) = delete; + rolling_median_t(const rolling_median_t&) = delete; + +public: + //creates new rolling_median_t: to calculate `nItems` running median. + rolling_median_t(size_t N): N(N) + { + int size = N * (sizeof(Item) + sizeof(int) * 2); + data = (Item*)malloc(size); + pos = (int*) (data + N); + heap = pos + N + (N / 2); //points to middle of storage. + clear(); + } + + rolling_median_t(rolling_median_t &&m) + { + free(data); + memcpy(this, &m, sizeof(rolling_median_t)); + m.data = NULL; + } + rolling_median_t &operator=(rolling_median_t &&m) + { + free(data); + memcpy(this, &m, sizeof(rolling_median_t)); + m.data = NULL; + return *this; + } + + ~rolling_median_t() + { + free(data); + } + + void clear() + { + idx = 0; + minCt = 0; + maxCt = 0; + sz = 0; + int nItems = N; + while (nItems--) //set up initial heap fill pattern: median,max,min,max,... + { + pos[nItems] = ((nItems + 1) / 2) * ((nItems & 1) ? -1 : 1); + heap[pos[nItems]] = nItems; + } + } + + int size() const + { + return sz; + } + + //Inserts item, maintains median in O(lg nItems) + void insert(Item v) + { + int p = pos[idx]; + Item old = data[idx]; + data[idx] = v; + idx = (idx + 1) % N; + sz = std::min<int>(sz + 1, N); + if (p > 0) //new item is in minHeap + { + if (minCt < (N - 1) / 2) + { + ++minCt; + } + else if (v > old) + { + minSortDown(p); + return; + } + if (minSortUp(p) && mmCmpExch(0, -1)) + maxSortDown(-1); + } + else if (p < 0) //new item is in maxheap + { + if (maxCt < N / 2) + { + ++maxCt; + } + else if (v < old) + { + maxSortDown(p); + return; + } + if (maxSortUp(p) && minCt && mmCmpExch(1, 0)) + minSortDown(1); + } + else //new item is at median + { + if (maxCt && maxSortUp(-1)) + maxSortDown(-1); + if (minCt && minSortUp(1)) + minSortDown(1); + } + } + + //returns median item (or average of 2 when item count is even) + Item median() const + { + Item v = data[heap[0]]; + if (minCt < maxCt) + { + v = (v + data[heap[-1]]) / 2; + } + return v; + } +}; + +} +} diff --git a/src/blockchain_db/lmdb/db_lmdb.cpp b/src/blockchain_db/lmdb/db_lmdb.cpp index 340434888..a03a0989b 100644 --- a/src/blockchain_db/lmdb/db_lmdb.cpp +++ b/src/blockchain_db/lmdb/db_lmdb.cpp @@ -770,8 +770,8 @@ void BlockchainLMDB::add_block(const block& blk, size_t block_weight, uint64_t l bi.bi_timestamp = blk.timestamp; bi.bi_coins = coins_generated; bi.bi_weight = block_weight; - bi.bi_diff_hi = (cumulative_difficulty >> 64).convert_to<uint64_t>(); - bi.bi_diff_lo = (cumulative_difficulty << 64 >> 64).convert_to<uint64_t>(); + bi.bi_diff_hi = ((cumulative_difficulty >> 64) & 0xffffffffffffffff).convert_to<uint64_t>(); + bi.bi_diff_lo = (cumulative_difficulty & 0xffffffffffffffff).convert_to<uint64_t>(); bi.bi_hash = blk_hash; bi.bi_cum_rct = num_rct_outs; if (blk.major_version >= 4) diff --git a/src/cryptonote_basic/cryptonote_boost_serialization.h b/src/cryptonote_basic/cryptonote_boost_serialization.h index 3dd98f0c6..79ce610a9 100644 --- a/src/cryptonote_basic/cryptonote_boost_serialization.h +++ b/src/cryptonote_basic/cryptonote_boost_serialization.h @@ -365,11 +365,11 @@ namespace boost else { // store high part - cryptonote::difficulty_type x_ = x >> 64; + cryptonote::difficulty_type x_ = (x >> 64) & 0xffffffffffffffff; uint64_t v = x_.convert_to<uint64_t>(); a & v; // store low part - x_ = x << 64 >> 64; + x_ = x & 0xffffffffffffffff; v = x_.convert_to<uint64_t>(); a & v; } diff --git a/src/cryptonote_core/blockchain.cpp b/src/cryptonote_core/blockchain.cpp index f733efb2f..39c9f8695 100644 --- a/src/cryptonote_core/blockchain.cpp +++ b/src/cryptonote_core/blockchain.cpp @@ -179,6 +179,7 @@ Blockchain::Blockchain(tx_memory_pool& tx_pool) : m_long_term_block_weights_window(CRYPTONOTE_LONG_TERM_BLOCK_WEIGHT_WINDOW_SIZE), m_long_term_effective_median_block_weight(0), m_long_term_block_weights_cache_tip_hash(crypto::null_hash), + m_long_term_block_weights_cache_rolling_median(CRYPTONOTE_LONG_TERM_BLOCK_WEIGHT_WINDOW_SIZE), m_difficulty_for_next_block_top_hash(crypto::null_hash), m_difficulty_for_next_block(1), m_btc_valid(false) @@ -519,7 +520,10 @@ bool Blockchain::init(BlockchainDB* db, const network_type nettype, bool offline } if (test_options && test_options->long_term_block_weight_window) + { m_long_term_block_weights_window = test_options->long_term_block_weight_window; + m_long_term_block_weights_cache_rolling_median = epee::misc_utils::rolling_median_t<uint64_t>(m_long_term_block_weights_window); + } { db_txn_guard txn_guard(m_db, m_db->is_read_only()); @@ -1283,21 +1287,20 @@ void Blockchain::get_last_n_blocks_weights(std::vector<uint64_t>& weights, size_ weights = m_db->get_block_weights(start_offset, count); } //------------------------------------------------------------------ -void Blockchain::get_long_term_block_weights(std::vector<uint64_t>& weights, uint64_t start_height, size_t count) const +uint64_t Blockchain::get_long_term_block_weight_median(uint64_t start_height, size_t count) const { LOG_PRINT_L3("Blockchain::" << __func__); CRITICAL_REGION_LOCAL(m_blockchain_lock); PERF_TIMER(get_long_term_block_weights); - if (count == 0) - return; + CHECK_AND_ASSERT_THROW_MES(count > 0, "count == 0"); bool cached = false; uint64_t blockchain_height = m_db->height(); uint64_t tip_height = start_height + count - 1; crypto::hash tip_hash = crypto::null_hash; - if (tip_height < blockchain_height && count == m_long_term_block_weights_cache.size()) + if (tip_height < blockchain_height && count == (size_t)m_long_term_block_weights_cache_rolling_median.size()) { tip_hash = m_db->get_block_hash_from_height(tip_height); cached = tip_hash == m_long_term_block_weights_cache_tip_hash; @@ -1306,32 +1309,30 @@ void Blockchain::get_long_term_block_weights(std::vector<uint64_t>& weights, uin if (cached) { MTRACE("requesting " << count << " from " << start_height << ", cached"); - weights = m_long_term_block_weights_cache; - return; + return m_long_term_block_weights_cache_rolling_median.median(); } // in the vast majority of uncached cases, most is still cached, // as we just move the window one block up: - if (tip_height > 0 && count == m_long_term_block_weights_cache.size() && tip_height < blockchain_height) + if (tip_height > 0 && count == (size_t)m_long_term_block_weights_cache_rolling_median.size() && tip_height < blockchain_height) { crypto::hash old_tip_hash = m_db->get_block_hash_from_height(tip_height - 1); if (old_tip_hash == m_long_term_block_weights_cache_tip_hash) { - weights = m_long_term_block_weights_cache; - for (size_t i = 1; i < weights.size(); ++i) - weights[i - 1] = weights[i]; MTRACE("requesting " << count << " from " << start_height << ", incremental"); - weights.back() = m_db->get_block_long_term_weight(tip_height); - m_long_term_block_weights_cache = weights; m_long_term_block_weights_cache_tip_hash = tip_hash; - return; + m_long_term_block_weights_cache_rolling_median.insert(m_db->get_block_long_term_weight(tip_height)); + return m_long_term_block_weights_cache_rolling_median.median(); } } MTRACE("requesting " << count << " from " << start_height << ", uncached"); - weights = m_db->get_long_term_block_weights(start_height, count); - m_long_term_block_weights_cache = weights; + std::vector<uint64_t> weights = m_db->get_long_term_block_weights(start_height, count); m_long_term_block_weights_cache_tip_hash = tip_hash; + m_long_term_block_weights_cache_rolling_median.clear(); + for (uint64_t w: weights) + m_long_term_block_weights_cache_rolling_median.insert(w); + return m_long_term_block_weights_cache_rolling_median.median(); } //------------------------------------------------------------------ uint64_t Blockchain::get_current_cumulative_block_weight_limit() const @@ -2324,8 +2325,8 @@ bool Blockchain::find_blockchain_supplement(const std::list<crypto::hash>& qbloc if (result) { cryptonote::difficulty_type wide_cumulative_difficulty = m_db->get_block_cumulative_difficulty(resp.total_height - 1); - resp.cumulative_difficulty = (wide_cumulative_difficulty << 64 >> 64).convert_to<uint64_t>(); - resp.cumulative_difficulty_top64 = (wide_cumulative_difficulty >> 64).convert_to<uint64_t>(); + resp.cumulative_difficulty = (wide_cumulative_difficulty & 0xffffffffffffffff).convert_to<uint64_t>(); + resp.cumulative_difficulty_top64 = ((wide_cumulative_difficulty >> 64) & 0xffffffffffffffff).convert_to<uint64_t>(); } return result; @@ -3934,9 +3935,7 @@ uint64_t Blockchain::get_next_long_term_block_weight(uint64_t block_weight) cons if (hf_version < HF_VERSION_LONG_TERM_BLOCK_WEIGHT) return block_weight; - std::vector<uint64_t> weights; - get_long_term_block_weights(weights, db_height - nblocks, nblocks); - uint64_t long_term_median = epee::misc_utils::median(weights); + uint64_t long_term_median = get_long_term_block_weight_median(db_height - nblocks, nblocks); uint64_t long_term_effective_median_block_weight = std::max<uint64_t>(CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V5, long_term_median); uint64_t short_term_constraint = long_term_effective_median_block_weight + long_term_effective_median_block_weight * 2 / 5; @@ -3968,7 +3967,6 @@ bool Blockchain::update_next_cumulative_weight_limit(uint64_t *long_term_effecti { const uint64_t block_weight = m_db->get_block_weight(db_height - 1); - std::vector<uint64_t> weights, new_weights; uint64_t long_term_median; if (db_height == 1) { @@ -3979,9 +3977,7 @@ bool Blockchain::update_next_cumulative_weight_limit(uint64_t *long_term_effecti uint64_t nblocks = std::min<uint64_t>(m_long_term_block_weights_window, db_height); if (nblocks == db_height) --nblocks; - get_long_term_block_weights(weights, db_height - nblocks - 1, nblocks); - new_weights = weights; - long_term_median = epee::misc_utils::median(weights); + long_term_median = get_long_term_block_weight_median(db_height - nblocks - 1, nblocks); } m_long_term_effective_median_block_weight = std::max<uint64_t>(CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V5, long_term_median); @@ -3989,13 +3985,19 @@ bool Blockchain::update_next_cumulative_weight_limit(uint64_t *long_term_effecti uint64_t short_term_constraint = m_long_term_effective_median_block_weight + m_long_term_effective_median_block_weight * 2 / 5; long_term_block_weight = std::min<uint64_t>(block_weight, short_term_constraint); - if (new_weights.empty()) - new_weights.resize(1); - new_weights[0] = long_term_block_weight; - long_term_median = epee::misc_utils::median(new_weights); + if (db_height == 1) + { + long_term_median = long_term_block_weight; + } + else + { + m_long_term_block_weights_cache_tip_hash = m_db->get_block_hash_from_height(db_height - 1); + m_long_term_block_weights_cache_rolling_median.insert(long_term_block_weight); + long_term_median = m_long_term_block_weights_cache_rolling_median.median(); + } m_long_term_effective_median_block_weight = std::max<uint64_t>(CRYPTONOTE_BLOCK_GRANTED_FULL_REWARD_ZONE_V5, long_term_median); - weights.clear(); + std::vector<uint64_t> weights; get_last_n_blocks_weights(weights, CRYPTONOTE_REWARD_BLOCKS_WINDOW); uint64_t short_term_median = epee::misc_utils::median(weights); diff --git a/src/cryptonote_core/blockchain.h b/src/cryptonote_core/blockchain.h index 244e2a89a..6200ec87e 100644 --- a/src/cryptonote_core/blockchain.h +++ b/src/cryptonote_core/blockchain.h @@ -37,7 +37,6 @@ #include <boost/multi_index/global_fun.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/member.hpp> -#include <boost/circular_buffer.hpp> #include <atomic> #include <functional> #include <unordered_map> @@ -46,6 +45,7 @@ #include "span.h" #include "syncobj.h" #include "string_tools.h" +#include "rolling_median.h" #include "cryptonote_basic/cryptonote_basic.h" #include "common/util.h" #include "cryptonote_protocol/cryptonote_protocol_defs.h" @@ -1064,7 +1064,7 @@ namespace cryptonote uint64_t m_long_term_block_weights_window; uint64_t m_long_term_effective_median_block_weight; mutable crypto::hash m_long_term_block_weights_cache_tip_hash; - mutable std::vector<uint64_t> m_long_term_block_weights_cache; + mutable epee::misc_utils::rolling_median_t<uint64_t> m_long_term_block_weights_cache_rolling_median; epee::critical_section m_difficulty_lock; crypto::hash m_difficulty_for_next_block_top_hash; @@ -1314,15 +1314,16 @@ namespace cryptonote void get_last_n_blocks_weights(std::vector<uint64_t>& weights, size_t count) const; /** - * @brief gets recent block long term weights for median calculation + * @brief gets block long term weight median * - * get the block long term weights of the last <count> blocks, and return by reference <weights>. + * get the block long term weight median of <count> blocks starting at <start_height> * - * @param weights return-by-reference the list of weights * @param start_height the block height of the first block to query * @param count the number of blocks to get weights for + * + * @return the long term median block weight */ - void get_long_term_block_weights(std::vector<uint64_t>& weights, uint64_t start_height, size_t count) const; + uint64_t get_long_term_block_weight_median(uint64_t start_height, size_t count) const; /** * @brief checks if a transaction is unlocked (its outputs spendable) diff --git a/src/cryptonote_protocol/cryptonote_protocol_handler.inl b/src/cryptonote_protocol/cryptonote_protocol_handler.inl index 7adca3158..8958af7c7 100644 --- a/src/cryptonote_protocol/cryptonote_protocol_handler.inl +++ b/src/cryptonote_protocol/cryptonote_protocol_handler.inl @@ -410,8 +410,8 @@ namespace cryptonote m_core.get_blockchain_top(hshd.current_height, hshd.top_id); hshd.top_version = m_core.get_ideal_hard_fork_version(hshd.current_height); difficulty_type wide_cumulative_difficulty = m_core.get_block_cumulative_difficulty(hshd.current_height); - hshd.cumulative_difficulty = (wide_cumulative_difficulty << 64 >> 64).convert_to<uint64_t>(); - hshd.cumulative_difficulty_top64 = (wide_cumulative_difficulty >> 64).convert_to<uint64_t>(); + hshd.cumulative_difficulty = (wide_cumulative_difficulty & 0xffffffffffffffff).convert_to<uint64_t>(); + hshd.cumulative_difficulty_top64 = ((wide_cumulative_difficulty >> 64) & 0xffffffffffffffff).convert_to<uint64_t>(); hshd.current_height +=1; hshd.pruning_seed = m_core.get_blockchain_pruning_seed(); return true; diff --git a/src/daemon/rpc_command_executor.cpp b/src/daemon/rpc_command_executor.cpp index 186296dc9..151baa33f 100644 --- a/src/daemon/rpc_command_executor.cpp +++ b/src/daemon/rpc_command_executor.cpp @@ -722,7 +722,7 @@ bool t_rpc_command_executor::print_blockchain_info(uint64_t start_block_index, u tools::msg_writer() << "" << std::endl; tools::msg_writer() << "height: " << header.height << ", timestamp: " << header.timestamp << " (" << tools::get_human_readable_timestamp(header.timestamp) << ")" - << ", size: " << header.block_size << ", weight: " << header.block_weight << ", transactions: " << header.num_txes << std::endl + << ", size: " << header.block_size << ", weight: " << header.block_weight << " (long term " << header.long_term_weight << "), transactions: " << header.num_txes << std::endl << "major version: " << (unsigned)header.major_version << ", minor version: " << (unsigned)header.minor_version << std::endl << "block id: " << header.hash << ", previous block id: " << header.prev_hash << std::endl << "difficulty: " << header.difficulty << ", nonce " << header.nonce << ", reward " << cryptonote::print_money(header.reward) << std::endl; diff --git a/src/mnemonics/language_base.h b/src/mnemonics/language_base.h index 653314b04..7d2599e9a 100644 --- a/src/mnemonics/language_base.h +++ b/src/mnemonics/language_base.h @@ -129,7 +129,7 @@ namespace Language case 1: *wptr++ = cp; break;
case 2: *wptr++ = 0xc0 | (cp >> 6); *wptr++ = 0x80 | (cp & 0x3f); break;
case 3: *wptr++ = 0xe0 | (cp >> 12); *wptr++ = 0x80 | ((cp >> 6) & 0x3f); *wptr++ = 0x80 | (cp & 0x3f); break;
- case 4: *wptr++ = 0xf0 | (cp >> 18); *wptr += 0x80 | ((cp >> 12) & 0x3f); *wptr++ = 0x80 | ((cp >> 6) & 0x3f); *wptr++ = 0x80 | (cp & 0x3f); break;
+ case 4: *wptr++ = 0xf0 | (cp >> 18); *wptr++ = 0x80 | ((cp >> 12) & 0x3f); *wptr++ = 0x80 | ((cp >> 6) & 0x3f); *wptr++ = 0x80 | (cp & 0x3f); break;
default: throw std::runtime_error("Invalid UTF-8");
}
*wptr = 0;
diff --git a/src/p2p/net_node.inl b/src/p2p/net_node.inl index be97edbe5..ba29d92c9 100644 --- a/src/p2p/net_node.inl +++ b/src/p2p/net_node.inl @@ -1955,7 +1955,7 @@ namespace nodetool const epee::net_utils::zone zone_type = context.m_remote_address.get_zone(); network_zone& zone = m_network_zones.at(zone_type); - zone.m_peerlist.get_peerlist_head(rsp.local_peerlist_new); + zone.m_peerlist.get_peerlist_head(rsp.local_peerlist_new, true); m_payload_handler.get_payload_sync_data(rsp.payload_data); /* Tor/I2P nodes receiving connections via forwarding (from tor/i2p daemon) @@ -2058,7 +2058,7 @@ namespace nodetool }); //fill response - zone.m_peerlist.get_peerlist_head(rsp.local_peerlist_new); + zone.m_peerlist.get_peerlist_head(rsp.local_peerlist_new, true); get_local_node_data(rsp.node_data, zone); m_payload_handler.get_payload_sync_data(rsp.payload_data); LOG_DEBUG_CC(context, "COMMAND_HANDSHAKE"); diff --git a/src/p2p/net_peerlist.h b/src/p2p/net_peerlist.h index 52814af94..f4fa921e2 100644 --- a/src/p2p/net_peerlist.h +++ b/src/p2p/net_peerlist.h @@ -102,7 +102,7 @@ namespace nodetool size_t get_white_peers_count(){CRITICAL_REGION_LOCAL(m_peerlist_lock); return m_peers_white.size();} size_t get_gray_peers_count(){CRITICAL_REGION_LOCAL(m_peerlist_lock); return m_peers_gray.size();} bool merge_peerlist(const std::vector<peerlist_entry>& outer_bs); - bool get_peerlist_head(std::vector<peerlist_entry>& bs_head, uint32_t depth = P2P_DEFAULT_PEERS_IN_HANDSHAKE); + bool get_peerlist_head(std::vector<peerlist_entry>& bs_head, bool anonymize, uint32_t depth = P2P_DEFAULT_PEERS_IN_HANDSHAKE); void get_peerlist(std::vector<peerlist_entry>& pl_gray, std::vector<peerlist_entry>& pl_white); void get_peerlist(peerlist_types& peers); bool get_white_peer_by_index(peerlist_entry& p, size_t i); @@ -263,23 +263,40 @@ namespace nodetool } //-------------------------------------------------------------------------------------------------- inline - bool peerlist_manager::get_peerlist_head(std::vector<peerlist_entry>& bs_head, uint32_t depth) + bool peerlist_manager::get_peerlist_head(std::vector<peerlist_entry>& bs_head, bool anonymize, uint32_t depth) { - CRITICAL_REGION_LOCAL(m_peerlist_lock); peers_indexed::index<by_time>::type& by_time_index=m_peers_white.get<by_time>(); uint32_t cnt = 0; - bs_head.reserve(depth); + + // picks a random set of peers within the first 120%, rather than a set of the first 100%. + // The intent is that if someone asks twice, they can't easily tell: + // - this address was not in the first list, but is in the second, so the only way this can be + // is if its last_seen was recently reset, so this means the target node recently had a new + // connection to that address + // - this address was in the first list, and not in the second, which means either the address + // was moved to the gray list (if it's not accessibe, which the attacker can check if + // the address accepts incoming connections) or it was the oldest to still fit in the 250 items, + // so its last_seen is old. + const uint32_t pick_depth = anonymize ? depth + depth / 5 : depth; + bs_head.reserve(pick_depth); for(const peers_indexed::value_type& vl: boost::adaptors::reverse(by_time_index)) { - if(!vl.last_seen) - continue; - - if(cnt++ >= depth) + if(cnt++ >= pick_depth) break; bs_head.push_back(vl); } + + if (anonymize) + { + std::random_shuffle(bs_head.begin(), bs_head.end()); + if (bs_head.size() > depth) + bs_head.resize(depth); + for (auto &e: bs_head) + e.last_seen = 0; + } + return true; } //-------------------------------------------------------------------------------------------------- diff --git a/src/p2p/p2p_protocol_defs.h b/src/p2p/p2p_protocol_defs.h index 59c6099d5..85774fcd5 100644 --- a/src/p2p/p2p_protocol_defs.h +++ b/src/p2p/p2p_protocol_defs.h @@ -81,7 +81,8 @@ namespace nodetool BEGIN_KV_SERIALIZE_MAP() KV_SERIALIZE(adr) KV_SERIALIZE(id) - KV_SERIALIZE(last_seen) + if (!is_store || this_ref.last_seen != 0) + KV_SERIALIZE_OPT(last_seen, (int64_t)0) KV_SERIALIZE_OPT(pruning_seed, (uint32_t)0) KV_SERIALIZE_OPT(rpc_port, (uint16_t)0) END_KV_SERIALIZE_MAP() @@ -132,7 +133,7 @@ namespace nodetool ss << pe.id << "\t" << pe.adr.str() << " \trpc port " << (pe.rpc_port > 0 ? std::to_string(pe.rpc_port) : "-") << " \tpruning seed " << pe.pruning_seed - << " \tlast_seen: " << epee::misc_utils::get_time_interval_string(now_time - pe.last_seen) + << " \tlast_seen: " << (pe.last_seen == 0 ? std::string("never") : epee::misc_utils::get_time_interval_string(now_time - pe.last_seen)) << std::endl; } return ss.str(); diff --git a/src/rpc/core_rpc_server.cpp b/src/rpc/core_rpc_server.cpp index 97e9b482e..bbcbc2fcd 100644 --- a/src/rpc/core_rpc_server.cpp +++ b/src/rpc/core_rpc_server.cpp @@ -75,9 +75,9 @@ namespace void store_difficulty(cryptonote::difficulty_type difficulty, uint64_t &sdiff, std::string &swdiff, uint64_t &stop64) { - sdiff = (difficulty << 64 >> 64).convert_to<uint64_t>(); + sdiff = (difficulty & 0xffffffffffffffff).convert_to<uint64_t>(); swdiff = cryptonote::hex(difficulty); - stop64 = (difficulty >> 64).convert_to<uint64_t>(); + stop64 = ((difficulty >> 64) & 0xffffffffffffffff).convert_to<uint64_t>(); } } @@ -2317,7 +2317,7 @@ namespace cryptonote const uint64_t req_to_height = req.to_height ? req.to_height : (m_core.get_current_blockchain_height() - 1); for (uint64_t amount: req.amounts) { - auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, req.cumulative); + auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, [this](uint64_t height) { return m_core.get_blockchain_storage().get_db().get_block_hash_from_height(height); }, req.cumulative, m_core.get_current_blockchain_height()); if (!data) { error_resp.code = CORE_RPC_ERROR_CODE_INTERNAL_ERROR; @@ -2360,7 +2360,7 @@ namespace cryptonote const uint64_t req_to_height = req.to_height ? req.to_height : (m_core.get_current_blockchain_height() - 1); for (uint64_t amount: req.amounts) { - auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, req.cumulative); + auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, [this](uint64_t height) { return m_core.get_blockchain_storage().get_db().get_block_hash_from_height(height); }, req.cumulative, m_core.get_current_blockchain_height()); if (!data) { res.status = "Failed to get output distribution"; diff --git a/src/rpc/daemon_handler.cpp b/src/rpc/daemon_handler.cpp index 7c8953930..5c214581c 100644 --- a/src/rpc/daemon_handler.cpp +++ b/src/rpc/daemon_handler.cpp @@ -437,7 +437,7 @@ namespace rpc auto& chain = m_core.get_blockchain_storage(); res.info.wide_difficulty = chain.get_difficulty_for_next_block(); - res.info.difficulty = (res.info.wide_difficulty << 64 >> 64).convert_to<uint64_t>(); + res.info.difficulty = (res.info.wide_difficulty & 0xffffffffffffffff).convert_to<uint64_t>(); res.info.target = chain.get_difficulty_target(); @@ -459,7 +459,7 @@ namespace rpc res.info.testnet = m_core.get_nettype() == TESTNET; res.info.stagenet = m_core.get_nettype() == STAGENET; res.info.wide_cumulative_difficulty = m_core.get_blockchain_storage().get_db().get_block_cumulative_difficulty(res.info.height - 1); - res.info.cumulative_difficulty = (res.info.wide_cumulative_difficulty << 64 >> 64).convert_to<uint64_t>(); + res.info.cumulative_difficulty = (res.info.wide_cumulative_difficulty & 0xffffffffffffffff).convert_to<uint64_t>(); res.info.block_size_limit = res.info.block_weight_limit = m_core.get_blockchain_storage().get_current_cumulative_block_weight_limit(); res.info.block_size_median = res.info.block_weight_median = m_core.get_blockchain_storage().get_current_cumulative_block_weight_median(); res.info.start_time = (uint64_t)m_core.get_start_time(); @@ -778,7 +778,7 @@ namespace rpc const uint64_t req_to_height = req.to_height ? req.to_height : (m_core.get_current_blockchain_height() - 1); for (std::uint64_t amount : req.amounts) { - auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, req.cumulative); + auto data = rpc::RpcHandler::get_output_distribution([this](uint64_t amount, uint64_t from, uint64_t to, uint64_t &start_height, std::vector<uint64_t> &distribution, uint64_t &base) { return m_core.get_output_distribution(amount, from, to, start_height, distribution, base); }, amount, req.from_height, req_to_height, [this](uint64_t height) { return m_core.get_blockchain_storage().get_db().get_block_hash_from_height(height); }, req.cumulative, m_core.get_current_blockchain_height()); if (!data) { res.distributions.clear(); @@ -829,7 +829,7 @@ namespace rpc } header.wide_difficulty = m_core.get_blockchain_storage().block_difficulty(header.height); - header.difficulty = (header.wide_difficulty << 64 >> 64).convert_to<uint64_t>(); + header.difficulty = (header.wide_difficulty & 0xffffffffffffffff).convert_to<uint64_t>(); return true; } diff --git a/src/rpc/rpc_handler.cpp b/src/rpc/rpc_handler.cpp index e0a81c70f..af5cb98a3 100644 --- a/src/rpc/rpc_handler.cpp +++ b/src/rpc/rpc_handler.cpp @@ -26,26 +26,49 @@ namespace rpc } boost::optional<output_distribution_data> - RpcHandler::get_output_distribution(const std::function<bool(uint64_t, uint64_t, uint64_t, uint64_t&, std::vector<uint64_t>&, uint64_t&)> &f, uint64_t amount, uint64_t from_height, uint64_t to_height, bool cumulative) + RpcHandler::get_output_distribution(const std::function<bool(uint64_t, uint64_t, uint64_t, uint64_t&, std::vector<uint64_t>&, uint64_t&)> &f, uint64_t amount, uint64_t from_height, uint64_t to_height, const std::function<crypto::hash(uint64_t)> &get_hash, bool cumulative, uint64_t blockchain_height) { static struct D { boost::mutex mutex; std::vector<std::uint64_t> cached_distribution; std::uint64_t cached_from, cached_to, cached_start_height, cached_base; + crypto::hash cached_m10_hash; + crypto::hash cached_top_hash; bool cached; - D(): cached_from(0), cached_to(0), cached_start_height(0), cached_base(0), cached(false) {} + D(): cached_from(0), cached_to(0), cached_start_height(0), cached_base(0), cached_m10_hash(crypto::null_hash), cached_top_hash(crypto::null_hash), cached(false) {} } d; const boost::unique_lock<boost::mutex> lock(d.mutex); - if (d.cached && amount == 0 && d.cached_from == from_height && d.cached_to == to_height) + crypto::hash top_hash = crypto::null_hash; + if (d.cached_to < blockchain_height) + top_hash = get_hash(d.cached_to); + if (d.cached && amount == 0 && d.cached_from == from_height && d.cached_to == to_height && d.cached_top_hash == top_hash) return process_distribution(cumulative, d.cached_start_height, d.cached_distribution, d.cached_base); std::vector<std::uint64_t> distribution; std::uint64_t start_height, base; // see if we can extend the cache - a common case - if (d.cached && amount == 0 && d.cached_from == from_height && to_height > d.cached_to) + bool can_extend = d.cached && amount == 0 && d.cached_from == from_height && to_height > d.cached_to && top_hash == d.cached_top_hash; + if (!can_extend) + { + // we kept track of the hash 10 blocks below, if it exists, so if it matches, + // we can still pop the last 10 cached slots and try again + if (d.cached && amount == 0 && d.cached_from == from_height && d.cached_to - d.cached_from >= 10 && to_height > d.cached_to - 10) + { + crypto::hash hash10 = get_hash(d.cached_to - 10); + if (hash10 == d.cached_m10_hash) + { + d.cached_to -= 10; + d.cached_top_hash = hash10; + d.cached_m10_hash = crypto::null_hash; + d.cached_distribution.resize(d.cached_distribution.size() - 10); + can_extend = true; + } + } + } + if (can_extend) { std::vector<std::uint64_t> new_distribution; if (!f(amount, d.cached_to + 1, to_height, start_height, new_distribution, base)) @@ -74,6 +97,8 @@ namespace rpc { d.cached_from = from_height; d.cached_to = to_height; + d.cached_top_hash = get_hash(d.cached_to); + d.cached_m10_hash = d.cached_to >= 10 ? get_hash(d.cached_to - 10) : crypto::null_hash; d.cached_distribution = distribution; d.cached_start_height = start_height; d.cached_base = base; diff --git a/src/rpc/rpc_handler.h b/src/rpc/rpc_handler.h index 2439eaa58..b81983d28 100644 --- a/src/rpc/rpc_handler.h +++ b/src/rpc/rpc_handler.h @@ -32,6 +32,7 @@ #include <cstdint> #include <string> #include <vector> +#include "crypto/hash.h" namespace cryptonote { @@ -56,7 +57,7 @@ class RpcHandler virtual std::string handle(const std::string& request) = 0; static boost::optional<output_distribution_data> - get_output_distribution(const std::function<bool(uint64_t, uint64_t, uint64_t, uint64_t&, std::vector<uint64_t>&, uint64_t&)> &f, uint64_t amount, uint64_t from_height, uint64_t to_height, bool cumulative); + get_output_distribution(const std::function<bool(uint64_t, uint64_t, uint64_t, uint64_t&, std::vector<uint64_t>&, uint64_t&)> &f, uint64_t amount, uint64_t from_height, uint64_t to_height, const std::function<crypto::hash(uint64_t)> &get_hash, bool cumulative, uint64_t blockchain_height); }; diff --git a/src/serialization/difficulty_type.h b/src/serialization/difficulty_type.h index e32e24b78..c551095f9 100644 --- a/src/serialization/difficulty_type.h +++ b/src/serialization/difficulty_type.h @@ -54,8 +54,8 @@ inline bool do_serialize(Archive<true>& ar, cryptonote::difficulty_type &diff) { if (!ar.stream().good()) return false; - const uint64_t hi = (diff >> 64).convert_to<uint64_t>(); - const uint64_t lo = (diff << 64 >> 64).convert_to<uint64_t>(); + const uint64_t hi = ((diff >> 64) & 0xffffffffffffffff).convert_to<uint64_t>(); + const uint64_t lo = (diff & 0xffffffffffffffff).convert_to<uint64_t>(); ar.serialize_varint(hi); ar.serialize_varint(lo); if (!ar.stream().good()) diff --git a/src/wallet/wallet2.cpp b/src/wallet/wallet2.cpp index f5b492771..4a4abd872 100644 --- a/src/wallet/wallet2.cpp +++ b/src/wallet/wallet2.cpp @@ -1003,7 +1003,7 @@ uint64_t gamma_picker::pick() const uint64_t n_rct = rct_offsets[index] - first_rct; if (n_rct == 0) return std::numeric_limits<uint64_t>::max(); // bad pick - MDEBUG("Picking 1/" << n_rct << " in block " << index); + MTRACE("Picking 1/" << n_rct << " in block " << index); return first_rct + crypto::rand_idx(n_rct); }; @@ -7761,7 +7761,7 @@ void wallet2::get_outs(std::vector<std::vector<tools::wallet2::get_outs_entry>> } } - if (num_outs <= requested_outputs_count && !existing_ring_found) + if (num_outs <= requested_outputs_count) { for (uint64_t i = 0; i < num_outs; i++) req.outputs.push_back({amount, i}); @@ -7787,6 +7787,8 @@ void wallet2::get_outs(std::vector<std::vector<tools::wallet2::get_outs_entry>> // while we still need more mixins uint64_t num_usable_outs = num_outs; bool allow_blackballed = false; + MDEBUG("Starting gamma picking with " << num_outs << ", num_usable_outs " << num_usable_outs + << ", requested_outputs_count " << requested_outputs_count); while (num_found < requested_outputs_count) { // if we've gone through every possible output, we've gotten all we can @@ -7886,6 +7888,7 @@ void wallet2::get_outs(std::vector<std::vector<tools::wallet2::get_outs_entry>> picks[type].insert(i); req.outputs.push_back({amount, i}); ++num_found; + MDEBUG("picked " << i << ", " << num_found << " now picked"); } for (const auto &pick: picks) @@ -12626,8 +12629,7 @@ std::string wallet2::make_uri(const std::string &address, const std::string &pay if (!payment_id.empty()) { crypto::hash pid32; - crypto::hash8 pid8; - if (!wallet2::parse_long_payment_id(payment_id, pid32) && !wallet2::parse_short_payment_id(payment_id, pid8)) + if (!wallet2::parse_long_payment_id(payment_id, pid32)) { error = "Invalid payment id"; return std::string(); @@ -12721,8 +12723,7 @@ bool wallet2::parse_uri(const std::string &uri, std::string &address, std::strin return false; } crypto::hash hash; - crypto::hash8 hash8; - if (!wallet2::parse_long_payment_id(kv[1], hash) && !wallet2::parse_short_payment_id(kv[1], hash8)) + if (!wallet2::parse_long_payment_id(kv[1], hash)) { error = "Invalid payment id: " + kv[1]; return false; diff --git a/src/wallet/wallet_rpc_server.cpp b/src/wallet/wallet_rpc_server.cpp index 22eaffa6f..a51057d0b 100644 --- a/src/wallet/wallet_rpc_server.cpp +++ b/src/wallet/wallet_rpc_server.cpp @@ -2814,20 +2814,20 @@ namespace tools } crypto::hash long_payment_id; - crypto::hash8 short_payment_id; if (!wallet2::parse_long_payment_id(req.payment_id, payment_id)) { if (!wallet2::parse_short_payment_id(req.payment_id, info.payment_id)) { er.code = WALLET_RPC_ERROR_CODE_WRONG_PAYMENT_ID; - er.message = "Payment id has invalid format: \"" + req.payment_id + "\", expected 16 or 64 character string"; + er.message = "Payment id has invalid format: \"" + req.payment_id + "\", expected 64 character string"; return false; } else { - memcpy(payment_id.data, info.payment_id.data, 8); - memset(payment_id.data + 8, 0, 24); + er.code = WALLET_RPC_ERROR_CODE_WRONG_PAYMENT_ID; + er.message = "Payment id has invalid format: standalone short payment IDs are forbidden, they must be part of an integrated address"; + return false; } } } diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt index bbb0bc051..afc69ee88 100644 --- a/tests/CMakeLists.txt +++ b/tests/CMakeLists.txt @@ -66,6 +66,7 @@ else () # Emulate the FindGTest module's variable. set(GTEST_LIBRARIES gtest gtest_main) + set(GTEST_BOTH_LIBRARIES gtest gtest_main) include_directories(SYSTEM "${CMAKE_CURRENT_SOURCE_DIR}/gtest/include") endif (GTest_FOUND) diff --git a/tests/difficulty/difficulty.cpp b/tests/difficulty/difficulty.cpp index 11ce0bd73..18f1d0030 100644 --- a/tests/difficulty/difficulty.cpp +++ b/tests/difficulty/difficulty.cpp @@ -124,7 +124,7 @@ int main(int argc, char *argv[]) { cryptonote::difficulty_type wide_res = cryptonote::next_difficulty( std::vector<uint64_t>(timestamps.begin() + begin, timestamps.begin() + end), std::vector<cryptonote::difficulty_type>(wide_cumulative_difficulties.begin() + begin, wide_cumulative_difficulties.begin() + end), DEFAULT_TEST_DIFFICULTY_TARGET); - if (wide_res.convert_to<uint64_t>() != res) { + if ((wide_res & 0xffffffffffffffff).convert_to<uint64_t>() != res) { cerr << "Wrong wide difficulty for block " << n << endl << "Expected: " << res << endl << "Found: " << wide_res << endl; diff --git a/tests/functional_tests/functional_tests_rpc.py b/tests/functional_tests/functional_tests_rpc.py index e754b4e33..1a1fa5490 100755 --- a/tests/functional_tests/functional_tests_rpc.py +++ b/tests/functional_tests/functional_tests_rpc.py @@ -10,7 +10,7 @@ import string import os USAGE = 'usage: functional_tests_rpc.py <python> <srcdir> <builddir> [<tests-to-run> | all]' -DEFAULT_TESTS = ['daemon_info', 'blockchain', 'wallet_address', 'integrated_address', 'mining', 'transfer', 'txpool', 'multisig', 'cold_signing', 'sign_message', 'proofs'] +DEFAULT_TESTS = ['daemon_info', 'blockchain', 'wallet_address', 'integrated_address', 'mining', 'transfer', 'txpool', 'multisig', 'cold_signing', 'sign_message', 'proofs', 'get_output_distribution'] try: python = sys.argv[1] srcdir = sys.argv[2] diff --git a/tests/functional_tests/get_output_distribution.py b/tests/functional_tests/get_output_distribution.py new file mode 100755 index 000000000..2a0762d5e --- /dev/null +++ b/tests/functional_tests/get_output_distribution.py @@ -0,0 +1,217 @@ +#!/usr/bin/env python3 + +# Copyright (c) 2019 The Monero Project +# +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without modification, are +# permitted provided that the following conditions are met: +# +# 1. Redistributions of source code must retain the above copyright notice, this list of +# conditions and the following disclaimer. +# +# 2. Redistributions in binary form must reproduce the above copyright notice, this list +# of conditions and the following disclaimer in the documentation and/or other +# materials provided with the distribution. +# +# 3. Neither the name of the copyright holder nor the names of its contributors may be +# used to endorse or promote products derived from this software without specific +# prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY +# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +# THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +# PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +# STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF +# THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +import time + +"""Test get_output_distribution RPC +""" + +from framework.daemon import Daemon +from framework.wallet import Wallet + +class GetOutputDistributionTest(): + def run_test(self): + self.reset() + self.create() + self.test_get_output_distribution() + + def reset(self): + print 'Resetting blockchain' + daemon = Daemon() + daemon.pop_blocks(1000) + daemon.flush_txpool() + + def create(self): + self.wallet = Wallet() + # close the wallet if any, will throw if none is loaded + try: self.wallet.close_wallet() + except: pass + res = self.wallet.restore_deterministic_wallet(seed = 'velvet lymph giddy number token physics poetry unquoted nibs useful sabotage limits benches lifestyle eden nitrogen anvil fewest avoid batch vials washing fences goat unquoted') + + def test_get_output_distribution(self): + print "Test get_output_distribution" + + daemon = Daemon() + + res = daemon.get_output_distribution([0], 0, 0) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 1 + assert d.distribution[0] == 0 + + res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 1) + + res = daemon.get_output_distribution([0], 0, 0) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 2 + assert d.distribution[0] == 0 + assert d.distribution[1] == 1 + + res = daemon.pop_blocks(1) + + res = daemon.get_output_distribution([0], 0, 0) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 1 + assert d.distribution[0] == 0 + + res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 3) + + res = daemon.get_output_distribution([0], 0, 0, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 4 + assert d.distribution[0] == 0 + assert d.distribution[1] == 1 + assert d.distribution[2] == 2 + assert d.distribution[3] == 3 + + # extend + res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 80) + + res = daemon.get_output_distribution([0], 0, 0, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 84 + for h in range(len(d.distribution)): + assert d.distribution[h] == h + + # pop and replace, this will do through the "trim and extend" path + res = daemon.pop_blocks(2) + self.wallet.refresh() + dst = {'address': '42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 'amount': 1000000000000} + self.wallet.transfer([dst]) + res = daemon.generateblocks('42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', 1) + for step in range(3): # the second will be cached, the third will also be cached, but we get it in non-cumulative mode + res = daemon.get_output_distribution([0], 0, 0, cumulative = step < 3) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 83 + for h in range(len(d.distribution)): + assert d.distribution[h] == (h if step < 3 else 1) + (2 if h == len(d.distribution) - 1 else 0) + + # start at 0, end earlier + res = daemon.get_output_distribution([0], 0, 40, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 41 + for h in range(len(d.distribution)): + assert d.distribution[h] == h + + # start after 0, end earlier + res = daemon.get_output_distribution([0], 10, 20, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 9 + assert d.binary == False + assert len(d.distribution) == 11 + for h in range(len(d.distribution)): + assert d.distribution[h] == 10 + h + + # straddling up + res = daemon.get_output_distribution([0], 15, 25, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 14 + assert d.binary == False + assert len(d.distribution) == 11 + for h in range(len(d.distribution)): + assert d.distribution[h] == 15 + h + + # straddling down + res = daemon.get_output_distribution([0], 8, 18, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 7 + assert d.binary == False + assert len(d.distribution) == 11 + for h in range(len(d.distribution)): + assert d.distribution[h] == 8 + h + + # encompassing + res = daemon.get_output_distribution([0], 5, 20, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 4 + assert d.binary == False + assert len(d.distribution) == 16 + for h in range(len(d.distribution)): + assert d.distribution[h] == 5 + h + + # single + res = daemon.get_output_distribution([0], 2, 2, cumulative = True) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 0 + assert d.base == 1 + assert d.binary == False + assert len(d.distribution) == 1 + assert d.distribution[0] == 2 + + # a non existent amount + res = daemon.get_output_distribution([1], 0, 0) + assert len(res.distributions) == 1 + d = res.distributions[0] + assert d.amount == 1 + assert d.base == 0 + assert d.binary == False + assert len(d.distribution) == 83 + for h in range(len(d.distribution)): + assert d.distribution[h] == 0 + + +if __name__ == '__main__': + GetOutputDistributionTest().run_test() diff --git a/tests/hash-target.cpp b/tests/hash-target.cpp index 1e988c302..e95475cac 100644 --- a/tests/hash-target.cpp +++ b/tests/hash-target.cpp @@ -61,7 +61,7 @@ int main(int argc, char *argv[]) { for (int i = 31; i >= 0; i--) { val = val * 256 + 255; ((char *) &h)[i] = static_cast<char>(static_cast<uint64_t>(val / diff)); - val %= diff.convert_to<uint64_t>(); + val %= (diff & 0xffffffffffffffff).convert_to<uint64_t>(); } if (check_hash(h, diff) != true) { return 3; diff --git a/tests/performance_tests/check_hash.h b/tests/performance_tests/check_hash.h index d24001903..53746fec4 100644 --- a/tests/performance_tests/check_hash.h +++ b/tests/performance_tests/check_hash.h @@ -44,13 +44,13 @@ public: difficulty = difficulty_high; difficulty = (difficulty << 64) | difficulty_low; boost::multiprecision::uint256_t hash_value = std::numeric_limits<boost::multiprecision::uint256_t>::max() / hash_target; - ((uint64_t*)&hash)[0] = (hash_value << 64 >> 64).convert_to<uint64_t>(); + ((uint64_t*)&hash)[0] = (hash_value & 0xffffffffffffffff).convert_to<uint64_t>(); hash_value >>= 64; - ((uint64_t*)&hash)[1] = (hash_value << 64 >> 64).convert_to<uint64_t>(); + ((uint64_t*)&hash)[1] = (hash_value & 0xffffffffffffffff).convert_to<uint64_t>(); hash_value >>= 64; - ((uint64_t*)&hash)[2] = (hash_value << 64 >> 64).convert_to<uint64_t>(); + ((uint64_t*)&hash)[2] = (hash_value & 0xffffffffffffffff).convert_to<uint64_t>(); hash_value >>= 64; - ((uint64_t*)&hash)[3] = (hash_value << 64 >> 64).convert_to<uint64_t>(); + ((uint64_t*)&hash)[3] = (hash_value & 0xffffffffffffffff).convert_to<uint64_t>(); return true; } diff --git a/tests/unit_tests/CMakeLists.txt b/tests/unit_tests/CMakeLists.txt index 56a1f8c4d..1c4c4384c 100644 --- a/tests/unit_tests/CMakeLists.txt +++ b/tests/unit_tests/CMakeLists.txt @@ -72,6 +72,7 @@ set(unit_tests_sources parse_amount.cpp pruning.cpp random.cpp + rolling_median.cpp serialization.cpp sha256.cpp slow_memmem.cpp diff --git a/tests/unit_tests/difficulty.cpp b/tests/unit_tests/difficulty.cpp index 090fecc84..a732e6969 100644 --- a/tests/unit_tests/difficulty.cpp +++ b/tests/unit_tests/difficulty.cpp @@ -42,13 +42,13 @@ static crypto::hash MKHASH(uint64_t high, uint64_t low) hash_target = (hash_target << 64) | low; boost::multiprecision::uint256_t hash_value = std::numeric_limits<boost::multiprecision::uint256_t>::max() / hash_target; crypto::hash h; - ((uint64_t*)&h)[0] = hash_value.convert_to<uint64_t>(); + ((uint64_t*)&h)[0] = (hash_value & 0xffffffffffffffff).convert_to<uint64_t>(); hash_value >>= 64; - ((uint64_t*)&h)[1] = hash_value.convert_to<uint64_t>(); + ((uint64_t*)&h)[1] = (hash_value & 0xffffffffffffffff).convert_to<uint64_t>(); hash_value >>= 64; - ((uint64_t*)&h)[2] = hash_value.convert_to<uint64_t>(); + ((uint64_t*)&h)[2] = (hash_value & 0xffffffffffffffff).convert_to<uint64_t>(); hash_value >>= 64; - ((uint64_t*)&h)[3] = hash_value.convert_to<uint64_t>(); + ((uint64_t*)&h)[3] = (hash_value & 0xffffffffffffffff).convert_to<uint64_t>(); return h; } diff --git a/tests/unit_tests/output_distribution.cpp b/tests/unit_tests/output_distribution.cpp index 2f3c78642..38f442c59 100644 --- a/tests/unit_tests/output_distribution.cpp +++ b/tests/unit_tests/output_distribution.cpp @@ -91,36 +91,43 @@ bool get_output_distribution(uint64_t amount, uint64_t from, uint64_t to, uint64 return r && bc->get_output_distribution(amount, from, to, start_height, distribution, base); } +crypto::hash get_block_hash(uint64_t height) +{ + crypto::hash hash; + *((uint64_t*)&hash) = height; + return hash; +} + TEST(output_distribution, extend) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 2); ASSERT_EQ(res->distribution, std::vector<uint64_t>({5, 0})); - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, true); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 29, ::get_block_hash, true, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 2); ASSERT_EQ(res->distribution, std::vector<uint64_t>({55, 55})); - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 3); ASSERT_EQ(res->distribution, std::vector<uint64_t>({5, 0, 2})); - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, true); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 30, ::get_block_hash, true, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 3); ASSERT_EQ(res->distribution, std::vector<uint64_t>({55, 55, 57})); - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 4); ASSERT_EQ(res->distribution, std::vector<uint64_t>({5, 0, 2, 3})); - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, true); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 28, 31, ::get_block_hash, true, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 4); ASSERT_EQ(res->distribution, std::vector<uint64_t>({55, 55, 57, 60})); @@ -130,7 +137,7 @@ TEST(output_distribution, one) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 0, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 0, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 1); ASSERT_EQ(res->distribution.back(), 0); @@ -140,7 +147,7 @@ TEST(output_distribution, full_cumulative) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, true); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, ::get_block_hash, true, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 32); ASSERT_EQ(res->distribution.back(), 60); @@ -150,7 +157,7 @@ TEST(output_distribution, full_noncumulative) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 0, 31, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 32); for (size_t i = 0; i < 32; ++i) @@ -161,7 +168,7 @@ TEST(output_distribution, part_cumulative) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, true); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, ::get_block_hash, true, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 5); ASSERT_EQ(res->distribution, std::vector<uint64_t>({0, 1, 6, 7, 11})); @@ -171,7 +178,7 @@ TEST(output_distribution, part_noncumulative) { boost::optional<cryptonote::rpc::output_distribution_data> res; - res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, false); + res = cryptonote::rpc::RpcHandler::get_output_distribution(::get_output_distribution, 0, 4, 8, ::get_block_hash, false, test_distribution_size); ASSERT_TRUE(res != boost::none); ASSERT_EQ(res->distribution.size(), 5); ASSERT_EQ(res->distribution, std::vector<uint64_t>({0, 1, 5, 1, 4})); diff --git a/tests/unit_tests/rolling_median.cpp b/tests/unit_tests/rolling_median.cpp new file mode 100644 index 000000000..6d6adcc7d --- /dev/null +++ b/tests/unit_tests/rolling_median.cpp @@ -0,0 +1,202 @@ +// Copyright (c) 2019, The Monero Project +// +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without modification, are +// permitted provided that the following conditions are met: +// +// 1. Redistributions of source code must retain the above copyright notice, this list of +// conditions and the following disclaimer. +// +// 2. Redistributions in binary form must reproduce the above copyright notice, this list +// of conditions and the following disclaimer in the documentation and/or other +// materials provided with the distribution. +// +// 3. Neither the name of the copyright holder nor the names of its contributors may be +// used to endorse or promote products derived from this software without specific +// prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY +// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL +// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF +// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#include <random> +#include "gtest/gtest.h" +#include "misc_language.h" +#include "rolling_median.h" +#include "crypto/crypto.h" + +TEST(rolling_median, one) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(1); + m.insert(42); + ASSERT_EQ(m.median(), 42); + m.insert(18); + ASSERT_EQ(m.median(), 18); + m.insert(7483); + ASSERT_EQ(m.median(), 7483); +} + +TEST(rolling_median, two) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(2); + m.insert(42); + ASSERT_EQ(m.median(), 42); + m.insert(45); + ASSERT_EQ(m.median(), 43); + m.insert(49); + ASSERT_EQ(m.median(), 47); + m.insert(41); + ASSERT_EQ(m.median(), 45); + m.insert(43); + ASSERT_EQ(m.median(), 42); + m.insert(40); + ASSERT_EQ(m.median(), 41); + m.insert(41); + ASSERT_EQ(m.median(), 40); +} + +TEST(rolling_median, series) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(100); + std::vector<uint64_t> v; + v.reserve(100); + for (int i = 0; i < 10000; ++i) + { + uint64_t r = rand(); + v.push_back(r); + if (v.size() > 100) + v.erase(v.begin()); + m.insert(r); + std::vector<uint64_t> vcopy = v; + ASSERT_EQ(m.median(), epee::misc_utils::median(vcopy)); + } +} + +TEST(rolling_median, clear_whole) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(100); + std::vector<uint64_t> random, median; + random.reserve(10000); + median.reserve(10000); + for (int i = 0; i < 10000; ++i) + { + random.push_back(rand()); + m.insert(random.back()); + median.push_back(m.median()); + } + m.clear(); + for (int i = 0; i < 10000; ++i) + { + m.insert(random[i]); + ASSERT_EQ(median[i], m.median()); + } +} + +TEST(rolling_median, clear_partway) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(100); + std::vector<uint64_t> random, median; + random.reserve(10000); + median.reserve(10000); + for (int i = 0; i < 10000; ++i) + { + random.push_back(rand()); + m.insert(random.back()); + median.push_back(m.median()); + } + m.clear(); + for (int i = 10000 - 100; i < 10000; ++i) + { + m.insert(random[i]); + } + ASSERT_EQ(median[10000-1], m.median()); +} + +TEST(rolling_median, order) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(1000); + std::vector<uint64_t> random; + random.reserve(1000); + for (int i = 0; i < 1000; ++i) + { + random.push_back(rand()); + m.insert(random.back()); + } + const uint64_t med = m.median(); + + std::sort(random.begin(), random.end(), [](uint64_t a, uint64_t b) { return a < b; }); + m.clear(); + for (int i = 0; i < 1000; ++i) + m.insert(random[i]); + ASSERT_EQ(med, m.median()); + + std::sort(random.begin(), random.end(), [](uint64_t a, uint64_t b) { return a > b; }); + m.clear(); + for (int i = 0; i < 1000; ++i) + m.insert(random[i]); + ASSERT_EQ(med, m.median()); + + std::shuffle(random.begin(), random.end(), std::default_random_engine(crypto::rand<unsigned>())); + m.clear(); + for (int i = 0; i < 1000; ++i) + m.insert(random[i]); + ASSERT_EQ(med, m.median()); +} + +TEST(rolling_median, history_blind) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(10); + + uint64_t median = 0; + for (int i = 0; i < 1000; ++i) + { + m.clear(); + int history_length = 743723 % (i+1); + while (history_length--) + m.insert(743284 % (i+1)); + for (int j = 0; j < 10; ++j) + m.insert(8924829384 % (j+1)); + if (i == 0) + median = m.median(); + else + ASSERT_EQ(median, m.median()); + } +} + +TEST(rolling_median, size) +{ + epee::misc_utils::rolling_median_t<uint64_t> m(10); + + ASSERT_EQ(m.size(), 0); + m.insert(1); + ASSERT_EQ(m.size(), 1); + m.insert(2); + ASSERT_EQ(m.size(), 2); + m.clear(); + ASSERT_EQ(m.size(), 0); + for (int i = 0; i < 10; ++i) + { + m.insert(80 % (i + 1)); + ASSERT_EQ(m.size(), i + 1); + } + m.insert(1); + ASSERT_EQ(m.size(), 10); + m.insert(2); + ASSERT_EQ(m.size(), 10); + m.clear(); + ASSERT_EQ(m.size(), 0); + m.insert(4); + ASSERT_EQ(m.size(), 1); + for (int i = 0; i < 1000; ++i) + { + m.insert(80 % (i + 1)); + ASSERT_EQ(m.size(), std::min<int>(10, i + 2)); + } +} diff --git a/tests/unit_tests/uri.cpp b/tests/unit_tests/uri.cpp index df1dbc130..04d935751 100644 --- a/tests/unit_tests/uri.cpp +++ b/tests/unit_tests/uri.cpp @@ -144,9 +144,7 @@ TEST(uri, bad_payment_id) TEST(uri, short_payment_id) { - PARSE_URI("monero:" TEST_ADDRESS"?tx_payment_id=1234567890123456", true); - ASSERT_EQ(address, TEST_ADDRESS); - ASSERT_EQ(payment_id, "1234567890123456"); + PARSE_URI("monero:" TEST_ADDRESS"?tx_payment_id=1234567890123456", false); } TEST(uri, long_payment_id) |