In einem meiner letzten Artikel zum Thema Rechnungsstellung habe ich erwähnt, dass manche Kundenüberweisungen aufgrund von Zahlendrehern in Rechnungsnummern nicht automatisiert zuordenbar waren. Dazu habe ich mir überlegt, wie ich die Zuordnungsquote erhöhen kann.

QR Code auf der Rechnung – Warum?

Eines Tages las ich einen Artikel über QR Codes (in diesem Zusammenhang oft als EPC QR Code oder als GiroCode bezeichnet), die vor allem im Paymentbereich in der Schweiz sehr verbreitet sind und eine Menge Vorteile bieten. Da kam mir die Idee, die QR Code Technologie für die Weiterentwicklung meines eigenen Rechnungsprogramm einzusetzen und die Rechnungen automatisch mit QR Codes auszustatten. Beim Einscannen des GiroCodes aus einer BankingApp heraus werden alle darin enthaltenen Daten dekodiert und direkt ins Überweisungsformular übernommen, sodass dieses nur noch zu kontrollieren und freizugeben ist. Davon würden beide Seiten profitieren – meine Kunden könnten sich das Abtippen oder Kopieren von Überweisungsdaten sparen und ich hätte dann keine Zuordnungsprobleme bei Überweisungen.

Hier stand ich vor der Überlegung, ob ich nicht einfach einen auf dem Markt frei erhältlichen QR Code Generator in meinem Rechnungsprogramm einbinde. Webbasierte Generatoren schieden allerdings gleich aus. Hauptsächlich, weil damit logischerweise kein Offlinebetrieb möglich ist. Zum anderen, weil ich nicht unbedingt Zahlungsinformationen durch das halbe Internet durchjagen wollte. Also drängte sich der Einsatz eines offline QR Code Generators nahezu auf. Da mich die Herausforderung gereizt hat und ich die Funktionsweise von QR Codes verstehen wollte, trieb mich der Forschungsdrang dazu, eigenen QR Code Generator zu programmieren.

Informationsbeschaffung

Bei der Recherche zum Thema QR Codes wurde mir schnell klar, dass viele Webseiten es relativ oberflächlich behandeln (ich kann es ihnen nicht verübeln 🙂 ) und nur einen groben Überblick über die Struktur, Aufbau und Funktionsweise geben, ohne jedoch stark in die Tiefe zu gehen. Es war also absehbar, dass ich für die komplexeren Teilgebiete, wie zum Beispiel Fehlerkorrektur oder Maskierung von QR Codes ganz andere Informationstiefe benötige. Dazu bin ich erst im englischsprachigen Raum fündig geworden (QR Code-Tutorial).

Auswahl der Technologie – VBA oder C#

Obwohl ich meinen QR Code Generator eigentlich nur für den Einsatz in meiner Microsoft Access-Rechnungsdatenbank (also in der VBA-Welt) vorgesehen habe, entschied ich mich, diesen nicht als ein VBA-Modul oder Add-In, sondern als eine C#-Klassenbibliothek unter Visual Studio zu entwickeln. Eine allgemeine Klassenbibliothek hätte den Charme, dass sich diese in eine Konsolen- oder auch in eine GUI-Anwendung integrieren ließe. Die geplante Verwendung aus der VBA-Welt heraus wäre durch die COM-Technologie ebenfalls abgedeckt.

Programmierung

Grundstruktur

Am Anfang des Projektes habe ich relativ schnell die ersten Erfolge erzielt und die statische Grundstruktur aufgebaut. So war die erste Version des QR Code Generators in der Lage, anhand des übergebenen Textes und des gewählten Korrekturlevels die benötigte Matrixgröße zu errechnen und die ganzen Pattern

• Finderpattern
• Alignmentpattern
• Timingpattern

in der Matrix abzubilden und in Bildform zu visualisieren. Mathematisch und programmiertechnisch war dies relativ einfach zu bewerkstelligen.

Die QR Code-Spezifikation (ISO 18004) gibt viele Parameter vor, die je nach gewähltem Fehlerkorrekturlevel und QR Code-Größe mit unterschiedlichen Ausprägungen zu verwenden sind. Für die Verwaltung dieser Parameter habe ich mich für XML entschieden. Die Parameterverwaltung direkt in der Klassenstruktur würde zwar mit zwei Dateien weniger (xml und xsd) auskommen, wäre aber für mich persönlich deutlich unübersichtlicher. Da ich es nicht im Rahmen eines Kundenauftrages mit konkreten Vorgaben, sondern für mich entwickele, gilt hier – „mein Generator, meine Regeln“ 🙂

Um ein Gefühl für die Vielfalt der Parameterausprägungen zu bekommen, zeige ich hier einen kleinen Auszug aus dieser Konfigurationsdatei. Darin sieht man allgemeine Parameter für QR Codes in der Version 11 und spezielle Parameter für den Fehlerkorrekturlevel L in der Version 11. Insgesamt sieht die Spezifikation 40 Versionen und 4 Fehlerkorrekturlevel vor – am Ende bin ich da bei stolzen 3.000 Zeilen allein an Parameterdaten hinausgelaufen.

