Circular shift

Implementing circular shifts

Circular shifts are used often in cryptography in order to permute bit sequences. Unfortunately, many programming languages, including C, do not have operators or standard functions for circular shifting, even though virtually all processors have bitwise operation instructions for it (e.g. Intel x86 has ROL and ROR). However, some compilers may provide access to the processor instructions by means of intrinsic functions. In addition, some constructs in standard ANSI C code may be optimized by a compiler to the "rotate" assembly language instruction on CPUs that have such an instruction. Most C compilers recognize the following idiom, and compile it to a single 32-bit rotate instruction.^[1][2]

/*
 * Shift operations in C are only defined for shift values which are
 * not negative and smaller than sizeof(value) * CHAR_BIT.
 * The mask, used with bitwise-and (&), prevents undefined behaviour
 * when the shift count is 0 or >= the width of unsigned int.
 */

#include <stdint.h>  // for uint32_t, to get 32-bit-wide rotates, regardless of the size of int.
#include <limits.h>  // for CHAR_BIT

uint32_t rotl32 (uint32_t value, unsigned int count) {
    const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
    count &= mask;
    return (value << count) | (value >> (-count & mask));
}

uint32_t rotr32 (uint32_t value, unsigned int count) {
    const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
    count &= mask;
    return (value >> count) | (value << (-count & mask));
}

This safe and compiler-friendly implementation was developed by John Regehr,^[3] and further polished by Peter Cordes.^[4][5]

A simpler version is often seen when the count is limited to the range of 1 to 31 bits:

uint32_t rotl32 (uint32_t value, unsigned int count) {
    return value << count | value >> (32 - count);
}

This version is dangerous because if the count is 0 or 32, it asks for a 32-bit shift, which is undefined behaviour in the C language standard. However, it tends to work anyway, because most microprocessors implement value >> 32 as either a 32-bit shift (producing 0) or a 0-bit shift (producing the original value), and either one produces the correct result in this application.

Example

If the bit sequence 0001 0111 were subjected to a circular shift of one bit position... (see images below)

to the left would yield: 0010 1110 Left circular shift.

to the right would yield: 1000 1011. Right circular shift.

If the bit sequence 1001 0110 were subjected to the following operations:

Applications

Cyclic codes are a kind of block code with the property that the circular shift of a codeword will always yield another codeword. This motivates the following general definition: For a string s over an alphabet Σ, let shift(s) denote the set of circular shifts of s, and for a set L of strings, let shift(L) denote the set of all circular shifts of strings in L. If L is a cyclic code, then shift(L) ⊆ L; this is a necessary condition for L being a cyclic language. The operation shift(L) has been studied in formal language theory. For instance, if L is a context-free language, then shift(L) is again context-free.^[6][7] Also, if L is described by a regular expression of length n, there is a regular expression of length O(n³) describing shift(L).^[8]

See also

• Barrel shifter
• Bitwise operation
• Circulant
• Lyndon word
• Necklace — an object like a tuple but for which circular shifts are considered equivalent.

References