Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Binary to BCD conversion algorithms (benchmark on AVR)
//
// 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;
}
//
// 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
//
// 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment