Introduction

PDEP is a new instruction from BMI2 (Bit Manipulation Instruction), pseudocode for 32-bit PDEP variant:

src    - a source word
mask   - a mask

result := 0
k := 0
for i := 0 .. 31 loop
    if mask.bit[i] then
        result.bit[i] := src.bit[k]
        k := k + 1
    end if
end loop

Quite complicated, but it is really fast — latency is just 3 cycles and throughput is only one cycle. I've showed how to use this instruction in conversion integers to binary and haxadecimal representation.

I was wondering how this algorithm would execute on an old hardware.

Naive implementation

uint32_t naive(uint32_t src, uint32_t mask) {

    uint32_t result   = 0;
    uint32_t mask_bit = 1;
    uint32_t src_bit  = 1;
    int i;

    for (i=0; i < 32; i++, mask_bit <<= 1) {
        if (mask & mask_bit) {
            if (src & src_bit) {
                result |= mask_bit;
            }

            src_bit <<= 1;
        }
    }

    return result;
}

Shift right by 1 could be expressed as a simple add, on x86 this could also be encoded using LEA (no register flags dependecy).

Branchless implementation

uint32_t branchless(uint32_t src, uint32_t mask) {

    uint32_t result = 0;

    while (1) {

        // 1. isolate the lowest set bit of mask
        const uint32_t lowest = (-mask & mask);

        if (lowest == 0) {
            break;
        }

        // 2. populate LSB from src
        const uint32_t LSB = (uint32_t)((int32_t)(src << 31) >> 31);

        // 3. copy bit from mask
        result |= LSB & lowest;

        // 4. clear lowest bit
        mask &= ~lowest;

        // 5. prepare for next iteration
        src >>= 1;
    }

    return result;
}

Comparison results on Pentium M

The branchless version is much more complicated, but there is one clear advantage over naive version — number of iterations is equal to number of bits set in a mask.

This is clear when we look at sample results.