Узнать, содержится ли один диапазон в другом на Си

1) Я Vic-у отвечал, он считает что signed переполнение почти не опасно

2) насчёт правил ты не совсем прав, с -fno-strict-overflow оно действительно предсказуемо работает безо всяких UB, а что там графоманы из комитета на этот счёт думают - вторично; но внимание этому аспекту конечно стоит уделять т.к. возможны подставы

Одним компилятором мир не заканчивается.

#define INT_MIN

Это же определено в <limits.h>. А примеры приведены в man gcc, в описании Wstrict-overflow.

хуже оказалось,

С -O0 проверяли?

Верно, в мире много всего есть. В том числе и другие языки даже. Однако это не отменяет того факта что gcc -fno-strict-overflow компилирует Си без UB для знаковых переполнений, и что шланг вынужден был это повторить.

С O0 всё в порядке.

В моём man gcc примеров для strict-overflow нет (и на сайте gcc тоже не нашёл), но возможно этот пример даже косвенно из какой-то старой gcc документации, я его не писал с нуля.

Только всё ещё хуже оказалось, -O1 походу с некоторых пор тоже содержит -fstrict-overflow

Надеюсь, ты уже начинаешь догадываться, что воюешь еще не с арифметикой, а с оптимизатором компилятора.

Например, первая функция void examine(int x) компилируется в получения абсолютного значения и всего два printf:

  82              	 # main.c:9:   else printf("%d!=%d\n", x, INT_MIN);
  83 0008 C7442408 		mov	DWORD PTR [esp+8], -2147483648	 #,
  84 0010 C7042400 		mov	DWORD PTR [esp], OFFSET FLAT:LC0	 #,

                                # if(x<0) x = -x;
  85 0017 89D8     		mov	eax, ebx	 # tmp89, x
  86 0019 C1F81F   		sar	eax, 31	 # tmp89,
  87 001c 31C3     		xor	ebx, eax	 # x, tmp89
  88 001e 29C3     		sub	ebx, eax	 # x, tmp89
  
  89 0020 895C2404 		mov	DWORD PTR [esp+4], ebx	 #, x
  90 0024 E8000000 		call	_printf	 # else printf("%d!=%d\n", x, INT_MIN);
  90      00
  91              	 # main.c:11:   else printf("%d>=0\n", x);
  92 0029 895C2404 		mov	DWORD PTR [esp+4], ebx	 #, x
  93 002d C7042408 		mov	DWORD PTR [esp], OFFSET FLAT:LC1	 #,
  93      000000
  94 0034 E8000000 		call	_printf	 # else printf("%d>=0\n", x);

Математикой, над кодированными в бинарном виде числами, можно рассматривать только вот этот кусочек:

  if(x<0) x = -x;

  85 0017 89D8     		mov	eax, ebx # tmp89, x
  86 0019 C1F81F   		sar	eax, 31 # tmp89,  
  87 001c 31C3     		xor	ebx, eax # x, tmp89
  88 001e 29C3     		sub	ebx, eax # x, tmp89  

Надеюсь, ты уже начинаешь догадываться, что воюешь еще не с арифметикой, а с оптимизатором компилятора.

Не надо косить под мудреца с откровениями. Про то, кто на что влияет, и без тебя все знают, но ты вдобавок к этому ещё пытаешься подменять понятия. Си-арифметика это и есть то, что тебе выдаст компилятор, в состав которого входит и оптимизатор. И она зависит от того, какой компилятор, какой версии и с какими опциями использовался. Тебе никто не запрещает рассматривать арифметику вне влияния компилятора, но называй это правильно: арифметика процессора или ассемблерная арифметика. Да, она именно такая как ты писал (по крайней мере на x86 процах) - с заворачиванием диапазона MAX+1=MIN. Но это не Си.

Погоди.

Сначала ты ловил программистов на знание переполнения разрядной сетки в арифметических операциях (которые я, возможно ошибочно, посчитал неожиданным откровением для тебя).

два попадания в расставленные (впрочем, десятилетия назад) ловушки

Эти вещи зависят НЕ от языка, а зависят от компилятора и флагов опций компилятора, о чем я тебе пояснил и предложил разобрать пример по-битам.

