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.
While this sounds something like a shameful family secret, discrete inversion is only the finite-valued variation on the method of inversion for the generation of random numbers with a given distribution (as I’ve discussed quite a while ago here). The case we’ll consider here is a random variable with few possible outcomes, each with different odds
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!
Quite a while ago, I presented my own simple, sed, grep and bash-based make-depend script. It was simple, and somewhat effective, except for the fact that it did not see include-only dependencies nor quote-includes. If you changed a header affecting a lot of things, it would not rebuild, because the make rules were incomplete. Let’s fix this.
The original plan was to come back in september 2018, but it turns out, I was rather busy with everything else. I missed blogging, so I’ve decided to continue, but it will be at a much softer rate of about a post of month, rather than once a week.
This is my tenth anniversary of blogging. I started back in 2008, and since then there has been 586 posts (including this one), about 1300 comments, 170 followers, 325000 visitors, and 825000 views, with a few posts well over 9000.
Well, that’s not bad, but for now, I must reconsider the time I invested, and will continue to invest in this blog. Posting once a week, even with the summer hiatuses, is becoming a strenuous pace, especially that I also have—many—other things to do. So I was tempted to just end it, and say, well, after ten years, it’s much better than your average two-post blog, let’s call it quits. But the thing is, I enjoy writing about the things I do, the math I work out, and other ideas. But I will likely stop for this month, then be back with once-a-month posting.
‘Till then, it’s summer. Let’s enjoy it.