andrew@webrtc.org | a7b57da | 2012-10-22 18:19:23 +0000 | [diff] [blame] | 1 | /* |
andrew@webrtc.org | cff84ec | 2013-05-05 18:54:10 +0000 | [diff] [blame] | 2 | * Written by Wilco Dijkstra, 1996. The following email exchange establishes the |
| 3 | * license. |
andrew@webrtc.org | a7b57da | 2012-10-22 18:19:23 +0000 | [diff] [blame] | 4 | * |
andrew@webrtc.org | cff84ec | 2013-05-05 18:54:10 +0000 | [diff] [blame] | 5 | * From: Wilco Dijkstra <Wilco.Dijkstra@ntlworld.com> |
| 6 | * Date: Fri, Jun 24, 2011 at 3:20 AM |
| 7 | * Subject: Re: sqrt routine |
| 8 | * To: Kevin Ma <kma@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@google.com> |
| 17 | * To: <Wilco.Dijkstra@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 |
andrew@webrtc.org | a7b57da | 2012-10-22 18:19:23 +0000 | [diff] [blame] | 27 | */ |
| 28 | |
andrew@webrtc.org | cff84ec | 2013-05-05 18:54:10 +0000 | [diff] [blame] | 29 | // Minor modifications in code style for WebRTC, 2012. |
| 30 | |
pbos@webrtc.org | abf0cd8 | 2013-05-27 09:49:58 +0000 | [diff] [blame] | 31 | #include "webrtc/common_audio/signal_processing/include/signal_processing_library.h" |
andrew@webrtc.org | a7b57da | 2012-10-22 18:19:23 +0000 | [diff] [blame] | 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 | } |