text:
Blitter Theory Part 1

# Blitter Theory, Part 1

For the past couple of days, I've been wanting to write some code that renders proportionally-spaced fonts to the screen. Not only does it need to support normal rendering, but in the absence of a dedicated italic font, it should at least attempt to synthesize an italic representation by skewing the characters. The problem sounds so simple, until you actually attempt to code something up.

After almost as long a period of time researching stuff through Google, I have come to the conclusion that it is of nobody's interest to understand how these algorithms work. Not one public website I've visited has had any explanation of this stuff. As a result, I've had to re-invent the wheel myself. Although I have access to the source code for GEOS/64, the assembly language listing is not commented in any meaningful way, which means I have to resort to plan B: derive a software blitter from first principles.

Now, I understand how the Amiga's own blitter is architected, and that knowledge has helped in some respects. But, let us be honest with ourselves: replicating the hardware, and knowing why it works are two fundamentally different problems. I can attempt to do the former, but in the event of a bug (and there will be plenty), how do I fix it? Do I just tweak what I think the problem is?

As a result, I'm going to resort to my old stand-by, which I've blogged about before: functional analysis. Yes, folks, you're about to see a real-world example of FA as it is applied to the Kestrel's blitter software. Since the intention is for printing text to the screen, my terms will focus on those applications. However, it should be noted that the software discussed in this article is general purpose, and with a bit of creativity, may be (re-)used to implement other graphical features too.

## The Obvious

Let $R_{x}$ refer to a matrix of 16-bit words $W_{x_{ij}}$ representing the bits of a bitmap. The largest values of $i$ and $j$ can be derived from a Bitmap descriptor belonging to $x$, but that will not concern us at this level. Let's also assume the existence of a function that operates on rows or lines (terms I use interchangeably) of these matrices, $F_L$. There are several kinds of functions you can possibly want (OSes like AmigaOS, which exploits a hardware blitter, provides up to 256 different functions!). For simplicity, however, we're only going to consider one: the simple logical-OR.

Then, we can succinctly express the entire operation of a blitter in this simple formula.

(1)
\begin{align} R_{D} = map2\,F_{L}\,R_{C}\,R_{S} \end{align}

The elegance of the solution ends here, unfortunately. I hope you've taken your pills; we're about to go down the rabbit hole.

Before I go on, though, the probability that you understand map is pretty slim. I'll show it by example below. If you've ever written code of this form before:

; iterate over some collection or other, and do something useful with it.
ldx #nElements*2
loop:
lda someData,x
jsr doSomethingWithTheData
dex
dex
bne loop

That is a map. What you've done is taken a function (doSomethingWithTheData in this case) designed to operate on a single datum, and extended it to work on a whole collection by factoring out the iteration over the collection. "But, that is common sense!" I hear you say. Of course it is. But common sense and formal logic do not always agree, but when it does, you find that formal names are given to certain concepts. Here's the above machine language code written more formally:

(2)
\begin{align} &map\,\,f\,\,[] = []\\ &map\,\,f\,\,(x:xs) = (f\,\,x):(map\,\,f\,\,xs) \end{align}

To explain fully how the mapping (sorry, but it works here too!) works, you'd need to try hacking around in a functional programming language, or take a class or two in formal logic. That is beyond the scope of this article; that a mapping does exist is what takes priority.

You'll find functions like fold and map2 in the equations I'll be writing. These are just different kinds of iteration that each have their own properties. A fold, for example, is very similar to a map, but it differs in that the state of a computation is threaded from element to element in an accumulator variable. map2 is a function that maps a 2-operand function onto two lists to produce a third.

## Characters

A bitmapped font is, well, a collection of letters strewn out on a bitmap. This means we can express a single character by finding its bitmap descriptor. This means that we point the bm_bits field inside the font's bitmap, making sure to word-align the address of course. Then, because the character of interest needn't fall on column 0 of the first word, we need to record the starting column of the character as well. We'll let $x_{C}$ refer to character C's left edge inside that bitmap. Oh, by now, you're probably thinking (correctly) that $R_{C}$ is the character's bitmap.

With this in mind, we can define a character bitmap algebraically:

