Overflow boundary checking

  • C#
  • .NET 4.5

Es gibt 26 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Overflow boundary checking

    Hey,

    Folgendes: Gegeben ist eine Zahl. Diese Zahl soll in zwei Zahlen zerlegt werden die addiert die Ursprüngliche Zahl ergeben.
    Das ist kein Problem, allerdings gilt es, ein vernünftiges Boundary-checking zu machen.

    Für Int32 Werte habe ich das wie folgt gelöst:

    C#-Quellcode

    1. int original = Convert.ToInt32(instruction.Operand);
    2. long value1 = simpleValueGenerator.GenerateInt32(int.MinValue, int.MaxValue);
    3. long value2 = original - value1;
    4. bool overflowing = value2 < int.MinValue || value2 > int.MaxValue;
    5. if (overflowing)
    6. {
    7. // Do stuff
    8. }
    9. else
    10. {
    11. // Do stuff
    12. }


    Nun möchte ich aber das ganze für longs, d.h. Int64 Werte machen, und zwar ohne dabei BigInteger oder decimal zu verwenden.
    Kann man prüfen ob die Operation für zwei longs overflowed indem man evtl klevere Bit-checks verwendet ?
    Ich möchte eine gute Overflow-Bedingung finden die mich informiert wenn ich die long bounds überschreite.
    C# Developer
    Learning C++

    C#-Quellcode

    1. public static bool IsOverflowing(int a, int b)
    2. {
    3. int sum = unchecked(a + b);
    4. return (a >= 0 && b >= 0) && sum < 0 || (a <= 0 && b <= 0) && sum > 0;
    5. }


    C#-Quellcode

    1. static void Main(string[] args)
    2. {
    3. Console.WriteLine(IsOverflowing(int.MinValue, -1)); // true
    4. Console.WriteLine(IsOverflowing(int.MaxValue, 1)); // true
    5. Console.Read();
    6. }


    _
    DotNETWork (Generische Tcp-Klasse, verschlüsselt!)
    MonogameMinecraftClone (Minecraft-Klon)
    NeuroEvolution (Implementation zweier Lernmethoden für neuronale Netze)

    C#-Quellcode

    1. public static bool IsOverflowing<T>(T a, T b) where T : struct,
    2. IComparable,
    3. IComparable<T>,
    4. IConvertible,
    5. IEquatable<T>,
    6. IFormattable
    7. {
    8. var x = (dynamic)Convert.ChangeType(a, typeof(T));
    9. var y = (dynamic)Convert.ChangeType(b, typeof(T));
    10. var sum = x + y;
    11. return (x >= 0 && y >= 0) && sum < 0 || (x <= 0 && y <= 0) && sum > 0;
    12. }


    Generisch; probier's damit.
    DotNETWork (Generische Tcp-Klasse, verschlüsselt!)
    MonogameMinecraftClone (Minecraft-Klon)
    NeuroEvolution (Implementation zweier Lernmethoden für neuronale Netze)
    Ohne Checked mit de beiden Funktionen CheckHigh und CheckLower

    Ungetestet

    VB.NET-Quellcode

    1. Option Strict On
    2. Option Explicit On
    3. Public Module Module1
    4. Public Sub Main()
    5. Dim val = 11L
    6. Dim l1 = Int64.MaxValue - 100
    7. Dim l2 = Int64.MinValue + 100
    8. Dim start = Int64.MaxValue - 200
    9. For i As Int64 = 0 To Int64.MaxValue - 1
    10. If CheckHigh(l1, i) OrElse CheckLower(l1, i) Then
    11. Stop
    12. Exit For
    13. End If
    14. Next
    15. start = Int64.MinValue + 200
    16. For i As Int64 = 0 To Int64.MaxValue - 1
    17. If CheckLower(l2, i) OrElse CheckLower(l2, i) Then
    18. Stop
    19. Exit For
    20. End If
    21. Next
    22. End Sub
    23. Private Function CheckLower(ByVal basis As Int64, ByVal val As Int64) As Boolean
    24. Dim m = Int64.MaxValue
    25. If (basis < 0) AndAlso (basis + m) < val - 1 Then
    26. Return True
    27. End If
    28. Return False
    29. End Function
    30. Private Function CheckHigh(ByVal basis As Int64, ByVal val As Int64) As Boolean
    31. Dim m = Int64.MinValue
    32. If (basis > 0) AndAlso (basis + m) > -val - 1 Then
    33. Return True
    34. End If
    35. Return False
    36. End Function
    37. End Module

    VB.NET-Quellcode

    1. Console.WriteLine(CheckLower(Int64.MaxValue, 1) OrElse CheckHigh(Int64.MaxValue, 1)) 'true
    2. Console.WriteLine(CheckLower(Int64.MinValue, 1) OrElse CheckHigh(Int64.MinValue, 1)) 'true
    3. Console.WriteLine(CheckLower(Int64.MaxValue, 0) OrElse CheckHigh(Int64.MaxValue, 0)) 'false
    4. Console.WriteLine(CheckLower(Int64.MinValue, 0) OrElse CheckHigh(Int64.MinValue, 0)) 'false

    C#-Quellcode

    1. static void Main()
    2. {
    3. var val = 11L;
    4. var l1 = Int64.MaxValue - 100;
    5. var l2 = Int64.MinValue + 100;
    6. var start = Int64.MaxValue - 200;
    7. for (Int64 i = 0; i <= Int64.MaxValue - 1; i++)
    8. {
    9. if (CheckHigh(l1, i) || CheckLower(l1, i))
    10. {
    11. System.Diagnostics.Debugger.Break();
    12. break;
    13. }
    14. }
    15. start = Int64.MinValue + 200;
    16. for (Int64 i = 0; i <= Int64.MaxValue - 1; i++)
    17. {
    18. if (CheckLower(l2, i) || CheckLower(l2, i))
    19. {
    20. System.Diagnostics.Debugger.Break();
    21. break;
    22. }
    23. }
    24. }
    25. private static bool CheckLower(Int64 basis, Int64 val)
    26. {
    27. var m = Int64.MaxValue;
    28. if ((basis < 0) && (basis + m) < val - 1)
    29. {
    30. return true;
    31. }
    32. return false;
    33. }
    34. private static bool CheckHigh(Int64 basis, Int64 val)
    35. {
    36. var m = Int64.MinValue;
    37. if ((basis > 0) && (basis + m) > -val - 1)
    38. {
    39. return true;
    40. }
    41. return false;
    42. }



    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „exc-jdbi“ ()

    Bezogen auf Post #3:
    Spricht was dagegen, eine Exception zu fangen?

    C#-Quellcode

    1. long a = ...;
    2. long b = ...;
    3. long sum;
    4. bool success;
    5. try
    6. {
    7. sum = checked(a + b);
    8. success = true;
    9. }
    10. catch (OverflowException ex)
    11. {
    12. success = false;
    13. }
    14. if (success) Console.WriteLine("Summe = {0}", sum); else Console.WriteLine("Überlauf");


    Einzig auf die Performance könnte das drücken, wenn häufig Überläufe auftreten.
    Ist aber meiner Meinung nach sehr gut lesbar, da sofort klar ist, was der Code macht. Ist auch extrem leicht veränderbar, wenn man andere Typen verwenden möchte.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Niko Ortner“ ()

    @Rikudo Probierma, das ganze einen Datentyp größer zu testen, also mit Long für (U)Integer und Decimal für (U)Long, da gibt keinen Unter- bzw. Überlauf.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    VB-Fragen über PN / Konversation werden ignoriert!
    @RodFromGermany Und bei einem Decimal? Es mag ja unendlich viele super duper wege geben, aber meist ist der Code dann am Ende kaum zu verstehen oder hat mehrere If-Anweisungen. Da bleibe ich lieber bei checked und fang die OverflowException.

    slice schrieb:

    Und bei einem Decimal?
    Das schien mir hier OutOfContext zu liegen.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    VB-Fragen über PN / Konversation werden ignoriert!
    @φConst Danke deine generische Lösung ist auf jeden Fall interessant.
    Kannst du vielleicht noch erklären welche der vielen Interfaces in der Methodensignatur für was genau verwendet werdet werden, krieg das noch nicht so ganz in meinen Kopf ^^"
    Ist die Bedingung für Overflowchecks immer die Gleiche unabhängig von der Rechenoperation?
    Also was ist bspw mit Subtraktion statt Addition? Wenn ich die eine Zahl von der anderen abziehe um auf die Ursprüngliche Zahl zu kommen?
    C# Developer
    Learning C++
    Die von @φConst vorgeschlagenen Interfaces, sowie der Hinweis auf Struct, würde ich auch so in Erwägung ziehen.

    C#-Quellcode

    1. where T : struct,
    2. IComparable,
    3. IComparable<T>,
    4. IConvertible,
    5. IEquatable<T>,
    6. IFormattable


    Schon aus dem Grunde, weil Microsoft das genau auf die gleiche Weise macht. Schlussendlich bewirkt es, die Einschränkung auf einen numerischen Wert. Numerische Datentypen besitzen in .Net eine Strukture.

    Freundliche Grüsse

    exc-jdbi
    Diese Idee hatte ich aus stackoverflow kopiert.
    Der Autor hat einfach alle diejenigen Interfaces als Bedingung gesetzt, von der jeder numerische Datentyp erbt.
    So wird gewährleistet das kein <string> und dergleichen übergeben werden kann (propbier's aus ;) )
    _
    DotNETWork (Generische Tcp-Klasse, verschlüsselt!)
    MonogameMinecraftClone (Minecraft-Klon)
    NeuroEvolution (Implementation zweier Lernmethoden für neuronale Netze)
    @φConst Das ist eigentlich recht clever, jetzt verstehe ich das auch.
    Allerdings scheint das ganze nicht sehr zuverlassig zu funktionieren.
    Hier ein Beispiel, das definitv overflowed aber die Funktion gibt false zuruck.
    Bei int und long scheint es zu gehen, bei byte, float und double irgendwie nicht so richtig, woran liegt das?

    C#-Quellcode

    1. public static void Main(string[] args)
    2. {
    3. Console.WriteLine(IsOverflowing(float.MaxValue - 10, 15.0F)); // Returns false ??
    4. Console.ReadKey();
    5. }
    6. private static bool IsOverflowing<T>(T a, T b)
    7. where T : struct, IComparable, IComparable<T>, IConvertible, IEquatable<T>, IFormattable
    8. {
    9. var x = (dynamic) Convert.ChangeType(a, typeof(T));
    10. var y = (dynamic) Convert.ChangeType(b, typeof(T));
    11. var sum = x + y;
    12. return (x >= 0 && y >= 0) && sum < 0 || (x <= 0 && y <= 0) && sum > 0;
    13. }
    C# Developer
    Learning C++
    Die Methode ist ausschließlich für Int64 Int32 und vielleicht int16 implementiert.

    Double, byte et cetera behandeln meiner Einschätzung nach Überläufe ganz anders.
    _
    DotNETWork (Generische Tcp-Klasse, verschlüsselt!)
    MonogameMinecraftClone (Minecraft-Klon)
    NeuroEvolution (Implementation zweier Lernmethoden für neuronale Netze)
    @φConst hmmm okay.
    Wie wuerde man es denn fuer die anderen Datentypen testen?
    Bei float point operations kann man evtl auf positiv infinity oder negative infinity testen?
    Aber wieso funktioniert byte auch nicht? Seltsam.
    C# Developer
    Learning C++
    bei byte und ist es nicht ein Problem von überläufen, sondern viel mehr das Problem, dass C# keine addition operation für diese hat, sondern das ganze viel mehr dann mit int passiert und somit ja nicht wirklich ein Überlauf stattfindet...
    Deshalb wäre die Lösung bei φConst code einfach am Ende noch ein cast zu "T" hinzuzufügen, denn auch casts haben einen Overflow check für die primitiven typen und das funktioniert dann auch für short und byte...
    Edit: bzw. in diesem fall eben damit der manuelle check funktioniert, weil es abschneidet...

    Btw. für Multiplikation gilt:

    Quellcode

    1. Math.Log(a,2) + Math.Log(b,2) > Math.Log(...MaxValue)

    natürlich wäre das einfache überprüfen mit einem upcast und gucken ob result > MaxValue einfacher. Jedoch leider nicht allgemein formuliert, wäre nämlich für long nicht möglich

    Ich hab hier aber auch noch was zusammengestellt, was ich aber nicht weiß ob das wirklich für alle Fälle funktioniert:

    C#-Quellcode

    1. static class Limits<T> where T : struct
    2. {
    3. public static readonly T MaxValue;
    4. public static readonly T MinValue;
    5. static Limits()
    6. {
    7. var type = typeof(T);
    8. var fld = type.GetField("MaxValue",BindingFlags.Public|BindingFlags.Static);
    9. if (fld != null)
    10. MaxValue = (T)fld.GetValue(null);
    11. fld = type.GetField("MinValue",BindingFlags.Public|BindingFlags.Static);
    12. if (fld != null)
    13. MinValue = (T)fld.GetValue(null);
    14. }
    15. }
    16. static bool checkOverflow<T>(T a,T b) where T : struct
    17. {
    18. decimal v1 = (decimal)Convert.ChangeType(a,typeof(decimal));//evtl. noch optimierbar mit einer reinen IL funktion...
    19. decimal v2 = (decimal)Convert.ChangeType(b,typeof(decimal));
    20. decimal maxVal = (decimal)Convert.ChangeType(Limits<T>.MaxValue,typeof(decimal));
    21. return (v1+v2) > maxVal;
    22. }


    Über decimal selbst brauchst dir keine sorgen machen, denn das sollte mW von selbst nen overflow schmeißen...
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---

    Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „jvbsl“ ()

    jvbsl schrieb:

    nicht wirklich ein Überlauf stattfindet...
    Bei der Rück-Zuweisung jedoh knallt es dann.
    Im Prinzip ist das mein Vorschlag von Post #10.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    VB-Fragen über PN / Konversation werden ignoriert!