Bei der Realisierung des Sepa Generators, den ich im verlinkten Betrag beschrieben habe, stand ich vor einer Teilaufgabe, eine Iban-Validierung auf die Beine zu stellen. Diese beinhaltete unter anderem die Umwandlung der darin enthaltenen Buchstaben (Ländercodes bzw. Bankcodes) in deren numerische Repräsentation. Eigentlich eine triviale Aufgabe für jeden Entwickler. Dennoch bin ich bei derer Realisierung auf ein paar interessante Erkenntnisse gestoßen, die mir zu Beginn gar nicht präsent waren. Genau um die geht es im aktuellen Beitrag.
Wie es meistens in der Softwareentwicklung der Fall ist, lässt sich auch diese Aufgabenstellung auf unterschiedliche Art und Weisen lösen. Schauen wir uns diese mal an.
Variante mit Dictionary Lookup
Bei dieser Variante erfolgt die „Übersetzung“ der Iban-Buchstaben in ihre numerischen Repräsentation mit Hilfe einer Datenstruktur namens Dictionary. Dieser Struktur geben wir bei der Initialisierung alle 26 Großbuchstaben als Keys und deren entsprechenden numerischen Werte als Values mit. Im Code lässt sich diese Struktur recht komfortabel nutzen, um Buchstabenwerte abzufragen.
byte value = ibanLetter['B'];
Der Schreibaufwand dieser Lösung steht jedoch in keinem Verhältnis zum gelieferten Ergebnis. Allein für die initiale Belegung der einzelnen Werte würden wir 26 Zeilen Code benötigen.
Dictionary<char, byte> ibanLetter = new Dictionary<char, byte>
{
{'A', 10 },
{'B', 11 },
///...
{'Z', 35 }
};
Wir Softwareentwickler haben von Berufs wegen eine natürliche Abneigung gegen Lösungen dieser Art. Zumal der Spaßfaktor bei der Umsetzung nahezu gegen Null tendiert. Daher stelle ich sie lediglich der Vollständigkeit halber vor – als tatsächliche Lösung lasse ich sie links liegen.
Variante mit Ascii-Abstand
Da wir für die Lösung dieser Aufgabe eine Auflistung aller Buchstaben benötigen, ist es naheliegender und deutlich eleganter, uns des ASCII-Zeichensatzes zu bedienen. ASCII steht für „American Standard Code for Information Interchange“ und ist der älteste noch existierende Zeichensatz, der nach wie vor Verwendung findet. In diesem 7Bit langen Zeichensatz finden 128 Zeichen Platz, darunter alle Groß- und Kleinbuchstaben des lateinischen Alphabets, alle Ziffern und einige Sonderzeichen sowie ein paar prähistorischer Zeichen aus der Zeit der Telegraphen.
Schauen wir uns ein paar Großbuchstaben mit ihren ASCII-Werten und mit ihren iban internen numerischen Repräsentationen als Beispiel an:
Buchstabe ASCII IBAN
A 65 10
Z 90 35Man erkennt anhand dieser Tabelle selbst mit unbewaffneten Auge, dass die Werte der beiden Kodierungen sich um jeweils 55 unterscheiden. Genau diese Abstandsberechnung ist im Prinzip auch schon der ganze Algorithmus, den wir für die Umwandlung benötigen. Verglichen mit der ersten Variante ist es Eleganz pur und eine Weide für die Entwickleraugen.
private int ConvertLetterToIbanNumeric(char letter) => letter - 55;
Als Einschränkung muss an der Stelle noch gesagt werden, dass diese Variante ausschließlich mit Großbuchstaben funktioniert. Dies muss im aufrufenden Programm sichergestellt werden, beispielsweise durch die Anwendung der ToUpper-Methode auf die Iban. Ich habe Ibans mit Kleinbuchstaben selbst zwar nie gesehen, aber der IBAN-Datentyp in der Pain001-XSD erlaubt diese außerhalb des Ländercodes explizit, sodass sie in der Praxis in Ibans einiger Länder auf jeden Fall vorkommen können.
Variante mit Alphabetposition und Bitmaske
So schön und einfach die vorherige Variante auch ist, sie hat einen gravierenden Nachteil – sie ist schlicht nicht nerdig genug (Achtung Entwicklerhumor). Um dieses Manko auszugleichen, schauen wir uns nun die letzte Variante an. Sie ist in der Tat etwas subtiler und offenbart sich einem erst, wenn man sich die ASCII-Werte der einzelnen Buchstaben nicht in dezimaler, sondern in binärer Form anschaut.
Ich habe auch früher oft den ASCII-Zeichensatz genutzt, mich jedoch nicht wirklich damit befasst. Es war für mich immer etwas, was man als gegeben hinnimmt und einfach verwendet. Daher habe ich mir auch nie Gedanken darüber gemacht, wie man damals festgelegt hat, welches Zeichen welchen Wert erhalten soll. War es eine reine willkürliche Entscheidung, oder steckte womöglich mehr dahinter? Nachdem ich mich bei der Realisierung des Sepa-Generators etwas tiefer mit dem ASCII-Zeichensatz auseinandergesetzt habe, weiß ich nun, dass da einige richtig clevere Vorüberlegungen eingeflossen sind. Beispielsweise hat man in den ASCII-Werten der Buchstaben deren Alphabetpositionen verankert. Betrachtet man in der unten stehenden Abbildung die 5 niedrigstwertigen Bits (fett markiert) und wandelt diese in numerische Darstellung um, dann erhält man tatsächlich die Position des jeweiligen Buchstabens im lateinischen Alphabet.
Buchstabe ASCII Binär Alphabetposition
A 65 1000001 1
Z 90 1011010 26Diese Besonderheit mache ich mir zu nutze und lese die Position mit Hilfe der Bitmagie Bitmaske 0b0011111 (in hexadezimaler Darstellung ausgedrückt 0x1F) und einer bitweisen UND-Verknüpfung aus.
1000001 Buchstabe A
0011111 Bitmaske 0x1F
-------
0000001 Ergebnis 1
1011010 Buchstabe Z
0011111 Bitmaske 0x1F
-------
0011010 Ergebnis 26Bei der bitweisen Verknüpfung der char Buchstabenvariablen mit der Bitmaske werden die einzelnen Bits beider Operanden paarweise betrachtet. Als Ergebnis kommt ein 1er Bit bei jedem Bitpaar nur dann zustande, wenn an seiner Bitposition bei beiden Operanden ein 1er Bit steht. In der Bitmaske setzt man daher diejenigen Bits auf den Wert 1, die man in der abzufragenden Variablen ausgelesen haben möchte. Die gesetzten fünf 1er Bits der Bitmaske bewirken, dass die bitweise UND-Verknüpfung mit der Buchstabenvariablen den relevanten Bitbereich (die 5 niedrigstwertigen Bits) aus der Variablen ausliest und als Position des Buchstabens liefert. Darauf addieren den festen Wert 9 und errechnen so aus der Alphabetposition die numerische Repräsentation für die Iban-Validierung.
private int ConvertLetterToIbanNumeric(char letter) => (letter & 0x1F) + 9;
Durch eine weitere ASCII-Besonderheit funktioniert diese Variante, anders als die vorherige, mit beiden Buchstabenschreibweisen. Im ASCII-Zeichensatz beträgt der numerische Abstand zwischen den korrespondierenden Groß- und Kleinbuchstaben immer 32. Da sich dieser Wert schön als Zweierpotenz 25 ausdrücken lässt, kann dieser komplett durch ein einzelnes Bit dargestellt werden. Da das erste Bit (mit dem niedrigsten Stellenwert) die Potenz 0 hat, befindet sich das Bit, welches die Zahl 25 repräsentiert, an der 6. Stelle:
26 25 24 23 22 21 20Dies bedeutet, dass die korrespondierenden Groß- und Kleinbuchstaben sich ausschließlich im 6.Bit (fett markiert) unterscheiden. Da dieses Bit außerhalb des Bitbereiches für die Position des Buchstabens im Alphabet (die ersten 5 Bits – kursiv markiert) liegt und somit mit der Maske gar nicht gelesen wird, ist die Buchstabenschreibweise nicht relevant.
Buchstabe ASCII Binär
A 65 1000001
a 97 1100001
Z 90 1011010
z 122 1111010Eine Bemerkung am Rande. Die in Ibans enthaltenen Ziffern lese ich ebenfalls mit einer Bitmaske aus. An sich wäre es nicht unbedingt erforderlich, denn eine Variable vom Typ char, in der eine Ziffer gespeichert ist, kann in ein String umgewandelt und mit Hilfe einer Parse-Methode in eine Zahl überführt werden (siehe unten stehendes Beispiel), um damit rechnen zu können.
foreach (char character in "123456789012345678131443")
{
int value = int.Parse(character.ToString());
}
Das „Problem“ dabei ist, dass dafür zwei Umwandlungen (von char zu string und dann zu int) ausgeführt werden, was aus dem Blickwinkel der Performance in der Regel recht „teuer“ ist.
Mit den Bitmaskierung extrahieren wir den numerischen Wert aus der char-Variablen direkt als Zahl, ohne dass es irgendwelcher Umwandlungen bedarf. Der Datentyp char arbeitet zwar intern mit UTF-16, dieser ist allerdings zu ASCII abwärtskompatibel und kodiert die in ASCII verfügbaren Zeichen genauso. Auch hier der Hinweis, dass diese Berechnung natürlich nur bei tatsächlichen Ziffern funktioniert – dies prüft die Methode nicht, sondern es ist auch an der STelle die Aufgabe des aufrufenden Codes dafür zu sorgen, dass sie nur mit Ziffernzeichen aufzurufen ist. In der ersten Variante ist es allerdings genauso erforderlich.
foreach (char character in "123456789012345678131443")
{
int value = character & 0xF;
}
Diese Art des Auslesens ist deswegen möglich, weil die Entwickler des Zeichensatzes in den ASCII-Werten der Ziffern auch deren tatsächlichen Wert (in den 4 niedrigstwertigen Bits) verankert haben.
0110001 Zeichen 1
0001111 Bitmaske 0xF
-------
0000001 Ergebnis 1
0111001 Zeichen 9
0001111 Bitmaske 0xF
-------
0001001 Ergebnis 9Programmiersprachen können solche Bitoperationen um einiges effizienter als Textoperationen ausführen, was man deutlich im nachfolgenden Performancevergleich sehen kann. Für die Umwandlung von 100.000 Ibans werden in der ersten Variante rund 191 Millisekunden gebraucht. Die Variante, die direkt auf der Bitebene arbeitet, ist mit 10 Millisekunden was 19 Mal schneller. Der relative Unterschied ist natürlich beachtlich – eine Iban-Validierungsklasse ist jedoch keine Komponente, in der es auf die letzte Millisekunde ankommt. Wenn man jedoch die Möglichkeit hat, dies ohne großen Aufwand zu optimieren und dabei was interessantes lernen kann – why not.