1 /* 2 * Written by Wilco Dijkstra, 1996. The following email exchange establishes the 3 * license. 4 * 5 * From: Wilco Dijkstra <Wilco.Dijkstra (at) ntlworld.com> 6 * Date: Fri, Jun 24, 2011 at 3:20 AM 7 * Subject: Re: sqrt routine 8 * To: Kevin Ma <kma (at) google.com> 9 * Hi Kevin, 10 * Thanks for asking. Those routines are public domain (originally posted to 11 * comp.sys.arm a long time ago), so you can use them freely for any purpose. 12 * Cheers, 13 * Wilco 14 * 15 * ----- Original Message ----- 16 * From: "Kevin Ma" <kma (at) google.com> 17 * To: <Wilco.Dijkstra (at) ntlworld.com> 18 * Sent: Thursday, June 23, 2011 11:44 PM 19 * Subject: Fwd: sqrt routine 20 * Hi Wilco, 21 * I saw your sqrt routine from several web sites, including 22 * http://www.finesse.demon.co.uk/steven/sqrt.html. 23 * Just wonder if there's any copyright information with your Successive 24 * approximation routines, or if I can freely use it for any purpose. 25 * Thanks. 26 * Kevin 27 */ 28 29 // Minor modifications in code style for WebRTC, 2012. 30 31 #include "webrtc/common_audio/signal_processing/include/signal_processing_library.h" 32 33 /* 34 * Algorithm: 35 * Successive approximation of the equation (root + delta) ^ 2 = N 36 * until delta < 1. If delta < 1 we have the integer part of SQRT (N). 37 * Use delta = 2^i for i = 15 .. 0. 38 * 39 * Output precision is 16 bits. Note for large input values (close to 40 * 0x7FFFFFFF), bit 15 (the highest bit of the low 16-bit half word) 41 * contains the MSB information (a non-sign value). Do with caution 42 * if you need to cast the output to int16_t type. 43 * 44 * If the input value is negative, it returns 0. 45 */ 46 47 #define WEBRTC_SPL_SQRT_ITER(N) \ 48 try1 = root + (1 << (N)); \ 49 if (value >= try1 << (N)) \ 50 { \ 51 value -= try1 << (N); \ 52 root |= 2 << (N); \ 53 } 54 55 int32_t WebRtcSpl_SqrtFloor(int32_t value) 56 { 57 int32_t root = 0, try1; 58 59 WEBRTC_SPL_SQRT_ITER (15); 60 WEBRTC_SPL_SQRT_ITER (14); 61 WEBRTC_SPL_SQRT_ITER (13); 62 WEBRTC_SPL_SQRT_ITER (12); 63 WEBRTC_SPL_SQRT_ITER (11); 64 WEBRTC_SPL_SQRT_ITER (10); 65 WEBRTC_SPL_SQRT_ITER ( 9); 66 WEBRTC_SPL_SQRT_ITER ( 8); 67 WEBRTC_SPL_SQRT_ITER ( 7); 68 WEBRTC_SPL_SQRT_ITER ( 6); 69 WEBRTC_SPL_SQRT_ITER ( 5); 70 WEBRTC_SPL_SQRT_ITER ( 4); 71 WEBRTC_SPL_SQRT_ITER ( 3); 72 WEBRTC_SPL_SQRT_ITER ( 2); 73 WEBRTC_SPL_SQRT_ITER ( 1); 74 WEBRTC_SPL_SQRT_ITER ( 0); 75 76 return root >> 1; 77 } 78