<qr-code version="11" number-of-remainder-bits="0">
	<alligment-pattern>
		<position>6</position>
		<position>30</position>
		<position>54</position>
	</alligment-pattern>
	<error-correction>
		<level-L>
			<capacity-in-characters>
				<numeric>772</numeric>
				<alphanumeric>468</alphanumeric>
				<byte>321</byte>
			</capacity-in-characters>
			<codeblock-information number-of-error-correction-codewords-per-block="20">
				<group index="1">
					<block number-per-group="4">
						<data-codeword number-per-block="81" />
					</block>
				</group>
			</codeblock-information>
		</level-L>
		...
	</error-correction>
</qr-code>

Für den Zugriff auf diese Parameterdatei habe ich eine separate Klasse implementiert, die auf dem Singleton-Entwurfsmuster basiert – so wird die Konfigurationsdatei physisch tatsächlich nur einmalig von der Festplatte gelesen. Das macht vor allem dann Sinn, wenn der Generator für eine Batchverarbeitung eingesetzt wird, wo mehrere Tausend QR Codes zu erzeugen sind. Diese Config-Klasse stellt dann über fachliche Methoden den lesenden Zugriff auf die einzelnen Parameter bereit.

Textkodierung

In Abhängigkeit davon, welche Daten der in QR Code zu überführende Text enthält, werden unterschiedliche Modi für die Kodierung der Daten herangezogen. Man verfolgt dabei das Ziel, den Text möglichst effizient (im Sinne von platzsparend) in eine Bitsequenz zu transformieren. In meiner Bibliothek habe ich folgende Modi realisiert.

• Numeric
• Alphanumeric
• Byte

Jeder dieser Modi wandelt Texte auf unterschiedliche Art und Weise in eine Bitsequenz um. Der grundsätzliche Ablauf, bei dem die umgewandelte Bitsequenz mit Zusatzinformationen angereichert wird, ist jedoch in jedem Modus gleich. Von links werden an die Bitsequenz diese Daten angehängt:

• Nummer des gewählten Kodierungsmodus (mode indicator)
• Anzahl der im Text enthaltenen Zeichen (character count indicator)

Von rechts wird die Bitsequenz um diese Daten angereichert:

• Bits, die das Ende der Nachricht einleiten (Terminatorbits)
• Eventuell notwendige 0-Auffüllbits (Paddingbits), damit die Sequenz nach der Auffüllung aus kompletten Bytes besteht(also ohne Rest durch 8 teilbar ist)
• Eventuell notwendige Auffüll-Bytes (Padding-Codewords), damit die Bitsequenz auf die erforderliche Ziellänge kommt

Diese Schritte der Anreicherung, die bei jedem Modus gleichermaßen zum Einsatz kommen, habe ich in der abstrakten Klasse MessageEncoderAbstract platziert.

Von dieser Klasse erben konkrete Klassen, welche nur die Spezifika des jeweiligen Kodierungsmodus zu implementieren brauchen, nämlich die Art und Weise, wie der Text in die Bitsequenz überführt wird, sowie die Information, mit welcher Bitlänge die Anzahl der im Text enthaltenen Zeichen dargestellt werden soll.

Die tatsächliche Nutzung dieser Funktionalität ist innerhalb der Bibliothek sehr einfach. Dabei kommt die zentrale Rolle der statischen Klasse MessageEncoderFactory zu.

MessageEncoderAbstract MessageEncoder = MessageEncoderFactory.GetEncoder(message);
CodewordSet dataCodeWords = MessageEncoder.GetMessageCodewords(errorCorrectionLevel);

Beim Aufruf der GetEncoder-Methode, wird der übergebene Text analysiert. Anhand seiner Inhalte wird dabei der beste Modus ermittelt und ein Objekt der konkreten Kodierungsklasse (MessageNumericEncoder, bzw. MessageAlphanumericEncoder bzw. MessageByteEncoder) erzeugt und an den Aufrufer zurückgegeben.

Auf diesem Objekt wird dann die GetMessageCodewords Methode aufgerufen, die dann die tatsächliche Umwandlung des Textes in die Bitsequenz übernimmt und diese anschließend in Codeword-Auflistung transferiert, die dann in den nächsten Schritten für die Fehlerkorrekturerzeugung verwendet werden.

Fehlerkorrekturcodes

Das nächste Teilgebiet des Projektes forderte mich so richtig (mathematisch, programmiertechnisch und geistig) heraus. Es ging dabei um die Erzeugung von Fehlerkorrekturcodes. QR Codes können nämlich auch dann eingescannt und dekodiert werden, wenn ein gewisser Teil des Codes nicht lesbar ist. Beim höchsten Fehlerkorrekturlevel reichen gar 70% des QR Codes aus, ohne dass es dabei zu Dekodierungsproblemen kommt. Diese Fehlerkorrekturen werden, aus meiner Sicht als Nichtmathematiker, nach einem sehr komplizierten Verfahren namens Reed-Solomon (benannt nach zwei Überfliegern vom Massachusetts Institute of Technology) generiert.

