Relocatable Binaries

A General Discussion forum for TI calculators

Moderator: MaxCoderz Staff

Post Reply
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Relocatable Binaries

Post by benryves »

This is not a specific programming question, which is why I've posted it here rather than in the programming help forum.

I've been pondering the possibility of reloctable binary modules; less so for assemblers, more so for on-calculator relocation. The idea is that rather than directly copy an program to a fixed address, it can be loaded to any address and have internal values (such as call or jump offsets, data offers and so on) recalculated as it is loaded. Relocatable machine code could be useful for whole programs, dynamically-loaded libraries and so on.

The REL file format, as used by Microsoft's 8080/Z80 compiler and linker suite (M80 and L80), would seem like a good example of what I mean, as the files used were designed to be small (using a bitstream to save space) and the tools to handle them ran on an 8080 or Z80 CPU.

Picking a standard format would seem like a sensible approach to take. We would need to establish which features would be required, for example:
  • At least two places to output data to - program code (which must live below $C000) and data code (which can exist anywhere in RAM).
  • Resolution of external labels, for values that cannot be determined at compile-time (eg "plotsscreen" having different addresses on the TI-82, TI-83 and TI-83+).
  • Exporting of labels, such as entry points and variable addresses (more useful for libraries than programs).
I'm primarily thinking of library support for BBC BASIC, though such a format could be useful for assembly shells or maybe even Vera.

Any thoughts?
User avatar
Timendus
Calc King
Posts: 1729
Joined: Sun 23 Jan, 2005 12:37 am
Location: Netherlands
Contact:

Re: Relocatable Binaries

Post by Timendus »

Sounds interesting enough, how do you have such a thing in mind?

I don't get your first example though..?
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: Relocatable Binaries

Post by King Harold »

for "Resolution of external labels, for values that cannot be determined at compile-time"
I used (not on z80 though but it should be equally possible) a list of pointers to where the value should be changed. It worked, but I wasn't happy about the way it went (kinda feels like a very dirty hack to me)

so.. just ignore that idea :)
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Re: Relocatable Binaries

Post by benryves »

Timendus wrote:Sounds interesting enough, how do you have such a thing in mind?
I don't have any particular implementation in mind - hence this thread to see if anyone has any suggestions. :-)
I don't get your first example though..?
If this is the program code vs data code example, imagine a program that has data stored in RAM (lets say a level in a game that can be modified). You could relocate the entire program to a single new base address, but it may be more efficient to only relocate the program code to below $C000 and store the data (like the level) above $C000, to make as much use as possible of the relatively small amount of RAM that you can execute code in (ie, without falling foul of RAM page 0 protection).
User avatar
Timendus
Calc King
Posts: 1729
Joined: Sun 23 Jan, 2005 12:37 am
Location: Netherlands
Contact:

Re: Relocatable Binaries

Post by Timendus »

Ah, I think I did get your example then, but I don't really see that as a problem. Most applications don't carry much data, so the percentage of executable RAM lost versus the amount of trouble to separate the two... I don't really think it's worth it :)

I think the most obvious thing to do would be to rig an assembler to make all calls relative to program start (.org 0) and output a table of pointers to places where labels are used (only not relative jumps, obviously) at the beginning of the binary. So all you have to do to run the binary is add <binary location> to all the addresses listed in the relocation table and give it a spin.

But it sounds to me like you want to do more than just be able to relocate binaries. You also want to be able to share binaries between calculator versions and figure out a way to use them as libraries that you can jump into at any label. Now this, I think, is where it's getting interesting. Because if we can devise a way to make this kind of abstraction we can run one executable (i.e. a popular game) on all hardware, OS versions, and even Vera. That would make life easier on the user, and focus our efforts by providing a uniform platform (read: more applications that run on <specific hardware/OS>, because ALL those applications run on ALL of them). And libraries are something that, as you know, have been haunting the Vera project since the beginning; we all know we need them, but nobody knows how we should make 'em work :)

The solution that comes to mind is adding more tables, one pointing at all locations where an OS call or saferam is used (and we can use the value at that location as an identifier for the call/location we'd like to use, look that ID up in a map and replace it with the proper address) and another table with relative entry points (although the question rises what the value of those entry points is if we don't also come up with a uniform way of accessing the routines -- if we follow that train of thoughts we get back to what CoBB calls "abstraction hell" ;)).

I'd like to hear your thoughts on this!
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Re: Relocatable Binaries

Post by benryves »

The table method is the most obvious and easiest, but has some shortcomings (what if a particular piece of code needed to be aligned to a particular boundary)?

I'm more concerned with dynamic libraries (as in, reusable binaries that can be loaded at runtime by another program) than OS/hardware-agnostic binaries (though the latter would be nice if it could be made work, we'd probably also need to define a standard library that all implementations would offer). On top of the relocation table we'd also need to find a way of exporting function and variable names (which could just be another table) as well as importing function and variable names (which could, again, be another table). Of course, more complex relocation and initialisation could be performed by the relocated library itself by adding some DllMain-alike exported function that could be called immediately after relocation and immediately before unloading.

