Benutzer:Nummer5
Herleitung der Zählerberechnung von Peter Danneggers Entprellroutine
Einige werden sich fragen wie man zu dem Code in der Entprellroutine kommt. Im folgenden wird eine Herleitung für den Zählercode
i = key_state ^ ~KEY_PIN; // key changed ?
ct0 = ~( ct0 & i ); // reset or count ct0
ct1 = ct0 ^ (ct1 & i); // reset or count ct1
i &= ct0 & ct1; // count until roll over ?
gezeigt. Zum besseren Verständnis werden die Variablen etwas umbenannt:
changed = key_state ^ inputs;
ct0 = ~(ct0 & changed);
ct1 = ct0 ^ (ct1 & changed);
toggle = changed & ct0 & ct1;
Die logischen Verknüpfungen sind alle in C-Notation geschrieben damit es leichter verständlich ist.
Im folgenden sind klein geschriebene Variablen nur 1bit Breit, können also nur die Werte 0 und 1 annehmen. Groß geschriebene Variablen enthalten Integer Zahlen.
Die Schreibweise CT[i] bezeichnet das i-te bit von CT. Und carry[i] bezeichnet einfach eine durchnummerierte Variable.
Formulierung des Problems
Bevor man ein Problem löst, ist es sehr hilfreich sich erstmal aufzuschreiben was das genaue Problem ist was man lösen möchte. Dabei ist es gut wenn man allen Parametern irgendwelche Namen gibt.
Das Problem des Prellens haben wir bereits gelöst indem wir nach Änderung eines Pins die Änderung nur übernehmen wollen wenn M = 4 Takte (Aufrufe der ISR) lang der gleiche Pins Zustand anliegt.
Unser jetziges Problem lautet dann:
Wie implementieren wir einen Zähler (CT) der zurückgesetzt wird wenn der aktuelle Zustand (inputs) gleich dem stabilen Zustand (key_state) ist (changed = 0) und der bis M zählt wenn sich die Zustände unterschieden (changed = 1) und dann ein Signal (toggle) gibt? Der Zähler darf nur mit logischen Operatoren aufgebaut werden.
M ist durch die Bitbreite B des Zähler vorgegeben M = 1 << B. Im C-Code ist B=2, aber wir lassen die Bitbreite erstmal unbestimmt und schauen zum Schluss ob wir für B=2 ein paar Optimierungen vornehmen können.
Pseudocode
Hier ist ein Stück Pseudocode, der die Funktionsweise des Zähler zeigt:
MAX = (1 << B) - 1; // höchster Zählerstand, alle Bits 1;
toggle = 0
if (changed) {
CT -= 1;
if (CT == MAX) {
toggle = 1
}
} else {
CT = MAX;
}
Herleitung
Die Hauptaufgabe ist es CT herunter zu zählen also jeden Takt CT' = CT - 1 zu rechnen (Der ' kennzeichnet den neuen Wert der Variablen). Erinnert man sich an die Schule kann man das Ganze als schriftliche Subtraktion schreiben (hier als Beispiel mit irgendeinem Zählerwert für B=3):
Variable Binär Dezimal
CT 100 4
- 1 001 1
- Übertrag 110 0
------------------------------
CT' 011 3Wenn man ein paar Beispiele durchprobiert fällt es auf, dass man für jede Stelle effektiv nur einen Wert subtrahieren muss. Der Übertrag für die kleinste Stelle ist immer 0 und wir ziehen nur den Subtrahenden ab der immer 1 ist. Für alle anderen Stellen ist der Subtrahend immer 0 und wir ziehen nur den Übertrag ab.
Diese Berechnung ist genau was ein Halbsubtrahierer macht[1], er subtrahiert x von y und hat als Ausgabe das Ergebnis result sowie den Übertrag carry.
Mit logischen Operatoren kann man die Ausgaben wie folgt berechnen:
result = x ^ y;
carry = ~x & y;
Für das Beispiel oben kann man nun drei Halbsubtrahierer nehmen und sie hintereinander schalten:
CT'[0] = CT[0] ^ 1;
carry0 = ~CT[0] & 1;
CT'[1] = CT[1] ^ carry0;
carry1 = ~CT[1] & carry0;
CT'[2] = CT[2] ^ carry1;
carry2 = ~CT[2] & carry1;
Wenn wir diese Zeilen nun etwas verallgemeinern erhalten wir einen Algorithmus mit dem man von einem B Bit breiten Zähler Eins subtrahieren kann:
carry[-1] = 1;
Für N=1..B-1:
CT'[N] = CT[N] ^ carry[N-1];
carry[N] = ~CT[N] & carry[N-1];
Jetzt müssen wir noch eine Möglichkeit finden den Zähler in Abhängigkeit von changed zurück zu setzen (auf den Wert MAX). Aufgeschrieben beudeutet das, dass wir folgende Fallunterscheidung vornehmen wollen:
changed == 1: CT'[N] = CT[N] ^ carry[N-1];
changed == 0: CT'[N] = 1;Da wir keine if-Abfrage o.ä. nutzen dürfen, müssen wir es schaffen in beide Berechnungen die Variable changed einzubauen ohne das sich das Ergebnis ändert und die Berechnungen dann so umformen, dass sie für beide Fälle gleich sind.
Folgende Rechenregeln sind hier hilfreich:
x & 1 = x;
x & 0 = 0;
0 ^ 1 = 1;Hierbei ist die Erkenntnis nützlich, dass der Wert von carry[i] für den Fall changed == 0 nicht von Bedeutung ist. Wir können also für carry[i] einen Wert auswählen der für uns von Vorteil ist.
changed == 1: CT'[N] = (CT[N] & changed) ^ carry[N-1] = CT[N] ^ carry[N-1];
changed == 0: carry[N-1] = 1;
CT'[N] = (CT[N] & changed) ^ carry[N-1] = 1;Damit carry[i] den richtigen Wert hat müssen wir hierfür weitere Fallunterscheidungen betrachten:
changed == 1: carry[N] = ~CT[N] & carry[N-1];
changed == 0: carry[N] = 1;Auch diese lassen sich umformulieren:
changed == 1: carry[N] = ~(CT[N] & changed) & carry[N-1] = ~CT[N] & carry[N-1];
changed == 0: carry[N-1] = 1;
carry[N] = ~(CT[N] & changed) & carry[N-1] = 1;Solange jeder vorherige carry Wert 1 ist können wir die Fallunterscheidungen als Berechnungen mit logischen Operatoren formulieren. Und der erste Wert carry[-1] ist zum Glück immer 1.
Schreiben wir den Algorithmus von oben um erhalten wir nun:
carry[-1] = 1;
Für N=0..B-1:
CT'[N] = (CT[N] & changed) ^ carry[N-1];
carry[N] = ~(CT[N] & changed) & carry[N-1];
Jetzt fehlt nur noch das Signal toggle, das uns mitteilt ob wir den Zustand übernehmen können.
Wenn wir den Zustand übernehmen können hat der Zähler von MAX bis Null gezählt und ist wieder auf MAX gesprungen. Genau dann ist der Wert des letzen Übertrags carry[B-1] == 1. Wir müssen nur Aufpassen da im Fall changed == 0 alle carry Variablen immer 1 sind. Mit dem gleichem Trick wie oben ist das togggle Signal dann:
toggle = carry[B-1] & changed;
Hiermit haben wir endlich eine Lösung für unser Problem gefunden. Wir können den Algorithmus jetzt in C ausformulieren und dabei die Parameter so wählen wie wir sie brauchen (hier B=2 und uint8_t als Datentyp):
static uint8_t ct[2] = { 0xFF, 0xFF }; // Anfgangszustand ist CT = MAX
uint8_t const changed = key_state ^ inputs;
uint8_t carry = 0xFF;
for (int n = 0; n < 2; ++n) { // Schleife über die Zähler Bits
uint8_t tmp = ct[n] & changed;
ct[n] = tmp ^ carry;
carry = ~tmp & carry;
}
uint8_t const toggle = carry & changed;
Optimieren für B=2
Der Code oben ist sehr allgemein gehalten und da in der Praxis B=2 ausreichend ist, sollten wir versuchen den Code noch etwas zu optimieren. Es ist sehr wahrscheinlich, dass der Compiler diese Optimierungen auch durchführt und wir uns die Arbeit umsonst machen. Aber auf diese Weise erhalten wir den Code von Peter Dannegger was das eigentliche Ziel dieses Artikels ist.
Zuerst betreiben wir loop runrolling indem wir die Schleife ausschreiben:
uint8_t carry0 = 0xFF;
uint8_t tmp0 = ct0 & changed;
ct0 = tmp0 ^ carry0;
carry1 = ~tmp0 & carry0;
uint8_t tmp1 = ct1 & changed;
ct1 = tmp1 ^ carry1;
carry2 = ~tmp1 & carry1;
uint8_t const toggle = carry2 & changed;
Nun folgt constant propagation indem wir alle konstanten Werte einsetzen. Zusätzlich setzen wir die temporären Variablen ein:
uint8_t tmp0 = ct0 & changed;
ct0 = (ct0 & changed) ^ 0xFF;
carry1 = ~tmp0 & 0xFF;
uint8_t tmp1 = ct1 & changed;
ct1 = (ct1 & changed) ^ carry1;
carry2 = ~tmp1 & carry1;
uint8_t const toggle = carry2 & changed;
Nutzt man die Beziehungen
x & 0xFF = x;
x ^ 0xFF = ~x;
erhält man
ct0 = ~(ct0 & changed);
carry1 = ct0 & 0xFF;
uint8_t tmp1 = ct1 & changed;
ct1 = (ct1 & changed) ^ carry1;
carry2 = ~tmp1 & carry1;
uint8_t const toggle = carry2 & changed;
und
ct0 = ~(ct0 & changed);
uint8_t tmp1 = ct1 & changed;
ct1 = (ct1 & changed) ^ ct0;
carry2 = ~tmp1 & ct0;
uint8_t const toggle = carry2 & changed;
Da wir nur zwei Zählbits haben können wir für das toggle Signal auch einfach prüfen ob beide Bits 1 sind und brauchen die tmp1 Variable nicht mehr:
ct0 = ~(ct0 & changed);
ct1 = (ct1 & changed) ^ ct0;
uint8_t const toggle = changed & ct1 & c2;
Dies sind nun die drei Zeilen mit denen der Artikel begonnen hat.