Skip to content

Instantly share code, notes, and snippets.

@Druid-of-Luhn
Last active November 28, 2018 17:39
Show Gist options
  • Save Druid-of-Luhn/6229cdbbc4bd2bc879a68e615a40ed60 to your computer and use it in GitHub Desktop.
Save Druid-of-Luhn/6229cdbbc4bd2bc879a68e615a40ed60 to your computer and use it in GitHub Desktop.
C bit compression
#include <stdlib.h>
#include <stdio.h>
#define BYTE_SIZE 8
size_t compress_code(const int *code, const size_t code_length, unsigned char **compressed)
{
if (code == NULL || code_length == 0 || compressed == NULL) {
return 0;
}
// Round the number of compressed characters up, so that no bits are lost
size_t compressed_length = (code_length + BYTE_SIZE - 1) / BYTE_SIZE;
*compressed = calloc(compressed_length, sizeof(char));
// Loop over the bits to be compressed, but do not go beyond the end of the characters that are
// being written to. This should not happen, but is a safeguard in case of an error in the code.
for (size_t char_counter = 0, i = 0; char_counter < compressed_length && i < code_length; ++i) {
// Move on to the next compressed char when the previous one has been filled
if (i > 0 && (i % BYTE_SIZE) == 0) {
++char_counter;
}
// Shift every bit in the compressed character to the left by one space.
// This opens one space at the rightmost end (with a 0), to which we can write
// the desired bit.
(*compressed)[char_counter] <<= 1;
// Set the current bit in the array and force it to be 0 or 1
(*compressed)[char_counter] |= (code[i] & 1);
}
// Pad the data out with 0s on the rightmost end, instead of leaving initial
// bits on the leftmost end
(*compressed)[compressed_length - 1] <<= compressed_length * BYTE_SIZE - code_length;
return compressed_length;
}
int main(void)
{
// Replace this with the output of your Huffman coder
const int code[] = { 0, 1, 0, 0, 0, 0, 0, 1, // 65: A
0, 1, 0, 0, 0, 0, 1, 0 }; // 66: B
const size_t code_length = 16;
unsigned char *compressed = NULL;
size_t compressed_length = compress_code(code, code_length, &compressed);
for (size_t i = 0; i < compressed_length; ++i) {
printf("%c\n", compressed[i]);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment