Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame^] | 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 | |
| 5 | #ifndef COMPONENTS_ZUCCHINI_ALGORITHM_H_ |
| 6 | #define COMPONENTS_ZUCCHINI_ALGORITHM_H_ |
| 7 | |
| 8 | #include <stddef.h> |
| 9 | |
| 10 | #include <algorithm> |
| 11 | #include <type_traits> |
| 12 | #include <vector> |
| 13 | |
| 14 | #include "base/logging.h" |
| 15 | |
| 16 | // Collection of simple utilities used in for low-level computation. |
| 17 | |
| 18 | namespace zucchini { |
| 19 | |
| 20 | // Safely determines whether |[begin, begin + size)| is in |[0, bound)|. Note: |
| 21 | // The special case |[bound, bound)| is not considered to be in |[0, bound)|. |
| 22 | template <typename T> |
| 23 | bool RangeIsBounded(T begin, T size, size_t bound) { |
| 24 | static_assert(std::is_unsigned<T>::value, "Value type must be unsigned."); |
| 25 | return begin < bound && size <= bound - begin; |
| 26 | } |
| 27 | |
| 28 | // Safely determines whether |value| lies in |[begin, begin + size)|. Works |
| 29 | // properly even if |begin + size| overflows -- although such ranges are |
| 30 | // considered pathological, and should fail validation elsewhere. |
| 31 | template <typename T> |
| 32 | bool RangeCovers(T begin, T size, T value) { |
| 33 | static_assert(std::is_unsigned<T>::value, "Value type must be unsigned."); |
| 34 | return begin <= value && value - begin < size; |
| 35 | } |
| 36 | |
| 37 | // Returns the integer in inclusive range |[lo, hi]| that's closest to |value|. |
| 38 | // This departs from the usual usage of semi-inclusive ranges, but is useful |
| 39 | // because (1) sentinels can use this, (2) a valid output always exists. It is |
| 40 | // assumed that |lo <= hi|. |
| 41 | template <class T> |
| 42 | T InclusiveClamp(T value, T lo, T hi) { |
| 43 | static_assert(std::is_unsigned<T>::value, "Value type must be unsigned."); |
| 44 | DCHECK_LE(lo, hi); |
| 45 | return value <= lo ? lo : (value >= hi ? hi : value); |
| 46 | } |
| 47 | |
| 48 | // Returns the minimum multiple of |m| that's no less than |x|. Assumes |m > 0| |
| 49 | // and |x| is sufficiently small so that no overflow occurs. |
| 50 | template <class T> |
| 51 | constexpr T ceil(T x, T m) { |
| 52 | static_assert(std::is_unsigned<T>::value, "Value type must be unsigned."); |
| 53 | return T((x + m - 1) / m) * m; |
| 54 | } |
| 55 | |
| 56 | // Sorts values in |container| and removes duplicates. |
| 57 | template <class T> |
| 58 | void SortAndUniquify(std::vector<T>* container) { |
| 59 | std::sort(container->begin(), container->end()); |
| 60 | container->erase(std::unique(container->begin(), container->end()), |
| 61 | container->end()); |
| 62 | container->shrink_to_fit(); |
| 63 | } |
| 64 | |
| 65 | // Copies bits at |pos| in |v| to all higher bits, and returns the result as the |
| 66 | // same int type as |v|. |
| 67 | template <typename T> |
| 68 | constexpr T SignExtend(int pos, T v) { |
| 69 | int kNumBits = sizeof(T) * 8; |
| 70 | int kShift = kNumBits - 1 - pos; |
| 71 | return static_cast<typename std::make_signed<T>::type>(v << kShift) >> kShift; |
| 72 | } |
| 73 | |
| 74 | // Optimized version where |pos| becomes a template parameter. |
| 75 | template <int pos, typename T> |
| 76 | constexpr T SignExtend(T v) { |
| 77 | constexpr int kNumBits = sizeof(T) * 8; |
| 78 | constexpr int kShift = kNumBits - 1 - pos; |
| 79 | return static_cast<typename std::make_signed<T>::type>(v << kShift) >> kShift; |
| 80 | } |
| 81 | |
| 82 | } // namespace zucchini |
| 83 | |
| 84 | #endif // COMPONENTS_ZUCCHINI_ALGORITHM_H_ |