Establishing the requirements of the starfield simulator
Most people reading this will already be familiar with what a starfield simulator is. In it's most simple form, it's essentially just an animation of white pixels radiating out from the centre of the screen, to give a visual illusion of travelling quickly through space and passing an infinite number of stars on the way.
This will be our starting point. Once it's working, we'll look at various enhancements to improve it's visual appeal.
Although this is really a programming exercise, we'll approach this project as if we needed to create a starfield animation sequence to use as part of a larger multimedia project. A background for credits at the beginning or end of a video presentation, maybe.
The output from our program will be a series of sequentially numbered image files in ppm format. This format is easily manipulated by most graphics and video editing software, which is important since we want to be able to use our newly generated starfield for something useful rather than just looking at it. The ppm image format is ideal for this use case for several reasons. Firstly, it's completely uncompressed so the code to write it is very simple indeed. Secondly, processing uncompressed ppm data uses very little cpu time. Thirdly, since there is obviously no lossy compression, there will be no unwanted compression artifacts to degrade the image quality.
The disadvantage, of course, of using an uncompressed format for output, is that we will create a large amount of data, about six megabytes per animation frame at a resolution of 1920 × 1080 in 24-bit color. However, this data only ever needs to be stored temporarily, as our program will always allow us to re-create the exact same image data whenever we need it. Once we're satisfied with a particular output, all we need to retain on disk is about 3 Kilobytes of C source code. Contrast this with creating a similar starfield animation sequence with third party graphics software for use in a multimedia project such as a video. Although it might be easy to create a generic, random starfield and output it as a video file, it might be much more difficult to re-create the exact same, pixel-identical effect again. You'd probably end up having to keep a multi-megabyte video file of the starfield hanging around in case you ever needed to re-create your final presentation from the original source material at some point in the future.
If it seems like that wouldn't matter, think again. Some random starfields might just look better than others when text is overlayed on top of them, or certain star movements might just happen to cause noticeable compression artifacts when the final output media is prepared. Here at Exotic Silicon, we deliver work to the highest standards, and these details matter to us.
So our overall requirements are to write a series of ppm image files to disk, containing a few white or light colored pixels which start at or near the centre of the screen, and radiate further outwards to the edge with each successive frame. Critically, although the sequence should appear random, it should be possible to re-create the exact same pixel-identical sequence on each run so that we can avoid having to store the large ppm files other than temporarily.
Making an organised start
We'll begin by creating a template for a version history, including the C standard library, and defining our main function. If you're writing software for external distribution, it's a good idea to include the license text as comments at the beginning of the file before the version history. Writing original code gives us a free choice of distribution license, and like all of the other projects in this series, this code is licensed under the ESASSL.
So we begin with something like this:
/* Starfield simulation, Exotic Silicon programming project 1 */
/*
Copyright 2021, Exotic Silicon, all rights reserved.
Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:
1. This software is licensed exclusively under this specific license text. The
license text may not be changed, and the software including modified versions
may not be re-licensed under any other license text.
2. Redistributions of source code must retain the above copyright notice, this
list of conditions, and the following disclaimer.
3. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions, and the following disclaimer in the documentation
and/or other materials provided with the distribution.
4. All advertising materials mentioning features or use of this software must
display the following acknowledgement: This product includes software
developed by Exotic Silicon.
5. The name of Exotic Silicon must not be used to endorse or promote products
derived from this software without specific prior written permission.
6. Redistributions of modified versions of the source code must be clearly
identified as having been modified from the original.
7. Redistributions in binary form that have been created from modified versions
of the source code must clearly state in the documentation and/or other
materials provided with the distribution that the source code has been
modified from the original.
THIS SOFTWARE IS PROVIDED 'AS IS' AND ANY EXPRESS OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
EXOTIC SILICON BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
OF SUCH DAMAGE.
*/
/* 20211231 - Version 1.0 */
/* Initial version */
#include <stdio.h>
int main(int argc, char * argv[])
{
}
More comments than code, and that is a good start. Well written source code should be absolutely full of comments explaining the reasons why the code was written the way it was. There are an almost infinite number of ways to program the same thing, and it's useful to know whether the decisions to implement it the way it has been implemented were taken consciously with some particular specialist knowledge of the task in hand, or whether it was just an arbitrary choice. Whether you're looking at somebody else's code, or code you wrote yourself twenty years ago, you'll often see what look like obvious improvements. But can you be sure that you're not just about to introduce bugs that the original programmer was careful to avoid? Don't be lazy. Comment your code.
Of course, the comments don't all have to live within the source file itself. If you are using a version control system with the facility to store commit messages, then your comments can go there. If code has good supporting documentation elsewhere explaining the algorithms, comments in the source file itself can be more spartan. But please, don't leave your code undocumented. Your future self will thank you!
Note that since we are not going to be processing environment variables in this project, we didn't include the full standard function definition for main(), which would be:
int main(int argc, char * argv[], char * env[])
This isn't intended as an optimisation, (although it does save eight bytes on the stack and one movq opcode when compiled on X86-64), but rather a form of self-documentation. If main() doesn't accept env[], then clearly the program doesn't use it.
The ppm file format
The ppm format that we are going to use has several variations, for storing 1-bit, 8-bit, and 24-bit images in either binary or a rarely-used textual format. They are all very similar, but here we only need to concern ourselves with one of them, the 24-bit binary variant. This consists of a header with four fields in ASCII, separated by spaces, tabs, or newlines, followed by a single space, tab, or newline, and then immediately by binary data in a simple linear RGB format:
$ hexdump -C blank.ppm
00000000 50 36 0a 31 39 32 30 20 31 30 38 30 0a 32 35 35 |P6.1920 1080.255|
00000010 0a 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00000020 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
*
005eec10 00 |.|
005eec11
The first field specifies the variant of the ppm format, which in this case is 6. All of the ppm files we write will begin with a literal ASCII P6 in the first two bytes. The second and third fields specify the dimensions of the image in pixels. The last field specifies the bit-depth of the stored image, in the form of the value that represents 100% intensity of a particular color channel.
So we can do all of our graphics work in an area of memory that we treat as a linear framebuffer, and all we need to do to write a valid ppm file from it is to prepend the four header fields. Simple.
First implementation decision
At this early stage in our development process, we have already arrived at a point where we need to make a fundamental decision about the technique we'll use to create the bitmap data for each frame. This is probably a decision that would have been made for us if we'd been using third party libraries for our coding, but since we're not, we have the freedom to choose.
For each of the stars that we'll be simulating in our starfield, we obviously need to store their location on the current animation frame, and either store or compute some kind of movement vector, to say how quickly they are moving and in which direction.
When we come to write the frame as a ppm file, we could choose to allocate enough memory for the whole frame, which for a 1920 × 1080 pixel, 24-bit image would be 1920 × 1080 × 3 = 6220800 bytes, or almost six megabytes, write pixel data to it as we please, then write the whole block of data out after the ppm header. Alternatively, we could use two nested loops, the outer counting the Y co-ordinate, and the inner counting the X co-ordinate, check our vector data at each pixel point to see what it should be, and then write three bytes, representing one RGB pixel, at a time to disk.
The first method uses an order of magnitude more RAM, but will run much faster as we can do one large write to disk instead of approximately two million small writes.
Obviously, since six megabytes of RAM is a trivial amount to allocate on a typical workstation in 2021, the first approach is the clear winner. However, we do have a choice. If we were working on an embedded system, with significant constraints on memory usage, the situation might be different.
Of course, the two approaches can also be combined. It would be possible to allocate just enough memory for a quarter of the display, for example, which would be about one and a half megabytes. We could then write just calculate the bitmap data for the first 270 rows of pixels, ignoring for the time being any starts which appeared in the lower part of the image, write the data for the first 270 rows out to disk in one go, and then re-parse the vectors of all of the stars, using the same memory to store the next 270 rows of pixel data for output. Performance would be almost as good as writing the whole frame in one go, but memory usage would be reduced by 75%.
At the end of the day, implementation decisions like these are often dictated by the hardware in use. What's good about writing our own code from first principles is that we can do whatever we like.
Let's dive right in and create some functions to manipulate our framebuffer, and write it to disk as a ppm file.
Creating and manipulating a linear framebuffer - memory allocation
We'll start by defining some constants that will be used in various places throughout the code:
#define FRAME_WIDTH 1920
#define FRAME_HEIGHT 1080
#define STARS_TOTAL 500
#define FRAMES_TOTAL 300
These should be fairly self-explanatory. It's good practice to avoid the direct of numerical constants in the code if they occur in more than once place, and if their meaning in any particular context might not be entirely obvious. Not only does it help to avoid bugs due to typographical errors which might be difficult to spot, but it also makes searching the source code easier and more reliable. This is why we've used, STARS_TOTAL rather than perhaps the more obvious TOTAL_STARS, as it's useful for searching to have all star-related defines begin with STAR_.
However, there are exceptions to this general rule that it's best to use constants instead of magic numbers. We're only interested in producing 24-bit RGB output, and this functionality will be hard-coded into the algorithms of the program. Adding extra code to support arbitrary bit-depths makes little sense, if we're not going to need them. Code that doesn't exist can't contain bugs, and the ability to limit the scope of our code to our needs is one of the big advantages of creating a project from scratch. Wherever the magic number 3 occurs in the context of pixel addressing, it should be obvious that we are dealing with 3-byte RGB triplets. Littering the source code with FRAME_BITDEPTH when it will never need to change seems pointless here.
Since we only ever need to manipulate one animation frame at a time, we can allocate memory for a single framebuffer near the beginning of our program, and re-use it for each frame. The memory we need to allocate for image data is 1920 × 1080 × 3 = 6220800 bytes, but we'll add an extra 32 bytes to this so that we can prepend the ppm header just before the actual pixel data. We also need to include the stdlib.h header file along with the other include near the top of our source, to use the memory allocation functions:
int main(int argc, char * argv[])
{
unsigned char * framebuffer;
framebuffer=malloc(32 + FRAME_WIDTH * FRAME_HEIGHT * 3);
if (framebuffer==NULL) { return (1); }
return (0);
}
A few things to note here. We've used a multiplication within the malloc, and whenever you do this it's wise to think about the risk of overflow. If the result of the multiplication overflows and wraps around, you'll likely get less memory allocated than you expected. In this case we can see that we're safe on just about any modern platform, as the values passed are fixed and don't come near to even a 32-bit overflow anyway. However, in general this sort of code warrants some extra care and attention.
The memory won't automatically be zero'ed, which is fine because we'll have to have some routine to set the entire framebuffer to the background color between frames anyway, and that won't necessary be the RGB value 0, 0, 0 as we'll see later on.
If we work with an X-Y co-ordinate grid that places (0,0) at the top left of the frame, then the 8-bit RGB pixels for any location are found at the three bytes starting at 32+((Y * FRAME_WIDTH + X) * 3). No need for any fancy C structures or object-orientation, we just write RGB values to the calculated addresses.
Enhanced malloc features in OpenBSD
Before we leave the area of memory allocation, note that the OpenBSD implementation of malloc includes features that are very useful for detecting out of bounds accesses and other memory management bugs during software development. Various options can be set, and they are detailed in the manual page for malloc, but the most interesting ones for our purposes are CFG and J, to enable canaries, enhanced free checking, guard pages, and junking. To enable them globally, we can set the sysctl vm.malloc_conf:
sysctl vm.malloc_conf=CFGJ
Currently, the S option enables exactly these options as you can see by looking in /usr/src/lib/libc/stdlib, but since this behaviour could theoretically change in the future, I always prefer to specify the options manually.
This basically gains us two things. Firstly, we'll get an immediate segmentation fault and program termination if we try to write outside of our allocated memory. Secondly, reading allocated memory before writing to it will return the byte value 0xDB, which should be a fairly obvious indicator that our code is buggy.
If you've used versions of OpenBSD before 6.5, you might have enabled these features by creating a symbolic link /etc/malloc.conf. This was replaced with the above sysctl during the OpenBSD 6.6 development cycle.
After calling malloc, we check the return value, and if it's NULL, indicating failure, we simply exit with status 1. You might be wondering why I've separated the check for NULL into a separate statement instead of using something like:
if ((framebuffer=malloc(32 + FRAME_WIDTH * FRAME_HEIGHT * 3))==NULL) { return (1); }
In this case, the source code is simple enough that the two-line version doesn't really gain anything in clarity, but in more complex examples it often does. A modern optimising compiler should generate the same code for both cases anyway, even though technically in the first example we are testing the value of the variable framebuffer, and in the second example, testing the value of the assignment. This can be clearly seen by comparing the compiler output for the following C source code:
callq malloc@PLT
movq %rax, -24(%rbp)
cmpq $0, -24(%rbp)
jne .LBB0_2
#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned char * i;
i=malloc(4096);
if (i==NULL) { return (1); };
return (0);
}
Even if you're not familiar with X86-64 assembler, it should be fairly easy to see what is going on in these four lines of code. The malloc function is called, and returns it's value in the RAX register. This value is then moved, (copied), into a main memory location, highlighted in red.
callq malloc@PLT
movq %rax, -24(%rbp)
cmpq $0, %rax
jne .LBB0_2
#include <stdio.h>
#include <stdlib.h>
int main()
{
unsigned char * i;
if ((i=malloc(4096))==NULL) { return (1); };
return (0);
}
Next, a comparison is done, but in the first example we compare a literal value of 0x00 with the contents of the memory location that we just wrote to, whereas in the second example, we compare against the RAX register directly, which obviously still contains the same value.
We could reasonably expect that comparing against a memory location would be slower than a comparison against a value in a register. However, this is the assembly code generated by the compiler when it's invoked without using any optimisation. Invoking the C compiler with -O3, we get the following snippet of assembly output for both C programs following the malloc call:
callq malloc@PLT
xorl %ecx, %ecx
testq %rax, %rax
sete %cl
The upshot of all this is that if you're using compound constructs and assignments within if statements simply because you think it will always compile into tighter code, think again.
Don't hurt readability of the source code for an optimisation which doesn't exist.
Writing a ppm file
As we mentioned above, writing a ppm file is as simple as prepending the short ppm header to the data we have in the framebuffer. Although we could do this in a compiler macro too, we'll implement it as an actual function. This makes it easier to do propper error handling in the main program, if for some reason the filesystem operations fail, (which could happen due to a read-only filesystem, or out of free space situation):
/* Write a ppm file to disk */
/* Call with a filename, pointer to the framebuffer, and X and Y dimensions of the data */
/* The framebuffer should contain 32 bytes of scratch space before the pixel data in RGB format. */
/* This will be overwritten with the ppm header. */
/* Returns 0 on success, 1 on error */
int output_ppm(unsigned char * filename, unsigned char * framebuffer, unsigned int x, unsigned int y)
{
unsigned char * ppm_header;
int fd;
int headerlen;
int pos;
if ((fd=open(filename, O_WRONLY | O_CREAT | O_TRUNC, 0664))==-1) { return (1); }
headerlen=sprintf (framebuffer, "P6 %d %d 255\n", x, y);
for (pos=headerlen; pos>0; pos--) { *(framebuffer+31-headerlen+pos)=*(framebuffer+pos-1); }
write (fd, framebuffer+32-headerlen, headerlen+(x*y*3));
close (fd);
return (0);
}
Still, the code for this new function is fairly straightforward.
It's just eighteen lines, five of which are comments.
We do, however, also need to add two more includes for the filesystem functions:
#include <unistd.h>
#include <fcntl.h>
The length of the ppm header can vary by a few bytes, depending on the number of characters needed to represent the values of the dimensions as strings of ASCII characters. This means that we can't just write it at a fixed offset before the pixel data. We could have solved this problem in several ways.
Firstly, instead of allocating extra memory at the beginning of the framebuffer to store the header, we could have simply written the header to it's own buffer, and arranged for the framebuffer allocation to be used exclusively for pixel data, starting at offset zero. The main disadvantage of this approach is that we would then either need to do two separate write calls to write the file to disk, one for the header and one for the pixel data, or alternatively copy the header and the entire framebuffer into another area of memory, just to concatenate them ready to write to disk in one go. Obviously this isn't a very efficient approach. We would also need to either allocate and de-allocate a small buffer for the header on each call to output_ppm, which is inefficient due to the repeated calls to the memory allocation routines, or alternatively, allocate the buffer once in the main program, and pass it's location to the function each time. None of this is particularly efficient.
Secondly, we could have simply padded the ASCII data values for the dimensions with leading spaces, ensuring that they were always, for example, five characters. This would produce a valid ppm file, but it doesn't seem very elegant. Also, there might just be some software somewhere that incorrectly assumes that the fields are always delimited by a single space, tab or newline. As a general rule, it's good to adhere as strictly as possible to standards when writing files for maximum compatibility.
Note that we can't simply call sprintf twice, once to find the length of the string, then, with this information in hand, a second time to write it to the correct offset just before the pixel data. Remember that sprintf will zero terminate the string, leaving an 0x00 byte after the header, which would overwrite the first red value of the first pixel. Of course, since we know that the last byte of the header is going to be 0x0a for a newline, we could have just left this off of the format string passed to sprintf, and allowed the zero terminating byte to be written in it's position, in the last byte before the start of the pixel data. We could then have overwritten that 0x00 byte with 0x0a, and achieved the same result as we have with the code above. However, this would still mean making two calls to sprintf, which seems like inefficient coding.
So finally we arrive at the solution above. Write the header of unknown length to the very beginning of the extra 32 bytes that we allocated before the pixel data, and once we know it's length, which we get from the return value of sprintf, copy it to the correct position just before the pixel data. Then we just write the buffer to disk starting from where we wrote the first character of the header.
Sounds simple, and essentially it is, but we have to pay attention to a few details.
Most importantly, we copy the header backwards, starting at the last character. This is essential, because if the header is longer than 16 bytes, (and for our 1920 × 1080 8-bit RGB data it will be 17 bytes), then the bytes containing the end of the header that we are reading are the same bytes that we are going to write the beginning of the header to in it's new location.
Here we can see a potential bug that would only show up if certain conditions were met. If we only ever tested the code by writing image files with small dimensions, it could easily go un-noticed. This is a prime example of why writing good code means understanding the implications of any particular implementation and choice of algorithm, and why we should not just assume that because code runs to completion without producing errors that it's bug-free.
In this example, the values for x and y are passed to the function as unsigned integers, ensuring that we don't have to do any error handling for negative or overly large values that would create a header exceeding 32 bytes.
We have to remember, too, that the value returned by sprintf is 1-based, as it is the number of characters written, not including the zero terminating byte. So if our header contains 17 characters, sprintf returns 17. However, the byte offsets that we are interested in copying are 0 through 16. This is why our formulas for calculating the destination and source byte offsets are framebuffer+31-headerlen+pos, and framebuffer+pos-1. The last byte to copy is obviously when pos=headerlen, and we want this byte written at offset 31, as our pixel data starts at offset 32. However, we want to read this byte from offset pos-1, as our source offsets are zero-based, and go from zero to pos-1, not from 1 to pos.
Sensible coding practicies
The issues mentioned above also clearly demonstrate a good reason to be vary, very wary of writing code like this:
Dubious
for (pos=headerlen+1; --pos;) { *(framebuffer+31-headerlen+pos)=*(framebuffer+pos-1); }
for (pos=headerlen; pos--;) { *(framebuffer+31-headerlen+pos+1)=*(framebuffer+pos); }
The two examples above are valid C code, and produce the same output. They both move the decrement of pos into the condition part of the for loop, and leave the third argument of the for statement empty. This works, because pos-- will return the original value of pos, and --pos will return the post-decremented value. Values above zero will evaluate to true, the condition part of the loop is satisfied, and it continues. Once the value of pos is zero, the condition part of the loop evaluates to false, and the loop ends.
However, we need to remember that the compiler evaluates the condition part of the for statement before each iteration of the loop, and the third part of the for statement at the end of each iteration of the loop. By simply moving the pos-- into the condition part of the loop, we've adjusted the bounds that the loop will iterate over. The value of headerlen initially assigned to pos will be decremented by one before the loop is entered, regardless of whether we use pos-- or --pos.
If used correctly, code like this is absolutely fine. The assembler output from the compiler will likely be a few opcodes shorter, unless the value assigned to pos is a constant. The big risk, though, is that at some point we might want to change the code or re-use it elsewhere, and in the process, change the bounds of the loop. It would be a very easy oversight indeed to introduce an off-by-one error when we did this.
Overall, it's important to balance readability of the source code with micro-optimisations. If you're happy with writing code like this, and have enough experience to be confident that you will always be fully aware of what it's doing, that's fine. But in that case, you probably wouldn't need to be reading this tutorial anyway.
Of course, we could have just wasted a byte of RAM, and written the data to location framebuffer+1 in the sprintf statement rather than mess around with this -1 offset in the copying loop. At the end of the day, it's an arbitrary decision, because this certainly isn't a situation where we need to squeeze every bit of performance out of the CPU. And yes, we could have just used the memmove function included by string.h, but we didn't for three reasons:
Firstly, this is a programming exercise, and it was useful to point out the necessity to copy the data backwards to avoid overwriting the source.
Secondly, although in this case we don't need to process the data we are copying in any way, in a more complicated situation we might need to. If we rely on doing the copying by calling a library function, it's not possible to add our own code within that, (unless we modify and re-compile the library itself), so we could end up looping through the same dataset twice instead of once.
Thirdly, we're only likely to be copying up to 17 bytes. Looking at the source code for the memmove library function in /usr/src/lib/libc/string/memmove.c, as might expect, we can see that it's optimised for copying much larger blocks of memory, taking into account memory alignment to get the best performance. This is obviously completely un-necessary for our case, so lose nothing by writing our own data copying loop.
First test
We can now write a ppm file to disk, and check that it loads correctly into any graphics editing program that supports the ppm format. Let's change our main function to create a simple pattern across the whole framebuffer:
int main(int argc, char * argv[])
{
int x,y;
unsigned char * framebuffer;
framebuffer=malloc(32 + FRAME_WIDTH * FRAME_HEIGHT * 3);
if (framebuffer==NULL) { return (1); }
for (x=0; x<FRAME_WIDTH; x++) {
for (y=0; y<FRAME_HEIGHT; y++) {
SETPIXEL(x, y, (((x+y) % 768) < 256 ? (x+y) & 255 : 0), (((256+x+y) % 768) < 256 ? (x+y) & 255 : 0), (((512+x+y) % 768) < 256 ? (x+y) & 255 : 0));
}
}
output_ppm("/output/test_1.ppm", framebuffer, FRAME_WIDTH, FRAME_HEIGHT);
return (0);
}
This should produce an image of a repeating red, blue and green gradient across the screen in diagonal stripes. The color of each pixel obviously depends on it's position, as we're calculating the RGB values from the co-ordinates, but let's have a look at exactly how this pattern is generated. We're basically doing the same calculation for each color channel, but offsetting it by a different amount. Ignoring the Y value for a moment, the X value is taken modulo 768, so will cycle from 0 to 767 and back to 0 as we move from left to right. We then take the lower eight bits if the value is between 0 and 255, or set it to 0 if it's 256 or above. This gives us 256 values containing a sweep from 0 to 255, followed by 512 zero values. We add 256 to the green channel, and 512 to the blue channel to make sure that only one channel has a non-zero value at any time. We add the Y value to the X value simply so that each successive line of pixels will be offset by exactly one from the line above, making the result more interesting than the simple vertical stripes that we would get by taking the color value from the X co-ordinate alone.
OK, so it's not exactly a mandelbot set, but wasn't it satisfying to do it from first principles?