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

Намного лучше но ещё не 100%.

И правда, не знал. Вообще не задумывался про stat в винде. Ну, вообще даже без винды я когда-то думал что это create time т.к. это самая интуитивная расшифровка 'c' для файла. То что кто-то придумал таймстампы на изменение метаданных - неочевидно.

Но мне кажется в серьёзных проектах таких ошибок не должно быть и должно правильное birthtime туда показываться.

Да, тут у тебя существенно много чего не указано, как минимум что за массивы, какой тип, корректны ли входные данные, размер элементов в массиве, массив это сишный массив или АСД, какой тип данных возвращать… С т.з. применения к реальному коду это все телепатия.

Задачи только на естественном языке ставить можно и даже полезно (я студентам их даю), но это должны быть цельные задания, не являющиеся частью какого-то программного решения. Например, промоделировать капитал человека, если он взял ипотеку под 10% на 30 лет на 30.000.000 руб с 1.000.000 первоначального взноса, учесть траты на еду, на машину, индексацию зарплаты, 13 зарплату, инфляцию, написать код так, чтобы можно было добавлять дополнительные расходы и доходы не сильно портя структуру кода. Все недостающие цифры и параметры додумать самому опираясь на существующую реальность.

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

А твое задание это «пойди туда – не знаю куда, принеси то – не знаю что, но чтобы было то, что нужно».

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

Все недостающие цифры и параметры додумать самому опираясь на существующую реальность.

Вот тут не так: «додумать самому, опираясь на свою фантазию и рандом, но не вступая в противоречие с теми параметрами которые таки указаны».

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

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

ЯННП, но вот :)

#include <stddef.h>
#define OLOLO 2
/*
 *  h_pose : ptr addres
 *  q_pose : ptr addres
 *  h_lens : number_elements * sizeof(element_type)
 *  q_lens : number_elements * sizeof(element_type)
 */
unsigned char 
is_contained(ptrdiff_t h_pose, size_t h_lens, ptrdiff_t q_pose, size_t q_lens)
{
   return ((q_pose >= h_pose) && ((h_pose+q_lens) <= (h_pose + h_lens)));
}

int main(int argc , char * argv[])
{
    if(argc > 1)
    {
        switch (argv[1][0]-'0')
        {
            case 1: return is_contained(5,50,5,50);
            case 2: return is_contained(5,50,4,49);
            case 3: return is_contained(5,50,6,49);
            case 4: return is_contained(5,50,5,51);
            case 5: return is_contained(5,50,4,51);
        }
    }
    return OLOLO;
}

dron@gnu:~$ gcc -Wall -Wextra -std=c89 -pedantic test.c
dron@gnu:~$ ./a.out 1 ; echo $?
1
dron@gnu:~$ ./a.out 2 ; echo $?
0
dron@gnu:~$ ./a.out 3 ; echo $?
1
dron@gnu:~$ ./a.out 4 ; echo $?
0
dron@gnu:~$ ./a.out 5 ; echo $?
0

Я все видел.

Да, факап.

q0 + qlen < q0

не, ну тогда уж

int is_contained(size_t h0, size_t hlen, size_t q0, size_t qlen)
{
    // тут да
    if (q0 < h0)
        return 0;

    // а еще
    if (qlen > hlen)
        return 0;

    // и q0 в диапазоне от h0 до h0 + hlen
    if ((q0 - h0) > hlen)
        return 0;

    // а теперь еще проверим, что qlen меньше, чем  дистанция от q0 до h0 + hlen
    if (qlen > (hlen - (q0 - h0)))
        return 0;


    // и вот теперь
    return 1;
}

а то все эти сложения до добра не доведут )

Ну вот теперь кажется всё в порядке.

И так тоже можно, хотя кода получается больше, но зато не опираемся на переполнение. Мой вариант наверно на этот был бы больше похож, но «трюк» if(a+b<a) error я тоже местами использую.

Итого рефакторим обратно в человекочитаемый вид.

Первой ставим проверку на переполнение. А второй проверку из начала обсуждения, где не учитывается переполнение.

Лень с телефона код писать.

Это не трюк. Это определено языком для unsigned типов, они заворачиваются.

Да я в курсе. Но с точки зрения непрограммистов, а так же программистов на некоторых других языках это вызывает недоумение. А ещё больше путаницы вызывает то, что оно почему-то гарантируется только для unsigned, а для signed зависит от настроек компилятора (-fstrict-overflow или -O2 без -fno-strict-overflow превращает signed переполнение в UB, а без него оно такое же с заворачиванием).

Кстати, у меня где-то лежит незаконченная либа (ну как либа, она header-only), реализующая целые с NaN.

Не знаю, нужна кому такая. Надо бы доделать ее. Думал, пригодится мне самому, но как-то и без неё неплохо.

По-моему, автор хотел, чтобы это на макросах записали. И никаких размышлений насчет типов данных. Какие надо, такие и будут =)

#include<stdio.h>

#define is_contained(h0, hlen, q0, qlen) ((q0 >= h0) && ((q0 + qlen) <= (h0 + hlen)))

