Преобразуем в строку. Часть 1. Целые числа.

Задача преобразования числа в строку стоит всегда, когда нужно отобразить числовые результаты работы программы. Процессоры у нас оперируют двоичными данными, человеку-же подавай десятичные числа. Собственно задача состоит в преобразовании базы числа. Какие для этого есть способы? Целью данной статьи является описание и сравнение максимального количества способов преобразования числа в строку. Задачу, естественно, рассматриваем с точки зрения реализации на микроконтроллерах, по этому размер и скорость имеют значение. Для простоты рассматриваем только без-знаковые 32-х и 16-ти разрядные числа (со знаком не намного сложнее).

1. sprintfПервое что приходит в голову это функция sprintf из стандартной библиотеки Си. Использовать её просто:
char buffer[12];
uint32_t value32 = 12345678ul;
sprintf(buffer, "%lu", value32 );

uint16_t value16 = 1234;
sprintf(buffer, "%u", value16 );
После чего в массиве buffer у нас лежит требуемая строка.
Но вот беда, sprintf это ведь функция форматированного вывода, которая много чего умеет и тянет за собой много другие функций стандартной библиотеки. Размер машинного кода при ее использовании увеличивается значительно. Например, даже минимальная версия sprintf из avr-libc (это то, что идет в составе WinAVR / AVR Toolchain) добавляет чуть менее 2 килобайт.
2. utoa, ultoaВ состав библиотек, поставляемых с компиляторами, часто включают функции преобразования числа в строку itoa, ltoa, utoa, ultoa. Вообще эти функции не стандартные, ног часто имеются в наличии и, в отличии от sprintf, не делают ничего лишнего.
char buffer[12];
uint32_t value32 = 12345678ul;
ultoa(value32, buffer, 10);

uint16_t value16 = 1234;
utoa(value16, buffer, 10);
3. Извлечение цифр делением на 10.Готовые стандартные и не очень способы посмотрели. Теперь пришло время свои велосипеды изобретать. Первый самый очевидный способ это конечно деление на 10 и вычисление остатка в цикле.
char * utoa_builtin_div(uint32_t value, char *buffer)
{
buffer += 11;
// 11 байт достаточно для десятичного представления 32-х байтного числа
// и завершающего нуля
*—buffer = 0;
do
{
*—buffer = value % 10 + ‘0’;
value /= 10;
}
while (value != 0);
return buffer;
}
Остаток от деления выдаёт нам десятичные цифры в обратном порядке, начиная с младшего, поэтому записываем из в буфер начиная с конца, чтоб потом не разворачивать полученную строку.
Всё вроде просто красиво, ничего лишнего, но есть одно но. Собственно деление, да еще и вычисление остатка. Если в процессоре нет аппаратного деления, то это очень медленно.
4. Извлечение цифр делением на 10 с помощью функции divМожет попробовать использовать стандартную функцию div, которая возвращает сразу частное и остаток?
char * utoa_divmod(uint32_t value, char *buffer)
{
buffer += 11;
*—buffer = 0;
do
{
ldiv_t res = ldiv(value, 10);
*—buffer = res.rem + ‘0’;
value = res.quot;
}
while (value != 0);
return buffer;
}
Но деление всё равно остается. К преимуществам этого и предыдущего метода можно отнести то, что они могут преобразовывать число в строку по любому основанию (если ёх чуть доработать), не обязательно 10.
5. Деление на 10 сдвигами и сложениями.Если у целевого процессора нет аппаратной поддержки 32-х разрядного деления, то предыдущие два метода будут довольно медленными. Деление на 10 можно заменить на серию сдвигов и сложений. Вдохновившись книжкой «Алгоритмические трюки для программистов» (она-же «Hacker’s delight»), берём оттуда функцию деления на 10 с помощью сдвигов и сложений, заменив имеющееся там умножение на 10 (оно тоже «дорогое», на AVR по крайней мере) также сдвигами и сложениями. Модифицируем ее, чтоб она возвращала и частное и остаток:
struct divmod10_t
{
uint32_t quot;
uint8_t rem;
};
inline static divmod10_t divmodu10(uint32_t n)
{
divmod10_t res;
// умножаем на 0.8
res.quot = n >> 1;
res.quot += res.quot >> 1;
res.quot += res.quot >> 4;
res.quot += res.quot >> 8;
res.quot += res.quot >> 16;
uint32_t qq = res.quot;
// делим на 8
res.quot >>= 3;
// вычисляем остаток
res.rem = uint8_t(n — ((res.quot << 1) + (qq & ~7ul)));
// корректируем остаток и частное
if(res.rem > 9)
{
res.rem -= 10;
res.quot++;
}
return res;
}
Выглядит страшно и непонятно, но на самом деле всё просто. Сначала умножаем исходное число на 0.8 или 0.1100 1100 1100 1100 1100 1100 1100 1100 в двоичном представлении. Очень удобно, что дробь периодическая и удалось обойтись всего пятью сдвигами и четырьмя сложениями. Далее делим то, что получилось на 8, сдвигая на 3 разряда вправо. Получается исходное число делённое на 10 с точностью до единицы из-за ошибок округления. После находим остаток умножая полученное частное на 10 и вычитая его из исходного числа. Если остаток больше 9, то корректируем его и частное.
Сама функция использующее «быстрое» деление не отличается по виду от своих предшественниц.
char * utoa_fast_div(uint32_t value, char *buffer)
{
buffer += 11;
*—buffer = 0;
do
{
divmod10_t res = divmodu10(value);
*—buffer = res.rem + ‘0’;
value = res.quot;
}
while (value != 0);
return buffer;
}
6. Вычитание степеней 10.Еще один популярный способ преобразования числа в строку, заключается в последовательном вычитании из исходного числа степеней 10, начиная с максимальной. Для этого понадобится таблица с этими степенями 10:
const uint32_t pow10Table32[]=
{
1000000000ul,
100000000ul,
10000000ul,
1000000ul,
100000ul,
10000ul,
1000ul,
100ul,
10ul,
1ul
};
40 байт размером. И сама функция:

static char *utoa_cycle_sub(uint32_t value, char *buffer)
{
if(value == 0)
{
buffer[0] = ‘0’;
buffer[1] = 0;
return buffer;
}
char *ptr = buffer;
uint8_t i = 0;
do
{
uint32_t pow10 = pow10Table32[i++];
uint8_t count = 0;
while(value >= pow10)
{
count ++;
value -= pow10;
}
*ptr++ = count + ‘0’;
}while(i < 10);
*ptr = 0;
// удаляем ведущие нули
while(buffer[0] == ‘0’) ++buffer;
return buffer;
}
Работает очень просто, пока число больше текущей степени 10 вычитаем эту степень 10 из числа и считаем сколько раз вычлось. Потом переходим на меньшую степень 10. И так пока не доберёмся до 1. Цифры получаются сразу в нужном порядке, нужно только удалить ведущие нули.

Методы на двоично-десятичных числах.Следующие три метода основаны на операциях с упакованными двоично-десятичными числами — binary coded decimals (BCD). В этом представлении каждая тетрада (4 бита) хранит одну десятичную цифру. В 32-х разрядной переменной можно таким образом хранить 8 десятичных цифр. В двоичном представлении в 2-х разрядной переменной 10 десятичных цифр. Поэтому эти методы дают урезанные результаты для чисел больше 99999999. Двоично-десятичные числа очень легко преобразуются в строку:
char *bcd_to_str(uint32_t bcd, char *buffer)
{
char *ptr = buffer + sizeof(bcd) * 2 — 1;
for(uint8_t i = 0; i < sizeof(bcd) * 2; i++)
{
*ptr— = uint8_t(bcd & 0x0f) + ‘0’;
bcd >>= 4;
}
buffer[sizeof(bcd) * 2] = 0;
while(buffer[0] == ‘0’) ++buffer;
return buffer;
}
Собственно из операций с BCD нам нужно сложение и умножение на 2, которое успешно заменяется сложением числа с самим собой. Поэтому нужно только сложение:
static uint32_t bcd_add(uint32_t a, uint32_t b)
{
/*1*/ uint32_t carry = b + 0x66666666ul;
/*2*/ carry ^= (a + carry) ^ a;
/*3*/ a += b;
/*4*/ carry &= 0x11111111ul;
/*5*/ carry >>= 2;
/*6*/ a += carry;
/*7*/ carry >>= 1;
/*8*/ a += carry;
return a;
}
Выглядит страшно и непонятно — опять какое-то хитрое побитовое колдунство. На самом деле, чтоб сложить два BCD нужно просто сложить их как обычные двоичные числа — строчка a += b. А потом к каждой тетраде значение которой оказалось больше 9 нужно добавить корректирующее число 6 с переносом бита в старшую тетраду. И к каждой тетраде из которой был перенос бита в старшую тетраду, нужно также добавить корректирующее число 6. Все остальные строки функции — как раз эта коррекция. В первых двух строках мы определяем все биты суммы a + b + 0x66666666ul, которые изменили своё значение из-за переноса бита из младшего разряда. В третей строка складываем наши два числа. В четвёртой — выделяем младшие биты переноса для каждой тетрады. В остальных — прибавляем 6 к тем тетрадам из которых был перенос бита. Вот так вот — без единого условного перехода.

7. Сложение степеней двойки.Первый способ, хорошо всем знакомый еще со школьных уроков информатики, — сложение десятичных представлений степеней двойки, соответствующих единичным битам в преобразуемом числе:
static char *utoa_bcd_add(uint32_t value, char *buffer)
{
uint32_t bcd=0, pow2 = 1;
while(value)
{
// если бит — единица
if(value & 1)
// добавляем текущею степень двойки
bcd = bcd_add(bcd, pow2);
// следующий бит
value >>= 1;
// следующая степень двойки
pow2 = bcd_add(pow2, pow2);
}
// преобразуем в строку
return bcd_to_str(bcd, buffer);
}
7. Сложение степеней двойки с таблицей.В предыдущем методе используется два сложения двоично-десятичных чисел. От одного из них можно избавиться беря степень двойки из таблицы:
const uint32_t pow2Table32[]=
{
0x00000001,
0x00000002,
0x00000004,
0x00000008,
0x00000016,
0x00000032,
0x00000064,
0x00000128,
0x00000256,
0x00000512,
0x00001024,
0x00002048,
0x00004096,
0x00008192,
0x00016384,
0x00032768,
0x00065536,
0x00131072,
0x00262144,
0x00524288,
0x01048576,
0x02097152,
0x04194304,
0x08388608,
0x16777216,
0x33554432,
0x67108864,
0,//0x134217728
0,// 0x268435456
0//0x4294967296
};

static char *utoa_bcd_table(uint32_t value, char *buffer)
{
uint32_t bcd=0;
for(uint8_t i=0; value; i++)
{
if(value & 1)
bcd = bcd_add(bcd, pow2Table32[i]);
value >>= 1;
}
return bcd_to_str(bcd, buffer);
}
Таблица содержит 30 элментов — 120 байт.
8. Horner’s methodВ этом методе на каждом шаге удваиваем накопленный десятичный результат, если старший бит двоичного числа единица, то добавляем к результату единицу, двоичное число при этом умножаем на 2 (сдвигаем на бит влево).
static char *utoa_bcd_horner(uint32_t value, char *buffer)
{
uint32_t bcd=0;
for(uint8_t i=0; i < sizeof(value) * 8; i++)
{
bcd = bcd_add(bcd, bcd);
if(value & 0x80000000)
{
bcd = bcd_add(bcd, 1);
}
value <<= 1;
}
return bcd_to_str(bcd, buffer);
}
Здесь уже две операции сложения BCD, но одна из них сложение с 1 и от неё одной можно избавиться.
static char *utoa_bcd_horner(uint32_t value, char *buffer)
{
uint32_t bcd=0, add;
for(uint8_t i=0; i < sizeof(value) * 8; i++)
{
add = !!(value & 0x80000000);
bcd = bcd_add(bcd + add, bcd);
value <<= 1;
}
return bcd_to_str(bcd, buffer);
}
При этом первый аргумент bcd_add может оказаться не корректным BCD, где младшая тетрада содержит цифру больше 9. Однако наша bcd_add это нормально прожевывает выдавая правильный результат. А вот если добавлять эту лишнюю единицу ко второму аргументы, то результат будет уже не правильным.
Количество итераций в цикле этого метода всегда будет равно разрядности числа, в отличии от предыдущих, где цикл закончится, как только в числе не останется единичных бит.

