Compiler Explorer

Source code

using System.Buffers.Text;
using System.Diagnostics;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;

namespace System.Globalization
{
    internal static class TimeSpanParse
    {
        private const int MaxFractionDigits = 7;
        private const int MaxDays = 10675199;
        private const int MaxHours = 23;
        private const int MaxMinutes = 59;
        private const int MaxSeconds = 59;
        private const int MaxFraction = 9999999;

[Flags]
        private enum TimeSpanStandardStyles : byte
        {
            // Standard Format Styles
            None = 0x00000000,
            Invariant = 0x00000001, // Allow Invariant Culture
            Localized = 0x00000002, // Allow Localized Culture
            RequireFull = 0x00000004, // Require the input to be in DHMSF format
            Any = Invariant | Localized,
        }

// TimeSpan Token Types
        private enum TTT : byte
        {
            None = 0,         // None of the TimeSpanToken fields are set
            End = 1,          // '\0'
            Num = 2,          // Number
            Sep = 3,          // literal
            NumOverflow = 4,  // Number that overflowed
        }

private ref struct TimeSpanToken
        {
            internal TTT _ttt;
            internal int _num;                // Store the number that we are parsing (if any)
            internal int _zeroes;             // Store the number of leading zeroes (if any)
            internal ReadOnlySpan<char> _sep; // Store the literal that we are parsing (if any)

public TimeSpanToken(TTT type) : this(type, 0, 0, default) { }

public TimeSpanToken(int number) : this(TTT.Num, number, 0, default) { }

public TimeSpanToken(int number, int leadingZeroes) : this(TTT.Num, number, leadingZeroes, default) { }

public TimeSpanToken(TTT type, int number, int leadingZeroes, ReadOnlySpan<char> separator)
            {
                _ttt = type;
                _num = number;
                _zeroes = leadingZeroes;
                _sep = separator;
            }
            
            public bool NormalizeAndValidateFraction1()
            {
                Debug.Assert(_ttt == TTT.Num);
                Debug.Assert(_num > -1);

if (_num == 0)
                    return true;

if (_zeroes == 0 && _num > MaxFraction)
                    return false;

int totalDigitsCount = FormattingHelpers.CountDigits((uint)_num) + _zeroes;

if (totalDigitsCount == MaxFractionDigits)
                {
                    // Already normalized. no more action needed
                    // .9999999  normalize to 9,999,999 ticks
                    // .0000001  normalize to 1 ticks
                    return true;
                }

if (totalDigitsCount < MaxFractionDigits)
                {
                    // normalize the fraction to the 7-digits
                    // .999999  normalize to 9,999,990 ticks
                    // .99999   normalize to 9,999,900 ticks
                    // .000001  normalize to 10 ticks
                    // .1       normalize to 1,000,000 ticks

_num *= PowersOfTen[MaxFractionDigits - totalDigitsCount];
                    return true;
                }

// totalDigitsCount is greater then MaxFractionDigits, we'll need to do the rounding to 7-digits length
                // .00000001    normalized to 0 ticks
                // .00000005    normalized to 1 ticks
                // .09999999    normalize to 1,000,000 ticks
                // .099999999   normalize to 1,000,000 ticks

Debug.Assert(_zeroes > 0); // Already validated that in the condition _zeroes == 0 && _num > MaxFraction

if (_zeroes > MaxFractionDigits)
                {
                    // If there are 8 leading zeroes, it rounds to zero
                    _num = 0;
                    return true;
                }

Debug.Assert(totalDigitsCount - MaxFractionDigits <= MaxFractionDigits);
                uint power = (uint)Pow10UpToMaxFractionDigits(totalDigitsCount - MaxFractionDigits);
                _num = (int)(((uint)_num + power / 2) / power);
                Debug.Assert(_num < MaxFraction);

return true;
            }

public bool NormalizeAndValidateFraction0()
            {
                Debug.Assert(_ttt == TTT.Num);
                Debug.Assert(_num > -1);

if (_num == 0)
                    return true;

if (_zeroes == 0 && _num > MaxFraction)
                    return false;

int totalDigitsCount = FormattingHelpers.CountDigits((uint)_num) + _zeroes;

_num *= PowersOfTen[MaxFractionDigits - totalDigitsCount];
                    return true;
                }

Debug.Assert(_zeroes > 0); // Already validated that in the condition _zeroes == 0 && _num > MaxFraction

Debug.Assert(totalDigitsCount - MaxFractionDigits <= MaxFractionDigits);
                _num = (int)Math.Round((double)_num / Pow10UpToMaxFractionDigits(totalDigitsCount - MaxFractionDigits), MidpointRounding.AwayFromZero);
                Debug.Assert(_num < MaxFraction);

return true;
            }
        }
        
