Thank you so much for that link Lionel! The ProgFormatV6.txt is fantastic; I believe I may keep most of those ideas. I will attempt a compressed relocation table, but I may start out with an uncompressed one to start out with in order to keep my sanity first.

Yeah, you should definitely start simpler with the uncompressed relocation table

The standard code to produce programs in "kernel" format is in the custom, environment-specific GCC4TI linker, which supports COFF and AmigaOS object formats:
https://github.com/debrouxl/gcc4ti/tree/next/trunk/tigcc/ld-tigcc
I'm not _sure_ it produces v6 binaries, though. Historically, the TIGCC toolchain, headers and library have been an integral part of limiting the number of programmers which used non-native "kernel"-based mode. GCC4TI hardly improved on that area of the TIGCC legacy, we focused on other areas of likely greater importance and relevance.

Sorry that I am making such a question now but will (Edit: Not will but is it possible?) there be a port to the TI-83+?

There's already been some work on C toolchains + headers targeting the TI-Z80 platforms, based on e.g. SDCC (some topics on this board). However, the Z80 is a poor target for C code, and the few C compilers which target the Z80 produce code which makes even moderately experienced assembly programmers laugh (or cry).
The eZ80 is better suited to C programming, though less so than e.g. the newer 68000 which has more, wider registers and more powerful effective address modes.

As for other aspects of Mateo's current work: the TI-Z80 series has a paged, and smaller, addressing space, unlike the TI-eZ80 series. Therefore, a number of technical solutions coming from the TI--68k series, which uses a flat addressing space as well, don't work in any kind of sane way, or at least, are much harder to achieve.

I more mean the ability to run ASM programs from Archive the way Doors CSE does: at least copying to RAM before executing, and at best being able to do things like writeback.

Okay, here are some really quick questions before I go any further:

1. Do we want libraries like ANSI C, or like Prizm C?

2. How should handling of printf and graphics work with different bpp modes? Should there be a standard of 8bpp or something? Like how would one color the screen a different color when in different bpp modes?

Honestly, the only reason I see for relocation on the ez80 series is just so we can chain libraries together and have multiple libraries. There is really no other point, as in assembly programming, relocation isn't done... Just pointing that out too. Thoughts?

The routines built into the OS / boot code should be leveraged as much as possible, assuming their API deviations from the standard aren't too onerous (AMS has several, which don't necessarily mattera a lot...).
For the useful routines not provided by the OS, perhaps the way to go for minimizing development time, at least in the beginning, is to start from the battle-tested, lightweight and liberally licensed implementations of the C library (newlib, musl, etc.), and hope the C compiler does a decent optimization job on them ?
Reinventing one's routines for the libc definitely is an interesting learning exercise, but algorithmic or implementation bugs are ugly. For instance, unlike TIGCC's, GCC4TI's bsearch actually works, and GCC4TI's qsort, besides being rewritten in assembly for smaller size (~20 bytes over ~150, IIRC) and higher performance, uses an algorithmically faster implementation of the shell sort algorithm (better sequence).


On GCC4TI, printf leverages built-in ROM_CALLs: it calls vcbprintf (accessible through sprintf with a hack) with the address of fputchar, which uses FontGetSys + ScrRect + SaveScrState + FontCharWidth + ScrRectScroll + DrawChar + MoveTo.

I guess that you'll have to implement some of the functionality built into AMS by yourself because the TI-eZ80 series' OS happens not to provide it, but unless the character drawing code in the OS / boot code is agonizingly slow, you should at least try to leverage it. Doing so will define the number of bpp in the beginning, but as you control the implementation of printf, you can always (theoretically...) add support for other modes later.
On the TI-68k/AMS platform, few people use printf, because ScrRectScroll and DrawChar _are_ silly and slow, like most of AMS' graphics routines anyway.

Okay; so here is a couple more things that I just wanted to list out. Changing bpp modes modifies the content that is displayed on screen. Thus, it makes sense that the lowest bpp mode should be 8bpp, and 16bpp. This is because clipping and drawing is much faster and reasonable in 8bpp than 1bpp. Thus, if someone really wants to write one, go for it. But the graphics library that I am creating will be using 8bpp mode for the standard, and options to switch to 16bpp if necessary, such as picture display or something to do with the OS. 8bpp honestly makes everything behave quite nicely, and I already have an image compressor for 8bpp images so you can include them in C projects.

