[m-rev.] for review: implement fast path string to int and uint conversion
Julien Fischer
jfischer at opturion.com
Sat Sep 12 22:27:44 AEST 2026
For review by anyone.
----------------------------------------
Implement fast path string to int and uint conversion.
When converting strings to ints we can omit the overflow check when we know
that the number of digits in the string is small enough that overflow cannot
occur. Since conversion begins by computing the length of the string, we have
a bound on the number of digits ready to hand. Change base_string_to_int/3 to
check whether the number of digits is below the safe limit, and if it is, to
use a conversion that omits the overflow check.
The safe digit limit depends on both the base and the word size. For a base
B and word size W, it is the largest number of digits D such that every
string of D base B digits denotes a value that is representable, i.e. the
largest D such that B^D - 1 =< 2^(W-1) - 1 (max_int). We provide two tables
of safe digit limits, one for each word size.
We use the limit derived from max_int for negative values as well. The bound
that applies there is the magnitude of min_int, i.e. max_int + 1, which is
larger, so the limit derived from it can only be the same or larger than the
one we use. Borrowing the max_int limit is therefore never unsafe: at worst
it would send a string to the checked path that the fast path could have
handled. As it happens it does not even do that, since the two limits are the
same for every base from 2 to 36 at both word sizes.
Implement the same fast path approach for string to uint conversion. The safe
digit limit tables, likewise one per word size, are not the same as for int,
since the bound is max_uint rather than max_int: in base 10 with 64-bit words,
for example, 19 digits are safe for a uint but only 18 are safe for an int.
Using the benchmark program added by this change, in asm_fast.gc, shows a speed
up of ~11% over the existing implementation for converting 1 million randomly
generated decimal strings of between 1 and 31 digits. For 1 million randomly
generated decimal strings of between 1 and 6 digits (i.e. where all the strings
are below the safe limit), the speed up is ~25%.
library/string.m:
Add the fast path conversions described above.
benchmarks/prog/string_to_integer/benchmark_string_to_int.m:
Add the program for benchmarking base_string_to_int/3.
tests/general/test_string_to_int_overflow.m:
tests/general/test_string_to_int_overflow.exp*:
tests/hard_coded/string_to_uint_overflow.m:
tests/hard_coded/string_to_uint_overflow.exp*:
Add some tests at the boundary between the fast and checked paths.
tests/hard_coded/Mmakefile:
tests/hard_coded/base_string_to_int_bases.{m,exp}:
tests/hard_coded/base_string_to_uint_bases.{m,exp}:
Add a more systematic word-size-independent test of the boundary
between the fast and checked paths.
Julien.
diff --git a/benchmarks/progs/string_to_integer/benchmark_string_to_int.m
b/benchmarks/progs/string_to_integer/benchmark_string_to_int.m
new file mode 100644
index 000000000..8c5c158dd
--- /dev/null
+++ b/benchmarks/progs/string_to_integer/benchmark_string_to_int.m
@@ -0,0 +1,466 @@
+%---------------------------------------------------------------------------%
+% vim: ts=4 sw=4 et ft=mercury
+%---------------------------------------------------------------------------%
+%
+% Benchmarking harness of string.base_string_to_int/3.
+%
+% TODO: add options for controlling leading zeros.
+%
+%---------------------------------------------------------------------------%
+
+:- module benchmark_string_to_int.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is cc_multi.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module benchmarking.
+:- import_module bool.
+:- import_module char.
+:- import_module cord.
+:- import_module getopt.
+:- import_module int.
+:- import_module list.
+:- import_module maybe.
+:- import_module random.
+:- import_module random.system_rng.
+:- import_module random.sfc32.
+:- import_module string.
+:- import_module uint.
+:- import_module uint32.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+ io.command_line_arguments(Args, !IO),
+ OptionOps = option_ops_multi(
+ short_option,
+ long_option,
+ option_default
+ ),
+ getopt.process_options(OptionOps, Args, NonOptionArgs, OptionResult),
+ (
+ OptionResult = ok(OptionTable),
+ ( if getopt.lookup_bool_option(OptionTable, help, yes) then
+ print_help_message(!IO)
+ else
+ (
+ NonOptionArgs = [],
+ handle_options_and_run_benchmark(OptionTable, !IO)
+ ;
+ NonOptionArgs = [_ | _],
+ print_usage_error(!IO)
+ )
+ )
+ ;
+ OptionResult = error(Error),
+ print_option_error(Error, !IO)
+ ).
+
+:- pred handle_options_and_run_benchmark(option_table(option)::in,
+ io::di, io::uo) is cc_multi.
+
+handle_options_and_run_benchmark(OptionTable, !IO) :-
+ handle_options(OptionTable, SeedA, SeedB, SeedC, Base,
+ MinDigits, MaxDigits, NumTestCases, Repeats, cord.init, Errors, !IO),
+ ( if cord.is_empty(Errors) then
+ run_benchmark(SeedA, SeedB, SeedC, Base, MinDigits, MaxDigits,
+ NumTestCases, Repeats, !IO)
+ else
+ print_errors(Errors, !IO)
+ ).
+
+:- pred handle_options(option_table(option)::in,
+ uint32::out, uint32::out, uint32::out, int::out, uint::out,
+ uint::out, uint::out, int::out,
+ cord(string)::in, cord(string)::out,
+ io::di, io::uo) is det.
+
+handle_options(OptionTable, SeedA, SeedB, SeedC, Base,
+ MinDigits, MaxDigits, NumTestCases, Repeats, !Errors, !IO) :-
+ getopt.lookup_int_option(OptionTable, base, OptBase),
+ ( if OptBase >= 2, OptBase =< 36 then
+ Base = OptBase
+ else
+ string.format("invalid value for option '--base': %d.",
+ [i(OptBase)], InvalidBaseError),
+ cord.snoc(InvalidBaseError, !Errors),
+ Base = 0 % Dummy value.
+ ),
+ getopt.lookup_int_option(OptionTable, minimum_digits,
+ OptMinDigits),
+ ( if
+ uint.from_int(OptMinDigits, MinDigits0),
+ MinDigits0 > 0u
+ then
+ MinDigits = MinDigits0
+ else
+ InvalidMinDigitsError =
+ "invalid value for option '--minimum-digits'.",
+ cord.snoc(InvalidMinDigitsError, !Errors),
+ MinDigits = 0u % Dummy value.
+ ),
+ getopt.lookup_int_option(OptionTable, maximum_digits,
+ OptMaxDigits),
+ ( if
+ uint.from_int(OptMaxDigits, MaxDigits0),
+ MaxDigits0 > 0u
+ then
+ MaxDigits = MaxDigits0
+ else
+ InvalidMaxDigitsError =
+ "invalid value for option '--maximum-digits'.",
+ cord.snoc(InvalidMaxDigitsError, !Errors),
+ MaxDigits = 0u % Dummy value.
+ ),
+ ( if MinDigits > MaxDigits then
+ string.format("--minimum-digits=%u > --maximum-digits=%u.",
+ [u(MinDigits), u(MaxDigits)], MinMaxDigitsOverlapError),
+ cord.snoc(MinMaxDigitsOverlapError, !Errors)
+ else
+ true
+ ),
+ getopt.lookup_int_option(OptionTable, num_test_cases, OptNumTestCases),
+ ( if
+ uint.from_int(OptNumTestCases, NumTestCases0),
+ NumTestCases0 > 0u
+ then
+ NumTestCases = NumTestCases0
+ else
+ InvalidNumTestCasesError =
+ "invalid value for option '--num-test-cases'.",
+ cord.snoc(InvalidNumTestCasesError, !Errors),
+ NumTestCases = 0u % Dummy value.
+ ),
+ getopt.lookup_int_option(OptionTable, num_repeats, OptRepeats),
+ ( if
+ OptRepeats < 1
+ then
+ InvalidRepeatsError =
+ "value of option '--repeats' is less than one.",
+ cord.snoc(InvalidRepeatsError, !Errors),
+ Repeats = 0 % Dummy value.
+ else
+ Repeats = OptRepeats
+ ),
+ getopt.lookup_maybe_int_option(OptionTable, seed_a, MaybeSeedA),
+ getopt.lookup_maybe_int_option(OptionTable, seed_b, MaybeSeedB),
+ getopt.lookup_maybe_int_option(OptionTable, seed_c, MaybeSeedC),
+ ( if
+ MaybeSeedA = yes(OptSeedA),
+ MaybeSeedB = yes(OptSeedB),
+ MaybeSeedC = yes(OptSeedC)
+ then
+ ( if
+ uint32.from_int(OptSeedA, SeedA0),
+ uint32.from_int(OptSeedB, SeedB0),
+ uint32.from_int(OptSeedC, SeedC0)
+ then
+ SeedA = SeedA0,
+ SeedB = SeedB0,
+ SeedC = SeedC0
+ else
+ InvalidSeedsError =
+ "invalid value for one or more '--seed-' options.",
+ cord.snoc(InvalidSeedsError, !Errors),
+ SeedA = 0u32,
+ SeedB = 0u32,
+ SeedC = 0u32
+ )
+ else if
+ MaybeSeedA = no,
+ MaybeSeedB = no,
+ MaybeSeedC = no
+ then
+ make_random_seeds(SeedA, SeedB, SeedC, !Errors, !IO)
+ else
+ MixedSeedSourceError = "Either all or none of " ++
+ "'--seed-a', '--seed-b' and '--seed-c' must be specified.",
+ cord.snoc(MixedSeedSourceError, !Errors),
+ SeedA = 0u32, % Dummy value.
+ SeedB = 0u32, % Dummy value.
+ SeedC = 0u32 % Dummy value.
+ ).
+
+:- pred make_random_seeds(uint32::out, uint32::out, uint32::out,
+ cord(string)::in, cord(string)::out, io::di, io::uo) is det.
+
+make_random_seeds(SeedA, SeedB, SeedC, !Errors, !IO) :-
+ system_rng.open_system_rng(MaybeRNG, !IO),
+ (
+ MaybeRNG = ok(RNG),
+ system_rng.generate_uint32(RNG, SeedA, !IO),
+ system_rng.generate_uint32(RNG, SeedB, !IO),
+ system_rng.generate_uint32(RNG, SeedC, !IO),
+ close_system_rng(RNG, !IO)
+ ;
+ MaybeRNG = error(Error),
+ cord.snoc(Error, !Errors),
+ SeedA = 0u32, % Dummy value.
+ SeedB = 0u32, % Dummy value.
+ SeedC = 0u32 % Dummy value.
+ ).
+
+:- pred run_benchmark(uint32::in, uint32::in, uint32::in, int::in,
+ uint::in, uint::in, uint::in, int::in, io::di, io::uo) is cc_multi.
+
+run_benchmark(SeedA, SeedB, SeedC, Base, MinDigits, MaxDigits, NumTestCases,
+ Repeats, !IO) :-
+ random.sfc32.seed(SeedA, SeedB, SeedC, RNG, State),
+ make_io_urandom(RNG, State, IO_RNG, !IO),
+ make_test_cases(IO_RNG, Base, NumTestCases, MinDigits, MaxDigits,
+ TestCases, !IO),
+ benchmark_det_io(test_pred(Base), TestCases, {Successes, Fails},
+ !IO, Repeats, Time),
+ OptionString = make_options_string(SeedA, SeedB, SeedC, Base, MinDigits,
+ MaxDigits, NumTestCases, Repeats),
+ io.format("Seed A: %u\n", [u32(SeedA)], !IO),
+ io.format("Seed B: %u\n", [u32(SeedB)], !IO),
+ io.format("Seed C: %u\n", [u32(SeedC)], !IO),
+ io.format("Base: %d\n", [i(Base)], !IO),
+ io.format("Min. Digits: %u\n", [u(MinDigits)], !IO),
+ io.format("Max. Digits: %u\n", [u(MaxDigits)], !IO),
+ io.format("Bits-per-int: %d\n", [i(bits_per_int)], !IO),
+ io.format("Num. Tests: %u\n", [u(NumTestCases)], !IO),
+ io.format("Repeats: %d\n", [i(Repeats)], !IO),
+ io.format("Successes: %u\n", [u(Successes)], !IO),
+ io.format("Failures: %u\n", [u(Fails)], !IO),
+ io.format("Options: %s\n", [s(OptionString)], !IO),
+ io.format("Total Time: %d ms\n", [i(Time)], !IO).
+
+%---------------------------------------------------------------------------%
+
+:- func make_options_string(uint32, uint32, uint32, int, uint, uint,
+ uint, int) = string.
+
+make_options_string(SeedA, SeedB, SeedC, Base, MinDigits, MaxDigits,
+ NumTestCases, Repeats) = String :-
+ string.format("-a %u -b %u -c %u -B %d -l %u -u %u -n %u -r %d",
+ [u32(SeedA), u32(SeedB), u32(SeedC), i(Base), u(MinDigits),
+ u(MaxDigits), u(NumTestCases), i(Repeats)], String).
+
+%---------------------------------------------------------------------------%
+
+:- type option
+ ---> help
+
+ ; base
+ ; num_test_cases
+ ; num_repeats
+ ; minimum_digits
+ ; maximum_digits
+
+ ; seed_a
+ ; seed_b
+ ; seed_c.
+
+:- pred short_option(char::in, option::out) is semidet.
+
+short_option('h', help).
+short_option('B', base).
+short_option('n', num_test_cases).
+short_option('r', num_repeats).
+short_option('l', minimum_digits).
+short_option('u', maximum_digits).
+short_option('a', seed_a).
+short_option('b', seed_b).
+short_option('c', seed_c).
+
+:- pred long_option(string::in, option::out) is semidet.
+
+long_option("help", help).
+long_option("base", base).
+long_option("num-test-cases", num_test_cases).
+long_option("num-repeats", num_repeats).
+long_option("repeats", num_repeats).
+long_option("min-digits", minimum_digits).
+long_option("minimum-digits", minimum_digits).
+long_option("max-digits", maximum_digits).
+long_option("maximum-digits", maximum_digits).
+long_option("seed-a", seed_a).
+long_option("seed-b", seed_b).
+long_option("seed-c", seed_c).
+
+:- pred option_default(option::out, option_data::out) is multi.
+
+option_default(help, bool(no)).
+option_default(base, int(10)).
+option_default(num_test_cases, int(1_000_000)).
+option_default(num_repeats, int(10)).
+option_default(minimum_digits, int(1)).
+option_default(maximum_digits, int(31)).
+option_default(seed_a, maybe_int(no)).
+option_default(seed_b, maybe_int(no)).
+option_default(seed_c, maybe_int(no)).
+
+%---------------------------------------------------------------------------%
+
+:- pred test_pred(int::in, list(string)::in, {uint, uint}::out,
+ io::di, io::uo) is det.
+
+test_pred(Base, TestCases, {Successes, Fails}, !IO) :-
+ list.foldl3(do_conversion(Base), TestCases, 0u, Successes, 0u, Fails, !IO).
+
+:- pred do_conversion(int::in, string::in, uint::in, uint::out,
+ uint::in, uint::out, io::di, io::uo) is det.
+
+do_conversion(Base, String, !Successes, !Fails, !IO) :-
+ ( if base_string_to_int(Base, String, Int) then
+ !:Successes = !.Successes + 1u,
+ consume_int(Int, !IO)
+ else
+ !:Fails = !.Fails + 1u
+ ).
+
+:- pragma no_inline(pred(consume_int/3)).
+:- pred consume_int(int::in, io::di, io::uo) is det.
+
+consume_int(_, !IO).
+
+%---------------------------------------------------------------------------%
+
+:- pred make_test_cases(RNG::in, int::in, uint::in, uint::in, uint::in,
+ list(string)::out, State::di, State::uo) is det <= urandom(RNG, State).
+
+make_test_cases(RNG, Base, N, MinDigits, MaxDigits, TestCases, !State) :-
+ do_make_test_cases(RNG, Base, N, MinDigits, MaxDigits, [], TestCases,
+ !State).
+
+:- pred do_make_test_cases(RNG::in, int::in, uint::in, uint::in, uint::in,
+ list(string)::in, list(string)::out, State::di, State::uo)
+ is det <= urandom(RNG, State).
+
+do_make_test_cases(RNG, Base, N, MinDigits, MaxDigits, !TestCases, !State) :-
+ ( if N = 0u then
+ true
+ else
+ uniform_uint_in_range(RNG, MinDigits, MaxDigits - MinDigits + 1u,
+ NumDigits, !State),
+ generate_n_random_digits(RNG, Base, NumDigits, [], Digits0, !State),
+ uniform_int_in_range(RNG, 0, 3, PickSign, !State),
+ ( if PickSign = 0 then
+ Digits = Digits0 % No sign character.
+ else if PickSign = 1 then
+ Digits = ['+' | Digits0]
+ else
+ Digits = ['-' | Digits0]
+ ),
+ TestCase = from_char_list(Digits),
+ !:TestCases = [TestCase | !.TestCases],
+ do_make_test_cases(RNG, Base, N - 1u, MinDigits, MaxDigits, !TestCases,
+ !State)
+ ).
+
+:- pred generate_n_random_digits(RNG::in, int::in, uint::in,
+ list(char)::in, list(char)::out, State::di, State::uo)
+ is det <= urandom(RNG, State).
+
+generate_n_random_digits(RNG, Base, N, !Digits, !State) :-
+ ( if N = 0u then
+ true
+ else
+ uniform_int_in_range(RNG, 0, Base, Int, !State),
+ Digit = det_base_int_to_digit(Base, Int),
+ !:Digits = [Digit | !.Digits],
+ generate_n_random_digits(RNG, Base, N - 1u, !Digits, !State)
+ ).
+
+%---------------------------------------------------------------------------%
+
+:- pred print_help_message(io::di, io::uo) is det.
+
+print_help_message(!IO) :-
+ io.write_strings([
+ "Name: benchmark_string_to_int\n",
+ "\n",
+ "Usage: benchmark_string_to_int [<options>]\n",
+ "\n",
+ "Description:\n"
+ ], !IO),
+ io.write_prefixed_lines("\t", [
+ "Benchmark string-to-int conversion in the standard library.",
+ "Specifically, benchmark string.base_string_to_int/3 on randomly",
+ "generated test strings. The test strings have an equal probability",
+ "of having a postive, negative or no sign character.",
+ "Prints a summary to the standard output."
+ ], !IO),
+ io.nl(!IO),
+ io.nl(!IO),
+ io.write_string("Options:\n", !IO),
+ io.write_prefixed_lines("\t", [
+ "-h, --help",
+ "\tPrint this information and exit.",
+
+ "-B <n>, --base <n>",
+ "\tSpecify the base of the digits in the strings. n must be between",
+ "\t2 and 36 (inclusive). Default: 10.",
+
+ "-n <n>, --num-test-cases <n>",
+ "\tSpecify the number of test cases to generate. n must be greater",
+ "\tthan zero. Default: 1_000_000.",
+
+ "-r <n>, --repeats <n>, --num-repeats <n>",
+ "\tSpecify the number of test repetitions: n must be greater than",
+ "\tzero. Default: 10.",
+
+ "-l <min>, --min-digits <min>, --minimum-digits <min>",
+ "\tSpecify the minimum number of digits in the test cases.",
+ "\tmin must be greater than zero and must be less than or equal to",
+ "\tthe value of the '--maximum-digits' option.",
+ "\tDefault: 1.",
+
+ "-u <max>, --max-digits <max>, --maximum-digits <max>",
+ "\tSpecify the maximum number of digits in the test cases.",
+ "\tmax must be greater than zero and must be greater than or equal",
+ "\tto the value of the 'minimum-digits' option.",
+ "\tDefault: 31.",
+
+ "-a <seed>, --seed-a <seed>",
+ "-b <seed>, --seed-b <seed>",
+ "-c <seed>, --seed-c <seed>",
+ "\tSpecify the seeds of the SFC32 pseudo-random number generator used",
+ "\tto generate the test cases. If no seed options are specified, then",
+ "\tthe seeds will be randomly generated using the system RNG.",
+ "\tIf seeds are specified, then all three seed options must occur on",
+ "\tthe command line."
+ ], !IO).
+
+%---------------------------------------------------------------------------%
+
+:- pred print_option_error(option_error(option)::in, io::di, io::uo) is det.
+
+print_option_error(Error, !IO) :-
+ Msg = option_error_to_string(Error),
+ io.stderr_stream(Stderr, !IO),
+ io.format(Stderr, "error: %s.\n", [s(Msg)], !IO),
+ io.set_exit_status(1, !IO).
+
+:- pred print_usage_error(io::di, io::uo) is det.
+
+print_usage_error(!IO) :-
+ io.stderr_stream(Stderr, !IO),
+ io.print_line(Stderr, "Usage: benchmark_string_to_int [<options>]", !IO),
+ io.set_exit_status(1, !IO).
+
+:- pred print_errors(cord(string)::in, io::di, io::uo) is det.
+
+print_errors(Errors, !IO) :-
+ io.stderr_stream(Stderr, !IO),
+ cord.foldl_pred(print_error(Stderr), Errors, !IO),
+ io.set_exit_status(1, !IO).
+
+:- pred print_error(io.text_output_stream::in, string::in,
+ io::di, io::uo) is det.
+
+print_error(Stream, Error, !IO) :-
+ io.format(Stream, "Error: %s\n", [s(Error)], !IO).
+
+%---------------------------------------------------------------------------%
+:- end_module benchmark_string_to_int.
+%---------------------------------------------------------------------------%
diff --git a/library/string.m b/library/string.m
index 372dec55f..85d58c363 100644
--- a/library/string.m
+++ b/library/string.m
@@ -6027,22 +6027,150 @@ do_base_string_to_int(Base, String, Int) :-
Sign = positive,
Start = 0
),
- % The divisions below are all safe since our callers set Base
- % to be in 2..36.
+
+ % Do not include the sign bit, if any, in our initial digit count.
+ NumStringDigits = End - Start,
(
Sign = positive,
- CutOff = max_int `unchecked_quotient` Base,
- CutLimit = max_int `unchecked_rem` Base,
- do_base_string_to_positive_int_loop(Base, CutOff, CutLimit, String,
- Start, End, 0, Int)
+ ( if can_use_to_int_fast_path(Base, NumStringDigits) then
+ do_unsafe_base_string_to_positive_int_loop(Base, String,
+ Start, End, 0, Int)
+ else
+ % These divisions (and the ones in the negative case) are all safe
+ % since our callers set Base to be in 2..36.
+ CutOff = max_int `unchecked_quotient` Base,
+ CutLimit = max_int `unchecked_rem` Base,
+ do_base_string_to_positive_int_loop(Base, CutOff, CutLimit, String,
+ Start, End, 0, Int)
+ )
;
Sign = negative,
- CutOff = min_int `unchecked_quotient` Base,
- CutLimit = -(min_int `unchecked_rem` Base),
- do_base_string_to_negative_int_loop(Base, CutOff, CutLimit, String,
- Start, End, 0, Int)
+ ( if can_use_to_int_fast_path(Base, NumStringDigits) then
+ do_unsafe_base_string_to_negative_int_loop(Base, String,
+ Start, End, 0, Int)
+ else
+ CutOff = min_int `unchecked_quotient` Base,
+ CutLimit = -(min_int `unchecked_rem` Base),
+ do_base_string_to_negative_int_loop(Base, CutOff, CutLimit, String,
+ Start, End, 0, Int)
+ )
).
+%---------------------%
+
+ % can_use_to_int_fast_path(Base, NumDigits):
+ %
+ % Can we safely use the fast path string-to-int conversion for a string of
+ % base Base digits of length NumDigits?
+ %
+:- pred can_use_to_int_fast_path(int::in, int::in) is semidet.
+
+can_use_to_int_fast_path(Base, NumDigits) :-
+ WordSize = bits_per_int,
+ (
+ WordSize = 32,
+ safe_int_digits_for_word32_and_base(Base, SafeDigits)
+ ;
+ WordSize = 64,
+ safe_int_digits_for_word64_and_base(Base, SafeDigits)
+ ),
+ NumDigits =< SafeDigits.
+
+ % safe_int_digits_for_word32_and_base(Base, SafeDigits):
+ %
+ % For a given base Base, SafeDigits is the largest number of digits such
+ % that every string of SafeDigits base Base digits denotes a value that
+ % fits in a 32-bit signed int. That is, SafeDigits is the largest number
+ % such that:
+ %
+ % Base ^ SafeDigits - 1 =< max_int, where max_int = 2 ^ (32 - 1) - 1.
+ %
+ % We use the same value of SafeDigits for negative ints. That is safe,
+ % since abs(min_int) = max_int + 1 (i.e., a bound that holds for max_int
+ % also holds for min_int).
+ %
+:- pred safe_int_digits_for_word32_and_base(int::in, int::out) is semidet.
+
+safe_int_digits_for_word32_and_base(2, 31).
+safe_int_digits_for_word32_and_base(3, 19).
+safe_int_digits_for_word32_and_base(4, 15).
+safe_int_digits_for_word32_and_base(5, 13).
+safe_int_digits_for_word32_and_base(6, 11).
+safe_int_digits_for_word32_and_base(7, 11).
+safe_int_digits_for_word32_and_base(8, 10).
+safe_int_digits_for_word32_and_base(9, 9).
+safe_int_digits_for_word32_and_base(10, 9).
+safe_int_digits_for_word32_and_base(11, 8).
+safe_int_digits_for_word32_and_base(12, 8).
+safe_int_digits_for_word32_and_base(13, 8).
+safe_int_digits_for_word32_and_base(14, 8).
+safe_int_digits_for_word32_and_base(15, 7).
+safe_int_digits_for_word32_and_base(16, 7).
+safe_int_digits_for_word32_and_base(17, 7).
+safe_int_digits_for_word32_and_base(18, 7).
+safe_int_digits_for_word32_and_base(19, 7).
+safe_int_digits_for_word32_and_base(20, 7).
+safe_int_digits_for_word32_and_base(21, 7).
+safe_int_digits_for_word32_and_base(22, 6).
+safe_int_digits_for_word32_and_base(23, 6).
+safe_int_digits_for_word32_and_base(24, 6).
+safe_int_digits_for_word32_and_base(25, 6).
+safe_int_digits_for_word32_and_base(26, 6).
+safe_int_digits_for_word32_and_base(27, 6).
+safe_int_digits_for_word32_and_base(28, 6).
+safe_int_digits_for_word32_and_base(29, 6).
+safe_int_digits_for_word32_and_base(30, 6).
+safe_int_digits_for_word32_and_base(31, 6).
+safe_int_digits_for_word32_and_base(32, 6).
+safe_int_digits_for_word32_and_base(33, 6).
+safe_int_digits_for_word32_and_base(34, 6).
+safe_int_digits_for_word32_and_base(35, 6).
+safe_int_digits_for_word32_and_base(36, 5).
+
+ % safe_int_digits_for_word64_and_base(Base, SafeDigits):
+ %
+ % As above, but for 64-bit ints.
+ %
+:- pred safe_int_digits_for_word64_and_base(int::in, int::out) is semidet.
+
+safe_int_digits_for_word64_and_base(2, 63).
+safe_int_digits_for_word64_and_base(3, 39).
+safe_int_digits_for_word64_and_base(4, 31).
+safe_int_digits_for_word64_and_base(5, 27).
+safe_int_digits_for_word64_and_base(6, 24).
+safe_int_digits_for_word64_and_base(7, 22).
+safe_int_digits_for_word64_and_base(8, 21).
+safe_int_digits_for_word64_and_base(9, 19).
+safe_int_digits_for_word64_and_base(10, 18).
+safe_int_digits_for_word64_and_base(11, 18).
+safe_int_digits_for_word64_and_base(12, 17).
+safe_int_digits_for_word64_and_base(13, 17).
+safe_int_digits_for_word64_and_base(14, 16).
+safe_int_digits_for_word64_and_base(15, 16).
+safe_int_digits_for_word64_and_base(16, 15).
+safe_int_digits_for_word64_and_base(17, 15).
+safe_int_digits_for_word64_and_base(18, 15).
+safe_int_digits_for_word64_and_base(19, 14).
+safe_int_digits_for_word64_and_base(20, 14).
+safe_int_digits_for_word64_and_base(21, 14).
+safe_int_digits_for_word64_and_base(22, 14).
+safe_int_digits_for_word64_and_base(23, 13).
+safe_int_digits_for_word64_and_base(24, 13).
+safe_int_digits_for_word64_and_base(25, 13).
+safe_int_digits_for_word64_and_base(26, 13).
+safe_int_digits_for_word64_and_base(27, 13).
+safe_int_digits_for_word64_and_base(28, 13).
+safe_int_digits_for_word64_and_base(29, 12).
+safe_int_digits_for_word64_and_base(30, 12).
+safe_int_digits_for_word64_and_base(31, 12).
+safe_int_digits_for_word64_and_base(32, 12).
+safe_int_digits_for_word64_and_base(33, 12).
+safe_int_digits_for_word64_and_base(34, 12).
+safe_int_digits_for_word64_and_base(35, 12).
+safe_int_digits_for_word64_and_base(36, 12).
+
+%---------------------%
+
% do_base_string_to_positive_int_loop(Base, CutOff, CutLimit, String,
% CurOffset, EndOffset, !Int):
%
@@ -6160,6 +6288,44 @@ do_base_string_to_negative_int_loop(Base,
CutOff, CutLimit, String,
true
).
+%---------------------%
+
+ % A version of do_base_string_to_positive_int_loop that omits the the
+ % overflow check. This is faster, but can only be used safely when the
+ % number of digits in the string is below that which potentially overflow.
+ %
+:- pred do_unsafe_base_string_to_positive_int_loop(int::in, string::in,
+ int::in, int::in, int::in, int::out) is semidet.
+
+do_unsafe_base_string_to_positive_int_loop(Base, String, CurOffset,
+ EndOffset, !Int) :-
+ ( if CurOffset < EndOffset then
+ unsafe_index_next(String, CurOffset, NextOffset, Char),
+ char.unsafe_base_digit_to_int(Base, Char, M),
+ !:Int = (Base * !.Int) + M,
+ do_unsafe_base_string_to_positive_int_loop(Base, String, NextOffset,
+ EndOffset, !Int)
+ else
+ true
+ ).
+
+ % As above, but for the negative case.
+ %
+:- pred do_unsafe_base_string_to_negative_int_loop(int::in, string::in,
+ int::in, int::in, int::in, int::out) is semidet.
+
+do_unsafe_base_string_to_negative_int_loop(Base, String, CurOffset,
+ EndOffset, !Int) :-
+ ( if CurOffset < EndOffset then
+ unsafe_index_next(String, CurOffset, NextOffset, Char),
+ char.unsafe_base_digit_to_int(Base, Char, M),
+ !:Int = (Base * !.Int) - M,
+ do_unsafe_base_string_to_negative_int_loop(Base, String,
+ NextOffset, EndOffset, !Int)
+ else
+ true
+ ).
+
%---------------------%
to_uint(String, UInt) :-
@@ -6191,12 +6357,128 @@ do_base_string_to_uint(Base, String, UInt) :-
End = string.count_code_units(String),
End > 0, % Fail if we have the empty string.
UBase = uint.cast_from_int(Base),
- % Both of these divisions are safe since our callers set Base
- % to be in 2..36.
- CutOff = max_uint `unchecked_quotient` UBase,
- CutLimit = max_uint `unchecked_rem` UBase,
- do_base_string_to_uint_loop(UBase, Base, CutOff, CutLimit, String,
- 0, End, 0u, UInt).
+ ( if can_use_to_uint_fast_path(Base, End) then
+ do_unsafe_base_string_to_uint_loop(UBase, Base, String, 0, End,
+ 0u, UInt)
+ else
+ % Both of these divisions are safe since our callers set Base
+ % to be in 2..36.
+ CutOff = max_uint `unchecked_quotient` UBase,
+ CutLimit = max_uint `unchecked_rem` UBase,
+ do_base_string_to_uint_loop(UBase, Base, CutOff, CutLimit, String,
+ 0, End, 0u, UInt)
+ ).
+
+%---------------------%
+
+ % can_use_to_uint_fast_path(Base, NumDigits):
+ %
+ % Can we safely use the fast path string-to-uint conversion for a string of
+ % base Base digits of length NumDigits?
+ %
+:- pred can_use_to_uint_fast_path(int::in, int::in) is semidet.
+
+can_use_to_uint_fast_path(Base, NumDigits) :-
+ WordSize = bits_per_uint,
+ (
+ WordSize = 32,
+ safe_uint_digits_for_word32_and_base(Base, SafeDigits)
+ ;
+ WordSize = 64,
+ safe_uint_digits_for_word64_and_base(Base, SafeDigits)
+ ),
+ NumDigits =< SafeDigits.
+
+ % safe_uint_digits_for_word32_and_base(Base, SafeDigits):
+ %
+ % For a given base Base, SafeDigits is the largest number of digits such
+ % that every string of SafeDigits base Base digits denotes a value that
+ % fits in a 32-bit unsigned int. That is, SafeDigits is the largest number
+ % such that:
+ %
+ % Base ^ SafeDigits - 1 =< max_uint, where max_uint = 2 ^ 32 - 1.
+ %
+:- pred safe_uint_digits_for_word32_and_base(int::in, int::out) is semidet.
+
+safe_uint_digits_for_word32_and_base(2, 32).
+safe_uint_digits_for_word32_and_base(3, 20).
+safe_uint_digits_for_word32_and_base(4, 16).
+safe_uint_digits_for_word32_and_base(5, 13).
+safe_uint_digits_for_word32_and_base(6, 12).
+safe_uint_digits_for_word32_and_base(7, 11).
+safe_uint_digits_for_word32_and_base(8, 10).
+safe_uint_digits_for_word32_and_base(9, 10).
+safe_uint_digits_for_word32_and_base(10, 9).
+safe_uint_digits_for_word32_and_base(11, 9).
+safe_uint_digits_for_word32_and_base(12, 8).
+safe_uint_digits_for_word32_and_base(13, 8).
+safe_uint_digits_for_word32_and_base(14, 8).
+safe_uint_digits_for_word32_and_base(15, 8).
+safe_uint_digits_for_word32_and_base(16, 8).
+safe_uint_digits_for_word32_and_base(17, 7).
+safe_uint_digits_for_word32_and_base(18, 7).
+safe_uint_digits_for_word32_and_base(19, 7).
+safe_uint_digits_for_word32_and_base(20, 7).
+safe_uint_digits_for_word32_and_base(21, 7).
+safe_uint_digits_for_word32_and_base(22, 7).
+safe_uint_digits_for_word32_and_base(23, 7).
+safe_uint_digits_for_word32_and_base(24, 6).
+safe_uint_digits_for_word32_and_base(25, 6).
+safe_uint_digits_for_word32_and_base(26, 6).
+safe_uint_digits_for_word32_and_base(27, 6).
+safe_uint_digits_for_word32_and_base(28, 6).
+safe_uint_digits_for_word32_and_base(29, 6).
+safe_uint_digits_for_word32_and_base(30, 6).
+safe_uint_digits_for_word32_and_base(31, 6).
+safe_uint_digits_for_word32_and_base(32, 6).
+safe_uint_digits_for_word32_and_base(33, 6).
+safe_uint_digits_for_word32_and_base(34, 6).
+safe_uint_digits_for_word32_and_base(35, 6).
+safe_uint_digits_for_word32_and_base(36, 6).
+
+ % safe_uint_digits_for_word64_and_base(Base, SafeDigits):
+ %
+ % As above, but for 64-bit uints.
+ %
+:- pred safe_uint_digits_for_word64_and_base(int::in, int::out) is semidet.
+
+safe_uint_digits_for_word64_and_base(2, 64).
+safe_uint_digits_for_word64_and_base(3, 40).
+safe_uint_digits_for_word64_and_base(4, 32).
+safe_uint_digits_for_word64_and_base(5, 27).
+safe_uint_digits_for_word64_and_base(6, 24).
+safe_uint_digits_for_word64_and_base(7, 22).
+safe_uint_digits_for_word64_and_base(8, 21).
+safe_uint_digits_for_word64_and_base(9, 20).
+safe_uint_digits_for_word64_and_base(10, 19).
+safe_uint_digits_for_word64_and_base(11, 18).
+safe_uint_digits_for_word64_and_base(12, 17).
+safe_uint_digits_for_word64_and_base(13, 17).
+safe_uint_digits_for_word64_and_base(14, 16).
+safe_uint_digits_for_word64_and_base(15, 16).
+safe_uint_digits_for_word64_and_base(16, 16).
+safe_uint_digits_for_word64_and_base(17, 15).
+safe_uint_digits_for_word64_and_base(18, 15).
+safe_uint_digits_for_word64_and_base(19, 15).
+safe_uint_digits_for_word64_and_base(20, 14).
+safe_uint_digits_for_word64_and_base(21, 14).
+safe_uint_digits_for_word64_and_base(22, 14).
+safe_uint_digits_for_word64_and_base(23, 14).
+safe_uint_digits_for_word64_and_base(24, 13).
+safe_uint_digits_for_word64_and_base(25, 13).
+safe_uint_digits_for_word64_and_base(26, 13).
+safe_uint_digits_for_word64_and_base(27, 13).
+safe_uint_digits_for_word64_and_base(28, 13).
+safe_uint_digits_for_word64_and_base(29, 13).
+safe_uint_digits_for_word64_and_base(30, 13).
+safe_uint_digits_for_word64_and_base(31, 12).
+safe_uint_digits_for_word64_and_base(32, 12).
+safe_uint_digits_for_word64_and_base(33, 12).
+safe_uint_digits_for_word64_and_base(34, 12).
+safe_uint_digits_for_word64_and_base(35, 12).
+safe_uint_digits_for_word64_and_base(36, 12).
+
+%---------------------%
% do_base_string_to_uint_loop(UBase, Base, CutOff, CutLimit, String,
% CurOffset, EndOffset, !UInt):
@@ -6223,6 +6505,29 @@ do_base_string_to_uint_loop(UBase, Base,
CutOff, CutLimit, String,
true
).
+ % do_unsafe_base_string_to_uint_loop(UBase, Base, String, CurOffset,
+ % EndOffset, !UInt):
+ %
+ % A version of do_base_string_to_uint_loop that omits the the overflow
+ % check. This is faster, but can only be used safely when the number of
+ % digits in the string is below that which potentially overflow.
+ %
+:- pred do_unsafe_base_string_to_uint_loop(uint::in, int::in, string::in,
+ int::in, int::in, uint::in, uint::out) is semidet.
+
+do_unsafe_base_string_to_uint_loop(UBase, Base, String, CurOffset, EndOffset,
+ !UInt) :-
+ ( if CurOffset < EndOffset then
+ unsafe_index_next(String, CurOffset, NextOffset, Char),
+ char.unsafe_base_digit_to_int(Base, Char, M),
+ MU = uint.cast_from_int(M),
+ !:UInt = (UBase * !.UInt) + MU,
+ do_unsafe_base_string_to_uint_loop(UBase, Base, String,
+ NextOffset, EndOffset, !UInt)
+ else
+ true
+ ).
+
%---------------------%
:- pragma foreign_export("C", to_float(in, out),
diff --git a/tests/general/test_string_to_int_overflow.exp
b/tests/general/test_string_to_int_overflow.exp
index 16662d4d4..6783e7f17 100644
--- a/tests/general/test_string_to_int_overflow.exp
+++ b/tests/general/test_string_to_int_overflow.exp
@@ -64,6 +64,48 @@ no
no
no
no
+### Fast path boundary values for 32-bit ints ###
+2147483647
+no
+-2147483647
+no
+1073741823
+no
+-1073741823
+no
+999999999
+no
+-999999999
+no
+268435455
+no
+-268435455
+no
+60466175
+no
+-60466175
+no
+### Fast path boundary values for 64-bit ints ###
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
### Overflow regression tests for 32-bit ints ###
no
no
diff --git a/tests/general/test_string_to_int_overflow.exp2
b/tests/general/test_string_to_int_overflow.exp2
index 72dedae4b..797f9303f 100644
--- a/tests/general/test_string_to_int_overflow.exp2
+++ b/tests/general/test_string_to_int_overflow.exp2
@@ -64,6 +64,48 @@ no
2147483648
9223372036854775807
no
+### Fast path boundary values for 32-bit ints ###
+2147483647
+4294967295
+-2147483647
+-4294967295
+1073741823
+8589934591
+-1073741823
+-8589934591
+999999999
+9999999999
+-999999999
+-9999999999
+268435455
+4294967295
+-268435455
+-4294967295
+60466175
+2176782335
+-60466175
+-2176782335
+### Fast path boundary values for 64-bit ints ###
+9223372036854775807
+no
+-9223372036854775807
+no
+9223372036854775807
+no
+-9223372036854775807
+no
+999999999999999999
+no
+-999999999999999999
+no
+1152921504606846975
+no
+-1152921504606846975
+no
+4738381338321616895
+no
+-4738381338321616895
+no
### Overflow regression tests for 32-bit ints ###
5368709120
-5368709120
diff --git a/tests/general/test_string_to_int_overflow.m
b/tests/general/test_string_to_int_overflow.m
index 42d658066..8af20fecb 100644
--- a/tests/general/test_string_to_int_overflow.m
+++ b/tests/general/test_string_to_int_overflow.m
@@ -120,6 +120,88 @@ main(!IO) :-
test(base_string_to_int(10, "+9223372036854775807"), !IO),
test(base_string_to_int(10, "+9223372036854775808"), !IO),
+ % The base_string_to_int/3 fast path skips the overflow check entirely for
+ % strings that are short enough no string of that many digits can overflow.
+ % The number of digits for which this holds depends on the base and the
+ % word size; see safe_int_digits_for_word{32,64}_and_base in string.m.
+ %
+ % The following paired tests check that the overflow behaviour is correct
+ % at boundary between the fast and checked paths. The first test in each
+ % pair is the largest value with the largest number of digits that the fast
+ % path accepts: as many copies of the digit Base - 1 as the table allows.
+ % If the table said one more digit is safe, then this value would overflow
+ % on the unchecked loop and be converted to the wrong answer. The second
+ % test in each pair adds that one more digit, which must take the checked
+ % path and be rejected.
+
+ line("Fast path boundary values for 32-bit ints", !IO),
+
+ test(base_string_to_int(2, "1111111111111111111111111111111"), !IO),
+ test(base_string_to_int(2, "11111111111111111111111111111111"), !IO),
+
+ test(base_string_to_int(2, "-1111111111111111111111111111111"), !IO),
+ test(base_string_to_int(2, "-11111111111111111111111111111111"), !IO),
+
+ test(base_string_to_int(8, "7777777777"), !IO),
+ test(base_string_to_int(8, "77777777777"), !IO),
+
+ test(base_string_to_int(8, "-7777777777"), !IO),
+ test(base_string_to_int(8, "-77777777777"), !IO),
+
+ test(base_string_to_int(10, "999999999"), !IO),
+ test(base_string_to_int(10, "9999999999"), !IO),
+
+ test(base_string_to_int(10, "-999999999"), !IO),
+ test(base_string_to_int(10, "-9999999999"), !IO),
+
+ test(base_string_to_int(16, "FFFFFFF"), !IO),
+ test(base_string_to_int(16, "FFFFFFFF"), !IO),
+
+ test(base_string_to_int(16, "-FFFFFFF"), !IO),
+ test(base_string_to_int(16, "-FFFFFFFF"), !IO),
+
+ test(base_string_to_int(36, "ZZZZZ"), !IO),
+ test(base_string_to_int(36, "ZZZZZZ"), !IO),
+
+ test(base_string_to_int(36, "-ZZZZZ"), !IO),
+ test(base_string_to_int(36, "-ZZZZZZ"), !IO),
+
+ line("Fast path boundary values for 64-bit ints", !IO),
+
+ test(base_string_to_int(2, "1111111111111111111111111111111" ++
+ "11111111111111111111111111111111"), !IO),
+ test(base_string_to_int(2, "11111111111111111111111111111111" ++
+ "11111111111111111111111111111111"), !IO),
+
+ test(base_string_to_int(2, "-1111111111111111111111111111111" ++
+ "11111111111111111111111111111111"), !IO),
+ test(base_string_to_int(2, "-1111111111111111111111111111111" ++
+ "111111111111111111111111111111111"), !IO),
+
+ test(base_string_to_int(8, "777777777777777777777"), !IO),
+ test(base_string_to_int(8, "7777777777777777777777"), !IO),
+
+ test(base_string_to_int(8, "-777777777777777777777"), !IO),
+ test(base_string_to_int(8, "-7777777777777777777777"), !IO),
+
+ test(base_string_to_int(10, "999999999999999999"), !IO),
+ test(base_string_to_int(10, "9999999999999999999"), !IO),
+
+ test(base_string_to_int(10, "-999999999999999999"), !IO),
+ test(base_string_to_int(10, "-9999999999999999999"), !IO),
+
+ test(base_string_to_int(16, "FFFFFFFFFFFFFFF"), !IO),
+ test(base_string_to_int(16, "FFFFFFFFFFFFFFFF"), !IO),
+
+ test(base_string_to_int(16, "-FFFFFFFFFFFFFFF"), !IO),
+ test(base_string_to_int(16, "-FFFFFFFFFFFFFFFF"), !IO),
+
+ test(base_string_to_int(36, "ZZZZZZZZZZZZ"), !IO),
+ test(base_string_to_int(36, "ZZZZZZZZZZZZZ"), !IO),
+
+ test(base_string_to_int(36, "-ZZZZZZZZZZZZ"), !IO),
+ test(base_string_to_int(36, "-ZZZZZZZZZZZZZ"), !IO),
+
% Regression tests for incorrect overflow check. For each of these
% values, processing the final digit overflows by 2^63 or more
% (2^31 on 32-bit platforms), so the wrapped-around result has the
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index dacc6d148..4c79a5275 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -26,6 +26,8 @@ ORDINARY_PROGS = \
array_unify_compare \
bad_set_line_number \
bag_various \
+ base_string_to_int_bases \
+ base_string_to_uint_bases \
bidirectional \
bigtest \
bimap_set_bug \
diff --git a/tests/hard_coded/base_string_to_int_bases.exp
b/tests/hard_coded/base_string_to_int_bases.exp
new file mode 100644
index 000000000..070464191
--- /dev/null
+++ b/tests/hard_coded/base_string_to_int_bases.exp
@@ -0,0 +1,280 @@
+base 2: largest fast path value: ok
+base 2: negated largest fast path value: ok
+base 2: one digit more than the fast path allows: ok
+base 2: negated one digit more than the fast path allows: ok
+base 2: max_int: ok
+base 2: min_int: ok
+base 2: max_int + 1: ok
+base 2: min_int - 1: ok
+base 3: largest fast path value: ok
+base 3: negated largest fast path value: ok
+base 3: one digit more than the fast path allows: ok
+base 3: negated one digit more than the fast path allows: ok
+base 3: max_int: ok
+base 3: min_int: ok
+base 3: max_int + 1: ok
+base 3: min_int - 1: ok
+base 4: largest fast path value: ok
+base 4: negated largest fast path value: ok
+base 4: one digit more than the fast path allows: ok
+base 4: negated one digit more than the fast path allows: ok
+base 4: max_int: ok
+base 4: min_int: ok
+base 4: max_int + 1: ok
+base 4: min_int - 1: ok
+base 5: largest fast path value: ok
+base 5: negated largest fast path value: ok
+base 5: one digit more than the fast path allows: ok
+base 5: negated one digit more than the fast path allows: ok
+base 5: max_int: ok
+base 5: min_int: ok
+base 5: max_int + 1: ok
+base 5: min_int - 1: ok
+base 6: largest fast path value: ok
+base 6: negated largest fast path value: ok
+base 6: one digit more than the fast path allows: ok
+base 6: negated one digit more than the fast path allows: ok
+base 6: max_int: ok
+base 6: min_int: ok
+base 6: max_int + 1: ok
+base 6: min_int - 1: ok
+base 7: largest fast path value: ok
+base 7: negated largest fast path value: ok
+base 7: one digit more than the fast path allows: ok
+base 7: negated one digit more than the fast path allows: ok
+base 7: max_int: ok
+base 7: min_int: ok
+base 7: max_int + 1: ok
+base 7: min_int - 1: ok
+base 8: largest fast path value: ok
+base 8: negated largest fast path value: ok
+base 8: one digit more than the fast path allows: ok
+base 8: negated one digit more than the fast path allows: ok
+base 8: max_int: ok
+base 8: min_int: ok
+base 8: max_int + 1: ok
+base 8: min_int - 1: ok
+base 9: largest fast path value: ok
+base 9: negated largest fast path value: ok
+base 9: one digit more than the fast path allows: ok
+base 9: negated one digit more than the fast path allows: ok
+base 9: max_int: ok
+base 9: min_int: ok
+base 9: max_int + 1: ok
+base 9: min_int - 1: ok
+base 10: largest fast path value: ok
+base 10: negated largest fast path value: ok
+base 10: one digit more than the fast path allows: ok
+base 10: negated one digit more than the fast path allows: ok
+base 10: max_int: ok
+base 10: min_int: ok
+base 10: max_int + 1: ok
+base 10: min_int - 1: ok
+base 11: largest fast path value: ok
+base 11: negated largest fast path value: ok
+base 11: one digit more than the fast path allows: ok
+base 11: negated one digit more than the fast path allows: ok
+base 11: max_int: ok
+base 11: min_int: ok
+base 11: max_int + 1: ok
+base 11: min_int - 1: ok
+base 12: largest fast path value: ok
+base 12: negated largest fast path value: ok
+base 12: one digit more than the fast path allows: ok
+base 12: negated one digit more than the fast path allows: ok
+base 12: max_int: ok
+base 12: min_int: ok
+base 12: max_int + 1: ok
+base 12: min_int - 1: ok
+base 13: largest fast path value: ok
+base 13: negated largest fast path value: ok
+base 13: one digit more than the fast path allows: ok
+base 13: negated one digit more than the fast path allows: ok
+base 13: max_int: ok
+base 13: min_int: ok
+base 13: max_int + 1: ok
+base 13: min_int - 1: ok
+base 14: largest fast path value: ok
+base 14: negated largest fast path value: ok
+base 14: one digit more than the fast path allows: ok
+base 14: negated one digit more than the fast path allows: ok
+base 14: max_int: ok
+base 14: min_int: ok
+base 14: max_int + 1: ok
+base 14: min_int - 1: ok
+base 15: largest fast path value: ok
+base 15: negated largest fast path value: ok
+base 15: one digit more than the fast path allows: ok
+base 15: negated one digit more than the fast path allows: ok
+base 15: max_int: ok
+base 15: min_int: ok
+base 15: max_int + 1: ok
+base 15: min_int - 1: ok
+base 16: largest fast path value: ok
+base 16: negated largest fast path value: ok
+base 16: one digit more than the fast path allows: ok
+base 16: negated one digit more than the fast path allows: ok
+base 16: max_int: ok
+base 16: min_int: ok
+base 16: max_int + 1: ok
+base 16: min_int - 1: ok
+base 17: largest fast path value: ok
+base 17: negated largest fast path value: ok
+base 17: one digit more than the fast path allows: ok
+base 17: negated one digit more than the fast path allows: ok
+base 17: max_int: ok
+base 17: min_int: ok
+base 17: max_int + 1: ok
+base 17: min_int - 1: ok
+base 18: largest fast path value: ok
+base 18: negated largest fast path value: ok
+base 18: one digit more than the fast path allows: ok
+base 18: negated one digit more than the fast path allows: ok
+base 18: max_int: ok
+base 18: min_int: ok
+base 18: max_int + 1: ok
+base 18: min_int - 1: ok
+base 19: largest fast path value: ok
+base 19: negated largest fast path value: ok
+base 19: one digit more than the fast path allows: ok
+base 19: negated one digit more than the fast path allows: ok
+base 19: max_int: ok
+base 19: min_int: ok
+base 19: max_int + 1: ok
+base 19: min_int - 1: ok
+base 20: largest fast path value: ok
+base 20: negated largest fast path value: ok
+base 20: one digit more than the fast path allows: ok
+base 20: negated one digit more than the fast path allows: ok
+base 20: max_int: ok
+base 20: min_int: ok
+base 20: max_int + 1: ok
+base 20: min_int - 1: ok
+base 21: largest fast path value: ok
+base 21: negated largest fast path value: ok
+base 21: one digit more than the fast path allows: ok
+base 21: negated one digit more than the fast path allows: ok
+base 21: max_int: ok
+base 21: min_int: ok
+base 21: max_int + 1: ok
+base 21: min_int - 1: ok
+base 22: largest fast path value: ok
+base 22: negated largest fast path value: ok
+base 22: one digit more than the fast path allows: ok
+base 22: negated one digit more than the fast path allows: ok
+base 22: max_int: ok
+base 22: min_int: ok
+base 22: max_int + 1: ok
+base 22: min_int - 1: ok
+base 23: largest fast path value: ok
+base 23: negated largest fast path value: ok
+base 23: one digit more than the fast path allows: ok
+base 23: negated one digit more than the fast path allows: ok
+base 23: max_int: ok
+base 23: min_int: ok
+base 23: max_int + 1: ok
+base 23: min_int - 1: ok
+base 24: largest fast path value: ok
+base 24: negated largest fast path value: ok
+base 24: one digit more than the fast path allows: ok
+base 24: negated one digit more than the fast path allows: ok
+base 24: max_int: ok
+base 24: min_int: ok
+base 24: max_int + 1: ok
+base 24: min_int - 1: ok
+base 25: largest fast path value: ok
+base 25: negated largest fast path value: ok
+base 25: one digit more than the fast path allows: ok
+base 25: negated one digit more than the fast path allows: ok
+base 25: max_int: ok
+base 25: min_int: ok
+base 25: max_int + 1: ok
+base 25: min_int - 1: ok
+base 26: largest fast path value: ok
+base 26: negated largest fast path value: ok
+base 26: one digit more than the fast path allows: ok
+base 26: negated one digit more than the fast path allows: ok
+base 26: max_int: ok
+base 26: min_int: ok
+base 26: max_int + 1: ok
+base 26: min_int - 1: ok
+base 27: largest fast path value: ok
+base 27: negated largest fast path value: ok
+base 27: one digit more than the fast path allows: ok
+base 27: negated one digit more than the fast path allows: ok
+base 27: max_int: ok
+base 27: min_int: ok
+base 27: max_int + 1: ok
+base 27: min_int - 1: ok
+base 28: largest fast path value: ok
+base 28: negated largest fast path value: ok
+base 28: one digit more than the fast path allows: ok
+base 28: negated one digit more than the fast path allows: ok
+base 28: max_int: ok
+base 28: min_int: ok
+base 28: max_int + 1: ok
+base 28: min_int - 1: ok
+base 29: largest fast path value: ok
+base 29: negated largest fast path value: ok
+base 29: one digit more than the fast path allows: ok
+base 29: negated one digit more than the fast path allows: ok
+base 29: max_int: ok
+base 29: min_int: ok
+base 29: max_int + 1: ok
+base 29: min_int - 1: ok
+base 30: largest fast path value: ok
+base 30: negated largest fast path value: ok
+base 30: one digit more than the fast path allows: ok
+base 30: negated one digit more than the fast path allows: ok
+base 30: max_int: ok
+base 30: min_int: ok
+base 30: max_int + 1: ok
+base 30: min_int - 1: ok
+base 31: largest fast path value: ok
+base 31: negated largest fast path value: ok
+base 31: one digit more than the fast path allows: ok
+base 31: negated one digit more than the fast path allows: ok
+base 31: max_int: ok
+base 31: min_int: ok
+base 31: max_int + 1: ok
+base 31: min_int - 1: ok
+base 32: largest fast path value: ok
+base 32: negated largest fast path value: ok
+base 32: one digit more than the fast path allows: ok
+base 32: negated one digit more than the fast path allows: ok
+base 32: max_int: ok
+base 32: min_int: ok
+base 32: max_int + 1: ok
+base 32: min_int - 1: ok
+base 33: largest fast path value: ok
+base 33: negated largest fast path value: ok
+base 33: one digit more than the fast path allows: ok
+base 33: negated one digit more than the fast path allows: ok
+base 33: max_int: ok
+base 33: min_int: ok
+base 33: max_int + 1: ok
+base 33: min_int - 1: ok
+base 34: largest fast path value: ok
+base 34: negated largest fast path value: ok
+base 34: one digit more than the fast path allows: ok
+base 34: negated one digit more than the fast path allows: ok
+base 34: max_int: ok
+base 34: min_int: ok
+base 34: max_int + 1: ok
+base 34: min_int - 1: ok
+base 35: largest fast path value: ok
+base 35: negated largest fast path value: ok
+base 35: one digit more than the fast path allows: ok
+base 35: negated one digit more than the fast path allows: ok
+base 35: max_int: ok
+base 35: min_int: ok
+base 35: max_int + 1: ok
+base 35: min_int - 1: ok
+base 36: largest fast path value: ok
+base 36: negated largest fast path value: ok
+base 36: one digit more than the fast path allows: ok
+base 36: negated one digit more than the fast path allows: ok
+base 36: max_int: ok
+base 36: min_int: ok
+base 36: max_int + 1: ok
+base 36: min_int - 1: ok
diff --git a/tests/hard_coded/base_string_to_int_bases.m
b/tests/hard_coded/base_string_to_int_bases.m
new file mode 100644
index 000000000..ab4ad3531
--- /dev/null
+++ b/tests/hard_coded/base_string_to_int_bases.m
@@ -0,0 +1,180 @@
+%---------------------------------------------------------------------------%
+% vim: ts=4 sw=4 et ft=mercury
+%---------------------------------------------------------------------------%
+%
+% Check the boundary between the fast and checked paths in
+% string.base_string_to_int/3, for every base from 2 to 36.
+%
+% For each base, we compute:
+%
+% - SafeDigits, the largest number of digits D such that every string of
+% D digits in that base denotes a value that fits in an int, i.e. the
+% largest D such that Base^D - 1 =< max_int.
+%
+% - The largest string the fast path can accept, namely SafeDigits copies
+% of the digit Base - 1, whose value is Base^SafeDigits - 1. Converting
+% it must yield that value. If the table in string.m allowed one digit
+% more than is safe, this conversion would overflow on the unchecked
+% loop and yield a wrong answer instead.
+%
+% - The same string with one more digit, whose value exceeds max_int.
+% Converting it must fail, both with and without a leading '-'.
+%
+% - max_int and min_int themselves, which for most bases have more than
+% SafeDigits digits and so take the checked path. Converting them must
+% yield max_int and min_int.
+%
+% - max_int + 1 and min_int - 1, which must fail.
+%
+% Since this test checks the results of the conversions rather than printing
+% them, its expected output does not depend on the word size.
+%
+%---------------------------------------------------------------------------%
+
+:- module base_string_to_int_bases.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module char.
+:- import_module int.
+:- import_module integer.
+:- import_module list.
+:- import_module string.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+ int.fold_up(test_base, 2, 36, !IO).
+
+:- pred test_base(int::in, io::di, io::uo) is det.
+
+test_base(Base, !IO) :-
+ SafeDigits = safe_digits(Base),
+ MaxDigit = det_base_int_to_digit(Base, Base - 1),
+
+ % The largest value the fast path can be given, and one digit more.
+ LargestFastStr = string.duplicate_char(MaxDigit, SafeDigits),
+ TooManyDigitsStr = string.duplicate_char(MaxDigit, SafeDigits + 1),
+ LargestFast = integer.pow(integer(Base), integer(SafeDigits))
+ - integer.one,
+
+ % max_int and min_int, and the values just outside the range.
+ MaxInt = integer(max_int),
+ MinInt = integer(min_int),
+ MaxIntStr = integer.to_base_string(MaxInt, Base),
+ MinIntStr = "-" ++ integer.to_base_string(-MinInt, Base),
+ AboveMaxIntStr = integer.to_base_string(MaxInt + integer.one, Base),
+ BelowMinIntStr = "-" ++
+ integer.to_base_string(-MinInt + integer.one, Base),
+
+ Checks = [
+ succeeds("largest fast path value",
+ LargestFastStr, LargestFast),
+ succeeds("negated largest fast path value",
+ "-" ++ LargestFastStr, -LargestFast),
+ fails("one digit more than the fast path allows",
+ TooManyDigitsStr),
+ fails("negated one digit more than the fast path allows",
+ "-" ++ TooManyDigitsStr),
+ succeeds("max_int", MaxIntStr, MaxInt),
+ succeeds("min_int", MinIntStr, MinInt),
+ fails("max_int + 1", AboveMaxIntStr),
+ fails("min_int - 1", BelowMinIntStr)
+ ],
+ list.foldl(run_check(Base), Checks, !IO).
+
+%---------------------------------------------------------------------------%
+
+:- type check
+ ---> succeeds(
+ s_desc :: string,
+ s_string :: string,
+ s_expected :: integer
+ )
+ ; fails(
+ f_desc :: string,
+ f_string :: string
+ ).
+
+:- pred run_check(int::in, check::in, io::di, io::uo) is det.
+
+run_check(Base, Check, !IO) :-
+ (
+ Check = succeeds(Desc, Str, Expected),
+ ( if base_string_to_int(Base, Str, Int) then
+ ( if integer(Int) = Expected then
+ report_ok(Base, Desc, !IO)
+ else
+ report_bad(Base, Desc, Str,
+ "expected " ++ integer.to_string(Expected) ++
+ ", got " ++ integer.to_string(integer(Int)), !IO)
+ )
+ else
+ report_bad(Base, Desc, Str, "conversion failed", !IO)
+ )
+ ;
+ Check = fails(Desc, Str),
+ ( if base_string_to_int(Base, Str, Int) then
+ report_bad(Base, Desc, Str,
+ "conversion succeeded, yielding " ++
+ integer.to_string(integer(Int)), !IO)
+ else
+ report_ok(Base, Desc, !IO)
+ )
+ ).
+
+:- pred report_ok(int::in, string::in, io::di, io::uo) is det.
+
+report_ok(Base, Desc, !IO) :-
+ io.format("base %d: %s: ok\n", [i(Base), s(Desc)], !IO).
+
+:- pred report_bad(int::in, string::in, string::in, string::in,
+ io::di, io::uo) is det.
+
+report_bad(Base, Desc, Str, Problem, !IO) :-
+ io.format("base %d: %s: FAILED: \"%s\": %s\n",
+ [i(Base), s(Desc), s(Str), s(Problem)], !IO).
+
+%---------------------------------------------------------------------------%
+
+ % safe_digits(Base) = SafeDigits:
+ %
+ % SafeDigits is the largest number of digits D such that
+ % Base^D - 1 =< max_int, i.e. the largest number of base Base digits
+ % that a string can have while being guaranteed to denote a value
+ % that fits in an int.
+ %
+ % We compute this here rather than reading it out of string.m, so that this
+ % test cannot inherit an error from the tables there.
+ %
+:- func safe_digits(int) = int.
+
+safe_digits(Base) = SafeDigits :-
+ safe_digits_loop(integer(Base), integer(max_int), integer.one, 0,
+ SafeDigits).
+
+:- pred safe_digits_loop(integer::in, integer::in, integer::in, int::in,
+ int::out) is det.
+
+safe_digits_loop(Base, MaxInt, Power0, Digits0, Digits) :-
+ % Power0 is Base^Digits0. Add another digit if the largest value with
+ % Digits0 + 1 digits, i.e. Base^(Digits0 + 1) - 1, still fits.
+ Power1 = Power0 * Base,
+ ( if Power1 - integer.one =< MaxInt then
+ safe_digits_loop(Base, MaxInt, Power1, Digits0 + 1, Digits)
+ else
+ Digits = Digits0
+ ).
+
+%---------------------------------------------------------------------------%
+:- end_module base_string_to_int_bases.
+%---------------------------------------------------------------------------%
diff --git a/tests/hard_coded/base_string_to_uint_bases.exp
b/tests/hard_coded/base_string_to_uint_bases.exp
new file mode 100644
index 000000000..b58489c8b
--- /dev/null
+++ b/tests/hard_coded/base_string_to_uint_bases.exp
@@ -0,0 +1,140 @@
+base 2: largest fast path value: ok
+base 2: one digit more than the fast path allows: ok
+base 2: max_uint: ok
+base 2: max_uint + 1: ok
+base 3: largest fast path value: ok
+base 3: one digit more than the fast path allows: ok
+base 3: max_uint: ok
+base 3: max_uint + 1: ok
+base 4: largest fast path value: ok
+base 4: one digit more than the fast path allows: ok
+base 4: max_uint: ok
+base 4: max_uint + 1: ok
+base 5: largest fast path value: ok
+base 5: one digit more than the fast path allows: ok
+base 5: max_uint: ok
+base 5: max_uint + 1: ok
+base 6: largest fast path value: ok
+base 6: one digit more than the fast path allows: ok
+base 6: max_uint: ok
+base 6: max_uint + 1: ok
+base 7: largest fast path value: ok
+base 7: one digit more than the fast path allows: ok
+base 7: max_uint: ok
+base 7: max_uint + 1: ok
+base 8: largest fast path value: ok
+base 8: one digit more than the fast path allows: ok
+base 8: max_uint: ok
+base 8: max_uint + 1: ok
+base 9: largest fast path value: ok
+base 9: one digit more than the fast path allows: ok
+base 9: max_uint: ok
+base 9: max_uint + 1: ok
+base 10: largest fast path value: ok
+base 10: one digit more than the fast path allows: ok
+base 10: max_uint: ok
+base 10: max_uint + 1: ok
+base 11: largest fast path value: ok
+base 11: one digit more than the fast path allows: ok
+base 11: max_uint: ok
+base 11: max_uint + 1: ok
+base 12: largest fast path value: ok
+base 12: one digit more than the fast path allows: ok
+base 12: max_uint: ok
+base 12: max_uint + 1: ok
+base 13: largest fast path value: ok
+base 13: one digit more than the fast path allows: ok
+base 13: max_uint: ok
+base 13: max_uint + 1: ok
+base 14: largest fast path value: ok
+base 14: one digit more than the fast path allows: ok
+base 14: max_uint: ok
+base 14: max_uint + 1: ok
+base 15: largest fast path value: ok
+base 15: one digit more than the fast path allows: ok
+base 15: max_uint: ok
+base 15: max_uint + 1: ok
+base 16: largest fast path value: ok
+base 16: one digit more than the fast path allows: ok
+base 16: max_uint: ok
+base 16: max_uint + 1: ok
+base 17: largest fast path value: ok
+base 17: one digit more than the fast path allows: ok
+base 17: max_uint: ok
+base 17: max_uint + 1: ok
+base 18: largest fast path value: ok
+base 18: one digit more than the fast path allows: ok
+base 18: max_uint: ok
+base 18: max_uint + 1: ok
+base 19: largest fast path value: ok
+base 19: one digit more than the fast path allows: ok
+base 19: max_uint: ok
+base 19: max_uint + 1: ok
+base 20: largest fast path value: ok
+base 20: one digit more than the fast path allows: ok
+base 20: max_uint: ok
+base 20: max_uint + 1: ok
+base 21: largest fast path value: ok
+base 21: one digit more than the fast path allows: ok
+base 21: max_uint: ok
+base 21: max_uint + 1: ok
+base 22: largest fast path value: ok
+base 22: one digit more than the fast path allows: ok
+base 22: max_uint: ok
+base 22: max_uint + 1: ok
+base 23: largest fast path value: ok
+base 23: one digit more than the fast path allows: ok
+base 23: max_uint: ok
+base 23: max_uint + 1: ok
+base 24: largest fast path value: ok
+base 24: one digit more than the fast path allows: ok
+base 24: max_uint: ok
+base 24: max_uint + 1: ok
+base 25: largest fast path value: ok
+base 25: one digit more than the fast path allows: ok
+base 25: max_uint: ok
+base 25: max_uint + 1: ok
+base 26: largest fast path value: ok
+base 26: one digit more than the fast path allows: ok
+base 26: max_uint: ok
+base 26: max_uint + 1: ok
+base 27: largest fast path value: ok
+base 27: one digit more than the fast path allows: ok
+base 27: max_uint: ok
+base 27: max_uint + 1: ok
+base 28: largest fast path value: ok
+base 28: one digit more than the fast path allows: ok
+base 28: max_uint: ok
+base 28: max_uint + 1: ok
+base 29: largest fast path value: ok
+base 29: one digit more than the fast path allows: ok
+base 29: max_uint: ok
+base 29: max_uint + 1: ok
+base 30: largest fast path value: ok
+base 30: one digit more than the fast path allows: ok
+base 30: max_uint: ok
+base 30: max_uint + 1: ok
+base 31: largest fast path value: ok
+base 31: one digit more than the fast path allows: ok
+base 31: max_uint: ok
+base 31: max_uint + 1: ok
+base 32: largest fast path value: ok
+base 32: one digit more than the fast path allows: ok
+base 32: max_uint: ok
+base 32: max_uint + 1: ok
+base 33: largest fast path value: ok
+base 33: one digit more than the fast path allows: ok
+base 33: max_uint: ok
+base 33: max_uint + 1: ok
+base 34: largest fast path value: ok
+base 34: one digit more than the fast path allows: ok
+base 34: max_uint: ok
+base 34: max_uint + 1: ok
+base 35: largest fast path value: ok
+base 35: one digit more than the fast path allows: ok
+base 35: max_uint: ok
+base 35: max_uint + 1: ok
+base 36: largest fast path value: ok
+base 36: one digit more than the fast path allows: ok
+base 36: max_uint: ok
+base 36: max_uint + 1: ok
diff --git a/tests/hard_coded/base_string_to_uint_bases.m
b/tests/hard_coded/base_string_to_uint_bases.m
new file mode 100644
index 000000000..a867ccca5
--- /dev/null
+++ b/tests/hard_coded/base_string_to_uint_bases.m
@@ -0,0 +1,165 @@
+%---------------------------------------------------------------------------%
+% vim: ts=4 sw=4 et ft=mercury
+%---------------------------------------------------------------------------%
+%
+% Check the boundary between the fast and checked paths in
+% string.base_string_to_uint/3, for every base from 2 to 36.
+%
+% For each base, we compute:
+%
+% - SafeDigits, the largest number of digits D such that Base^D - 1 =<
+% max_uint.
+%
+% - The largest string the fast path can accept, namely SafeDigits copies
+% of the digit Base - 1. Converting it must yield Base^SafeDigits - 1.
+%
+% - The same string with one more digit, which must fail.
+%
+% - max_uint itself, which for most bases takes the checked path, and
+% max_uint + 1, which must fail.
+%
+% Since this test checks the results of the conversions rather than printing
+% them, its expected output does not depend on the word size.
+%
+%---------------------------------------------------------------------------%
+
+:- module base_string_to_uint_bases.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module char.
+:- import_module int.
+:- import_module integer.
+:- import_module list.
+:- import_module string.
+:- import_module uint.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+ int.fold_up(test_base, 2, 36, !IO).
+
+:- pred test_base(int::in, io::di, io::uo) is det.
+
+test_base(Base, !IO) :-
+ SafeDigits = safe_digits(Base),
+ MaxDigit = det_base_int_to_digit(Base, Base - 1),
+
+ % The largest value the fast path can be given, and one digit more.
+ LargestFastStr = string.duplicate_char(MaxDigit, SafeDigits),
+ TooManyDigitsStr = string.duplicate_char(MaxDigit, SafeDigits + 1),
+ LargestFast = integer.pow(integer(Base), integer(SafeDigits))
+ - integer.one,
+
+ % max_uint, and the value just outside the range.
+ MaxUInt = integer.from_uint(max_uint),
+ MaxUIntStr = integer.to_base_string(MaxUInt, Base),
+ AboveMaxUIntStr = integer.to_base_string(MaxUInt + integer.one, Base),
+
+ Checks = [
+ % Description, string, expected result.
+ succeeds("largest fast path value",
+ LargestFastStr, LargestFast),
+ fails("one digit more than the fast path allows",
+ TooManyDigitsStr),
+ succeeds("max_uint", MaxUIntStr, MaxUInt),
+ fails("max_uint + 1", AboveMaxUIntStr)
+ ],
+ list.foldl(run_check(Base), Checks, !IO).
+
+%---------------------------------------------------------------------------%
+
+:- type check
+ ---> succeeds(
+ s_desc :: string,
+ s_string :: string,
+ s_expected :: integer
+ )
+ ; fails(
+ f_desc :: string,
+ f_string :: string
+ ).
+
+:- pred run_check(int::in, check::in, io::di, io::uo) is det.
+
+run_check(Base, Check, !IO) :-
+ (
+ Check = succeeds(Desc, Str, Expected),
+ ( if base_string_to_uint(Base, Str, UInt) then
+ ( if integer.from_uint(UInt) = Expected then
+ report_ok(Base, Desc, !IO)
+ else
+ report_bad(Base, Desc, Str,
+ "expected " ++ integer.to_string(Expected) ++
+ ", got " ++ integer.to_string(integer.from_uint(UInt)),
+ !IO)
+ )
+ else
+ report_bad(Base, Desc, Str, "conversion failed", !IO)
+ )
+ ;
+ Check = fails(Desc, Str),
+ ( if base_string_to_uint(Base, Str, UInt) then
+ report_bad(Base, Desc, Str,
+ "conversion succeeded, yielding " ++
+ integer.to_string(integer.from_uint(UInt)), !IO)
+ else
+ report_ok(Base, Desc, !IO)
+ )
+ ).
+
+:- pred report_ok(int::in, string::in, io::di, io::uo) is det.
+
+report_ok(Base, Desc, !IO) :-
+ io.format("base %d: %s: ok\n", [i(Base), s(Desc)], !IO).
+
+:- pred report_bad(int::in, string::in, string::in, string::in,
+ io::di, io::uo) is det.
+
+report_bad(Base, Desc, Str, Problem, !IO) :-
+ io.format("base %d: %s: FAILED: \"%s\": %s\n",
+ [i(Base), s(Desc), s(Str), s(Problem)], !IO).
+
+%---------------------------------------------------------------------------%
+
+ % safe_digits(Base) = SafeDigits:
+ %
+ % SafeDigits is the largest number of digits D such that
+ % Base^D - 1 =< max_uint, i.e. the largest number of base Base digits
+ % that a string can have while being guaranteed to denote a value
+ % that fits in a uint.
+ %
+ % We compute this rather than reading it out of string.m, so that this
+ % test cannot inherit an error from the tables there.
+ %
+:- func safe_digits(int) = int.
+
+safe_digits(Base) = SafeDigits :-
+ safe_digits_loop(integer(Base), integer.from_uint(max_uint),
+ integer.one, 0, SafeDigits).
+
+:- pred safe_digits_loop(integer::in, integer::in, integer::in, int::in,
+ int::out) is det.
+
+safe_digits_loop(Base, MaxUInt, Power0, Digits0, Digits) :-
+ % Power0 is Base^Digits0. Add another digit if the largest value with
+ % Digits0 + 1 digits, i.e. Base^(Digits0 + 1) - 1, still fits.
+ Power1 = Power0 * Base,
+ ( if Power1 - integer.one =< MaxUInt then
+ safe_digits_loop(Base, MaxUInt, Power1, Digits0 + 1, Digits)
+ else
+ Digits = Digits0
+ ).
+
+%---------------------------------------------------------------------------%
+:- end_module base_string_to_uint_bases.
+%---------------------------------------------------------------------------%
diff --git a/tests/hard_coded/string_to_uint_overflow.exp
b/tests/hard_coded/string_to_uint_overflow.exp
index fba5b659e..4f2eb433d 100644
--- a/tests/hard_coded/string_to_uint_overflow.exp
+++ b/tests/hard_coded/string_to_uint_overflow.exp
@@ -43,6 +43,28 @@ no
no
no
no
+### Fast path boundary values for 32-bit uints ###
+4294967295u
+no
+1073741823u
+no
+999999999u
+no
+4294967295u
+no
+2176782335u
+no
+### Fast path boundary values for 64-bit uints ###
+no
+no
+no
+no
+no
+no
+no
+no
+no
+no
### Overflow regression tests for 32-bit uints ###
no
no
diff --git a/tests/hard_coded/string_to_uint_overflow.exp2
b/tests/hard_coded/string_to_uint_overflow.exp2
index 10de7b8c3..6ff6c0618 100644
--- a/tests/hard_coded/string_to_uint_overflow.exp2
+++ b/tests/hard_coded/string_to_uint_overflow.exp2
@@ -43,6 +43,28 @@ no
18446744073709551614u
18446744073709551615u
no
+### Fast path boundary values for 32-bit uints ###
+4294967295u
+8589934591u
+1073741823u
+8589934591u
+999999999u
+9999999999u
+4294967295u
+68719476735u
+2176782335u
+78364164095u
+### Fast path boundary values for 64-bit uints ###
+18446744073709551615u
+no
+9223372036854775807u
+no
+9999999999999999999u
+no
+18446744073709551615u
+no
+4738381338321616895u
+no
### Overflow regression tests for 32-bit uints ###
5368709120u
5368709120u
diff --git a/tests/hard_coded/string_to_uint_overflow.m
b/tests/hard_coded/string_to_uint_overflow.m
index 448af604d..638780c03 100644
--- a/tests/hard_coded/string_to_uint_overflow.m
+++ b/tests/hard_coded/string_to_uint_overflow.m
@@ -97,6 +97,65 @@ main(!IO) :-
test(base_string_to_uint(36, "3W5E11264SGSF"), !IO),
test(base_string_to_uint(36, "3W5E11264SGSG"), !IO),
+ % The base_string_to_uint/3 fast path skips the overflow check entirely
+ % for strings that are short enough that no string of that many digits
+ % can overflow. The number of digits for which this holds depends on
+ % the base and the word size; see safe_uint_digits_for_word{32,64}_and_base
+ % in string.m.
+ %
+ % Note that the number of safe digits for a uint is not always the same as
+ % it is for an int of the same word size: in base 10 with 64-bit words, for
+ % example, 19 digits are safe for a uint but only 18 are safe for an int.
+ %
+ % The following paired tests check that the overflow behaviour is correct
+ % at the boundary between the fast and the checked paths. The first test
+ % in each pair is the largest value with the largest number of digits
+ % that the fast path accepts: as many copies of the digit Base - 1 as the
+ % table allows. If the table said one more digit is safe, then this value
+ % would overflow on the unchecked loop and be converted to a wrong answer.
+ % The second test in each pair adds that one more digit, which must take
+ % the checked path and be rejected.
+ %
+ % Note that in base 2 and base 16, max_uint consists entirely of the
+ % digit Base - 1, so for those bases the first test of each pair is
+ % max_uint itself, as tested in the boundary sections above.
+
+ line("Fast path boundary values for 32-bit uints", !IO),
+
+ test(base_string_to_uint(2, "11111111111111111111111111111111"), !IO),
+ test(base_string_to_uint(2, "111111111111111111111111111111111"), !IO),
+
+ test(base_string_to_uint(8, "7777777777"), !IO),
+ test(base_string_to_uint(8, "77777777777"), !IO),
+
+ test(base_string_to_uint(10, "999999999"), !IO),
+ test(base_string_to_uint(10, "9999999999"), !IO),
+
+ test(base_string_to_uint(16, "FFFFFFFF"), !IO),
+ test(base_string_to_uint(16, "FFFFFFFFF"), !IO),
+
+ test(base_string_to_uint(36, "ZZZZZZ"), !IO),
+ test(base_string_to_uint(36, "ZZZZZZZ"), !IO),
+
+ line("Fast path boundary values for 64-bit uints", !IO),
+
+ test(base_string_to_uint(2, "11111111111111111111111111111111" ++
+ "11111111111111111111111111111111"), !IO),
+ test(base_string_to_uint(2, "11111111111111111111111111111111" ++
+ "111111111111111111111111111111111"), !IO),
+
+ test(base_string_to_uint(8, "777777777777777777777"), !IO),
+ test(base_string_to_uint(8, "7777777777777777777777"), !IO),
+
+ test(base_string_to_uint(10, "9999999999999999999"), !IO),
+ test(base_string_to_uint(10, "99999999999999999999"), !IO),
+
+ test(base_string_to_uint(16, "FFFFFFFFFFFFFFFF"), !IO),
+ test(base_string_to_uint(16, "FFFFFFFFFFFFFFFFF"), !IO),
+
+ test(base_string_to_uint(36, "ZZZZZZZZZZZZ"), !IO),
+ test(base_string_to_uint(36, "ZZZZZZZZZZZZZ"), !IO),
+
% Regression tests for incorrect overflow check. Bases 10, 16, 8
% and 2 each exercise one of the specialised accumulator closures;
% base 36 exercises the generic accumulator that is shared by all
More information about the reviews
mailing list