HW 04 - RLE kodér

Termín odevzdání	5.11.2021 22:00 PT
Bodový zisk	4b
Počet uploadů	10 15
Typ zadání	povinné

Tato úloha slouží k procvičení cyklů a podmínek, není třeba používat pole (řešení bez použití pole je preferováno).

RLE kódování

RLE (run-length encoding) je bezeztrátová komprese, která kóduje vstupní data tak, že kóduje posloupnosti stejných hodnot do dvojic (délka posloupnosti, hodnota). Účinnost komprese je silně závislá na charakteru vstupních dat, která musí obsahovat delší sekvence stejných znaků, jinak výrazně účinnost komprese klesá.

Příklad vstupních dat kodéru RLE:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Výsledek kódování RLE (není výstupem programu řešícího HW04, pouze demonstrační):

W12B1W12B3W24B1W14

Implementace

Nejčastější implementace je komprese bytového proudu. Implementuje se pomocí dvojic bytů, jeden byte udává hodnotu kódovaného bytu (symbol), druhý byte určuje počet opakování. Nevýhoda je, že pro jeden neopakující se symbol v proudu bytů se kóduje tato hodnota pomocí dvojice bytů, proto pro nevhodná vstupní data může být komprese neúčinná a velikost proudu z výstupu kóderu RLE až dvojnásobná oproti vstupu. Proto pro naší implementaci zvolíme následující pravidla:

a) kódování neopakujícího se symbolu

A ⇒ A

b) kódování symbolů s jedním opakováním

AA ⇒ AA

c) kódování sekvence 3 - 255 stejných symbolů

AAA ⇒ A3

d) pro sekvence delší než 255 stejných symbolů proběhne kódování 'nadvakrát'. Následující příklad je zkáceným zápisem zakódování 257 znaků 'A'

A..A ⇒ A255AA

Aby bylo kódování efektivní, mělo by probíhat v binárním režimu, takže místo ASCII číslic se budou do výstupního proudu zapisovat přímo hodnoty bytů. Pak je třeba ověřit správnost výsledku v editoru, který umí zobrazit binární podobu souboru. Následující příklad ukazuje zakódování 66 opakování symbolu A (pro připomenutí, znak B má číselnou podobu v ASCII tabulce 66):

$ cat file.in
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
$ ./hw04 < file.in > file.out
$ cat file.out
AB
$ hexdump -C file.out
00000000  41 42 0a                                          |AB.|
00000003

V rámci tohoto domácího úkolu budeme místo binárního vyjádření počtu opakování používat dekadické číslice v ASCII kódování; bude jednodušší vizuální i automatická kontrola. Při výpočtu kompresního poměru pak ale bude třeba počítat s tím, že čísla větší než 9 jsou reprezentovány dvěma a více byty v ASCII kódování.

Povinné zadání

Program ze standardního vstupu načte symboly, které se mají kódovat.
Kódují se symboly, které patří do množiny velkých písmen ('A' - 'Z').
Kódování se řídí pravidly popsanými v sekci Implementace.
Pokud se na vstupu objeví symbol, který nepatří do této množiny, vypíše program na standardní chybový výstup zprávu: “Error: Neplatny symbol!\n” a program ukončete s návratovou hodnotou 100. Viz Příklad 4. Běh programu je v tomto případě okamžitě ukončen a výstupní soubor není ukončen znakem 0x0A.
Pokud se podaří zakódovat všechny vstupní symboly, vypíše se na standardní výstup zakódovaná sekvence a na standardní chybový výstup se vypíše dosažený kompresní poměr. Viz Příklad 1.
Vstupní ~~i výstupní soubor~~ jsou ukončeny znakem 0x0A, který se při výpočtu kompresního poměru nezapočítává.

Pro zobrazení šestnáctkového výstupu je použit následující příkaz:

$ hexdump -v -e '1/1 "%02X "' pub01.out

Příklad 1 - pub01

Vstupní hodnoty (stdin)	Výstup (stdout)	Chybový výstup (stderr)	Návratová hodnota
BWWBBBWWWWWWWBBBBBBBWWWBBBWWWWBBBWWWWWWBBBBBBBBBWWWWWWBBBBBB	BWWB3W7B7W3B3W4B3W6B9W6B6	Pocet vstupnich symbolu: 60 Pocet zakodovanych symbolu: 25 Kompresni pomer: 0.42	0

Příklad 2 - pub02

Vstupní hodnoty (stdin)	Výstup (stdout)	Chybový výstup (stderr)	Návratová hodnota
ABC	ABC	Pocet vstupnich symbolu: 3 Pocet zakodovanych symbolu: 3 Kompresni pomer: 1.00	0

Příklad 3 - pub03

Vstupní hodnoty (stdin)	Výstup (stdout hex)	Chybový výstup (stderr)	Návratová hodnota
AABTTT	AABT3	Pocet vstupnich symbolu: 6 Pocet zakodovanych symbolu: 5 Kompresni pomer: 0.83	0

Příklad 4 - pub04

Vstupní hodnoty (stdin)	Výstup (stdout)	Chybový výstup (stderr)	Návratová hodnota
ABBbdfbYYYY	ABB	Error: Neplatny symbol!	100

Odevzdání

Veřejné příklady + Makefile: hw04_-_rle.zip

	Povinné zadání
Název v BRUTE	HW04
Odevzdávané soubory	main.c
Argumenty při spuštění	žádné
Kompilace pomocí	clang -Wno-error=gnu-case-range -pedantic -Wall -Werror -std=c99 -O3
Procvičované oblasti	cykly a podmínky

Table of Contents