Apologies for rambling. ;)
User avatar
Timendus
Calc King
Posts: 1729
Joined: Sun 23 Jan, 2005 12:37 am
Location: Netherlands
Contact:

Re: Relocatable Binaries

Post by Timendus »

On top of the relocation table we'd also need to find a way of exporting function and variable names (which could just be another table) as well as importing function and variable names (which could, again, be another table).
One ugly solition could be something like this:

mathlib.inc:

Code: Select all

libid = 25
devide = 1
multiply = 2
mathlib.asm:

Code: Select all

.include mathlib.inc

; table
.db libid
.db devide
.dw devide_func
.db multiply
.dw multiply_func

; routines
devide_func:
   ret

multiply_func:
   ret
application.asm:

Code: Select all

.include mathlib.inc
.define libcall(X) call do_lib_call \ .db libid \ .db X

ld hl,5
ld de,10
libcall(multiply)
...
Where "do_lib_call" is a routine the OS / shell implements that searches for a library with this library/routine ID combination in it's table..?
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Re: Relocatable Binaries

Post by benryves »

Ah, that's the problem there - you need compile-time information mapping ordinals to addresses. I'm thinking of embedding exported names as strings within the binary. Maybe like this:

Code: Select all

.dw Exports

Function1:
    ; ...
    ret
Function2:
    ; ...
    ret

Exports:
.db "FUNCTION1",0 \ .dw Function1
.db "FUNCTION2",0 \ .dw Function2
Then, to use them:

Code: Select all

; Program start-up:
    ld hl,LibraryName
    call LoadLibrary
    ld (LibraryHandle),hl

    ld hl,Function1Name
    ld de,(LibraryHandle)
    call GetExportedAddress
    ld (Function1),hl

; Calling the function:
    call Function1

LibraryHandle:
.dw 0

; Jump-table in RAM (so can be edited).
Function1 = $+1
    jp 0

LibraryName:
.db "SOMELIB",0

Function1Name:
.db "FUNCTION1",0

You could then look up an exported function or variable address via its (textual) name. Naturally, this makes the binaries larger, but also makes them easier to work with!
User avatar
driesguldolf
Extreme Poster
Posts: 395
Joined: Thu 17 May, 2007 4:49 pm
Location: $4080
Contact:

Re: Relocatable Binaries

Post by driesguldolf »

Very interesting indeed :D

However the program startup looks like one big mess now... Perhaps automate this?

Code: Select all

; Program initialization
   ld bc, LibraryName
   ld de, BufferToJumpTable
   ld hl, LibInitData
   call InitializeLibrary
   ; ...

LibInitData:
.db "Function1",0
.db "Function2",0
This would cause the jumptable to be filled in with correct pointers.
benryves wrote:(what if a particular piece of code needed to be aligned to a particular boundary)
You could tag the exports

As for data stored in programs (which I feel is just a bad habit in ti83+ asm programming): Why not do it the way apps do it? If you don't have saferam you can always use RAM right after the program (and tell the os how many bytes are needed). This way, programs don't need to include dummy bytes. One of the reasons this was done was to reduce the number of 'files' on a calc, but with half a decent file system this shouldn't be a problem.

Vera fs related:
To reduce creating a new file over and over (to overwrite game data), overwrite the previous data with 0s and paste the new data after it (as long as it fits in a single block).
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Re: Relocatable Binaries

Post by benryves »

driesguldolf wrote:Very interesting indeed :D

However the program startup looks like one big mess now... Perhaps automate this?
Good idea, that could work well. :)
As for data stored in programs (which I feel is just a bad habit in ti83+ asm programming): Why not do it the way apps do it? If you don't have saferam you can always use RAM right after the program (and tell the os how many bytes are needed).
That could work, too. Of course, we could have all sorts of fun features (eg compressed libraries) on top of this design too. :)
User avatar
Timendus
Calc King
Posts: 1729
Joined: Sun 23 Jan, 2005 12:37 am
Location: Netherlands
Contact:

Re: Relocatable Binaries

Post by Timendus »

I guess what we need to define is a library header. A few things that it should contain:
  • Preference for alignment in memory
  • Labels that need to get updates according to location
  • Exported labels
  • Imported labels
  • Leave room for things like compression
I guess we should draft a spec and give it a try :)
http://clap.timendus.com/ - The Calculator Link Alternative Protocol
http://api.timendus.com/ - Make your life easier, leave the coding to the API
http://vera.timendus.com/ - The calc lover's OS
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Re: Relocatable Binaries

Post by benryves »

A standard binary header is indeed what I was aiming at. I'm going to try and focus on getting a simple BBC BASIC together first (I've run out of ROM space for more exotic features!) then turn my attention to a spec for this. If all I've done is planted the seed of an idea in your mind, that's a good start. :)
Post Reply