Arithmetic coding is a common algorithm used in both lossless and lossy data compression algorithms. It is an entropy encoding technique, in which the frequently seen symbols are encoded with fewer bits than rarely seen symbols. It has some advantages over well-known techniques like Huffman coding. This article will describe the CACM87 implementation of arithmetic coding in detail, giving you a good understanding of all the details needed to implement it.
Continue reading this post…

Voting on the C++14 standard was completed in August, and all that remains before we can say it is officially complete is publication by the ISO. In this article I will visit the high points of the new standard, demonstrating how the upcoming changes will affect the way you program, particularly when using the idioms and paradigms of Modern C++.
Continue reading this post…

Alexander Stepanov’s Standard Template Library provided a huge push towards making template programming an important part of C++, and helped to insure that it was included as part of the first standard in 1998. But adoption of templates by most programmers has been more of an incremental process, as opposed to a revolutionary one – many of us have literally decades of Object Oriented == The One True Path to unlearn. And to top things off, templates needed some refinement over the years before they could do many of the things we expected of them.

In this article, I’ll show you how generic programming with templates makes a noticeable improvement in a pedestrian but important task I deal with constantly in my data compression work. Then I’ll show you the annoying but understandable problems with this approach circa 1998, and finally, how to resolve them with features added in TR1 and C++11.
Continue reading this post…

In the days of XP, a Windows Service was more or less an ordinary executable running in the same session as all other executables. Debugging it was fairly simple, although you did have to deal with the complication that it was started by the Service Control Manager.

Today Windows Services run in a mysterious Session 0, which is difficult to work with. If your Service is written in C++, you’ll find that it can be problematic to deal with bugs, particularly crashes, that occur during Service startup.

In this article I’ll explain why that is, and show you a very simple set of techniques for dealing with this problem. I hope that the relative simplicity of all this will reduce your frustration level when debugging your Windows Services.
Continue reading this post…

It’s always exciting to get an email like this from an iconic tech giant:

Hi Mark,

I recently found your profile in our database, and your background is impressive. The (redacted big company) Media Division will be flying several candidates in for interviews at our (redacted big city) headquarters in April and considering you.

I’m not actively seeking a new job, so normally I’d just file this away in my emergency just-laid-off folder, but this email had a twist that got my attention:

If interested in exploring Development opportunities with us, the first step will be to complete our coding challenge ideally within the next 3 to 5 days.

Who doesn’t love a coding challenge?
Continue reading this post…

A frequently cited rule in the C++ standard is the One Definition Rule. In this article, I’ll show you how I inadvertently blundered into an ODR problem, found my way out, and uncovered a deeper truth about the language standard.

This story starts with a very mundane exercise in debugging using the Windows API function OutputDebugString(), an attempt to simplify my life, followed by a puzzle, and eventually, enlightenment.
Continue reading this post…

Instead of writing about C+, data compression, or my usual raft of interesting topics, I’ve been busy for the past few weeks writing a new game, Rack Master. Rack Master is a free training program that gives you a fresh puzzle every day. Your goal is to make the best scores out of five racks of letters, using the scoring rules from games like Scrabble and Words for friends.

There are four levels, with varying degrees of difficulty. See what you think, give feedback, and by all means, pass the link along to any friends who are word enthusiasts.

- Mark

Ten years ago I issued a simple challenge to the compression community: reduce the size of roughly half a megabyte of random data – by as little as one byte – and be the first to actually have a legitimate claim to this accomplishment.

Ten years later, my challenge is still unmet. After making a small cake and blowing out the candles, I thought this would be a good time to revisit this most venerable quest for coders who think outside the box.

Continue reading this post…

There are a lot of great features in C++11, but unique_ptr stands out in the area of code hygiene. Simply put, this is a magic bullet for dynamically created objects. It won’t solve every problem, but it is really, really good at what it does: managing dynamically created objects with simple ownership semantics.
Continue reading this post…

C++11 brings rich support for threading to the language, and one of the features that really works for me is the function template async. This provides a great mechanism for spinning off worker threads and easily collecting their results. In this article, I’ll show you how I used async to introduce threading to C++ beginners in a nice non-threatening fashion.
Continue reading this post…