1dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/* libs/pixelflinger/fixed.cpp 2dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** 3dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** Copyright 2006, The Android Open Source Project 4dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** 5dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** Licensed under the Apache License, Version 2.0 (the "License"); 6dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** you may not use this file except in compliance with the License. 7dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** You may obtain a copy of the License at 8dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** 9dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** http://www.apache.org/licenses/LICENSE-2.0 10dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** 11dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** Unless required by applicable law or agreed to in writing, software 12dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** distributed under the License is distributed on an "AS IS" BASIS, 13dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** See the License for the specific language governing permissions and 15dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project** limitations under the License. 16dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project*/ 17dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 18dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <stdio.h> 19dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 20dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <private/pixelflinger/ggl_context.h> 21dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <private/pixelflinger/ggl_fixed.h> 22dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 23dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 24dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// ------------------------------------------------------------------------ 25dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 26dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectint32_t gglRecipQNormalized(int32_t x, int* exponent) 27dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 28dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project const int32_t s = x>>31; 29dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project uint32_t a = s ? -x : x; 30dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 31dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // the result will overflow, so just set it to the biggest/inf value 32dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (ggl_unlikely(a <= 2LU)) { 33dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project *exponent = 0; 34dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return s ? FIXED_MIN : FIXED_MAX; 35dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 36dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 37dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // Newton-Raphson iteration: 38dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // x = r*(2 - a*r) 39dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 40dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project const int32_t lz = gglClz(a); 41dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project a <<= lz; // 0.32 42dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project uint32_t r = a; 43dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // note: if a == 0x80000000, this means x was a power-of-2, in this 44dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // case we don't need to compute anything. We get the reciprocal for 45dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // (almost) free. 46dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (a != 0x80000000) { 47dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r = (0x2E800 << (30-16)) - (r>>(2-1)); // 2.30, r = 2.90625 - 2*a 48dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // 0.32 + 2.30 = 2.62 -> 2.30 49dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // 2.30 + 2.30 = 4.60 -> 2.30 50dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r = (((2LU<<30) - uint32_t((uint64_t(a)*r) >> 32)) * uint64_t(r)) >> 30; 51dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r = (((2LU<<30) - uint32_t((uint64_t(a)*r) >> 32)) * uint64_t(r)) >> 30; 52dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 53dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 54dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // shift right 1-bit to make room for the sign bit 55dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project *exponent = 30-lz-1; 56dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r >>= 1; 57dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return s ? -r : r; 58dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 59dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 60dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectint32_t gglRecipQ(GGLfixed x, int q) 61dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 62dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int shift; 63dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project x = gglRecipQNormalized(x, &shift); 64dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project shift += 16-q; 6565026f980a6df01a7d437ce51a47de911820041eBhanu Chetlapalli if (shift > 0) 6665026f980a6df01a7d437ce51a47de911820041eBhanu Chetlapalli x += 1L << (shift-1); // rounding 67dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project x >>= shift; 68dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return x; 69dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 70dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 71dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// ------------------------------------------------------------------------ 72dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 73dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source ProjectGGLfixed gglFastDivx(GGLfixed n, GGLfixed d) 74dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 75dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if ((d>>24) && ((d>>24)+1)) { 76dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n >>= 8; 77dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project d >>= 8; 78dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 79dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return gglMulx(n, gglRecip(d)); 80dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 81dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 82dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// ------------------------------------------------------------------------ 83dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 84dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic const GGLfixed ggl_sqrt_reciproc_approx_tab[8] = { 85dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // 1/sqrt(x) with x = 1-N/16, N=[8...1] 86dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 0x16A09, 0x15555, 0x143D1, 0x134BF, 0x1279A, 0x11C01, 0x111AC, 0x10865 87dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}; 88dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 89dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source ProjectGGLfixed gglSqrtRecipx(GGLfixed x) 90dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 91dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (x == 0) return FIXED_MAX; 92dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (x == FIXED_ONE) return x; 93dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project const GGLfixed a = x; 94dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project const int32_t lz = gglClz(x); 95dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project x = ggl_sqrt_reciproc_approx_tab[(a>>(28-lz))&0x7]; 96dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project const int32_t exp = lz - 16; 97dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (exp <= 0) x >>= -exp>>1; 98dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else x <<= (exp>>1) + (exp & 1); 99dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (exp & 1) { 100dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project x = gglMulx(x, ggl_sqrt_reciproc_approx_tab[0])>>1; 101dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 102dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // 2 Newton-Raphson iterations: x = x/2*(3-(a*x)*x) 103dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project x = gglMulx((x>>1),(0x30000 - gglMulx(gglMulx(a,x),x))); 104dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project x = gglMulx((x>>1),(0x30000 - gglMulx(gglMulx(a,x),x))); 105dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return x; 106dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 107dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 108dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source ProjectGGLfixed gglSqrtx(GGLfixed a) 109dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 110dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // Compute a full precision square-root (24 bits accuracy) 111dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project GGLfixed r = 0; 112dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project GGLfixed bit = 0x800000; 113dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int32_t bshift = 15; 114dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project do { 115dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project GGLfixed temp = bit + (r<<1); 116dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (bshift >= 8) temp <<= (bshift-8); 117dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else temp >>= (8-bshift); 118dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (a >= temp) { 119dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r += bit; 120dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project a -= temp; 121dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 122dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project bshift--; 123dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } while (bit>>=1); 124dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return r; 125dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 126dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 127dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// ------------------------------------------------------------------------ 128dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 129dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic const GGLfixed ggl_log_approx_tab[] = { 130dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // -ln(x)/ln(2) with x = N/16, N=[8...16] 131dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 0xFFFF, 0xd47f, 0xad96, 0x8a62, 0x6a3f, 0x4caf, 0x3151, 0x17d6, 0x0000 132dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}; 133dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 134dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic const GGLfixed ggl_alog_approx_tab[] = { // domain [0 - 1.0] 135dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 0xffff, 0xeac0, 0xd744, 0xc567, 0xb504, 0xa5fe, 0x9837, 0x8b95, 0x8000 136dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}; 137dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 138dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source ProjectGGLfixed gglPowx(GGLfixed x, GGLfixed y) 139dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 140dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // prerequisite: 0 <= x <= 1, and y >=0 141dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 142dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // pow(x,y) = 2^(y*log2(x)) 143dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // = 2^(y*log2(x*(2^exp)*(2^-exp)))) 144dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // = 2^(y*(log2(X)-exp)) 145dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // = 2^(log2(X)*y - y*exp) 146dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // = 2^( - (-log2(X)*y + y*exp) ) 147dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 148dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int32_t exp = gglClz(x) - 16; 149dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project GGLfixed f = x << exp; 150dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project x = (f & 0x0FFF)<<4; 151dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project f = (f >> 12) & 0x7; 152dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project GGLfixed p = gglMulAddx( 153dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ggl_log_approx_tab[f+1] - ggl_log_approx_tab[f], x, 154dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ggl_log_approx_tab[f]); 155dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project p = gglMulAddx(p, y, y*exp); 156dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project exp = gglFixedToIntFloor(p); 157dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (exp < 31) { 158dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project p = gglFracx(p); 159dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project x = (p & 0x1FFF)<<3; 160dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project p >>= 13; 161dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project p = gglMulAddx( 162dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ggl_alog_approx_tab[p+1] - ggl_alog_approx_tab[p], x, 163dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ggl_alog_approx_tab[p]); 164dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project p >>= exp; 165dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } else { 166dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project p = 0; 167dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 168dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return p; 169dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // ( powf((a*65536.0f), (b*65536.0f)) ) * 65536.0f; 170dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 171dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 172dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// ------------------------------------------------------------------------ 173dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 174dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectint32_t gglDivQ(GGLfixed n, GGLfixed d, int32_t i) 175dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 176dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project //int32_t r =int32_t((int64_t(n)<<i)/d); 177dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project const int32_t ds = n^d; 178dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n<0) n = -n; 179dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (d<0) d = -d; 180dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int nd = gglClz(d) - gglClz(n); 181dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project i += nd + 1; 182dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (nd > 0) d <<= nd; 183dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n <<= -nd; 184dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project uint32_t q = 0; 185dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 186dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int j = i & 7; 187dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project i >>= 3; 188dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 189dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // gcc deals with the code below pretty well. 190dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // we get 3.75 cycles per bit in the main loop 191dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // and 8 cycles per bit in the termination loop 192dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (ggl_likely(i)) { 193dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n -= d; 194dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project do { 195dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project q <<= 8; 196dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n>=0) q |= 128; 197dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n += d; 198dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n = n*2 - d; 199dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n>=0) q |= 64; 200dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n += d; 201dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n = n*2 - d; 202dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n>=0) q |= 32; 203dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n += d; 204dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n = n*2 - d; 205dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n>=0) q |= 16; 206dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n += d; 207dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n = n*2 - d; 208dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n>=0) q |= 8; 209dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n += d; 210dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n = n*2 - d; 211dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n>=0) q |= 4; 212dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n += d; 213dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n = n*2 - d; 214dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n>=0) q |= 2; 215dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n += d; 216dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n = n*2 - d; 217dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n>=0) q |= 1; 218dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n += d; 219dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 220dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (--i == 0) 221dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project goto finish; 222dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 223dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n = n*2 - d; 224dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } while(true); 225dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project do { 226dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project q <<= 1; 227dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n = n*2 - d; 228dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n>=0) q |= 1; 229dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n += d; 230dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project finish: ; 231dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } while (j--); 232dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return (ds<0) ? -q : q; 233dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 234dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 235dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project n -= d; 236dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (n>=0) q |= 1; 237dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else n += d; 238dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project j--; 239dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project goto finish; 240dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 241dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 242dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// ------------------------------------------------------------------------ 243dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 244dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// assumes that the int32_t values of a, b, and c are all positive 245dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// use when both a and b are larger than c 246dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 247dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projecttemplate <typename T> 248dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic inline void swap(T& a, T& b) { 249dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project T t(a); 250dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project a = b; 251dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project b = t; 252dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 253dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 254dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic __attribute__((noinline)) 255dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectint32_t slow_muldiv(uint32_t a, uint32_t b, uint32_t c) 256dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 257dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // first we compute a*b as a 64-bit integer 258dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // (GCC generates umull with the code below) 259dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project uint64_t ab = uint64_t(a)*b; 260dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project uint32_t hi = ab>>32; 261dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project uint32_t lo = ab; 262dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project uint32_t result; 263dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 264dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // now perform the division 265dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (hi >= c) { 266dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project overflow: 267dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project result = 0x7fffffff; // basic overflow 268dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } else if (hi == 0) { 269dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project result = lo/c; // note: c can't be 0 270dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if ((result >> 31) != 0) // result must fit in 31 bits 271dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project goto overflow; 272dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } else { 273dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project uint32_t r = hi; 274dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int bits = 31; 275dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project result = 0; 276dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project do { 277dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r = (r << 1) | (lo >> 31); 278dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project lo <<= 1; 279dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project result <<= 1; 280dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (r >= c) { 281dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r -= c; 282dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project result |= 1; 283dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 284dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } while (bits--); 285dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 286dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return int32_t(result); 287dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 288dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 289dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// assumes a >= 0 and c >= b >= 0 290dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectstatic inline 291dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectint32_t quick_muldiv(int32_t a, int32_t b, int32_t c) 292dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 293dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int32_t r = 0, q = 0, i; 294dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int leading = gglClz(a); 295dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project i = 32 - leading; 296dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project a <<= leading; 297dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project do { 298dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r <<= 1; 299dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (a < 0) 300dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r += b; 301dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project a <<= 1; 302dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project q <<= 1; 303dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (r >= c) { 304dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r -= c; 305dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project q++; 306dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 307dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project asm(""::); // gcc generates better code this way 308dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (r >= c) { 309dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project r -= c; 310dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project q++; 311dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 312dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 313dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project while (--i); 314dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return q; 315dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 316dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 317dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// this function computes a*b/c with 64-bit intermediate accuracy 318dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// overflows (e.g. division by 0) are handled and return INT_MAX 319dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 320dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectint32_t gglMulDivi(int32_t a, int32_t b, int32_t c) 321dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 322dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int32_t result; 323dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project int32_t sign = a^b^c; 324dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 325dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (a < 0) a = -a; 326dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (b < 0) b = -b; 327dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (c < 0) c = -c; 328dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 329dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (a < b) { 330dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project swap(a, b); 331dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project } 332dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 333dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (b <= c) result = quick_muldiv(a, b, c); 334dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project else result = slow_muldiv((uint32_t)a, (uint32_t)b, (uint32_t)c); 335dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 336dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project if (sign < 0) 337dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project result = -result; 338dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 339dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project return result; 340dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project} 341