AdVANCEd C PROGRAMMiNG ON THE
ATARi 8-BiT, PART 2
MARk MillER, AC CONTRibUTiNG AUTHOR
AC thanks the Front Range Atari User's Group in Fort Collins, CO for permission to use this article.
[In Part 1 of this article (AC, Feb. 1993), Mr. Miller briefly surveyed the various C compilers available for the Classic Ataris and outlined the advantages of CC8. This time he wraps up his discourse on CC8 by presenting some of its limitations and giving us some programming examples.]
Limitations of CC8
Here's my "gripe list" of things in standard C that aren't supported or are limited in CC8:
- The float or double data types, but limited floating point is allowed if Ace C libraries are used. (The float data type should be familiar to experienced programmers, but it has other names in other languages. In Atari BASIC, all numeric variables are floating point variables that can hold real number values. This is what the float type is also. The double type is a doubleprecision type. You can use floating point numbers if you use the Ace C libraries, but variables used to input your real numbers can't be of type float. The Ace C documents discuss necessary conditions for using floating point values.)
- No bit fields.
- Local variables can't be initialized, as in: char q[10]="hello"; (inside of a function or compound statement).
- Structs and unions, and their fields, are part of the global name-space.
- Variables can be declared more than once at the same scope level (Ex.: If int a; int a; were declarations at the global level, CC8 will declare 'a' twice, which will confuse the linker.).
- Maximum array bound is 6 dimensions (7 dimensions for char and int types). This is still pretty large though.
- Unsigned, long, short, etc. variables can't be declared
- You can't rename a type using typedef.
Runtime C Files: Faster Than Assembly?
Using the Ace C linker, it's possible to create an independent executable file that doesn't require any other file. The way you do this is to link the runtime engine with the rest of the program. This linker also allows you to incorporate assembly code in your C programs. You can either link in absolute (non-relocatable) object files, or put the assembly language right in your C source code. According to both the CC8 and Ace C documentation, the way you insert assembly into the C source code depends entirely upon the linker you use. Ace C's linker does have a certain '#asm' protocol that's described in the Ace C docs.
Unfortunately, even though your program is compiled into machine language, this doesn't mean you'll get assembly language performance from it. It's been my experience that C programs compiled on an Atari 8-bit are noticeably faster than the equivalent program in BASIC, but there's just no comparison in speed between assembly language and C. Assembly language wins the contest every time. I believe this is because of a general fact of compiled languages. Any time you have to compile a program, the compiled code will generally be less efficient than if the same program were written directly in assembly language by a person. This fact is becoming less true with advances in algorithms for compilers. Most compilers for 16- and 32-bit systems come with optimizers that make the object code nearly as efficient as though the program were written in assembly. Ace C comes with an optimizer, but it mainly helps in making the final object code smaller. In my experience, the Ace C's optimizer doesn't notably enhance execution speed.
DOS Compatability
If you plan to use CC8, there are some configuration matters you should consider. You don't have to configure the software in any way (like set any settings). What I'm talking about is what DOS you want to run it under and where to put which files. I have a 130XE with an unmodified 1050 drive. I use MyDOS 4.5 and a RAMdisk. The reason I use MyDOS is I like the ability to use subdirectories to organize my files- and there are a lot of files! It turns out MyDOS also comes with a utility that copies whatever files you have in a directory called RAMDISK into the RAMdisk upon bootup. I have it copy the text editor (I use TextPro), compiler, and linker into RAMdisk. This makes loading these large programs very fast. If your machine has extended RAM capacity, you should seriously consider doing it this way. (See Mike Jewison's "Fitting Room "column and Jeff McWilliams "Moonlight Workshop" column elsewhere in this issue for more info on extended RAM. -Ed.)
Frustrations and Dreams
There are three functions I use heavily when I write C programs with the compilers I use on the minicomputers at school, and which aren't included in the Ace C libraries: scanf(), malloc(), and free(). I've found a substitute for scanf() by using other input functions in the libraries. However, what makes a language like C really powerful is the ability to allocate blocks of memory dynamically, so data structures like stacks and binary trees can be created. I've dreamed of running on my 8-bit the same powerful C programs I run on the minicomputers, without making adaptations to the source code. In order to accomplish my 8-bit programming ambitions in C, I need the malloc() and free() functions. I've found that I'm not able to just copy a C program over from a minicomputer to my 8-bit and compile it. I always have to make some changes to the source code to make it work on different compilers.
When I refer to C's ability to allocate blocks of memory dynamically, what I mean is a different way of storing data than the way most programming languages on the 8bit do. In Atari BASIC, for example, when you want to use an array, you have to DIMension it first. From then on, you're limited to a certain size constraint, and you can only have one data type in it: characters for a string array, or numbers for a numeric array. A typical thing I do is define a struct (remember, a struct is a collection of variables that can be of different data types), and then call the malloc() function to allocate space for the struct somewhere in memory. Memory that's dynamically allocated isn't necessarily sequential (even though that's how it usually turns out on personal computers). A block of memory somewhere is found to be open, and a pointer (address) to that block is returned, so data can be put in that block (values for the fields of the struct, for example) through indirection.
Linked-List Via Dynamic Allocation
Let's use a simple data structure as an example: a linked-list. This data structure is formed by dynamically allocating blocks of memory for structs one by one. Each struct contains a pointer to the struct type containing it. For this example I'll call this pointer field "next". The construction of a linked list goes thus: Declare a structure type, I'll name it "node", a couple of local pointers, head, and a temporary pointer, I'll call it p, of type "pointer to struct node." The pointers "head" and "p" are declared outside the struct. Don't confuse these with being fields in struct node. A pointer called "head" (or some other name) is usually declared so it can be used as a beginning reference point for the list. The pointer "p" is used to create the linked-list by gradually travelling down the list, and being used as a reference point for more blocks to be added to the list. To start the construction of the list, you allocate a block of memory the size of struct node using malloc(). Malloc() will return an address to a free space it has found. Assign this address to the pointer "head" and "p". Then allocate another block, using malloc(), and assign the returned address to the "next" field in the block pointed to by "p".
This procedure has thus created a linked-list, since the two blocks have been connected by a pointer. If you want to add more blocks to the list, move "p" to the next block by saying "p = p->next". Fields in an allocated block can be referenced through the representation of the declared struct. What the "->" does here is say "Go to the block pointed to by 'p', and go to the 'next' field in that block." Since "next" contains the address of the next block allocated, it makes "p" point to the next allocated space. Do not also move "head". Its purpose is to be a reference to the beginning of this list, so that if you ever want to travel down the list again from the beginning, you can by saying "p = head". After "p" has been moved to this next allocated block, you proceed:
/* declare struct node*/
struct node
$(
char ch;
int num;
char name[15];
struct node *next; /* this is a pointer to this structure, of type*/
/* "struct node" */
$)
Now say we do the following in main():
main()
$(
/* declare pointers to structure of type "struct node" */
struct node *head, *p;
/* go out and get some memory that is just the right size for a*/
/* struct of type node*/
head = (struct node*) malloc(sizeof(struct node));
p = head;
/* do it again and assign the returned address to the pointer */
/* in the allocated block */
p->next = (struct node*) malloc(sizeof(struct node));
/* move temporary pointer to newly allocated block*/
p = p->next;
/* allocate a 3rd block and assign the returned address to the*/
/* pointer in the block */
p->next = (struct node*) malloc(sizeof(struct node));
/* The operations of moving the pointer p and allocating a new */
/* block and assigning the address to the "next" field is usually*/
/* done in a loop*/
$)
The "(struct node *)" you see after the "=" is a type cast. What this does is insure that the value on the right side of the "=" is of the correct data type for the variable on the left side of the "=". The "sizeof(struct node)" function call returns the total number of bytes all the variables in struct node require.
Since a linked-list can conceptually have any number of memory blocks linked together, how do you determine how long it is? The usual method is to assign the pointer field ("next" in this case) of the last block in, the list to a value called NULL. This NULL value is a specific value, usually 0. This is used so that when a function is searching down the list, it can know when the list ends by checking if the temporary pointer "p" has become NULL, or if NULL is what the "next" pointer points to. Some examples of searching a linked-list and testing for NULL may look like this: "while(p != NULL) ..." or "while(p->next != NULL) ..."
Why A Linked-List?
Besides allocating new blocks and linking them together, I can put values in these blocks, in the other fields. So I could do expressions like: p->ch = 'a'; strcpy(p->next->name, "me"); p->num = 16;.
The power of linked-lists is you don't have to dimension anything! In principle you can get as many memory blocks as you want. All you have to do is ask for them by calling malloc(). Notice I said this is the "principle." With the functions I've written, there's a limited amount of space for this type of allocated memory, since I have them use Page 6, which only has 256 bytes available. Presently, these functions are good for experimenting with this concept of dynamically allocating memory for different uses. On the other hand, as far as the amount of space a struct takes up, 256 bytes is nothing to sneeze at either. I've run C programs on my 8-bit, using these functions, that have implemented linked-lists (one of my programs did two at once), and binary trees. And I haven't run out of space yet. You just won't be able to do anything real large with these functions I've written.
My first attempt at writing the malloc() and free() functions worked ... but it was quick and dirty. For malloc(), I used a static variable that kept track of the next free location in memory. When I wanted to de-allocate something, I passed in the pointer to the block I wanted to de-allocate, and the size of it, to free(), which cleared the block to zeros. But the static variable would keep the same value, and just keep increasing (going forward through memory) each time I used malloc(). I could see that for the long haul, this just wouldn't do. My real goal was to create a set of functions that would support dynamic allocation. In other words, if there was a free spot somewhere in Page 6 of the right size, that spot would be a likely candidate to put something in. So if I freed a block, and later wanted to allocate another block that was the same size or smaller, it would return a pointer to a block that was previously freed. This would make the maximum use of the 256 bytes available.
Dynamic Allocation: A Breakthrough
A friend of mine gave me an idea one day when I said I didn't want to keep passing in the size of the data to deallocate, to free(). He suggested I put a byte before each allocated block, representing the length. That way, free() would be able to determine the size itself. I expanded on this idea to create more advanced versions of malloc() and free() that do the job of dynamic memory allocation within the boundaries of Page 6 and are still fairly memoryefficient. The concept of using a byte to store the size of an allocated area was the missing piece I needed.
Now I'll show you the source code of the set of functions I wrote enabling CC8 to dynamically allocate memory. Further, I'll demonstrate that it's possible to have almost identical source code of a program compiled on two different systems: a minicomputer and an Atari 8-bit. Following are two samples of the same program (written by my friend Darryl May). One compiles and runs on a minicomputer here at Colorado State University. The other is a slightly modified version that compiles and runs on an Atari 8-bit using CC8 with the Ace C linker and libraries. The CC8 version uses the following set of functions (which I wrote).
/* AIMLIB.C for CC8, by Mark Miller 5/27/91. */
#define NULL 0
#define MEMSTART 1536
#define ME14SIZE 256
/* mum of bytes for alloc info. */
#define INFOLEN 2
#define FREE_SPC 1
#define USED_SPC 2
/* Does housekeeping on memory space. If there are
consecutive memory spaces that are freed, it will
consolidate these spaces into one free space.
*/
update()
$(
/* ptr to alloc info.; ptr to first free space found */
char *loc, *tempaddr;
/* size of a space; accum for size of consecutive
spaces */
int size, templen;
/* flag for first non-free space found (after free
space(s) found) */
int done;
loc = MEMSTART;
templen = 0;
/* search through memory space until end, for free
space to consolidate */
while(loc < MEMSTART+MEMSIZE)
$(
if(*loc == FREE SPC)
$(
/* if space is free, search for consecutive free
spaces */
size = *(loc+l);
/* hold first free-space pos */
tempaddr = loc;
/* get size of this space */
templen = size;
/* get to next info. bytes */
loc += size+INFOLEN;
done = 0;
while((loc < MEMSTART+MEMSIZE) && !done)
$(
/* if next space is free, add its free space to
accum */
if(*loc = FREE SPC)
$(
size = *(loc+l);
templen += size+INFOLEN;
$) /* if */
else
/* otherwise, done with present search */
done = 1;
/* go to next info. bytes */
loc += size+INFOLEN;
$) /* while */
/* if more than one free space was found, record
this free space at first free-space pos */
if(templen 1= size)
*(tempaddr+l) = templen;
templen = 0;
$) /* if */
else
/* if space is not free, go to next info. bytes
(next space) */
loc += size+INFOLEN;
$) /* while */
$) /* update */
/* Finds a free space for something of specified size
(data type does not matter). If no free space can be
found with specified size, malloc will return NULL.
Currently malloc only works in the 256 byte space of
Page 6 (location 1536 decimal).
*/
char *malloc(size)
int size;
$(
/* ptr to info. bytes; ptr to allocated space */
char *loc, *bloc;
/* amt of space free/used */
int space;
/* flag for when free space found and allocated; flag
for when update() is called */
int done, updated;
loc = MEMSTART;
/* if memory area is completely unused, put in info.
bytes, set to free space */
if(*loc == 0)
$(
*loc = FREE _SPC;
*(loc+l) = MEMSIZE-2;
$) /* if */
bloc = NULL;
updated = 0;
done = 0;
while(!done)
$(
/* search for free space of specified size (or more) */
while((loc < MEMSTART+MEMSIZE) && !done)
$(
space = *(loc+l);
/* if space is free, allocate it and return ptr to
it. Also put modified info. bytes after allocated
space */
if((*loc == FREE SPC) && ((space == size)
(space >= size+INFOLEN) ||
$(
*loc = USED SPC;
*(loc+l) = size;
if(space >= size+INFOLEN)
$(
*(loc+INFOLEN+size) = FREE SPC;
*(loc+INFOLEN+l+size) = space-size-INFOLEN;
$) /* if */
bloc = loc+INFOLEN;
done = 1;
$) /* if */
else
/* otherwise, go to next info. bytes */
loc += space+INFOLEN;
$) /* while */
if(lupdated && ldone)
$(
update();
updated = 1;
loc = MEMSTART;
$)
else
done = 1;
$) /* while */
return bloc;
$) /* malloc */
/* Deallocates space pointed to by addr. */
free(addr)
char *addr;
$(
int size;
if((addr >= MEMSTART) && (addr < MEMSTART+MEMSIZE))
*(addr-2) = FREE SPC;
$) /* free */
/* Allocation Memory Reset:
Sets all bytes in memory space to 0, just in case any
data is there.
*/
almreset()
$(
clear(MEMSTART-1, MEMSIZE+1);
$)
/* Allocation Memory Dump:
This function is provided for program debugging
purposes. It displays, in decimal form, what is in the
memory area used for dynamic memory allocation by
malloc().
*/
almdump()
$(
char *addr;
printf(*Allocation memory dump from location\n*);
printf(*%d to %d, in bytes:\n*, MEMSTART, MEMSTART +
MEMSIZE);
for(addr = MEMSTART; addr <= MEMSTART+MEMSIZE; addr++)
printf(*%d *, *addr);
printf(*\nPress RETURN to continue*);
getchar();
$) /* almdump */
If you'd like to use the malloc(), free(), almreset(), and almdump() functions [update() is used by malloc(); you shouldn't need to use it yourself], just compile the above source code. I've named this library PTRLIB.C on my disk (when compiled it's filename is PTRLIB.CCC). When your program needs these functions, link PTRLIB.CCC with your compiled program, using a linker. CC8 doesn't mind if you call functions that don't exist in your source code. The linker deals with that.
Notice the part in malloc() that says when you want to allocate space for something, the data type doesn't matter, except when it comes to determining the size of the block you want to allocate. You could write something like the following, and it would work like a regular character array:
main()
$(
char *ch;
ch = (char *) ma11oc(5*sizeof(char));
$)
This would do essentially the same thing as declaring "char ch[5];" except you would have to remember to free(ch) when you were done with it (remember this allocated space is in Page 6). This is just to illustrate that you don't have to use just structs with malloc(). All malloc() cares about is how many bytes you want.
Pascal's Triangle: A C Comparison
Now for the example program. This program by Darryl May (thanks, Darryl!) displays Pascal's triangle- which comes from the Binomial Theorem- for however many levels you want. It uses linked-lists to do this. First, here's the version that runs on a minicomputer here at C.S.U.:
/* CS253
Assignment 5 - c
By Darryl May
April 25th 1990
/*
#include <atdio.h>
struct lnode
(
int value;
struct lnode *next;
};
struct lnode *new_row;
struct lnode *old_row;
struct lnode *print_row;
struct lnode *head_old;
struct lnode *head_new;
struct lnode *temp;
main(argc, argv)
int argc;
char *argv[];
(
int number_of_rows;
unsigned int vl;
if (argc == 2) number_of_rows atoi(argv[1]);
else scanf(*%d*,&number_of_rows);
/* Put a value of 1 into old row to get things started */
old_row= (struct lnode *) malloc(sizeof(struct lnode));
old_row -> value = 1;
old_row -> next = NULL;
head_new = old_row;
printf(*%u\n*,old_row -> value);
while(number_of_rows--) /* Main loop */
(
/* Start the new row off with a value of 1 */
new_row=(struct lnode *) malloc(sizeof (struct lnode)) ;
print_row = new_row;
head_old = old_row;
head_new = new_row;
new_row -> value = 1;
while(old_row -> next) /* Keep building new row until */
{ /* all the values in old row */
vl = old_row -> value; /* have been used. */
old_row = old_row -> next;
new_row->next=(struct lnode *) malloc(sizeof(struct lnode));
new_row = new_row, -> next;
new_row -> value = vl + old_row -> value;
)
/* End the new row with a value of 1. */
new_row -> next = (struct lnode *) malloc (sizeof (struct
lnode));
new_row = new_row -> next;
new_row -> value = 1;
new_row -> next = NULL;
/* Print out the new row. */
printf(*%u *,print_row -> value);
while(print_row -> next)
(
print_row = print_row -> next;
printf(*%u *,print_row -> value);
)
printf(*\n*);
/* Change the old row pointer to point to the head of the
new row. */
old_row = head_new;
/* Return the memory used by the new row back to the
system. */
temp = head _old -> next;
free(head_old);
while(temp)
(
head_old = temp;
temp = head_old -> next;
free(head_old);
)
old_row = head_new;
} /* End of the main loop */
/* Return the memory used by the old row back to the
system. */
temp = head_new -> next;
free(head_new);
while(temp)
(
head_new = temp;
temp = head_new -> next;
free(head_new);
)
} /* End of program. */
Now here's the Atari 8-bit version, slightly modified so it'll compile with CC8:
/* Atari 8-bit version, using CC8 with Ace C linker and
libraries.
CS253
Assignment 5 - c
By Darryl May
April 25th 1990
*/
#define NULL 0
struct lnode
$(
int value;
struct lnode *next;
$);
struct lnode *new_row;
struct lnode *old_row;
struct lnode *print_row;
struct lnode *head_old;
struct lnode *head_new;
struct lnode *temp;
main()
$(
int number_of_rows;
int vl;
char numinp[3];
printf("Enter number of rows to do\n");
gets(numinp);
number_of_rows = val(numinp);
/* Put a value of 1 into old row to get things started */
old_row =(struct lnode *) malloc(sizeof(struct lnode));
old_row -> value = 1;
old_row -> next = NULL;
head_new = old_row;
printf(*%d\n*,old_row -> value);
while(number_of_rows--) /* Main loop */
$(
/* Start the new row off with a value of 1 */
new_row=(struct lnode*) malloc(sizeof(struct lnode));
print_row = new_row;
head_old = old_row;
head_new = new_row;
new_row -> value = 1;
while(old_row -> next) /* Keep building new row until */
$( /* all the values in old row */
vl = old_row -> value; /* have been used. */
old_row = old_row -> next;
new_row->next=(struct lnode *) malloc(sizeof(struct
lnode));
new_row = new_row -> next;
new_row -> value = vl + old_row -> value;
$)
/* End the new row with a value of 1. */
new_row->next = (struct lnode *) malloc(sizeof(struct
lnode));
new_row = new_row -> next;
new_row -> value = 1;
new_row -> next = NULL;
/* Print out the new row. */
printf(*%d *,print_row -> value);
while(print_row -> next)
$(
print_row = print_row -> next;
printf(*%d *,print_row -> value);
$)
printf(*\n*);
/* Change the old row pointer to point to the head of the
new row. */
old_row = head_new;
/* Return the memory used by the new row back to the
system. */
temp = head_old -> next;
free (head_old) ;
while(temp)
$(
head_old = temp;
temp = head_old -> next;
free(head_old)
$)
old_row = head_new;
$) /* End of the main loop */
/* Return the memory used by the old row back to the
system. */
temp = head_new -> next;
free(head_new);
while(temp)
$(
head_new = temp;
temp = head_new -> next;
free(head_new);
$}
getchar();
$) /* End of program. */
