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

24/03/2020
In this quarantine week, let’s answer a (not that) simple question: how many bits do you need to encode sound and images with a satisfying dynamic range?

Let’s see what hypotheses are useful, and how we can use them to get a good idea on the number of bits needed.

Read the rest of this entry »

6 Comments | data compression | Tagged: dB, Dynamic Range, Luminosity, Pain Threshold, Photopic, Scotopic, sound, Threshold of hearing | 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

06/08/2019
Remember ye olde dayes when we had to be mindful of the so-called “web safe palette“? Once upon a time, screens could display 24-bits colors, but only 256 at a time in some “hi-res” modes. But that’s not what I’m going to tell you about: I’d rather tell you about the encoding of the palette, and about a somewhat better palette. And also about using *fractions of bits* for more efficient encodings.

Read the rest of this entry »

1 Comment | algorithms, data compression, hacks | Tagged: bit, coding, colorspace, log, web safe palette | Permalink

Posted by Steven Pigeon

07/08/2018
Pairing functions are fun. Last week, we had a look at the Cantor/Hopcroft and Ullman function, and this week, we’ll have a look at the Rosenberg-Strong function—and we’ll modify it a bit.

Read the rest of this entry »

3 Comments | algorithms, data compression, Mathematics | Tagged: Cantor, Hopcroft, pairing function, Rosenberg, Rosenberg-Strong, Strong, Ullman | Permalink

Posted by Steven Pigeon

31/07/2018
Pairing functions are used to reversibly map a pair of number onto a single number—think of a number-theoretical version of `std::pair`. Cantor was the first (or so I think) to propose one such function. His goal wasn’t data compression but to show that there are as many rationals as natural numbers.

Cantor’s function associates pairs (i,j) with a single number:

…but that’s not the only way of doing this. A much more fun—and spatially coherent—is the boustrophedonic pairing function.

Read the rest of this entry »

1 Comment | algorithms, data compression, Mathematics | Tagged: boustrophedonic, Cantor, Integer, ox, pairing function, plowing, Rational | Permalink

Posted by Steven Pigeon

03/07/2018
HSV (hue, saturation, value) and HSL (hue, saturation, lightness) are two intuitive, but computationally cumbersome, colorspaces.

The basic idea behind these colorspaces is the good ol’ color wheel, where primary colors are placed on a triangle and secondary colors between; complementary colors are to be found opposite on the circle. That’s intuitive enough, but we still have to make it into a workable colorspace.

Read the rest of this entry »

Leave a Comment » | algorithms, data compression, hacks | Tagged: colorspace, HSL, HSV, Matrix, Orthonormal, Primary colors, rgb, Transform | Permalink

Posted by Steven Pigeon

19/06/2018
Let’s have a look at another physical colorspace: Pantone.

The Pantone color system isn’t particularly useful for us as it is mainly concerned with “real world” colors, as in print. It also uses a variety of special dies, for metallic or fluorescent finish. It does, however, allow very accurate and consistent color reproduction for packaging, posters, and comics.

Read the rest of this entry »

Leave a Comment » | algorithms, data compression | Tagged: Black, color, Color Space, fluorescence, fluorescent, ink, Pantone, Pigment, white | Permalink

Posted by Steven Pigeon

12/06/2018
While the RGB and its transformed colorspaces are useful for computer graphics and video compression, there are other colorspaces that deal with “real life” materials, like ink and paint. Albert Henry Munsell (1858–1918), a painter, proposed such a system.

Unlike RGB and its friends, the Munsell colorspace isn’t based on mixing three primaries, but rather on hue (tint), value (brightness) and chroma (density of color, or *saturation*), and colors are arranged on a color wheel, but unlike the usual three/six primary color wheel, Munsell’s has 5 primary colors [1].

Read the rest of this entry »

Leave a Comment » | algorithms, data compression | Tagged: chroma, Color wheel, hue, Munsell, Primary colors | Permalink

Posted by Steven Pigeon

29/05/2018
A few posts ago, I said that while the colorspaces looked random, they really weren’t, and that there was underlying order. The structure cannot be easily seen just by looking at the numbers themselves, but at how the numbers are obtained.

The story begins sometimes in the 1950s, were transmitting color TV images started to be the next logical step. Someone (not sure who was first, but it may have been Valensi, in the 1930s) proposed that TV color should be encoded in a perceptually friendly way [1]. It was known for a while that the retina had four types of sensors, rods for brightness with no color information, and three other types corresponding to red, green, and blue, but also that in, and beyond the retina, information travels as brightness, yellow-blue and red-green differences [2,3].

Read the rest of this entry »

Leave a Comment » | algorithms, data compression | Tagged: Color Space, matrices, Matrix, Matrix Product, Rotation, YCbCr, YCC, YDbDr, YIQ, YUV | Permalink

Posted by Steven Pigeon