Tic-Tac-Toe on Arduino (MiniMax)

While playing around with Arduino and Nokia LCD Screen I've decided to create some simple game. Obviously there's nothing simpler than tic-tac-toe. The game itself is trivial, everyone knows it so it should be pretty simple to learn the machine to be a good opponent. Yeah... Of, course I could write something really simple, like a translation table, in a sense that if player made a move A, then computer should do a move B... and describe all of the possible situations or "strategies". But that would be pretty primitive and not very appealing, wouldn't it ?

Instead the obvious choice is to implement the MiniMax algorithm for this game. Of course, there a dozens of great articles available describing the basics and fundamentals of MiniMax and especially in tic-tac-toe context so, I'm not going to go into details regarding how it works. Instead I would like you to have a look on any of the links bellow to get at least some essentials:

• http://beej.us/blog/data/minimax/
• https://chessprogramming.wikispaces.com/Negamax
• http://ai-depot.com/articles/minimax-explained/

Tic-Tac-Toe indeed is a very simple game, even in MiniMax context; in comparison to chess or checkers or any other game alike. However the game tree may become pretty complex anyway. Let's think about it. The first level of the tree will have 9 nodes (since there's 9 possible initial moves), the second will have 9*8 nodes, the third 9*8*7 ... and so on, so already on the third level we will have a total of 9 + 9*8 + 9*8*7 = 585 nodes. OK, assuming that we game tree node is defined the following way:

struct node_t {
char *children;
// it's either 0 - empty, 1 - X, 2 - O, 
// two bits per field, 9*2 = 18 bits = 3 bytes
char game[3];
char children_cnt;
};

Which is 6 bytes per node on Arduino, and on the first level we'll need 8 children, which would give roughly:

1. lvl: 9*6 = 54
2. lvl: 9*8*6 = 432
3. lvl: 9*8*7*6 = 3024

= 3024 bytes of memory only for 3 level deep tree ! That's a little disappointing. Even though, there's still some room for optimization in the tree node definition it's obvious that this approach is a dead end.

It's still possible to build and analyze the whole game tree even in 2kB of RAM with which Arduino is equipped. The answer is: recursion. In worst case (first move), the function will never recurse deeper than 8 times. This is pretty good it means that even if we would dedicate 1 kB of RAM only for the function to solve the current game state it would give 128 bytes available for local data - which in this case is a lot more than enough. 

Let's consider the general pseudocode for negamax first (negamax is a version of minimax for symmetrical games - meaning, player's A win is player's B loss):

int negaMax( int depth  ) {
    if ( depth == 0  ) return evaluate();
    int max = -oo;
    for ( all moves )  {
        score = -negaMax( depth - 1  );
        if( score > max  )
           max = score;
    }
    return max;
}

Let's try to put it more in the context of the Tic-Tac-Toe game. For the sake of simplicity first let's operate on the pre-build game-tree:

struct node {
struct node *children[8];
    uint8_t _ch_no;
    uint8_t grid[3];
};

int negamax(struct node *game_state, int depth) {
    if (d == MAX_DEPTH) return evaluate();
    for (int i = 0; i < game_state->_ch_no; i++) {
score = -1 * negamax(game_state->children[i], depth + 1);
if (score > max_score) max_score = score;        
}
return max_score;
}

That's a simplified version, but well describing the intention. We iterate through all children of the current game state as player A looking for the worst move of player B. We know though, that having the full game tree pre-built is a luxury. Instead we must build each game state we want to analyse iteratively in order to consider it, let's look on the modified code:

int negamax(int *grid, int depth) {

if (d == MAX_DEPTH) return evaluate();

for (int i = 0; i < GRID_SIZE; i++) {

// looking for an empty field in the grid

if (grid[i] != EMPTY) continue;

grid[i] = MARK_X;

score = -1 * negamax(grid, depth + 1);

grid[i] = EMPTY;

if (score > max_score) max_score = score;

}

return max_score;

}

That's pretty simple. Instead of having a pre-built list of nodes we simply create every node on the fly and analyse it, after that the game grid is restored to it's original state. That's the essence. This will be slightly slower than having the tree but it will work and it's good enough.

The key to a good playing program is the evaluation function. That function takes the current game state and should return how likely it is for the current player to win. If your program is doing simple mistakes or looses in "obvious win" situation the evaluation function is to blame. There are many approaches, to count the potentially winning rows and columns, count empty columns etc. It all comes down to exploring all the different possibilities. 

