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