A General’s View – Complete Game

Author’s Note: I mentioned in my last post that I had been working on my final year project for college. Just wanted to share what I came up with in the end. The project is a two-player game based on A General’s View, the tabletop strategy game that I designed in 2015 and is written using the Allegro 4 game library. The game is not particularly sophisticated and there are a few interface bugs that need to be ironed out, but it works and could be used for the basis of a more sophisticated game in the future.

The game is played by two human players with the following controls:

Map keys

Up, Down, Left, Right – move cursor

Enter – enter menu

Menu keys

Up, Down – move cursor

Enter – select menu option highlighted by cursor

For full rules and objectives of the game, please see A General’s View: Rules (Alpha Version). Please note that in this version of the game, at most one unit from each player can occupy a tile at once.

The game (in both Windows executable and source code forms) can be downloaded from the following link: https://drive.google.com/folderview?id=0B_lGPZTjA4fzbHN4YVExelBEejA&usp=sharing

unit_moving

Screenshot_20160229_200035

Advertisements

The C Preprocessor

One of the peculiar things about the C programming language is that so many commonly occurring elements are not actually part of the language, per se. All of the functions in the standard library are actually extensions to C, additional parts which give us the input/output, mathematical and utility features which make C powerful. All of these are contained in a set of header files and binaries which are added to programs during the compilation process.

Another extension to C is the C preprocessor, and it is this that gives us the ability to extend the language to perform functions. The C preprocessor is a sort of computer language of its own sort, and while it is not Turing-complete, it is useful enough for the purposes for which it is called. The C preprocessor reads through a C source file, replacing various statements which are important to the preprocessor to ones which are important to the C compiler.

It is somewhat difficult to explain why the C preprocessor is important, but I will attempt to do so with a brief segue into the history of computer languages. Early high-level programming languages, such as Fortran and COBOL, were notable for being able to do one set of tasks very well and most others not so well at all. In some cases, this led to deficiencies which would be considered ghastly today; ALGOL 58 and 60, for instance, did not define any input/output operations, and any I/O routines would be completely machine-dependent.

In the later 1960s, language designers attempted to create new languages which would be suitable for multi-purpose applications. However, these languages, which included PL/I and ALGOL 68, were designed by committees who were made up of conflicting personalities, many of which were desperate to see their pet features included in the languages. As the complexity of the languages grew, so did the complexity of developing an efficient compiler. As computing resources were vastly smaller than they are now, these languages were only suitable for mainframe computers, and then not even efficiently.

Therefore, these language experiments tended to fail. PL/I has some residual support by being supported by IBM, but it is moribund outside of the confines of IBM machines; ALGOL 68 is dead and buried. When C came around, Dennis Ritchie was aiming to create a language which both implemented enough features in order to build an operating system and its applications, while being able to run efficiently on a much less powerful computer than those for which PL/I was designed.

The solution was to create a system in which only the subset of the functions that were required for a specific program would be implemented, rather than the full set. This made compilation of C more efficient, as the compiler generally only had to be concerned with a small number of functions at once. The method chosen to do this was to use the C preprocessor to keep the function definitions of most functions outside of the base language; when C was standardised in 1989 by the ANSI committee, and in 1990 by the ISO, all functions were taken out of the base language and put into header files.

Now that the history lesson is over, we can continue on to the operations of the preprocessor. As mentioned above, the preprocessor scans a C source file – or, in some circumstances, another source file; Brian Kernighan famously developed RATFOR to add similar features to Fortran as in C – and looks for statements that are important to it. It then replaces them with statements that are important to the C compiler or whatever other system the preprocessor is being used for.

The most fundamental operation of the preprocessor is #include. This operation looks for a file which is defined at a path included in the #include directive, then inserts its entire contents into the source file in place of the #include directive. The file’s contents might themselves contain C preprocessor statements, as is common in C header files, so the preprocessor goes through those and acts upon them appropriately.

One of the most common invocations of the #include directive is the following:

#include <stdio.h>

This directive locates the file, stdio.h, and places its contents into a source file. The use of angle brackets around the filename indicates that it is stored in a directory whose path is known to the C compiler, and which is defined as the standard storage path for header files. stdio.h itself contains several preprocessor statements, including #define and #include statements, which are resolved by the preprocessor appropriately.

Let’s define a simple program which can be used to test this. The program will be the standard “hello, world” program as defined in The C Programming Language (Brian Kernighan & Dennis Ritchie, 2nd Edition).

#include <stdio.h>

main()
{
    printf("hello, world\n");
}

Now, we can see some of the results when this is passed through the C preprocessor:

typedef long unsigned int size_t;
typedef unsigned char __u_char;
typedef unsigned short int __u_short;
typedef unsigned int __u_int;
typedef unsigned long int __u_long;
typedef signed char __int8_t;
typedef unsigned char __uint8_t;
typedef signed short int __int16_t;
typedef unsigned short int __uint16_t;

...

struct _IO_FILE {
  int _flags;
  char* _IO_read_ptr;
  char* _IO_read_end;
  char* _IO_read_base;
  char* _IO_write_base;
  char* _IO_write_ptr;
  char* _IO_write_end;
  char* _IO_buf_base;
  char* _IO_buf_end;
  char *_IO_save_base;
  char *_IO_backup_base;
  char *_IO_save_end;
  struct _IO_marker *_markers;
  struct _IO_FILE *_chain;
  int _fileno;
  int _flags2;
  __off_t _old_offset;
  unsigned short _cur_column;
  signed char _vtable_offset;
  char _shortbuf[1];
  _IO_lock_t *_lock;
  __off64_t _offset;
  void *__pad1;
  void *__pad2;
  void *__pad3;
  void *__pad4;
  size_t __pad5;
  int _mode;
  char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)];
};

...

extern int fprintf (FILE *__restrict __stream,
      __const char *__restrict __format, ...);
extern int printf (__const char *__restrict __format, ...);
extern int sprintf (char *__restrict __s,
      __const char *__restrict __format, ...) __attribute__ ((__nothrow__));
extern int vfprintf (FILE *__restrict __s, __const char *__restrict __format,
       __gnuc_va_list __arg);
extern int vprintf (__const char *__restrict __format, __gnuc_va_list __arg);
extern int vsprintf (char *__restrict __s, __const char *__restrict __format,
       __gnuc_va_list __arg) __attribute__ ((__nothrow__));

...

main()
{
    printf("hello, world\n");
}

Most of the file has been truncated, but as we can see, the stdio.h header contains typedef declarations for various types, structure definitions including the above one for a FILE type as used in the file input/output routines, and function definitions. By being able to call this file from elsewhere, we save ourselves a lot of time and work from having to copy all of these definitions into our program manually.

While the above definition works for the standard header files, the location of the standard header files is restricted to read-only operations for non-administration users in many operating systems. There is, therefore, another way to specify the location of a source file, which may be an absolute path or relative to the working directory. A set of definitions of this type, using a relative and then an absolute definition, are shown below.

#include "foo.h"
#include "/home/jrandom/bar.h"

The operation of these preprocessor statements is similar to that of the one used for stdio.h; the major difference is in where the files are located. Instead of checking the standard directory for header files, the first definition checks the same directory as the source file for a header file named foo.h, while the second checks the absolute path leading to the /home/jrandom directory for a file named bar.h.

As it is common practice in C programming to leave #define statements, function prototypes and structure definitions in separate header files, this allows us to create our own header files without having to access the standard directory for header files.

The other particularly common invocation of preprocessor statements is the #define statement. The #define statement has two parts, an identifier and a token sequence. The preprocessor changes all instances of the identifier for the token sequence. This is useful for defining more legible names throughout the source code, particularly for so-called “magic numbers” whose purpose is not obvious from observation. A few examples of how this may be used are shown below:

#define MAX_FILENAME 255 /* Defines the maximum length of a filename path */
#define DIB_HEADER_SIZE 40 /* Defines the size of a BMP DIB header in bytes */
#define FOO_STRING "foobarbazquux"

In most cases, the #define tag is simply used to provide effective macros for obscure or complex definitions, but there is another sort of functionality which the #define statement can be used for. The #define statement can be used to define a macro with arguments, which is an effective way of creating shorthand for a piece of simple code which one doesn’t want to consistently repeat, but for which one doesn’t want the overhead of a function. An example of this is shown below:

#define SQUARE(x) (x) * (x)

We might see this definition invoked in a program like so:

#include 
#define SQUARE(x) (x) * (x)

int main(void)
{
    int a;

    printf("Enter an integer: ");
    scanf("%d", &a);
    printf("The square of %d is %d\n", a, SQUARE(a));
    return 0;
}

When this function is called, the SQUARE(a) invocation is replaced by (a) * (a). Note the brackets around the arguments in the macro; these are imperative for preserving the appropriate order of operations. Let’s say that we were to define SQUARE(x) as the following:

#define SQUARE(x) x * x

and then call it with the following code:

SQUARE(5 + 4)

This would expand out to the following:

5 + 4 * 5 + 4