9. Извлечение цифр умножением на 10.Идея заключается в том, что десятичные цифры можно извлекать со стороны старших бит числа и использовать умножение на 10 для перехода к следующему десятичному разряду. Для этого придётся представить наше двоично число как дробную часть, мысленно перенести запятую на сколько-то разрядов влево, в нашем случае это будет 27. При этом число будет состоять из 2^-27 долей. Чтоб извлекать десятичные цифры эта дробь должна состоять из каких-то десятичных долей пусть это будет 10^-9. Его нужно для этого умножить на 2^-27/10^-9 = 1.34217728. После этого биты начиная с 27 разряда будут содержать старшую десятичную цифру. Но это если исходное число было меньше 2^27. Если оно было больше, то две цифры со значением не более 31. Это надо учесть. Еще один момент — это переполнение. Начиная с чисела 3199999999 ((2^32-1) / 1.34217728) у нас будет переполнение на 1 разряд, которое тоже надо учесть. А как-же всё-таки умножить челое число на 1.34217728 и без изпользования плавающей точки? Всё так-же сдвиками и сложениями. И так вот, что получилось:
char *utoa_fract(uint32_t value, char *buffer)
{
char *ptr = buffer;
*ptr++ = ‘0’;
if(value == 0)
{
buffer[1] = 0;
return buffer;
}
uint8_t correction = 0;
// если число больше 3199999999 то будет переполнение
if(value > 3199999999)
{
// корректируем старшую цифру сразу
buffer[0] = ‘3’;
// коррекция для предпоследней цифры
correction = 2;
}
// следующий цикл while делает тоже, что это выражение
//uint32_t t = value * 1.34217728;
// 1.34217728 = 1.01010111100110001110111000100011
uint32_t mask = 0b11000100011101110001100111101010;
uint32_t a = value;
uint32_t t = value + 1;
uint8_t a_fraction = 0;
// начальное значение дробной части для корректного округления
uint8_t t_fraction = 15;
do
{
// сдвигаем дробную часть на 1 влево
a_fraction >>= 1;
// переносим младший бит из целой части
if(a & 1) a_fraction |= 0x80;
// сдвигаем целую часть на 1 влево
a >>= 1;
if(mask & 1)
{
// прибавляем аккумулятор к результату
t += a;
// прибавляем аккумулятор к результату (дробная часть)
t_fraction += a_fraction;
// если дробная часть переполнилась, переносим бит в челую
if(t_fraction < a_fraction) t++;
}
mask >>= 1;
}while(a_fraction || a);

for(uint8_t i=0; i < 9; i++)
{
// извлекаем десятичную цифру
uint8_t hh = uint8_t(t >> 24);
*ptr++ = (hh >> 3) + ‘0’;
// очищаем ее биты
t &=0x07ffffff;
// умножаем на 10
t <<=1;
t+=t<<2;
}
ptr[0] = 0;
// коррекция двух старших цифр при переполнении
buffer[1] += correction;
while(buffer[1] > ‘9’)
{
buffer[1] -= 10;
buffer[0]++;
}
// удаляем ведущие нули
while(buffer[0] == ‘0’) ++buffer;
return buffer;
}
Как ни странно но это работает. Если кто-нибудь видел этот способ раньше — скажите мне, а то я могу претендовать на авторство.
Как видно при умножении пришлось использовать 40-ка битную арифметику — дополнительный байт для дробной части. Если дробную часть отбросить и использовать 32-х битную арифметику, то возникают ошибки округления, который достигают 7 для больших чисел. К сожалению в языке Си нет доступа к биту переноса и по этому перенос в/из дробной части пришлось организовывать вручную. Для эффективного использования бита переноса можно использовать ассемблерные вставки. Поскольку первая тестируемая платформа у нас будет avr-gcc, для него их и напишем, чисто ради спортивного интереса. С ними цикл умножения будет выглядеть так:
do
{
asm volatile (
"lsr %D0 n"
"ror %C0 n"
"ror %B0 n"
"ror %A0 n"
:"+r" (a)
);
asm volatile (
"ror %A0 n"
:"+r" (a_fraction)
);
if(mask & 1)
{
asm volatile (
"add %A0, %A1 n"
:"+r" (t_fraction) // output
:"r" (a_fraction) // input
);
asm volatile (
"adc %A0, %A1 n"
"adc %B0, %B1 n"
"adc %C0, %C1 n"
"adc %D0, %D1 n"
:"+r" (t) // output
: "r" (a) // input
);
}
mask >>= 1;
}while(a_fraction || a);

