Arduino Retro Computer: Managing Program Memory (FRAM)

Arduinos have very limited onboard RAM, so for my retro computer I'll be using the FRAM I added in the last post to store the BASIC programs. Managing FRAM isn't difficult, but it's a bit more complex than just defining a big array to manipulate. Below I create a handful of functions to manage the quirks of reading from and writing to FRAM.

The format and functions below are designed for a line number based program memory that you need to traverse forward and back through. However, it could easily be adapted for other types of storage. Please see the Alternate Data Formats section for ideas on how to make a pseudo file system.

Data Format

Programs can have any number of lines and each line can have anywhere from 1 to 100 characters. I don't want to block off the memory in 100 character chunks, because then my maximum program size would only be 320 lines (32,000 / 100). To maximize program size, I include the length of the command alongside the command so I can traverse forward and back with no wasted space.

I formatted the data within the chip as follows:
[Length of Command, 1 Byte, UInt8][Line Number, 4 Bytes, Int32][Command, Up to 100 Bytes, Char Array][Length of Command, 1 Byte, UInt8] .. repeat until length of command = 0..

The [Length of Command] field is so I know how long the current command line is. If the length is 0, then I know this is the end of the program. It's necessary to have the length before and after the data so I can traverse forward and backwards through the memory. An example reason to navigate backwards is to jump to a previous line for a "Goto" command without having to read from the beginning.

The [Line Number] field is an integer of the program's line number. This is purely for performance so that I can quickly parse what the line number is and jump forward or back as necessary. Converting text to an integer then comparing it to another integer is much slower than just comparing two integers.

The [Command] field is the complete command line the user had entered.

An example set of data:
10 PRINT "HELLO WORLD"
20 PRINT "HOW ARE YOU?"

Would be stored in memory as:
[22][10][10 PRINT "HELLO WORLD"][22][23][20][20 PRINT "HOW ARE YOU?"][23][0]

Alternate Data Formats

If you don't need to traverse back through the program memory, then you can leave out the 2nd length byte. That would save one byte per data entry and simplify things a bit.

Even more interesting, if you wanted to use this as a file system you could replace the 4-byte integer with a short string of characters (how about an 8 byte filename + 3 byte extension!).

[Length of File, 2 Bytes, UInt16][File Name + Extension, 11 Bytes, Char Array][File Data, Up to 65535 Bytes (or size of memory)] .. repeat until length of file = 0..

