Base64 is een manier om binaire bestanden te converteren naar tekst bestaande uit ASCII1-karakters. Dit gebeurt door binaire data te beschouwen als cijfers uit het talstelsel met grondtal $$2^6 = 64$$. Hierbij zijn 6 bits nodig om alle verschillende cijfers uit dit talstelsel te kunnen voorstellen. Drie bytes van 8 bits vormen samen 24 bits, en kunnen dus voorgesteld worden door $$4 \times 6$$ bits in de base64 codering.

De 64 verschillende karakters die gebruikt worden om de cijfers uit het 64-tallig stelsel voor te stellen, variëren tussen de verschillende implementaties. De algemene strategie is om 64 karakters te gebruiken die voorkomen in de doorsnede van de meeste karaktercoderingen en die ook afdrukbaar zijn. Hierdoor wordt het weinig waarschijnlijk dat de gegevens zullen gewijzigd worden bij uitwisseling tussen verschillende informatiesystemen (bijvoorbeeld email). Zo gebruikt de base64-implementatie van MIME2 een reeks karakters die bestaat uit de 26 hoofdletters (A-Z), de 26 kleine letters (a-z), de 10 cijfers (0-9), het plusteken (+) en de slash (/).

waarde karakter   waarde karakter   waarde karakter   waarde karakter
0 A 16 Q 32 g 48 w
1 B 17 R 33 h 49 x
2 C 18 S 34 i 50 y
3 D 19 T 35 j 51 z
4 E 20 U 36 k 52 0
5 F 21 V 37 l 53 1
6 G 22 W 38 m 54 2
7 H 23 X 39 n 55 3
8 I 24 Y 40 o 56 4
9 J 25 Z 41 p 57 5
10 K 26 a 42 q 58 6
11 L 27 b 43 r 59 7
12 M 28 c 44 s 60 8
13 N 29 d 45 t 61 9
14 O 30 e 46 u 62 +
15 P 31 f 47 v 63 /

Opgave

Elke regel van het tekstbestand base64.txt3 bestaat uit een patroon $$p \in \mathcal{P}$$, gevolgd door een spatie en een woord $$w \in \mathcal{W}$$. De verzameling $$\mathcal{C}$$ bevat alle afdrukbare karakters: hoofdletters, kleine letters, cijfers en leestekens. Deze verzameling bevat dus geen witruimtekarakters (spaties, tabs, newlines, …). De verzameling $$\mathcal{P}$$ bevat alle mogelijke coderingen: strings die enkel bestaan karakters die behoren tot de verzameling $$\mathcal{C}$$. De verzameling $$\mathcal{W}$$ bevat alle woorden die enkel bestaan uit letters. Gevraagd wordt:

  1. Bepaal zo kort mogelijke reguliere expressies voor de volgende deelverzamelingen van $$\mathcal{P}$$:

    • $$\mathcal{P}_1 = \{\,p \in \mathcal{P}\,|\,p\ $$bevat karakters die niet voorkomen in de base64-implementatie van MIME$$\,\}$$

      voorbeeld: FR+w0|^Z4<bq_,WVT{%xfVxdB<>0JY phis $$\in \mathcal{P}_1$$

    • $$\mathcal{P}_2 = \{\,p \in \mathcal{P}\,|\,p\ $$bevat vier of meer opeenvolgende cijfers, ingesloten tussen slashes$$\,\}$$

      voorbeeld: Q4HXD/7100525/+wgzC5mV2IimhFXh falcate $$\in \mathcal{P}_2$$

    • $$\mathcal{P}_3 = \{\,p \in \mathcal{P}\,|\,$$er is een cijfer dat minstens vier keer voorkomt in $$p\,\}$$

      voorbeeld: ZU4mg4I4BAVUzm5lfAbm4r9reE9zyk tarweeds $$\in \mathcal{P}_3$$

    • de verzameling $$\mathcal{P}_4$$ bestaat uit de regels die geselecteerd worden door de volgende twee commando's; beide commando's selecteren exact dezelfde regels

      # eerste alternatief
egrep -i '(.+).* \1$' base64.txt

# tweede alternatief
rev base64.txt | egrep -i '^(.*) .*\1' | rev

      1. omschrijf in woorden welke regels door deze commando's geselecteerd worden

      2. leg uit waarom de ene oplossing veel sneller werkt dan de andere

    Geef telkens een Unix commando waarin de reguliere expressie gebruikt wordt door een commando uit de grep familie om enkel de regels van het tekstbestand naar stdout te schrijven waarvan het patroon $$p$$ behoort tot $$\mathcal{P}_i\ (i = 1, 2, 3, 4)$$.

    Opmerking

    Gebruik voor deze opgave een recente versie van GNU grep. Op helios is een recente versie van GNU grep geïnstalleerd, maar Mac OS X gebruikt standaard typisch een oudere versie van GNU grep. Mac gebruikers kunnen voor de zekerheid dus best hun grep versie updaten naar de meest recente versie.

  2. Bepaal als volgt de woorden $$w_1\ w_2\ w_3\ w_4$$ van een geheime boodschap:

    • het woord $$w_1$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_1 \cap \mathcal{P_2}$$

    • het woord $$w_2$$ staat op de unieke regel waarvan $$p$$ behoort tot $$ \mathcal{P}_2 \cap \mathcal{P_3}$$

    • het woord $$w_3$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_3  \cap \mathcal{P_4}$$

    • het woord $$w_4$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_4 \cap \mathcal{P_1}$$

    Geef telkens een Unix commando waarin de reguliere expressies voor de verzamelingen $$\mathcal{P}_i\ (i = 1, 2, 3, 4)$$ gebruikt worden door commando's uit de grep familie om het woord $$w_j\ (j = 1, 2, 3, 4)$$ op te zoeken in het tekstbestand en uit te schrijven naar stdout. Hierbij is het niet toegelaten om het woord $$w_j$$ letterlijk uit te schrijven (bv. echo $$w_j$$).