Buffini's Blog

Bit Shifting – Chunk 77

Last modified on 2009-06-22 20:41:19 GMT. 0 comments. Top.

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 << | 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 withonly 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 << 24) | (greenValue << | blueValue;

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 << 24) – 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 iven 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 << | blueValue;

}

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 demonstraated 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 << 24) | (redValue << 16) | (greenValue << | blueValue;
}

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 << 24) | (greenValue << | blueValue;
}

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 << 24) | (redValue << 16) | blueValue;
}

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 << 24) | (redValue << 16) | (greenValue << 8);
}

// 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 your’re feeling particularly adventurous, apply a similar concept to a rotating sphere, or just go with whatever your imagination comes up with.

Bit Masking – Chunk 78

Last modified on 2009-06-22 20:37:55 GMT. 1 comment. Top.

Following on from our discussion of bit shifting, we come now to the topic of bit masking. This is an area that has enjoyed many uses over the years, not the least of them to do with cryptography, communications, and graphics. In fact some of the more common uses may be known to you from everyday applications such as Photoshop, used to mask out a particular colour, etc.. In this section we will cover the theory behind a mask, the power inherent in it, plus processing speed implications and other items. Firstly, the name is a bit of a giveaway. A bit mask does exactly that – it masks. Masks are generally used in conjunction with bitwise operations, the set of operations containing AND, OR and NOT, as well as XOR and others… These are a distinct class of operations from bit-shifting, and it is important to remember this. So, a bit mask ‘masks’ the original value of a bit.. How? Take this for a sample: You have the 8 bit integer (or 1 byte) 00101110. You want to alter, say, every 2nd bit to be on, regardless of its current value. You need to perform some operation on the integer such that the outcome is 01111111. To do this you will need a suitable operation, OR in this case, as well as the correct mask value:

Input: 00101110

Mask: 01010101

Output: 01111111

As you can see, performing an OR operation using these bits resulted in any bits already at 0 being set to 1, if they were masked by a 1. Simplicity itself, yes? What if you were to use an AND? This operation comes in handy if you are looking to switch bits off rather than on. Lets take the same input and mask values, change the operation and observe our output…

Input: 00101110

Mask: 01010101

Output: 00000100

So as we can see, a wildly different output. Whereas an OR gave us 01111111 (127), AND gives us 00000100 (4). There are a whole host of other applications available to us for use with these versatile little masks, such as…

Masking to 0/1

Switching them all on or off is fairly simple using masks. Similar to what we saw, preforming an OR with a 1 will give us an output of 1, regardless of the state of the original bit. Extending this idea then means that if our entire mask is comprised of 1’s, and we perform an OR operation with this on  our input number, what we get out the far side is a stream of 1’s.

Input:   00101110

OR:         11111111

Output: 11111111

If instead we want all of the bits off (0), we perform an AND with our old buddy 0 – note that in this case the size of your actual mask number itself doesn’t matter – whether it has 8 bits or 8000, they will all be 0, so the value of your massive stream of 0’s will always be 0. Makes it a little easier than working with similar fluctuations in size that you might have with an all 1 mask. In that instance you could potentially have 8 1’s (255), or 32 (16,777,215).

Input:   00101110

AND:     00000000

Output: 11111111

Bit querying

What if you need to know what state your component bits are currently in? You could dream up various ways of accomplishing this, all of which would probably make your head hurt. Using a mask makes it much easier – This is a two step process. First we decide which bit it is that we are actually looking to query, lets say 8 of 15. We construct a mask where all bits are 0 except the one we wish to examine, giving us 000000010000000.  The second step then is to perform an AND with the input and the mask.The ANDing of all the other bits to 0 effectively shifts all of those bits to 0 also, leaving only the 8th bit with a possibly different value.

The result will be a bit stream containing an 8th bit set to 1 if the original bit was 1, and 0 if it was 0. We then evaluate this result to see if the integer evaluates to 0 – if it does then our query bit was off. It the output does not evaluate to 0 (remember, we do not care what the actual value is, just that it’s not 0.. this alone tells us the pertinent information), then this tells us that the input bit was on. See example for details:

