Thursday 20 March 2014

Starting a new project with Ceedling

WORK IN PROGRESS!!! Installing Ceedling and the AVR toolchain

THIS NEEDS A BETTER INTRO ABOUT UNITY AND THE TOOLCHAIN Ceedling is a build system for C projects that is something of an extension around Ruby’s Rake (make-ish) build system. Ceedling is primarily targeted at Test-Driven Development in C and is designed to pull together CMock, Unity, and CException -- three other awesome open-source projects you can’t live without if you're creating awesomeness in the C language. In order to spread the awesomeness around, Ceedling is an extensible contraption with a nice plugin mechanism.

Before we install Ceedling, let's start by installing a compiler for the AVR ATmega328P, the microcontroller onboard the Arduino Uno. I'm going to show the installation commands for a typical Linux system, but the instructions for Windows and OSX follow a similar pattern. Open a terminal and type the following command:

ngourlay@craxine:~$ sudo apt-get install binutils-avr avr-libc avrdude gcc-avr

After installing Ceedling and the avr tools create a new project and edit the generated rakefile using your favourite text editor:

ngourlay@craxine:~$ ceedling new 74HC595
      create  74HC595/vendor/ceedling/docs/CeedlingPacket.pdf
      create  74HC595/vendor/ceedling/docs/CExceptionSummary.pdf

... many other messages from Ceedling ...

      create  74HC595/project.yml
      create  74HC595/rakefile.rb

Project '74HC595' created!
 - Tool documentation is located in vendor/ceedling/docs
 - Execute 'rake -T' to view available test & build tasks

ngourlay@craxine:~$ cd 74HC595/
ngourlay@craxine:/74HC595~$ emacs rakefile.rb


You'll need to add a couple of targets ('convert' and 'program') , plus a dummy target ('serial_port') to ensure that the required environmental variable has been set. For most projects, the following rakefile will be sufficient:


Now edit the project.yml file. Uncomment the 'release_build' variables, and add some environmental variables. Changes to the standard boilerplate are marked in bold, below.

:project:
  :use_exceptions: FALSE
  :use_test_preprocessor: TRUE
  :use_auxiliary_dependencies: TRUE
  :build_root: build
  :release_build: TRUE
  :test_file_prefix: test_

:release_build:
  :output: 74HC595
#  :use_assembly: FALSE

:environment:
  - :mcu: atmega328p
  - :f_cpu: 16000000UL
  - :serial_port: /dev/ttyACM0  # change this to the correct port
  - :objcopy: avr-objcopy


:extension:
  :executable: .bin

:tools:
  :release_compiler:
    :executable: avr-gcc
    :arguments:
      - ${1}
      - -DTARGET
      - -DF_CPU=#{ENV['F_CPU']}
      - -mmcu=#{ENV['MCU']}
      - -Iinclude/
      - -Wall
      - -Os
      - -c
      - -o ${2}
  :release_linker:
    :executable: avr-gcc
    :arguments:
      - -mmcu=#{ENV['MCU']}
      - ${1}
      - -o ${2}.bin

Monday 10 March 2014

Approximate division using multiplication and right-shift

Problem

Many processors have no native floating-point capabilities, leading to the choice between integer maths or floating-point emulation. One important range of microcontrollers, ATmega, also has no native arithmetic division operation. Thus, the Arduino project, which uses the ATmega chipset, must use a compiler that emulates both integer and floating-point division in software. In some cases, it might be better to ignore the compiler and roll your own less-accurate version of the division op.

Decimal Tricks

All numerate people have learned mental tricks to help with arithmetic division. We learn multiplication tables so that, given we know 55 is five times eleven and 66 is six times eleven, then we also know that 57 divided by 11 is slightly more than five.

5 < (57 / 11) < 6

Dividing is equivalent to multiplying by a reciprocal, and some of these reciprocals have a simple decimal expansion. For example, given we know that one-eighth is 0.125, we can assume that division by 125 is equivalent to multiplication by eight, with some shift of the decimal point.

(x / 125) == (x * 8 / 1000)

Further, some decimal expansions of reciprocals are close to being helpful. The reciprocal of 77 is around 0.01299, meaning that we can approximate a division by 77 with a multiplication by 13, followed by some shift of the decimal point.

(x / 77) =~ (x * 13 / 1000)

Binary Tricks

We can apply the "multiplication and right-shift" trick to binary division, which is slightly more useful when programming. First, of course, any division by a whole power of two is equivalent to a right-shift.

(x / 2) == (x >> 1)
(x / 4) == (x >> 2)
(x / 8) == (x >> 3)
(x / 16) == (x >> 4)
(x / 32) == (x >> 5)
...

Next, we can use approximations that give us good results within a limited range. For example, given that x is between zero and 255, and we are calculating an integer result, the following expressions are true:

(x / 3) == ((x * 171) >> 9)
(x / 5) == ((x * 205) >> 10)
(x / 6) == ((x * 171) >> 10)

Of course, if we are limiting ourselves in this way to integer maths, and 8-bit numerators, every result for divisors over 128 can be calculated with a simple comparison:

(x / 129) == (x < 129 ? 0 : 1)
(x / 130) == (x < 130 ? 0 : 1)
(x / 131) == (x < 131 ? 0 : 1)
(x / 132) == (x < 132 ? 0 : 1)
...

There are a few problems in replacing division by multiplication in this way. The best example is division by seven:

(x / 7) =~ ((x * 147) >> 10)

Now, this expression is mostly true, but starts to become inaccurate at x=209, with seven off-by-one errors in the whole range. Whether these off-by-one errors are acceptable is a matter of personal choice, but given the limitations of integer maths, it seems reasonable to sacrifice a little accuracy for speed here.

Use case

A sensor can produce a voltage on an Arduino analog pin which will be converted into an unsigned 10-bit integer. To format this value in human-readable units (centigrade, metres, hours, etc.) requires division by a constant divisor. Often, humans don't care about off-by-one errors when reading the temperature of their ovens. Using the multiply-and-shift method can reduce time and memory usage, and produce a result in a constant number of clock cycles.

Complete list of multiplications

Here's a complete list of approximate divisions in the 8-bit space. Change the Perl script for the equivalent 10-bit approximations.

Source code