As multiplication precedes addition, the multiplication in the middle would be performed first, with the multiplication of 4 and 5, giving 20, and then the flanking additions would be performed, giving an answer of 29. This is quite short from the 81 that we would expect from the square of 9. Therefore, it is important to appropriately define your macros in accordance with the expected order of operations.

Macros can have more than one argument, such as the following definition for a macro to find the larger of two numbers:

#define max(a, b) (a) > (b) ? (a) : (b)

Having defined something, we may want to undefine it further down the source file, possibly to prevent interference with certain operations, or to ensure that something is a function rather than a macro. For instance, in the standard libraries for low-power embedded platforms, getchar() and putchar() may be defined as macros in order to prevent the overhead of a function. In order to undefine something, we use #undef. The following code would undefine the SQUARE and max operation which we defined above:

#undef SQUARE
#undef max

Beyond the realms of #include and #define lie the conditional preprocessor directives. The first set of these are used to check whether something has already been defined, while the other set are used to check whether a C statement is true or false. We’ll discuss the definition-related directives first.

#ifdef is used to check if something has already been defined, while #ifndef is used to check whether something has not been defined. In professional code, this is regularly used to check the operating system and other details about the system which the program is to be compiled for, as the elementary operations which make up basic routines differ on different systems. We can also check if something is defined using the “defined” operator; this is useful if we want to continue checking after an #ifdef or #ifndef statement which was not satisfied.

Let’s say that we had a piece of source code which we needed to maintain on Windows, Mac OS X and Linux. Various bits of the source code might not apply to one or more of those operating systems. We could therefore hide the bits of source code that don’t apply to the current operating system using the following:

#ifdef _WIN32
#include 
#include 

#elif defined MACOSX
#include 
#include 

#elif defined LINUX
#include 
#include 

#endif

Note the use of #endif to close our set of conditional directives. This is part of the remainder of the conditional directives. #if checks if a C statement is true, and proceeds if it is, #elif is used to check another alternative if the preceding condition was not satisfied, #else is a universal alternative if none of the preceding conditions were satisfied, while #endif closes a block of conditional preprocessor statements. These operations work very similarly to the if…else if…else statements in C. The following example checks whether we are compiling for a 32-bit or 64-bit system:

#if !(defined __LP64__ || defined __LLP64__) || defined _WIN32 && \
    !defined _WIN64
/* we are compiling for a 32-bit system */
#else
/* we are compiling for a 64-bit system */
#endif

In this code, we’re looking for a definition of __LP64__ or __LLP64__, which define data models for 64-bit processors, to be false, or a definition of _WIN32, which defines a Windows software platform, to be true without a corresponding definition of _WIN64, which defines a 64-bit version of Windows, to be true. If this is true, the program is compiled for a 32-bit system, which will have different machine instructions to the 64-bit system.

While there are some other details of the preprocessor to discuss, they are best left to external reading. To conclude, there are a number of predefined macros in the C preprocessor, such as __LINE__, which calculates the line number, and __FILE__, which determines the filename. The C preprocessor can be somewhat obscure, but it gives the C language a great deal of flexibility – the sort of flexibility that sees its use on everything from microcontrollers to supercomputers.

A Project With Source Code: A Snake Clone in Allegro

#include <allegro.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TILE_SIZE 20
#define TILES_HORIZ 32
#define TILES_VERT 24
#define MAX_ENTITIES 768

/* Length of snake */
int length = 5;
/* Grid reference for food */
int food_location[2] = {-1, -1};
/* Grid reference array for segments of snake */
int snake_segment[MAX_ENTITIES + 1][2];
/* Direction of snake - 0 for up, 1 for right, 2 for down, 3 for left */
int snake_direction = 3;

BITMAP *back, *snake_body, *food, *game_over;

/* Function prototypes */
void setup_screen();
void create_snake();
void draw_snake(int i);
void set_food_location();
void move_snake();
int collision_check();
void get_input();
void cleanup();

int main(void)
{
    int i, check;
    clock_t last_cycle;
    
    /* Set up Allegro */
    allegro_init();
    setup_screen();
    srand(time(NULL));
    install_keyboard();

    /* Establish beginning conditions */
    create_snake();     
    draw_snake(0);
    set_food_location();
    last_cycle = clock();

    while(!key[KEY_ESC]) {
	if ((clock() - last_cycle) / (double) CLOCKS_PER_SEC >= 0.1) {
	    last_cycle = clock();
	    move_snake();
	    check = collision_check();
	    /* If snake collided with walls or itself, end the game */
	    if (check == 1) {
		break;
	    } else if (check == 2) {
		/* If snake coincided with food, extend snake and reset food
		   location */
		length++;
		set_food_location();
	    }
	    get_input();
	}
    }

    game_over = load_bitmap("game_over.bmp", NULL);

    /* Display game over message when collision detected */
    while (!key[KEY_ESC]) {
	blit(game_over, screen, 0, 0, 0, 0, SCREEN_W, SCREEN_H);
    }

    cleanup();
    allegro_exit();
}
END_OF_MAIN()

void setup_screen()
{
    int i;

    set_color_depth(24);
    set_gfx_mode(GFX_AUTODETECT_WINDOWED, 640, 480, 0, 0);
    
    back = create_bitmap(SCREEN_W, SCREEN_H);
    clear_bitmap(back);

    /* Create white grid on background bitmap, blit to screen */
    for (i = 0; i < SCREEN_W; i += TILE_SIZE) {
	vline(back, i, 0, SCREEN_H, makecol(255, 255, 255));
    }

    for (i = 0; i < SCREEN_H; i += TILE_SIZE) {
	hline(back, 0, i, SCREEN_W, makecol(255, 255, 255));
    }

    blit(back, screen, 0, 0, 0, 0, SCREEN_W, SCREEN_H);
}

void create_snake()
{
    int i, j;

    for (i = 0, j = 15; i < length; j++, i++) {
	snake_segment[i][0] = j;
	snake_segment[i][1] = 12;
    }
}

void draw_snake(int mode)
{
    int i;
    if (snake_body == NULL) {
	snake_body = load_bitmap("snake_body.bmp", NULL);
    }
    
    for (i = 0; i < length; i++) {
	draw_sprite(screen, snake_body, snake_segment[i][0] * TILE_SIZE + 1,
				snake_segment[i][1] * TILE_SIZE + 1);
    }

    /* If function called from move_snake(), remove final segment of snake
       from the screen */
    if (mode = 1) {
	blit(back, screen, snake_segment[length][0] * TILE_SIZE,
	     snake_segment[length][1] * TILE_SIZE, 
	     snake_segment[length][0] * TILE_SIZE,
	     snake_segment[length][1] * TILE_SIZE,
	     TILE_SIZE, TILE_SIZE);
    }
}

void set_food_location()
{
    int i, valid = 1;
    
    if (food == NULL) {
	food = load_bitmap("food.bmp", NULL);
    }
    
    /* Ensure food is not positioned on a snake segment */
    do {
	valid = 1;
	food_location[0] = rand() % TILES_HORIZ;
	food_location[1] = rand() % TILES_VERT;
	
	for (i = 0; i < length; i++) { 	    if (food_location[0] == snake_segment[i][0] && food_location[1] 		== snake_segment[i][1]) 		valid = 0; 	}     } while (!valid);     draw_sprite(screen, food, food_location[0] * TILE_SIZE + 1, 		food_location[1] * TILE_SIZE + 1); } void move_snake() {     int i;     /* Move all grid references for snake segments up one position */     for (i = length - 1; i >= 0; i--) {
	snake_segment[i + 1][0] = snake_segment[i][0];
	snake_segment[i + 1][1] = snake_segment[i][1];
    }

    /* Then, change the appropriate reference point depending on the snake's
       direction */
    if (snake_direction == 0) {
	--snake_segment[0][1];
    }
    else if (snake_direction == 1) {
	++snake_segment[0][0];
    }
    else if (snake_direction == 2) {
	++snake_segment[0][1];
    }
    else if (snake_direction == 3) {
	--snake_segment[0][0];
    }

    draw_snake(1);
}

int collision_check()
{
    int i;

    /* Snake collided with walls - end game */
    if (snake_segment[0][0] < 0 || snake_segment[0][0] >= TILES_HORIZ ||
	snake_segment[0][1] < 0 || snake_segment[0][1] >= TILES_VERT) {
	return 1;
    }

    /* Snake collided with itself - end game */
    for (i = 1; i < length; i++) {
	if (snake_segment[0][0] == snake_segment[i][0] &&
	    snake_segment[0][1] == snake_segment[i][1]) {
	    return 1;
	}
    }

    /* Snake coincided with food - extend snake and reset food position */
    if (snake_segment[0][0] == food_location[0] && snake_segment[0][1] ==
	food_location[1]) {
	return 2;
    }

    return 0;
}

void get_input()
{
    if (key[KEY_UP] && snake_direction != 2) {
	snake_direction = 0;
    }

    if (key[KEY_RIGHT] && snake_direction != 3) {
	snake_direction = 1;
    }

    if (key[KEY_DOWN] && snake_direction != 0) {
	snake_direction = 2;
    }

    if (key[KEY_LEFT] && snake_direction != 1) {
	snake_direction = 3;
    }
}

