Secret Code

The Game Has Changed

Oliver Higgins

Issue 12, June 2018

Using the correct data storage can make or break your code.

Sometimes we need data faster, harder and better because the primitive variables just don’t work in the way we want them to. Occasionally we need to access our data at a faster rate, or create constructs that can hold much more complex information.

There comes a time when we need to have the right tool for the job. Often we can reach into our programming toolbox and find a simple solution that will work with minimal intervention on our behalf. But there are times when we need to use more complex ideas. The ideas and principles presented here, are heavy on the side of computer science. At a low level, the principles remain the same and are fundamental to how computers work; but the implementation between C++ and Python are very different.

THE BROAD OVERVIEW

We will examine the use of queues and stacks, as well as structs and pointers, as all these things will add up to faster and more reusable code.

Lets quickly take a moment to revisit some of the simple data types that are available to us:

  • Primitives
  • String/CHAR

“Hello World”

This is the string that we always use when we are demonstrating the fundamentals of a language. Depending on the system, the “string” variable itself, is made up of a sequence of single characters. These are referred to as a “CHAR”. Standard C is explicit in defining an array of CHARs, as opposed to a string, but modern compilers including Arduino’s Processing and Python allow a string. A string is one of the most common variables we use. This is how we will give real-world feedback to the users. For example, “Hello” in the example above. Generally, the only limitation on this array is the available memory on your chosen processor.

INTEGER, LONG AND BYTE

1 or 73 or 42 or 7854 or -598. These are all integers. They are whole numbers and are often referred to as “counting numbers”. They are used for counters, loops and basic data elements. They occupy 16 bits and are used to store whole numbers from -32768 to 32767. If our number exceeds this range, then you will need to use a “long” type. A “long” is an integer that occupies 32 bits, and as such can hold a much greater number range.

Please note we are sticking with the general rule of ANSI C. Most modern languages are a minimum of twice this size for a long. A byte stores an 8-bit unsigned number, from 0 to 255. This is often used for storing things like colour codes. If your memory is at a premium in your project, you should consider whether your number will exceed this.

FLOAT

In simplest terms, a “float” is a number that is a fraction. Variables declared of type float will have numbers on both sides of the decimal point. The term “float” is short for “floating point number”. Internally, floating point numbers are expressed as fractions of base two math, and can represent values ranging from approximately 1.5 × 10-45 to 3.4 × 1038 with a precision of seven digits. This is defined as single precision and occupies 32 bits on the system memory. Modern systems will allow you to simply define a float to store any number that requires a decimal; however, if your function requires more precision I would consult your language's guide.

DOUBLE

A “double” is a very similar construct to the float, but it occupies 64 bits and so offers much greater decimal precision and a wider range of values.

ARRAYS

We can group our various data types into “arrays”, where the data is stored in the Random Access Memory (RAM). These data elements must be of the same type, and are accessed via the array’s index.

The vast majority of problems can be solved by using the primitive data elements above. However, there are times when these do not quite work. In these cases, we have some special tools that can help. In programming and computer science, we have a special data type known as an “abstract data type” or “ADT”. An ADT is a mathematical model for data types, where a data type is defined by its behaviour (semantics), from the point of view of a user of the data; specifically regarding possible values, possible operations on data of this type, and the behaviour of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, rather than a user.

STACKS AND QUEUES

Stacks and queues are two instances of an ADT. We can only put data in and out in one way. If it’s a queue then it’s “First In First Out” (FIFO). For the stack, it is “Last In First Out” (LIFO). Unlike an array, which is stored in whatever part of the memory that gets allocated the stack has its data elements stacked one above the other. What this means for us is raw speed.

The functions to access these elements may seem clunky at first, but they are designed to allow a index to just move along, without looking at each data element or the individual piece. This becomes useful when you need to get pieces of data rapidly stored and processed, once the data capture is complete. To visualise this, think of your work desk right now. We find that there are many copies of DIYODE that have been placed around it in various states of reading and mid-project. Let’s clean up. We make a place in the corner but within easy reach. We pick up the first issue and push it into the allocated spot. We go back to the next issue, and we then push it on top of the first one, and so forth until all of our magazines have been placed in a stack. Now we know where they all are and they are in a neat stack. We may or may not have put them in order, but there is only one way to gain access to the magazines, and that is to remove them one after another until we find what we need.

In this case, we want to find a magazine issue that we remember contained a particularly useful piece of code. We take a peek at the top issue and see that it’s not the one we want, so we pop it off and look at the next. It’s still not the one, so we pop it off then continue to repeat this process until we find the one we want, or run out of issues. Reading through this, we may feel that it’s a little pointless, but if we look back to the original distribution of the magazines all over the desk, or all over the workshop even, you can see the stack makes them more easily accessible. It is much faster to access them, when they are in a stack. Stacks are often used to traverse and retraverse strings, allowing us to quickly pack and unpack chunks of data.

Fig 1

The stack is built in the order that the elements were stacked up.

PUSH / POP / PEEK

Unlike accessing a standard variable, we can only access the element that is on top of the stack. To add an element to the top, we use the “Push” function and “Pop” to remove it. When you push a value it goes to the top, when we pop, it is removed. We cannot access the data within the element unless we use these commands, so yes, we must remove all the elements if we want to get to the bottom or midway. The exception to this is the “peek” command. We can peek the topmost element without it being removed, but only this particular element.

