DEV Community: Sijmen J. Mulder

Circle drawing algorithm in C

Sijmen J. Mulder — Sat, 12 Aug 2023 12:35:14 +0000

Originally posted at sjmulder.nl.

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

This page is about the final interview question: drawing a circle. I have to admit that this got me scratching my head a little bit at first!

Given a plot() function, which can be used to draw individual pixels, write a function that draws a circle around center point (cx,cy) with radius r, using only integer math:
void plot(int x, int y);                 /* provided */
void plot_circle(int cx, int cy, int r); /* implement */

My first thought was to step through angles 0 to 360 in small steps, then use sin(angle)*r and cos(angle)*r to calculate the positions on the circle, and finally draw lines between them. Lucky me for even remembering the cos/sin thing but there are problems:

We're not supposed to be using floating point math - it was 1994 after all.
Using large steps for the angles yields an ugly circle with clearly visible corners (Figure 1).
Now we have to implement line drawing too!

Figure 1: a circle drawn from 16 discrete angle steps. Not pretty.

So let's try something else: start from (cx,cy-r). This is the top of the circle and easily calculated. Plot a point. We know the circle goes on to the right (for r pixels), so step right by one pixel. From the top going right the circle slopes down, so we might have to take one or more steps down to remain on the edge.

Just how many steps down we need to make to meet the edge again we can find with the observation that the edge of the circle is always exactly the radius r away from the middle - for a circle of radius 5, the center is 5 units away from every point on the edge. Hence, we need to step down until we are less than r pixels away from (cx,cy) (Figure 2).

Figure 2: hugging the edge

We can use Pythagoras' Theorem for the distance test:

sqrt(x^2^ + y^2^) < r

The square root is an expensive floating point operation, but we can do without:

x^2^ + y^2^ < r^2^

Now we can write the first version of the function that draws just a single quadrant:

void plot_circle(int cx, int cy, int r)
{
        int x, y;

        for (x=0, y=r; x < r; x++)
        for (; y >= 0; y--) {
                plot(cx+x, cy+y);

                if (x*x + (y-1)*(y-1) < r*r)
                        break;
        }
}

The horizontal steps are bounded to r, the far right of the circle, and the vertical steps end when level with the center. Note that if the y axis points down in the coordinate system (as it often does in computer graphics), we're actually starting at the bottom of the circle and drawing the bottom right quadrant.

Now we have a quarter of a circle (Figure 3).

Figure 3: 1/4th of the way there

Actually, we're almost all the way there! There's no need to repeat this loop four times, we can simply plot each point three more times at the inverted x and y to mirror the arc:

void plot_circle(int cx, int cy, int r)
{
        int x, y;
        for (x=0, y=r; x < r; x++)
        for (; y >= 0; y--) {
                plot(cx+x, cy+y);
                plot(cx+x, cy-y);
                plot(cx-x, cy+y);
                plot(cx-x, cy-y);
                if (x*x + (y-1)*(y-1) < r*r)
                        break;
        }
}

A final change we can make is with the observation that the path back from the right edge to the top is the same as from the top to the right edge, except with the coordinates flipped - e.g. if from the top you go right and down, the same steps can be made up and left from the right side of the circle. We can compute just 1/8th of a circle and mirror it 7 times (Figure 4):

void plot_circle(int cx, int cy, int r)
{
        int x, y;

        for (x=0, y=r; x < y; x++)
        for (; y >= 0; y--) {
                plot(cx+x, cy+y);
                plot(cx+x, cy-y);
                plot(cx-x, cy+y);
                plot(cx-x, cy-y);

                plot(cx+y, cy+x);
                plot(cx+y, cy-x);
                plot(cx-y, cy+x);
                plot(cx-y, cy-x);

                if (x*x + (y-1)*(y-1) < r*r)
                        break;
        }
}

Figure 4: turn on the photocopier!

Finally, here’s a "screenshot" of my beautiful makeshift terminal text plotter:

Aside: I had a fun time making the graphics on the original web version of this post. Initially I used Inkscape to make the SVGs, but when viewing this page in dark mode the lines would barely be visible. By writing <svg> code directly into the HTML I could use CSS to adjust the colors in dark mode, like the rest of the site. Try it! (Use your OS or browser setting.)

Comments welcome on Mastodon or below.

Bit banging exercise in C

Sijmen J. Mulder — Sat, 12 Aug 2023 10:09:01 +0000

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:

In a copy of target, mask out three of the pairs.
Shift pattern left to make it line up with the remaining pair.
Compare the two values.
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.

String copy in C

Sijmen J. Mulder — Sat, 12 Aug 2023 09:34:59 +0000

Originally posted at sjmulder.nl.

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

This page is about the second: implementing a string copy function:

