Hidden Traps: Floating Point Math.

As a life long programmer, I’ve programmed a lot of calculations over the years. Yet, I was recently astounded to hear expressed the opinion that “Computer computations are error free and flawless”. The reasons that this is not (and never will be) the case are fairly deep and fundamental.

Mathematics routinely deals with matters of the infinite like the infinite digits in the value of the famous irrational number π (called pi). Engineers and computers on the others hand live in a world of the finite: finite memory, finite processing power, and finite time. The IEEE standards for computer arithmetic are marvels of ingenuity. They are also a compromise between the needs of speed, storage, and accuracy.

Let’s see a real example and test the associative property of addition. This crucial, fundamental rule of math says that:

(a+b)+c = a+(b+c)

Now lets try to program this. We’ll use Ruby for brevity, but the results would be the same for virtually any programming language that uses the computer’s floating point hardware.

a = 1.0e20
b = -1.0e20
c = 1.0

puts “(a+b)+c = #{(a+b)+c}”
puts “a+(b+c) = #{a+(b+c)}”

The output of this little snippet of code is:

(a+b)+c = 1.0
a+(b+c) = 0.0

The two results should be the same but they’re not. In one case, the use of a finite amount of memory to represent the numbers has caused an important “bit” of data to fall off the “end” and be lost. Addition in computers is not always associative.

Are there ways around this? Sure, you can improve things. In Ruby I can switch from Floats to Rational data, and this problem mostly goes away. The new program will consume more memory and take longer to run. Eventually, if the required precision becomes excessive, the program will slow to a crawl and/or run out of memory. Processing power and memory remain finite no matter how sophisticated the tools we use.

The moral: Know your math, yes, but realize that computers can’t do math, they can only approximate it! So know the limitations of your tools too.

Yours Truly

Peter Camilleri (aka Squidly Jones)

Version 0.0.2 format_engine released.

In other news, a very minor bug fix for the format_engine gem (just recently released) is now available. This corrects an issue with the handling of invalid format strings. A very minor fix and most need not rush out a get the update. Still found on RubyGems and GitHub. The plus side is that as a minor bug fix, and now passing even more tests, this is a low risk upgrade.

As always, comments and suggestions are welcomed. If problems or questions are encountered, please raise an issue under the GitHub project. I do watch the issues very closely so will be sure to give any reports immediate attention.

Yours Truly

Peter Camilleri (aka Squidly Jones)

Mock-up testing on another scale!

As a programmer, I often need to test code that interacts with other code. In the ideal universe, that testing would be done by interacting with the actual code. When this is not feasible, mocks and stubs are used as stand-ins.

Today, I had occasion to see mocks and stubs on a slightly different scale:

100_0582

The reactor mock-up at the Darlington Nuclear Power Facility.

I was lucky to have a tour of the the reactor mock-up at the Darlington Nuclear Power Plant near where I live in Ontario, Canada. The power facility is due for some tender loving care over the next decade or so and it turns out that similar maintenance projects  on similar (CANDU) class nuclear facilities have a poor track record for going over budget and time. When it comes to saving time and money, I understand mock-ups.

The idea of a mock-up reactor is to allow testing of tools and procedures, and training of personnel in a safe, low pressure environment, with the clock (or geiger counter) NOT running. This is an excellent idea and I was reminded of the training methods used by NASA in preparing astronauts for work to be done in the vastly more dangerous environment of space.

Now for dollars! The mock-up facility has a (hefty) price tag of $40 Million, but is expected to return savings benefits of $100 Million during the course of the reactor work. This does not count its value for on-going operations or the possible sale of training time to other operators who need to prepare for their refurbishment projects.

All in all, the visit to the power plant was an interesting diversion from my normal routine. It was good to take the opportunity to see test and maintenance engineering on a scale I normally never deal with. As engineers, I feel we owe it to ourselves and our art to keep an open mind and broad horizons.

As always, comments and suggestions are invited!

Yours Truly

Peter Camilleri (aka Squidly Jones)

Announcing the format_engine gem version 0.0.1

Just recently in my programming endeavors, I began to examine the Time class in Ruby. There were many subtle and nuanced points about how Time values were handled, but one area that struck me as interesting was how it dealt with formatted string I/O. The Time class supports two function strftime and srtptime. Both are based on “C” library time routines. The strftime method takes a time object, and a format specification string and creates a formatted output string. The strptime method reverses this with a formatted string and format specification string as input and a time object as output.

As I was considering these methods, it occurred to me that a generalized mechanism for build these sorts of formatters and parsers would be a useful thing. A check of available gems did not reveal an obvious candidate for this task, so, I set about writing my own. The format_engine gem is the result.

