Распознать число в не-0-терминированной строке
Имеется строка, представленная в виде пары итераторов либо в виде указателя на char и длины. Особенность строки такова, что в ней
- может содержаться число, но только одно;
- может содержаться ошибочное значение (лишние символы, либо число с переполнением);
- может не быть ничего (
begin+1 = end).
Известные мне функции стандартной библиотеки C и C++, а именно atoi, std::stoi, sscanf требуют нуль-терминированную строку. Есть ли подобные стандартные функции в библиотеках C и C++? К этим функциям также предъявляются требования:
- функция не должна динамически выделять память в куче;
- функция не должна использовать VLA;
- функция не должна бросать исключений.
Хотя заявлено, что IAR EWARM 8.40.1 поддерживает C++17, но в нём не оказалось класса std::string_view и функции std::from_chars. Последняя выглядит как наиболее подходящая, хотя и нигде не написано, выделяет ли она для внутренних нужд память в куче.
Ответы (3 шт):
Автор решения: maestro
→ Ссылка
Вот моя реализация такой функции.
namespace Internal {
inline uint32_t MultiplyAccumulate(uint32_t m1, uint32_t m2, uint32_t add, bool &overflow)
{
uint32_t ovf = 0;
//В инструкции MUL набора инструкций thumb-2 поведение флага C не определено. Поскольку работаем с
//беззнаковыми числами, а слишком больших чисел не ожидается, можно заменить проверку переполнения флагом N.
//После операции сложения проверяются флаги S и V.
asm volatile ("B calc \n"
"ovf: mov %6, #1 \n"
"B fin \n"
"calc: \n"
"muls %0, %1, %2 \n"
"BMI ovf \n"
"adds %3, %4, %5 \n"
"BVS ovf \n"
"BCS ovf \n"
"fin:"
:: "r"(m1), "r"(m1), "r"(m2),
"r"(m1), "r"(m1), "r"(add),
"r"(ovf));
overflow = (bool)ovf;
return m1;
}
};
/// \brief Преобразование массива символов в число
/// \details Функция принимает массив в виде пары итераторов и
/// выполняет преобразование его в число.
/// \param begin Итератор начала массива
/// \param end Итератор конца массива
template<typename Iterator>
std::experimental::optional<uint32_t> ParseUint32(const Iterator begin, const Iterator end)
{
using value_type = typename std::iterator_traits<Iterator>::value_type;
auto rbegin = std::make_reverse_iterator(end);
auto rend = std::make_reverse_iterator(begin);
uint32_t result = 0;
int radix = 1;
bool overflow = 0;
for (auto it = rbegin; it != rend; it++, radix *= 10)
{
if (*it < '0' || *it > '9')
return std::experimental::nullopt;
uint32_t val = *it - '0';
result = Internal::MultiplyAccumulate(val, radix, result, overflow);
if (overflow)
{
return std::experimental::nullopt;
}
}
return result;
}
Для остальных типов можно реализовать аналогично.
Автор решения: Stanislav Volodarskiy
→ Ссылка
Из "сложных" операций понадобится умножение на десять, которое можно заменить на три сдвига и одно сложение:
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <stdbool.h>
bool parse_uint(int n, const char s[/* n */], unsigned *result) {
if (n <= 0) {
return false;
}
unsigned r = 0;
for (const char *p = s; p < s + n; ++p) {
if (!isdigit((unsigned char)*p)) {
return false;
}
if (r > UINT_MAX / 10u) {
return false;
}
r *= 10u;
const unsigned d = *p - '0';
if (r > UINT_MAX - d) {
return false;
}
r += d;
}
*result = r;
return true;
}
int main()
{
unsigned n;
assert(parse_uint(1, "0", &n));
assert(n == 0);
assert(parse_uint(1, "1", &n));
assert(n == 1);
assert(parse_uint(2, "10", &n));
assert(n == 10);
assert(parse_uint(10, "4294967295", &n));
assert(n == 4294967295);
assert(!parse_uint(10, "4294967296", &n));
assert(!parse_uint(11, "42949672950", &n));
assert(!parse_uint(3, "1_2", &n));
assert(!parse_uint(0, "0", &n));
return 0;
}
Автор решения: Qwertiy
→ Ссылка
⚠️ Судя по всему, это решение предполагает, что завершающий 0 всё же есть в области, чтение которой доступно без UB, но не обязательно сразу за концом подстроки.
Подробнее в комментариях к ответу.
sscanf всё умеет (прочем, переполнение int'а я проверять не стал): playground
#include <cstdio>
#include <iostream>
using namespace std;
void f(const char *s, const char *e)
{
int n = e-s-1;
if (n >= 0)
printf("'%.*s' (len %d) - ", n, s, n);
else
printf("(len %d) - ", n);
if (n < 0)
puts("invalid arguments");
else if (!n)
puts("empty input");
else
{
char format[32];
sprintf(format, "%%%dd%%n", n);
int x, m;
sscanf(s, format, &x, &(m=0));
if (n != m)
puts("invalid input");
else
printf("parsed as %d\n", x);
}
}
int main()
{
const char *s = "-12345-67890123456789";
f(s, s);
f(s, s+1);
f(s, s+2);
f(s, s+7);
f(s, s+8);
f(s, s+10);
f(s+1, s+2);
f(s+1, s+3);
f(s+1, s+7);
f(s+1, s+8);
f(s+1, s+10);
f(s+6, s+17);
f(s+6, s+18);
f(s+7, s+17);
f(s+7, s+18);
f(s+18, s+20);
f(s+18, s+21);
f(s+18, s+22);
f(s+18, s+23);
f(s+18, s+100000);
}
(len -1) - invalid arguments
'' (len 0) - empty input
'-' (len 1) - invalid input
'-12345' (len 6) - parsed as -12345
'-12345-' (len 7) - invalid input
'-12345-67' (len 9) - invalid input
'' (len 0) - empty input
'1' (len 1) - parsed as 1
'12345' (len 5) - parsed as 12345
'12345-' (len 6) - invalid input
'12345-67' (len 8) - invalid input
'-678901234' (len 10) - parsed as -678901234
'-6789012345' (len 11) - parsed as 1800922247
'678901234' (len 9) - parsed as 678901234
'6789012345' (len 10) - parsed as -1800922247
'7' (len 1) - parsed as 7
'78' (len 2) - parsed as 78
'789' (len 3) - parsed as 789
'789' (len 4) - invalid input
'789' (len 99981) - invalid input