GCC проверяет, будет ли выражение выполняться за постоянное время

Допустим, у меня есть выражение (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 встроенную функцию, которая указывает, будет ли выражение компилироваться без переходов? Если это не так, как я могу узнать, будет ли выражение выполняться за постоянное время?
Является ли это проблемой для чувствительных ко времени приложений, таких как безопасность?

Второй для меня выглядит как скомпилированный с флагом -O0. Включите оптимизацию и посмотрите еще раз

0___________ 21.12.2020 19:01

Второй скомпилирован с -O3

Cl00e9ment 21.12.2020 19:07

clang компилируется в -m32 без условных переходов, но с cmov.

Maxim Egorushkin 21.12.2020 19:12

Информация о выбранных инструкциях может отсутствовать во время компиляции, когда C++ преобразуется в промежуточное представление. Во время генерации сборки он может выбрать другую инструкцию в зависимости от целевой модели затрат и опций оптимизации.

Maxim Egorushkin 21.12.2020 19:17

Хорошо, но есть ли способ гарантировать отсутствие условных переходов при компиляции безусловных выражений? Кстати, речь идет о C и GCC, а не о C++ и Clang.

Cl00e9ment 21.12.2020 19:26

Вы имеете в виду «постоянное время» здесь в смысле O (1) или буквально постоянное (например, невосприимчивое к временным атакам по сторонним каналам)? Даже код без переходов не обязательно будет выполняться за «постоянное время» в последнем смысле из-за неупорядоченного выполнения, кэширования и т. д. Чтобы избежать атак по времени, обычно требуется тщательная рукописная сборка, и неразумно ожидать этого от скомпилированного кода. .

Nate Eldredge 21.12.2020 20:09

Я имел в виду буквально постоянный. Кроме того, я не знал, что код без переходов и условных перемещений также уязвим для атак по времени.

Cl00e9ment 21.12.2020 20:30
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
7
139
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Нет такой функции не существует.

И если вы не пишете компилятор (а вы этого не делаете), вам не следует особо заботиться о фактическом генерируемом машинном коде. Компилятор может оптимизировать этот код так, как считает нужным (при условии, что он правильный) в зависимости от переданных вами параметров. А с -O3 вы должны получить самый быстрый код, даже с переходами.

Если бы существовала предложенная вами функция, ваш код был бы привязан к одной версии одного компилятора с определенным набором опций оптимизации. Другими словами: прощай переносимость.

Ответ принят как подходящий

Предоставляет ли GCC встроенную функцию, которая указывает, будет ли выражение компилироваться без переходов?

Нет.

Если это не так, как я могу узнать, будет ли выражение выполняться за постоянное время?

Глядя на сгенерированный код сборки.

Является ли это проблемой для чувствительных ко времени приложений, таких как безопасность?

Да. Вот почему в этих случаях не доверяйте компиляторам (и портировщикам/сборщикам пакетов, изменяющим настройки компилятора), а реализуйте их в сборке.

В общих libc есть некоторые функции с постоянным временем, например, в OpenBSD и FreeBSD. Например, Timingsafe_bcmp и Timingsafe_memcmp, которые написаны на чистом C, но их авторы верят, что их упаковщики не такие, как Debian или Ubuntu, которые, как предполагается, сломают его.

Многие другие подобные функции есть в самих различных библиотеках безопасности, но даже тогда можно смело предположить, что они сломаны. Наверняка в OpenSSL и libsodium во многих случаях.

Другие вопросы по теме