Figure 2

We can implement the stack in any C style language without too many issues, but in Arduino, we do need to include the StackArray.h file. It should be included, but if not then please go to sketch|include library|manage libraries and add it there. For Python, this is a little different, so we’ll discuss that soon.

ARDUINO

In the following code we start by including the stack library header. We then declare the string message that we will be using. Then, we need to create a stack of characters in that string. Our start up code now runs. For this example, the code will just be running once. The serial communication is started, and we then set the printer of the stack. This specifies where the data will be outputted. We then print the message out before reversing it. To do this, we push all the message’s characters to the stack. We then print the message after reversing. To do this, we pop all the message’s characters from the stack, before printing the end of line character.

#include <StackArray.h>
const String msg = “Hello World!”;
StackArray <char> stack;
void setup () {
  Serial.begin (9600);
  stack.setPrinter (Serial);
  Serial.println (“Normal String: “ + msg);
  for (int i = 0; i < msg.length (); i++)
    stack.push (msg.charAt (i));
  Serial.print (“Reversed String: “);
  while (!stack.isEmpty ())
    Serial.print (stack.pop ());
  Serial.println ();
}

There is nothing happening in the main loop, so just leave it blank if you are testing this code.

PYTHON

The stack is used in many languages, but Python handles the majority of its data as lists; however, if you want to use this process we can easily create a class that will allow us to use lists as a stack. We need to create a py file as follows and call it Stack.py.

class Stack:
  def __init__(self):
    self.items = []
  def push(self, item):
    self.items.append(item)
  def pop(self):
    return self.items.pop()
  def is_empty(self):
    return (self.items == [])

Once we have this, we can now use push, pull and peek on our stack.

s = Stack()
s.push(54)
s.push(45)
s.push(“+”)

Now we can use is_empty and pop to remove and print all of the items on the stack.

while not s.is_empty():
  print(s.pop(), end=” “)

Python’s implementation is different, but there are times when you need to use this abstract methodology to achieve a certain outcome. This will prove to be a very powerful tool to have in our toolbox.

STRUCTS

Structs are a composite data type declaration that defines a physically grouped list of variables to be placed under one name in a block of memory, allowing the different variables to be accessed via a single pointer, or the struct declared name, which returns the same address. The struct can contain many other complex and simple data types in an association, so is a natural organising type for records like the mixed data types.

The C struct directly references a contiguous block of physical memory, usually delimited by word-length boundaries. Being a block of contiguous memory, each field within a struct is located at a certain fixed offset from the start. Because the contents of a struct are stored in contiguous memory, the size of operator must be used to get the number of bytes needed to store a particular type of struct, just as it can be used for primitives. The alignment of particular fields in the struct is implementation-specific, and may include padding, which may change the size in bytes used for alignment.

Something cool we can do with a struct is to use the EEPROM library. There are many times when we need our users to make some changes to the software that need to persist for the following session when the system boots. The way to do this is to use the system’s on-board memory. Boards vary in memory size but by using the EEPROM, we can save bytes of information used by our program. The difficulty in this is that we cannot just save single or multiple variables to the memory. We need to start at a particular point in the EEPROM's memory then work through each piece, byte by byte. If we need to use different types of variables, reading and writing needs to have some complex code. However, if we design our system to use a structure to store our key data, we can use the “EEPROMWriteAnything” library. In order to do this, we need to define what data that we will be saving. By creating this beforehand, the EEPROM library will allocate the required memory and is aware of the size that each variable needs. When we re-read it, it simply returns the data to its correct variable.

The following code shows a simple alarm system. Our alarm needs to have two variables that are persistent: alarm and mode, where alarm is a long, and mode is an integer. They each occupy a different number of bytes and, therefore, different size of EEPROM. We have to declare these two variables inside the structure declaration, and then we name the structure. In this case it’s called “configuration”.

We can now read and write our data to the EEPROM at any time, using EEPROM_readAnything and EEPROM_writeAnything. In the case of the following code, we have put an input button on pin 13. The code will save the settings each time the button is pressed.

#include <EEPROM.h>
#include “EEPROMAnything.h”
struct config_t
{
  long alarm;
  int mode;
} configuration;
void setup()
{
  Serial.begin(9600);
  EEPROM_readAnything(0, configuration);
}
void loop()
{
  if (digitalRead(13) == HIGH)
    EEPROM_writeAnything(0, configuration);
  Serial.println(configuration.alarm)
}

Another quick example of a struct could be to create a holder for 3 bytes, in this case, Red, Green and Blue. More commonly known as RGB. This means they will always be together and easy to access;

//Declare Struct
struct RGB {
  byte r;
  byte g;
  byte b;
};
//To access elements
variable.r == 255
Serial.Println(variable.g)

WHERE TO FROM HERE?

Both structs and stacks are valuable assets to have in your toolbox. Stacks can be confusing, but they serve an important purpose; they are fast and well worth taking the time to invest our energy in. Structs are a great tool and often overlooked. If you come from an object-oriented background, or even a data-driven environment, then they will make working with complex and dynamic data much easier.