Memory resources are often very limited in retrocomputers and, in such conditions, the size of an executable program is limited to the one of the central memory.
For example, this is the available contiguous memory 1) on various Commodore computers:
This can be a very strong limit, especially if you use languages like C.
To overcome this limitation, I suggest to use a technique that it was widespread in the 1980s and that was called overlay. Overlay is a programming method that provides programs to be larger than the main memory of the computer, and now it is a technique now very common in embedded systems, precisely because of the limitation of physical memory.
The overlay concept is simple: when a program is running, it usually does not use all the code at the same time but only a part of it. That part is necessary while the others are not. It follows that it is not necessary to load the whole program in the main memory.
We need the requested part in that instance and it will therefore be sufficient to load, during execution, the necessary part by replacing a previous one (and no longer necessary).
The construction of an “overlay” program needs the manual subdivision of a program into autonomous object code blocks called “modules”. The modules share the same memory area which is called the “overlap region” or target area (“overlap area”). An overlay manager loads the required overlay from external storage to its target area, when needed.
A program that uses this technique will therefore have to be divided into two parts:
The resident part will contain all the functions that are used most frequently, and which eventually (possibly) will also be recalled by the parts that will be loaded in turn. The developer then divides the rest of the program into modules, so that not all modules must reside in memory at the very same time, and these modules will be loaded (from time to time) into the destination area.
This technique therefore allows you to run a program much larger than the size of the physical memory, provided only the instructions and data that are needed at a given time in memory. This is the main and unique advantage.
The disadvantages of this technique are:
It is emphasized that it is the programmer's responsibility to deal with the overlay, because the operating system does not provide any kind of support. This means that the programmer must also explicitly write which part is required by each module. This responsibility is known, in jargon, as “overlay management”. The correct implementation of this management allows you to move through the various sections of the code.
The demonstration program has been wrote for the Commodore 64 hardware platform, and then the Commodore VIC 20 was chosen as the target hardware platform, which is characterized by a very low contiguous memory, and it has been equipped with a mass memory tool (1541 disk drive). The result has been tested on VICE Emulator under Microsoft Windows 10.
At level of algorithms the choice fell on CC65, a cross-compiling environment in C language for retrocomputer based on CPU 6502/6510 and which is equipped with a linker that manages the overlay.
I wrote a very simple demonstration program that shows part of the first two “canti” of “Inferno” of the Divine Comedy, in Italian and English. The program has been prepared without taking particular attention to optimizations, such as storing texts on an external file, and this in order to give greater evidence of the space occupied by the code itself.
The program consists of a series of functions that interact with the user. They are separated from each other, and orchestrated by the “main” function. Some of these, in turn, make use of other functions.
For organizational purposes only, the various functions have been distributed among different sources. It follows that, by compiling all the sources, you get a single executable that occupies about 5 Kb.
Although the executable is managed without problems by compiling for the Commodore 64, it goes beyond the availability of memory on the VIC 20. In other words, despite the fact that the compiler can generate a program on both hardware platforms using the very same source code, the VIC 20 (unexpanded) is not able to execute it.
By adopting the overlay technique, we can promote the “main.c” module as “resident module” of the process; the remaining modules will be alternated, therefore, in the destination area. In this way, the executable now occupies about 2 Kb and therefore also the VIC 20 (unexpanded) is able to load the first module. The resident module, taking advantage of the logic of the overlay manager, will take care of loading the rest of the program.
By using VICE Emulator, you can call it attaching the disk image for VIC 20, and loading the first program.
This is a snapshot of the execution of a 5 Kb program on an unexpanded Commodore VIC20:
The official repository for this project is here.