c++

An SSL Client Using OpenSSL

Recently I wrote about how to use OpenSSL to connect to a plain data server, this time I’m modifying the same code to perform encrypted connections.  Naturally this is more of an example for how to use the API than production ready code.  It’s main purpose is to show the very small difference between using the library as I did last time and how that example can be altered to create a basic SSL client.

The essential changes to the code below are the replacement of the connection function ‘connect_unencrypted(host_and_port)‘ with ‘connect_encrypted(host_and_port, store_path, store_type, &ctx, &ssl)‘ and the introduction of the SSL cleanup step ‘SSL_CTX_free(ctx)‘.  All other changes are purely cosmetic; which really shows how simple adding SSL to your application connections can be.  Externally you need to provide the root CA certificate for the connection to be verified by.  That’s it.

At this point I could warble through the connection function, but you should just read through it yourself and consult the SSL man pages.  Note that there is a dreadful buffer overflow possibility in this code and no real error handling, just a bit of logging.  This is to keep the example short and also because only you will know what valid handling should take place for each situation when you write your own code.

So take a look and enjoy.  To try this out yourself:

  1. Make sure that you have Firefox, GCC and OpenSSL (development sources and libraries) installed.
  2. Copy the following code to a file called ‘main.c‘ in a directory that you will be playing around in.
  3. Compile the code using ‘gcc main.c -o sslclient -lssl‘ if you are on Linux or ‘gcc main.c -o sslclient -lssl-lcrypto‘ if you are on OSX.
  4. Select an SSL (https) web site to connect to and find the Root CA’s certificate name in the site’s certificate.
  5. Either export the appropriate root CA from Firefox or obtain it directly from the CA online in pem format and copy it to a file ‘certificate.pem‘ in the same directory as the ‘sslclient‘ file.
  6. Run the following command:


'./sslclient servername:443 "GET / \r\n\r\n" certificate.pem f e'


/*
 * File:   main.cpp
 *
 * Licence: GPL2
 */

/* Standard headers */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/* OpenSSL headers */
#include <openssl/bio.h>
#include <openssl/ssl.h>
#include <openssl/err.h>

/**
 * Simple log function
 */
void slog(char* message) {
    fprintf(stdout, message);
}

/**
 * Print SSL error details
 */
void print_ssl_error(char* message, FILE* out) {

    fprintf(out, message);
    fprintf(out, "Error: %s\n", ERR_reason_error_string(ERR_get_error()));
    fprintf(out, "%s\n", ERR_error_string(ERR_get_error(), NULL));
    ERR_print_errors_fp(out);
}

/**
 * Print SSL error details with inserted content
 */
void print_ssl_error_2(char* message, char* content, FILE* out) {

    fprintf(out, message, content);
    fprintf(out, "Error: %s\n", ERR_reason_error_string(ERR_get_error()));
    fprintf(out, "%s\n", ERR_error_string(ERR_get_error(), NULL));
    ERR_print_errors_fp(out);
}

/**
 * Initialise OpenSSL
 */
void init_openssl() {

    /* call the standard SSL init functions */
    SSL_load_error_strings();
    SSL_library_init();
    ERR_load_BIO_strings();
    OpenSSL_add_all_algorithms();

    /* seed the random number system - only really nessecary for systems without '/dev/random' */
    /* RAND_add(?,?,?); need to work out a cryptographically significant way of generating the seed */
}

/**
 * Close an unencrypted connection gracefully
 */
int close_connection(BIO* bio) {

    int r = 0;

    r = BIO_free(bio);
    if (r == 0) {
        /* Error unable to free BIO */
    }

    return r;
}

/**
 * Connect to a host using an unencrypted stream
 */
BIO* connect_unencrypted(char* host_and_port) {

    BIO* bio = NULL;

    /* Create a new connection */
    bio = BIO_new_connect(host_and_port);
    if (bio == NULL) {

        print_ssl_error("Unable to create a new unencrypted BIO object.\n", stdout);
        return NULL;
    }

    /* Verify successful connection */
    if (BIO_do_connect(bio) != 1) {

        print_ssl_error("Unable to connect unencrypted.\n", stdout);
        close_connection(bio);
        return NULL;
    }

    return bio;
}

/**
 * Connect to a host using an encrypted stream
 */
BIO* connect_encrypted(char* host_and_port, char* store_path, char store_type, SSL_CTX** ctx, SSL** ssl) {

    BIO* bio = NULL;
    int r = 0;

    /* Set up the SSL pointers */
    *ctx = SSL_CTX_new(SSLv23_client_method());
    *ssl = NULL;

    /* Load the trust store from the pem location in argv[2] */
    if (store_type == 'f')
        r = SSL_CTX_load_verify_locations(*ctx, store_path, NULL);
    else
        r = SSL_CTX_load_verify_locations(*ctx, NULL, store_path);
    if (r == 0) {

        print_ssl_error_2("Unable to load the trust store from %s.\n", store_path, stdout);
        return NULL;
    }

    /* Setting up the BIO SSL object */
    bio = BIO_new_ssl_connect(*ctx);
    BIO_get_ssl(bio, ssl);
    if (!(*ssl)) {

        print_ssl_error("Unable to allocate SSL pointer.\n", stdout);
        return NULL;
    }
    SSL_set_mode(*ssl, SSL_MODE_AUTO_RETRY);

    /* Attempt to connect */
    BIO_set_conn_hostname(bio, host_and_port);

    /* Verify the connection opened and perform the handshake */
    if (BIO_do_connect(bio) < 1) {

        print_ssl_error_2("Unable to connect BIO.%s\n", host_and_port, stdout);
        return NULL;
    }

    if (SSL_get_verify_result(*ssl) != X509_V_OK) {

        print_ssl_error("Unable to verify connection result.\n", stdout);
    }

    return bio;
}

/**
 * Read a from a stream and handle restarts if nessecary
 */
ssize_t read_from_stream(BIO* bio, char* buffer, ssize_t length) {

    ssize_t r = -1;

    while (r < 0) {

        r = BIO_read(bio, buffer, length);
        if (r == 0) {

            print_ssl_error("Reached the end of the data stream.\n", stdout);
            continue;

        } else if (r < 0) {

            if (!BIO_should_retry(bio)) {

                print_ssl_error("BIO_read should retry test failed.\n", stdout);
                continue;
            }

            /* It would be prudent to check the reason for the retry and handle
             * it appropriately here */
        }

    };

    return r;
}

