Я думаю, что вы, возможно, ищете реализацию нарезки битов .Вот как работают самые быстрые имплантации DES-крекинга.(Во всяком случае, это было до того, как появились инструкции SSE.)
Идея состоит в том, чтобы написать вашу функцию "побитовым" способом, представляя каждый выходной бит как логическое выражение над входными битами.Поскольку каждый выходной бит зависит только от входных битов, любая функция может быть представлена таким образом, даже такие вещи, как сложение, умножение или поиск в S-блоках.
Хитрость заключается в том, чтобы использовать фактические биты одного регистрадля представления одного бита из нескольких входных слов .
Я проиллюстрирую это простой четырехбитной функцией.
Предположим, например, что вы хотите взять четыребитовые входы вида:
x3 x2 x1 x0
... и для каждого входа рассчитайте четырехбитный выход:
x2 x3 x2^x3 x1^x2
И вы хотите сделать это, скажем, для восьмивходы.(Хорошо, для четырех битов таблица поиска будет самой быстрой. Но это просто для иллюстрации принципа.)
Предположим, ваши восемь входных данных:
A = a3 a2 a1 a0
B = b3 b2 b1 b0
...
H = h3 h2 h1 h0
Здесь a3 a2 a1 a0 представляетчетыре бита входа A и т. д.
Сначала закодируйте все восемь входов в четыре байта, где каждый байт содержит один бит от каждого из восьми входов:
X3 = a3 b3 c3 d3 e3 f3 g3 h3
X2 = a2 b2 c2 d2 e2 f2 g2 h2
X1 = a1 b1 c1 d1 e1 f1 g1 h1
X0 = a0 b0 c0 d0 e0 f0 g0 h0
Здесьa3 b3 c3 ... h3 - это восемь бит X3.Он состоит из старших бит всех восьми входов.X2 - следующий бит из всех восьми входов.И так далее.
Теперь, чтобы вычислить функцию восемь раз параллельно, вы просто делаете:
Y3 = X2;
Y2 = X3;
Y1 = X2 ^ X3;
Y0 = X1 ^ X2;
Теперь Y3 содержит старшие биты из всех восьми выходов, Y2 содержит следующий бит извсе восемь выходов и тд.Мы только что вычислили эту функцию на восьми разных входах, используя только четыре машинные инструкции!
Еще лучше, если наш ЦП 32-битный (или 64-битный), мы могли бы вычислить эту функцию на 32 (или 64) входах, все еще используя только четыре инструкции.
Кодирование ввода и декодирование вывода в / из представления "битовой части", конечно, занимает некоторое время.Но для правильного рода функций этот подход предлагает огромный параллелизм на уровне битов и, следовательно, значительное ускорение.
Основное предположение состоит в том, что у вас есть много входов (например, 32 или 64), на которых вы хотите вычислитьта же функция, и что функция не является ни слишком сложной, ни слишком простой для представления в виде набора логических операций.(Слишком сложно делает необработанные вычисления медленными; слишком легко делает время доминирующим за счет самого кодирования / декодирования битовых фрагментов.) В частности, для криптографии, где (a) данные должны пройти множество «циклов» обработки, (b) алгоритм часто уже использует биты, и (c) вы, например, пробуете множество ключей для одних и тех же данных ... Он часто работает довольно хорошо.