It took me a while to test all the different approaches and decide on the evaluation function. Finally I've decided to describe each game using a score between -100..100. A game which is a loss gets a score of -100, a game which is a win gets 100 points. What about all the values in between ? I'm using them to score a non-terminal game state. I'm counting all the rows, columns and diagonals on the board which do not contain the opponent's marking - meaning they can be potential wins. I'm doing the same for the opponent. After that I have two numbers: A- potential winning rows,cols and diags for player A and B - potential winning rows,cols & diags for player B. The game is scored by substracting those two numbers. Let's consider the following examples:

Game Evaluation example.

The values will vary within range [-8..8] which isn't much in comparison to the win/loss score, it's enough though to take a reasonable game decisions (well... in most cases :)). 

It's time to consider the full code.

This code is machine independent and can be compiled and executed on a standard x86 as well. Let's try that first. Since I was kinda lazy about the interface and my goal was to implement the MiniMax algorithm, the interface is clunky - but usable. In order to play type a number 0 - 8 in order to mark the field on the game grid. Human player starts first and uses the X mark. Let's play a game:

$ make
$ ./ttt

- - -
- - -
- - -
4
- - -
- X -
- - -
CPU
 O - -
 - X -
 - - -
2
O - X
- X -
- - -
CPU
 O - X
 - X -
 O - -
3
O - X
X X -
O - -
CPU
 O - X
 X X O
 O - -
1
O X X
X X O
O - -
CPU
 O X X
 X X O
 O O -
8
O X X
X X O
O O X
CPU
 O X X
 X X O
 O O X

Not bad. I must say that it plays pretty good in most of the cases. Try it out yourself. Putting this code onto an Arduino shouldn't be a problem now. The execution speed comparison may be interesting as well. As far as on a pretty old Core 2 Duo laptop there was no delay visible, I'm sure that little Atmega will require some time (at least in the beginning) to determine the best move.

Let's prepare the project. Clone the following repository

$ git clone git@github.com:dagon666/dev_MiniMax.git
$ cd dev_MiniMax

We need libpca as well:
$ git clone git@github.com:dagon666/avr_Libpca pca

Now, we can build it:

$ cd arduino
$ make
$ make install

As expected, since initially the tree of possible games to explore is quite bit it takes around 2 - 3 seconds for the Arduino to find the first move. The game set is much smaller afterwards - there seems to be no delays in second and further moves.

Just for fun (since I had it already connected) I decided to run the game on the Nokia LCD as well (there is an option in the code to do that - just change the LCD_OUTPUT to 1 in main.c). Here's how the game looks on the LCD:

I hope that this post was useful and educating. Have fun programming!

Nokia 3310 scope experiments part 1

Continuing with the nokia 3310 display experiments, I wanted to try out if visualizing signals with this display could be any useful. For that purpose I wanted to build a simple scope with Arduino. I simply configured the ADC, used the internal 1.1 V reference voltage, configured the analog comparator as a trigger and tried to visualize the incoming samples. All of this has been done using the libpca and the following simple sketch. 

So far, with enough accuracy I did some experiments with signals up to 8 kHz. I don't want to go into details at the moment especially that I consider this project as a work in progress. The ADC has been fed with a sine signal generated using Audacity. The quality of the measurement strictly depends on the ADC frequency. A couple of pictures bellow:

1kHz, sampled with prescaler = 4

2 kHz, prescaler = 4, visible trigger jitter

... same signal, bigger amplitude

 

4 kHz, prescaler = 4

 

6 kHz, prescaler = 4, very distorted

800 Hz, prescaler = 4, visible distortions

800 Hz, prescaler = 32, a lot better quality

Nokia 3310 display fun

Recently I wrote a driver for a nokia 3310 (pcd8544 based) lcd display which I had lying around.Again, I decided to create my own driver just to learn something about it and to see how much effort it will require - turned out that this driver is pretty easy to handle. Despite the fact that it's suggested to use 3V3 logic (maximum accepted voltage accordingly to the datasheet it's 7V), it works great with arduino powered with 5V and using 5V logic outputs.

Adafruit's Library

