Created
September 20, 2023 15:14
-
-
Save RaphGL/cf6efa87082368b0658155059e577160 to your computer and use it in GitHub Desktop.
Run-length encoding written in C11
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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