Reading/writing single bits from/to FILE

Question

I'm implementing a Huffman encoding/decoding program and I need a way to deal with single bits.

I tried to keep things as simple as possible, I "pack" bits inside a single byte and I have only one index to worry about (of course this is a bit inefficient).

I'd like to get general feedback. Any suggestion is welcome!

bitbuf.h

#ifndef BITBUF_HEADER
#define BITBUF_HEADER

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//#define NDEBUG
#include <assert.h>

#define BITS_IN_BUF     8

struct bitbuf
{
        FILE *fp;
        bool is_writer;
        unsigned char buf;
        unsigned int idx;
};

/**
 * bitbuf_new:  allocates a new bitbuf and returns its pointer.
 *
 *              If writer is true, it will be usable for writing bits to fp,
 *              otherwise for reading bits from fp.
 *              writer must be setted according to the opening mode of fp ("w",
 *              "a" -> true, "r" -> false).
 *
 *              Read and write ("w+", "r+", "a+") modes are a bit tricky to
 *              handle so they are not "officially" supported.
 *
 *              On alloc failure, returns NULL.
 */
struct bitbuf *bitbuf_new(FILE *fp, bool writer);

#define bitbuf_new_bit_writer(fp)       bitbuf_new((fp), true)

#define bitbuf_new_bit_reader(fp)       bitbuf_new((fp), false)

/**
 * bitbuf_write_bit:  writes a bit (1 if bit == true, 0 if bit == false) and
 *                    returns true.
 *
 *                    Bits are buffered inside a byte from left to right. Only
 *                    with a successful call to bitbuf_flush() they will be
 *                    written to the underlying FILE pointer. This happens
 *                    automatically when the buffer (byte) if full (or when
 *                    bitbuf_free() is called).
 *
 *                    On flush failure, returns false.
 */
bool bitbuf_write_bit(struct bitbuf *bit_writer, bool bit);

/**
 * bitbuf_flush:  flushes the buffer (a byte) to the underlying FILE pointer and
 *                returns true.
 *
 *                If the buffer is not full, it will be written "0 padded".
 *                If the buffer is empty, nothing will be written and true will
 *                be returned.
 *
 *                On write failure, returns false.
 */
bool bitbuf_flush(struct bitbuf *bit_writer);

/**
 * bitbuf_read_bit:  reads a bit and returns 0 or 1 accordingly.
 *
 *                   Bits are buffered inside a byte and read from left to
 *                   right. They will be loaded automatically from the
 *                   underlying FILE pointer when the buffer is empty.
 *
 *                   On load failure, returns EOF.
 */
int bitbuf_read_bit(struct bitbuf *bit_reader);

/**
 * bitbuf_load:  reads a byte from the underlying FILE pointer, sets it as new
 *               buffer to read from (with bitbuf_read_bit()) and returns true.
 *
 *               On read failure (or EOF), returns false.
 */
bool bitbuf_load(struct bitbuf *bit_reader);

/**
 * bitbuf_free:  frees memory occupied by bitbuf. If bitbuf is a "bit_writer",
 *               the buffer will be flushed using bitbuf_flush().
 *
 *               It's safe to pass a NULL pointer.
 */
void bitbuf_free(struct bitbuf *bitbuf);

/**
 * bitbuf_close:  frees bitbuf (using bitbuf_free()) and calls fclose() on the
 *                underlying FILE pointer used by bitbuf.
 *
 *                It's safe to pass a NULL pointer.
 */
void bitbuf_close(struct bitbuf *bitbuf);

#endif

bitbuf.c

#include "bitbuf.h"


struct bitbuf *bitbuf_new(FILE *fp, bool writer)
{
        struct bitbuf *new_bb = malloc(sizeof(*new_bb));
        if (new_bb == NULL) {
                return NULL;
        }
        new_bb->fp = fp;
        new_bb->is_writer = writer;
        new_bb->buf = 0;
        new_bb->idx = (writer) ? 0 : BITS_IN_BUF;       /* to force load upon first read */
        return new_bb;
}

bool bitbuf_write_bit(struct bitbuf *bw, bool bit)
{
        assert(bw->is_writer);

        if (bw->idx == BITS_IN_BUF && ! bitbuf_flush(bw)) {
                return false;
        }
        if (bit) {
                bw->buf |= (0x80 >> bw->idx);           /* 0x80 is 0b10000000 */
        }
        bw->idx++;
        return true;
}

bool bitbuf_flush(struct bitbuf *bw)
{
        assert(bw->is_writer);

        if (bw->idx > 0) {
                if (fputc(bw->buf, bw->fp) == EOF) {
                        return false;
                }
                bw->buf = 0;
                bw->idx = 0;
        }
        return true;
}

int bitbuf_read_bit(struct bitbuf *br)
{
        assert( ! br->is_writer);

        if (br->idx == BITS_IN_BUF && ! bitbuf_load(br)) {
                return EOF;
        }
        return ((0x80 >> br->idx++) & br->buf) == 0 ? 0 : 1;
}

bool bitbuf_load(struct bitbuf *br)
{
        assert( ! br->is_writer);

        int byte = fgetc(br->fp);
        if (byte == EOF) {
                return false;
        }
        br->buf = byte;
        br->idx = 0;
        return true;
}

void bitbuf_free(struct bitbuf *bitbuf)
{
        if (bitbuf == NULL) {
                return;
        }
        if (bitbuf->is_writer) {
                bitbuf_flush(bitbuf);
        }
        free(bitbuf);
}

void bitbuf_close(struct bitbuf *bitbuf)
{
        if (bitbuf == NULL) {
                return;
        }
        FILE *fp = bitbuf->fp;
        bitbuf_free(bitbuf);
        fclose(fp);
}

I also wrote two simple test programs:

test_sequence.c

#include "bitbuf.h"

#define N 1013

void test_write_bit(struct bitbuf *bw, int n)
{
        srand(n);
        for (int i = 0; i < n; i++) {
                bitbuf_write_bit(bw, rand() % 2 == 0);
        }
}

void test_read_bit(struct bitbuf *br, int n)
{
        srand(n);
        for (int i = 0; i < n; i++) {
                assert(bitbuf_read_bit(br) == (rand() % 2 == 0) ? 1 : 0);
        }
}

int main(void)
{
        FILE *fp = fopen("test_sequence_file", "w");
        if (fp == NULL) {
                perror("Error");
                return 1;
        }

        struct bitbuf *bw = bitbuf_new_bit_writer(fp);
        test_write_bit(bw, N);

        bitbuf_free(bw);
        freopen(NULL, "r", fp);

        struct bitbuf *br = bitbuf_new_bit_reader(fp);
        test_read_bit(br, N);

        bitbuf_close(br);

        puts("Test OK");
}

test_copy.c

#include "bitbuf.h"

bool open_files(char *in_path, FILE **in_file, char *out_path, FILE **out_file)
{
        *in_file = fopen(in_path, "r");
        if (*in_file == NULL) {
                perror("Error");
                return false;
        }
        *out_file = fopen(out_path, "w");
        if (*out_file == NULL) {
                perror("Error");
                fclose(*out_file);
                return false;
        }
        return true;
}

int main(int argc, char **argv)
{
        if (argc != 3) {
                fprintf(stderr, "Error: usage: %s [source] [dest]\n", argv[0]);
                return 1;
        }

        FILE *in_file, *out_file;
        if ( ! open_files(argv[1], &in_file, argv[2], &out_file)) {
                return 1;
        }

        struct bitbuf *br = bitbuf_new_bit_reader(in_file);
        struct bitbuf *bw = bitbuf_new_bit_writer(out_file);

        int bit;
        while ((bit = bitbuf_read_bit(br)) != EOF) {
                bitbuf_write_bit(bw, bit == 1);
        }

        bitbuf_close(br);
        bitbuf_close(bw);
}

Here some testing output:

bitbuf$ cc -std=c11 -Wall -Wextra -Werror -c -o bitbuf.o bitbuf.c
bitbuf$ cc -std=c11 -Wall -Wextra -Werror -o test_sequence bitbuf.o test_sequence.c 
bitbuf$ cc -std=c11 -Wall -Wextra -Werror -o test_copy bitbuf.o test_copy.c 
bitbuf$ ./test_sequence 
Test OK
bitbuf$ dd if=/dev/urandom bs=1M count=20 > original
20+0 records in
20+0 records out
20971520 bytes (21 MB, 20 MiB) copied, 0.179982 s, 117 MB/s
bitbuf$ time ./test_copy original copy

real    0m5.850s
user    0m5.796s
sys     0m0.052s
bitbuf$ ls -l original copy
-rw-r--r-- 1 marco marco 20971520 Jan 21 17:17 copy
-rw-r--r-- 1 marco marco 20971520 Jan 21 17:16 original
bitbuf$ diff original copy 
bitbuf$ echo $?
0
bitbuf$

Answer 1

For a beginner, this is pretty decent! Here are some things that could be improved.

Naming

Many of your variable names are 2 or 3 characters long. That's difficult to read and understand. I recommend using longer names that are descriptive. fp could be file; buf should be buffer or better yet byte_buffer, and idx should be bit_index. Using a single generic word (like idx) is usually a sign that you need better naming. What does it index? Why remove those 2 extra characters?

Don't Let A Caller Shoot Themselves in the Foot

The bitbuf_new() function takes a file pointer and a boolean value for whether the file is opened for reading or writing. There are many ways a user of this function can screw it up. They can pass in a NULL file pointer. They can pass in a file pointer that's open for read, but say that it's open for writing, or the reverse. They can pass in a stale file pointer (one that was already closed, for example). The macros don't solve this problem. They're just "shortcuts" that are actually longer to type than their textual replacement.

It would make more sense to have them pass in a file name and an open mode string, just like is sent to fopen() and to call fopen() in the bitbuf_new() function. Especially given the fact that bitbuf_close() closes the file. That's especially troublesome - you have to open the file yourself, pass it to bitbuf_new() but bitbuf_close() will close it for you. And bitbuf_close() also frees the buffer? Why? This all seems inconsistent and confusing.

I would make bitbuf_new() take a file name and a mode string. I would remove bitbuf_close() and just have bitbuf_free() also close the file.

Performance

You mention "this is a bit inefficient". I recommend reading in a larger buffer of around 1-4k and getting bits out of that. You should probably profile to figure out the ideal size, but that's probably a good place to start. Having 1 extra index will only add 4-8 bytes to the structure, so that shouldn't be too onerous. Are you reading from or writing to lots of files at the same time? If not, then it's negligible.

Answer 2

This code is good. You could try using a long as your buffer.

Answer 3

Looks good to me, but there is absolutely no need to have the code split between 4 different files. It makes reading it awkward and confusing, as one has to constantly jump between files and search for code lines scattered all around. I recommend unifying the code files into one logically-following file.