Re: bitrotate

[Simon Josefsson]

Paul Eggert <address@hidden> writes:

> That change looks good.  Some minor points:
>
>> +/* 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. */
>> +static inline uint16_t
>> +rotl16 (uint16_t x, int n)
>
> On all targets of interest for GNU software (including all POSIX-2001
> or later targets), N can also be 0 or 16.  That is because 'int' must
> be at least 32 bits on these platforms, and the arguments must widen
> to at least 32 bits before being shifted.  Perhaps this should be
> noted in the comment?  Similarly for rotr16.

Good idea, added in comments below.  I also made sure it is tested by
the self tests.

>> return ((x << n) | (x >> (64 - n))) & 0xFFFFFFFFFFFFFFFFULL;
>
> I found myself wondering "is that the right number of Fs?".  How about
> the following rewording instead?  Similarly for the other functions.
>
>   return ((x << n) | (x >> (64 - n))) & UINT64_MAX;

Excellent, I agree it is more readable.

> One other thing: if memory serves, the C standard does not require the
> existence of uint32_t and uint16_t (this is for portability to 36-bit
> hosts, I expect); this can easily be worked around by using #ifdef
> UINT32_MAX and #ifdef UINT16_MAX.

Maybe we can apply that patch using lazy evaluation until someone
reports it as a practical problem.  At least I'm curious to learn which
system they are using.  But I agree in principle.

Thanks,
/Simon

>From e6f0227e493c3104cead93665d37104a9c7f473c Mon Sep 17 00:00:00 2001
From: Simon Josefsson <address@hidden>
Date: Mon, 8 Sep 2008 12:15:14 +0200
Subject: [PATCH] bitrotate: Use UINT*_MAX constants.  Doc string improvement.

---
 ChangeLog       |    9 +++++++++
 lib/bitrotate.h |   32 ++++++++++++++++++++------------
 2 files changed, 29 insertions(+), 12 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 3c72521..47bc08f 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2008-09-08  Simon Josefsson  <address@hidden>
+
+       * lib/bitrotate.h: Doc fix, mention that N can be wider than minimally
+       required for 16-bit and 8-bit rotates.
+       * lib/bitrotate.h (rotl64, rotr64, rotl32, rotl32, rotl16, rotr16,
+       rotl8, rotr8): Use UINT64_MAX, UINT32_MAX, UINT16_MAX, and
+       UINT8_MAX instead of hard-coded constants.  Suggested by Paul
+       Eggert.
+
 2008-09-07  Bruno Haible  <address@hidden>
 
        * tests/test-striconveh.c (main): Check behaviour when converting from
diff --git a/lib/bitrotate.h b/lib/bitrotate.h
index 65bf682..d4911d0 100644
--- a/lib/bitrotate.h
+++ b/lib/bitrotate.h
@@ -28,7 +28,7 @@
 static inline uint64_t
 rotl64 (uint64_t x, int n)
 {
-  return ((x << n) | (x >> (64 - n))) & 0xFFFFFFFFFFFFFFFFULL;
+  return ((x << n) | (x >> (64 - n))) & UINT64_MAX;
 }
 
 /* Given an unsigned 64-bit argument X, return the value corresponding
@@ -37,7 +37,7 @@ rotl64 (uint64_t x, int n)
 static inline uint64_t
 rotr64 (uint64_t x, int n)
 {
-  return ((x >> n) | (x << (64 - n))) & 0xFFFFFFFFFFFFFFFFULL;
+  return ((x >> n) | (x << (64 - n))) & UINT64_MAX;
 }
 #endif
 
@@ -47,7 +47,7 @@ rotr64 (uint64_t x, int n)
 static inline uint32_t
 rotl32 (uint32_t x, int n)
 {
-  return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFF;
+  return ((x << n) | (x >> (32 - n))) & UINT32_MAX;
 }
 
 /* Given an unsigned 32-bit argument X, return the value corresponding
@@ -56,43 +56,51 @@ rotl32 (uint32_t x, int n)
 static inline uint32_t
 rotr32 (uint32_t x, int n)
 {
-  return ((x >> n) | (x << (32 - n))) & 0xFFFFFFFF;
+  return ((x >> n) | (x << (32 - n))) & UINT32_MAX;
 }
 
 /* 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. */
+   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. */
 static inline uint16_t
 rotl16 (uint16_t x, int n)
 {
-  return ((x << n) | (x >> (16 - n))) & 0xFFFF;
+  return ((x << n) | (x >> (16 - n))) & UINT16_MAX;
 }
 
 /* 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. */
