[ViKo 1]

void decbin_5dgt(uint8_t* x, uchar8* buffer)

...

Должно быть uint16_t *x

[ssvSerge 0]

Другого наверно и быть не может.

Ух какое обсуждение получилось.

И циклы вам не нравятся и деления - страшны.

 

Табличные решения должны быть быстрее.

Экономия будет на циклах и на операциях деления.

 

Каждая операция деления заменяется двеятью сравнениями

в худшем случае. (9ю сравнениями для каждого десятичного

знакоместа).

 

Вопрос в том на какой таблице остановиться:

Если на десятичной, то таблица будет 36 слов (4знака * 9цифр).

Если на двоичной, то надо будет осуществлять двоично-десятичное сложение.

 

Двоичная таблица будет медленнее (скорее всего) если есть аппаратный

умножитель. А вот если его нет, то будет быстрее раз эдак в 200 чем

программное деление.

[ViKo 1]

Пролистал K&R второе издание от корки до корки, нашел практически такое же "гуано" на языке Элочки Людоедовой, как у меня, defunct, да и Goodefin недалеко от него ушел :)

Раздел 3.6 стр. 77. Те же деление и взятие остатка от деления. С учетом функции reverse - 2 цикла. (замечу в скобках, что книжка эта у меня появилась не так давно, до этого пользовался Шилдтом, но решил "продвинуться", так что любые совпадения - случайны :))

Еще приводится пример рекурсивного вызова на стр. 100, тоже не скажу, что блещет производительностью.

 

А табличный способ - самый быстрый. Но и самый жрущий память кода :) Это одна из крайностей. Найти бы еще самый компактный.

 

P.S. Кстати, автор топика не указал, для чего ему нужна функция itoa. А может, он под Windows пишет, и на производительность и компактность ему одинаково наплевать. :)

[aaarrr 69]

Найти бы еще самый компактный.

Компактность зависит от архитектуры - если нет аппаратного умножения/деления, самым компактным получится вычитание.

[sigmaN 0]

K&R не Ымбеддеры. А zltigo дело говорит вам. К чему там ещё и к словам русского языка придираться то было?

[ViKo 1]

Покопался в своих проектах, нашел преобразование для PIC16. 2 байта преобразовываются в 3 двоично-десятичных упакованных. От которых рукой подать до ASCII. Выдаю кусок из файла. Может кому-то покажется интересным.

 

...К чему там ещё и к словам русского языка придираться то было?

Исключительно с целью обучения навыкам культурного ведения диалогов при общении.

 

K&R не Ымбеддеры.

А badik , с которого все началось, эмбеддер? Он об этом не говорил.

Bin2BCD.zip

[GenaSPB 11]

А разве в коде Genadi видно, как у него реализована функция ldiv?

А какая разница, как? Между прочим, это функция стандартной библиотеки C. Вместе с div(). В реализации библиотеки от CodeVision отсутствует.

Обычно эти функции инлайнятся, если есть аппаратное деление. После аппаратного (или программного) деления и частное и остаток обычно присутствуют в регистрах процессора и структура ldiv_t (div_t) эти самые регистры впрямую и отображает. Так было на x86. На ARM и AVR не интересовался.

Изменено 25 июня, 2010 пользователем Genadi Zawidowski

[ViKo 1]

Между прочим, это функция стандартной библиотеки C.

Это я уже понял. Есть ли в Keil для Cortex-M3 не смотрел, надеюсь, есть. Тогда можно будет совместить деление и взятие остатка. Попробую на досуге.

upd. Попробовал. Есть такая функция. Однако после замены деления и взятия остатка на div() размер кода остался тем же. Подробнее буду разбираться позже.

Для ARM интересен вариант от aaarrr - из области трюков и фокусов. Реально полезный пример!

А для процессоров без умножений и делений - вычитание, а на ассемблере - с помощью команд двоично-десятичной коррекции (вот бы на C ее задействовать).

[dimka76 60]

Пролистал K&R второе издание от корки до корки

 

Чутарик не в тему. На форуме все ссылаются на эту книгу. Хотя Дэнис Ричи и является отцом-основателем языка, но это не означает, что он написал хорошую книгу. Мне, например, вот ЭТА очень понравилась.

 

