Databases
StackOverflow2013
Postsdbo
POSimple interval/range intersection with overflow
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSimple interval/range intersection with overflow
    text
    copied!<p>I'm writing a physical memory manager that gets some intervals of memory from the BIOS that are not used by crucial system data. Each interval has <code>0 &lt;= start &lt;= 2^32 - 1</code> and <code>0 &lt;= length &lt;= 2^32</code>. I have already filtered out the zero-length intervals.</p> <p>Given two intervals S and T, I want to detect <em>how</em> they intersect. For example, does S start before T and end within T (picture <em>a</em>)? Or does S start before T and end after T (picture <em>c</em>)?</p> <p>You'd think the solution is trivial:</p> <pre class="lang-cpp prettyprint-override"><code>uint s_end = s_start + s_length; uint t_end = t_start + t_length; if (s_start &lt; t_start) // S starts before T else if (s_start &lt; t_end) // S starts within T else // S starts after T if (s_end &lt;= t_start) // S ends before T else if (s_end &lt;= t_end) // S ends within T else // S ends after T </code></pre> <p>The problem is overflow: I am technically limited to a 32-bit integer and the intervals can (and often do) use the whole range of available integers. For example in figure <em>b</em>, <code>t_end</code> equals 0 due to overflow. Or even, as in figure <em>f</em> <code>t_start = t_end = s_start = 0</code> while <code>t_length != 0</code>.</p> <p><strong>How can I make these interval intersection conditions work with overflow taken into account?</strong></p> <p>The overflow screws up my conditions, but I <em>really</em> can't use a 64-bit integer for this (that would be easiest). I know it must be possible using some clever reshuffling of my conditions and using addition and subtraction, but after making endless diagrams and thinking about it for hours, I can't seem to be able to wrap my head around it.</p> <p><img src="https://i.stack.imgur.com/HlpX5.png" alt="Some examples of intervals"></p> <p><sup>While my problem is with 32-bit integers, in this image I used 4-bit integers just to simplify it. The problem remains the same.</sup></p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload