On Sun, Mar 29, 2020 at 5:00 AM Jeffrey Walton <noloa...@gmail.com> wrote:
>
> It looks like test-bitrotate.c is missing test cases. It is missing
> the 32-bit rotl and rotr of 0-bits.
>
> The 0-bit rotate should tickle undefined behavior.
>
> If you want to clear the undefined behavior, then use this code. It is
> recognized by Clang, GCC, ICC. It will be compiled down to a single
> instruction on platforms like IA-32. I can find the mailing list
> messages for a citation, if needed.
Cleared on the bit rotate branch at
https://github.com/noloader/gnulib/tree/bitrotate.
The patch is attached.
Jeff
diff --git a/lib/bitrotate.h b/lib/bitrotate.h
index 59827e274..cafa1d99e 100644
--- a/lib/bitrotate.h
+++ b/lib/bitrotate.h
@@ -15,6 +15,7 @@
along with this program. If not, see <https://www.gnu.org/licenses/>. */
/* Written by Simon Josefsson <si...@josefsson.org>, 2008. */
+/* Updated for 128-bit types by Jeffrey Walton <noloa...@gmail.com>, 2020 */
#ifndef _GL_BITROTATE_H
#define _GL_BITROTATE_H
@@ -33,40 +34,40 @@ _GL_INLINE_HEADER_BEGIN
#ifdef UINT64_MAX
/* Given an unsigned 64-bit argument X, return the value corresponding
- to rotating the bits N steps to the left. N must be between 1 and
+ to rotating the bits N steps to the left. N must be between 0 and
63 inclusive. */
BITROTATE_INLINE uint64_t
rotl64 (uint64_t x, int n)
{
- return ((x << n) | (x >> (64 - n))) & UINT64_MAX;
+ return ((x << n) | (x >> (-n&63)));
}
/* Given an unsigned 64-bit argument X, return the value corresponding
- to rotating the bits N steps to the right. N must be between 1 to
+ to rotating the bits N steps to the right. N must be between 0 to
63 inclusive.*/
BITROTATE_INLINE uint64_t
rotr64 (uint64_t x, int n)
{
- return ((x >> n) | (x << (64 - n))) & UINT64_MAX;
+ return ((x >> n) | (x << (-n&63)));
}
#endif
/* Given an unsigned 32-bit argument X, return the value corresponding
- to rotating the bits N steps to the left. N must be between 1 and
+ to rotating the bits N steps to the left. N must be between 0 and
31 inclusive. */
BITROTATE_INLINE uint32_t
rotl32 (uint32_t x, int n)
{
- return ((x << n) | (x >> (32 - n))) & UINT32_MAX;
+ return ((x << n) | (x >> (-n&31)));
}
/* Given an unsigned 32-bit argument X, return the value corresponding
- to rotating the bits N steps to the right. N must be between 1 to
+ to rotating the bits N steps to the right. N must be between 0 to
31 inclusive.*/
BITROTATE_INLINE uint32_t
rotr32 (uint32_t x, int n)
{
- return ((x >> n) | (x << (32 - n))) & UINT32_MAX;
+ return ((x >> n) | (x << (-n&31)));
}
/* Given a size_t argument X, return the value corresponding
@@ -75,7 +76,8 @@ rotr32 (uint32_t x, int n)
BITROTATE_INLINE size_t
rotl_sz (size_t x, int n)
{
- return ((x << n) | (x >> ((CHAR_BIT * sizeof x) - n))) & SIZE_MAX;
+ enum {mask = (CHAR_BIT * sizeof x) -1};
+ return ((x << n) | (x >> (-n&mask)));
}
/* Given a size_t argument X, return the value corresponding
@@ -84,54 +86,68 @@ rotl_sz (size_t x, int n)
BITROTATE_INLINE size_t
rotr_sz (size_t x, int n)
{
- return ((x >> n) | (x << ((CHAR_BIT * sizeof x) - n))) & SIZE_MAX;
+ enum {mask = (CHAR_BIT * sizeof x) -1};
+ return ((x >> n) | (x << (-n&mask)));
}
/* Given an unsigned 16-bit argument X, return the value corresponding
- to rotating the bits N steps to the left. N must be between 1 to
- 15 inclusive, but on most relevant targets N can also be 0 and 16
- because 'int' is at least 32 bits and the arguments must widen
- before shifting. */
+ to rotating the bits N steps to the left. N must be between 0 to
+ 15 inclusive. */
BITROTATE_INLINE uint16_t
rotl16 (uint16_t x, int n)
{
- return (((unsigned int) x << n) | ((unsigned int) x >> (16 - n)))
- & UINT16_MAX;
+ return ((x << n) | (x >> (-n&15)));
}
/* Given an unsigned 16-bit argument X, return the value corresponding
- to rotating the bits N steps to the right. N must be in 1 to 15
- inclusive, but on most relevant targets N can also be 0 and 16
- because 'int' is at least 32 bits and the arguments must widen
- before shifting. */
+ to rotating the bits N steps to the right. N must be between 0 to
+ to 15 inclusive. */
BITROTATE_INLINE uint16_t
rotr16 (uint16_t x, int n)
{
- return (((unsigned int) x >> n) | ((unsigned int) x << (16 - n)))
- & UINT16_MAX;
+ return ((x >> n) | (x << (-n&15)));
}
/* Given an unsigned 8-bit argument X, return the value corresponding
- to rotating the bits N steps to the left. N must be between 1 to 7
- inclusive, but on most relevant targets N can also be 0 and 8
- because 'int' is at least 32 bits and the arguments must widen
- before shifting. */
+ to rotating the bits N steps to the left. N must be between 0 to 7
+ inclusive. */
BITROTATE_INLINE uint8_t
rotl8 (uint8_t x, int n)
{
- return (((unsigned int) x << n) | ((unsigned int) x >> (8 - n))) & UINT8_MAX;
+ return ((x << n) | (x >> (-n&7)));
}
/* Given an unsigned 8-bit argument X, return the value corresponding
- to rotating the bits N steps to the right. N must be in 1 to 7
- inclusive, but on most relevant targets N can also be 0 and 8
- because 'int' is at least 32 bits and the arguments must widen
- before shifting. */
+ to rotating the bits N steps to the right. N must be between 0 to 7
+ inclusive. */
BITROTATE_INLINE uint8_t
rotr8 (uint8_t x, int n)
{
- return (((unsigned int) x >> n) | ((unsigned int) x << (8 - n))) & UINT8_MAX;
+ return ((x >> n) | (x << (-n&7)));
+}
+
+/* Some GCC, Clang, ICC and XLC support 128-bit integers. */
+/* https://gcc.gnu.org/legacy-ml/gcc-help/2015-08/msg00185.html */
+
+#if __SIZEOF_INT128__ >= 16
+/* Given an unsigned 128-bit argument X, return the value corresponding
+ to rotating the bits N steps to the left. N must be between 0 to 127
+ inclusive. */
+BITROTATE_INLINE __uint128_t
+rotl128 (__uint128_t x, int n)
+{
+ return ((x << n) | (x >> (-n&127)));
+}
+
+/* Given an unsigned 128-bit argument X, return the value corresponding
+ to rotating the bits N steps to the right. N must be between 0 to 127
+ inclusive. */
+BITROTATE_INLINE __uint128_t
+rotr128 (__uint128_t x, int n)
+{
+ return ((x >> n) | (x << (-n&127)));
}
+#endif
_GL_INLINE_HEADER_END
diff --git a/tests/test-bitrotate.c b/tests/test-bitrotate.c
index 0007d1c33..8e0346af5 100644
--- a/tests/test-bitrotate.c
+++ b/tests/test-bitrotate.c
@@ -15,6 +15,7 @@
along with this program. If not, see <https://www.gnu.org/licenses/>. */
/* Written by Simon Josefsson <si...@josefsson.org>, 2008. */
+/* Updated for 128-bit types by Jeffrey Walton <noloa...@gmail.com>, 2020 */
#include <config.h>
@@ -81,6 +82,7 @@ main (void)
ASSERT (rotr16 (43981, 15) == 22427);
ASSERT (rotr16 (43981, 16) == 43981);
+ ASSERT (rotl32 (2309737967U, 0) == 2309737967U);
ASSERT (rotl32 (2309737967U, 1) == 324508639U);
ASSERT (rotl32 (2309737967U, 2) == 649017278U);
ASSERT (rotl32 (2309737967U, 3) == 1298034556U);
@@ -113,6 +115,7 @@ main (void)
ASSERT (rotl32 (2309737967U, 30) == 3798659963U);
ASSERT (rotl32 (2309737967U, 31) == 3302352631U);
+ ASSERT (rotr32 (2309737967U, 0) == 2309737967U);
ASSERT (rotr32 (2309737967U, 1) == 3302352631lU);
ASSERT (rotr32 (2309737967U, 2) == 3798659963lU);
ASSERT (rotr32 (2309737967U, 3) == 4046813629lU);
@@ -146,6 +149,7 @@ main (void)
ASSERT (rotr32 (2309737967U, 31) == 324508639lU);
#ifdef UINT64_MAX
+ ASSERT (rotl64 (16045690984503098046ULL, 0) == 16045690984503098046ULL);
ASSERT (rotl64 (16045690984503098046ULL, 1) == 13644637895296644477ULL);
ASSERT (rotl64 (16045690984503098046ULL, 2) == 8842531716883737339ULL);
ASSERT (rotl64 (16045690984503098046ULL, 3) == 17685063433767474678ULL);
@@ -210,6 +214,7 @@ main (void)
ASSERT (rotl64 (16045690984503098046ULL, 62) == 13234794782980550319ULL);
ASSERT (rotl64 (16045690984503098046ULL, 63) == 8022845492251549023ULL);
+ ASSERT (rotr64 (16045690984503098046ULL, 0) == 16045690984503098046ULL);
ASSERT (rotr64 (16045690984503098046ULL, 1) == 8022845492251549023ULL);
ASSERT (rotr64 (16045690984503098046ULL, 2) == 13234794782980550319ULL);
ASSERT (rotr64 (16045690984503098046ULL, 3) == 15840769428345050967ULL);
@@ -275,5 +280,27 @@ main (void)
ASSERT (rotr64 (16045690984503098046ULL, 63) == 13644637895296644477ULL);
#endif /* UINT64_MAX */
+ /* Hack ahead because GCC does not provide a way to initialize uint128_t */
+ /* https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html */
+ #if __SIZEOF_INT128__ >= 16
+ {
+ const __uint128_t v = (((__uint128_t)(0xffffffffffffffffULL)) << 64) | 0x00ffffffffffff00ULL;
+ const __uint128_t xl = v;
+ const __uint128_t xr = v;
+
+ ASSERT (rotl128 (v, 0) == xl);
+ ASSERT (rotr128 (v, 0) == xr);
+ }
+
+ {
+ const __uint128_t v = (((__uint128_t)(0xffffffffffffffffULL)) << 64) | 0x00ffffffffffff00ULL;
+ const __uint128_t xl = (((__uint128_t)(0xffffffffffffff00ULL)) << 64) | 0xffffffffffff00ffULL;
+ const __uint128_t xr = (((__uint128_t)(0x00ffffffffffffffULL)) << 64) | 0xff00ffffffffffffULL;
+
+ ASSERT (rotl128 (v, 8) == xl);
+ ASSERT (rotr128 (v, 8) == xr);
+ }
+ #endif
+
return 0;
}
