Algorithms

Computing the CRC8-ATM CRC in Python

The 8-bit CRC8-ATM polynomial is used in many embedded applications, including Trinamic UART-controlled stepper motor drivers like the TMC2209:

\text{CRC} = x^8 + x^2 + x^1 + x^0

The following code provides an example on how to compute this type of CRC in Python:

def compute_crc8_atm(datagram, initial_value=0):
    crc = initial_value
    # Iterate bytes in data
    for byte in datagram:
        # Iterate bits in byte
        for _ in range(0, 8):
            if (crc >> 7) ^ (byte & 0x01):
                crc = ((crc << 1) ^ 0x07) & 0xFF
            else:
                crc = (crc << 1) & 0xFF
            # Shift to next bit
            byte = byte >> 1
    return crc

This code has been field-verified for the TMC2209.

Posted by Uli Köhler in Algorithms, Embedded, MicroPython, Python

Get all suffixes for a string in Python (Suffix list)

Problem:

Given a string, e.g. foobar, you want to get the list of all suffixes of said string, e.g. ["r", "ar", "bar", "obar", "oobar", "foobar"]

Solution:

Use this snippet:

def all_suffixes(s):
    return [s[-i:] for i in range(1, len(s) + 1)]

s = "foobar"
print(all_suffixes(s)) # ['r', 'ar', 'bar', 'obar', 'oobar', 'foobar']

 

Posted by Uli Köhler in Algorithms, Python

An introduction to Z-boxes

You most likely found this post for one of two reasons:

  • Either you haven’t heard of Z-Boxes and are interested in if they can somehow help you
  • or you have to learn about Z-Boxes and you have absolutely no idea how to understand the mathematical definitions.

Either way, we’re going to investigate Z-Boxes – not using a box of formulas but using examples and Python code.

Continue reading →

Posted by Uli Köhler in Algorithms

Reusing your calendars, the pythonic way

Yesterday got a calendar for 2016. An interesting question came up my mind: When can I reuse this calendar, and for which year can I reuse which old calendar?

The 1st January 2015 was a Thursday. The same day in 2016 is a Friday. Once you follow this pattery you will quickly recognize that the base period of seven years is disrupted by leap years.

It quickly turns out that for some years it takes decades until you can reuse a calendar: 2016 is a leap yer, so you can not reuse it for 2044.

However, there’s a neat quirk that is currently unimplemented in online services like whencanireusethiscalendar.com: You can partially reuse a calendar.

Continue reading →

Posted by Uli Köhler in Algorithms

Reading TAR files in C++

This article describes a method of  reading TAR archives (including .tar.gz and .tar.bz2) in C++ using Boost IOStreams.

You could use libtar for this, but the original version hasn’t been updated since 2003 and doesn’t provide you flexibility and insight to the internal structure of a TAR archive. Continue reading →

Posted by Uli Köhler in Algorithms, C/C++

HackThisSite Programming Challenge 1 Algorithm (Unscrambling)

Recently hackthissite.org was recommended to me — it’s really fun to play around with, even if I think some of the challenges are not that realistic any more.

I thought it would be just as much fun to post some of my solutions to the programming challenges here. If not absolutely neccessary for understanding the underlying algorithm, I won’t post any information about how to use the programs, because the purpose of these posts shall be to understand it, not to use it in order to solve the HTS challenges.

Continue reading →

Posted by Uli Köhler in Algorithms