Nanfeng

Notes on software development, code, and curious ideas

Implementing a Custom Bit Array Type for Lua in C

In
Store Boolean values compactly in C userdata and expose safe indexed access, length, and string conversion to Lua.

A Lua table can represent a Boolean array, but a native bit array can store each value in one bit. This example focuses on the API design needed to expose a custom C type safely.

Storage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <limits.h>
#include <lua.h>
#include <lauxlib.h>

#define BITS_PER_WORD (CHAR_BIT * sizeof(unsigned int))
#define WORD_INDEX(i) ((unsigned int)(i) / BITS_PER_WORD)
#define BIT_MASK(i)   (1u << ((unsigned int)(i) % BITS_PER_WORD))

typedef struct {
    size_t size;
    unsigned int values[];
} BitArray;

#define BIT_ARRAY_TYPE "Example.BitArray"

A flexible array member is available in C99. Allocate enough words for the requested number of bits and check for overflow before calculating the byte count.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static BitArray *check_array(lua_State *L, int index) {
    return (BitArray *)luaL_checkudata(L, index, BIT_ARRAY_TYPE);
}

static int new_array(lua_State *L) {
    lua_Integer requested = luaL_checkinteger(L, 1);
    luaL_argcheck(L, requested > 0, 1, "size must be positive");

    size_t size = (size_t)requested;
    size_t words = WORD_INDEX(size - 1) + 1;
    size_t bytes = sizeof(BitArray) + words * sizeof(unsigned int);

    BitArray *array = (BitArray *)lua_newuserdata(L, bytes);
    array->size = size;
    for (size_t i = 0; i < words; i++) array->values[i] = 0;

    luaL_getmetatable(L, BIT_ARRAY_TYPE);
    lua_setmetatable(L, -2);
    return 1;
}

Validate indexes and read/write bits

Lua-facing indexes are one-based:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static unsigned int *get_entry(
    lua_State *L,
    unsigned int *mask
) {
    BitArray *array = check_array(L, 1);
    lua_Integer requested = luaL_checkinteger(L, 2);
    luaL_argcheck(
        L,
        requested >= 1 && (size_t)requested <= array->size,
        2,
        "index out of range"
    );

    size_t index = (size_t)requested - 1;
    *mask = BIT_MASK(index);
    return &array->values[WORD_INDEX(index)];
}

static int set_array(lua_State *L) {
    unsigned int mask;
    unsigned int *entry = get_entry(L, &mask);
    luaL_checkany(L, 3);

    if (lua_toboolean(L, 3)) *entry |= mask;
    else *entry &= ~mask;
    return 0;
}

static int get_array(lua_State *L) {
    unsigned int mask;
    unsigned int *entry = get_entry(L, &mask);
    lua_pushboolean(L, (*entry & mask) != 0);
    return 1;
}

static int get_size(lua_State *L) {
    BitArray *array = check_array(L, 1);
    lua_pushinteger(L, (lua_Integer)array->size);
    return 1;
}

luaL_checkudata is essential: a raw lua_touserdata cast would accept unrelated userdata and could corrupt memory.

Expose normal Lua syntax

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static int array_to_string(lua_State *L) {
    BitArray *array = check_array(L, 1);
    lua_pushfstring(L, "BitArray(%d)", (int)array->size);
    return 1;
}

static const luaL_Reg methods[] = {
    {"__index", get_array},
    {"__newindex", set_array},
    {"__len", get_size},
    {"__tostring", array_to_string},
    {NULL, NULL}
};

static const luaL_Reg functions[] = {
    {"new", new_array},
    {NULL, NULL}
};

int luaopen_bitarray(lua_State *L) {
    luaL_newmetatable(L, BIT_ARRAY_TYPE);
    luaL_setfuncs(L, methods, 0);
    luaL_newlib(L, functions);
    return 1;
}

Lua can then use the object naturally:

1
2
3
4
5
6
local bitarray = require("bitarray")
local values = bitarray.new(1000)
values[10] = true
print(values[10]) -- true
print(#values)    -- 1000
print(values)     -- BitArray(1000)

Full userdata owns its storage and supports metatables. Light userdata is only a raw pointer value: it has no per-value metatable and is not managed as an owned buffer, so it is better suited to identity keys and non-owning native references than to this array type.

+