15-122 Principles of Imperative Computation
Recitation 3 - Wed Jan 19

Conceptually, an image is a 2 dimensional array of pixels, where each pixel is a 32 bit integer made up of the following 4 8-bit channels or components:

alpha - leftmost eight bits (opaqueness between 0-255 inclusive)
red - next eight bits (intensity of red component between 0-255 inclusive)
green - next eight bits (intensity of green component between 0-255 inclusive)
blue - rightmost eight bits (intensity of blue component between 0-255 inclusive)

In memory, the image is stored as a one-dimensional array, row by row. If the image is of size height (the number of rows) times width (the number of columns), then a pixel in the 2D conceptual image at row j, column i is stored in the one-dimensional array at index j*width+i. To understand this, remember that rows and columns are indexed starting at 0, so the formula basically says to skip the first j rows (first j "widths") and then skip the first i cells in the next row to get to the desired pixel in the array.

To remove the red of an image, we can write a function that takes as its arguments an array of pixels, and the width and height of the image represented in the array. It will return a new array representing a modified image with the red component removed. See the code below.

/* make pixel a type alias for int */
typedef int pixel;

pixel[] remove_red (pixel[] A, int width, int height)
//@requires \length(A) >= width*height;
//@ensures \length(\result) == width*height;
{
  int i;
  int j;
  pixel[] B = alloc_array(pixel, width*height);

  for (j = 0; j < height; j++)
    //@loop_invariant 0 <= j && j <= height;
    {
      for (i = 0; i < width; i++)
      //@loop_invariant 0 <= i && i <= width;
       {
         // Clear the bits corresponding to the red component
         B[j*width+i] = A[j*width+i] & 0xFF00FFFF;
       }
    }

  return B;
}

Note the use of the command typedef which allows us to define a new identifier called pixel that is logically equivalent to int. Although we didn't really need to do this, it makes the code easier to read when we see that the array of integers A should be treated as pixels. Additionally, it conveys the intent that these ints are being used for their bits and not for their interpretations as numbers.

In order to create a new array for the modified image, we need to use the alloc_array function which requires two arguments: the type of each element and the number of elements desired. The function gets a block of memory large enough to hold the desired amount of information and returns back a reference to it, which we store in variable B:

pixel[] B = alloc_array(pixel, width*height);

Now let's see how the red is removed. We have two loops: the j loop picks a particular row and the i loop picks a column in that row, and we then take the pixel value in A and convert it to a new pixel value for B. Recall that the red component is the 8 bits immediately after the alpha component. To clear these bits, we simply have to use bitwise-and (&), remembering that when you "and" a bit with 1, the bit doesn't change and when you "and" a bit with 0, the result is always 0.

B[j*width+i] = A[j*width+i] & 0xFF00FFFF;

Remember that the value 0xFF00FFFF is a 32-bit integer in hexadecimal notation and hex 00 represents the 8 bits 00000000 and hex FF represents the 8 bits 11111111. So 0xFF00FFFF lets the alpha, green and blue components through to B unchanged, while the red component is cleared.

Consider the decimal integer 15122. What is its value in binary?

Using our algorithm from class, divide by 2 repeatedly, and record the remainders:

15122 / 2 = 7561 R 0
 7561 / 2 = 3780 R 1
 3780 / 2 = 1890 R 0
 1890 / 2 =  945 R 0
  945 / 2 =  472 R 1
  472 / 2 =  236 R 0
  236 / 2 =  118 R 0
  118 / 2 =   59 R 0
   59 / 2 =   29 R 1
   29 / 2 =   14 R 1
   14 / 2 =    7 R 0
    7 / 2 =    3 R 1
    3 / 2 =    1 R 1
    1 / 2 =    0 R 1

Reading up from the bottom, 15122 in decimal is 11101100010010 in binary.

If we stored this as a 32-bit siged integer, then it would be stored as:

00000000000000000011101100010010

(Note how the leftmost bit is 0, indicating a postive integer.)

What is this value expressed in hexadecimal? Break up the binary number into groups of 4 bits and translate each to its equivalent hex digit:

0000 0000 0000 0000 0011 1011 0001 0010
   0    0    0    0    3    B    1    2

Check this in coin by entering 0x00003B12; and you should see 15122 (int) printed out.

What is the negation of 0x00003B12 (using 2's complement notation)? To find this, flip all the bits and then add 1:

0000 0000 0000 0000 0011 1011 0001 0010  (15122 in binary)
1111 1111 1111 1111 1100 0100 1110 1101  (flip all the bits)
1111 1111 1111 1111 1100 0100 1110 1110  (add 1)
   F    F    F    F    C    4    E    E  (-15122 in hex)

Again, use coin to check this value. If you add 0x00003B12 and 0xFFFFC4EE in coin you should get 0. (Why?)

How do you compute the negation of integer i using C0 operators? Obviously, you can just write -i. But using the logical and arithmetic operators, you could use bitwise-exclusive-or (bitwise-xor):

(i ^ 0xFFFFFFFF) + 1

Think: Why does this work?

Now let's look at the shift operators. If we take the value 15122 and shift right one bit in coin, we get the value 7561. It looks like a shift right of one bit divides the value by 2. If we take 15122 and shift left by one bit, we get 30244. So shifting left by 1 bit multiplies by 2.

What happens to the bit that gets shifted "off"? It is ignored. What happens to the bit position that becomes "empty"? For a left shift, the bit 0 is shifted in from the right into the rightmost bit. Note that a left shift may change the sign of the integer. (Do you see why?) For a right shift, however, the sign bit is duplicated and shifted in from the left into the leftmost bit, so the sign of the resulting value doesn't change in a right shift. This is called arithmetic right shift. (There is also the notion of a logical right shift where a 0 is always shifted in from the left into the leftmost bit, but this could change the sign of the number.)

Suppose you want the rightmost 2 bits of an integer i? One way to do this is to use the bitwise-and operator like we did with the image example above:

i & 0x00000003

Another way you might think of doing this is using the modulo operator (%). If we were to divide by 4, this is equivalent to shifting right two times. The two bits that gets lost represent the bits we want. So if we use modulo (%), this is a division operation but you get back the remainder instead of the quotient, and the remainder is these two bits that we want. So you might think about doing this:

i % 4

But this doesn't work if the integer is negative. If the integer is negative and you want the rightmost two bits, you should use the bitwise-and operator, not modulo. Experiment in coin and see why.

Exercise

Suppose you want the alpha channel of a pixel p. Two solutions come to mind:

(p & 0xFF000000) >> 24
(p >> 24) & 0xFF

The first solution is incorrect, while the second solution is correct. Why?