Writing a stream of 9 bit values as bytes to a file in C

Question

I have an array with integer values from 0-511 (9 bits max). I am trying to write this to a file with fwrite.

For Example, with the array:

[257, 258, 259]
Which is 100000001, 100000010, 100000011

I am trying to write
100000001100000010100000011 + extra padding of 0s to the file

But since fwrite limits writes to 1 byte at a time, I am not sure how to go about doing this. I am new to bitwise operations and am not how to separate out the individual bytes.

Closely related to [Writing integer values to a file in binary using C](https://stackoverflow.com/questions/47504816/writing-integer-values-to-a-file-in-binary-using-c) — by the same OP and also about 9-bit values. — Jonathan Leffler, Nov 27 '17 at 07:44
Unless you're on some extremely unusual hardware, there are no 9-bit data types available. You have to store each "9-bit" value in a 16-bit datum in memory and on disk. You could in theory store 3 x 9-bit values in a single 32-bit unit, I suppose. At the moment, it is not clear what you're after or why. If you're working on 36-bit hardware, do say so; the rules suddenly change. There used to be such machines; I don't think there are many still running, but you could be about to educate me. — Jonathan Leffler, Nov 27 '17 at 07:47
@JonathanLeffler The previous Q was more general, in this one OP asks specifically a method/algo to optimally write n x 9-bits into (n x 9)/8+1 bytes. If a solution is released, we could then stuff it into the previous Q. — Déjà vu, Nov 27 '17 at 07:48
@RingØ: I marvel at your reading that from the question. I don't get that message, but I'm not particularly worried about that. I think clarification is in order, though. You have to know how the data was written to be able to retrieve it. I don't think you could write 1 unit, then 3 units, then 2 units, then 1 unit to disk and reliably read them in again unless you knew that was the sequence in which they were written. But I could be missing everything. — Jonathan Leffler, Nov 27 '17 at 07:50
@JonathanLeffler from both questions actually ;-) [didn't have the courage to write the bit-shifting stuff into the previous Q, and well, could be hidden somewhere else on SO...] (+another warning about endianness...) — Déjà vu, Nov 27 '17 at 07:51
@JonathanLeffler I am trying to implement an LZW compression algorithm. I have unsigned int values that range from 257-512 that I need to write to a file. Since these values are 9 bits, I am trying to pack them into 8 bits and read from them later. — user100663, Nov 27 '17 at 07:58
If the values range from 257-512, simply subtract 257 from the value and save the 8-bit quantity (0..255). That will save you endless headaches. On reading, add 257 back again. You'd have 16-bit quantities that you'd map to a sequence of 8-bit values, and you'd read an array of 8-bit values and expand them back into 16-bit quantities. — Jonathan Leffler, Nov 27 '17 at 07:59
@JonathanLeffler That could work. Sadly I need to pack the bits as this is for a school project. — user100663, Nov 27 '17 at 08:01
Have fun. I don't think even sadistic teachers would try to make you work with 9-bit data storage. It simply doesn't work sanely in a powers-of-2 world of computing sizes. — Jonathan Leffler, Nov 27 '17 at 08:02
The logical choise should be to write 16 bits integer. But if you need to save space it could be intersting understand how to "compress" this kind of data! — Sir Jo Black, Nov 27 '17 at 09:47
Your question would be more interesting if you'd elaborate on the *why* (in the question). A typical approach for data like that would be to pad the data to a multiple of 8 9bit-words and then write 8 times 8 bits, followed by an octet of most-significant bits. Even simpler and probably not worse in space efficiancy: just use 16bit words and a generic compression algorithm. — , Nov 27 '17 at 10:00
Incidentally, you should check your range. 512 needs a tenth bit; it isn't a 9-bit value. Did you mean 256..511? It doesn't affect the add/subtract 257 scheme; it might affect processing elsewhere. — Jonathan Leffler, Nov 27 '17 at 10:09

user694733 · Accepted Answer · 2017-12-04T08:56:29.253

You need a bit buffer.

Since you are writing 8 bits at the time, you must have data type that can hold at least 9+7 bits at minimum. uint16_t would do, but I recommend using size that would at least as big as your native int. Make sure you use unsigned types to avoid shifting issues.

uint32_t bitBuffer = 0;  // Our temporary bit storage
uint32_t count = 0;      // Number of bits in buffer

Let's assume we have single data:

uint32_t data9b = 257;  // 1 0000 0001

Adding bits to buffer is simple; just shift bits at the end of the buffer, and combine with OR.

bitBuffer |= (data9b << count); // At first iteration, shift does nothing
count += 9;                     // Update counter

After 9 bits are added, we can flush 8 bits to file.

while(count >= 8) {
    writeToFile(bitBuffer & 0xFF);  // Mask out lowest bits with AND
    bitBuffer >>= 8;                // Remove written bits
    count -= 8;                     // Fix counter
}

After each cycle you have 0 - 7 bits left over in the buffer. At the end of all data, if you finish with non-multiple of 8 bits, just write remaining contents of bitBuffer to file.

if(count > 0)
    writeToFile(bitBuffer);

score 1 · Answer 2 · answered Nov 27 '17 at 09:22

Ok, so did it using bit shifting, oring (can also do with *, '+', % and /) but shift is more appropriate / readable, imo.

// Your data, n is the number of 9-bits values
uint16_t dat[] = { 257, 258, 259 };
int i,n = sizeof(dat)/sizeof(*dat);

// out file
FILE *fp = fopen("f8.bin","w");

uint16_t one = 0;
int shift = 0;
uint8_t b;

// main loop
for(i=0 ; i<n ; i++) {
    b = (dat[i] << shift) | one; // one is remainder from previous value
    one = dat[i]>>(8-shift);     // Move the remaining MSb to the right
    shift = (shift+9) % 8;       // next shift
    fwrite(&b, 1, 1, fp);        // write our b byte
}
// remainder, always have a remainder
fwrite(&one, 1, 1, fp);
fclose(fp);

Had fun :-)

Writing a stream of 9 bit values as bytes to a file in C

2 Answers2

Linked