Open Source and the Workplace

Posted in Uncategorized on March 6, 2015 by Noah

Today, just a small post.

You should work someplace where you can write and publish open source software.

Not everything has to be open source, but something should be.

You should do it to give back.

You should do it to build your own reputation.

You should do it to be sure your workplace can do it — some say they want to, but in practice they can’t.

And perhaps most of all, because when a company asks you, “hey, what’s your GitHub profile?”, the correct answer includes, “… and also, where’s yours?

Git Merge Without Fast Forward

Posted in Uncategorized on February 27, 2015 by Noah

If you’re doing work in a branch and you want the branch marked as such, it’s a great idea to merge with no fast forward.

Normally, if you merge a branch into your git master branch, you can lose a record of the branch — if the branch is entirely after the head of master, its commits will just be folded in with no record of the branch having ever existed.

You can fix this problem by using “git merge –no-ff”, meaning “no fast forward.” That way you’re guaranteed to get a merge commit, which gives you a place to write a message, which lets you say something like “merged from noahs-zazzy-new-feature-branch”.

It’s a common thing to want to do.

x264 Rate Control (part one)

Posted in Uncategorized on February 20, 2015 by Noah

Overview of video encoder’s rate control

(For more on video encoding, see Is H265 Such An Enabling Technology for Cloud Gaming?)

A rate controller in a video encoder adjusts the quantization steps of macroblocks in video frames; as a result, the encoded video bitstream is maintained at a constant video quality, or more often at a constant bit rate (CBR) with constraints on frame size fluctuation.

Quantization is the process of mapping a large set of input values to a countable smaller set, usually by rounding values to some unit of precision.  The diagram below shows how analog signal samples are quantized to digital values.  Larger quantization step sizes cause bigger loss of signal fidelity; on the other hand, use less number of bits to represent the quantized results.  Therefore, the trade-off between video quality and bit rate cost can be realized by appropriate quantization steps being selected dynamically.

quantization

(Click any image for larger version)

Compressed video frames even in a CBR bit stream have different sizes (e.g., I-frame bigger than P-frame, P-frame bigger than B-frame, etc.).  The video bit rate is measured as the average rate of the bit stream over a period of time.  In order to constrain the maximum range of frame size fluctuation, there’s an important concept of VBV (video buffer verifier).  In the VBV model, the compressed video bit stream fills the buffer at a constant speed, i.e., video at a constant bit rate (see picture below).  On the other hand, complete compressed video frames are expected to be available in the buffer at regular time intervals, i.e., video can be played out at a constant frame rate.  The size of the VBV buffer determines the range of frame size fluctuation.  It is also the amount of memory that a decoder must have for buffering its incoming compressed bit stream, in order to achieve smooth playout.  The VBV buffer size directly affects the overall encoding/decoding latency: the bigger the size, the higher the latency.

02_VBV

x264’s rate control algorithm and implementation

x264’s rate control logic is contained in ratecontrol.h/c.  The control is performed at two levels (see the flowchart below):

  • frame level quant (quantization step) adaptation;
  • MB level quant adaption.

In this article, we only talk about the frame-level quant adaptation for real-time low-latency encoding (no 2nd pass, look ahead).  The MB-level control (per-row VBV level tracking, mb tree, adaptive quant) will be discussed in a separate blog article.  In the following sections, we will mainly explain two functions – x264_rate_control_start() and x264_rate_control_end().

03_block_diagram

x264_rate_control_start()

x264_rate_control_start() is called before the first macroblock of a frame is encoded.  It performs necessary computation to derive the quant for the frame to be encoded. It has 2 major subroutines:

  • update_vbv_plan() calculates the target VBV buffer level after the frame is encoded;
  • rate_estimate_qscale() calculates the quant of the frame, based on its SATD and the historical frame size/complexity stats.  If VBV constrains are specified, the VBV level is predicted based on the previous SATD/frame size/quant stats and quant is further adjusted according to the predicted VBV level.

