Narabu is a new intraframe video codec. You probably want to read
part 1,
part 2,
part 3
and
part 4
first.
At this point, we've basically caught up with where I am, so thing are less
set in stone. However, let's look at what qualitatively differentiates
encoding from decoding; unlike in interframe video codecs (where you need
to do motion vector search and stuff), encoding and decoding are very much
mirror images of each other, so we can intuitively expect them to be
relatively similar in performance. The procedure is DCT, quantization,
entropy coding, and that's it.
One important difference is in the entropy coding. Since our rANS encoding
is non-adaptive (a choice made largely for simplicity, but also because
our streams are so short) works by first signaling a distribution and then
encoding each coefficient using that distribution. However, we don't know
that distribution until we've DCT-ed all blocks in the picture, so we can't
just DCT each block and entropy code the coefficients on-the-fly.
There are a few ways to deal with this:
- DCT and quantize first, then store to a temporary array, count up all the
values, make rANS distributions, and then entropy code from that array.
This is conceptually the simplest, but see below.
- Use some sort of approximate distribution, which also saves us from doing
the actual counting. This has the problem that
different images look different, so it loses efficiency (and could do so
quite badly). Furthermore, it means this approximate distribution could
never have a 0 for any frequency, which also is a net-negative when we're
talking about only 12-bit resolution.
- Use the values from the previous frame, since video tends to have
correlation between frames (and we can thus expect the distribution to
be a better fit than some generic distribution decided ahead of time).
Has many of the same problems as previous point, though, plus we get
back the overhead of counting. Still, an interesting possibility that
I haven't tried in practice yet.
- Do DCT and quantization just to get the values for counting, then do
it all over again later when we have the distribution. Saves the store
to the temporary array (the loads will be the same, since we need to
load the image twice), at the cost of doing DCT twice. I haven't tried
this either.
- A variant on the previous one: Do DCT on a few random blocks (10%?)
to get an approximate distribution. I did something similar to this
at some point, and it was surprisingly good, but I haven't gone further
with it.
As you can see, tons of possible strategies here. For simplicity, I've ended
up with the former, although this could very well be changed at some point.
There are some interesting subproblems, though:
First of all, we need to decide the data type of this temporary array.
The DCT tends to concentrate energy into fewer coefficients (which is
a great property for compression!), so even after quantization, some of
them will get quite large. This means we cannot store them in an 8-bit
texture; however, even the bigger ones are very rarely bigger than 10 bits
(including a sign bit), so using 16-bit textures wastes precious memory
bandwidth.
I ended up slicing the coefficients by horizontal index and then pairing
them up (so that we generate pairs 0+7, 1+6, 2+5 and 3+4 for the first line
of the 8x8 DCT block, 8+15, 9+14, 10+13 and 11+12 for the next line, etc.).
This allows us to pack two coefficients into a 16-bit texture, for an
average of 8 bits per coefficient, which is what we want. It makes for
some slightly fiddly clamping and bit-packing since we are packing signed
values, but nothing really bad.
Second, and perhaps surprisingly enough, counting efficiently is nontrivial.
We want a histogram over what coefficients are used the more often, ie.,
for each coefficient, we want something like
++counts[dist][coeff]
(recall we have four distinct distributions). However, since we're in a
massively parallel algorithm, this add needs to be atomic, and since values
like e.g. 0 are super-common, all of our GPU cores will end up fighting over
the cache line containing
counts[dist][0]. This is not fast.
Think 10 ms/frame not fast.
Local memory to the rescue again; all modern GPUs have fast atomic adds
to local memory (basically integrating adders into the cache, as I understand
it, although I might have misunderstood here). This means we just make a
suitably large local group, build up our sub-histogram in local memory and
then add all nonzero buckets (atomically) to the global histogram. This
improved performance
dramatically, to the point where it was well below 0.1
ms/frame.
However, our histogram is still a bit raw; it sums to 1280x720 = 921,600
values, but we want an approximation that sums to exactly 4096 (12 bits), with
some additional constraints (like no nonzero coefficients). Charles Bloom has
an exposition of a nearly optimal algorithm,
although it took me a while to understand it. The basic idea is: Make a good
approximation by multiplying each frequency by 4096/921600 (rounding
intelligently). This will give you something that very nearly rounds to
4096 either above or below, e.g. 4101. For each step you're above or below
the total (five in this case), find the best single coefficient to adjust (most entropy gain, or least
loss); Bloom is using a heap, but on the GPU, each core is slow but we have
many of them, so it's better just to try all 256 possibilities in parallel
and have a simple voting scheme through local memory to find the best one.
And then finally, we want a cumulative distribution function, but that is
simple through a parallel prefix sum on the 256 elements.
And then finally, we can take our DCT coefficients and the finished rANS
distribution, and write the data! We'll have to leave some headroom for
the streams (I've allowed 1 kB for each, which should be ample except for
adversarial data and we'll probably solve that just by truncating the
writes and accepting the corruption), but we'll compact them when we write to
disk.
Of course, the Achilles heel here is performance. Where decoding 720p (luma only)
on my GTX 950 took 0,4 ms or so, encoding is 1,2 ms or so, which is just too
slow. Remember that 4:2:2 is twice that, and we want multiple streams, so
2,4 ms per frame is eating too much. I don't really know why it's so slow;
the DCT isn't bad, the histogram counting is fast, it's just the rANS shader
that's slow for some reason I don't understand, and also haven't had the time
to really dive deeply into. Of course, a faster GPU would be faster, but I
don't think I can reasonably demand that people get a 1080 just to encode
a few video streams.
Due to this, I haven't really worked out the last few kinks. In particular,
I haven't implemented DC coefficient prediction (it needs to be done before
tallying up the histograms, so it can be a bit tricky to do efficiently,
although perhaps local memory will help again to send data between
neighboring DCT blocks). And I also haven't properly done bounds checking
in the encoder or decoder, but it should hopefully be simple as long as
we're willing to accept that evil input decodes into garbage instead of
flagging errors explicitly. It also depends on a GLSL extension that my
Haswell laptop doesn't have to get 64-bit divides when precalculating the
rANS tables; I've got some code to simulate 64-bit divides using 32-bit,
but it doesn't work yet.
The code as it currently stands is in
this Git repository;
you can consider it licensed under GPLv3. It's really not very user-friendly
at this point, though, and rather rough around the edges.
Next time, we'll wrap up with some performance numbers. Unless I magically
get more spare time in the meantime and/or some epiphany about how to make
the encoder faster. :-)
A unit is a part of your program you can test in isolation. You write
unit tests to test all aspects of it that you care about. If all your
unit tests pass, you should know that your unit works well.
Integration tests are for testing that when your various well-tested,
high quality units are combined, integrated, they work together.
Integration tests test the integration, not the individual units.
You could think of building a car. Your units are the ball bearings,
axles, wheels, brakes, etc. Your unit tests for the ball bearings
might test, for example, that they can handle a billion rotations, at
various temperatures, etc. Your integration test would assume the ball
bearings work, and should instead test that the ball bearings are
installed in the right way so that the car, as whole, can run a
kilometers, and accelerate and brake every kilometer, uses only so
much fuel, produces only so much pollution, and doesn't kill
passengers in case of a crash.
As a cat owner, being surprised by cat intelligence delights me. They re not exactly smart like a human, but they are smart in cattish ways. The more I watch them and try to sort out what they re thinking, the more it pleases me to discover they can solve problems and adapt in recognizably intelligent ways, sometimes unique to each individual cat. Each time that happens, it evokes in me affectionate wonder.
Today, I had one of those joyful moments.
First, you need to understand that some months ago, I thought I had my male cat all figured out with respect to mealtimes. I had been cleaning up after my oafish boy who made a watery mess on the floor from his mother s bowl each morning. I was slightly annoyed, but was mostly curious, and had a hunch. A quick search of the web confirmed it: my cat was left-handed. Not only that, but I learned this is typical for males, whereas females tend to be right-handed. Right away, I knew what I had to do: I adjusted the position of their water bowls relative to their food, swapping them from right to left; the messy morning feedings ceased. I congratulated myself for my cleverness.
You see, after the swap, as he hooked the kibbles with his left paw out of the right-hand bowl, they would land immediately on the floor where he could give them chase. The swap caused the messes to cease because before, his left-handed scoops would land the kibbles in the water to the right; he would then have to scoop the kibble out onto the floor, sprinkling water everywhere! Furthermore, the sodden kibble tended to not skitter so much, decreasing his fun. Or so I thought. Clearly, I reasoned, having sated himself on the entire contents of his own bowl, he turned to pilfering his mother s leftovers for some exciting kittenish play. I had evidence to back it up, too: he and his mother both seem to enjoy this game, a regular fixture of their mealtime routines. She, too, is adept at hooking out the kibbles, though mysteriously, without making a mess in her water, whichever way the bowls are oriented. I chalked this up to his general clumsiness of movement vs. her daintiness and precision, something I had observed many times before.
Come to think of it, lately, I ve been seeing more mess around his mother s bowl again. Hmm. I don t know why I didn t stop to consider why
And then my cat surprised me again.
This morning, with Shadow behind my back as I sat at my computer, finishing up his morning meal at his mother s bowl, I thought I heard something odd. Or rather, I didn t hear something. The familiar skitter-skitter sound of kibbles evading capture was missing. So I turned and looked. My dear, devious boy had squished his overgrown body behind his mother s bowls, nudging them ever so slightly askew to fit the small space. Now the bowl orientation was swapped back again. Stunned, I watched him carefully flip out a kibble with his left paw. Plop! Into the water on the right. Concentrating, he fished for it. A miss! He casually licked the water from his paw. Another try. Swoop! Plop, onto the floor. No chase now, just satisfied munching of his somewhat mushy kibble. And then it dawned on me that I had got it somewhat wrong. Yes, he enjoyed Chase the Kibble, like his mom, but I never recognized he had been indulging in a favourite pastime, peculiarly his own
I had judged his mealtime messes as accidents, a very human way of thinking about my problem. Little did I know, it was deliberate! His private game was Bobbing for Kibbles. I don t know if it s the altered texture, or dabbling in the bowl, but whatever the reason, due to my meddling, he had been deprived of this pleasure. No worries, a thwarted cat will find a way. And that is the joy of cat intelligence.
Before I start, I would like to make it clear that the below is entirely my personal view, and not necessarily that of the GNOME Foundation, the Debian Project, or anyone else.
There s been quite a bit of interest recently about the petition by Software Freedom Law Center to cancel the Software Freedom Conservancy s trademark. A number of people have asked my views on it, so I thought I d write up a quick blog on my experience with SFLC and Conservancy both during my time as Debian Project Leader, and since.
It s clear to me that for some time, there s been quite a bit of animosity between SFLC and Conservancy, which for me started to become apparent around the time of the large debate over ZFS on Linux. I talked about this in my DebConf 16 talk, which fortunately was 
A shiny new (mostly-but-not-completely maintenance) release of 
Like many laptop users, I often plug my laptop into different monitor
setups (multiple monitors at my desk, projector when presenting, etc.)
Running xrandr commands or clicking through interfaces gets tedious,
and writing scripts isn't much better.
Recently, I ran
across 
](http://jmtd.net/log/coil/400x-coil.jpg)