void cleanup()
{
    destroy_bitmap(back);
    destroy_bitmap(snake_body);
    destroy_bitmap(food);
    destroy_bitmap(game_over);
}

Basics of Structures in C

With this post, we get to one of the most useful elements of C: Structures. While structures didn’t exist in some of the early versions of C, they were soon added in as the developers of C and the Unix operating system saw how useful they could be for extending the utility of their pre-existing programs, and indeed, developing programs outside of the field of system programming. The C data structure is, along with functions, one of the elements that gives it extra utility compared to the programming languages that came before, like FORTRAN and BASIC.

A structure is, speaking succinctly, a way of wrapping multiple variables up into one “package”. To demonstrate why you might want to do this, we could say that you’re designing a simple data processing application like a rudimentary stock control system for a small shop. This stock control system works on a number of different variables, such as char arrays for storing the names of the products, float variables for storing the cost and sell price of these products, and int variables for storing the number of products left in stock. Without structures, we have to declare all of these variables discretely, as illustrated below:

char *name[100];

int *number;

double *cost;

double *price;

The reason we have declared all of these as pointers is because we will want to declare arrays of these variables, but unless you know exactly how many product types are in your database, you won’t know how much memory to allocate, and so, you will have to use malloc(), calloc() or realloc() to create arrays of the appropriate size.

The problem we have here is that none of the elements of these arrays has any particular connection to the corresponding elements in the other arrays. Let’s say you wanted to sort the products into alphabetical order. You’d perform your sorting algorithm on the name[] array, which would work perfectly well, but if you forgot to appropriately change around the other three arrays, you’d end up with a situation where all of the arrays were knocked out of sync. This demonstrates how fragile this stock control system would be – and how inefficient, as you’d have to appropriately change the positions of three other arrays in addition to the name[] array!

What’s more, this particular stock control program wouldn’t work very well when it came to passing the elements into a function. In order to perform a stock reordering function, what we’d have to do is pass four separate variables into the function. Let’s say that we just wanted to reorder a single product, which might use a function with a prototype like this:

int reorder(char **name, int *number, double *cost, double *price);

Pretty messy, don’t you think? One of the preferable things about structures is that they allow you to send a single variable into this function. The function prototype can be rewritten in the following fashion:

int reorder(struct item *product);

This is a lot cleaner and easier to handle. There’s a single variable in the arguments of type “pointer to struct item“, which contains all of the discrete variables which we had before. I’ll explain more about pointers to structures later. First of all, we’re going to leave our stock control system for a few moments and look at a simpler structure declaration.

One useful application that C can and regularly has been used for is graphical manipulation. In a raster graphical format, such as BMP, JPEG, GIF or PNG, each pixel has an x and a y coordinate. In the light of what we’ve seen above with the lack of robustness with discrete variables, we’re going to want to create a “package” – or structure – to hold both components of a pixel location together. We’ll create a structure type for doing this:

struct pixel {
    int x;
    int y;
};

What we’ve just created is a structure declaration, which essentially says, “Let’s create a new type, called struct pixel, whose elements will be an int variable named x, and an int variable named y“. This structure declaration now allows us to create variables of type struct pixel in other parts of the program.

Once we have the structure declaration, we create an element of this structure type like this:

struct pixel pixel_1;

The element pixel_1 is now created, just as we’d create an int, char or float variable. It follows some of the same rules as any of these other variables, in that it fills a certain amount of space (in this case, as it contains two int variables, its size will be sizeof(2 * int)). However, because it contains more than one variable itself, changing the values of these internal variables involves a different step than we’ve taken before.

To do this, we introduce the structure member operator, “.” (a single full stop). Let’s illustrate how this works by setting the value of the x coordinate in pixel_1 to 150:

pixel_1.x = 150;

The structure member operator is very high in the order of precedence in C; it has a higher precedence than the pointer dereference operator, and equivalent precedence to brackets and square brackets.

We’ll put this all together in a simple program:

#include <stdio.h>

struct pixel {
    int x;
    int y;
};

int main(void)
{
    /* We'll create a variable of type struct pixel */
    struct pixel pixel_1;

    /* Set the elements of pixel_1 /*
    pixel1.x = 200;
    pixel1.y = 350;
    return 0;
}

The elements of a structure can be any legal variable, such as int, char, float and double. Notably, a structure, once it has been declared, is a legal variable. This means that structures are themselves legal elements of a structure – as long as they are structures of a different type. Extending our metaphor of a graphics program, we can use these so-called nested structures to create a representation of a rectangle. Our simple representation of a rectangle will consist of two pixels representing the origin and the diagonally opposite corner:

struct rect {
    struct pixel pt_1;
    struct pixel pt_2;
};

Indeed, the dimensions of a standard computer screen can be represented by a rectangular structure. We will illustrate how we would use our nested structure here for a 1920×1200 screen:

struct rect screen;

screen.pt_1.x = 0;
screen.pt_1.y = 0;
screen.pt_2.x = 1919;
screen.pt_2.y = 1199;

Unfortunately, without graphical functions to act upon these structures, we can’t do much with our pixel and rectangle structures. We return, therefore, to the stock control program described earlier. Having seen some simple structures, we can now design a structure which will represent a data entry.

struct item {
  char name[100];
  int number;
  float cost;
  float price;
};

This structure contains the variables for which we would have had to declare separate arrays in the previous program. In using a structure, we have packaged all of these variables together, giving them a mutual association. We’ll demonstrate how this may be used, given a database containing the following, which we can save to a file:

Bread 12 1.65 2.25
Milk 23 1.40 1.80
Eggs 20 1.60 2.15
Cheese 11 1.85 2.50
Bacon 6 2.65 3.15

Now, we write a program to take these values in and to print them out. This program will take a single additional command-line argument, which will be the file name of the database that we defined above:

#include <stdio.h>

struct item {
    char name[100];
    int number;
    float cost;
    float price;
};

int main(int argc, char *argv[])
{
    struct item item_array[5];
    FILE *ifp;
    int i;

    if (argc != 2) {
	printf("Usage: basic_database <filename>\n");
	return -1;
    } else if ((ifp = fopen(argv[1], "r")) == NULL) {
	printf("Error: Could not open file %s\n", argv[1]);
	return -2;
    } else {
	for (i = 0; i <= 5; i++) {
	    fscanf(ifp, "%s%d%f%f", item_array[i].name,
	    &item_array[i].number,
	    &item_array[i].price, &item_array[i].cost);
	}
	fclose(ifp);
    }

    for (i = 0; i <= 4; i++) {
	printf("%s %5d %8.2f %8.2f\n", item_array[i].name, item_array[i].number,
	item_array[i].price, item_array[i].cost);
    }
    return 0;
}

When we call it with our data from before, we get the following result:

Bread 12 1.65 2.25 
Milk 23 1.40 1.80 
Eggs 20 1.60 2.15 
Cheese 11 1.85 2.50 
Bacon 6 2.65 3.15

So, we’ve defined the framework for a simple database. We could do things with these values, such as searching through them to find the item with the highest price for the consumer:

float highest_price = 0;
int highest_price_pos = 0;

for (i = 0; i < 5; i++) {
    if (item_array[i].price > highest_price) {
	highest_price = item_array[i].price;
	highest_price_pos = i;
    }
}

A problem arises, though, when we look at this in greater detail. What happens if the database – as is very likely – contains more than five items? We don’t want to have to recompile our program every time we get a new item to sell, so we do what we would do if we required additional variables of other types: We use dynamic memory allocation. In order to do this, we will require a pointer to our structure type, but before I change our program, we need to discuss pointers to structures.

Pointers to structures operate similarly to pointers to other variables, in that they store memory addresses to structures. They are also declared similarly, with the following example being a pointer to type struct item:

struct item *item_pointer;

However, the order of precedence in C creates a bit of a problem when it comes to using the traditional dereference operator to access the contents of a pointer to a structure. The traditional syntax for accessing data in the elements of a pointer to a structure looks peculiar and confusing:

item_pointer = item_array[3];

(*item_pointer).price = 2.50;

Note that we have to use brackets around the dereference operator and the thing it’s dereferencing. The order of precedence for the structure member operator is higher than that of the dereference operator, and therefore we have to use brackets, which have the same precedence as the structure member operator, in order to allow the pointer to access its memory address before the structure member is called.

Luckily, there is a separate operator used specifically for allowing a pointer to a structure to access its elements without having the potential source of confusion caused by the dereference operator in this circumstance. The structure pointer operator, -> (a minus sign, followed by a greater-than sign), has the same precedence as the structure member operator, and reduces the ambiguity existing with the traditional syntax.

Having discussed that, we can modify our program from before to dynamically allocate memory based on the number of elements contained in the list. We will use malloc() to initially allocate memory for a single element of type struct item *, then use fscanf() to read in the values into the elements of this structure. For each line that fscanf() doesn’t read in the EOF character, the program increases the size of the dynamically allocated memory by the size of the struct item type using the realloc() function. Then, the elements of the structure array are read out as above.

#include <stdio.h>
#include <stdlib.h>

struct item {
    char name[100];
    int number;
    float cost;
    float price;
};

int main(int argc, char *argv[])
{
    struct item *item_array;
    FILE *ifp;
    int i;
    int array_elements = 0;
    int el_size;

    /* Store the size of a single element */
    el_size = sizeof(struct item);

    /* Start off by declaring a single element */
    item_array = (struct item *) malloc (el_size);

    if (argc != 2) {
	printf("Usage: basic_database <filename>\n");
	return -1;
    } else if ((ifp = fopen(argv[1], "r")) == NULL) {
	printf("Error: Could not open file %s\n", argv[1]);
	return -2;
    } else {
	/* Keep going until fscanf hits the EOF character */
	while (fscanf(ifp, "%s%d%f%f", item_array[array_elements].name,
		      &item_array[array_elements].number,
		      &item_array[array_elements].cost,
		      &item_array[array_elements].price) != EOF) {
	    /* Reallocate memory, then increment the elements counter */
	    /* NOTE: We've got a bodge in here. The memory allocated will
	     * always be one element more than we need. */
	    item_array = (struct item *)
		realloc(item_array, (el_size * ++array_elements) + el_size);
	    if (item_array == NULL) {
		printf("Error: Cannot allocate memory\n");
		return -1;
	    }
	}
	fclose(ifp);
    }
    for (i = 0; i < array_elements; i++) {
	printf("%s %d %.2f %.2f\n", item_array[i].name, item_array[i].number,
	       item_array[i].cost, item_array[i].price);
    }

    free(item_array);
    return 0;
}

