block/include/nil/crypto3/detail/reverser.hpp
Go to the documentation of this file.
1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2018-2020 Mikhail Komarov <nemo@nil.foundation>
3 // Copyright (c) 2020 Alexander Sokolov <asokolov@nil.foundation>
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_DETAIL_REVERSER_HPP
28 #define CRYPTO3_DETAIL_REVERSER_HPP
29 
30 #include <climits>
31 #include <type_traits>
32 
33 #include <boost/integer.hpp>
34 #include <boost/static_assert.hpp>
35 #include <boost/endian/conversion.hpp>
36 
37 #include <nil/crypto3/detail/unbounded_shift.hpp>
38 #include <nil/crypto3/detail/stream_endian.hpp>
39 #include <nil/crypto3/detail/predef.hpp>
40 
41 namespace nil {
42  namespace crypto3 {
43  namespace detail {
44 
49  typedef typename boost::uint_t<CHAR_BIT>::exact byte_type;
50 
63  inline void reverse_byte(byte_type &b) {
64 
65 #if (BOOST_ARCH_CURRENT_WORD_BITS == 32)
66  b = unbounded_shr<16>(((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU);
67 #elif (BOOST_ARCH_CURRENT_WORD_BITS == 64)
68  b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
69 #else
70 #error "BOOST_ARCH_CURRENT_WORD_BITS not set"
71 #endif
72  }
73 
86  template<int UnitBits, int k = 0>
88 
89  BOOST_STATIC_ASSERT(!(UnitBits % CHAR_BIT));
90 
92  typedef typename boost::uint_t<UnitBits>::exact UnitType;
93 
94  inline static void reverse(UnitType &in, UnitType &out) {
95  int const shift = UnitBits - (CHAR_BIT + k);
96  byte_type byte = byte_type(low_bits<CHAR_BIT>(unbounded_shr(in, shift)));
97  reverse_byte(byte);
98  out |= unbounded_shl(low_bits<CHAR_BIT>(UnitType(byte)), shift);
99 
100  next_type::reverse(in, out);
101  }
102  };
103 
104  template<int UnitBits>
105  struct bit_in_unit_byte_reverser<UnitBits, UnitBits> {
106  inline static void reverse(typename boost::uint_t<UnitBits>::exact &,
107  typename boost::uint_t<UnitBits>::exact &) {
108  }
109  };
110 
129  template<typename UnitType,
130  int UnitBits = sizeof(UnitType) * CHAR_BIT,
131  typename std::enable_if<(UnitBits > CHAR_BIT), int>::type = 0>
132  inline void reverse_bits(UnitType &unit) {
133  boost::endian::endian_reverse_inplace(unit);
134  UnitType out = UnitType();
136  unit = out;
137  }
150  template<typename UnitType,
151  int UnitBits = sizeof(UnitType) * CHAR_BIT,
152  typename std::enable_if<(UnitBits == CHAR_BIT), int>::type = 0>
153  inline void reverse_bits(UnitType &unit) {
154  reverse_byte(unit);
155  }
156 
170  template<int InputBits, int UnitBits, int k = 0>
172 
173  BOOST_STATIC_ASSERT(!(InputBits % UnitBits) && !(UnitBits % CHAR_BIT));
174 
176  typedef typename boost::uint_t<UnitBits>::exact UnitType;
177 
178  template<typename ValueType>
179  inline static void reverse(ValueType &in, ValueType &out) {
180  int const shift = InputBits - (UnitBits + k);
181  UnitType unit = UnitType(low_bits<UnitBits>(unbounded_shr(in, shift)));
182  reverse_bits(unit);
183  out |= unbounded_shl(low_bits<UnitBits>(ValueType(unit)), shift);
184 
185  next_type::reverse(in, out);
186  }
187  };
188 
189  template<int InputBits, int UnitBits>
190  struct bit_in_unit_reverser<InputBits, UnitBits, InputBits> {
191  template<typename ValueType>
192  inline static void reverse(ValueType &, ValueType &) {
193  }
194  };
195 
210  template<typename Endianness, int UnitBits>
211  struct is_big_bit {
212  constexpr static const bool value =
213  std::is_same<Endianness, stream_endian::big_unit_big_bit<UnitBits>>::value ||
214  std::is_same<Endianness, stream_endian::little_unit_big_bit<UnitBits>>::value;
215  };
216 
226  template<typename Endianness, int UnitBits>
227  struct is_little_bit {
228  constexpr static const bool value =
229  std::is_same<Endianness, stream_endian::big_unit_little_bit<UnitBits>>::value ||
230  std::is_same<Endianness, stream_endian::little_unit_little_bit<UnitBits>>::value;
231  };
232 
243  template<typename Endianness1, typename Endianness2, int UnitBits>
244  struct is_same_bit {
245  constexpr static const bool value =
248  };
249 
262  template<typename InputEndianness,
263  typename OutputEndianness,
264  int UnitBits,
266  struct bit_reverser;
267 
278  template<typename InputEndianness, typename OutputEndianness, int UnitBits>
279  struct bit_reverser<InputEndianness, OutputEndianness, UnitBits, true> {
280  template<typename ValueType>
281  inline static void reverse(ValueType &) {
282  }
283 
284  template<typename ValueType>
285  inline static ValueType reverse(ValueType const &val) {
286  return val;
287  }
288  };
289 
300  template<typename InputEndianness, typename OutputEndianness, int UnitBits>
301  struct bit_reverser<InputEndianness, OutputEndianness, UnitBits, false> {
302  template<typename ValueType, int ValueBits = sizeof(ValueType) * CHAR_BIT>
303  inline static void reverse(ValueType &val) {
304  ValueType out = ValueType();
306  val = out;
307  }
308 
309  template<typename ValueType, int ValueBits = sizeof(ValueType) * CHAR_BIT>
310  inline static ValueType reverse(ValueType const &val) {
311  ValueType tmp = val;
312  ValueType out = ValueType();
314  return out;
315  }
316  };
317 
331  template<int InputBits, int UnitBits, int k = 0>
333 
334  BOOST_STATIC_ASSERT(!(InputBits % UnitBits) && !(UnitBits % CHAR_BIT));
335 
337  typedef typename boost::uint_t<UnitBits>::exact UnitType;
338 
339  template<typename ValueType>
340  inline static void reverse(ValueType &in, ValueType &out) {
341  int const shift = InputBits - (UnitBits + k);
342  UnitType unit = UnitType(low_bits<UnitBits>(unbounded_shr(in, shift)));
343  boost::endian::endian_reverse_inplace(unit);
344  out |= unbounded_shl(low_bits<UnitBits>(ValueType(unit)), shift);
345 
346  next_type::reverse(in, out);
347  }
348  };
349 
350  template<int InputBits, int UnitBits>
351  struct byte_in_unit_reverser<InputBits, UnitBits, InputBits> {
352  template<typename ValueType>
353  inline static void reverse(ValueType &, ValueType &) {
354  }
355  };
356 
371  template<typename Endianness, int UnitBits>
372  struct is_big_unit {
373  constexpr static const bool value =
374  std::is_same<Endianness, stream_endian::big_unit_big_bit<UnitBits>>::value ||
375  std::is_same<Endianness, stream_endian::big_unit_little_bit<UnitBits>>::value;
376  };
377 
387  template<typename Endianness, int UnitBits>
388  struct is_little_unit {
389  constexpr static const bool value =
390  std::is_same<Endianness, stream_endian::little_unit_big_bit<UnitBits>>::value ||
391  std::is_same<Endianness, stream_endian::little_unit_little_bit<UnitBits>>::value;
392  };
393 
404  template<typename Endianness1, typename Endianness2, int UnitBits>
405  struct is_same_unit {
406  constexpr static const bool value =
409  };
410 
422  template<typename InputEndianness, typename OutputEndianness, int UnitBits, typename Enable = void>
424 
435  template<typename InputEndianness, typename OutputEndianness, int UnitBits>
437  InputEndianness,
438  OutputEndianness,
439  UnitBits,
440  typename std::enable_if<is_same_unit<InputEndianness, OutputEndianness, UnitBits>::value>::type> {
441  template<typename ValueType>
442  inline static void reverse(ValueType &) {
443  }
444 
445  template<typename ValueType>
446  inline static ValueType reverse(ValueType const &val) {
447  return val;
448  }
449  };
450 
461  template<typename InputEndianness, typename OutputEndianness, int UnitBits>
463  InputEndianness,
464  OutputEndianness,
465  UnitBits,
466  typename std::enable_if<!is_same_unit<InputEndianness, OutputEndianness, UnitBits>::value &&
467  UnitBits == CHAR_BIT>::type> {
468  template<typename ValueType>
469  inline static void reverse(ValueType &val) {
470  boost::endian::endian_reverse_inplace(val);
471  }
472 
473  template<typename ValueType>
474  inline static ValueType reverse(ValueType const &val) {
475  return boost::endian::endian_reverse(val);
476  }
477  };
478 
490  template<typename InputEndianness, typename OutputEndianness, int UnitBits>
492  InputEndianness,
493  OutputEndianness,
494  UnitBits,
495  typename std::enable_if<!is_same_unit<InputEndianness, OutputEndianness, UnitBits>::value &&
496  (UnitBits > CHAR_BIT)>::type> {
497  template<typename ValueType, int ValueBits = sizeof(ValueType) * CHAR_BIT>
498  inline static void reverse(ValueType &val) {
499  boost::endian::endian_reverse_inplace(val);
500  ValueType out = ValueType();
502  val = out;
503  }
504 
505  template<typename ValueType, int ValueBits = sizeof(ValueType) * CHAR_BIT>
506  inline static ValueType reverse(ValueType const &val) {
507  ValueType tmp = boost::endian::endian_reverse(val);
508  ValueType out = ValueType();
510  return out;
511  }
512  };
513  } // namespace detail
514  } // namespace crypto3
515 } // namespace nil
516 
517 #endif // CRYPTO3_DETAIL_REVERSER_HPP
void reverse_bits(UnitType &unit)
The functions listed below deal with bit reversal in a unit.
Definition: block/include/nil/crypto3/detail/reverser.hpp:132
void reverse_byte(byte_type &b)
This function reverses bit order in the byte b depending on the machine word size....
Definition: block/include/nil/crypto3/detail/reverser.hpp:63
T unbounded_shr(T x)
Definition: algebra/include/nil/crypto3/detail/unbounded_shift.hpp:64
T unbounded_shl(T x)
Definition: algebra/include/nil/crypto3/detail/unbounded_shift.hpp:59
boost::uint_t< CHAR_BIT >::exact byte_type
Definition: block/include/nil/crypto3/detail/reverser.hpp:49
typename std::iterator_traits< Iterator >::value_type ValueType
Definition: algebra/include/nil/crypto3/detail/make_array.hpp:50
Definition: pair.hpp:29
static void reverse(typename boost::uint_t< UnitBits >::exact &, typename boost::uint_t< UnitBits >::exact &)
Definition: block/include/nil/crypto3/detail/reverser.hpp:106
bit_in_unit_byte_reverser transforms the sequence of bits in each byte of the input unit into reverse...
Definition: block/include/nil/crypto3/detail/reverser.hpp:87
static void reverse(UnitType &in, UnitType &out)
Definition: block/include/nil/crypto3/detail/reverser.hpp:94
boost::uint_t< UnitBits >::exact UnitType
Definition: block/include/nil/crypto3/detail/reverser.hpp:92
bit_in_unit_byte_reverser< UnitBits, k+CHAR_BIT > next_type
Definition: block/include/nil/crypto3/detail/reverser.hpp:91
static void reverse(ValueType &, ValueType &)
Definition: block/include/nil/crypto3/detail/reverser.hpp:192
bit_in_unit_reverser transforms the sequence of bits in each unit of the input value into reversed se...
Definition: block/include/nil/crypto3/detail/reverser.hpp:171
static void reverse(ValueType &in, ValueType &out)
Definition: block/include/nil/crypto3/detail/reverser.hpp:179
bit_in_unit_reverser< InputBits, UnitBits, k+UnitBits > next_type
Definition: block/include/nil/crypto3/detail/reverser.hpp:175
boost::uint_t< UnitBits >::exact UnitType
Definition: block/include/nil/crypto3/detail/reverser.hpp:176
BOOST_STATIC_ASSERT(!(InputBits % UnitBits) &&!(UnitBits % CHAR_BIT))
static ValueType reverse(ValueType const &val)
Definition: block/include/nil/crypto3/detail/reverser.hpp:310
static void reverse(ValueType &val)
Definition: block/include/nil/crypto3/detail/reverser.hpp:303
static ValueType reverse(ValueType const &val)
Definition: block/include/nil/crypto3/detail/reverser.hpp:285
static void reverse(ValueType &)
Definition: block/include/nil/crypto3/detail/reverser.hpp:281
bit_reverser reverses the sequence of bits in each unit of the given value, if InputEndianness and Ou...
Definition: block/include/nil/crypto3/detail/reverser.hpp:266
static void reverse(ValueType &, ValueType &)
Definition: block/include/nil/crypto3/detail/reverser.hpp:353
byte_in_unit_reverser transforms the sequence of bytes in each unit of the input value into reversed ...
Definition: block/include/nil/crypto3/detail/reverser.hpp:332
static void reverse(ValueType &in, ValueType &out)
Definition: block/include/nil/crypto3/detail/reverser.hpp:340
boost::uint_t< UnitBits >::exact UnitType
Definition: block/include/nil/crypto3/detail/reverser.hpp:337
BOOST_STATIC_ASSERT(!(InputBits % UnitBits) &&!(UnitBits % CHAR_BIT))
byte_in_unit_reverser< InputBits, UnitBits, k+UnitBits > next_type
Definition: block/include/nil/crypto3/detail/reverser.hpp:336
The group of traits below is used to determine the order of bits defined by the endianness.
Definition: block/include/nil/crypto3/detail/reverser.hpp:211
constexpr static const bool value
Definition: block/include/nil/crypto3/detail/reverser.hpp:212
The group of traits below is used to determine the order of units defined by the endianness.
Definition: block/include/nil/crypto3/detail/reverser.hpp:372
constexpr static const bool value
Definition: block/include/nil/crypto3/detail/reverser.hpp:373
Trait to determine whether the order of bits defined by Endianness endianness is little.
Definition: block/include/nil/crypto3/detail/reverser.hpp:227
constexpr static const bool value
Definition: block/include/nil/crypto3/detail/reverser.hpp:228
Trait to determine whether the order of units defined by Endianness endianness is little.
Definition: block/include/nil/crypto3/detail/reverser.hpp:388
constexpr static const bool value
Definition: block/include/nil/crypto3/detail/reverser.hpp:389
Trait to determine whether the orders of bits defined by Endianness1 endianness and Endianness2 endia...
Definition: block/include/nil/crypto3/detail/reverser.hpp:244
constexpr static const bool value
Definition: block/include/nil/crypto3/detail/reverser.hpp:245
Trait to determine whether the orders of units defined by Endianness1 endianness and Endianness2 endi...
Definition: block/include/nil/crypto3/detail/reverser.hpp:405
constexpr static const bool value
Definition: block/include/nil/crypto3/detail/reverser.hpp:406
unit_reverser reverses the sequence of units in the given value, if InputEndianness and OutputEndiann...
Definition: block/include/nil/crypto3/detail/reverser.hpp:423