БенчмаркТеперь собственно та часть ради которой всё затевалось — сравнение скорости работы. Первой испытанной платформой будет будет AVR с использованием компилятора GCC.
Для методов разных типов время работы будет зависеть от разных факторов, например для методов основанных на делении на 10 время будет зависеть в большей степени от количества десятичных цифр, о есть от абсолютной величины числа и очень мало от самих этих цифр. Вычитание степеней 10 в цикле будет тем быстрее работать чем меньше сумма десятичных цифр составляющих число. То есть 1000000 обработается гораздо быстрее чем 999999. Методы основанные на двоично-десятичных числах будут быстрее работать если в исходном числе мало единичных бит — быстрее всего со степенями двойки. Время работы последнего метода будет зависеть только от абсолютной величины преобразуемого числа, но в меньшей степени чем методы с делением на 10. Итак в наборе для тестирования должны быть маленькие чила, большие числа, степени двойки, степени десяти, числа где много девяток.
Всякие тесты для AVR удобно проводить на симуляторе Simulavr — не нужно никакого железа, и многочисленных перепрошивок.
Для замера времени выполнения наших функций воспользуемся 16-ти разрядным таймером, тикающем на частоте ядра. Вывод на консоль через отладочный порт эмулятора. Оптимизация кода максимальная по скорости.
Вот что получилось в результате для 32-х разрядных чисел:

* после плюса размер зависимостей — таблицы или функции деления
** в скобках указаны результаты для варианта с ассемблерными вставками.

Лидирует в этом бенчмарке с не большим отрывом метод на быстром делении на 10 сдвигами и сложениями. К нему близко подобралось вычитание степеней 10. Следом метод с умножением на 10. методы с честным делением (включая utoa), как и ожидалось, самые медленные, особенно тот, что использует функцию ldiv, но и самые компактные. Время выполнения метода Хорнера практически не зависит от конвертируемого числа. sprintf работает относительно быстро, по сравнению с utoa. И не удивительно — у неё внутри используется метод похожий на utoa_fast_div, но накладные на разбор форматной строки и медленный вывод в буффер через fputc дают о себе знать.

UPDATE.
Результат для 16-х разрядных чисел:

Здесь опять с заметным преимуществом лидирует быстрое деление сдвигами/сложениями. Худший результат теперь у sprintf, ведь внутри она всё равно использует 32- разрядные числа.
UPDATE #2. Результаты для MSP430.
Результат для 16-х разрядных чисел:

Поскольку кроме MSP430 Launcpad-а с камнем MSP430G2231 других MSP430 у меня нет, тестировать пришлось на нем. Все функции разумеется в него не помещаются, по этому заливаются и тестируются по одной с помощью скрипта.
Как видно честное деление здесь почти вдвое медленнее чем у AVR.
UPDETE #3
Результаты для STM32.
Обсуждение результатовАутсайдером везде является функция использующая библиотечную функцию деления div. Несмотря на то, что она возвращает за один вызов и остаток и частное от деления, даже на STM32 аппаратным делением, она реализована программно и работает очень медленно. Очевидно этот способ использовать не стоит. Однако функция использующая встроенный оператор деления utoa_builtin_div, плетущаяся в конце на AVR и MSP430, на STM32 — в лидерах. Ничего удивительного, ведь в Cortex M3 есть аппаратное деление скажут многие, и будут не совсем правы — деление-то там есть, но оно не такое уж и быстрое (в скобках для utoa_builtin_div указано время, если заставить компилятор сгенерировать честное деление). Дело в том, что хитрый GCC при делении на константу использует хитрый трюк — заменяет деление на умножение на константу такую, что старшие 32 бита в 64 разрядном произведении, содержат исходное делимое, делённое на 10.
*—buffer = value % 10 + ‘0’;
8000718: f6cc 43cc movt r3, #52428 ; 0xcccc
800071c: fba3 4200 umull r4, r2, r3, r0
8000720: 08d2 lsrs r2, r2, #3
8000722: eb02 0482 add.w r4, r2, r2, lsl #2
8000726: eba0 0044 sub.w r0, r0, r4, lsl #1
800072a: f100 0430 add.w r4, r0, #48 ; 0x30
800072e: f801 4d01 strb.w r4, [r1, #-1]!

Этот код эквивалентен примерно следующему:
uint32_t tmp = value;
value = (uint64_t(value) * 0xcccccccd) >> 32;
*—buffer = tmp — ((value << 1) + (value << 3))+0x30;
Такой способ тоже описан в книжке «Алгоритмические трюки для программистов». Однако на AVR и MSP430 этот номер не пройдёт — там умножение 32*32 => 64 работает неприлично долго, дольше честного деления.
Еще utoa_builtin_div всегда имеет минимальный размер.
Всегда хороший, а зачастую лучший результат даёт деление на 10 сдвигами и сложениями utoa_fast_div. Это практически безусловный лидер по скорости и часто имеет вполне скромный размер. Этот метод всегда удачный выбор.
Любимое многими вычитание степеней десяти utoa_cycle_sub по размеру вместе с таблицей примерно совпадает сutoa_fast_div, но всегда немного уступает по скорости. Вобщем, тоже не плохой выбор.
Методы основанные на двоично десятичных числах работают не очень быстро, имеют не самый маленький размер и к тому-же выдают только 8 цифр результата (в моей реализации, можно получить все 10 цифр, но будет еще медленнее). Их лучше использовать не для преобразования двоичных чисел в строки, а для преобразования двоичных чисел в упакованные двоично десятичные, для последующей работы сними.
Особняком стоит метод с умножением на 10 utoa_fract. Он не выглядит очень привлекательным по среднему времени, однако его худшее время часто оказывается меньше, чем худшее время лидеров. У этого метода разница между лучшим и худшим относительно небольшая — он работает стабильно.

UPDATE.
Нашел еще один интересный и очень быстрый метод. Вот Вот здесь.
char* shift_and_mul_utoa16(uint16_t n, char *buffer)
{
uint8_t d4, d3, d2, d1, q, d0;

d1 = (n>>4) & 0xF;
d2 = (n>>8) & 0xF;
d3 = (n>>12) & 0xF;

d0 = 6*(d3 + d2 + d1) + (n & 0xF);
q = (d0 * 0xCD) >> 11;
d0 = d0 — 10*q;

d1 = q + 9*d3 + 5*d2 + d1;
q = (d1 * 0xCD) >> 11;
d1 = d1 — 10*q;

d2 = q + 2*d2;
q = (d2 * 0x1A) >> 8;
d2 = d2 — 10*q;

d3 = q + 4*d3;
d4 = (d3 * 0x1A) >> 8;
d3 = d3 — 10*d4;

char *ptr = buffer;
*ptr++ = ( d4 + ‘0’ );
*ptr++ = ( d3 + ‘0’ );
*ptr++ = ( d2 + ‘0’ );
*ptr++ = ( d1 + ‘0’ );
*ptr++ = ( d0 + ‘0’ );
*ptr = 0;

while(buffer[0] == ‘0’) ++buffer;
return buffer;
}
Описание того, как это работает по ссылке выше на английском. К сожалению, корректные результаты этот метод выдаёт только для 15-ти битных значений, зато очень быстро:
для AVR лучшее время — 133 такта, худшее — 167, среднее — 146.

Coming next.Часть 2. Фиксированная и плавающая точка.

PS. Может быть кто знает еще какие нибудь методы преобразования чисел в строку?
Источник

Оставить комментарий

Вы можете использовать следующие теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>