The get_qscale() inside rate_estimate_qscale() computes the quant using the following equation:

04_equation1

where

04_equation2

Here the (-1) means the previous frame, (-2) means the frame before the previous frame, and so on.

The blurred_complexity is the SATD (sum of absolute transformed differences) of this and past frames.  SATD represents the amount of residual information, and can be regarded as linear to the encoded frame size. wanted_bits_windows and cplxr_sum are history frame-size and complexity stats, collected in x264_rate_control_end().

x264_rate_control_end()

x264_rate_control_end() is called after the last macroblock of a frame has been encoded.  It collects stats for next frame’s x264_rate_control_start().  Similarly, it also performs 2 tasks:

  • calculate wanted_bits_window and cplxr_sum;
  • update_vbv() updates the VBV level with the actual encoded frame size.

04_equation3

04_equation4

where 0.x is the decay constant.

So, wanted_bits_window is the low-pass-filtered nominal frame size, while cplxr_sum is the low-passed-filtered ratio between actual_frame_size times qscale and blurred_complexity to the power (1 – qcompress).

Finally, if we plug the equation 2,3,4 into 1, we can present the formula of frame-level quant as:

04_equation5

The quantization step is derived from the previous stats of actual frame size and quant step: if already in the stable scene and the the desired frame size being (bit rate / frame rate), the second part of the equation can give us the right quantization step for the next frame.  However, as every frame’s SATD is always different from the average, we scale the quant according to SATD: the bigger the SATD (picture is more difficult to encode), the higher the quant (so we won’t waste too many bits on the frame).

In the next article, we will explain how x264’s rate control meets the VBV constraints, i.e., how clip_qscale() at the frame level and x264_ratecontrol_mb_qp() at the macroblock level work.

CoffeeScript Subtleties: Hashes / Objects

Posted in Front End on February 6, 2015 by Noah

CoffeeScript has a fun syntax for declaring hash tables (aka JavaScript objects). It looks like this:

myhash =
  field1: "foo"
  field2: "blah"
  field3: 7

In fact, it has several different syntaxes for that:

myhash = { field1: "foo", field2: "blah" }
myhash = field1: "foo", field2: "blah"

You can’t declare the first field on one line and then continue multiline, though:

# Doesn't work
myhash = field1: "foo"
  field2: 7

The big thing is to watch out when using comprehensions:

# A list of hashes, each with three fields
{ field1: "foo", field2: i, field3: 7 } for i in [1, 2, 3]

BUT! This is different:

# A hash with three fields, the last of which is a list
field1: "foo", field2: i, field3: 7 for i in [1, 2, 3]

So watch your order of operations with list comprehensions, and don’t be afraid to use curly braces (as above) or parens:

# A list of hashes, each with three fields
( field1: "foo", field2: i, field3: 7 ) for i in [1, 2, 3]

Using tsql with FreeTDS to query MS SQL Server?

Posted in Uncategorized on January 23, 2015 by Noah

The tsql man page and user guide are wonderful about telling you all the ways it can fail. Yay!

They simply do not bother to tell you how to get it to do a SQL query. Boo!

Here’s the (very simple) secret:

tsql query

Type your query. Hit enter. Type “GO” (or “go” or “gO” or whatever) and hit enter.

Done.

Now you can see if your problem is, like mine, somewhere in tiny_tds or freetds or activerecord-sqlserver-adapter, or… And you don’t even have to read through tsql.c like I did.

And if you’re getting an argument error after the new year in 2015 in tiny_tds on Linux (only), it’s something wacky about how your datetime timestamps are getting parsed. It seems to be a problem in tiny_tds or ActiveRecord’s sqlserver adapter, not in FreeTDS — tsql reads the entries just fine, and that’s raw calls to FreeTDS.

Also, a query only reveals the problem if you actually return one or more timestamps, not if you get no rows returned. Now you know!

knowing_is_half

Rotate a Shaded D3 Globe with Moving Highlight

Posted in Front End on January 16, 2015 by Noah

D3 has some great world maps and globes. For instance click and drag on this one.

