diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index f71b12bd9b..766d9e4276 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -1,357 +1,358 @@ # Copyright (c) 2017 The Bitcoin developers cmake_minimum_required(VERSION 3.5) project(BitcoinABC) set(CMAKE_CXX_STANDARD 14) # Default visibility is hidden on all targets. set(CMAKE_C_VISIBILITY_PRESET hidden) set(CMAKE_CXX_VISIBILITY_PRESET hidden) option(BUILD_BITCOIN_WALLET "Activate the wallet functionality" ON) option(BUILD_BITCOIN_ZMQ "Activate the ZeroMQ functionalities" ON) option(BUILD_BITCOIN_SEEDER "Build bitcoin-seeder" ON) option(BUILD_BITCOIN_CLI "Build bitcoin-cli" ON) option(BUILD_BITCOIN_TX "Build bitcoin-tx" ON) option(BUILD_BITCOIN_QT "Build bitcoin-qt" ON) option(ENABLE_HARDENING "Harden the executables" ON) # Cmake uses the CMAKE_BUILD_TYPE variable to select the build configuration. # By default it supports more configurations that needed for Bitcoin ABC, and # all the releases types set NDEBUG which is unwanted as it disables the assert # completely. # Remove the -DNDEBUG flag from the CFLAGS/CXXFLAGS in all the configurations include(AddCompilerFlags) remove_compiler_flags(-DNDEBUG) # Overrides the flags for the Debug build type # This mimics the autotools behavior by setting the CFLAGS to '-g -O2`, which # are not well suited for debugging. # FIXME: update CFLAGS with better debug oriented optimization flags set(CMAKE_C_FLAGS_DEBUG "-g -O2") # Prefer -g3, defaults to -g if unavailable add_cxx_compiler_flag_with_fallback(CMAKE_CXX_FLAGS_DEBUG -g3 -g) # Prefer -Og, defaults to -O0 if unavailable add_cxx_compiler_flag_with_fallback(CMAKE_CXX_FLAGS_DEBUG -Og -O0) # Define the debugging symbols DEBUG and DEBUG_LOCKORDER when the Debug build # type is selected. string(APPEND CMAKE_CXX_FLAGS_DEBUG " -DDEBUG -DDEBUG_LOCKORDER") # Ensure that WINDRES_PREPROC is enabled when using windres. if(${CMAKE_SYSTEM_NAME} MATCHES "Windows") # Ensure that WINDRES_PREPROC is enabled when using windres. list(APPEND CMAKE_RC_FLAGS "-DWINDRES_PREPROC") # Build all static so there is no dll file to distribute. add_compiler_flag(-static) endif() # All windows code is PIC, forcing it on just adds useless compile warnings if(NOT ${CMAKE_SYSTEM_NAME} MATCHES "Windows") add_compiler_flag(-fPIC) endif() if(ENABLE_HARDENING) # Enable stack protection add_cxx_compiler_flag(-fstack-protector-all -Wstack-protector) # Enable some buffer overflow checking add_compiler_flag(-U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=2) # Enable ASLR (these flags are primarily targeting MinGw) add_linker_flag(-Wl,--dynamicbase -Wl,--nxcompat -Wl,--high-entropy-va) # Make the relocated sections read-only add_linker_flag(-Wl,-z,relro -Wl,-z,now) # CMake provides the POSITION_INDEPENDENT_CODE property to set PIC/PIE. # Unfortunately setting the -pie linker flag this way require CMake >= 3.14, # which is not widely distributed at the time of writing. # FIXME: use the POSITION_INDEPENDENT_CODE property instead if(NOT ${CMAKE_SYSTEM_NAME} MATCHES "Windows") add_compiler_flag(-fPIE) add_linker_flag(-pie) else() # MinGw provides its own libssp for stack smashing protection link_libraries(ssp) endif() endif() # Enable warning add_c_compiler_flag(-Wnested-externs -Wstrict-prototypes) add_compiler_flag( -Wall -Wextra -Wformat -Wvla -Wformat-security -Wcast-align -Wunused-parameter -Wmissing-braces # FIXME: Activating this flag cause cmake to fail on leveldb. # -Wthread-safety-analysis -Wshadow ) option(EXTRA_WARNINGS "Enable extra warnings" OFF) if(EXTRA_WARNINGS) add_cxx_compiler_flag(-Wsuggest-override) else() add_compiler_flag(-Wno-unused-parameter) endif() # Create a target for OpenSSL include(BrewHelper) find_brew_prefix(OPENSSL_ROOT_DIR openssl) find_package(OpenSSL REQUIRED) # libtool style configure add_subdirectory(config) # libraries add_subdirectory(crypto) add_subdirectory(leveldb) add_subdirectory(secp256k1) add_subdirectory(univalue) # Because the Bitcoin ABc source code is disorganised, we # end up with a bunch of libraries without any aparent # cohesive structure. This is inherited from Bitcoin Core # and reflecting this. # TODO: Improve the structure once cmake is rocking. # Various completely unrelated features shared by all executables. add_library(util chainparamsbase.cpp clientversion.cpp compat/glibc_sanity.cpp compat/glibcxx_sanity.cpp compat/strnlen.cpp fs.cpp logging.cpp random.cpp rcu.cpp rpc/protocol.cpp support/cleanse.cpp support/lockedpool.cpp sync.cpp threadinterrupt.cpp uint256.cpp util.cpp utilmoneystr.cpp utilstrencodings.cpp utiltime.cpp ) target_compile_definitions(util PUBLIC HAVE_CONFIG_H) target_include_directories(util PUBLIC . # To access the config. ${CMAKE_CURRENT_BINARY_DIR} ) # Target specific configs if(${CMAKE_SYSTEM_NAME} MATCHES "Windows") set(Boost_USE_STATIC_LIBS ON) set(Boost_THREADAPI win32) find_package(SHLWAPI REQUIRED) target_link_libraries(util ${SHLWAPI_LIBRARY}) target_include_directories(util PUBLIC ${SHLWAPI_INCLUDE_DIR}) find_library(WS2_32_LIBRARY NAMES ws2_32) target_link_libraries(util ${WS2_32_LIBRARY}) target_compile_definitions(util PUBLIC BOOST_THREAD_USE_LIB) endif() # Boost packages set(BOOST_PACKAGES_REQUIRED chrono filesystem program_options thread) function(prepend var prefix) set(listVar "") foreach(f ${ARGN}) list(APPEND listVar "${prefix}${f}") endforeach(f) set(${var} "${listVar}" PARENT_SCOPE) endfunction(prepend) prepend(BOOST_LIBRARIES "Boost::" ${BOOST_PACKAGES_REQUIRED}) find_package(Boost 1.58 REQUIRED ${BOOST_PACKAGES_REQUIRED}) target_link_libraries(util univalue crypto ${BOOST_LIBRARIES}) # Make sure boost uses std::atomic (it doesn't before 1.63) target_compile_definitions(util PUBLIC BOOST_SP_USE_STD_ATOMIC BOOST_AC_USE_STD_ATOMIC) # More completely unrelated features shared by all executables. # Because nothing says this is different from util than "common" add_library(common amount.cpp base58.cpp cashaddr.cpp cashaddrenc.cpp chainparams.cpp config.cpp consensus/merkle.cpp coins.cpp compressor.cpp dstencode.cpp feerate.cpp globals.cpp core_read.cpp core_write.cpp key.cpp keystore.cpp netaddress.cpp netbase.cpp primitives/block.cpp protocol.cpp scheduler.cpp script/sign.cpp script/standard.cpp warnings.cpp ) target_link_libraries(common util secp256k1) # libbitcoinconsensus add_library(bitcoinconsensus arith_uint256.cpp hash.cpp primitives/transaction.cpp pubkey.cpp script/bitcoinconsensus.cpp script/interpreter.cpp script/script.cpp script/script_error.cpp script/sigencoding.cpp uint256.cpp utilstrencodings.cpp ) target_link_libraries(bitcoinconsensus common) # Bitcoin server facilities add_library(server addrman.cpp addrdb.cpp avalanche.cpp bloom.cpp blockencodings.cpp + blockfilter.cpp chain.cpp checkpoints.cpp config.cpp consensus/activation.cpp consensus/tx_verify.cpp globals.cpp httprpc.cpp httpserver.cpp init.cpp dbwrapper.cpp merkleblock.cpp miner.cpp net.cpp net_processing.cpp noui.cpp policy/fees.cpp policy/policy.cpp pow.cpp rest.cpp rpc/abc.cpp rpc/blockchain.cpp rpc/command.cpp rpc/jsonrpcrequest.cpp rpc/mining.cpp rpc/misc.cpp rpc/net.cpp rpc/rawtransaction.cpp rpc/safemode.cpp rpc/server.cpp script/scriptcache.cpp script/sigcache.cpp script/ismine.cpp timedata.cpp torcontrol.cpp txdb.cpp txmempool.cpp ui_interface.cpp validation.cpp validationinterface.cpp ) # This require libevent find_package(Event REQUIRED) target_include_directories(server PRIVATE leveldb/helpers/memenv) target_link_libraries(server Event bitcoinconsensus leveldb memenv ) # Test suite. add_subdirectory(test) # Benchmark suite. add_subdirectory(bench) # Wallet if(BUILD_BITCOIN_WALLET) add_subdirectory(wallet) target_link_libraries(server wallet) endif() # ZeroMQ if(BUILD_BITCOIN_ZMQ) add_subdirectory(zmq) target_link_libraries(server zmq) endif() # RPC client support add_library(rpcclient rpc/client.cpp) target_link_libraries(rpcclient univalue util) # bitcoin-seeder if(BUILD_BITCOIN_SEEDER) add_subdirectory(seeder) endif() # bitcoin-cli if(BUILD_BITCOIN_CLI) add_executable(bitcoin-cli bitcoin-cli.cpp) if(${CMAKE_SYSTEM_NAME} MATCHES "Windows") target_sources(bitcoin-cli PRIVATE bitcoin-cli-res.rc) endif() target_link_libraries(bitcoin-cli common rpcclient Event) endif() # bitcoin-tx if(BUILD_BITCOIN_TX) add_executable(bitcoin-tx bitcoin-tx.cpp) if(${CMAKE_SYSTEM_NAME} MATCHES "Windows") target_sources(bitcoin-tx PRIVATE bitcoin-tx-res.rc) endif() target_link_libraries(bitcoin-tx bitcoinconsensus) endif() # bitcoind add_executable(bitcoind bitcoind.cpp) target_link_libraries(bitcoind server) if(${CMAKE_SYSTEM_NAME} MATCHES "Windows") target_sources(bitcoind PRIVATE bitcoind-res.rc) endif() # Bitcoin-qt if(BUILD_BITCOIN_QT) add_subdirectory(qt) endif() diff --git a/src/Makefile.am b/src/Makefile.am index fe65f88064..9800552fae 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -1,648 +1,650 @@ # Copyright (c) 2013-2016 The Bitcoin Core developers # Distributed under the MIT software license, see the accompanying # file COPYING or http://www.opensource.org/licenses/mit-license.php. DIST_SUBDIRS = secp256k1 univalue AM_LDFLAGS = $(PTHREAD_CFLAGS) $(LIBTOOL_LDFLAGS) $(HARDENED_LDFLAGS) $(SANITIZER_LDFLAGS) AM_CXXFLAGS = $(DEBUG_CXXFLAGS) $(HARDENED_CXXFLAGS) $(ERROR_CXXFLAGS) $(SANITIZER_CXXFLAGS) AM_CPPFLAGS = $(DEBUG_CPPFLAGS) $(HARDENED_CPPFLAGS) EXTRA_LIBRARIES = if EMBEDDED_UNIVALUE LIBUNIVALUE = univalue/libunivalue.la $(LIBUNIVALUE): $(wildcard univalue/lib/*) $(wildcard univalue/include/*) $(AM_V_at)$(MAKE) $(AM_MAKEFLAGS) -C $(@D) $(@F) else LIBUNIVALUE = $(UNIVALUE_LIBS) endif BITCOIN_INCLUDES=-I$(builddir) -I$(builddir)/obj $(BDB_CPPFLAGS) $(BOOST_CPPFLAGS) $(LEVELDB_CPPFLAGS) $(CRYPTO_CFLAGS) $(SSL_CFLAGS) BITCOIN_INCLUDES += -I$(srcdir)/secp256k1/include BITCOIN_INCLUDES += $(UNIVALUE_CFLAGS) BITCOIN_SEEDER_INCLUDES = -I$(srcdir)/seeder BITCOIN_SEEDER_INCLUDES += $(BITCOIN_INCLUDES) LIBBITCOIN_SERVER=libbitcoin_server.a LIBBITCOIN_COMMON=libbitcoin_common.a LIBBITCOIN_CONSENSUS=libbitcoin_consensus.a LIBBITCOIN_CLI=libbitcoin_cli.a LIBBITCOIN_UTIL=libbitcoin_util.a LIBBITCOIN_CRYPTO_BASE=crypto/libbitcoin_crypto_base.a LIBBITCOINQT=qt/libbitcoinqt.a LIBSECP256K1=secp256k1/libsecp256k1.la if ENABLE_ZMQ LIBBITCOIN_ZMQ=libbitcoin_zmq.a endif if BUILD_BITCOIN_LIBS LIBBITCOINCONSENSUS=libbitcoinconsensus.la endif if BUILD_BITCOIN_SEEDER LIBBITCOIN_SEEDER=libbitcoin_seeder.a endif if ENABLE_WALLET LIBBITCOIN_WALLET=libbitcoin_wallet.a endif LIBBITCOIN_CRYPTO= $(LIBBITCOIN_CRYPTO_BASE) if ENABLE_SSE41 LIBBITCOIN_CRYPTO_SSE41 = crypto/libbitcoin_crypto_sse41.a LIBBITCOIN_CRYPTO += $(LIBBITCOIN_CRYPTO_SSE41) endif if ENABLE_AVX2 LIBBITCOIN_CRYPTO_AVX2 = crypto/libbitcoin_crypto_avx2.a LIBBITCOIN_CRYPTO += $(LIBBITCOIN_CRYPTO_AVX2) endif if ENABLE_SHANI LIBBITCOIN_CRYPTO_SHANI = crypto/libbitcoin_crypto_shani.a LIBBITCOIN_CRYPTO += $(LIBBITCOIN_CRYPTO_SHANI) endif $(LIBSECP256K1): $(wildcard secp256k1/src/*) $(wildcard secp256k1/include/*) $(AM_V_at)$(MAKE) $(AM_MAKEFLAGS) -C $(@D) $(@F) # Make is not made aware of per-object dependencies to avoid limiting building parallelization # But to build the less dependent modules first, we manually select their order here: EXTRA_LIBRARIES += \ $(LIBBITCOIN_CRYPTO) \ $(LIBBITCOIN_UTIL) \ $(LIBBITCOIN_COMMON) \ $(LIBBITCOIN_CONSENSUS) \ $(LIBBITCOIN_SERVER) \ $(LIBBITCOIN_CLI) \ $(LIBBITCOIN_SEEDER) \ $(LIBBITCOIN_WALLET) \ $(LIBBITCOIN_ZMQ) lib_LTLIBRARIES = $(LIBBITCOINCONSENSUS) bin_PROGRAMS = noinst_PROGRAMS = TESTS = BENCHMARKS = if BUILD_BITCOIND bin_PROGRAMS += bitcoind endif if BUILD_BITCOIN_SEEDER bin_PROGRAMS += bitcoin-seeder endif if BUILD_BITCOIN_UTILS bin_PROGRAMS += bitcoin-cli bitcoin-tx endif .PHONY: FORCE check-symbols check-security # bitcoin core # BITCOIN_CORE_H = \ addrdb.h \ addrman.h \ avalanche.h \ base58.h \ bloom.h \ blockencodings.h \ blockfileinfo.h \ + blockfilter.h \ blockindexworkcomparator.h \ blockstatus.h \ blockvalidity.h \ cashaddr.h \ cashaddrenc.h \ chain.h \ chainparams.h \ chainparamsbase.h \ chainparamsseeds.h \ checkpoints.h \ checkqueue.h \ clientversion.h \ coins.h \ compat.h \ compat/byteswap.h \ compat/endian.h \ compat/sanity.h \ compressor.h \ config.h \ consensus/activation.h \ consensus/consensus.h \ consensus/tx_verify.h \ core_io.h \ core_memusage.h \ cuckoocache.h \ diskblockpos.h \ dstencode.h \ fs.h \ globals.h \ httprpc.h \ httpserver.h \ indirectmap.h \ init.h \ key.h \ keystore.h \ dbwrapper.h \ limitedmap.h \ logging.h \ memusage.h \ merkleblock.h \ miner.h \ net.h \ net_processing.h \ netaddress.h \ netbase.h \ netmessagemaker.h \ noui.h \ policy/fees.h \ policy/policy.h \ pow.h \ protocol.h \ radix.h \ random.h \ rcu.h \ reverse_iterator.h \ reverselock.h \ rpc/blockchain.h \ rpc/client.h \ rpc/command.h \ rpc/jsonrpcrequest.h \ rpc/mining.h \ rpc/misc.h \ rpc/protocol.h \ rpc/rawtransaction.h \ rpc/safemode.h \ rpc/server.h \ rpc/tojson.h \ rpc/register.h \ rwcollection.h \ scheduler.h \ script/scriptcache.h \ script/sigcache.h \ script/sign.h \ script/standard.h \ script/ismine.h \ streams.h \ support/allocators/secure.h \ support/allocators/zeroafterfree.h \ support/cleanse.h \ support/events.h \ support/lockedpool.h \ sync.h \ threadsafety.h \ threadinterrupt.h \ timedata.h \ torcontrol.h \ txdb.h \ txmempool.h \ ui_interface.h \ undo.h \ util.h \ utilmoneystr.h \ utiltime.h \ validation.h \ validationinterface.h \ versionbits.h \ walletinitinterface.h \ wallet/coincontrol.h \ wallet/crypter.h \ wallet/db.h \ wallet/finaltx.h \ wallet/rpcdump.h \ wallet/fees.h \ wallet/rpcwallet.h \ wallet/wallet.h \ wallet/walletdb.h \ wallet/walletutil.h \ warnings.h \ zmq/zmqabstractnotifier.h \ zmq/zmqconfig.h\ zmq/zmqnotificationinterface.h \ zmq/zmqpublishnotifier.h obj/build.h: FORCE @$(MKDIR_P) "$(builddir)/obj" @$(top_srcdir)/share/genbuild.sh "$(abs_top_builddir)/src/obj/build.h" \ "$(abs_top_srcdir)" libbitcoin_util_a-clientversion.$(OBJEXT): obj/build.h # server: shared between bitcoind and bitcoin-qt libbitcoin_server_a_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) $(MINIUPNPC_CPPFLAGS) $(EVENT_CFLAGS) $(EVENT_PTHREADS_CFLAGS) libbitcoin_server_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) libbitcoin_server_a_SOURCES = \ addrman.cpp \ addrdb.cpp \ avalanche.cpp \ bloom.cpp \ blockencodings.cpp \ + blockfilter.cpp \ chain.cpp \ checkpoints.cpp \ config.cpp \ consensus/activation.cpp \ consensus/tx_verify.cpp \ globals.cpp \ httprpc.cpp \ httpserver.cpp \ init.cpp \ dbwrapper.cpp \ merkleblock.cpp \ miner.cpp \ net.cpp \ net_processing.cpp \ noui.cpp \ policy/fees.cpp \ policy/policy.cpp \ pow.cpp \ rest.cpp \ rpc/abc.cpp \ rpc/blockchain.cpp \ rpc/command.cpp \ rpc/jsonrpcrequest.cpp \ rpc/mining.cpp \ rpc/misc.cpp \ rpc/net.cpp \ rpc/rawtransaction.cpp \ rpc/safemode.cpp \ rpc/server.cpp \ script/scriptcache.cpp \ script/sigcache.cpp \ script/ismine.cpp \ timedata.cpp \ torcontrol.cpp \ txdb.cpp \ txmempool.cpp \ ui_interface.cpp \ validation.cpp \ validationinterface.cpp \ $(BITCOIN_CORE_H) if ENABLE_ZMQ libbitcoin_zmq_a_CPPFLAGS = $(BITCOIN_INCLUDES) $(ZMQ_CFLAGS) libbitcoin_zmq_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) libbitcoin_zmq_a_SOURCES = \ zmq/zmqabstractnotifier.cpp \ zmq/zmqnotificationinterface.cpp \ zmq/zmqpublishnotifier.cpp endif # wallet: shared between bitcoind and bitcoin-qt, but only linked # when wallet enabled libbitcoin_wallet_a_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) libbitcoin_wallet_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) libbitcoin_wallet_a_SOURCES = \ wallet/crypter.cpp \ wallet/db.cpp \ wallet/finaltx.cpp \ wallet/fees.cpp \ wallet/init.cpp \ wallet/rpcdump.cpp \ wallet/rpcwallet.cpp \ wallet/wallet.cpp \ wallet/walletdb.cpp \ wallet/walletutil.cpp \ $(BITCOIN_CORE_H) # crypto primitives library crypto_libbitcoin_crypto_base_a_CPPFLAGS = $(AM_CPPFLAGS) crypto_libbitcoin_crypto_base_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) crypto_libbitcoin_crypto_base_a_SOURCES = \ crypto/aes.cpp \ crypto/aes.h \ crypto/chacha20.h \ crypto/chacha20.cpp \ crypto/common.h \ crypto/hmac_sha256.cpp \ crypto/hmac_sha256.h \ crypto/hmac_sha512.cpp \ crypto/hmac_sha512.h \ crypto/ripemd160.cpp \ crypto/ripemd160.h \ crypto/sha1.cpp \ crypto/sha1.h \ crypto/sha256.cpp \ crypto/sha256.h \ crypto/sha512.cpp \ crypto/sha512.h if USE_ASM crypto_libbitcoin_crypto_base_a_SOURCES += crypto/sha256_sse4.cpp endif crypto_libbitcoin_crypto_sse41_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) crypto_libbitcoin_crypto_sse41_a_CPPFLAGS = $(AM_CPPFLAGS) crypto_libbitcoin_crypto_sse41_a_CXXFLAGS += $(SSE41_CXXFLAGS) crypto_libbitcoin_crypto_sse41_a_CPPFLAGS += -DENABLE_SSE41 crypto_libbitcoin_crypto_sse41_a_SOURCES = crypto/sha256_sse41.cpp crypto_libbitcoin_crypto_avx2_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) crypto_libbitcoin_crypto_avx2_a_CPPFLAGS = $(AM_CPPFLAGS) crypto_libbitcoin_crypto_avx2_a_CXXFLAGS += $(AVX2_CXXFLAGS) crypto_libbitcoin_crypto_avx2_a_CPPFLAGS += -DENABLE_AVX2 crypto_libbitcoin_crypto_avx2_a_SOURCES = crypto/sha256_avx2.cpp crypto_libbitcoin_crypto_shani_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) crypto_libbitcoin_crypto_shani_a_CPPFLAGS = $(AM_CPPFLAGS) crypto_libbitcoin_crypto_shani_a_CXXFLAGS += $(SHANI_CXXFLAGS) crypto_libbitcoin_crypto_shani_a_CPPFLAGS += -DENABLE_SHANI crypto_libbitcoin_crypto_shani_a_SOURCES = crypto/sha256_shani.cpp # consensus: shared between all executables that validate any consensus rules. libbitcoin_consensus_a_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) libbitcoin_consensus_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) libbitcoin_consensus_a_SOURCES = \ amount.h \ arith_uint256.cpp \ arith_uint256.h \ consensus/merkle.cpp \ consensus/merkle.h \ consensus/params.h \ consensus/validation.h \ feerate.h \ hash.cpp \ hash.h \ prevector.h \ primitives/block.cpp \ primitives/block.h \ primitives/transaction.cpp \ primitives/transaction.h \ primitives/txid.h \ pubkey.cpp \ pubkey.h \ script/bitcoinconsensus.cpp \ script/sighashtype.h \ script/interpreter.cpp \ script/interpreter.h \ script/script.cpp \ script/script.h \ script/script_error.cpp \ script/script_error.h \ script/script_flags.h \ script/sigencoding.cpp \ script/sigencoding.h \ serialize.h \ tinyformat.h \ uint256.cpp \ uint256.h \ utilstrencodings.cpp \ utilstrencodings.h \ version.h # common: shared between bitcoind, and bitcoin-qt and non-server tools libbitcoin_common_a_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) libbitcoin_common_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) libbitcoin_common_a_SOURCES = \ amount.cpp \ base58.cpp \ cashaddr.cpp \ cashaddrenc.cpp \ chainparams.cpp \ config.cpp \ coins.cpp \ compressor.cpp \ dstencode.cpp \ feerate.cpp \ globals.cpp \ core_read.cpp \ core_write.cpp \ key.cpp \ keystore.cpp \ netaddress.cpp \ netbase.cpp \ protocol.cpp \ scheduler.cpp \ script/sign.cpp \ script/standard.cpp \ warnings.cpp \ $(BITCOIN_CORE_H) # util: shared between all executables. # This library *must* be included to make sure that the glibc # backward-compatibility objects and their sanity checks are linked. libbitcoin_util_a_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) libbitcoin_util_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) libbitcoin_util_a_SOURCES = \ support/lockedpool.cpp \ chainparamsbase.cpp \ clientversion.cpp \ compat/glibc_sanity.cpp \ compat/glibcxx_sanity.cpp \ compat/strnlen.cpp \ fs.cpp \ logging.cpp \ random.cpp \ rcu.cpp \ rpc/protocol.cpp \ support/cleanse.cpp \ sync.cpp \ threadinterrupt.cpp \ uint256.cpp \ uint256.h \ util.cpp \ utilmoneystr.cpp \ utilstrencodings.cpp \ utiltime.cpp \ $(BITCOIN_CORE_H) if GLIBC_BACK_COMPAT libbitcoin_util_a_SOURCES += compat/glibc_compat.cpp AM_LDFLAGS += $(COMPAT_LDFLAGS) endif # cli: shared between bitcoin-cli and bitcoin-qt libbitcoin_cli_a_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) libbitcoin_cli_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) libbitcoin_cli_a_SOURCES = \ rpc/client.cpp \ $(BITCOIN_CORE_H) # seeder library libbitcoin_seeder_a_CPPFLAGS = $(AM_CPPFLAGS) $(PIE_FLAGS) $(BITCOIN_SEEDER_INCLUDES) libbitcoin_seeder_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) libbitcoin_seeder_a_SOURCES = \ seeder/bitcoin.cpp \ seeder/bitcoin.h \ seeder/db.cpp \ seeder/db.h \ seeder/dns.cpp \ seeder/dns.h \ seeder/strlcpy.h \ seeder/util.h nodist_libbitcoin_util_a_SOURCES = $(srcdir)/obj/build.h # # bitcoind binary # bitcoind_SOURCES = bitcoind.cpp bitcoind_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) bitcoind_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) bitcoind_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) if TARGET_WINDOWS bitcoind_SOURCES += bitcoind-res.rc endif bitcoind_LDADD = \ $(LIBBITCOIN_SERVER) \ $(LIBBITCOIN_COMMON) \ $(LIBUNIVALUE) \ $(LIBBITCOIN_UTIL) \ $(LIBBITCOIN_WALLET) \ $(LIBBITCOIN_ZMQ) \ $(LIBBITCOIN_CONSENSUS) \ $(LIBBITCOIN_CRYPTO) \ $(LIBLEVELDB) \ $(LIBLEVELDB_SSE42) \ $(LIBMEMENV) \ $(LIBSECP256K1) bitcoind_LDADD += $(BOOST_LIBS) $(BDB_LIBS) $(SSL_LIBS) $(CRYPTO_LIBS) $(MINIUPNPC_LIBS) $(EVENT_PTHREADS_LIBS) $(EVENT_LIBS) $(ZMQ_LIBS) # bitcoin-cli binary # bitcoin_cli_SOURCES = bitcoin-cli.cpp bitcoin_cli_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) $(EVENT_CFLAGS) bitcoin_cli_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) bitcoin_cli_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) if TARGET_WINDOWS bitcoin_cli_SOURCES += bitcoin-cli-res.rc endif bitcoin_cli_LDADD = \ $(LIBBITCOIN_CLI) \ $(LIBUNIVALUE) \ $(LIBBITCOIN_UTIL) \ $(LIBBITCOIN_CRYPTO) bitcoin_cli_LDADD += $(BOOST_LIBS) $(SSL_LIBS) $(CRYPTO_LIBS) $(EVENT_LIBS) # # bitcoin-seeder binary # bitcoin_seeder_SOURCES = seeder/main.cpp bitcoin_seeder_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_SEEDER_INCLUDES) bitcoin_seeder_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) bitcoin_seeder_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) bitcoin_seeder_LDADD = \ $(LIBBITCOIN_SEEDER) \ $(LIBBITCOIN_COMMON) \ $(LIBBITCOIN_UTIL) \ $(LIBBITCOIN_CRYPTO) bitcoin_seeder_LDADD += $(BOOST_LIBS) $(CRYPTO_LIBS) # # bitcoin-tx binary # bitcoin_tx_SOURCES = bitcoin-tx.cpp bitcoin_tx_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) bitcoin_tx_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) bitcoin_tx_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) if TARGET_WINDOWS bitcoin_tx_SOURCES += bitcoin-tx-res.rc endif bitcoin_tx_LDADD = \ $(LIBUNIVALUE) \ $(LIBBITCOIN_COMMON) \ $(LIBBITCOIN_UTIL) \ $(LIBBITCOIN_CONSENSUS) \ $(LIBBITCOIN_CRYPTO) \ $(LIBSECP256K1) bitcoin_tx_LDADD += $(BOOST_LIBS) $(CRYPTO_LIBS) # # bitcoinconsensus library # if BUILD_BITCOIN_LIBS include_HEADERS = script/bitcoinconsensus.h libbitcoinconsensus_la_SOURCES = $(crypto_libbitcoin_crypto_base_a_SOURCES) $(libbitcoin_consensus_a_SOURCES) if GLIBC_BACK_COMPAT libbitcoinconsensus_la_SOURCES += compat/glibc_compat.cpp endif libbitcoinconsensus_la_LDFLAGS = $(AM_LDFLAGS) -no-undefined $(RELDFLAGS) libbitcoinconsensus_la_LIBADD = $(LIBSECP256K1) libbitcoinconsensus_la_CPPFLAGS = $(AM_CPPFLAGS) -I$(builddir)/obj -I$(srcdir)/secp256k1/include -DBUILD_BITCOIN_INTERNAL libbitcoinconsensus_la_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) endif # CTAES_DIST = crypto/ctaes/bench.c CTAES_DIST += crypto/ctaes/ctaes.c CTAES_DIST += crypto/ctaes/ctaes.h CTAES_DIST += crypto/ctaes/README.md CTAES_DIST += crypto/ctaes/test.c CLEANFILES = $(EXTRA_LIBRARIES) CLEANFILES += *.gcda *.gcno CLEANFILES += compat/*.gcda compat/*.gcno CLEANFILES += consensus/*.gcda consensus/*.gcno CLEANFILES += crypto/*.gcda crypto/*.gcno CLEANFILES += policy/*.gcda policy/*.gcno CLEANFILES += primitives/*.gcda primitives/*.gcno CLEANFILES += script/*.gcda script/*.gcno CLEANFILES += support/*.gcda support/*.gcno CLEANFILES += univalue/*.gcda univalue/*.gcno CLEANFILES += wallet/*.gcda wallet/*.gcno CLEANFILES += wallet/test/*.gcda wallet/test/*.gcno CLEANFILES += zmq/*.gcda zmq/*.gcno DISTCLEANFILES = obj/build.h EXTRA_DIST = $(CTAES_DIST) clean-local: -$(MAKE) -C secp256k1 clean -$(MAKE) -C univalue clean -rm -f leveldb/*/*.gcda leveldb/*/*.gcno leveldb/helpers/memenv/*.gcda leveldb/helpers/memenv/*.gcno -rm -rf test/__pycache__ .rc.o: @test -f $(WINDRES) ## FIXME: How to get the appropriate modulename_CPPFLAGS in here? $(AM_V_GEN) $(WINDRES) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(CPPFLAGS) -DWINDRES_PREPROC -i $< -o $@ .mm.o: $(AM_V_CXX) $(OBJCXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \ $(CPPFLAGS) $(AM_CXXFLAGS) $(QT_INCLUDES) $(AM_CXXFLAGS) $(PIE_FLAGS) $(CXXFLAGS) -c -o $@ $< check-symbols: $(bin_PROGRAMS) if GLIBC_BACK_COMPAT @echo "Checking glibc back compat..." $(AM_V_at) READELF=$(READELF) CPPFILT=$(CPPFILT) $(top_srcdir)/contrib/devtools/symbol-check.py < $(bin_PROGRAMS) endif check-security: $(bin_PROGRAMS) if HARDEN @echo "Checking binary security..." $(AM_V_at) READELF=$(READELF) OBJDUMP=$(OBJDUMP) $(top_srcdir)/contrib/devtools/security-check.py < $(bin_PROGRAMS) endif %.pb.cc %.pb.h: %.proto @test -f $(PROTOC) $(AM_V_GEN) $(PROTOC) --cpp_out=$(@D) --proto_path=$( "$@.new" && mv -f "$@.new" "$@" @echo "Generated $@" diff --git a/src/Makefile.test.include b/src/Makefile.test.include index bc98a9218a..aff246b372 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -1,204 +1,205 @@ # Copyright (c) 2013-2016 The Bitcoin Core developers # Distributed under the MIT software license, see the accompanying # file COPYING or http://www.opensource.org/licenses/mit-license.php. TESTS += test/test_bitcoin LOG_DRIVER = $(srcdir)/test/test-bitcoin-driver EXTRA_DIST += test/test-bitcoin-driver bin_PROGRAMS += test/test_bitcoin noinst_PROGRAMS += test/test_bitcoin_fuzzy TEST_SRCDIR = test TEST_BINARY=test/test_bitcoin$(EXEEXT) JSON_TEST_FILES = \ test/data/script_tests.json \ test/data/base58_keys_valid.json \ test/data/base58_encode_decode.json \ test/data/base58_keys_invalid.json \ test/data/tx_invalid.json \ test/data/tx_valid.json \ test/data/sighash.json RAW_TEST_FILES = GENERATED_TEST_FILES = $(JSON_TEST_FILES:.json=.json.h) $(RAW_TEST_FILES:.raw=.raw.h) # test_bitcoin binary # BITCOIN_TESTS =\ test/scriptnum10.h \ test/activation_tests.cpp \ test/addrman_tests.cpp \ test/allocator_tests.cpp \ test/amount_tests.cpp \ test/arith_uint256_tests.cpp \ test/avalanche_tests.cpp \ test/base32_tests.cpp \ test/base58_tests.cpp \ test/base64_tests.cpp \ test/bip32_tests.cpp \ test/blockcheck_tests.cpp \ test/blockencodings_tests.cpp \ + test/blockfilter_tests.cpp \ test/blockindex_tests.cpp \ test/blockstatus_tests.cpp \ test/bloom_tests.cpp \ test/bswap_tests.cpp \ test/cashaddr_tests.cpp \ test/cashaddrenc_tests.cpp \ test/checkdatasig_tests.cpp \ test/checkpoints_tests.cpp \ test/checkqueue_tests.cpp \ test/coins_tests.cpp \ test/compress_tests.cpp \ test/config_tests.cpp \ test/core_io_tests.cpp \ test/crypto_tests.cpp \ test/cuckoocache_tests.cpp \ test/dbwrapper_tests.cpp \ test/DoS_tests.cpp \ test/dstencode_tests.cpp \ test/excessiveblock_tests.cpp \ test/feerate_tests.cpp \ test/finalization_tests.cpp \ test/getarg_tests.cpp \ test/hash_tests.cpp \ test/inv_tests.cpp \ test/jsonutil.cpp \ test/jsonutil.h \ test/key_tests.cpp \ test/lcg_tests.cpp \ test/lcg.h \ test/limitedmap_tests.cpp \ test/main_tests.cpp \ test/mempool_tests.cpp \ test/merkle_tests.cpp \ test/miner_tests.cpp \ test/monolith_opcodes_tests.cpp \ test/multisig_tests.cpp \ test/net_tests.cpp \ test/netbase_tests.cpp \ test/pmt_tests.cpp \ test/policyestimator_tests.cpp \ test/pow_tests.cpp \ test/prevector_tests.cpp \ test/radix_tests.cpp \ test/raii_event_tests.cpp \ test/random_tests.cpp \ test/rcu_tests.cpp \ test/reverselock_tests.cpp \ test/rpc_tests.cpp \ test/rpc_server_tests.cpp \ test/rwcollection_tests.cpp \ test/sanity_tests.cpp \ test/scheduler_tests.cpp \ test/schnorr_tests.cpp \ test/script_commitment_tests.cpp \ test/script_P2SH_tests.cpp \ test/script_tests.cpp \ test/scriptflags.cpp \ test/scriptflags.h \ test/scriptnum_tests.cpp \ test/serialize_tests.cpp \ test/sigcache_tests.cpp \ test/sigencoding_tests.cpp \ test/sighash_tests.cpp \ test/sighashtype_tests.cpp \ test/sigopcount_tests.cpp \ test/sigutil.cpp \ test/sigutil.h \ test/skiplist_tests.cpp \ test/streams_tests.cpp \ test/sync_tests.cpp \ test/test_bitcoin.cpp \ test/test_bitcoin.h \ test/test_bitcoin_main.cpp \ test/timedata_tests.cpp \ test/transaction_tests.cpp \ test/txvalidationcache_tests.cpp \ test/uint256_tests.cpp \ test/undo_tests.cpp \ test/univalue_tests.cpp \ test/util_tests.cpp \ test/validation_tests.cpp \ test/work_comparator_tests.cpp \ rpc/test/server_tests.cpp if ENABLE_WALLET BITCOIN_TESTS += \ wallet/test/wallet_test_fixture.cpp \ wallet/test/wallet_test_fixture.h \ wallet/test/accounting_tests.cpp \ wallet/test/wallet_tests.cpp \ wallet/test/walletdb_tests.cpp \ wallet/test/wallet_crypto_tests.cpp endif test_test_bitcoin_SOURCES = $(BITCOIN_TESTS) $(JSON_TEST_FILES) $(RAW_TEST_FILES) test_test_bitcoin_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -I$(builddir)/test/ $(TESTDEFS) $(EVENT_CFLAGS) test_test_bitcoin_LDADD = if ENABLE_WALLET test_test_bitcoin_LDADD += $(LIBBITCOIN_WALLET) endif test_test_bitcoin_LDADD += $(LIBBITCOIN_SERVER) $(LIBBITCOIN_CLI) $(LIBBITCOIN_COMMON) $(LIBBITCOIN_UTIL) $(LIBBITCOIN_CONSENSUS) $(LIBBITCOIN_CRYPTO) $(LIBUNIVALUE) \ $(LIBLEVELDB) $(LIBLEVELDB_SSE42) $(LIBMEMENV) $(BOOST_LIBS) $(BOOST_UNIT_TEST_FRAMEWORK_LIB) $(LIBSECP256K1) $(EVENT_LIBS) $(EVENT_PTHREADS_LIBS) test_test_bitcoin_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) test_test_bitcoin_LDADD += $(LIBBITCOIN_CONSENSUS) $(BDB_LIBS) $(SSL_LIBS) $(CRYPTO_LIBS) $(MINIUPNPC_LIBS) test_test_bitcoin_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) -static if ENABLE_ZMQ test_test_bitcoin_LDADD += $(ZMQ_LIBS) endif # # test_bitcoin_fuzzy binary # test_test_bitcoin_fuzzy_SOURCES = test/test_bitcoin_fuzzy.cpp test_test_bitcoin_fuzzy_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) test_test_bitcoin_fuzzy_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) test_test_bitcoin_fuzzy_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) test_test_bitcoin_fuzzy_LDADD = \ $(LIBUNIVALUE) \ $(LIBBITCOIN_SERVER) \ $(LIBBITCOIN_COMMON) \ $(LIBBITCOIN_UTIL) \ $(LIBBITCOIN_CONSENSUS) \ $(LIBBITCOIN_CRYPTO) \ $(LIBSECP256K1) test_test_bitcoin_fuzzy_LDADD += $(BOOST_LIBS) $(CRYPTO_LIBS) # nodist_test_test_bitcoin_SOURCES = $(GENERATED_TEST_FILES) $(BITCOIN_TESTS): $(GENERATED_TEST_FILES) CLEAN_BITCOIN_TEST = test/*.gcda test/*.gcno $(GENERATED_TEST_FILES) CLEANFILES += $(CLEAN_BITCOIN_TEST) bitcoin_test: $(TEST_BINARY) bitcoin_test_check: $(TEST_BINARY) FORCE $(MAKE) check-TESTS TESTS=$^ bitcoin_test_clean : FORCE rm -f $(CLEAN_BITCOIN_TEST) $(test_test_bitcoin_OBJECTS) $(TEST_BINARY) check-local: @echo "Running test/util/bitcoin-util-test.py..." $(top_builddir)/test/util/bitcoin-util-test.py $(AM_V_at)$(MAKE) $(AM_MAKEFLAGS) -C secp256k1 check if EMBEDDED_UNIVALUE $(AM_V_at)$(MAKE) $(AM_MAKEFLAGS) -C univalue check endif %.json.h: %.json @$(MKDIR_P) $(@D) @{ \ echo "namespace json_tests{" && \ echo "static unsigned const char $(*F)[] = {" && \ $(HEXDUMP) -v -e '8/1 "0x%02x, "' -e '"\n"' $< | $(SED) -e 's/0x ,//g' && \ echo "};};"; \ } > "$@.new" && mv -f "$@.new" "$@" @echo "Generated $@" diff --git a/src/bench/CMakeLists.txt b/src/bench/CMakeLists.txt index d45b613e89..84a1f8a4ff 100644 --- a/src/bench/CMakeLists.txt +++ b/src/bench/CMakeLists.txt @@ -1,32 +1,33 @@ # Copyright (c) 2018 The Bitcoin developers project(bitcoin-bench) include_directories(.) add_executable(bitcoin-bench EXCLUDE_FROM_ALL base58.cpp bench.cpp bench_bitcoin.cpp cashaddr.cpp ccoins_caching.cpp # checkblock.cpp TODO Fix including bench/data/*.raw files checkqueue.cpp crypto_hash.cpp + gcs_filter.cpp Examples.cpp lockedpool.cpp mempool_eviction.cpp perf.cpp prevector.cpp rollingbloom.cpp ) target_link_libraries(bitcoin-bench common bitcoinconsensus server) add_custom_target(bench-bitcoin COMMAND ./bitcoin-bench DEPENDS bitcoin-bench ) diff --git a/src/bench/gcs_filter.cpp b/src/bench/gcs_filter.cpp new file mode 100644 index 0000000000..9bf316d0d4 --- /dev/null +++ b/src/bench/gcs_filter.cpp @@ -0,0 +1,41 @@ +// Copyright (c) 2018 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include +#include + +static void ConstructGCSFilter(benchmark::State &state) { + GCSFilter::ElementSet elements; + for (int i = 0; i < 10000; ++i) { + GCSFilter::Element element(32); + element[0] = static_cast(i); + element[1] = static_cast(i >> 8); + elements.insert(std::move(element)); + } + + uint64_t siphash_k0 = 0; + while (state.KeepRunning()) { + GCSFilter filter(siphash_k0, 0, 20, 1 << 20, elements); + + siphash_k0++; + } +} + +static void MatchGCSFilter(benchmark::State &state) { + GCSFilter::ElementSet elements; + for (int i = 0; i < 10000; ++i) { + GCSFilter::Element element(32); + element[0] = static_cast(i); + element[1] = static_cast(i >> 8); + elements.insert(std::move(element)); + } + GCSFilter filter(0, 0, 20, 1 << 20, elements); + + while (state.KeepRunning()) { + filter.Match(GCSFilter::Element()); + } +} + +BENCHMARK(ConstructGCSFilter, 1000); +BENCHMARK(MatchGCSFilter, 50 * 1000); diff --git a/src/blockfilter.cpp b/src/blockfilter.cpp new file mode 100644 index 0000000000..29d735bd34 --- /dev/null +++ b/src/blockfilter.cpp @@ -0,0 +1,198 @@ +// Copyright (c) 2018 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include +#include +#include + +/// SerType used to serialize parameters in GCS filter encoding. +static constexpr int GCS_SER_TYPE = SER_NETWORK; + +/// Protocol version used to serialize parameters in GCS filter encoding. +static constexpr int GCS_SER_VERSION = 0; + +template +static void GolombRiceEncode(BitStreamWriter &bitwriter, uint8_t P, + uint64_t x) { + // Write quotient as unary-encoded: q 1's followed by one 0. + uint64_t q = x >> P; + while (q > 0) { + int nbits = q <= 64 ? static_cast(q) : 64; + bitwriter.Write(~0ULL, nbits); + q -= nbits; + } + bitwriter.Write(0, 1); + + // Write the remainder in P bits. Since the remainder is just the bottom + // P bits of x, there is no need to mask first. + bitwriter.Write(x, P); +} + +template +static uint64_t GolombRiceDecode(BitStreamReader &bitreader, + uint8_t P) { + // Read unary-encoded quotient: q 1's followed by one 0. + uint64_t q = 0; + while (bitreader.Read(1) == 1) { + ++q; + } + + uint64_t r = bitreader.Read(P); + + return (q << P) + r; +} + +// Map a value x that is uniformly distributed in the range [0, 2^64) to a +// value uniformly distributed in [0, n) by returning the upper 64 bits of +// x * n. +// +// See: +// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ +static uint64_t MapIntoRange(uint64_t x, uint64_t n) { +#ifdef __SIZEOF_INT128__ + return (static_cast(x) * + static_cast(n)) >> + 64; +#else + // To perform the calculation on 64-bit numbers without losing the + // result to overflow, split the numbers into the most significant and + // least significant 32 bits and perform multiplication piece-wise. + // + // See: https://stackoverflow.com/a/26855440 + uint64_t x_hi = x >> 32; + uint64_t x_lo = x & 0xFFFFFFFF; + uint64_t n_hi = n >> 32; + uint64_t n_lo = n & 0xFFFFFFFF; + + uint64_t ac = x_hi * n_hi; + uint64_t ad = x_hi * n_lo; + uint64_t bc = x_lo * n_hi; + uint64_t bd = x_lo * n_lo; + + uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF); + uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32); + return upper64; +#endif +} + +uint64_t GCSFilter::HashToRange(const Element &element) const { + uint64_t hash = CSipHasher(m_siphash_k0, m_siphash_k1) + .Write(element.data(), element.size()) + .Finalize(); + return MapIntoRange(hash, m_F); +} + +std::vector +GCSFilter::BuildHashedSet(const ElementSet &elements) const { + std::vector hashed_elements; + hashed_elements.reserve(elements.size()); + for (const Element &element : elements) { + hashed_elements.push_back(HashToRange(element)); + } + std::sort(hashed_elements.begin(), hashed_elements.end()); + return hashed_elements; +} + +GCSFilter::GCSFilter(uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, + uint32_t M) + : m_siphash_k0(siphash_k0), m_siphash_k1(siphash_k1), m_P(P), m_M(M), + m_N(0), m_F(0) {} + +GCSFilter::GCSFilter(uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, + uint32_t M, std::vector encoded_filter) + : GCSFilter(siphash_k0, siphash_k1, P, M) { + m_encoded = std::move(encoded_filter); + + VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0); + + uint64_t N = ReadCompactSize(stream); + m_N = static_cast(N); + if (m_N != N) { + throw std::ios_base::failure("N must be <2^32"); + } + m_F = static_cast(m_N) * static_cast(m_M); + + // Verify that the encoded filter contains exactly N elements. If it has too + // much or too little data, a std::ios_base::failure exception will be + // raised. + BitStreamReader bitreader(stream); + for (uint64_t i = 0; i < m_N; ++i) { + GolombRiceDecode(bitreader, m_P); + } + if (!stream.empty()) { + throw std::ios_base::failure("encoded_filter contains excess data"); + } +} + +GCSFilter::GCSFilter(uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, + uint32_t M, const ElementSet &elements) + : GCSFilter(siphash_k0, siphash_k1, P, M) { + size_t N = elements.size(); + m_N = static_cast(N); + if (m_N != N) { + throw std::invalid_argument("N must be <2^32"); + } + m_F = static_cast(m_N) * static_cast(m_M); + + CVectorWriter stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0); + + WriteCompactSize(stream, m_N); + + if (elements.empty()) { + return; + } + + BitStreamWriter bitwriter(stream); + + uint64_t last_value = 0; + for (uint64_t value : BuildHashedSet(elements)) { + uint64_t delta = value - last_value; + GolombRiceEncode(bitwriter, m_P, delta); + last_value = value; + } + + bitwriter.Flush(); +} + +bool GCSFilter::MatchInternal(const uint64_t *element_hashes, + size_t size) const { + VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0); + + // Seek forward by size of N + uint64_t N = ReadCompactSize(stream); + assert(N == m_N); + + BitStreamReader bitreader(stream); + + uint64_t value = 0; + size_t hashes_index = 0; + for (uint32_t i = 0; i < m_N; ++i) { + uint64_t delta = GolombRiceDecode(bitreader, m_P); + value += delta; + + while (true) { + if (hashes_index == size) { + return false; + } else if (element_hashes[hashes_index] == value) { + return true; + } else if (element_hashes[hashes_index] > value) { + break; + } + + hashes_index++; + } + } + + return false; +} + +bool GCSFilter::Match(const Element &element) const { + uint64_t query = HashToRange(element); + return MatchInternal(&query, 1); +} + +bool GCSFilter::MatchAny(const ElementSet &elements) const { + const std::vector queries = BuildHashedSet(elements); + return MatchInternal(queries.data(), queries.size()); +} diff --git a/src/blockfilter.h b/src/blockfilter.h new file mode 100644 index 0000000000..373b60ebed --- /dev/null +++ b/src/blockfilter.h @@ -0,0 +1,74 @@ +// Copyright (c) 2018 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_BLOCKFILTER_H +#define BITCOIN_BLOCKFILTER_H + +#include +#include + +#include +#include +#include + +/** + * This implements a Golomb-coded set as defined in BIP 158. It is a + * compact, probabilistic data structure for testing set membership. + */ +class GCSFilter { +public: + typedef std::vector Element; + typedef std::set ElementSet; + +private: + uint64_t m_siphash_k0; + uint64_t m_siphash_k1; + uint8_t m_P; //!< Golomb-Rice coding parameter + uint32_t m_M; //!< Inverse false positive rate + uint32_t m_N; //!< Number of elements in the filter + uint64_t m_F; //!< Range of element hashes, F = N * M + std::vector m_encoded; + + /** Hash a data element to an integer in the range [0, N * M). */ + uint64_t HashToRange(const Element &element) const; + + std::vector BuildHashedSet(const ElementSet &elements) const; + + /** Helper method used to implement Match and MatchAny */ + bool MatchInternal(const uint64_t *sorted_element_hashes, + size_t size) const; + +public: + /** Constructs an empty filter. */ + GCSFilter(uint64_t siphash_k0 = 0, uint64_t siphash_k1 = 0, uint8_t P = 0, + uint32_t M = 0); + + /** Reconstructs an already-created filter from an encoding. */ + GCSFilter(uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, uint32_t M, + std::vector encoded_filter); + + /** Builds a new filter from the params and set of elements. */ + GCSFilter(uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, uint32_t M, + const ElementSet &elements); + + uint8_t GetP() const { return m_P; } + uint32_t GetN() const { return m_N; } + uint32_t GetM() const { return m_M; } + const std::vector &GetEncoded() const { return m_encoded; } + + /** + * Checks if the element may be in the set. False positives are possible + * with probability 1/M. + */ + bool Match(const Element &element) const; + + /** + * Checks if any of the given elements may be in the set. False positives + * are possible with probability 1/M per element checked. This is more + * efficient that checking Match on multiple elements separately. + */ + bool MatchAny(const ElementSet &elements) const; +}; + +#endif // BITCOIN_BLOCKFILTER_H diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt index 651c4f37ed..7767e3b242 100644 --- a/src/test/CMakeLists.txt +++ b/src/test/CMakeLists.txt @@ -1,175 +1,176 @@ # Copyright (c) 2018 The Bitcoin developers project(bitcoin-test) # Process json files. file(MAKE_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}/data") find_program(PYTHON python) function(gen_json_header NAME) set(HEADERS "") foreach(f ${ARGN}) set(h "${CMAKE_CURRENT_BINARY_DIR}/${f}.h") # Get the proper name for the test variable. get_filename_component(TEST_NAME ${f} NAME_WE) add_custom_command(OUTPUT ${h} COMMAND ${PYTHON} ARGS "${CMAKE_CURRENT_SOURCE_DIR}/data/generate_header.py" "${TEST_NAME}" "${CMAKE_CURRENT_SOURCE_DIR}/${f}" > ${h} MAIN_DEPENDENCY ${f} DEPENDS "data/generate_header.py" VERBATIM ) list(APPEND HEADERS ${h}) endforeach(f) set(${NAME} "${HEADERS}" PARENT_SCOPE) endfunction() gen_json_header(JSON_HEADERS data/script_tests.json data/base58_keys_valid.json data/base58_encode_decode.json data/base58_keys_invalid.json data/tx_invalid.json data/tx_valid.json data/sighash.json ) include(TestSuite) create_test_suite(bitcoin) add_dependencies(check check-bitcoin) add_test_to_suite(bitcoin test_bitcoin activation_tests.cpp addrman_tests.cpp allocator_tests.cpp amount_tests.cpp arith_uint256_tests.cpp avalanche_tests.cpp base32_tests.cpp base58_tests.cpp base64_tests.cpp bip32_tests.cpp blockcheck_tests.cpp blockencodings_tests.cpp + blockfilter_tests.cpp blockindex_tests.cpp blockstatus_tests.cpp bloom_tests.cpp bswap_tests.cpp cashaddr_tests.cpp cashaddrenc_tests.cpp checkdatasig_tests.cpp checkpoints_tests.cpp checkqueue_tests.cpp coins_tests.cpp compress_tests.cpp config_tests.cpp core_io_tests.cpp crypto_tests.cpp cuckoocache_tests.cpp dbwrapper_tests.cpp DoS_tests.cpp dstencode_tests.cpp excessiveblock_tests.cpp feerate_tests.cpp finalization_tests.cpp getarg_tests.cpp hash_tests.cpp inv_tests.cpp jsonutil.cpp key_tests.cpp lcg_tests.cpp limitedmap_tests.cpp main_tests.cpp mempool_tests.cpp merkle_tests.cpp miner_tests.cpp monolith_opcodes_tests.cpp multisig_tests.cpp net_tests.cpp netbase_tests.cpp pmt_tests.cpp policyestimator_tests.cpp pow_tests.cpp prevector_tests.cpp radix_tests.cpp raii_event_tests.cpp random_tests.cpp rcu_tests.cpp reverselock_tests.cpp rpc_tests.cpp rpc_server_tests.cpp rwcollection_tests.cpp sanity_tests.cpp scheduler_tests.cpp schnorr_tests.cpp script_commitment_tests.cpp script_P2SH_tests.cpp script_tests.cpp scriptflags.cpp scriptnum_tests.cpp serialize_tests.cpp sigcache_tests.cpp sigencoding_tests.cpp sighash_tests.cpp sighashtype_tests.cpp sigopcount_tests.cpp sigutil.cpp skiplist_tests.cpp streams_tests.cpp sync_tests.cpp test_bitcoin.cpp test_bitcoin_main.cpp timedata_tests.cpp transaction_tests.cpp txvalidationcache_tests.cpp uint256_tests.cpp undo_tests.cpp univalue_tests.cpp util_tests.cpp validation_tests.cpp work_comparator_tests.cpp # RPC Tests ../rpc/test/server_tests.cpp # Tests generated from JSON ${JSON_HEADERS} ) target_include_directories(test_bitcoin PUBLIC # To access the generated json headers. ${CMAKE_CURRENT_BINARY_DIR} ) find_package(Boost 1.58 REQUIRED unit_test_framework) target_link_libraries(test_bitcoin Boost::unit_test_framework rpcclient server) # We need to detect if the BOOST_TEST_DYN_LINK flag is required. set(CMAKE_REQUIRED_LIBRARIES Boost::unit_test_framework) check_cxx_source_compiles(" #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MAIN #include " BOOST_TEST_DYN_LINK) if(BOOST_TEST_DYN_LINK) target_compile_definitions(test_bitcoin PRIVATE BOOST_TEST_DYN_LINK) endif(BOOST_TEST_DYN_LINK) if(BUILD_BITCOIN_WALLET) target_sources(test_bitcoin PRIVATE ../wallet/test/wallet_test_fixture.cpp ../wallet/test/accounting_tests.cpp ../wallet/test/wallet_tests.cpp ../wallet/test/walletdb_tests.cpp ../wallet/test/wallet_crypto_tests.cpp ) endif() diff --git a/src/test/blockfilter_tests.cpp b/src/test/blockfilter_tests.cpp new file mode 100644 index 0000000000..b97deed3c6 --- /dev/null +++ b/src/test/blockfilter_tests.cpp @@ -0,0 +1,33 @@ +// Copyright (c) 2018 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include + +#include + +BOOST_AUTO_TEST_SUITE(blockfilter_tests) + +BOOST_AUTO_TEST_CASE(gcsfilter_test) { + GCSFilter::ElementSet included_elements, excluded_elements; + for (int i = 0; i < 100; ++i) { + GCSFilter::Element element1(32); + element1[0] = i; + included_elements.insert(std::move(element1)); + + GCSFilter::Element element2(32); + element2[1] = i; + excluded_elements.insert(std::move(element2)); + } + + GCSFilter filter(0, 0, 10, 1 << 10, included_elements); + for (const auto &element : included_elements) { + BOOST_CHECK(filter.Match(element)); + + auto insertion = excluded_elements.insert(element); + BOOST_CHECK(filter.MatchAny(excluded_elements)); + excluded_elements.erase(insertion.first); + } +} + +BOOST_AUTO_TEST_SUITE_END()