Mapping (x,y) co-ordinates to bits in a byte array - as quickly and efficiently as possible

Question

I'm using C# (.NET Micro Framework running on the Netduino Plus) to control an LCD screen of 84 x 48 pixels.

Each pixel in the LCD screen has two states: 1 (ON) or 0 (OFF). To control the pixels in the screen, I need to send an array of 504 bytes, where each byte represents one column of 8 pixels (ie, the screen is 'split' into 6 rows of 84 x 8 pixels).

This is best demonstrated with an example:

• The byte 00000001 (2^0) represents one column of eight pixels, where the first pixel at the top of the column is ON (1).

• The byte 00001001 (2^0 + 2^3) represents another column of eight pixels, where the first and 4th pixels from the top of the column are ON.

From this you can see that a bitwise AND operation will show which pixels in a given column are ON or OFF. For example, to see if the 4th pixel in a given column of 8 pixels is ON:

00001001    AND
00001000
-----------------
00001000 > 0
∴ The 4th pixel is ON

The problem is that I need to be able to use (x,y) co-ordinates to access each pixel in the screen. For example, the point (3,10) would represent the pixel 4 to the right of and 11 below the pixel in the top left corner of the screen. Similarly, the point (83,47) would represent the bottom right pixel of the screen.

I have written the following C# code to achieve this:

byte[] display = new byte[504];

// storing these means they don't need to be calculated every time:
byte[] base2 = { 1, 2, 4, 8, 16, 32, 64, 128 };

// Determine if the pixel is ON (true) or OFF (false)
public bool PixelState(Pixel px)
{
    return (display[GetColumn(px)] & base2[GetPxNum(px)]) > 0;
}

// Find the number of the pixel in its column of 8
private int GetPxNum(Pixel px)
{
    return px.y % 8;
}

// Find the index of the byte containing the bit representing the state of a pixel
private int GetColumn(Pixel px)
{
    return (px.y / 8 * 84) + px.x;
}

// Set a pixel's state
public void SetPixel(Pixel px, bool state)
{
    int col = GetColumn(px);
    int num = GetPxNum(px);

    if (state && !PixelState(px))
        display[col] += base2[num];
    else if (!state && PixelState(px))
        display[col] -= base2[num];
}

// Represents one (x,y) point
public struct Pixel
{
    public int x, y;

    public Pixel(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}

Since this is running on a microcontroller, I need the code to be as quick and efficient as possible. This is also necessary because these methods may be called many times in quick succession to update pixels in the LCD screen.

Therefore my question is how can I make this code faster and more efficient? Is there any better way of going about this?

EDIT: After some extensive testing I've realised that I should be using Math.Floor (or just an integer operation) in GetColumn. I've updated my code.

Answer 1

This little snippet in SetPixel:

if (state && !PixelState(px))
    display[col] += base2[num];
else if (!state && PixelState(px))
    display[col] -= base2[num];

Could be replaced by:

if (state)
    display[col] |= base2[num];
else
    display[col] &= (byte)~base2[num]; // You could precompute this inverse array too

If you've got plenty of memory available precomputing might be okay but, seriously, uCs have SO MUCH processing power these days. Are you really going to notice a little bit-shift or negation?

---

Also, you might be interested in not using (double) and Math.ceiling() since your microcontroller probably has no floating point support, so it must be emulated (with a consequent drop of performance. Using (float) would make it better (single precision emulation is faster) but even better would be this:

return ( (px.y/8 + ((px.y%8)?1:0)) * 84 ) + px.x;

EDIT: taking a closer look at netduino it might have a FPU (although I can't see it in the datasheet, so it probably doesn't...) The integer math alternative is probably still faster :)

---

Wether it's faster can only be assured by testing but, like I said in the comments, this is arguably going to be a bottleneck and you look just like another victim of premature optimization.

The biggest bottleneck here is your framework.