Bit banging exercise in C

Originally posted at sjmulder.nl.

Casey of Molly Rocket posted four interview questions asked for his 1994 Microsoft intership.

This page is about the third: implementing a flood fill check. A flood fill is what you get when you use a bucket tool in a drawing program to fill an area covered by one color with another.

Implementing a flood fill is a fun exercise by itself, but here it's about a specific part in a specific situation -- testing if 4 pixels packed into a byte are all the same specific color:

Implement a function taking a byte (8 bits), representing 4 packed pixels of 2 bits each, and a 2-bit pattern, and checks if all pixels in the byte match the pattern:

int flood_check(uint8_t pattern, uint8_t target)

Examples:

  target     pattern  result      explanation
00 00 00 00    10       0     pattern doesn't occur in target
00 10 10 00    10       0     only par 2 and 3 match
10 10 10 10    10       1     all pairs match

(Update: Casey's video for the problem is online now and it turns out the point was to return true if any of the pixels match, and, preprocessing the pattern is allowed. This yields a very different solution. Worth a watch!)

One solution we could try is comparing each pair individually against the pattern. The process would roughly be:

1. In a copy of target, mask out three of the pairs.
2. Shift pattern left to make it line up with the remaining pair.
3. Compare the two values.
4. Repeat for all 4 pairs.

But there's a more elegant solution that doesn't involve having to figure out these different mask values: pack pattern first and then compare that against target. Suppose we have pattern ab (two bits of unspecified value). We do:

00 00 00 ab    original pattern
00 00 ab 00 pattern shifted left by 2
00 ab 00 00 pattern shifted left by 4
ab 00 00 00 pattern shifted left by 6
----------- OR
ab ab ab ab     packed pattern

In C, << is the shift-left operator and | performs the binary OR.

Now it's a matter of comparing the packed pattern to target. Implementation:

int flood_check_1(uint8_t pattern, uint8_t target)
{
        return (pattern << 6 |
                pattern << 4 |
                pattern << 2 |
                pattern) == target;
}

This version does require that pattern really only holds two bits; if higher bits are set they will mess up the combined pattern. This can be alleviated by masking out the other bits:

int flood_check_2(uint8_t pattern, uint8_t target)
{
        return ((pattern & 3) << 6 |
                (pattern & 3) << 4 |
                (pattern & 3) << 2 |
                (pattern & 3)) == target;
}

Decimal 3 is 11 in binary. AND-ing that with another value using & masks out other bits, that is to say, any other bits that are 1 become 0.

Bonus: x86-64 assembly

As an additional exercise, I thought it fun to implement the same in x86-64 assembly. Here is the listing in NASM syntax:

flood_check_x86_64:
        xor  eax, eax   ; clear register A, the output register
        xor  ecx, ecx   ; clear register C, for our packed pattern
        mov  cl, dil    ; copy pattern to C (1 byte)
        and  cl, 3      ; mask out all but lower 2 bits
        mov  al, cl     ; copy pattern to A where we'll pack it
        shl  al, 2      ; shift left by 2
        or   al, cl     ; OR with pattern. now 2 packed patterns in C
        shl  al, 2
        or   al, cl     ; and again, now 3 packed patterns in C 
        shl  al, 2
        or   al, cl     ; and again, now 4 packed patterns in C
        cmp  al, sil    ; compare with target in SI
        sete al         ; 1 if equal
        ret

Again given pattern ab, this version builds up the packed ab ab ab ab, used to test against target, by repeatedly shifting left and adding the pattern on the end:

00 00 00 ab  shift left, OR with pattern
00 00 ab ab  shift left, OR with pattern
00 ab ab ab  shift left, OR with pattern
ab ab ab ab

Some notes on assembler and this code:

• mov assings a value, shl is shift-left, cmp compares (setting status flags), sete sets a register to 1 if comparison was equal. In this syntax, the left operand is also the destination, e.g., or a, b is equivalent to a = a | b in C.
• We're using the A, C, SI, and DI registers. They are 64 bits, but e.g. eax refers to the lower 32 bits of A, and al to the lower 8 bits. Instructions using these smaller values generally take up fewer bytes in machine code.
• This x86-64 calling convention places the first two function arguments in DI and SI respectively, and expects a return value in A.
• xor eax, eax is equivalent to mov eax, 0 but yields shorter machine code. It even clears the upper 32 bits of the full 64 bit register.

Perhaps this could be taken to the next level by using vector instructions to "fan out" the pattern or target and compare, but that's way beyond my so I'll use the easy cop-out of leaving that as "an exercise for the reader".

Comments welcome on Mastodon or below.