This code has undergone a decent amount of testing so the 0.0.1 release version should not be seen as too discouraging to those seeking to try it out. The gem may be found at Ruby Gems and the source code at GitHub.

I hope you find this code useful. If you feel motivated to comment, leave me a note. If you find a problem, please raise an issue on the project in the GitHub repository.

Yours Truly

Peter Camilleri (aka Squidly Jones)

Embedded Systems

Vending Machine ControllerA comparatively new medium for social interaction is the idea of a “meetup”. A gathering of like minded people to a public event, usually moderated by a web service like meetup.com or it’s equivalent. I attend these as a way to relax and meet interesting people.

There is however a sort of downside; Most of the people attending are 30 years younger than me. The result is this rather odd snippet of conversation:

Young Person: What do you do?
Old Guy: I’m a programmer.
Young Person: What kind of web programming do you do?
Old Guy: I do embedded systems programming.
Young Person: Huh?

From there the conversations diverge a lot, but the problem is answering the difficult question always follows: What is an embedded system?

While Wikipedia has an excellent article on this subject, I’ll give you my answer to this question:

An embedded (computer) system is a computer that is part of a product, device, or system that is not itself considered to be a computer.

Here are a few examples:

  • Cars: cars contain many embedded systems from fuel control, anti-lock braking, transmission control, dashboard display, ignition timing and many many more. I once read that the average car contains more than a dozen embedded systems.
  • Dumb cell phones: The cell phone needs a computer to interact with the over-the-air digital data network used to make phone calls. I exclude Smart cell phones because these are so powerful and flexible (with applications) that they are closer to hand held computers than to the dumb cell phones of old.
  • Vending machines: Like the car above, these are actually a number of embedded systems in one package. The devices that accept coins, bills, and credit cards for payment are little embedded modules within the whole, and the vending machine controller is an embedded system too. I can say that I have personally worked on each of these components over the years. A prototype of the controller is pictured above.
  • Computer components: Many storage sub-systems are in fact embedded systems that work to make mass storage devices work. Hard drives and memory “sticks” contain their own computers hidden away in them. They can even be hacked for good or ill.

This web site is devoted to the joys and frustrations of programming these embedded systems. Very often, programmers must deal with complex protocols, demanding real-time performance requirements, difficult debugging, and limited or non-existent user interfaces. Yet, it is precisely these challenges that make this type of programming so interesting. It was fun (?) yes, but maybe not so relevant any more.

Embedded systems used to use a lot of 4 bit microcontrollers. These are all gone now. The poor performance, lack of features, and high cost of programming those relics has long since over-shadowed any cost savings. So too, lower end, more primitive systems are being pushed into smaller and smaller niches. When those niches dry up, so will the sales of those parts.

In the pages of this blog, we have reviewed the chips, their defects, the math behind how things work, the crazy things that the vendors do, and the many other things that affect programming at the bare metal level. Yet embedded programming IS changing. New products like the Arduino, Raspberry PI and the Beagle are bringing a new level of power, integration and ease of use to the embedded world.

The world is changing, and so must this blog. I have taken the plunge and obtained a number of these new embeddable systems and plan to focus on this new direction. This will mean a new emphasis on Linux, higher level languages and protocols, and yes even some web programming. I have a great deal of learning and exploring to do and I hope I can share this with you, my readers.

As always, your comments and suggestions are most welcome:

Best regards;

Peter Camilleri (aka Squidly Jones)

Random in C++

Recently, I posted an article about my work with random number generators. That work was all done in the Ruby programming language. Now Ruby is a fun language to program in, but I got to thinking that it is not the first choice for embedded work. (Yes, there is mruby, but it is still not well known) So it became clear to me that C or C++ would be good choices to explore.

So I set about porting my Fibonacci pseudorandom number generator to C++. It was not entirely a pleasant experience. I used Visual Studio 2013 (free edition) to do my development. My motivation for picking that tool was simple convenience. I supposed I could have set up Eclipse with GCC, but the tool setup time would have been excessive for my simple goal of evaluating a small bit of code. Further there can be no doubt that many alternative development communities provide little to no support for the majority of users who own Windows based computers. No VS is not perfect either. Most project templates start users off with code littered with non-standard, non-portable language extensions. To the best of my ability, I avoided and removed these. If I missed any, please tell me, so I can make the needed corrections.

It has been a few years since I’ve programmed in C/C++ in a professional capacity. In the beginning it seemed that everything I did was wrong. I was writing incorrect code in so many ways that the compiler was perplexed as to what I was trying to say. Over the course of a few hours though, things got better and soon, the IDE was starting to feel comfortable and productive.

