Kódování a dekódování Base64

(2017)



Teorie k realizaci Base64 dekodéru:
Base64 je formát pro uložení binárního souboru tak, aby výsledný textový soubor obsahoval pouze základní tisknutelné znaky. (Je využito např. u příloh v emailu, kde je při odesílání podporován pouze textový způsob komunikace tj. 7bit ASCII).

Vaším úkolem je implementovat dekodér formátu Base64 a pomocí něj rozkódovat připravenou zprávu. Při řešení úkolu si procvičíte práci s řetězci, operace bitového posuvu a bitového maskování.

 

Popis formátu Base64:
Formát kóduje vždy 3 osmibitové znaky/bajty na 4 znaky z množiny 64 znaků, proto Base64. Množina 64 znaků obsahuje tyto znaky:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Předchozí řádek (převodní pole pro znaky) slouží k převodu přijatého znaku na index = pozice znaku v tomto řádku. Nebo pro převod indexu na výstupní znak.

Princip kódování popisuje nákres níže, kde jsou vždy 3 osmibitové znaky původní zprávy rozděleny na 4 skupiny po 6 bitech. Jednotlivé skupiny po 6 bitech (tj. 64 kombinací) potom představuji vždy index do základní Base64 množiny, ze které je následně vybrán znak na pozici indexu.

Vstupní zpráva (tři 8bitové hodnoty):



X7X6X5X4X3X2X1X0

Y7Y6Y5Y4Y3Y2Y1Y0

Z7Z6Z5Z4Z3Z2Z1Z0

Výsledná zakódovaná zpráva (čtyři 6bitové hodnoty, následně převedené na čtyři znaky Base64):

X7X6X5X4X3X2

X1X0Y7Y6Y5Y4

Y3Y2Y1Y0Z7Z6

Z5Z4Z3Z2Z1Z0

 

Zakončovací (zarovnávací) sekvence:
Vstupní (kódovaný) soubor je vždy čten po 3 znacích (bajtech) a na výstup jsou vždy odeslány 4 znaky. Proto je třeba pro soubory délky nedělitelné bezezbytku třemi, doplnit na vstupní straně chybějící znaky (doplňuje se vždy znak s hodnotou \0) a na výstupní straně odlišit doplněné znaky od původních (znak =). Tímto je zajištěno, že správně zakódovaná zpráva má počet znaků vždy dělitelný čtyřmi a zároveň je možné určit přesnou velikost původního souboru.

Příklady koncového zarovnání na výstupní délku čtyř znaků v případě chybějících bajtů na vstupu:

Vstup (pouze jedna 8bitová hodnota / bajt):

X7X6X5X4X3X2X1X0

Výstup (dvě 6bitové hodnoty převedené na Base64 znaky a dva doplňující znaky =):

X7X6X5X4X3X2

X1X00 0 0 0

=

=

 

Vstup (pouze dvě 8bitové hodnoty / bajty):

X7X6X5X4X3X2X1X0

Y7Y6Y5Y4Y3Y2Y1Y0

Výstup (tři 6bitové hodnoty převedené na Base64 znaky a jeden doplňující znak =):

X7X6X5X4X3X2

X1X0Y7Y6Y5Y4

Y3Y2Y1Y00 0

=

 

Zadání base64 dekodér:
Sestavte program v jazyce C, který správně rozkóduje zadaný textový soubor.

1.      Navrhněte strukturu funkcí programu, včetně kontrol.

2.      Navrhněte a implementujte funkci pro převod znaku Base64 na jeho index v množině povolených znaků (při výskytu nepovoleného znaku generujte chybové hlášení).

3.      Navrhněte a implementujte funkci pro dekódování (čtveřice 6bitových znaků na 3 osmibitové).

4.      Využijte tuto funkci při postupné konverzi vstupního souboru.

5.      Ošetřete chybové stavy (špatná délka vstupu, chybný znak ...).

6.      Ověřte, že daný program umožňuje dekódovat i zakódované binární soubory.

 