        static ReadOnlySpan<int> PowersOfTen =>
        [
            1,
            10,
            100,
            1000,
            10000,
            100000,
            1000000,
            10000000,
        ];

internal static int Pow10UpToMaxFractionDigits(int pow)
        {
            Debug.Assert(PowersOfTen.Length == MaxFractionDigits + 1);
            return PowersOfTen[pow];
        }
    }
    
    internal static partial class FormattingHelpers
    {
        // Based on do_count_digits from https://github.com/fmtlib/fmt/blob/662adf4f33346ba9aba8b072194e319869ede54a/include/fmt/format.h#L1124
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int CountDigits(ulong value)
        {
            // Map the log2(value) to a power of 10.
            ReadOnlySpan<byte> log2ToPow10 =
            [
                1,  1,  1,  2,  2,  2,  3,  3,  3,  4,  4,  4,  4,  5,  5,  5,
                6,  6,  6,  7,  7,  7,  7,  8,  8,  8,  9,  9,  9,  10, 10, 10,
                10, 11, 11, 11, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 15, 15,
                15, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 19, 19, 19, 20
            ];
            Debug.Assert(log2ToPow10.Length == 64);

// TODO: Replace with log2ToPow10[BitOperations.Log2(value)] once https://github.com/dotnet/runtime/issues/79257 is fixed
            nuint index = Unsafe.Add(ref MemoryMarshal.GetReference(log2ToPow10), BitOperations.Log2(value));

// Read the associated power of 10.
            ReadOnlySpan<ulong> powersOf10 =
            [
                0, // unused entry to avoid needing to subtract
                0,
                10,
                100,
                1000,
                10000,
                100000,
                1000000,
                10000000,
                100000000,
                1000000000,
                10000000000,
                100000000000,
                1000000000000,
                10000000000000,
                100000000000000,
                1000000000000000,
                10000000000000000,
                100000000000000000,
                1000000000000000000,
                10000000000000000000,
            ];
            Debug.Assert((index + 1) <= (uint)powersOf10.Length);
            ulong powerOf10 = Unsafe.Add(ref MemoryMarshal.GetReference(powersOf10), index);

// Return the number of digits based on the power of 10, shifted by 1
            // if it falls below the threshold.
            return (int)index - (value < powerOf10 ? 1 : 0);
        }

[MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int CountDigits(uint value)
        {
            // Algorithm based on https://lemire.me/blog/2021/06/03/computing-the-number-of-digits-of-an-integer-even-faster.
            ReadOnlySpan<long> table =
            [
                4294967296,
                8589934582,
                8589934582,
                8589934582,
                12884901788,
                12884901788,
                12884901788,
                17179868184,
                17179868184,
                17179868184,
                21474826480,
                21474826480,
                21474826480,
                21474826480,
                25769703776,
                25769703776,
                25769703776,
                30063771072,
                30063771072,
                30063771072,
                34349738368,
                34349738368,
                34349738368,
                34349738368,
                38554705664,
                38554705664,
                38554705664,
                41949672960,
                41949672960,
                41949672960,
                42949672960,
                42949672960,
            ];
            Debug.Assert(table.Length == 32, "Every result of uint.Log2(value) needs a long entry in the table.");

// TODO: Replace with table[uint.Log2(value)] once https://github.com/dotnet/runtime/issues/79257 is fixed
            long tableValue = Unsafe.Add(ref MemoryMarshal.GetReference(table), uint.Log2(value));
            return (int)((value + tableValue) >> 32);
        }

[MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int CountHexDigits(UInt128 value)
        {
            // The number of hex digits is log16(value) + 1, or log2(value) / 4 + 1
            return ((int)UInt128.Log2(value) >> 2) + 1;
        }

[MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int CountHexDigits(ulong value)
        {
            // The number of hex digits is log16(value) + 1, or log2(value) / 4 + 1
            return (BitOperations.Log2(value) >> 2) + 1;
        }

// Counts the number of trailing '0' digits in a decimal number.
        // e.g., value =      0 => retVal = 0, valueWithoutTrailingZeros = 0
        //       value =   1234 => retVal = 0, valueWithoutTrailingZeros = 1234
        //       value = 320900 => retVal = 2, valueWithoutTrailingZeros = 3209
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int CountDecimalTrailingZeros(uint value, out uint valueWithoutTrailingZeros)
        {
            int zeroCount = 0;

if (value != 0)
            {
                while (true)
                {
                    uint temp = value / 10;
                    if (value != (temp * 10))
                    {
                        break;
                    }

value = temp;
                    zeroCount++;
                }
            }

valueWithoutTrailingZeros = value;
            return zeroCount;
        }
    }
}