Arduino DRO Serial Protocol Considerations

Last time I posted the schematic and firmware code for the Arduino DRO, for reading the iGaging scales. The plan is that the Arduino will read the positions and send it over UART to the app running on Android tablet via an inexpensive Bluetooth module. The nice part of using a serial-to-bluetooth adapter is that it's completely Plug-and-Play, so the hardware layer isn't too complicated. On the Arduino side we simply connected the Rx and Tx to the Tx and Rx on the Bluetooth board respectively, and provided power via Vdd and Ground. On the Android side all you need to do is to pair with the device. These Bluetooth modules use the so-called SPP (Serial Port Profile), also known as RFCOMM. When the controller is paired with the tablet it will behave like a regular serial port.

To receive the messages the application will simply create a Bluetooth socket and read the data as it appears. The tricky part is that we are using an asynchronous protocol, without flow control. Consequently the application has no say or knowledge of when the data will come. It will need to continuously poll the socket, read the available data as it arrives and parse it into meaningful position readings.

Data processing and reading needs to happen as fast as possible, so we don't run into buffer overrun issues etc. (no pun intended.) Before going further, let's figure out what kind of parameters we will be working with. Arduino and the BT module can run at 115200kbps, we might, in theory, need to read and process close to 11520 characters per second (each character takes 10 bits, 8 for data and 2 for start and stop). This amounts to a bit over 86 micro seconds to process each character. Even on modest single CPU system this gives us plenty of time to get things done, as long as we don't do anything silly.

One way to process our data is to append the read characters to a string until a terminator character is encountered. At that point the string is tested against a regular expression, and if the match succeeds, parse the string (either by breaking it into substrings or using regular expression's named groups). This approach might work, and it might even work fast enough, but it has a few tablet-specific problems that I'd like to avoid. First of all, strings are immutable, so any time you make a change to a string (in this case by adding a character), you are actually creating a new string. The problem arises from the fact that we could be potentially creating and destroying over 11000 strings per second, so the tablet will spend considerable amount of time performing garbage collection (reclaiming the memory freed by the discarded strings). On top of that, constant string matching using regular expressions doesn't come free either (I've seen some figures suggesting as much as 10x overhead). I think we can do much better.

Warning: copious amounts of geek gobbledygook ahead. Please wear your safety gear...
A much more efficient solution would be to implement a simple parser/interpreter. To do so we would implement a FSM (Finite State Machine) for the following grammar:

message:= axis digit_0

axis := 'x' | 'y' | 'z' | 'w' | 'a' | 'b' | 'c' | 'd'

digit_0:= '-' digit
  |'0' digit
  |'1' digit
  |'2' digit
  |'3' digit
  |'4' digit
  |'5' digit
  |'6' digit
  |'7' digit
  |'8' digit
  |'9' digit

digit:= '0' digit
  |'1' digit
  |'2' digit
  |'3' digit
  |'4' digit
  |'5' digit
  |'6' digit
  |'7' digit
  |'8' digit
  |'9' digit
  | ';'
 

This grammar can be parsed by the following state machine:

Finite state machine used to parse a message

As you can see, this is a very simple machine that can be implemented using a reasonably small switch statement. This way each character is going to be read and compared only once, and we woudn't be creating thousands of strings in process. This not only reduces the memory footprint, but frees up a lot of processing power.