Integer division and timer resolution

I have this very specific need to send a list of pre-timed messages from an embedded system. Each message has a specific time when it needs to be sent out. The time is specified in milliseconds (ms) with respect to the previous message in the list. The first message being at time zero.

The algorithm to send messages out is very simple. I send out the first message, and arm a timer with the time of the second message. As soon as the timer expires, I send out the second message, and rearm the timer to send the third message, and so on. Thus, it is pretty clear that timer resolution is very important. Since the smallest integer time interval I require is 1 ms, a timer resolution of 1 ms or less would be ideal.

The embedded system I am dealing with, has a timer resolution of 2.5 ms i.e. 1 tick of the timer is 2.5 ms long. The timer routine does not accept a time of 0, 1 tick is the smallest integer value the routine expects. To convert time in milliseconds to ticks, I need a routine that can convert milliseconds to ticks. The conversion routine, putting it simply, would receive time in milliseconds, divide it by 2.5, and round the result to an integer value. I don’t have access to floating point math though, so the routine I’ve developed looks like this

typedef unsigned int uint32_t;
const unsigned short MULTIPLY_BY = 2;
const unsigned short DIVIDE_BY = 5; // never ever set to zero

uint32_t MillisToTicks(uint32_t timeInMillis, int *remainder)
    uint32_t timesTwo;
    uint32_t result;

    timesTwo = timeInMillis * MULTIPLY_BY;
    result =  timesTwo / DIVIDE_BY;
    *remainder += timesTwo % DIVIDE_BY;
    if (*remainder >= DIVIDE_BY)
        result += 1;
        *remainder -= DIVIDE_BY;
    else if(*remainder <= -1 * DIVIDE_BY && result > 1)
        result -= 1;
        *remainder += DIVIDE_BY;
    else if (result == 0)
        result = 1;
        *remainder -= DIVIDE_BY - result;
    return result;

MillisToTicks never returns zero. Dividing by 2.5 is the same as multiplying by 2 and dividing by 5. 2 is read from a constant called MULTIPLY_BY and 5 from another constant called DIVIDE_BY. Since the integer division will produce a remainder, MillisToTicks requires a pointer to integer where it can store the remainder of the integer division. That remainder is updated and checked during each call. If it exceeds DIVIDE_BY, the result is incremented by one, and remainder decremented by DIVIDE_BY.

If the result of integer division is zero, I force it to a value of 1, and decrement remainder by DIVIDE_BY. Next time MillisToTicks gets called, if remainder is less than or equal to -DIVIDE_BY, I decrement result by 1, and increment remainder by DIVIDE_BY. Putting it simply, there will be moments when I’ll stray away from timing the messages perfectly, but given enough messages, I’ll stray back on track. To test that, I have implemented the following code

int remainderMillisToTicks = 0;

uint32_t times1[] = {6, 6, 6, 2, 6, 6, 2, 2, 6, 6, 7, 8, 1, 1, 2, 3, 6, 20, 30, 9, 30, 100, 3000, 1, 1, 8000, 10000, 23, 1, 1, 19, 6, 5, 26, 201, 503, 901};

uint32_t times2[] = {6, 6, 6, 2, 6, 6, 2, 2, 6, 6, 7, 8, 503, 901, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 6, 20, 30, 9, 30, 100, 3000, 1, 1, 8000, 10000, 23, 1, 1, 19, 6, 5, 26, 201, 503, 901};

