AK: Fix some overflows/underflows that weren't properly handled

Based on #5699. Closes #5699.

3 files changed, 127 insertions, 94 deletions

diff --git a/AK/Tests/TestTime.cpp b/AK/Tests/TestTime.cpp
index 7999be706d..87ce8da036 100644
--- a/AK/Tests/TestTime.cpp
+++ b/AK/Tests/TestTime.cpp
@@ -227,10 +227,29 @@ TEST_CASE(rounding)
     EXPECT_EQ(TIME(0, 0).to_milliseconds(), 0);
     EXPECT_EQ(TIME(0, 0).to_microseconds(), 0);
     EXPECT_EQ(TIME(0, 0).to_nanoseconds(), 0);
+
+    EXPECT_EQ(TIME(0, 1).to_seconds(), 1);
+    EXPECT_EQ(TIME(0, 1).to_milliseconds(), 1);
+    EXPECT_EQ(TIME(0, 1).to_microseconds(), 1);
+    EXPECT_EQ(TIME(0, 1).to_nanoseconds(), 1);
+    EXPECT_EQ(TIME(0, -1).to_seconds(), -1);
+    EXPECT_EQ(TIME(0, -1).to_milliseconds(), -1);
+    EXPECT_EQ(TIME(0, -1).to_microseconds(), -1);
+    EXPECT_EQ(TIME(0, -1).to_nanoseconds(), -1);
+
+    EXPECT_EQ(TIME(-9223372037, 145'224'191).to_nanoseconds(), (i64)-0x8000'0000'0000'0000);
+    EXPECT_EQ(TIME(-9223372037, 145'224'192).to_nanoseconds(), (i64)-0x8000'0000'0000'0000);
+    EXPECT_EQ(TIME(-9223372037, 145'224'193).to_nanoseconds(), -0x7fff'ffff'ffff'ffff);
+    EXPECT_EQ(TIME(9223372036, 854'775'806).to_nanoseconds(), 0x7fff'ffff'ffff'fffe);
+    EXPECT_EQ(TIME(9223372036, 854'775'807).to_nanoseconds(), 0x7fff'ffff'ffff'ffff);
+    EXPECT_EQ(TIME(9223372036, 854'775'808).to_nanoseconds(), 0x7fff'ffff'ffff'ffff);
 }
 
 TEST_CASE(truncation)
 {
+    // Sanity
+    EXPECT_EQ(TIME(2, 0).to_truncated_seconds(), 2);
+    EXPECT_EQ(TIME(-2, 0).to_truncated_seconds(), -2);
     EXPECT_EQ(TIME(2, 800'800'800).to_truncated_seconds(), 2);
     EXPECT_EQ(TIME(2, 800'800'800).to_truncated_milliseconds(), 2'800);
     EXPECT_EQ(TIME(2, 800'800'800).to_truncated_microseconds(), 2'800'800);
@@ -238,13 +257,29 @@ TEST_CASE(truncation)
     EXPECT_EQ(TIME(-2, -800'800'800).to_truncated_milliseconds(), -2'800);
     EXPECT_EQ(TIME(-2, -800'800'800).to_truncated_microseconds(), -2'800'800);
 
-    EXPECT_EQ(TIME(0, 0).to_truncated_seconds(), 0);
-    EXPECT_EQ(TIME(1, 999'999'999).to_truncated_seconds(), 1);
-    EXPECT_EQ(TIME(1, 1'000'000'000).to_truncated_seconds(), 2);
-    EXPECT_EQ(TIME(-2, 0).to_truncated_seconds(), -2);
-
+    // Overflow, seconds
     EXPECT_EQ(Time::min().to_truncated_seconds(), (i64)-0x8000'0000'0000'0000);
     EXPECT_EQ(Time::max().to_truncated_seconds(), 0x7fff'ffff'ffff'ffff);
+
+    // Overflow, milliseconds
+    EXPECT_EQ(TIME(-9223372036854776, 191'000'000).to_truncated_milliseconds(), (i64)-0x8000'0000'0000'0000);
+    EXPECT_EQ(TIME(-9223372036854776, 192'000'000).to_truncated_milliseconds(), (i64)-0x8000'0000'0000'0000);
+    EXPECT_EQ(TIME(-9223372036854776, 192'000'001).to_truncated_milliseconds(), -0x7fff'ffff'ffff'ffff);
+    EXPECT_EQ(TIME(-9223372036854776, 193'000'000).to_truncated_milliseconds(), -0x7fff'ffff'ffff'ffff);
+    EXPECT_EQ(TIME(9223372036854775, 806'000'000).to_truncated_milliseconds(), 0x7fff'ffff'ffff'fffe);
+    EXPECT_EQ(TIME(9223372036854775, 806'999'999).to_truncated_milliseconds(), 0x7fff'ffff'ffff'fffe);
+    EXPECT_EQ(TIME(9223372036854775, 807'000'000).to_truncated_milliseconds(), 0x7fff'ffff'ffff'ffff);
+    EXPECT_EQ(TIME(9223372036854775, 808'000'000).to_truncated_milliseconds(), 0x7fff'ffff'ffff'ffff);
+
+    // Overflow, microseconds
+    EXPECT_EQ(TIME(-9223372036855, 224'191'000).to_truncated_microseconds(), (i64)-0x8000'0000'0000'0000);
+    EXPECT_EQ(TIME(-9223372036855, 224'192'000).to_truncated_microseconds(), (i64)-0x8000'0000'0000'0000);
+    EXPECT_EQ(TIME(-9223372036855, 224'192'001).to_truncated_microseconds(), (i64)-0x7fff'ffff'ffff'ffff);
+    EXPECT_EQ(TIME(-9223372036855, 224'193'000).to_truncated_microseconds(), (i64)-0x7fff'ffff'ffff'ffff);
+    EXPECT_EQ(TIME(9223372036854, 775'806'000).to_truncated_microseconds(), 0x7fff'ffff'ffff'fffe);
+    EXPECT_EQ(TIME(9223372036854, 775'806'999).to_truncated_microseconds(), 0x7fff'ffff'ffff'fffe);
+    EXPECT_EQ(TIME(9223372036854, 775'807'000).to_truncated_microseconds(), 0x7fff'ffff'ffff'ffff);
+    EXPECT_EQ(TIME(9223372036854, 775'808'000).to_truncated_microseconds(), 0x7fff'ffff'ffff'ffff);
 }
 
 TEST_MAIN(Time)
diff --git a/AK/Time.cpp b/AK/Time.cpp
index 3e2f2cd9a4..3eb2f7b36a 100644
--- a/AK/Time.cpp
+++ b/AK/Time.cpp
@@ -24,7 +24,6 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-#include <AK/Assertions.h>
 #include <AK/Checked.h>
 #include <AK/Time.h>
 
@@ -71,22 +70,6 @@ unsigned day_of_week(int year, unsigned month, int day)
     return (year + year / 4 - year / 100 + year / 400 + seek_table[month - 1] + day) % 7;
 }
 
-ALWAYS_INLINE static i32 sane_mod(i32& numerator, i32 denominator)
-{
-    VERIFY(2 <= denominator && denominator <= 1'000'000'000);
-    // '%' in C/C++ does not work in the obvious way:
-    // For example, -9 % 7 is -2, not +5.
-    // However, we want a representation like "(-2)*7 + (+5)".
-    i32 dividend = numerator / denominator;
-    numerator %= denominator;
-    if (numerator < 0) {
-        // Does not overflow: different signs.
-        numerator += denominator;
-        // Does not underflow: denominator >= 2.
-        dividend -= 1;
-    }
-    return dividend;
-}
 Time Time::from_timespec(const struct timespec& ts)
 {
     i32 nsecs = ts.tv_nsec;
@@ -105,48 +88,45 @@ i64 Time::to_truncated_seconds() const
 {
     VERIFY(m_nanoseconds < 1'000'000'000);
     if (m_seconds < 0 && m_nanoseconds) {
-        Checked<i64> seconds(m_seconds);
-        seconds++;
-        return seconds.has_overflow() ? 0x7fff'ffff'ffff'ffffLL : seconds.value();
+        // Since m_seconds is negative, adding 1 can't possibly overflow
+        return m_seconds + 1;
     }
     return m_seconds;
 }
 i64 Time::to_truncated_milliseconds() const
 {
     VERIFY(m_nanoseconds < 1'000'000'000);
-    Checked<i64> milliseconds(m_seconds);
+    Checked<i64> milliseconds((m_seconds < 0) ? m_seconds + 1 : m_seconds);
     milliseconds *= 1'000;
-    if (!milliseconds.has_overflow()) {
-        u32 add_ms = (u32)(m_nanoseconds / 1'000'000);
-        if (add_ms) {
-            milliseconds += add_ms;
-            if (m_seconds < 0 && m_nanoseconds % 1'000'000 != 0)
-                milliseconds++;
-            if (!milliseconds.has_overflow())
-                return milliseconds.value();
-        } else {
-            return milliseconds.value();
+    milliseconds += m_nanoseconds / 1'000'000;
+    if (m_seconds < 0) {
+        if (m_nanoseconds % 1'000'000 != 0) {
+            // Does not overflow: milliseconds <= 1'999.
+            milliseconds++;
         }
+        // We dropped one second previously, put it back in now that we have handled the rounding.
+        milliseconds -= 1'000;
     }
+    if (!milliseconds.has_overflow())
+        return milliseconds.value();
     return m_seconds < 0 ? -0x8000'0000'0000'0000LL : 0x7fff'ffff'ffff'ffffLL;
 }
 i64 Time::to_truncated_microseconds() const
 {
     VERIFY(m_nanoseconds < 1'000'000'000);
-    Checked<i64> microseconds(m_seconds);
+    Checked<i64> microseconds((m_seconds < 0) ? m_seconds + 1 : m_seconds);
     microseconds *= 1'000'000;
-    if (!microseconds.has_overflow()) {
-        u32 add_us = (u32)(m_nanoseconds / 1'000);
-        if (add_us) {
-            microseconds += add_us;
-            if (m_seconds < 0 && m_nanoseconds % 1'000 != 0)
-                microseconds++;
-            if (!microseconds.has_overflow())
-                return microseconds.value();
-        } else {
-            return microseconds.value();
+    microseconds += m_nanoseconds / 1'000;
+    if (m_seconds < 0) {
+        if (m_nanoseconds % 1'000 != 0) {
+            // Does not overflow: microseconds <= 1'999'999.
+            microseconds++;
         }
+        // We dropped one second previously, put it back in now that we have handled the rounding.
+        microseconds -= 1'000'000;
     }
+    if (!microseconds.has_overflow())
+        return microseconds.value();
     return m_seconds < 0 ? -0x8000'0000'0000'0000LL : 0x7fff'ffff'ffff'ffffLL;
 }
 i64 Time::to_seconds() const
@@ -162,64 +142,47 @@ i64 Time::to_seconds() const
 i64 Time::to_milliseconds() const
 {
     VERIFY(m_nanoseconds < 1'000'000'000);
-    Checked<i64> milliseconds(m_seconds);
+    Checked<i64> milliseconds((m_seconds < 0) ? m_seconds + 1 : m_seconds);
     milliseconds *= 1'000;
-    if (!milliseconds.has_overflow()) {
-        u32 add_ms = (u32)(m_nanoseconds / 1'000'000);
-        if (add_ms) {
-            milliseconds += add_ms;
-            if (!milliseconds.has_overflow()) {
-                if (m_seconds >= 0 && m_nanoseconds % 1'000'000 != 0) {
-                    milliseconds++;
-                    if (!milliseconds.has_overflow())
-                        return milliseconds.value();
-                } else {
-                    return milliseconds.value();
-                }
-            }
-        } else {
-            return milliseconds.value();
-        }
+    milliseconds += m_nanoseconds / 1'000'000;
+    if (m_seconds >= 0 && m_nanoseconds % 1'000'000 != 0)
+        milliseconds++;
+    if (m_seconds < 0) {
+        // We dropped one second previously, put it back in now that we have handled the rounding.
+        milliseconds -= 1'000;
     }
+    if (!milliseconds.has_overflow())
+        return milliseconds.value();
     return m_seconds < 0 ? -0x8000'0000'0000'0000LL : 0x7fff'ffff'ffff'ffffLL;
 }
 i64 Time::to_microseconds() const
 {
     VERIFY(m_nanoseconds < 1'000'000'000);
-    Checked<i64> microseconds(m_seconds);
+    Checked<i64> microseconds((m_seconds < 0) ? m_seconds + 1 : m_seconds);
     microseconds *= 1'000'000;
-    if (!microseconds.has_overflow()) {
-        u32 add_us = (u32)(m_nanoseconds / 1'000);
-        if (add_us) {
-            microseconds += add_us;
-            if (!microseconds.has_overflow()) {
-                if (m_seconds >= 0 && m_nanoseconds % 1'000 != 0) {
-                    microseconds++;
-                    if (!microseconds.has_overflow())
-                        return microseconds.value();
-                } else {
-                    return microseconds.value();
-                }
-            }
-        } else {
-            return microseconds.value();
-        }
+    microseconds += m_nanoseconds / 1'000;
+    if (m_seconds >= 0 && m_nanoseconds % 1'000 != 0)
+        microseconds++;
+    if (m_seconds < 0) {
+        // We dropped one second previously, put it back in now that we have handled the rounding.
+        microseconds -= 1'000'000;
     }
+    if (!microseconds.has_overflow())
+        return microseconds.value();
     return m_seconds < 0 ? -0x8000'0000'0000'0000LL : 0x7fff'ffff'ffff'ffffLL;
 }
 i64 Time::to_nanoseconds() const
 {
     VERIFY(m_nanoseconds < 1'000'000'000);
-    Checked<i64> nanoseconds(m_seconds);
+    Checked<i64> nanoseconds((m_seconds < 0) ? m_seconds + 1 : m_seconds);
     nanoseconds *= 1'000'000'000;
-    if (!nanoseconds.has_overflow()) {
-        if (m_nanoseconds) {
-            nanoseconds += m_nanoseconds;
-            if (!nanoseconds.has_overflow())
-                return nanoseconds.value();
-        }
-        return nanoseconds.value();
+    nanoseconds += m_nanoseconds;
+    if (m_seconds < 0) {
+        // We dropped one second previously, put it back in now that we have handled the rounding.
+        nanoseconds -= 1'000'000'000;
     }
+    if (!nanoseconds.has_overflow())
+        return nanoseconds.value();
     return m_seconds < 0 ? -0x8000'0000'0000'0000LL : 0x7fff'ffff'ffff'ffffLL;
 }
 timespec Time::to_timespec() const
diff --git a/AK/Time.h b/AK/Time.h
index e3ecb2724a..2f0410b3ba 100644
--- a/AK/Time.h
+++ b/AK/Time.h
@@ -26,6 +26,7 @@
 
 #pragma once
 
+#include <AK/Assertions.h>
 #include <AK/Platform.h>
 #include <AK/Types.h>
 
@@ -100,18 +101,51 @@ public:
         return *this;
     }
 
+private:
+    // This must be part of the header in order to make the various 'from_*' functions constexpr.
+    // However, sane_mod can only deal with a limited range of values for 'denominator', so this can't be made public.
+    ALWAYS_INLINE static constexpr i64 sane_mod(i64& numerator, i64 denominator)
+    {
+        VERIFY(2 <= denominator && denominator <= 1'000'000'000);
+        // '%' in C/C++ does not work in the obvious way:
+        // For example, -9 % 7 is -2, not +5.
+        // However, we want a representation like "(-2)*7 + (+5)".
+        i64 dividend = numerator / denominator;
+        numerator %= denominator;
+        if (numerator < 0) {
+            // Does not overflow: different signs.
+            numerator += denominator;
+            // Does not underflow: denominator >= 2.
+            dividend -= 1;
+        }
+        return dividend;
+    }
+    ALWAYS_INLINE static constexpr i32 sane_mod(i32& numerator, i32 denominator)
+    {
+        i64 numerator_64 = numerator;
+        i64 dividend = sane_mod(numerator_64, denominator);
+        // Does not underflow: numerator can only become smaller.
+        numerator = numerator_64;
+        // Does not overflow: Will be smaller than original value of 'numerator'.
+        return dividend;
+    }
+
+public:
     constexpr static Time from_seconds(i64 seconds) { return Time(seconds, 0); }
     constexpr static Time from_nanoseconds(i64 nanoseconds)
     {
-        return Time(nanoseconds / 1'000'000'000, nanoseconds % 1'000'000'000);
+        i64 seconds = sane_mod(nanoseconds, 1'000'000'000);
+        return Time(seconds, nanoseconds);
     }
     constexpr static Time from_microseconds(i64 microseconds)
     {
-        return Time(microseconds / 1'000'000, (microseconds % 1'000'000) * 1'000);
+        i64 seconds = sane_mod(microseconds, 1'000'000);
+        return Time(seconds, microseconds * 1'000);
     }
     constexpr static Time from_milliseconds(i64 milliseconds)
     {
-        return Time(milliseconds / 1'000, (milliseconds % 1'000) * 1'000'000);
+        i64 seconds = sane_mod(milliseconds, 1'000);
+        return Time(seconds, milliseconds * 1'000'000);
     }
     static Time from_timespec(const struct timespec&);
     static Time from_timeval(const struct timeval&);
@@ -119,16 +153,17 @@ public:
     static Time zero() { return Time(0, 0); };
     static Time max() { return Time(0x7fff'ffff'ffff'ffffLL, 999'999'999); };
 
-    // Truncates "2.8 seconds" to 2 seconds.
-    // Truncates "-2.8 seconds" to -2 seconds.
+    // Truncates towards zero (2.8s to 2s, -2.8s to -2s).
     i64 to_truncated_seconds() const;
     i64 to_truncated_milliseconds() const;
     i64 to_truncated_microseconds() const;
+    // Rounds away from zero (2.3s to 3s, -2.3s to -3s).
     i64 to_seconds() const;
     i64 to_milliseconds() const;
     i64 to_microseconds() const;
     i64 to_nanoseconds() const;
     timespec to_timespec() const;
+    // Rounds towards -inf (it was the easiest to implement).
     timeval to_timeval() const;
 
     bool is_zero() const { return !m_seconds && !m_nanoseconds; }