(3)
\begin{align} R_{C} = fst\,(fold\,(skew\,\delta)\,([]\,0\,0)\,R_{C}^{'}) \end{align}

YIKES! Wait; it gets better later on. But, for now, we'll concentrate on skew, a function responsible for optionally skewing the character for the purposes of synthesizing an italic representation of a font if needed. $\delta$ is the "skew period." If we let $\delta=3$, for example, it means that our font will slip one pixel to the right after every three rows drawn. Computers like the Apple IIgs have $\delta=4$, which means that an 8-pixel tall font will barely have any noticeable skew. However, the Amiga's graphics.library used $\delta=2$, which actually produced a bit too much skew. I've settled on 3 since it's nicely between these extremes.

What you're probably wondering about most is what the heck a fold operation is. It is a function that performs implicit iteration over a collection. It takes as arguments the function you want to call for each item in the list, a starting value which is used as an accumulator between invocations, and finally the list itself. So, $(skew\,\delta)$ is the function we wish to apply to each row in the bitmap. $([],0,0)$ is the accumulator's initial value. I'll get to the different components in a bit. And, of course, $R_{C}^{'}$ is the raw character bitmap data. Since the result of a fold is of the same type as its accumulator, we use $fst$ to extract the first field of the tuple, namely the list of altered rows.

Skew is defined like so:

(4)
\begin{align} skew\,&m\,(rs_{i},\epsilon_{i},\alpha_{i})\,r = \text{if}\,(\epsilon_{i}+m) \ge 1\, & \text{then}\,(rs^{'}_{i+1}, \epsilon^{'}_{i+1}, \alpha^{'}_{i+1})\\ &&\text{else}\,(rs^{''}_{i+1}, \epsilon^{''}_{i+1}, \alpha^{''}_{i+1})\\ &\text{where:}\\ &rs^{'}_{i+1} = rs_{i} : (shiftRight\,r\,(\alpha_{i}+1))\\ &\epsilon^{'}_{i+1} = (\epsilon_{i}+m)-1\\ &\alpha^{'}_{i+1} = \alpha_{i}+1\\ &rs^{''}_{i+1} = rs_{i} : (shiftRight\,r\,\alpha_{i})\\ &\epsilon^{''}_{i+1} = \epsilon_{i}+m\\ &\alpha^{''}_{i+1} = \alpha_{i} \end{align}

This crazy expression models the synthesis of italic print by simple skewing. Here, $m=\frac{1}{\delta}$ is our slope, $rs_{i}$ is the accumulated rows of the bitmap, $\epsilon_{i}$ is the accumulated error term, $\alpha_{i}$ represents the current shift offset in pixels, and $r$ represents the row we're currently processing.

Here's a proof by induction for you, to prove that it works.

If our font bitmap happens to have zero rows, then the fold operation will immediate just return the accumulator value, which is just ([],0,0), remember? Taking $fst\,([],\dots)=[]$, which is as expected — skewing an empty bitmap results in an empty bitmap.

If our font bitmap has precisely one row, then the result will depend on the initial value of $\epsilon_{i}$ and $m$. If $m=\frac{1}{\delta}$ and $\delta=3$, then clearly $\epsilon_{i}$ must be given an initial of at least 3 to produce a single-pixel skew. Since blitter formula always sets $\epsilon_{i}$ to zero in the fold, we never have to worry about this particular caveat. Therefore, skewing a single-line bitmap will produce precisely the same single-line bitmap, as we expect.

If our font has a height greater than one, say two in this case, and we assume that $m=\frac{1}{2}$, then for the first row $r_{0}$:

(5)
\begin{aligned} skew\, \frac{1}{2}\, ([],0,0)\, r_{0} &= \text{if }\left(0+\frac{1}{2}\right)\ge1\text{ then }\cdots\text{ else }\left([]:(shiftRight\,r_{0}\,0), 0+\frac{1}{2}, 0\right)\\ &=\left([(r_{0}\gg0)], \frac{1}{2}, 0\right) \end{aligned}

Note that $\forall r.$r\gg0=r$, so our base case for the skew function is demonstrated. For subsequent rows on the threshold of needing to be shifted, however, we'll look at the case of the second row$r_{1}in our little example: (6) \begin{aligned} skew\, \frac{1}{2}\, \left([r_{0}],\frac{1}{2},0\right)\, r_{1} &= \text{if }\left(\frac{1}{2}+\frac{1}{2}\right)\ge1\text{ then }\left([r_{0}]:(shiftRight\,r_{1}\,1), \frac{1}{2}+\frac{1}{2}-1, 0+1\right)\\ &\text{ else }\cdots\\ &=\left([(r_{0}\gg0), (r_{1}\gg1)], 0, 1\right) \end{aligned} As we can see, our second scanline is shifted by one pixel, as expected. Additionally, our error term is reset, and we "remember" our new pixel offset in\alpha_{i+1}$. Therefore, inductively, we have proven the soundness of the skew function's design. And, we know it must work. Or do we? Shouldn't$r_{0}$represent the bottom of the character's bitmap if the skew is to occur to the right? That is absolutely correct — by "looking at the math," we can divine a software requirement that we previously didn't know before. But let's not forget our focus here; whether we start at the top and work our way down, or vice versa, is a pointer arithmetic issue. It has no concrete bearing on the abstract description of the operation we're trying to perform. Besides, we're not going to code this in a Haskell environment (although if you really want to be thorough, I encourage the practice; I no doubt have a metric #!@%-load of type errors in my analysis so far. But as long as the reader gets it "good enough," that's all that really matters at this point). Not one thing here relies on any state monads, which is nice, because it makes clear that the skew function is not only unit testable, but it also shows how one can go about unit testing it. In fact, inductive proofs, like the one I did above, is really a form of unit testing. For this reason alone, the fact that the abstract can be reasoned about algebraically is of immense value, and doesn't seem to be appreciated by most programmers I meet. Incidentally, what happens if we don't want to skew our character when drawing? By setting$\delta=H,\,m=\frac{1}{\delta}=\frac{1}{H}$, we make it so that the skew threshold exceeds the number of rows being drawn. Therefore, our skewing engine is effectively disabled. Now that we've proven our model/algorithm for skewing character images works for our needs, we turn our attention to$R^{'}_C. Remember that a Bitmap descriptor can only reference a bitmap correctly if the bm_bits field points to a word-aligned chunk of data. This doesn't necessarily mean that bit 0 of the address be zero (although for other CPUs like the 68000, it certainly does mean this). It just means that it points to an even byte in the bitmap itself. For example, you can have a bitmap's data placed at an address ofABCD, which is certainly an odd address from the point of view of address line A0 being asserted. But, since that's the first byte of a row, and all rows have an even number of bytes in them, then it is still word-aligned from the perspective of the bitmap.

Even if we could enforce the requirement that each character's bitmap be naturally aligned, we cannot guarantee that the destination bitmap's text cursor sits on such a nice boundary. In fact, there is only 1-in-16 chance that it will! If font characters are nicely aligned on word boundaries in the font's bitmap, then the average amount of shifting that would be needed (over a longish period of time) should come out to be about 8 pixels. Now, if we allow the characters to also float in the font's bitmap, then we should see this average reduce to about 4 pixels. In other words, it may full well be to our advantage to allow the complexity that comes with characters not aligning with natural word boundaries! (How to [dis]prove this mathematically is outside of my realm of knowledge, but I'd like to analyze this rigorously some day.)

Therefore, knowing that shifting character bits from the font bitmap to their final resting place in the destination's bitmap early, we can now define what $R^{'}_C$ is:

(7)

$R^{0}_{C}$ is the actual bitmap describing the character right from the raw font bitmap. It is relatively easily computed from the font's own bitmap, so we won't discuss it here. Instead, we note that we're composing to line-oriented functions here: $masked_{L}$ and $shifted_{L}$. Since the latter is evaluated first, we'll examine it first.

Recognizing that the left-hand column of a character can appear anywhere in the bitmap, then it follows that we can shift it either left or right. Therefore, we account for this in the definition of $shifted_{L}$:

(8)
\begin{align} shifted_{L}\,r = \text{if }\Delta > 0&\text{ then }shiftRight_{L}\,\,r\,\,\Delta\\ &\text{ else }shiftLeft_{L}\,\,r\,\,(-\Delta) \end{align}

This seems pretty straight forward: depending on the sign of the displacement $\Delta=l_{D}-x_{C}$ from the source alignment to the destination's alignment, either shift the row left or right by $|\Delta|$ bits. The right-shift is defined as follows (left-shift is structurally identical; just swap the $\gg$ and $\ll$ operators):

(9)
\begin{align} &shiftRight_{L}\,\,rs\,\,d=fst \left(fold\,\,(shr\,\,d)\,\,([], 0)\,\,rs\right)\\ &shr\,\,d\,\,(ws, \omega)\,\,w=(ws^{'}, \omega^{'})\\ \text{where: }\\ &ws^{'} = ws : \left((w \gg d) \vee \omega\right)\\ &\omega^{'} = w \ll (16-d) \end{align}

Let's prove this works correctly. Our first case is when the supplied displacement $d$ is zero. In this case:

(10)
\begin{align} shr\,\,0\,\,([], 0)\,\,w&=\left([]:\left((w \gg 0) \vee 0\right), (w \ll 16)\right)\\ &=([w], 0) \end{align}

Shifting by zero produces no change from the input to the output, as we expect. For subsequent words:

(11)
\begin{align} shr\,\,0\,\,([\dots, w_{n}], 0)\,\,w&=\left([\dots, w_{n}]:\left((w \gg 0) \vee 0\right), (w \ll 16)\right)\\ &=([\dots, w_{n}, w], 0) \end{align}

Thus, inductively, the shifter works for a zero displacement. The next case to prove is when $d\not=0$. Starting with the first word:

(12)
\begin{align} shr\,\,3\,\,([], 0)\,\,w_{0}&=\left([]:\left((w_{0} \gg 3) \vee 0\right), (w_{0} \ll 13)\right)\\ &=\left([\frac{w_{0}}{8}], 2^{13}(w_{0} \mod 8)\right) \end{align}

The first word is divided by 8, which is to be expected since we're shifting right 3 positions. We also see that we're prepared for the next by "remembering" the least significant bits of $w$. To avoid some pretty hairy equations that just run off the edge of the page, I'm going to define a convenience functions $\chi\,\,x=2^{13}(x\mod 8)$:

(13)
\begin{align} shr 3 ([\dots, \frac{w_n}{8}+(\chi w_{n-1})], (\chi w_{n})) w&=\left(\left[\dots, \frac{w_{n}}{8}+(\chi\,\,w_{n-1})\right]:\left((w \gg 3) \vee (\chi\,\,w_{n})\right), (w \ll 13)\right)\\ &=\left(\left[\dots, \frac{w_{n}}{8}+(\chi\,\,w_{n-1}), \frac{w}{8}+(\chi\,\,w_{n})\right], (\chi\,\,w)\right) \end{align}

Therefore, we see that the right-shift operates as expected with non-zero displacements, provided $0\le d < 16$. The fold takes care of iterating over the row for us, so we don't have to worry about that mechanism (yet).

After we shift a row, we are undoubtedly going to have some bogus bits left over, particularly if we don't shift 15 places. Therefore, we're going to need to mask off those extraneous bits. This is the job of the $masked_{L}$ function:

(14)

The result of $mask\,\,l\,\,r$ is a bit vector spanning the width of our bitmap, with 1s where we allow the character's data to fall through (in the range $[l, r)$), and 0s elsewhere to mask the unused data out. We then logically-AND ($\wedge$) this bit-vector against our row to extract just the character we want. Notice that we generate the character's window over the destination's coordinate range, not that of the source. This is why we first shift the character's image.

Note that it is technically possible to reverse the order of operations here — you could mask first, then shift. In this case, you'd obviously want to use the character's coordinates instead of the destination's.

As you might have guessed by now, $l_{D}$ is the left-edge of where to place the glyph. This corresponds to the current application cursor location in the bitmap. However, we need to compute:

(15)
\begin{align} r_{D} = l_{D} + W_{C}\\ \end{align}
(16)
$$W_{C} = x_{C+1} - x_{C}$$

where $W_{C}$ is the width of the selected character. Notice how the width is determined by subtracting the right edge of the character (which is the same as the left-edge of the next character) from the left-edge. This isn't the only way to find this value, of course. Some systems, like AmigaOS, have a table of character widths that they can look up.

## Source Bitmap

Remarkably, after all that heady math, where I demonstrate just enough knowledge and understanding to prove how utterly inept I am at this stuff, I can say this much about the source bitmap:

(17)
I should make clear an assumption at this time: all this time, I anticipated printing text with both foreground and background fill. That is, if I print "HELLO" on the screen, I'd see a black hello on a white background, regardless of the background's previous contents. If you do not want an opaque background for the text, you can just set $R_{S}=R_{S}^{0}$ and bingo, you'll have text rendered with transparency.


text:
# Parameters

## Recommended Posts

I understand what parameters anf arguements are used for, however when I try to use my own I get errors. Can anyone explain the correct syntax?

##### Share on other sites
Show us your code, and the errors.

It could take quite some time for us to guess the problem you are having [grin].

If it helps, arguments appear like this:

functionReturnType functionName( argument1Type name1, argument2Type name2 /* and so on */ );

So an example:

int add( int x, int y ){   return x + y;}

##### Share on other sites
I think you'll have to be more specific. For instance, what language are you programming in? What IDE are you using? Do you have an example of code that didn't work? Do you have an example from a book that you're trying to emulate?

EDIT: Too slow!

##### Share on other sites
Your learning resource can most likely, if it can't then it isn't good enough. If you want us to help you you need to specify at least three things:
1) Your language (C, C++, C#, Scheme, F#, Java or something else?)
2) The code which doesn't work
3) The error you get (does the code behave odd? does it give you a compile time error? Or does it start shouting?)

In C and C++ the correct syntax is:
return-type identifier(type1 id1,type2 id2,type3 id3 ... typen idn);

So for a function returning void and taking two int paramters you would do this:
void func(int a,int b);

Possibly with another function and parameter names.

##### Share on other sites
//Function to take two numbers and add them together.int addNums(int num1, int num2) {    return (num1 + num2);}

In that function num1, and num2 are arguments. You would use the fuction as such:
myInt = addNums(1, 2);

Then myInt would equal three. Arguments can be anything you want them to be. You have strings, ints, floats, doubles, chars, vector<*ints>, etc... The thing to keep in mind is that if you make a function that takes a integer, don't pass it a string or issues will result. If you need a solitary function to take many differant types of arguments but perform similer things on each type you can use polymorphism(I think thats the correct term). For example, to make addNums take doubles, floats and ints you would do the following.

//Function to take two numbers and add them together.int addNums(int num1, int num2) {    return (num1 + num2);}float addNums(float num1, float num2) {    return (num1 + num2);}double addNums(double num1, double num2) {    return (num1 + num2);}

The complier will then use the correct function based off of how you call it. For example.

myFlt = addNums(1.0f, 2.0f); Calls the second function.
myDbl = addNums(1.00, 2.00); Calls the third function.

I hope this has helped.

##### Share on other sites
I am using C++ and the compiler is the G++ compiler that comes with the Fedora O/S. The error I am trying to fix is a compile time error say in:

#include

using namespace std;

string getName(string);

int main()
{
string name;

getName();
return 0;
}

string getName()
{
string name;

cout > name;

return name;
}

{
cout <

##### Share on other sites
[quote]Original post by Anonymous Poster
I am using C++ and the compiler is the G++ compiler that comes with the Fedora O/S. The error I am trying to fix is a compile time error say in:

#include //Include what, exactly here?using namespace std;string getName(string);void addName(string);int main(){  string name;  //This call to getName doesn't assign what is returned to anything at all  //When a function returns something that you want, you need to actually do  //something with the results - however, make sure you read the notes in the  //function itself, below  getName();  //Perhaps the line should have been... :  name = getName();  //assigns the returned value (string) to name  //Otherwise, if you didn't assign the value above, when you call *this*  //function, you're sending it a string variable that has not been  //initialized to anything at all. - error  addName(name);  return 0;}string getName(){  string name;    //This isn't the correct syntax for the cout statement...  cout > name;  //The line should be:  cout << name;  //However, as in the main function, you're attempting to cout a value  //from a variable that has not been initialized yet. In other words,  //name needs to have something assigned to it before you can cout it or  //return it. What is this function's purpose? Have the user type it in?  //If so, get rid of cout and use cin:  cout << "Please enter a name: ";  cin >> name;  //this will allow the user to type in a name  return name; //this would now have something to return. Otherwise, you're               //trying to return something that doesn't have a value yet}void addName(name){  //Not sure what happened to the rest of the code here, so I have nothing here  cout <

[/quote]

HTH :)
Scorp

EDIT - GRRRRRRRR At getting source posts to quit turning my < into & lt !

##### Share on other sites
On your addName function you need to specifiy a type for the paramter.

theTroll

##### Share on other sites
Sorry about that, I hit the wrong button and didn't notice until I was able to get back online today.

I ended up fixing the problem, I had tp make a global declaration of my string variable name. Also in any other function I wanted to use a param with I had to make the varaible that I was passing global. Is this something that has to be done at all times?

//now code looks like this #include <iostream>#include <string>using namespace std;string name;  // here is the global declaration of my string variablevoid addName(string);string getName();int main(){  getName();  addName(name);}string getName(){  cout << "Enter Name:" << endl;  cin >> name; return name;}void addName(string){  cout << name << " is the name that I typed in" << endl;}

This works when I compile and run it, but I didn't think that I would have to make variables to be used as parameters global...

Thanks Everyone

##### Share on other sites
Quote:
 Original post by up in flamesSorry about that, I hit the wrong button and didn't notice until I was able to get back online today.I ended up fixing the problem, I had tp make a global declaration of my string variable name. Also in any other function I wanted to use a param with I had to make the varaible that I was passing global. Is this something that has to be done at all times? *** Source Snippet Removed ***This works when I compile and run it, but I didn't think that I would have to make variables to be used as parameters global...Thanks Everyone

OK you shouldn't have to use a global. In your addName function declaration you are providing a string parameter, which is allright, but in you function definition you have left out a parameter identifier.

Your function should be addName(string name) and thereby you'll use the string given in main. Here is the altered code:

//now code looks like this #include <iostream>#include <string>using namespace std;// prototypesvoid addName(string);string getName();int main(){  string name;  name = getName();  addName(name);return 0;}string getName(){  cout << "Enter Name: " << endl;  cin >> name;   return name;}void addName(string name) // now name will be used in this function scope{  cout << name << " is the name that I typed in" << endl;}

EDIT: Oh yeah remember to add a return value to your main

[Edited by - thallish on August 20, 2006 4:48:41 PM]

##### Share on other sites
You don't have to define arguments globally...You certainly don't have too. The problem is that you you're functions in an other way. You do:

string name;Function(string){  cout << name;}

But it should be:

Function(string name){  cout << name;}

You declare the variable and it's type inside the function like:

Function(string name);

And then the function uses that string you just defined:

{
cout << name;
}

Remember the variable name will be deletet/removed/destroyed when the function has ended.

Hope that helped

-Stenny

---P.S.---
And for the others out there: I might have swapped the words declared and defined but I just can't remember their meaning[grin]. Feel free to correct this if you want.
---/P.S.---

format: plain


text:
# Blog Archive

Viewing page 1 from archive of February 2015

# When to NOT Linearize Your Textures

## Although most images are non-linear, sometimes you should leave them that way.

Knowing how and when to deal with colour spaces in your textures files is crucial to a realistic rendering workflow.

In short: since monitors are usually non-linear devices, image files are generally stored with the inverse non-linearity baked in (the general example of which is sRGB). Since rendering calculations work in a linear space, you must convert your images back to the linear space before using them otherwise your renders will not be accurate.

While it is key that you linearize your colour textures (e.g. diffuse, specular colour, etc.), you must be very thoughtful of doing the same with your data textures (e.g. displacement, bump, etc.).

For example, lets look at a displacement:

Read more... (1 minute remaining to read.)

Posted . Categories: .

# Inadvertent Algorithmic Cruelty

## Well, that escalated quickly.

Eric Meyer, like many others, hasn't had the best of years. Facebook's "Year in Review" app inadvertently rubbed it in his face, as his most popular image was that of his recently deceased daughter. He discusses this, and the difficulty of the problem:

New post: “Inadvertent Algorithmic Cruelty”; or, when good code yields bad results, and thoughtlessly hurts people. http://wp.me/p2jgYa-Ox

@meyerweb (Eric A. Meyer) on . Visit on Twitter.

The internet decided this was a Very Big Deal™, and quickly got out of control (and covered by mainstream media). Eric decided to set the record straight, and get behind the developers who created it:

New post: “Well, That Escalated Quickly”, an initial followup to my last post: http://wp.me/p2jgYa-OG

@meyerweb (Eric A. Meyer) on . Visit on Twitter.

Posted . Categories: .

@mikeboers on . Visit on Twitter.

I'm slowly clueing into the terror of how the various #Minecraft server mod frameworks work...

@mikeboers on . Visit on Twitter.

Arguing for over-estimates being the best target for software development -> http://netinstructions.com/a-developers-guide-to-estimating-software/

@mikeboers on . Visit on Twitter.

my favorite commits, by far, are the ones where I did nothing but delete code.

@codinghorror (Jeff Atwood) on . Visit on Twitter.

I miss AIR's "Instancer" shaders in @pixarsrenderman. #vfx #cg

@mikeboers on . Visit on Twitter.

# Repairing Python Virtual Environments

## When upgrading Python breaks our environment, we can rebuild.

Python virtual environments are a fantastic method of insulating your projects from each other, allowing each project to have different versions of their requirements.

They work (at a very high level) by making a lightweight copy of the system Python, which symlinks back to the real thing whenever necessary. You can then install whatever you want in lib/pythonX.Y/site-packages (e.g. via pip), and you are good to go.

Depending on what provides your source Python, however, upgrading it can break things. For example, I use Homebrew, which (under the hood) stores everything it builds in versioned directories:

$readlink$(which python)
../Cellar/python/2.7.8_2/bin/python

Whenever there even a minor change to this Python, symlinks back to that versioned directory may not work anymore, which breaks my virtual environments:

\$ python
dyld: Library not loaded: @executable_path/../.Python
Trace/BPT trap: 5

There is an easy fix: manually remove the links back to the old Python, and rebuild the virtual environment.

Read more... (1 minute remaining to read.)

Posted . Categories: .

# The Evils of Gamifying Git

## Your green squares do you little good, and encourage bad behaviour.

Nearly two years ago, GitHub introduced contribution calendars on everyone's profile, which roughly visualize how frequently one has been "contributing" for the past year. Through 2013, mine displayed some interesting patterns and features, many of which scream that they have a story:

Having used GitHub as the primary code host for multiple full-time jobs, and a few growing open-source projects, I now believe that these calendars introduce, for me, two negative effects that vastly outweigh their benefits.

Read more... (3 minutes remaining to read.)

Posted . Categories: .

Seems like LibreSSL is doing its job so far... https://www.openssl.org/news/secadv_20141015.txt #netsec

@mikeboers on . Visit on Twitter.

View posts before October 15, 2014


text:
# Definition:Preimage/Mapping/Mapping

## Definition

Let $f: S \to T$ be a mapping.

The preimage of $f$ is defined as:

$\Preimg f := \set {s \in S: \exists t \in T: f \paren s = t}$

That is:

$\Preimg f := f^{-1} \sqbrk T$

where $f^{-1} \sqbrk T$ is the image of $T$ under $f^{-1}$.

In this context, $f^{-1} \subseteq T \times S$ is the the inverse of $f$.

It is a relation but not necessarily itself a mapping.

## Also known as

Consistently with the definition as the image of $T$ under $f$, $f^{-1} \sqbrk T$ can also be used instead of $\Preimg f$.

## Technical Note

The $\LaTeX$ code for $\Preimg {f}$ is \Preimg {f} .

When the argument is a single character, it is usual to omit the braces:

\Preimg f


text:
# Quantum capacity

In the theory of quantum communication, the quantum capacity is the highest rate at which quantum information can be communicated over many independent uses of a noisy quantum channel from a sender to a receiver. It is also equal to the highest rate at which entanglement can be generated over the channel, and forward classical communication cannot improve it. The quantum capacity theorem is important for the theory of quantum error correction, and more broadly for the theory of quantum computation. The theorem giving a lower bound on the quantum capacity of any channel is colloquially known as the LSD theorem, after the authors Lloyd,[1] Shor,[2] and Devetak[3] who proved it with increasing standards of rigor.

## Hashing Bound for Pauli Channels

The LSD theorem states that the coherent information of a quantum channel is an achievable rate for reliable quantum communication. For a Pauli channel, the coherent information has a simple form[citation needed] and the proof that it is achievable is particularly simple as well. We prove the theorem for this special case by exploiting random stabilizer codes and correcting only the likely errors that the channel produces.

Theorem (Hashing Bound). There exists a stabilizer quantum error-correcting code that achieves the hashing limit $R=1-H\left(\mathbf{p}\right)$ for a Pauli channel of the following form:

$\rho \mapsto p_{I}\rho+p_{X}X\rho X+p_{Y}Y\rho Y+p_{Z}Z\rho Z,$

where $\mathbf{p}=\left(p_{I},p_{X},p_{Y},p_{Z}\right)$ and $H\left(\mathbf{p}\right)$ is the entropy of this probability vector.

Proof. We consider correcting only the typical errors. That is, consider defining the typical set of errors as follows:

$T_{\delta}^{\mathbf{p}^{n}}\equiv\left\{ a^{n}:\left\vert -\frac{1}{n} \log_{2}\left( \Pr\left\{ E_{a^{n}}\right\} \right) -H\left( \mathbf{p}\right) \right\vert \leq\delta\right\} ,$

where $a^{n}$ is some sequence consisting of the letters $\left\{I,X,Y,Z\right\}$ and $\Pr\left\{E_{a^{n}}\right\}$ is the probability that an IID Pauli channel issues some tensor-product error $E_{a^{n}}\equiv E_{a_{1}}\otimes\cdots\otimes E_{a_{n}}$. This typical set consists of the likely errors in the sense that

$\sum_{a^{n}\in T_{\delta}^{\mathbf{p}^{n}}}\Pr\left\{E_{a^{n}}\right\} \geq 1-\epsilon,$

for all $\epsilon>0$ and sufficiently large $n$. The error-correcting conditions[4] for a stabilizer code $\mathcal{S}$ in this case are that $\{E_{a^{n}}:a^{n}\in T_{\delta}^{\mathbf{p}^{n}}\}$ is a correctable set of errors if

$E_{a^{n}}^{\dagger}E_{b^{n}}\notin N\left(\mathcal{S}\right) \backslash \mathcal{S},$

for all error pairs $E_{a^{n}}$ and $E_{b^{n}}$ such that $a^{n},b^{n}\in T_{\delta}^{\mathbf{p}^{n}}$ where $N(\mathcal{S})$ is the normalizer of $\mathcal{S}$. Also, we consider the expectation of the error probability under a random choice of a stabilizer code.

We proceed as follows:

\begin{align} \mathbb{E}_{\mathcal{S}}\left\{p_{e}\right\} &= \mathbb{E}_{\mathcal{S}} \left\{ \sum_{a^{n}} \Pr \left\{ E_{a^{n}}\right\} \mathcal{I}\left(E_{a^{n}}\text{ is uncorrectable under }\mathcal{S}\right) \right\} \\ &\leq \mathbb{E}_{\mathcal{S}} \left\{ \sum_{a^{n} \in T_{\delta}^{\mathbf{p}^{n}}} \Pr\left\{E_{a^{n}}\right\} \mathcal{I}\left(E_{a^{n}}\text{ is uncorrectable under }\mathcal{S}\right) \right\} + \epsilon \\ &= \sum_{a^{n} \in T_{\delta}^{\mathbf{p}^{n}}} \Pr\left\{E_{a^{n}}\right\} \mathbb{E}_{\mathcal{S}} \left\{ \mathcal{I}\left(E_{a^{n}}\text{ is uncorrectable under }\mathcal{S}\right) \right\} + \epsilon \\ &= \sum_{a^{n} \in T_{\delta}^{\mathbf{p}^{n}}} \Pr\left\{E_{a^{n}}\right\} \Pr_{\mathcal{S}} \left\{E_{a^{n}}\text{ is uncorrectable under }\mathcal{S}\right\} + \epsilon. \end{align}

The first equality follows by definition—$\mathcal{I}$ is an indicator function equal to one if $E_{a^{n}}$ is uncorrectable under $\mathcal{S}$ and equal to zero otherwise. The first inequality follows, since we correct only the typical errors because the atypical error set has negligible probability mass. The second equality follows by exchanging the expectation and the sum. The third equality follows because the expectation of an indicator function is the probability that the event it selects occurs. Continuing, we have

$=\sum_{a^{n}\in T_{\delta}^{\mathbf{p}^{n}}}\Pr\left\{ E_{a^{n}}\right\} \Pr_{\mathcal{S}}\left\{ \exists E_{b^{n}}:b^{n}\in T_{\delta}^{\mathbf{p} ^{n}},\ b^{n}\neq a^{n},\ E_{a^{n}}^{\dagger}E_{b^{n}}\in N\left( \mathcal{S} \right) \backslash\mathcal{S}\right\}$
$\leq\sum_{a^{n}\in T_{\delta}^{A^{n}}}\Pr\left\{ E_{a^{n}}\right\} \Pr_{\mathcal{S}}\left\{ \exists E_{b^{n}}:b^{n}\in T_{\delta}^{\mathbf{p} ^{n}},\ b^{n}\neq a^{n},\ E_{a^{n}}^{\dagger}E_{b^{n}}\in N\left( \mathcal{S} \right) \right\}$
$=\sum_{a^{n}\in T_{\delta}^{\mathbf{p}^{n}}}\Pr\left\{ E_{a^{n}}\right\} \Pr_{\mathcal{S}}\left\{ \bigcup\limits_{b^{n}\in T_{\delta}^{\mathbf{p}^{n} },\ b^{n}\neq a^{n}}E_{a^{n}}^{\dagger}E_{b^{n}}\in N\left( \mathcal{S}\right) \right\}$
$\leq\sum_{a^{n},b^{n}\in T_{\delta}^{\mathbf{p}^{n}},\ b^{n}\neq a^{n}} \Pr\left\{ E_{a^{n}}\right\} \Pr_{\mathcal{S}}\left\{ E_{a^{n}}^{\dagger }E_{b^{n}}\in N\left( \mathcal{S}\right) \right\}$
$\leq\sum_{a^{n},b^{n}\in T_{\delta}^{\mathbf{p}^{n}},\ b^{n}\neq a^{n}} \Pr\left\{ E_{a^{n}}\right\} 2^{-\left( n-k\right) }$
$\leq2^{2n\left[ H\left( \mathbf{p}\right) +\delta\right] }2^{-n\left[ H\left( \mathbf{p}\right) +\delta\right] }2^{-\left( n-k\right) }$
$=2^{-n\left[ 1-H\left( \mathbf{p}\right) -k/n-3\delta\right] }.$

The first equality follows from the error-correcting conditions for a quantum stabilizer code, where $N\left( \mathcal{S}\right)$ is the normalizer of $\mathcal{S}$. The first inequality follows by ignoring any potential degeneracy in the code—we consider an error uncorrectable if it lies in the normalizer $N\left( \mathcal{S}\right)$ and the probability can only be larger because $N\left( \mathcal{S}\right) \backslash\mathcal{S}\in N\left( \mathcal{S}\right)$. The second equality follows by realizing that the probabilities for the existence criterion and the union of events are equivalent. The second inequality follows by applying the union bound. The third inequality follows from the fact that the probability for a fixed operator $E_{a^{n}}^{\dagger}E_{b^{n}}$ not equal to the identity commuting with the stabilizer operators of a random stabilizer can be upper bounded as follows:

$\Pr_{\mathcal{S}}\left\{ E_{a^{n}}^{\dagger}E_{b^{n}}\in N\left( \mathcal{S} \right) \right\} =\frac{2^{n+k}-1}{2^{2n}-1}\leq2^{-\left( n-k\right) }.$

The reasoning here is that the random choice of a stabilizer code is equivalent to fixing operators $Z_{1}$, ..., $Z_{n-k}$ and performing a uniformly random Clifford unitary. The probability that a fixed operator commutes with $\overline{Z}_{1}$, ..., $\overline{Z}_{n-k}$ is then just the number of non-identity operators in the normalizer ($2^{n+k}-1$) divided by the total number of non-identity operators ($2^{2n}-1$). After applying the above bound, we then exploit the following typicality bounds:

$\forall a^{n} \in T_{\delta}^{\mathbf{p}^{n}}:\Pr\left\{ E_{a^{n} }\right\} \leq2^{-n\left[ H\left( \mathbf{p}\right) +\delta\right] },$
$\left\vert T_{\delta}^{\mathbf{p}^{n}}\right\vert \leq2^{n\left[ H\left( \mathbf{p}\right) +\delta\right] }.$

We conclude that as long as the rate $k/n=1-H\left( \mathbf{p}\right) -4\delta$, the expectation of the error probability becomes arbitrarily small, so that there exists at least one choice of a stabilizer code with the same bound on the error probability.

## References

1. ^ Seth Lloyd (1997). "Capacity of the noisy quantum channel". Physical Review A 55 (3): 1613–1622. arXiv:quant-ph/9604015. Bibcode:1997PhRvA..55.1613L. doi:10.1103/PhysRevA.55.1613.
2. ^ Peter Shor (2002). "The quantum channel capacity and coherent information" (pdf). Lecture Notes, MSRI Workshop on Quantum Computation.
3. ^ Igor Devetak (2005). "The private classical capacity and quantum capacity of a quantum channel". IEEE Transactions on Information Theory 51: 44–55. arXiv:quant-ph/0304127. doi:10.1109/TIT.2004.839515.
4. ^ Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge University Press, ISBN 9780521635035.