/**
 * Write to a stream and handle restarts if nessecary
 */
int write_to_stream(BIO* bio, char* buffer, ssize_t length) {

    ssize_t r = -1;

    while (r < 0) {

        r = BIO_write(bio, buffer, length);
        if (r <= 0) {

            if (!BIO_should_retry(bio)) {

                print_ssl_error("BIO_read should retry test failed.\n", stdout);
                continue;
            }

            /* It would be prudent to check the reason for the retry and handle
             * it appropriately here */
        }

    }

    return r;
}

/**
 * Main SSL demonstration code entry point
 */
int main(int argc, char** argv) {

    char* host_and_port = argv[1]; /* localhost:4422 */
    char* server_request = argv[2]; /* "GET / \r\n\r\n" */
    char* store_path = argv[3]; /* /home/user/projects/sslclient/certificate.pem */
    char store_type = argv[4][0]; /* f = file, anything else is a directory structure */
    char connection_type = argv[5][0]; /* e = encrypted, anything else is unencrypted */

    char buffer[4096];
    buffer[0] = 0;

    BIO* bio;
    SSL_CTX* ctx = NULL;
    SSL* ssl = NULL;

    /* initilise the OpenSSL library */
    init_openssl();

    /* encrypted link */
    if (connection_type == 'e') {

        if ((bio = connect_encrypted(host_and_port, store_path, store_type, &ctx, &ssl)) == NULL)
            return (EXIT_FAILURE);
    }
        /* unencrypted link */
    else if ((bio = connect_unencrypted(host_and_port)) == NULL)
        return (EXIT_FAILURE);

    write_to_stream(bio, server_request, strlen(server_request));
    read_from_stream(bio, buffer, 4096);
    printf("%s\r\n", buffer);

    if (close_connection(bio) == 0)
        return (EXIT_FAILURE);

    /* clean up the SSL context resources for the encrypted link */
    if (connection_type == 'e')
        SSL_CTX_free(ctx);

    return (EXIT_SUCCESS);
}

Non SSL Connections Using OpenSSL

Strange as it seems but you can make non-SSL connections using the OpenSSL libraries.  The following code is a brief example.  I like it because it appears to simplify (arguably) the rather more involved Berkley sockets.  It still lets you get at the socket if you want to mangle it yourself.  But ultimately its kind of handy to have a library that does SSL and plain transfers without too much of a code change.

Here is a simple example of using the OpenSSL BIO interface to retrieve a root web page.  Naturally most of the exception handling is not included so don’t going using it for production purposes as is.  Not that it’d be a lot of use as anything other than an exaple of the OpenSSL BIO API usage.

Have fun.


/*
 * File:   main.cpp
 *
 * Licence: GPL2
 */

/* Standard headers */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/* OpenSSL headers */
#include <openssl/bio.h>
#include <openssl/ssl.h>
#include <openssl/err.h>

/**
 * Initialise OpenSSL
 */
void init_openssl() {

    SSL_load_error_strings();
    ERR_load_BIO_strings();
    OpenSSL_add_all_algorithms();
}

/**
 * Close a BIO connection gracefully
 */
int close_connection(BIO* bio) {

    int r = 0;

    r = BIO_free(bio);
    if (r == 0) {
        /* Error unable to free BIO */
    }

    return r;
}

/**
 * Connect to a host using an unencrypted stream
 */
BIO* connect_unencrypted(char* host_and_port) {

    BIO* bio = NULL;

    /* Create a new connection */
    bio = BIO_new_connect(host_and_port);
    if (bio == NULL) {

        printf("Error: %s\n", ERR_reason_error_string(ERR_get_error()));
        printf("%s\n", ERR_error_string(ERR_get_error(), NULL));

        return NULL;
    }

    /* Verify successful connection */
    if (BIO_do_connect(bio) != 1) {

        printf("Error: %s\n", ERR_reason_error_string(ERR_get_error()));
        printf("%s\n", ERR_error_string(ERR_get_error(), NULL));

        close_connection(bio);
        return NULL;
    }

    return bio;
}

/**
 * Read a from a stream and handle restarts if nessecary
 */
ssize_t read_from_stream(BIO* bio, char* buffer, ssize_t length) {

    ssize_t r = -1;

    while (r < 0) {

        r = BIO_read(bio, buffer, length);
        if (r == 0) {

            /* Handle closed connection */
            continue;

        } else if (r < 0) {

            if (!BIO_should_retry(bio)) {

                /* Handle failed read here */

                printf("Error: %s\n", ERR_reason_error_string(ERR_get_error()));
                printf("%s\n", ERR_error_string(ERR_get_error(), NULL));

                continue;
            }

            /* It would be prudent to check the reason for the retry and handle
             * it appropriately here */
        }

    };

    return r;
}

/**
 * Write to a stream and handle restarts if nessecary
 */
int write_to_stream(BIO* bio, char* buffer, ssize_t length) {

    ssize_t r = -1;

    while (r < 0) {

        r = BIO_write(bio, buffer, length);
        if (r <= 0) {

            if (!BIO_should_retry(bio)) {

                /* Handle failed write here */
                printf("Error: %s\n", ERR_reason_error_string(ERR_get_error()));
                printf("%s\n", ERR_error_string(ERR_get_error(), NULL));

                continue;
            }

            /* It would be prudent to check the reason for the retry and handle
             * it appropriately here */
        }

    }

    return r;
}

/**
 * Main SSL demonstration code entry point
 */
int main(int argc, char** argv) {

    BIO * bio;
    char *addr = "GET / HTTP/1.1\r\nHost: www.home.com\r\n\r\n";
    char buffer[4096];
    buffer[0] = 0;

    init_openssl();

    if ((bio = connect_unencrypted(argv[1])) == NULL)
        return (EXIT_FAILURE);

    write_to_stream(bio, addr, strlen(addr));
    read_from_stream(bio, buffer, 4096);
    printf("%s", buffer);

    if (close_connection(bio) == 0)
        return (EXIT_FAILURE);

    return (EXIT_SUCCESS);
}

A Brief Linux Sockets Connect Illustration

For a little while I’ve been playing with sockets in C now and have come up with the following succinct example of connecting.  Note that the connection is fairly flexible with regards to protocol and transport type.  It really is simply there to make the connection to somewhere else with as few questions asked.  It will involve DNS and service lookups if you provide names instead of the network address and port.  If you want to catch exceptions you need to clear the standard error variable and check it yourself after receiving a fail return value.  It won’t, or at least shouldn’t, report any exceptions because for my current purposes failures are not really exceptions just dead ends on some of many paths.  I tried to keep it simple too, have fun.


