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