1. Changelog
1.1. Revision 3 - September 4th, 2024
-
Minor typo and wording fixes in preparation for C2y/C3a.
-
Additional updates for Minneapolis meeting for wording.
1.2. Revision 2 - February 7th, 2023
-
The wrong paper was sent in for Revision 1, so this paper was re-published as revision 2.
1.3. Revision 1 - January 31st, 2023
-
Change specification for
stdc_rotate_left stdc_rotate_right -
Add footnote about preventing promotion issues from using
unsigned char unsigned short int -
Make sure constraints on
generic_count_type
-
1.4. Revision 0 - December 14th, 2022
-
Initial release. ✨
-
Removed all of the components from [n3022] that were accepted, and migrated all of the non-accepted parts to this in response to feedback from many individuals.
-
Changed the conditions on the 8-bit memory reversal functions to be
CHAR_BIT == 8 -
Users who want this functionality on those platforms should begin to converge on a design that works for them, preferably in the fashion as described by this paper and its predecessors.
-
That designs should be implemented by those users on those platforms and brought forward for standardization at another point in time.
-
2. Polls
No polls except for the ones noted in the older version of this paper for C23 was taken ([n3022]).
3. Introduction & Motivation
There is a lot of proposals and work that goes into figuring out the "byte order" of integer values that occupy more than 1 octet (8 bits). This is nominally important when dealing with data that comes over network interfaces and is read from files, where the data can be laid out in various orders of octets for 2-, 3-, 4-, 6-, or 8-tuples of octets. The most well-known endian structures on existing architectures include "Big Endian", where the least significant bit comes "last" and is featured prominently in network protocols and file protocols; and, "Little Endian", where the least significant bit comes "first" and is typically the orientation of data for processor and user architectures most prevalent today.
In more legacy architectures (Honeywell, PDP), there also exists other orientations called "mixed" or "middle" endian. The uses of such endianness are of dubious benefit and are vanishingly rare amongst commodity and readily available hardware today, but nevertheless still represent an applicable ordering of octets.
In other related programming interfaces, the C functions/macros
This proposal puts forth the fundamentals that make a homegrown implementation of
4. Design
This is a library addition. It is meant to expose both macros and functions that can be used for translation time-suitable checks. It provides a way to check endianness within the preprocessor, and gives definitive names that allow for knowing whether the endianness is big, little, or neither. We state big, little, or neither, because there is no settled-upon name for the legacy endianness of "middle" or "mixed", nor any agreed upon ordering for such a "middle" or "mixed" endianness between architectures. This is not the case for big endian or little endian, where one is simply the reverse of the other, always, in every case, across architectures, file protocols, and network specifications.
The next part of the design is functions for working with groupings of 8 bits. They are meant to communicate with network or file protocols and formats that have become ubiquitous in computing for the last 30 years.
Finally, this design adds new left/right bit rotation functions, all within the
4.1. Preliminary: Why the stdc_
We use the
4.2. Charter: unsigned char const ptr [ static sizeof ( uintN_t )]
There are 2 choices on how to represent sized pointer arguments. The first is a
To start, we still put any
One of the tipping arguments in favor of our choice of
4.3. Signed vs. Unsigned
This paper has gone back and forth between signed vs. unsigned
-
All of the values returned from the functions here return conceptually unsigned/natural numbers (0 to potentially infinity, but not negative).
-
Some existing practice — e.g., C++ — has in recent years struggled against unsigned integers and tried to move towards signed. "Anything that is a count should just be an
int -
Conversely, some of C’s most fierce proponents use unsigned numbers almost exclusively until they have a proper justification for a signed number. For them,
unsigned size_t -
Whatever decision we make for one (e.g., for the argument type of
rotate_left rotate_right count_ones popcount
This brings up a lot of questions about whether or not the functions here should be signed or unsigned. We will analyze this primarily from the standpoint of
4.3.1. In Defense of Signed Integers
Let us consider a universe where
SDCC and several other compilers optimize for left and right shifts ([sdcc]). Texas Instruments and a handful of other specialist architectures also have "variable shift" instructions (SSHVL), which uses the sign of the argument to shift in one direction or the other ([ti-tms320c64x]). Having a
To test code generation for using a signed integer and 2’s complement arithmetic, we used both C++ and C code samples. The C++ code is based on its accepted C++20 proposal, [p0463]. It’s a fairly accurate predictor of how notable compilers handle this kind of specification. The generated assembly for the compilers turns out to be optimal, so long as an implementation does not do a literal copy-paste of the specification’s text
Using non-constant offset, with generated x86_64 assembly:
#include <bit>extern unsigned int x ; extern int offset ; int main () { int l = std :: rotl ( x , offset ); int r = std :: rotr ( x , offset ); return l + r ; }
main : # @main mov eax , dword ptr [ rip + x ] mov cl , byte ptr [ rip + offset ] mov edx , eax rol edx , cl ror eax , cl add eax , edx ret
— And, using constant offset, with generated x86_64 assembly.
#include <bit>extern unsigned int x ; int main () { int l = std :: rotl ( x , -13 ); int r = std :: rotr ( x , -13 ); return l + r ; }
main : # @main mov eax , dword ptr [ rip + x ] mov ecx , eax rol ecx , 19 rol eax , 13 add eax , ecx ret
The generated code shows that the compiler understands the symmetric nature of the operations (from the constant code) and also shows that it will appropriately handle it even when it cannot see through constant values. The same can be shown when writing C code using a variety of styles, as shown here:
#if UNSIGNED_COUNT == 1 static unsigned int rotate_right ( unsigned int value , unsigned int count ); inline static unsigned int rotate_left ( unsigned int value , unsigned int count ) { unsigned int c = count % 32 ; return value >> c | value << ( 32 - c ); } inline static unsigned int rotate_right ( unsigned int value , unsigned int count ) { unsigned int c = count % 32 ; return value << c | value >> ( 32 - c ); } #elif TWOS_COMPLEMENT_CAST == 1 static unsigned int rotate_right ( unsigned int value , int count ); inline static unsigned int rotate_left ( unsigned int value , int count ) { unsigned int c = ( unsigned int ) count ; c = c % 32 ; return value >> c | value << ( 32 - c ); } inline static unsigned int rotate_right ( unsigned int value , int count ) { unsigned int c = ( unsigned int ) count ; c = c % 32 ; return value << c | value >> ( 32 - c ); } #else static unsigned int rotate_right ( unsigned int value , int count ); inline static unsigned int rotate_left ( unsigned int value , int count ) { int c = count % 32 ; if ( c < 0 ) { return rotate_right ( value , - c ); } return value >> c | value << ( 32 - c ); } inline static unsigned int rotate_right ( unsigned int value , int count ) { int c = count % 32 ; if ( c < 0 ) { return rotate_left ( value , - c ); } return value << c | value >> ( 32 - c ); } #endif #if UNSIGNED_COUNT == 1 unsigned int f ( unsigned int x , unsigned int offset ) { #else unsigned int f ( unsigned int x , int offset ) { #endif unsigned int l = rotate_left ( x , offset ); unsigned int r = rotate_right ( x , offset ); return l + r ; }
When using the various definitions, we find that the generated assembly for
2 Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.
— §6.3.1.3, ¶2, ISO/IEC 9899:202x "C2x" Standard
Finally, the vast majority of existing practice takes the offset value in as a signed integer, and all the return types are also still some form of signed integer (unless the intrinsic is returning the exact same unsigned value put in that was manipulated). It also allows "plain math" being done on the type to naturally manifest negative numbers without accidentally having roundtripping or signed/unsigned conversion issues.
4.3.2. In Defense of Unsigned
Unsigned, on the other hand, has existing practice in hardware. While the intrinsics defined by glibc, C++'s standard libraries, and many more use signed integers, they are conceptually unsigned in their implementations. For example, for a 32-bit rotate, most standard libraries taking an
count = count & 31 ;
This is critical for optimization here. Note that, if we were to provide a specification using a
count = count % 32 ;
produces optimal code generation for most compilers, as they understand that bit
Rust is one of the few languages that provides optimal versions of this code using
All in all, unsigned naturally optimizes better and matches the size type of C. It has no undefined behavior on overflow and produces better assembly in-general when it comes to bit intrinsics. Shifting behavior is also well-defined for unsigned types and not signed types, further compounding unsigned types as far better than their signed counterparts.
4.3.3. Which Does This Paper Choose?
Ultimately, this paper chooses unsigned integer types. The core of the reasoning is that this avoids undefined behavior in the specification and is also morally and spiritually what architectures expect (at least for 2’s complement). Since C23 embraces 2’s complement, using unsigned here would work more or less identically to a signed integer anyways and therefore it just does not matter enough to want to write an exception for
4.4. Generic 8-bit Memory Reverse and Exact-width 8-bit Memory Reverse
In order to accommodate both a wide variety of architectures but also support minimum-width integer optimized intrinsics, this proposal takes from the industry 2 forms of byteswap:
-
one generic
mem_ -
a sequence of exact-width byte swapping instructions which (typically) map directly to intrinsics available in compilers and instructions in hardware.
These end up inhabiting the
#include <stdbit.h>#include <limits.h>#include <stdint.h>#if ((CHAR_BIT) % 8 == 0) void stdc_memreverse8 ( size_t n , unsigned char ptr [ static n ]); uintN_t stdc_memreverse8uN ( uintN_t value ); #endif
where
// On typical CHAR_BIT == 8, i686/x86_32/x86_64/ARM32/AARCH64 implementations const uint32_t normal = 0xAABBCCDDu ; const uint32_t reversed = 0xDDCCBBAAu ; assert ( stdc_memreverse8u32 ( normal ) == reversed );
4.4.1. But Memory Reverse Is Dangerous?
Byte swapping, by itself, is absolutely dangerous in terms of code portability. Users often program strictly for their own architecture when doing serialization, and do not take into consideration that their endianness can change. This means that, while
The inclusion of the
4.4.2. Vetting the Implementation / Algorithm for memreverse
In previous iterations of the paper, there were various off-by-one errors in transcribing the algorithm used to get the job done. Therefore, we more directly lifted the code for the algorithm from the example implementation here. To further prove that it works on "bytes" that may be larger than 8 bits, we also took the following steps.
-
Implemented it as a macro (as shown from the link above).
-
Use that macro implementation in the normal
unsigned char -
Use that macro implementation all unsigned integer types that are larger than
unsigned char -
Apply
- fno - strict - alias
All of the tests pass across the three major compilers (MSVC, GCC, and Clang) and across platforms (Windows, Linux, Mac OS). We find this to be compelling enough to ensure that the implementation and the algorithm in the wording is suitably correct. Nevertheless, any wording failures present here represent the authors' collective inability to properly serialize wording, not that an implementation is not possible or too inventive.
Regardless of how well it’s tested and checked, the paper still restricts the content to
4.5. stdc_load8_ * stdc_store8_ *
Functions meant to transport bytes to a specific endianness need 3 pieces of information:
-
the sign of the input/output;
-
the byte order of the input; and,
-
the desired byte order of the output.
To represent any operation that goes from/to the byte order that things like
The specification for the endianness functions borrows from many different sources listed above, and is as follows:
#include <stdbit.h>#include <limits.h>#include <stdint.h>#if (CHAR_BIT) == 8 void stdc_store8_leuN ( uint_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_beuN ( uint_leastN_t value , unsigned char ptr [ static ( N / 8 )]); uint_leastN_t stdc_load8_leuN ( const unsigned char ptr [ static ( N / 8 )]); uint_leastN_t stdc_load8_beuN ( const unsigned char ptr [ static ( N / 8 )]); void stdc_store8_aligned_leuN ( uint_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_aligned_beuN ( uint_leastN_t value , unsigned char ptr [ static ( N / 8 )]); uint_leastN_t stdc_load8_aligned_leuN ( const unsigned char ptr [ static ( N / 8 )]); uint_leastN_t stdc_load8_aligned_beuN ( const unsigned char ptr [ static ( N / 8 )]); void stdc_store8_lesN ( int_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_besN ( int_leastN_t value , unsigned char ptr [ static ( N / 8 )]); int_leastN_t stdc_load8_lesN ( const unsigned char ptr [ static ( N / 8 )]); int_leastN_t stdc_load8_besN ( const unsigned char ptr [ static ( N / 8 )]); void stdc_store8_aligned_lesN ( int_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_aligned_besN ( int_leastN_t value , unsigned char ptr [ static ( N / 8 )]); int_leastN_t stdc_load8_aligned_lesN ( const unsigned char ptr [ static ( N / 8 )]); int_leastN_t stdc_load8_aligned_besN ( const unsigned char ptr [ static ( N / 8 )]); #endif
Thanks to some feedback from implementers and librarians, this first implementation would also need an added signed variant to the load and store functions as well as aligned and unaligned loads and stores. While C23 mandates a two’s complement representation for integers, because we are using the
This specification is marginally more complicated than the
We are fine with not making these precisely
4.5.1. Vetting the Implementation / Algorithm for 8-bit loads and stores
In previous iterations of the paper, getting the algorithm written down properly in a way that does not rely on any kind of implementation-defined behavior for signed and unsigned endian-aware loads and stores was tough and resulted in many errors in the wording. Still, we know that the implementation is solid because we have tested it (both theoretically and factually) by writing implementations which base "unit" for writing into has a width greater than
-
Implemented the core bodies of the functions as macros whose base unit is not necessarily
unsigned char -
Use that macro implementation in the normal
unsigned char -
Use that macro implementation all unsigned integer types that are larger than
unsigned char -
Apply
- fno - strict - alias
All of the tests pass across the three major compilers (MSVC, GCC, and Clang) and across platforms (Windows, Linux, Mac OS). We find this to be compelling enough to ensure that the implementation is suitably correct, even if the wording may not be proper or ideal. Therefore, we hope this can serve as a good basis in establishing that, at the very least, this is both implementable and usable. This also corroborates additional materials outside of compilers who always target
Regardless of how well it’s tested and checked, the paper still restricts the content to
4.6. Additional Modern Bit Utilities
Additionally to this, upon first review of the paper there was a strong supporting groundswell for bit operations that have long been present in both hardware and as compiler intrinsics. This idea progressed naturally from the
| operation | Intel/AMD | ARM | PowerPC |
|---|---|---|---|
| ROL | - | rldicl |
| ROR | ROR, EXTR | - |
Many of the below bit functions are defined below to ease portability to these architectures. For places where specific compiler idioms and automatic detection are not possible, similar assembly tricks or optimized implementations can be provided by C. Further bit functions were also merged into C++, resulting in the current state of the C++ bit header.
There is further a bit of an "infamous" page amongst computer scientists for Bit Twiddling Hacks. These may not all map directly to instructions but they provide a broad set of useful functionality commonly found in not only CPU-based programming libraries, but GPU-based programming libraries and other high performance computing resources as well.
We try to take the most useful subset of these functions that most closely represent functionality on both old and new CPU architectures as well as common, necessary operations that have been around in the last 25 years for various industries. We have left out operations such as sign extension, parity computation, bit merging, clear/setting bits, fast negation, bit swaps, lexicographic next bit permutation, and bit interleaving. The rest are more common and appear across a wide range of industries from cryptography to graphics to simulation to efficient property lookup and kernel scheduling.
4.6.1. Type-Generic Macros and Counts for Types
All of the functions below have type generic macros associated with them. This can bring up an interesting question: if the return value depends on the type of the argument going into the function (i.e. for
4.6.2. Argument Types
Many of the functions below are defined over the fundamental unsigned integer types, rather than their minimum width or exact width counterparts. This is done to provide maximum portability: users can combine information from the recently-introduced
The
The exact-width types suffer from non-availability on specific platforms, which makes little sense for functions which do not depend on a no-padding bits requirement. As long as the values read from the array only involve
Extended integer types, least-width integer types, and exact-width integer types, can all be used with the type-generic macros since the type-generic macros are required to work over all standard (unsigned) integer types and extended (unsigned) integer types, while excluding
Finally, in general
4.6.3. Return Types
Ostensibly, part of the motivation to capture here should be that the types used to do things such as rotations should be identical to the return type used to do things like count zeros, e.g.
At the moment, the functions do not accept all bit-precise integer types (just ones that are bit-width equivalent to the existing standard and extended integer types), so this is technically a non-issue. But, if and when bit-precise integer types are given better handling in
4.6.4. stdc_rotate_left stdc_rotate_right
#include <stdbit.h>unsigned char stdc_rotate_left_uc ( unsigned char value , unsigned int count ); unsigned short stdc_rotate_left_us ( unsigned short value , unsigned int count ); unsigned int stdc_rotate_left_ui ( unsigned int value , unsigned int count ); unsigned long stdc_rotate_left_ul ( unsigned long value , unsigned int count ); unsigned long long stdc_rotate_left_ull ( unsigned long long value , unsigned int count ); unsigned char stdc_rotate_right_uc ( unsigned char value , unsigned int count ); unsigned short stdc_rotate_right_us ( unsigned short value , unsigned int count ); unsigned int stdc_rotate_right_ui ( unsigned int value , unsigned int count ); unsigned long stdc_rotate_right_ul ( unsigned long value , unsigned int count ); unsigned long long stdc_rotate_right_ull ( unsigned long long value , unsigned int count ); // type-generic macro generic_value_type stdc_rotate_left ( generic_value_type value , generic_count_type count ); generic_value_type stdc_rotate_right ( generic_value_type value , generic_count_type count );
They cover all of the built-in unsigned integer types. A discussion of signed vs. unsigned integer types for the count type and the return type can be found in a previous section, here § 4.3 Signed vs. Unsigned.
As for choosing a single function like
f : # @f mov r8d , edi mov ecx , esi rol r8d , cl mov edx , edi ror edx , cl mov ecx , esi neg ecx mov eax , edi rol eax , cl ror edi , cl test esi , esi cmovs edx , r8d cmovle eax , edi add eax , edx ret
This is more than double the size of the rotates found using left/right directly in § 4.3 Signed vs. Unsigned. Due to this, we decided that it was not advantageous to have a signed count with an unknown left/right: it is important to be capable of biasing the optimizer to whether a given rotate is left/right oriented.
5. Wording
The following wording is relative to the latest draft standard.
5.1. Add a new §7.18.✨17 and §7.18.✨18 sub-sub-clauses for "8-bit Memory Reversal" in §7.18
7.18.✨17 8-bit Memory ReversalSynopsis#include <stdbit.h>#include <limit.h>#if (CHAR_BIT) == 8 void stdc_memreverse8 ( size_t n , unsigned char ptr [ static n ]); #endif DescriptionThe
function reverses the order of the bytes pointed to bystdc_memreverse8 . For everyptr at offsetunsigned char in the rangeindex , inclusive, swap the values at[ 0 , n / 2 ] andptr [ index ] , except whenptr [ n - index - 1 ] ==index in which case nothing is done.n - index - 1 §7.18.✨18 Exact-width 8-bit Memory ReversalSynopsis#include <stdbit.h>#include <limits.h>#include <stdint.h>#if (CHAR_BIT) == 8 uintN_t stdc_memreverse8uN ( uintN_t value ); #endif DescriptionThe
functions provide an interface to swap the bytes of a correspondingstdc_memreverse8u N object, where N matches one of the exact-width integer types (7.20.1.1). If an implementation provides the correspondinguint N _t typedef, it shall define the corresponding exact-width memory reversal function for that value ofuint N _t .N ReturnsThe
functions returns the 8-bit memory reversedstdc_memreverse8u N value, as if by invokinguint N _t and then returningstdc_memreverse8 ( sizeof ( value ), ( unsigned char * ) & value ) .value
5.2. Add a new §7.18.✨19 sub-sub-clause for "Endian-Aware" functions in §7.18
7.18.✨19 Endian-Aware 8-bit LoadSynopsis#include <stdbit.h>#if (CHAR_BIT) == 8 uint_leastN_t stdc_load8_leuN ( const unsigned char ptr [ static ( N / 8 )]); uint_leastN_t stdc_load8_beuN ( const unsigned char ptr [ static ( N / 8 )]); uint_leastN_t stdc_load8_aligned_leuN ( const unsigned char ptr [ static ( N / 8 )]); uint_leastN_t stdc_load8_aligned_beuN ( const unsigned char ptr [ static ( N / 8 )]); int_leastN_t stdc_load8_lesN ( const unsigned char ptr [ static ( N / 8 )]); int_leastN_t stdc_load8_besN ( const unsigned char ptr [ static ( N / 8 )]); int_leastN_t stdc_load8_aligned_lesN ( const unsigned char ptr [ static ( N / 8 )]); int_leastN_t stdc_load8_aligned_besN ( const unsigned char ptr [ static ( N / 8 )]); #endif DescriptionThe 8-bit load family of functions functions read an
orint_least N _t object from the provideduint_least N _t in an endian-aware (7.18.2) manner, where N matches an existing minimum-width integer type (7.20.1.2). If an implementation provides the correspondingptr typedef, it shall define the corresponding endian-aware load function function for that value ofuint_least N _t . If this function is present, N shall be a multiple of 8 andN shall be 8. The functions containingCHAR_BIT in the name shall assume that_aligned is suitably aligned to access a signed or unsigned integer of width N for a signed or unsigned variant of the function, respectively. If the function name contains theptr suffix in the name, it is a signed variant. Otherwise, the function is an unsigned variant. If the function name contains thes N orles N suffix, it is a little-endian variant. Otherwise, if the function name contains theleu N orbes N suffix, it is a big-endian variant.beu N ReturnsLet the computed value $result$ be:
$$\sum_{index = 0}^{(N \div{} 8) - 1} b_{index} \times{} 2^{8 \times{} index}$$
where $b_{index}$ is:
—
, if the function is the little-endian variant;ptr [ index ] — otherwise,
, if the function is the the big-endian variant.ptr [ N - index - 1 ] If the function is an unsigned variant, return $result$. Otherwise, if the function is a signed variant, return:
$result$, if $result$ is less than $2^{N-1}$;
otherwise, $result - 2^{N}$.
7.18.✨20 Endian-Aware 8-bit StoreSynopsis#include <stdbit.h>#if (CHAR_BIT) == 8 void stdc_store8_leuN ( uint_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_beuN ( uint_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_aligned_leuN ( uint_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_aligned_beuN ( uint_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_lesN ( int_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_besN ( int_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_aligned_lesN ( int_leastN_t value , unsigned char ptr [ static ( N / 8 )]); void stdc_store8_aligned_besN ( int_leastN_t value , unsigned char ptr [ static ( N / 8 )]); #endif DescriptionThe 8-bit store family of functions functions write a
orint_least N _t object into the provideduint_least N _t in an endian-aware (7.18.2) manner, where N matches an existing minimum-width integer type (7.20.1.2). If an implementation provides the correspondingptr typedef, it shall define the corresponding endian-aware store function function for that value ofuint_least N _t . If this function is present, N shall be a multiple of 8 andN shall be 8. The functions containingCHAR_BIT in the name shall assume that_aligned is suitably aligned to access a signed or unsigned integer of width N. If the function name contains theptr suffix in the name, it is a signed variant. Otherwise, the function is an unsigned variant. If the function name contains thes N orles N suffix, it is a little-endian variant. Otherwise, if the function name contains theleu N orbes N suffix, it is a big-endian variant.beu N Let
bevalue_unsigned if the function is a unsigned variant. Otherwise, letvalue be the conversion ofvalue_unsigned to its corresponding unsigned type, if the function is a signed variant.value Let
be an integer in a sequence thatindex
— starts from 0 and increments by 8 in the range of [0, N), if the function is a little-endian variant;
— starts from
and decrements by 8 in the range of [0, N), if the function is a big-endian variant.N - 8 Let
be an integer that starts from 0. For eachptr_index in the order of the above-specified sequence:index
Sets the 8 bits in
toptr [ ptr_index ] .( value_unsigned >> index ) & 0xFF
Increments
by 1.ptr_index
5.3. Add a new §7.18.✨21 sub-sub-clause for Rotate Left and Rotate Right Bit Utilities in §7.18
7.18.✨21 Rotate LeftSynopsisunsigned char stdc_rotate_left_uc ( unsigned char value , unsigned int count ); unsigned short stdc_rotate_left_us ( unsigned short value , unsigned int count ); unsigned int stdc_rotate_left_ui ( unsigned int value , unsigned int count ); unsigned long stdc_rotate_left_ul ( unsigned long value , unsigned int count ); unsigned long long stdc_rotate_left_ull ( unsigned long long value , unsigned int count ); generic_value_type stdc_rotate_left ( generic_value_type value , generic_count_type count ); DescriptionThefunctions perform a bitwise rotate left. This operation is typically known as a left circular shift.stdc_rotate_left ReturnsLet N be the width corresponding to the type of the input
. Letvalue beno_promote_value . Let( unsigned _BitInt ( N ) value ber .count % N
— If r is 0, returns
;value — otherwise, returns
FN0✨).( no_promote_value < < r ) | ( no_promote_value >> ( N - r )) The type-generic function (marked by its
argument) returns the above described result for a given input value so long as thegeneric_value_type isgeneric_value_type
— a standard unsigned integer type, excluding
;bool — an extended unsigned integer type;
— or, a bit-precise unsigned integer type whose width matches any standard or extended integer type, excluding
.bool The
argument shall be a non-negative value of signed or unsigned integer type, orgeneric_count_type count .char FN0✨) Bit-precise integer types do not perform integer promotion in these expressions and therefore prevent potential undefined behavior from a literal implementation which would usein place ofvalue (e.g., from a function call such asno_promote_value with anstdc_rotate_left_us ( 0xFFFF , 15 ) width of 16 with anunsigned short width of 24).int
7.18.✨22 Rotate RightSynopsisunsigned char stdc_rotate_right_uc ( unsigned char value , unsigned int count ); unsigned short stdc_rotate_right_us ( unsigned short value , unsigned int count ); unsigned int stdc_rotate_right_ui ( unsigned int value , unsigned int count ); unsigned long stdc_rotate_right_ul ( unsigned long value , unsigned int count ); unsigned long long stdc_rotate_right_ull ( unsigned long long value , unsigned int count ); generic_value_type stdc_rotate_right ( generic_value_type value , generic_count_type count ); DescriptionThefunctions perform a bitwise rotate right. This operation is typically known as a right circular shift.stdc_rotate_right ReturnsLet N be the width corresponding to the type of the input
. Letvalue beno_promote_value . Let r be( unsigned _BitInt ( N )) value .count % N
— If r is 0, returns
;value — otherwise, returns
FN1✨);( no_promote_value >> r ) | ( no_promote_value << ( N - r )) FN1✨) Bit-precise integer types do not perform integer promotion in these expressions and therefore prevent potential undefined behavior from a literal implementation which would usein place ofvalue (e.g., from a function call such asno_promote_value with anstdc_rotate_right_us ( 0xFFFF , 15 ) width of 16 with anunsigned short width of 24).int The type-generic function (marked by its
argument) returns the above described result for a given input value so long as thegeneric_value_type isgeneric_value_type
— a standard unsigned integer type, excluding
;bool — an extended unsigned integer type;
— or, a bit-precise unsigned integer type whose width matches any standard or extended integer type, excluding
.bool The
argument shall be a non-negative value of signed or unsigned integer type, orgeneric_count_type count .char
6. Appendix
A collection of miscellaneous and helpful bits of information and implementation.
6.1. Example Implementations in Publicly-Available Libraries
Optimized routines following the naming conventions present in this paper can be found in the Shepherd’s Oasis Industrial Development Kit (IDK) library, compilable with a conforming C11 compiler and tested on MSVC, GCC, and Clang on Windows, Mac, and Linux:
Optimized routines following the basic principles present in this paper and used as motivation to improve several C++ Standard Libraries can be found in the Itsy Bitsy Bit Libraries, compilable with a conforming C++17 and tested on MSVC, GCC, and Clang on Windows, Mac, and Linux:
-
Bit Intrinsics (Declarations) (Sources)
Endianness routines and original motivation that spawned this proposal came from David Seifert’s Portable Endianness library and its deep dive into compiler optimizations and efficient code generation when alignment came into play:
-
Endian Load/Store (Declarations) (Sources)
7. Acknowledgements
Many thanks to David Seifert, Aaron Bachmann, Jens Gustedt, Tony Finch, Erin AO Shepherd, and many others who helped fight to get the semantics and wording into the right form, providing motivation, giving example code, pointing out existing libraries, and helping to justify this proposal.