I had a look on Adafruit's library for that display just as a reference (github) and it seems very primitive to be honest - it allocates a huge display buffer without asking the user whether it is really needed (it consumes more than 25% of available RAM on Arduino) and what's even worse it uses bit banged SPI to communicate with the display. Why ? Why bother when there is fast & reliable hardware bus available on that MCU (and of course like all Arduino IDE libraries it's written in C++ which makes things even more slower). And it doesn't come with any font, so in fact the user must take care about it himself. Not being very humble - the implementation in libpca is far more superior.

Hello World

Just to test the driver & the display - let's first play around with a code template and generate some easy graphics (and of course mandatory for every project - "Hello World" program)

Simple, isn't it ? This code in a couple of lines initializes the SPI bus in the simplest manner, initializes the display itself, installs it as an STDOUT output and prints the "Hello World" string. That's fancy, plain and simple, no unnecesary C++ mumbo jumbo (don't get me wrong I love C++, but the way it is used in the Arduino libraries - it's a joke really). This is how it looks on the display:

I'll use that code as a template and will enhance it further on to generate some other effects. I'll be simply replacing the "Hello World" printf line with some other code.

Let's start with something simple - checker board. Each byte in the display represents 8 rows, 48 rows are distributed amongst 6 bytes. The memory organization of the display looks the following way:

Which means that if we'll fill the display with a pattern of 0b10101010 (0xaa) - we'll get something like a very high grained stripes. Let's test that. Replacing the 37th line (printf("Hello world !!!");) line with the following code:

pcd8544_fill(&lcd, 0xaa);

You'll get:

Ok, let's do something fancier. There's an old trick which I love to use (back from the dos 7.0 world and the famous software interrupt 13 which brought you into the 320x240 graphics mode) - generating the Sierpinski's triangle with just logical AND operation. Let's replace the line 37th again with the following code:


The result:

Yeah, that's nice, but we can still do better without much effort. Each pixel on the display can be either turned on or off - it's a 1-bit color depth. In other words it's physically impossible to display any shade of grey. But this is not a problem really - that limitation has been overcome long time ago with dithering alghorithms - we could implement simple error diffusion dithering or floyd-steinberg dithering to get awesome effects - but that would require some more effort than I really want to spend at the moment. Let's focus on an ordered dithering using an 8x8 Bayer lookup table - thanks to that method we'll be able to effectively simulate a 6-bit color depth (0 - 63) on a 1-bit color depth capable hardware and guess what - yes libpca implements that method for your convenience as well all you have to do is simply use it.

I recommend having a look on those articles if you are really interested in dithering - it's a lot of fun.

• www.tannerhelland.com/4660/dithering-eleven-algorithms-source-code/

• http://en.literateprograms.org/Floyd-Steinberg_dithering_%28C%29

• http://www.efg2.com/Lab/Library/ImageProcessing/DHALF.TXT 

First, let's generate a gradient. This will be the code:

And the effect:

Ok. That's pretty nice. We can tell how this method works - it generates different patterns (with different intensity) in order to simulate a particular shade - it's not as good as floyd-steinberg but good enough and what's most important - fast enough.

Let's see if good old atmega is fast enough to generate another old-school graphics effect - famous plasma effect This will be a challenging task for small Atmega - this effect heavilly depends on the sinus function and sqrt, power of two functions - everything of which our CPU is not very good at. Let's try anyway. 

The general alghorithm for the basic plasma effect is:

for every x
for every y
color = sin( sqrt(x*x + y*y) );
putpixel (x,y,color);

Surprisingly previously I was using a "buffer" variable as a display buffer, but for the plasma effect it's not really needed. First thing which I've done was generating the sin function lookup table:

    for (uint16_t i = 0; i < 256; i++) {
        sin_table[i] = (cos(i/2)*sin(i))*31 + 32;
    }

In order to avoid two loops, one which generates the image in the buffer and the other one which copies the data to the display I'm trying to do everything in one loop (just to make it quicker). The complete code looks the following way:


What I'm trying to achieve is to generate a byte of image (vertical) and copy it to the display, so in fact I'm using a single byte as a processing buffer. I'm using the ordered dithering function the same way as previously. This code on my Arduino is able to generate the plasma effect with something around 2, 3 frames per second. Have a look:

The code is available on github. You need libpca:

git clone git@github.com:dagon666/avr_Libpca pca

and the my avr projects repository:

git clone git@github.com:dagon666/avr_ArduinoProjects projects

In the projects directory you'll find a directory called nokia_spi.

A snapshot is available also here.
 

A(rduino) OS - Simple pre-emptive Arduino Scheduler

A(rduino)OS (AOS) is an attempt to write a simple pre-emptive scheduler - mostly to learn about how such system works but it's a fully functional implementation which can be used in a practical way good as well. First of all, if you have no theoretical background about context switching I would recommend to have a look on a great description regarding schedulers published by avrfreaks:

Multitasking on an AVR

AOS depends on libpca - it uses some routines from it in order to avoid code duplication. It is completely written in C from scratch with a little of assembler (in order to realize context switching). It comes with a documentation and some examples as well, which is hosted along with the repository on github:

AOS Doxygen documentation

Overview

Most of the pre-emptive schedulers (besides cooperative schedulers) is implements and is driven around a "tick" - an interrupt which happens periodically with a programmed frequency and which is responsible for context switching. In other words, assuming that there are two tasks in the system: taskA and taskB and taskA is currently running, once the tick interrupt happens it will check how much time taskA has already consumed and will switch to taskB if taskA has used all of it's assigned slot.

Context switch reprograms most of the CPU registers and re-positions the stack pointer - which means that every individual task has it's own memory area dedicated for the stack.

I strongly encourage you to give it a try. The doxygen documentation contains a description on how to prepare the project and use the system. In the near future I'm going to try to provide some more practical examples of using this scheduler.

Standalone Project: Multi functional Clock

I would like to share my project with you. It's an RTC clock with thermometer powered by atmega328p.

Clock, displaying current time, date & day of week.

It took me a while to finish this project since I wanted to polish the software. I wanted to implement a couple of features which will make my clock more interesting than any other similar device like that build before. I'll try to go through all the details now so, if you find this project interesting you can build it yourself (everything. including the software, is available for free).

Hardware 

The hardware itself is pretty simple. I used a ds18b20 digital One-Wire temperature sensor as a thermometer, a DS1307 RTC module which comes with a battery and a classic hd44780 LCD 16x2 display. Everything is pretty generic in that matter. There's a diode as well used to indicate that the clock is running and a couple of buttons. Besides that I use a couple of transistors in order to be able to control the LCD's brightness and contrast through software, using PWM timer. This is the schematics:

Clock schematics

I've taken some pictures during the building:

All elements populated, making the connections on the perf board.

Cutting the connections on the universal board.

View from the side.

Making the connections.

Completed device.

Software

As usual, the software is written purely in C - WITHOUT any 3rd party libraries. The code is 100 % mine - that includes the I2C driver, LCD driver, Software One Wire driver - all available in the libpca library. The software itself is pretty complicated as for a project like this it contains two state machines; the main one and the temperature measurement dedicated, handles two interrupt sources (INT0 from RTC, as well as Timer overflow interrupt) a fully independent menu system which can be used in any other project and some other additional routines.

Features:

• Event driven state machine - buttons, interrupts, FSM itself, generate events
• PWM controlled LCD backlight brightness
• PWM controlled LCD contrast
• LCD backlight fade-in/fade-out on keypress (handled in interrupt)
• Multiple information screens (scrolling from one to another)
• Independent scrolling strings
• Animated transitions between the "screens"
• The clock maintains all the data like current time and temperature measurements (maximum temperature / minimum temperature) without the external power (stored in RTC)
• Displays a proverbs for every day of year
• Displays a unique nameday for every day of year
• Software "integration" key de-bouncing algorithm

The software is 31 kB is size - it takes almost whole available FLASH space. The code itself is somewhere around 15 kB, but since I wanted to display an occasional proverbs and name-days information those additional assets consume the remaining space (it's quite a lot considering the fact that you need at least one (let's say 16 bytes long only) for every day of the year 16 * 365 ~ 6 kB !!!.

Software Functional Block Diagram.

Although the software may look over complicated it is acutally very simple. Let's talk about the interrupts first. I use the RTC's square wave output as an external interrupt (INT0) source. Thanks to that I don't have to constantly poll the RTC in order to update the time - since it will only change once every second. The rest of the time I can use the CPU for any different task. This 1 Hz interrupt is crutial to the system. It generates 1 Hz event in order to update the time, decrements the internal timers - so for example I can program a variable to a value and I know it will be decremented with every second - this can be used to generate timeouts and I use it to generate screen timeouts. For example, once the finite state machine enters Time Display mode the timer is programmed to i.e. 30 seconds - this timer is decremented in the 1 Hz interrupt handler. Once zero a TIMEOUT event will be generate which will force the FSM to transite into another screen (like temperature display or any other). It is used as well to control the backlight on time. If the backlight time is configured to a fixed value (like 30 seconds) the backlight timer is decremented in the 1 Hz interrupt handler if there is no keypress. The 1 Hz interrupt triggers the temperature measurement as well.

Temperature measurement

Temperature measurement is kind of tricky, since in order to get the results I need to wait for around 800 ms in for the sensors to finish the conversion. There were two solutions really - do it with every second - it will synchronous with the clock or do it asynchronously - I wanted to try the second one. This method is slightly more complicated and requires the second Timer interrupt to come into play. In order to synchronize two interrupts and a main loop a small finite state machine dedicated to temperature measurement had to be created. Bellow diagram depicts the process of triggering the temperature sensor and obtaining the results.

Temperature measurement.

Timer interrupt & Screen Transition

The timer interrupt is needed for other purposes. I use to for transitions between screens and for dimming in/out the backlight of the screen (change the PWM duty cycle from/to programmed one from/to zero).

In order to realize the transitions between screens I use a nice property of the hd44780 display. Although it is 16x2 characters it has a lot more DISPLAY RAM it is actually 2 x 40 characters. What I do is during the transition generate the content of for example time display screen to the display RAM at zeroth character and generate the second screen at character 17th (currently outside of the display frame), during the transition I simply move the display frame from 0 to 17 changing the screen content in result

Screen Transition

Menu system

Menu system has been implemented as a separate module. With a small adjustments it's possible to use it in any different project. The menu definition looks the following way:

struct menu_item {
const char *name;

// 1 - inactive/active
// 0 - cb/submenu
uint8_t config;

union {
menu_callback_t cb;
struct menu *submenu;
} ptr;
};

Each item has a name, and respective callback pointer called once the item has been selected. The menu definition for the clock looks the following way:

static struct menu_item items[] = {

{ "Set Time", MENU_ITEM_OWNER, { menu_set_time } }, 

{ "Set Date", MENU_ITEM_OWNER, { menu_set_date } }, 

{ "Time Mode",MENU_ITEM_DEFAULT, { menu_set_time_mode } }, 

{ "LCD Brightness", MENU_ITEM_DEFAULT, { menu_set_lcd_brightness } }, 

{ "LCD Contrast", MENU_ITEM_DEFAULT, { menu_set_lcd_contrast } },

{ "LCD Backlight Time", MENU_ITEM_DEFAULT, { menu_set_lcd_backlight } }, 

{ "Reset temperature", MENU_ITEM_DEFAULT, { menu_reset_temperature } },

{ "Temperature Display Time", MENU_ITEM_DEFAULT, { menu_set_temp_disp_time } },

{ "Time Display Time", MENU_ITEM_DEFAULT, { menu_set_time_disp_time } },

{ "Nameday Display Time", MENU_ITEM_DEFAULT, { menu_set_nameday_disp_time } },

{ "Words Of Wisdom Display Time", MENU_ITEM_DEFAULT, { menu_set_wow_disp_time } },

{ "Save Settings to EEPROM", MENU_ITEM_DEFAULT, { menu_save_settings } }

};

Of course if any string is longer than the the display line, the string will be scrolled. The implementation for that is generic and modular as well so can be taken straight away.

Overview

Clock displaying nameday.

Picture bellow shows the transition in progress, from the Time Screen to the Settings Menu. It also depicts how long does it take to switch a character in this LCD, since the new character is overlaying on the remnants of the old one.

Transition from Menu Screen to Time Screen

Menu Screen

More options in the Menu Screen

Long Option name is being scrolled in the menu screen.

Transition in progress.

Simple progress bar implemented for the menu.

Brightness regulation.

Video demonstration:

As usual, the source code as well as all the documentation is available on my github account:

git clone git@github.com:dagon666/avr_Libpca pca
git clone git@github.com:dagon666/avr_ArduinoProjects projects

Look for subdirectory projects/clk.

Simple Serial Port Command Line Interface (CLI)

It's often very useful to have some sort of interface through which a basic management can be done of our application. Whether you're designing a giant Marquee with a LED display or a plotter or you simply need to get some diagnostics from your device occasionally, a simple CLI system can come very handy. 

Of course, designing something similar to "bash" or any other unix shell is completely out of scope since those applications are huge and are simply an overkill for our needs. It's pretty simple though to create some basic, yet flexible & easilly extensible CLI system.

First thing needed is a command type definition. This will bind a keyword with an actual underlying routine executed for that keyword typed in the CLI.


typedef struct _t_cmd {
const char *cmd;
void (*fh)(void*);
} t_cmd;


The command type is pretty simple. There's the CLI command/keyword pointer, it holds a pointer to the execution function and that's it.

OK, so far so good. Now we need to define a set of commands since a single command CLI isn't much useful. Let's create a CLI context type for that which will hold entire CLI state - this has two advantages, first - it aggregates all the data in one place, second - if we'll write our functions to depend only on the context (which I'm going to do), then it will be possible to declare a couple of independent CLIs on different interfaces for example running concurrently.


typedef struct _t_cli_ctx {
// command set
t_cmd *cmds;

// cmd
char cmd[CLI_CMD_BUFFER_SIZE];
unsigned char cpos;

} t_cli_ctx;


OK, the context is pretty simple. It contains the command set pointer and current command buffer "cmd" - this buffer will hold everything you type before hitting ENTER and interpreting the command. It contains current cursor position as well. Once again, at the moment the context is pretty simple - but it will be enhanced later on to implement some more features.


static t_cmd g_cmds[] = {

{ "hw", fh_hello },
{ "hi", fh_hi }

// null
{ {0x00}, 0x00, 0x00  }
};


Let's prepare an initialization function for the CLI context definition in order to prepare it for execution.


void cli_init(t_cli_ctx *a_ctx, t_cmd *a_cmds) {
memset(a_ctx, 0x00, sizeof(t_cli_ctx));
a_ctx->cmds = a_cmds;
}


Believe it or not but more or less that's it. We can now declare some commands and proceed with the implementation of the CLI interpreter. We haven't yet used or done anything hardware specific so, the code can be compiled on a usual x86 machine for tests. The only platform specific code will be IO related. We need to create it now in order to proceed. For the AVR it will be quite simple. Our CLI system needs to be fed one key at a time. We can use a function from libpca:

