Hi I'm taking a microprocessor class and trying to create a recursive function that returns the length of some strings that are in a linked-list structure.
I've been given this macro to work with and was hoping somebody could help me to understand it. Particularly I'd like to know how exactly using this macro creates a linked-list.
.set NEXT_STRING = 0x0000
.macro defstring
.set T = PC
.dw NEXT_STRING << 1
.set NEXT_STRING = T
.if strlen(@0) & 1
.db @0, 0
.else
.db @0, 0, 0
.endif
.endmacro
The ways it's used is as follows:
defstring "somestring"
defstring "another"
Then supposedly, a linked-list is created with these strings held as data on each node.
Any help appreciated, Thanks!
The line below declares an assembler constant called NEXT_STRING with a value of 0. Wherever NEXT_STRING appears in the program, it will be replaced by 0.
.set NEXT_STRING = 0x0000
I think the name NEXT_STRING could be confusing. It's actually a pointer to the last string you declared in your assembly file.
This line sets T to equal the current program counter (PC). So that is the current location in flash that the assembler is writing to.
.set T = PC
The .dw directive below writes a 16-bit word to flash, with the specified value. This word will store a pointer to the next node in the list, so we set it equal to NEXT_STRING. The bit shift part is probably due to the fact that the PC counts in words, but AVR pointers count in bytes, so you have to multiply by 2 when turning a PC value into a pointer. This is the first part of code that actually wrote anything to flash.
.dw NEXT_STRING << 1
The first pointer you generate will be a null pointer because NEXT_STRING is 0. But then we set NEXT_STRING equal to T, so that when you call the macro the next time, the pointer will point to the place in flash where the last pointer is stored.
.set NEXT_STRING = T
At this point, I think you can see that a linked list is being formed. The first time you call defstring, a null pointer is stored in flash, which will some day be the end of the linked list. Then you call it again, and it makes a second pointer that points to the first. Then you call it again, and it makes a third pointer that points to the second.
Linked lists are only useful if there is some data in them, so the next thing the macro does is add the string data using the code below. Whoever wrote this decided that they wanted to always end the string with a null byte (which is standard for C-language strings) and they also decided to add an extra padding byte if the length of the string is odd, ensuring the space taken by a node in the linked list is always even. This is called 2-alignment and it might make it easier for the AVR to load the 2-byte pointer. I am not convinced that this alignment is necessary, but if it is, I would prefer to use the .align 2 directive at the beginning and/or end of the macro instead of doing this hack.
.if strlen(@0) & 1
.db @0, 0
.else
.db @0, 0, 0
.endif
Aside: This is not the only way to store a list of strings in an AVR. A more standard approach that you see in C programs would be to have all the strings in one place and then have an array of pointers in another place. The length of the array would either be a constant or the array could be terminated by a null pointer. Another option, used by REG_MULTI_SZ data in the Windows Registry, is to just store the strings one after another in memory, with no pointers, separated by null bytes, and ended by two null bytes. Each method gives you different space/performance tradeoffs and the last one cannot store an empty string.