von gjlayde

Unter Saturierung (von engl. to saturate, wörtlich Sättigen) versteht man die Eigenschaft bestimmter Operatoren, bei Überschreitung der Bereichs-Grenzen den Maximal- bzw. Minimalwert zu liefern, anstatt überzulaufen und einen Wert zu liefen, der sehr weit vom erwarteten Ergebnis entfernt liegt.

[Bearbeiten] Einleitung

Bei vielen Anwendungen wie der digitalen Signalverarbeitung ist es wichtig, daß ein Wert an den Rändern seines Wertebereiches nicht überläuft. Ist eine Größe x zum Beispiel als 8-Bit Wert mit Vorzeichen gespeichert, so führt die Operation

    char x = 127; // x =  127
    char y = x+1; // y = -128 

zum Ergebnis y=−128. Solch ein riesiger Sprung ist in vielen Anwendungen fatal. Anstatt an den Bereichsgrenzen überzulaufen ist dann erforderlich daß der Wert an der Maximalgrenze stehen bleibt, d.h. daß das Ergebnis in dem Falle y=127 ist anstatt −128. Die Variable kann ab dieser Grenze nichts mehr aufnehmen: sie hat ihre "Sättigung" erreicht.

Um saturierte Addition von der üblichen Addition zu unterscheiden, wird hier das Symbol verwendet.

Eine saturierte Addition hat eine sehr wichtige Eigenschaft der gewohnten Addition, nämlich die Monotonie:

Analoge Zusammenhänge gibt es für die Monotonie der (saturierten) Subtraktion

sowie für andere saturierte Operatoren wie Negation, Betragsbildung, Multiplikation und Division, welche die gleichen Monotonie-Eigenschaften haben wie die "nativen" mathematischen Operatoren.

Durch Zugewinn der Monotonie verliert man allerdings die Assoziativität, so daß die Reihenfolge, in der saturierte Operatoren anwandt werden, wie im folgenden Beispiel einen Einfluß auf das Ergebnis haben kann:

Das ist bei Verwendung von saturierten Operatoren immer zu bedenken!

Neber der Saturierung, welche bei den Werte an den Bereichsgrenzen – also dort, wo ein Überlauf stattfinden würde – stehen bleibt, gibt es auch Saturierungen, die zB auf den Wertebereich −100...100 begrenzen. Letztere lässt sich zusammensetzen aus einer "normalen" Saturierung, wie sie hier im weiteren besprochen wird, und einer Maximum- bzw. Minimum-Bildung gegen den gewünschten Wertebereich.

[Bearbeiten] Umsetzung

Zur konkreten Umsetzung der Saturierung gibt es mehrere Möglichkeiten:

A priori

Bereits bevor das Ergebnis berechnet wurde wird anhand der Eingabe entschieden, ob der Wertebereich verlassen und ein Über- oder Unterlauf entstehen wird.

A posteriori

Erst nach der Berechnung wird anhand des Ergebnisses entschieden, ob ein Über- oder Unterlauf auftrat.

Sind vorzeichenbehaftete Operanden beteiligt, so fällt die Entscheidung strenggenommen automatisch zugunsten der a priori-Variante aus: In C führt der Überlauf von vorzeichenbehafteten Zahlen explizit zu undefiniertem Verhalten; es steht dem Compiler frei, in einem solchen Fall Instruktionen zu generieren, die beispielsweise den Prozessor anhalten oder neustarten.

Am gebräuchlichsten und effizientesten für kleine Typen sind (wenn möglich) A-posteriori-Methoden, da hier das Ergebnis als Entscheidungsgrundlage mit einbezogen werden kann. Das Ergebnis wird unbedingt berechnet und im Fall eines Überlaufs wieder verworfen. Dieser Mehraufwand muss bei aufwändigen Operatoren mit dem Aufwand von a-priori-Methoden abgewogen werden.

Die A-posteriori-Verfahren lassen sich wiederum untergliedern in unterschiedliche Strategien, die je nach Einsatzfeld mehr oder minder effizient oder garnicht anwendbar sind:

Erweiterter Zahlenbereich

Die Operation wird in einem erweiterten Zahlenbereich ausgeführt in dem kein Überlauf auftreten kann. Das Ergebnis wird dann gegen die Grenzen getestet und ggf. beschnitten. Die Saturierung eines 32-Bit Wertes wird damit sehr aufwändig, weil der nächstgrößere Typ in Hochsprachen 64 Bits breit ist. Irgendwo ist eine Grenze erreicht, ab der es keinen nächstgrößeren Typ mehr gibt. Eine 8-Bit signed Saturierung könnte in C so aussehen:

char add_signed_sat8 (char x, char y)
{
    short x_y = (short) x + y;
    
    return MAX (MIN (x_y, 127), -128);
}

Auswertung von Flags

Viele Rechenwerke produzieren Flags, die Auskunft über Eigenschaften des Ergebnisses enthalten. Dazu gehören Carry-, Overflow-, Negative-, Zero-Flag etc. Von einer Hochsprache aus hat man auf diese Flags keinen Zugriff, man muss also Assembler zu ihrer Auswertung heranziehen.

Test auf Ergebnis-Überlauf ohne Flags

Hier wird die Monotonie ausgenutzt: Falls eine positive Zahle addiert wird, so muß das Ergebnis größer werden. Falls nicht, muß ein Überlauf aufgetreten sein. Eine Formulierung in C:

char add_signed_sat8 (char x, char y)
{
    char x_y = x + y;
 
    if (y > 0  &&  x_y < x)
        return 127;
 
    if (y < 0  &&  x_y > x)
        return -128;
 
    return x_y;
}

[Bearbeiten] Auf AVR

Saturierung ist eine Eigenschaft eines Operators und nicht die einer Zahl, wie bei unsigned/signed, welche nur von der Interpretation des Ergebnisses abhängt. Während für signed/unsigned-Addition die gleichen Befehle verwendet werden, ist dies bei Saturierung nicht der Fall, und wir müssen unterscheiden zwischen verschiedenen Ausprägungen der Saturierung, was in unterschiedlichen Implementierungen resultiert.

Wie im vorhergehenden Abschitt zu sehen, kann Saturierung im Vergleich zu einer gewohnten Addition, die in einem Maschinenbefehl umsetzbar ist, sehr aufwändig sein. Daher versuchen wir nach Möglichkeit Status-Flags des AVR zu verwenden, um einen Überlauf zu erkennen. Dies ist von einer Hochsprache aus leider nicht möglich, so daß wir auf (Inline-)Assembler zurückgreifen müssen, um eine effiziente Implementierung zu erhalten.

Angemerkt sei noch, daß in einer Hochsprache wie C auch bei Verwendung von Assembler die Portabilität erhalten bleibt, wenn maschinenabhängige Sequenzen z. B. per #ifdef parametrisiert werden.

[Bearbeiten] Unsigned

Addition

Das ist der einfachste Fall. Die Addition zweier vorzeichenloser Zahlen liefert immer ein nicht-kleineres Ergebnis. Ein Überlauf ist am Carry erkennbar:

;; unsigned R16
;; unsigned R0
;; R16 := R16 + R0 mit Saturierung
add  R16, R0
brcc 0f
; Falls es einen signed Überlauf gab (C=1) Maximalwert laden
ldi  R16, 0xff    
0:

Als Inline-Assembler-Schnippel für avr-gcc, der in eine Inline-Funktion gefasst ist, sieht das so aus:

#include <stdint.h>
 
// x += y mit Saturierung
static inline uint8_t add_usat8 (uint8_t x, uint8_t y)
{
    asm ("add  %[x], %[y]"   "\n\t"
         "brcc 0f"           "\n\t"
         "ldi  %[x], 0xff"   "\n\t"
         "0:"
         : [x] "+d" (x)
         : [y] "r"  (y));
 
    return x;
}

Zu beachten ist, daß x wegen dem LDI in Registerklasse "d" (R16–R31) liegen muss, während für y jedes Register erlaubt ist, es also in Klasse "r" (R0–R31) liegen kann.

