xxh3.hpp 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786
  1. #ifndef BOOST_HASH2_XXH3_HPP_INCLUDED
  2. #define BOOST_HASH2_XXH3_HPP_INCLUDED
  3. // Copyright 2025 Christian Mazakas.
  4. // Distributed under the Boost Software License, Version 1.0.
  5. // https://www.boost.org/LICENSE_1_0.txt
  6. //
  7. // xxHash, https://cyan4973.github.io/xxHash/
  8. #include <boost/hash2/digest.hpp>
  9. #include <boost/hash2/detail/byteswap.hpp>
  10. #include <boost/hash2/detail/is_constant_evaluated.hpp>
  11. #include <boost/hash2/detail/memset.hpp>
  12. #include <boost/hash2/detail/memcpy.hpp>
  13. #include <boost/hash2/detail/mul128.hpp>
  14. #include <boost/hash2/detail/read.hpp>
  15. #include <boost/hash2/detail/rot.hpp>
  16. #include <boost/hash2/detail/write.hpp>
  17. #include <boost/assert.hpp>
  18. #include <boost/config.hpp>
  19. #include <boost/config/workaround.hpp>
  20. #include <cstdint>
  21. #include <cstring>
  22. #include <cstddef>
  23. #if defined(BOOST_MSVC) && BOOST_MSVC < 1920
  24. # pragma warning(push)
  25. # pragma warning(disable: 4307) // '+': integral constant overflow
  26. #endif
  27. namespace boost
  28. {
  29. namespace hash2
  30. {
  31. template<class = void>
  32. struct xxh3_128_constants
  33. {
  34. constexpr static unsigned char const default_secret[ 192 ] =
  35. {
  36. 0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
  37. 0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
  38. 0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
  39. 0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
  40. 0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3,
  41. 0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8,
  42. 0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d,
  43. 0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64,
  44. 0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb,
  45. 0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e,
  46. 0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce,
  47. 0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e,
  48. };
  49. };
  50. // copy-paste from Boost.Unordered's prime_fmod approach
  51. #if defined(BOOST_NO_CXX17_INLINE_VARIABLES)
  52. // https://en.cppreference.com/w/cpp/language/static#Constant_static_members
  53. // If a const non-inline (since C++17) static data member or a constexpr
  54. // static data member (since C++11)(until C++17) is odr-used, a definition
  55. // at namespace scope is still required, but it cannot have an
  56. // initializer.
  57. template<class T>
  58. constexpr unsigned char xxh3_128_constants<T>::default_secret[ 192 ];
  59. #endif
  60. class xxh3_128
  61. {
  62. private:
  63. static constexpr std::size_t const default_secret_len = 192;
  64. static constexpr std::size_t const min_secret_len = 136;
  65. static constexpr std::size_t const buffer_size = 256;
  66. static constexpr std::uint64_t const P32_1 = 0x9E3779B1U;
  67. static constexpr std::uint64_t const P32_2 = 0x85EBCA77U;
  68. static constexpr std::uint64_t const P32_3 = 0xC2B2AE3DU;
  69. static constexpr std::uint64_t const P64_1 = 0x9E3779B185EBCA87ULL;
  70. static constexpr std::uint64_t const P64_2 = 0xC2B2AE3D27D4EB4FULL;
  71. static constexpr std::uint64_t const P64_3 = 0x165667B19E3779F9ULL;
  72. static constexpr std::uint64_t const P64_4 = 0x85EBCA77C2B2AE63ULL;
  73. static constexpr std::uint64_t const P64_5 = 0x27D4EB2F165667C5ULL;
  74. static constexpr std::uint64_t const PRIME_MX1 = 0x165667919E3779F9ULL;
  75. static constexpr std::uint64_t const PRIME_MX2 = 0x9FB21C651E98DF25ULL;
  76. BOOST_CXX14_CONSTEXPR void init_secret_from_seed( std::uint64_t seed )
  77. {
  78. auto const secret = xxh3_128_constants<>::default_secret;
  79. std::size_t num_rounds = default_secret_len / 16;
  80. for( std::size_t i = 0; i < num_rounds; ++i )
  81. {
  82. auto low = detail::read64le( secret + 16 * i ) + seed;
  83. auto high = detail::read64le( secret + 16 * i + 8 ) - seed;
  84. detail::write64le( secret_ + 16 * i, low );
  85. detail::write64le( secret_ + 16 * i + 8, high );
  86. }
  87. }
  88. BOOST_FORCEINLINE BOOST_CXX14_CONSTEXPR static std::uint64_t avalanche( std::uint64_t x )
  89. {
  90. x ^= ( x >> 37 );
  91. x *= PRIME_MX1;
  92. x ^= ( x >> 32 );
  93. return x;
  94. }
  95. BOOST_FORCEINLINE BOOST_CXX14_CONSTEXPR static std::uint64_t avalanche_xxh64( std::uint64_t x )
  96. {
  97. x ^= x >> 33;
  98. x *= P64_2;
  99. x ^= x >> 29;
  100. x *= P64_3;
  101. x ^= x >> 32;
  102. return x;
  103. }
  104. BOOST_CXX14_CONSTEXPR std::uint64_t mix_step( unsigned char const* data, std::size_t secret_offset, std::uint64_t seed )
  105. {
  106. auto const secret = with_secret_? secret_: xxh3_128_constants<>::default_secret;
  107. std::uint64_t data_words[ 2 ] = {};
  108. std::uint64_t secret_words[ 2 ] = {};
  109. for( int i = 0; i < 2; ++i )
  110. {
  111. data_words[ i ] = detail::read64le( data + 8 * i );
  112. secret_words[ i ] = detail::read64le( secret + secret_offset + 8 * i );
  113. }
  114. detail::uint128 r = detail::mul128( data_words[ 0 ] ^ ( secret_words[ 0 ] + seed ), data_words[ 1 ] ^ ( secret_words[ 1 ] - seed ) );
  115. return r.low ^ r.high;
  116. }
  117. BOOST_CXX14_CONSTEXPR void mix_two_chunks( unsigned char const* x, unsigned char const* y, std::size_t secret_offset, std::uint64_t seed, std::uint64_t (&acc)[ 2 ] )
  118. {
  119. std::uint64_t data_words1[ 2 ] = {};
  120. std::uint64_t data_words2[ 2 ] = {};
  121. for( int i = 0; i < 2; ++i )
  122. {
  123. data_words1[ i ] = detail::read64le( x + 8 * i );
  124. data_words2[ i ] = detail::read64le( y + 8 * i );
  125. }
  126. acc[ 0 ] += mix_step( x, secret_offset, seed );
  127. acc[ 1 ] += mix_step( y, secret_offset + 16, seed );
  128. acc[ 0 ] ^= ( data_words2[ 0 ] + data_words2[ 1 ] );
  129. acc[ 1 ] ^= ( data_words1[ 0 ] + data_words1[ 1 ] );
  130. }
  131. BOOST_CXX14_CONSTEXPR void accumulate( std::uint64_t stripe[ 8 ], std::size_t secret_offset )
  132. {
  133. std::uint64_t secret_words[ 8 ] = {};
  134. for( int i = 0; i < 8; ++i )
  135. {
  136. secret_words[ i ] = detail::read64le( secret_ + secret_offset + 8 * i );
  137. }
  138. for( int i = 0; i < 8; ++i )
  139. {
  140. std::uint64_t value = stripe[ i ] ^ secret_words[ i ];
  141. acc_[ i ^ 1 ] = acc_[ i ^ 1 ] + stripe[ i ];
  142. acc_[ i ] = acc_[ i ] + ( value & 0xffffffff ) * ( value >> 32 );
  143. }
  144. }
  145. BOOST_CXX14_CONSTEXPR void scramble()
  146. {
  147. std::uint64_t secret_words[ 8 ] = {};
  148. for( int i = 0; i < 8; ++i )
  149. {
  150. secret_words[ i ] = detail::read64le( secret_ + ( secret_len_ - 64 ) + ( 8 * i ) );
  151. }
  152. for( int i = 0; i < 8; ++i )
  153. {
  154. acc_[ i ] ^= acc_[ i ] >> 47;
  155. acc_[ i ] ^= secret_words[ i ];
  156. acc_[ i ] *= P32_1;
  157. }
  158. }
  159. BOOST_CXX14_CONSTEXPR void last_round()
  160. {
  161. unsigned char last_stripe[ 64 ] = {};
  162. unsigned char* last_stripe_ptr = nullptr;
  163. if( m_ >= 64 )
  164. {
  165. std::size_t num_stripes = ( m_ == 0 ? 0 : ( m_ - 1 ) / 64 );
  166. for( std::size_t n = 0; n < num_stripes; ++n )
  167. {
  168. std::uint64_t stripe[ 8 ] = {};
  169. for( int i = 0; i < 8; ++i )
  170. {
  171. stripe[ i ] = detail::read64le( buffer_ + ( 64 * n ) + ( 8 * i ) );
  172. }
  173. accumulate( stripe, 8 * num_stripes_++ );
  174. std::size_t const stripes_per_block_ = ( secret_len_ - 64 ) / 8;
  175. (void)stripes_per_block_;
  176. BOOST_ASSERT( num_stripes_ <= stripes_per_block_ );
  177. }
  178. last_stripe_ptr = buffer_ + m_ - 64;
  179. }
  180. else
  181. {
  182. std::size_t len = 64 - m_;
  183. detail::memcpy( last_stripe, buffer_ + buffer_size - len, len );
  184. detail::memcpy( last_stripe + len, buffer_, m_ );
  185. last_stripe_ptr = last_stripe;
  186. }
  187. std::uint64_t stripe[ 8 ] = {};
  188. for( int i = 0; i < 8; ++i )
  189. {
  190. stripe[ i ] = detail::read64le( last_stripe_ptr + ( 8 * i ) );
  191. }
  192. accumulate( stripe, secret_len_ - 71 );
  193. }
  194. BOOST_CXX14_CONSTEXPR std::uint64_t final_merge( std::uint64_t init_value, std::size_t secret_offset )
  195. {
  196. std::uint64_t secret_words[ 8 ] = {};
  197. for( int i = 0; i < 8; ++i )
  198. {
  199. secret_words[ i ] = detail::read64le( secret_ + secret_offset + 8 * i );
  200. }
  201. std::uint64_t result = init_value;
  202. for( int i = 0; i < 4; ++i )
  203. {
  204. auto mul_result = detail::mul128( acc_[ 2 * i ] ^ secret_words[ 2 * i ], acc_[ 2 * i + 1 ] ^ secret_words[ 2 * i + 1 ] );
  205. result += mul_result.low ^ mul_result.high;
  206. }
  207. return avalanche( result );
  208. }
  209. BOOST_CXX14_CONSTEXPR digest<16> xxh3_128_digest_empty()
  210. {
  211. auto const secret = with_secret_? secret_: xxh3_128_constants<>::default_secret;
  212. std::uint64_t secret_words[ 4 ] = {};
  213. for( int i = 0; i < 4; ++i )
  214. {
  215. secret_words[ i ] = detail::read64le( secret + 64 + 8 * i );
  216. }
  217. digest<16> r;
  218. detail::write64be( r.data() + 8, avalanche_xxh64( seed_ ^ secret_words[ 0 ] ^ secret_words[ 1 ] ) );
  219. detail::write64be( r.data() + 0, avalanche_xxh64( seed_ ^ secret_words[ 2 ] ^ secret_words[ 3 ] ) );
  220. return r;
  221. }
  222. BOOST_CXX14_CONSTEXPR digest<16> xxh3_128_digest_1to3()
  223. {
  224. auto const secret = with_secret_? secret_: xxh3_128_constants<>::default_secret;
  225. std::uint32_t v1 = buffer_[ ( n_ - 1 ) ];
  226. std::uint32_t v2 = static_cast<std::uint32_t>( n_ << 8 );
  227. std::uint32_t v3 = buffer_[ 0 ] << 16;
  228. std::uint32_t v4 = buffer_[ ( n_ >> 1 ) ] << 24;
  229. std::uint32_t combined = v1 | v2 | v3 | v4;
  230. std::uint32_t secret_words[ 4 ] = {};
  231. for( int i = 0; i < 4; ++i )
  232. {
  233. secret_words[ i ] = detail::read32le( secret + 4 * i );
  234. }
  235. std::uint64_t low = ( ( secret_words[ 0 ] ^ secret_words[ 1 ] ) + seed_ ) ^ combined;
  236. std::uint64_t high = ( ( secret_words[ 2 ] ^ secret_words[ 3 ] ) - seed_ ) ^ ( detail::rotl( detail::byteswap( combined ), 13 ) );
  237. digest<16> r;
  238. detail::write64be( r.data() + 8, avalanche_xxh64( low ) );
  239. detail::write64be( r.data() + 0, avalanche_xxh64( high ) );
  240. return r;
  241. }
  242. BOOST_CXX14_CONSTEXPR digest<16> xxh3_128_digest_4to8()
  243. {
  244. auto const secret = with_secret_? secret_: xxh3_128_constants<>::default_secret;
  245. std::uint32_t input_first = detail::read32le( buffer_ );
  246. std::uint32_t input_last = detail::read32le( buffer_ + ( n_ - 4 ) );
  247. std::uint64_t modified_seed = seed_ ^ ( std::uint64_t{ detail::byteswap( static_cast<std::uint32_t>( seed_ ) ) } << 32 );
  248. std::uint64_t secret_words[ 2 ] = {};
  249. for( int i = 0; i < 2; ++i )
  250. {
  251. secret_words[ i ] = detail::read64le( secret + 16 + i * 8 );
  252. }
  253. std::uint64_t combined = std::uint64_t{ input_first } | ( std::uint64_t{ input_last } << 32 );
  254. std::uint64_t value = ( ( secret_words[ 0 ] ^ secret_words[ 1 ] ) + modified_seed ) ^ combined;
  255. detail::uint128 mul_result = detail::mul128( value, P64_1 + ( n_ << 2 ) );
  256. std::uint64_t high = mul_result.high;
  257. std::uint64_t low = mul_result.low;
  258. high += ( low << 1 );
  259. low ^= ( high >> 3 );
  260. low ^= ( low >> 35 );
  261. low *= PRIME_MX2;
  262. low ^= ( low >> 28 );
  263. high = avalanche( high );
  264. digest<16> r;
  265. detail::write64be( r.data() + 0, high );
  266. detail::write64be( r.data() + 8, low );
  267. return r;
  268. }
  269. BOOST_CXX14_CONSTEXPR digest<16> xxh3_128_digest_9to16()
  270. {
  271. auto const secret = with_secret_? secret_: xxh3_128_constants<>::default_secret;
  272. std::uint64_t input_first = detail::read64le( buffer_ );
  273. std::uint64_t input_last = detail::read64le( buffer_ + ( n_ - 8 ) );
  274. std::uint64_t secret_words[ 4 ] = {};
  275. for( int i = 0; i < 4; ++i )
  276. {
  277. secret_words[ i ] = detail::read64le( secret + 32 + ( i * 8 ) );
  278. }
  279. std::uint64_t val1 = ( ( secret_words[ 0 ] ^ secret_words[ 1 ] ) - seed_ ) ^ input_first ^ input_last;
  280. std::uint64_t val2 = ( ( secret_words[ 2 ] ^ secret_words[ 3 ] ) + seed_ ) ^ input_last;
  281. detail::uint128 mul_result = detail::mul128( val1, P64_1 );
  282. std::uint64_t low = mul_result.low + ( std::uint64_t{ n_ - 1 } << 54 );
  283. std::uint64_t high = mul_result.high + val2 + ( val2 & 0x00000000ffffffff ) * ( P32_2 - 1 );
  284. low ^= detail::byteswap( high );
  285. detail::uint128 mul_result2 = detail::mul128( low, P64_2 );
  286. low = mul_result2.low;
  287. high = mul_result2.high + high * P64_2;
  288. digest<16> r;
  289. detail::write64be( r.data() + 0, avalanche( high ) );
  290. detail::write64be( r.data() + 8, avalanche( low ) );
  291. return r;
  292. }
  293. BOOST_CXX14_CONSTEXPR digest<16> xxh3_128_digest_17to128()
  294. {
  295. std::uint64_t acc[ 2 ] = { n_ * P64_1, 0 };
  296. std::uint64_t num_rounds = ( ( n_ - 1 ) >> 5 ) + 1;
  297. for( std::int64_t i = num_rounds - 1; i >= 0; --i )
  298. {
  299. std::size_t offset_start = static_cast<std::size_t>( 16 * i );
  300. std::size_t offset_end = n_ - static_cast<std::size_t>( 16 * i ) - 16;
  301. mix_two_chunks( buffer_ + offset_start, buffer_ + offset_end, static_cast<std::size_t>( 32 * i ), seed_, acc );
  302. }
  303. std::uint64_t low = acc[ 0 ] + acc[ 1 ];
  304. std::uint64_t high = ( acc[ 0 ] * P64_1 ) + ( acc[ 1 ] * P64_4 ) + ( ( std::uint64_t{ n_ } - seed_ ) * P64_2 );
  305. digest<16> r;
  306. detail::write64be( r.data() + 0, std::uint64_t{ 0 } - avalanche( high ) );
  307. detail::write64be( r.data() + 8, avalanche( low ) );
  308. return r;
  309. }
  310. BOOST_CXX14_CONSTEXPR digest<16> xxh3_128_digest_129to240()
  311. {
  312. std::uint64_t acc[ 2 ] = { n_ * P64_1, 0 };
  313. std::uint64_t num_chunks = n_ >> 5;
  314. for( std::size_t i = 0; i < 4; ++i )
  315. {
  316. mix_two_chunks( buffer_ + 32 * i, buffer_ + ( 32 * i ) + 16, 32 * i, seed_, acc );
  317. }
  318. acc[ 0 ] = avalanche( acc[ 0 ] );
  319. acc[ 1 ] = avalanche( acc[ 1 ] );
  320. for( std::size_t i = 4; i < num_chunks; ++i )
  321. {
  322. mix_two_chunks( buffer_ + 32 * i, buffer_ + ( 32 * i ) + 16, ( i - 4 ) * 32 + 3, seed_, acc );
  323. }
  324. mix_two_chunks( buffer_ + n_ - 16, buffer_ + n_ - 32, 103, std::uint64_t{ 0 } - seed_, acc );
  325. std::uint64_t low = acc[ 0 ] + acc[ 1 ];
  326. std::uint64_t high = ( acc[ 0 ] * P64_1 ) + ( acc[ 1 ] * P64_4 ) + ( ( std::uint64_t{ n_ } - seed_ ) * P64_2 );
  327. digest<16> r;
  328. detail::write64be( r.data() + 0, std::uint64_t{ 0 } - avalanche( high ) );
  329. detail::write64be( r.data() + 8, avalanche( low ) );
  330. return r;
  331. }
  332. BOOST_CXX14_CONSTEXPR digest<16> xxh3_128_digest_long()
  333. {
  334. last_round();
  335. std::uint64_t low = final_merge( n_ * P64_1, 11 );
  336. std::uint64_t high = final_merge( ~( n_ * P64_2 ), secret_len_ - 75 );
  337. digest<16> r;
  338. detail::write64be( r.data() + 0, high );
  339. detail::write64be( r.data() + 8, low );
  340. return r;
  341. }
  342. BOOST_CXX14_CONSTEXPR static std::uint64_t combine( std::uint64_t v1, std::uint64_t v2 )
  343. {
  344. return avalanche( v1 + v2 );
  345. }
  346. private:
  347. unsigned char secret_[ default_secret_len ] = {};
  348. std::uint64_t seed_ = 0;
  349. bool with_secret_ = false;
  350. unsigned char buffer_[ buffer_size ] = {};
  351. std::uint64_t acc_[ 8 ] = { P32_3, P64_1, P64_2, P64_3, P64_4, P32_2, P64_5, P32_1 };
  352. std::size_t n_ = 0;
  353. std::size_t m_ = 0;
  354. std::size_t secret_len_ = default_secret_len;
  355. std::size_t num_stripes_ = 0; // current number of processed stripes
  356. public:
  357. using result_type = digest<16>;
  358. BOOST_CXX14_CONSTEXPR xxh3_128()
  359. {
  360. detail::memcpy( secret_, xxh3_128_constants<>::default_secret, default_secret_len );
  361. }
  362. BOOST_CXX14_CONSTEXPR explicit xxh3_128( std::uint64_t seed ): seed_( seed )
  363. {
  364. init_secret_from_seed( seed );
  365. }
  366. xxh3_128( void const* p, std::size_t n ): xxh3_128( static_cast<unsigned char const*>( p ), n )
  367. {
  368. }
  369. BOOST_CXX14_CONSTEXPR xxh3_128( unsigned char const* p, std::size_t n )
  370. {
  371. detail::memcpy( secret_, xxh3_128_constants<>::default_secret, default_secret_len );
  372. if( n == 0 ) return;
  373. with_secret_ = true;
  374. std::size_t const n2 = n;
  375. std::uint64_t seed = 0;
  376. while( n >= default_secret_len )
  377. {
  378. for( std::size_t i = 0; i < default_secret_len / 8; ++i )
  379. {
  380. std::uint64_t v1 = detail::read64le( p + i * 8 );
  381. std::uint64_t v2 = detail::read64le( secret_ + i * 8 );
  382. detail::write64le( secret_ + i * 8, combine( v1, v2 ) );
  383. seed = combine( seed, v1 );
  384. }
  385. p += default_secret_len;
  386. n -= default_secret_len;
  387. }
  388. {
  389. std::size_t i = 0;
  390. for( ; i < n / 8; ++i )
  391. {
  392. std::uint64_t v1 = detail::read64le( p + i * 8 );
  393. std::uint64_t v2 = detail::read64le( secret_ + i * 8 );
  394. detail::write64le( secret_ + i * 8, combine( v1, v2 ) );
  395. seed = combine( seed, v1 );
  396. }
  397. n = n % 8;
  398. if( n > 0 )
  399. {
  400. unsigned char w[ 8 ] = {};
  401. detail::memcpy( w, p + i * 8, n );
  402. std::uint64_t v1 = detail::read64le( w );
  403. std::uint64_t v2 = detail::read64le( secret_ + i * 8 );
  404. detail::write64le( secret_ + i * 8, combine( v1, v2 ) );
  405. seed = combine( seed, v1 );
  406. }
  407. }
  408. {
  409. std::size_t const i = 0;
  410. std::uint64_t v1 = n2;
  411. std::uint64_t v2 = detail::read64le( secret_ + i * 8 );
  412. detail::write64le( secret_ + i * 8, combine( v1, v2 ) );
  413. seed = combine( seed, v1 );
  414. }
  415. seed_ = seed;
  416. }
  417. private: // supporting constructor for the static factory functions
  418. BOOST_CXX14_CONSTEXPR xxh3_128( std::uint64_t seed, unsigned char const* p, std::size_t n, bool with_secret ): seed_( seed ), with_secret_( with_secret )
  419. {
  420. if( n < min_secret_len )
  421. {
  422. // this is a precondition violation for XXH3, but we try to do something reasonable
  423. detail::memcpy( secret_, xxh3_128_constants<>::default_secret, default_secret_len );
  424. secret_len_ = default_secret_len;
  425. }
  426. else if( n < default_secret_len )
  427. {
  428. secret_len_ = n;
  429. }
  430. else
  431. {
  432. secret_len_ = default_secret_len;
  433. }
  434. // incorporate passed secret into secret_
  435. // in the case where min_secret_len <= n <= default_secret_len,
  436. // this is a simple copy because the initial secret_ is {}
  437. while( n >= default_secret_len )
  438. {
  439. for( std::size_t i = 0; i < default_secret_len / 8; ++i )
  440. {
  441. std::uint64_t v1 = detail::read64le( p + i * 8 );
  442. std::uint64_t v2 = detail::read64le( secret_ + i * 8 );
  443. detail::write64le( secret_ + i * 8, v1 + v2 );
  444. }
  445. p += default_secret_len;
  446. n -= default_secret_len;
  447. }
  448. {
  449. std::size_t i = 0;
  450. for( ; i < n / 8; ++i )
  451. {
  452. std::uint64_t v1 = detail::read64le( p + i * 8 );
  453. std::uint64_t v2 = detail::read64le( secret_ + i * 8 );
  454. detail::write64le( secret_ + i * 8, v1 + v2 );
  455. }
  456. n = n % 8;
  457. if( n > 0 )
  458. {
  459. unsigned char w[ 8 ] = {};
  460. detail::memcpy( w, p + i * 8, n );
  461. std::uint64_t v1 = detail::read64le( w );
  462. std::uint64_t v2 = detail::read64le( secret_ + i * 8 );
  463. detail::write64le( secret_ + i * 8, v1 + v2 );
  464. }
  465. }
  466. }
  467. public:
  468. // XXH3-specific named constructors, matching the reference implementation
  469. // for completeness only
  470. static BOOST_CXX14_CONSTEXPR xxh3_128 with_seed( std::uint64_t seed )
  471. {
  472. return xxh3_128( seed );
  473. }
  474. static BOOST_CXX14_CONSTEXPR xxh3_128 with_secret( unsigned char const* p, std::size_t n )
  475. {
  476. return xxh3_128( 0, p, n, true );
  477. }
  478. static xxh3_128 with_secret( void const* p, std::size_t n )
  479. {
  480. return with_secret( static_cast<unsigned char const*>( p ), n );
  481. }
  482. static BOOST_CXX14_CONSTEXPR xxh3_128 with_secret_and_seed( unsigned char const* p, std::size_t n, std::uint64_t seed )
  483. {
  484. return xxh3_128( seed, p, n, false );
  485. }
  486. static xxh3_128 with_secret_and_seed( void const* p, std::size_t n, std::uint64_t seed )
  487. {
  488. return with_secret_and_seed( static_cast<unsigned char const*>( p ), n, seed );
  489. }
  490. void update( void const* p, std::size_t n )
  491. {
  492. update( static_cast<unsigned char const*>( p ), n );
  493. }
  494. BOOST_CXX14_CONSTEXPR void update( unsigned char const* p, std::size_t n )
  495. {
  496. if( n == 0 ) return;
  497. std::size_t const stripes_per_block_ = ( secret_len_ - 64 ) / 8;
  498. n_ += n;
  499. if( n <= buffer_size - m_ )
  500. {
  501. detail::memcpy( buffer_ + m_, p, n );
  502. m_ += n;
  503. return;
  504. }
  505. if( m_ > 0 )
  506. {
  507. std::size_t k = buffer_size - m_;
  508. detail::memcpy( buffer_ + m_, p, k );
  509. p += k;
  510. n -= k;
  511. for( std::size_t i = 0; i < 4; ++i )
  512. {
  513. std::uint64_t stripe[ 8 ] = {};
  514. for( int j = 0; j < 8; ++j )
  515. {
  516. stripe[ j ] = detail::read64le( buffer_ + ( 64 * i) + ( 8 * j ) );
  517. }
  518. accumulate( stripe, 8 * num_stripes_ );
  519. ++num_stripes_;
  520. if( num_stripes_ == stripes_per_block_ )
  521. {
  522. scramble();
  523. num_stripes_ = 0;
  524. }
  525. }
  526. m_ = 0;
  527. }
  528. if( n > buffer_size )
  529. {
  530. while( n > 64 )
  531. {
  532. std::uint64_t stripe[ 8 ] = {};
  533. for( int j = 0; j < 8; ++j )
  534. {
  535. stripe[ j ] = detail::read64le( p + ( 8 * j ) );
  536. }
  537. accumulate( stripe, 8 * num_stripes_ );
  538. ++num_stripes_;
  539. if( num_stripes_ == stripes_per_block_ )
  540. {
  541. scramble();
  542. num_stripes_ = 0;
  543. }
  544. p += 64;
  545. n -= 64;
  546. }
  547. detail::memcpy( buffer_ + buffer_size - 64, p - 64, 64 );
  548. BOOST_ASSERT( n <= 64 );
  549. }
  550. if( n > 0 )
  551. {
  552. detail::memcpy( buffer_, p, n );
  553. m_ = n;
  554. }
  555. }
  556. BOOST_CXX14_CONSTEXPR result_type result()
  557. {
  558. result_type r;
  559. if( n_ == 0 )
  560. {
  561. r = xxh3_128_digest_empty();
  562. // perturb state to enable result extension
  563. seed_ += P64_5;
  564. }
  565. else if( n_ < 4 )
  566. {
  567. r = xxh3_128_digest_1to3();
  568. }
  569. else if( n_ < 9 )
  570. {
  571. r = xxh3_128_digest_4to8();
  572. }
  573. else if( n_ < 17 )
  574. {
  575. r = xxh3_128_digest_9to16();
  576. }
  577. else if( n_ < 129 )
  578. {
  579. r = xxh3_128_digest_17to128();
  580. }
  581. else if( n_ < 241 )
  582. {
  583. r = xxh3_128_digest_129to240();
  584. }
  585. else
  586. {
  587. r = xxh3_128_digest_long();
  588. // perturb state to enable result extension
  589. acc_[ 0 ] -= P64_1;
  590. acc_[ 1 ] += P64_1;
  591. acc_[ 2 ] -= P64_2;
  592. acc_[ 3 ] += P64_2;
  593. acc_[ 4 ] -= P64_3;
  594. acc_[ 5 ] += P64_3;
  595. acc_[ 6 ] -= P64_4;
  596. acc_[ 7 ] += P64_4;
  597. }
  598. // finalize buffer to clear plainext and enable result extension
  599. {
  600. std::uint64_t h1 = detail::read64le( r.data() + 0 );
  601. std::uint64_t h2 = detail::read64le( r.data() + 8 );
  602. std::uint64_t v1 = detail::read64le( buffer_ + 0 );
  603. detail::write64le( buffer_ + 0, v1 + h1 );
  604. std::uint64_t v2 = detail::read64le( buffer_ + 8 );
  605. detail::write64le( buffer_ + 8, v2 + h2 );
  606. detail::memset( buffer_ + 16, 0, buffer_size - 16 );
  607. }
  608. return r;
  609. }
  610. };
  611. } // namespace hash2
  612. } // namespace boost
  613. #if defined(BOOST_MSVC) && BOOST_MSVC < 1920
  614. # pragma warning(pop)
  615. #endif
  616. #endif // #ifndef BOOST_HASH2_XXH3_HPP_INCLUDED