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