Теперь по теме. Предлагаю глянуть, что ATMEL предлагает. А глядеть ЗДЕСЬ

 

[zltigo 1]

Пролистал K&R второе издание от корки до корки, нашел практически такое же "гуано" на языке Элочки Людоедовой

Не обижайте Кернигана :(. Проблема % / это одна частная проблема, которая на некоторых платформах и не проблема - настоятельно

рекомендую откомпилировать и посмотреть на результат работы с 32bit для:

Pentium

Сortex-M3

ARM7

ATmega

ATtiny

Ильфа тоже не обижайте - Эллочкина фамилия была Щукина, а "людоедкой" она была по причине того, что обходилась 30 словами. В чем ее превосходило даже племя людоедов Мумбо-Юмбо, чей словарный запас был 300 слов.

[ReAl 0]

После аппаратного (или программного) деления и частное и остаток обычно присутствуют в регистрах процессора и структура ldiv_t (div_t) эти самые регистры впрямую и отображает.

Вот именно. Просто всё-таки нужно представлять себе, во что выливается операция / или %, даже если пишешь для x86, как вообще деление реализуется.

 

Так было на x86. На ARM и AVR не интересовался.

Да так же. Только для AVR в библиотеке компилятора есть функции для деления, которые вызываются и для /, %, только при этом берётся половина результата. А div просто переназначено на эту функцию, возвращающую на регистрах обе части результата деления.

avr-gcc, stdlib.h

/* __divmodhi4 and __divmodsi4 from libgcc.a */
extern div_t div(int __num, int __denom) __asm__("__divmodhi4") __ATTR_CONST__;
extern ldiv_t ldiv(long __num, long __denom) __asm__("__divmodsi4") __ATTR_CONST__;

 

Так что применение div и тут в два раза сокращает затраты времени на деление по сравнению с раздельной парой /, %. Оптимизатор сам не видит, что можно было бы вызвать еление один раз.

Хотя для данной конкретной задачи для AVR другие способы побыстрее всё равно. Вариант с div, кажется, немного компактнее для случая, когда деление в программе всё равно есть и __divmod* всё равно линкуются.

[ViKo 1]

Не обижайте Кернигана ... настоятельно

рекомендую откомпилировать и посмотреть на результат работы с 32bit для:

...Сortex-M3...

А я для чего написал? STM32. Вот и вы меня "не обижайте". Хоть я и не Керниган.:)

Ильфа тоже не обижайте...

Написал, как помнилось. Не входит в сферу моих обязательных знаний, которые нужно периодически обновлять. Наверное, вы правы. Признаю!

[Johnny81 0]

В свое время написал такое:

/**
* "Указатель" на тетраду байта (обертка над указателем и признаком первая\вторая тетрада)
*/
struct TBCDLocation
{
byte *buf;
bool isFH;

TBCDLocation(byte *buf = 0, bool isFH = true) { this->buf = buf; this->isFH = isFH; }

TBCDLocation& operator++();
TBCDLocation& operator--();
TBCDLocation& operator+=(byte b );
TBCDLocation& operator-=(byte b );
uint_fast16_t operator-(const TBCDLocation& b ) const;
uint_fast16_t operator-(byte *b ) const;
TBCDLocation operator-(uint_fast8_t b ) const;
TBCDLocation operator+(uint_fast8_t b ) const;
bool operator==(const TBCDLocation& b ) const;
bool operator!=(const TBCDLocation& b ) const;
bool operator>(const TBCDLocation& b ) const;

void put(byte val);
void putAndInc(byte val);
void putAndDec(byte val);
byte get();
byte getAndInc();
byte getAndDec();
};

struct TBINtoBCDres
{
TBCDLocation loc; //!< Указатель на цифру перед первой результата
bool isOverflow : 1; //!< признак переполнения
bool isMinus : 1; //!< знак
TBINtoBCDres (TBCDLocation loc, bool isOverflow, bool isMinus) : loc(loc), isOverflow(isOverflow), isMinus(isMinus) {}
};

