Atome der digitalen Welt – 2

von | Nov 28, 2021 | PowerShell, Grundlagen | 0 Kommentare

Atome der digitalen Welt – 2

Dieses kleine Code-Projekt ist inspiriert von Franz Fialas Text und Code auf https://clubcomputer.at/2021/11/24/atome-der-digitalen-welt/

Der Facebook-Account von Mimikama postete auf Facebook kommentarlos folgendes (https://www.facebook.com/mimikama.at/posts/269868261849482

Der Inhalt ist in der Datei raetsel.txt nachzulesen.

Dieses Posting hatte ein großes Echo, fast 1000 Kommentare in einem Tag. Bei einer groben Durchsicht der etwas verunsicherten Kommentatoren fand sich aber kein Interpret dieser Zahlenfolge.

Die Aufgabe besteht nun darin, diese Zahlenfolge lesbar zu machen. Als Sprache wurde PowerShell gewählt.

Die Annahme besteht darin, dass es sich um codierten Text handelt. Jeweils ein Block aus acht 0en und 1en (Oktett) stellt dabei die binäre Codierung eines Zeichens dar.

Die Aufgabenstellung lautet nun, ein Programm zu schreiben, das den Text lesbar macht.

Lösung 1: Die alte Schule (inspiriert durch den Algorithmus von Franz Fiala)

# Decodiere eine binär als 0 und 1 codierte Textdatei.

#region Initialisierung

$eingabedateiPfad = '.\raetsel.txt'

# In dieser Variable werden wir das Ergebnis speichern
$nachricht = ''

#endregion Initialisierung

#region Eingabe

$eingabeText = Get-Content -Path $eingabedateiPfad

#endregion eingabe

#region Verarbeitung

<#
    Die Zeilen der Eingabedatei werden in einem Array von Strings gespeichert.
    Wir gehen die Elemente des Arrays mit foreach durch, um jede Zeile zu
    verarbeiten.
#>
foreach ($zeile in $eingabeText) {
    #region Verarbeitung

    # Wir verarbeiten die Bits jeder Zeile in 8er-Blöchen
    for ($p = 0; $p -lt $zeile.Length; $p += 8) {
        #region Initialisierung

        # $dezimalzahl soll den Zahlenwert der Binärzahl enthalten und ist zunächst 0
        $dezimalzahl = 0

        #endregion

        #region Eingabe

        # Wir nehmen die nächsten 8 Zeichen ab $p
        $oktett = $zeile.Substring($p, 8)

        #endregion Eingabe

        #region Verarbeitung
        
        # 8 Zeichen der Zeile werden gelesen, beginnend bei der höchsten Stelle
        for ($i = 0; $i -lt 8; $i++) {
            
            <# 
                $oktett[$i] ist die i-te Stelle und kann entweder "0" (= 
                ASCII-48) oder "1" (= ASCII-49) sein. Zieht man 48 ab, erhält
                man 0 oder 1. Man zählt diesen Wert zu $dezimalzahl und verdoppelt vorher 
                $dezimalzahl. Der Grund für diese Verdoppelung ist, dass jede Stelle den 
                doppelten Wert der jeweils nächsten hat. Nach der 8. 
                Wiederholung wurde also ein 1er an der ersten Stelle mit 2 ^ 7 =
                128 multipliziert.
            #>
            $dezimalzahl = $dezimalzahl * 2 + ($oktett[$i] - 48)
        }
        
        <# 
            Damit die Zahl als Zeichen ausgegeben wird, muss man sie vorher in 
            ein Zeichen umwandeln
        #>
        $zeichen = [char]$dezimalzahl

        #endregion Verarbeitung

        #region Ausgabe

        $nachricht += $zeichen

        #endregion Ausgabe
    }
}

#endregion Verarbeitung

#region Ausgabe

Clear-Host
Write-Host $nachricht

#endregion Ausgabe

Mit einer for-Schleife werden die Zeichen in 8er-Blöcken verarbeitet. Bemerkenswert dabei ist, dass eine for-Schleife die Zählervariable nicht immer nur um 1 erhöhen kann, sondern auch um andere Werte, z. B. 8.

Mit der Substring-Methode aus dem .NET-Framework Teilstrings extrahiert werden. Beispiel:

$zeile = '01010101011011100111001100100000011101110111'
$p = 8
$oktett = $zeile.Substring($p, 8) # ergibt 01101110

Der erste Parameter gibt dabei die Startposition an. Der zweite Parameter gibt die Anzahl der Zeichen an, die ab der Startposition zurückgegeben werden. Wird der zweite Parameter weggelassen, wird der gesamte verbleibenden String zurückgeliefert.

Eine zweite innere for-Schleife verarbeitet dann die einzelnen Zeichen als Bits und bildet mit dem bekannten Algorithmus zur Umwandlung einer Binärzahl in eine Dezimalzahl eine Dezimalzahl.

Auf ein einzelnes Zeichen eines Strings greift man in PowerShell am besten mit

$oktett[$i]

zu, wobei $i die Position des Zeichens ist. Behandelt man ein Zeichen in Berechnungen wie eine Zahl, so wird der Unicode des Zeichens verwendet. Dazu muss man wissen, dass '0' den Unicode 48 hat und '1' den Unicode 49. $c - 48 ergibt also 0 oder 1, je nachdem, ob $c vorher '0' oder '1' war.

Zuletzt muss die ermittelte Dezimalzahl wieder in ein Zeichen umgewandelt werden. Dies erfolgt am einfachsten durch

$zeichen = [char]$dezimalzahl

Mit diesen Informationen sollte es auch PowerShell-Einsteigern nicht allzu schwerfallen, die Lösung zu programmieren.

Wer lieber gleich einen Blick auf die Lösung werfen möchte, findet diese in der Datei bin2text.ps1.

Die Lösung hat das Problem, dass Umlaute nicht richtig dargestellt werden. Außerdem werden im modernen Windows Terminal oder in Visual Studio Code bedingt durch die fehlende Decodierung von Unicode als Steuerzeichen interpretiert, was die Anzeige verstümmelt. Im klassischen conhost.exe von Windows ist die Darstellung mit Ausnahme der Umlaute hingegen korrekt. Wir werden uns diesem Problem in der Lösung 3 widmen.

Lösung 2: Lassen wir uns durch das .NET-Framework helfen

# Decodiere eine binär als 0 und 1 codierte Textdatei.

#region Initialisierung

$eingabedateiPfad = '.\raetsel.txt'

# In dieser Variable werden wir das Ergebnis speichern
$nachricht = ''

#endregion Initialisierung

#region Eingabe

$eingabeText = Get-Content -Path $eingabedateiPfad

#endregion eingabe

#region Verarbeitung

<#
    Die Zeilen der Eingabedatei werden in einem Array von Strings gespeichert.
    Wir gehen die Elemente des Arrays mit foreach durch, um jede Zeile zu
    verarbeiten.
#>
foreach ($zeile in $eingabeText) {

    # Verarbeite die Zeichen 0 und 1 in 8er-Blöcken
    for ($p = 0; $p -lt $zeile.Length; $p += 8) {
        #region Eingabe

        # Extrahiere einen 8er-Block
        $oktett = $zeile.Substring($p, 8)

        #endregion Eingabe

        #region Verarbeitung
            
        <#
            Jetzt konvertieren wir die binäre Repräsentation unseres
            Zeichens in eine Dezimalzahl. Dabei hilft uns das
            .NET-Framework.
        #>

        $dezimalzahl = [convert]::ToInt32($oktett, 2)

        # Eine Zahl kann direkt in ein Zeichen konvertiert werden

        $zeichen = [char] $dezimalzahl
        
        #endregion Verarbeitung

        #region Ausgabe

        # Nun hängen wir das ermittelte Zeichen an unsere Nachricht an

        $nachricht += $zeichen

        #endregion Ausgabe

    }
}

#region Ausgabe

Clear-Host
Write-Host $nachricht

#endregion Ausgabe

Die innere Schleife aus Lösung 1, die die Zeichen einzeln in eine Dezimalzahl umwandelt, kann durch einen simplen .NET-Befehl ersetzt werden. Die statische Funktion ToInt32 der Klasse convert kann einen Text in eine Zahl umwandeln, wobei der zweite Parameter die Basis angibt. 2 steht dabei für binär, 16 würde für hexadezimal stehen usw. Ein Typ muss in PowerShell wie immer in eckigen Klammern geschreiben werden. Eine statische Methode wird von der Klasse durch zwei Doppelpunkte getrennt. Beispiel:

$dezimalzahl = [convert]::ToInt32($oktett, 2)

Immerhin spart die Lösung 2 gegenüber Lösung 1 sage und schreibe 3 Zeilen Code (Kopf und Fuß der for-Schleife und die Initialisierung von $zeichen), wie anhand der Datei bin2text2.ps1 leicht nachgeprüft werden kann.

Lösung 3: Widmen wir uns den Unicode-Zeichen

<#
    Decodiere eine binär als 0 und 1 codierte Textdatei. Der Text ist als UTF-8
    codiert. Für Details zu UTF-8 siehe z. B. 
    https://en.wikipedia.org/wiki/UTF-8
#>

#region Initialisierung

$eingabedateiPfad = '.\raetsel.txt'

# In dieser Variable werden wir das Ergebnis speichern
$nachricht = ''

#endregion Initialisierung

#region Eingabe

$eingabeText = Get-Content -Path $eingabedateiPfad

#endregion eingabe

#region Verarbeitung

<#
    Die Zeilen der Eingabedatei werden in einem Array von Strings gespeichert.
    Wir gehen die Elemente des Arrays mit foreach durch, um jede Zeile zu
    verarbeiten.
#>
foreach ($zeile in $eingabeText) {

    # Verarbeite die Zeichen 0 und 1 in 8er-Blöcken
    for ($i = 0; $i -lt $zeile.Length; $i += 8) {
        #region Initialisierung

        $zeichen = ''

        #endregion Initialisierung

        #region Eingabe

        # Extrahiere einen 8er-Block
        $oktett = $zeile.Substring($i, 8)

        #endregion Eingabe

        #region Verarbeitung

        <#
            In UTF-8 kann jedes Zeichen 1 - 4 Oktette lang sein. Wenn ein
            Zeichen aus mehr als einem Oktett besteht, beginnen die
            nachfolgenden Oktette mit binär 10. Diese müssen hier übersprungen
            werden.
        #>
        if ($oktett.Substring(0, 2) -ne '10') {
            <#
                Die Anzahl der Oktette, aus denen ein Zeichen besteht wird durch
                die höchst signifikanten (linken) Bits definiert. Diese werden
                immer durch ein 0-Bit terminiert. Sind die zwei linken Bits
                gesetzt, besteht das Zeichen aus 2 Oktetten, bei 3 Bits aus 3,
                usw.
                Um die Anzahl der Oktette zu ermitteln, suchen wir ab der 
                aktuellen Position $i nach der nächsten 0. Da die Positionen
                immer bei 0 zu zählen beginnen, definiert die Position der 0 die
                Anzahl der Oktette.
            #>
            $anzahlOktette = $zeile.Substring($i).IndexOf('0')
            <#
                Vom ersten Oktett müssen nun die Bits bis zum ersten 0-Bit
                entfernt werden. Wir speichern die binäre Repräsentation des
                Zeichens nun laufend in der Variable $binaer
            #>
            $binaer = $zeile.Substring(
                $i + $anzahlOktette + 1,
                8 - $anzahlOktette - 1
            )

            <#
                Es gibt den Sonderfall der ersten 127 Zeichen. Bei diesen ist
                schon das erste Bit 0 (ASCII-Kompatibilität). Bei diesen Zeichen
                wird die nachfolgende for-Schleife nicht ausgeführt.
                In allen anderen Fällen durchlaufen wir nun die nachfolgenden
                Oktette. Ausnahmsweise beginnen wir mit 1 zu zählen, um uns das
                laufende Addieren von 1 zu ersparen
            #>

            for ($z = 1; $z -lt $anzahlOktette; $z++) {

                #region Initialisierung

                $binaerTeil = ''

                #endregion Initialisierung

                #region Eingabe

                # Extrahiere den nächsten 8er-Block
                $oktett = $zeile.Substring($i + $z * 8, 8)

                #endregion Eingabe

                #region Verarbeitung

                <# 
                    Überprüfe, ob die ersten zwei Bits 10 sind. Das kennzeichnet
                    ein Fortsetzungsoktett. Das sollte immer der Fall sein, aber
                    Vorsicht ist die Mutter der Porzellankiste. :-)
                #>
                if ($oktett.Substring(0, 2) -eq '10') {
                    <#
                        Die ersten zwei Bits des Oktetts lassen wir fallen, weil
                        diese ja nur das Kennzeichen für die Fortsetzung sind.
                    #>
                    $binaerTeil =  $oktett.Substring(2, 6)
                }

                #endregion Verarbeitung

                #region Ausgabe

                <#
                    Nun erweitern wird die binäre Repräsentation unseres
                    Zeichens um die Forsetzungsbits.
                #>

                $binaer += $binaerTeil

                #endregion Ausgabe
            }

            <#
                Jetzt konvertieren wir die binäre Repräsentation unseres
                Zeichens in eine Dezimalzahl. Dabei hilft uns das
                .NET-Framework.
            #>

            $dezimalzahl = [convert]::ToInt32($binaer, 2)

            # Eine Zahl kann direkt in ein Zeichen konvertiert werden

            $zeichen = [char] $dezimalzahl
        }

        #endregion Verarbeitung

        #region Ausgabe

        # Nun hängen wir das ermittelte Zeichen an unsere Nachricht an

        $nachricht += $zeichen

        #endregion Ausgabe

    }
}

#region Ausgabe

Clear-Host
Write-Host $nachricht

#endregion Ausgabe

Da wir es uns nun viel einfacher gemacht und Unmengen an Codezeilen eingespart haben (3 von 15 Zeilen sind immerhin 20 %, also bitte nicht lachen), können wir uns dem Problem widmen, dass die Umlaute nicht richtig dargestellt werden. Tatsächlich ist der Text in UTF-8 codiert. Eine verständliche Erklärung von UTF-8 findet sich wie so oft in Wikipedia (https://en.wikipedia.org/wiki/UTF-8).

Lösung 3 führt keine neuen Programmiertechniken ein, hat aber einen komplexeren Algorithmus. Nach sorgfältigem Lesen des o. a. Wikipedia-Artikels sollte die Implementierung möglich sein. Wer zu faul ist, selbst nachzudenken, findet die Lösung in der Datei bin2text3.ps1.

Lösung 3 hat 24 Zeilen Code, ist also um 100 % länger als Lösung 2 und aufgrund einiger zweier zusätzlicher Verzweigungen und einer zusätzlichen Schleife um 300 % komplexer, was wieder einmal zeigt, warum Umlaute unter Informatikern so unbeliebt sind. 🙂

Links

Kommentar absenden

Zur Werkzeugleiste springen