diff options
| -rw-r--r-- | include/utils/LinearTransform.h | 64 | ||||
| -rw-r--r-- | libs/utils/Android.mk | 1 | ||||
| -rw-r--r-- | libs/utils/LinearTransform.cpp | 262 |
3 files changed, 327 insertions, 0 deletions
diff --git a/include/utils/LinearTransform.h b/include/utils/LinearTransform.h new file mode 100644 index 0000000..04cb355 --- /dev/null +++ b/include/utils/LinearTransform.h @@ -0,0 +1,64 @@ +/* + * 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. + */ + +#ifndef _LIBS_UTILS_LINEAR_TRANSFORM_H +#define _LIBS_UTILS_LINEAR_TRANSFORM_H + +#include <stdint.h> + +namespace android { + +// LinearTransform defines a structure which hold the definition of a +// transformation from single dimensional coordinate system A into coordinate +// system B (and back again). Values in A and in B are 64 bit, the linear +// scale factor is expressed as a rational number using two 32 bit values. +// +// Specifically, let +// f(a) = b +// F(b) = f^-1(b) = a +// then +// +// f(a) = (((a - a_zero) * a_to_b_numer) / a_to_b_denom) + b_zero; +// +// and +// +// F(b) = (((b - b_zero) * a_to_b_denom) / a_to_b_numer) + a_zero; +// +struct LinearTransform { + int64_t a_zero; + int64_t b_zero; + int32_t a_to_b_numer; + uint32_t a_to_b_denom; + + // Transform from A->B + // Returns true on success, or false in the case of a singularity or an + // overflow. + bool doForwardTransform(int64_t a_in, int64_t* b_out) const; + + // Transform from B->A + // Returns true on success, or false in the case of a singularity or an + // overflow. + bool doReverseTransform(int64_t b_in, int64_t* a_out) const; + + // Helpers which will reduce the fraction N/D using Euclid's method. + template <class T> static void reduce(T* N, T* D); + static void reduce(int32_t* N, uint32_t* D); +}; + + +} + +#endif // _LIBS_UTILS_LINEAR_TRANSFORM_H diff --git a/libs/utils/Android.mk b/libs/utils/Android.mk index 093189c..774e8c9 100644 --- a/libs/utils/Android.mk +++ b/libs/utils/Android.mk @@ -27,6 +27,7 @@ commonSources:= \ Debug.cpp \ FileMap.cpp \ Flattenable.cpp \ + LinearTransform.cpp \ ObbFile.cpp \ Pool.cpp \ PropertyMap.cpp \ diff --git a/libs/utils/LinearTransform.cpp b/libs/utils/LinearTransform.cpp new file mode 100644 index 0000000..d752415 --- /dev/null +++ b/libs/utils/LinearTransform.cpp @@ -0,0 +1,262 @@ +/* + * 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 |