{{indexmenu_n>3}}
======== HW 04 - RLE kodér ========

^ Termín odevzdání |  <wrap important> 5.11.2021 22:00 PT</wrap> | 
^ Bodový zisk |  4b |
^ Počet uploadů |  <del>10</del> 15 | 
^ Typ zadání | povinné |

<note tip>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).</note>

===== 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: 
<code>
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
</code>

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

==== 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
<code>
A ⇒ A
</code>

b) kódování symbolů s jedním opakováním
<code>
AA ⇒ AA
</code>

c) kódování sekvence 3 - 255 stejných symbolů
<code>
AAA ⇒ A3
</code>

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'
<code>
A..A ⇒ A255AA
</code>

<note tip>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):

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

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í. 
</note>

======= 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: "''<fc #c78100>Error: Neplatny symbol!\n</fc>''" a program ukončete s návratovou hodnotou ''<fc #c78100>100</fc>''. 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í <del>i výstupní soubor</del> jsou ukončeny znakem ''0x0A'', který se při výpočtu kompresního poměru nezapočítává.


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

<code>
$ hexdump -v -e '1/1 "%02X "' pub01.out
</code>
</note>

==== Příklad 1 - pub01 ====

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

==== Příklad 2 - pub02 ====
^ Vstupní hodnoty (stdin) ^ Výstup (stdout)  ^ Chybový výstup (stderr)  ^ Návratová hodnota ^
| <code>
ABC
</code> |  <code>ABC</code>   | <code>
Pocet vstupnich symbolu: 3
Pocet zakodovanych symbolu: 3
Kompresni pomer: 1.00
</code> |  0  |

==== Příklad 3 - pub03 ====
^ Vstupní hodnoty (stdin) ^ Výstup (stdout hex)  ^ Chybový výstup (stderr)  ^ Návratová hodnota ^
| <code>
AABTTT
</code> |  <code>
AABT3
</code>   | <code>
Pocet vstupnich symbolu: 6
Pocet zakodovanych symbolu: 5
Kompresni pomer: 0.83
</code> |  0  |

==== Příklad 4 - pub04 ====
^ Vstupní hodnoty (stdin) ^ Výstup (stdout)  ^ Chybový výstup (stderr)  ^ Návratová hodnota ^
| <code>
ABBbdfbYYYY
</code> |  <code>ABB</code>   | <code>
Error: Neplatny symbol!
</code> |  100  |




====== Odevzdání ======

Veřejné příklady + Makefile: {{ :courses:b0b99prpa:hw: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  |