Practical Arduino C
Chapter 12: Extras
Page 185
Page 186
struct Lookup
{
byte code;
char result;
};
struct Lookup bSearch[36];
struct Node
{
byte left;
byte right;
char result;
};
struct Node bTree[40];
void createCodeArray() {
for(int i = 0; i < 36; i++) {
bSearch[i].code = mCode[i];
bSearch[i].result = (i < 26) ? (char)(i + 65) :
(char)(i + 22);
}
}
// a quick sort for the bSearch array Lookup structs
// makes use of pointer arithmatic (just for fun)
void bSort(Lookup array[], int left, int right) {
if(left > right) {return;}
swapB(array + left, array + ((left + right) / 2));
int last = left;
for(int i = left + 1; i <= right; i++) {
if(compB(array + i, array + left) < 0) {
swapB(array + (++last), array + i);
}
}
swapB(array + left, array + last);
bSort(array, left, last - 1);
bSort(array, last + 1, right);
}
Page 187
int compB(Lookup* a, Lookup* b) {
if(a->code == b->code) {return 0;}
return (a->code > b->code) ? 1 : -1;
}
void swapB(Lookup* a, Lookup* b) {
Lookup temp = *a;
*a = *b;
*b = temp;
}
void createBinaryTree() {
for(int i = 0; i < 40; i++) {
bTree[i].result = ' ';
}
int bIndex = 0;
for(int i = 0; i < 36; i++) {
bIndex = 0; // start at the beginning
byte code = bSearch[i].code;
int bc = code & ((1 << 3)-1);
for(int bi = 0; bi < bc; bi++) {
if((code & HIBIT_MASK) == 0){
// dot
if(bTree[bIndex].left == 0) {
bTree[bIndex].left = nextFree();
}
bIndex = bTree[bIndex].left;
} else {
if(bTree[bIndex].right == 0) {
bTree[bIndex].right = nextFree();
}
bIndex = bTree[bIndex].right;
}
code = code << 1;
}
bTree[bIndex].result = bSearch[i].result;
}
}
byte nextFree() {
static byte nFree = 0;
return ++nFree;
}
Page 188
char treeSearch(byte findThis) {
int treeIndex = 0;
int bc = findThis & ((1 << 3)-1);
for(int bi = 0; bi < bc; bi++) {
if((findThis & HIBIT_MASK) == 0){
treeIndex = bTree[treeIndex].left;
} else {
treeIndex = bTree[treeIndex].right;
}
findThis = findThis << 1;
}
return bTree[treeIndex].result;
}
void displayTreeCode() {
Serial.print("const Node bTree[] = {");
for(int i = 0; i < 40; i++) {
Serial.print((i > 0) ? ", {" : "{");
Serial.print(bTree[i].left);
Serial.print(", ");
Serial.print(bTree[i].right);
Serial.print(", '");
Serial.print(bTree[i].result);
Serial.print("'}");
}
Serial.println("};");
}
void testTree() {
Serial.println("Testing binary tree");
for(int i = 0; i < 36; i++) {
Serial.print((i < 26) ? (char)(i + 65) :
(char)( i + 22));
Serial.print(" : ");
char getC = treeSearch(mCode[i]);
Serial.println(getC);
}
}
Page 189
void setup() {
Serial.begin(115200);
createCodeArray(); // load codes into bSearch
bSort(bSearch, 0, 35); // sort the array
createBinaryTree();
displayTreeCode();
testTree();
}
const Node bTree[] = {{1, 20, ' '}, {2, 13, 'E'}, {3, 9, 'I'},
{4, 7, 'S'}, {5, 6, 'H'}, {0, 0, '5'},
{0, 0, '4'}, {0, 8, 'V'}, {0, 0, '3'},
{10, 11, 'U'}, {0, 0, 'F'}, {0, 12, ' '},
{0, 0, '2'}, {14, 16, 'A'}, {15, 0, 'R'},
{0, 0, 'L'}, {17, 18, 'W'}, {0, 0, 'P'},
{0, 19, 'J'}, {0, 0, '1'}, {21, 29, 'T'},
{22, 26, 'N'}, {23, 25, 'D'}, {24, 0, 'B'},
{0, 0, '6'}, {0, 0, 'X'}, {27, 28, 'K'},
{0, 0, 'C'}, {0, 0, 'Y'}, {30, 34, 'M'},
{31, 33, 'G'}, {32, 0, 'Z'}, {0, 0, '7'},
{0, 0, 'Q'}, {35, 37, 'O'}, {36, 0, ' '},
{0, 0, '8'}, {38, 39, ' '}, {0, 0, '9'},
{0, 0, '0'}};
void showCode() {
for(int i = 0, j = sizeof(readCodes); i < j; i++) {
if(readCodes[i] == B00000000) {
if(i > 0 and readCodes[i-1] == B00000000) {
break;
}
Serial.println(" ");
} else {
Serial.print(treeSearch(readCodes[i]));
}
}
}
Page 190
#define CODE_LIMIT 30
byte readCodes[CODE_LIMIT];
int nextCode = 0;
void rollCodes() {
nextCode--;
for(int i = 0; i < nextCode; i++) {
readCodes[i] = readCodes[i+1];
}
}
void showCode(bool all) {
for(int i = 0; i < nextCode; i++) {
if(readCodes[i] == B00000000) {
Serial.println(" ");
} else {
Serial.print(treeSearch(readCodes[i]));
}
if(!all) {return;}
}
nextCode = 0;
}
Page 191
void readBytes(bool justOne) {
bool codeAdded = false;
int bCount = 0;
byte wrk = B00000000;
while(signalQ->count) {
SignalInt* item = readFirst();
long t = item->intTime;
if(item->isCode) {
wrk = wrk << 1;
if(t >= codeTimes[dash].minMillis &&
t <= codeTimes[dash].maxMillis) {
wrk ^= 1;
}
bCount++;
} else {
if(t >= codeTimes[letterSpace].minMillis) {
wrk = wrk << (8 - bCount);
wrk ^= bCount;
bCount = 0;
readCodes[nextCode] = wrk;
codeAdded = true;
nextCode++;
wrk = B00000000;
if(t >= codeTimes[wordSpace].minMillis &&
t <= codeTimes[wordSpace].maxMillis){
readCodes[nextCode] = wrk;
nextCode++;
}
}
}
deQueue();
if((justOne && codeAdded) || nextCode > CODE_LIMIT - 1) {break;}
}
}
Page 192
void loop() {
switch(sStatus) {
case 2:
detachInterrupt(digitalPinToInterrupt(MORSE_PIN));
sStatus = 0;
while(signalQ->count > 0 || nextCode > 0) {
readBytes(false);
while(nextCode > 0) {
showCode(true); // display all characters in array
}
}
attachInterrupt(digitalPinToInterrupt(MORSE_PIN),morseInter,CHANGE);
Serial.println("Ready for more");
break;
case 1:
if(signalQ->count >=11 && nextCode < CODE_LIMIT - 2) {
readBytes(true); // read a character from signal stream
}
if(nextCode > 0) {
showCode(false); // display top character
rollCodes(); // roll it off the array
}
break;
}
}
Page 193
} else {
int t = (unsigned long)(currentMicros -
lastMicros) / 1000;
if(wasCode || t >= codeTimes[letterSpace].minMillis) {
if(queueAdd(wasCode, t)) {
TCNT1 = 3036; // reset timer
} else {
sStatus = 2; // error adding to Q so stop
}
}
Further thoughts
By the time we got to the end of the development of the Morse reading program we could have refined the SignalInt structure.The time value no longer needed to be a long and could have been signed and the sign bit used in place of the boolean isCode.
Alternately the idea from Charles Petzold could also have been applied to load incoming signals into a sequence of bytes.
As the final program demonstrated that Morse could be translated into text more or less in real time the readCodes[] array could be smaller although the rollCodes() function never has to work very hard.