/* connect_to_socket
 *
 * connect to a socket using an initialised addrinfo structure,
 *
 * info is an initialised addrinfo structure
 * sock is a pointer to the location to store the socket descriptor when opened
 *
 * returns 0 if successful
 */
int connect_to_socket(const struct addrinfo *info, int* sock) {

    /* open socket */
    *sock = socket(info->ai_family, info->ai_socktype, info->ai_protocol);
    if (*sock < 1) return -1;

    /* connect to the server*/
    if (connect(*sock, info->ai_addr, info->ai_addrlen) == 0)
        return 0;

    /* clean up on failure */
    close(*sock);
    return -1;
}

/* connect_to_server
 *
 * connect to a server using the server name or adress and port or service name
 *
 * server is a string containing either the name or address of the server
 * port is a string containing either the service name or port number to use
 * sock is a pointer to the location to store the socket descriptor when opened
 *
 *  returns 0 if successful
 */
int connect_to_server(const char* server, const char* port, int* sock) {

    struct addrinfo hints, *info = NULL, *list = NULL;
    int e = 0;

    /* initialise the hints for retrieving the address details */
    memset(&hints, 0, sizeof (hints));
    hints.ai_family = AF_UNSPEC;
    hints.ai_socktype = SOCK_STREAM;
    hints.ai_flags = AI_PASSIVE;
    hints.ai_protocol = 0;

    /* get the address if the server to connect to */
    e = getaddrinfo(server, port, &hints, &list);
    if (e != 0) return -1;

    /* connect to the first socket in the list */
    for (info = list; info != NULL; info = info->ai_next)
        if (connect_to_socket(info, sock) == 0)
            break;

    /* clean up and return */
    if (list != NULL) freeaddrinfo(list);
    if (sock > 0) return 0;
    else return -1;
}

When there’s Nothing in your Sock

Normally I do most of my network programming in Java; life is just easier that way. But some times, *very* rarely, you need to carve up a little C.  So I’ve not touched socket networking for a while and all its foibles.  Hence a few problems with reading from a socket.

When socket programming with the ‘read’ function it does not always return the length read into the buffer.  In fact if you are talking to an HTTP server a ‘GET /‘ will nearly always end with read returning 0.  This is because the socket will have been closed on your last read.  This of course begs the question, how do you know how much was read in the last read?  For me this was simple; I just zero filled the buffer prior to reading.


ssize_t r_read(int sock, void* buf, size_t size)
{
        ssize_t ret;
        bzero(buf, size);
        while (ret = read(sock, buf, size - 1), ret == -1 && errno == EINTR);
        return ret;
}


Which does work because now its a simple matter of counting until the first 0 shows up, but I’d still like to know how to tell how many characters were read without having to do the count. This becomes more important when transferring binary files as you won’t know if the 0 is validly part of the file or not.


Hex Translation of a char Buffer to a hex char Buffer

Some time ago I wrote up a hex2bin and a bin2hex utility in this blog.  This is an example of my hint in the comments in that blog as I’ve seen quite a few rather hashed attempts and it is really dauntingly simple.  I didn’t think that I needed to write it!  Note there’s no real error checking here because it has not been written to fit a particular purpose, so be careful. Somewhat interestingly this code runs faster compiled by a C compiler as opposed to a C++ compiler.

/**
 * char_to_hex_buf
 *
 * Takes a char buffer (s) of length l and inserts the ascii representation
 * of the hex values into the provided hex char buffer (h) of length lx2+1
 * terminating the hex buffer with '\0' in the final position of h[l].
 *
 * h - preallocated char buffer of length lx2+1 to put the translated source
 *     buffer hex character contents into
 * s - source char buffer of length l containing the characters to return as
 *     a hex character string the '\0' character is not a terminator for the
 *     purposes of this string
 * l - length of the source string
 *
 * returns EXIT_SUCCESS no other return value makes sense
 */
int char_to_hex_buf(char *h, const size_t l, const char *s) {

	size_t c;

	for (c=0;c<l;c++)
		sprintf(&(h[c*2]),"%02X",(unsigned char)(s[c]));

	return EXIT_SUCCESS;
}

Simple Berkeley Sockets C Server Example

About Apache and Bloat

Every now and then I look at Apache and wonder about its size and complexity. Its a huge beastie now but absolutely brilliant too. I have quite a respect for it as do many around the world. But then I don’t really use very much of its functionality.

Sure its been re-factored into a modular form so that you only need to use the bits that you want but it still presents a mental preponderance thatmany would consider bloat.  But bloat is a term used to describe software that has vast wads of unnessecary code that could be accomplished more simply.  However Idon’t think that Apache has that.  All of its code seems very purposeful, and as I indicated earlier it is reasonably easy to include or exclude as you will.

Introducing the Example

So this example is not here to show you the right way of doing things, but rather how simple the solution to you particular problem could be.  In this case the example server simply serves up the time on the server machine to port 6543 for any client and then closes the stream.  It can do this for many concurrent connections at once given the only complexity that is added to the server is client handling by forked process.

Now to the Code

/* -----------------------------------------------------------------------------

	simple example of a server in C using very simple Berkeley sockets 

	This is just an example for looking at.  Not really how you would actually
	implement a server.  For a start it does not take care of signals and isn't
	capable of being implemented as a service.

----------------------------------------------------------------------------- */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <strings.h>
#include <arpa/inet.h>

/* we're not going to use arguments for this example */

#define SERV_UDP_PORT 6543
#define SERV_TCP_PORT 6543
#define SERV_HOST_ADDR "192.168.2.200"