int main()
{
  int a = is_contained(11,20,4,10);
  int b = is_contained(1,30,4,15);
  printf("\na = %d  b = %d\n",a,b);
  return 0;
}

Результат:

./a.out 

a = 0  b = 1

P.S. Макрос для прода не очень годен, но мне лень его кучей скобок обкладывать, чтобы совсем правильно было.

Кстати, твой вариант даже циклические диапазоны с переходом через ноль почти (не полностью) поддерживает, хотя в задаче этого не просилось.

Для signed UB. Там надо вот такие штуки делать, как выше в решении на 4 ифа. Сначала сравниваем, потом вычитанием, когда выяснили, что вычитание не даст ub.

если диапазон под вопросом

Русский, мазефакер, говоришь ты его?

а для signed зависит от настроек компилятора (-fstrict-overflow или -O2 без -fno-strict-overflow превращает signed переполнение в UB, а без него оно такое же с заворачиванием).

Для -O2 и больше есть -fwrapv, который определяет это заворачивание. В теории можно написать так:

#pragma GCC push_options
#pragma GCC optimize ("wrapv")

// код, использующий знаковое переполнение

#pragma GCC pop_options

Для signed если нужно поддерживать отрицательные числа и весь диапазон типа - местами оказывается весьма сложно и запутанно даже если no-strict-overflow режим (а всё из-за того что в Си нельзя процовый флаг переполнения после арифметики проверить). Если не нужно - то сначала их отсеиваем как некорректный ввод а затем работаем без переполнений (если больше чем попарно не складываем и не вычитаем).

wrapv и no-strict-overflow как-то связаны друг с другом, то ли первый подразумевает второй, то ли наоборот, то ли они вообще синонимы.

И правильно нельзя. В risc-v нету флага переполнения.

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

А https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html не помогут?

О, круто, полезные штуки, хоть и нестандартные.

А так вроде (если типы не нарушать извне) разницы с функцией не будет.

Типы ведь намного разнообразнее могут быть в отличие от функции. Хоть Int, хоть float/double, хоть указатели, вообще где определены отношения .

Насчет переполнения, на практике если академически писать, то да, нужна проверка конечно, тогда код сильно усложнится.

Ладно, не томите уже, объясните, почему может быть переполнение q0+qlen, если size_t q0, qlen и «Оба диапазона относятся к индексам некоего массива»

Так в этом суть темы была - за переполнениями надо следить. Причём, если это прикладное приложение то ещё можно сделать какие-то предположения о диапазонах входных данных, то в случае общей библиотеки крайне нежелательно добавлять в её апи подобные ограничения и надо поддерживать на входе всё, чего туда могут прислать (в случае с функцией - ограничено типам аргументов, с макросом - вообще ничем).

Потому что h0 hlen это то что у нас есть, а q0 qlen это то что спрашиваем. Оно, конечно, относится к массиву, но находится в рамках заранее не обязано (функция как раз рамки и проверяет).

Прочитал

Оба диапазона относятся к индексам некоего массива или смещениям байт в файле

как h0, hlen и q0, qlen — два диапазона в некотором массиве

Ладно, возможно это было не совсем понятно и надо было это указать где-то кроме названий переменных. Типа h0-hlen это реально существующий диапазон а q0-qlen это некоторые числа, претендующие им быть.

У него по условию не true/false возвращается, а 1/0. Ну и не сказано как должно работать если hlen = qlen = 0. Хотя правильнее наверное обобщить правило для qlen = 0

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

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

влез в аллоцированный блок памяти

В моей вселенной это значит, что сложение q0 и qlen, которые бы относились к типу uintptr_t, не может дать переполнения. Не говоря о том, что «Оба диапазона относятся к индексам некоего массива».

Ну и формулировочки у вас.

Пффффф

Значит я выиграл :) Пойду спать.

q0+qlen <= h0+hlen

Попахивает целочисленным переполнением.

А, уже нашли.

Что-то сильно опасна ваша Сишечка.
Почему if в Си так опасно себя ведёт?

#include <stdio.h>
#include <stdint.h> // SIZE_MAX

int is_contained(size_t h0, size_t hlen, size_t q0, size_t qlen)
{
	printf("h0=%lu\n", h0);
	printf("hlen=%lu\n", hlen);
	printf("q0=%lu\n", q0);
	printf("qlen=%lu\n", qlen);
	
    if (q0 < h0) return 1;
    if (q0 + qlen < h0) return 2;
    if (q0 + qlen > h0 + hlen) return 3;
    return 0;
}

int main (int argc, char ** argv) {
    int r;
    //printf("SIZE_MAX=%lu\n\n", SIZE_MAX);
    r=is_contained(10, SIZE_MAX,  0, SIZE_MAX); printf("r=%u\n\n", r);
    r=is_contained(10, SIZE_MAX, 10, SIZE_MAX); printf("r=%u\n\n", r); // ужас: r=2
    r=is_contained( 0, SIZE_MAX, 10, SIZE_MAX); printf("r=%u\n\n", r);
}