unsigned char serial_getc(unsigned char *a_data);

It returns one if there is a character available and place it in the pointer provided. In order to perform some offline tests a similar function for x86 Linux terminal is needed. Unfortunately such function doesn't exist. There are two options

1. Use ncurses which implements getch() function - to retrieve a single character.
2. Disabled so called "canonical mode" for a standard linux terminal and use getchar() in non blocking mode.

Let's focus on the second approach. Ncurses is a bit of an overkill as far as I'm concerned though using it would be platform independent - but it's only a test application so, it's not that important. Let's have a look on the test program bellow.


I implemented here two functions cm_off & cm_on in order to turn the "canonical" mode on & off. When this mode is turned off - I'm able to get a direct input using the getchar() routine without having to press ENTER after every key. Our final linux_getc() along with linux_putc() routine will look the following way:


Let's implement the CLI interpreter itself now.


It doesn't do much at the moment. In fact it doesn't even run the commands. All it does is handle some basic input. We echo back the incoming characters, interpret backspace key and the ENTER key, printing some fancy prompt:

$ ./a.out 

#> command

#> some other cmd 

#> aaa

#> 

That is not very exciting in particular. Let's implement a command interpretation first:


I'll place that function in the KEY_CODE_ENTER switch case:


case KEY_CODE_ENTER: // new line
a_ctx->cmd[POSINC(a_ctx->cpos)] = '\0';
CLI_IO_OUTPUT("\r\n", 2);

