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

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. Может быть кто знает еще какие нибудь методы преобразования чисел в строку?
- +28
- 24 августа 2012, 20:03
- neiver
- 3
Поставь кат после первого абзаца, статья заняла всю первую страницу сайта…
А за информацию спасибо, отличная подборка.
А за информацию спасибо, отличная подборка.
- ALPINE63rus
- 24 августа 2012, 20:16
- ↓
Я как-то так решил проблему
void convdata (long temp, int pos)
long temp = '0'
{
while (temp>=1000)
{
tempStr[0]++;
temp -= 1000;
}
while (temp>=100)
{
tempStr[1]++;
temp -= 100;
}
while (temp>=10)
{
tempStr[2]++;
temp -= 10;
}
while (temp>=1)
{
tempStr[3]++;
temp -= 1;
}
lcd_print(tempStr, 5, 5+pos);
}
Порой полезно такое поведение, что бы результат был с начала буффера. в основном не сложно добится копированием, но один из методов может делать сразу.
За статью спасибо.
6. Вычитание степенеи 10.Можно с начала пропустит нули, а потом формировать строку.
…
Цифры получаются сразу в нужном порядке, нужно только удалить ведущие нули.
// skip
char *ptr = buffer;
uint8_t i = 0;
while(value < pow10Table32[i]) i++;
while(i < 10)
{
uint32_t pow10 = pow10Table32[i++];
// skip
}
*ptr = 0;
return buffer;
//return ptr; // указатель на конец строки полезен для конкатенации
}
За статью спасибо.
Кстити этот вариант оказывается всреднем на 50 тактов быстрее чем тот, что у меня для 32-х разрядов и на 10 для 16-ти.
Я ожидал другого результата, т.к. вместо цикла со сравнением 8бит поставлен цикл с 32битным сравнением. Только после вашего поста сообразил, что там отбрасывается несколько итераций с вложенным циклом вычитания на малых значениях.
P.S.: На STM8 по идеи если писать не uint8_t i = 0; а int i = 0; можно ещё чуток в производительности поднять.
P.S.: На STM8 по идеи если писать не uint8_t i = 0; а int i = 0; можно ещё чуток в производительности поднять.
Хм, а мне кажется упадёт, вместо одного байта будут операции с двумя.
Но в любом случае для этого дела предусмотрены типы [u]int_fastN_t. Надо бы посмотреть как uint_fast8_t определён на STM8?
Но в любом случае для этого дела предусмотрены типы [u]int_fastN_t. Надо бы посмотреть как uint_fast8_t определён на STM8?
Особенность архетиктуры. Раньше я тоже дымал что упадет, и использовал 8 бит для индексов. но оказалось что мне было лучше использовать обычный int.
Там есть команда разадресации, которая получает 2-байтовые константный указатель и регистр со смещением. Для 8-битного смещения же команды нет. В итоге 8бит либо разворачивается в 16, либо выливается в арифметику.
Вообще оно раз на раз не приходится. На практике надо смотреть, если станет вопрос производительности.
Там есть команда разадресации, которая получает 2-байтовые константный указатель и регистр со смещением. Для 8-битного смещения же команды нет. В итоге 8бит либо разворачивается в 16, либо выливается в арифметику.
Вообще оно раз на раз не приходится. На практике надо смотреть, если станет вопрос производительности.
Что-то не получается повторить тест.
Ни utoa, ни ultoa не находятся:
Инклуды подключил:
Они может не реализованы в моём тулчайне(Yagarto)?
Ни utoa, ни ultoa не находятся:
error: 'utoa' was not declared in this scope
Инклуды подключил:
#include <stdlib.h>
#include <stdio.h>
Они может не реализованы в моём тулчайне(Yagarto)?
Превильно, их там нет. Это не стандартные функции, но иногда они есть. В avr-gcc, msp-gcc они есть, а в IAR их нет. Просто убрать их из теста.
>>Это не стандартные функции
Понял. спасибо.
>>а в IAR их нет
Ну, я не в ИАРе проьовал, а в Yagarto.
P.S. Два теста повторил — ul_to_dec (деление на 10) и utoa_cycle_sub.
Результат такой (в циклах):
ul_to_dec utoa_cycle_sub
IARAVR 56773 6600
CortexM3 2444 3738
Что называется «почувствуйте разницу».
Настройки оптимизации
AVR — High (speed)
ARM — -Os
Понял. спасибо.
>>а в IAR их нет
Ну, я не в ИАРе проьовал, а в Yagarto.
P.S. Два теста повторил — ul_to_dec (деление на 10) и utoa_cycle_sub.
Результат такой (в циклах):
ul_to_dec utoa_cycle_sub
IARAVR 56773 6600
CortexM3 2444 3738
Что называется «почувствуйте разницу».
Настройки оптимизации
AVR — High (speed)
ARM — -Os
Я имел в виду разницу не между делением и вычитанием, а между AVR и CortexM3 (не думаю что у CM0 по другому).
Недавно сравнивал на других тестах CM3 и АВР, и даже там где используются в основном байтовые операции(без аппаратных делений), всё равно Cortex-ы выигрывают на 10-20%.
Недавно сравнивал на других тестах CM3 и АВР, и даже там где используются в основном байтовые операции(без аппаратных делений), всё равно Cortex-ы выигрывают на 10-20%.
Дык, Открыли Америку. Кто ж спорит что кортоксы шустрее. При том, что авру приходится 32-битную арифметику эмулировать, а в кортексах она встроенная.
Или вы так хотели показать аврофилам что им пора задуматься о смене камня?
Или вы так хотели показать аврофилам что им пора задуматься о смене камня?
>>Дык, Открыли Америку.
Для меня это ново. Не знал что такая разница.
>>Или вы так хотели показать аврофилам
Да я сам — «аврофил», в смысле ни на чём кроме АВР не работал… И теперь вижу, нечего думать переходить или нет — ответ очевиден. Вопрос куда переходить, чтобы было так же надёжно, просто и дёшево.
Для меня это ново. Не знал что такая разница.
>>Или вы так хотели показать аврофилам
Да я сам — «аврофил», в смысле ни на чём кроме АВР не работал… И теперь вижу, нечего думать переходить или нет — ответ очевиден. Вопрос куда переходить, чтобы было так же надёжно, просто и дёшево.
Для таймингов (на АВР в том числе) таймеры существуют. Делать задержки через nop-ы — редковозникающая задача.
Проблема перехода ещё в том что не получается найти близкий к АВР по цене Cortex (не там ищу наверное). К примеру: ATXMEGA256D3 — 2,85 евро за 100 шт. Что из Cortex-ов есть близкое? На какой бы проц не посмотрел замеино дороже.
Проблема перехода ещё в том что не получается найти близкий к АВР по цене Cortex (не там ищу наверное). К примеру: ATXMEGA256D3 — 2,85 евро за 100 шт. Что из Cortex-ов есть близкое? На какой бы проц не посмотрел замеино дороже.
1-wire только ни кто на таймерах не делает почему-то, все нопы тулят.
и вопрос не только в нопах. те же прерывания. если авр ты видешь что тут прерывание, а тут ежё 10 команд, значит в этой точке мы будем через N мкс (V-USB на это в частности и полагается). В конвеерной же системе, да ещё с акселератором памяти в этой точке мы будем где-то через хрен-его-знает-как-карта-ляжет мкс. а этот цикл задержки может выполняться от 1 мс до 3мс в зависимости от фазы луны (это без учёта вытеснений). Касается не только С кода, но и асм.
и вопрос не только в нопах. те же прерывания. если авр ты видешь что тут прерывание, а тут ежё 10 команд, значит в этой точке мы будем через N мкс (V-USB на это в частности и полагается). В конвеерной же системе, да ещё с акселератором памяти в этой точке мы будем где-то через хрен-его-знает-как-карта-ляжет мкс. а этот цикл задержки может выполняться от 1 мс до 3мс в зависимости от фазы луны (это без учёта вытеснений). Касается не только С кода, но и асм.
Табличка «STM32» на самом деле для MSP430 — 32bit.
Алсо, почему sprintf на MSP430 — n/a, хотя размер указан?
Алсо, почему sprintf на MSP430 — n/a, хотя размер указан?
Вот блин, опять накосячил :)
sprintf на MSP430 не удалось протестировать — он не помещается в 2 кб памяти MSP43g2231, который уменя в Launchpad-е стоит.
sprintf на MSP430 не удалось протестировать — он не помещается в 2 кб памяти MSP43g2231, который уменя в Launchpad-е стоит.
Нет. Там еще вектора прерываний, startup, софтварный UART, калибровка DCO — так как нормальный кварц к нему не подключить. Где-то 100 байт не помещается.
UART мона выкинуть наверно, заменив каким-нить более кодоэкономичным способом вывода (быть может, через аппаратный дебаг — если, конечно, он не замедляет работу проца). Да и калибровка вроде не особо нужна — ты ж не в секундах время меряешь, а в циклах.
А то вполне можно и новый ланчпад купить, с камнями на 8 и 16 кб.
А то вполне можно и новый ланчпад купить, с камнями на 8 и 16 кб.
А не подскажите, как избавиться от ведущих нулей в «Вычитание степеней 10»?
И еще, можно ли этот метод переделать под дробные числа?
И еще, можно ли этот метод переделать под дробные числа?
Собственно они и так удаляются. Функция utoa_cycle_sub возвращает указатель на то место в буфере, где ведущие нули закончились и и начались значимые цифры. Этот указатель и нужно использовать в качестве резельтирующей строки.
Дело в том, что я пишу
мне он выводит 0000002457.
unsigned int i = 2457;
char myStr[] = "";
utoa_cycle_sub(i, myStr);
lcdPuts(myStr);//Отправляю строку на lcd
мне он выводит 0000002457.
Здесь две ошибки.
1. char myStr[] = "";
Это буфер на всего на 1 символ. Для 16-ти разрядного целого нужно как минимум 6 символов (включая завершающий 0), для 32-х — 11 символов.
2. utoa_cycle_sub возвращает то место, где лидирующие нули заканчиваются, это значение и надо использовать.
Надо так:
1. char myStr[] = "";
Это буфер на всего на 1 символ. Для 16-ти разрядного целого нужно как минимум 6 символов (включая завершающий 0), для 32-х — 11 символов.
2. utoa_cycle_sub возвращает то место, где лидирующие нули заканчиваются, это значение и надо использовать.
Надо так:
unsigned int i = 2457;
char buffer[11];
char *myStr = utoa_cycle_sub(i, buffer);
lcdPuts(myStr);//Отправляю строку на lcd
В функции «Деление на 10 сдвигами и сложениями»
// умножаем на 0.8
res.quot = n >> 1;
нужно прибавить 1 к начальному значению частного:
// умножаем на 0.8
res.quot = 1+ n >> 1;
. тогда корректировка не нужна
Тема хоть и древняя, но понекрофильствую всё же. Способ #5 не даёт корректные результаты в том виде, в котором они здесь приведены. Кто сомневается — проверьте 21dec и 2971215073dec. И причина ошибки проста: при умножении двух чисел разрядность результата равна сумме разрядов исходных величин. И при сдвиге тоже надо их не просто выкидывать, а оставлять в дробной части, которая как раз накопит недостающую разницу. Вот после полной обработки уже можно дробную часть выкинуть.
Становится понятен и «трюк компилятора GCC» — это магическое число и есть не что иное, как «0.1», интерпретированное как целое число. Если я прав, то это 0x19999999.
Придумал ещё способ, основанный на дробях или на рядах, уж не знаю, как правильней сказать. Если доберусь — набросаю материал (надо или нет — высказывайте). Но предварительные результаты без сохранения дробной части хуже.
neiver , протестируете, как опишу, если вы ещё на сайте присутсвуете?
Становится понятен и «трюк компилятора GCC» — это магическое число и есть не что иное, как «0.1», интерпретированное как целое число. Если я прав, то это 0x19999999.
Придумал ещё способ, основанный на дробях или на рядах, уж не знаю, как правильней сказать. Если доберусь — набросаю материал (надо или нет — высказывайте). Но предварительные результаты без сохранения дробной части хуже.
neiver , протестируете, как опишу, если вы ещё на сайте присутсвуете?
Протестировал 5 способ еще раз на всём диапазоне uint32_t. Отклонений не обнаружено.
codepad.org/AZcD1P5Y
codepad.org/AZcD1P5Y
Хм… Оказывается, я с первого раза не совсем понял алгоритм: вы не тетрады (нииблы, 4 бита) копируете, а удваиваете каждый раз количество используемых битов с накоплением суммы. Хитро!
Ошибку вы обходите автокоррекцией результата.
Добавив ещё один сдвиг на 32 и используя 64-битные значения получил тоже корректные значения. Похоже, ошибка округления компенсируется в результирующей сумме не вполне понятным для меня образом, потому как с отдельными тетрадами (здесь совпадает с периодом дроби (1100)bin), ошибка накапливается.
Спасибо большое за статью!
uint32_t out = n>>1; // first nibble
out += n>>2;
// [1100 ....] [.... ....] [.... ....] [.... ....]
out += out >> 4;
// [1100 1100] [.... ....] [.... ....] [.... ....]
out += out >> 8;
// [1100 1100] [1100 1100] [.... ....] [.... ....]
out += out >> 16;
// [1100 1100] [1100 1100] [1100 1100] [1100 1100]
Ошибку вы обходите автокоррекцией результата.
Добавив ещё один сдвиг на 32 и используя 64-битные значения получил тоже корректные значения. Похоже, ошибка округления компенсируется в результирующей сумме не вполне понятным для меня образом, потому как с отдельными тетрадами (здесь совпадает с периодом дроби (1100)bin), ошибка накапливается.
Спасибо большое за статью!
Поясню, про что я писал, а то чувствую себя паникёром. Для 52(dec) и ограничимся 8 разрядами.
Как выясняется, последовательность действий важна, то есть нельзя насдвигать, а потом результаты сдвигов складывать, надо именно с накоплением на каждом сдвиге. Вроде как эквивалентны должны быть, к.м.к.
/*
52 dec to 16-bit bin
0000000000110100 - value
....****....****
00011010.0ooooo - [1...]
00001101.00oooo - [11..]
00000000.110100 - [11..] [1... ]
00000000.0110100 - [11..] [11.. ]
00100111 - summ , >>3
00000100 - result is 4!!!
*/
Как выясняется, последовательность действий важна, то есть нельзя насдвигать, а потом результаты сдвигов складывать, надо именно с накоплением на каждом сдвиге. Вроде как эквивалентны должны быть, к.м.к.
6. Вычитание степеней 10.
На ассемблере и короче и быстрее, для черырезразрядного индикатора:
VALUE содержит исходное число.
.DEF TEMP = R16
.DEF BCD_0 = R7; цифра младшего разряда, BCD формат
.DEF BCD_1 = R8; цифра среднего разряда, BCD формат
.DEF BCD_2 = R9; цифра старшего разряда, BCD формат
;.MACRO DIGIT; двоично-десятичное преобразование
; LDI @1, -1
;DGT: INC @1
; SUBI TEMP, @0
; BRSH DGT
; SUBI TEMP, -@0
;.ENDM
LDIL BCD_2, -1
OP_1:
INC BCD_2
SUBI VALUEL, Low(1000)
SBCI VALUEH, High(1000)
BRSH OP_1
SUBI VALUEL, Low(-1000)
SBCI VALUEH, High(-1000)
LDIL BCD_1, -1
OP_2:
INC BCD_1
SUBI VALUEL, Low(100)
SBCI VALUEH, High(100)
BRSH OP_2
SUBI VALUEL, -100
LDIL BCD_0, -1
OP_3:
INC BCD_0
SUBI VALUEL, 10
BRSH OP_3
SUBI VALUEL, -10
Единицы остались в VALUE.
На ассемблере и короче и быстрее, для черырезразрядного индикатора:
VALUE содержит исходное число.
.DEF TEMP = R16
.DEF BCD_0 = R7; цифра младшего разряда, BCD формат
.DEF BCD_1 = R8; цифра среднего разряда, BCD формат
.DEF BCD_2 = R9; цифра старшего разряда, BCD формат
;.MACRO DIGIT; двоично-десятичное преобразование
; LDI @1, -1
;DGT: INC @1
; SUBI TEMP, @0
; BRSH DGT
; SUBI TEMP, -@0
;.ENDM
LDIL BCD_2, -1
OP_1:
INC BCD_2
SUBI VALUEL, Low(1000)
SBCI VALUEH, High(1000)
BRSH OP_1
SUBI VALUEL, Low(-1000)
SBCI VALUEH, High(-1000)
LDIL BCD_1, -1
OP_2:
INC BCD_1
SUBI VALUEL, Low(100)
SBCI VALUEH, High(100)
BRSH OP_2
SUBI VALUEL, -100
LDIL BCD_0, -1
OP_3:
INC BCD_0
SUBI VALUEL, 10
BRSH OP_3
SUBI VALUEL, -10
Единицы остались в VALUE.
Это можно сделать быстро:
Но лучше сделать правильно:
Первый вариант работает быстро, но не всегда. Это зависит от того, умеет ли целевой процессор обращаться к невыровненным данным. Также порядок байт в uint32_t имеет значение (Little Endian — Big Endian).
Второй вариант работает всегда и везде, но потенциально медленней, если компилятор не додумается его соптимизировать.
val_32 = *((uint32_t*)val_8);
Но лучше сделать правильно:
val_32 = (uint32_t)val_8[0] | ((uint32_t)val_8[1] << 8) |
((uint32_t)val_8[2] << 16) | ((uint32_t)val_8[3] << 24);
Первый вариант работает быстро, но не всегда. Это зависит от того, умеет ли целевой процессор обращаться к невыровненным данным. Также порядок байт в uint32_t имеет значение (Little Endian — Big Endian).
Второй вариант работает всегда и везде, но потенциально медленней, если компилятор не додумается его соптимизировать.
Лучшее Худшее Среднее
Сишный вариант 4121 4216 4150
Ассемблерный 1440 1497 1466
Сишный вариант никуда не годится — проигрывает по среднему даже делению.
У ассемблерного варианта тоже результат посредственный.
Сишный вариант 4121 4216 4150
Ассемблерный 1440 1497 1466
Сишный вариант никуда не годится — проигрывает по среднему даже делению.
У ассемблерного варианта тоже результат посредственный.
еще вариант с апп.делением:
uint32_t bin2bcd_U32_hwdiv(uint32_t data) {
uint32_t result = 0;
uint8_t result_shift = 0;
while (data > 0) {
result += (data % 10) << result_shift;
data /= 10;
result_shift += 4;
}
return result;
}
еще вариант — с использованием ldiv:
uint32_t bin2bcd_U32_ldiv(uint32_t data) {
static ldiv_t bin2bcd_ldiv_result;
bin2bcd_ldiv_result.quot = data;
uint32_t result = 0;
uint8_t result_bytes = 0;
while (bin2bcd_ldiv_result.quot > 0) {
bin2bcd_ldiv_result = ldiv(bin2bcd_ldiv_result.quot, 10);
result += bin2bcd_ldiv_result.rem << result_bytes;
result_bytes += 4;
}
return result;
}
да, посмотрел в листинг и ужаснулся — там деление софтовое, код вырос почти на 1кБ. Видимо авторы поленились оптимизировать stdlib под разные архитектуры
К сожалению, разработчики компиляторов, как свободных, так и комерческих, часто не оптимизируют стандартные библиотеки под разные архитектуры. Понадобилось мне недавно длинное деление 64 бита на 32 бита => 32 бита, на ядре Cortex-m3. Там есть аппаратное деление 32/32 бита, вроде должно облегчить задачу. Посмотрел, в arm-gcc используется полностью програмное деление 64/64 сдвигами и вычитаниями — очень медленно ~350-400 тактов. Посмотрел, как с этим дела в IAR и в Keil, там не на много лучше — порядка 250-300 тактов.
Я взял алгоритм длинного деления с использованием аппаратного деления 32/32 из нкижки Hacker's Delight, получилось 50-60 тактов.
Я взял алгоритм длинного деления с использованием аппаратного деления 32/32 из нкижки Hacker's Delight, получилось 50-60 тактов.
А разьве не проще всего взять цифру, прибавить к ней 31 в результате получим код символа, который можно уже использовать для вывода?
Неужели такой метод никто не использует?
Неужели такой метод никто не использует?
Дык именно это и делается абсолютно во всех методах, только я прибавляю не 31, а '0' — код симовла ноль, что есть одно и тоже. Но эти самые цифры, из большого двоичного числа нужно сначала как-то выделить — статья как раз об этом.
А, понял. Статью прочитал, но не сразу въехал.
Надо-же сначала на рязряды разбить.
Спасибо за статью. Очень информативно. Жаль, что для MSP нет сравнения использования методов sprintf и utoa.
Т.к. начинаучему проще использовать готовые конструкции, а контроллеры сейчас даже с ланчпадом идут с памятью, в которую такой код легко поместится.
Надо-же сначала на рязряды разбить.
Спасибо за статью. Очень информативно. Жаль, что для MSP нет сравнения использования методов sprintf и utoa.
Т.к. начинаучему проще использовать готовые конструкции, а контроллеры сейчас даже с ланчпадом идут с памятью, в которую такой код легко поместится.
Не совсем по теме, но вдруг кому пригодится. Для отладочной печати с минимальными издержками написал примитивную функцию перевода значения байта в шестнадцатеричный вид:
Думаю, в пояснениях не нуждается =).
#define USART_PRINT_BYTE(a_byte) \
do{ \
uint8_t tmp_char; \
USART_SEND_BYTE('x'); \
tmp_char = (a_byte>>4&0x0f)+0x30; \
USART_SEND_BYTE((tmp_char<0x3A)?tmp_char:(tmp_char+7));\
tmp_char = ((a_byte)&0x0f)+0x30; \
USART_SEND_BYTE((tmp_char<0x3A)?tmp_char:(tmp_char+7));\
}while(0);
Думаю, в пояснениях не нуждается =).
Обычно это делается командой вида x *= -1. Я думаю, компилятор должен это распознать и оптимизировать.
Нашел еще один способ преобразования, по моему его тут не разбирали:
При оптимизации -Os в среднем показывает результаты в 2 раза лучше на 10000 преобразованиях, чем utoa_builtin_div на STM32F051.
PS: Хотя при -O3 проигрывает на порядок.
#define MUL10( a ) (((a) << 3 ) + ((a) << 1 ))
void itoa10( int32_t a, char *s )
{
uint32_t b = a;
char *p;
if ( a < 0 )
{
*s++ = '-';
b = -a;
}
p = s;
do
{
uint32_t d = ( b * 0x6667 ) >> 18; // magic
*p++ = b - MUL10( d ) + '0';
b = d;
}
while ( b );
*p-- = '\0';
// inverse
while ( s < p )
*p-- ^= *s++ ^= *p ^= *s;
}
При оптимизации -Os в среднем показывает результаты в 2 раза лучше на 10000 преобразованиях, чем utoa_builtin_div на STM32F051.
PS: Хотя при -O3 проигрывает на порядок.
Простите за глупый вопрос!
buffer += 11;
*--buffer = 0;
Что это такое? И как его гуглить?
Пришел сюда из паскаля и Arduino, Arduino buffer подсвечивает, но тут arduino.ua/ru/prog/ инфы нет.
buffer += 11;
*--buffer = 0;
Что это такое? И как его гуглить?
Пришел сюда из паскаля и Arduino, Arduino buffer подсвечивает, но тут arduino.ua/ru/prog/ инфы нет.
Изучай адресную арифметику и работу с указателями в С.
На паскаль оно в лоб не переводится из-за отсутствия в оном адресной арифметики. Суть кода — кладем в 11-й символ буфера результата NULL (в С нуль-терминированные строки, а 32-битное целое в десятичном виде занимает не более 10 разрядов вместе со знаком) и передвигаем указатель на один символ влево (т.е. туда, куда будем класть разряд единиц).
На паскаль оно в лоб не переводится из-за отсутствия в оном адресной арифметики. Суть кода — кладем в 11-й символ буфера результата NULL (в С нуль-терминированные строки, а 32-битное целое в десятичном виде занимает не более 10 разрядов вместе со знаком) и передвигаем указатель на один символ влево (т.е. туда, куда будем класть разряд единиц).
Впрочем, нет. Указатель сдвигается на 12 символ, затем сдвигается влево (на 11-й) и уже туда кладется нулл, указатель продолжает указывать на него.
Спасибо.
Я «учился» работать с указателями, но уже такой возраст, что с трудом дается и легко забывается. Читаю примеры, делаю сам, «успокаиваюсь», когда код начинает работать и почти сразу забываю :)
Меня смутило, что буфер, вроде 12 байт, мы смещаемся на +11 а потом сразу -1
*--buffer = 0;
Это сначала уменьшить указатель, а потом по указателю переслать?
или
По указателю переслать, указатель уменьшить?
Я «учился» работать с указателями, но уже такой возраст, что с трудом дается и легко забывается. Читаю примеры, делаю сам, «успокаиваюсь», когда код начинает работать и почти сразу забываю :)
Меня смутило, что буфер, вроде 12 байт, мы смещаемся на +11 а потом сразу -1
*--buffer = 0;
Это сначала уменьшить указатель, а потом по указателю переслать?
или
По указателю переслать, указатель уменьшить?
VGA > На паскаль оно в лоб не переводится из-за отсутствия в оном адресной арифметики.
Все есть, непонятное утверждение…
Все есть, непонятное утверждение…
Все есть, непонятное утверждение…Да неужели? Ну переведи в лоб
buffer += 11;
*--buffer = 0;
Только двумя строчками (так что inc/dec отпадает) и без километровых приведений пойнтеров к интегерам и обратно.
Никуда инкдеки не отпадают. Точка с запятой в паскале существует. Какого требование, такого и решение.
Точка с запятой в паскале существует. Какого требование, такого и решение.ОК, более формально: двумя выражениями без километровых приведений и потери семантики оригинального кода. Потому как оригинальная фраза «в лоб на паскаль не переводится» подразумевает, что я не могу написать точно то же самое на знакомом veoramid'у языке, чтобы он понял, как эта конструкция работает.
Не обязательно в 2-х строчках, но так и условие именно так не стояло.Вот сперва неплохо бы разобраться, как там условие стоит, а потом утверждать «все есть». На дельфи можно написать аналогичный по поведению, но отличающийся семантически код, который ни разу не пояснит, как работает этот кусок на С и как понимать подобный код в других проектах на С.
Кроме того, указательной арифметики в паскале (по крайней мере, если брать распространенный диалект Delphi, что до оригинального паскаля — там указателей вообще нет в принципе) действительно нет, и «в лоб» код придется переписывать с приведением указателя к целочисленному типу, что вообще говоря не комильфо и охотно аукнется при портировании.
Что-то вроде этого:
Buffer := ^Char(Integer(Buffer) + 11); //buffer +=11
Buffer := ^Char(Integer(Buffer) - 1); //*--buffer = 0 часть первая
Buffer^ := 0; //*--buffer = 0 часть вторая
Но нормальные люди так не пишут и вместо манипуляций указателем заведут индекс, благо PChar в Delphi и с ним совместимых — массив.
Если нажать Ctrl-F и вбить туда обсуждаемый кусок кода, то можно найти и его контекст:
На дельфи это будет, соответственно, ^Char.
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;
}
На дельфи это будет, соответственно, ^Char.
Не знаю было ли, но для не высоких требований к точности очень быстрый результат дают:
temp = (ms * 205) >> 11; // 205/2048 близко к /10
и
(X * 655) >> 16 (деление на 100)
Или вот быстрое деление на 3:
x/3 = x * 21845 / 65536 = (x * 21845) >> 16
Недостаток — возможно переполнение, т.к. умножение делается первым. И это вынуждает переходить на большую разрядность. Но всё равно работает быстро.
temp = (ms * 205) >> 11; // 205/2048 близко к /10
и
(X * 655) >> 16 (деление на 100)
Или вот быстрое деление на 3:
x/3 = x * 21845 / 65536 = (x * 21845) >> 16
Недостаток — возможно переполнение, т.к. умножение делается первым. И это вынуждает переходить на большую разрядность. Но всё равно работает быстро.
Да… Топик старый, но актуальности не утрачивает.
Далее IMHO, так сказать.
Не вижу смысла в цифрах минимального и среднего времени исполнения. Так как если есть ограничение по времени, то худший случай должен удовлетворять ограничению. Ни среднее, ни минимальное время роли не играют.
Есть мои реализации на AVR ассемблере для подключения к Си (avr-gcc).
Первые два подписал соответственно алгоритмам использованным в этой статье, функционал и параметры полностью аналогичны.
Последние два представляют собой реализацию так называемого "Shift and Add-3 Algorithm". Он же используется в заметках AVR204. Конкретно эти реализации дают максимум 8 младших цифр в упакованном BCD.
Да, чуть не забыл. Набор чисел для тестирования в приложенной программе не покрывает все худшие случаи.
Далее IMHO, так сказать.
Не вижу смысла в цифрах минимального и среднего времени исполнения. Так как если есть ограничение по времени, то худший случай должен удовлетворять ограничению. Ни среднее, ни минимальное время роли не играют.
Есть мои реализации на AVR ассемблере для подключения к Си (avr-gcc).
Название время размер
(циклов) (байт)
uint32_to_ascii_fastdiv_asm 802 166
uint32_to_ascii_cycle_sub_asm 897 112
uint32_to_p8bcd_fast ~900 124
uint32_to_p8bcd_small ~1920 58
Первые два подписал соответственно алгоритмам использованным в этой статье, функционал и параметры полностью аналогичны.
Последние два представляют собой реализацию так называемого "Shift and Add-3 Algorithm". Он же используется в заметках AVR204. Конкретно эти реализации дают максимум 8 младших цифр в упакованном BCD.
Да, чуть не забыл. Набор чисел для тестирования в приложенной программе не покрывает все худшие случаи.
Комментарии (119)
RSS свернуть / развернуть