将 4 字节 int 交织到 8 字节 int
Interleave 4 byte ints to 8 byte int
我目前正在创建一个接受两个 4 字节无符号整数和 returns 一个 8 字节无符号长整数的函数。我试图将我的工作基于 this research 描述的方法,但我所有的尝试都没有成功。我正在处理的具体输入是:0x12345678
和 0xdeadbeef
,我要查找的结果是 0x12de34ad56be78ef
。这是我到目前为止的工作:
unsigned long interleave(uint32_t x, uint32_t y){
uint64_t result = 0;
int shift = 33;
for(int i = 64; i > 0; i-=16){
shift -= 8;
//printf("%d\n", i);
//printf("%d\n", shift);
result |= (x & i) << shift;
result |= (y & i) << (shift-1);
}
}
然而,这个函数一直返回 0xfffffffe
,这是不正确的。我正在使用以下方法打印和验证这些值:
printf("0x%x\n", z);
并且输入初始化如下:
uint32_t x = 0x12345678;
uint32_t y = 0xdeadbeef;
任何关于此主题的帮助将不胜感激,C 对我来说是一门非常困难的语言,位运算更是如此。
你可以这样做:
uint64_t interleave(uint32_t x, uint32_t y)
{
uint64_t z;
unsigned char *a = (unsigned char *)&x; // 1
unsigned char *b = (unsigned char *)&y; // 1
unsigned char *c = (unsigned char *)&z;
c[0] = a[0];
c[1] = b[0];
c[2] = a[1];
c[3] = b[1];
c[4] = a[2];
c[5] = b[2];
c[6] = a[3];
c[7] = b[3];
return z;
}
根据订购要求,在标有 1
的行上交换 a
和 b
。
带移位的版本,其中 y
的 LSB 始终是输出的 LSB,如您的示例所示,是:
uint64_t interleave(uint32_t x, uint32_t y)
{
return
(y & 0xFFull)
| (x & 0xFFull) << 8
| (y & 0xFF00ull) << 8
| (x & 0xFF00ull) << 16
| (y & 0xFF0000ull) << 16
| (x & 0xFF0000ull) << 24
| (y & 0xFF000000ull) << 24
| (x & 0xFF000000ull) << 32;
}
我试过的编译器似乎都没有很好地优化这两个版本,所以如果这是一个性能关键的情况,那么评论中的内联汇编建议可能是可行的方法。
使用位移位和按位运算(字节顺序无关):
uint64_t interleave(uint32_t x, uint32_t y){
uint64_t result = 0;
for(uint8_t i = 0; i < 4; i ++){
result |= ((x & (0xFFull << (8*i))) << (8*(i+1)));
result |= ((y & (0xFFull << (8*i))) << (8*i));
}
return result;
}
有指针(取决于字节顺序):
uint64_t interleave(uint32_t x, uint32_t y){
uint64_t result = 0;
uint8_t * x_ptr = (uint8_t *)&x;
uint8_t * y_ptr = (uint8_t *)&y;
uint8_t * r_ptr = (uint8_t *)&result;
for(uint8_t i = 0; i < 4; i++){
*(r_ptr++) = y_ptr[i];
*(r_ptr++) = x_ptr[i];
}
return result;
}
注意:此解决方案采用小端字节顺序
使用联合双关语。易于编译器优化。
#include <stdio.h>
#include <stdint.h>
#include <string.h>
typedef union
{
uint64_t u64;
struct
{
union
{
uint32_t a32;
uint8_t a8[4]
};
union
{
uint32_t b32;
uint8_t b8[4]
};
};
uint8_t u8[8];
}data_64;
uint64_t interleave(uint32_t a, uint32_t b)
{
data_64 in , out;
in.a32 = a;
in.b32 = b;
for(size_t index = 0; index < sizeof(a); index ++)
{
out.u8[index * 2 + 1] = in.a8[index];
out.u8[index * 2 ] = in.b8[index];
}
return out.u64;
}
int main(void)
{
printf("%llx\n", interleave(0x12345678U, 0xdeadbeefU)) ;
}
这可以在 interleaving bits 的基础上完成,但会跳过一些步骤,因此它只会交错字节。同样的想法:首先分几步展开字节,然后组合它们。
这是计划,用我惊人的手绘技巧来说明:
在 C 中(未测试):
// step 1, moving the top two bytes
uint64_t a = (((uint64_t)x & 0xFFFF0000) << 16) | (x & 0xFFFF);
// step 2, moving bytes 2 and 6
a = ((a & 0x00FF000000FF0000) << 8) | (a & 0x000000FF000000FF);
// same thing with y
uint64_t b = (((uint64_t)y & 0xFFFF0000) << 16) | (y & 0xFFFF);
b = ((b & 0x00FF000000FF0000) << 8) | (b & 0x000000FF000000FF);
// merge them
uint64_t result = (a << 8) | b;
有人建议使用 SSSE3 PSHUFB,它可以工作,但有一条指令可以一次性完成逐字节交织,punpcklbw。所以我们真正需要做的就是将值传入和传出向量寄存器,然后这条指令就会处理它。
未测试:
uint64_t interleave(uint32_t x, uint32_t y) {
__m128i xvec = _mm_cvtsi32_si128(x);
__m128i yvec = _mm_cvtsi32_si128(y);
__m128i interleaved = _mm_unpacklo_epi8(yvec, xvec);
return _mm_cvtsi128_si64(interleaved);
}
我目前正在创建一个接受两个 4 字节无符号整数和 returns 一个 8 字节无符号长整数的函数。我试图将我的工作基于 this research 描述的方法,但我所有的尝试都没有成功。我正在处理的具体输入是:0x12345678
和 0xdeadbeef
,我要查找的结果是 0x12de34ad56be78ef
。这是我到目前为止的工作:
unsigned long interleave(uint32_t x, uint32_t y){
uint64_t result = 0;
int shift = 33;
for(int i = 64; i > 0; i-=16){
shift -= 8;
//printf("%d\n", i);
//printf("%d\n", shift);
result |= (x & i) << shift;
result |= (y & i) << (shift-1);
}
}
然而,这个函数一直返回 0xfffffffe
,这是不正确的。我正在使用以下方法打印和验证这些值:
printf("0x%x\n", z);
并且输入初始化如下:
uint32_t x = 0x12345678;
uint32_t y = 0xdeadbeef;
任何关于此主题的帮助将不胜感激,C 对我来说是一门非常困难的语言,位运算更是如此。
你可以这样做:
uint64_t interleave(uint32_t x, uint32_t y)
{
uint64_t z;
unsigned char *a = (unsigned char *)&x; // 1
unsigned char *b = (unsigned char *)&y; // 1
unsigned char *c = (unsigned char *)&z;
c[0] = a[0];
c[1] = b[0];
c[2] = a[1];
c[3] = b[1];
c[4] = a[2];
c[5] = b[2];
c[6] = a[3];
c[7] = b[3];
return z;
}
根据订购要求,在标有 1
的行上交换 a
和 b
。
带移位的版本,其中 y
的 LSB 始终是输出的 LSB,如您的示例所示,是:
uint64_t interleave(uint32_t x, uint32_t y)
{
return
(y & 0xFFull)
| (x & 0xFFull) << 8
| (y & 0xFF00ull) << 8
| (x & 0xFF00ull) << 16
| (y & 0xFF0000ull) << 16
| (x & 0xFF0000ull) << 24
| (y & 0xFF000000ull) << 24
| (x & 0xFF000000ull) << 32;
}
我试过的编译器似乎都没有很好地优化这两个版本,所以如果这是一个性能关键的情况,那么评论中的内联汇编建议可能是可行的方法。
使用位移位和按位运算(字节顺序无关):
uint64_t interleave(uint32_t x, uint32_t y){
uint64_t result = 0;
for(uint8_t i = 0; i < 4; i ++){
result |= ((x & (0xFFull << (8*i))) << (8*(i+1)));
result |= ((y & (0xFFull << (8*i))) << (8*i));
}
return result;
}
有指针(取决于字节顺序):
uint64_t interleave(uint32_t x, uint32_t y){
uint64_t result = 0;
uint8_t * x_ptr = (uint8_t *)&x;
uint8_t * y_ptr = (uint8_t *)&y;
uint8_t * r_ptr = (uint8_t *)&result;
for(uint8_t i = 0; i < 4; i++){
*(r_ptr++) = y_ptr[i];
*(r_ptr++) = x_ptr[i];
}
return result;
}
注意:此解决方案采用小端字节顺序
使用联合双关语。易于编译器优化。
#include <stdio.h>
#include <stdint.h>
#include <string.h>
typedef union
{
uint64_t u64;
struct
{
union
{
uint32_t a32;
uint8_t a8[4]
};
union
{
uint32_t b32;
uint8_t b8[4]
};
};
uint8_t u8[8];
}data_64;
uint64_t interleave(uint32_t a, uint32_t b)
{
data_64 in , out;
in.a32 = a;
in.b32 = b;
for(size_t index = 0; index < sizeof(a); index ++)
{
out.u8[index * 2 + 1] = in.a8[index];
out.u8[index * 2 ] = in.b8[index];
}
return out.u64;
}
int main(void)
{
printf("%llx\n", interleave(0x12345678U, 0xdeadbeefU)) ;
}
这可以在 interleaving bits 的基础上完成,但会跳过一些步骤,因此它只会交错字节。同样的想法:首先分几步展开字节,然后组合它们。
这是计划,用我惊人的手绘技巧来说明:
在 C 中(未测试):
// step 1, moving the top two bytes
uint64_t a = (((uint64_t)x & 0xFFFF0000) << 16) | (x & 0xFFFF);
// step 2, moving bytes 2 and 6
a = ((a & 0x00FF000000FF0000) << 8) | (a & 0x000000FF000000FF);
// same thing with y
uint64_t b = (((uint64_t)y & 0xFFFF0000) << 16) | (y & 0xFFFF);
b = ((b & 0x00FF000000FF0000) << 8) | (b & 0x000000FF000000FF);
// merge them
uint64_t result = (a << 8) | b;
有人建议使用 SSSE3 PSHUFB,它可以工作,但有一条指令可以一次性完成逐字节交织,punpcklbw。所以我们真正需要做的就是将值传入和传出向量寄存器,然后这条指令就会处理它。
未测试:
uint64_t interleave(uint32_t x, uint32_t y) {
__m128i xvec = _mm_cvtsi32_si128(x);
__m128i yvec = _mm_cvtsi32_si128(y);
__m128i interleaved = _mm_unpacklo_epi8(yvec, xvec);
return _mm_cvtsi128_si64(interleaved);
}