So how did the two languages compare? Well the C++ code had a lot more “pomp and circumstance” to it. To give an example, the spin function that updates the internal random state looks like this in Ruby:

#Cycle through the PRNG once.
def do_spin
  @buffer[-2] = @buffer[0]
  @buffer[-1] = @buffer[1]
  (0...@depth).each do |idx|
    @buffer[idx] = (@buffer[idx+1] + (@buffer[idx+2] >> 1)) & CHOP
  end
end

The C++ version requires an entry in the class declaration in the header file:

// much omitted...
void spin(void);
// more omitted...

as well as the actual code:

// Scramble the eggs some more.
void FibRng::spin(void)
{
    // Copy over the 'end' values.
    ring[depth] = ring[0];
    ring[depth + 1] = ring[1];
    // Spin the wheel!
    for (int i = 0; i < depth; i++)
    {
        ring[i] = (ring[i+1] + (ring[i+2] >> 1)) & CHOP;
    }
}

In fact, most of the entities in the class had to be specified twice, once in the header file and once in the source file. On the plus side, this extra detail made it possible for the IDE and the compiler to scrutinize the code to an extent impossible in Ruby. On the other hand this is a lot of extra drudge typing and ignores the fact the C++ developer is responsible for dealing with memory management, which is simple in this case; not so simple in normal, larger programs.

So what about the bottom line? How did the code perform? Well, running from the command line, on the same hardware, with the same algorithm, the C++ version was about one hundred times faster. The executable was a mere 7K in size. While these figures are impressive, they are of a trivial example. In real applications, things are much more complex. For now, this is but one data point, and one data point it shall remain. The C++ and Ruby code in question may be found on GitHub.

As always, comments and suggestions are most welcome.

Best regards;

Peter Camilleri (aka Squidly Jones)

Random Thoughts [Updated]

A long time ago, I conceived of an algorithm for generating random numbers, inspired by the famous Fibonacci sequence of numbers. The one that goes like this:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765…

The basic idea behind the sequence was that each number is the sum of the previous two. My idea was what if an array of counters were maintained in a ring, where each value was the sum of the previous two? The numbers would cascade and overflow and become very chaotic. Still I was never sure if such an algorithm would actually work. I implemented it and it did’nt. The sums sped off until they were all zero. I fixed the algorithm by shifting one of the terms to the right by one bit and now it seemed to work. Still, I was haunted by that line from the essential text: “The Art of Computer Programming” that says (after expounding the flaws in many fine algorithms thought to be suitable):

The moral of this story is that random numbers should not be generated with a method chosen at random.

Donald Knuth

I had no way of determining the quality of the numbers generated, so my code languished on the back burner. I realize now that what I was lacking was an understanding of statistics and statistical analysis. I went to university, but I am sad to say that I never took a stats course. I really wish I had.

Normally, I can figure things out from Wikipedia, but maybe my cognitive facilities are fading because it was mostly just greek to me. A few things stood out. The Chi² measure is often used in grading pseudo random number generators. I created a test bed and ran 10,000,000 iterations of a six way test (like a cubic dice) using both my creation and the one built into the Ruby language (ruby 1.9.3p484 (2013-11-22) [i386-mingw32]). Lower values of Chi² indicate closer conformance to the expected distribution of results. The values obtained were:

Generator Chi Squared Value
Home brewed 6.040861333333967e-08
Built In 1.7266209333333707e-07

Now, I still don’t know how to interpret these results fully, but my home brew generator had lower scores which means the values were more evenly distributed. Which is good… I think. I was still very uncertain. The second test I tried was an Auto-correlation test. The nature of this test is too complex to explain here except to say that it is excellent in finding hidden patterns in seemingly random data. Here are the results:

fib corr

Fibonacci Generator

Internal Generator

Internal Generator

The correlation is high when the data is compared literally to itself. This is expected. Note that as soon as the comparison starts to shift, correlation collapses and becomes essentially random. This is also expected. So far my homebrew code is holding out.

The final test is a simple scatter graph. The random number generator is used to generate random coordinates that are plotted on a graph. Patterns in the data will show up as patterns in the graph that may be visible. Here is the result of this test.

Fib_Scatter

Fibonacci Scatter

 And this is where things stand so far. All the tests I have run give me the confidence that my little algorithm produces random numbers at least as well as commercial generators, while using only addition and divide by 2 and no higher math operators. The code for this project may be found at: https://github.com/PeterCamilleri/fibonacci_rng. The code is also available as a Ruby Gem at: https://rubygems.org/gems/fibonacci_rng. Take a look at the code if you like, use for any purpose, just don’t expect any guarantees! After all, 9,9,9,9,9,9,9,9… could be a random sequence!