res = _cli_interpret_cmd(a_ctx);

a_ctx->cpos = 0;
memset(a_ctx->cmd, 0x00, CLI_CMD_BUFFER_SIZE);
_cli_prompt(a_ctx, 1);
break;


I need some dummy commands implementation as well:

static void fh_hw(void *a_data) {
CLI_IO_OUTPUT("hello_world", 11);
}

static void fh_hi(void *a_data) {
CLI_IO_OUTPUT("hi", 2);
}

Let's do the test

./a.out 
#> hw
hello_world
#> hi
hi
#> test

#> 

Looks good, although there are is a problem - there is no info that a particular command is unknown. This must be fixed. Let's create another function and place it just after _cli_interpret_cmd in the switch case for ENTER key.


The switch case for ENTER will look the following way now:

case KEY_CODE_ENTER: // new line
a_ctx->cmd[POSINC(a_ctx->cpos)] = '\0';
CLI_IO_OUTPUT("\r\n", 2);

res = _cli_interpret_cmd(a_ctx);
_cli_reinterpret_cmd(a_ctx, res);

a_ctx->cpos = 0;
memset(a_ctx->cmd, 0x00, CLI_CMD_BUFFER_SIZE);
_cli_prompt(a_ctx, 1);
break;

Let's test it:

./a.out

#> test

Command not found
#> other

Command not found
#> hw
hello_world
#>

That's starting to look very good. At the moment we have a functional very basic CLI system. Let's consider what else is missing. When pressing an arrow keys nothing happens - we are unable to correct any mistakes in the middle of the command. This can be implemented. But first, let's checkout the key codes produced by those keys. On my terminal those are:

• Left: 1b 5b 44
• Right: 1b 5b 43
• Up: 1b 5b 41
• Down: 1b 5b 42

They may be completely different on yours. It's all terminal dependent, things like character encoding and terminal settings have a major influence here. That complicates the situation slightly, since a single key produces 3 codes and the key itself can be distinguished only by the third one. Our present implementation is unable to cope with that kind of input. Let's define a structure for that kind of input representing a single key

#define MULTICODE_INPUT_MAX_LEN 5

typedef struct _t_multicode_input {
unsigned char buf[MULTICODE_INPUT_MAX_LEN];
unsigned char pos;
} t_multicode_input;


... and a related command:


typedef struct _t_multicode_cmd {
unsigned char pattern[MULTICODE_INPUT_MAX_LEN];
unsigned char len;
void (*fh)(void*);
} t_multicode_cmd;


OK. The "input code" can be up to 5 characters long. What I want to do is to simply read the whole multi-code input and compare it against known ones in order to trigger some actions. First the CLI context structure must be extended:


typedef struct _t_cli_ctx {
// command set
t_cmd *cmds;
t_multicode_cmd *mcmds;

// cmd
char cmd[CLI_CMD_BUFFER_SIZE];
unsigned char cpos;

// multicode input
t_multicode_input mchar;
} t_cli_ctx;


The interpreter must be extended as well:


What I'm doing here is simply matching a whole multi-code input sequence against the known ones and fire an action if there is a match. Still, there's no associated actions defined. Let's create a couple:

t_multicode_cmd g_mc_cmds[] = {

{ { 0x1b, 0x5b, 0x44 }, 3, _cli_key_left },
{ { 0x1b, 0x5b, 0x43 }, 3, _cli_key_right },

// null
{ {0x00}, 0, 0x00}
};

static void _cli_key_left(void *a_data) {
t_cli_ctx *ctx = (t_cli_ctx *)a_data;

if (ctx->cpos) {
ctx->cmd[ctx->cpos--] = '\0';
CLI_IO_OUTPUT("\b \b", 3);
}
}

static void _cli_key_right(void *a_data) {
}

Just to make things simple - the left arrow key will behave the same way as backspace key. The right key won't do anything. That's great we can now handle even more complex input type. Let's think what else is still missing ?

What happends when you hit an up arrow key in bash ? It brings back the previous command. Some simple history implementation would be very fancy and would make the CLI system very attractive. Let's implement it as well. First some additional data fields are needed in the CLI context. Let's have a look on it once again:

#define CLI_CMD_HISTORY_LEN 8

typedef struct _t_cli_ctx {
// command set
t_cmd *cmds;
t_multicode_cmd *mcmds;

// cmd
char cmd[CLI_CMD_BUFFER_SIZE];
unsigned char cpos;

// history
char history[CLI_CMD_HISTORY_LEN][CLI_CMD_BUFFER_SIZE];
unsigned char hpos;
unsigned char hhead, htail;

// multicode input
t_multicode_input mchar;
} t_cli_ctx;


The CLI will hold last 8 commands typed into it. After pressing ENTER we need to save current command line into the history. Let's do it in the _cli_reinterpret_cmd function to sift any junk input from contaminating the history:


Handlers for up/down arrow keys are needed to make this feature complete:


Now, those commands must be attached to our multicode_input command array.