Postup práce (doporučení):
Nesnažte se naprogramovat vše najednou. Postupujte po částech.

  1. Na papír si vyřešte převod pro první čtveřici znaků testovacího textu


    Vstupní znaky

    '...'

    '...'

    '...'

    '...'

    Pozice znaku v převodním poli (dekadicky/hexa)

    I1:

    I2:

    I3:

    I4:

    Pozice binárně

























    Převod šestic na osmice

























    Osmice hexa/dekadicky

    O1:

    O2:

    O3:

  2. Napište funkci na převod z binárních šestic (pole čtyř znaků – v počítači uložené v osmi bitech) do osmic (pole tří osmibitových znaků)
    Realizace polí v paměti (nuly ze vstupního řádku se při přesunu do výsledku „vypouští“).

    Vstup I (4x8 bitů)
    pozice bitů/hodnota

    8
    0

    7
    0

    6

    5

    4

    3

    2

    1

    8
    0

    7
    0

    6

    5

    4

    3

    2

    1

    8
    0

    7
    0

    6

    5

    4

    3

    2

    1

    8
    0

    7
    0

    6

    5

    4

    3

    2

    1

    Výstup O (3x8bitů)
    pozice bitů

    8

    7

    6

    5

    4

    3

    2

    1

    8

    7

    6

    5

    4

    3

    2

    1

    8

    7

    6

    5

    4

    3

    2

    1

    Pro binární operace používejte bezznaménkové typy. Pro práci se znaky použijte nejmenší celočíselný datový typ (unsigned char).
    Ve funkci používejte operátory bitového posunu (doprava a doleva) o daný počet znaků – pro unsigned typy se při posunu doplňují nuly. Dále používejte operátory bitového součtu a součinu (OR a AND).
    Napište si na papír jak se vytvoří výstupní data (O1, O2, O3) v závislosti na vstupních datech (I1,I2,I3,I4) pomocí binárních operátorů jazyka C a pro ověřte zda funguje pro první čtveřici znaků. (Například první výstup O1 (šedá) má na třetím bitu zprava první bit I1 (žlutá) – I1 je tedy nutné posunout tak aby se její první bit objevil na třetí pozici. Dále jsou v O1 na prvních dvou bitech bity 6 a 5 I2 (oranžová), je tedy nutné I2 posunout tak, aby se bity 6 a 5 objevili na pozici 2 a 1).
    Možná hlavička funkce: int Prevod( datový_typ Input[4], datový_typ Output[3])
    Ve funkci main si vytvořte pole o čtyřech znacích, do kterého vložíte (pro účely testování) hodnoty z druhého řádku tabulky z bodu 1. Dále vytvořte pole pro uložení výsledku. Zavolejte funkci Prevod s těmito poli a překontrolujte zda převod proběhl správně.
    V jazyce C se volající a volaná funkce „dělí“ o předané pole – změny provedené v poli ve volané funkci se proto objeví i ve funkci volající.
    Funkce main s ukázkami volání bude v souboru base64main.c, funkce budou v souboru fbase64.c a příslušné hlavičky v fbase64.h.

  3. Napište funkci, která zjistí (a vrátí) pozici předaného znaku v převodním poli. Možná hlavička funkce: datový_typ Pozice(datový_typ PrevadenyZnak).
    Řešení je možné dvojí:
    První řešení: vytvoří se pole znaků, které se naplní převodním polem. Pomocí cyklu se postupně srovnává PrevadenyZnak se znakem v poli. Při souhlasu znaků jsme zjistili pozici znaku v poli a to je návratová hodnota. Toto řešení je programově jednoduché ale při provádění je časově náročné.
    Druhé řešení vychází z toho, že v převodním poli jsou bloky za sebou jdoucích znaků a tedy převod pro velká písmena může vypadat takto:
    if (PrevadenyZnak je velké písmeno) return (PrevadenyZnak – 'A');
    Obdobně provedeme převod i pro malá písmena a číslice s tím, že malá písmena začínají na pozici off = 'Z'-'A'+1 (na této pozici je malé a).
    Problém by mohl tvořit vyplňovací/ukončovací znak '='. Pokud by jeho ASCII hodnota ležela v intervalu pozic písmen tabulky (do hodnoty 64), musí být převeden na hodnotu větší než 64 (například 254).
    Ve funkci main zavolejte tuto funkci postupně pro první čtyři znaky a výsledky uložte tak, aby byly připraveny jako vstupní parametr pro funkci z bodu 2). Ověřte zda funguje.
    Při tvorbě je možné se inspirovat zde.

  4. Po odladění první čtveřice následuje (pokus o) převod celého textu. Vytvořte si pole, do kterého vložíte testovací řetězec znaků (při kopírování řetězce z těchto stránek odstraňte formátovací znaky (které se projeví jako (skryté) mezery v textu, a převeďte celý text na jeden řádek). Napište cyklus, ve kterém budete ze vstupního řetězce brát čtveřice znaků (, které po převodu pomocí funkce z bodu 3) překopírujete do pole, které je použité jako pole vstupních parametrů funkce z bodu 2)). Postupně převeďte všechny čtveřice vstupního textu. Výsledek převodu vytiskněte na konzolu.

  5. Funkci Prevod z bodu 2) upravte/doplňte tak, aby převáděla i poslední čtveřici. To znamená, že pokud je posledním znakem rovná se, převedou se pouze dva znaky a pokud jsou na konce dvě rovná se, převede se pouze jeden znak. Návratová hodnota funkce potom může značit kolik znaků bylo převedeno.



