title: Simple interval/range intersection with overflow
body: <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>