As always, comments and suggestions are most welcome.

Best regards;

Peter Camilleri (aka Squidly Jones)

 [Update] November 29, 2014

I recently watched the most fascinating video about the cracking of the Enigma cipher in World War 2. Here is a link to Turing’s Enigma Problem – Computerphile. The most fascinating thing for me was the analysis of the enemy’s efforts to make the code harder to crack. These changes resulted in inconsistencies that actually made it easier to crack! It re-affirms Knuth’s assertion that random things done at random are NOT assured to increase security!

New PICs, New Errata [Update 2]

It’s been a while since the topic of chip errata has come up. This is due to the fact that things have pretty much settled down for existing PIC32MX parts (See the last update). Now by that I mean that everyone now pretty much codes around these errata on a permanent basis.

Sometime ago, a new series of PIC32MZ parts was announced and these are now starting to become available. What new and exciting features will be available here to power new products and projects? Here’s a really brief summary:

  • Operation up to 200 MHz with Instruction and Data Caching for up to 330 DMIPS of performance. [No too shabby at all but no speed demon either!]
  • Internal memory of up to 2048 KB of flash memory and 512 KB of ram. [YAY!]
  • An external 50 MHz memory interface for further external memory.
  • A Serial Quad Interface allows this PIC to take advantage of serial flash devices that move four bits at a time rather than the pokey one bit at a time [finally!] An added bonus is that the PIC can actually execute from serial memory using XIP mode! [Don’t cheer just yet…]
  • An Analog to Digital converter that can operate as high as 500 K Samples per Second. [Ditto.]

That is a lot of text, so here’s a cool picture:

PIC32MZECfamilybloc

There is a lot of new stuff going on here, so the skeptics and other normal people may be wondering about errata. Well here are the PIC32MZ Family Datasheet 60001191C and the latest PIC32MZ Errata 80000588F.

They ARE pretty dense reading so I’ll give a very brief summary of the issues. First some good news. While earlier PICs suffered from serious flaws in the CPU and Flash memory, these new PICs are not repeating those mistakes. This is a HUGE relief. The peripherals however have a few notable gosh-darns. Here are some selected notes:

11. Module: Secondary Oscillator
A crystal oscillator cannot be used as the input to the Secondary
Oscillator (SOSCI/SOSCO pins).
Work around
Instead, use the external clock. [This is all well and good except that this clock input is usually used for a 32.768 KHz RTC clock and getting battery operation may be more difficult to achieve with an external oscillator]

13. Module: Power-Saving Modes
Dream mode is intended as a feature allowing DMA operation while the CPU is in Idle mode; however, Dream mode does not function.
Work around
None. [Too bad, this sounds like a great idea.]

15. Module: SPI
The SPI clock speed does not meet the published specification. The maximum supported SPI clock speed is 27 MHz.
Work around
None.. [Bye bye 50 Mhz… On the bright side, 27 MHz should be useful for jamming annoying people who still use CB radio!]

27. Module: Random Number Generator
True RNG mode does not function.
Work around
Instead, use Pseudo-Random Number Generator (PRNG) mode. [I guess the NSA was not happy with the idea of people having effective security. PRNGs are easily cracked.]

31. Module: SQI
XIP mode is not operational (MODE<2:0> bits = 011 in the SQI1CFG register).
Work around
Use PIO mode (MODE<2:0> bits = 001) or DMA mode (MODE<2:0> bits = 010). [Sigh… This feature had such promise for code executing out of a pluggable memory device without a lot of extra expenses.]

34. Module: SQI
Clock speed for read operations does not meet the maximum specification (SQ10) of 50 MHz. For read operations the maximum clock is 25 MHz.
Work around
None. [Drat! Now we can’t even jam CB radios!]

44. Module: ADC
For Revision A3 and A4 silicon: The ADC module does not meet the published
Throughput Rate (AD51) and Full-Scale Input Range (AD12) specifications. The updated Maximum Throughput Rate (AD51) specification is 125 ksps, assuming 16x Oversampling mode. The updated Maximum Full-Scale Input Range is 2.5V for both Differential and Singled-Ended modes. The updated Minimum Full-Scale Input Range is -2.5V for Differential mode.
For Revision A5 and newer silicon: The ADC module does not meet [the] published throughput rate (AD51) and accuracy specifications. More information will be provided in a subsequent October 2014 update of this document.
Work around
None. [So the ADC runs at 1/4 speed but that may change. I’ll post an update when I get one.]

OK, so how do these errata compare? Overall, they are pretty light. While it is true that some nifty features are making an exit, on the whole the core is solid and the peripherals are a significant improvement over any available before. I look forward to working with this new PIC and will write about any interesting things that may come up.

