Compiler Explorer

Source code

typedef _Bool bool;
#define false 0
#define true 1

typedef unsigned char u8;
typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef i64 isize;
typedef float f32;

typedef struct {
    char const *data;
    isize size;
} StringView;
#define SV(string_literal) (StringView) {string_literal, sizeof(string_literal) - 1}

f32 string_to_f32(StringView);
bool string_is_float(StringView);

i32 main(void) {
    char const input[] = "1357.9341e-2";
    f32 expected = 1357.9341e-2F;

if (string_is_float(SV(input)) && string_to_f32(SV(input)) != expected) {
        return 1;
    }
}

#define ARRAY_SIZE(array) ((isize) (sizeof(array) / sizeof(array[0])))

bool sv_equals(StringView left_string, StringView right_string) {
    if (left_string.size != right_string.size) {
        return false;
    }

char const *left_string_iter = left_string.data;
    char const *right_string_iter = right_string.data;

while (left_string_iter < left_string.data + left_string.size) {
        if (*left_string_iter != *right_string_iter) {
            return false;
        }

left_string_iter += 1;
        right_string_iter += 1;
    }

return true;
}

static inline bool is_digit(char ch) {
    return '0' <= ch && ch <= '9';
}

bool string_is_i32(StringView source) {
    bool is_negative = false;

if (source.size == 0) {
        return false;
    }

if (source.data[0] == '-' && source.size == 1) {
        return false;
    }

StringView limit_unsigned;
    if (source.data[0] == '-') {
        limit_unsigned = SV("2147483648");
    } else {
        limit_unsigned = SV("2147483647");
    }

// Tolerate leading zeros
    StringView source_unsigned = {0};
    {
        char const *source_iter = source.data;
        if (*source_iter == '-') {
            source_iter += 1;
        }

while (source_iter < source.data + source.size - 1) {
            if (*source_iter != '0') {
                break;
            }

source_iter += 1;
        }

source_unsigned.data = source_iter;
        source_unsigned.size = source.data + source.size - source_iter;
    }

if (source_unsigned.size > limit_unsigned.size) {
        return false;
    }
    if (source_unsigned.size < limit_unsigned.size) {
        return true;
    }

char const *source_unsigned_iter = source_unsigned.data;
    char const *limit_unsigned_iter = limit_unsigned.data;
    while (source_unsigned_iter < source_unsigned.data + source_unsigned.size) {
        if (!is_digit(*source_unsigned_iter)) {
            return false;
        }

if (*source_unsigned_iter < *limit_unsigned_iter) {
            break;
        }
        if (*source_unsigned_iter > *limit_unsigned_iter) {
            return false;
        }

source_unsigned_iter += 1;
        limit_unsigned_iter += 1;
    }

return true;
}

i32 string_to_i32(StringView source) {
    if (source.size == 0) {
        return 0;
    }

char const *source_iter = source.data;

bool is_negative = false;
    if (*source_iter == '-') {
        is_negative = true;
        source_iter += 1;
    }

i64 absolute_value = 0;
    while (source_iter < source.data + source.size) {
        absolute_value = absolute_value * 10 + (*source_iter - '0');
        source_iter += 1;
    }

return (is_negative ? -1 : 1) * absolute_value;
}

bool string_is_float(StringView source) {
    if (source.size == 0) {
        return false;
    }

char const *source_iter = source.data;
    char const *source_end = source.data + source.size;

// Optional minus
    if (*source_iter == '-') {
        source_iter += 1;
    }

{
        StringView source_unsigned = {
            .data = source_iter,
            .size = source_end - source_iter,
        };
        if (sv_equals(source_unsigned, SV("inf")) || sv_equals(source_unsigned, SV("nan"))) {
            return true;
        }
    }

// Integral part
    if (source_iter == source_end || !is_digit(*source_iter)) {
        return false;
    }
    if (*source_iter == '0') {
        source_iter += 1;

if (source_iter < source_end && is_digit(*source_iter)) {
            return false;
        }
    } else {
        source_iter += 1;

while (source_iter < source_end && is_digit(*source_iter)) {
            source_iter += 1;
        }
    }

// Optional fractional part
    if (source_iter == source_end) {
        return true;
    }
    if (*source_iter == '.') {
        source_iter += 1;

// At least one digit in the fractional part
        if (source_iter == source_end) {
            return false;
        }

while (source_iter < source_end && is_digit(*source_iter)) {
            source_iter += 1;
        }
    }

// Optional exponent
    if (source_iter == source_end) {
        return true;
    }
    if (*source_iter == 'e' || *source_iter == 'E') {
        source_iter += 1;

if (source_iter == source_end) {
            return false;
        }
        if (*source_iter == '-' || *source_iter == '+') {
            source_iter += 1;
        }

if (source_iter == source_end) {
            return false;
        }

// Tolerate leading zeros (any sequence of digits is allowed)
        while (source_iter < source_end && is_digit(*source_iter)) {
            source_iter += 1;
        }
    }

return source_iter == source_end;
}

