Integer Overflow

[Schorschi (Gast)]

Hallo zusammen,

Mal eine Frage an euch C cracks über integer overflows. Man nehme 
folgendes Beispiel an:

static uint16_t top_value = 6249;

void pwm_set(uint8_t value) {
  value = (value > 100) ? (100) : (value);
  
  // 1. Möglichkeit
  uint16_t cmp = (top_value * value) / 100;

  // 2. Möglichkeit
  uint16_t cmp = top_value / 100 * value;
}

Aus meiner Sicht wäre in der ersten Möglichkeit ein Overflow, falls der 
value z.B. 100 ist. Handelt dass der Compiler, oder muss ich da selber 
auf die zweite Möglichkeit ausweichen? Die Erste würde mir besser 
gefallen, da dann kein (oder ein viel kleinerer) Rundungsfehler 
entsteht.

[Oliver S. (oliverso)]

Schorschi schrieb:
> Handelt dass der Compiler,

Der Compiler nicht, aber der C-Standard.

Oliver

[Jörg W. (dl8dtl) (Moderator)]

Ist die Frage, wie groß ein "int" auf deiner Maschine ist.

Ist es nur 16 Bit (bpsw. AVR), dann macht der Compiler nichts, um dem 
Overflow zu entgegnen. Du müsstest dort manuell einen der beiden 
Elemente der Multiplikatiion auf "unsigned int" casten.

Ist es 32 Bit (bspw. ARM), dann würden die Operanden implizit nach "int" 
konvertiert. Dann passt alles.

Deine zweite Variante ist natürlich suboptimal; dann könntest du auch 
gleich den Top-Wert durch 100 teilen.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Schorschi schrieb:
> muss ich da selber auf die zweite Möglichkeit ausweichen?
Ich würde die Rechnung einfach in 32 Bit machen, und dann vom Ergebnis 
nur 16 Bit verwenden:
uint16_t cmp = (uint32_t)top_value*value / 100;

[Theor (Gast)]

Ich schlage vor, falls es um einen AVR geht, und der Compiler GCC ist, 
auf 32 Bit zu casten.
Denn dezimal 6294 hat schon 13 Bit und die Multiplikation mit dezimal 
100 (7 Bit) oder sogar dezimal 255 (8 Bit) ergibt dann 20 bwz. 21 Bit.
unsigned int hat, soweit ich weiß, hingegen nur 16 Bit.

[Schorschi (Gast)]

Hallo und vielen Dak erst mal!

Ja, es geht um einen AVR. Ich werde dann wohl die cast Methode nehmen!
Danke und Gruss

[sid (Gast)]

Jörg W. schrieb:
> Deine zweite Variante ist natürlich suboptimal; dann könntest du auch
> gleich den Top-Wert durch 100 teilen.


Jo..

ooder durch zehn ;) dann ist der Rundungsfehler (value/100)
und der maximalwert 62500 (also innerhalb 16bit)

cmd = (625*value)/10
oder wenn der Rundungsfehler inakzeptabel scheint (ist ja nie grösser 
als 1!)
und da wir ja von integern reden.... zu vernachlässigen IMHO...
egal falls Deiner Meinung nach nicht:
cmd = (625*value)/10 - value/100

(lass mal den controller beides nebeneinander herrechnen, alle werte 
zwischen 1 und 100 ... ich denke es wird keinen Unterschied machen 
#schulterzuck

'sid

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

sid schrieb:
> ich denke es wird keinen Unterschied machen #schulterzuck
Bestenfalls bei der Laufzeit... ;-)

Und dann könnte man noch weiter optimieren und das Ganze auf eine 16er 
Basis stellen, so dass man mit einer Multiplikation auskommt und gar 
nicht teilen muss, sondern nur die unteren 16 Bit abschneidet:

  cmp = (6249 * value) / 100;

                         // den Bruch mit "65536/100" erweitern
      = (6249 * value * 65536/100) / (100 * 65536/100); 
                                      
                         // Unsortieren
      = (6249 * 65536/100 * value ) / (100/100 * 65536)
   
                         // Division durch "Shift" ersetzen
      = (6249 * 65536/100 * value) >> 16;

                         // nichts für schwache Nerven: Magic Number
      = (4095344 * value) >> 16;

Und voila: wie versprochen ist von der Division nur eine Multiplikation 
übrig... ;-)

BTW: klar, dass man in den obigen Zwischenschritten für ein korrektes 
ergebnis hie und da noch ein UL anfügen sollte.

[sid (Gast)]

Lothar M. schrieb:
> Bestenfalls bei der Laufzeit... ;-)

Touché!

'sid

[Sven B. (scummos)]

Lothar M. schrieb:
> Und voila: wie versprochen ist von der Division nur eine Multiplikation
> übrig... ;-)

Ohne konkreten Bedarf würde ich sowas ja dem Compiler überlassen ;)