156c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks/*---------------------------------------------------------------------------- 256c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * 356c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * File: 456c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * eas_flog2.c 556c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * 656c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * Contents and purpose: 756c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * Fixed point square root 856c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * 956c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * 1056c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * Copyright (c) 2006 Sonic Network Inc. 117df30109963092559d3760c0661a020f9daf1030The Android Open Source Project 127df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 137df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * you may not use this file except in compliance with the License. 147df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * You may obtain a copy of the License at 157df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * 167df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 177df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * 187df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 197df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 207df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 217df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * See the License for the specific language governing permissions and 227df30109963092559d3760c0661a020f9daf1030The Android Open Source Project * limitations under the License. 2356c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * 2456c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks *---------------------------------------------------------------------------- 2556c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * Revision Control: 2656c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * $Revision$ 2756c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * $Date$ 2856c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks *---------------------------------------------------------------------------- 2956c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks*/ 3056c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 3156c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks#include "eas_types.h" 3256c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks#include "eas_math.h" 3356c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 3456c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks#define MANTISSA_SHIFT 27 3556c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks#define MANTISSA_MASK 0x0000000f 3656c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks#define MANTISSA_LSB_SHIFT 7 3756c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks#define MANTISSA_LSB_MASK 0x000fffff 3856c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks#define LOG_EXPONENT_SHIFT 10 3956c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks#define INTERPOLATION_SHIFT 20 4056c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks#define MAX_NEGATIVE (-2147483647-1) 4156c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 4256c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks/* log lookup table */ 4356c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparksstatic const EAS_U16 eas_log2_table[] = 4456c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks{ 4556c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 0, 90, 174, 254, 330, 402, 470, 536, 4656c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 599, 659, 717, 773, 827, 879, 929, 977, 4756c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 1024 4856c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks}; 4956c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 5056c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks/*---------------------------------------------------------------------------- 5156c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * EAS_flog2() 5256c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks *---------------------------------------------------------------------------- 5356c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * Purpose: 5456c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * Calculates the log2 of a 32-bit fixed point value 5556c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * 5656c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * Inputs: 5756c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * n = value of interest 5856c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * 5956c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * Outputs: 6056c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * returns the log2 of n 6156c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks * 6256c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks *---------------------------------------------------------------------------- 6356c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks*/ 6456c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave SparksEAS_I32 EAS_flog2 (EAS_U32 n) 6556c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks{ 6656c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks EAS_U32 exp; 6756c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks EAS_U32 interp; 6856c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 6956c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks /* check for error condition */ 7056c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks if (n == 0) 7156c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks return MAX_NEGATIVE; 7256c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 7356c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks /* find exponent */ 7456c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks for (exp = 31; exp > 0; exp--) 7556c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks { 7656c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks /* shift until we get a 1 bit in bit 31 */ 7756c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks if ((n & (EAS_U32) MAX_NEGATIVE) != 0) 7856c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks break; 7956c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks n <<= 1; 8056c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks } 8156c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks /*lint -e{701} use shift for performance */ 8256c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks exp <<= LOG_EXPONENT_SHIFT; 8356c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 8456c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks /* get the least significant bits for interpolation */ 8556c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks interp = (n >> MANTISSA_LSB_SHIFT) & MANTISSA_LSB_MASK; 8656c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 8756c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks /* get the most significant bits for mantissa lookup */ 8856c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks n = (n >> MANTISSA_SHIFT) & MANTISSA_MASK; 8956c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 9056c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks /* interpolate mantissa */ 9156c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks interp = ((eas_log2_table[n+1] - eas_log2_table[n]) * interp) >> INTERPOLATION_SHIFT; 9256c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks exp += eas_log2_table[n] + interp; 9356c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 9456c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks return (EAS_I32) exp; 9556c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks} 9656c99cd2c2c1e6ab038dac5fced5b92ccf11ff6cDave Sparks 97