Как я могу создать 256-битную маску - PullRequest
Новая
       95

Как я могу создать 256-битную маску

1 голос
/ 15 апреля 2019

У меня есть массив uint64_t [4], и мне нужно сгенерировать маску, такую, чтобы массив, если бы он был 256-битным целым, равнялся (1 << w) - 1, где w идет от 1до 256. </p>

Лучшее, что я придумал, - это безветвление, но оно требует МНОГИХ инструкций.Это в Zig, потому что Clang, кажется, не выставляет насыщающее вычитание llvm.http://localhost:10240/z/g8h1rV

Есть ли лучший способ сделать это? 

var mask: [4]u64 = undefined;
for (mask) |_, i|
    mask[i] = 0xffffffffffffffff;
mask[3] ^= ((u64(1) << @intCast(u6, (inner % 64) + 1)) - 1) << @intCast(u6, 64 - (inner % 64));
mask[2] ^= ((u64(1) << @intCast(u6, (@satSub(u32, inner, 64) % 64) + 1)) - 1) << @intCast(u6, 64 - (inner % 64));
mask[1] ^= ((u64(1) << @intCast(u6, (@satSub(u32, inner, 128) % 64) + 1)) - 1) << @intCast(u6, 64 - (inner % 64));
mask[0] ^= ((u64(1) << @intCast(u6, (@satSub(u32, inner, 192) % 64) + 1)) - 1) << @intCast(u6, 64 - (inner % 64));

1 Ответ

2 голосов
/ 16 апреля 2019

Вы ориентируетесь на x86-64 с AVX2 для 256-битных векторов? Я подумал, что это интересный случай для ответа.

Если это так, вы можете сделать это в нескольких инструкциях, используя насыщающее вычитание и переменное число смещений.

x86 SIMD сдвиги как vpsrlvq насыщают счет сдвига , сдвигая все биты, когда счет>> = ширина элемента. В отличие от целочисленных сдвигов счетчик сдвигов маскируется (и, следовательно, оборачивается).

Для самого низкого элемента u64, начиная со всех единиц, нам нужно оставить его неизменным для bitpos> = 64. Или для меньших битовых позиций, сдвинуть его вправо на 64-bitpos , Беззнаковое вычитающее насыщение выглядит как способ, как вы заметили, создать отсчет сдвига 0 для больших битовых постов. Но x86 имеет только SIMD-насыщающее вычитание, и только для байтов или элементов слова. Но если мы не заботимся о битовых позициях> 256, это нормально, мы можем использовать 16-битные элементы внизу каждого u64, и позволить 0-0 произойти в остальной части u64.

Ваш код выглядит довольно сложным, создавая (1<<n) - 1 и XORing. Я думаю, что намного проще просто использовать переменное число для элементов 0xFFFF...FF напрямую.

Я не знаю Зига, поэтому делай все, что тебе нужно, чтобы заставить его излучать асм вот так. Надеюсь, это полезно, потому что вы пометили эту ; должно быть легко перевести на встроенные для C или Zig, если они есть. 

default rel
section .rodata
shift_offsets:  dw  64, 128, 192, 256        ; 16-bit elements, to be loaded with zero-extension to 64

section .text
pos_to_mask256:
    vpmovzxwq   ymm2, [shift_offsets]      ; _mm256_set1_epi64x(256, 192, 128, 64)
    vpcmpeqd    ymm1, ymm1,ymm1            ; ymm1 = all-ones
                                  ; set up vector constants, can be hoisted

    vmovd         xmm0, edi
    vpbroadcastq  ymm0, xmm0           ; ymm0 = _mm256_set1_epi64(bitpos)

    vpsubusw      ymm0, ymm2, ymm0     ; ymm0 = {256,192,128,64}-bitpos with unsigned saturation
    vpsrlvq       ymm0, ymm1, ymm0     ; mask[i] >>= count, where counts >= 64 create 0s.

    ret

Если входное целое число начинается в памяти, вы, конечно, можете эффективно транслировать его прямо в регистр ymm.

Вектор смещений сдвига, конечно, можно вывести из цикла, как и все единицы.

При входе = 77 старшие 2 элемента обнуляются сдвигами 256-77 = 179 и 192-77 = 115 бит. Протестировано с NASM + GDB для EDI = 77, и результат равен 

(gdb) p /x $ymm0.v4_int64
{0xffffffffffffffff, 0x1fff, 0x0, 0x0}

GDB сначала печатает нижний элемент, в отличие от нотации / диаграмм Intel. Этот вектор на самом деле равен 0, 0, 0x1fff, 0xffffffffffffffff, то есть 64 + 13 = 77 единиц, а все остальные нули. Другие тестовые случаи

  • edi=0: маска = все ноль
  • edi=1: маска = 1
  • ...: mask = edi один бит внизу, затем нули
  • edi=255: mask = все единицы, кроме верхнего бита верхнего элемента
  • edi=256: маска = все единицы
  • edi>256: маска = все единицы. (вычитание без знака насыщается до 0 везде.)

Вам необходим AVX2 для смены с переменным счетом. psubusb/w - это SSE2 , поэтому вы можете рассмотреть возможность выполнения этой части с SIMD, а затем вернуться к скалярному целому числу для смен или просто использовать сдвиги SSE2 для одного элемента за раз. Как и psrlq xmm1, xmm0, который принимает младшие 64 бита xmm0 в качестве счетчика сдвига для всех элементов xmm1.

Большинство МСА не имеют насыщающее скалярное вычитание . Я думаю, что некоторые процессоры ARM используют скалярное целое число, а x86 - нет. IDK, что вы используете.

На x86 (и многих других ISA) у вас есть 2 проблемы:

  • оставить все единицы для младших элементов (либо изменить результат сдвига, либо перенастроить счетчик сдвига до 0)
  • выдает 0 для старших элементов над элементом, содержащим верхний бит маски. Скалярные сдвиги x86 вообще не могут этого сделать, поэтому для этого случая вы можете ввести сдвиг 0. Возможно, используя cmov, чтобы создать его на основе флагов, установленных sub для 192-w или чего-то еще. 
    count = 192-w;
    shift_input = count<0 ? 0 : ~0ULL;
    shift_input >>= count & 63;      // mask to avoid UB in C.  Optimizes away on x86 where shr does this anyway.

Хм, это не справится с насыщением вычитания до 0, чтобы сохранить все.

Если вы настраиваете для ISA, отличных от x86, возможно, посмотрите на некоторые другие варианты. Или, может быть, есть что-то лучше и на x86. Создание единичных или всех нулей с sar reg,63 - интересный вариант (широковещательный бит), но нам действительно нужны единичные единицы, когда 192-count имеет знаковый бит = 0.

...