h0=10
hlen=18446744073709551615
q0=0
qlen=18446744073709551615
r=1

h0=10
hlen=18446744073709551615
q0=10
qlen=18446744073709551615
r=2

h0=0
hlen=18446744073709551615
q0=10
qlen=18446744073709551615
r=0

wandrien

https://godbolt.org/z/GE87MqE37

#include <assert.h>
#include <stdbool.h>
#include <limits.h>

static inline
bool contains(unsigned begin, unsigned len, unsigned begin1, unsigned len1) {
    if (begin1 < begin || len1 > len)
        return false;
    
    begin1 -= begin;
    if (begin1 > len)
        return false;    

    len -= len1;
    return begin1 <= len;
}

int main() {
    assert(contains(10, 50, 20, 40));
    assert(contains(0, 0, 0, 0));
    assert(contains(UINT_MAX, 0, UINT_MAX, 0));
    assert(contains(UINT_MAX, UINT_MAX, UINT_MAX, UINT_MAX));
    assert(contains(UINT_MAX - 10, 10, UINT_MAX - 5, 5));
    assert(contains(0, UINT_MAX, UINT_MAX - 1, 0));
    assert(contains(UINT_MAX - 3, 3, UINT_MAX - 1, 1));
    assert(!contains(UINT_MAX, 0, 0, UINT_MAX));
}

Вывод

ASM generation compiler returned: 0
Execution build compiler returned: 0
Program returned: 0

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

З.Ы. «Какой массив?! Какие индексы?!»

Не помню точно на каком курсе ВУЗа, но про кодировку чисел и связанные с кодировкой чисел, диапазонами и получающимися эффектами от этого, точно рассказывают и дают поясняющие примеры.

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

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

Они конечно связаны с представлением чисел в компе, но всё равно, как ты сам и заметил, в других языках это всё может так или иначе отличаться. И даже в самом Си, если перейти на signed числа, при некоторых настройках компилятора поведение будет не таким, как ты наивно ожидаешь от «компьютерной» кодировки знаковых чисел. Так что однозначно следует говорить именно про язык, а не про компы вообще.

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

Ну так ты же как раз «включаешь» дополнительные правила и фичи компилятора (gcc?), а сам язык как бы тут и ни при чем.

Кстати, о какой опции какого компилятора идет речь?

Язык тут как раз причём, без компилятора его не существует, а указанные опции много где дефолт.

Для gcc достаточно указать -O2 (многие его используют дефолтно), не указав рядом -fno-strict-overflow. У clang скорее всего так же. У других компиляторов может быть по-другому. По версии комитета-стандартописателя (который издаёт c89 c99 c11) данный режим вообще единственный возможный.

Так и компилятора без языка не существует.

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

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

Ты же создал тему изначально про неявные «нюансы» арифметики, которые для тебя и многих являются неожиданным открытием.

Я же просто пояснил, что причина наличия «нюансов» не в языке, а в выбранной кодировке чисел в виде двоичной информации и что это давали в ВУЗе, по крайней мере в мое время, в том ВУЗе где я учился.

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

Только и всего.

Надо знать причину наличия «нюансов», тогда она не сможет стать неожиданностью в любом языке.

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

Так что операции сложения и вычитания можно проводить как беззнаковые с гарантированным результатом.

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

Верно.

Поясняющий пример такой:

#include <stdio.h>

int main(void) {
  signed char a, b;
  a = 100;
  b = 100;
  a += b;
  if(a>100) printf ("a>100");
  else printf("a<100");
  return 0;
}

В режиме no-strict-overflow (который совпадает с машинным представлением чисел) будет выведено a<100. В режиме strict-overflow, который автоматически включается ключом -O2 у gcc, который подразумевается в C89/C99/C11 и который в каком-то другом компиляторе может оказаться дефолтным или вообще неотключаемым - тут получается UB и он может вывести любую из надписей (хотя конкретно этот пример на моём gcc10 стабильно выдаёт a<100 но это не гарантируется), или вообще непредсказуемо сломать порядок выполнения.

Побитово это не объяснить, потому что компилятор может тупо выкинуть if или заменить условие в нём на другое, которое ты не писал, но которое, по мнению компилятора, будет давать тот же результат если не случилось переполнение.

Ты же создал тему изначально про неявные «нюансы» арифметики, которые для тебя ... являются неожиданным открытием.

Нет, не являются. С чего ты взял?

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

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

#include <stdio.h>

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

void examine(int x) {
  if(x<0) x = -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++;
  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) {
  examine(1);
  examine(-1);
  examine(INT_MIN);
  examine2(INT_MAX);
  return 0;
}

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

Непонятно, чего ты пытаешься добиться.

Есть чёткие правила, переполнение signed в текущей версии стандарта - UB.

Поэтому нужно либо писать код без UB на signed, либо интерпретировать числа как unsigned, делать арифметику на беззнаковых и затем правильно интерпретировать результат.

Всё остальное - непортабельно.