Input:   0010111011111101

AND:     000000010000000

Output: 000000000000000

Bit toggling

Say you don’t care what the contents of that bit were, you just want it inverted. Inverting the complete bits of an image will allow you to do funky things like generate image negatives and so on, for relatively little effort. How would you go about this? Actually it’s quite simple. Using an XOR operation, you can alter the bit you are interested in, say the MSB in this case, so if your mask bit is 1, your output will always be the inverse of the original input. Simple, and extremely powerful and useful. So if you’re input is 0, and you XOR this with 1, you get an output of 1 – only one bit had to be set to give the desired output. On the other hand, performing an XOR using two 1’s gives a 0 – the reason is that an XOR will perform just like a normal OR operation, if, and only if, only bit is set to 1. If both are set to 1 then the operation fails, returning a 0. See the example for details:

Input:   00101110

XOR:     10000000

Output: 10000000

So, our basic operations are looking good… Now for some real world applications. One of the simplest ways to actually use a mask is a set of boolean flags. Think of it like this: Your binary integer is made up of an arbitrary number of 1s and os, lets say 8 in this case. To a computer, these are synonymous with TRUE and FALSE. So, conceptually, we now have one input object filled 8 boolean flags, each of which we can set on or off to our hearts content. This gives us the massive advantage of only needing to incur the expense of passing one parameter around, and only having to perform one operation/comparison to actually use it. Example time… you have an 8-bit integer. You fill it with 10010110. You pass this to your method and perform an operation on it to determine an output colour, lets say the overall level of green in a photo.. In pseudo code this looks something like..

unsigned int processUsingMask(unsigned int myMask)

{

  unsigned int currentValue = 00101101;

  unsigned int outputValue = currentValue & myMask;

  return outputValue;

}

Hey presto, your very own bit masker. Now obviously this is horribly oversimplified, but its just intended to give you an induction into the possibilities that this solution presents. Another massive area where masking is commonly employed is in network addressing. Ever wondered what the subnet mask related to your IP address is? Well go and find out, because it’s not currently the area we’re interested in, but there is a wealth of information available out there on it.

Several large and well known image editing packages will give you an implementation of a mask for image manipulation,  such as Photoshop. Anyone who is familiar with such packages will already know quite about this useful little tool and what you can accomplish with them. These masks can be tricky to use and can cause more than a few headaches. This is one particular area where Processing wins out.

The mask functionality implemented in Processing allows you to very simply load two images into memory and mask one with the other to alter the displayed output.  Say you have an image of a family photo, a favourite old snapshot from years before. You want to take this image and touch it up a little, because the sky is very bright and drowns out the rest of the image a little. How would you do this?

One of the simpler ways would be to import your original photo to Processing, and have created a gradient grayscale image (Processing seems to work best with grayscale for this type of application) that has the bits at the top of the image set to a low value (the darker the mask colour, the more it will cover up the original input pixel), and higher values up to 255 towards the bottom. In effect, what you will get out of this operation is your original image with the sky brightness toned down.

To accomplish something like this, we could use something similar to the following code snippet..

size(200, 200);

PImage inputImage = loadImage("Sample.jpg");

PImage maskImage = loadImage("MaskOfSample.jpg");

inputImage.mask(maskImage);

image(inputImage);

And thats it… in just 5 lines of code we have achieved the ability to imitate sophisticated image manipulation technology. One thing to bear in mind here is that both the input and mask images need to be of the same size in order for Processing to be able to mask them. You should also be aware of the fact that if you are using a mask image Processing will only make use of the blue channel while applying the mask, so a grayscale image is probably best for use as a mask.

However, what we are going to focus on here is the ability of Processing to create a pixel mask. What a pixel mask does is essentially create an image out of pixels (specified by the program to be anything at all, from something as simple as a plain black image, or something like a  shaded gradient ) and then apply this collection of pixels as a mask to the original input image.

Take a look at this sample code and see what it does..

