30/06/2020
The C99 <stdint.h> header provides a plethora of type definition for platform-independent safe code: `int_fast16_t`, for example, provides an integer that plays well with the machine but has at least 16 bits. The `int_fast`xx`_t` and `int_least`xx`_t` defines doesn’t guarantee a tight fit, they provide an *machine-efficient* fit. They find the fastest type of integer for that machine that respects the constraint.

But let’s take the problem the other way around: what about defines that gives you the smallest integer, not for the number of bits (because that’s trivial with `int`xx`_t`) but from the maximum value you need to represent?

Read the rest of this entry »

Leave a Comment » | C-plus-plus, C99, data compression, data structures, hacks | Tagged: Bits, C, C Preprocessor, C99, Log2, Portable software, template | Permalink

Posted by Steven Pigeon

13/08/2019
Last week, we used the 6×7×6 palette as an example of very simple fraction-of-a-bit coding^{1}. However, we can generalize still a bit more to allow single field extraction and modification

Read the rest of this entry »

2 Comments | algorithms, data compression, data structures | Tagged: Arithmetic Coding, bit-field, fractional bits, Palette, sub-bit | Permalink

Posted by Steven Pigeon

24/04/2018
Let’s continue with lesser known color spaces. In 1980, Yu-Ichi Ohta [1] to segment images based on colors, and to do this, introduced a new colorspace—or more precisely, two variants of the same color space.

Ohta’s concern wasn’t image coding but region separation. He supposed (without much evidence) that a color space with a basis close to the principal components of the colors in the image should be maximally discriminant. He then proposed that the colorspace

Read the rest of this entry »

Leave a Comment » | algorithms, data structures | Tagged: Color Space, compression, Lossess Compression, Ohta | Permalink

Posted by Steven Pigeon

27/03/2018
Last week, we had a look at how to implement a `trool`, or a tri-valued boolean what accepts true, false, and undefined. We remarked that the storage of an `enum` likely defaults to `int`, and that my poc wouldn’t play well with `std::vector` as that container has no specialization to deal with this new type.

A specialization would be interesting because we can do much better than using an integer to store three different values. We can do much, much better.

Read the rest of this entry »

2 Comments | algorithms, C-plus-plus, data compression, data structures | Tagged: integer division, modulo, Power, shift, trool | Permalink

Posted by Steven Pigeon

06/12/2016
More often than I’d like, simple tasks turn out to be not that simple. For example, displaying (beautifully) a binary tree for debugging purpose in a terminal. Of course, one could still use lots of parentheses, but that does not lend itself to a very fast assessment of the tree. We could, however, use box drawing characters, as in DOS’s goode olde tymes, since they’re now part of the Unicode standard.

Read the rest of this entry »

3 Comments | algorithms, data structures, hacks, programming | Tagged: Box, Box-Drawing, Pretty-Printing, recursion, terminal, Tree, Unicode | Permalink

Posted by Steven Pigeon

06/09/2016
Quite a while ago I discussed using flat arrays and address calculations to store a tree in a simple array. The trick wasn’t new (I think it’s due to Williams, 1964 [1]), but is only really practical when we consider heaps, or otherwise very well balanced trees. If you have a misshapen tree, that trick doesn’t help you. It doesn’t help you either if you try to serialize a misshapen tree to disk.

But what if we do want to serialize arbitrarily-shaped trees to disk? Is it painful? Fortunately, no! Let’s see how.

Read the rest of this entry »

Leave a Comment » | algorithms, C-plus-plus, data structures, programming | Tagged: bit, C, Deserialization, Pointers, serialization, Standish, Tree | Permalink

Posted by Steven Pigeon

19/01/2016
We all know about binary search. It’s been with us such a long time. Knuth thinks it’s first appearance in print is in the Moore School Lectures, in 1946. The technique search for an item in a list by halving, iteratively, the searched portion. Its complexity is for a list of values, making it a very efficient algorithm for searching.

One may even be tempted to think that it’s in fact optimal, that we can’t do significantly better. Is that so?

Read the rest of this entry »

Leave a Comment » | algorithms, data structures | Tagged: Binary Search, complexity, interpolation, Interpolation Search, PoC, search | Permalink

Posted by Steven Pigeon

05/01/2016
Let’s make a detour through low-level programming this week. Let’s talk about bit-fields and some of their quirks.

Read the rest of this entry »

Leave a Comment » | bit twiddling, C, C99, data structures, programming | Tagged: Alignment, bit-field, C, File format, gif | Permalink

Posted by Steven Pigeon

29/12/2015
While preparing my lecture notes on sorting, I rediscovered the *Dutch flag problem* proposed by Edsger W. Dijkstra quite a while ago. This problem is relevant in the context of sorting, especially for variants of Quicksort, where you want to create not two but three partitions.

Like many problems, the Dutch flag problem has a very simple statement. Say you have an array with three types of value, how can you arrange them so that all the items of the first type is at the beginning of the array, the items of the third at the end (and, of course, leaving the second type between the two)?

Read the rest of this entry »

Leave a Comment » | algorithms, data structures, programming | Tagged: Dijkstra, Dutch Flag, Dutch Flag Problem, Partition, QuickSort, sorting | Permalink

Posted by Steven Pigeon

08/12/2015
Old computer science books aren’t perceived as being of much use, since everything is so much better now. Of course, that’s not entirely true, especially when we are interested in the techniques used in the days where 32KB core memory was “a lot”. Leafing through one such book, Standish’s 1980 *Data Structure Techniques*, I found a method of maintaining doubly-linked lists using *only one pointer*. Let’s see how it works!

Read the rest of this entry »

Leave a Comment » | algorithms, data structures, hacks | Tagged: bit twiddling, C, C99, cpp, linked lists, lists, Pointers, uintptr_t | Permalink

Posted by Steven Pigeon