int main (int argc, char ** argv, char ** env) {

	int socket_server, socket_client, child_pid;
	struct sockaddr_in address_client, address_server;
	socklen_t client_address_size;
	FILE *stream_client;
	time_t now;
	struct tm *tm;

	/* open a tcp socket to listen on */

	if ( (socket_server = socket(AF_INET, SOCK_STREAM, 0) ) < 0)
		err_dump("server: can't open stream socket");

	/* bind to our local address  ans start listening so that clients can find us */

	bzero((void *) &address_server, (size_t)sizeof(address_server));

	address_server.sin_family = AF_INET;
	address_server.sin_addr.s_addr = htonl(INADDR_ANY);
	address_server.sin_port = htons(SERV_TCP_PORT);

	if (bind(
		socket_server,
		(struct sockaddr *) &address_server,
		sizeof(address_server))
			< 0)
		err_dump("server: can't bind local address");

	listen(socket_server, 5);

	for ( ; ; ) {

		/* wait for client connection and accpt it when it comes */

		client_address_size = sizeof(address_client);
		socket_client = accept(
				socket_server,
				(struct sockaddr *) &address_client,
				&client_address_size);

		if (socket_client < 0)
			err_dump("server: accept error");

		if ( (child_pid = fork() ) < 0)
			err_dump("server: fork error");

		/* specific client process handling starts here */

		else if (child_pid == 0) {

			/* client process has no need of the server socket */

			close(socket_server);

			/* generate a file stream from the client socket */

			if ((stream_client = fdopen(socket_client, "w")) == NULL) {
				perror("daytimed fdopen");
				return 5;
			}

			/* write to the client stream as per normal then close it */

        		if ((now = time(NULL)) < 0) {
            			perror("daytimed time");

            			return 6;
        		}

        		tm = gmtime(&now);
        		fprintf(stream_client, "%.4i-%.2i-%.2iT%.2i:%.2i:%.2iZ\n",
           			 tm->tm_year + 1900,
           			 tm->tm_mon + 1,
            			tm->tm_mday,
           			 tm->tm_hour,
           			 tm->tm_min,
            			tm->tm_sec);

        		fclose(stream_client);

			exit(EXIT_SUCCESS);

			/* client process has left the building */
		}

		/* the server has no need to keep the client socket open */

		close(socket_client);
	}

	return 0;
}

Rewriting the Wheel: bin2hex – hex2bin

Yep everybody does it; repetition.  In the grand old days of old we all rebuilt the wheel leading to the establishment of patterns.  For me patterns often help me get to achieve my goals faster than using Google.  Using Google to find simple tools normally means understanding the search engine, browsing the results and evaluating each alternative in turn.  Invariably this means slightly altering someone else’s code, compromising objectives or installing a bulky tool that is bloated by a thousand functions you don’t need or want.  Naturally this last list is not exhaustive; just consider the dependencies that an external solution often requires.  If its simple and quick its often better to reinvent your wheel.

A perennial favuorite of mine is base translation; specifically hexadecimal to binary and binary to hexidecimal.  This is so simple and so useful it’s the subject of thousands of Google results.  Yet the useful bits are rarely on the first page of results.  So I coded it in about 30 minutes, and debugged it in about 30 minutes – because I was tired at the time.  Interestingly this is not the first time that I’ve written this code.  My earliest recollection of having written it was about 1986 over 22 years ago.  Of course it was coded in basic at the time on an Atari, however it wasn’t too long before I started translating it into C.

Patterns have long been a formal word in Computer Science.  In 1996 a very famous book, the name of which escapes me now and I’m too lazy to get it off my shelf, was dedicated to the development of patterns in software development.  Interestingly the way that the patterns were described was almost a deterent to the patterns themselves.  Being of academic nature the usefulness of the book was somewhat tarnished by its lack of pragmatic style and appeal to the great unwashed.  Its a fantastic book though which every software engineer should read.

For me patterns are best expressed in real world examples and in the languages that I understand.  It makes them instantly availble to me and much more likely to improve my work.  Yes they do need some formal definition most of the time.  However if its so simple as to be obvious then don’t clutter the example with an explanation other than to say what you used it for.  If its really that useful to be made into a pattern it’ll resurface again in the form of ‘now what did I do with that code I wrote 22 years ago that solved this problem?’

Well here it is, I used it to translate a Hexadecimal network packet lifted from an application log back into binary so that it could be replayed over a network for testing the application time and again.  Note the use of redirected standard input and output; its clean – no Swiss army knife in this one, what would I need a spoon on it for anyway?

hex2bin.c

#include "stdio.h"

#include "stdlib.h"

int main( int argc, char ** argv, char ** env ) {

  char h = '0';
  FILE * fi = stdin;
  FILE * fo = stdout;

  if ( argc > 1 ) {

    printf( "Usage: redirect input and output to stdin and stdout respectively.\n" );
    return 0;
  }

  h = getc( fi );

  while ( h != EOF ) {

    char b = 0;

    if ( h - '0' < 10 ) b = h - '0';
    else if ( h - 'a' < 'g' - 'a' ) b = ( h - 'a' ) + 10;
    else if ( h - 'A' < 'G' - 'A' ) b = ( h - 'A' ) + 10;

    b = b << 4;

    h = getc( fi );
    if ( h == EOF ) return 0;

    if ( h - '0' < 10 ) b += h - '0';
    else if ( h - 'a' < 'g' - 'a' ) b += ( h - 'a' ) + 10;
    else if ( h - 'A' < 'G' - 'A' ) b += ( h - 'A' ) + 10;

    if ( putc( b, fo ) == EOF ) return 0;

    h = getc( fi );
  }

  return 0;

}

Of course in this case it was just too tempting to write it’s sister as well: binary to hex. If you combine these two tools on the command line with netcat and some other favourite script favourites you can make quite a useful test tool.

bin2hex.c

#include "stdio.h"

#include "stdlib.h"

int main( int argc, char ** argv, char ** env ) {

  char b = '0';
  FILE * fi = stdin;
  FILE * fo = stdout;

  if ( argc > 1 ) {

    printf( "Usage: redirect input and output to stdin and stdout respectively.\n" );
    return 0;
  }

  b = getc( fi );

  while ( b != EOF ) {

    char h = 0;

    h = b >> 4;
    if ( h < 10 ) h = h + '0';
    else if ( h < 16 ) h = h + 'a';
    if ( putc( h, fo ) == EOF ) return 0;

    h = b & 0x0f;
    if ( h < 10 ) h = h + '0';
    else if ( h < 16 ) h = h + 'a';
    if ( putc( h, fo ) == EOF ) return 0;

    b = getc( fi );
  }

  return 0;

}

Lastly there is a point that is quite good to note about such simple patterns: they make really a really good basis for recruitment tests. You can always tell how good an organisation is in recruitment by the quality of this process. If they complain about spelling it generally means that the organisation is focussed on minutia and micro-management is probably the order of the day. Normally that’s a warning sign. So I always include spelling mistakes in my submissions. However if you are asked about the various ways of implementing the illustrated code (once of course you’ve rewritten it for them from requirements!) and integration strategies, impact on speed, memory usage along with testing and comparison of the requirements provided you’re probably to a good thing.

