В приложении к криптографии я задался вопросом как "правильно" писать исходный код на языке Си, чтобы компилятор использовал инструкции BFI (Bit Field Insert) и BFX(Bit Field Extract).
Мой алгоритм берет 4 бита и использует их в качестве индекса массива. В примере я описываю "нелинейное биективное преобразование" по таблице подстановок (ГОСТ 34.12-2015 п.5.1.1).
Для отладки алгоритма я использую компиляцию в ассемблер и рассматриваю, какими командами компилятор выражается.
> gcc -march=native -O3 -o - -S magma.c
-- на экран выводится ассемблерный код оптимизированный под мой процессор
Или под целевую платформу ARMv7e-m
$ arm-none-eabi-gcc -mthumb -mcpu=cortex-m4 -march=armv7e-m -mfloat-abi=hard -mfpu=fpv4-sp-d16 -o - -O3 magma.c -S
Исходно пишу на Си, рассматриваю результат.
Пишу определение, которое соответствует операции BFX
В ассемблерном коде возникает команда
ubfx...
Но мне никак не удается подобрать обратную операцию.
Пишу определение
#define BFI(x, y, n, len) x = ((x) & ~(((1 << (len))-1)<<(n))) | ((y & ((1 << (len))-1))<<(n))
Но в результате компилятор НЕ использует инструкцию bfi, определение НЕ работает.
Смотрю в документацию (Arm C Language Extensions, ACLE Q2 2019) нахожу пояснение, инструкция BFI описывается средствами языка Си, т.е. должно быть соответствующее ей выражение.
Через некоторое время, дошло, что в расширении языка С бывают свои битовые строки. Такое вот описание битовых полей (см код ниже) позволило однозначно задействовать инструкцию извлечения битовой строки и последующее помещение битовой строки обратно в регистр.
В результате компилятор создает такой код:
Мой алгоритм берет 4 бита и использует их в качестве индекса массива. В примере я описываю "нелинейное биективное преобразование" по таблице подстановок (ГОСТ 34.12-2015 п.5.1.1).
Для отладки алгоритма я использую компиляцию в ассемблер и рассматриваю, какими командами компилятор выражается.
> gcc -march=native -O3 -o - -S magma.c
-- на экран выводится ассемблерный код оптимизированный под мой процессор
Или под целевую платформу ARMv7e-m
$ arm-none-eabi-gcc -mthumb -mcpu=cortex-m4 -march=armv7e-m -mfloat-abi=hard -mfpu=fpv4-sp-d16 -o - -O3 magma.c -S
Исходно пишу на Си, рассматриваю результат.
Пишу определение, которое соответствует операции BFX
#define BEXTR(x, n, len) (((x) >> (n)) & ((1 << (len))-1))
В исходнике пишу так:
for (i=0; i<8; i++){
s = sbox[i][BEXTR(a,(i*4),4)];
r |= (s & 0xF) <<(i*4);
}
sbox - это таблица подстановок.В ассемблерном коде возникает команда
ubfx...
Но мне никак не удается подобрать обратную операцию.
Пишу определение
#define BFI(x, y, n, len) x = ((x) & ~(((1 << (len))-1)<<(n))) | ((y & ((1 << (len))-1))<<(n))
Но в результате компилятор НЕ использует инструкцию bfi, определение НЕ работает.
Смотрю в документацию (Arm C Language Extensions, ACLE Q2 2019) нахожу пояснение, инструкция BFI описывается средствами языка Си, т.е. должно быть соответствующее ей выражение.
Через некоторое время, дошло, что в расширении языка С бывают свои битовые строки. Такое вот описание битовых полей (см код ниже) позволило однозначно задействовать инструкцию извлечения битовой строки и последующее помещение битовой строки обратно в регистр.
uint32_t T(uint32_t a)
{
register union {
struct {
uint32_t u0:4;
uint32_t u1:4;
uint32_t u2:4;
uint32_t u3:4;
uint32_t u4:4;
uint32_t u5:4;
uint32_t u6:4;
uint32_t u7:4;
};
uint32_t x;
} r;
r.x = a;
r.u0 = sbox[0][r.u0];
r.u1 = sbox[1][r.u1];
r.u2 = sbox[2][r.u2];
r.u3 = sbox[3][r.u3];
r.u4 = sbox[4][r.u4];
r.u5 = sbox[5][r.u5];
r.u6 = sbox[6][r.u6];
r.u7 = sbox[7][r.u7];
return r.x;
}
Это и есть биективное преобразование согласно ГОСТ, именно в таком виде оно попало в мою реализацию. -- Магия!!В результате компилятор создает такой код:
ubfx r2, r0, #16, #4 -- загрузить битовое поле
add r2, r2, r3
ldrb r2, [r2,#64] @ zero_extendqisi2 -- загрузить байт из таблицы
bfi r0, r2, #16, #4 -- вставить битовое поле