libs/common_time/LinearTransform.cpp

   1 /*
   2  * Copyright (C) 2011 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #define __STDC_LIMIT_MACROS
  18
  19 #include "LinearTransform.h"
  20 #include <assert.h>
  21
  22
  23 // disable sanitize as these functions may intentionally overflow (see comments below).
  24 // the ifdef can be removed when host builds use clang.
  25 #if defined(__clang__)
  26 #define ATTRIBUTE_NO_SANITIZE_INTEGER __attribute__((no_sanitize("integer")))
  27 #else
  28 #define ATTRIBUTE_NO_SANITIZE_INTEGER
  29 #endif
  30
  31 namespace android {
  32
  33 // sanitize failure with T = int32_t and x = 0x80000000
  34 template<class T>
  35 ATTRIBUTE_NO_SANITIZE_INTEGER
  36 static inline T ABS(T x) { return (x < 0) ? -x : x; }
  37
  38 // Static math methods involving linear transformations
  39 // remote sanitize failure on overflow case.
  40 ATTRIBUTE_NO_SANITIZE_INTEGER
  41 static bool scale_u64_to_u64(
  42         uint64_t val,
  43         uint32_t N,
  44         uint32_t D,
  45         uint64_t* res,
  46         bool round_up_not_down) {
  47     uint64_t tmp1, tmp2;
  48     uint32_t r;
  49
  50     assert(res);
  51     assert(D);
  52
  53     // Let U32(X) denote a uint32_t containing the upper 32 bits of a 64 bit
  54     // integer X.
  55     // Let L32(X) denote a uint32_t containing the lower 32 bits of a 64 bit
  56     // integer X.
  57     // Let X[A, B] with A <= B denote bits A through B of the integer X.
  58     // Let (A | B) denote the concatination of two 32 bit ints, A and B.
  59     // IOW X = (A | B) => U32(X) == A && L32(X) == B
  60     //
  61     // compute M = val * N (a 96 bit int)
  62     // ---------------------------------
  63     // tmp2 = U32(val) * N (a 64 bit int)
  64     // tmp1 = L32(val) * N (a 64 bit int)
  65     // which means
  66     // M = val * N = (tmp2 << 32) + tmp1
  67     tmp2 = (val >> 32) * N;
  68     tmp1 = (val & UINT32_MAX) * N;
  69
  70     // compute M[32, 95]
  71     // tmp2 = tmp2 + U32(tmp1)
  72     //      = (U32(val) * N) + U32(L32(val) * N)
  73     //      = M[32, 95]
  74     tmp2 += tmp1 >> 32;
  75
  76     // if M[64, 95] >= D, then M/D has bits > 63 set and we have
  77     // an overflow.
  78     if ((tmp2 >> 32) >= D) {
  79         *res = UINT64_MAX;
  80         return false;
  81     }
  82
  83     // Divide.  Going in we know
  84     // tmp2 = M[32, 95]
  85     // U32(tmp2) < D
  86     r = tmp2 % D;
  87     tmp2 /= D;
  88
  89     // At this point
  90     // tmp1      = L32(val) * N
  91     // tmp2      = M[32, 95] / D
  92     //           = (M / D)[32, 95]
  93     // r         = M[32, 95] % D
  94     // U32(tmp2) = 0
  95     //
  96     // compute tmp1 = (r | M[0, 31])
  97     tmp1 = (tmp1 & UINT32_MAX) | ((uint64_t)r << 32);
  98
  99     // Divide again.  Keep the remainder around in order to round properly.
 100     r = tmp1 % D;
 101     tmp1 /= D;
 102
 103     // At this point
 104     // tmp2      = (M / D)[32, 95]
 105     // tmp1      = (M / D)[ 0, 31]
 106     // r         =  M % D
 107     // U32(tmp1) = 0
 108     // U32(tmp2) = 0
 109
 110     // Pack the result and deal with the round-up case (As well as the
 111     // remote possiblility over overflow in such a case).
 112     *res = (tmp2 << 32) | tmp1;
 113     if (r && round_up_not_down) {
 114         ++(*res);
 115         if (!(*res)) {
 116             *res = UINT64_MAX;
 117             return false;
 118         }
 119     }
 120
 121     return true;
 122 }
 123
 124 // at least one known sanitize failure (see comment below)
 125 ATTRIBUTE_NO_SANITIZE_INTEGER
 126 static bool linear_transform_s64_to_s64(
 127         int64_t  val,
 128         int64_t  basis1,
 129         int32_t  N,
 130         uint32_t D,
 131         bool     invert_frac,
 132         int64_t  basis2,
 133         int64_t* out) {
 134     uint64_t scaled, res;
 135     uint64_t abs_val;
 136     bool is_neg;
 137
 138     if (!out)
 139         return false;
 140
 141     // Compute abs(val - basis_64). Keep track of whether or not this delta
 142     // will be negative after the scale opertaion.
 143     if (val < basis1) {
 144         is_neg = true;
 145         abs_val = basis1 - val;
 146     } else {
 147         is_neg = false;
 148         abs_val = val - basis1;
 149     }
 150
 151     if (N < 0)
 152         is_neg = !is_neg;
 153
 154     if (!scale_u64_to_u64(abs_val,
 155                           invert_frac ? D : ABS(N),
 156                           invert_frac ? ABS(N) : D,
 157                           &scaled,
 158                           is_neg))
 159         return false; // overflow/undeflow
 160
 161     // if scaled is >= 0x8000<etc>, then we are going to overflow or
 162     // underflow unless ABS(basis2) is large enough to pull us back into the
 163     // non-overflow/underflow region.
 164     if (scaled & INT64_MIN) {
 165         if (is_neg && (basis2 < 0))
 166             return false; // certain underflow
 167
 168         if (!is_neg && (basis2 >= 0))
 169             return false; // certain overflow
 170
 171         if (ABS(basis2) <= static_cast<int64_t>(scaled & INT64_MAX))
 172             return false; // not enough
 173
 174         // Looks like we are OK
 175         *out = (is_neg ? (-scaled) : scaled) + basis2;
 176     } else {
 177         // Scaled fits within signed bounds, so we just need to check for
 178         // over/underflow for two signed integers.  Basically, if both scaled
 179         // and basis2 have the same sign bit, and the result has a different
 180         // sign bit, then we have under/overflow.  An easy way to compute this
 181         // is
 182         // (scaled_signbit XNOR basis_signbit) &&
 183         // (scaled_signbit XOR res_signbit)
 184         // ==
 185         // (scaled_signbit XOR basis_signbit XOR 1) &&
 186         // (scaled_signbit XOR res_signbit)
 187
 188         if (is_neg)
 189             scaled = -scaled; // known sanitize failure
 190         res = scaled + basis2;
 191
 192         if ((scaled ^ basis2 ^ INT64_MIN) & (scaled ^ res) & INT64_MIN)
 193             return false;
 194
 195         *out = res;
 196     }
 197
 198     return true;
 199 }
 200
 201 bool LinearTransform::doForwardTransform(int64_t a_in, int64_t* b_out) const {
 202     if (0 == a_to_b_denom)
 203         return false;
 204
 205     return linear_transform_s64_to_s64(a_in,
 206                                        a_zero,
 207                                        a_to_b_numer,
 208                                        a_to_b_denom,
 209                                        false,
 210                                        b_zero,
 211                                        b_out);
 212 }
 213
 214 bool LinearTransform::doReverseTransform(int64_t b_in, int64_t* a_out) const {
 215     if (0 == a_to_b_numer)
 216         return false;
 217
 218     return linear_transform_s64_to_s64(b_in,
 219                                        b_zero,
 220                                        a_to_b_numer,
 221                                        a_to_b_denom,
 222                                        true,
 223                                        a_zero,
 224                                        a_out);
 225 }
 226
 227 template <class T> void LinearTransform::reduce(T* N, T* D) {
 228     T a, b;
 229     if (!N || !D || !(*D)) {
 230         assert(false);
 231         return;
 232     }
 233
 234     a = *N;
 235     b = *D;
 236
 237     if (a == 0) {
 238         *D = 1;
 239         return;
 240     }
 241
 242     // This implements Euclid's method to find GCD.
 243     if (a < b) {
 244         T tmp = a;
 245         a = b;
 246         b = tmp;
 247     }
 248
 249     while (1) {
 250         // a is now the greater of the two.
 251         const T remainder = a % b;
 252         if (remainder == 0) {
 253             *N /= b;
 254             *D /= b;
 255             return;
 256         }
 257         // by swapping remainder and b, we are guaranteeing that a is
 258         // still the greater of the two upon entrance to the loop.
 259         a = b;
 260         b = remainder;
 261     }
 262 };
 263
 264 template void LinearTransform::reduce<uint64_t>(uint64_t* N, uint64_t* D);
 265 template void LinearTransform::reduce<uint32_t>(uint32_t* N, uint32_t* D);
 266
 267 // sanitize failure if *N = 0x80000000
 268 ATTRIBUTE_NO_SANITIZE_INTEGER
 269 void LinearTransform::reduce(int32_t* N, uint32_t* D) {
 270     if (N && D && *D) {
 271         if (*N < 0) {
 272             *N = -(*N);
 273             reduce(reinterpret_cast<uint32_t*>(N), D);
 274             *N = -(*N);
 275         } else {
 276             reduce(reinterpret_cast<uint32_t*>(N), D);
 277         }
 278     }
 279 }
 280
 281 }  // namespace android