Sättigende Integer-Addition

[Walter T. (nicolas)]

Hallo zusammen,

ich habe gerade eine (einfache) Funktion geschrieben, um die Addition 
von Werten auf einen Bereich zu begrenzen:

/* Addition mit Begrenzung auf waehlbaren Bereich
 * val:  Summand 1
 * incr: Summand 2
 * min:  Untere Wertegrenze
 * max:  Obere Wertegrenze */
uint8_t limadd_uint8(uint8_t val,int8_t incr,uint8_t min,uint8_t max)
{
    int16_t temp;
    
    temp = val+incr;

    // Fehlerhafte max/min abfangen
    if (temp > (int16_t) UINT8_MAX) {
        temp = UINT8_MAX;
    }
    else if (temp < 0) {
        temp = 0;
    }
    
    if (temp > max) {
        temp = max;
    }
    else if (temp < min) {
        temp = min;
    }
    
    return (uint8_t) temp;
}

Nun frage ich mich: soetwas ist doch vermutlich eine ziemlich oft 
benötigte Funktion (implizit kommt sie in meinem Quelltext mit 
unterschiedlichen Datentypen zweistellig vor und wird nur gerade in eine 
einzelne Funktion pro Datentyp gebracht). Gibt es soetwas nicht schon in 
der C-Standard-Library?

Viele Grüße
W.T.

[(prx) A. K. (prx)]

Walter Tarpan schrieb:
> Nun frage ich mich: soetwas ist doch vermutlich eine ziemlich oft
> benötigte Funktion

In DSP-Code, Audio- und Videoverarbeitung kommt saturierende Arithmetik 
oft vor, in den meisten anderen Bereichen über die Häufigkeit 
ausgeführter Befehle betrachtet jedoch selten. Oft gibt es bei in diesen 
Bereichen eingesetzten Prozessoren SIMD-Befehle (x86 ab MMX) für 
saturierende Addition/Subtraktion und prozessorspezifische Libraries um 
diese zu nutzen.

[Walter T. (nicolas)]

Guten Morgen,
an DSPs habe ich noch nicht einmal gedacht. Hier sind es gerade so 
einfache Sachen wie "erlaubter Wertebereich in xy-Einstellungen".

Mir geht es aber auch gar nicht mal darum, das möglichst effizient oder 
clever umzusetzen - die Funktionen tun das, was sie sollen und sind an 
keiner Stelle, wo die Geschwindigkeit wichtig ist.

Mir geht es darum, ob ich gerade eine Standard-Library-Funktion 
nachimplementiere (wobei ich mich schon ein paarmal erwischt habe, wenn 
ich Wochen später zufällig auf den passenden Header gestoßen bin).

[Hans (Gast)]

Aktuelle GCC-Versionen haben eigene Datentypen für 
Fixed-Point-Arithmetik mit Saturierung:
http://gcc.gnu.org/onlinedocs/gcc-4.9.0/gcc/Fixed-Point.html#Fixed-Point

[Uwe (de0508)]

Hallo,

und wie behandelst Du einen Überlauf, wenn die Addition überhaupt nicht 
mit 16Bit ausgeführt wird?

temp = val+incr;

[(prx) A. K. (prx)]

Uwe S. schrieb:
> und wie behandelst Du einen Überlauf, wenn die Addition überhaupt nicht
> mit 16Bit ausgeführt wird?

Sie wird hier mit mindestens 16 Bits ausgeführt.

[Johann L. (gjlayde)]

Sind da nicht 2 Vergleiche bzw. MIN/MAX-Berechnungen überflüssig?

Etwa ist immer max <= UINT8_MAX und daher

   MIN (temp, UINT8_MAX, max) = MIN (temp, max)

und analog wegen min >= 0

   MAX (temp, 0, min) = MAX (temp, min)

d.h. deine Funktion macht nichts anderes als

uint8_t limadd_uint8 (uint8_t val, int8_t incr, uint8_t min, uint8_t max)
{
    int16_t temp = val + incr;

    if (temp > max)
        temp = max;

    if (temp < min)
        temp = min;
    
    return (uint8_t) temp;
}

[Walter T. (nicolas)]

Johann L. schrieb:
> Sind da nicht 2 Vergleiche bzw. MIN/MAX-Berechnungen überflüssig?

Du hast Recht. Und der Compiler ist in dieser Frage auch deutlich 
mutiger als ich vorgegangen. Ich bin bei Vergleichen Int/unsigned int 
vielleicht etwas zu mißtrauisch.

[Gaestchen (Gast)]

Johann L. schrieb:
> d.h. deine Funktion macht nichts anderes als

