Bit Shifting - Chunk 77

2009-05-02T17:49:00.000-07:00

Before exploring the advantages of bit shifting to graphical processing, we should first consider this question - What is bit shifting? Basically put, it does exactly what it says on the bit... It performs a shift operation, either left or right, on a particular input, resulting in a changed output.

They are not to be confused with bit-wise operations, or standard bit operations, such as NOT, AND and OR. These are a separate class of operations which we do not intend to cover in depth in this example. Instead we will focus on the bit-shift operations, from a basic perspective all the way up to their use for graphical processing in the example that will follow.

As we know, a standard byte is made up of 8 bits. A standard integer is 4 bytes, so 32 bits. These bits are 1 or 0, and are then shunted back and forth between these states by means of the bit shift operations. There are also two main classes of bit-shifting. These are:

Arithmetic shifts
Logical shifts

Before we continue, there are three important concepts to be aware of here:

Most Significant Bit: The term most significant bit refers to the bit having the highest value in your number. Generally considered to be the left-most bit in most languages and representations. The least significant bit then is the lowest value bit, or right most bit. So in our example (chopped down for brevity's sake), we have "10 10 10", where the red 1 is the most significant/left most bit (MSB), and the blue 0 is the least significant/right most bit (LSB).
The Sign of the binary number:The MSB of a binary number is frequently taken to be the sign of the number, so for example 1 for negative, 0 for positive. If we had an 8 bit integer, 10110010, the this number would be counted as a negative because of the rightmost bit being 1. However, it is also important to note that the an integer can be declared as unsigned, meaning that the MSB is regarded as a art of the number and nothing more.
The Carry Bit: The carry bit of a binary number does what you might think the name suggests - it carries over left over bits from operations. Lets say you have added two unsigned 8 bit integers (255 + 255) and gotten 510 as your result. Normally this would be represented as 1 11 11 11 10, but remember, we are 8 bit ints here... This means that in order to perserve our 8 bit interity, we have to drop the 9th bit from our normal representation and store it instead in a special bit, the carry bit. Our corrected output then becomes11 11 11 10 (254), and carry 1.

Arithmetic Shift

Let start with Arithmetic shift operations. As mentioned previously, one int is made up of 4 bytes, 32 individual bits.

A 32-bit integer represented in binary as :

00 00 00 00 00 00 00 00 00 00 00 00 00 10 10 10

Lets say we perform a left shift operation on this number, shifting it by two bits. This now gives us:

00 00 00 00 00 00 00 00 00 00 00 00 10 10 10 00

We can visualise the preceding operation from this illustration:

Right shifting by two bits would instead have given us:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 10 10

As you can see, performing a straight forward left bit-shift operation on our 42 has changed the representation. the two left-most bits have dropped off, to be removed by the register storing the information, and two new bits, both 0, have been added to the right of the integer. Right shifting moved all of the digits to the right, dropping the trailing 10 from the right, and adding 00 (assuming the carry bit has been set to 0) to the left hand side.

It is important to remember that while right shifting a bit, the sign of the number is always preserved, i.e. if the MSB is 0 or 1, this bit is preserved through all of the right shifting operations you can throw at it. The other implication to note is that the LSB is shifted rightward, into the carry bit. Each successive right shift operation will overwrite the carry bit with the current LSB.

Logical shifting

A logical shift is essentially the same as an arithmetic shift, with one very important difference - where the arithmetic shift uses the carry bit as the value to insert in right shift operations, the logical shift uses only 0s. What this means from a practical point of view is that a logical shift is the shift of choice for an unsigned int (no carry preserved), and an arithmetic shift is the choice for signed operations. See examples below:

Logical right shift of 1 bit on 0011010101 (carry bit: 1) - 0110101010

Arithmetic right shift of 1 bit on 0011010101 (carry bit: 1) - 0110101011

Next to consider are the areas of Rotate (no carry), and Rotate (carry through). Both of these operations perform a rotation on the bits, essentially behaving as if the integer was circular and you were just spinning them around on a big wheel. However there is an important difference to note, and that difference concerns the carry bit.

Rotate (no carry):

This form of the rotation behaves exactly as you would expect, all bits are preserved as they are rotated, no information is lost at any stage. A standard application of this type of bit shift would be in cryptography. Consider the age old Caeser Cipher and you'll see what I mean.

Rotate (carry through)

This form is slightly different - Instead of preserving bit fidelity on each pass, there is a change affected. The operation behaves as if the carry bit is a separator between the two ends of the integer, so instead of shifting the MSB to the LSB, or vice versa, these values are instead shifted in and out of the carry bit. What this gives us, in effect, is a situation where you might have our old friend (42) 101010, with carry bit 1. A 1-bit left rotation will then give us 010101 with carry bit 1. See illustration below for clarification.

Bit-Shifting Applications

Finally, some real uses. There have been several major uses for bit-shifting over the years, all on semi-related themes - because bit-shifting is a very low-level operation, it became very useful for applications that needed to perform fast, and to work in close synch with the areas being acted upon, for example with device drivers, image processing, communications and so on. Think about it - instead of performing big fancy operations like multiplication and so on, which can incur an overhead (always an issue where these areas are concerned), would you prefer instead to be able to simply shift the bits right and left and come out with the same solution, just much faster?

So why does this interest us? Say you are developing a program in Processing and you have a colour in an image that you want to manipulate. You might come up with something like this..

PImage myImage = loadImage("LotsOfColours.jpg");

loadPixels();

for(int i = 0; i < (myImage.width * myImage.height); i++) { int greenValue = myImage.pixels[i] >> 8 & 0xFF;
int blueValue = myImage.pixels[i] & 0xFF;
int alphaValue = myImage.pixels[i] >> 24 & 0xFF;

// Recombine component colours
myImage.pixels[i] = (alphaValue << 24) | (greenValue << 8) | blueValue;
}

Lets examine this fragment and see what it does for us.. A we have seen previously, we can load an image into memory using the PImage and loadPixel comands. We have our array of pixels stored away. So far so good. But what if this was a particularly large image? We don't want to expend a lot of time and processor effort in just shifting a particular shade or range of colours out of our way, so we do it on the cheap using a bit shift. Take a look at the first line inside the for loop:

int greenValue = myImage.pixels[i] >> 8 & 0xFF;

What we have happening here is quite simple and beautifully powerful - We take the current pixel, which evaluates to a 32 bit integer, and decide that since we know that range the green components of a colour live in the 8 bit range, we simply shift right by 8 bits and perform a bit-wise AND with 0xFF (an int consisting of all 1's) which gives us our original pixel with only the green components present. Simple, fast and effective!! And the beauty is it can be done for any colour or shade you might want.

Obviously this is not the end of the story. We have extracted the green, blue and alpha components of our current colour into outside variables. We now need to do something with them, namely re-combine them back into our original source colour leaving out the components we did not want. To do this we use the line at the bottom of the for loop:

myImage.pixels[i] = (alphaValue <<>

This could be a little daunting for anyone not used to bit work, so lets step through it piecemeal and see what it does.

(alphaValue <<> - Take our alpha component and shift it 24 bits to the right - Give us a 32 bit int with the alpha components in the correct position: 11111111000000000000000000000000
(greenValue <<>- Take our green component and shift it 8 bits to the right - Give us a 32 bit int with the green components in the correct position: 0000000011011010000000000000000
blueValue - Take our blue component and don't shift it at all (should already be in the correct position for blue): 0000000000000000000000011110001

Next we perform a bit-wise OR on all three of these integers...

11111111000000000000000000000000
| 0000000011011010000000000000000
| 0000000000000000000000011110001
= 11111111110110100000000011110001

And last,but most definitely not least, we take our newly modified and red free colour and assign back to the current pixel in our image. Tada!! Our loop then hops on to the next pixel in line and does the same thing again. Very shortly our whole image has been processed and we have a beautifully dull and colour constrained image.

By now you should be getting a rough idea of just how powerful this small and seemingly insignificant low-level process is. With a little imagination, and a firm grasp of the fact that full manipulation of every facet of a pixel is now yours to command, you can accomplish whatever the hell you like. Take for instance the example given by Greenberg in his Processing book - that of contrast manipulation. What exactly is the contrast of our image? Basically it is the signal to noise ratio of the colour components in a given set of colour components. So if, for example, you were to take a green component that evaluated to the decimal number 120 and then applied a multiplier to it of 1.5, you would achieve a result of 180, meaning that your green is now 50% stronger in effect. So in code this would look like:

int contrastMultiplier= 1.5;

for(int i = 0; i < (myImage.width * myImage.height); i++)
{
int greenValue = myImage.pixels[i] >> 8 & 0xFF;
int blueValue = myImage.pixels[i] & 0xFF;
int alphaValue = myImage.pixels[i] >> 24 & 0xFF;

greenValue = greenValue * contrastMultiplier;

// Recombine component colours
myImage.pixels[i] = (alphaValue << 24) | (greenValue << 8) | blueValue;
}

image(myImage, 0, 0);)

So now we have an image with no red at all, and a sharpened green component. In a grand total of five lines of image manipulation code. Not a bad return on investment. The following program ties in all of the pieces we have demonstrated so far and produces a 4 image output...

float contrastMultiplier = 1.75;

void setup()
{
size (690, 726);
}

void draw()
{
PImage image1 = loadImage("Beermotions.jpg");
PImage image2 = createImage(image1.width, image1.height, RGB);
PImage image3 = createImage(image1.width, image1.height, RGB);
PImage image4 = createImage(image1.width, image1.height, RGB);

arraycopy(image1.pixels, image2.pixels);
arraycopy(image1.pixels, image3.pixels);
arraycopy(image1.pixels, image4.pixels);

loadPixels();

for (int i = 0; i < (image1.width * image1.height); i++)
{
int redValue = image1.pixels[i] >> 16 & 0xFF;
int greenValue = image1.pixels[i] >> 8 & 0xFF;
int blueValue = image1.pixels[i] & 0xFF;
int alphaValue = image1.pixels[i] >> 24 & 0xFF;

redValue = int(redValue * contrastMultiplier);
redValue = constrain(redValue, 0, 255);

greenValue = int(greenValue * contrastMultiplier);
greenValue = constrain(greenValue, 0, 255);

blueValue = int(blueValue * contrastMultiplier);
blueValue = constrain(blueValue, 0, 255);

alphaValue = int(alphaValue * contrastMultiplier);
alphaValue = constrain(alphaValue, 0, 255);

// Recombine component colours
image1.pixels[i] = (alphaValue <<>
}

for (int i = 0; i < (image1.width * image1.height); i++)
{
int greenValue = image2.pixels[i] >> 8 & 0xFF;
int blueValue = image2.pixels[i] & 0xFF;
int alphaValue = image2.pixels[i] >> 24 & 0xFF;

// Recombine component colours
image2.pixels[i] = (alphaValue <<>
}

for (int i = 0; i < (image1.width * image1.height); i++)
{
int redValue = image3.pixels[i] >> 16 & 0xFF;
int blueValue = image3.pixels[i] & 0xFF;
int alphaValue = image3.pixels[i] >> 24 & 0xFF;

// Recombine component colours
image3.pixels[i] = (alphaValue <<>
}

for (int i = 0; i < (image1.width * image1.height); i++)
{
int redValue = image4.pixels[i] >> 16 & 0xFF;
int greenValue = image4.pixels[i] >> 8 & 0xFF;
int alphaValue = image4.pixels[i] >> 24 & 0xFF;

// Recombine component colours
image4.pixels[i] = (alphaValue <<>
}

// Draw all 4 images
image(image1, 0, 0);
image(image2, width/2, 0);
image(image3, 0, height/2);
image(image4, width/2, height/2);
}

This program functions as a standalone artifact which encompasses all of the concepts we have covered in this chapter. All of the code snippets, and the program we have produced should be easily understandable by this point. What our final program does, in essence, is:

Take an input image and create three copies.
Process image 1 such that all colours are present in the final output, and have each of the colour components processed so that the contrast level of each has been magnified.
Process image 2 such that the contrast stays the same, but the red components have been completely removed.
Process image 3 such that the contrast stays the same, but the green components have been completely removed.
Process image 4 such that the contrast stays the same, but the blue components have been completely removed.
Draw all 4 images in 2*2 grid

Hopefully Andy Warhol would have been proud of us.

All simple ideas, but when combined and utilised in a creative fashion you can come up with some truly bizzare and astonishing effects. As a test of your comprehension, see if you can create a program which takes an input image and redraws several times a second with the colours shifted by some random variable. If you're feeling particularly adventurous, apply a similar concept to a rotating sphere, or just go with whatever your imagination comes up with.

Gone fishing...

2009-04-03T13:30:00.000-07:00

... Forgot I still had this thing. I've shunted all of my blog stuff over to my new site http://darraghbuffini.com, and will be working off that from now on.

Because this is the blog I originally registered for the project I'll also post my finished chunks here, but draft stuff will be over on the new one for the forseeable. Finally have some time to get properly suck into it at long last. Should be entertaining.

Waterstone's

2008-12-20T03:42:00.000-08:00

Am having sever trouble with the above. Ordered the book online from them so I could use the gift card (Waterstone's in Ireland won't take them), and have had nothing but trouble.

Firstly, the order did not process the gift card, so the full amount got charged to my credit card. Very annoying.

Secondly, I still haven't received it, and it is now headaing towards 4 weeks after my order, even though they assure me it has been posted. I have been on holiday for the last week, so it could have arrived in the meantime, but I doubt it.

Thirdly, and this is the one that really got on my nerves, their customer services are SERIOUSLY bad. Absolutely atrocious. I asked the same 2 questions (why wasn't the gift card used, and when will it be delivered) 4 mails in a row and kept getting the same crappy canned answer back. Eventually gave up and demanded a manager, who preceeded to tell me the same thing. Oh the joys.

I am currently considering options. I threatened to cancel the payment off my credit card and report them to a consumer body, so this may be the only way to go about it. Will decided if it's still not arrived when I get back.

Book Token

2008-11-15T03:47:00.000-08:00

Has been received. Haven't had time to get down to Waterstone's to pick up the book as yet, but will do either this weekend or on Monday at lunch. With the arrival of the token it gives the project a much more definite and immediate feel, makes you feel like things are getting started. Unfortunately I'm still in the middle of another project (NaNoWriMo), so have to finish that first at the end of this month before I can move in. But I have been planning...

I have a couple of ideas tossing around in the back of my mind, basically to do with what kind of images I can get it to produce. I have a friend who does a lot of mathematical work, and knows a good bit about topography, so she's hopefully going to supply some inspiration for this. It will be interesting if I can make it work, I may well end up playing with the software long after the project is finished just to see what I can make it do :)

Chunks bitten off

2008-10-28T13:24:00.000-07:00

Successfully bit off the chunks I wanted from the project - bit processing and masking (77 & 78). Wanted these for two reasons:
- First: The bit processing is more low level code than the high level code/concepts that will be documented throughout a lot of the rest of the book, and its similar to the area I have most experience in.
- Second: The mask work is something I haven't dealt with before, and as such will push me out of my comfort zone. It will deal with more sophisticated errors of image processing than I have seen to date, and will give me a good background in newer methodologies.

I'm looking forward to getting started on the project. Waiting patiently for the book token now to get a hold of the Greenberg text. I've started playing with the IDE and its pretty cool, looks like you can get a lot of advanced functionality for free, wondering now if there are similar (or the same) plugins for something for Eclipse, which would open things up even more...

Interesting....

Initial post on the OU Mass Writing Project

2008-10-22T14:21:00.000-07:00