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