So just for fun let’s look at one aspect of this. IF you go do that dreaded Google search and sift through the cruft out there you will find a very specific approach often used that is quite different to that which I’ve used above to determine binary or hex value in translation; it normally involves using a switch statement like this:

char h;
int b;

switch ( h ) {
  '0'  :  b = 0;
          break;
  '1'  :  b = 1;
          break;
  '2'  :  b = 2;
          break;
  '3'  :  b = 3;
          break;
  '4'  :  b = 4;
          break;
  '5'  :  b = 5;
          break;
  '6'  :  b = 6;
          break;
  '7'  :  b = 7;
          break;
  '8'  :  b = 8;
          break;
  '9'  :  b = 9;
          break;
  'A'  :
  'a'  :  b = 10;
          break;
  'B'  :
  'b'  :  b = 11;
          break;
  'C'  :
  'c'  :  b = 12;
          break;
  'D'  :
  'd'  :  b = 13;
          break;
  'E'  :
  'e'  :  b = 14;
          break;
  'F'  :
  'f'  :  b = 15;
          break;
  default : return -1;
}

All this seems reasonable. Yes its going to be bigger than my code but its going to be quicker right? Actually that’s not right. You see the code is larger so its going to take a larger number of get requests to the memory. My code is small enough to fit inside most modern processor’s register sets not even touching the processor cache which the static example just given would have to sit in. Next the compiler on average will make twice the number of comparisons to jump into the switch statement, than the corresponding number of operations for my version. But this is also compiler and processor dependent. Coding simply in this case makes the optimiser’s job easier but an optimiser normally doesn’t have the nous to translate the code to another approach, just apply obvious short cuts to the code already presented. Naturally this could lead into discussions about optimisers and their abilities and limitations.

In fact there are a large number of optimisations that could be made to my code that would improve its performance too. But I’ll stop here because I could write a book on this one piece of code. So you see a particularly innocuous, been-done-before, simple piece of code can be interesting and be used to draw out the depth of a person’s knowledge. Plus there’s a certain amount of satisfaction in being able to go back an polish old code, it’s like visiting an old friend.


C++ Valarray Matrix Madness

Numeric STL container valarray began life partially as an attempt to make C++ appealing to the supercomputing community. At the time the big thing in those big machines was, the ironically named, vector processing. However the valarray fell by the wayside as the people driving its development left the STL development group. Perhaps they realised that it didn’t really fit 100% with the STL, or maybe they just got sidetracked; who knows. But it is still useful, and here are a few reasons why:

  • Can be used to write faster code for numeric spaces than possible with other STL types like the ubiquitous vector template.
  • Offers the coder the possibility of staying within the comfort zone of the STL and familiar object oriented concepts with a small speed sacrifice over hand carved C.
  • Allows library developers a way of writing optimized libraries for different environments so that coder can concentrate on the development at hand and not loose track in the complexity of the target environment.

So I’ve been playing around with valarray. It seemed that the best example to play with is that old classic the matrix. So here it is. Yes I know that there are some particularly hairy things wrong with it, but its not meant as a copy and paste solution. Its here as the results of a learning exercise and an example of what’s possible with valarray. There are one or two places which are not implemented or have not been tested, but you should be able to complete or test these by just looking at the rest of the examples. It should compile and run as is.

Have a look and have fun.

#include <fstream>
#include <iostream>
#include <iterator>
#include <string>
#include <valarray>
#include <vector>

/*------------------------------------------------------------------------------
  matrix2d interface

  This is the template for the matrix class.  Its not that fancy and there could
  be a lot more added to it but that was not the point of the exercise.  It is
  also limited by the number of types supported by the underlying valarray data
  container.  From an OO point of view its really not that good either given
  that a lot of the manipulation or generator methods really don't need to have
  access directly to the data part of the construct.  However on a practical
  basis including those methods in this class provide small benefits in speed
  and allow things to be a little more obvious.  There are also problems in the
  way that the generators return new matrix2d objects.  But I've no intention to
  fix them as this was just a learning exercise.  I've tossed the implementation
  of the methods into seperate compilation objects to make the interface cleaner
  for inspection purposes.  In keeping with the valarray perspective there is no
  bounds checking anywhere - you have been warned.
  ----------------------------------------------------------------------------*/

template<ypename T>

class matrix2d {
public:

  // creates based on the rows and data size
  matrix2d(std::size_t rows, std::valarray<T> data);
  // creates an empty rows x size matrix
  matrix2d(std::size_t rows, std::size_t cols);
  // direct initialisation - beware that rows x cols must equal data.size()
  matrix2d(std::size_t rows, std::size_t cols, std::valarray<T> data);

  // get the number of rows in the matrix2d
  std::size_t rows() const;
  // get the number of columns in the matrix2d
  std::size_t cols() const;
  // get a copy of the data in the matrix2d
  std::valarray<T> array() const;

  // retrieve the data from row r of the matrix
  std::valarray<T> row(std::size_t r) const;
  // retrieve the data from col c of the matrix
  std::valarray<T> col(std::size_t c) const;

  // retrieve refernce to the data from row r of the matrix
  std::slice_array<T> row(std::size_t r);
  // retrieve refernce to the data from col c of the matrix
  std::slice_array<T> col(std::size_t c);

  // basic item reference
  T & operator()(std::size_t r, std::size_t c);
  // basic item retrieval
  T operator()(std::size_t r, std::size_t c) const;

  // generate a matrix sort each row then sort the rows - UNIMPLEMENTED
  matrix2d<T> sort();
  // genetate a new matrix that is the transposition of this one
  matrix2d<T> transpose();
  // generate a new matrix with this matrix's data and sort each row
  matrix2d<T> rowItmSort();
  // generate a new matrix with this matrix's data and sort each row in reverse
  matrix2d<T> rowItmSortRev();
  // generate a new matrix with this matrix's data and sort each col
  matrix2d<T> colItmSort();
  // generate a new matrix with this matrix's data and sort each col in reverse
  matrix2d<T> colItmSortRev();

  // generate a new matrix of this one with m appended below
  matrix2d<T> appendRows(matrix2d<T> &m);
  // generate a new matrix of this one with m appended to the right
  matrix2d<T> appendCols(matrix2d<T> &m);
  // generate a matrix of this one, upper left corner at row t col l - UNTESTED
  matrix2d<T> extractMatrix2d(size_t t, size_t l, size_t w, size_t h);

protected:

  std::size_t rows_;
  std::size_t cols_;
  std::valarray<T> data_;

};

