Bit banging exercise in C
Tags: c, algorithms, beginners, assembly
Published: 2023-08-12 10:09:01

*Originally posted at [sjmulder.nl](https://sjmulder.nl/2023/casey-interview-3.html).*

Casey of *[Molly Rocket](https://www.youtube.com/@MollyRocket)* posted [four interview questions](https://www.youtube.com/watch?v=DS7ygFv84yk) 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:
>
> ```c
> 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](https://www.youtube.com/watch?v=OE_UNZW-4_U) 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:

```c
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:

```c
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](https://nasm.us/) syntax:

```assembly
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](https://en.wikipedia.org/wiki/X86_calling_conventions#System_V_AMD64_ABI) 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](https://bsd.network/web/@sjmulder/110827408702958909) or below.