Пример мы нашли. Я правильно понимаю, что теперь тебя коробит (вполне обоснованно) тот факт, что результат работы этого примера зависит от флага компиляции -fno-strict-overflow / -fstrict-overflow компилятора gcc?

Да что ты несёшь?

Эти вещи зависят НЕ от языка, а зависят от компилятора и флагов опций компилятора,

Язык это то, что компилирует компилятор. Теоретическими изысканиями на тему несуществующего абстрактного идеального Си заниматься ни к чему. Но если хочешь - присоединяйся к графоманам-теоретикам, сидящим в Си-комитете. Вот неприятность только, они считают что знаковое переполнение это безальтернативное UB, а вовсе не повторение ассемблерной арифметики на этот счёт.

о чем я тебе пояснил

Я сразу и писал что оно зависит от флагов компилятора.

Я правильно понимаю, что теперь тебя коробит тот факт

Неправильно. Меня ничего не коробит.

Неправильно. Меня ничего не коробит.

А что ты тогда хотел показать вот этим найденным примером?

Вот пример для демонстрации который срабатывает на gcc10:

#include <stdio.h>

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX-1)

void examine(int x) {
...

Объяснить тебе, что в общем случае нельзя считать сишную знаковую арифметику эквивалентной ассемблерной.

на знание переполнения разрядной сетки в арифметических операциях

Не на знание, а на достаточную внимательность к своему коду, в котором это знание надо учитывать. А то часто вижу как игнорируют возможность переполнения, или, хуже того, суют свои любимые int-ы вместо size_t, а потом заявляют «Си плохой язык потому что в нём баги».

Объяснить тебе, что в общем случае нельзя считать сишную знаковую арифметику эквивалентной ассемблерной.

Арифметика и кодирование целых чисел int (и многих других типов) у Си/С++ и процессора - абсолютно одинаковая. Собственно, даже в википедии нет никакой особой Си-арифметики, потому нативная арифметика - она одна на всех.

Твой флаг -fno-strict-overflow / -fstrict-overflow у gcc компилятора, влияет не на арифметику, а на получающийся код программы, вставлять или нет дополнительные проверки и ветвления в ход выполнения программы, можешь сам сравнить ассемблерный выхлоп с разными флагами и без (в обоих случаях с опцией -O0). А там, где идут вычисления, арифметика не меняется. Ну и у gcc там еще наверняка 100500 подобных флагов.

Собственно, даже в википедии нет никакой особой Си-арифметики.

В Си переполнение signed типа указано как UB, а у машины - даёт конкретный результат.

Вот вам и «нет особой арифметики». Еще как есть.

В Си вычисление выражения INT_MAX + 1 формально может иметь любые последствия, от падения программы до вывода на экран содержимого многотомника Кнута.

В Си переполнение signed типа указано как UB, а у машины - даёт конкретный результат.

Правильно, причем стопроцентный и одинаковый результат на практически любой машине (арифметика одна на всех и результат ее работы, к счастью, одинаков).

UB написали не потому что язык Си, а потому что сначала наплодили кучу компиляторов с разным генератором кода и разным поведением и кучей опций меняющих это поведение как явно так и неявно, а потом только это решили поместить стандарт и … очевидно, не договорились/забили и «подложили себе бумажку» в виде UB что бы не докапывались (сорян, но подлинной истории не знаю, я вообще за однообразие, но против стандартов).

Ну вот пока в официальной бумаге не договорятся до чего-то конкретного, так оно и будет.

Если я, чисто теоретически, напишу такой компилятор, который каждый раз при переполнении signed типа останавливает исполнение программы и запускает на воспроизведение известный юмористический шлягер 90-х «Два кусочка колбаски», то такой компилятор по всем формальным признакам не будет противоречить спецификации языка.

Ты только предупреди об этом, а то нам, практикам, с таким компилятором потом работать. Пожалей нас.

Тю, нашли с кем спорить. Афтар еще и гуманитарий к тому же, как выяснилось, а не хухры-мухры. Как грица, «и столяр, и плотник, и маляр, и штукатур». А занимался бы одним программированием, может и вышел бы толк.

Так сильно хотел подловить программеров на чем-то своем сферическом, будучи не в состоянии поставить правильно задачу, и зафейлился.

UB написали не потому что язык Си

Именно потому. Причём ты не прав аж два раза в этой простой фразе.

Во-первых

сначала наплодили кучу компиляторов с разным генератором кода и разным поведением и кучей опций меняющих это поведение как явно так и неявно, а потом только это решили поместить стандарт

Это и есть то, что сформировало Си - куча разных компиляторов более-менее похожих друг на друга, но не во всём. Другого Си нет.

Во-вторых, UB при signed переполнении в современном исполнении сделано не из-за этого, а для того, чтобы оптимизатору было проще выкидывать твой код при работе.

Например, чтобы он мог из подобного кода:

f(int x) {
  int y;
  y = x+5;
  if(y<x) { ... }
  ...
}

Во-вторых, UB при signed переполнении в современном исполнении сделано не из-за этого, а для того, чтобы оптимизатору было проще выкидывать твой код при работе.

Ерунда. Тут перепутаны причина и следствие.

Ок, вот вы в итоге сами и пришли к тому же, с чего начали, что дело не в языке, а в компиляторе gcc.

PS. Ну вот захотели авторы gcc такую оптимизацию, и сделали, может это им очень очень сильно надо (и реально полезно), и ни вы, ни я им не указ. Стандарт си, как я понимаю, пишут они же под себя же любимых и плевать им на всех остальных.

Скорее-всего было «как обычно», сначала сделали оптимизацию, эффективно выкидывающую блоки кода (вполне может быть и скрытую за тоннами макросов и шаблонов), а потом оказалось, что люди-то пользуются переполнением разрядной сетки, и пришлось делать опцию компилятора, вертающую все взад.

Но это мое личное мнение, не претендующее на истину. Просто так случается достаточно часто, что фича в общем-то полезная, но что-то не доглядели и у нее есть небольшие артефакты… как из багов делаются фичи, все знают, надо баг описать в документации/стандарте и это сразу становится фичей.

Да, на уровне компилятора видимо так и было. Сделали вычислительную модель для оптимизатора, которая проходит все тесты согласно официальным требованиям, а потом оказалось, что она из генерируемого кода выкидывает то, что никто в здравом уме выкидывать бы не стал.

А вот на уровне стандарта мне интересно… Вот это UB там - выглядит как робкая попытка осмыслить тот факт, что переполнение в коде нужно либо явным образом использовать на благо алгоритма, либо столь же явным образом ловить и выкидывать исключение. Но поскольку реальные компиляторы работали кто во что горазд, а исключений в Си нет, то получилось… чёрное пятно.

Вот для сравнения, как этот вопрос решает язык, который делался для того, чтобы давать чёткие результаты:

For a modular type, if the result of the execution of a predefined operator is outside the base range of the type, the result is reduced modulo the modulus of the type to a value that is within the base range of the type.

For a signed integer type, the exception Constraint_Error is raised by the execution of an operation that cannot deliver the correct result because it is outside the base range of the type. 

For any integer type, Constraint_Error is raised by the operators "/", "rem", and "mod" if the right operand is zero.

Garbage in, garbage out. ¯\_(ツ)_/¯

UB написали не потому что язык Си, а потому что сначала наплодили кучу компиляторов с разным генератором кода и разным поведением и кучей опций меняющих это поведение как явно так и неявно, а потом только это решили поместить стандарт и … очевидно, не договорились/забили и «подложили себе бумажку» в виде UB что бы не докапывались (сорян, но подлинной истории не знаю, я вообще за однообразие, но против стандартов).

Не потому. Результат переполнения знаковых вполне может зависеть от представления отрицательных чисел (это сейчас мы по сути в миру победившего «ones' complement» живём). С беззнаковыми всё несколько проще.

в миру победившего «ones’ complement»

two’s complement

Результат переполнения знаковых вполне может зависеть от представления отрицательных чисел

Для этого достаточно потребовать данную фичу быть implementation defined. Undefined behavior - избыточно.

Вот более простой и понятный пример:

char* add1(int a) {
    if (a+1 > a) 
      return "a+1 > a";
    else 
      return "a+1 < a";
}

Компилируем с -O и получаем такой листинг:

.LC0:
        .string "a+1 > a"
add1:
        mov     eax, OFFSET FLAT:.LC0
        ret

Компилируем с -O -fwrapv и получаем другой асм:

.LC0:
        .string "a+1 > a"
.LC1:
        .string "a+1 < a"
add1:
        cmp     edi, 2147483647
        mov     eax, OFFSET FLAT:.LC1
        mov     edx, OFFSET FLAT:.LC0
        cmovne  rax, rdx
        ret

По умолчанию компилятор предполагает, что переполнения быть не может. Юзер может повлиять на такое поведение флагами -fwrapv или -fno-strict-overflow (что почти одно и то же).

Очевидно, флаги работают только при включенной оптимизации кода.

Только всё ещё хуже оказалось, -O1 походу с некоторых пор тоже содержит -fstrict-overflow

Нет. Ни один из уровней оптимизации не содержит ни -fstrict-overflow ни -fno-wrapv. Это просто такое поведение компилятора по умолчанию при включенной оптимизации.

В целом поддержу и пример действительно хороший. Но

Нет. Ни один из уровней оптимизации не содержит ни -fstrict-overflow ни -fno-wrapv. Это просто такое поведение компилятора по умолчанию при включенной оптимизации.

Формально может и так, но по факту gcc 4 и более ранние не начинали сами считать переполнение UB на уровнях меньше -O2. Теперь - начинают. 6.3 уже делал это но не всегда (из моего примера он при -O1 багает x++ но не багает x=-x). 8.3 уже -O1 и -O2 воспринимает одинаково в аспекте этих переполнений.

Вот для сравнения, как этот вопрос решает язык, который делался для того, чтобы давать чёткие результаты:

Этот язык тратит лишние циклы процессора на эти проверки. Си же рассчитан на то, что если программист считает конкретно тут проверки нужными - он их закодит вручную, а если нет - проц не будет делать ненужные действия, и оптимизатор может не ограничивать себя поддержкой предсказуемых переполнений.

Всё бы ничего, вот только для unsigned определена семантика переполнений.

На этом фантазии про разумный замысел сего творения в разрезе байто***тва можно оставить.

дело не в языке, а в компиляторе gcc

Ну сколько можно? Спецификация работы компилятора это и есть язык. Хватит раз за разом пытаться разделить эти понятия. А UB это есть не только в gcc.

Стандарт си, как я понимаю, пишут они же под себя же любимых и плевать им на всех остальных.

Понимаешь ты неправильно. Я не знаю когда ввели эту оптимизацию, но история взаимоотношений стандарта и языка такая: до 89 года десятка два лет все писали компиляторы вообще без каких-либо стандартов, дорабатывая их так же как дорабатывают любой другой софт: нужна фича - допишем. В 89 году группа людей провела полезную работу по систематизации и обобщению текущей имеющейся ситуации среди актуальных компиляторов и издала это исследование под названием C89. После чего компиляторописатели продолжили заниматься тем, чем занимались раньше (доработка по мере нужности), а комитет решил, что он вместо исследования и обобщения ситуации будет теперь пытаться на неё влиять, и в 99 году издал вторую версию документа (C99) в которой было много всего, чего не было в компиляторах, зато не было многого из того, чего в компиляторах за 10 лет добавилось (gcc в связи с этим поддерживает диалекты ansi c89, gnu c89, ansi c99, gnu c99). Но пункт про UB при знаковом переполнении был ещё в C89.

Это было к языкам которые проактивно ловят переполнения. В Си для unsigned тоже они не ловятся. Разница между signed и unsigned могла быть исторически по разным причинам, как потому что signed могут иметь разное представление, так и потому что в нём реже нужно использовать переполнения. Но те причины исторические, а сейчас это не убирают (и даже наоборот форсят) из-за оптимизатора.

Ну понятно, пошли отмазки, когда аргумент не сработал.

Для этого достаточно потребовать данную фичу быть implementation defined. Undefined behavior - избыточно.

Кстати да, для разных представлений достаточно implementation defined, а вот оптимизатору нужно именно UB.

https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/statements/checked-and-unchecked

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

В голанге кстати этого нет. Можно Лавсану добавить в свою копилку унижений голанга.

Вот совершенно верно ребята поступили, потому что программисту нужно строго определенное поведение на конкретную операцию, а не флагами фигачить всю программу и потом удивляться WTF.

Пробиваем фанеру оптимизатору компилятора.

#include <stdio.h>
#include <stdbool.h>

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX-1)


int (*fooptr)(int) = NULL;

int foo(int x)
{
    if (x < 0) x = -x;
    return x;
}

int (*barptr)(int) = NULL;

int bar(int x)
{
    x++;
    return x;
}

void examine(int x) {
  x = fooptr(x);
  if(x==INT_MIN) printf("%d==%d\n", x, INT_MIN);
  else printf("%d!=%d\n", x, INT_MIN);
  if(x<0) printf("%d<0\n", x);
  else printf("%d>=0\n", x);
}

void examine2(int x) {
  x = barptr(x);
  if(x==INT_MIN) printf("%d==%d\n", x, INT_MIN);
  else printf("%d!=%d\n", x, INT_MIN);
  if(x<0) printf("%d<0\n", x);
  else printf("%d>=0\n", x);
}

int main(void) {
  fooptr = foo;
  barptr = bar;
  examine(1);
  examine(-1);
  examine(INT_MIN);
  examine2(INT_MAX);
  return 0;
}

Результат:

1!=-2147483648
1>=0
1!=-2147483648
1>=0
-2147483648==-2147483648
-2147483648<0
-2147483648==-2147483648
-2147483648<0

Ни одно арифметическое действие не пострадало… чтд.

чтд.

И что ты доказал этим? Ты не знаешь что такое UB?

И что ты доказал этим?

Что дело в оптимизаторе конкретного компилятора, а не в какой-то никому не известной Си-арифметике и не в самом языке Си.

Ты не знаешь что такое UB?

Уже не только я тебе написал, что UB в вычитанном тобой стандарте - это «отмазка» стандартописателей.

Ну и в коде, который я привел, больше нет никакого «UB», и все арифметические операции полностью совпадают с исходным примером. ТЧК.

wandrien зацени, как тебе вариант борьбы с оптимизатором компилятора?

Это будет работать до тех пор, пока в очередной версии компилятор не решит, что в рамках оптимизации кода он имеет право переобъявить fooptr как static. (А он может, например, если знает, что компилирует программу статически.) И потом пошло-поехало…

bool is_contained(unsigned h0, unsigned hlen, unsigned q0, unsigned qlen) {
  return q0 >= h0 && hlen >= qlen && q0 - h0 <= hlen - qlen;
}

не проверял особо, но вроде так

Первый раз вижу такое сочетание: с одной стороны, пропагандируешь некий оторванный от реальности «идеальный» Си, не привязанный ни к какому компилятору, с другой - критикуешь такой же оторванный от реальности стандарт от комитета. Все идеалисты, которых я раньше встречал, очень уважали стандарт и приводили его как образец независимости от компиляторов. Наверно тебе надо основать свой Си-комитет и издавать альтернативную версию этой графомании.

больше нет никакого «UB»

Я тебя расстрою, но он там есть и будет до тех пор, пока ты не зафиксируешь -fno-strict-overflow или -fwrapv. UB не означает гарантированную поломку, он означает непредсказуемое поведение - где-то может и работает, а где-то неожиданно всё пойдёт не так.

Сей кейс я проверил на текущем компиляторе, и static и inline для foo() и bar(), никак не повлияли на функции examine() и examine2(). Оптимизатор же ведь именно в examine() и examine2() «поработал», вырезав куски кода. Они сейчас пилят с++, на обычный си вроде как забили, так что gcc для си, надеюсь, теперь будет долго и стабильно.

Считаю, что вы глубоко ошибаетесь.

Да это просто дурка вместо x++ писать вызов функции. Код понимать сложнее и у многих будет желание поправить код обратно. Плюс надо смотреть, на всех ли архитектурах компилятор себя так поведёт.

Да это просто дурка вместо x++ писать вызов функции.

Совершенно с вами согласен! Никто в обычной программе так делать не станет. Этот пример служит доказательством топикстартеру, что корень проблем в оптимизаторе конкретного компилятора (gcc), а не в какой-то магической си-арифметике. Не более того.

корень проблем

Проблем, которые ты выдумал - может быть. Я ни про какие проблемы не писал, а только описывал штатную ситуацию.

корень проблем в оптимизаторе конкретного компилятора (gcc)

Нет. Оптимизатор не обязан во что-то осмысленное компилировать код, который в документации на язык явно указан как UB.

Пишите письма в комитет.

Не берусь вас судить.