1 /* ------------------------------------------------------------------ 2 * Copyright (C) 1998-2009 PacketVideo 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 13 * express or implied. 14 * See the License for the specific language governing permissions 15 * and limitations under the License. 16 * ------------------------------------------------------------------- 17 */ 18 /**************************************************************************************** 19 Portions of this file are derived from the following 3GPP standard: 20 21 3GPP TS 26.073 22 ANSI-C code for the Adaptive Multi-Rate (AMR) speech codec 23 Available from http://www.3gpp.org 24 25 (C) 2004, 3GPP Organizational Partners (ARIB, ATIS, CCSA, ETSI, TTA, TTC) 26 Permission to distribute, modify and use this file under the standard license 27 terms listed above has been obtained from the copyright holder. 28 ****************************************************************************************/ 29 /* 30 Pathname: ./audio/gsm-amr/c/src/inv_sqrt.c 31 32 ------------------------------------------------------------------------------ 33 REVISION HISTORY 34 35 Description: Put file into template. 36 37 Description: Synchronized file with UMTS version 3.2.0. Updated coding 38 template. Removed unnecessary include files. 39 40 Description: Replaced basic_op.h with the header files of the math functions 41 used in the file. 42 43 Description: Made the following changes per comments from Phase 2/3 review: 44 1. Defined one local variable per line. 45 2. Used "&=", ">>=", and "+=" in the code. 46 47 Description: Updated template. Changed function interface to pass in a 48 pointer to overflow flag into the function instead of using a 49 global flag. 50 51 Description: Removed inclusion of inv_sqrt.tab file. Changed array name 52 from "table" to "inv_sqrt_tbl" 53 54 Description: Removed math operations that were not needed as functions, 55 this because the numbers themselves will not saturate the 56 operators, so there is not need to check for saturation. 57 58 Description: Updated copyrigth year, according to code review comments. 59 60 Description: Replaced "int" and/or "char" with defined types. 61 Added proper casting (Word32) to some left shifting operations 62 63 Who: Date: 64 Description: 65 66 ------------------------------------------------------------------------------ 67 */ 68 69 /*---------------------------------------------------------------------------- 70 ; INCLUDES 71 ----------------------------------------------------------------------------*/ 72 #include "inv_sqrt.h" 73 #include "typedef.h" 74 #include "basic_op.h" 75 76 /*---------------------------------------------------------------------------- 77 ; MACROS 78 ; Define module specific macros here 79 ----------------------------------------------------------------------------*/ 80 81 82 /*---------------------------------------------------------------------------- 83 ; DEFINES 84 ; Include all pre-processor statements here. Include conditional 85 ; compile variables also. 86 ----------------------------------------------------------------------------*/ 87 88 89 /*---------------------------------------------------------------------------- 90 ; LOCAL FUNCTION DEFINITIONS 91 ; Function Prototype declaration 92 ----------------------------------------------------------------------------*/ 93 94 95 /*---------------------------------------------------------------------------- 96 ; LOCAL STORE/BUFFER/POINTER DEFINITIONS 97 ; Variable declaration - defined here and used outside this module 98 ----------------------------------------------------------------------------*/ 99 100 101 /* 102 ------------------------------------------------------------------------------ 103 FUNCTION NAME: Inv_sqrt 104 ------------------------------------------------------------------------------ 105 INPUT AND OUTPUT DEFINITIONS 106 107 Inputs: 108 L_x = input value (Word32) 109 pOverflow = pointer to overflow flag 110 111 Outputs: 112 pOverflow -> if the Inv_sqrt operation resulted in an overflow. 113 114 Returns: 115 L_y = inverse squareroot of L_x (Word32) 116 117 Global Variables Used: 118 None. 119 120 Local Variables Needed: 121 None. 122 123 ------------------------------------------------------------------------------ 124 FUNCTION DESCRIPTION 125 126 This function computes 1/sqrt(L_x), where L_x is positive. 127 If L_x is negative or zero, the result is 1 (3fff ffff). 128 129 The function 1/sqrt(L_x) is approximated by a table and linear 130 interpolation. The inverse square root is computed using the 131 following steps: 132 1- Normalization of L_x. 133 2- If (30-exponent) is even then shift right once. 134 3- exponent = (30-exponent)/2 +1 135 4- i = bit25-b31 of L_x; 16<=i<=63 because of normalization. 136 5- a = bit10-b24 137 6- i -=16 138 7- L_y = table[i]<<16 - (table[i] - table[i+1]) * a * 2 139 8- L_y >>= exponent 140 141 ------------------------------------------------------------------------------ 142 REQUIREMENTS 143 144 None. 145 146 ------------------------------------------------------------------------------ 147 REFERENCES 148 149 inv_sqrt.c, UMTS GSM AMR speech codec, R99 - Version 3.2.0, March 2, 2001 150 151 ------------------------------------------------------------------------------ 152 PSEUDO-CODE 153 154 Word32 Inv_sqrt ( // (o) : output value 155 Word32 L_x // (i) : input value 156 ) 157 { 158 Word16 exp, i, a, tmp; 159 Word32 L_y; 160 161 * The reference ETSI code uses a global Overflow flag. In the actual 162 * implementation a pointer to the overflow flag is passed into the function. 163 * This pointer is in turn passed into the basic math functions such as add(), 164 * L_shl(), L_shr(), sub() called by this module. 165 166 if (L_x <= (Word32) 0) 167 return ((Word32) 0x3fffffffL); 168 169 exp = norm_l (L_x); 170 L_x = L_shl (L_x, exp); // L_x is normalize 171 172 exp = sub (30, exp); 173 174 if ((exp & 1) == 0) // If exponent even -> shift right 175 { 176 L_x = L_shr (L_x, 1); 177 } 178 exp = shr (exp, 1); 179 exp = add (exp, 1); 180 181 L_x = L_shr (L_x, 9); 182 i = extract_h (L_x); // Extract b25-b31 183 L_x = L_shr (L_x, 1); 184 a = extract_l (L_x); // Extract b10-b24 185 a = a & (Word16) 0x7fff; 186 187 i = sub (i, 16); 188 189 L_y = L_deposit_h (table[i]); // table[i] << 16 190 tmp = sub (table[i], table[i + 1]); // table[i] - table[i+1]) 191 L_y = L_msu (L_y, tmp, a); // L_y -= tmp*a*2 192 193 L_y = L_shr (L_y, exp); // denormalization 194 195 return (L_y); 196 } 197 198 ------------------------------------------------------------------------------ 199 RESOURCES USED [optional] 200 201 When the code is written for a specific target processor the 202 the resources used should be documented below. 203 204 HEAP MEMORY USED: x bytes 205 206 STACK MEMORY USED: x bytes 207 208 CLOCK CYCLES: (cycle count equation for this function) + (variable 209 used to represent cycle count for each subroutine 210 called) 211 where: (cycle count variable) = cycle count for [subroutine 212 name] 213 214 ------------------------------------------------------------------------------ 215 CAUTION [optional] 216 [State any special notes, constraints or cautions for users of this function] 217 218 ------------------------------------------------------------------------------ 219 */ 220 221 Word32 Inv_sqrt( /* (o) : output value */ 222 Word32 L_x, /* (i) : input value */ 223 Flag * pOverflow /* (i) : pointer to overflow flag */ 224 ) 225 { 226 Word16 exp; 227 Word16 i; 228 Word16 a; 229 Word16 tmp; 230 Word32 L_y; 231 OSCL_UNUSED_ARG(pOverflow); 232 233 if (L_x <= (Word32) 0) 234 { 235 return ((Word32) 0x3fffffffL); 236 } 237 238 exp = norm_l(L_x); 239 L_x <<= exp; /* L_x is normalize */ 240 241 exp = 30 - exp; 242 243 if ((exp & 1) == 0) /* If exponent even -> shift right */ 244 { 245 L_x >>= 1; 246 } 247 exp >>= 1; 248 exp += 1; 249 250 L_x >>= 9; 251 i = (Word16)(L_x >> 16); /* Extract b25-b31 */ 252 a = (Word16)(L_x >> 1); /* Extract b10-b24 */ 253 a &= (Word16) 0x7fff; 254 255 i -= 16; 256 257 L_y = (Word32)inv_sqrt_tbl[i] << 16; /* inv_sqrt_tbl[i] << 16 */ 258 259 /* inv_sqrt_tbl[i] - inv_sqrt_tbl[i+1]) */ 260 tmp = inv_sqrt_tbl[i] - inv_sqrt_tbl[i + 1]; 261 /* always a positive number less than 200 */ 262 263 L_y -= ((Word32)tmp * a) << 1; /* L_y -= tmp*a*2 */ 264 /* always a positive minus a small negative number */ 265 266 L_y >>= exp; /* denormalization, exp always 0< exp < 31 */ 267 268 return (L_y); 269 } 270 271