Простой интервал/пересечение диапазона с переполнением

Question

Я пишу диспетчер физической памяти, который получает некоторые интервалы памяти из BIOS, которые не используются критическими системными данными. Каждый интервал имеет 0 <= start <= 2^32 - 1 и 0 <= length <= 2^32. Я уже отфильтровывал интервалы нулевой длины.

Учитывая два интервала S и T, я хочу обнаружить , как они пересекаются. Например, S начинается до T и заканчивается в пределах T (картинка a)? Или S начинается до T и заканчивается после T (картинка c)?

Можно подумать, что решение тривиально:

uint s_end = s_start + s_length; 
uint t_end = t_start + t_length; 

if (s_start < t_start) 
    // S starts before T 
else if (s_start < t_end) 
    // S starts within T 
else 
    // S starts after T 

if (s_end <= t_start) 
    // S ends before T 
else if (s_end <= t_end) 
    // S ends within T 
else 
    // S ends after T 

Проблема заключается в переполнении: Я технически ограничен 32-разрядное целое число и интервалы могут (и часто) использовать весь спектр имеющихся целые числа. Например, на рисунке b, t_end равно 0 из-за переполнения. Или даже, как на рисунке ft_start = t_end = s_start = 0 пока t_length != 0.

Как я могу заставить эти условия пересечения интервалов работать с учетом переполнения?

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

^{Хотя моя проблема с 32-разрядными целыми числами, в этом образе я использовал 4-битные целые числа только упростить. Проблема остается прежней.}

Answer 1

Одним из решений является для лечения конца 0, как частный случай. Соединив это с if-утверждениями, оно становится следующим:

uint s_end = s_start + s_length; 
uint t_end = t_start + t_length; 

if (s_start < t_start) 
    // S starts before T 
else if (t_end == 0 || s_start < t_end) 
    // S starts within T 
else 
    // S starts after T 

if (s_end != 0 && s_end <= t_start) 
    // S ends before T 
else if (t_end == 0 || s_end == t_end 
    || (s_end != 0 && s_end <= t_end)) 
    // S ends within T 
else 
    // S ends after T 

Это выглядит правильно.

Answer 2

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

Чтобы решить проблему переполнения, вы можете попытаться добавить другую математику, основанную на начальном сравнении, которая не будет включать вычисления концов вообще. Что-то вроде:

if (s_start < t_start) 
{ 
    // S starts before T 
    uint start_offset = t_start - s_start; 
    if (start_offset < s_length) 
    { 
     if (s_length - start_offset < t_length) 
     { 
      // ... 
     } 
     else ... 
    } else ... 
} 

Answer 3

ОК, проблема, если вы хотите, чтобы ваши диапазоны, чтобы охватить все п-бит, любые расчеты, основанные на старте/конце имеет потенциал переполнения.

Итак, трюк состоит в том, чтобы сделать линейное преобразование в место, где ваши вычисления начала и конца не переполняются, не выполняются ваши вычисления, а затем линейное преобразование обратно.

ПРИМЕЧАНИЕ

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

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

ВЫХОД

-11

КОД

#include <iostream> 

using type = uint8_t; 

struct segment 
{ 
    type start, length; 
    type end() const { return start + length; } 
}; 

static segment 
intersect(segment s, segment t) 
{ 
    type shift = std::min(s.start, t.start); 

    // transform so we can safely call end() 
    s.start -= shift;  // doesn't affect length 
    t.start -= shift;  // doesn't affect length 

    // we can safely call end() now ---------------------------------------------- 
    type u_start = std::max(s.start, t.start); 
    type u_end = std::min(s.end(), t.end()); 
    type u_length = u_end - u_start; 

    segment u{ u_start, u_length }; 

    // transform back 
    u.start += shift; 

    return u; 
} 

int main() 
{ 
    segment s{ 3, 13 }, t{ 5, 11 }; 
    segment u = intersect(s, t); 

    std::cerr << uint32_t(u.start) << " " << uint32_t(u.length) << std::endl; 

    return 0; 
} 

Answer 4

Я не знаю, что вы делаете с такими условиями, как (f), поскольку 32-разрядная t_length будет 0. Предполагая, что вы сумели это дело каким-то образом, когда вы отфильтровывать длину = 0, что может означать как 0 и 2^32, основная идея заключается в следующем:

bool s_overflows=false; 
if(s_start>0)//can't have overflow with s_start==0, 
{ 
    uint32 s_max_length=_UI32_MAX-s_start+1; 
    if(s_length==s_max_length) s_overflow=true; 
} 
bool t_overflows=false; 
if(t_start>0) 
{ 
    uint32 t_max_length=_UI32_MAX-t_start+1; 
    if(t_length==t_max_length) t_overflow=true; 
} 

Тогда вы просто сделать ваши расчеты, но если s_overflow true, вы не вычисляете s_end - вам это не нужно, поскольку вы уже знаете, что это 0x100000000. То же самое для t_overflow. Поскольку это уже особые случаи, так же как start = 0, они не должны сильно усложнять ваш код.