Da wäre ich mir an Deiner Stelle nicht so wirklich sicher.  Übergib mal 
( 0, -2,-2, 100)

[Walter Tarpan (Gast)]

Gaestchen schrieb:
> Da wäre ich mir an Deiner Stelle nicht so wirklich sicher.  Übergib mal
> ( 0, -2,-2, 100)

Naja, also min > max würde ich allerdings schon als "grobe Gemeinheit" 
bezeichnen.

[Kaj (Gast)]

Gaestchen schrieb:
> Johann L. schrieb:
>> d.h. deine Funktion macht nichts anderes als
>
> Da wäre ich mir an Deiner Stelle nicht so wirklich sicher.  Übergib mal
> ( 0, -2,-2, 100)
Wer unzulaessige Werte an eine Funktion uebergibt, der muss sich nicht 
wundern wenn die Funktion nicht das macht, was man erwartet. Ganz 
einfach.
Und wer bei einem Argument, das mit "uint..." deklariert ist, eine -2 
uebergibt, dem ist eh nicht zu helfen.

[Johann L. (gjlayde)]

Walter Tarpan schrieb:
> Gaestchen schrieb:
>> Da wäre ich mir an Deiner Stelle nicht so wirklich sicher.  Übergib mal
>> ( 0, -2,-2, 100)
>
> Naja, also min > max würde ich allerdings schon als "grobe Gemeinheit"
> bezeichnen.

Zudem ist die Frage, was wäre dann eine sinnvolle Ausgabe wenn gefordert 
werd, daß die Ausgabe min <= wert <= max erfüllt?

Wenn min > max dann ist wegen

   max < min <= wert <= max < min

Das bedeutet dann max < max und min < min, was schwerlich zu erfüllen 
ist...

[Andreas S. (Firma: Schweigstill IT) (schweigstill)]

Hans schrieb:
> http://gcc.gnu.org/onlinedocs/gcc-4.9.0/gcc/Fixed-Point.html#Fixed-Point

Und zwar nicht erst seit GCC 4.9, sondern schon 4.6. Jedoch muss der 
Compiler (und die C-Bibliothek?) mit der Option "--enable-fixed-point" 
übersetzt worden sein:

http://stackoverflow.com/questions/11005162/how-to-make-use-of-the-gcc-fixed-point-types-extension-on-arm-cortex-m

[Johann L. (gjlayde)]

Andreas Schweigstill schrieb:
> Hans schrieb:
>> http://gcc.gnu.org/onlinedocs/gcc-4.9.0/gcc/Fixed-Point.html#Fixed-Point
>
> Und zwar nicht erst seit GCC 4.9, sondern schon 4.6. Jedoch muss der
> Compiler (und die C-Bibliothek?) mit der Option "--enable-fixed-point"
> übersetzt worden sein:

Nicht unbedingt, wenn der entsprechende Support im GCC Backend aktiviert 
ist, dann ist --enable-fixed-point nicht notwendig.  Dies ist z.B. der 
Fall ab avr-gcc  4.8

Und erst ab avr-gcc 4.8 sind einige Typen optimiert untestützt und nicht 
nur durch zwar funktionierende, aber extrem ineffiziente 
libgcc-Implementierungen verfügbar.

Um eine saturierende 16-Bit short Addition zu erhalten, kann man recht 
umständlich:
 

#include <stdfix.h>

short satadd (short a, short b)
{
    sat fract fa = rbits (a);
    sat fract fb = rbits (b);

    return bitsr (fa + fb);
    
}

 
Was dann ergibt:
 

satadd:
  add r24,r22
  adc r25,r23
  brvc 0f
  ldi r25,0x80
  cp r23,r25
  sbc r24,r24
  sbci r25,0
  0:
  ret

Die Saturierung ist allerding immer auf die Bitbreite des Typs; so 
allgemein wie im OP mit frei wählbaren min und max ist sie nicht. 
Allerdings kann sie dazu verwendet werden, in der gleichen Bitbreite zu 
bleiben und nicht den nächst größeren Typ (falls es so einen gibt) 
verwenden zu müssen.

Im OP liegt jedoch ein besonderer Fall von unsigned+signed vor, der 
eigentlich nicht kommutativ ist:

Bei

   (unsigned char) 255 + (signed char) -1

will man als Ergebnis (unsigned char) 254 haben, während es bei

   (signed) -1 + (unsigned) 255

an der (signed char) Obergrenze anschlägt und das Ergebnis (signed char) 
127 sein soll.

Die Fixed-Point Typen des GCC hingegen haben die gleichen Promotions von 
unsigned (als Qualifier) wie int-Typen auch.