algorithm.h 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147
  1. // Copyright 2017 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef COMPONENTS_ZUCCHINI_ALGORITHM_H_
  5. #define COMPONENTS_ZUCCHINI_ALGORITHM_H_
  6. #include <stddef.h>
  7. #include <algorithm>
  8. #include <deque>
  9. #include <type_traits>
  10. #include <vector>
  11. #include "base/check_op.h"
  12. // Collection of simple utilities used in for low-level computation.
  13. namespace zucchini {
  14. // Safely determines whether |[begin, begin + size)| is in |[0, bound)|. Note:
  15. // The special case |[bound, bound)| is not considered to be in |[0, bound)|.
  16. template <typename T>
  17. bool RangeIsBounded(T begin, T size, size_t bound) {
  18. static_assert(std::is_unsigned<T>::value, "Value type must be unsigned.");
  19. return begin < bound && size <= bound - begin;
  20. }
  21. // Safely determines whether |value| lies in |[begin, begin + size)|. Works
  22. // properly even if |begin + size| overflows -- although such ranges are
  23. // considered pathological, and should fail validation elsewhere.
  24. template <typename T>
  25. bool RangeCovers(T begin, T size, T value) {
  26. static_assert(std::is_unsigned<T>::value, "Value type must be unsigned.");
  27. return begin <= value && value - begin < size;
  28. }
  29. // Returns the integer in inclusive range |[lo, hi]| that's closest to |value|.
  30. // This departs from the usual usage of semi-inclusive ranges, but is useful
  31. // because (1) sentinels can use this, (2) a valid output always exists. It is
  32. // assumed that |lo <= hi|.
  33. template <class T>
  34. T InclusiveClamp(T value, T lo, T hi) {
  35. static_assert(std::is_unsigned<T>::value, "Value type must be unsigned.");
  36. DCHECK_LE(lo, hi);
  37. return value <= lo ? lo : (value >= hi ? hi : value);
  38. }
  39. // Returns the minimum multiple of |m| that's no less than |x|. Assumes |m > 0|
  40. // and |x| is sufficiently small so that no overflow occurs.
  41. template <class T>
  42. constexpr T AlignCeil(T x, T m) {
  43. static_assert(std::is_unsigned<T>::value, "Value type must be unsigned.");
  44. return T((x + m - 1) / m) * m;
  45. }
  46. // Specialized alignment helpers that returns the increment to |pos| to get the
  47. // next n-aligned value, where n is in {2, 4}. This is useful for aligning
  48. // iterators relative to a base iterator using:
  49. // it += IncrementForAlignCeil2(it - base);
  50. template <class T>
  51. inline int IncrementForAlignCeil2(T pos) {
  52. return static_cast<int>(pos & 1); // Optimized from (-pos) & 1.
  53. }
  54. template <class T>
  55. inline int IncrementForAlignCeil4(T pos) {
  56. return static_cast<int>((-pos) & 3);
  57. }
  58. // Sorts values in |container| and removes duplicates.
  59. template <class T>
  60. void SortAndUniquify(std::deque<T>* container) {
  61. std::sort(container->begin(), container->end());
  62. container->erase(std::unique(container->begin(), container->end()),
  63. container->end());
  64. container->shrink_to_fit();
  65. }
  66. // Extracts a single bit at |pos| from integer |v|.
  67. template <int pos, typename T>
  68. constexpr T GetBit(T v) {
  69. return (v >> pos) & 1;
  70. }
  71. // Extracts bits in inclusive range [|lo|, |hi|] from integer |v|, and returns
  72. // the sign-extend result. For example, let the (MSB-first) bits in a 32-bit int
  73. // |v| be:
  74. // xxxxxxxx xxxxxSii iiiiiiii iyyyyyyy,
  75. // hi^ lo^ => lo = 7, hi = 18
  76. // To extract "Sii iiiiiiii i", calling
  77. // GetSignedBits<7, 18>(v);
  78. // produces the sign-extended result:
  79. // SSSSSSSS SSSSSSSS SSSSSiii iiiiiiii.
  80. template <int lo, int hi, typename T>
  81. constexpr typename std::make_signed<T>::type GetSignedBits(T v) {
  82. constexpr int kNumBits = sizeof(T) * 8;
  83. using SignedType = typename std::make_signed<T>::type;
  84. // Assumes 0 <= |lo| <= |hi| < |kNumBits|.
  85. // How this works:
  86. // (1) Shift-left by |kNumBits - 1 - hi| to clear "left" bits.
  87. // (2) Shift-right by |kNumBits - 1 - hi + lo| to clear "right" bits. The
  88. // input is casted to a signed type to perform sign-extension.
  89. return static_cast<SignedType>(v << (kNumBits - 1 - hi)) >>
  90. (kNumBits - 1 - hi + lo);
  91. }
  92. // Similar to GetSignedBits(), but returns the zero-extended result. For the
  93. // above example, calling
  94. // GetUnsignedBits<7, 18>(v);
  95. // results in:
  96. // 00000000 00000000 0000Siii iiiiiiii.
  97. template <int lo, int hi, typename T>
  98. constexpr typename std::make_unsigned<T>::type GetUnsignedBits(T v) {
  99. constexpr int kNumBits = sizeof(T) * 8;
  100. using UnsignedType = typename std::make_unsigned<T>::type;
  101. return static_cast<UnsignedType>(v << (kNumBits - 1 - hi)) >>
  102. (kNumBits - 1 - hi + lo);
  103. }
  104. // Copies bits at |pos| in |v| to all higher bits, and returns the result as the
  105. // same int type as |v|.
  106. template <typename T>
  107. constexpr T SignExtend(int pos, T v) {
  108. int kNumBits = sizeof(T) * 8;
  109. int kShift = kNumBits - 1 - pos;
  110. return static_cast<typename std::make_signed<T>::type>(v << kShift) >> kShift;
  111. }
  112. // Optimized version where |pos| becomes a template parameter.
  113. template <int pos, typename T>
  114. constexpr T SignExtend(T v) {
  115. constexpr int kNumBits = sizeof(T) * 8;
  116. constexpr int kShift = kNumBits - 1 - pos;
  117. return static_cast<typename std::make_signed<T>::type>(v << kShift) >> kShift;
  118. }
  119. // Determines whether |v|, if interpreted as a signed integer, is representable
  120. // using |digs| bits. |1 <= digs <= sizeof(T)| is assumed.
  121. template <int digs, typename T>
  122. constexpr bool SignedFit(T v) {
  123. return v == SignExtend<digs - 1, T>(v);
  124. }
  125. } // namespace zucchini
  126. #endif // COMPONENTS_ZUCCHINI_ALGORITHM_H_