Developing in C for the ATmega328: PRNG, FSM and more!

Where I discuss psuedo-random number generators (PRNG), finite state machines (FSM) and other software topics.

Sources

Mersenne Twister

• TinyMT - Tiny Mersenne Twister
• TinyMT on GitHub
• Mersenne Twister Readings

Introduction

This entry covers several topics, random number generation, finite state machines and native programming. All of the code discussed is in AVR_C on GitHub. The objective is to continue to expand on the development of a standard C library for the Arduino Uno and other ATmega328-based microcontroller boards.

Pseudo-random number generators (PRNG)

I needed a random number for a project I was working on. This kicked off a short dive into the concept of random numbers, pseudo-random numbers, generators, sequences and the cryptography. In a nutshell, random numbers are a sequence of numbers where the sequence never repeats (random) and repeats after a while (pseudo-random). The generators to create the sequences aren’t simple, however, they can be short, lending themselves to programming concepts. For security, its critical to have random vs. pseudo-random, as the latter lends itself to code breaking quite easily.

And while the AVR C version random() seemed to be working well, exploring the concept helped me discover TinyMT. TinyMT is a scaled-down version of the Mersenne Twister, which is a highly regarded, fast, efficient pseudo-random number generator. From their site on TinyMT:

TinyMT is a new small-sized variant of Mersenne Twister (MT) introduced by Mutsuo Saito and Makoto Matsumoto in 2011. There are two types of TinyMT, tinymt32 and tinymt64. tinymt32 outputs 32-bit unsigned integers and single precision floating point numbers. On the other hand, tinymt64 outputs 64-bit unsigned integers and double precision floating point numbers.

The purpose of TinyMT is not to replace Mersenne Twister. TinyMT has far shorter period than Mersenne Twister. The merit of TinyMT is in its small size of the internal state of 127 bits, far smaller than 19937 of Mersenne Twister. The purpose of TinyMT may be used in a situation where large state generators such as Mersenne Twister are difficult to use. According to statistical test (BigCrush in TestU01 and AdaptiveCrush), the quality of the outputs of TinyMT seems pretty good, taking the small size of the internal state into consideration.

You will know when you need a random number. For me, I wanted to provide a random frequency for a random amount of time for a significant period of time (> 8 hours). And to do this, I needed to calculate random numbers. When I ran into some issues in implementing the version in stdlib, random(), solving those issues led me to TinyMT.

The standard version works now, however, I thought it would be interesting to add TinyMT and perform some benchmarking. In a test (examples/rand_test) using both routines to generate a matrix of 20 x 10 random numbers, TinyMT was 4 times faster? (see update below) Given its pedigree and the its blistering performance, I incorporated it into the AVR_C Library and will use it instead of random().

Update on TinyMT

I have rerun the tests comparing TinyMT to native avr-libc rand() and it appears the numbers might be reversed. The routine rand() appears to be four times faster. That said, I believe its valuable to have both and will continue to look at exploring these pseudo-random number generators.

Finite State Machines

There are many explanations of finite state machines. I found this one to be helpful as it keeps it fairly basic. Like random numbers, the topic of finite state machines can become quite complex quickly. For my purposes, I have found having a simple four state FSM which uses push buttons to move between states and LED’s to indicate the state, valuable as a programming starting point.

I wanted to point out the fundamental aspects of the code. The FSM is split between a switch statement in main, which drives the moving from state to state and the button checks in each state file to determine to which state to move.

Main Loop

The less code that exists in this loop, the better. The code to execute needs to be in the state files. The objective of this code is to acknowledge the state then move to the state and act as a central command for distribution.

    while(1) {
        /* execution code goes here */
        delay(50);
        printf("Entering Switch, state = %d\n", state);
        switch (state)
        {
             case 0:
             // Power on State
                puts("state0");
                state0();
                break;
             ;
             case 1:
             // State 1
                puts("state1");
                state1();
                break;
             ;
             case 2:
             // State 2
                puts("state2");
                state2();
                break;
             ;
             case 3:
             // State 3
                puts("state3");
                state3();
                break;
             ;
             // this should not be reached
             default:
               puts("Default found");
        }
    }

State Code

Each state gets its own file (actually two files, a header file for declarations and a .c file for execution.) Here the state will perform two tasks, first it will execute its state code, meaning what happens when it is in this code and second it will determine which state to move to upon a change of state.

In this example, there are two buttons, one for moving from state to state called UP as it increments through the states and the other enters the state for execution, appropriately called ENTER.

void state1() {
    digitalWrite(LED_bit0, HIGH);
    digitalWrite(LED_bit1, LOW);
    uint8_t unpressed = 1;

    while(unpressed) {
        // Up Button
        if (buttons[UP].pressed) {
            state = 2;
            unpressed = 0;
        }
        // Enter Button
        if (buttons[ENTER].pressed) {
            printf("In Enter State 1, state = %d\n", state);

            blue_led(DIM);
        }
    }

    blue_led(OFF);
    printf("Exiting State 1, state = %d\n", state);
    return;
}	

By reviewing the code, you can see that state execution depends on the ENTER button being pressed. This eans the FSM moves from state to state, however doesn’t execute code for that state unless ENTER is pressed. For my purposes, this is what I needed, I wanted a confirmation of entering state as compared to automatic execution.

Native Blink

I added a native blink program avr_blink to the list of the examples. I believe it helps someone to understand the differences between native C operations on the ATmega microcontroller as well as provides a low overhead test bed.

In the latter example, I wanted to test some timing routines and realized that blink has too much overhead to reliably use it for timing. When I examined the same functionality using native code, I ended up with the following comparison:

Clearly for a blinking LED to test if a board works, this parameters are irrelevant. They are useful for beginning to understand the impact of abstraction or ease of programming on code size and execution speed.

More improvements could be made on the native code. For example, the ATmega will toggle a bit when it is setup as output and a one is written to the input register. Changing to this approach will shrink the code size another 20 bytes to 604 bytes.