Implement strcpy(), which copies a string into another buffer (we don't care about the return value for now):
char *strcpy(char *src, char *dst);

Let's get this out of the way: using this function is usually a bad idea because you need to be absolutely sure that the destination buffer can fit the full source string. Instead, use strcpy_s() if available, strclpy(), or even snprintf() (snprintf(dst, sizeof(dst), "%s", src)).

Let's do a simple for-loop copy first:

void strcpy_1(char *src, char *dst)
{
        size_t len, i;

        len = strlen(src);

        for (i=0; i < len; i++)
                dst[i] = src[i];

        dst[len] = '\0';
}

We find the length of the string, then copy it over one char at a time. Don't forget the null termination!

But since strlen has to walk the string to find the null terminator, we's looping over the string twice! See by expanding strlen:

void strcpy_2(char *src, char *dst)
{
        size_t len=0, i;

        for (i=0; src[i] != '\0'; i++)
                len++;
        for (i=0; i < len; i++)
                dst[i] = src[i];

        dst[len] = '\0';
}

Let's put that in one loop:

void strcpy_3(char *src, char *dst)
{
        size_t i;

        for (i=0; src[i] != '\0'; i++)
                dst[i] = src[i];

        dst[i] = '\0';
}

This works perfectly fine, but we can avoid having the i variable altogether by incrementing src and dst directly. Walking a pointer like that is a common idiom in C:

void strcpy_4(char *src, char *dst)
{
        while (*src != '\0') {
                *dst = *src;
                src++;
                dst++;
       }
}

Our final change is to simplify this version by removing the explicit \0 comparison and folding the increment expressions into the assign statement - which may make your hair stand up but this access-and-increment pattern is so common that it's a useful trick to know:

void strcpy_5(char *src, char *dst)
{
        while (*src)
                *dst++ = *src++;

        *dst = '\0';
}

Let's dissect that: *dst++ is *(dst++). The ++ here is post-increment, which means that first the old value is returned, and only after the statement the new value is assigned to dst. So first *dst = *src is performed, and only then are dst and src incremented - just like in the previous version.

Perhaps a lot to grasp for those unfamiliar with this pattern, but again it's a often-used solution to this common situation. For a different take, here's how OpenBSD implements the function with a for loop instead (and also returning the copied string, per spec):

char *
strcpy(char *to, const char *from)
{
    char *save = to;

    for (; (*to = *from) != '\0'; ++from, ++to);
    return(save);
}

Appendum

Casey's video on this question is out now. His solution was:

for (int i=0; (dst[i] = src[i]); i++) ;

I hadn't thought to use the result of the assignment as the loop condition. Now you also don't need the extra \0 assignment because that happens in the last iteration of the loop.

Another version from the video:

while (*dst++ = *src++) ;

In a Borland C compiler of the time the first version generates faster code.

Comments welcome on Mastodon or below.

Rectangular array copy in C

Sijmen J. Mulder — Sat, 12 Aug 2023 09:09:10 +0000

Originally posted at sjmulder.nl.

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

This page is about the first: rectangular array copy. Essentially:

Implement a function to copy a rectangular section from one
two-dimensional byte array to another, e.g.:
void rect_copy(
    char *src_buf, int src_stride,
    char *dst_buf, int dst_stride,
    int x0, int y0, int x1, int y1, int w, int h);

Casey's own explainer video is already online by now but I thought it fun to have a go myself, event hough this is a fairly straightforward question for most programmers with some C experience.

First, let's go through the signature:

src_buf and is the source buffer.
src_stride is the line length in the source buffer -- that is to say, when you're at column x in row y, advancing stride elements through the buffer gets you to the same column x on row below, y+1.
dst_buf and dst_stride are the same but for the destination array.
x0 and y0 are the column and row of the top left corner of the source rectangle, in the source array.
x1 and y1 are the column and row of the top left corner of the destination rectangle, in the destination array.
w and h are the width and height of the rectangle to be copied. Because no scaling is to be applied, these are the same for the source and destination rectangle.

As is implied here, two-dimensional arrays are represented in memory by laying out the rows sequentially -- the last element is one row is followed by the first element of the next.

I decided that the simplest approach would be to use two counters, y and x, to loop over every position in the rectangle and then calculate the indices in both arrays in the loop:

void rect_copy(
    char *src_buf, int src_stride,
    char *dst_buf, int dst_stride,
    int x0, int y0, int x1, int y1, int w, int h)
{
    int x, y;

    for (y=0; y<h; y++)
    for (x=0; x<w; x++) {
        dst_buf[dst_stride * (y1+y) + x1+x] =
                src_buf[src_stride * (y0+y) + x0+x];
    }
}

So given an x and y position relative to our rectangle origin, we find the position of that element within either array by taking the starting position (the buf pointer), taking y jumps of length stride to get to the correct row, and then finally adding x to get to the position.

This is a common idiom for accessing multi-dimensional arrays in C. If the length is known at compile-time we can declare a 2-dimensional array directly, e.g. int cells[25][80]; for 25 rows of 80 elements, but that syntax will use the same logic.

While clear in intent and readable (in my opinion) this solution could be optimized, which is what Casey did in his solution. By keeping an offset that is incremented +1 for every column and +stride for every row, no multiplication would be necessary.

No big takeaways here, hope you have a nice day! Comments welcome on Mastodon or below.