1 /* 2 * Written by Wilco Dijkstra, 1996. 3 * Refer to NOTICE file at the root of git project. 4 * 5 * Minor modifications in code style for WebRTC, 2012. 6 */ 7 8 #include "signal_processing_library.h" 9 10 /* 11 * Algorithm: 12 * Successive approximation of the equation (root + delta) ^ 2 = N 13 * until delta < 1. If delta < 1 we have the integer part of SQRT (N). 14 * Use delta = 2^i for i = 15 .. 0. 15 * 16 * Output precision is 16 bits. Note for large input values (close to 17 * 0x7FFFFFFF), bit 15 (the highest bit of the low 16-bit half word) 18 * contains the MSB information (a non-sign value). Do with caution 19 * if you need to cast the output to int16_t type. 20 * 21 * If the input value is negative, it returns 0. 22 */ 23 24 #define WEBRTC_SPL_SQRT_ITER(N) \ 25 try1 = root + (1 << (N)); \ 26 if (value >= try1 << (N)) \ 27 { \ 28 value -= try1 << (N); \ 29 root |= 2 << (N); \ 30 } 31 32 int32_t WebRtcSpl_SqrtFloor(int32_t value) 33 { 34 int32_t root = 0, try1; 35 36 WEBRTC_SPL_SQRT_ITER (15); 37 WEBRTC_SPL_SQRT_ITER (14); 38 WEBRTC_SPL_SQRT_ITER (13); 39 WEBRTC_SPL_SQRT_ITER (12); 40 WEBRTC_SPL_SQRT_ITER (11); 41 WEBRTC_SPL_SQRT_ITER (10); 42 WEBRTC_SPL_SQRT_ITER ( 9); 43 WEBRTC_SPL_SQRT_ITER ( 8); 44 WEBRTC_SPL_SQRT_ITER ( 7); 45 WEBRTC_SPL_SQRT_ITER ( 6); 46 WEBRTC_SPL_SQRT_ITER ( 5); 47 WEBRTC_SPL_SQRT_ITER ( 4); 48 WEBRTC_SPL_SQRT_ITER ( 3); 49 WEBRTC_SPL_SQRT_ITER ( 2); 50 WEBRTC_SPL_SQRT_ITER ( 1); 51 WEBRTC_SPL_SQRT_ITER ( 0); 52 53 return root >> 1; 54 } 55
