Hallo, wie kann man effektiv 16-Bit Multiplikations-/Divisionsroutinen (Assembler) testen? Ich könnte jeden möglichen Eingabewert in einer Schleife durchlaufen lassen, jeweils inkrementieren und das Ergebnis ausgeben lassen, aber a) sitz ich da ewig und b) sitze ich noch länger für's Prüfen aller Ergebnisse ;) Einfach ein paar zufällig gewählte Werte reinwerfen und Ergebnis prüfen geht schon, doch mich interessiert, wie man die jeweilige Implementierung effektiv prüft. Gibt's da spezielle Vorgehensweisen, Richtlinien, o.ä.? Ralf
Ralf schrieb: > Gibt's da spezielle Vorgehensweisen, Richtlinien, o.ä.? Rückgriff auf bewährte Routinen, die schon lange stabil laufen?
Ralf schrieb: > wie kann man effektiv 16-Bit Multiplikations-/Divisionsroutinen > (Assembler) testen? Man schaut sich die Implementierung an und überlegt, was alles schief gehen kann. In aller Regel gibt es Sonderfälle oder bestimmte Grenzen, ab denen etwas anders laufen muß, damit das Ergebnis stimmt. Bezogen auf da konkrete Problem sind das natürlich die Fälle, wenn die Operanden größer als 8 Bit werden sind bzw. das Ergebnis größer als 8 Bit wird. Bei signed oder gemischten signed/unsigned Operationen kommt dazu dann noch der Einfluß des Vorzeichens, da sind also ein paar Fälle mehr zu testen. Wie auch immer, wenn man die paar Grenzfälle erfolgreich durchgetestet hat, kann man ziemlich sicher sein, daß die Implementierung insgesamt auch korrekt ist.
Ralf schrieb: > Gibt's da spezielle Vorgehensweisen, Richtlinien, o.ä.? 1. Nachweis der Korrektheit der verwendeten mathematischen Algorithmen 2. Nachweis der Korrektheit der Implementation - Nachweisen, dass der vorhandene Code zu 100% getestet wird, sprich JEDE Codezeile muss mindestens einmal durchlaufen werden JEDER Vergleich muss mindestens einmal falsch und einmal wahr getestet worden sein Wenn da steht JEDER, dann musst Du beweisen können, dass wirklich ausnahmslos jede Instruktion und jeder bedingte Sprung in den Test einbezogen wird, und bei letzterem für (Bedingung wahr) und (Bedingung falsch). Das nennt man Testabdeckung, und die muss 100% sein. Deine Eingangswerte musst Du so wählen, dass Du Deine 100% erreichst. 3. Optional: Nachweis des Zeitverhaltens heißt: wie viele Takte braucht der Code minimal, wie viel maximal, und wovon hängt das ab. Manchmal ist es wichtig, dass eine Routine immer exakt die gleiche Anzahl an Zyklen und an Energie braucht, unabhängig von den Parametern. Beispiel Kryptographie. Das jetzt mal so als Anregung ohne Anspruch auf Vollständigkeit. fchk
Ralf schrieb: > Einfach ein paar zufällig gewählte Werte reinwerfen und Ergebnis prüfen > geht schon, doch mich interessiert, wie man die jeweilige > Implementierung effektiv prüft. Am besten automatisch, die Ergebnisse dann per RS232 auf den PC übertragen und dort auswerten. Ich würde bis 8*8 Bit vollständig testen und danach mit Schrittweite 127 für A und 129 für B die übrigen Werte. sind ca 5 * 65536 Ergebnisse a 4 Byte also bei 9600 Baud ist der Test in einer halben Stunde durch. Aber hoffentlich findest du keinen Pentium-Bug. Gruß Anja
@Werner: >> Gibt's da spezielle Vorgehensweisen, Richtlinien, o.ä.? > Rückgriff auf bewährte Routinen, die schon lange stabil laufen? Naja, wie man's nimmt... ich hab mir halt für den Anfang eine Routine aus'm Web rausgesucht und passend implementiert. Was ist für dich bewährt? Das was man aus nem Open-Source-Compiler aus dem Quellcode rauskopieren kann? Das was die NASA verwendet (die ja bekanntlich auch schon Abstürze im wahrsten Sinne des Wortes wegen Fehlern im Code hatte)? Zeig mir bitte die Seite mit den bewährten Sachen ;) Ich verstehe was du meinst, aber ich kenne keine "bewährte" Quelle. @c-hater: > Man schaut sich die Implementierung an und überlegt, was alles schief > gehen kann. In aller Regel gibt es Sonderfälle oder bestimmte Grenzen, > ab denen etwas anders laufen muß, damit das Ergebnis stimmt. Das erste was ich bei der Divisionsroutine gemacht habe war die Erweiterung auf Division durch Null, entsprechend gekennzeichnet durch den Rückgabewert ;) > Bei signed oder gemischten signed/unsigned Operationen kommt dazu dann > noch der Einfluß des Vorzeichens, da sind also ein paar Fälle mehr zu > testen. Ich brauche momentan nur unsigned, aber du hast recht, an die 'signed'-Fälle hab ich noch gar nicht gedacht... > Wie auch immer, wenn man die paar Grenzfälle erfolgreich durchgetestet > hat, kann man ziemlich sicher sein, daß die Implementierung insgesamt > auch korrekt ist. Okay, das passt zum o.g. 'reinwerfen von ein paar ausgesuchten Werten'. @fchk: > 1. Nachweis der Korrektheit der verwendeten mathematischen Algorithmen Den Nachweis wollte ich eigentlich durch das Testen erreichen ;) Aber du meinst vermutlich, dass schon die Basis für die Umsetzung nachweislich korrekt sein muss. > 2. Nachweis der Korrektheit der Implementation > ... > Das nennt man Testabdeckung, und die muss 100% sein. > Deine Eingangswerte musst Du so wählen, dass Du Deine 100% erreichst. Das aber jeder Sprung bzw. jedes 'IF' abgearbeitet wird bedeutet aber doch nicht, dass am Ende immer das korrekte Ergebnis rauskommt? > 3. Optional: Nachweis des Zeitverhaltens So schnell wie möglich ist natürlich immer gut, aber 16-Bit-Berechnungen auf nem 8-Bitter schließt das irgendwie aus ;) In meinem Fall wäre es zwar schön, wenn's zügig läuft, aber es ist (gottseidank) kein absolutes Kriterium gesetzt. Aber deine Liste gefällt mir gut. @Anja: > Am besten automatisch, die Ergebnisse dann per RS232 auf den PC > übertragen und dort auswerten. Ja, das hatte ich ursprünglich vor, aber ich hab das mal grob überschlagen, wenn ich für die Eingangswerte die vollen 16 Bit verwende und jeweils um eins inkrementiere, da komme ich auf 2^32 Ergebnisse, welche jeweils vier Bytes lang sind, (Division, jeweils 16-Bit Ganzzahl & Rest). Das wären ohne(!) das Mitsenden der Eingangsdaten 8GB(!). Macht bei 115200 Baud, 10 Bit Übertragung und der (irrigen) Annahme, dass keine Pausen zwischen den Zeichen auftreten etwa 8,6 Tage ;) > Ich würde bis 8*8 Bit vollständig testen und danach mit Schrittweite 127 > für A und 129 für B die übrigen Werte. sind ca 5 * 65536 Ergebnisse a 4 > Byte also bei 9600 Baud ist der Test in einer halben Stunde durch. Mmmmh, okay, das gefällt mir, das könnte ich mal ausprobieren. > Aber hoffentlich findest du keinen Pentium-Bug. Es ist ne Intel-Architektur, aber damals waren Cores noch bugfrei ;) Danke an alle für den Input! Ralf
@Viktor: > mit einem Simulator ? Ich bezweifle dass es einen 8051 Simulator gibt, der die Ausgabe der seriellen Schnittstelle in eine Datei umleiten kann, aber ich such mal, danke für den Tipp. Ralf
Ralf schrieb: > @fchk: >> 1. Nachweis der Korrektheit der verwendeten mathematischen Algorithmen > Den Nachweis wollte ich eigentlich durch das Testen erreichen ;) Damit prüfst Du Deine Implementation. Die Mathematik dahinter könnte trotzdem falsch sein. > Aber du meinst vermutlich, dass schon die Basis für die Umsetzung > nachweislich korrekt sein muss. Genau. >> 2. Nachweis der Korrektheit der Implementation >> ... >> Das nennt man Testabdeckung, und die muss 100% sein. >> Deine Eingangswerte musst Du so wählen, dass Du Deine 100% erreichst. > Das aber jeder Sprung bzw. jedes 'IF' abgearbeitet wird bedeutet aber > doch nicht, dass am Ende immer das korrekte Ergebnis rauskommt? Automatisch nicht. Du weißt dann aber, dass jeder Vergleich korrekt codiert ist. Wenn Du in einer Hochsprache arbeitest und mehrere Vergleich logisch miteinander verknüpfst, musst Du das natürlich für jeden Einzelvergleich machen. Und Du gehst sicher, dass JEDE Codezeile tatsächlich durchlaufen und damit getestet wird und Du damit keine ungetesteten Codeblöcke hast, und auch keinen toten Code, der nie durchlaufen werden kann, weil Du z.B. ein unsigned auf <0 oder ein char auf >300 testest oder ein if (a=0) statt if (a==0) stehen hast (vorsichtige Menschen schreiben daher if (0==a), weil ein versehentliches if (0=a) einen error wirft). Die Kunst ist, mit möglichst wenigen Testvektoren auszukommen und trotzdem eine vollständige Codeabdeckung zu haben. Das ist dann aber schon etwas für echte Spezialisten in diesem Bereich. Ich gehöre nicht dazu. >> 3. Optional: Nachweis des Zeitverhaltens > So schnell wie möglich ist natürlich immer gut, Eben gerade nicht! Das hatte ich ja geschrieben. Manchmal ist es wichtiger, eine konstante Durchlaufzeit zu haben als in jedem Fall eine möglichst kurze. Bei einer Multiplikation kannst Du Spezialfälle (0, 1, 2^n) nutzen, wenn es nicht auf konstante Durchlaufzeit ankommt. Und Du kannst schauen, ob beispielsweise 193*13 mehr Takte braucht als 13*193, sprich, ob es vorteilhaft ist, wenn der größere oder der kleinere Faktor zuerst kommt. Das Beispiel habe ich mit Bedacht gewählt - beide Zahlen sind prim und haben drei 1-Bits in der Binärdarstellung. fchk
Hallo Fortlaufend, chipintern, Multiplikation und deren Umkehrung rechnen. Kommt es zu einer Abweichung wird das im EEprom niedergelegt. Da darf der Chip gerne 8-Tage vor sich hinrechnen, Kontrollarbeit fällt keine an, der Chip rechnet und übernimmt zugleich die Kontrollarbeit.
Ralf schrieb: >> Am besten automatisch, die Ergebnisse dann per RS232 auf den PC >> übertragen und dort auswerten. > > Ja, das hatte ich ursprünglich vor, aber ich hab das mal grob > überschlagen, wenn ich für die Eingangswerte die vollen 16 Bit verwende > und jeweils um eins inkrementiere, da komme ich auf 2^32 Ergebnisse, > welche jeweils vier Bytes lang sind, (Division, jeweils 16-Bit Ganzzahl > & Rest). Das wären ohne(!) das Mitsenden der Eingangsdaten 8GB(!). Macht > bei 115200 Baud, 10 Bit Übertragung und der (irrigen) Annahme, dass > keine Pausen zwischen den Zeichen auftreten etwa 8,6 Tage ;) Wie Du richtig erkannt hast, macht es wenig Sinn, absolut jeden einzelnen Fall zu testen (obwohl dies bei einer geringen Anzahl von Fällen am einfachsten ist). Stattdessen mußt Du Dir überlegen, welche Fälle es wert sind, getestet zu werden. Diese Fälle zu identifizieren, ist eine Kunst für sich. Typischerweise deckt man die Fälle ab, wo es zu Über/Unterläufen bzw. Über/Unterträgen kommt. Stichworte: http://en.wikipedia.org/wiki/Boundary_case http://en.wikipedia.org/wiki/Corner_case http://en.wikipedia.org/wiki/Edge_case
Ralf schrieb: > wie kann man effektiv 16-Bit Multiplikations-/Divisionsroutinen > (Assembler) testen? Mach's mal ein bissel einfacher als all die schlauen Vorredner. Ich würde mir nen kleinen Kommandointerpreter auf dem uC schreiben, der Kommandos von der seriellen Schnittstelle empfängt, deine Lib aufruft und das Ergebnis als Text wieder zurückgibt. Die umgekehrt polnische macht sich da am einfachsten. Beispiel: 1234E321* sollte als 123 Enter, 321 multipliziere mit "geenterter" Zahl und liefere Ergebnis (also 123*321) zurück interpretiert werden. Den Rest macht ein Skript auf'n PC und da würde ich Roulette spielen, also mit Zufallszahlen arbeiten. Bei einer Lib, die so etwa 10000 mal mit Zufallszahlen richtig rechnet, brauchst du dann bloß noch Sonderfälle abzutesten, also Überläufe, Division durch 0 usw. W.S.
Muß man für eine 16bit/8bit-Division wirklich alle Zahlen durch simulieren, die überhaupt vor kommen können? Nonsens. Es reicht, wenn man begriffen hat, daß der Code anständig arbeitet, und wie er arbeitet. Man kann da bspw. mal zwei passende Operanden nehmen, und den Assemblercode mit dem Simulator durch steppen, um zu sehen. Zu beachten sind da nur Sonderfälle wie z.B. Division durch 0.
In einem ollen aber leistungsfähigen 8051-Derivat 80C517A habe ich eine MDU. Eine Hardware-Multiplikations-Divisisions-Unit für 32/16 oder 16*16. Nur 4 Maschinenzyklen für das Ergebnis. Diese bläßt den 8051 auch um Welten auf, er rechnet damit gut um den Faktor 100 schneller als Software, die Unit ist auch noch auf Floating Point optimiert, und hat Shift-Operationen bzw. Normalisierung. Da weiß man allerdings nicht, ob die Hardware richtig rechnet. Bugs ERRATA sind mir aber nicht bekannt.
@fchk: > Die Kunst ist, mit möglichst wenigen Testvektoren auszukommen und > trotzdem eine vollständige Codeabdeckung zu haben. Das ist dann aber > schon etwas für echte Spezialisten in diesem Bereich. Ich gehöre nicht > dazu. Ja, ich glaub das sind z.T. mittlerweile sogar eigene Studienkurse (je nachdem). >> So schnell wie möglich ist natürlich immer gut, > Eben gerade nicht! Das hatte ich ja geschrieben. Manchmal ist es > wichtiger, eine konstante Durchlaufzeit zu haben als in jedem Fall eine > möglichst kurze. Das stimmt schon, aber abgesehen von der von dir erwähnten Kryptographie fällt mir keine Anwendung ein, bei der die konstante Laufzeit den Vorzug hat. Oder gibt's da noch mehr? > Bei einer Multiplikation kannst Du Spezialfälle (0, 1, 2^n) nutzen, wenn > es nicht auf konstante Durchlaufzeit ankommt. Stimmt, wobei ich das für diesen Fall wahrscheinlich eher nicht brauche, aber ich behalt's im Hinterkopf. > Und Du kannst schauen, ob beispielsweise 193*13 mehr Takte braucht als > 13*193, sprich, ob es vorteilhaft ist, wenn der größere oder der > kleinere Faktor zuerst kommt. Das Beispiel habe ich mit Bedacht gewählt > - beide Zahlen sind prim und haben drei 1-Bits in der Binärdarstellung. Gute Idee, das probier ich mal. @Anfänger: > Fortlaufend, chipintern, Multiplikation und deren Umkehrung rechnen. > Kommt es zu einer Abweichung wird das im EEprom niedergelegt. Da darf > der Chip gerne 8-Tage vor sich hinrechnen, Kontrollarbeit fällt keine > an, der Chip rechnet und übernimmt zugleich die Kontrollarbeit. Weiss nicht ob die Idee so gut ist. Ich halte es zwar für nahezu unwahrscheinlich dass beispielsweise eine Multiplikations- und Divisionsroutine "gleichartig falsch" rechnen, aber ich halte einen (zusätzlichen) externen Test für sinnvoll. @Bronco: Danke für die Stichwörter. @W.S.: > Mach's mal ein bissel einfacher als all die schlauen Vorredner. Hältst du nichts von dem, was sie sagten? Dann darfst du gerne sachlich und detailliert argumentieren/kommentieren ;) > Ich würde... > Den Rest macht... So hab ich's jetzt auch gemacht, Eingangsdaten rein, Ergebnis zurück und vergleichen. Danke an alle. Ralf
@Wilhelm: Njaaaaaaaaa, der ist dann physikalisch etwas oversized vom Gehäuse ;) Und es mag sein dass solche Berechnungen zwar schneller gehen, aber der C517 hat glaub ich noch die 12er-Taktteilung. Damit ist er für das was ich machen will wiederum zu langsam :/ Ralf
Ralf schrieb: > @Wilhelm: > Njaaaaaaaaa, der ist dann physikalisch etwas oversized vom Gehäuse ;) > Und es mag sein dass solche Berechnungen zwar schneller gehen, aber der > C517 hat glaub ich noch die 12er-Taktteilung. Damit ist er für das was > ich machen will wiederum zu langsam :/ > > Ralf Wegen seiner schnellen Rechnung war dieser µC in der Automation und mit Regelungen sehr beliebt. Auch wenn da noch der Flaschenhals 8051 drin steckt. Für Miniatur-Platinen in der Streichholzschachtel ist er nichts, da hast du Recht. Fürs Hobby reicht er mir immer noch ein Weilchen. Auf meiner To-Do-Liste steht noch, die Mathe-Routinen aus dem SDCC-Compiler darauf anzupassen. SDCC unterstützt ja leider nicht die speziellen Features der 8051-Derivate. memcpy() ist unter anderem auch noch mal dran, wegen der Multiple Datapointer im Derivat. Wenn ich mal was brauche, was ich nicht habe, suche ich auch was anständiges, z.B. ARM Cortex, keine Frage.
Ralf schrieb: > Das stimmt schon, aber abgesehen von der von dir erwähnten Kryptographie > fällt mir keine Anwendung ein, bei der die konstante Laufzeit den Vorzug > hat. In welcher Anwendung im Embedded-Bereich hat denn eine möglichst kurze durchschnittliche Laufzeit einen Vorteil, wenn die maximale Laufzeit gleich bleibt? Die meisten Sachen haben gewisse Echtzeitanforderungen und da bringt es nichts schneller als nötig fertig zu sein. Ganz im Gegenteil ist eine konstante Laufzeit beim Test der Anwendung hilfreich.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.