However, its extremely flexible projection model can make it hard to do tricks that might be easy in other frameworks. There’s no easy way to get a 3D-shaded spherical globe out there. Well, okay, maybe with WebGL, but that’s its own can of worms.

Luckily, you can cheat! (Link to code later in the post)

world_rotate

What Are We Working With?

For D3 world maps with TopoJSON, your choices are Canvas and SVG. Both work great. We’ll use SVG here. The only reason that winds up mattering is a single animated transition later, which you could also do in Canvas if you wanted.

But if you don’t want a simple flat square gradient, your only other choice is a flat radial (round) gradient. That’s true in both Canvas and SVG unless you want to shade pixel by pixel. And for speed reasons, you don’t.

blue radial gradient

You know how to exactly match a 3D sphere’s shading with a flat circular gradient perfectly, on a sphere that may be weirdly rotated, right?

Yeah, me either.

Background Image?

For a moving gradient, you can’t just drop in a background picture. Darn it.

I mean, you could. But then either it wouldn’t move, which defeats the whole point, or you’d need a video which is big and slow to load and scales funny.

Also, again, that whole “may be rotated in random directions” thing is a bear.

Implementation? Cheat!

So let’s talk about the cheat to use, shall we?

First off, there will be a brightest spot, wherever on Earth is closest to the sun. You can calculate that from the time of day, though it’s a tad annoying — see the code later for details. I pick the brightest longitude correctly from the time of day and say, “you know what? I declare the brightest latitude is always 45 degrees north.” Which is pretty, but completely inaccurate.

You can check whether a projected point is clipped, which lets you tell if the brightest point is on the visible side of the globe or the other one.

I then set up a radial gradient. If we’re dark-side-showing, I always use the same fairly dark blue gradient. If we’re light-side-showing, I pick a gradient centered at the very brightest point. I also use a two-step gradient in both cases, mostly so there can be a small very bright highlight and a larger, more subtle gradient around the edges. It works decently, as you can see from the visual.

This gives us everything except the sunlight fading in and out nicely, which is yet another simple cheat.

For that, I just keep a global variable. Did we just change from dark-side-showing to light-side-showing or vice versa? If so, do a simple animation on the gradient. If not, move the gradient center, but don’t change the colors.

What’s the Code Like?

The basic globe-and-rotation is based on one of the simpler D3 examples, and works the same way.

A lot more of the code is calculating the brightest spot and the gradient. Here it is on bl.ocks.org, for the full code.

I calculate the brightest spot like this:

// Calculate brightest and darkest longitudes
var current_time = new Date() - 0;
var day_in_millis = 24 * 60 * 60 * 1000;
var half_day = day_in_millis / 2;
var offset_from_day_start = current_time % day_in_millis;
var offset_from_noon = offset_from_day_start - half_day;
// The sun moves one degree of longitude every 240 seconds
var degrees_from_noon = parseInt(offset_from_noon / 240000.0);
if(degrees_from_noon >= 180.0)
  degrees_from_noon -= 360.0;

lightest_longitude = -degrees_from_noon;

I won’t copy-and-paste the code for creating and transitioning the gradient… But mostly it’s simple. Transition the center of it always. Transition the colors only if we just changed between dark and light. Check the runnable code on bl.ocks.org for full details.

What Does That Look Like?

The animated GIF up top is a screen capture of my actual example code, or you can see it on bl.ocks.org.

Let’s see that animated gif bigger this time. Click on it for full size.

(And yet the real D3 version is still smoother.)

world_rotate

CoffeeScript Comprehensions – Where’s My For/In Loop?

Posted in Front End on January 8, 2015 by Noah

CoffeeScript is a fun JavaScript generator. I love their style of documentation. I love that it’s sort of a weird hybrid of Ruby, YAML and JavaScript but it still reads well. I love that it’s really pretty weird, like most JavaScript.

But sometimes it takes me awhile to figure out the CoffeeScript way to do something.

Like loops.

Continue reading