我正在尝试将二进制文件加载到内存中。它具有特定的编码和有限的字母表,我的意思是每两位代表一个整数值(00 -> 0、01 -> 1、10 -> 2 和 11 -> 3),仅此而已。
现在 11 或基本上 3 代表缺失值。我可以使用 BMI2 解包并将缺失设置为零并填充主矩阵(完整数据没有缺失),但想创建一个映射或基本上是稀疏数组来存储缺失值的索引。
下面是我目前如何做的演示代码(使用 BMI2),因为与 2 字节解包相比,我没有发现 avx2 或其他方法有益。如果您不同意,请告诉我!
所以真正的问题是:如何result_and_mask
在不使用简单循环的情况下使用此处的变量将字节索引存储在数组中?
只是为了添加更多上下文,这是在一个循环中发生的,该循环使用 memmap 读取一组数据并进行解包和存储。
#include <immintrin.h>
#include <stdio.h>
#include <inttypes.h>
void printBits(size_t const size, void const * const ptr, int put)
{
unsigned char *b = (unsigned char*) ptr;
unsigned char byte;
int i, j;
for (i = size-1; i >= 0; i--) {
for (j = 7; j >= 0; j--) {
byte = (b[i] >> j) & 1;
if (byte == 0) {
printf(".");
} else{
printf("1");
}
// printf("%u", byte);
if (j % 2 == 0){
printf(" ");
}
}
if (put != 0) printf("|");
}
if (put != 0) puts("");
}
int main() {
uint16_t ww = 0xCA07;
uint64_t result;
const int PRINT_LINE = 1;
# define S_CAST(type, val) ((type)(val))
static const uintptr_t kMask0303 = (~S_CAST(uintptr_t, 0)) / 85;
static const uintptr_t kMask1111 = (~S_CAST(uintptr_t, 0)) / 15;
printf("ww : ");
printBits(sizeof(ww), &ww, PRINT_LINE);
printf("mask03: ");
printBits(sizeof(kMask0303), &kMask0303, PRINT_LINE);
printf("result: ");
result = _pdep_u64(ww, kMask0303);
printBits(sizeof(result), &result, PRINT_LINE);
uint64_t result_shift = result >> 1;
printf("shift : ");
printBits(sizeof(result_shift), &result_shift, PRINT_LINE);
uint64_t result_and = result & result_shift;
printf("and : ");
printBits(sizeof(result_and), &result_and, PRINT_LINE);
printf("mask01: ");
printBits(sizeof(kMask1111), &kMask1111, PRINT_LINE);
uint64_t result_and_mask = result_and & kMask1111;
printf("miss : ");
printBits(sizeof(result_and_mask), &result_and_mask, PRINT_LINE);
// printf("sub : ");
// uint64_t result_and_mask_mult = result_and_mask * 3;
// printBits(sizeof(result_and_mask_mult), &result_and_mask_mult, PRINT_LINE);
// printf("fin : ");
// uint64_t final = result - result_and_mask_mult;
// printBits(sizeof(final), &final, PRINT_LINE);
}
示例输出:
ww : 11 .. 1. 1. |.. .. .1 11 |
mask03: .. .. .. 11 |.. .. .. 11 |.. .. .. 11 |.. .. .. 11 |.. .. .. 11 |.. .. .. 11 |.. .. .. 11 |.. .. .. 11 |
result: .. .. .. 11 |.. .. .. .. |.. .. .. 1. |.. .. .. 1. |.. .. .. .. |.. .. .. .. |.. .. .. .1 |.. .. .. 11 |
shift : .. .. .. .1 |1. .. .. .. |.. .. .. .1 |.. .. .. .1 |.. .. .. .. |.. .. .. .. |.. .. .. .. |1. .. .. .1 |
and : .. .. .. .1 |.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .1 |
mask01: .. .1 .. .1 |.. .1 .. .1 |.. .1 .. .1 |.. .1 .. .1 |.. .1 .. .1 |.. .1 .. .1 |.. .1 .. .1 |.. .1 .. .1 |
miss : .. .. .. .1 |.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .1 |
更新:进一步说明
- 所需的输出是索引的左压缩列表。在上面的例子中,我需要 0,7。基本上,我有一个指向数组中下一个空点的指针来存储缺失值的索引,比如说指向元素 100(到目前为止找到了 99 个缺失值),现在我正在读取索引 1000 处的 col 元素,所以我想做的是将 (1000 + 7, 1000 + 0, 顺序无关紧要) 添加到缺少的数组中。现在指针将指向 102。
- 该平台将具有最低 avx2,这是一个科学程序,主要用于云和/或 HPC,CPU 主要是英特尔和 Skylake 向上(avx-512 很常见),所以我假设 avx2 至少存在。
更新:用于解包的 AVX2 演示
这是我第一次尝试使用 avx2 进行解包:
#include <immintrin.h>
#include <stdio.h>
#include <inttypes.h>
#include <stdint.h>
#include <string.h> // for memset
void printBits(size_t const size, void const * const ptr, int put)
{
unsigned char *b = (unsigned char*) ptr;
unsigned char byte;
int i, j;
for (i = size-1; i >= 0; i--) {
for (j = 7; j >= 0; j--) {
byte = (b[i] >> j) & 1;
if (byte == 0) {
printf(".");
} else{
printf("1");
}
// printf("%u", byte);
if (j % 2 == 0){
printf(" ");
}
}
if (put != 0) printf("|");
}
if (put != 0) puts("");
}
int main() {
uint64_t x = 0x1360EA787654321;
const int PRINT_LINE = 1;
// mask: where to put each byte
static const char mask1a[32] = {
0x00, 0x00, 0x00, 0x00,
0x01, 0x01, 0x01, 0x01,
0x02, 0x02, 0x02, 0x02,
0x03, 0x03, 0x03, 0x03,
0x04, 0x04, 0x04, 0x04,
0x05, 0x05, 0x05, 0x05,
0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07
};
static const char mask2a[32] = {
0x03, 0x0c, 0x30, 0xC0,
0x03, 0x0c, 0x30, 0xC0,
0x03, 0x0c, 0x30, 0xC0,
0x03, 0x0c, 0x30, 0xC0,
0x03, 0x0c, 0x30, 0xC0,
0x03, 0x0c, 0x30, 0xC0,
0x03, 0x0c, 0x30, 0xC0,
0x03, 0x0c, 0x30, 0xC0,
};
static const char mask3a[32] = {
0x00, 0x04, 0x08, 0x0C,
0x01, 0x05, 0x09, 0x0D,
0x02, 0x06, 0x0A, 0x0E,
0x03, 0x07, 0x0B, 0x0F,
0x00, 0x04, 0x08, 0x0C,
0x01, 0x05, 0x09, 0x0D,
0x02, 0x06, 0x0A, 0x0E,
0x03, 0x07, 0x0B, 0x0F,
};
static const char mask4a[32] = {
0x00, 0x00, 0x00, 0x00,
0x02, 0x00, 0x00, 0x00,
0x04, 0x00, 0x00, 0x00,
0x06, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00,
0x02, 0x00, 0x00, 0x00,
0x04, 0x00, 0x00, 0x00,
0x06, 0x00, 0x00, 0x00,
};
unsigned char out[32];
__m256i mask2 = _mm256_loadu_si256((__m256i*)mask2a);
__m256i mask1 = _mm256_loadu_si256((__m256i*)mask1a);
__m256i mask3 = _mm256_loadu_si256((__m256i*)mask3a);
__m256i mask4 = _mm256_loadu_si256((__m256i*)mask4a);
union combine { __m128i reg; uint8_t value; };
const union combine THREE = {.value = 3};
__m256i mult3 = _mm256_broadcastb_epi8(THREE.reg);
__m256i y = _mm256_set1_epi64x(x);
__m256i z = _mm256_shuffle_epi8(y,mask1);
z = _mm256_and_si256(z,mask2);
_mm256_storeu_si256((__m256i*)out,z);
printf("\nX : ");
printBits(sizeof(x), &x, PRINT_LINE);
for(int i=28; i>=0; i-=4) {
uint8_t orig = *((uint8_t *)&(x) + (i / 4));
uint32_t num = *(uint32_t *)&out[i];
printBits(sizeof(orig), &orig, 0);
printf(" ---> ");
printBits(sizeof(num), &num, PRINT_LINE);
} printf("\n");
printf("Result with Missing: \n");
for(int i=28; i>=0; i-=4) {
uint32_t num = *(uint32_t *)&out[i];
printBits(sizeof(num), &num, PRINT_LINE);
} printf("\n");
z = _mm256_shuffle_epi8(z, mask3);
_mm256_storeu_si256((__m256i*)out,z);
printf("Transpose: \n");
for(int i=28; i>=0; i-=4) {
uint32_t num = *(uint32_t *)&out[i];
printBits(sizeof(num), &num, PRINT_LINE);
} printf("\n");
z = _mm256_srlv_epi32(z, mask4);
_mm256_storeu_si256((__m256i*)out,z);
printf("Shift: \n");
for(int i=28; i>=0; i-=4) {
uint32_t num = *(uint32_t *)&out[i];
printBits(sizeof(num), &num, PRINT_LINE);
} printf("\n");
z = _mm256_shuffle_epi8(z, mask3);
_mm256_storeu_si256((__m256i*)out,z);
printf("Transpose: \n");
for(int i=28; i>=0; i-=4) {
uint32_t num = *(uint32_t *)&out[i];
printBits(sizeof(num), &num, PRINT_LINE);
} printf("\n");
__m256i z_shifted = _mm256_srli_epi32(z, 1);
_mm256_storeu_si256((__m256i*)out,z_shifted);
printf("Shifted: \n");
for(int i=28; i>=0; i-=4) {
uint32_t num = *(uint32_t *)&out[i];
printBits(sizeof(num), &num, PRINT_LINE);
} printf("\n");
__m256i z_and = _mm256_and_si256(z, z_shifted);
_mm256_storeu_si256((__m256i*)out,z_and);
printf("Bytes with Missing value (11): \n");
for(int i=28; i>=0; i-=4) {
uint32_t num = *(uint32_t *)&out[i];
printBits(sizeof(num), &num, PRINT_LINE);
} printf("\n");
__m256i z_and_shift_back = _mm256_slli_epi32(z_and, 1);
_mm256_storeu_si256((__m256i*)out,z_and_shift_back);
printf("SHIFT BACK: \n");
for(int i=28; i>=0; i-=4) {
uint32_t num = *(uint32_t *)&out[i];
printBits(sizeof(num), &num, PRINT_LINE);
} printf("\n");
__m256i z_and_shift_back_or = _mm256_or_si256(z_and, z_and_shift_back);
_mm256_storeu_si256((__m256i*)out,z_and_shift_back_or);
printf("OR: \n");
for(int i=28; i>=0; i-=4) {
uint32_t num = *(uint32_t *)&out[i];
printBits(sizeof(num), &num, PRINT_LINE);
} printf("\n");
__m256i z_sub = _mm256_sub_epi8(z, z_and_shift_back_or);
_mm256_storeu_si256((__m256i*)out,z_sub);
printf("Result with Missing set to zero: \n");
for(int i=28; i>=0; i-=4) {
uint32_t num = *(uint32_t *)&out[i];
printBits(sizeof(num), &num, PRINT_LINE);
} printf("\n");
}
输出:
X : .. .. .. .1 |.. 11 .1 1. |.. .. 11 1. |1. 1. .1 11 |1. .. .1 11 |.1 1. .1 .1 |.1 .. .. 11 |.. 1. .. .1 |
.. .. .. .1 ---> .. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .1 |
.. 11 .1 1. ---> .. .. .. .. |.. 11 .. .. |.. .. .1 .. |.. .. .. 1. |
.. .. 11 1. ---> .. .. .. .. |.. .. .. .. |.. .. 11 .. |.. .. .. 1. |
1. 1. .1 11 ---> 1. .. .. .. |.. 1. .. .. |.. .. .1 .. |.. .. .. 11 |
1. .. .1 11 ---> 1. .. .. .. |.. .. .. .. |.. .. .1 .. |.. .. .. 11 |
.1 1. .1 .1 ---> .1 .. .. .. |.. 1. .. .. |.. .. .1 .. |.. .. .. .1 |
.1 .. .. 11 ---> .1 .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. 11 |
.. 1. .. .1 ---> .. .. .. .. |.. 1. .. .. |.. .. .. .. |.. .. .. .1 |
Result with Missing:
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .1 |
.. .. .. .. |.. 11 .. .. |.. .. .1 .. |.. .. .. 1. |
.. .. .. .. |.. .. .. .. |.. .. 11 .. |.. .. .. 1. |
1. .. .. .. |.. 1. .. .. |.. .. .1 .. |.. .. .. 11 |
1. .. .. .. |.. .. .. .. |.. .. .1 .. |.. .. .. 11 |
.1 .. .. .. |.. 1. .. .. |.. .. .1 .. |.. .. .. .1 |
.1 .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. 11 |
.. .. .. .. |.. 1. .. .. |.. .. .. .. |.. .. .. .1 |
Transpose:
.. .. .. .. |.. .. .. .. |.. .. .. .. |1. .. .. .. |
.. .. .. .. |.. 11 .. .. |.. .. .. .. |.. 1. .. .. |
.. .. .. .. |.. .. .1 .. |.. .. 11 .. |.. .. .1 .. |
.. .. .. .1 |.. .. .. 1. |.. .. .. 1. |.. .. .. 11 |
1. .. .. .. |.1 .. .. .. |.1 .. .. .. |.. .. .. .. |
.. .. .. .. |.. 1. .. .. |.. .. .. .. |.. 1. .. .. |
.. .. .1 .. |.. .. .1 .. |.. .. .. .. |.. .. .. .. |
.. .. .. 11 |.. .. .. .1 |.. .. .. 11 |.. .. .. .1 |
Shift:
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. 1. |
.. .. .. .. |.. .. .. 11 |.. .. .. .. |.. .. .. 1. |
.. .. .. .. |.. .. .. .1 |.. .. .. 11 |.. .. .. .1 |
.. .. .. .1 |.. .. .. 1. |.. .. .. 1. |.. .. .. 11 |
.. .. .. 1. |.. .. .. .1 |.. .. .. .1 |.. .. .. .. |
.. .. .. .. |.. .. .. 1. |.. .. .. .. |.. .. .. 1. |
.. .. .. .1 |.. .. .. .1 |.. .. .. .. |.. .. .. .. |
.. .. .. 11 |.. .. .. .1 |.. .. .. 11 |.. .. .. .1 |
Transpose:
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .1 |
.. .. .. .. |.. .. .. 11 |.. .. .. .1 |.. .. .. 1. |
.. .. .. .. |.. .. .. .. |.. .. .. 11 |.. .. .. 1. |
.. .. .. 1. |.. .. .. 1. |.. .. .. .1 |.. .. .. 11 |
.. .. .. 1. |.. .. .. .. |.. .. .. .1 |.. .. .. 11 |
.. .. .. .1 |.. .. .. 1. |.. .. .. .1 |.. .. .. .1 |
.. .. .. .1 |.. .. .. .. |.. .. .. .. |.. .. .. 11 |
.. .. .. .. |.. .. .. 1. |.. .. .. .. |.. .. .. .1 |
Shifted:
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. .1 |1. .. .. .. |1. .. .. .1 |
.. .. .. .. |.. .. .. .. |.. .. .. .1 |1. .. .. .1 |
.. .. .. .1 |.. .. .. .1 |.. .. .. .. |1. .. .. .1 |
.. .. .. .1 |.. .. .. .. |.. .. .. .. |1. .. .. .1 |
.. .. .. .. |1. .. .. .1 |.. .. .. .. |1. .. .. .. |
.. .. .. .. |1. .. .. .. |.. .. .. .. |.. .. .. .1 |
.. .. .. .. |.. .. .. .1 |.. .. .. .. |.. .. .. .. |
Bytes with Missing value (11):
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. .1 |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. .. |.. .. .. .1 |.. .. .. .. |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .1 |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .1 |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .1 |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |
SHIFT BACK:
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. 1. |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. .. |.. .. .. 1. |.. .. .. .. |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. 1. |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. 1. |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. 1. |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |
OR:
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. 11 |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. .. |.. .. .. 11 |.. .. .. .. |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. 11 |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. 11 |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. 11 |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .. |
Result with Missing set to zero:
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. .1 |
.. .. .. .. |.. .. .. .. |.. .. .. .1 |.. .. .. 1. |
.. .. .. .. |.. .. .. .. |.. .. .. .. |.. .. .. 1. |
.. .. .. 1. |.. .. .. 1. |.. .. .. .1 |.. .. .. .. |
.. .. .. 1. |.. .. .. .. |.. .. .. .1 |.. .. .. .. |
.. .. .. .1 |.. .. .. 1. |.. .. .. .1 |.. .. .. .1 |
.. .. .. .1 |.. .. .. .. |.. .. .. .. |.. .. .. .. |
.. .. .. .. |.. .. .. 1. |.. .. .. .. |.. .. .. .1 |
我正在使用结果而不会丢失来存储完整的数组。现在我想使用“缺少值的字节 (11)”来获取左压缩索引以将索引存储到稀疏数组中。