+   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. */
 static inline uint16_t
 rotr16 (uint16_t x, int n)
 {
-  return ((x >> n) | (x << (16 - n))) & 0xFFFF;
+  return ((x >> n) | (x << (16 - n))) & UINT16_MAX;
 }
 
 /* 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. */
+   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. */
 static inline uint8_t
 rotl8 (uint8_t x, int n)
 {
-  return ((x << n) | (x >> (8 - n))) & 0xFF;
+  return ((x << n) | (x >> (8 - n))) & UINT8_MAX;
 }
 
 /* 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. */
+   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. */
 static inline uint8_t
 rotr8 (uint8_t x, int n)
 {
-  return ((x >> n) | (x << (8 - n))) & 0xFF;
+  return ((x >> n) | (x << (8 - n))) & UINT8_MAX;
 }
 
 #endif /* _GL_BITROTATE_H */
-- 
1.5.6.5

>From 54c148b43d12bab5a96a8619d86e474692d664b3 Mon Sep 17 00:00:00 2001
From: Simon Josefsson <address@hidden>
Date: Mon, 8 Sep 2008 12:18:02 +0200
Subject: [PATCH] bitrotate: Test 8/16-bit rotates with 0 and maximum rotate 
amounts.

---
 ChangeLog              |    3 +++
 tests/test-bitrotate.c |    8 ++++++++
 2 files changed, 11 insertions(+), 0 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 47bc08f..0fc0019 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,8 @@
 2008-09-08  Simon Josefsson  <address@hidden>
 
+       * tests/test-bitrotate.c: Test 8/16-bit rotates with 0 and maximum
+       rotate amounts.
+
        * lib/bitrotate.h: Doc fix, mention that N can be wider than minimally
        required for 16-bit and 8-bit rotates.
        * lib/bitrotate.h (rotl64, rotr64, rotl32, rotl32, rotl16, rotr16,
diff --git a/tests/test-bitrotate.c b/tests/test-bitrotate.c
index 5b7d171..5ebf60f 100644
--- a/tests/test-bitrotate.c
+++ b/tests/test-bitrotate.c
@@ -39,6 +39,7 @@
 int
 main (void)
 {
+  ASSERT (rotl8 (42, 0) == 42);
   ASSERT (rotl8 (42, 1) == 84);
   ASSERT (rotl8 (42, 2) == 168);
   ASSERT (rotl8 (42, 3) == 81);
@@ -46,7 +47,9 @@ main (void)
   ASSERT (rotl8 (42, 5) == 69);
   ASSERT (rotl8 (42, 6) == 138);
   ASSERT (rotl8 (42, 7) == 21);
+  ASSERT (rotl8 (42, 8) == 42);
 
+  ASSERT (rotr8 (42, 0) == 42);
   ASSERT (rotr8 (42, 1) == 21);
   ASSERT (rotr8 (42, 2) == 138);
   ASSERT (rotr8 (42, 3) == 69);
@@ -54,7 +57,9 @@ main (void)
   ASSERT (rotr8 (42, 5) == 81);
   ASSERT (rotr8 (42, 6) == 168);
   ASSERT (rotr8 (42, 7) == 84);
+  ASSERT (rotr8 (42, 8) == 42);
 
+  ASSERT (rotl16 (43981, 0) == 43981);
   ASSERT (rotl16 (43981, 1) == 22427);
   ASSERT (rotl16 (43981, 2) == 44854);
   ASSERT (rotl16 (43981, 3) == 24173);
@@ -70,7 +75,9 @@ main (void)
   ASSERT (rotl16 (43981, 13) == 46457);
   ASSERT (rotl16 (43981, 14) == 27379);
   ASSERT (rotl16 (43981, 15) == 54758);
+  ASSERT (rotl16 (43981, 16) == 43981);
 
+  ASSERT (rotr16 (43981, 0) == 43981);
   ASSERT (rotr16 (43981, 1) == 54758);
   ASSERT (rotr16 (43981, 2) == 27379);
   ASSERT (rotr16 (43981, 3) == 46457);
@@ -86,6 +93,7 @@ main (void)
   ASSERT (rotr16 (43981, 13) == 24173);
   ASSERT (rotr16 (43981, 14) == 44854);
   ASSERT (rotr16 (43981, 15) == 22427);
+  ASSERT (rotr16 (43981, 16) == 43981);
 
   ASSERT (rotl32 (2309737967U, 1) == 324508639U);
   ASSERT (rotl32 (2309737967U, 2) == 649017278U);
-- 
1.5.6.5