Ohne die ausführlichen und für die Nichtdoktoren der Mathematik aufbereiteten Informationen aus dem Tutorial, hätte ich die Generierung der Fehlerkorrekturcodes definitiv nicht umsetzen können. Allerdings auch den wirklich ausführlich beschriebenen Ablauf in den Code zu gießen, war nicht ohne – wie oft hat man schon als Anwendungsentwickler, der eher im betriebswirtschaftlichen Umfeld unterwegs ist, eine Methode für die Polynomdivision zweier Gleichungen 68en Grades zu programmieren 🙂

Polynomdivisionen

Bei diesen Gleichungen handelt es sich um Generator- und Nachrichtenpolynomen. Das Generatorpolynom hängt ausschließlich von der Anzahl der zu berechnenden Fehlerkorrekturcodes ab. Da die ISO-18004 nur insgesamt 13 unterschiedliche Anzahlen je Block dafür vorsieht, wäre es denkbar, alle möglichen 13 Generatorpolynomen vorab zu berechnen und im Sourcecode oder in der Konfigurationsdatei vorzuhalten. Ich habe mich entschieden, die Erzeugung von Generatorpolynomen zur Laufzeit durch die Klasse PolynomialGenerator vorzunehmen. Um jedoch mehrfache Erzeugung von Generatorpolynomen (vor allem, wenn der QR Code Generator im Batchbetrieb läuft) zu vermeiden, habe ich diese Klasse mit einem statischen Member vom Typ Dictionary ausgestattet. In diesem fungieren die Fehlerkorrekturcodes-Anzahlen als Keys und die Generatorpolynome als Values. Jedes Mal, wenn der Konstruktor der Klasse aufgerufen wird, wird zuerst geprüft, ob für die übergebene Anzahl an Fehlerkorrekturcodes bereits ein Generatorpolynom errechnet worden ist. In diesem Fall wird dieses direkt aus dem Dictionary abgerufen, ohne dass es erneut berechnet werden muss.

Das Nachrichtenpolynom repräsentiert je nach ermittelter QR Code Version und vorgegebenem Fehlerkorrekturlevel, entweder die komplette Nachricht, bzw. nur einen Teil davon. Dies ist in der Spezifikation für jede Kombination der Version und des Fehlerkorrekturlevels vorgegeben und hat eine große Auswirkung auf das Aussehen und die Komplexität der Polynome.

Wollen wir beispielsweise den Text „Besonders geistreicher Spruch!“ in der höchsten Fehlerkorrekturstufe als QR Code generieren, ist dabei der Text, bzw. seine Bitsequenz auf 4 Nachrichtenpolynome mit je 9 Termen aufzuteilen und dafür jeweils 16 Fehlerkorrekturcodes auszurechen. Durch diese Aufteilung sehen die Nachrichtenpolynome nahezu süß und harmlos aus, wie es das unten stehende Beispiel schön zeigt:

65x⁸ + 228x⁷ + 38x⁶ + 87x⁵ + 54x⁴ + 246x³ + 230x² + 70x + 87

Doch es geht auch anders. Wollen wir beispielsweise den Text „Besonders geistreicher Spruch, mit mehr Text, damit dieser in die Version 5 fällt!!!“ in der niedrigsten Fehlerkorrekturstufe als QR Code generieren, besagt die Spezifikation, den ganzen Text bzw. seine Bitsequenz nicht aufzuteilen, sondern als ein ganzes Nachrichtenpolynom zu verwenden und dafür insgesamt 26 Fehlerkorrekturcodes zu generieren. Dieser Vorgang bringt daher ein wahres Monstrum mit 108 Termen hervor:

69x¹⁰⁷ + 68x¹⁰⁶ + 38x¹⁰⁵ + 87x¹⁰⁴ + 54x¹⁰³ + 246x¹⁰² + 230x¹⁰¹ + 70x¹⁰⁰ + 87x⁹⁹ + 39x⁹⁸ + 50x⁹⁷ + 6x⁹⁶ + 118x⁹⁵ + 86x⁹⁴ + 151x⁹³ + 55x⁹² + 71x⁹¹ + 38x⁹⁰ + 86x⁸⁹ + 150x⁸⁸ + 54x⁸⁷ + 134x⁸⁶ + 87x⁸⁵ + 34x⁸⁴ + 5x⁸³ + 55x⁸² + 7x⁸¹ + 39x⁸⁰ + 86x⁷⁹ + 54x⁷⁸ + 130x⁷⁷ + 194x⁷⁶ + 6x⁷⁵ + 214x⁷⁴ + 151x⁷³ + 66x⁷² + 6x⁷¹ + 214x⁷⁰ + 86x⁶⁹ + 135x⁶⁸ + 34x⁶⁷ + 5x⁶⁶ + 70x⁶⁵ + 87x⁶⁴ + 135x⁶³ + 66x⁶² + 194x⁶¹ + 6x⁶⁰ + 70x⁵⁹ + 22x⁵⁸ + 214x⁵⁷ + 151x⁵⁶ + 66x⁵⁵ + 6x⁵⁴ + 70x⁵³ + 150x⁵² + 87x⁵¹ + 54x⁵⁰ + 87x⁴⁹ + 34x⁴⁸ + 6x⁴⁷ + 150x⁴⁶ + 226x⁴⁵ + 6x⁴⁴ + 70x⁴³ + 150x⁴² + 82x⁴¹ + 5x⁴⁰ + 102x³⁹ + 87x³⁸ + 39x³⁷ + 54x³⁶ + 150x³⁵ + 246x³⁴ + 226x³³ + 3x³² + 82x³¹ + 6x³⁰ + 110x²⁹ + 70x²⁸ + 198x²⁷ + 199x²⁶ + 66x²⁵ + 18x²⁴ + 18x²³ + 16x²² + 236x²¹ + 17x²⁰ + 236x¹⁹ + 17x¹⁸ + 236x¹⁷ + 17x¹⁶ + 236x¹⁵ + 17x¹⁴ + 236x¹³ + 17x¹² + 236x¹¹ + 17x¹⁰ + 236x⁹ + 17x⁸ + 236x⁷ + 17x⁶ + 236x⁵ + 17x⁴ + 236x³ + 17x² + 236x + 17

