Idiomatic way to allocate memory for bitfields

Help
1

I have a background in c, and I’m currently building a board game program. I’m currently representing the 5x5 board with unsigned 25 bit integers. There ways of moving a piece are represented in code the same way. I’d like to refactor the code to allow variable board sizes. Looking at the documentation, it appears zigs allocators require typing.
In short, I need to allocate x bits multiple times and am unsure as to the functional equivalent to malloc in this situation

2 Likes
2

Welcome to the community!

solution idea

If this board size is determined at the compile-time, you can use build options.

example following…

// build.zig
pub fn build(b: *std.Build) void {
    const target = b.standardTargetOptions(.{});
    const optimize = b.standardOptimizeOption(.{});

    const exe = b.addExecutable(.{
        .name = "config_board_size",
        .root_source_file = .{ .path = "src/main.zig" },
        .target = target,
        .optimize = optimize,
    });

    const cfgs = b.addOptions(); // create new configuration
    cfgs.addOption(u8, "board_size", 25); // specify board size
    exe.root_module.addOptions("configs", cfgs); // add as compile configuration

    b.installArtifact(exe);
    const run_cmd = b.addRunArtifact(exe);
    run_cmd.step.dependOn(b.getInstallStep());

    if (b.args) |args| {
        run_cmd.addArgs(args);
    }

    const run_step = b.step("run", "Run the app");
    run_step.dependOn(&run_cmd.step);
}

// main.zig
const std = @import("std");
const configs = @import("configs"); // import build configuration

pub fn main() !void {
    // create desiered type
    const typ = @Type(.{
        .Int = .{
            .signedness = .unsigned,
            .bits = configs.board_size, // apply board size
        },
    });

    var x2: typ = 0;
    std.debug.print("{x}\n", .{x2});
    x2 ^= 0b00000_00000_00000_00000_01100; // Ok!!!
    std.debug.print("{x}\n", .{x2});
    x2 ^= 0b1_00000_00000_00000_00000_00000; // Compile error !!!
    std.debug.print("{x}\n", .{x2});
}

If this board size is determined at the runtime, I have no idea, sorry.

4 Likes
3

Welcome @itsmeitsgreg

In C malloc returns a pointer to bytes allocation. The equivalent function in std.mem.Allocator is alloc where the type is u8 (i.e. a byte).

Yes, it requires typing. In C you have the cast the result to something non void. In zig the result is a pointer to the provided type and you don’t have to cast.

For your specific case:

const board_size = 5;
const Board: type = std.meta.Int(.unsigned, board_size * board_size);
var board: *Board = try allocator.create(Board);
defer allocator.destroy(board);

allocator.create is like alloc for one element.
std.meta.Int creates an integer type. For this call the resulting type is u25 (unsigned, 5*5).

Note that the resulting memory that board pointer points to is not initialized.

Zig have support for bit sets in standard library.
IntegerBitSet is the standard library type using an unsigned integer for storage like in the example above.
The advantage to using the standard library type is the provided methods to set, unset, toggle, initEmpty, etc.
There are various bit set implementations in std.bit_set.

4 Likes
4

I recommend you take a look at std.bit_set. Here’s sample usage:

var bits = std.bit_set.StaticBitSet(25).initEmpty();
bits.set(42);
bits.set(13);
std.debug.print("is 42 set? {}\n", .{bits.isSet(42)});

The static bit set doesn’t allocate at all. There’s also a DynamicBitSet that uses an allocator.

1 Like
5

Unfortunately it is, as I’m going to gamify it quite a bit and plan to change board sizes between levels, etc. Still, thank you for the response!

Thanks for the info, I understand it better now.

Thank you very much! This is exactly what I was looking for.

Well, that’s something I regret that I neglected to check. I’ll take a look and see if it’s right for me.

Appreciate it, will take a look!

2 Likes
6

I’ve been experimenting with this solution, but I have not been able to figure out any way to program it so that the size can actually change, since it has to be comptime. If anyone could guide me in the right direction, I’d appreciate it. I’d prefer to not have to use std.bit_set or an array/slice. I’d like to be able to use bitwise operations.

7

Yes, bit_set is the way to go (unless you have a maximum board size 10*10).

For any size, provided at runtime, use std.bit_set.DynamicBitSet.
An allocator is needed on initialization.
e.g.

var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const gpa_allocator = gpa.allocator();

var board = try std.bit_set.DynamicBitSet.initEmpty(gpa_allocator, 12*12);

board.set(12);   // set 1 to bit no 12
board.unset(12); // set 0 to bit no 12
2 Likes