It’s been six months since the last status update. Long gone are the days of publishing monthly updates. This page contains updates on the things I’ve been working on between March 15th, 2021 and September 15th, 2021.
This is a long post, so feel free to use the table of contents to jump ahead to the sections that interest you.
Instead of publishing large update posts, I could prepare and backdate them to the appropriate months. But that would mess with the sanctity of the blog dates, which is something I want to keep accurate.
Kernel / OSDev
The kernel finally has a name that is not “the kernel”. It is now called Cardinal and has its own tiny homepage.
Protothreads
Previously, the kernel had multi-tasking based on “real” threads. This meant that each task could yield() or become pre-empted at arbitrary points. This is a very powerful way of multi-tasking but it requires separate stacks for each task, a small snippet written in assembly to switch the tasks, and relatively expensive switches.
To mitigate some of these issues, and to play around with another way of programming, I have introduced protothreads to the kernel.
Real-time scheduler
In order to learn more about scheduling, I turned the previous round-robin scheduler of the kernel into a real-time scheduler based on deadlines.
The scheduling algorithm is called Earliest Deadline First (EDF).
Userland
At long last, Cardinal can execute code that is not baked in to the kernel image during compile time. Instead, it is possible to run code from files on disk.
For now, the only executable format that is supported is Brainfuck. This severely limits the usefulness of the system, but it was only added as a proof-of-concept. In the future, I want to support more sensible executable formats. The primary candidates are the RISC-V ISA or webassembly bytecode.
I/O buffers
There are now ring-buffers around serial output and keyboard input. This is meant to prevent losing I/O data when the system is overloaded and keyboard events cannot be consumed faster than the user’s input speed.
The commit for the serial output buffer is b99f91ef5e, and the commit for the keyboard buffer is be23af6523.
PCI driver
There is now a driver for the PCI bus that enumerates the available devices and automatically loads the correct drivers if we recognize any devices.
We also have a small “PCI database” that can map some vendor or device IDs into human-readable names. This is used in the lspci command. The lspci command was added in commit 5ddc4e123f.
RTL8139 ethernet card
The first driver I wrote that uses PCI is for RTL8139, an old ethernet card. This card supports receiving and transmitting raw ethernet frames, and it is relatively easy to write a driver for. It is emulated in QEMU, and has a lot of sample code on the internet. Additionally, there is a really detailed datasheet that explains how everything works.
The RTL8139 driver was first introduced in commit bd5b300fb5, and became able to transmit raw ethernet frames on commit b264f59061.
Networking stack
After having a driver for an ethernet card, it was time to work on the networking stack of Cardinal. For the first steps, I wrote simple wrapper types for IPv4 addresses and MAC addresses. Then I wrote methods to create ethernet frames and ARP packets.
You can send raw ethernet frames and capture them with Wireshark. This can be used as an additional method of logging.
Unfortunately, the network stack is unable to receive packets right now. Only transmitting is supported.
VirtIO drivers
I started looking into the VirtIO specs. Nothing is working yet, I’m still trying to wrap my head around the virtio queues. I’d love to fully implement these at some point but it’s not a priority for now.
Next steps
Here are the next steps for the kernel. Unless there is a change in plans, I’m hoping to tackle some of these for the next status update about the kernel.
- Networking
- Receive packets
- Get IP address with DHCP
- Send UDP syslog packets to a syslog server
- Drivers
- Write a VirtIO driver. Any driver should work as a proof-of-concept. The easiest one is probably the RNG device.
- Misc
- Nightly build server to produce ISO files
- Update project homepage with more information
Radio / DSP
There hasn’t been too much radio work for this status update, because most of my focus has been on kernel development and learning about cryptography. But six months is a long time, and “not too much work” doesn’t mean nothing got done.
APRS modulator
APRS (Automatic Packet Reporting System) is an amateur radio system for exchanging small packets of information such as the location of a transmitter, the data from a weather sensor, or text messages between amateurs.
I wrote a modulator that can generate APRS packets as audio and transmit them with any radio that has an audio line-in. These packets were successfully demodulated when tested locally, and showed up on APRS-IS / aprs.fi when transmitted with a Baofeng handheld transceiver.
ADS-B modulator
I wrote an ADS-B (Mode S) modulator. At this point it is unable to calculate checksums or generate messages with a high level interface, but it can read hex-encoded messages and emit I/Q samples.
So far no testing has been done with transmitting packets from one PC and trying to receive and decode them with another.
AHICDM modulator
AHICDM, or Adam H Image Capable Digital Mode, is a relatively niche modulation for transmitting arbitrary binary data over a radio link. I have never come across this modulation in the wild, and the only place I’ve found an audio example is the Signal Identification Wiki.
I wrote a modulator that matched the information and audio sample provided on the wiki page to the best of my abilities.
You can find the modulator source code, and my notes about AHICDM on my wiki here.
Cryptography / Cryptology
A new topic that hasn’t been on the status updates before is cryptography.
Sponge functions
I first read about sponge functions earlier this year, and found their use as “cryptographic Swiss army knives” very intriguing. I published an article called “Constructing a sponge function from MD5”; which goes over the process of implementing a toy sponge function using the very broken MD5 hash, and showcases different use cases of sponge functions.
After that article, I have implemented and used sponge functions in different projects, using various transform functions like the ChaCha/Salsa hash, cellular automatons, random boolean networks, and the Gimli permutation.
Overall, I find sponge functions really useful, and fun to play with.
Bit mixers
Bit mixers are random n-bit to n-bit mappings that try to randomize the relationship between the input and the output as much as possible. Popular mixers include SplitMix64 and the MurmurHash finalizer.
In order to explore bit mixers, and to make my own ones, I made a framework that can compare the bias of bit mixers and draw avalanche diagrams. The initial implementation was in Python and worked perfectly, but it was too slow to test with large numbers of iterations. In the end, I had to rewrite the whole thing in C and ended up with much better results due to being able to run more iterations.
Random number generators
Building on my work with bit mixers, I made a very simple PRNG by incrementing a 64-bit counter, hashing it with the bit mixer, and outputting the first 32 bits. The output does pretty well on ent / PractRand tests.
I also implemented and wrote about various RNG algorithms on my wiki.
Small projects
This section includes projects that are not large enough in scope to need their own top-level headings.
Redis proxy server
In order to get more familiar with distributed database design, I wrote a Redis proxy server.
In order to serve Redis client libraries and talk to the actual Redis servers, I implemented the RESP protocol. The proxy server only supports the most common commands, I only implemented the functionality I needed.
When the proxy server gets a request regarding a key, that key gets hashed using rendezvous hashing. The Redis server to use for storing or retrieving the data is determined using the resulting hash.
The proxy is written in Python for now. In the future, a C rewrite with async sockets might be a good idea.
Barcodes
I recently got interested in barcodes, so I wrote a Code 39 barcode encoder. It takes an input string and generates a barcode image.
If I can find the time for it, I am hoping to move on to generating 2D barcodes and then start making barcode readers. It is the same story as signals or file formats, it is always easier to generate it than to decode it.
Algorithmic trading / Algotrading
I tried to get into algorithmic trading a little. This is a completely new field for me, and there is so much material to read.
I have written some integration code with stock data providers. These providers include BIST (Istanbul stock exchange), my bank, an investment company and a data broker called Matriks.
Unfortunately; I quickly got distracted by other projects and work, so my progress with algotrading is limited to this.
End-to-end encrypted chat application
After playing with sponge functions for a while, I decided to use them in a practical way and started building an end-to-end encrypted chat application.
I made two prototypes; a TUI application that lets you chat from the command line, and a web application that works with desktop and mobile browsers. I successfully used this application to have encrypted group chats and one-on-one conversations.
Future work
If I have time to work on this project in the future, I want to make a proof-of-concept Android application for it. A desktop app using GTK/Qt might also be good to have.
Conclusion
This is all I could remember. There might have been more things I’ve done, but I’ve forgotten them since 6 months is a long time frame to remember.
If you want to learn more about any of my side-projects, or have comments/recommendations about any of them, feel free to leave a comment or send an email.