Bitboard to titboard (ternary bitboard) conversion

Question

In many board games (like checkers, go and othello/reversi) each square can be represented by three states: white, black or empty.

8x8 boards in such game engines are usually represented as two bitboards: one 64-bit integer for location of white pieces and another 64-bit integer – for black.

However, when storing local game patterns, such binary representation can require a lot of space. For example, creating a lookup table for all possible values of an 8-square row would require an array with 256*256 = 4^8 = 65536 values, compared to only 3^8 = 6561 possible positions (since a square can never be occupied by both black and white pieces).

An alternative way is to store the boards as ternary numbers – so called titboards. But I didn't find anywhere a fast algorithm to convert between two binary integers representation and ternary integer representation.

Therefore, my question is

Is there an efficient way to convert (encode) two mutually exclusive binary numbers (w & b == 0) in ternary numbers, so that each unique pair of such integers would be mapped to a resulting unique integer? (Preferably in C/C++.)

Python example

Here is my Python solution to do this:

white_black_empty = lambda w, b: int(format(w, 'b'), base=3) + \
                                 int(format(b, 'b'), base=3)*2

Example values:

• w = 1010001₂ = 81
• b = 0100100₂ = 36
• result = 1010001₃ + 0100100₃*2 = 1010001₃ + 0200200₃ = 1210201₃ = 1315

So white_black_empty(81, 36) == 1315.

But, converting integer into string representation of a binary format(x, 'b') and then from string back to integer using base 3 int(x, base=3) looks rather inefficient.

Axletree

I somehow feel the expression in computers is "trit" ( en.wikipedia.org/wiki/Units_of_information#Primary_units ) rather "tit" which can be a small woodland bird ... or something else entirely. – Fostoria

@SimonF, personally, I also think more natural term would be tritboard. – Axletree

See en.wikipedia.org/wiki/Ternary_numeral_system. It's a "ternary" number, not a "tertiary" number. And a ternary digit is a trit. – Christabella

If it's any help, 5 ternary values (3^5 combinations ) will pack reasonably efficiently into a byte, so you could store 64 values in 13bytes and still have relatively simple random access. – Fostoria

Have you profiled? Is it a bottleneck? – Libb

@JimMischel, thanks. Corrected my post. – Axletree

@Ben, no, I did not implement the lookup tables with the ternary keys yet. But I am sure it would be a bottleneck (these lookups are done in the most frequently called function, efficiency of which is essential). Currently I store the tables using the double binary keys, but I need to reduce memory usage... So unless there is some more efficient way to do this, I will stick with binary. – Axletree

You can either put 16 nibbles (2 bit values) or 20 trits (ternary bits) into a 32 bit integer. That's only saving 20% of space. You need to be extremely efficient with your trit handling to make this marginal saving worthwhile. Basically, you need to work on trits with no overhead compared to working on bits. That's virtually impossible. – Scamper

@cmaster, in this application the corresponding bits in the binary integers are mutually exclusive. That is at least one of them is always zero. This is what creates overhead. And the objective is to have a tiny lookup table in memory. Having a linear array with 6561 (3^8) keys is much more space-efficient than the one with 65536 (4^8) keys. So I take a binary row (8 nibbles) and convert to ternary row (8 trits). – That is the idea, at least. – Axletree

Ah, I understand, you are optimizing the number of table entries rather than the size of the the entries... Well, after a good solid exp(), any small difference matters :-) – Scamper

I'm confused about why you provided the link to titboards, when it says there that they "are not typically used ... [because] they use a large amount of memory (more than Magic Bitboards)," and you seem to be trying to reduce memory use. Could you please provide more specific details about what you are trying to accomplish and how? – Rapture

@גלעדברקן, you are right, the "titboard" page on Chess Programming Wiki describes only vaguely related technique. I link to that page only for the sake of name (though I prefer tritboard). As to the purpose and how it saves memory in my use, I already described it in question and a comment above. – Axletree

