Binary to BCD conversion algorithms (benchmark on AVR)

avr.cpp

//
// Simple binary to BCD conversion algorithms
// http://blog.malcom.pl/2017/konwersja-liczb-binarnych-do-kodu-bcd-avr.html
//
// Copyright (C) 2017 Marcin 'Malcom' Malich <me@malcom.pl>
// Released under the MIT License.
//
// This file contains simple benhmark for AVR microcontrollers
//

#include <stdio.h>
#include <avr/io.h>

#define AVR_TICK_COUNTER_USE_32BIT 1
#include "avr-tick-counter.h"

#include "bcd.h"

void UartInit() {

	constexpr auto Baud = 9600;
	constexpr auto BaudRate = (F_CPU) / (Baud * 16UL) - 1;

	UBRRH = (BaudRate >> 8);
	UBRRL = BaudRate;

	UCSRB |= (1 << TXEN);
	UCSRC |= (1 << URSEL) | (1 << UCSZ0) | (1 << UCSZ1);
}

void UartSend(char c) {

	while (!(UCSRA & (1 << UDRE)))
		;

	UDR = c;
}


void UartPrint(const char* format, ...) {

	char buf[128];

	va_list args;
	va_start(args, format);
	int n = vsnprintf(buf, sizeof(buf), format, args);
	va_end(args);

	const char* b = buf;
	const char* e = buf + n;
	
	while (b != e)
		UartSend(*b++);

}

#define UartPrintLn(...) \
	UartPrint(__VA_ARGS__);	\
	UartSend('\r');			\
	UartSend('\n');			\


template<typename T>
struct TestData { };

#define DefineData(T, ...) \
	template<>												\
	struct TestData<T> {									\
		constexpr static const char* name = #T;				\
		constexpr static const T data[] = { __VA_ARGS__ };	\
	};														\
	constexpr const T TestData<T>::data[]					\


template<typename T>
constexpr auto Max = IntegralTraits<T>::Max;

#define DefineDataAproxMax(T) \
	DefineData(T, 0, Max<T>/16, Max<T>/8, Max<T>/4, Max<T>/2, Max<T>)

DefineDataAproxMax(uint8_t);
DefineDataAproxMax(uint16_t);
DefineDataAproxMax(uint32_t);

template<typename T>
void PrintTestData() {

	typedef TestData<T> Data;

	UartPrint("  %s", Data::name);
	for (const uint32_t& bin : Data::data)
		UartPrint("\t%lu", bin);
	UartPrintLn("");
}

#define PrintData() \
	UartPrintLn("Test data:");	\
	PrintTestData<uint8_t>();	\
	PrintTestData<uint16_t>();	\
	PrintTestData<uint32_t>();	\
	UartPrintLn("");

template<typename T, typename F>
void TestFunction(F func) {

	typedef TestData<T> Data;

	UartPrint("  %s", Data::name);

	uint8_t bcd[Digits<T>];
	for (const auto& bin : Data::data) {

		ResetTickCounter();
		StartTickCounter();
		func(bin, bcd, sizeof(bcd));
		StopTickCounter();

		UartPrint("\t%lu", GetTicks());
	}

	UartPrintLn("");
}

