blob: 463aca3840d67c128112c165135e29c12f8fcc53 [file] [log] [blame]
 // Copyright 2017 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef COMPONENTS_ZUCCHINI_ALGORITHM_H_ #define COMPONENTS_ZUCCHINI_ALGORITHM_H_ #include #include #include #include #include "base/logging.h" // Collection of simple utilities used in for low-level computation. namespace zucchini { // Safely determines whether |[begin, begin + size)| is in |[0, bound)|. Note: // The special case |[bound, bound)| is not considered to be in |[0, bound)|. template bool RangeIsBounded(T begin, T size, size_t bound) { static_assert(std::is_unsigned::value, "Value type must be unsigned."); return begin < bound && size <= bound - begin; } // Safely determines whether |value| lies in |[begin, begin + size)|. Works // properly even if |begin + size| overflows -- although such ranges are // considered pathological, and should fail validation elsewhere. template bool RangeCovers(T begin, T size, T value) { static_assert(std::is_unsigned::value, "Value type must be unsigned."); return begin <= value && value - begin < size; } // Returns the integer in inclusive range |[lo, hi]| that's closest to |value|. // This departs from the usual usage of semi-inclusive ranges, but is useful // because (1) sentinels can use this, (2) a valid output always exists. It is // assumed that |lo <= hi|. template T InclusiveClamp(T value, T lo, T hi) { static_assert(std::is_unsigned::value, "Value type must be unsigned."); DCHECK_LE(lo, hi); return value <= lo ? lo : (value >= hi ? hi : value); } // Returns the minimum multiple of |m| that's no less than |x|. Assumes |m > 0| // and |x| is sufficiently small so that no overflow occurs. template constexpr T AlignCeil(T x, T m) { static_assert(std::is_unsigned::value, "Value type must be unsigned."); return T((x + m - 1) / m) * m; } // Sorts values in |container| and removes duplicates. template void SortAndUniquify(std::vector* container) { std::sort(container->begin(), container->end()); container->erase(std::unique(container->begin(), container->end()), container->end()); container->shrink_to_fit(); } // Extracts a single bit at |pos| from integer |v|. template constexpr T GetBit(T v) { return (v >> pos) & 1; } // Extracts bits in inclusive range [|lo|, |hi|] from integer |v|, and returns // the sign-extend result. For example, let the (MSB-first) bits in a 32-bit int // |v| be: // xxxxxxxx xxxxxSii iiiiiiii iyyyyyyy, // hi^ lo^ => lo = 7, hi = 18 // To extract "Sii iiiiiiii i", calling // GetSignedBits<7, 18>(v); // produces the sign-extended result: // SSSSSSSS SSSSSSSS SSSSSiii iiiiiiii. template constexpr typename std::make_signed::type GetSignedBits(T v) { constexpr int kNumBits = sizeof(T) * 8; using SignedType = typename std::make_signed::type; // Assumes 0 <= |lo| <= |hi| < |kNumBits|. // How this works: // (1) Shift-left by |kNumBits - 1 - hi| to clear "left" bits. // (2) Shift-right by |kNumBits - 1 - hi + lo| to clear "right" bits. The // input is casted to a signed type to perform sign-extension. return static_cast(v << (kNumBits - 1 - hi)) >> (kNumBits - 1 - hi + lo); } // Similar to GetSignedBits(), but returns the zero-extended result. For the // above example, calling // GetUnsignedBits<7, 18>(v); // results in: // 00000000 00000000 0000Siii iiiiiiii. template constexpr typename std::make_unsigned::type GetUnsignedBits(T v) { constexpr int kNumBits = sizeof(T) * 8; using UnsignedType = typename std::make_unsigned::type; return static_cast(v << (kNumBits - 1 - hi)) >> (kNumBits - 1 - hi + lo); } // Copies bits at |pos| in |v| to all higher bits, and returns the result as the // same int type as |v|. template constexpr T SignExtend(int pos, T v) { int kNumBits = sizeof(T) * 8; int kShift = kNumBits - 1 - pos; return static_cast::type>(v << kShift) >> kShift; } // Optimized version where |pos| becomes a template parameter. template constexpr T SignExtend(T v) { constexpr int kNumBits = sizeof(T) * 8; constexpr int kShift = kNumBits - 1 - pos; return static_cast::type>(v << kShift) >> kShift; } // Determines whether |v|, if interpreted as a signed integer, is representable // using |digs| bits. |1 <= digs <= sizeof(T)| is assumed. template constexpr bool SignedFit(T v) { return v == SignExtend(v); } } // namespace zucchini #endif // COMPONENTS_ZUCCHINI_ALGORITHM_H_