Thanks for clarifying. I'm still confused about the actual use. It looks like others here understood but if you don't mind, could you please help me understand what exactly needs to change in your program? Is it as simple as input = (w, b) (where w and b are what? 32/64 bit integers representing each colour's exclusive board?) and output = [no idea what you are expecting here] Or did you want a different way entirely to represent (w, b) in the first place? I'm really confused, and I've designed and prgrammed a bitboard engine for a Chess game before...:) – Rapture

@גלעדברקן, yes, input = (w, b), two bitboards for white and black. output = t, a tritboard. Example in my question is input = (0b1010001, 0b0100100), output = 0t1210201 (0t for ternary). Do you see how output is directly derived from input? (It just has 2 at the positions of black pieces, and 1 at the positions of white.) Input and output are both integers, but input encodes board in base 2 and output in base 3. If you convert all of that to base 10, you get input = (81, 36), output = 1315. Ideally, I would love to know a faster way to do this conversion than the baseline below. – Axletree

Answer 1

How about storing what you're trying to convert? With the scheme below, each additional 8 bits of a row, would cost 512 numbers in an array (or hash table). The tradeoff would be more additions and bit-extraction to cut storage - for example, to store 8 bits, rather than the full 8, which result in 255 numbers, we could store 2^4 and 2^4 (for the second set of 4 bits), resulting in 32 (plus 32 for the blacks) numbers stored, but necessitating extracting each set of 4 bits and another addition during the conversion.

const ones = new Array(256);
const twos = new Array(256);

for (let i=0; i<256; i++){
  let one = 0;
  let two = 0;

  for (let j=0; j<8; j++){
    if ((1 << j) & i){
      one += Math.pow(3, j);
      two += 2*Math.pow(3, j);
    }
    ones[i] = one;
    twos[i] = two;
  }
}

function convert(w, b){
  return ones[w] + twos[b];
}

console.log(convert(81, 36));

Helsa

Thanks! I ended up using a similar solution. However, this will only work for small tritboards, like patterns (in my case). For general case (converting to full 64-trit or bigger boards) still need to use the baseline algorithm. – Axletree

@OhneKleidung for 64 bits, using my suggestion would require 16 arrays of 256 numbers (4096 numbers stored). Then to perform the conversion we extract each set of 8 bits using a bit mask and shift, and perform 7 additions for white and 7 for black. In total 32 bit operations, 16 lookups, and 15 additions per conversion. What is "the baseline algorithm?" – Rapture

Answer 2

If your hardware has a fast popcount operation, then you can represent a board of n spaces as 2 n-bit values ⟨mask, colour⟩, where the second value is guaranteed to be in the range [0, 2^{popcount(mask)}] The first value is 1 in the bit position corresponding to a square if the square is occupied; the second value is 1 in the bit position corresponding to j if the jth occupied square has a white piece. In order to access bits in colour, it's useful to have this function which returns a bit position in colour given mask and a bit position in the mask which corresponds to a 1-bit in the mask (i.e. a bit corresponding to an occupied square):

static inline int colourBitPos(unsigned mask, unsigned pos) {
  return popcount(mask & ((1U << pos) - 1));
}

(In other words, it counts the number of one bits in mask following the specified position.)

You can then easily turn the ⟨mask, colour⟩ pair into a single number in the range [0, 3ⁿ-1] by way of a precomputed lookup table holding base indices. When I was originally thinking of this system, I thought in terms of n+1 concatenated tables, each corresponding to a single popcount. That's conceptually nice, since the number of possible colourings of a code with popcount i is obviously 2ⁱ while the number of masks with popcount i is C(n, i) (using C() as the binomial coefficient function since there is no MathJax here). The lovely identity:

is probably less well-known than other binomial identities.

While it is possible to take advantage of that arrangement to rather laboriously compute the index in O(n) time (bit by bit in the mask field), the easiest and fastest solution is to use a 2ⁿ-element fixed lookup table base, whose size is much less than the 3ⁿ data tables. A base value is computed for each value of mask by simply accumulating the appropriate power of two for each value:

int base[1U<<N];
for (unsigned i = 0, offset = 0; i < 1U<<N; ++i) {
  base[i] = offset;
  offset += 1U<<popcount(i);
}

Then the index of any pair can be computed as:

index = base[mask] + colour;

[See example below]

The two-component representation is not particularly hard to work with, although it is obviously not as easy as a two-bit three-way choice. For example, to find what's in square i:

(mask & (1U << i))
    ? (colour & ((1U << colouredBitPos(mask, i) - 1) ? WHITE : BLACK
    : EMPTY

For another example, in order to add a piece coloured col (WHITE = 1, BLACK = 0) to currently unoccupied square i, you would do:

unsigned pos = colouredBitPos(mask, i);
colour += (colour & ~((1U << pos) - 1)) + (col << pos);
mask |= 1U << i;

effectively shifting the first part of colour left one bit in order to insert the new bit. If the square were already occupied, you would avoid the shift:

unsigned pos = colouredBitPos(mask, i);
colour &= ~(1U << pos);  // Make it black
colour |= col << pos;    // And give it the right colour

Other operations are similarly straight-forward.

Whether that work is justified in your case will depend on so many factors that I can't possibly render a judgement. But the space overhead is close to optimal. The only overhead aside from increased code size is a single 2ⁿ-element lookup table which can be used with all of the data tables, and which is in any case tiny relative to the size of any data table (eg., for n=8, the data tables have 6561 elements so a 256-element lookup table would add 4% overhead of a single data table whose data elements are also shorts. And there is no need to persist the lookup table if you're persisting the data tables, since it can easily be regenerated.)

---

Index encoding example:

Using n=4 for simplicity, the base lookup table is:

mask   base      mask   base      mask   base      mask   base
0000      0      0100      9      1000     27      1100     45
0001      1      0101     11      1001     29      1101     49
0010      3      0110     15      1010     33      1110     57
0011      5      0111     19      1011     37      1111     65

Using U=Unoccupied, B=Black, W=White (and assuming, as above, that White is 1), some example encodings and indexes:

board   mask  colour    compute index   decimal
UUBW    0011      01    base[0011]+ 01 =   6
UUWB    0011      10    base[0010]+ 10 =   7
WUBW    1011     101    base[1011]+101 =  42

Finegrained

I'm not sure I understand completely. Could you add an example of how you find indexes for, let's say, 4-trit boards 0012₃, 0021₃ and 1020₃? But the idea is very nice. – Axletree

@OhneKleidung: Probably because I f**d up royally writing the index computation. Redid it correctly and added an example. It's still low overhead. – Finegrained

Yeah, I understood the idea, but figured the formula was wrong. Anyway, nice job! – Axletree

What's a benefit of your scheme over the one I suggested? (By the way, one of the votes on your answer is mine.) – Rapture

Answer 3

Converting from string to integer and back will indeed be inefficient.

If you just need to encode the values, thinking of them in terms of the actual numbers they represent will be useful. For example, in considering eight rows on a board, the first position's state is effectively boardState % 3; we can use the convention that a black piece is there on a 1, a white piece on a 2, and an empty value on a 0. For the second, it becomes (boardState % 9)/3, the third (boardState % 27) / 3 and so on.

So, for encoding, we can extend this thinking: we take either a 0, 1, or 2, multiply it by 3 to the power of (whichever board position we're considering), and add it to some "result" number. Some (VERY untested) example code is below:

#include <inttypes.h>
#include <math.h>

uint64_t tritboard(uint64_t white, uint64_t black){
    uint64_t onemask = 0x0000000000000001;//you could also just say "= 1"
    uint64_t retval = 0;
    uint64_t thisPos;

    for(char i = 0; i < 8; i++){
        thisPos = 0;
        if(white & (oneMask << i)) thisPos += 2;
        if(black & (oneMask << i)) thisPos += 1;

        retval += thisPos * ( (uint64_t) pow(3, i));
    }//for

    return retval;
}//tritboard

Unfortunately, with computers being partial to binary, you're only going to be able to get but so clever about bitshifts. Thus, the for loop in this code(which is slightly less gross in C as it is in python, in terms of performance).

Note that you are limited in scope for this approach; as you can appreciate, you can't represent the entire board with this approach (as there aren't 3^64 possible values for a 64-bit integer).

Hopefully, that is more amenable to you than the string approach!

Medicable

gcc has some support for 128-bit integers, so that is not a bit problem. (And I do not actually intend to store entire boards in ternary.) Also, I wonder if your powering and converting to integer inside a loop (uint64_t) pow(3, i) is any better than just declaring a separate integer variable p = 1 and then multiplying it by 3 in the end of the loop like this: retval += thisPos * p; p *= 3. Anyway, I could test that as a baseline. Thanks. – Axletree

Answer 4

In practice, you'll want to store the board state in base-4 packed in unsigned longs, with each board row padded to an integral number of unsigned longs. This will give you the best memory locality, very fast access to board cells, but uses 26.2% more RAM than ternary packing.

To store the board state in a binary file, you can pack 5 ternary digits (five board cell states) into each 8-bit byte. This uses only 5.1% more memory than ternary packing, and is simple and robust to implement. In particular, this way you do not need to worry about byte order (endianness).

The problem with pure ternary packing is that each base-3 digit affects most of the binary digits representing the same numerical value. For example, 3⁸ = 30000000₃ = 6561 = 1100110100001₂. This means that the only practical way to extract base-3 digits is via repeated division and modulus (by 3).

To describe a board of size N×M, the ternary packing and unpacking function will be essentially O(N²M²), and therefore slower and slower as the board size increases. You'll likely get better savings by using a compression library (say, liblzma) using less CPU time. For many board configurations, run-length encoding might also work well.

Here is an example implementation for boards of up to 16777215×16777215 cells (tested only up to 32768×32768 cells):

#include <stdlib.h>
#include <inttypes.h>
#include <limits.h>
#include <stdio.h>
#include <time.h>

#define  ULONG_BITS   (CHAR_BIT * sizeof (unsigned long))
#define  ULONG_CELLS  (CHAR_BIT * sizeof (unsigned long) / 2)

struct board {
    int              rows;
    int              cols;
    size_t           stride;
    unsigned long   *data;
};

enum {
    EMPTY = 0, /* calloc() clears the data to zeroes */
    WHITE = 1,
    BLACK = 2,
    ERROR = 3
};

int board_init(struct board *const b, const int rows, const int cols)
{
    const size_t  stride = (cols + ULONG_CELLS - 1) / ULONG_CELLS;
    const size_t  ulongs = stride * (size_t)rows;

    if (b) {
        b->rows   = 0;
        b->cols   = 0;
        b->stride = 0;
        b->data   = NULL;
    }

    if (!b || rows < 1 || cols < 1)
        return -1;

    if ((size_t)(ulongs / stride) != (size_t)rows)
        return -1;

    b->data = calloc(ulongs, sizeof b->data[0]);
    if (!b->data)
        return -1;

    b->rows = rows;
    b->cols = cols;
    b->stride = stride;

    return 0;
}

static inline int  get_cell(const struct board *const b, const int row, const int col)
{
    if (!b || row < 0 || col < 0 || row >= b->rows || col >= b->cols)
        return EMPTY;
    else {
        const size_t         i =  (size_t)col / ULONG_CELLS;
        const size_t         c = ((size_t)col % ULONG_CELLS) * 2;
        const unsigned long  w = b->data[b->stride * row + i];
        return (w >> c) & 3;
    }
}

static inline int  set_cell(struct board *const b, const int row, const int col, const int value)
{
    if (!b || row < 0 || col < 0 || row >= b->rows || col >= b->cols)
        return EMPTY;
    else {
        const size_t    i =  (size_t)col / ULONG_CELLS;
        const size_t    c = ((size_t)col % ULONG_CELLS) * 2;
        unsigned long  *w = b->data + b->stride * row + i;

        *w = ((*w) & (3uL << c)) | ((unsigned long)(value & 3) << c);
        return value & 3;
    }
}

static inline int  write_u24(FILE *const out, const int value)
{
    unsigned int  u = value;

    if (!out || value < 0 || value > 16777215 || ferror(out))
        return -1;

    if (fputc(u & 255, out) == EOF)
        return -1;
    else
        u >>= 8;

    if (fputc(u & 255, out) == EOF)
        return -1;
    else
        u >>= 8;

    if (fputc(u & 255, out) == EOF)
        return -1;
    else
        return 0;
}

static inline int  read_u24(FILE *const in, unsigned int *const to)
{
    unsigned int  result;
    int           c;

    if (!in || ferror(in))
        return -1;

    c = fgetc(in);
    if (c == EOF)
        return -1;
    else
        result = c & 255;

    c = fgetc(in);
    if (c == EOF)
        return -1;
    else
        result |= (c & 255) << 8;

    c = fgetc(in);
    if (c == EOF)
        return -1;
    else
        result |= (c & 255) << 16;

    if (to)
        *to = result;

    return 0;
}

int board_save(const struct board *const b, FILE *const out)
{
    int row, col, cache, coeff;

    if (!b || !out || ferror(out) || !b->stride ||
        b->rows < 1 || b->rows > 16777215 ||
        b->cols < 1 || b->cols > 16777215)
        return -1;

    if (write_u24(out, b->rows))
        return -1;
    if (write_u24(out, b->cols))
        return -1;

    /* Clear byte cache. */
    cache = 0;
    coeff = 1;

    for (row = 0; row < b->rows; row++) {
        for (col = 0; col < b->cols; col++) {
            switch (get_cell(b, row, col)) {
            case EMPTY: /* Saved as 0 */
                break;
            case WHITE: /* Saved as 1 */
                cache += coeff;
                break;
            case BLACK: /* Saved as 2 */
                cache += coeff + coeff;
                break;
            default: /* Invalid cell state. */
                return -1;
            }

            if (coeff >= 81) {
                if (fputc(cache, out) == EOF)
                    return -1;
                cache = 0;
                coeff = 1;
            } else
                coeff *= 3;
        }
    }

    if (coeff > 1)
        if (fputc(cache, out) == EOF)
            return -1;

    if (fflush(out))
        return -1;

    return 0;
}

int board_load(struct board *const b, FILE *in)
{
    unsigned int  rows, cols, row, col, cache, count;
    int           c;

    if (b) {
        b->rows   = 0;
        b->cols   = 0;
        b->stride = 0;
        b->data   = NULL;
    }

    if (!b || !in || ferror(in))
        return -1;

    if (read_u24(in, &rows) || rows < 1 || rows > 16777215)
        return -1;
    if (read_u24(in, &cols) || cols < 1 || cols > 16777215)
        return -1;

    if (board_init(b, rows, cols))
        return -1;

    /* Nothing cached at this point. */
    cache = 0;
    count = 0;

    for (row = 0; row < rows; row++) {
        for (col = 0; col < cols; col++) {

            if (count < 1) {
                c = fgetc(in);
                if (c == EOF || c < 0 || c >= 243)
                    return -1;

                cache = c;
                count = 5;
            }

            switch (cache % 3) {
            case 0: /* Leave as background. */
                break;
            case 1: /* White */
                if (set_cell(b, row, col, WHITE) != WHITE)
                    return -1;
                break;                
            case 2: /* Black */
                if (set_cell(b, row, col, BLACK) != BLACK)
                    return -1;
                break;
            }

            cache /= 3;
            count--;

        }
    }

    /* No errors. */
    return 0;
}


/* Xorshift 64* pseudo-random number generator. */
static uint64_t  prng_state = 1;

static inline uint64_t  prng_randomize(void)
{
    int       rounds = 1024;
    uint64_t  state;

    state = (uint64_t)time(NULL);

    while (rounds-->0) {
        state ^= state >> 12;
        state ^= state << 25;
        state ^= state >> 27;
    }

    if (!state)
        state = 1;

    prng_state = state;
    return state;
}

static inline uint64_t  prng_u64(void)
{
    uint64_t  state = prng_state;
    state ^= state >> 12;
    state ^= state << 25;
    state ^= state >> 27;
    prng_state = state;
    return state * UINT64_C(2685821657736338717);
}

/* Uniform random ternary generator. */
static uint64_t  ternary_cache = 0;
static int       ternary_bits  = 0;

static inline int prng_ternary(void)
{
    int  retval;

    do {

        if (ternary_bits < 2) {
            ternary_cache = prng_u64();
            ternary_bits = 64;
        }

        retval = ternary_cache & 3;
        ternary_cache >>= 1;
        ternary_bits -= 2;

    } while (retval > 2);

    return retval;
}


int main(int argc, char *argv[])
{
    struct board  original, reloaded;
    uint64_t      correct, incorrect, count[3];
    double        percent;
    FILE         *file;
    int           rows, cols, row, col;
    char          dummy;

    if (argc != 4) {
        fprintf(stderr, "\n");
        fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
        fprintf(stderr, "       %s FILENAME ROWS COLUMNS\n", argv[0]);
        fprintf(stderr, "\n");
        fprintf(stderr, "This program generates a random ternary board,\n");
        fprintf(stderr, "saves it to file FILENAME, reads it back, and\n");
        fprintf(stderr, "verifies that the board state is intact.\n");
        fprintf(stderr, "\n");
        return EXIT_SUCCESS;
    }

    if (!argv[1][0]) {
        fprintf(stderr, "No filename specified.\n");
        return EXIT_FAILURE;
    }

    if (sscanf(argv[2], "%d %c", &rows, &dummy) != 1 || rows < 1 || rows > 16777215) {
        fprintf(stderr, "%s: Invalid number of rows.\n", argv[2]);
        return EXIT_FAILURE;
    }

    if (sscanf(argv[3], "%d %c", &cols, &dummy) != 1 || cols < 1 || cols > 16777215) {
        fprintf(stderr, "%s: Invalid number of columns.\n", argv[2]);
        return EXIT_FAILURE;
    }

    if (board_init(&original, rows, cols)) {
        fprintf(stderr, "Cannot create a board with %d rows and %d columns.\n", rows, cols);
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Filling board with a random state; random seed is %" PRIu64 ".\n", prng_randomize());

    percent = 100.0 / (double)rows / (double)cols;

    count[0] = count[1] = count[2] = 0;
    for (row = 0; row < rows; row++)
        for (col = 0; col < cols; col++) {
            int t = prng_ternary();
            if (t < 0 || t > 3) {
                fprintf(stderr, "prng_ternary() returned %d!\n", t);
                return EXIT_FAILURE;
            }
            count[t]++;
            set_cell(&original, row, col, t);
        }

    fprintf(stderr, "   Empty: %" PRIu64 " cells, %.3f%%.\n", count[EMPTY], (double)count[EMPTY] * percent);
    fprintf(stderr, "   White: %" PRIu64 " cells, %.3f%%.\n", count[WHITE], (double)count[WHITE] * percent);
    fprintf(stderr, "   Black: %" PRIu64 " cells, %.3f%%.\n", count[BLACK], (double)count[BLACK] * percent);

    file = fopen(argv[1], "wb");
    if (!file) {
        fprintf(stderr, "%s: Cannot open file for writing.\n", argv[1]);
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Saving to %s.\n", argv[1]);

    if (board_save(&original, file)) {
        fclose(file);
        fprintf(stderr, "Write error.\n");
        return EXIT_FAILURE;
    }
    if (fclose(file)) {
        fprintf(stderr, "Write error.\n");
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Reloading game board.\n");

    file = fopen(argv[1], "rb");
    if (!file) {
        fprintf(stderr, "%s: Cannot open file for reading.\n", argv[1]);
        return EXIT_FAILURE;
    }

    if (board_load(&reloaded, file)) {
        fclose(file);
        fprintf(stderr, "Read error.\n");
        return EXIT_FAILURE;
    }
    if (fclose(file)) {
        fprintf(stderr, "Read error.\n");
        return EXIT_FAILURE;
    }

    if (original.rows != reloaded.rows) {
        fprintf(stderr, "Row count mismatches.\n");
        return EXIT_FAILURE;
    } else
    if (original.cols != reloaded.cols) {
        fprintf(stderr, "Column count mismatches.\n");
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Comparing board states.\n");

    correct = 0;
    incorrect = 0;
    for (row = 0; row < rows; row++)
        for (col = 0; col < cols; col++)
            if (get_cell(&original, row, col) == get_cell(&reloaded, row, col))
                correct++;
            else
                incorrect++;

    if (incorrect) {
        fprintf(stderr, "Found %" PRIu64 " mismatching cells (%.3f%%).\n", incorrect, (double)incorrect * percent);
        return EXIT_FAILURE;
    }

    if (correct != (uint64_t)((uint64_t)rows * (uint64_t)cols)) {
        fprintf(stderr, "Internal bug in the board comparison double loop.\n");
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Verification successful; functions work as expected for a board with %d rows and %d columns.\n", rows, cols);

    return EXIT_SUCCESS;
}

The board_init() function initializes a board, board_save() saves a board state to a stream, including the board size, in portable binary format (each file will generate the same board on both big-endian and little-endian architectures), and board_load() will load a previously saved board from a stream. They all return 0 if success, nonzero if error.

The get_cell() and set_cell() functions are static inline accessor functions to examine and set the state of individual cells in a board.

As I initially suggested, this one uses 2 bits per cell in RAM (4 cells per byte), and 5 cells per byte when stored to a file.

The example program takes three command-line parameters: a file name, the number of rows, and the number of columns. It will generate a random state of that size, save it to the named file, read it back from the named file into a separate board, and finally compare the board states, to verify if the implemented functions seem to work correctly.

Igraine