Двоичное матричное векторное умножение

Question

Я хочу умножить 8x8 двоичную матрицу , представленную как 64-разрядное целое число без знака, на 8-разрядный вектор, представленный символом без знака.Однако из-за некоторых других проблем матрица должна быть упорядочена по столбцам, поэтому нет простого сопоставления байтов для простого умножения.

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

Умножения выполняются над полем из 2 элементов (F-2).

Answer 1

С помощью этой матрицы и векторного представления, это помогает сделать умножение матрицы следующим образом:

(кол ₁ ... кол ₈ ) * (v ₁ ... v ₈ ) ^T = col ₁ * v ₁ + ... + col ₈ * v ₈

, где матрица A = (кол ₁ ... кол ₈ )

и вектор столбца v = (v ₁ ... v ₈ ) ^T

Если подумать об этом, вы можете выполнить все умножения за один раз, если переведите 8-битный вектор в 64-битный вектор, повторяя каждый бит 8 раз и затем вычисляя P = A & v_inflated. Остается только добавить (то есть XOR) продуктов.

Простой подход для XORing продуктов:

uint64_t P = calculated products from text above;
uint64_t sum = 0;
for( int i = 8; i; --i )
{
   sum ^= P & 0xFF;
   P >> 8;  
}

Answer 2

У вас ТОЛЬКО 256 векторов! Используйте таблицы поиска для генерации правильных битовых масок, тогда ваша логика будет выглядеть примерно так:

output_bit_n = bool (matrix [n] & lookup [vector])

Другими словами, ваша справочная таблица может транспонировать 8-битное значение в 64-битный мир.

Вы можете эффективно упаковать это в результат с помощью инструкций rotate-with-carry , если компилятор не достаточно умен, чтобы оптимизировать (value<<=1)|=result.