Unfortunately, I am unable to figure out how to build a relocation table in ZDS. This means that relocation probably isn't very sane. But I would like to hear some thoughts and ideas; and if you have any suggestions, please place them here.

EDIT: One way I could see doing things is making each library have an allocatable chunk of saferam where it will store library entry point vectors, and have a manually created relocation table. But this sounds awful.

EDIT2: Perhaps one shared library, and then others such as USB that would be static? I mean, that stuff might not be used as often... So it would make sense to just be there...

Yeah, manually created relocation tables / manually relocating the program is unusable in anything but early development. For a while, Ndless-based programs used manual program relocation, but that's way too inconvenient, and hampers development effort.

The ZDS eZ80Acclaim! User Manual mentions relocations, but only under object file form, indeed. The linker clearly attempts to resolve said relocations into absolute addresses
That manual contains references to OMF695 object format as assembler output (.obj, https://en.wikipedia.org/wiki/Relocatable_Object_Module_Format ?) and IEEE 695 executable format as linker output (.lod).

In the former, relocation information is held by FIXUPP records, which apply to LEDATA (binary) records. FIXUPP records can only handle LEDATA records up to 1 KB, so data must be split by programs which produce OMF.

More investigation is needed on the IEEE 695 format, which is supported by binutils. It provides debugging information.

Using non-relocatable binaries on the calculator side means letting go of future-proofness, which would be very meh.

Writing one's own linker for handling OMF as input and whatever as output, or at least, leveraging an existing FLOSS linker which would by chance support OMF is another (bad) option.
Writing a full-custom linker is the approach used by the ancestor of GCC4TI, because binutils didn't support AmigaOS object files, BFD isn't much fun to work with, and supporting some features provided by older TI-68k toolchain incarnations required patching the linker anyway, in ways which probably wouldn't have been accepted by upstream. Section reordering, constant merging, and other features are interesting - but platform-specific.

From an ASM standpoint, relocation is fairly trivial to do: calls and jumps are replaced by a mechanism that adds an offset stored at a fixed memory location to the call/jump target, and pointers must be loaded through a similar mechanism. From a C standpoint, I'd imagine that it's trickier, although certainly some postprocessing that handles pointer loads, calls, and jumps is doable. Based on Lionel's information, it sounds like doing the latter in a way that's sane and non-terrible is tricky.

Well, the relocation part is easy. That's not really the problem. It's that there are no tools or options, as in most compilers, to create a dynamic symbol table of some sort. Which means that post-processing isn't an option. And manually adding in the table wouldn't be a viable option.


Well, I believe this is the assumption for all ez80 ASM programs.

After a bit of a debate in the IRC channel, I've decided to post this.
----
From what I understand, Mateo wants to create something so he can call library functions from a C program regardless of where the library is or is located in RAM. Given that requirement, I understand the following:

1. The C program does not know exactly where the library functions are at run-time.
2. The library does not know exactly where it is at run-time.

The following conditions apply:
a. The library must exist someplace, either in Flash or in RAM, but must ultimately be in RAM when it is run.
b. The C program that is running is a destructible copy.
c. The C program must be coded in ZDS. The library can be coded using whatever so long as it spits out the needed things to get the C program to compile and run correctly.

Note: To make a long story short, most of the heavy lifting is done in SPASM-ng since I can't figure out how to leverage ZDS to do the stuff, and tbh, the documentation on ZDS is rather poor. I mean, documentation for SPASM is scarce, but there's just too much stuff in ZDS, without really telling you much. Is an index or a quick reference too much to ask for?

To solve (1), I figured that the C compiler has to link to something, so I would generate a sort of jump table, with each jump being labeled.

Code:

The function labels being the things that are being called and funcID being the number of the function being referenced.

The ASM program component that is linked to the C program contains half of an initializer which finds, puts it in RAM if necessary, then runs it from the start. We still haven't solved (1) yet but now we're running the library which finishes the work. The start of the "jump table" (which is known) is passed via register to the library.

In this way, (2) also gets solved since the jump is a jp (hl), so HL will contain the start of the library's location. The library now then begins by iterating through the "jump" table, using the funcID's to locate the actual offset from a table internal to the library, add it with start of the library, then write that back into what will be an actual jump table. Huzzah. C program now has entry points.

Now, we've got to update references in the library itself. Since I'm using SPASM-ng, I can use macros to generate a table when you stick another macro prior to instructions you want to change.

Code:


The relocation routine will change all addresses pointed to by the relocation table to reflect current location.

Now, this is important. The library itself is assumed to NOT be a copy and is the original, so all the relocated labels has to be undone at some point. This isn't feasible since nobody is going do anything with the library aside from initialization and normal use. No putaway code. So what we do is store what the library's last location was someplace in the library so when the library is used again, it can be used to undo all the changes, then add the new location. We don't need to check for first run since the "last location" in that instance is 0.

All in all, this is what I'm thinking of:

Code:

-----

Not thoroughly proofread. Discuss this while I read up on this ELF format thinger that I got linked to.

EDIT: I rewrote the offset thing to do ID's. Some of the verbiage hints at this. Oops.

Here is what I have as a setup, in case anyone is interested:

C program:

Code:


CELib.h

Code:


And the CElib.asm library begining:

Code:

This approach is big and awkward. A smaller, faster option is to use a special call for calls, jumps, and pointer loading. Consider calls that look like this:
Code:


This special call at SomeSafeRAMRoutine should do the following:
1) Know the actual start of the routine in RAM
2) Use the stack to read TargetOffsetLabel
3) Adjust the return address to skip three more bytes
4) Restore registers and jump to the recomputed location.