Ein volatile ist hier übrigens nicht notwendig: der Schnippel hat den Compiler nämlich bereits über alle Nebeneffekte informiert. Der Compiler darf den Schnippel (bzw. die Inline-Funktion) also wegoptmieren, wenn das Ergebnis nicht verwendet wird – was hier vollkommen in Ordnung ist.

Subtraktion

Ganz analog verläuft die Subtraktion:

;; unsigned R1
;; unsigned R0
;; R1 := R1 - R0 mit Saturierung
sub  R1, R0
brcc 0f
; Falls es einen unsigned Unterlauf gab (C=1) Minimalwert laden
clr  R1
0:

[Bearbeiten] Signed

Mehr Aufwand erfordern die signed-Operatoren, weil diese in zwei Richtungen überlaufen können.

Addition

;; signed R16
;; signed R0
;; R16 := R16 + R0 mit Saturierung
add  R16, R0
brvc 0f
; Falls es einen signed Überlauf gab (V=1) Maximalwert laden
ldi  R16, 0x7f
sbrc R0, 7
; R0 ist negativ, daher muss der Minimalwert geladen werden
ldi  R16, 0x80
0:

Subtraktion

;; signed R16
;; signed R0
;; R16 := R16 - R0 mit Saturierung
sub  R16, R0
brvc 0f
; Falls es einen signed Überlauf gab (V=1) Minimalwert laden
ldi  R16, 0x80
sbrc R0, 7
; R0 ist negativ, daher muss der Maximalwert geladen werden
ldi  R16, 0x7f
0:

Negation

Vorsicht ist geboten beim Negieren einer Zahl und bei Betragsbildung, weil der Wert 0x80=−128 kein positives Pendant hat:

;; signed R0
;; R0 := -R0 mit Saturierung
neg  R0
brvc 0f
; Signed Überlauf (V=1): Das Ergebnis ist 0x80 und wird verändert zu 0x7f
dec  R0
0:

Betrag

;; signed R0
;; R0 := Abs (R0) mit Saturierung
sbrc R0, 7
neg  R0        ; R0 < 0: negieren
sbrc R0, 7
dec  R0        ; R0 ist immer noch < 0 (also 0x80): lade 0x7f 

[Bearbeiten] Unsigned + Signed

Diese Kombination ist am aufwändigsten in der Behandlung und geschieht am einfachsten durch Umskalierung auf zwei signed-Werte, signed-saturierter Operation und nachfolgender Rückskalierung. Zu beachten ist, daß dieser Operator nicht kommutativ ist, d.h. a+b liefert i.A. ein anderes Ergebnis als b+a.

Addition

;; unsigned R16
;; signed   R0
;; R16 := R16 + R0 mit Saturierung
; Transformation [0x00, 0xff] -> [0x80, 0x7f]
subi R16, 0x80
add  R16, R0
brvc 0f
; Falls es einen signed Überlauf gab (V=1) Maximalwert laden
ldi  R16, 0x7f
sbrc R0, 7
; R0 ist negativ, daher muss der Minimalwert geladen werden
ldi  R16, 0x80
0:
; Rücktransformation [0x80, 0x7f] -> [0x00, 0xff]
subi R16, 0x80

Subtraktion

;; unsigned R16
;; signed   R0
;; R16 := R16 - R0 mit Saturierung
; Transformation [0x00, 0xff] -> [0x80, 0x7f]
subi R16, 0x80
sub  R16, R0
brvc 0f
; Falls es einen signed Überlauf gab (V=1) Minimalwert laden
ldi  R16, 0x80
sbrc R0, 7
; R0 ist negativ, daher muss der Maximalwert geladen werden
ldi  R16, 0x7f
0:
; Rücktransformation [0x80, 0x7f] -> [0x00, 0xff]
subi R16, 0x80

[Bearbeiten] Siehe auch

Im AVR-Tutorial:

• 8-Bit Arithmetik
• Vergleiche