Base64-Transcoder

Eine Rust-Implementierung

Base64 ist ein sehr verbreiteter Algorithmus zur Kodierung und Dekodierung 8-Bit Zeichenfolgen. Dabei ist der Output der Kodierung eine Zeichenfolge, die nur aus ASCII-Zeichen besteht und damit für den Menschen noch halbwegs verständlich erscheint. Die Kodierung benötigt kein Dictionary wie ein solches, das zum Beispiel beim weitverbreiteten Lempel-Ziv-Algorithmus Anwendung findet. Stattdessen werden die 8-Bitfolgen direkt in 6-bitlange ASCII-Charaktere übersetzt. Im folgenden sieht man das Bit-Matching: drei 8er-Folgen des Inputsignals werden in 4 6er-Folgen des Outputsignals übersetzt.

7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 | Inputsignal

5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 5 4 3 2 1 0 | Outputsignal

Aus der Darstellung ist ersichtlich, dass es sich hierbei um keinen komprimierenden Algorithmus handelt. Als Referenzimplementierung lassen sich die JavaScript-Funktionen btoa und atob nutzen. Mit btoa lässt sich eine Zeichenkette mit Base64 kodieren. Die Funktion atob ist die Inverse, mit der sich eine Base64-Zeichenfolge wieder dekodieren lässt. Um meine eigene Implementierung auf Korrektheit zu überprüfen, nutze ich unter anderem diese Funktionen. Heißt ich kodiere eine Zeichenkette mit meiner Implementierung und dekodiere es mit btoa. Kommt die ursprüngliche Zeichenkette raus, ist meine Implementierung der encode-Funktion korrekt. Umgekehrt lässt sich die Korrektheit meiner Implementierung der decode-Funktion mit atob testen. Parallel dazu schreibe ich Tests direkt im Rust-Code, um bekannte Zeichenketten zu testen. Im Nachhinein kann ich sagen, dass beide Funktionen korrekt funktionieren und mir damit die Implementierung der Base64-Kodierung in Rust gelungen ist. Performance-Tests habe ich bisher nicht gemacht, da dies nicht der Fokus dieses Projektes war.

Die öffentliche API der Crate

Die von mir entwickelte Rust Crate ("Package") hat zwei Funktionen in der öffentlichen API: encode und decode. Mit Ersterer lässt sich eine Zeichenfolge in Base64 übersetzen. Mit Letztererer ist die Rücktransformation möglich. Ein Beispiel für die Nutzung der encode-Funktion wäre:

use base64_transcoder::encode;fn main() {    let test_str = "Hello World!";    let res = encode(test_str.as_bytes());    println!("base 64 encode result: {}", res);    // prints: base 64 encode result: SGVsbG8gV29ybGQh}

Die Signatur der Funktion ist:

pub fn encode(bits: &[u8]) -> String;

Sie akzeptiert als Parameter also eine Referenz ("Pointer") zu einem Array aus unsigned 8-Bit-Integers. Zurück gibt sie einen String ("owned", Daten auf der Heap) mit der Base64-Zeichenfolge.

Das Ergebnis können wir rücktransformieren um den ursprünglichen Text zu erhalten:

use base64_transcoder::{encode, decode};fn main() {    let test_str = "Hello World!";    let res = encode(test_str.as_bytes());    let res = decode(&res);    println!("base64 decode result: {}",        std::str::from_utf8(&res).unwrap());    //prints: base64 decode result: Hello World!}

Wie wir an der Signatur der decode-Funktion sehen können

pub fn decode(base64_string: &str) -> Vec<u8>;

gibt sie keinen String zurück, den wir direkt ausgeben können, wir müssen den zurückgegebenen Vector von unsigned 8-Bit-Integers erst noch mit std::str::from_utf8() in UTF8 umwandeln. Das liegt daran, dass die decode-Funktion nicht weiß, was für Daten sie dort hat. Wir könnten Base64 genauso gut nutzen, um ein Bild oder eine Audiodatei zu kodieren und könnten dafür die selben zwei Funktionen nutzen. Wir als Entwickler müssen uns dann darum kümmern, die dekodierten Daten wieder in das richtige Ausgabeformat umzuwandeln. Das gelingt in Rust dank der mächtigen Crate Serde mit den meisten Formaten aber ausgesprochen einfach.

Details zur Implementierung

Ich habe noch nie zuvor einen Kodierer geschrieben und auch mit Rust war ich noch nicht sehr vertraut, insofern stellte mich dieses Projekt vor viele neue Herausforderungen. Eine der interessantesten Fragestellungen war das Mapping von ASCII-Zeichen der Base64-Kodierung zurück zu 6er-Binärfolgen der ursprünglichen Daten. Die andere Richtung ist sehr einfach, jede 6er-Folge wird linear auf ein ASCII-Zeichen gemappt. So wird aus: 000000 -> A 000001 -> B 000010 -> C 000011 -> D und so weiter. Dies ermöglicht die Implementierung der Abbildung 6-Bitfolge -> ASCII-Charakter als Array:

const CHAR_MAP: [char; 64] = [    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',    'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',    'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '0', '1', '2', '3', '4',    '5', '6', '7', '8', '9', '+', '/',];

Die 6-Bitfolge ist hierbei der Index in das Array. Schwieriger ist die Rücktransformation. Die ASCII-Charaktere starten in ihrer Kodierung weder bei 0, noch liegen sie alle linear hintereinander. Eine direkte Implementierung als dicht gefülltes Array war nicht möglich, ich wollte aber auch nicht auf eine HashMap zurückgreifen, da die Initialisierung dieser Kosten der Performance hat. Die Lösung war ein nur zum Teil gefülltes Array, das wieder ein exaktes Abbilden der Dekodierung erlaubt:

const BYTE_MAP: [u8; 123] = [    0, // index 0    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // index 10    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // index 20    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // index 30    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // index 40    0, 0, 0, // index 43 - +    0, 0, 0, 0b11_1111, // index 47 - /    0b11_0100, // index 48 - 0    0b11_0101, 0b11_0110, // index 50    0b11_0111, 0b11_1000, 0b11_1001, 0b11_1010, 0b11_1011, 0b11_1100,    0b11_1101, // index 57 - 9    0, 0, 0, // index 60    0, 0, 0, 0, 0b00_0000, // index 65 - A    0b00_0001, 0b00_0010, 0b00_0011, 0b00_0100, 0b00_0101, // index 70    0b00_0110, 0b00_0111, 0b00_1000, 0b00_1001, 0b00_1010, 0b00_1011, 0b00_1100, 0b00_1101,    0b00_1110, 0b00_1111, // index 80    0b01_0000, 0b01_0001, 0b01_0010, 0b01_0011, 0b01_0100, 0b01_0101, 0b01_0110, 0b01_0111,    0b01_1000, 0b01_1001, // index 90 - Z    0, 0, 0, 0, 0, 0, 0b01_1010, // index 97 - a    0b01_1011, 0b01_1100, 0b01_1101, // index 100    0b01_1110, 0b01_1111, 0b10_0000, 0b10_0001, 0b10_0010, 0b10_0011, 0b10_0100, 0b10_0101,    0b10_0110, 0b10_0111, // index 110    0b10_1000, 0b10_1001, 0b10_1010, 0b10_1011, 0b10_1100, 0b10_1101, 0b10_1110, 0b10_1111,    0b11_0000, 0b11_0001, // index 120    0b11_0010, 0b11_0011, // index 122 - z];

Dabei werden zwar viele Leerstellen gelassen, die niemals verwendet werden, gleichzeitig ist die Abbildungstabelle dafür statisch und muss nicht initialisiert werden.

Die eigentlichen decode- und encode-Funktionen sind dann trivial. Sie iterieren über die übergebene Zeichenkette/Bitkette und parsen Gruppe für Gruppe in das richtige Format. Das gesamte Projekt ist hier auf Github zu finden.