uint32_t times3[] = {6, 6, 6, 2, 6, 6, 2, 2, 6, 6, 7, 8, 1, 1, 2, 3, 6, 20, 30, 9, 30, 100, 3000, 8000, 10000, 23, 19, 6, 5, 26, 201, 503, 901, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

void test(uint32_t *times, unsigned short size)
    int i;
    uint32_t totalMillis = 0;
    uint32_t ticks = 0;
    double ticksToMillis = 0;
    double totalTicksToMillis = 0;

    for (i = 0; i < size; i++)
        totalMillis += times[i];
        ticks = MillisToTicks(times[i], &remainderMillisToTicks);
        ticksToMillis = ((double)ticks*DIVIDE_BY) / MULTIPLY_BY;
        totalTicksToMillis += ticksToMillis;
        //printf("%d\t%f\t%d\t%d\t%f\n", times[i], ticksToMillis, remainderMillisToTicks, totalMillis, totalTicksToMillis);
    printf("Ideal total time required: %d, time achieved: %f\n", totalMillis, totalTicksToMillis);

int main()
    test(times1, sizeof(times1) / sizeof(uint32_t));
    remainderMillisToTicks = 0;
    test(times2, sizeof(times2) / sizeof(uint32_t));
    remainderMillisToTicks = 0;
    test(times3, sizeof(times3) / sizeof(uint32_t));

Here’s how the output of that test code looks like

Ideal total time required: 22953, time achieved: 22952.500000
Ideal total time required: 24363, time achieved: 24362.500000
Ideal total time required: 22965, time achieved: 22985.000000

Enable the commented printf statement in test and you’ll see a call by call log. At times, when the time value requested is too small, you’ll see the messages stray away from perfect timing, and stray back to a normal cadence later. The overall time is thus unaffected or affected only slightly. The last call to test represents a failure condition that can only be avoided by using a higher resolution timer.


Node.js on Raspberry Pi with Buildroot

I successfully built an embedded Linux system for Raspberry Pi using Buildroot recently, and decided it was time to add some useful packages to it. The first that came to mind is Node.js. Having that on the Linux system will allow me to serve an HTML5 UI to any computer with a browser, on the same network.


make menuconfig 

in buildroot folder to obtain the configuration UI. Node.js requires IPv6 support so I enabled that in the Toolchain menu thus


Then I enabled Node.js and npm from the Target packages menu thus



I followed that up by issuing a full build thus

make clean

Buildroot stores all downloads in the dl folder, so it will only download whatever isn’t already there. It will build the host cross-compilation toolchain from scratch though, since that is available under output, and make clean removes everything there.

I’ve now got Node.js 0.10.12 working successfully on the Linux system.

SparkFun FTDI Basic with Raspberry Pi

The following diagram shows how you can connect an FTDI Basic (USB to serial) breakout board to Raspberry Pi’s GPIO connector. If you’ve configured VCC to output 5 Volts, you can also power the Raspberry Pi by connecting its 5V header pin to VCC.


If you’ve got Adafruit’s USB to Serial TTL cable, you can follow their lesson on using it.

Output kernel log to console

For the kernel log to appear on the serial port, console should be set to ttyAMA0.

Here’s how cmdline.txt in the boot partition of my Raspberry Pi looks like

dwc_otg.fiq_fix_enable=1 sdhci-bcm2708.sync_after_dma=0 dwc_otg.lpm_enable=0 console=ttyAMA0,115200 root=/dev/mmcblk0p2 rootwait

To get a login prompt /etc/inittab should contain a line such as

ttyAMA0::respawn:/sbin/getty -L ttyAMA0 115200 vt100 # GENERIC_SERIAL

If you’re compiling your own kernel using Buildroot, set the TTY port to ttyAMA0 under System configuration, getty options


What woes Samsung?

Samsung announced a rather lackluster quarter (compared to last year). What woes it? I am willing to hazard it is software. I was recently in the market for a cheap Android phone. Even though Samsung had an impressive lineup of hardware, none had Android 4.4 (KitKat) on it.

Low-end hardware requires Android KitKat due to improvements in how it supports low memory. The only phones that were touting Android 4.4 were from LG and Motorola. Motorola was still slightly costlier and Moto E hand’t arrived yet. Guess which I bought?

Embedded Linux system for Raspberry Pi with Buildroot

This post shows how easy it is to make a custom embedded Linux system for Raspberry Pi using Buildroot. I used an Ubuntu 13.04 VM for Parallels Desktop 9 to perform the build.

The Ubuntu VM required only a few dependencies and I could go ahead with the build. These I installed by executing

sudo apt-get install ncurses-dev git g++

I then obtained Buildroot release buildroot-2014.05.tar.gz and extracted it to a local folder using tar xvzf buildroot-2014.05.tar.gz. The procedure to perform the build and prepare an SD card is well documented in file board/raspberrypi/readme.txt.

I headed into the buildroot-2014.05 folder and prepared the appropriate .config file required by buildroot

cd buildroot-2014.05
make raspberrypi_defconfig

Since I wanted to generate a persistent root file system, I followed that by executing


The build takes a while to finish. Once done, I followed the steps in readme.txt mentioned above to prepare an SD card. I already had an appropriately formatted SD card so I copied the relevant output files

rm /media/parallels/boot/*
cp output/images/rpi-firmware/* /media/parallels/boot/
cp output/images/zImage /media/parallels/boot/
sudo rm -rf /media/parallels/fc254b57-8fff-4f96-9609-ea202d871acf/*
sudo tar xf output/images/rootfs.tar -C /media/parallels/fc254b57-8fff-4f96-9609-ea202d871acf/

I was able to boot Raspberry Pi with the newly minted headless embedded Linux system, use an HDMI display to log in, and bring up the ethernet interface eth0.

Packaging source code using Grunt

I have this very specific need to package source code of an Atmel Studio 6.2 project. For those not in the know, Atmel Studio 6.2 is based on Visual Studio Isolated Shell, and retains many of the features that make Visual Studio itself a neat IDE.

I had several choices for packaging the source code:

  1. Do it manually – that would have worked once or twice. Since I have to keep some files out of the source package, it would make repeated packaging an error-prone and time-consuming affair.
  2. Use msbuild – I didn’t find a convenient task native to msbuild for creating a zip file. Maybe I didn’t look hard enough.
  3. Use Apache Ant – I didn’t want to include a Java dependency into my build and decided to let Ant go.
  4. Use Grunt – I always seem to have Node.js installed, and find JSON for writing build instructions an interesting alternative to writing XML (verbose). Grunt is also quite portable. Grunt won.

The only files Grunt requires is a package.json file with the project configuration, and a Gruntfile.js with the build instructions.

You can create package.json by invoking npm init and providing some details about your project. Gruntfile.js can be hand-coded in any text editor. Here’s my own script to get you started.

module.exports = function(grunt) {

  // Project configuration.

    pkg: grunt.file.readJSON('package.json'),

    compress: {
      main: {
        options: {
          archive: ''
        files: [
            expand: true,
            cwd: './',
            src: ['**', '!*/Debug/**', '!*/Release/**', '!node_modules/**', '!*.atsuo', '!**/file.h', '!']

  // Load tasks

  // Default task(s).
  grunt.registerTask('default', ['compress']);


To invoke Grunt, you need to have grunt and its plugins installed. Use npm to download and install a project-local copy of these packages, and include them in your package.json as dependencies. In my case

npm install grunt --save-dev
npm install grunt-contrib-compress --save-dev

That results in creation of of a node_modules folder in the root folder of the project. I don’t add node_modules to version control. If you use git, add it to your .gitignore. Other developers can obtain dependencies listed in package.json by invoking npm install within the root folder.

You are now ready to invoke Grunt and execute the relevant tasks. In my case, invoking grunt results in creation of a file containing all the files under the project root folder, minus whatever files and folders I choose to leave out.

Lists and sorting in .NET

.NET Framework provides a generic SortedList class that keeps objects sorted by Key while they are added. It requires Key to be unique, probably for performance reasons. The example below demonstrates the alternative List<T> class for sorting and searching, and the limitation of SortedList while trying to do the same thing. You’ll probably get better performance out of SortedList. List has a BinarySearch method that can improve search performance significantly.

using System;
using System.Collections.Generic;
using System.Linq;

namespace ListExample
    class Person
        public string name;
        public byte age;

        public Person(string name, byte age)
   = name;
            this.age = age;

    class CompareByAge : IComparer<Person>
        public int Compare(Person x, Person y)
            return x.age - y.age;

    class Program
        static void Main(string[] args)
            Person luisa = new Person("Luisa", 7);
            Person victoria = new Person("Victoria", 10);
            Person alice = new Person("Alice", 10);
            Person lara = new Person("Lara", 1);
            Person rafaela = new Person("Rafaela", 9);
            Person noname = new Person("Noname", 6);
            Person p;

            Console.WriteLine("Sorting with List:");
            List<Person> list = new List<Person>();

            // Sort using System.Collections.Generic.IComparer<T>
            list.Sort(new CompareByAge());

            // Sort using the System.Comparison<T> delegate
            //list.Sort(delegate(Person x, Person y) {
            //    return x.age - y.age;

            foreach (Person person in list)


            Console.WriteLine("Find with List:");
            //p = list[list.FindIndex(0, person => person.age >= noname.age)];
            //p = list.Find(person => person.age >= noname.age);
            int i = list.BinarySearch(noname, new CompareByAge());
            i = i < 0 ? ~i : i;
            if (i == list.Count)
                Console.WriteLine("No one that old here");
                p = list[i];


            Console.WriteLine("Sorting with SortedList:");
            SortedList<byte, Person> sortedList = new SortedList<byte, Person>();
            sortedList.Add(luisa.age, luisa);
            sortedList.Add(victoria.age, victoria);
            //sortedList.Add(alice.age, alice); // throws System.ArgumentException
            sortedList.Add(lara.age, lara);
            sortedList.Add(rafaela.age, rafaela);

            foreach (Person person in sortedList.Values)


            Console.WriteLine("Find with SortedList:");
                p = sortedList.First(keyValue => keyValue.Key >= noname.age).Value;
                Console.WriteLine("No one that old here");


Here’s the output produced by that example.

Sorting with List:

Find with List:

Sorting with SortedList:

Find with SortedList: