writing 3 bits at a time to binary file in C

Question

Image

hello, i have a list of locations as described in the image stored in a linked list. every node has an unsigned char in the size of 2(chessPos in the code) - the first location represents a row and the second a col. for example the first node: row = 'C', col = '5' and so on. the list is passed through the function i dont need to built it.

i need to write the data to a binary file, when each row or col is written in 3 bits. so 'C' will be written as 010 and right after '5' will be written as 100 (the 3 bits written represent the row/col -1, thats why '5' is represnted by 100 which is 4 in binary).

the difficulty is that every byte is 8 bits and every time i write a byte to the file it contains 6 bits which represt a row and a col, and 2 bits of the next byte.

how can i make it work?

thanks

this is my code so far:

      typedef char chessPos[2];
    
    
    typedef struct _chessPosArray {
        unsigned int size;
        chessPos* positions;
    }chessPosArray;
    
    typedef struct _chessPosCell {
        chessPos position;
        struct _chessPosCell* next;
    }chessPosCell;
    
    typedef struct _chessPosList {
        chessPosCell* head;
        chessPosCell* tail;
    }chessPosList;

 

    void function_name(char* file_name, chessPosList* pos_list)
{

    FILE* file;
    short list_len;
    int i = 0;
    unsigned char row, col, byte_to_file, next_byte;
    chessPosCell* curr = pos_list->head;


    file = fopen(file_name, "wb"); /* open binary file to writing */
    checkFileOpening(file);

    
    while (curr != NULL)
    {
        row = curr->position[0] - 'A' - 17; /* 'A' ---> '1' ---> '0' */
        col = curr->position[1] - 1; /* '4' ---> '3' */

        if (remain < 6)
        { 
            curr = curr->next;
            remain += 8;                
        }

        if (i > 1)
        {
            i = 0;
        }

        if (curr->next != NULL)
        {
            next_byte = curr->next->position[i] >> (remain - 7);
            byte_to_file = ((row << (remain - 3)) | (col << (remain - 6))) | (next_byte);
            i++;
        }
        else
        {
            byte_to_file = ((row << (remain - 3)) | (col << (remain - 6)));
        }

        fwrite(&byte_to_file, sizeof(unsigned char), 1, file);

        remain -= 6;                    
             
    }

Answer 1

how can i make it work?

Since each location requires both a column and a row, you can actually think of a location as a single 6-bit value in which the lowest 3 bits are the row and the high 3 bits are the column. If you think of it that way, then the problem is a little bit simpler in that you're actually just talking about base-64 encoding/decoding, and there are lots of open-source implementations available if you really want to pack the data into the smallest possible space.

That said, I'd encourage you to consider whether your problem really requires minimizing the storage space. You could instead store those locations as characters, either using 4 bits for row and 4 for column, continue treating locations as 6-bit values and just ignore the two extra bits. Unless you're storing a huge number of these locations, the benefit of saving two bits per location isn't likely to matter.

Answer 2

how can i make it work?

Well, first start with a good abstraction. Anyway, it's actually pretty simple:

• let's take a 16-bit/2-byte buffer and a bit position within the buffer
  • it's way easier when the buffer is continues (uint16_t) instead of two separate bytes (unsigned char byte_to_file, next_byte). The next_byte bits just shift themselves and byte_to_file can be extracted with a mask.
• I "see" in my imagination MSB on the left and LSB on the right
• for each new 6-bits push it to the most left position that is not set yet
  • so shift of 16-6 minus the position
• if we filled more then 8 bits
  • take one byte and output it
  • and shift the buffer 8 bits to the left

Here's a sample program that prints Hello world\n:

#include <stdint.h>
#include <stdio.h>

struct bitwritter {
    FILE *out;
    // our buffer for bits
    uint16_t buf;
    // the count of set bits within buffer counting from MSB
    unsigned char pos;
};

struct bitwritter bitwritter_init(FILE *out) {
   return (struct bitwritter){ .out = out };
}

int bitwritter_write_6bits(struct bitwritter *t, unsigned char bits6) {
   // we always write starting from MSB
   unsigned char toshift = 16 - 6 - t->pos;
   // just a mask with 6 bits
   bits6 &= 0x3f;
   t->buf |= bits6 << toshift;
   t->pos += 6;
   // do we have whole byte?
   if (t->pos >= 8) {
      // extract the byte - note it's in MSB
      unsigned char towrite = t->buf >> 8;
      // shift out buffer
      t->buf <<= 8;
      t->pos -= 8;
      // write output
      if (fwrite(&towrite, sizeof(towrite), 1, t->out) != 1) {
             return -1;
      }
      return 1;
   }
   return 0;
}

int main() {
    struct bitwritter bw = bitwritter_init(stdout);
    // echo 'Hello world' | xxd -c1 -p | while read l; do python -c "print(\"{0:08b}\".format(0x$l))"; done | paste -sd '' | sed -E 's/.{6}/0b&,\n/g'
    unsigned char data[] = {
        0b010010,
        0b000110,
        0b010101,
        0b101100,
        0b011011,
        0b000110,
        0b111100,
        0b100000,
        0b011101,
        0b110110,
        0b111101,
        0b110010,
        0b011011,
        0b000110,
        0b010000,
        0b001010,
    };
    for (size_t i = 0; i < sizeof(data); ++i) {
        bitwritter_write_6bits(&bw, data[i]);
    }
}