accumulators/hash.hpp
Go to the documentation of this file.
1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2018-2020 Mikhail Komarov <nemo@nil.foundation>
3 // Copyright (c) 2019 Aleksey Moskvin <zerg1996@yandex.ru>
4 // Copyright (c) 2020 Nikita Kaskov <nbering@nil.foundation>
5 //
6 // MIT License
7 //
8 // Permission is hereby granted, free of charge, to any person obtaining a copy
9 // of this software and associated documentation files (the "Software"), to deal
10 // in the Software without restriction, including without limitation the rights
11 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 // copies of the Software, and to permit persons to whom the Software is
13 // furnished to do so, subject to the following conditions:
14 //
15 // The above copyright notice and this permission notice shall be included in all
16 // copies or substantial portions of the Software.
17 //
18 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 // SOFTWARE.
25 //---------------------------------------------------------------------------//
26 
27 #ifndef CRYPTO3_ACCUMULATORS_HASH_HPP
28 #define CRYPTO3_ACCUMULATORS_HASH_HPP
29 
30 #include <boost/parameter/value_type.hpp>
31 
32 #include <boost/accumulators/framework/accumulator_base.hpp>
33 #include <boost/accumulators/framework/extractor.hpp>
34 #include <boost/accumulators/framework/depends_on.hpp>
35 #include <boost/accumulators/framework/parameters/sample.hpp>
36 
37 #include <boost/container/static_vector.hpp>
38 
39 #include <nil/crypto3/detail/make_array.hpp>
40 #include <nil/crypto3/detail/static_digest.hpp>
41 #include <nil/crypto3/detail/endian_shift.hpp>
42 #include <nil/crypto3/detail/inject.hpp>
43 
45 
48 
49 #include <boost/accumulators/statistics/count.hpp>
50 
51 namespace nil {
52  namespace crypto3 {
53  namespace hashes {
54  template<typename Params, typename BasePointGeneratorHash, typename Group>
55  struct pedersen;
56  }
57  namespace accumulators {
58  namespace impl {
59  template<typename Hash>
60  struct hash_impl : boost::accumulators::accumulator_base {
61  protected:
62  typedef Hash hash_type;
63  typedef typename hash_type::construction::type construction_type;
64  typedef typename hash_type::construction::params_type params_type;
65 
66  typedef typename params_type::digest_endian endian_type;
67 
68  constexpr static const std::size_t word_bits = construction_type::word_bits;
69  typedef typename construction_type::word_type word_type;
70 
71  constexpr static const std::size_t block_bits = construction_type::block_bits;
72  constexpr static const std::size_t block_words = construction_type::block_words;
73  typedef typename construction_type::block_type block_type;
74 
75  constexpr static const std::size_t length_bits = params_type::length_bits;
76  // FIXME: do something more intelligent than capping at 64
77  constexpr static const std::size_t length_type_bits = length_bits < word_bits ? word_bits :
78  length_bits > 64 ? 64 :
80  typedef typename boost::uint_t<length_type_bits>::least length_type;
81  constexpr static const std::size_t length_words = length_bits / word_bits;
83 
84  typedef ::nil::crypto3::detail::injector<endian_type, word_bits, block_words, block_bits>
86 
87  public:
88  typedef typename hash_type::digest_type result_type;
89 
90  // The constructor takes an argument pack.
91  hash_impl(boost::accumulators::dont_care) : filled(false), total_seen(0) {
92  }
93 
94  template<typename ArgumentPack>
95  inline void operator()(const ArgumentPack &args) {
96  resolve_type(args[boost::accumulators::sample],
97  args[::nil::crypto3::accumulators::bits | std::size_t()]);
98  }
99 
100  inline result_type result(boost::accumulators::dont_care) const {
102  return res.digest(cache, total_seen);
103  }
104 
105  protected:
106  inline void resolve_type(const block_type &value, std::size_t bits) {
107  // total_seen += bits == 0 ? block_bits : bits;
108  process(value, bits == 0 ? block_bits : bits);
109  }
110 
111  inline void resolve_type(const word_type &value, std::size_t bits) {
112  // total_seen += bits == 0 ? word_bits : bits;
113  process(value, bits == 0 ? word_bits : bits);
114  }
115 
116  inline void process(const block_type &value, std::size_t value_seen) {
117  using namespace ::nil::crypto3::detail;
118 
119  if (filled) {
120  construction.process_block(cache, total_seen);
121  filled = false;
122  }
123 
124  std::size_t cached_bits = total_seen % block_bits;
125 
126  if (cached_bits != 0) {
127  // If there are already any bits in the cache
128 
129  std::size_t needed_to_fill_bits = block_bits - cached_bits;
130  std::size_t new_bits_to_append =
131  (needed_to_fill_bits > value_seen) ? value_seen : needed_to_fill_bits;
132 
133  injector_type::inject(value, new_bits_to_append, cache, cached_bits);
134  total_seen += new_bits_to_append;
135 
136  if (cached_bits == block_bits) {
137  // If there are enough bits in the incoming value to fill the block
138  filled = true;
139 
140  if (value_seen > new_bits_to_append) {
141 
142  construction.process_block(cache, total_seen);
143  filled = false;
144 
145  // If there are some remaining bits in the incoming value - put them into the cache,
146  // which is now empty
147 
148  cached_bits = 0;
149 
151  value, value_seen - new_bits_to_append, cache, cached_bits, new_bits_to_append);
152 
153  total_seen += value_seen - new_bits_to_append;
154  }
155  }
156 
157  } else {
158 
159  total_seen += value_seen;
160 
161  // If there are no bits in the cache
162  if (value_seen == block_bits) {
163  // The incoming value is a full block
164  filled = true;
165 
166  std::move(value.begin(), value.end(), cache.begin());
167 
168  } else {
169  // The incoming value is not a full block
170  std::move(value.begin(),
171  value.begin() + value_seen / word_bits + (value_seen % word_bits ? 1 : 0),
172  cache.begin());
173  }
174  }
175  }
176 
177  inline void process(const word_type &value, std::size_t value_seen) {
178  using namespace ::nil::crypto3::detail;
179 
180  if (filled) {
181  construction.process_block(cache, total_seen);
182  filled = false;
183  }
184 
185  std::size_t cached_bits = total_seen % block_bits;
186 
187  if (cached_bits % word_bits != 0) {
188  std::size_t needed_to_fill_bits = block_bits - cached_bits;
189  std::size_t new_bits_to_append =
190  (needed_to_fill_bits > value_seen) ? value_seen : needed_to_fill_bits;
191 
192  injector_type::inject(value, new_bits_to_append, cache, cached_bits);
193  total_seen += new_bits_to_append;
194 
195  if (cached_bits == block_bits) {
196  // If there are enough bits in the incoming value to fill the block
197 
198  filled = true;
199 
200  if (value_seen > new_bits_to_append) {
201 
202  construction.process_block(cache, total_seen);
203  filled = false;
204 
205  // If there are some remaining bits in the incoming value - put them into the cache,
206  // which is now empty
207  cached_bits = 0;
208 
210  value, value_seen - new_bits_to_append, cache, cached_bits, new_bits_to_append);
211 
212  total_seen += value_seen - new_bits_to_append;
213  }
214  }
215 
216  } else {
217  cache[cached_bits / word_bits] = value;
218 
219  total_seen += value_seen;
220  }
221  }
222 
223  bool filled;
224  std::size_t total_seen;
227  };
228 
229  template<typename Params, typename BasePointGeneratorHash, typename Group>
230  struct hash_impl<nil::crypto3::hashes::pedersen<Params, BasePointGeneratorHash, Group>>
231  : boost::accumulators::accumulator_base {
232  protected:
235 
236  public:
238 
239  template<typename Args>
240  hash_impl(const Args &args) {
241  hash_type::init_accumulator(acc);
242  }
243 
244  template<typename Args>
245  inline void operator()(const Args &args) {
246  resolve_type(args[boost::accumulators::sample],
247  args[::nil::crypto3::accumulators::iterator_last | nullptr]);
248  }
249 
250  inline result_type result(boost::accumulators::dont_care) const {
251  return hash_type::process(acc);
252  }
253 
254  protected:
255  template<typename InputRange, typename InputIterator>
256  inline void resolve_type(const InputRange &range, InputIterator) {
257  hash_type::update(acc, range);
258  }
259 
260  template<typename InputIterator>
261  inline void resolve_type(InputIterator first, InputIterator last) {
262  hash_type::update(acc, first, last);
263  }
264 
266  };
267  } // namespace impl
268 
269  namespace tag {
270  template<typename Hash>
271  struct hash : boost::accumulators::depends_on<bits_count> {
272  typedef Hash hash_type;
273 
276 
277  typedef boost::mpl::always<accumulators::impl::hash_impl<Hash>> impl;
278  };
279  } // namespace tag
280 
281  namespace extract {
282  template<typename Hash, typename AccumulatorSet>
283  typename boost::mpl::apply<AccumulatorSet, tag::hash<Hash>>::type::result_type
284  hash(const AccumulatorSet &acc) {
285  return boost::accumulators::extract_result<tag::hash<Hash>>(acc);
286  }
287  } // namespace extract
288  } // namespace accumulators
289  } // namespace crypto3
290 } // namespace nil
291 
292 #endif // CRYPTO3_ACCUMULATORS_HASH_HPP
boost::mpl::apply< AccumulatorSet, tag::hash< Hash > >::type::result_type hash(const AccumulatorSet &acc)
Definition: accumulators/hash.hpp:284
OutputIterator move(const SinglePassRange &rng, OutputIterator result)
Definition: move.hpp:45
Definition: algebra/include/nil/crypto3/detail/make_array.hpp:33
Definition: pair.hpp:31
void resolve_type(const InputRange &range, InputIterator)
Definition: accumulators/hash.hpp:256
void resolve_type(InputIterator first, InputIterator last)
Definition: accumulators/hash.hpp:261
result_type result(boost::accumulators::dont_care) const
Definition: accumulators/hash.hpp:250
nil::crypto3::hashes::pedersen< Params, BasePointGeneratorHash, Group > hash_type
Definition: accumulators/hash.hpp:233
hash_type::internal_accumulator_type internal_accumulator_type
Definition: accumulators/hash.hpp:234
Definition: accumulators/hash.hpp:60
construction_type::block_type block_type
Definition: accumulators/hash.hpp:73
hash_type::digest_type result_type
Definition: accumulators/hash.hpp:88
constexpr static const std::size_t word_bits
Definition: accumulators/hash.hpp:68
void operator()(const ArgumentPack &args)
Definition: accumulators/hash.hpp:95
construction_type::word_type word_type
Definition: accumulators/hash.hpp:69
void process(const word_type &value, std::size_t value_seen)
Definition: accumulators/hash.hpp:177
constexpr static const std::size_t length_bits
Definition: accumulators/hash.hpp:75
constexpr static const std::size_t block_words
Definition: accumulators/hash.hpp:72
params_type::digest_endian endian_type
Definition: accumulators/hash.hpp:66
void process(const block_type &value, std::size_t value_seen)
Definition: accumulators/hash.hpp:116
Hash hash_type
Definition: accumulators/hash.hpp:62
std::size_t total_seen
Definition: accumulators/hash.hpp:224
boost::uint_t< length_type_bits >::least length_type
Definition: accumulators/hash.hpp:80
constexpr static const std::size_t length_words
Definition: accumulators/hash.hpp:81
hash_type::construction::params_type params_type
Definition: accumulators/hash.hpp:64
result_type result(boost::accumulators::dont_care) const
Definition: accumulators/hash.hpp:100
void resolve_type(const word_type &value, std::size_t bits)
Definition: accumulators/hash.hpp:111
block_type cache
Definition: accumulators/hash.hpp:225
hash_type::construction::type construction_type
Definition: accumulators/hash.hpp:63
::nil::crypto3::detail::injector< endian_type, word_bits, block_words, block_bits > injector_type
Definition: accumulators/hash.hpp:85
hash_impl(boost::accumulators::dont_care)
Definition: accumulators/hash.hpp:91
BOOST_STATIC_ASSERT(!length_bits||length_bits % word_bits==0)
construction_type construction
Definition: accumulators/hash.hpp:226
constexpr static const std::size_t block_bits
Definition: accumulators/hash.hpp:71
bool filled
Definition: accumulators/hash.hpp:223
void resolve_type(const block_type &value, std::size_t bits)
Definition: accumulators/hash.hpp:106
constexpr static const std::size_t length_type_bits
Definition: accumulators/hash.hpp:77
Definition: accumulators/hash.hpp:271
Hash hash_type
Definition: accumulators/hash.hpp:272
boost::mpl::always< accumulators::impl::hash_impl< Hash > > impl
Definition: accumulators/hash.hpp:277
static void inject(const block_type &b_src, std::size_t b_src_seen, block_type &b_dst, std::size_t &b_dst_seen, std::size_t block_shift=0)
Definition: block/include/nil/crypto3/detail/inject.hpp:267
Definition: hash/include/nil/crypto3/hash/pedersen.hpp:185
hashing_to_curve_accumulator_set< base_hash_type > internal_accumulator_type
Definition: hash/include/nil/crypto3/hash/pedersen.hpp:219
digest_type result_type
Definition: hash/include/nil/crypto3/hash/pedersen.hpp:199