PImage inputImage = loadImage("Sample.jpg");

background (100, 50, 50);

fill(255);

rect(random(width), random(height), 20, 20);

loadPixels();

inputImage.mask(pixels);

image(inputImage, 0, 0);

Lets break it down – the first line is simple enough, we load an image, nothing special there. Line 2 gives us something slightly new: background(100, 50, 50); What this does is dim the levels of the colours in our image. Line 4 then tells us that we are about to fill our object with 255, to make it completely opaque in other words. We then create a rectangle to which this applies, and spawn it somewhere randomly on the image. Then we build a pixel array of the screen, and call the mask method using our inputImage, and the newly created pixel array. The last step is to output this image to screen.

What would we expect from this code? Basically, a greyed out input image with one little rectangular window cut through it somewhere that fully displayed the image underneath. The reason for this is that, by creating our rectangle with a fill of 255, making it opaque, we have created a mask window through the background colours, or fog if you will, that displays your original image in all its glory. If you set the size of your rectangle to be the same as that of the image the you would see the entire image clearly, but there’s not a hell of a lot of point in doing that… for the extra processing effort all you really achieve is to get the same image back out. If however you were to spawn a few shapes off, on an otherwise dark background, it would appear as if just small segments of the image were showing through. Have a look at the following program and try to work out what it does before running it..

PImage inputImage;

void setup()

{

  size(200, 200);

  inputImage = loadImage("Sample.jpg");

  noStroke();

}

void draw()

{

  fill(255);

  ellipse(mouseX, mouseY, 45, 45);

  loadPixels();

  inputImage.mask(pixels);

  background(0);

  image(inputImage, 0, 0);

}

Got it yet? What we’ve got here is an input image that is completely blacked out by constantly redrawing the background to 0, and a circle that we create in the pixel array that is completely opaque, which we then mask over the original image. The position of this circle is then free floating, as determined by the mouseX and mouseY parameters for position. The effect is that of shining a torch on a  dark scene and only being able to see what is currently displayed by the narrow torch beam.

Using this code it is very easy to come up with variants on the end effect. For example, to create a “scratchcard” type effect, whereby the entire image is slowly revealed by moving your circle over all areas of the picture till it is clear, requires only one very small change – move the background(0); call from the draw method (where it is called continually) up to the setup  method where it is only called once: if the background is only set once, then the opaque circles will eventually override the darkness we have imposed. Blindingly simple, and creates a function much like old-style dungeon master games where the map had to be gradually exposed overtime by the players movements. Consider how you would go about altering the program to display an image, and use your circle to black it out?

As an exercise in understanding of the topic we have just discussed, try your hand at these three examples:

1. Implement a “Catchphrase” style image revealer game based on random images – you might have a checkbox for multiple selection answers on one side, with the program revealing one new grid square every 5 seconds – the less squares uncovered the higher your points!!
2. Create a James Bond style image mask – Have a circle track across the screen until it hits a certain point and gradually fills with red, or possibly explodes
3. Create a game whereby the image mask functions similar to the program described here, but the underlying image is a maze. The player gets to uncover the maze bit by bit as they move the mouse over the screen, but if they go over the maze lines/boundaries, they lose, quite like one of those electric buzzer games, except in the dark….

As you can see, the possibilities for this small application are almost endless. You can accomplish a mountain of functionality with very little effort, so test it and see what you can do.

PImage inputImage;

void setup()
{
// Load image and correctly set the size of the display
size(340, 363);
inputImage = loadImage(“Beermotions.jpg”);
// Remove the borders from the images and shapes we will create
noStroke();
// Set the background opcaity to 0 – completely black
background(255);
}

void draw()
{
// Create an ellipse (a circle in this case)
// make the circle completely opaque using the fill command
fill(0);
ellipse(mouseX, mouseY, 45, 45);

// Build and load the pixel array with the circle we have created
loadPixels();
// Mask the input image with our pixel mask
inputImage.mask(pixels);

// Draw the entire image
image(inputImage, 0, 0);
}