• MatthewWilcox
• NaturallyAlignedOrder

This is an encoding scheme that allows us to describe an offset and an order with a single extra bit. While this sounds like black magic, it's even relatively efficient to encode/decode.

To start with a toy example, imagine we have four pages numbered 0-3. We have eight possible things to describe, each of the four pages of order 0 (size 1); pages 0 and 2 of order 1 (size 2); page 0 of order 2 (size 4) and no page. Clearly we can encode eight things in 3 bits, so we need one extra bit beyond the two bits we need to describe the four pages.

OK, so how do we encode this information in a regular fashion? There are a few different ways to do this (eg inverting all the bits, or using top bits instead of low bits), but here's the one I like:

If bit 0 is set, the described object is order 0, and bits 1-N are the offset. If the bottom two bits are 10b, the object is order 1. Bits 2-N multiplied by two are the offset. If the bottom three bits are 100b, the object is order 2. Bits 3-N multiplied by four are the offset. ... and so on. If all bits are zero, there is no object.

Example (bold highlights the bits used for order)

int decode_order(unsigned long data)
{
    return ffsl(data) - 1;
}

unsigned long decode_offset(unsigned long data)
{
    return (data & (data - 1)) / 2;
}

unsigned long encode_offset_order(int order, unsigned long offset)
{
    assert(offset & ((1UL << order) - 1) == 0);
    return (1UL << order) | (offset * 2);
}

decode_order() will return -1 for the "no object" case. Or you can test for that explicitly before calling these functions. encode_offset_order() cannot return "no object"; you would set that up yourself.