Einem geübten Auge wird auffallen, dass in diesem Beispiel die letzten 22 Terme abwechselnd die Koeffizienten 17 und 236 haben. Es sind nämlich die im vorherigen Kapitel erwähnten Padding-Codewords. Da in der Version 5 mit dem Fehlerkorrekturlevel H in der Byte-Kodierung insgesamt 106 Zeichen Platz finden und unser Text mit 84 Zeichen deutlich unterhalb dieser maximalen Kapazität liegt, besagt die Spezifikation, den nicht genutzten Platz mit diesen Padding-Codewords, die jeweils 8 Bit lang sind, abwechselnd aufzufüllen.

Doch selbst dieses Monstrum ist noch nicht das Ende der Fahnenstange. Das toppt beispielsweise die Version 27 in der niedrigsten Fehlerkorrekturstufe, in der Nachrichtenpolynome mit insgesamt 123 Termen heranzuziehen sind.

Kehren wir jedoch nun zurück zum Wesentlichen.

Das Tutorial besagt, dass die Polynomdivision so oft durchzuführen ist, wie viele Terme das Nachrichtenpolynom hat. Klingt nach einem perfekten Einsatzszenario für eine For-Schleife, da die Anzahl der Durchläufe vor dem Beginn der Berechnung festzustehen scheint.

Bei jedem Schleifendurchlauf wird das Generatorpolynom mit dem ersten Term des Nachrichtenpolynoms bzw. mit dem des Ergebnispolynoms aus dem vorherigen Divisionsschritt multipliziert. Dadurch, dass laut der QR-Spezifikation sämtliche Generatorpolynomen (egal, welche Anzahl an Fehlerkorrekturen zu generieren ist) im ersten Term immer den Koeffizienten mit dem Wert ɑ⁰ haben, führt die im vorherigen Satz erwähnte Multiplikation des Generatorpolynoms mit dem ersten Terms des Nachrichtenpolynoms immer dazu, dass das Multiplikationsergebnis eben denselben ɑ Wert im ersten Term erhält, da beispielsweise ɑ⁰ * ɑ⁶⁷ = ɑ⁶⁷ ist.

Anschließend werden die Koeffizienten aus diesem Ergebnis und dem Nachrichtenpolynom bzw. dem Ergebnispolynom aus dem vorherigen Divisionsschritt aus der Alpha- in die Integer-Notation überführt und mit dem XOR-Operator verknüpft. Da beide Polynomen in ihren ersten Terms immer den selben Koeffizienten haben, bekommt der erste Term des Ergebnisses immer den Koeffizienten 0 und kann dadurch eliminiert werden. Am einfachsten ist diese XOR-Verknüpfung zu verstehen, wenn man die Integer-Notation gedanklich verlässt und sich die Koeffizienten in ihrer binärer Darstellung vorstellt. Der XOR-Operator besagt, dass zwei damit verknüpften Bits als Ergebnisbit immer dann 1 ergeben, wenn genau ein Bit den Wert 1 hat. Oder auch anders ausgedrückt, lautet das Ergebnisbit immer dann 0, wenn beide verknüpften Bits identisch sind.

Schauen wir uns mal an, was passiert, wenn man zwei identische Integer-Werte, beispielsweise 194 miteinander mit XOR verknüpft. Wie man sieht, ist deren binäre Darstellung logischerweise auch identisch, weswegen auch alle Bitpaare identisch sind. Daher ergibt die XOR-Verknüpfung von zwei identischen Integer-Werten immer den Wert 0.

194 -> 11000010
194 -> 11000010
       --------
       00000000 -> 0

Verknüpft man mit XOR hingegen einen 0 Integer-Wert mit einem beliebigen anderen größeren Integer-Wert, beispielsweise 254, wird das Ergebnis immer identisch mit dem größeren Wert sein, weil dabei alle Bits des größeren Wertes nicht verändert werden (aufgrund dessen, da immer ein Bit von jedem Paar den Wert 0 hat).

  0 -> 00000000
