</>EmbeddedInterview
← All problems · Algorithms

Run-Length Encoding

Medium

Implement size_t rle_encode(const uint8_t *in, size_t n, uint8_t *out, size_t cap) that writes pairs of (count, value) bytes. Runs longer than 255 are split. Return the number of bytes written, or 0 if out is too small (never write past cap).

RLE is used to compress display bitmaps, fonts and log data on small devices.

Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.

Walk the input with an index i. Count how many bytes starting at i equal in[i], stopping at 255. Emit the pair, then advance i by the count.

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

size_t rle_encode(const uint8_t *in, size_t n, uint8_t *out, size_t cap)
{
    size_t i = 0, o = 0;
    while (i < n) {
        uint8_t v = in[i];
        size_t run = 1;
        while (i + run < n && in[i + run] == v && run < 255) run++;
        if (o + 2 > cap) return 0;
        out[o++] = (uint8_t)run;
        out[o++] = v;
        i += run;
    }
    return o;
}

Plain RLE can double the size of data with no repeats, so real formats use a flag bit to mix literal runs and repeated runs (PackBits, the TGA format). The bounds check before each write is the important part: compression code that trusts its output buffer size is a common source of overflows.

Follow-up: write the decoder, checking that the expanded output fits its buffer before writing each run.

solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
    uint8_t out[16];
    const uint8_t a[] = { 7, 7, 7, 1, 2, 2 };
    const uint8_t ea[] = { 3, 7, 1, 1, 2, 2 };
    CHECK(rle_encode(a, sizeof a, out, sizeof out) == 6 && memcmp(out, ea, 6) == 0);
    uint8_t big[300]; memset(big, 0x55, sizeof big);
    const uint8_t eb[] = { 255, 0x55, 45, 0x55 };
    CHECK(rle_encode(big, sizeof big, out, sizeof out) == 4 && memcmp(out, eb, 4) == 0);
    CHECK(rle_encode(a, sizeof a, out, 5) == 0);        /* too small */
    CHECK(rle_encode(a, 0, out, sizeof out) == 0);
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}