Fundamentals of String Manipulation in C: Part 2

Having discussed most of the important functions relating to strings before, there are only a few others of particular note. We saw gets() previously, which acts like scanf(“%s”, string), and while it performs the job it’s asked to do, it is regarded as somewhat dangerous as it is prone to buffer overflow. A function does exist in the C standard library in <stdio.h> which is somewhat safer.

fgets() is an equivalent function to gets() designed to work on file input. Unlike gets(), you can specify a maximum number of characters to be taken in, which mitigates the buffer overflow that can occur with gets(). fgets() is called with three arguments: the string where input will be stored; the maximum number of characters, including the null character and either stdin, the reference of the standard input stream, or a pointer to a variable of the type FILE. File pointers will be discussed later; for now, we are only interested in stdin.

An example of the use of fgets() is illustrated below:

#include <stdio.h>

int main(void)
{
    char string[30];
    printf("Please enter a string: ");
    fgets(string, 30, stdin);
    puts(string);
    return 0;
}

One peculiar difference between fgets() and gets() is that fgets() does not remove newline characters from its input, while gets() does. This is to be noted when trying to concatenate two strings with strcat() which have been entered from the standard input stream with fgets().

Previously, we also saw the strcmp() function for comparing two strings. A similar function, strstr() (for string string) can be used to find an instance of a string of smaller or equal size within another string. It takes two arguments, both of them strings, and returns a pointer to the first instance of the string being searched for in the string being searched. The following program demonstrates strstr() in action.

#include <stdio.h>
#include <string.h>

int main(void)
{
    char string[] = "yellow dinosaurs eat snow reluctantly";
    char *p;
    int index;

    /* Looking for the location of "eat" in string[] */
    p = strstr(string, "eat");
    /* Finding the element within the array where "eat" begins */
    index = p - string;
    printf("The string \"eat\" begins at index %d of string[]\n");

  return 0;
}

This returns the following:

The string "eat" begins at index 16 of string[]

Searching for multiple instances of strings using strstr() requires a slight modification of our program. We can do this by creating an index, or a point in the array where the last instance of the string was found, and call the strstr() function from the next contiguous point in memory (i.e. the pointer string + index + 1). This example will benefit from the following illustration:

#include <stdio.h>
#include <string.h>

int main(void)
{
    char long_string[] = "The C programming language was invented in the \n"
    "early 1970s by the computer scientist, Dennis Ritchie, who was then \n"
    "working at Bell Labs in New Jersey, which had just removed its \n"
    "support from the Multics project.\n";
    int index = -1, count = 0, i;
    char *p;

    printf("%s", long_string);

    for (i = 0; i < strlen(long_string); i += index) {
	p = strstr(long_string + index + 1, "in");
	if ((index = p - long_string) >= strlen(long_string) || p == NULL)
	break;
	++count;
    }
    printf("\nThe string \"in\" has been located in the string %d times\n", count);
    return 0;
}

This example returns the following:

The C programming language was invented in the 
early 1970s by the computer scientist, Dennis Ritchie, who was then 
working at Bell Labs in New Jersey, which had just removed its 
support from the Multics project.

The string "in" has been located in the string 5 times

One thing to notice about this program is that the counter variable is not incremented by 1 on every loop, but instead by the value of index; this ensures that the loop continues only as long as there are still instances of the string being searched for to be counted.

In the last tutorial, We demonstrated atoi(), a function which converts a string consisting of numeral digits into a decimal integer. It was mentioned at the time that other functions of the same type exist. atof(), for instance, converts a string consisting of numeral digits, exponents and at most one radix point into a double; atol() operates like atoi(), except that it returns a long int. On most modern compilers, atol() works exactly like atoi(), but on older compilers with 2-byte ints, the two functions work differently.

The implementation of simple versions of these two functions is discussed in The C Programming Language (Kernighan & Ritchie, 2nd Edition, 1988). Other functions of this type with more flexibility exist, like strtod(), strtol() and strtoul(), the operations of which can be found in any good C reference material.

A Project With Source Code: An Updated Graphical, Hexadecimal LMC Simulator

Author’s Note: There were several details of my original simulator which I was dissatisfied with, even if the whole package did manage to properly simulate the hexadecimal variant of the LMC source code that it was meant to. The vector graphics were primitive, the toggle switches were far too responsive to extended key presses for my liking and the peculiar 640×250 resolution prevented the program from being easily made fullscreen. What’s more, each of the buttons and LEDs were placed based on “magic numbers” which were hardcoded into the source. None of these problems proved insurmountable, and I have now developed a slightly more sophisticated version of the simulator with bitmap graphics and switches which have a delay timer built into them.

The project still isn’t perfect; the appearance of the graphics is still amateur, although more appealing than the original version, and it doesn’t exactly mimic the operation of a comparable real-world machine, like the PDP-8 – to do that, I’d need to change the operation towards having a “load address” switch rather than having the switch positions change every time a new address is loaded. This wouldn’t be an insurmountable prospect either, although I prefer the switches being in sync with the LEDs for aesthetic reasons. A real-world LMC computer doesn’t exist, so I don’t have to worry about complete historical accuracy.

The controls are as they were in my original simulator, which is still available under the GNU General Public Licence as before. You will also require a number of graphics for the front plate, the LEDs and the switches. You can either use the graphics here, which you’ll have to manually convert to PCX format, or create your own, as long as they conform to the 640x250px size of the front plate, the 20x20px size of the LEDs and the 20x35px size of the toggle switches.

Note: The layout of this blog format doesn’t extend to the 80 columns required to show all of the source code appropriately. You can circumvent this restriction by dragging the mouse over all of the source code and copying it to a text editor; the hidden code will show up.

/* lmc_gui: A graphical simulator for the Little Man educational instruction
   set, modified for hexadecimal operation.
   Copyright (C) 2012  Richard Kiernan

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

#include <allegro.h>
#include <stdio.h>
#include <time.h>

#define MAILBOXES 0x100 /* Hexadecimal LMC instruction set has 255 */
			/* "mailboxes" */
#define INSTRUCTION_MAX 0xFFF /* Highest value of LMC instructions/data */
#define OP_SPLIT 0xFF /* Denotes the split between opcodes and operands */
#define INSTRUCTION_REST 15 /* The pause time between executed instructions */
			    /* in milliseconds */

#define LED_WIDTH 20 /* LEDs are 20 pixels wide, 20 pixels high */
#define LED_HEIGHT 20
#define SWITCH_WIDTH 20 /* Switches are 20 pixels wide, 35 pixels high */
#define SWITCH_HEIGHT 35

#define BUFFER_HEIGHT 115 /* The black "buffer" on the top and bottom of the
			   screen is 115 pixels high. */

/* We want milliseconds, not full seconds! */
#define CLOCKS_PER_MS (CLOCKS_PER_SEC / 1000)

/* LED structure */
struct individual_led {
    int light_x, light_y;
    int activity_status;
};

/* LED/Switch combination structure */
struct led_switch {
    int light_x, light_y;
    int switch_x, switch_y;
    int activity_status;
    clock_t last_access_time;
};

/* Function prototypes */
void setup_screen(void);
void setup_structs(void);
void setup_components(void);
void setup_front_plate(void);
void setup_accumulator(void);
void setup_memory_addresses(void);
void setup_memory_contents(void);
void setup_power_switch(void);
void setup_clear_switch(void);
void setup_execute_switch(void);
void setup_input_light(void);
void setup_uinput_switch(void);
void initialise_memory(void);
void get_input(void);
void toggle_power(void);
void toggle_address_switch(int toggle);
void set_contents(void);
void toggle_contents_switch(int toggle, char mode);
void toggle_clear_switch(void);
void toggle_execute_switch(void);
void execute_instructions(void);
void set_accumulator(void);
void get_program_input(void);

/* Program variables */
int address_counter = 0; /* Address counter */
int accumulator = 0; /* Accumulator contents */
int input_temp = 0; /* Temporary storage for user input */
int mailbox[MAILBOXES]; /* "Mailboxes" - memory storage slots */

/* Program structures */
struct individual_led accumulator_led[12];
struct individual_led awaiting_input;
struct led_switch address_switch[8];
struct led_switch contents_switch[12];
struct led_switch power_switch;
struct led_switch clear_memory;
struct led_switch execute_switch;
struct led_switch user_input;

/* Program bitmaps */
BITMAP *front_plate = NULL;
BITMAP *led_on = NULL;
BITMAP *led_off = NULL;
BITMAP *switch_on = NULL;
BITMAP *switch_off = NULL;

int main(void)
{
    /* Initialise program */
    allegro_init();
    setup_structs();
    setup_screen();
    install_keyboard();
    initialise_memory();

    while (!key[KEY_ESC]) {
	if (keypressed()) {
	    get_input();
	}
    }

    /* Clean up */
    allegro_exit();
    return 0;
}

/* setup_structs: Assigns values to all of the appropriate structures in the
   program */
void setup_structs(void)
{
    int i;

    /* Start with the accumulator LEDs and contents LED/switch combos -
       12 of each */
    for (i = 0; i < 12; i++) {
	/* The accumulator LEDs start 50 pixels in, and are spaced at 30 pixel
	   increments. */
	accumulator_led[i].light_x = 50 + (i * 30);
	/* The accumulator LEDs are placed 40 pixels below the top edge of the
	   computer box. */
	accumulator_led[i].light_y = BUFFER_HEIGHT + 40;
	/* All of the LEDs are turned off by default. */
	accumulator_led[i].activity_status = 0;

	/* The contents LEDs and switches start 50 pixels in, and are spaced
	   at 30 pixel increments. */
	contents_switch[i].light_x = contents_switch[i].switch_x =
	    50 + (i * 30);
	/* The contents LEDs are placed 160 pixels below the top edge of the
	   computer box. */
	contents_switch[i].light_y = BUFFER_HEIGHT + 160;
	/* The contents switches are placed 35 pixels below the LEDs. */
	contents_switch[i].switch_y = contents_switch[i].light_y + 35;
	contents_switch[i].activity_status = 0;
	/* The default "last access time" is -1; this states that the switches
	   have not yet been activated. */
	contents_switch[i].last_access_time = -1;
    }

    /* Now we initialise the memory address switches. */
    for (i = 0; i < 8; i++) {
	/* The address LEDs and switches start 170 pixels in, and are spaced
	   at 30 pixel increments. */
	address_switch[i].light_x = address_switch[i].switch_x
	    = 170 + (i * 30);
	/* The address LEDs are placed 80 pixels below the top edge of the
	   computer box. */
	address_switch[i].light_y = BUFFER_HEIGHT + 80;
	/* The address switches are placed 35 pixels below the LEDs. */
	address_switch[i].switch_y = address_switch[i].light_y + 35;
	address_switch[i].activity_status = 0;
	address_switch[i].last_access_time = -1;
    }

    /* Next, we do the "awaiting input" LED. */
    /* The LED is placed 450 pixels in. */
    awaiting_input.light_x = 450;
    /* The LED is placed 40 pixels below the top edge of the computer box. */
    awaiting_input.light_y = BUFFER_HEIGHT + 40;
    awaiting_input.activity_status = 0;

    /* Then, we want to do the user input switch. */
    /* The LED and switch are placed on the same x coordinate as the "awaiting
       input" light. */
    user_input.light_x = user_input.switch_x = awaiting_input.light_x;
    /* The LED is placed 110 pixels below the top edge of the computer box. */
    user_input.light_y = BUFFER_HEIGHT + 110;
    /* The switch is placed 35 pixels below the LED. */
    user_input.switch_y = user_input.light_y + 35;
    /* We set the activity status of this just in case, even though we don't
       need it. */
    user_input.activity_status = 0;
    user_input.last_access_time = -1;

    /* Finally, we do the power switch, the "clear memory" switch and the
       "execute instructions" switch. */
    /* All of these LEDs and switches have the same x coordinate; 500 pixels
       in. */
    power_switch.light_x = clear_memory.light_x = execute_switch.light_x
	= power_switch.switch_x = clear_memory.switch_x 
	= execute_switch.switch_x = 500;
    /* The power switch is placed individually; the other y coordinates are
       based on pre-existing coordinates. */
    power_switch.light_y = BUFFER_HEIGHT + 20;
    power_switch.switch_y = power_switch.light_y + 30;
    clear_memory.light_y = address_switch[0].light_y + 10;
    clear_memory.switch_y = address_switch[0].switch_y;
    execute_switch.light_y = contents_switch[0].light_y;
    execute_switch.switch_y = contents_switch[0].switch_y;

    power_switch.activity_status = clear_memory.activity_status =
	execute_switch.activity_status = 0;
    power_switch.last_access_time = clear_memory.last_access_time =
	execute_switch.last_access_time = -1;
}

/* setup_screen: Sets graphics mode, then calls the setup_components() function
   to draw the screen. */
void setup_screen(void)
{
    /* Change video mode to 640x480 windowed */
    int ret = set_gfx_mode(GFX_AUTODETECT_WINDOWED, 640, 480, 0, 0);
    if (ret != 0) {
	allegro_message(allegro_error);
	return;
    }

    setup_components();
}

/* setup_components: Sets up all the individual graphical elements of the
   simulator. */
void setup_components(void)
{
    rectfill(screen, 0, 0, SCREEN_W, SCREEN_H, 0); /* Clear screen */

    /* Load bitmaps into memory */
    if (front_plate == NULL)
	front_plate = load_bitmap("front_plate.pcx", NULL);
    if (led_on == NULL)
	led_on = load_bitmap("led_on.pcx", NULL);
    if (led_off == NULL)
	led_off = load_bitmap("led_off.pcx", NULL);
    if (switch_on == NULL)
	switch_on = load_bitmap("switch_on.pcx", NULL);
    if (switch_off == NULL)
	switch_off = load_bitmap("switch_off.pcx", NULL);

    setup_front_plate();
    setup_accumulator();
    setup_memory_addresses();
    setup_memory_contents();
    setup_power_switch();
    setup_execute_switch();
    setup_clear_switch();
    setup_input_light();
    setup_uinput_switch();
}

/* setup_front_plate: Blits the front plate bitmap to the screen. */
void setup_front_plate(void)
{
    blit(front_plate, screen, 0, 0, 0, 115, SCREEN_W, 250);
}

/* setup_accumulator: Draws the accumulator lights in their default "off"
   state */
void setup_accumulator(void)
{
    int i;

    /* Blit the unlit LEDs to the screen in sequence. */
    for (i = 0; i < 12; i++)
	blit(led_off, screen, 0, 0, accumulator_led[i].light_x,
	     accumulator_led[i].light_y, LED_WIDTH, LED_HEIGHT);

    /* Print a label 5 pixels below the row of LEDs; 25 pixels below their
       top point. */
    textout_ex(screen, font, "ACCUMULATOR", 200,
	       accumulator_led[0].light_y + 25, 15, -1);
}

/* setup_memory_addresses: Draws the memory address lights and switches in their
   default "off" state */
void setup_memory_addresses(void)
{
    int i;

    /* Blit the unlit LEDs and switches to the screen in sequence. */
    for (i = 0; i < 8; i++) {
	blit(led_off, screen, 0, 0, address_switch[i].light_x,
	     address_switch[i].light_y, LED_WIDTH, LED_HEIGHT);
	blit(switch_off, screen, 0, 0, address_switch[i].switch_x,
	     address_switch[i].switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
    }

    /* Print a label 5 pixels below the row of LEDs; 25 pixels below their
       top point. */
    textout_ex(screen, font, "MEMORY ADDRESS", 200, 
	       address_switch[0].light_y + 25, 15, -1);
}

/* setup_memory_contents: Draws the address contents lights and switches in
   their default "off" state */
void setup_memory_contents(void)
{
    int i;

    /* Blit the unlit LEDs and switches to the screen in sequence. */
    for (i = 0; i < 12; i++) {
	blit(led_off, screen, 0, 0, contents_switch[i].light_x,
	     contents_switch[i].light_y, LED_WIDTH, LED_HEIGHT);
	blit(switch_off, screen, 0, 0, contents_switch[i].switch_x,
	     contents_switch[i].switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
    }

    /* Print a label 5 pixels below the row of LEDs; 25 pixels below their
       top point. */
    textout_ex(screen, font, "ADDRESS CONTENTS", 200, 
	       contents_switch[0].light_y + 25, 15, -1);
}

/* setup_power_switch: Draws the power toggle light and switch in their default
   "off" state */
void setup_power_switch(void)
{
    /* Blit the unlit LED and switch to the screen. */
    blit(led_off, screen, 0, 0, power_switch.light_x, power_switch.light_y,
	 LED_WIDTH, LED_HEIGHT);
    blit(switch_off, screen, 0, 0, power_switch.switch_x, power_switch.switch_y,
	 SWITCH_WIDTH, SWITCH_HEIGHT);

    /* Print a label 10 pixels beside the LED; 30 pixels to its leftmost point
       and 5 pixels below its top point. */
    textout_ex(screen, font, "POWER", power_switch.light_x + 30,
	       power_switch.light_y + 5, 15, -1);
}

/* setup_clear_switch: Draws the clear memory light and switch in their default
   "off" state */
void setup_clear_switch(void)
{
    /* Blit the unlit LED and switch to the screen. */
    blit(led_off, screen, 0, 0, clear_memory.light_x,
	 clear_memory.light_y, LED_WIDTH, LED_HEIGHT);
    blit(switch_off, screen, 0, 0, clear_memory.switch_x,
	 clear_memory.switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);

    /* Print a label 10 pixels beside the LED; 30 pixels to its leftmost point
       and 5 pixels below its top point. */
    textout_ex(screen, font, "CLEAR", clear_memory.light_x + 30,
	       clear_memory.light_y + 5, 15, -1);
    textout_ex(screen, font, "MEMORY", clear_memory.light_x + 30,
	       clear_memory.light_y + 15, 15, -1);
}

/* setup_execute_switch: Draws the execute instructions light and switch in
   their default "off" state */
void setup_execute_switch(void)
{
    /* Blit the unlit LED and switch to the screen. */
    blit(led_off, screen, 0, 0, execute_switch.light_x,
	 execute_switch.light_y, LED_WIDTH, LED_HEIGHT);
    blit(switch_off, screen, 0, 0, execute_switch.switch_x,
	 execute_switch.switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);

    /* Print a label 10 pixels beside the LED; 30 pixels to its leftmost point
       and 5 pixels below its top point. */
    textout_ex(screen, font, "EXECUTE", execute_switch.light_x + 30,
	       execute_switch.light_y + 5, 15, -1);
    textout_ex(screen, font, "INSTRUCTIONS", execute_switch.light_x + 30,
	       execute_switch.light_y + 15, 15, -1);
}

/* setup_input_light: Draws the input light in its default "off" state */
void setup_input_light(void)
{
    /* Blit the unlit LED to the screen. */
    blit(led_off, screen, 0, 0, awaiting_input.light_x,
	 awaiting_input.light_y, LED_WIDTH, LED_HEIGHT);

    /* Print a label 10 pixels below the LED; 30 pixels below its top point
       and 20 pixels left of its leftmost point. */
    textout_ex(screen, font, "AWAITING", awaiting_input.light_x - 20,
	       awaiting_input.light_y + 30, 15, -1);
    textout_ex(screen, font, "INPUT", awaiting_input.light_x - 20,
	       awaiting_input.light_y + 40, 15, -1);
}

/* setup_input_light: Draws the input light in its default "off" state */
void setup_uinput_switch(void)
{
    /* Blit the unlit LED and switch to the screen. */
    blit(led_off, screen, 0, 0, user_input.light_x,
	 user_input.light_y, LED_WIDTH, LED_HEIGHT);
    blit(switch_off, screen, 0, 0, user_input.switch_x,
	 user_input.switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);

    /* Print a label 10 pixels below the switch; 45 pixels below its top point
       and 20 pixels left of its leftmost point. */
    textout_ex(screen, font, "USER", user_input.switch_x,
	       user_input.switch_y + 45, 15, -1);
    textout_ex(screen, font, "INPUT", user_input.switch_x,
	       user_input.switch_y + 55, 15, -1);
}

/* initialise_memory: zeroes the contents of all mailboxes and the
   accumulator */
void initialise_memory(void)
{
    int i;

    /* Set mailbox contents appropriately to clear memory */
    for (i = 0; i < MAILBOXES; i++) {
	mailbox[i] = 0;
    }

    /* Clear accumulator contents */
    accumulator = 0;
}

/* get_input: receives and resolves user input from the keyboard */
void get_input(void)
{
    if (key[KEY_P])
	toggle_power();

    if (power_switch.activity_status == 1) {
	/* Toggle address switches */
	if (key[KEY_Q])
	    toggle_address_switch(0);

	if (key[KEY_W])
	    toggle_address_switch(1);

	if (key[KEY_E])
	    toggle_address_switch(2);

	if (key[KEY_R])
	    toggle_address_switch(3);

	if (key[KEY_T])
	    toggle_address_switch(4);

	if (key[KEY_Y])
	    toggle_address_switch(5);

	if (key[KEY_U])
	    toggle_address_switch(6);

	if (key[KEY_I])
	    toggle_address_switch(7);

	/* Toggle contents switches */
	if (key[KEY_A])
	    toggle_contents_switch(0, 't');

	if (key[KEY_S])
	    toggle_contents_switch(1, 't');

	if (key[KEY_D])
	    toggle_contents_switch(2, 't');

	if (key[KEY_F])
	    toggle_contents_switch(3, 't');

	if (key[KEY_G])
	    toggle_contents_switch(4, 't');

	if (key[KEY_H])
	    toggle_contents_switch(5, 't');

	if (key[KEY_J])
	    toggle_contents_switch(6, 't');

	if (key[KEY_K])
	    toggle_contents_switch(7, 't');

	if (key[KEY_Z])
	    toggle_contents_switch(8, 't');

	if (key[KEY_X])
	    toggle_contents_switch(9, 't');

	if (key[KEY_C])
	    toggle_contents_switch(10, 't');

	if (key[KEY_V])
	    toggle_contents_switch(11, 't');

	/* Toggle clear memory switch */
	if (key[KEY_DEL])
	    toggle_clear_switch();

	/* Toggle execute instructions switch */
	if (key[KEY_ENTER])
	    toggle_execute_switch();
    }
}

/* toggle_power: toggles power from on to off and vice versa; flips the switch
   and light status appropriately. */
void toggle_power(void)
{
    int i;

    /* Check if the switch was accessed in the last 300 milliseconds */
    if (power_switch.last_access_time < 0 || 	(clock() / (double) CLOCKS_PER_MS) - 	power_switch.last_access_time >= 300) {
	/* Set the new access time */
	power_switch.last_access_time = clock() / (double) CLOCKS_PER_MS;

	if (power_switch.activity_status == 0) {
	    /* Turn on power, change power switch activity status */
	    power_switch.activity_status = 1;
	    /* Turn on light, flip switch up */
	    blit(led_on, screen, 0, 0, power_switch.light_x,
		 power_switch.light_y, LED_WIDTH, LED_HEIGHT);
	    blit(switch_on, screen, 0, 0, power_switch.switch_x,
		 power_switch.switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
	} else {
	    /* Turn off power, change power switch activity status */
	    power_switch.activity_status = 0;
	    /* Clear memory, reset screen, set address counter to 0 */
	    initialise_memory();
	    setup_components();
	    address_counter = 0;
	    /* Set all of the contents and address switch activity statuses
	       back to 0 */
	    for (i = 0; i < 8; i++)
		address_switch[i].activity_status = 0;
	    for (i = 0; i < 12; i++)
		contents_switch[i].activity_status = 0;
	}
    }
}

/* toggle_address_switch: toggles the bit in the current address addressed by
 the switch from on to off and vice versa; flips the switch and light status
 appropriately. */
void toggle_address_switch(int toggle)
{
    /* Check if the switch was accessed in the last 300 milliseconds */
    if (address_switch[toggle].last_access_time < 0 || 	(clock() / (double) CLOCKS_PER_MS) - 	address_switch[toggle].last_access_time >= 300) {
	/* Set the new access time */
	address_switch[toggle].last_access_time =
	    clock() / (double) CLOCKS_PER_MS;

	if (address_switch[toggle].activity_status == 0) {
	    /* Change address switch activity status */
	    address_switch[toggle].activity_status = 1;
	    /* Turn on light, flip switch up */
	    blit(led_on, screen, 0, 0, address_switch[toggle].light_x,
		 address_switch[toggle].light_y, LED_WIDTH, LED_HEIGHT);
	    blit(switch_on, screen, 0, 0, address_switch[toggle].switch_x,
		 address_switch[toggle].switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
	} else {
	    /* Change address switch activity status */
	    address_switch[toggle].activity_status = 0;
	    /* Turn off light, flip switch down */
	    blit(led_off, screen, 0, 0, address_switch[toggle].light_x,
		 address_switch[toggle].light_y, LED_WIDTH, LED_HEIGHT);
	    blit(switch_off, screen, 0, 0, address_switch[toggle].switch_x,
		 address_switch[toggle].switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
	}

	/* Flip the bit of the program counter corresponding to the big-endian
	   position of the address switch */
	address_counter ^= 1 << (7 - toggle);
    }

    set_contents();
}

/* set_contents: Sets the positions of the memory contents switches correctly
   based on the current memory address */
void set_contents(void)
{
    int i;

    for (i = 0; i < 12; i++) {
	if (mailbox[address_counter] & (1 << (11 - i))) {
	    /* Change activity status appropriately */
	    contents_switch[i].activity_status = 1;
	    /* Turn on light, flip switch up */
	    blit(led_on, screen, 0, 0, contents_switch[i].light_x,
		 contents_switch[i].light_y, LED_WIDTH, LED_HEIGHT);
	    blit(switch_on, screen, 0, 0, contents_switch[i].switch_x,
		 contents_switch[i].switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
	} else {
	    /* Change activity status appropriately */
	    contents_switch[i].activity_status = 0;
	    /* Turn off light, flip switch down */
	    blit(led_off, screen, 0, 0, contents_switch[i].light_x,
		 contents_switch[i].light_y, LED_WIDTH, LED_HEIGHT);
	    blit(switch_off, screen, 0, 0, contents_switch[i].switch_x,
		 contents_switch[i].switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
	}
    }
}

/* toggle_contents_switch: Flips the switch and light status of the switch
 appropriately; depending on the mode, it may also toggle the bit in either
 the current memory address's contents or the temporary input storage buffer
 based on the switch. */
void toggle_contents_switch(int toggle, char mode)
{
    /* Check if the switch was accessed in the last 300 milliseconds */
    if (contents_switch[toggle].last_access_time < 0 || 	(clock() / (double) CLOCKS_PER_MS) - 	contents_switch[toggle].last_access_time >= 300) {
	/* Set the new access time */
	contents_switch[toggle].last_access_time =
	    clock() / (double) CLOCKS_PER_MS;

	if (contents_switch[toggle].activity_status == 0) {
	    /* Change activity status appropriately */
	    contents_switch[toggle].activity_status = 1;
	    /* Turn on light, flip switch up */
	    blit(led_on, screen, 0, 0, contents_switch[toggle].light_x,
		 contents_switch[toggle].light_y, LED_WIDTH, LED_HEIGHT);
	    blit(switch_on, screen, 0, 0, contents_switch[toggle].switch_x,
		 contents_switch[toggle].switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
	} else {
	    /* Change activity status appropriately */
	    contents_switch[toggle].activity_status = 0;
	    /* Turn off light, flip switch down */
	    blit(led_off, screen, 0, 0, contents_switch[toggle].light_x,
		 contents_switch[toggle].light_y, LED_WIDTH, LED_HEIGHT);
	    blit(switch_off, screen, 0, 0, contents_switch[toggle].switch_x,
		 contents_switch[toggle].switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
	}

	/* If mode is 't', flip the bit in the address contents corresponding to
	   the big-endian position of the switch.
	   If mode is 'a', do this for the bit in the temporary input store. */
	if (mode == 't')
	    mailbox[address_counter] ^= 1 << (11 - toggle);
	if (mode == 'a')
	    input_temp ^= 1 << (11 - toggle);
    }
}

/* toggle_clear_switch: Clears the contents of the mailbox contents; flips the
   clear switch up and down and turns the light on and off. */
void toggle_clear_switch(void)
{
    int i;

    /* Turn on light, flip switch up. Pause for effect */
    blit(led_on, screen, 0, 0, clear_memory.light_x,
	 clear_memory.light_y, LED_WIDTH, LED_HEIGHT);
    blit(switch_on, screen, 0, 0, clear_memory.switch_x,
	 clear_memory.switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
    rest(150);

    /* Clear contents of all mailboxes */
    for (i = 0; i < MAILBOXES; i++) {
	mailbox[i] = 0;
    }

    /* Change positions of address contents switches */
    set_contents();

    /* Turn off light, flip switch up */
    blit(led_off, screen, 0, 0, clear_memory.light_x,
	 clear_memory.light_y, LED_WIDTH, LED_HEIGHT);
    blit(switch_off, screen, 0, 0, clear_memory.switch_x,
	 clear_memory.switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
}

/* toggle_execute_switch: Calls the execute_instructions() function; keeps the
   switch flipped down and the light turned on until that function has
   finished. */
void toggle_execute_switch(void)
{
    /* Check if the switch was accessed in the last 300 milliseconds */
    if (execute_switch.last_access_time < 0 || 	(clock() / (double) CLOCKS_PER_MS) - 	execute_switch.last_access_time >= 300) {
	/* Set the new access time */
	execute_switch.last_access_time =
	    clock() / (double) CLOCKS_PER_MS;

	/* Turn on light, flip switch down. Pause for effect */
	blit(led_on, screen, 0, 0, execute_switch.light_x,
	 execute_switch.light_y, LED_WIDTH, LED_HEIGHT);
	blit(switch_on, screen, 0, 0, execute_switch.switch_x,
	 execute_switch.switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
	rest(200);

        execute_instructions();

	/* Turn off light, flip switch up. */
	blit(led_off, screen, 0, 0, execute_switch.light_x,
	 execute_switch.light_y, LED_WIDTH, LED_HEIGHT);
	blit(switch_off, screen, 0, 0, execute_switch.switch_x,
	 execute_switch.switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
    }
}

/* execute_instructions: Splits instructions into op codes and operands, then
   executes those instructions in accordance with the modified hexadecimal LMC
   rules of execution. */
void execute_instructions(void)
{
    int opcode = 0, operand = 0;
    int pc = 0;
    int i;
    FILE *ofp = fopen("lmc_output", "a");

    accumulator = 0;
    do {
	opcode = mailbox[pc] / (OP_SPLIT + 1);
	operand = mailbox[pc] & OP_SPLIT;
	/* Increment the program counter in advance; if it's a jump instruction,
	 the PC will be set manually. */
	++pc;

	switch(opcode) {
	case 0x1:
	    accumulator += mailbox[operand];
	    break;
	case 0x2:
	    accumulator -= mailbox[operand];
	    break;
	case 0x3:
	    mailbox[operand] = accumulator;
	    break;
	case 0x4:
	    break; /* Treat as NOP */
	case 0x5:
	    accumulator = mailbox[operand];
	    break;
	case 0x6:
	    pc = operand;
	    break;
	case 0x7:
	    /* If accumulator is zero, branch; otherwise, progress to next
	       instruction - treat as NOP. */
	    if (accumulator == 0)
		pc = operand;
	    break;
	case 0x8:
	    /* If accumulator is greater than or equal to zero, branch;
	       otherwise, progress to next instruction - treat as NOP. */
	    if (accumulator >= 0)
		pc = operand;
	    break;
	case 0x9:
	    if (operand == 0x1) {
		get_program_input();
		accumulator = input_temp;
	    } else if (operand == 0x2) {
		fprintf(ofp, "%3x\n", accumulator);
	    }
	    break;
	case 0x0:
	    set_accumulator(); /* Display accumulator contents */
	    fprintf(ofp, "----- INSTRUCTIONS COMPLETE -----\n");
	    fclose(ofp);
	    return;
	default:
	    break; /* All op codes outside of 0 - 9 are undefined.
		    * Treat as NOP. */
	}

	set_accumulator(); /* Display accumulator contents */

	/* Pause for effect, to enable accumulator lights to be seen in action.
	   May be changed or removed for a faster or slower simulation. */
	rest(INSTRUCTION_REST);

	if (key[KEY_ESC])
	    return; /* Allow the user to exit, e.g. from an infinite loop */
    } while (opcode != 0);
}

/* set_accumulator: Set the status of the accumulator lights based on the
   active bits in the accumulator "register" */
void set_accumulator(void)
{
    int i;

    /* Set accumulator lights based on the active bits in the accumulator */
    for (i = 0; i < 12; i++) {
	if (accumulator & 1 << (11 - i))
	    blit(led_on, screen, 0, 0, accumulator_led[i].light_x,
		 accumulator_led[i].light_y, LED_WIDTH, LED_HEIGHT);
	else
	    blit(led_off, screen, 0, 0, accumulator_led[i].light_x,
		 accumulator_led[i].light_y, LED_WIDTH, LED_HEIGHT);
    }
}

/* get_program_input: Allows entry of data into the temporary input storage
   buffer using the memory contents switches. */
void get_program_input(void)
{
    int i;

    /* Clear temporary input storage buffer */
    input_temp = 0;

    /* Clear all contents switches */
    for (i = 0; i < 12; i++) {
	contents_switch[i].activity_status = 0;
	blit(led_off, screen, 0, 0, contents_switch[i].light_x,
	     contents_switch[i].light_y, LED_WIDTH, LED_HEIGHT);
	blit(switch_off, screen, 0, 0, contents_switch[i].switch_x,
	     contents_switch[i].switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
    }

    /* Turn on "awaiting input" LED */
    blit(led_on, screen, 0, 0, awaiting_input.light_x, awaiting_input.light_y,
	 LED_WIDTH, LED_HEIGHT);

    /* Basically, keep taking contents entries while the Space key isn't pressed
       and the last access time period of 300 milliseconds hasn't been met. Yes,
       it's a very complex test. */
    for(;;) {
	/* Toggle contents switches */
	if (key[KEY_A])
	    toggle_contents_switch(0, 'a');

	if (key[KEY_S])
	    toggle_contents_switch(1, 'a');

	if (key[KEY_D])
	    toggle_contents_switch(2, 'a');

	if (key[KEY_F])
	    toggle_contents_switch(3, 'a');

	if (key[KEY_G])
	    toggle_contents_switch(4, 'a');

	if (key[KEY_H])
	    toggle_contents_switch(5, 'a');

	if (key[KEY_J])
	    toggle_contents_switch(6, 'a');

	if (key[KEY_K])
	    toggle_contents_switch(7, 'a');

	if (key[KEY_Z])
	    toggle_contents_switch(8, 'a');

	if (key[KEY_X])
	    toggle_contents_switch(9, 'a');

	if (key[KEY_C])
	    toggle_contents_switch(10, 'a');

	if (key[KEY_V])
	    toggle_contents_switch(11, 'a');

	/* I recognise that wrapping this test up in an infinite loop is bad
	   practice, but I couldn't get the last access time to work in the
	   main test of the while loop, and the key bounce issue from last
	   time was plaguing this part of the program again. */
	if (key[KEY_SPACE] && (user_input.last_access_time < 0 || 	(clock() / (double) CLOCKS_PER_MS) - 			       user_input.last_access_time >= 300))
	    break;

	/* We also need a way to escape from this part of the program
	   quickly, in order to allow exiting from all states in the program. */
	if (key[KEY_ESC])
	    return;
    }

    /* Set the last access time for the user input switch */
    user_input.last_access_time = clock() / (double) CLOCKS_PER_MS;

    /* Turn on light, flip switch down. Pause for effect */
    blit(led_on, screen, 0, 0, user_input.light_x,
	 user_input.light_y, LED_WIDTH, LED_HEIGHT);
    blit(switch_on, screen, 0, 0, user_input.switch_x,
	 user_input.switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);
    rest(200);

    /* Turn off light, flip switch up. */
    blit(led_off, screen, 0, 0, user_input.light_x,
	 user_input.light_y, LED_WIDTH, LED_HEIGHT);
    blit(switch_off, screen, 0, 0, user_input.switch_x,
	 user_input.switch_y, SWITCH_WIDTH, SWITCH_HEIGHT);

    /* Turn off the "awaiting input" LED */
    blit(led_off, screen, 0, 0, awaiting_input.light_x, awaiting_input.light_y,
	 LED_WIDTH, LED_HEIGHT);

    /* Reset the contents switches */
    set_contents();
}

Fundamentals of String Manipulation in C: Part 1

We’ve already seen arrays, which are chains of contiguous pointers to variables, and we’ve seen how we use them. There are arrays available of all data types, including integers of all lengths, floats, doubles and chars. A char array could be used to hold a series of characters corresponding to a word or sentence, as such:

#include <stdio.h>

int main(void)
{
    char word[] = {'f', 'o', 'o', 'b', 'a', 'r'};
    int i;
    for (i = 0; i < 6; i++)
	printf("%c", word[i]);
    printf("\n");
    return 0; /* Recall that main() returns this as an error code */
}

The array is defined with a series of characters, six in total, and the for loop goes through each character in sequence and prints it to the screen. This is, however, a cumbersome procedure and requires knowledge of the length of each individual character array. Because the manipulation of text in C is so common, there is a simpler, less cumbersome way of declaring and using arrays of characters, as illustrated below:

#include <stdio.h>

int main(void)
{
    /* Note that there are no curly brackets, and quotation marks are
    * used. */
    char word[] = "foobar";
    int i;
    for (i = 0; i < 6; i++)
	printf("%c", word[i]);
    printf("\n");
    return 0;
}

The format of the character array in this example is known as a string. Indeed, we’ve seen them before many times without explicitly referring to them as such; the printf() function takes arguments which are strings. Indeed, we can change the printf() arguments in this example to make it easier and less cumbersome:

#include <stdio.h>

int main(void)
{
    char word[] = "foobar";
    printf("%s\n", word);
    return 0;
}

This is much simpler to read, less dependent on knowing the length of the string and less error-prone. The question is, however, “How does printf() know when to stop printing?” The answer is that the word[] string isn’t just declared with the six characters in “foobar”, but also with a so-called null character, which is denoted using “”. Internally, printf() goes through the characters in the string until it reaches the null character, whereby the function terminates and returns.

There is another function in <stdio.h> which acts like printf() with a %s format specifier, and which is easier to remember and use. puts() takes a single argument, a character array, and prints it to the screen with a newline character at the end. This is illustrated below:

#include <stdio.h>

int main(void)
{
    char word[] = "foobar";
    puts(foobar);
    return 0;
}

As you can see, this is a cleaner way of printing strings to the screen than printf(), albeit without the flexibility. String printing is commonplace in text-based systems with C programming, and so puts() is often useful.

Now that we have a string, we might want to add it to another string. This can be done by declaring a larger character array which is large enough to accommodate all of the characters of both strings, and then copying the contents of both strings together. This can be illustrated with the following example:

#include <stdio.h>

int main(void)
{
    char word_1[] = "foobar";
    char word_2[] = "baz";
    char combined[10];
    int i = 0; j = 0;

    /* Continue going through the string until '' is reached */
    while (word_1[i] != '')
    {
	combined[i] = word_1[i];
	i++; /* Incrementing i goes to the next slot in memory for
	* both arrays */
    }
    /* i is now equal to the first empty element in combined */

    /* Starting again with a new counter variable */
    while (word_2[i] != '')
    {
	combined[i+j] = word_2[j];
	j++;
    }
    combined[i+j] = ''; 
    printf("%s\n", combined);
    return 0;
}

This will print out a string with the contents “foobarbaz”. The problem here, though, is that as above, with the definition of the character array using individual characters, is that this is complicated, cumbersome and error-prone. For this reason, several functions have been defined in the C standard library under the header file, <string.h>, which more cleanly deal with the manipulation of strings. The following program demonstrates some of them:

#include <stdio.h>
#include <string.h>

int main(void)
{
    char word_1[] = "foobar";
    char word_2[] = "baz";
    char combined[10];

    strcpy(combined, word_1);
    strcat(combined, word_2);
    puts(combined);
    return 0;
}

As you can see, this is a far cleaner way of defining these operations, without any need for explicit counters or anything else which would make the program more error-prone. Both strcpy() and strcat()take their arguments in the following form:
strcpy(destination, source);
strcat(destination, source);

strcpy() (standing for string copy) is used to copy the contents of one string to another, including the ” null character. strcat() (standing for string concatenate) is used to append the contents of one string onto the end of another; the word “concatenate” is merely a fancy way of saying “link

together”, in this case referring to joining two pieces of text together.

There are a number of other useful functions defined in <string.h> which are of note. strcmp() takes two strings and compares the characters in them. If the characters are exactly the same, the function returns 0; otherwise, it returns a positive or negative value depending on the difference in ASCII values between the first character that disagrees in both strings. strlen() returns the length of a string. Both functions are illustrated below:

#include <stdio.h>
#include <string.h>

int main(void)
{
    char word_1[]="hello";
    char word_2[]="world";
    char word_3[]="concatenate";

    /* Note the different values returned each time. */
    printf("The difference between word_1 and word_2 is %d\n",
    strcmp(word_1, word_2));

    printf("The difference between word_2 and word_1 is %d\n",
    strcmp(word_2, word_1));

    printf("The length of word_3 is %d\n", strlen(word_3));

    return 0;
}

This program returns the following results:

The difference between word_1 and word_2 is -15
The difference between word_2 and word_1 is 15
The length of word_3 is 11

This is consistent with the difference between ‘h’ and ‘w’ in the ASCII table; this is also consistent with the length of the word “concatenate”. These functions can therefore be used usefully when comparing text, which is a common task in the C programming language.

Using scanf(), we can write our own text into a character array as a string; however, this does not have any security against the characters overflowing the string and causing a segmentation fault. The use of scanf() to write into a string is illustrated below:

#include <stdio.h>

int main(void)
{
    char string[21]; /* 20 characters plus the null character. */

    /* Note that we don't use the & dereference operator here. */
    scanf("%s", string);
    printf("%s", string);
    return 0;
}

This will work successfully unless the characters entered are greater than 20; this will cause a segmentation fault and cause the program to halt unexpectedly. As with printf() and puts(), there is a function defined for entering characters specifically into a string called gets(). gets() is, however, considered dangerous and replacements are available in many extended C standard libraries; however, gets() is defined in ISO C90 and C99 and is available on all implementations of Standard C. It is illustrated below:

#include <stdio.h>

int main(void)
{
    char string[21];
    gets(string);
    puts(string);
    return 0;
}

Another thing to note is that strings, unlike character arrays defined with discrete characters, are not modifiable. Assignment statements cannot be used on a string or its elements. A function must therefore be used on the string in order to modify it.

Finally, there are a number of functions which are defined in <stdlib.h> which can be used to convert a string of characters with numerical values (i.e. ‘0’ to ‘9’) into integers, floats or doubles. atoi(), for example, (standing for ASCII to integer) converts a string consisting of such values, e.g. “1234” into an integer value. Other similar functions are also contained in <stdlib.h> and would be described in a reference of the C standard library (such as Appendix B of The C Programming Language (Kernighan & Ritchie, 2nd Edition, 1988)).