Converting ASCII sequence to numbers
While hacking on a Forth interpreter for the AVR, I realised I'd have
to implement something like atoi(3).
There are two types of numbers that the interpreter has to process:
hexadecimal and decimal. Hexadecimal numbers are prefixed with $,
while decimal numbers are prefixed by #.
Hexadecimal
Here's the function, with some clean up and debug output emitted:
/*
* forth_process_himm takes a word (which is stored as a character
* buffer), and converts it to a 16-bit unsigned integer,
* interpreting it as a hexadecimal number.
*/
static void
forth_process_himm(char *word, uint8_t l)
{
uint8_t i, j;
uint16_t digit;
uint16_t n = 0;
if (l > 4) {
return;
}
for (i = 0; i < l; i++) {
digit = (uint16_t)(word[i] & 0xff);
/*
* The decimal digits are in a single row in
* the ASCII table, starting with character 0x48.
* The value of a digit from 0-9 can thus be calculated
* as the ASCII value - 48.
*/
if ((digit > 47) && (digit < 58)) {
digit -= 48;
}
/*
* Right now, only uppercase letters are supported
* until I can get a working version. Then, I can
* check for lowercase letters and ^= 0x20 to flip
* the case.
*
* This works similarly to the digit calculation;
* however, A-F start at 0x65. Also, A is a value
* of 10, so 10 needs to be added to the result.
* Alternatively, add 10 to the number being subtracted;
* hence the value of 55.
*/
else if ((digit > 64) && (digit < 71)) {
digit -= 55;
} else {
return;
}
/*
* Digits need to be shifted left by four (a multiply
* by 16) for each decimal place away from the
* least significant digit they are.
*/
for (j = 1; j < (l - i); j++) {
digit <<= 4;
}
/*
* Add the result to the final number.
*/
n += digit;
}
/*
* Push this number on the stack.
*/
stack_push(fstack, n);
}
Decimal
/*
* forth_process_dimm takes a word (which is stored as a character
* buffer), and converts it to a 16-bit unsigned integer,
* interpreting it as a decimal number.
*/
static void
forth_process_dimm(char *word, uint8_t l)
{
uint8_t i, j;
uint16_t digit;
uint16_t n = 0;
if (l > 5) {
return;
}
for (i = 0; i < l; i++) {
digit = (uint16_t)(word[i] & 0xff);
/*
* This is the same trick employed in forth_process_himm.
*/
if ((digit > 47) && (digit < 58)) {
digit -= 48;
} else {
return;
}
/*
* For each place away from the least signficant
* digit, we'll need to multiple by ten. This is
* accomplished by adding the number to itself
* (a multiply by two) and adding the number
* shifted left three places (a multiply by eight).
*/
for (j = 1; j < (l - i); j++) {
digit += (digit + (digit << 3));
}
n += digit;
}
stack_push(fstack, n);
}
The multiplication tricks are done as an optimisation. A multiply instruction takes a lot longer than either an addition or shift. A single shift takes usually one or two cycles to complete; an addition is on the same order. The addition and shift has a cycle or two of overhead copying the original value into a working register, but this is on the same order of magnitude. On ARM, for example, this might be
/* Duplicate the original value in r0 */
MOV r1, r0
* Add r0 to itself (multiply by 2) */
ADD r0, r0
/* Shift r1 left by 3 to multiply by 8 */
LSL r1, #3
/* Add these two together */
ADD r0, r1
According to AVR200: Multiply and Divide Routines, this multiplication would take 58 cycles to complete when optimised when using integer multiplication. These instructions each take one cycle a piece: four cycles total.
In fact, these can even be combined into a single instruction on ARM processors made in the last decade:
ADD r0, r0, r0,LSL #3
Other architectures do not share this feature.
These kinds of things are exactly why I love embedded engineering. Now, to try to get this thing working.