Skip to main content

proctor_libc/stdlib/
mod.rs

1//! Safe equivalents of functions declared in C's `stdlib.h` header.
2
3use num_bigint::BigUint;
4
5/// An integer conversion error.
6#[derive(Clone, Copy, Debug, Eq, PartialEq)]
7pub enum StrtoIntError {
8    /// The requested base is not supported.
9    InvalidBase,
10    /// The converted value is outside the range of the return type.
11    OutOfRange,
12}
13
14/// A floating-point conversion error.
15#[derive(Clone, Copy, Debug, Eq, PartialEq)]
16pub enum StrtoFloatError {
17    /// The converted value overflowed or underflowed the return type.
18    OutOfRange,
19}
20
21const F32_FORMAT: FloatFormat = FloatFormat {
22    precision: 24,
23    fraction_bits: 23,
24    exponent_bits: 8,
25    exponent_bias: 127,
26    minimum_exponent: -126,
27    maximum_exponent: 127,
28    minimum_decimal_order: -45,
29    maximum_decimal_order: 38,
30};
31const F64_FORMAT: FloatFormat = FloatFormat {
32    precision: 53,
33    fraction_bits: 52,
34    exponent_bits: 11,
35    exponent_bias: 1023,
36    minimum_exponent: -1022,
37    maximum_exponent: 1023,
38    minimum_decimal_order: -324,
39    maximum_decimal_order: 308,
40};
41const F128_FORMAT: FloatFormat = FloatFormat {
42    precision: 113,
43    fraction_bits: 112,
44    exponent_bits: 15,
45    exponent_bias: 16383,
46    minimum_exponent: -16382,
47    maximum_exponent: 16383,
48    minimum_decimal_order: -4966,
49    maximum_decimal_order: 4932,
50};
51
52#[derive(Clone, Copy)]
53struct FloatFormat {
54    precision: u32,
55    fraction_bits: u32,
56    exponent_bits: u32,
57    exponent_bias: i32,
58    minimum_exponent: i64,
59    maximum_exponent: i64,
60    minimum_decimal_order: i64,
61    maximum_decimal_order: i64,
62}
63
64enum FloatSubject {
65    None,
66    Infinity {
67        negative: bool,
68        end: usize,
69    },
70    Nan {
71        negative: bool,
72        end: usize,
73    },
74    Finite {
75        negative: bool,
76        digits: Vec<u8>,
77        scale: FloatScale,
78        end: usize,
79    },
80}
81
82enum FloatScale {
83    Decimal(i64),
84    Binary(i64),
85}
86
87struct Mantissa {
88    digits: Vec<u8>,
89    saw_digit: bool,
90    fraction_digits: usize,
91    trailing_zeros: usize,
92    end: usize,
93}
94
95/// Converts the initial floating-point number in `buf` to an `f64`.
96pub fn atof(buf: &[i8]) -> f64 {
97    strtod(buf).0.0
98}
99
100/// Converts the initial floating-point number in `buf` to an `f64`.
101///
102/// Returns the converted value, the unconsumed suffix, and the conversion
103/// status. `StrtoFloatError::OutOfRange` is the only error variant and reports
104/// overflow or inexact underflow.
105pub fn strtod(buf: &[i8]) -> ((f64, &[i8]), Result<(), StrtoFloatError>) {
106    let ((bits, suffix), status) = strto_float_bits(buf, F64_FORMAT);
107    ((f64::from_bits(bits as u64), suffix), status)
108}
109
110/// Converts the initial floating-point number in `buf` to an `f32`.
111///
112/// Returns the converted value, the unconsumed suffix, and the conversion
113/// status. `StrtoFloatError::OutOfRange` is the only error variant and reports
114/// overflow or inexact underflow.
115pub fn strtof(buf: &[i8]) -> ((f32, &[i8]), Result<(), StrtoFloatError>) {
116    let ((bits, suffix), status) = strto_float_bits(buf, F32_FORMAT);
117    ((f32::from_bits(bits as u32), suffix), status)
118}
119
120/// Converts the initial floating-point number in `buf` to [`struct@f128::f128`].
121///
122/// Returns the converted value, the unconsumed suffix, and the conversion
123/// status. `StrtoFloatError::OutOfRange` is the only error variant and reports
124/// overflow or inexact underflow.
125pub fn strtold(buf: &[i8]) -> ((f128::f128, &[i8]), Result<(), StrtoFloatError>) {
126    let ((bits, suffix), status) = strto_float_bits(buf, F128_FORMAT);
127    ((f128_from_bits(bits), suffix), status)
128}
129
130fn strto_float_bits(
131    buf: &[i8],
132    format: FloatFormat,
133) -> ((u128, &[i8]), Result<(), StrtoFloatError>) {
134    match scan_float_subject(buf) {
135        FloatSubject::None => ((0, buf), Ok(())),
136        FloatSubject::Infinity { negative, end } => {
137            ((infinity_bits(format, negative), &buf[end..]), Ok(()))
138        }
139        FloatSubject::Nan { negative, end } => ((nan_bits(format, negative), &buf[end..]), Ok(())),
140        FloatSubject::Finite {
141            negative,
142            digits,
143            scale,
144            end,
145        } => {
146            if digits.is_empty() {
147                return ((zero_bits(format, negative), &buf[end..]), Ok(()));
148            }
149
150            let (bits, out_of_range) = convert_finite_float(negative, &digits, scale, format);
151            let status = if out_of_range {
152                Err(StrtoFloatError::OutOfRange)
153            } else {
154                Ok(())
155            };
156            ((bits, &buf[end..]), status)
157        }
158    }
159}
160
161fn scan_float_subject(buf: &[i8]) -> FloatSubject {
162    let limit = buf.iter().position(|&byte| byte == 0).unwrap_or(buf.len());
163    let mut index = 0;
164    while index < limit && is_c_whitespace(buf[index]) {
165        index += 1;
166    }
167
168    let negative = match buf.get(index).copied() {
169        Some(byte) if byte == b'-' as i8 => {
170            index += 1;
171            true
172        }
173        Some(byte) if byte == b'+' as i8 => {
174            index += 1;
175            false
176        }
177        _ => false,
178    };
179    let number_start = index;
180
181    if starts_ignore_ascii_case(buf, index, limit, b"inf") {
182        index += 3;
183        if starts_ignore_ascii_case(buf, index, limit, b"inity") {
184            index += 5;
185        }
186        return FloatSubject::Infinity {
187            negative,
188            end: index,
189        };
190    }
191
192    if starts_ignore_ascii_case(buf, index, limit, b"nan") {
193        index += 3;
194        if buf.get(index).copied() == Some(b'(' as i8) {
195            let mut payload_end = index + 1;
196            while payload_end < limit && is_nan_character(buf[payload_end]) {
197                payload_end += 1;
198            }
199            if buf.get(payload_end).copied() == Some(b')' as i8) {
200                index = payload_end + 1;
201            }
202        }
203        return FloatSubject::Nan {
204            negative,
205            end: index,
206        };
207    }
208
209    if index + 2 <= limit
210        && buf.get(index).copied() == Some(b'0' as i8)
211        && matches!(buf.get(index + 1).copied(), Some(byte) if byte == b'x' as i8 || byte == b'X' as i8)
212    {
213        let mantissa = scan_mantissa(buf, index + 2, limit, 16);
214        if mantissa.saw_digit {
215            let (end, exponent) = scan_float_exponent(buf, mantissa.end, limit, b'p', b'P');
216            let scale = adjust_scale(
217                exponent,
218                mantissa.fraction_digits,
219                mantissa.trailing_zeros,
220                4,
221            );
222            return FloatSubject::Finite {
223                negative,
224                digits: mantissa.digits,
225                scale: FloatScale::Binary(scale),
226                end,
227            };
228        }
229    }
230
231    let mantissa = scan_mantissa(buf, number_start, limit, 10);
232    if !mantissa.saw_digit {
233        return FloatSubject::None;
234    }
235    let (end, exponent) = scan_float_exponent(buf, mantissa.end, limit, b'e', b'E');
236    FloatSubject::Finite {
237        negative,
238        digits: mantissa.digits,
239        scale: FloatScale::Decimal(adjust_scale(
240            exponent,
241            mantissa.fraction_digits,
242            mantissa.trailing_zeros,
243            1,
244        )),
245        end,
246    }
247}
248
249fn scan_mantissa(buf: &[i8], start: usize, limit: usize, radix: u32) -> Mantissa {
250    let mut digits = Vec::new();
251    let mut saw_digit = false;
252    let mut fraction_digits = 0;
253    let mut pending_zeros = 0;
254    let mut index = start;
255    let mut after_point = false;
256
257    while index < limit {
258        if !after_point && buf[index] == b'.' as i8 {
259            after_point = true;
260            index += 1;
261            continue;
262        }
263        let Some(digit) = digit_value(buf[index]).filter(|&digit| digit < radix) else {
264            break;
265        };
266        saw_digit = true;
267        if digit == 0 {
268            if !digits.is_empty() {
269                pending_zeros += 1;
270            }
271        } else {
272            digits.extend(std::iter::repeat_n(0, pending_zeros));
273            pending_zeros = 0;
274            digits.push(digit as u8);
275        }
276        if after_point {
277            fraction_digits += 1;
278        }
279        index += 1;
280    }
281
282    Mantissa {
283        digits,
284        saw_digit,
285        fraction_digits,
286        trailing_zeros: pending_zeros,
287        end: index,
288    }
289}
290
291fn scan_float_exponent(
292    buf: &[i8],
293    marker: usize,
294    limit: usize,
295    lower: u8,
296    upper: u8,
297) -> (usize, i64) {
298    if marker >= limit || !matches!(buf[marker] as u8, byte if byte == lower || byte == upper) {
299        return (marker, 0);
300    }
301
302    let mut index = marker + 1;
303    let negative = match buf.get(index).copied() {
304        Some(byte) if byte == b'-' as i8 => {
305            index += 1;
306            true
307        }
308        Some(byte) if byte == b'+' as i8 => {
309            index += 1;
310            false
311        }
312        _ => false,
313    };
314    let first_digit = index;
315    let mut exponent = 0_i64;
316    while index < limit {
317        let byte = buf[index] as u8;
318        if !byte.is_ascii_digit() {
319            break;
320        }
321        exponent = exponent
322            .saturating_mul(10)
323            .saturating_add(i64::from(byte - b'0'));
324        index += 1;
325    }
326    if index == first_digit {
327        return (marker, 0);
328    }
329    if negative {
330        exponent = -exponent;
331    }
332    (index, exponent)
333}
334
335fn convert_finite_float(
336    negative: bool,
337    digits: &[u8],
338    scale: FloatScale,
339    format: FloatFormat,
340) -> (u128, bool) {
341    let (numerator, denominator, binary_exponent) = match scale {
342        FloatScale::Decimal(decimal_exponent) => {
343            let decimal_order = usize_to_i64(digits.len())
344                .saturating_sub(1)
345                .saturating_add(decimal_exponent);
346            if decimal_order > format.maximum_decimal_order {
347                return (infinity_bits(format, negative), true);
348            }
349            if decimal_order < format.minimum_decimal_order.saturating_sub(1) {
350                return (zero_bits(format, negative), true);
351            }
352
353            let significand = BigUint::from_radix_be(digits, 10).expect("decimal digits are valid");
354            if decimal_exponent >= 0 {
355                let five = BigUint::from(5_u8).pow(decimal_exponent as u32);
356                (significand * five, BigUint::from(1_u8), decimal_exponent)
357            } else {
358                let magnitude = decimal_exponent.unsigned_abs() as u32;
359                (
360                    significand,
361                    BigUint::from(5_u8).pow(magnitude),
362                    decimal_exponent,
363                )
364            }
365        }
366        FloatScale::Binary(binary_exponent) => {
367            let leading_digit_exponent = i64::from(7 - digits[0].leading_zeros());
368            let exponent = usize_to_i64(digits.len().saturating_sub(1))
369                .saturating_mul(4)
370                .saturating_add(leading_digit_exponent)
371                .saturating_add(binary_exponent);
372            let minimum_subnormal_exponent =
373                format.minimum_exponent - i64::from(format.precision - 1);
374            if exponent > format.maximum_exponent {
375                return (infinity_bits(format, negative), true);
376            }
377            if exponent < minimum_subnormal_exponent - 1 {
378                return (zero_bits(format, negative), true);
379            }
380
381            (
382                BigUint::from_radix_be(digits, 16).expect("hexadecimal digits are valid"),
383                BigUint::from(1_u8),
384                binary_exponent,
385            )
386        }
387    };
388
389    encode_ratio(negative, &numerator, &denominator, binary_exponent, format)
390}
391
392fn encode_ratio(
393    negative: bool,
394    numerator: &BigUint,
395    denominator: &BigUint,
396    binary_exponent: i64,
397    format: FloatFormat,
398) -> (u128, bool) {
399    let ratio_exponent = floor_log2_ratio(numerator, denominator);
400    let mut exponent = ratio_exponent.saturating_add(binary_exponent);
401    let minimum_subnormal_exponent = format.minimum_exponent - i64::from(format.precision - 1);
402
403    if exponent >= format.minimum_exponent {
404        let shift = i64::from(format.precision - 1) - ratio_exponent;
405        let (mut significand, _) = round_ratio(numerator, denominator, shift);
406        if significand.bits() > u64::from(format.precision) {
407            significand >>= 1_usize;
408            exponent += 1;
409        }
410        if exponent > format.maximum_exponent {
411            return (infinity_bits(format, negative), true);
412        }
413
414        let significand = biguint_to_u128(&significand);
415        let implicit_bit = 1_u128 << (format.precision - 1);
416        let exponent_field = (exponent + i64::from(format.exponent_bias)) as u128;
417        let bits = sign_bits(format, negative)
418            | (exponent_field << format.fraction_bits)
419            | (significand - implicit_bit);
420        return (bits, false);
421    }
422
423    let shift = binary_exponent.saturating_sub(minimum_subnormal_exponent);
424    let (significand, inexact) = round_ratio(numerator, denominator, shift);
425    let significand = biguint_to_u128(&significand);
426    let minimum_normal_significand = 1_u128 << (format.precision - 1);
427    if significand >= minimum_normal_significand {
428        let bits = sign_bits(format, negative) | (1_u128 << format.fraction_bits);
429        return (bits, inexact);
430    }
431
432    (sign_bits(format, negative) | significand, inexact)
433}
434
435fn floor_log2_ratio(numerator: &BigUint, denominator: &BigUint) -> i64 {
436    let exponent = (numerator.bits() as i64) - (denominator.bits() as i64);
437    let below_power = if exponent >= 0 {
438        numerator < &(denominator << exponent as usize)
439    } else {
440        &(numerator << exponent.unsigned_abs() as usize) < denominator
441    };
442    if below_power { exponent - 1 } else { exponent }
443}
444
445fn round_ratio(numerator: &BigUint, denominator: &BigUint, shift: i64) -> (BigUint, bool) {
446    let (scaled_numerator, scaled_denominator) = if shift >= 0 {
447        (numerator << shift as usize, denominator.clone())
448    } else {
449        (
450            numerator.clone(),
451            denominator << shift.unsigned_abs() as usize,
452        )
453    };
454    let mut quotient = &scaled_numerator / &scaled_denominator;
455    let remainder = &scaled_numerator % &scaled_denominator;
456    let inexact = remainder.bits() != 0;
457    let doubled_remainder = &remainder << 1_usize;
458    if doubled_remainder > scaled_denominator
459        || (doubled_remainder == scaled_denominator && quotient.bit(0))
460    {
461        quotient += 1_u8;
462    }
463    (quotient, inexact)
464}
465
466fn biguint_to_u128(value: &BigUint) -> u128 {
467    let digits = value.to_u64_digits();
468    u128::from(digits.first().copied().unwrap_or(0))
469        | (u128::from(digits.get(1).copied().unwrap_or(0)) << 64)
470}
471
472fn zero_bits(format: FloatFormat, negative: bool) -> u128 {
473    sign_bits(format, negative)
474}
475
476fn infinity_bits(format: FloatFormat, negative: bool) -> u128 {
477    sign_bits(format, negative) | (maximum_exponent_field(format) << format.fraction_bits)
478}
479
480fn nan_bits(format: FloatFormat, negative: bool) -> u128 {
481    infinity_bits(format, negative) | (1_u128 << (format.fraction_bits - 1))
482}
483
484fn sign_bits(format: FloatFormat, negative: bool) -> u128 {
485    u128::from(negative) << (format.fraction_bits + format.exponent_bits)
486}
487
488fn maximum_exponent_field(format: FloatFormat) -> u128 {
489    (1_u128 << format.exponent_bits) - 1
490}
491
492fn f128_from_bits(bits: u128) -> f128::f128 {
493    // SAFETY: `f128::f128` is a `repr(C)` wrapper around `[u8; 16]`, and all
494    // IEEE binary128 bit patterns are valid values of that type.
495    unsafe { std::mem::transmute(bits.to_ne_bytes()) }
496}
497
498fn starts_ignore_ascii_case(buf: &[i8], start: usize, limit: usize, expected: &[u8]) -> bool {
499    start + expected.len() <= limit
500        && buf[start..start + expected.len()]
501            .iter()
502            .zip(expected)
503            .all(|(&actual, &expected)| (actual as u8).eq_ignore_ascii_case(&expected))
504}
505
506fn is_nan_character(byte: i8) -> bool {
507    matches!(byte as u8, b'0'..=b'9' | b'a'..=b'z' | b'A'..=b'Z' | b'_')
508}
509
510fn usize_to_i64(value: usize) -> i64 {
511    i64::try_from(value).unwrap_or(i64::MAX)
512}
513
514fn adjust_scale(
515    exponent: i64,
516    fractional_digits: usize,
517    trailing_zeros: usize,
518    radix_bits: i64,
519) -> i64 {
520    if fractional_digits >= trailing_zeros {
521        let adjustment =
522            usize_to_i64(fractional_digits - trailing_zeros).saturating_mul(radix_bits);
523        exponent.saturating_sub(adjustment)
524    } else {
525        let adjustment =
526            usize_to_i64(trailing_zeros - fractional_digits).saturating_mul(radix_bits);
527        exponent.saturating_add(adjustment)
528    }
529}
530
531enum IntegerSubject {
532    None,
533    Digits {
534        negative: bool,
535        radix: u32,
536        start: usize,
537    },
538}
539
540struct IntegerMagnitude {
541    magnitude: u64,
542    end: usize,
543    out_of_range: bool,
544}
545
546/// Converts the initial decimal integer in `buf` to an `i32`.
547pub fn atoi(buf: &[i8]) -> i32 {
548    strtol(buf, 10).0.0 as i32
549}
550
551/// Converts the initial decimal integer in `buf` to an `i64`.
552pub fn atol(buf: &[i8]) -> i64 {
553    strtol(buf, 10).0.0
554}
555
556/// Converts the initial integer in `buf` using `base`.
557///
558/// Returns the converted value, the unconsumed suffix, and the conversion
559/// status. `StrtoIntError::InvalidBase` and `StrtoIntError::OutOfRange` are the
560/// only error variants; they report an unsupported base and overflow,
561/// respectively.
562pub fn strtol(buf: &[i8], base: i32) -> ((i64, &[i8]), Result<(), StrtoIntError>) {
563    let subject = match scan_integer_subject(buf, base) {
564        Ok(subject) => subject,
565        Err(error) => return ((0, buf), Err(error)),
566    };
567    let IntegerSubject::Digits {
568        negative,
569        radix,
570        start,
571    } = subject
572    else {
573        return ((0, buf), Ok(()));
574    };
575    let limit = if negative {
576        i64::MAX as u64 + 1
577    } else {
578        i64::MAX as u64
579    };
580    let conversion = convert_integer_magnitude(buf, start, radix, limit);
581
582    if conversion.out_of_range {
583        let value = if negative { i64::MIN } else { i64::MAX };
584        return (
585            (value, &buf[conversion.end..]),
586            Err(StrtoIntError::OutOfRange),
587        );
588    }
589
590    let value = if negative {
591        if conversion.magnitude == i64::MAX as u64 + 1 {
592            i64::MIN
593        } else {
594            -(conversion.magnitude as i64)
595        }
596    } else {
597        conversion.magnitude as i64
598    };
599
600    ((value, &buf[conversion.end..]), Ok(()))
601}
602
603/// Converts the initial unsigned integer in `buf` using `base`.
604///
605/// Returns the converted value, the unconsumed suffix, and the conversion
606/// status. `StrtoIntError::InvalidBase` and `StrtoIntError::OutOfRange` are the
607/// only error variants; they report an unsupported base and overflow,
608/// respectively.
609pub fn strtoul(buf: &[i8], base: i32) -> ((u64, &[i8]), Result<(), StrtoIntError>) {
610    let subject = match scan_integer_subject(buf, base) {
611        Ok(subject) => subject,
612        Err(error) => return ((0, buf), Err(error)),
613    };
614    let IntegerSubject::Digits {
615        negative,
616        radix,
617        start,
618    } = subject
619    else {
620        return ((0, buf), Ok(()));
621    };
622    let conversion = convert_integer_magnitude(buf, start, radix, u64::MAX);
623
624    if conversion.out_of_range {
625        return (
626            (u64::MAX, &buf[conversion.end..]),
627            Err(StrtoIntError::OutOfRange),
628        );
629    }
630
631    let value = if negative {
632        0_u64.wrapping_sub(conversion.magnitude)
633    } else {
634        conversion.magnitude
635    };
636
637    ((value, &buf[conversion.end..]), Ok(()))
638}
639
640fn scan_integer_subject(buf: &[i8], base: i32) -> Result<IntegerSubject, StrtoIntError> {
641    if base != 0 && !(2..=36).contains(&base) {
642        return Err(StrtoIntError::InvalidBase);
643    }
644
645    let mut index = 0;
646    while index < buf.len() && is_c_whitespace(buf[index]) {
647        index += 1;
648    }
649
650    let negative = match buf.get(index).copied() {
651        Some(byte) if byte == b'-' as i8 => {
652            index += 1;
653            true
654        }
655        Some(byte) if byte == b'+' as i8 => {
656            index += 1;
657            false
658        }
659        _ => false,
660    };
661
662    let radix = if base == 0 {
663        if has_hex_prefix(buf, index) {
664            index += 2;
665            16
666        } else if buf.get(index).copied() == Some(b'0' as i8) {
667            8
668        } else {
669            10
670        }
671    } else {
672        let radix = base as u32;
673        if radix == 16 && has_hex_prefix(buf, index) {
674            index += 2;
675        }
676        radix
677    };
678
679    if !matches!(buf.get(index).copied().and_then(digit_value), Some(digit) if digit < radix) {
680        return Ok(IntegerSubject::None);
681    }
682
683    Ok(IntegerSubject::Digits {
684        negative,
685        radix,
686        start: index,
687    })
688}
689
690fn convert_integer_magnitude(buf: &[i8], start: usize, radix: u32, limit: u64) -> IntegerMagnitude {
691    let cutoff = limit / u64::from(radix);
692    let cutlim = limit % u64::from(radix);
693    let mut magnitude = 0_u64;
694    let mut out_of_range = false;
695    let mut index = start;
696
697    while let Some(digit) = buf.get(index).copied().and_then(digit_value) {
698        if digit >= radix {
699            break;
700        }
701
702        if !out_of_range {
703            let digit = u64::from(digit);
704            if magnitude > cutoff || (magnitude == cutoff && digit > cutlim) {
705                out_of_range = true;
706            } else {
707                magnitude = magnitude * u64::from(radix) + digit;
708            }
709        }
710        index += 1;
711    }
712
713    IntegerMagnitude {
714        magnitude,
715        end: index,
716        out_of_range,
717    }
718}
719
720fn is_c_whitespace(byte: i8) -> bool {
721    matches!(byte as u8, b' ' | b'\t' | b'\n' | b'\x0b' | b'\x0c' | b'\r')
722}
723
724fn has_hex_prefix(buf: &[i8], index: usize) -> bool {
725    buf.get(index).copied() == Some(b'0' as i8)
726        && matches!(buf.get(index + 1).copied(), Some(byte) if byte == b'x' as i8 || byte == b'X' as i8)
727        && matches!(
728            buf.get(index + 2).copied().and_then(digit_value),
729            Some(0..=15)
730        )
731}
732
733fn digit_value(byte: i8) -> Option<u32> {
734    match byte as u8 {
735        byte @ b'0'..=b'9' => Some(u32::from(byte - b'0')),
736        byte @ b'a'..=b'z' => Some(u32::from(byte - b'a') + 10),
737        byte @ b'A'..=b'Z' => Some(u32::from(byte - b'A') + 10),
738        _ => None,
739    }
740}
741
742#[cfg(test)]
743mod tests;