summaryrefslogtreecommitdiffstats
path: root/libs/utils/LinearTransform.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'libs/utils/LinearTransform.cpp')
-rw-r--r--libs/utils/LinearTransform.cpp262
1 files changed, 0 insertions, 262 deletions
diff --git a/libs/utils/LinearTransform.cpp b/libs/utils/LinearTransform.cpp
deleted file mode 100644
index d752415..0000000
--- a/libs/utils/LinearTransform.cpp
+++ /dev/null
@@ -1,262 +0,0 @@
-/*
- * 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>
-
-namespace android {
-
-template<class T> static inline T ABS(T x) { return (x < 0) ? -x : x; }
-
-// Static math methods involving linear transformations
-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;
-}
-
-static bool linear_transform_s64_to_s64(
- int64_t val,
- int64_t basis1,
- int32_t N,
- uint32_t D,
- 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,
- 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;
- 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,
- 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_denom,
- a_to_b_numer,
- 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);
-
-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
generated by cgit v1.1 at 2024-08-01 10:33:38 +0000