Jumps work exactly the same way, save one additional stack manipulation, and loading pointers is very similar as well.

Does ZDS not support __asm__(...)?

Does ZDS not support __asm__(...)?[/quote]

No. It supports function-enclosed asm() and pragmas. In C files, not assembly files. To chain multie lines, you still need a delimiter. Silly, I know. Also, my above code is just how I am testing things. Just wanted to get a jump on actaully writting functions. I have quite a few in the other topic.

You might have mistaken that for a table that the library uses for internal purposes. This table is used in the C program to provide something static to link to.

The ZDS documentation makes it very clear what a function call is (ZDS II ez80Acclaim User Manual, page 244+). It is literally a bunch of pushes, a call, and a bunch of pops, where arguments are shoved onto the stack. The location of said call in the code is not knowable (and usable) at compile-time, nor is there any way to attach data to it in any manner apart from passing arguments.

Believe me, I wished there was a way to alter what ZDS does when it encounters a function call in the C code, but I haven't figured out a way to do that, if it's even possible. The jump table method seems to be the most sane to me at the moment because that's generated with the library build process (SPASM-ng) and then compiled with the C program (ZDS) later on.
--

Let me tell you a little about how ELFs work since there has been some wheel reinventing going on. I'll go from memory with a simple example if relocation was implemented.

SCENE

Code:

Code:

Code:

Code:

Code:


Well, I had fun. Now, I'm not going to go into the details, I'm saying what it looks like from a coder's perspective. Tools can be made to generate shared libraries, code can be made to dynamically link objects. I already wrapped my head around it when working on the Prizm.

Firstly, lets assume take the code above and build ELFs, 2 shared libraries for our stars and 1 runnable binary for the car. The fun happens when you poke into how the ELF was made.

Marty!
libmarty.so has quite a few symbols exported, but among them are marty_name and marty_invoke. Now, the library object is made up of different sections. The dynamic symbol section contains all symbols that can be used externally with metadata about them. They contain the symbol value, size, type, binding, visibility, and a few other things. Now, this is specific to the ELF format and can be changed for other implementations, I'm just saying what is being used today.

Ok, so, you have a dynamic symbol table looking something like:
Code:


Hey, marty_invoke and marty_name are there! They are symbol #9 and 11! Great! First thing, look at the values. marty_name is an 8 byte pointer. The value is the virtual address (can be modified). That address points to the .data section, and at that location is the value 0x750. 0x750 is mapped directly in virtual memory and in the ELF, and guess what's at 0x750? "Marty McFly\0"

Now, hold on, Marty. I can take an entry, find out where that symbol's value is, and a few other things. How... do I find which symbol is what? There's another section for that! Meet the dynamic string section! It contains all symbol names as zero-terminated strings. Want to look up a symbol's index in the dynsym section? Start searching for the string in the dynstr section. (Now, there are extensions to this, but aren't needed. There are optional hash tables that can speed up symbol lookup times)

I can now take, say, "marty_name" and through some logic find the string is at 0x750. Great Scott!

But Doc...
libdoc.so isn't anything special, it comes down to being the same with different names and values. Nothing interesting there.

Where we're going, we don't need roads.
Now for the fun part, the DeLorean! It isn't much fun if it can't find Doc and Marty, right?

Now, remember, delorean is still an ELF, but it has an entry point (Yes, libraries can be ran, too. Try running libc.so.6) unlike the above 2. The ELF still has dynsym and dynstr sections (Doh, since I used the same headers in delorean without doing anything special about visibility, this ELF has marty_* and doc_* symbols exported. No worries), but there are sections that are worth looking at now.

Relocation!
There's a relocation section (.rela.*) that is important to letting the DeLorean know about Marty and Doc. There are 2 subsections, one for functions (.rela.plt) and one for symbols (.rela.dyn) (There is one for compile-time relocation, ignoring as these aren't in the final ELF). Let's take a peek into these sections:
Code:


Hey, that looks right. From the headers, you can see that these tables show the offset (But for what, might you ask?), info (a bit cryptic), the type of relocation operation to perform, symbol value (wait, why again?), and the name and addend. Now, wait, these aren't actually what is stored. Think about it, you already have some of this information stored (in terms of the ELF, you can move this into these sections if you want). The ELF has a symbol table with symbol names, value, etc.. This section just has the offset (into the program's virtual memory), relocation type, and symbol offset (in the table), sorry!

So, ok, our program has relocation tables, ok. So, how are they used? Well, this is where ELF gets more complicated as it thinks bigger, but this is what has been tossed around.

GOT and PLT
The Global Offset Table, or GOT/.got, is a reserved chunk of memory that is allocated at runtime for the process. This table stores the addresses to use for symbols. There is a second section called the GOT Procedure Lookup Table, or GOT PLT/.got.plt (also allocated and stored in RAM). Now, in this process, there is another special section named the PLT (not related to the GOT now, this is different. This is in the program, not copied). The PLT section holds a number of "trampolines" (different from GCC trampolines). You'll see why they are called trampolines further down.

Ok, that's a lot to drop on you. 2 GOT tables and a PLT. Wat.

How should I start... Let's look at how the program runs as-is, ok?
Code:


Whoa, whoa, hold on, what am I looking at? This is in fact x64 assembly. Don't be scared, you don't need to know it to understand what's going on so long that you understand assembly in general.

Ok, reading this... some registers are being moved... Oh look, comments! And symbols! 0x4008fa, this is where magic happens. There's an offset to %rip (Note, this is an x64 feature to make PIC code easier, x86 has slightly different magic), objdump kindly told me it is 0x601048, or __TMC_END__. Yes..., but that just picked the first equate for that address. Looking at the symbols, marty_name is there. Hey, that's cool! From the symbol table:
Code:


Ok, but uh, that's not part of our program. And this address, where is it? readelf tells me it is in the .bss section (or uninitialized global data). Huh, why is marty_name in this section? I thought the GOT has the addresses, what gives? The answer is in the .rela.dyn section from before. Look at the offset for marty_name. 0x601048. This particular relocation type says to copy the actual symbol's value to that offset, in the .bss section. Cool, that's how that library symbol was relocated (I'll elaborate on how this happens once I talk about how it happens with functions). But, what about function calls?

