The 6×7×6 palette (Coding with fractions of bits, Part I)

August 6, 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 »


Of small copies and templates.

July 23, 2019

Sometimes, it’s the little things that make a big difference. For example, moving small, not machine-sized, pieces of data may be a problem. If it happens to be machine-sized (that is, the size of something like uint32_t), then the copy is readily done by a single (integer) copy. But what if it’s, say, 5 bytes?

The first solution that comes to mind is either a for-loop or a call to a library function like memcpy. The for-loop would give something like:

char * dest = ...
char * src = ...
for (std::size_t i=0;i<5;i++) dest[i]=src[i];

If you’re lucky, the compiler understands the small copy and optimizes. More likely, it will merely unroll the loop and generate something like:

14d4:   0f b6 07    movzx  eax,BYTE PTR [rdi]
14df:   88 04 24    mov    BYTE PTR [rsp],al
14e2:   0f b6 47 01 movzx  eax,BYTE PTR [rdi+0x1]
14e6:   88 44 24 01 mov    BYTE PTR [rsp+0x1],al
14ea:   0f b6 47 02 movzx  eax,BYTE PTR [rdi+0x2]
14ee:   88 44 24 02 mov    BYTE PTR [rsp+0x2],al
14f2:   0f b6 47 03 movzx  eax,BYTE PTR [rdi+0x3]
14f6:   88 44 24 03 mov    BYTE PTR [rsp+0x3],al
14fa:   0f b6 47 04 movzx  eax,BYTE PTR [rdi+0x4]
14fe:   88 44 24 04 mov    BYTE PTR [rsp+0x4],al

Let’s see how we can fix that!

Read the rest of this entry »


The Well-Tempered Palette (Part 3)

July 24, 2018

This week, we’ll discuss a cool, but failed, experiment.

In the last few weeks (of posts, because in real time, I worked on that problem over a week-end) we’ve looked at how to generate well distributed, maximally different colors. The methods were to use well-distributed sequences or lattices to ensure that the colors are equidistant. What if we used physical analogies to push the colors around so that they are maximally apart?

Read the rest of this entry »


The Well-Tempered Palette (Part 2)

July 17, 2018

Last week, we’ve had a look at how to distribute maximally different colors on the RGB cube. But I also remarked that we could use some other color space, say HSV. How do we distribute colors uniformly in HSV space?

Read the rest of this entry »


The Well-Tempered Palette

July 10, 2018

When we use false color to encode useful information in an image, it helps greatly if the colors are meaningful in themselves (like a rainbow to encode heat) or maximally different when the image is segmented (like a map showing geologic provinces). But how do we chose those maximally different colors?

Somehow, we need a maximally distributed set of points in RGB space (but not necessarily RGB). We might have just what we need for this! We’ve discussed Halton sequences before. They’re a simple way of progressively and uniformly distribute points over an interval. The sequence starts by the ends of the interval then progressively fills the gaps. It generates the sequence 0, 1, 0.5, 0.25, 0.75, 0.125, 0.625, 0.375, 0.875, …

Read the rest of this entry »


HSV and HSL (colorpsaces XI)

July 3, 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 »


Linear Feedback Shift Registers (Generating Random Sequences XII)

June 26, 2018

While working on a project with a student, I had a look at linear feedback shift registers as a mean of generating (pseudo)random values. The principle isn’t very complicated: you select a number of bits in the register and use them to compute one bit value, you shift the register by one position and insert the new bit in the vacant spot.

Typically, the function is merely a series of exclusive ors, which basically computes the parity of the selected bits. This will help us create an efficient implementation—maybe using the compiler intrinsics.

Read the rest of this entry »