254 -> 11111110
       --------
       11111110 -> 254

In der Regel sind beide zu verknüpfenden Integer-Werte unterschiedlich, beispielsweise 243 und 187, sodass deren Verknüpfung dann tatsächlich einen komplett neuen Wert ergibt.

243 -> 11110011
187 -> 10111011
       --------
       01001000 -> 72

So funktioniert der Ablauf in rund 95-98% aller Fälle.

Im Laufe der Entwicklung bin ich auf die anderen 2-5% gestoßen, bei denen ein Divisionsschritt nicht nur den Koeffizienten des ersten Terms, sondern den des 2. oder gar des 3. Terms zu 0 werden ließ. In solchen Schritten konnten daher nicht nur der erste Term, sondern alle direkt darauf folgenden Terme eliminiert werden, die den Koeffizienten 0 hatten. Durch diese Besonderheit musste allerdings die Anzahl der noch auszuführenden Divisionen korrigiert werden.

Jeder, der programmiert hat, weiß, dass die Anpassung des Schleifenzählers in einer For-Schleife nicht wirklich die feine englische Art ist. Nach der Erkenntnis, dass die Anzahl der Divisionschritte vor dem Beginn der Division doch nicht zu 100% zuverlässig ermittelt werden kann, habe ich die For-Schleife durch eine While-Schleife ersetzt, um mich nicht mehr um die Anzahl der Durchläufe kümmern zu müssen. Diese Schleife läuft nämlich solange, solange der Exponent des ersten Terms vom Divisionsergebnis mindestens so hoch, wie die Anzahl der erforderlichen Fehlerkorrekturcodes ist.

while (leadTerm.ExponentOfX.Value >= this.numberOfErrorCorrectionwords)
{
	PolynomialEquitation generatorMultipliedByLeadTerm = generatorPolynomialWithFactor * leadTerm;

	messagePolynomial = messagePolynomial.XOR(generatorMultipliedByLeadTerm);
	messagePolynomial.RemoveLeadTermsWithZeroXCoefficient();

	leadTerm = messagePolynomial.LeadTerm;
}

Diese Besonderheit mit der Eliminierung von mehreren führenden Termen hat noch eine weitere Anpassung notwendig gemacht. Denn Polynomen, die in diesen Konstellationen am Ende erzeugt wurden, wiesen oft eine zu geringeiche Anzahl an Terms auf. Hier ist ein konkretes und aus meiner Sicht ein recht fieses Beispiel(hat mich einiges an Debugging-Aufwand gekostet):

Wir haben als Input eine Bitsequenz, die einen Teil des Textes repräsentiert. In dezimale Werte zur Verwendung als Koeffizienten des Nachrichtenpolynoms umgewandelt, sieht diese wie folgt aus:

117, 51, 20, 39, 21, 181, 245, 119, 117, 197, 162, 37

117x³⁵ + 51x³⁴ + 20x³³ + 39x³² + 21x³¹ + 181x³⁰ + 245x²⁹ + 119x²⁸ + 117x²⁷ + 197x²⁶ + 162x²⁵ + 37x²⁴

Da diese Sequenz zu einer Nachricht gehört, die in einem QR Code in der Version 14 und dem Fehlerkorrekturlevel H untergebracht wird, besagt die Spezifikation, dass pro Block 24 Fehlerkorrekturcodes benötigen werden und aus diesem Grund dieses Generatorpolynom zu verwenden ist (beide Polynomen wurden bereits auf die einheitliche Basis hinsichtlich ihres X-Exponenten gebracht).

ɑ⁰x³⁵ + ɑ²²⁹x³⁴ + ɑ¹²¹x³³ + ɑ¹³⁵x³² + ɑ⁴⁸x³¹ + ɑ²¹¹x³⁰ + ɑ¹¹⁷x²⁹ + ɑ²⁵¹x²⁸ + ɑ¹²⁶x²⁷ + ɑ¹⁵⁹x²⁶ + ɑ¹⁸⁰x²⁵ + ɑ¹⁶⁹x²⁴ + ɑ¹⁵²x²³ + ɑ¹⁹²x²² + ɑ²²⁶x²¹ + ɑ²²⁸x²⁰ + ɑ²¹⁸x¹⁹ + ɑ¹¹¹x¹⁸ + ɑ⁰x¹⁷ + ɑ¹¹⁷x¹⁶ + ɑ²³²x¹⁵ + ɑ⁸⁷x¹⁴ + ɑ⁹⁶x¹³ + ɑ²²⁷x¹² + ɑ²¹x¹¹

Lassen wir die Division des Generator- und des Nachrichtenpolynoms komplett durchlaufen, erhalten wir dieses Ergebnis:

49x²² + 29x²¹ + 117x²⁰ + 167x¹⁹ + 92x¹⁸ + 210x¹⁷ + 71x¹⁶ + 182x¹⁵ + 89x¹⁴ + 146x¹³ + 92x¹² + 232x¹¹ + 72x¹⁰ + 111x⁹ + 84x⁸ + 131x⁷ + 249x⁶ + 69x⁵ + 229x⁴ + 132x³ + 6x² + 181x