Upravte program tak, aby zpracoval soubor jehož název je dán na příkazovém řádku. Další parametr na příkazovém řádku bude název výstupního souboru (například prevod.exe s64.txt svysl.txt)

Soubor pro testy je zde.



Budete-li mít čas, naprogramujte i kodér Base64.



Testovací zpráva:
Využijte soubor získaný na adrese:

http://www.uamt.feec.vutbr.cz/~petyovsky/vyuka/bppc/base64/base64_message.php

Případně testovací text:

KiogVG90byBqZSB6YWtvZG92YW5hIHpwcmF2YSAqKgpQb2t1ZCBqc2kgamkgc3ByYXZuZSByb3prb2Rv
dmFsLCByZWtuaSBuYWhsYXM6CiJIZWxlIHZlbmt1IHByc2k/IgoqKiogS29uZWMgenByYXZ5ICoqCg==



Ukázka řešení první čtveřice:

První čtveřice: Kiog se převede na trojici ???
Kiog (jedná se vlastně o čtyři znaky 'K' 'i' 'o' 'g' v paměti jsou uloženy pomocí ASCII reprezentace obsahující hodnoty: 4B, 69, 6F, 67.
Nyní musíme najít pozici každého znaku v tabulce „AB....89+/“ → 0A, 22,28,20 hexa (tj. 10,34,40,32 dekadicky)
Tyto hodnoty mají bitovou reprezentaci v 6-ti bitové (BASE64) logice : 001010 100010 101000 100000
V paměti jsou ovšem uloženy v 8-mi bitových jednotkách: 0000 1010 / 0010 0010 / 0010 1000/ 0010 0000.
Tyto je nutné „přeskládat“ do tří osmibitových bytů: 0010 1010 / 0010 1010 / 0010 0000
Toto jsou již výstupní hodnoty: 2A, 2A, 20
Výstupní hodnoty mohou reprezentova (ale obecně nemusí – můžeme převádět i soubory pdf, jpg, png …) text. V tom případě jsme dostali ASCII hodnoty znaků. Po zobrazení hodnot získáváme znaky '*' '*' ' ' (tj. Hvězdička, hvězdička, mezera).





Literatura:
http://cs.wikipedia.org/wiki/Base64

http://en.wikipedia.org/wiki/Base64

 







Poslední úpravy 2017-02-23