在实践中，您需要将棋盘状态存储在以 s 为基础的 4 进制中unsigned long，每个棋盘行填充到整数个unsigned longs。这将为您提供最佳的内存位置，非常快速地访问板单元，但使用的 RAM 比三元封装多 26.2%。
要将电路板状态存储在二进制文件中，您可以将 5 个三进制数字（五个电路板单元状态）打包到每个 8 位字节中。这仅比三元打包多使用 5.1% 的内存，并且实现起来简单而健壮。特别是，这种方式您无需担心字节顺序（字节序）。
纯三元打包的问题是每个基数为 3 的数字都会影响表示相同数值的大多数二进制数字。例如，3 8 = 30000000 3 = 6561 = 1100110100001 2。这意味着提取 base-3 数字的唯一实用方法是通过重复除法和模数（除以 3）。
描述一块尺寸为N × M的板子，三元打包和拆包函数本质上是O ( N 2 M 2 )，因此随着板子尺寸的增加越来越慢。通过使用更少 CPU 时间的压缩库（例如liblzma ） ，您可能会获得更好的节省。对于许多电路板配置，游程编码也可以很好地工作。
以下是最多 16777215×16777215 个单元的板的示例实现（仅测试最多 32768×32768 个单元）：
#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;
}
该board_init()函数初始化板，board_save()将板状态保存到流中，包括板大小，以可移植二进制格式（每个文件将在 big-endian 和 little-endian 架构上生成相同的板），board_load()并将加载以前保存的板从一条溪流。如果成功，它们都返回0，如果错误则非零。
和函数是静态内联访问器函数get_cell()，set_cell()用于检查和设置板中各个单元的状态。
正如我最初建议的那样，这个在 RAM 中每个单元使用 2 位（每个字节 4 个单元），存储到文件时每个字节使用 5 个单元。
示例程序采用三个命令行参数：文件名、行数和列数。它将生成该大小的随机状态，将其保存到命名文件中，将其从命名文件读回到单独的板中，最后比较板状态，以验证实现的功能是否正常工作。
