<p>Harald Welte <strong>merged</strong> this change.</p><p><a href="https://gerrit.osmocom.org/9476">View Change</a></p><div style="white-space:pre-wrap">Approvals:
Jenkins Builder: Verified
Harald Welte: Looks good to me, approved
</div><pre style="font-family: monospace,monospace; white-space: pre-wrap;">Add osmo_isqrt32() to compute 32bit integer square root<br><br>Change-Id: I2b96db6e037e72e92317fec874877e473a1cf909<br>---<br>M include/osmocom/core/utils.h<br>M src/utils.c<br>M tests/utils/utils_test.c<br>M tests/utils/utils_test.ok<br>4 files changed, 66 insertions(+), 0 deletions(-)<br><br></pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;"><span>diff --git a/include/osmocom/core/utils.h b/include/osmocom/core/utils.h</span><br><span>index 8928f68..cd22dfb 100644</span><br><span>--- a/include/osmocom/core/utils.h</span><br><span>+++ b/include/osmocom/core/utils.h</span><br><span>@@ -128,4 +128,6 @@</span><br><span> const char *osmo_quote_str(const char *str, int in_len);</span><br><span> const char *osmo_quote_str_buf(const char *str, int in_len, char *buf, size_t bufsize);</span><br><span> </span><br><span style="color: hsl(120, 100%, 40%);">+uint32_t osmo_isqrt32(uint32_t x);</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span> /*! @} */</span><br><span>diff --git a/src/utils.c b/src/utils.c</span><br><span>index 32ea87c..ea0bbde 100644</span><br><span>--- a/src/utils.c</span><br><span>+++ b/src/utils.c</span><br><span>@@ -592,4 +592,44 @@</span><br><span> return osmo_quote_str_buf(str, in_len, namebuf, sizeof(namebuf));</span><br><span> }</span><br><span> </span><br><span style="color: hsl(120, 100%, 40%);">+/*! perform an integer square root operation on unsigned 32bit integer.</span><br><span style="color: hsl(120, 100%, 40%);">+ * This implementation is taken from "Hacker's Delight" Figure 11-1 "Integer square root, Newton's</span><br><span style="color: hsl(120, 100%, 40%);">+ * method", which can also be found at http://www.hackersdelight.org/hdcodetxt/isqrt.c.txt */</span><br><span style="color: hsl(120, 100%, 40%);">+uint32_t osmo_isqrt32(uint32_t x)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ uint32_t x1;</span><br><span style="color: hsl(120, 100%, 40%);">+ int s, g0, g1;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ if (x <= 1)</span><br><span style="color: hsl(120, 100%, 40%);">+ return x;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ s = 1;</span><br><span style="color: hsl(120, 100%, 40%);">+ x1 = x - 1;</span><br><span style="color: hsl(120, 100%, 40%);">+ if (x1 > 0xffff) {</span><br><span style="color: hsl(120, 100%, 40%);">+ s = s + 8;</span><br><span style="color: hsl(120, 100%, 40%);">+ x1 = x1 >> 16;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ if (x1 > 0xff) {</span><br><span style="color: hsl(120, 100%, 40%);">+ s = s + 4;</span><br><span style="color: hsl(120, 100%, 40%);">+ x1 = x1 >> 8;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ if (x1 > 0xf) {</span><br><span style="color: hsl(120, 100%, 40%);">+ s = s + 2;</span><br><span style="color: hsl(120, 100%, 40%);">+ x1 = x1 >> 4;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ if (x1 > 0x3) {</span><br><span style="color: hsl(120, 100%, 40%);">+ s = s + 1;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ g0 = 1 << s; /* g0 = 2**s */</span><br><span style="color: hsl(120, 100%, 40%);">+ g1 = (g0 + (x >> s)) >> 1; /* g1 = (g0 + x/g0)/2 */</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ /* converges after four to five divisions for arguments up to 16,785,407 */</span><br><span style="color: hsl(120, 100%, 40%);">+ while (g1 < g0) {</span><br><span style="color: hsl(120, 100%, 40%);">+ g0 = g1;</span><br><span style="color: hsl(120, 100%, 40%);">+ g1 = (g0 + (x/g0)) >> 1;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ return g0;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span> /*! @} */</span><br><span>diff --git a/tests/utils/utils_test.c b/tests/utils/utils_test.c</span><br><span>index a124352..cb4e476 100644</span><br><span>--- a/tests/utils/utils_test.c</span><br><span>+++ b/tests/utils/utils_test.c</span><br><span>@@ -27,6 +27,7 @@</span><br><span> </span><br><span> #include <stdio.h></span><br><span> #include <ctype.h></span><br><span style="color: hsl(120, 100%, 40%);">+#include <time.h></span><br><span> </span><br><span> static void hexdump_test(void)</span><br><span> {</span><br><span>@@ -425,6 +426,26 @@</span><br><span> printf("'%s'\n", osmo_quote_str_buf(NULL, -1, out_buf, 10));</span><br><span> }</span><br><span> </span><br><span style="color: hsl(120, 100%, 40%);">+static void isqrt_test(void)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ int i;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ printf("\nTesting integer square-root\n");</span><br><span style="color: hsl(120, 100%, 40%);">+ srand(time(NULL));</span><br><span style="color: hsl(120, 100%, 40%);">+ for (i = 0; i < 1024; i++) {</span><br><span style="color: hsl(120, 100%, 40%);">+ uint16_t x;</span><br><span style="color: hsl(120, 100%, 40%);">+ uint32_t r = rand();</span><br><span style="color: hsl(120, 100%, 40%);">+ if (RAND_MAX < UINT16_MAX)</span><br><span style="color: hsl(120, 100%, 40%);">+ x = r * (UINT16_MAX/RAND_MAX);</span><br><span style="color: hsl(120, 100%, 40%);">+ else</span><br><span style="color: hsl(120, 100%, 40%);">+ x = r;</span><br><span style="color: hsl(120, 100%, 40%);">+ uint32_t sq = x*x;</span><br><span style="color: hsl(120, 100%, 40%);">+ uint32_t y = osmo_isqrt32(sq);</span><br><span style="color: hsl(120, 100%, 40%);">+ if (y != x)</span><br><span style="color: hsl(120, 100%, 40%);">+ printf("ERROR: x=%u, sq=%u, osmo_isqrt(%u) = %u\n", x, sq, sq, y);</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span> int main(int argc, char **argv)</span><br><span> {</span><br><span> static const struct log_info log_info = {};</span><br><span>@@ -437,5 +458,6 @@</span><br><span> bcd_test();</span><br><span> str_escape_test();</span><br><span> str_quote_test();</span><br><span style="color: hsl(120, 100%, 40%);">+ isqrt_test();</span><br><span> return 0;</span><br><span> }</span><br><span>diff --git a/tests/utils/utils_test.ok b/tests/utils/utils_test.ok</span><br><span>index 5bc3896..ea9216f 100644</span><br><span>--- a/tests/utils/utils_test.ok</span><br><span>+++ b/tests/utils/utils_test.ok</span><br><span>@@ -137,3 +137,5 @@</span><br><span> '<buf-too-small>'</span><br><span> - NULL string becomes a "NULL" literal:</span><br><span> 'NULL'</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+Testing integer square-root</span><br><span></span><br></pre><p>To view, visit <a href="https://gerrit.osmocom.org/9476">change 9476</a>. To unsubscribe, or for help writing mail filters, visit <a href="https://gerrit.osmocom.org/settings">settings</a>.</p><div itemscope itemtype="http://schema.org/EmailMessage"><div itemscope itemprop="action" itemtype="http://schema.org/ViewAction"><link itemprop="url" href="https://gerrit.osmocom.org/9476"/><meta itemprop="name" content="View Change"/></div></div>
<div style="display:none"> Gerrit-Project: libosmocore </div>
<div style="display:none"> Gerrit-Branch: master </div>
<div style="display:none"> Gerrit-MessageType: merged </div>
<div style="display:none"> Gerrit-Change-Id: I2b96db6e037e72e92317fec874877e473a1cf909 </div>
<div style="display:none"> Gerrit-Change-Number: 9476 </div>
<div style="display:none"> Gerrit-PatchSet: 1 </div>
<div style="display:none"> Gerrit-Owner: Harald Welte <laforge@gnumonks.org> </div>
<div style="display:none"> Gerrit-Reviewer: Harald Welte <laforge@gnumonks.org> </div>
<div style="display:none"> Gerrit-Reviewer: Jenkins Builder </div>