Thursday, June 25, 2015

Arduino Retro Computer: BASIC Interpreter (Variables)

Design


The Arduino works by having a single large block of memory that is manipulated from both the beginning and end: the HEAP starts at the beginning and works forward, the stack starts at the end and works back. As long as the two never intersect, you're good.

I designed my memory to be the same. I didn't want to use any more of the onboard memory of the Arduino for program variables because it's already very limited (and I'm running out!). Instead, I have the variables written to the FRAM memory block.

Each variable name has a maximum of 10 characters. The name must include a symbol to denote what kind of variable it is (matching QBasic's convention):
$ String (100 characters)
% Integer (4 bytes)
! Float (4 bytes)

Rather than mess with memory fragments and/or shifting large amounts of memory left and right every time a string variable gets resized, I decided to make each string variable take up a 100 character block of memory. A little wasteful, but that can be readdressed later if necessary (ha ha).

The memory structure (from the end back):
<Length of Data><Name of variable with symbol, 10 characters><Data>
.. repeat ..

A length of data of 0 denotes there are no more variables present.

(You'll see I'm using the long variable type for my integer. An int on the Arduino is only 16 bits, so you have to use a long for a 32 bit integer.)

Code


Before we dive into the new code, here's a quick recap of some existing code:

    // Programs are stored in a block of memory.
    // Code is stored from the beginning towards the end.
    // Variables are stored from the end towards the beginning.
    programMemoryAddressStart_bytes = screenIndex * programMemorySizePerScreen_bytes;
    programMemoryAddressEnd_bytes = programMemoryAddressStart_bytes + programMemorySizePerScreen_bytes - 1;

So inside the given ScreenModel, the variables will start at programMemoryAddressEnd_bytes, and work themselves back to programMemoryAddressStart_bytes.

New const at the top of the code:

const int sizeOfVariableName = 10;

The following code is all contained within my ever growing class ScreenModel. I'll eventually break these parts out into separate classes...

A simple enumeration to keep track of the variable type I'm working with:

  enum variableType
  {
    undefinedType = 0,
    stringType = 1,
    integerType = 2,
    floatType = 3
  };

I modified my startProgram() to automatically clear out all the program variables. I can see use cases for not doing this but that feature can be added later:

  bool startProgram()
  {
    programMemoryAddressCurrent_bytes = programMemoryAddressStart_bytes;

    // Clear Program Variables
    programVariablesClear();
    
    operatingMode = operatingModeProgram;

    return true;
  }

  bool programVariablesClear()
  {
    // Program memory starts at the end and works forward. Setting a name of
    // 0 length for the first program memory address effectively clears all memory.
    fram.write8(programMemoryAddressEnd_bytes, 0);
         
    return true;
  }

A function to find the next empty memory address spot:

  int getNextProgramVariableAddress_bytes()
  {
    int loopAddress_bytes = programMemoryAddressEnd_bytes;
    while (loopAddress_bytes > programMemoryAddressStart_bytes)
    {
      byte variableLength_bytes = fram.read8(loopAddress_bytes);
      if (variableLength_bytes == 0)
      {
        // Found next location for variable.
        return loopAddress_bytes;
      }
      else
      {
        // Decrement the loopAddress back (past the length).
        loopAddress_bytes -= 1;
        
        // Decrement the loopAddress back (past the variable name).
        loopAddress_bytes -= sizeOfVariableName;
        
        // Decrement the loopAddress back (past the variable contents).
        loopAddress_bytes -= variableLength_bytes;
      }
    }

    // No memory available.
    return -1;
  };

And a function to get the memory address of a variable:

  int getProgramVariableAddress_bytes(char *variableName)
  {
    int loopAddress_bytes = programMemoryAddressEnd_bytes;
    while (loopAddress_bytes > programMemoryAddressStart_bytes)
    {
      byte variableLength_bytes = fram.read8(loopAddress_bytes);
      if (variableLength_bytes == 0)
      {
        // Variable name length of 0, ran out of variables.
        return -1;
      }
      else
      {
        // Decrement the loopAddress back (past the length).
        loopAddress_bytes -= 1;

        // Found a variable in our loop, gets its name.
        char loopVariableName[11];
        for (int loopVariableNameIndex = 0; loopVariableNameIndex < sizeOfVariableName; loopVariableNameIndex++)
        {
          loopVariableName[loopVariableNameIndex] = fram.read8(loopAddress_bytes-loopVariableNameIndex);
        }
        // Null terminate.
        loopVariableName[sizeOfVariableName] = 0;

        // Decrement the loopAddress back (past the the variable name).
        loopAddress_bytes -= sizeOfVariableName;
        
        // Compare the variable name from the loop to what was passed in.        
        if (!strcmp(variableName, loopVariableName))
        {
          // A match!
          
          // Go back to the start of the variable block (the length field).
          loopAddress_bytes += 11;
          
          return loopAddress_bytes;
        }
        else
        {
          // Decrement the loopAddress back (past the variable contents).
          loopAddress_bytes -= variableLength_bytes;
        }
      }
    } // loopAddress_bytes
    
    // Never found a match.
    return -1;
  }

Each variable type is read slightly differently from memory:

  bool programVariableReadInt32(char *variableName, long *variableValue)
  {
    // Get the memory address of this variable.
    int memoryAddress_bytes = getProgramVariableAddress_bytes(variableName);
    
    if (memoryAddress_bytes < 0)
    {
      // Variable not found.
      return false;
    }
    
    // Skip over the variable length & name.
    memoryAddress_bytes -= 11;
    
    if ((memoryAddress_bytes - 3) < programMemoryAddressStart_bytes)
    {
      // Bad memory location.
      return false;
    }
    
    // Return the integer value!
    *variableValue = ((long)fram.read8(memoryAddress_bytes - 0) << 0) |
                     ((long)fram.read8(memoryAddress_bytes - 1) << 8) |
                     ((long)fram.read8(memoryAddress_bytes - 2) << 16) |
                     ((long)fram.read8(memoryAddress_bytes - 3) << 24);
       
    return true;
  }
  
  bool programVariableReadFloat32(char *variableName, float *variableValue)
  {
    // Get the memory address of this variable.
    int memoryAddress_bytes = getProgramVariableAddress_bytes(variableName);
    
    if (memoryAddress_bytes < 0)
    {
      // Variable not found.
      return false;
    }
    
    // Skip over the variable length & name.
    memoryAddress_bytes -= 11;
    
    if ((memoryAddress_bytes - 3) < programMemoryAddressStart_bytes)
    {
      // Bad memory location.
      return false;
    }
    
    // Return the float value!
    long integerValue = ((long)fram.read8(memoryAddress_bytes - 0) << 0) |
                        ((long)fram.read8(memoryAddress_bytes - 1) << 8) |
                        ((long)fram.read8(memoryAddress_bytes - 2) << 16) |
                        ((long)fram.read8(memoryAddress_bytes - 3) << 24);

    *variableValue = *(float*)&integerValue;
    
    return true;
  }
  
  bool programVariableReadString(char *variableName, char *variableValue)
  {
    // Get the memory address of this variable.
    int memoryAddress_bytes = getProgramVariableAddress_bytes(variableName);

    if (memoryAddress_bytes < 0)
    {
      // Variable not found.
      return false;
    }

    int variableLength_bytes = (int)fram.read8(memoryAddress_bytes); // sizeOfCommandArray;

    // Skip over the variable length & name.
    memoryAddress_bytes -= 11;
    
    if ((memoryAddress_bytes - variableLength_bytes) < programMemoryAddressStart_bytes)
    {
      // Bad memory location.
      return false;
    }
   
    // Read from the memory address back.
    for (int variableOffset_bytes = 0;
             variableOffset_bytes < variableLength_bytes;
             variableOffset_bytes ++)
    {
      // Store the character.
      *variableValue = (char)fram.read8(memoryAddress_bytes - variableOffset_bytes);
      if (*variableValue == 0)
      {
        // Null termination.
        break;
      }
      variableValue ++;
    }
    
    return true;
  }

Each variable type is also written slightly differently to memory:

  bool programVariableWriteInt32(char *variableName, long variableValue)
  {
    // Get the memory address of this variable.
    int memoryAddress_bytes = getProgramVariableAddress_bytes(variableName);
    
    if (memoryAddress_bytes < 0)
    {
      // Variable not found, create it.
      memoryAddress_bytes = getNextProgramVariableAddress_bytes();
    }
    
    if (memoryAddress_bytes < 0)
    {
      // No valid memory location found, give up.
      return false;
    }

    // Store the variable size. Integer is 4 bytes.
    byte variableSize_bytes = 4;
    fram.write8(memoryAddress_bytes, variableSize_bytes);

    // Store the variable name.
    for (int variableNameOffset_bytes = 0;
             variableNameOffset_bytes < sizeOfVariableName;
             variableNameOffset_bytes ++)
    {
      fram.write8((memoryAddress_bytes - variableNameOffset_bytes - 1), *variableName);
      if (*variableName!=0)
      {
        // Increment to the next variable name character (as long as we
        // haven't already reached the null terminator).
        variableName ++;
      }
    }

    // Store the variable value.
    // Take an 8 bit mask of the 32 bit variable, shift it to the right
    // to the position as necessary to write into FRAM.
    fram.write8((memoryAddress_bytes - 11), ((variableValue & 0xFF) >> 0));
    fram.write8((memoryAddress_bytes - 12), ((variableValue & 0xFF00) >> 8));
    fram.write8((memoryAddress_bytes - 13), ((variableValue & 0xFF0000) >> 16));
    fram.write8((memoryAddress_bytes - 14), ((variableValue & 0xFF000000) >> 24));
    
    return true;
  }
  
  bool programVariableWriteFloat32(char *variableName, float variableValue)
  {
    // Get the memory address of this variable.
    int memoryAddress_bytes = getProgramVariableAddress_bytes(variableName);
    
    if (memoryAddress_bytes < 0)
    {
      // Variable not found, create it.
      memoryAddress_bytes = getNextProgramVariableAddress_bytes();
    }
    
    if (memoryAddress_bytes < 0)
    {
      // No valid memory location found, give up.
      return false;
    }
    
    // Store the variable size. Float is 4 bytes.
    byte variableSize_bytes = 4;
    fram.write8(memoryAddress_bytes, variableSize_bytes);

    // Store the variable name.
    for (int variableNameOffset_bytes = 0;
             variableNameOffset_bytes < sizeOfVariableName;
             variableNameOffset_bytes ++)
    {
      fram.write8((memoryAddress_bytes - variableNameOffset_bytes - 1), *variableName);
      if (*variableName!=0)
      {
        // Increment to the next variable name character (as long as we
        // haven't already reached the null terminator).
        variableName ++;
      }
    }

    // Store the variable value.
    // Take an 8 bit mask of the 32 bit variable, shift it to the right
    // to the position as necessary to write into FRAM.
    long variableValueInt = *(long*)&variableValue;
    fram.write8((memoryAddress_bytes - 11), (variableValueInt & 0xFF) >> 0);
    fram.write8((memoryAddress_bytes - 12), (variableValueInt & 0xFF00) >> 8);
    fram.write8((memoryAddress_bytes - 13), (variableValueInt & 0xFF0000) >> 16);
    fram.write8((memoryAddress_bytes - 14), (variableValueInt & 0xFF000000) >> 24);

    return true;
  }
  
  bool programVariableWriteString(char *variableName, char *variableValue)
  {
    // Get the memory address of this variable.
    int memoryAddress_bytes = getProgramVariableAddress_bytes(variableName);
    
    if (memoryAddress_bytes < 0)
    {
      // Variable not found, create it.
      memoryAddress_bytes = getNextProgramVariableAddress_bytes();
    }
    
    if (memoryAddress_bytes < 0)
    {
      // No valid memory location found, give up.
      return false;
    }

    // Store the variable size.
    byte variableSize_bytes = sizeOfCommandArray;
    fram.write8(memoryAddress_bytes, variableSize_bytes);

    // Store the variable name.
    for (int variableNameOffset_bytes = 0;
             variableNameOffset_bytes < sizeOfVariableName;
             variableNameOffset_bytes ++)
    {
      fram.write8((memoryAddress_bytes - variableNameOffset_bytes - 1), *variableName);
      variableName ++;
    }

    // Store the variable value.
    for (int variableValueOffset_bytes = 0;
             variableValueOffset_bytes < sizeOfCommandArray;
             variableValueOffset_bytes ++)
    {
      fram.write8((memoryAddress_bytes - variableValueOffset_bytes - 11), *variableValue);
      if (*variableName!=0)
      {
        // Increment to the next variable name character (as long as we
        // haven't already reached the null terminator).
        variableName ++;
      }
    }

    return true;
  }


Within the existing parseProgramString function:

  bool parseProgramString(char *programString)
  {
    .
    .
    else if (!strncmp(programString, "print ", 6))
    {
      parseProgramPrintVariable(programString + 6);
    }
    else if (!strncmp(programString, "let ", 4))
    {
      parseProgramLet(programString + 4);
    }
    .
  }

A helper function so we know what type of variable we're dealing with based on its name:

  int getProgramVariableType(char *variableName)
  {
    while (*variableName != 0)
    {
      switch (*variableName)
      {
        case '$':
          return stringType;
        case '%':
          return integerType;
        case '!':
          return floatType;
      }
      variableName++;
    }
    return undefinedType;
  }

Using the let command to write a variable

  bool parseProgramLet(char *commandString)
  {
    // Up to the first 10 characters (or the first space) is the variable name.
    char variableName[sizeOfVariableName+1];
    memset(variableName, 0, sizeOfVariableName+1);
    for (int variableNameLoop = 0; variableNameLoop < sizeOfVariableName; variableNameLoop++)
    {
      if (*commandString == 0)
      {
        // Should not have reached null terminate yet, fail out.
        advanceNextProgramMemoryAddress();
        return false;
      }
      else if (*commandString == ' ')
      {
        // Done with variable name.
        commandString++;
        break;        
      }
      else
      {
        variableName[variableNameLoop] = *commandString;
        commandString++;
      }
    }

    // The remaining characters are the value.
    switch (getProgramVariableType(variableName))
    {
      case stringType:
        {
          char stringValue[sizeOfCommandArray];
          memset(stringValue, 0, sizeOfCommandArray);
          strcpy(stringValue, commandString);
          programVariableWriteString(variableName, stringValue);
        }
        break;
      case integerType:
        {
          long integerValue = (long)strtod(commandString, &commandString);
          programVariableWriteInt32(variableName, integerValue);
        }
        break;
      case floatType:
        {
          float floatValue = (float)strtod(commandString, &commandString);
          programVariableWriteFloat32(variableName, floatValue);
        }
        break;
    }  

    advanceNextProgramMemoryAddress();
    
    return true;
  }

Using the print command to display the variable's value:

  bool parseProgramPrintVariable(char *variableName)
  {
    bool errorDetected = false;
    switch (getProgramVariableType(variableName))
    {
      case stringType:
        char printString[sizeOfCommandArray];
        if (programVariableReadString(variableName, printString))
        {
          // Successfully found string value, print it.
          addOutputLine(printString);
        }
        else
        {
          errorDetected = true;
        }
        break;
      case integerType:
        long integerValue;
        if (programVariableReadInt32(variableName, &integerValue))
        {
          // Successfully found integer value, print it.
          char printString[sizeOfOutputColumnArray];
          snprintf(printString, sizeOfOutputColumnArray, "%ld", integerValue);
          addOutputLine(printString);
        }
        else
        {
          errorDetected = true;
        }
        break;
      case floatType:
        float floatValue;
        if (programVariableReadFloat32(variableName, &floatValue))
        {
          // Successfully found float value, print it.
          char printString[sizeOfOutputColumnArray];
          dtostrf(floatValue, sizeOfOutputColumnArray-1, 8, printString);
          addOutputLine(printString);
        }
        else
        {
          errorDetected = true;
        }
        break;
      default:
        errorDetected = true;
        break;
    }
    
    if (errorDetected)
    {
      addOutputLine("-- Error printing variable. --");
    }
    
    advanceNextProgramMemoryAddress();
    
    return true;
  }

Future Improvements 


When the program executes I could warn the user if the total number of "let <variable>" will eat into their program. And I can throw an out of memory error rather than overwrite code when that happens.

Store only the used length of a string. When that string variable is resized, shift the adjacent memory as necessary. Good for memory consumption, bad for performance.


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.

No comments:

Post a Comment