Допустим, у меня есть выражение (x << n) | (x >> (-n & 63))
.
В нем нет ничего условного.
Итак, насколько я понимаю, он будет выполняться в постоянное время.
Действительно, когда я компилирую следующий код с помощью gcc -O3 -S
:
#include <stdint.h>
// rotate left x by n places assuming n < 64
uint64_t rotl64(uint64_t x, uint8_t n) {
return (x << n) | (x >> (-n & 63));
}
Я получаю на linux/amd64
следующий вывод (который выполняется за постоянное время):
.file "test.c"
.text
.p2align 4
.globl rotl64
.type rotl64, @function
rotl64:
.LFB0:
.cfi_startproc
movq %rdi, %rax
movl %esi, %ecx
rolq %cl, %rax
ret
.cfi_endproc
.LFE0:
.size rotl64, .-rotl64
.ident "GCC: (Alpine 9.3.0) 9.3.0"
.section .note.GNU-stack,"",@progbits
Однако на linux/386
я получаю вывод, содержащий условные переходы:
.file "test.c"
.text
.p2align 4
.globl rotl64
.type rotl64, @function
rotl64:
.LFB0:
.cfi_startproc
pushl %edi
.cfi_def_cfa_offset 8
.cfi_offset 7, -8
pushl %esi
.cfi_def_cfa_offset 12
.cfi_offset 6, -12
movl 12(%esp), %eax
movl 16(%esp), %edx
movzbl 20(%esp), %ecx
movl %eax, %esi
movl %edx, %edi
shldl %esi, %edi
sall %cl, %esi
testb $32, %cl
je .L4
movl %esi, %edi
xorl %esi, %esi
.L4:
negl %ecx
andl $63, %ecx
shrdl %edx, %eax
shrl %cl, %edx
testb $32, %cl
je .L5
movl %edx, %eax
xorl %edx, %edx
.L5:
orl %esi, %eax
orl %edi, %edx
popl %esi
.cfi_restore 6
.cfi_def_cfa_offset 8
popl %edi
.cfi_restore 7
.cfi_def_cfa_offset 4
ret
.cfi_endproc
.LFE0:
.size rotl64, .-rotl64
.ident "GCC: (Alpine 9.3.0) 9.3.0"
.section .note.GNU-stack,"",@progbits
Насколько я понимаю, здесь нужно эмулировать 64-битные операции, отсюда и необходимость условных переходов.
Предоставляет ли GCC встроенную функцию, которая указывает, будет ли выражение компилироваться без переходов?
Если это не так, как я могу узнать, будет ли выражение выполняться за постоянное время?
Является ли это проблемой для чувствительных ко времени приложений, таких как безопасность?
Второй скомпилирован с -O3
clang компилируется в -m32
без условных переходов, но с cmov
.
Информация о выбранных инструкциях может отсутствовать во время компиляции, когда C++ преобразуется в промежуточное представление. Во время генерации сборки он может выбрать другую инструкцию в зависимости от целевой модели затрат и опций оптимизации.
Хорошо, но есть ли способ гарантировать отсутствие условных переходов при компиляции безусловных выражений? Кстати, речь идет о C и GCC, а не о C++ и Clang.
Вы имеете в виду «постоянное время» здесь в смысле O (1) или буквально постоянное (например, невосприимчивое к временным атакам по сторонним каналам)? Даже код без переходов не обязательно будет выполняться за «постоянное время» в последнем смысле из-за неупорядоченного выполнения, кэширования и т. д. Чтобы избежать атак по времени, обычно требуется тщательная рукописная сборка, и неразумно ожидать этого от скомпилированного кода. .
Я имел в виду буквально постоянный. Кроме того, я не знал, что код без переходов и условных перемещений также уязвим для атак по времени.
Нет такой функции не существует.
И если вы не пишете компилятор (а вы этого не делаете), вам не следует особо заботиться о фактическом генерируемом машинном коде. Компилятор может оптимизировать этот код так, как считает нужным (при условии, что он правильный) в зависимости от переданных вами параметров. А с -O3 вы должны получить самый быстрый код, даже с переходами.
Если бы существовала предложенная вами функция, ваш код был бы привязан к одной версии одного компилятора с определенным набором опций оптимизации. Другими словами: прощай переносимость.
Предоставляет ли GCC встроенную функцию, которая указывает, будет ли выражение компилироваться без переходов?
Нет.
Если это не так, как я могу узнать, будет ли выражение выполняться за постоянное время?
Глядя на сгенерированный код сборки.
Является ли это проблемой для чувствительных ко времени приложений, таких как безопасность?
Да. Вот почему в этих случаях не доверяйте компиляторам (и портировщикам/сборщикам пакетов, изменяющим настройки компилятора), а реализуйте их в сборке.
В общих libc есть некоторые функции с постоянным временем, например, в OpenBSD и FreeBSD. Например, Timingsafe_bcmp и Timingsafe_memcmp, которые написаны на чистом C, но их авторы верят, что их упаковщики не такие, как Debian или Ubuntu, которые, как предполагается, сломают его.
Многие другие подобные функции есть в самих различных библиотеках безопасности, но даже тогда можно смело предположить, что они сломаны. Наверняка в OpenSSL и libsodium во многих случаях.
Второй для меня выглядит как скомпилированный с флагом -O0. Включите оптимизацию и посмотрите еще раз