/*------------------------------------------------------------------------------
  matrix2d implementation
  ----------------------------------------------------------------------------*/

/*------------------------------------------------------------------------------
  matrix2d constructors
  ----------------------------------------------------------------------------*/

template<class T>
matrix2d<T>::matrix2d(std::size_t rows, std::valarray<T> data) :
rows_(rows), cols_(data.size() / rows), data_(data) {}

template<class T>
matrix2d<T>::matrix2d(std::size_t rows, std::size_t columns) :
rows_(rows), cols_(columns), data_(rows * columns) {}

template<class T>
matrix2d<T>::matrix2d(std::size_t rows, std::size_t columns,
std::valarray<T> data) :
rows_(rows), cols_(columns), data_(data) {}

/*------------------------------------------------------------------------------
  matrix2d operations
  ----------------------------------------------------------------------------*/

template<class T>
std::size_t matrix2d<T>::rows() const {
  return rows_;
}

template<class T>
std::size_t matrix2d<T>::cols() const {
  return cols_;
}

template<class T>
std::valarray<T> matrix2d<T>::array() const {
  return data_;
}

template<class T>
std::valarray<T> matrix2d<T>::row(std::size_t r) const {
  return data_[std::slice(r * cols(), cols(), 1)];
}

template<class T>
std::valarray<T> matrix2d<T>::col(std::size_t c) const {
  return data_[std::slice(c, rows(), cols())];
}

template<class T>
std::slice_array<T> matrix2d<T>::row(std::size_t r) {
  return data_[std::slice(r * cols(), cols(), 1)];
}

template<class T>
std::slice_array<T> matrix2d<T>::col(std::size_t c) {
  return data_[std::slice(c, rows(), cols())];
}

template<class T>
T& matrix2d<T>::operator()(std::size_t r, std::size_t c) {
  return data_[r * cols() + c];
}

template<class T>
T matrix2d<T>::operator()(std::size_t r, std::size_t c) const {
  return row(r)[c];
}

/*------------------------------------------------------------------------------
  matrix2d generators
  ----------------------------------------------------------------------------*/

template<class T>
matrix2d<T> matrix2d<T>::sort() {

  matrix2d<T> result(rows_, cols_);

  /* TO DO TO DO TO DO TO DO TO DO TO DO TO DO TO DO TO DO TO DO TO DO TO DO */

  return result;
}

template<class T>
matrix2d<T> matrix2d<T>::transpose() {

  matrix2d<T> result(cols_, rows_);

  for (std::size_t i = 0; i < rows_; ++i)
    result.col(i) = static_cast<std::valarray<T> > (row(i));

  return result;
}

template<class T>
matrix2d<T> matrix2d<T>::rowItmSort() {

  matrix2d<T> result(rows_, cols_);

  for (std::size_t i = 0; i < rows_; ++i) {

    std::valarray<T> x = static_cast<std::valarray<T> > (row(i));
    std::sort(&x[0], &x[cols_]);
    result.row(i) = x;
  }

  return result;
}

template<class T> bool rev (const T & a, const T & b) { return a > b; }

template<class T>
matrix2d<T> matrix2d<T>::rowItmSortRev() {

  matrix2d<T> result(rows_, cols_);

  for (std::size_t i = 0; i < rows_; ++i) {

    std::valarray<T> x = static_cast<std::valarray<T> > (row(i));
    std::sort(&x[0], &x[cols_], rev<T>);
    result.row(i) = x;
  }

  return result;
}

template<class T>
matrix2d<T> matrix2d<T>::colItmSort() {

  matrix2d<T> result(rows_, cols_);

  for (std::size_t i = 0; i < cols_; ++i) {

    std::valarray<T> x = static_cast<std::valarray<T> > (col(i));
    std::sort(&x[0], &x[rows_]);
    result.col(i) = x;
  }

  return result;
}

template<class T>
matrix2d<T> matrix2d<T>::colItmSortRev() {

  matrix2d<T> result(rows_, cols_);

  for (std::size_t i = 0; i < cols_; ++i) {

    std::valarray<T> x = static_cast<std::valarray<T> > (col(i));
    std::sort(&x[0], &x[rows_], rev<T>);
    result.col(i) = x;
  }

  return result;
}

template<class T>
matrix2d<T> matrix2d<T>::appendRows(matrix2d<T> &m) {

  matrix2d<T> result(rows_ + m.rows_, cols_);

  result.data_[std::slice(0, rows_ * cols_, 1)] = data_;
  result.data_[std::slice(rows_ * cols_, m.rows_ * m.cols_, 1)] = m.data_;

  return result;
}

template<class T>
matrix2d<T> matrix2d<T>::appendCols(matrix2d<T> &m) {

  matrix2d<T> result(rows_, cols_ + m.cols_);

  std::size_t s1[] = {rows_,cols_}; // shape of left matrix
  std::size_t p1[] = {result.cols_,1}; // position of left matrix in result
  std::size_t s2[] = {m.rows_,m.cols_}; // shape of right matrix
  std::size_t p2[] = {result.cols_,1}; // position or right matrix in result

  std::valarray<std::size_t> sv1(s1, 2);
  std::valarray<std::size_t> pv1(p1, 2);
  std::valarray<std::size_t> sv2(s2, 2);
  std::valarray<std::size_t> pv2(p2, 2);

  result.data_[std::gslice(0, sv1, pv1)] = data_; // copy left matrix into place
  result.data_[std::gslice(cols_, sv2, pv2)] = m.data_; // repeat for m

  return result;
}

template<class T>
matrix2d<T> matrix2d<T>::extractMatrix2d(size_t x, size_t y, size_t w,
size_t h) {

  /* TEST ME TEST ME TEST ME TEST ME TEST ME TEST ME TEST ME TEST ME TEST ME */

  matrix2d<T> result(h, w);

  size_t x2[] = {h, w}, s[] = {rows_, 1};
  std::valarray<size_t> xa(x2, 2), sa(s, 2);

  result.data_ = data_[(const std::gslice)std::gslice(y * rows_ + x, xa, sa)];

  return result;
}

/*------------------------------------------------------------------------------
  matrix2d general input output

  This is a simple class to help collect methods of serialising the matrix2d
  data forms.  Really they should be done another way but once again I don't
  really care as they are throw away code for the purpoese of demonstration
  only.
  ----------------------------------------------------------------------------*/

template<typename T>

class matrix2dio {
public:

