3-3 Detecting a Power-of-2 Boundary Crossing

Assume memory is divided into blocks that are a power of 2 in size, starting at address 0. The blocks may be words, doublewords, pages, and so on. Then, given a starting address a and a length l, we wish to determine whether or not the address range from a to a + l - 1, l 2, crosses a block boundary. The quantities a and l are unsigned and any values that fit in a register are possible.

If l = 0 or 1, a boundary crossing does not occur, regardless of a. If l exceeds the block size, a boundary crossing does occur, regardless of a. For very large values of l (wraparound is possible), a boundary crossing can occur even if the first and last bytes of the address range are in the same block.

There is a surprisingly concise way to detect boundary crossings on the IBM System/370 [CJS]. This method is illustrated below for a block size of 4096 bytes (a common page size).

O   RA,=A(-4096) 
ALR RA,RL 
BO?CROSSES 

The first instruction forms the logical or of RA (which contains the starting address a) and the number 0xFFFFF000. The second instruction adds in the length, and sets the machine's 2-bit condition code. For the add logical instruction, the first bit of the condition code is set to 1 if a carry occurred, and the second bit is set to 1 if the 32-bit register result is nonzero. The last instruction branches if both bits are set. At the branch target, RA will contain the length that extends beyond the first page (this is an extra feature that was not asked for).

If, for example, a = 0 and l = 4096, a carry occurs but the register result is 0, so the program properly does not branch to label CROSSES.

Let us see how this method can be adapted to RISC machines, which generally do not have branch on carry and register result nonzero. Using a block size of 8 for notational simplicity, the method of [CJS] branches to CROSSES if a carry occurred ((a | -8) + l 2³²) and the register result is nonzero ((a | -8) + l 2³²). Thus, it is equivalent to the predicate

This in turn is equivalent to getting a carry in the final addition in evaluating ((a | -8) -1) + l. If the machine has branch on carry, this can be used directly, giving a solution in about five instructions counting a load of the constant -8.

If the machine does not have branch on carry, we can use the fact that carry occurs in (see "Unsigned Add/Subtract" on page 29) to obtain the expression

Using various identities such as ?x - 1) = -x gives the following equivalent expressions for the "boundary crossed" predicate:

These can be evaluated in five or six instructions on most RISC computers.

Using another tack, clearly an 8-byte boundary is crossed if

This cannot be directly evaluated because of the possibility of overflow (which occurs if l is very large), but it is easily rearranged to 8 - (a & 7) < l, which can be directly evaluated on the computer (no part of it overflows). This gives the expression

which can be evaluated in five instructions on most RISCs (four if it has subtract from immediate). If a boundary crossing occurs, the length that extends beyond the first block is given by l - (8 - (a & 7)) which can be calculated with one additional instruction (subtract).