The XOP instruction set does provide _mm_rot_epi8()
(which is NOT Microsoft-specific; it is also available in GCC since 4.4 or earlier, and should be available in recent clang, too). It can be used to perform the desired task in 128-bit units. Unfortunately, I don't have a CPU with XOP support, so I cannot test that.
On AVX2, splitting the 256-bit register into two halves, one containing even bytes, and the other odd bytes shifted right 8 bits, allows a 16-bit vector multiply to do the trick. Given constants (using GCC 64-bit component array format)
static const __m256i epi16_highbyte = { 0xFF00FF00FF00FF00ULL,
0xFF00FF00FF00FF00ULL,
0xFF00FF00FF00FF00ULL,
0xFF00FF00FF00FF00ULL };
static const __m256i epi16_lowbyte = { 0x00FF00FF00FF00FFULL,
0x00FF00FF00FF00FFULL,
0x00FF00FF00FF00FFULL,
0x00FF00FF00FF00FFULL };
static const __m256i epi16_oddmuls = { 0x4040101004040101ULL,
0x4040101004040101ULL,
0x4040101004040101ULL,
0x4040101004040101ULL };
static const __m256i epi16_evenmuls = { 0x8080202008080202ULL,
0x8080202008080202ULL,
0x8080202008080202ULL,
0x8080202008080202ULL };
the rotation operation can be written as
__m256i byteshift(__m256i value)
{
return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_lowbyte), epi16_oddmuls), 8),
_mm256_and_si256(_mm256_mullo_epi16(_mm256_and_si256(_mm256_srai_epi16(value, 8), epi16_lowbyte), epi16_evenmuls), epi16_highbyte));
}
This has been verified to yield correct results on Intel Core i5-4200U using GCC-4.8.4. As an example, the input vector (as a single 256-bit hexadecimal number)
88 87 86 85 84 83 82 81 38 37 36 35 34 33 32 31 28 27 26 25 24 23 22 21 FF FE FD FC FB FA F9 F8
gets rotated into
44 E1 D0 58 24 0E 05 81 1C CD C6 53 A1 CC 64 31 14 C9 C4 52 21 8C 44 21 FF BF BF CF DF EB F3 F8
where the leftmost octet is rotated left by 7 bits, next 6 bits, and so on; seventh octet is unchanged, eighth octet is rotated by 7 bits, and so on, for all 32 octets.
I am not sure if the above function definition compiles to optimal machine code -- that depends on the compiler --, but I'm certainly happy with its performance.
Since you probably dislike the above concise format for the function, here it is in procedural, expanded form:
static __m256i byteshift(__m256i value)
{
__m256i low, high;
high = _mm256_srai_epi16(value, 8);
low = _mm256_and_si256(value, epi16_lowbyte);
high = _mm256_and_si256(high, epi16_lowbyte);
low = _mm256_mullo_epi16(low, epi16_lowmuls);
high = _mm256_mullo_epi16(high, epi16_highmuls);
low = _mm256_srli_epi16(low, 8);
high = _mm256_and_si256(high, epi16_highbyte);
return _mm256_or_si256(low, high);
}
In a comment, Peter Cordes suggested replacing the srai
+and
with an srli
, and possibly the final and
+or
with a blendv
. The former makes a lot of sense, as it is purely an optimization, but the latter may not (yet, on current Intel CPUs!) actually be faster.
I tried some microbenchmarking, but was unable to get reliable results. I typically use the TSC on x86-64, and take the median of a few hundred thousand tests using inputs and outputs stored to an array.
I think it is most useful if I will just list the variants here, so any user requiring such a function can make some benchmarks on their real-world workloads, and test to see if there is any measurable difference.
I also agree with his suggestion to use odd
and even
instead of high
and low
, but note that since the first element in a vector is numbered element 0, the first element is even, the second odd, and so on.
#include <immintrin.h>
static const __m256i epi16_oddmask = { 0xFF00FF00FF00FF00ULL,
0xFF00FF00FF00FF00ULL,
0xFF00FF00FF00FF00ULL,
0xFF00FF00FF00FF00ULL };
static const __m256i epi16_evenmask = { 0x00FF00FF00FF00FFULL,
0x00FF00FF00FF00FFULL,
0x00FF00FF00FF00FFULL,
0x00FF00FF00FF00FFULL };
static const __m256i epi16_evenmuls = { 0x4040101004040101ULL,
0x4040101004040101ULL,
0x4040101004040101ULL,
0x4040101004040101ULL };
static const __m256i epi16_oddmuls = { 0x8080202008080202ULL,
0x8080202008080202ULL,
0x8080202008080202ULL,
0x8080202008080202ULL };
/* Original version suggested by Nominal Animal. */
__m256i original(__m256i value)
{
return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_evenmask), epi16_evenmuls), 8),
_mm256_and_si256(_mm256_mullo_epi16(_mm256_and_si256(_mm256_srai_epi16(value, 8), epi16_evenmask), epi16_oddmuls), epi16_oddmask));
}
/* Optimized as suggested by Peter Cordes, without blendv */
__m256i no_blendv(__m256i value)
{
return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_evenmask), epi16_evenmuls), 8),
_mm256_and_si256(_mm256_mullo_epi16(_mm256_srli_epi16(value, 8), epi16_oddmuls), epi16_oddmask));
}
/* Optimized as suggested by Peter Cordes, with blendv.
* This is the recommended version. */
__m256i optimized(__m256i value)
{
return _mm256_blendv_epi8(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value, epi16_evenmask), epi16_evenmuls), 8),
_mm256_mullo_epi16(_mm256_srli_epi16(value, 8), epi16_oddmuls), epi16_oddmask);
}
Here are the same functions written in a way that shows the individual operations. Although it does not affect sane compilers at all, I've marked the function parameter and each temporary value const
, so that it is obvious how you can insert each into a subsequent expression, to simplify the functions to their above concise forms.
__m256i original_verbose(const __m256i value)
{
const __m256i odd1 = _mm256_srai_epi16(value, 8);
const __m256i even1 = _mm256_and_si256(value, epi16_evenmask);
const __m256i odd2 = _mm256_and_si256(odd1, epi16_evenmask);
const __m256i even2 = _mm256_mullo_epi16(even1, epi16_evenmuls);
const __m256i odd3 = _mm256_mullo_epi16(odd3, epi16_oddmuls);
const __m256i even3 = _mm256_srli_epi16(even3, 8);
const __m256i odd4 = _mm256_and_si256(odd3, epi16_oddmask);
return _mm256_or_si256(even3, odd4);
}
__m256i no_blendv_verbose(const __m256i value)
{
const __m256i even1 = _mm256_and_si256(value, epi16_evenmask);
const __m256i odd1 = _mm256_srli_epi16(value, 8);
const __m256i even2 = _mm256_mullo_epi16(even1, epi16_evenmuls);
const __m256i odd2 = _mm256_mullo_epi16(odd1, epi16_oddmuls);
const __m256i even3 = _mm256_srli_epi16(even2, 8);
const __m256i odd3 = _mm256_and_si256(odd2, epi16_oddmask);
return _mm256_or_si256(even3, odd3);
}
__m256i optimized_verbose(const __m256i value)
{
const __m256i even1 = _mm256_and_si256(value, epi16_evenmask);
const __m256i odd1 = _mm256_srli_epi16(value, 8);
const __m256i even2 = _mm256_mullo_epi16(even1, epi16_evenmuls);
const __m256i odd2 = _mm256_mullo_epi16(odd1, epi16_oddmuls);
const __m256i even3 = _mm256_srli_epi16(even2, 8);
return _mm256_blendv_epi8(even3, odd2, epi16_oddmask);
}
I personally do write my test functions initially in their above verbose forms, as forming the concise version is a trivial set of copy-pasting. I do, however, testing both versions to verify against introducing any errors, and keeping the verbose version accessible (as a comment or so), because the concise versions are basically write-only. It is much easier to edit the verbose version, then simplify it to the concise form, than trying to edit the concise version.