Looking at 0x400904, 0x4009e0 is stored to the %edi register. Most likely this is the string "Hey, %s, what's new?\n" (which makes sense, below the same reference is used for printf). Now, this call to 0x4007b0. Hey, it says printf@plt, that looks like magic! It says that's in the PLT, so, what does the PLT look like?
Code:


Hmm, so it calls the printf@plt trampoline (but why call it a trampoline?!), which jumps to address specified in the GOT PLT (Different area than the GOT). Hey, that sounds exactly like what the GOT PLT is for, right? Storing the address of relocated functions? Yes! Well, erm, not quite yet. .got.plt + 0x18 (address 0x601018, important) contains 0x4007b6. Welp, that's shot me back into the PLT. Bounced into the GOT PLT, now bouncing to the dynamic linker, kinda trampoline-like .

Under the hood
Ok, now what's this _init+0x28? Ding ding ding, that makes a call into the dynamic linker (well, through the GOT PLT, but it gets there)! Yup, ELF uses lazy loading for functions because these lookups can get quite long (Exceptions apply depending on situation). If you have a large project with tons of deeply nested symbols in other libraries, looking up every symbol at startup would be noticeable. (And again, you don't have to do this, but look at how easy lazy loading is. If the dynamic linker has to get much more complex to do single shot resolution, you might do away with lazy loading, its up to the implementer of the dynamic linker).

Now, this linker code, what is it doing? Well, see that pushq $0x0? That's the index into the .rela.plt table for the function it wants to invoke. And that row in the .rela.plt table has the address 0x601018, which is the printf entry in the GOT PLT. When the linker resolved, it replaces that placeholder entry in the GOT PLT with the resolved address for the function. Now, the trampoline bounces directly into the intended function. Amazing!

But... but...
Remember the *_name variables? On startup, the dynamic linker runs for all non-lazy relocations all at once. Nothing fancy here besides what was already said.

Ok, the linker is told to find these symbols. There is yet another section in the ELF that lists the names of the shared libraries and their relation (are they required or not). Some other metadata is stored, like the rpath (where to search for these), but that's not required afaik. (For calcs, you'd need a list of appvar names. Not the name of the library, you want these to be easily shared and interchangable. Makes searching the VAT easier afaik, else you'd need to read everything and find their name.

Relocation, location, what's your version?
Now, version differences was brought up on IRC. How do I know the function I am calling in the library will work right? What if the version changed? "We're all adults", this is less of a problem that ELF would handle, more-so a problem with the developers of the library and them changing the API to existing functions. In short, define your API. Specify a solid declaration. Define how the inputs are handled and what the outputs are. If you break API compatibility, release a differently named library so the dynamic linker will not pick it. Just like how requiring libusb-0.1.so will only pick that specific name, not libusb-1.0.so which has a different API.