/**
* Преобразование двоичного числа произвольной длины в десятичное число произвольной длины
* (две цифры в байте). Результат выравнивается по правому краю.
* Заполнение ведущими нулями НЕ производится (в частности, при преобразовании числа 0
* целевой массив НЕ ИЗМЕНИТСЯ вообще и будет возвращен lsBCD).\n
* Если десяичное число не влезает в  указанное число разрядов,
* старшие разряды будут потеряны (т.е. 0xffff при преобразовании
* в три разряда даст 535)\n
* Двоичное число лежит младшим байтом вперед. Десятичное - старшей цифрой вперед.
*
* @param lsBCD     указатель на младшую цифру результата (самую последнюю)
* @param bin       указатель на младший байт двоичного числа (самый первый)
* @param halfbyteCnt
*                  число тетрад в двоичном числе
* @param bcdDigCnt число цифр в десятичном числе
*
* @return Указатель на цифру перед первой результата и признак переполнения
*/
TBINtoBCDres BINtoBCD(TBCDLocation lsBCD, void const *bin, uint_fast8_t halfbyteCnt, uint_fast8_t bcdDigCnt)
{
// используется сдвиговый алгоритм (полубайты выдвигаются из двоичного регистра и вдвигаются
// в десятичный, при этом произодится коррекция) Число итераций = (число байт) * (число дес цифр)
TBCDLocation msBCD = lsBCD;
bool isOverflow = false;
byte *pbin = ((byte*)bin) + (halfbyteCnt/2)-1;
bool binIsFH = true;
uint_fast8_t tmp;
while(halfbyteCnt--)
{
	uint_fast8_t sdv; // выдвинутый полубайт
	if (binIsFH)
	{
		tmp = *pbin--;
		sdv = HIGHPART(tmp);
		binIsFH = false;
	}
	else
	{
		sdv = LOWPART(tmp);
		binIsFH = true;
	}
	TBCDLocation bcd(lsBCD);
	while(true) // вдвигаем полубайт в десятичный регистр
	{
		bool isLim = msBCD == bcd;  // признак достижения старшей цифры
		if(isLim && sdv == 0) break;

		uint_fast8_t cur = isLim ? 0 : bcd.get();
     uint_fast8_t tmp = tableBINtoBCD[(cur<<4) | sdv];
		cur = HIGHPART(tmp);
		sdv = LOWPART(tmp);
		if (isLim)
		{
			if (cur || sdv)
			{
				if (bcdDigCnt)
				{
					bcd.putAndDec(cur);
					--bcdDigCnt;
					msBCD = bcd;
				}
				else
				{
					isOverflow = true;
					break;
				}
			}
			else
				break;
		}
		else
			bcd.putAndDec(cur);
	}
}
return TBINtoBCDres(msBCD, isOverflow, false);
}

 

Таблицу tableBINtoBCD (160 байт) и класс TBCDLocation могу дать, если кому интересно. Написано на С++, но можно переделать на С.

 

Когда написал, сравнил (на IAR АВР) с двумя алгоритмами - первый использовал деление, второй - вычитание. Цифр уже не помню, но оказался быстрее обоих. Кроме того работает с числами произвольной длины (несколько раз понадобилось :) ) и контролирует переполнение.

 

Конвертит не в АСКи, а в BCD - две десятичных цифры в байте - но потом легко преобразовать куда надо.

 

ЗЫ смайлы почему-то парсятся в коде...

[zltigo 1]

А я для чего написал?

Вы написали для чего-то на момент написания неназванного. Топикстартер, тоже не сказал для чего. Посему повторяю рекомендации откомпилировать и посмотреть на результат с / % для всех ранее помянутых ядер. Так-же напомню, что слово "гуано" относилось далеко не только к использованию / %.

 

 

[sonycman 0]

Оптимизатор сам не видит, что можно было бы вызвать деление один раз.

Да, я тоже замечал, что функция деления вызывается именно два раза (сначала остаток, потом деление), несмотря на то, что достаточно было бы единственного вызова.

 

Хотя это было, вроде бы, ещё на AVR. Не знаю, как это будет компилироваться под кортекс и RealView.