static inline f32 u32_as_f32(u32 u32_value) {
    f32 f32_value = 0.0F;

for (isize i = 0; i < 4; i += 1) {
        ((u8 *) &f32_value)[i] = ((u8 *) &u32_value)[i];
    }

return f32_value;
}

f32 string_to_f32(StringView source) {
    f32 const PLUS_INFINITY = u32_as_f32(0x7f800000);
    f32 const MINUS_INFINITY = u32_as_f32(0xff800000);

// Put different parts of the source into different string views in advance (assuming the source
    // contains a valid floating-point number)

bool is_negative = false;
    StringView source_integral = {0};
    StringView source_fractional = {0};
    StringView source_exponent = {0};

char const *source_iter = source.data;
    char const *source_end = source.data + source.size;

if (*source_iter == '-') {
        is_negative = true;
        source_iter += 1;
    }

// Handle speical values: "inf", "-inf", "nan"
    {
        StringView source_unsigned = {
            .data = source_iter,
            .size = source_end - source_iter,
        };
        if (sv_equals(source_unsigned, SV("inf"))) {
            if (is_negative) {
                return MINUS_INFINITY;
            } else {
                return PLUS_INFINITY;
            }
        }

if (sv_equals(source, SV("nan"))) {
            return u32_as_f32(0x7f800001);
        }
    }

source_integral.data = source_iter;
    while (source_iter < source_end) {
        if (*source_iter == '.') {
            break;
        }
        if (*source_iter == 'e' || *source_iter == 'E') {
            break;
        }

source_iter += 1;
    }
    source_integral.size = source_iter - source_integral.data;

if (source_iter < source_end && *source_iter == '.') {
        source_iter += 1;

source_fractional.data = source_iter;

while (source_iter < source_end) {
            if (*source_iter == 'e' || *source_iter == 'E') {
                break;
            }

source_iter += 1;
        }

source_fractional.size = source_iter - source_fractional.data;
    }

if (source_iter < source_end && (*source_iter == 'e' || *source_iter == 'E')) {
        source_iter += 1;

if (*source_iter == '+') {
            source_iter += 1;
        }

source_exponent.data = source_iter;
        source_exponent.size = source_end - source_exponent.data;
    }

// Read the decimal exponent to binary, return early in case it's obvioulsy too large / too
    // small

i32 decimal_exponent = 0;

if (source_exponent.size > 0) {
        if (!string_is_i32(source_exponent)) {
            if (source_exponent.data[0] == '-') {
                if (is_negative) {
                    return u32_as_f32(0x80000000);
                } else {
                    return 0.0F;
                }
            } else {
                if (is_negative) {
                    return MINUS_INFINITY;
                } else {
                    return PLUS_INFINITY;
                }
            }
        }

decimal_exponent = string_to_i32(source_exponent);
    }

// Read the integral part to binary (might need to partially read the fractional part as well
    // because of the positive decimal exponent)

char const *source_integral_iter = source_integral.data;
    char const *source_integral_end = source_integral.data + source_integral.size;

if (decimal_exponent < 0) {
        source_integral_end += decimal_exponent;
    }

char const *source_fractional_iter = source_fractional.data;
    char const *source_fractional_end = source_fractional.data + source_fractional.size;

// Max exponent = 127 => longest integral part = 2^127 => at least 128 bits needed
    // + at least 3 bits for the guard, round and sticky bits, this is why I went with 5 u32's
    u32 integral[5] = {0};

while (true) {
        if (source_integral_iter >= source_integral_end && decimal_exponent <= 0) {
            break;
        }

{
            u32 overflow = 0;

isize digit_index = ARRAY_SIZE(integral) - 1;

while (digit_index >= 0) {
                u64 product = (u64) 10 * integral[digit_index] + overflow;
                integral[digit_index] = (u32) product;
                overflow = (u32) (product >> 32);

digit_index -= 1;
            }

if (digit_index == -1 && overflow != 0) {
                if (is_negative) {
                    return MINUS_INFINITY;
                } else {
                    return PLUS_INFINITY;
                }
            }
        }

if (
            source_integral_iter < source_integral_end ||
            source_fractional_iter < source_fractional_end
        ) {
            u32 overflow;

if (source_integral_iter < source_integral_end) {
                overflow = *source_integral_iter - '0';
                source_integral_iter += 1;
            } else {
                overflow = *source_fractional_iter - '0';
                source_fractional_iter += 1;
                decimal_exponent -= 1;
            }

isize digit_index = ARRAY_SIZE(integral) - 1;

while (digit_index >= 0) {
                u64 sum = (u64) integral[digit_index] + overflow;
                integral[digit_index] = (u32) sum;
                overflow = (u32) (sum >> 32);

digit_index -= 1;
            }

if (digit_index == -1 && overflow != 0) {
                if (is_negative) {
                    return MINUS_INFINITY;
                } else {
                    return PLUS_INFINITY;
                }
            }
        } else {
            decimal_exponent -= 1;
        }
    }

// Read the fractional part to binary (might need to partially read the fractional part as well
    // because of the negative decimal exponent)

// Min exponent = -126 and min mantissa (denormal) = 1 (23 bits) => 126 + 23 = 149 bits needed
    // + at least 3 bits for the guard, round and sticky bits, this is why I went with 5 u32's
    u32 fractional[5] = {0};

if (decimal_exponent < 0 || source_fractional_iter < source_fractional_end) {
        // Min positive denormal float = 2^-149 ≅ 1.401 * 10^-45, so 50 digits should be enough and
        // we can ignore the rest of the decimal digits?

// The decimal point is assumed to be placed right after the first digit
        u8 decimal_fractional[50] = {0};

u8 *decimal_fractional_iter = decimal_fractional + 1;
        u8 *decimal_fractional_end = decimal_fractional + ARRAY_SIZE(decimal_fractional);

while (decimal_fractional_iter < decimal_fractional_end) {
            if (decimal_exponent < 0) {
                char const *borrowed_integral_digit =
                    source_integral.data + source_integral.size + decimal_exponent;

if (borrowed_integral_digit >= source_integral.data) {
                    *decimal_fractional_iter = *borrowed_integral_digit - '0';
                }

decimal_exponent += 1;
            } else if (source_fractional_iter < source_fractional_end) {
                *decimal_fractional_iter = *source_fractional_iter - '0';
                source_fractional_iter += 1;
            }

decimal_fractional_iter += 1;
        }

u32 *fractional_iter = fractional;
        u32 *fractional_end = fractional + ARRAY_SIZE(fractional);
        i32 fractional_bit_pos = 0;

while (fractional_iter < fractional_end) {
            u8 overflow = 0;
            u8 *decimal_fractional_iter = decimal_fractional + ARRAY_SIZE(decimal_fractional) - 1;

while (decimal_fractional_iter >= decimal_fractional) {
                u8 product = *decimal_fractional_iter * 2 + overflow;

*decimal_fractional_iter = (product % 10);
                overflow = product / 10;

decimal_fractional_iter -= 1;
            }

if (decimal_fractional[0] == 1) {
                decimal_fractional[0] = 0;
                *fractional_iter |= 1 << (31 - fractional_bit_pos);
            }

fractional_bit_pos += 1;
            if (fractional_bit_pos == 32) {
                fractional_bit_pos = 0;
                fractional_iter += 1;
            }
        }
    }

// Start assembling different parts of the floating-point number

i32 exponent = 0;

u32 mantissa = 0;
    i32 mantissa_bit_pos = 0;

bool integral_is_zero = true;
    bool fractional_is_zero = true;

u8 guard_bit;
    bool guard_bit_set = false;

u8 round_bit;
    bool round_bit_set = false;

u8 sticky_bit;
    bool sticky_bit_set = false;

// Process the integral part

u32 *integral_iter = integral;
    u32 *integral_end = integral + ARRAY_SIZE(integral);
    i32 integral_bit_pos = 0;

// Skip to the first "1" in the integral part

while (integral_iter < integral_end) {
        if (*integral_iter == 0) {
            integral_iter += 1;
            integral_bit_pos = 0;
            continue;
        }

u32 integral_bit = (*integral_iter & (1 << (31 - integral_bit_pos))) != 0 ? 1 : 0;

integral_bit_pos += 1;
        if (integral_bit_pos == 32) {
            integral_bit_pos = 0;
            integral_iter += 1;
        }

if (integral_bit == 1) {
            integral_is_zero = false;
            break;
        }
    }

// Fill mantissa with the bits from the integral part

while (integral_iter < integral_end) {
        u32 integral_bit = (*integral_iter & (1 << (31 - integral_bit_pos))) != 0 ? 1 : 0;

if (mantissa_bit_pos < 23) {
            mantissa |= integral_bit << (22 - mantissa_bit_pos);
            mantissa_bit_pos += 1;
        } else {
            if (!guard_bit_set) {
                guard_bit = integral_bit;
                guard_bit_set= true;
            } else if (!round_bit_set) {
                round_bit = integral_bit;
                round_bit_set = true;
            } else if (!sticky_bit_set || sticky_bit != 1) {
                sticky_bit = integral_bit;
                sticky_bit_set = true;
            }
        }

exponent += 1;
        if (exponent == 128) {
            if (is_negative) {
                return MINUS_INFINITY;
            } else {
                return PLUS_INFINITY;
            }
        }

integral_bit_pos += 1;
        if (integral_bit_pos == 32) {
            integral_bit_pos = 0;
            integral_iter += 1;
        }
    }

// Process the fractional part

u32 *fractional_iter = fractional;
    u32 *fractional_end = fractional + ARRAY_SIZE(fractional);
    i32 fractional_bit_pos = 0;

// Skip to the first "1" in the fractional part

if (integral_is_zero) {
        while (fractional_iter < fractional_end) {
            u32 fractional_bit =
                (*fractional_iter & (1 << (31 - fractional_bit_pos))) != 0 ? 1 : 0;

exponent -= 1;

// The float is subnormal
            if (exponent == -127) {
                break;
            }

fractional_bit_pos += 1;
            if (fractional_bit_pos == 32) {
                fractional_bit_pos = 0;
                fractional_iter += 1;
            }

if (fractional_bit == 1) {
                fractional_is_zero = false;
                break;
            }
        }
    }

// Fill mantissa with the bits from the fractional part

while (fractional_iter < fractional_end) {
        u32 fractional_bit =
            (*fractional_iter & (1 << (31 - fractional_bit_pos))) != 0 ? 1 : 0;

if (fractional_bit == 1) {
            fractional_is_zero = false;
        }

if (mantissa_bit_pos < 23) {
            mantissa |= fractional_bit << (22 - mantissa_bit_pos);
            mantissa_bit_pos += 1;
        } else {
            if (!guard_bit_set) {
                guard_bit = fractional_bit;
                guard_bit_set = true;
            } else if (!round_bit_set) {
                round_bit = fractional_bit;
                round_bit_set = true;
            } else if (!sticky_bit_set || sticky_bit != 1) {
                sticky_bit = fractional_bit;
                sticky_bit_set = true;
            }
        }

fractional_bit_pos += 1;
        if (fractional_bit_pos == 32) {
            fractional_bit_pos = 0;
            fractional_iter += 1;
        }
    }

// Rounding

guard_bit = guard_bit_set ? guard_bit : 0;
    round_bit = round_bit_set ? round_bit : 0;
    sticky_bit = sticky_bit_set ? sticky_bit : 0;

u32 raw_float = 0;
    if (is_negative) {
        raw_float |= 0x80000000;
    }
    if (!integral_is_zero || !fractional_is_zero) {
        raw_float |= ((u32) (exponent + 127) << 23);
    }
    raw_float |= mantissa & 0x007fffff;

if (guard_bit == 1) {
        if (round_bit == 1 || sticky_bit == 1) {
            raw_float += 1;
        } else if ((mantissa & 1) != 0) {
            raw_float &= ~((u32) 1);
        }
    }

return u32_as_f32(raw_float);
}