Skip to content

Instantly share code, notes, and snippets.

@RaphGL
Created September 20, 2023 15:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save RaphGL/cf6efa87082368b0658155059e577160 to your computer and use it in GitHub Desktop.
Save RaphGL/cf6efa87082368b0658155059e577160 to your computer and use it in GitHub Desktop.
Run-length encoding written in C11
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
size_t times;
char chr;
} RLEChar;
// Run length Encoding
// dest: a pointer to a buffer of RLEChar
// data: the data that will be encoded
// siz: the size of the data buffer
void rle_encode(RLEChar *dest, char *const data, size_t siz) {
// previous byte in data
char prev = data[0];
// counts how many times the byte has repeated sequentially
size_t count = 0;
// the dest index that's being written to
size_t rle_idx = 0;
for (size_t i = 0; i <= strlen(data); i++) {
const char curr = data[i];
if (curr == prev) {
count++;
} else {
// writes how many times the byte was repeated once it stops repeating
dest[rle_idx] = (RLEChar) {
.times = count,
.chr = prev,
};
// count is started at one so that it can include the byte
// in the current iteration
count = 1;
// we now check how many times the new value is repeated
// so we store it in prev to be able to do that
prev = curr;
// infinitely increments idx so we can always write to the next
// address in memory for the destination
rle_idx++;
}
}
}
// Run length Encoding
// dest: a pointer to a buffer of RLEChar
// data: the data that will be encoded
// siz: the size of the data buffer
// NOTE: this might cause a segfault if the decoded string is
// bigger than the destination buffer size.
void rle_decode(char *dest, RLEChar *data, size_t siz) {
// stores the next write index in memory in destination
size_t rle_idx = 0;
// siz indicates how big the buffer for data is
// we divide it by the size of each item (RLEChar)
// in it to get its length
for (size_t i = 0; i < (siz / sizeof(RLEChar)); i++) {
RLEChar rle_char = data[i];
// we repeat the byte rle_char.times
for (size_t j = 0; j < rle_char.times; j++) {
dest[rle_idx] = rle_char.chr;
++rle_idx;
}
}
}
int main(void) {
// strings
char * str = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW";
RLEChar rle_str[1000] = {0};
char decoded[1000] = {0};
// applying RLE to strings
rle_encode(rle_str, str, strlen(str));
rle_decode(decoded, rle_str, 1000 * sizeof(RLEChar));
// printing the encoded format in a prettier format
printf("RLE Encoded: ");
for (size_t i = 0; i < 1000 && rle_str[i].chr != '\0'; i++) {
const RLEChar rle_char = rle_str[i];
printf("%c%zu:", rle_char.chr, rle_char.times);
}
printf("\n");
// checking if it successfully decoded encoded string
if (strcmp(str, decoded) == 0) {
printf("Successfully decoded: %s", decoded);
} else {
printf("Failed decoding: expected \"%s\" found \"%s\"", str, decoded);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment