libutils/LinearTransform.cpp

/*
 * Copyright (C) 2011 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#define __STDC_LIMIT_MACROS

#include <assert.h>
#include <stdint.h>

#include <utils/LinearTransform.h>

// disable sanitize as these functions may intentionally overflow (see comments below).
// the ifdef can be removed when host builds use clang.
#if defined(__clang__)
#define ATTRIBUTE_NO_SANITIZE_INTEGER __attribute__((no_sanitize("integer")))
#else
#define ATTRIBUTE_NO_SANITIZE_INTEGER
#endif

namespace android {

// sanitize failure with T = int32_t and x = 0x80000000
template<class T>
ATTRIBUTE_NO_SANITIZE_INTEGER
static inline T ABS(T x) { return (x < 0) ? -x : x; }

// Static math methods involving linear transformations
// remote sanitize failure on overflow case.
ATTRIBUTE_NO_SANITIZE_INTEGER
static bool scale_u64_to_u64(
        uint64_t val,
        uint32_t N,
        uint32_t D,
        uint64_t* res,
        bool round_up_not_down) {
    uint64_t tmp1, tmp2;
    uint32_t r;

    assert(res);
    assert(D);

    // Let U32(X) denote a uint32_t containing the upper 32 bits of a 64 bit
    // integer X.
    // Let L32(X) denote a uint32_t containing the lower 32 bits of a 64 bit
    // integer X.
    // Let X[A, B] with A <= B denote bits A through B of the integer X.
    // Let (A | B) denote the concatination of two 32 bit ints, A and B.
    // IOW X = (A | B) => U32(X) == A && L32(X) == B
    //
    // compute M = val * N (a 96 bit int)
    // ---------------------------------
    // tmp2 = U32(val) * N (a 64 bit int)
    // tmp1 = L32(val) * N (a 64 bit int)
    // which means
    // M = val * N = (tmp2 << 32) + tmp1
    tmp2 = (val >> 32) * N;
    tmp1 = (val & UINT32_MAX) * N;

    // compute M[32, 95]
    // tmp2 = tmp2 + U32(tmp1)
    //      = (U32(val) * N) + U32(L32(val) * N)
    //      = M[32, 95]
    tmp2 += tmp1 >> 32;

    // if M[64, 95] >= D, then M/D has bits > 63 set and we have
    // an overflow.
    if ((tmp2 >> 32) >= D) {
        *res = UINT64_MAX;
        return false;
    }

    // Divide.  Going in we know
    // tmp2 = M[32, 95]
    // U32(tmp2) < D
    r = tmp2 % D;
    tmp2 /= D;

    // At this point
    // tmp1      = L32(val) * N
    // tmp2      = M[32, 95] / D
    //           = (M / D)[32, 95]
    // r         = M[32, 95] % D
    // U32(tmp2) = 0
    //
    // compute tmp1 = (r | M[0, 31])
    tmp1 = (tmp1 & UINT32_MAX) | ((uint64_t)r << 32);

    // Divide again.  Keep the remainder around in order to round properly.
    r = tmp1 % D;
    tmp1 /= D;

    // At this point
    // tmp2      = (M / D)[32, 95]
    // tmp1      = (M / D)[ 0, 31]
    // r         =  M % D
    // U32(tmp1) = 0
    // U32(tmp2) = 0

    // Pack the result and deal with the round-up case (As well as the
    // remote possiblility over overflow in such a case).
    *res = (tmp2 << 32) | tmp1;
    if (r && round_up_not_down) {
        ++(*res);
        if (!(*res)) {
            *res = UINT64_MAX;
            return false;
        }
    }

    return true;
}

// at least one known sanitize failure (see comment below)
ATTRIBUTE_NO_SANITIZE_INTEGER
static bool linear_transform_s64_to_s64(
        int64_t  val,
        int64_t  basis1,
        int32_t  N,
        uint32_t D,
        bool     invert_frac,
        int64_t  basis2,
        int64_t* out) {
    uint64_t scaled, res;
    uint64_t abs_val;
    bool is_neg;

    if (!out)
        return false;

    // Compute abs(val - basis_64). Keep track of whether or not this delta
    // will be negative after the scale opertaion.
    if (val < basis1) {
        is_neg = true;
        abs_val = basis1 - val;
    } else {
        is_neg = false;
        abs_val = val - basis1;
    }

    if (N < 0)
        is_neg = !is_neg;

    if (!scale_u64_to_u64(abs_val,
                          invert_frac ? D : ABS(N),
                          invert_frac ? ABS(N) : D,
                          &scaled,
                          is_neg))
        return false; // overflow/undeflow

    // if scaled is >= 0x8000<etc>, then we are going to overflow or
    // underflow unless ABS(basis2) is large enough to pull us back into the
    // non-overflow/underflow region.
    if (scaled & INT64_MIN) {
        if (is_neg && (basis2 < 0))
            return false; // certain underflow

        if (!is_neg && (basis2 >= 0))
            return false; // certain overflow

        if (ABS(basis2) <= static_cast<int64_t>(scaled & INT64_MAX))
            return false; // not enough

        // Looks like we are OK
        *out = (is_neg ? (-scaled) : scaled) + basis2;
    } else {
        // Scaled fits within signed bounds, so we just need to check for
        // over/underflow for two signed integers.  Basically, if both scaled
        // and basis2 have the same sign bit, and the result has a different
        // sign bit, then we have under/overflow.  An easy way to compute this
        // is
        // (scaled_signbit XNOR basis_signbit) &&
        // (scaled_signbit XOR res_signbit)
        // ==
        // (scaled_signbit XOR basis_signbit XOR 1) &&
        // (scaled_signbit XOR res_signbit)

        if (is_neg)
            scaled = -scaled; // known sanitize failure
        res = scaled + basis2;

        if ((scaled ^ basis2 ^ INT64_MIN) & (scaled ^ res) & INT64_MIN)
            return false;

        *out = res;
    }

    return true;
}

bool LinearTransform::doForwardTransform(int64_t a_in, int64_t* b_out) const {
    if (0 == a_to_b_denom)
        return false;

    return linear_transform_s64_to_s64(a_in,
                                       a_zero,
                                       a_to_b_numer,
                                       a_to_b_denom,
                                       false,
                                       b_zero,
                                       b_out);
}

bool LinearTransform::doReverseTransform(int64_t b_in, int64_t* a_out) const {
    if (0 == a_to_b_numer)
        return false;

    return linear_transform_s64_to_s64(b_in,
                                       b_zero,
                                       a_to_b_numer,
                                       a_to_b_denom,
                                       true,
                                       a_zero,
                                       a_out);
}

template <class T> void LinearTransform::reduce(T* N, T* D) {
    T a, b;
    if (!N || !D || !(*D)) {
        assert(false);
        return;
    }

    a = *N;
    b = *D;

    if (a == 0) {
        *D = 1;
        return;
    }

    // This implements Euclid's method to find GCD.
    if (a < b) {
        T tmp = a;
        a = b;
        b = tmp;
    }

    while (1) {
        // a is now the greater of the two.
        const T remainder = a % b;
        if (remainder == 0) {
            *N /= b;
            *D /= b;
            return;
        }
        // by swapping remainder and b, we are guaranteeing that a is
        // still the greater of the two upon entrance to the loop.
        a = b;
        b = remainder;
    }
};

template void LinearTransform::reduce<uint64_t>(uint64_t* N, uint64_t* D);
template void LinearTransform::reduce<uint32_t>(uint32_t* N, uint32_t* D);

// sanitize failure if *N = 0x80000000
ATTRIBUTE_NO_SANITIZE_INTEGER
void LinearTransform::reduce(int32_t* N, uint32_t* D) {
    if (N && D && *D) {
        if (*N < 0) {
            *N = -(*N);
            reduce(reinterpret_cast<uint32_t*>(N), D);
            *N = -(*N);
        } else {
            reduce(reinterpret_cast<uint32_t*>(N), D);
        }
    }
}

}  // namespace android