Home | History | Annotate | Download | only in libutils
      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 <assert.h>
     20 #include <stdint.h>
     21 
     22 #include <utils/LinearTransform.h>
     23 
     24 namespace android {
     25 
     26 template<class T> static inline T ABS(T x) { return (x < 0) ? -x : x; }
     27 
     28 // Static math methods involving linear transformations
     29 static bool scale_u64_to_u64(
     30         uint64_t val,
     31         uint32_t N,
     32         uint32_t D,
     33         uint64_t* res,
     34         bool round_up_not_down) {
     35     uint64_t tmp1, tmp2;
     36     uint32_t r;
     37 
     38     assert(res);
     39     assert(D);
     40 
     41     // Let U32(X) denote a uint32_t containing the upper 32 bits of a 64 bit
     42     // integer X.
     43     // Let L32(X) denote a uint32_t containing the lower 32 bits of a 64 bit
     44     // integer X.
     45     // Let X[A, B] with A <= B denote bits A through B of the integer X.
     46     // Let (A | B) denote the concatination of two 32 bit ints, A and B.
     47     // IOW X = (A | B) => U32(X) == A && L32(X) == B
     48     //
     49     // compute M = val * N (a 96 bit int)
     50     // ---------------------------------
     51     // tmp2 = U32(val) * N (a 64 bit int)
     52     // tmp1 = L32(val) * N (a 64 bit int)
     53     // which means
     54     // M = val * N = (tmp2 << 32) + tmp1
     55     tmp2 = (val >> 32) * N;
     56     tmp1 = (val & UINT32_MAX) * N;
     57 
     58     // compute M[32, 95]
     59     // tmp2 = tmp2 + U32(tmp1)
     60     //      = (U32(val) * N) + U32(L32(val) * N)
     61     //      = M[32, 95]
     62     tmp2 += tmp1 >> 32;
     63 
     64     // if M[64, 95] >= D, then M/D has bits > 63 set and we have
     65     // an overflow.
     66     if ((tmp2 >> 32) >= D) {
     67         *res = UINT64_MAX;
     68         return false;
     69     }
     70 
     71     // Divide.  Going in we know
     72     // tmp2 = M[32, 95]
     73     // U32(tmp2) < D
     74     r = tmp2 % D;
     75     tmp2 /= D;
     76 
     77     // At this point
     78     // tmp1      = L32(val) * N
     79     // tmp2      = M[32, 95] / D
     80     //           = (M / D)[32, 95]
     81     // r         = M[32, 95] % D
     82     // U32(tmp2) = 0
     83     //
     84     // compute tmp1 = (r | M[0, 31])
     85     tmp1 = (tmp1 & UINT32_MAX) | ((uint64_t)r << 32);
     86 
     87     // Divide again.  Keep the remainder around in order to round properly.
     88     r = tmp1 % D;
     89     tmp1 /= D;
     90 
     91     // At this point
     92     // tmp2      = (M / D)[32, 95]
     93     // tmp1      = (M / D)[ 0, 31]
     94     // r         =  M % D
     95     // U32(tmp1) = 0
     96     // U32(tmp2) = 0
     97 
     98     // Pack the result and deal with the round-up case (As well as the
     99     // remote possiblility over overflow in such a case).
    100     *res = (tmp2 << 32) | tmp1;
    101     if (r && round_up_not_down) {
    102         ++(*res);
    103         if (!(*res)) {
    104             *res = UINT64_MAX;
    105             return false;
    106         }
    107     }
    108 
    109     return true;
    110 }
    111 
    112 static bool linear_transform_s64_to_s64(
    113         int64_t  val,
    114         int64_t  basis1,
    115         int32_t  N,
    116         uint32_t D,
    117         bool     invert_frac,
    118         int64_t  basis2,
    119         int64_t* out) {
    120     uint64_t scaled, res;
    121     uint64_t abs_val;
    122     bool is_neg;
    123 
    124     if (!out)
    125         return false;
    126 
    127     // Compute abs(val - basis_64). Keep track of whether or not this delta
    128     // will be negative after the scale opertaion.
    129     if (val < basis1) {
    130         is_neg = true;
    131         abs_val = basis1 - val;
    132     } else {
    133         is_neg = false;
    134         abs_val = val - basis1;
    135     }
    136 
    137     if (N < 0)
    138         is_neg = !is_neg;
    139 
    140     if (!scale_u64_to_u64(abs_val,
    141                           invert_frac ? D : ABS(N),
    142                           invert_frac ? ABS(N) : D,
    143                           &scaled,
    144                           is_neg))
    145         return false; // overflow/undeflow
    146 
    147     // if scaled is >= 0x8000<etc>, then we are going to overflow or
    148     // underflow unless ABS(basis2) is large enough to pull us back into the
    149     // non-overflow/underflow region.
    150     if (scaled & INT64_MIN) {
    151         if (is_neg && (basis2 < 0))
    152             return false; // certain underflow
    153 
    154         if (!is_neg && (basis2 >= 0))
    155             return false; // certain overflow
    156 
    157         if (ABS(basis2) <= static_cast<int64_t>(scaled & INT64_MAX))
    158             return false; // not enough
    159 
    160         // Looks like we are OK
    161         *out = (is_neg ? (-scaled) : scaled) + basis2;
    162     } else {
    163         // Scaled fits within signed bounds, so we just need to check for
    164         // over/underflow for two signed integers.  Basically, if both scaled
    165         // and basis2 have the same sign bit, and the result has a different
    166         // sign bit, then we have under/overflow.  An easy way to compute this
    167         // is
    168         // (scaled_signbit XNOR basis_signbit) &&
    169         // (scaled_signbit XOR res_signbit)
    170         // ==
    171         // (scaled_signbit XOR basis_signbit XOR 1) &&
    172         // (scaled_signbit XOR res_signbit)
    173 
    174         if (is_neg)
    175             scaled = -scaled;
    176         res = scaled + basis2;
    177 
    178         if ((scaled ^ basis2 ^ INT64_MIN) & (scaled ^ res) & INT64_MIN)
    179             return false;
    180 
    181         *out = res;
    182     }
    183 
    184     return true;
    185 }
    186 
    187 bool LinearTransform::doForwardTransform(int64_t a_in, int64_t* b_out) const {
    188     if (0 == a_to_b_denom)
    189         return false;
    190 
    191     return linear_transform_s64_to_s64(a_in,
    192                                        a_zero,
    193                                        a_to_b_numer,
    194                                        a_to_b_denom,
    195                                        false,
    196                                        b_zero,
    197                                        b_out);
    198 }
    199 
    200 bool LinearTransform::doReverseTransform(int64_t b_in, int64_t* a_out) const {
    201     if (0 == a_to_b_numer)
    202         return false;
    203 
    204     return linear_transform_s64_to_s64(b_in,
    205                                        b_zero,
    206                                        a_to_b_numer,
    207                                        a_to_b_denom,
    208                                        true,
    209                                        a_zero,
    210                                        a_out);
    211 }
    212 
    213 template <class T> void LinearTransform::reduce(T* N, T* D) {
    214     T a, b;
    215     if (!N || !D || !(*D)) {
    216         assert(false);
    217         return;
    218     }
    219 
    220     a = *N;
    221     b = *D;
    222 
    223     if (a == 0) {
    224         *D = 1;
    225         return;
    226     }
    227 
    228     // This implements Euclid's method to find GCD.
    229     if (a < b) {
    230         T tmp = a;
    231         a = b;
    232         b = tmp;
    233     }
    234 
    235     while (1) {
    236         // a is now the greater of the two.
    237         const T remainder = a % b;
    238         if (remainder == 0) {
    239             *N /= b;
    240             *D /= b;
    241             return;
    242         }
    243         // by swapping remainder and b, we are guaranteeing that a is
    244         // still the greater of the two upon entrance to the loop.
    245         a = b;
    246         b = remainder;
    247     }
    248 };
    249 
    250 template void LinearTransform::reduce<uint64_t>(uint64_t* N, uint64_t* D);
    251 template void LinearTransform::reduce<uint32_t>(uint32_t* N, uint32_t* D);
    252 
    253 void LinearTransform::reduce(int32_t* N, uint32_t* D) {
    254     if (N && D && *D) {
    255         if (*N < 0) {
    256             *N = -(*N);
    257             reduce(reinterpret_cast<uint32_t*>(N), D);
    258             *N = -(*N);
    259         } else {
    260             reduce(reinterpret_cast<uint32_t*>(N), D);
    261         }
    262     }
    263 }
    264 
    265 }  // namespace android
    266