#define Test(func) \
	UartPrintLn(#func":");					\
	TestFunction<uint8_t>(func<uint8_t>);	\
	TestFunction<uint16_t>(func<uint16_t>);	\
	TestFunction<uint32_t>(func<uint32_t>);	\
	UartPrintLn("");						\



// Emulate hardware ALU div by mul for approximation.
// It's only for calc used cycles when ALU has hardware div!
template<typename T>
struct HardwareDiv {

	static T div10(T n, uint8_t& r) {
		r = n * 10;
		return n * r;
	}

};

template<typename T>
inline void HardwareDivBCD(T n, uint8_t* digits, size_t count) {
	return DivideBCD<HardwareDiv, T>(n, digits, count);
}


int main() {

	UartInit();
	PrintData();

	UartPrintLn("Starting test...");
	
	Test(HardwareDivBCD);

	Test(BruteForceBCD);
	Test(DoubleDabbleBCD);
	Test(NativeDivBCD);
	Test(ApproxMulBCD);
	Test(ApproxShiftBCD);

	UartPrintLn("Stop test...");

	while (true)
		;

	return 0;
}

bcd.h

//
// Simple binary to BCD conversion algorithms
// http://blog.malcom.pl/2017/konwersja-liczb-binarnych-do-kodu-bcd-avr.html
//
// Copyright (C) 2017 Marcin 'Malcom' Malich <me@malcom.pl>
// Released under the MIT License.
//

#ifndef BCD_ALGORITHM_IMPL_H
#define BCD_ALGORITHM_IMPL_H


// Definition of traits and helpers used by algorithms

#ifdef ENV_WITH_STL_AND_STUFF

#include <algorithm>
#include <type_traits>
#include <limits>

#include <boost/integer.hpp>

using std::max;
using std::min;

template<typename T>
struct IntegralTraits {

	using UnsignedType = typename std::make_unsigned<T>::type;

	static constexpr T Min = std::numeric_limits<UnsignedType>::min();
	static constexpr T Max = std::numeric_limits<UnsignedType>::max();

	static constexpr T Bits = std::numeric_limits<UnsignedType>::digits;
	static constexpr T Digits = std::numeric_limits<UnsignedType>::digits10 + 1;

	using BiggerType = typename boost::uint_t<Bits + 1>::least;

};

#else

#include <stdint.h>
#include <limits.h>

template<class T>
inline constexpr const T max(const T& left, const T& right) {
	return left < right ? right : left;
}

template<class T>
inline constexpr const T min(const T& left, const T& right) {
	return  right < left ? right : left;
}


template<int Least>
struct RequiredBits {

	enum {
		value =
			Least <=  8 ? 8 :
			Least <= 16 ? 16 :
			Least <= 32 ? 32 :
					 64
	};
};

template<int bits> struct Integer;
template<> struct Integer <8> { typedef uint8_t  type; };
template<> struct Integer<16> { typedef uint16_t type; };
template<> struct Integer<32> { typedef uint32_t type; };
template<> struct Integer<64> { typedef uint64_t type; };

// valid for unsigned only!
template<typename T>
struct IntegralTraits {

	static constexpr T Min = 0;
	static constexpr T Max = static_cast<T>(~0);

	static constexpr T Bits = CHAR_BIT * sizeof(T);
	static constexpr T Digits = (CHAR_BIT * sizeof(T) * 301L / 1000) + 1;

	using BiggerType = typename Integer<RequiredBits<Bits + 1>::value>::type;

};

#endif

// helpers
template<typename T>
constexpr size_t Bits = IntegralTraits<T>::Bits;

template<typename T>
constexpr size_t Digits = IntegralTraits<T>::Digits;


//
// Brute force algorithm 
//

template<typename T>
void BruteForceBCD(T n, uint8_t* digits, size_t count) {

	// look-up table for decimal points
	static const uint32_t SubVal[] = {
		1,
		10,
		100,
		1000,
		10000,
		100000,
		1000000,
		10000000,
		100000000,
		1000000000,
	};

	constexpr uint32_t SubValSize = sizeof(SubVal) / sizeof(SubVal[0]);
	static_assert(SubValSize == Digits<uint32_t>, "incorrect SubVal content for uint32_t");

	count = ::min<size_t>(count, Digits<uint32_t>);

	for (size_t i = count - 1; i > 0; i--) {

		uint8_t& dig = digits[i];
		const T& sub = SubVal[i];

		dig = 0;
		while (n >= sub) {
			n -= sub;
			dig += 1;
		}
	}

	digits[0] = static_cast<uint8_t>(n);
}


//
// Double-Dabble (Shift and Add-3) algorithm
//

template<typename T>
void DoubleDabbleBCD(T n, uint8_t* digits, size_t count) {

	count = ::min<size_t>(count, Digits<uint32_t>);
	size_t smax = count > 2 ? 2 : 0;	// speed optimization

	for (size_t i = 0; i < count; ++i)
		digits[i] = 0;

	for (size_t i = Bits<T>; i > 0; --i) {

		// This bit will be shifted in on the right.
		int shifted_in = (n & (1 << (i - 1))) ? 1 : 0;
		
		// Add 3 everywhere that digits[k] >= 5.
		for (size_t j = 0; j < count; ++j)
			digits[j] += (digits[j] >= 5) ? 3 : 0;

		// Shift digits to the left by one position.
		if (digits[smax] >= 8 && smax < count)
			smax += 1;
		for (size_t j = count - 1; j > 0; --j) {
			digits[j] <<= 1;
			digits[j] &= 0xF;
			digits[j] |= (digits[j - 1] >= 8);
		}

		// Shift in the new bit from arr.
		digits[0] <<= 1;
		digits[0] &= 0xF;
		digits[0] |= shifted_in;
	}

}


//
// Algorithm based on divide by 10
//

template<template<typename> class F, typename T>
void DivideBCD(T n, uint8_t* digits, size_t count) {

	for (size_t i = 0; i < count; i++)
		n = F<T>::div10(n, digits[i]);

}


//
// Version based on native divide operation
//

template<typename T>
struct NativeDiv {

	static T div10(T n, uint8_t& r) {
		r = n % 10;
		return n / 10;
	}

};

template<typename T>
inline void NativeDivBCD(T n, uint8_t* digits, size_t count) {
	return DivideBCD<NativeDiv, T>(n, digits, count);
}


//
// Divide emulated by aproximation and reciprocal multiplication
// Version used native multiplication
//

template<typename T>
struct ApproxMul {

	static T div10(T n, uint8_t& r) {

		using Trait = IntegralTraits<T>;
		constexpr T Trunc = Trait::Max / 10;

		typename Trait::BiggerType x = n;
		T q = (x * Trunc) >> Trait::Bits;

		r = n - 10 * q;
		if (r >= 10) {
			q += 1;
			r -= 10;
		}

		return q;
	}

};

template<typename T>
inline void ApproxMulBCD(T n, uint8_t* digits, size_t count) {
	return DivideBCD<ApproxMul, T>(n, digits, count);
}


//
// Divide emulated by aproximation and reciprocal multiplication
// Version used shift operation
//

template<size_t Bits, size_t End = 0, bool stop = Bits == End>
struct shift_for {
	template<typename V>
	static V iterate(V q) {
		V x = shift_for<Bits / 2, End>::iterate(q);
		return (x >> Bits) + x;
	}
};

template<size_t Bits, size_t End>
struct shift_for<Bits, End, true> {
	template<typename V>
	static V iterate(V q) {
		return q;
	}
};


template<typename T>
struct ApproxShift {

	static T div10(T n, uint8_t& r) {
		
		using Trait = IntegralTraits<T>;
		
		typename Trait::BiggerType x = n;
		x = ((x >> 1) + x) >> 1;

	//	for (size_t i = 4; i <= Trait::Bits / 2; i <<= 1)
	//		x = ((x >> i) + x);

		// unrooling in compile-time
		x = shift_for<Trait::Bits / 2, 2>::iterate(x);

		x = x >> 3;
		T q = static_cast<T>(x);

		r = ((q << 2) + q) << 1;	// 10 * q
		r = n - r;					// r = n - 10 * q
		if (r >= 10) {
			q += 1;
			r -= 10;
		}

		return q;
	}

};

template<typename T>
inline void ApproxShiftBCD(T n, uint8_t* digits, size_t count) {
	return DivideBCD<ApproxShift, T>(n, digits, count);
}

#endif // BCD_ALGORITHM_IMPL_H

test.cpp

//
// Simple binary to BCD conversion algorithms
// http://blog.malcom.pl/2017/konwersja-liczb-binarnych-do-kodu-bcd-avr.html
//
// Copyright (C) 2017 Marcin 'Malcom' Malich <me@malcom.pl>
// Released under the MIT License.
//
// This file contains unit tests of BCD algorithms
//

//#define ENV_WITH_STL_AND_STUFF

#define BOOST_TEST_MODULE BCD test module
#define BOOST_TEST_DYN_LINK

#include <boost/test/unit_test.hpp>
#include <boost/mpl/list.hpp>
#include <array>

#include "bcd.h"


template<typename T>
struct Data {
	T Input;
	std::array<uint8_t, Digits<T>> Output;
};

template<typename T>
struct TestData { };

template<>
struct TestData<uint8_t> {
	constexpr static const
		Data<uint8_t> data[] = {
			{ 0,	{ 0, 0, 0 } },
			{ 1,	{ 1, 0, 0 } },
			{ 127,	{ 7, 2, 1 } },
			{ 255,	{ 5, 5, 2 } },
	};
};

template<>
struct TestData<uint16_t> {
	constexpr static const
		Data<uint16_t> data[] = {
			{ 0,		{ 0, 0, 0, 0, 0 } },
			{ 1,		{ 1, 0, 0, 0, 0 } },
			{ 255,		{ 5, 5, 2, 0, 0 } },
			{ 32767,	{ 7, 6, 7, 2, 3 } },
			{ 65535,	{ 5, 3, 5, 5, 6 } },
	};
};

template<>
struct TestData<uint32_t> {
	constexpr static const
		Data<uint32_t> data[] = {
			{ 0,			{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
			{ 1,			{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
			{ 255,			{ 5, 5, 2, 0, 0, 0, 0, 0, 0, 0 } },
			{ 65535,		{ 5, 3, 5, 5, 6, 0, 0, 0, 0, 0 } },
			{ 2147483647,	{ 7, 4, 6, 3, 8, 4, 7, 4, 1, 2 } },
			{ 4294967295,	{ 5, 9, 2, 7, 6, 9, 4, 9, 2, 4 } },
	};
};


template<typename T, std::size_t N>
std::string ArrayContent(const std::array<T, N>& arr) {

	std::ostringstream oss;
	oss << "{ ";
	for (auto n : arr)
		oss << static_cast<int>(n);
	oss << " }";
	return oss.str();
}


template<typename T, typename F>
void TestFunction(F func) {

	for (const auto& data : TestData<T>::data) {

		std::array<uint8_t, Digits<T>> digits;
		func(data.Input, digits.data(), digits.size());

		BOOST_TEST(
			digits == data.Output,
			"mismatch values for number " << data.Input << "\n"
			<< "  expected: " << ArrayContent(data.Output) << "\n"
			<< "  result:   " << ArrayContent(digits) << "\n"
		);

	}
}


typedef boost::mpl::list<uint8_t, uint16_t, uint32_t> IntegralTestTypes;

#define Test(func) \
	BOOST_AUTO_TEST_CASE_TEMPLATE(func##Test, T, IntegralTestTypes) {	\
		TestFunction<T>(func<T>);										\
	}																	\


Test(BruteForceBCD);
Test(DoubleDabbleBCD);
Test(NativeDivBCD);
Test(ApproxMulBCD);
Test(ApproxShiftBCD);

How is it?

`
unsigned char bcd2bin(unsigned char n)
{
#asm
ld r30,y
swap r30
andi r30,0xf
mov r26,r30
lsl r26
lsl r26
add r30,r26
lsl r30
ld r26,y+
andi r26,0xf
add r30,r26
ret
#endasm
}

unsigned char bin2bcd(unsigned char n)
{
#asm
ld r26,y+
clr r30
bin2bcd0:
subi r26,10
brmi bin2bcd1
subi r30,-16
rjmp bin2bcd0
bin2bcd1:
subi r26,-10
add r30,r26
ret
#endasm
}
`