t_multicode_cmd g_mc_cmds[] = {

{ { 0x1b, 0x5b, 0x44 }, 3, _cli_key_left },
{ { 0x1b, 0x5b, 0x43 }, 3, _cli_key_right },

{ { 0x1b, 0x5b, 0x41 }, 3, _cli_history_up },
{ { 0x1b, 0x5b, 0x42 }, 3, _cli_history_down },

// null
{ {0x00}, 0, 0x00}
};

And we're ready to go. Let's test it.

$ ./a.out

#> command1

Command not found
#> cmd2

Command not found
#> cmd3

Command not found
#>
(3/8)cmd3
(2/8)cmd2
(1/8)command1

Command not found
#>
(4/8)command1
(3/8)cmd3

Command not found
#>

That seems to work very well. Our CLI starts to look very attractive now. One thing is still missing though - the basic command argument support. I left it for the end deliberately. Let's not forget that the final product will run on a small micro-controller with not much RAM on board. The only generic useful information would be an argc - an integer defining how many space delimited words have been typed into the CLI. If the command really needs to parse arguments then it should do it itself, just to save resources. Let's modify the code for _cli_interpret_cmd first and add a call to the argument counting routine:

a_ctx->argc = _cli_count_arguments(a_ctx);

The routine itself:


Let's write a test command for that as well:

{ "argc", fh_argc },


static void fh_argc(void *a_data) {
char tmp[16] = { 0x00 };
t_cli_ctx *ctx = (t_cli_ctx *)a_data;
sprintf(tmp, "argc: %d", ctx->argc);
CLI_IO_OUTPUT(tmp, strlen(tmp));
}

and test it:

$ ./a.out

#> argc
argc: 1
#> argc a1 a2 a4
argc: 4
#>

That works fine as well. At this stage we are done with testing on the x86 platform and we can move the code to the MCU itself. It's a good point to summarize the complete code so far. I reorganized the whole thing and split the code into files



The test application can be compiled without a Makefile, the following way:

gcc main.c linux_io.c cli.c -I. -o cli

Moving the CLI to the MCU

There's not much to do actually since the CLI has been written with a hardware independent code. However there are some gotchas which will come out later on. First let's prepare the project, change the IO routines for the CLI, compile the project and try to run it. Of course, I'm going to use the serial routines implemented in libpca for the IO. The IO definitions look the following way:


/**
 * @brief IO input routine - change it accordingly to your implementation
 */
#define CLI_IO_INPUT(__data) \
serial_getc(__data)


/**
 * @brief IO output routine - change it accordingly to your implementation
 */
#define CLI_IO_OUTPUT(__data, __len) \
serial_poll_send(__data, __len)

After flashing the arduino and connecting a minicom terminal, first thing to notice is lack of any response for ENTER key. Minicom emulates VT102 terminal and sends only a 0x0d code for a new line character, the devinition for KEY_CODE_ENTER must be changed accordingly. Let's recompile and verify the rest of the keys. The arrow keys works. The backspace key and the delete key don't work though, again it's the matter of the incorrect keycodes. We can discover those by echoing them back after receiving:

sprintf(tmp, "%02x\n", i);
CLI_IO_OUTPUT(tmp,strlen(tmp));

Minicom on my machine sends 0x08 code for backspace and a set of codes for backspace key: 0x1b 0x5b 33 7e. The code needs to be adjusted slightly. First the value of KEY_CODE_BACKSPACE must be corrected. The DELETE key needs to be interpreted in "multicode" fashion. I'll attach the same action to it as for BACKSPACE and left arrow key:

{ { 0x1b, 0x5b, 0x33, 0x7e }, 4, _cli_delete }, // delete

Let's recompile and test once again. Everything seems to work now. The basic CLI code is complete. This code proves how much CLI systems and interpreters are terminal dependent. We can either try to be as much compliant and flexible with most of popular terminal emulators or simply require from the user to use only one specific type i.e. VT100 / VT102 or any other.

As usual a set of sources can be downloaded either from my google drive or from github. Snapshot, containing a version of libpca as well as the source code discussed in this post is available here

The code is available in my GitHub repositories. First you need libpca:

git clone git@github.com:dagon666/avr_Libpca pca

and my projects repository:

git clone git@github.com:dagon666/avr_ArduinoProjects projects

Navigate to projects/cli_mcu to find the source code.