1

我正在编写一个物理内存管理器，它从 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。甚至，如图f t_start = t_end = s_start = 0 while t_length != 0。

如何使这些区间相交条件在考虑溢出的情况下工作？

溢出搞砸了我的条件，但我真的不能为此使用 64 位整数（这将是最简单的）。我知道对我的条件进行一些巧妙的改组并使用加法和减法一定是可能的，但是在制作了无尽的图表并思考了几个小时之后，我似乎无法理解它。

间隔的一些例子

虽然我的问题是 32 位整数，但在这张图片中，我使用 4 位整数只是为了简化它。问题仍然相同。

4

4 回答 4

1

好的，问题是，如果您希望您的范围跨越所有 n 位，则任何基于开始/结束的计算都有可能溢出。

所以诀窍是对开始/结束计算不会溢出的地方进行线性变换，进行计算，然后线性变换回来。

笔记

在我们可以安全地调用 end() now行下方，您可以调用排序检查（您的原始代码），这将是安全的，因为在线性变换期间会保留排序。

此外，正如我在上一篇文章中所指出的，存在一种特殊的边界情况，即使您进行此转换，也会溢出（跨越整行的地方） - 但您可以针对该特殊边界条件进行编码。

输出

5 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;
}
于 2013-04-12T19:35:18.287 回答
0

One solution is to treat an end of 0 as a special case. Weaving this into the if-statements, it becomes:

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

This looks correct.

于 2013-04-12T21:29:17.503 回答
0

I don't know what do you do with conditions like (f), since 32-bit t_length will be 0 there. Assuming you've managed this case somehow when you were filtering out length=0, which can mean both 0 and 2^32, the basic idea is this:

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;
}

Then you just do your calculations, but if s_overflow is true, you don't calculate s_end -- you don't need it, since you already know it's 0x100000000. The same for t_overflow. Since these are already special cases, just like start=0, they shouldn't complicate your code much.

于 2013-04-14T16:29:40.103 回答
0

您的示例代码并未列举所有情况。例如，间隔也可以在同一点开始或结束。

要解决溢出问题，您可以尝试根据开始比较添加不同的数学，其中根本不包括计算结束。就像是：

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 ...
}
于 2013-04-12T18:38:50.650 回答