  matrix2d<T> textToM2d(std::istream & is, size_t w);
  matrix2d<T> fileToM2d(std::string file, size_t w);
  void m2dToText(std::ostream & os, const matrix2d<T> & m);
  void printValarray(std::ostream & os, const std::valarray<int> & va);
};

/*------------------------------------------------------------------------------
  matrix2dio operations
  ----------------------------------------------------------------------------*/

typedef std::istream_iterator<int> int_istrm_iter;

template<class T>
matrix2d<T> matrix2dio<T>::textToM2d(std::istream & is, size_t w) {

  std::vector<T> v;
  std::valarray<T> a;

  if (!is.good() || is.eof())
    return;

  copy(int_istrm_iter(is), int_istrm_iter(), back_inserter(v));
  a.resize(v.size(), sizeof ( int));
  copy(v.begin(), v.end(), &a[0]);

  return new matrix2d<T > (w, a);
}

template<class T>
matrix2d<T> matrix2dio<T>::fileToM2d(std::string file, size_t w) {

  std::filebuf fb;
  std::istream is(&fb);

  fb.open(file.c_str(), std::ios::in);
  matrix2d<T> m = textToM2d(is, w);
  fb.close();

  return m;
}

template<class T>
void matrix2dio<T>::m2dToText(std::ostream & os, const matrix2d<T> & m) {

  size_t i = 0, j = 0;

  for (i = 0; i < m.rows(); i++) {

    std::valarray<T> r = m.row(i);
    os << r[0];

    for (j = 1; j < m.cols(); j++)
      std::cout << ' ' << r[j];

    os << '\n';
  }

  os << std::flush;
}

template<class T>
void matrix2dio<T>::printValarray(std::ostream & os,
const std::valarray<int> & va) {

  copy(&va[0], &va[va.size() - 1], std::ostream_iterator<T > (os, " "));
  os << va[va.size() - 1] << std::endl;
}

/*------------------------------------------------------------------------------
  matrix2d tests
  ----------------------------------------------------------------------------*/

void testConstructors() {

  std::cout << "\n\n\nRunning Constructor Tests\n\n";

  int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
  std::valarray<int> v( a, 12 );
  std::size_t x = 3, y = 4;
  matrix2dio<int> i;

  std::cout <<
    "\nTesting: matrix2d(std::size_t rows, std::size_t columns, "
    "std::valarray<T> data);\n";
  matrix2d<int> m1( x, y, v );

  std::cout << "number of rows: " << m1.rows() << '\n'
  << "number of cols: " << m1.cols() << '\n'
  << "matrix content:\n";
  i.m2dToText( std::cout, m1 );

  std::cout << "\nTesting: matrix2d(std::size_t rows, std::size_t columns);\n";
  matrix2d<int> m2( x, y );

  std::cout << "number of rows: " << m2.rows() << '\n'
  << "number of cols: " << m2.cols() << '\n'
  << "matrix content:\n";
  i.m2dToText( std::cout, m2 );

  std::cout <<
    "\nTesting: matrix2d(std::size_t rows, std::valarray<T> data);\n";
  matrix2d<int> m3( x, v );

  std::cout << "number of rows: " << m3.rows() << '\n'
  << "number of cols: " << m3.cols() << '\n'
  << "matrix content:\n";
  i.m2dToText( std::cout, m3 );
}

void testRowsAndCols() {

  std::cout << "\n\n\nRunning Row/Col Accessor Tests\n\n";

  int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
  std::valarray<int> v( a, 12 );
  std::size_t x = 3, y = 4;
  matrix2dio<int> i;

  matrix2d<int> m1( x, y, v );

  std::cout << "\nTesting: std::valarray<T> row(std::size_t r) const;\n";

  std::valarray<int> r1 = m1.row(0);
  std::valarray<int> r2 = m1.row(1);
  std::valarray<int> r3 = m1.row(2); 

  std::cout << "row 1:\n";
  i.printValarray( std::cout, r1 );
  std::cout << "row 2:\n";
  i.printValarray( std::cout, r2 );
  std::cout << "row 3:\n";
  i.printValarray( std::cout, r3 );

  std::cout << "\nTesting: std::valarray<T> col(std::size_t r) const;\n";

  std::valarray<int> c1 = m1.col(0);
  std::valarray<int> c2 = m1.col(1);
  std::valarray<int> c3 = m1.col(2);
  std::valarray<int> c4 = m1.col(3); 

  std::cout << "col 1:\n";
  i.printValarray( std::cout, c1 );
  std::cout << "col 2:\n";
  i.printValarray( std::cout, c2 );
  std::cout << "col 3:\n";
  i.printValarray( std::cout, c3 );
  std::cout << "col 4:\n";
  i.printValarray( std::cout, c4 );

  std::cout << "\nTesting: std::slice_array<T> row(std::size_t r);\n";

  std::slice_array<int> rs1 = m1.row(0);
  std::slice_array<int> rs2 = m1.row(1);
  std::slice_array<int> rs3 = m1.row(2); 

  std::cout << "row 1:\n";
  i.printValarray( std::cout, rs1 );
  std::cout << "row 2:\n";
  i.printValarray( std::cout, rs2 );
  std::cout << "row 3:\n";
  i.printValarray( std::cout, rs3 );

  std::cout << "\nTesting: std::slice_array<T> col(std::size_t r);\n";

  std::slice_array<int> cs1 = m1.col(0);
  std::slice_array<int> cs2 = m1.col(1);
  std::slice_array<int> cs3 = m1.col(2);
  std::slice_array<int> cs4 = m1.col(3); 

  std::cout << "col 1:\n";
  i.printValarray( std::cout, cs1 );
  std::cout << "col 2:\n";
  i.printValarray( std::cout, cs2 );
  std::cout << "col 3:\n";
  i.printValarray( std::cout, cs3 );
  std::cout << "col 4:\n";
  i.printValarray( std::cout, cs4 );
}

void testGenerators() {

  std::cout << "\n\n\nRunning Generator Tests\n\n";

  int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
  int b[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120 };
  std::valarray<int> v1( a, 12 );
  std::valarray<int> v2( b, 12 );
  std::size_t x = 3, y = 4;
  matrix2dio<int> i;

  matrix2d<int> m1( x, y, v1 );
  matrix2d<int> m2( x, y, v2 );

  std::cout << "\nTesting: matrix2d<T> transpose();\noriginal:\n";

  matrix2d<int> m3 = m1.transpose();
  i.m2dToText( std::cout, m1 );
  std::cout << "transposed:\n";
  i.m2dToText( std::cout, m3 );

  std::cout << "\nTesting: matrix2d<T> appendRows(matrix2d<T> &v);\n";

  matrix2d<int> m4 = m2.appendRows(m1);
  i.m2dToText( std::cout, m4 );

  std::cout << "\nTesting: matrix2d<T> appendCols(matrix2d<T> &m);\n";

  matrix2d<int> m5 = m2.appendCols(m1);
  i.m2dToText( std::cout, m5 );

  std::cout << "\nTesting: matrix2d<T> rowItmSort();\n";

  matrix2d<int> m6 = m5.rowItmSort();
  i.m2dToText( std::cout, m6 );

  std::cout << "\nTesting: matrix2d<T> rowItmSortRev();\n";

  matrix2d<int> m7 = m5.rowItmSortRev();
  i.m2dToText( std::cout, m7 );

  std::cout << "\nTesting: matrix2d<T> colItmSort();\n";

  matrix2d<int> m8 = m4.colItmSort();
  i.m2dToText( std::cout, m8 );

  std::cout << "\nTesting: matrix2d<T> colItmSortRev();\n";

  matrix2d<int> m9 = m4.colItmSortRev();
  i.m2dToText( std::cout, m9 );
}

void testMatrix2d() {

    testConstructors();
    testRowsAndCols();
    testGenerators();
}

/*------------------------------------------------------------------------------
  matrix2d test entry point
  ----------------------------------------------------------------------------*/

int main( int argc, char** argv ) {

  testMatrix2d();
  return (EXIT_SUCCESS);
}

Fussing with slice_array

Some times we just make things far to complicated for ourselves: note to self (and whoever cares),do not put compiler hints into unproven code. Every now and then you overstep your confidence and do something that you look back at and think, “Now that’s just stupid!”. I’ve just spent the last several days wondering why the following does not compile.

void foo( const std::valarray<int> & va ) {
  std::slice_array<int> sa = va[std::slice( 1, 1, 1 )];
}

After all the line in the middle is exactly the same as sooo much example code out there it isn’t funny. However the compiler throws an awful wobbly and kicks back an error like this.

example.cc: In function ‘void foo(const std::valarray<int>&)’:
example.cc:20: error:
    conversion from
        ‘std::_Expr<std::_SClos<std::_ValArray, int>, int>’
    to non-scalar type
        ‘std::slice_array<int>’
    requested

Which is not quite what I expected. I’ve laid it out a bit different to the compiler for readability. Essentially the error means that the type of the expression on the right is not equivalent to the type of the variable on the left. However you can do this.

void foo( const std::valarray<int> & va ) {
  std::valarray<int> sa = va[std::slice( 1, 1, 1 )];
}

Which of course will compile without issue. OK so the operator() is overloaded, what’s its problem? The solution is blindingly obvious, but for those with a sense of anticipation I’ll drag it out just a tiny wee bit more. The mystery, and partly where I went wrong, was deepened by the valarray header.

/**
*  @brief  Return an array subset.
*
*  Returns a new valarray containing the elements of the array
*  indicated by the slice argument.  The new valarray has the same size
*  as the input slice.  @see slice.
*
*  @param  s  The source slice.
*  @return  New valarray containing elements in @a s.
*/
_Expr<_SClos<_ValArray, _Tp>, _Tp> operator[](slice) const;

/**
* @brief Return a reference to an array subset.
*
* Returns a new valarray containing the elements of the array
* indicated by the slice argument. The new valarray has the same size
* as the input slice. @see slice.
*
* @param s The source slice.
* @return New valarray containing elements in @a s.
*/
slice_array<_Tp> operator[](slice);

Now that's probably give it away if you didn't already know. But once again I wasn't looking properly. There were two real problems and none of them to do with my code: firstly I was programming by Google, secondly I was trying to be smart. The first error was as stupid as a cut and paste error. I'd looked up similar issues in Google and cut someone else's understanding of the problem out of a page that I had read and stapled it into my brain. Seems someone else had the same problem but not the nouse to get over it and was blaming the spec. Very silly, I should have known better. The second thing was that I'd tried to hint to the compiler before understanding its implications. Never hint to the compiler before you have the thing working, I'd have never wasted my time with it, although programming by debugger has its own worms.

Turns out this is the code that I wanted.

void foo( std::valarray<int> & va ) {
  std::slice_array<int> sa = va[std::slice( 1, 1, 1 )];
}

See it? If you still can't see it compare it to the earlier version and have a look at the prototypes in copied from the header above, which should explain almost everything. All that time. Silly, silly silly ... proceed with self flagellation of 50 lashings with a wet noodle! I have 15 years experience programming with C++ and 20 with C (which can generate similar errors), very embarrassing.


Generating Combinations

One of the tasks of numerical analysis is to search for or compare patterns. In the deep past this was quite a problem as it was easy to swamp the systems available with data making it more practical to employ a mathematician to perform some arcane analysis via algebra. However the manual way did not give the code opportunity to be tested against all possible combinations. Normally tests were conductd against boundaries and samples of statisitically significant combinations.

However in these days of Gig’s of memory and fast processors not to mention the terrabytes of disk space available cheaply it is possible to generate and test every possible combination in many cases. One of these is the classic combination space of mathematics. This following alogorithm is a crude base to progress from to generate such a number space.

// pattern generation
void genPat(size_t smpSize, size_t popSize, vector cmbSpace) {
  t_combo v(smpSize); // entry vector
  t_combo m(smpSize); // entry limit vector

  int i, e, a; // index and place holders

  // initialise the entry vector with an ascending order 1 to smpSize
  // and the limit vector with the max value each entry should reach
  for (i = 0; i < smpSize; i++)
  {
    v[i] = i + 1;
    m[i] = popSize - smpSize + v[i];
  }

  // repeat until the first entry in the vector is less than its
  // maximum value
  while (v[0] < m[0])
  {
    // update the combination space
    cmbSpace.push_back(v);

    // set an index to the last element
    e = smpSize - 1;

    // find the first element from the right to be less than the limit
    while (v[e] == m[e]) e--;

    // add one to and store the value of the current element in a var
    a = ++v[e];

    // set each element to the right to one more than the current
    while (e < smpSize - 1) v[++e] = ++a;
  }

  cmbSpace.push_back(v);
}

Copyright © 1996-2010 Code Snips. All rights reserved.
iDream theme by Templates Next | Powered by WordPress