As always, comments and suggestions are most welcome.

Best regards;

Peter Camilleri (aka Squidly Jones)

[Update Nov 27, 2014]

It has come to my attention that I’ve left out at least one important errata. Here it is:

41. Module: Oscillator 
A crystal oscillator cannot be used as the input to the Primary Oscillator (OSC1/OSC2 pins).
Work around
Use an external clock or an internal FRC. [I did not see this as a killer bug as I routinely design in both a crystal and an oscillator module (and populate only one part). The modules often perform better and it makes for more options in the final BOM while consuming very little space.]

As usual, check the docs for yourself and you be the judge!

Peter Camilleri (aka Squidly Jones)

[Update Jan 3, 2015]
The most recent errata (80000588G) for the PIC32MZ family reveals that the latest revision of silicon can finally use a crystal for its main oscillator. Yay! Mind you there are still some spec issues here, and those errata remain. IMHO those issues are minor compared to not being able to run with a crystal at all. For the most demanding applications though, an external oscillator module may still be the best bet.

Again, check the docs for yourself and you be the judge!

Peter Camilleri (aka Squidly Jones)

Wow! Did they really do that?

I once heard that the intelligence of any group of people is that of the person with the lowest IQ divided by the number of people involved. A recent case seems to be a supporting data point for this point of view.

Consider if you will the company FTDI. This company is (was?) the world leader in the area of USB bridge chips that make it easy to add USB access to all sorts of gadgets that would otherwise be difficult, expensive, and problem prone. The FTDI chips work well and come with easy to use software distributed for free with Windows, Mac, Linux, and many other sorts of computers. The chips and the software drivers were so good that many customers chose to go with FTDI rather than other vendors. The result of this is that these chips are expensive and often hard to find.

So FTDI gets to laugh all the way to the bank and otherwise all is well right? Well not quite. Counterfeits! With the real mccoy so hard to get, many legitimate vendors were tricked into buying fake chips. Do these fakes work? Mostly, it’s not as if the USB bridging function is that hard to do. FTDI however was not amused. They were losing some sales and lots of that delicious money! They had to do something and they did!

To stem the loss of revenue, a new software driver was released that detects some subtle difference between genuine and fake chips and then erases a vital data entry called the PID (Product ID) if a fake is detected. After that, the fake chip and the product it was embedded in will no longer function. The consumer is now the proud owner of a new paper weight or brick as it is sometimes called. The new driver was released through the Microsoft Windows update mechanism where it was incorporated into countless millions of computers all around the world.

So; Is this a nasty thing to do? Consider this bit on computer trespass (my emphasis):

In Virginia, computer trespass consists of, with malicious intent, copying, altering, or erasing data from a computer, causing a computer to malfunction, causing an electronic funds transfer, etc.[Wikipedia]

Yes this IS a very nasty thing to do! It hurts consumers at random. Some have gone so far as to label it cyber-terrorism! While I am not sure about that, one thing is certain, this action has caused serious, if not fatal, damage to the faith and value of the FTDI brand. Engineers chose and specified FTDI chips over others because they were trusted, reliable and dependable. That perception is gone and it will be very difficult to recover that goodwill.

I cannot even begin to imagine the legal fall-out from what would happen if a large number of products suddenly stopped working and the victim decided to let loose the dogs (lawyers) of war in revenge!

I am a big fan of the EEVBLOG and this posting does a good job of summarizing people’s feelings about this issue and the lameness of the company’s responses:

EEVblog #676 – RANT: FTDI Bricking Counterfeit Chips!

As for me, I am looking for other vendors. This sort behaviour is so unacceptable that it makes me seriously wonder what kind of crazy people are in charge at FTDI.

What do you think? I’d really like to hear what you think about this issue!

Best regards;

Peter Camilleri (aka Squidly Jones)

I’ll be back!

Hello All;

For some time now, this web site has gone very quiet. The reason is simple. About two years ago, a dear friend convinced me to move of in a different direction. This divided my attention and eventually I had to let this web blog slip into silence.

The thing is that after two years of trying that other thing, I cannot escape the truth that I like writing about and building technology a LOT more. Coming to my senses, I know I must return to my roots and this blog.

That is why I am glad to report that you can expect this web site to return to some semblance of activity very soon. In the interim, a lot has happened and been learned, and the articles will reflect that learning.

I also hope to hear from you, my gentle readers. Having looked through some previous postings, has some topic perked your interest? Let me know about it and I will do my best to provide answers!

Best regards;

Peter Camilleri (aka Squidly Jones)