Hmmm. Jetzt haben wir zwar ein Endpolynom, dessen Koeffizienten als Fehlerkorrekturcodes fungieren sollen. Allerdings hat dieses lediglich 22 Koeffizienten anstelle von erforderlichen 24 – hier kommen wir nicht um die Auffüllung mit 0-Werten herum.

Am Anfang habe ich mich schwer getan, da ich aus dem Tutorial nicht herauslesen konnte, ob die Auffüllung von links oder von rechts erfolgen musste. Nun, nach dem ich die Endpolynomen von Standarddivisionen aufmerksamer studiert habe, lag die Lösung eigentlich schon auf der Hand – es kann nämlich alle 3 Konstellationen geben (fehlende Termen von links, fehlende Termen von rechts, sowie auf beiden Seiten). Für die korrekte Auffüllung muss jedes zu kurz geratene Endpolynom lediglich mit dem „idealen“ Polynom verglichen werden, welches diese Voraussetzungen erfüllt:

1. Das Polynom besteht aus insgesamt so vielen Terms, wie viele Fehlerkorrekturcodes benötigt werden.
2. Der erste Terms des Polynoms weist den X-Exponenten auf, der um 1 kleiner ist als die Anzahl der Fehlerkorrekturcodes.
3. Der letzte Terms des Polynoms weist den X-Exponenten von 0 auf.

Für die Prüfung und eventuell erforderliche Ergänzung des Endpolynoms, habe ich folgende kurze Methode entwickelt:

while (LastTerm.ExponentOfX.Value != 0)
{
	XCoefficient coefficientOfX = new XCoefficient(0);
	XExponent exponentOfX = new XExponent(LastTerm.ExponentOfX.Value - 1);

	this.equation.Add(new PolynomialTerm(coefficientOfX, exponentOfX));
}


while (LeadTerm.ExponentOfX.Value < numberOfErrorCorrectionwords - 1)
{
	XCoefficient coefficientOfX = new XCoefficient(0);
	XExponent exponentOfX = new XExponent(LeadTerm.ExponentOfX.Value + 1);

	this.equation.Insert(0, new PolynomialTerm(coefficientOfX, exponentOfX));
}

Diese prüft zuerst, ob der Exponent des letzten Term vom Polynom 0 ist. Wenn es nicht der Fall ist, werden ans Ende des Polynoms solange Terms mit dem Koeffizient von 0 und dem um 1 kleineren X-Exponenten angehängt, bis am Ende wirklich nur noch ein Koeffizient von 0 steht, der den X-Exponenten von 0 hat.

Nachdem dies erfolgt ist, wird der erste Term des Polynoms geprüft, ob die Anzahl der Fehlerkorrekturcodes minus 1 immer noch den X-Exponenten übersteigt. Ist es der Fall, werden an den Anfang des Polynoms solange Terms mit dem Koeffizient von 0 und dem um 1 größeren X-Exponenten angehängt, bis am Anfangs des Polynoms wirklich ein Term steht, der den X-Exponenten von Fehlerkorrekturcodes minus 1 hat.

So füllt diese Methode dieses zu kurze Polynom am Anfang und am Ende

49x²² + 29x²¹ + 117x²⁰ + 167x¹⁹ + 92x¹⁸ + 210x¹⁷ + 71x¹⁶ + 182x¹⁵ + 89x¹⁴ + 146x¹³ + 92x¹² + 232x¹¹ + 72x¹⁰ + 111x⁹ + 84x⁸ + 131x⁷ + 249x⁶ + 69x⁵ + 229x⁴ + 132x³ + 6x² + 181x

so auf, dass dieses seine Ziellänge erreicht:

0x²³ + 49x²²  + 29x²¹ + 117x²⁰ + 167x¹⁹ + 92x¹⁸ + 210x¹⁷ + 71x¹⁶ + 182x¹⁵ + 89x¹⁴ + 146x¹³ + 92x¹² + 232x¹¹ + 72x¹⁰ + 111x⁹ + 84x⁸ + 131x⁷ + 249x⁶ + 69x⁵ + 229x⁴ + 132x³ + 6x² + 181x + 0

Klassenhierarchie der Polynome

Verlieren wir ein paar Worte zur technischen Umsetzung und der Klassenhierarchie, die für die Arbeit mit Polynomen zum Einsatz kommt. Auf der obersten Ebene befindet sich die Klasse PolynomialEquitation. Objekte dieser Klasse repräsentieren konkrete Polynome, beispielsweise das Generatorpolynom oder das Nachrichtenpolynom.

Wie man dem Screenshot entnehmen kann, bietet diese Klasse grundlegende Methoden, um zum einen gewisse Rechenoperationen wie beispielsweise Multiplikation oder XOR durchzuführen und zum anderen um Polynomen durch das Hinzufügen von einzelnen Termen aufzubauen. Ebenfalls stellt diese Klasse zwei Methoden bereit, welche die Formatierung des Polynoms (entweder in der AlphaNotation bzw. in der IntegerNotation) übernehmen.

Die einzelnen Termen, aus denen sich Polynome zusammensetzen, werden durch Objekte der Klasse PolynomialTerm repräsentiert. Diese Klasse stellt zwei Konstruktoren bereit, mit denen sich entweder Termen in der AlphaNotation bzw. IntegerNotation erzeugen lassen

Auf der unterstehen (fachlichen) Ebene befinden sich die 3 Klassen, welche die einzelnen Bestandteile eines Polynomterms repräsentieren. Ein Term in der Alphanotation, beispielsweise ɑ²²⁹x³⁴ besteht aus einem Objekt der Klasse AlphaExponent und einem Objekt der Klasse XExponent. Ein Term in der Integernotation wiederum besteht aus einem Objekt der Klasse XExponent und einem Objekt der Klasse XExponent, beispielsweise 69x⁵

Jede dieser Klassen stellt auch konkrete Implementierungen der ToString()-Methode, welche für eine html-gestützte Ausgabe sorgen.

Auf der untersten (technischen) Ebene befindet sich die abstrakte Klasse PolynomialTermPart, welche ein paar gemeinsam genutzte Methode für die 3 oben genannten Klassen zur Verfügung stellt.

Maskierung

Das letzte Teilgebiet mit der Darstellung der kodierten Daten in der Matrix und deren Maskierung für ein besseres maschinelles Einscannen war verglichen mit dem vorherigen Teil schon fast zu einfach. Das hat mich auch richtig motiviert, dass ich den komplizierten Teil schon hinter mir habe und kurz vor der Fertigstellung stehe. Tja, und dann kam das Testen:-)

Testen

Einem QR Code sieht man mit unbewaffnetem Auge in der Regel nicht an, ob es richtig aufgebaut ist. Für den Schnelltest nutzte ich dabei mein Handy – beim Einscannen hatte ich dann direkt die Rückmeldung, ob der QR Code richtig war oder zumindest eingescannt werden konnte. Wenn jedoch der erzeugte QR Code nicht lesbar war, dann ging die Suche nach dem Fehler erst richtig los.

Einen guten Dienst hat mir dabei diese Webseite https://www.nayuki.io/page/creating-a-qr-code-step-by-step geleistet. Im Gegensatz zu anderen webbasierten QR Code Generatoren, erlaubt der Betreiber hier einen Blick in den „Maschinenraum“. So ist es zum Beispiel möglich, sich die generierten Korrekturwörter oder die Penaltyscores der einzelnen Masken anzeigen zu lassen. Durch den Vergleich mit dem Output meiner Klasse konnte ich den Fehler zumindest ganz grob lokalisieren. Der Löwenanteil aller Fehler lag in der Klasse für die Erzeugung der Fehlerkorrekturcodes – mit Sicherheit habe ich für die Fehlersuche und deren Behebung fast genauso lang gebraucht wie für die Entwicklung . Aufgrund deren Komplexität auch nicht weiter verwunderlich – aus sprachlicher Sicht dennoch amüsant:-). Alle anderen Klassen waren da deutlich robuster und wiesen kaum Fehler auf.

Projektergebnis

Herausgekommen ist aus diesem Projekt, wie erwähnt, ein QR Code Generator in Form einer dll-Datei, eine Wrapperklasse für die Nutzung des Generators in der VBA-Welt (ebenfalls als eine dll-Datei) und eine Parameter-XML-Datei mit QR Code Spezifikationen inklusive einer XSD-Datei.

Klasse QRCodeGenerator

Alle C#-Klassen bis auf die Klasse QRCodeGenerator haben die Sichtbarkeit internal und treten somit gar nicht in Erscheinung, sondern verrichten ihren Dienst ausschließlich im Hintergrund. Die Klasse QRCodeGenerator ist public und fungiert somit als die Schnittstelle nach außen. Die Nutzung dieser Klasse in anderen Anwendungen (beispielsweise in einer GUI- oder einer Konsolenanwendung) ist wirklich sehr einfach, weil nahezu alle Parameter entweder von der Klasse selbst errechnet oder in der Parameterdatei „nachgeschlagen“ werden. Das geht natürlich etwas auf die Kosten der Flexibilität, sodass man beispielsweise keinen Einfluss auf die QR Code Größe hat – die Einfachheit in der Nutzung war mir persönlich aber am wichtigsten. Zumal im Fall der Fälle sich der Generator ohne Probleme erweitern lässt, um gewisse Parameter manuell vorgeben zu können.

Diese zentrale Klasse QRCodeGenerator bietet einen dreifach überlagerten Konstruktor, der jeweils unterschiedliche Eingabeparameter erwartet:

allgemeiner Konstruktor (für die .NET-Welt)

Der erste Konstruktor wird verwendet, wenn die Klasse in ein normales Visual Studio Projekt eingebunden ist und es um die Erzeugung eines QR Codes geht, den man mit einem bestimmten Fehlerkorrekturlevel erzeugen möchte.

public QRCodeGenerator(string message, QRErrorCorrectionLevel errorCorrectionLevel)
{
//
}

allgemeiner Konstruktor (für die VBA-Welt)

Der zweite Konstruktor ähnelt sehr dem ersten und ist für den Einsatz in der VBA-Welt gedacht, da VBA die im ersten Konstruktor eingesetzte Enumeration vom Typ QRErrorCorrectionLevel natürlich nicht kennt.

public QRCodeGenerator(string message, string errorCorrectionLevel)
{
//
}

fachlicher Konstruktor (für die .NET- und VBA-Welt)

Möchte man mit der Klasse einen Girocode für eine Rechnung generieren, dann kommt der dritte und letzte Konstruktor zum Einsatz. Dieser nimmt fachliche Bestandteile einer Rechnung als Eingabeparameter entgegen und kümmert sich im Hintergrund um den korrekten Aufbau des Girocode-Strings. Ein kurzer Ausflug zum Wikipedia-Artikel European Payment Council (EPC) verriet mir, welchen Aufbau der EPC-Text haben muss, damit alle darin hinterlegten Überweisungsinformationen von BankingApps korrekt eingelesen werden können. Der Artikel ist sehr übersichtlich und klar geschrieben, sodass ich den nicht zusammenzufassen brauche. Das einzige, was ich extra erwähnen würde, ist, dass im Betrag der dezimale Punkt(nicht Komma!) als Trennzeichen zu verwenden ist. Dies hab ich nämlich beim ersten Lesen übersehen.

Da der EPC-Standard die Korrekturstufe M voraussetzt, wird diese automatisch bei der Erzeugung mit dem 3. Konstruktor verwendet.

public QRCodeGenerator(string iban, string accountOwner, double amount, string invoiceReference, string bic = "")
{
//
}

Nachdem das Objekt mit einem der Konstruktoren erzeigt ist, kann mit einer der beiden SaveAs-Methoden der generierte QR Code auf die Festplatte gespeichert werden.

Klasse QRCodeGeneratorVBALibrary

Um den QR Code Generator auch unter Microsoft Access nutzen zu können, war es erforderlich, ihn von einer Wrapperklasse aufzurufen zu lassen, welche die COM-Schnittstelle implementiert. Diese enthält tatsächlich keinerlei Verarbeitungslogik, sondern macht den Generator „lediglich“ für die VBA-Welt aufrufbar. Dafür ist eine einmalige DLL-Registrierung auf dem Zielrechner erforderlich. Zu diesem Zweck gibt es vom .NET-Framework das entsprechende Tool RegAsm.exe.

Anbindung des QR Code Generators an die Rechnungsstellung

In meinen ersten Versionen des QR Code Generators wurden erzeugte QR Codes physisch auf der Festplatte unter einem festen Namen gespeichert und anschließend direkt vom Access-Rechnungsbericht eingebunden und dargestellt. Doch damit war ich nicht ganz zufrieden. Es war keine Lösung wie aus einem Guss, sondern ein Umweg, bei dem ich mich mit unschönen Nebeneffekten wie verzögertes Speichern befassen musste. Dabei war die Codezeile für die QR-Codeerzeugung schon abgearbeitet, der PC war unter Umständen jedoch noch mit dem physischen Speichervorgang des QR Codes beschäftigt, sodass die nächste Codezeile beim Einbinden des QR Codes ins Leere lief.

Zum Glück hat sich bei meiner Recherche herausgestellt, dass Access nicht nur die Möglichkeit bietet, Bilder von der Festplatte einzubinden, sondern kann auch Bilder darstellen, die in Form eines Bytearrays vorliegen.
Das war genau das, was ich gesucht habe. Aus diesem Grund habe ich neben SVG- und JPEG-Exportmethode auch eine weitere Methode realisiert, die das vorbereitete QR Code-Bildobjekt in einen Bytestrom umwandelt und diesen ausgibt. So konnte ich den Output, den diese Methode liefert, direkt dem Bildcontainer (seinem Attribut pictureData) im Access Bericht zuweisen.

    On Error Resume Next
    
    Set objQrGenerator = CreateObject("QRCodeGeneratorVBALibrary")
    If Err.Number = 0 Then
        Call objQrGenerator.CreateQRCodeGenerator(strQrCodeMessage, "M")
        If Err.Number = 0 Then
            bytQrCodeArray = objQrGenerator.getQRBytes()
        End If
    End If
    
    Err.Clear
    On Error GoTo 0

Diese Zuweisung bewirkt, dass auf der Rechnung der EPC GiroCode dargestellt wird, ohne dass dieser zuvor als Bild abgespeichert werden muss. Der komplette Prozess läuft ausschließlich auf dem lokalen Rechner ab und benötigt zu keinem Zeitpunkt eine Internetverbindung.

Fazit

Im Nachhinein betrachtet ist das ganze Projekt deutlich deutlich komplexer geworden als ich anfangs gedacht habe. Dennoch war es aus dem Blickwinkel Wissensaufbau enorm bereichernd und lehrreich, vor allem was Datenstrukturen, Designpattern und C#-Entwicklung im Allgemeinen angeht.

Sollten Sie ebenfalls Interesse an diesem Generator haben, sprechen Sie mich einfach an.