This is merely a historical archive of years 2008-2021, before the migration to mailman3.
A maintained and still updated list archive can be found at https://lists.osmocom.org/hyperkitty/list/gerrit-log@lists.osmocom.org/.
Harald Welte gerrit-no-reply at lists.osmocom.orgHarald Welte has uploaded this change for review. ( https://gerrit.osmocom.org/9476 Change subject: Add osmo_isqrt32() to compute 32bit integer square root ...................................................................... Add osmo_isqrt32() to compute 32bit integer square root Change-Id: I2b96db6e037e72e92317fec874877e473a1cf909 --- M include/osmocom/core/utils.h M src/utils.c M tests/utils/utils_test.c M tests/utils/utils_test.ok 4 files changed, 66 insertions(+), 0 deletions(-) git pull ssh://gerrit.osmocom.org:29418/libosmocore refs/changes/76/9476/1 diff --git a/include/osmocom/core/utils.h b/include/osmocom/core/utils.h index 8928f68..cd22dfb 100644 --- a/include/osmocom/core/utils.h +++ b/include/osmocom/core/utils.h @@ -128,4 +128,6 @@ const char *osmo_quote_str(const char *str, int in_len); const char *osmo_quote_str_buf(const char *str, int in_len, char *buf, size_t bufsize); +uint32_t osmo_isqrt32(uint32_t x); + /*! @} */ diff --git a/src/utils.c b/src/utils.c index 32ea87c..ea0bbde 100644 --- a/src/utils.c +++ b/src/utils.c @@ -592,4 +592,44 @@ return osmo_quote_str_buf(str, in_len, namebuf, sizeof(namebuf)); } +/*! perform an integer square root operation on unsigned 32bit integer. + * This implementation is taken from "Hacker's Delight" Figure 11-1 "Integer square root, Newton's + * method", which can also be found at http://www.hackersdelight.org/hdcodetxt/isqrt.c.txt */ +uint32_t osmo_isqrt32(uint32_t x) +{ + uint32_t x1; + int s, g0, g1; + + if (x <= 1) + return x; + + s = 1; + x1 = x - 1; + if (x1 > 0xffff) { + s = s + 8; + x1 = x1 >> 16; + } + if (x1 > 0xff) { + s = s + 4; + x1 = x1 >> 8; + } + if (x1 > 0xf) { + s = s + 2; + x1 = x1 >> 4; + } + if (x1 > 0x3) { + s = s + 1; + } + + g0 = 1 << s; /* g0 = 2**s */ + g1 = (g0 + (x >> s)) >> 1; /* g1 = (g0 + x/g0)/2 */ + + /* converges after four to five divisions for arguments up to 16,785,407 */ + while (g1 < g0) { + g0 = g1; + g1 = (g0 + (x/g0)) >> 1; + } + return g0; +} + /*! @} */ diff --git a/tests/utils/utils_test.c b/tests/utils/utils_test.c index a124352..cb4e476 100644 --- a/tests/utils/utils_test.c +++ b/tests/utils/utils_test.c @@ -27,6 +27,7 @@ #include <stdio.h> #include <ctype.h> +#include <time.h> static void hexdump_test(void) { @@ -425,6 +426,26 @@ printf("'%s'\n", osmo_quote_str_buf(NULL, -1, out_buf, 10)); } +static void isqrt_test(void) +{ + int i; + + printf("\nTesting integer square-root\n"); + srand(time(NULL)); + for (i = 0; i < 1024; i++) { + uint16_t x; + uint32_t r = rand(); + if (RAND_MAX < UINT16_MAX) + x = r * (UINT16_MAX/RAND_MAX); + else + x = r; + uint32_t sq = x*x; + uint32_t y = osmo_isqrt32(sq); + if (y != x) + printf("ERROR: x=%u, sq=%u, osmo_isqrt(%u) = %u\n", x, sq, sq, y); + } +} + int main(int argc, char **argv) { static const struct log_info log_info = {}; @@ -437,5 +458,6 @@ bcd_test(); str_escape_test(); str_quote_test(); + isqrt_test(); return 0; } diff --git a/tests/utils/utils_test.ok b/tests/utils/utils_test.ok index 5bc3896..ea9216f 100644 --- a/tests/utils/utils_test.ok +++ b/tests/utils/utils_test.ok @@ -137,3 +137,5 @@ '<buf-too-small>' - NULL string becomes a "NULL" literal: 'NULL' + +Testing integer square-root -- To view, visit https://gerrit.osmocom.org/9476 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmocore Gerrit-Branch: master Gerrit-MessageType: newchange Gerrit-Change-Id: I2b96db6e037e72e92317fec874877e473a1cf909 Gerrit-Change-Number: 9476 Gerrit-PatchSet: 1 Gerrit-Owner: Harald Welte <laforge at gnumonks.org> -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.osmocom.org/pipermail/gerrit-log/attachments/20180606/f195184d/attachment.htm>