On the plus side, the file system would never be fragmented (the code below doesn't allow wasted space between data, it always condenses it upon each delete or insert). On the downside, it does a lot of extra read/writes to keep the data compressed / defragged. Which is ok for FRAM (fast, lots of writes are ok), but that could be bad for other types of memory.

Setup / Constants

I use the same FRAM chip for all the screens of the Arduino. So at each screen's instantiation, I assign a block of bytes of the FRAM chip for that screen's program memory.

Screen 0 will have memory address 0 through 15999.
Screen 1 will have memory address 16000 through 31999.

const int programMemorySizePerScreen_bytes = 16000;

class ScreenModel
{
  ...
  int programMemoryAddressStart_bytes;
  int programMemoryAddressEnd_bytes;

  bool init(byte newIndex)

  {

    screenIndex = newIndex;

    programMemoryAddressStart_bytes = screenIndex * programMemorySizePerScreen_bytes;

    programMemoryAddressEnd_bytes = programMemoryAddressStart_bytes + programMemorySizePerScreen_bytes - 1;

    ...

  }

  ...
}

Clearing the Program

The Program Memory is stored from programMemoryAddressStart_bytes to programMemoryAddressEnd_bytes. As soon as a command length returns a 0, I consider that the end of the program. If I want to clear a program, it's very easy - just set the first memory address to 0 length.

  bool commandNew()
  {
    programMemoryNew();
    addOutputLine("New program created.");

    return true;
  }

  bool programMemoryNew()
  {
    // Set first memory address to null. It's not necessary to individually
    // clear every line - we won't traverse past a null line.
    fram.write(programMemoryAddressStart_bytes, 0);
    
    return true;
  }

Reading / Writing Line Numbers

I store the line number as a 4-byte integer in the FRAM. Since the FRAM library only writes and reads individual bytes, I have to use bitwise operations to handle the number.

  long getProgramMemoryLineNumber(int memoryAddress_bytes)
  {
    // Get the 4 byte line number from 4 single bytes of the FRAM memory.
    // Take each single byte and offset its position into the corresponding
    // location of the 32 bit integer, then do an OR bitwise operation to
    // combine them into a single number.
    // Please note, Arduino int is only 2 bytes, using long for a 4 byte integer.
    return ((long)fram.read8(memoryAddress_bytes + 4) << 0) |
           ((long)fram.read8(memoryAddress_bytes + 3) << 8) |
           ((long)fram.read8(memoryAddress_bytes + 2) << 16) |
           ((long)fram.read8(memoryAddress_bytes + 1) << 24);
  }
  
  bool setLineNumberToMemory(char *memoryAddress_bytes, long writeLineNumber)
  {
    // Take an 8 bit mask of the 32 bit line number, shift it to the right
    // most 8 bits, then store it in an 8 bit char. Increment the pointer
    // by one byte and repeat until all 4 bytes of the line number have
    // been stored.
    // Please note, Arduino int is only 2 bytes, using long for a 4 byte integer.
    *memoryAddress_bytes = (char)((writeLineNumber & 0xFF000000) >> 24);
    memoryAddress_bytes ++;
    *memoryAddress_bytes = (char)((writeLineNumber & 0xFF0000) >> 16);
    memoryAddress_bytes ++;
    *memoryAddress_bytes = (char)((writeLineNumber & 0xFF00) >> 8);
    memoryAddress_bytes ++;
    *memoryAddress_bytes = (char)((writeLineNumber & 0xFF) >> 0);
    return true;
  }

Memory Manipulation Functions

The following are a variety of supporting function for reading and writing to a memory address.

  int getLastProgramMemoryAddress(int startingAddress_bytes)
  {
    // Find the last program memory address.
    int loopAddress_bytes = startingAddress_bytes;
    while (loopAddress_bytes <= programMemoryAddressEnd_bytes)
    {
      byte loopCommandLength_bytes = fram.read8(loopAddress_bytes);
      
      if (loopCommandLength_bytes == 0)
      {
        // Found the last program memory address.
        break;
      }
      else
      {
        // Increment forward past the command length and supporting variables.
        // 1 Byte, UInt8, Length of Command
        // 4 Bytes, Int32, Line Number
        // # Bytes, Char[], Data
        // 1 Byte, UInt8, Length of Command
        loopAddress_bytes += 1 + 4 + loopCommandLength_bytes + 1;
      }
    }
    return loopAddress_bytes;
  }

  bool programMemoryDeleteData(int deleteAddress_bytes)
  {
    // Get the length of the command.
    int lengthToDelete_bytes = 1 + 4 + fram.read8(deleteAddress_bytes) + 1;

    // Get the last address so we know how much data to shift.
    int lastAddress_bytes = getLastProgramMemoryAddress(deleteAddress_bytes);
    int newLastAddress_bytes = lastAddress_bytes - lengthToDelete_bytes;
    
    // This function shifts memory left (to delete data).
    // Start at the memory address to delete.
    int loopAddress_bytes = deleteAddress_bytes;

    // Loop to the last memory address.
    while (loopAddress_bytes <= newLastAddress_bytes)
    {
      // Copy the data byte then increment to the next address.
      byte dataToCopy = fram.read8(loopAddress_bytes + lengthToDelete_bytes);
      fram.write8(loopAddress_bytes, dataToCopy);
      loopAddress_bytes++;
    }
   
    return true;
  }

  bool programMemoryInsertData(int insertAddress_bytes, char writeData[sizeOfCommandArray+6], int writeDataLength_bytes)
  {
    // This function shifts memory right (for inserting data).
    
    // Start at the last program memory address.
    int lastAddress_bytes = getLastProgramMemoryAddress(insertAddress_bytes);

    for (int loopAddress_bytes = lastAddress_bytes;
             loopAddress_bytes >= insertAddress_bytes;
             loopAddress_bytes --)
    {
      fram.write8((loopAddress_bytes + writeDataLength_bytes), fram.read8(loopAddress_bytes));
    }
    
    // Insert the new data.
    for (int copyOffset_bytes = 0;
             copyOffset_bytes < writeDataLength_bytes;
             copyOffset_bytes ++)
    {
      fram.write8((insertAddress_bytes + copyOffset_bytes), writeData[copyOffset_bytes]);
    }
    
    // Terminate the program.
    fram.write8(lastAddress_bytes + writeDataLength_bytes, 0);

    return true;
  }

  int getProgramMemoryCommandString(int memoryAddress_bytes, char *memoryString)
  {
      byte commandLength_bytes = fram.read8(memoryAddress_bytes);
      memoryAddress_bytes += 1 + 4; // Skip over command length and line number field.
      for (int loopAddress_bytes = memoryAddress_bytes; loopAddress_bytes < memoryAddress_bytes + commandLength_bytes; loopAddress_bytes++)
      {
        // Copy the memory at this address into the memoryString.
        *memoryString = (char)fram.read8(loopAddress_bytes);
        // Then increment our memoryString pointer to the next memory block.
        memoryString++;
      }
      return commandLength_bytes;
  }

Editing a Program Line

If the user enters only a line number, then I interpret that as deleting the line. If the user enters any data after the line number, then I'll create a new line with that data. If the line already exists, I'll replace the existing line with the new one.

  bool commandEditProgramLine(char *commandString)
  {
    int lineNumber = atoi(commandString);
    if (lineNumber > 0)
    {
      // Get the string representation of that number.
      char lineNumberString[11];
      itoa(lineNumber, lineNumberString, 10);
      
      // If the commandString only contains the line number, then let's delete that line.
      if (strcmp(lineNumberString, commandString) == 0)
      {
        // Deleting a program line.
        if (programMemoryDeleteLine(lineNumber))
        {
          addOutputLine("Successfully deleted program line.");
        }
        else
        {
          addOutputLine("Error deleting program line.");
        }
      }
      else 
      {
        // Writing / editing a program line.
        if (programMemoryWriteLine(lineNumber, commandString, strlen(commandString)))
        {
          addOutputLine("Successfully wrote program line.");
        }
        else
        {
          addOutputLine("Error writing program line.");
        }
      }
    }
    else
    {
      addOutputLine("Invalid line number.");
    }
    
    return true;
  }

  bool programMemoryWriteLine(int writeLineNumber, char commandData[sizeOfCommandArray], int commandDataLength_bytes)
  {
    // 1 Byte, UInt8, Length of Command
    // 4 Bytes, Int32, Line Number
    // # Bytes, Char[], Data
    // 1 Byte, UInt8, Length of Command

    int lastAddress_bytes = getLastProgramMemoryAddress(programMemoryAddressStart_bytes);
    
    int loopAddress_bytes = programMemoryAddressStart_bytes;
    while (loopAddress_bytes <= lastAddress_bytes)
    {
      byte loopCommandLength_bytes = fram.read8(loopAddress_bytes);

      // Check for end of program.      
      if (loopCommandLength_bytes == 0)
      {
        // End of program, write data here.
        break;
      }

      // Check if we're replacing or inserting at this line.
      int loopLineNumber = getProgramMemoryLineNumber(loopAddress_bytes);
      
      if (writeLineNumber == loopLineNumber)
      {
        // Overwrite the current line.
        programMemoryDeleteData(loopAddress_bytes);
        break;
      }
      else if (writeLineNumber < loopLineNumber)
      {
        // Insert write line here.
        break;
      }
      
      // Increment to the next data line.
      loopAddress_bytes += 1 + 4 + loopCommandLength_bytes + 1;
    }
    
    // Valid address to write to, insert now.
    char writeData[sizeOfCommandArray+6];
    writeData[0] = commandDataLength_bytes;
    // writeData[1] through writeData[4] will have the line number.
    setLineNumberToMemory(&writeData[1], writeLineNumber);
    memcpy(&writeData[5], commandData, commandDataLength_bytes);
    writeData[5 + commandDataLength_bytes] = commandDataLength_bytes;
    int writeDataLength_bytes = commandDataLength_bytes + 6;
    programMemoryInsertData(loopAddress_bytes, writeData, writeDataLength_bytes);
    
    return true;
  }

  bool programMemoryDeleteLine(int deleteLineNumber)
  {
    int lastAddress_bytes = getLastProgramMemoryAddress(programMemoryAddressStart_bytes);
    
    int loopAddress_bytes = programMemoryAddressStart_bytes;
    while (loopAddress_bytes <= lastAddress_bytes)
    {
      byte loopCommandLength_bytes = fram.read8(loopAddress_bytes);

      // Check for end of program.      
      if (loopCommandLength_bytes == 0)
      {
        // End of program.
        break;
      }

      // Check if we're deleting this line.
      int lineNumber = getProgramMemoryLineNumber(loopAddress_bytes);
      if (deleteLineNumber == lineNumber)
      {
        // Delete this line.
        programMemoryDeleteData(loopAddress_bytes);
        break;
      }

      // Increment to the next data line.
      loopAddress_bytes += 1 + 4 + loopCommandLength_bytes + 1;
    } // loopAddress_bytes <= lastAddress_bytes
    return true;
  }

Listing the Contents of a Program

The commandList() function traverses the entire program to print each line of code to the screen. Ultimately I'll also have it so users can give a range of line numbers to display.

  bool commandList()
  {
    addOutputLine("== Start of Program ==");
    int lastAddress_bytes = getLastProgramMemoryAddress(programMemoryAddressStart_bytes);
    
    int loopAddress_bytes = programMemoryAddressStart_bytes;
    while (loopAddress_bytes <= lastAddress_bytes)
    {
      byte loopCommandLength_bytes = fram.read8(loopAddress_bytes);

      // Check for end of program.      
      if (loopCommandLength_bytes == 0)
      {
        // End of program.
        break;
      }

      char loopCommandString[sizeOfCommandArray];
      memset(loopCommandString, 0, sizeOfCommandArray);
      getProgramMemoryCommandString(loopAddress_bytes, loopCommandString);
      
      // The command array is up to 100 characters (2 lines x 50 characters per line).
      // We have to split up the output into two separate output lines if the user exceeds
      // the size of one line (50 characters). 
      for (int cursorIndex = 0; cursorIndex < loopCommandLength_bytes; cursorIndex += numberOfScreenColumns)
      {
        char commandLineOutput[sizeOfOutputColumnArray];
        memset(commandLineOutput, 0, sizeOfOutputColumnArray); // Ensure null terminated.
        // On the first loop through, copy the first 50 characters (numberOfScreenColumns).
        // If our cursor position exceeds 50 characters (numberOfScreenColumns), then
        // we'll loop through a second time to copy the remaining 50 characeters.
        memcpy(commandLineOutput, &loopCommandString[cursorIndex], numberOfScreenColumns);
        addOutputLine(commandLineOutput);
      } // cursorIndex
      
      // Increment to the next data line.
      loopAddress_bytes += 1 + 4 + loopCommandLength_bytes + 1;
    } // loopAddress_bytes <= lastAddress_bytes

    addOutputLine("==  End of Program  ==");
    return true;
  }

Commands Added to OS

The following if conditions were added to the submitCommand() function to parse the commands:

    else if (strcmp(commandFormatted, "new") == 0)
    {
      commandNew();
    }
    else if (strcmp(commandFormatted, "list") == 0)
    {
      commandList();
    }
    else if (isdigit(commandFormatted[0]))
    {
      commandEditProgramLine(commandFormatted);
    }

If the first character of the command entered begins with a number, then I interpret that as a user editing that program line.

We're approaching a fairly useful computer. Two must-have items remaining: a BASIC interpreter and case to protect everything.


Copyright (c) 2015 Clinton Kam
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.