Lookup Table 在 NEON 中的處理

在 SIMD Programming 中由於希望能夠每個 lane 有一致的行為,
因此有一些事情是不容易達到的
而 Lookup Table (LUT) 即是其中之一

但若是特定條件之下, 還是有可能透過 NEON 加速
而這個直接前提是 8bit LUT (當然藉此方法可以做 8bit 轉 16bit LUT)
在 ARMv7 中 NEON 就提供兩個指令 - VTBL 與 VTBX 作為有限度的 LUT功能使用
兩者提供了同時能夠處理 8筆 8bit 資料的 LUT 動作 (64bit NEON register)所使用的 table 最多為 4個 64bit NEON 暫存器
這也就是說 index 範圍為 < 8x4 = 32
而 VTBL 與 VTBX 兩者的差異是:
VTBL 對於 index 超出範圍的 lane 輸出值為 0
VTBX 對於 index 超出範圍的 lane 並不更動

值得慶幸的是在 ARMv8 中將這兩者寬度加倍
也就是一次可以查找 16筆 8bit 資料的 LUT 動作 ( 128bit NEON register)
table 也變為 4個 128bit NEON register
因此 index 合法範圍為 < 16x4 =64
以下就只針對重點部分演示:

以下的 code 即為常見的 LUT 方式

#define TEST_W 4096
#define TEST_H 3072
unsigned char *table = (unsigned char*)malloc(256); 
unsigned char *buf_0 = (unsigned char*)malloc(TEST_W*TEST_H); 
unsigned char *buf_1 = (unsigned char*)malloc(TEST_W*TEST_H);  
// buffer filled with random numbers
...
for(int i = 0; i < TEST_W*TEST_H; i++){
    buf_0[i] = table[buf_0[i]];
} 

以下為 ARMv8 的實作方式

uint8x16x4_t vlut_tbl[4]; 
//table initialization
for(int i = 0; i < 4; i++){
    vlut_tbl[i].val[0] = vld1q_u8(table+i*64);
    vlut_tbl[i].val[1] = vld1q_u8(table+i*64+16);
    vlut_tbl[i].val[2] = vld1q_u8(table+i*64+32);
    vlut_tbl[i].val[3] = vld1q_u8(table+i*64+48);
} 
//SIMD LUT
for(int i = 0; i < TEST_W*TEST_H; i+=16){ 
    uint8x16_t vlut_idx = vld1q_u8(buf_1 + i);
    uint8x16_t vlut_val = vqtbl4q_u8(vlut_tbl[0], vlut_idx); 
    vlut_val = vqtbx4q_u8(vlut_val, vlut_tbl[1], vsubq_u8(vlut_idx, vdupq_n_u8(64)));
    vlut_val = vqtbx4q_u8(vlut_val, vlut_tbl[2], vsubq_u8(vlut_idx, vdupq_n_u8(128)));
    vlut_val = vqtbx4q_u8(vlut_val, vlut_tbl[3], vsubq_u8(vlut_idx, vdupq_n_u8(192)));
    vst1q_u8(buf_1 + i, vlut_val);
}

透過手邊的 Xperia M4 (Snapdragon 615, Cortex-A53 octa cores)平台測試
C-LUT : 58271 us, NEON-LUT : 21702 us

得到了 2.7X 的效能