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

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

Лучшее, что я придумал - это безветвление, но оно требует МНОГИХ инструкций. Это в Zig, потому что Clang, кажется, не выставляет насыщающее вычитание llvm. HTTP: // локальный: 10240 / г / 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 ответ

Решение

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

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

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

Для самых низких u64 элемент, начиная со всех единиц, мы должны оставить его неизменным для bitpos >= 64. Или для меньших битовых позиций сдвиньте его вправо на64-bitpos, Беззнаковое вычитающее насыщение выглядит как способ, как вы заметили, создать отсчет сдвига 0 для больших битовых постов. Но x86 имеет только SIMD-насыщающее вычитание, и только для байтов или элементов слова. Но если мы не заботимся о bitpos > 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: mask = 1
  • ...: mask =ediодин бит внизу, затем нули
  • edi=255: mask = все единицы, кроме верхнего бита верхнего элемента
  • edi=256: mask = все
  • edi>256: mask = все. (вычитание без знака насыщает до 0 везде.)

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

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

На 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.

Источник

Вот код Zig, который компилируется и запускается:

const std = @import("std");

noinline fn thing(x: u256) bool {
    return x > 0xffffffffffffffff;
}

pub fn main() anyerror!void {
    var num: u256 = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff;
    while (thing(num)) {
        num /= 2;
        std.debug.print(".", .{});
    }
    std.debug.print("done\n", .{});
}

Из этого Zig master генерирует относительно чистый ассемблер x86.

Источник
Другие вопросы по тегам