Преобразуем в строку. Часть 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. Может быть кто знает еще какие нибудь методы преобразования чисел в строку?