(Yes, ELF has a section for versioning of libraries, it is mostly used for libc.so*, but mostly seend by different library names. If you have a newer version of the library, you'd see a symbolic link made to the specific version. For a calc, maybe an API version should be put in the ELF objects. Only increment when the existing API changes, not when existing functions are changed but have the same functionality or the API is expanded.)

(Just an idea, you could add versions to functions, but I'd see that as less optimal in terms of planning your API)

Great Scott! We made it!
Well, I drove this example at 88mph and didn't explode, which is great. This example is limited, so not all relocation types were shown. Also, I used x64 so I cheated a bit with %rip. How is it normally done for architectures that don't cheat? The code dedicates an index register to hold the address of the GOT. The program code indexes from this register to get any needed addresses. Someone fill me in, it looks like the PLT is only really needed for x64 platforms because of a limitation on the instructions. Are the PLT trampolines needed because you can't invoke a function at an address specified on and offset of an index register? Sounds like way too much for 1 instruction. In that case, the GOT PLT alone would suffice?

But wait, why happened to lonely GOT? Our name variables were put into .bss! GOT is for PIC code in your current binary (Oh god, this gets even more complex, turn off your brain for now). Lets say you have this code:
Code:


This is a masterpiece. Besides code quality, if you want PIC enforced in your code, fine, you can't have an absolute address built-in to your code. BUT WAIT, where's x? You don't where! And you don't care because the dynamic linker relocated the data section the variable was in and stored the address in the GOT! You now just use your GOT-set index register to get the value of x, increment it, and write it back.

Aaaand here's the bad part. You have a library that uses the GOT. You have a program that uses the GOT. You have a conflict, oh joy. You need to have multiple GOTs/GOT PLTs for each shared object. This is the part I like the least. How this is done, information is scarce. And it depends on the architecture. Please, someone fill me in on this!

And now, the larch
I think that just about covers how relocation and PIC works in ELF objects enough for those who haven't slaved over the technical details, ELF dumps, and disassemblies to have an idea of what goes on. I had loads of fun reading this as I already had plans of writing the dynamic linker for the Prizm for fun.

So, I don't do dev for TIOS, and my z80 knowledge didn't carry into the ez80. The above highlights how things work today for ELF binaries, a lot can carry into assembly programs on ez80 calcs with some design changes. (Here I go talking about an OS I don't know about for an architecture that I don't know its limits):

• Assembly programs are copied to a place in RAM, great. What was it, a duplicate VAT entry is made of the same size and the program is copied there? If so, find somewhere to allocate the GOT and GOT PLT (ELF-wise, they are stored right after each other).
  
• The real end-goal is to make a shell/kernel for the calcs with the dynamic linker contained. It should be able to take a relocation entry w/symbol entry (for name), search the VAT for the appvar or asm program (or w/e you want), optionally check the API versions match, then...? Find a way to make it accessible. Functions are easy, you can handle the calls (proxy the call to the flash, changing pages if needed). I don't know about the ez80, if you can map pages into memory so that all code is accessible, great, everything is there. Otherwise, that makes the following difficult:
  
• Figure out what to do with relocating objects (non-functions). Pointers can get nasty if you can't map them into memory (either copying or mapping pages.)
  
• A way of outputting in a different format is needed. ZDS/etc. output in a flat format that doesn't support unresolved symbols in the final output AFAIK. A linker'd be needed to build a program in the right format with all needed sections/metadata.
  
• ABI needs to change to allow these features. Getting the ZDS C compiler to bend appropriately might not be possible. Note, that's really needed for PIC generation, so libraries would have issues. Regular C programs could use PIC'd asm libraries, you'd just need to link accordingly and use a dynamic linker.

Cites Worked

1. https://www.cs.stevens.edu/~jschauma/631/elf.html - Nice technical details on the ELF sections
   
2. http://bottomupcs.sourceforge.net/csbu/x3824.htm (and the next page) - Simpler approach that walks through the discovery process
   
3. https://docs.oracle.com/cd/E23824_01/html/819-0690/chapter6-46512.html#scrolltoc - Bunch of pages that detailed a bit more about the ELF format
   
4. http://linux.die.net/man/5/elf - Structures, defines, not that much help on the low-level aspects
   
5. http://sco.com/developers/gabi/latest/contents.html - The System V ABI Draft (2013), describes ELF object files, loading, and dynamic linking.

tl;dr, Tiny elves inside your computer write magical symbols that assemble themselves into a completed puzzle.
Total character count: 20,807

Thank you very much AHelper for writing that up! The ideas are definitely applicable, but the ELF format isn't reasonable on the ez80 series:


Also, can someone please explain to me what we are trying to future-proof against here? I'm really quite confused on that front. For instance, if TI changes the location of RAM equates, nothing would work anymore anyway for that OS version. Also, if some OS calls were moved or vanished, that would also cause big irregualties. TI made Apps relocatable because they are loaded into the archive, and thus cannot be guaranteed to run from the correct location. However, programs are always assumed to be. The OS is pretty stable as-is. I just need to know why future-proofing is so crucial. What is the purpose behind dynamically linked shared libraries? What is wrong with shared static on-calc libraries? Just wondering. Thanks!

Don't mistaken that for me telling you to use the ELF format, I was literally just describing how ELFs in general work. As such:
The point is to show how one existing technology works in order to help brainstorm how to specialize it for any ez80-based calc.

That isn't not a conflicting description for libraries.