Selecting 8-bit CRC

Data errors are a reality when communicating between electronic devices. While one can use various hashing algorithms in order to verify data, this is not a luxury easily afforded when working with microcontrollers. For such cases, one often uses just a simple parity, sum, or ideally a CRC algorithm.

I won’t go much into a history and general use of these algorithm as Wikipedia covers it nicely. I will just present you with a problem I had. Which of many CRC algorithms do I actually use for my Microchip PIC microcontroller project?

The first part of rough selection was easy. Due to the limited nature of my PIC microcontroller, the only realistic options were CRCs up to 16 bits in length. After discounting all CRCs that ended on non-byte boundaries, that left me with only CRC-16 and CRC-8.

While CRC-16 is superior in all manners, it’s not only more computationally intensive but it also requires more memory to implement. Both of which are notoriously absent from microcontrollers. While both of those might be a worthy compromise if I had long messages that needed checksumming, my messages were couple of bytes in length. So, CRC-8 it is.

However, CRC-8 has quite a few variants out there. Heck, my own C# library supports over 20 of them. What I needed was a logical way to select the best one. And that came in the form of the excellent “Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks” article.

However, what this article has shown me was that I was wrong in thinking there is a single optimal solution. For example, from charts its easy to see that polynomial 0xA6 is vastly superior when it comes to long messages. It will detect two bit errors (yes, simplifying here a bit) no matter what the length. However, if we want CRC to detect four bit errors, polynomial 0x97 will actually do better – albeit only up to 120 bits (15 bytes). Whether one is better than the other, is now function of message length.

And that sealed it for me. Since my messages were to be short, polynomial 0x97 was actually the right choice for me. Since CRC is defined by more than its polynomial, I went to the repository of CRC knowledge to see if someone implemented the same. And I couldn’t find it. Heck, I couldn’t find any of the polynomials discussed.

It took me a hot minute to see that whitepaper and CRC RevEng page were actually describing the same polynomials in a different way. CRC RevEng used their normal form while whitepaper decided to call them out in reversed reciprocal. My 0x97 was actually 0x2F.

After understanding that, I actually found two existing CRC-8 algorithms using my chosen polynomial: AutoSar and OpenSAFETY. Since AuroSar had an extra step of XORing the output with 0xFF, I went with a slightly shorter OpenSAFETY CRC-8 variant. Even better, I had that algorithm already implemented in C#. Converting it to C for my microcontroller would be a breeze.

However, since my C# algorithm used lookup table to speed things up, that made it really unsuitable for microcontroller implementation. How could I give 256 bytes to the lookup table when I had only 1024 to begin with? No, for this I needed a variant that uses as little memory as possible.

After a while, this is what I ended with:

Code
uint8_t crc8(uint8_t* data, uint8_t length) {
uint8_t crc = 0;
while (length--) {
crc ^= *data++;
for (uint8_t i = 0; i < 8; i++) {
if (crc & 0x80) {
crc = (uint8_t)(crc << 1) ^ 0x2F;
} else {
crc <<= 1;
}
}
}
return crc;
}

Without any optimizations, this code needs only 3 bytes in RAM and 46 words of program memory (37 words with optimizations). And yes, speed does suck a bit but that’s the tradeoff. If speed was of essence, one could always go with lookup tables, no matter the RAM cost.

In any case, my problem was solved and algorithm selected.


PS: Yes, code could be optimized further if we used overflow from STATUS register as that would allow us to have only one crc << 1 but I opted not to do that as to keep code easily transportable between platforms.

PPS: And yes, if one is willing to go into the assembly, you can optimize it even more.

Small(er) Ubuntu Server 22.04 Install on Vultr

For my new Ubuntu Server deployment I decided to go with Intel High Frequency Vultr instance, mostly due to its larger disk allotment. However, going with default Vultr’s deployment image, I ended up with 18 GB of disk occupied. And yes, I could have removed extra stuff I didn’t need (e.g. /usr/local/cuda/ was the prime candidate). However, I decided to go a different route – manual installation.

Getting the Ubuntu ISO is easy enough as a wide selection is already available behind ISO Library tab on Server Image selection page. Combine that with noVNC console and you can just click your way through. However, one can also find Shell option within the Help menu giving you access to the bash prompt and allowing for more control.

While noVNC is decent, the lack of copy/paste makes it unwieldy when more then a few commands need to be entered. So, my first task was to SSH into the installation and continue from there. To do this, we have to allow for password login and set the password.

Terminal
sed -i 's/^#PermitRootLogin.*$/PermitRootLogin yes/' /etc/ssh/sshd_config
systemctl restart sshd
passwd

