Раз уж мы решили пооптимизировать алгоритмы

[Absurd]

Меня недавно заинтриговала операция mor из книжки Кнута, которая рассматривает два 64-х битных числа как две матрицы 8*8 на кольце значений {0, 1} и производит их умножение. Умножение бита на бит это and, сложение двух бит это or. Как мы знаем из линейной алгебры умножение на побочную диагональ состоящую из единичек меняет порядок строк на противоположный, так что 0x0123456789abcdefULL mor 0x0102040810204080ULL == 0xefcdab8967452301ULL. К сожалению, мыслей по поводу того как это сделать эффективно у меня нет. Написал такой код, но в нем слишком много умножений. Если отбрасывать нулевые байты при помощи if-а получается заметно медленнее за исключением того случая когда там действительно есть нули.

Код: Выделить всё

uint64_t mor(uint64_t y, uint64_t z)
{
  uint64_t x = 0;
#define morl(i) \
		x |= (((z >> (i)) & 0x0101010101010101ull) * 0xff) & ((y >> ((i) << 3) & 0xff) * 0x0101010101010101ull);

  morl(0);
  morl(1);
  morl(2);
  morl(3);
  morl(4);
  morl(5);
  morl(6);
  morl(7);
#undef morl
  return x;
}

[somewhere]

По правилу умножений матриц нам нужно подсчитать 64 скалярных произведения двух векторов.
Каждый из векторов - это 8 битное число, причем по условию задачи скалярное произведение A*B = E(0,7) A & B, то есть ABCDEFGH * IJKLMNOP = (A & I) | (B & J) | (C & K) | (D & L) | (E & M) | (F & N) | (G & O) | (H & P)
Результат этой операции равен 1, если ((ABCDEFGH | IJKLMNOP) != 0) - я правильно понимаю?

[Absurd]

Assume that the 64 bits in $Y are numbered as follows (and similar for the bits in register $Z and $X):

y00y01...y07 y10y11...y17 ... y70y71...y77

Now bit xij in register register $X is computed as follows:

MOR: xij = y0j& zi0 | y1j& zi1 | ... | y7j& zi7
MXOR: xij = y0j & zi0 ˆ y1j & zi1 ˆ ... ˆ y7j & zi7

Timing:

1υ

Description:

These instructions regard the 8 Byte of a register as a 8×8-Matrix and compute the result as a matrix multiplication, where in MOR, Addition is replaced by OR (logical or (|)) and in MXOR, Addition is replaced by XOR (exclusive or (ˆ)). In both cases the AND operation (&) is used instead of multiplication.

В другом документе:

These operations essentially set each byte of $X by looking at the corresponding byte of $Z and using its bits to select bytes of $Y; the selected bytes are then ored or xored together.

Для каждого i-го байта из $X берется i-й байт из $Z. Его биты используются для выборки байтов 0..7 из $Y. Выбранные байты or-ятся или xor-ятся друг с другом и записываются в i-й байт $X.

[somewhere]

Давайте тогда определимся. Интересует оптимизация именно скалярного произведения (о нем как раз написано в предыдущем посте), оптимизация умножения на побочную диагональ (первый пост) или оптимизация умножения указанных матриц в целом?
Применять ли architecture-specific features или нет? Здесь, например, отлично подходит команда процессора BT из IA-32

[Absurd]

оптимизация умножения указанных матриц в целом?
Применять ли architecture-specific features или нет? Здесь, например, отлично подходит команда процессора BT из IA-32

Интересует оптимальная замена кода из оригинального поста (умножение двух матриц 8x8 на поле вычетов по модулю 2), и да, сгодится все до SSE4 включительно. А порядок байт можно инвертировать одной инструкцией bswap, это не интересно.