Now we can connect using any SSH client and do the rest of steps from there.

I like to start by setting a few variables. Here I needed only DISK and HOST.

Terminal
DISK=/dev/vda
HOST=ubuntu

Assuming this is a fresh VM, the disk should already be empty but I like to clean it again (just in case) and create a single partition. On servers I quite often skip swap partition and that’s the case here too.

Terminal
blkdiscard -f $DISK
echo -e "o\nn\np\n1\n\n\nw" | fdisk $DISK
fdisk -l $DISK

Now we can format our partition and mount it into /mnt/install/.

Terminal
mkfs.ext4 ${DISK}1
mkdir /mnt/install
mount ${DISK}1 /mnt/install/

We will need to install debootstrap to get our installation going.

Terminal
apt update ; apt install --yes debootstrap

And now we can finally move installation files to our disk.

Terminal
debootstrap $(basename `ls -d /cdrom/dists/*/ | grep -v stable | head -1`) /mnt/install/

Before proceeding, we might as well update a few settings.

Terminal
echo $HOST > /mnt/install/etc/hostname
sed "s/ubuntu/$HOST/" /etc/hosts > /mnt/install/etc/hosts
sed '/cdrom/d' /etc/apt/sources.list > /mnt/install/etc/apt/sources.list
cp /etc/netplan/*.yaml /mnt/install/etc/netplan/

Finally we get to chroot into our newly installed system.

Terminal
mount --rbind /dev /mnt/install/dev
mount --rbind /proc /mnt/install/proc
mount --rbind /sys /mnt/install/sys
chroot /mnt/install \
/usr/bin/env DISK=$DISK HOST=$HOST \
bash --login

While optional, I like to update locale settings and set the time zone.

Terminal
locale-gen --purge "en_US.UTF-8"
update-locale LANG=en_US.UTF-8 LANGUAGE=en_US
dpkg-reconfigure --frontend noninteractive locales
dpkg-reconfigure tzdata

Installing kernel is next.

Terminal
apt update
apt install --yes --no-install-recommends linux-image-generic linux-headers-generic

Followed by our boot environment packages.

Terminal
apt install --yes initramfs-tools grub-pc

Setting FSTab will ensure disk is mounted once done.

Terminal
echo "PARTUUID=$(blkid -s PARTUUID -o value ${DISK}1) \
/ ext4 noatime,nofail,x-systemd.device-timeout=5s 0 1" > /etc/fstab
cat /etc/fstab

Of course, boot wouldn’t be possible without getting images ready.

Terminal
KERNEL=`ls /usr/lib/modules/ | cut -d/ -f1 | sed 's/linux-image-//'`
update-initramfs -u -k $KERNEL

And finally, boot needs Grub installed to MBR.

Terminal
update-grub
grub-install ${DISK}

While we could boot our system already, it’s a bit too bare for my taste so I’ll add a basic set of packages.

Terminal
apt install --yes ubuntu-server-minimal man

Once done, a small update will not hurt.

Terminal
apt update ; apt dist-upgrade --yes

Of course, we need to ensure we can boot into our system. While one could use passwd to set the root password, I like to use keys for access.

Terminal
mkdir /root/.ssh
echo 'ssh-ed25519 AAAA...' > /root/.ssh/authorized_keys
chmod 600 -R /root/.ssh

With all set, we can exit our chroot environment.

Terminal
exit

We might as well unmount our custom install.

Terminal
mount | tac | awk '/\/mnt/ {print $3}' | xargs -i{} umount -lf {}

And finally we get to reboot. Please note that you should also go to VM Settings and unmount custom ISO to avoid getting into installation again.

Terminal
reboot

If all steps worked, you will face a pristine Ubuntu installation measuring something around 5 GB. To make it even smaller, one can turn off the swap.

Terminal
swapoff -a
vi /etc/fstab
rm /swapfile

Regardless, your system is now ready for abuse. :)

You Need to Load the Kernel First

I update my Linux servers regularly. What I do less regularly is restarting them. So I was not really surprised when one of them failed to boot with “you need to load the kernel first” message. What I usually do is: select the old kernel, boot the darn thing up, and then refresh grub. However, this time I overdid it so even the attempt to boot the old kernel produced the same message. It was time for troubleshooting.

While I knew which kernels wouldn’t boot, I didn’t actually know which kernels I have available. Fortunately, grub has a command line mode hidden behind ‘c‘ key press. There I selected my disk and listed all files:

Terminal
ls
set root=(hd1,2)
ls /

It helps if you know how your partitions are setup for this to work but, in the worst case scenario, you can also go over each partition to find vmlinuz files. This is also the reason why I leave the boot partition unencrypted. Had my boot partition been encrypted, this step would be impossible and more involved recovery would be needed.

In this case, I was able to find vmlinuz files and I saw that the newest kernel I had installed was 5.4.0.117. Armed with that knowledge I went back to the main grub screen.

On the main screen I went to the edit option hidden behind ‘e‘ keypress. There it was simple to edit existing commands (both linux and initrd) to update the kernel version to match the one I had on my disk, followed by F10 keypress. Voila! My linux was booting.

Mind you, this wasn’t a permanent solution since the next reboot would leave me with the same issue. What I needed was to update grub (and I might as well update initramfs while I’m at it).

From the prompt, two commands were enough to make my next reboot a boring affair.

Terminal
sudo update-initramfs -k all -u
sudo update-grub

And that’s it. Now my grub and my kernels are back in sync. At least for a while.

Text for OpenGL

I occasionally like to learn something I literally have no use for. It keeps me happy and entertained. This month I decided to deal with OpenGL. And no, I don’t consider learn OpenGL an useless skill. OpenGL is very much useful and, despite newer technologies, still here to stay. It’s just that, since I do no game development, I have no real use for it. But I wanted to dip my toes into that world regardless.

After getting few triangles on the screen, it came time to output text and I was stunned to learn OpenGL has no real text support. And no, OpenGL is not unique here as neither Vulkan or Metal provide much support. Rendering text is simply not an integral part of rendering pipeline. And, once one gives it a thought, it’s clear it doesn’t belong there.

That’s not to say there are no ways to render text. The most common one is treating text as a texture. The less common way is rasterizing font into triangles. Since I really love bitmap fonts and square is easily constructed from two right triangles, I decided to go the rustic route.

The first issue was which font to select. I wanted something old, rather complete, and free. Due to quirks in the copyright law, bitmap fonts are generally not considered copyrightable under US law. Mind you, that holds true only for their final bitmap form. Fonts that come to you as TTF or OTF are definitely copyrightable.

The other issue with selection was completeness. While selecting old ROM font supporting code page 437 (aka US) is easy, the support for various European languages is limited, to say the least. Fortunately, here I came upon Bedstead font family which covered every language I could think off with some extra. While era-faithful setup would include upscaling and even a rudimentary anti-aliasing, I decided to go with a raw 5×9 pixel grid.

For conversion I wrote BedsteadToVertices utility that simply takes all character bitmaps and extracts them into a Vector2 array of triangles. The resulting file is essentially a C# class returning buffer that can be directly drawn. Something like this:

Code
var triangles = BedsteadVerticesFont.GetVertices(text,
offsetX: -0.95f,
offsetY: 0.95f,
scaleX: 0.1f,
scaleY: 0.2f);
gl.BindBuffer(BufferTargetARB.ArrayBuffer, BufferId);
gl.BufferData<float>(BufferTargetARB.ArrayBuffer, triangles, BufferUsageARB.DynamicDraw);
gl.DrawArrays(GLEnum.Triangles, 0, (uint)triangles.Length / 2);

The very first naïve version of this file ended up generating a 3.8 MB source file. Not a breaking deal but quite a bit larger than I was comfortable with. So I went with a low hanging fruit first. Using float arrays instead of Vector2 instantly dropped the file size to 2.3 MB. Dropping all floats to 4 decimal places dropped it further to 2.0 MB.

And no, I didn’t think about reducing the whitespace. Code generated files don’t need to be ugly and reducing space count to a minimum would do just that. Especially because removing spaces will result in the exactly same compiled code at the expense of readability. Not worth it.

However, merging consecutive pixels into one big rectangle was yet another optimization that’s both cheap in implementation and reduces file size significantly. In my case, the end result was 1 MB for 1,500 characters. And yes, this is still a big file but if you exclude all the beautiful Unicode non-ASCII characters, that can bring file size down to 61 KB. Had I wanted to go the binary route, that would be even smaller but I was happy enough with this not to bother.

While the original Bedstead font is monospaced, I decided to throw a wrench into this and remove all extra spacing where I could do so easily. That means that font still feels monospaced but you won’t have excessive spaces really visible. And yes, kerning certain letter pairs (e.g., rl) was too out of scope.

On the OpenGL side, one could also argue that this style of bitmap drawing would be an excellent territory for the use of indices to reduce triangle count. One would be right on technicality but I opted not to complicate my life for dubious gains as modern GPUs (even the integrated ones) are quite capable of handling extra few hundred of triangles.

In any case, I solved my problem and, as always, the source code is available for download.


[2022-06-07: With a bit of optimization, ASCII-only file is at 50 KB.]