LED Matrix – Row, Column addressing question, C programming

[Mr.B]

I have designed and built a PCB containing 74HCT595 shift registers, FETs and a 16x16 matrix of LEDs.
To make life easy with the board layout the Rows and Columns are interleaved to the shift registers.
See picture 1 below.

The output stream to the shift registers consists of 4 bytes.
Picture 2 below shows the relationship between the bytes, bits, rows and columns.

Picture 3 below shows a (sort of) frame buffer using the relationship between the bytes, bits, rows and columns.

Now, to convert the ‘frame buffer’ to a 4 byte stream to send out to the shift registers I can create an intermediate lookup table:
Example: If the bit top left of the frame buffer is set, then set bit 0 of byte 0 and bit 7 of byte 3.
This is manageable although likely not very elegant or efficient.

Now my question:
Is there a clever C bit manipulation method that will interleave the bits from the 2 byte Row stream with the bits from the 2 byte Column stream?

Question backup information:
The MCU is a MK20DX256 32 bit ARM Cortex-M4 @ 72 MHz (Teensy 3.2)
Reversing all bits in the 2 byte Row word is not a difficult task in order to interleave the two streams sequentially if necessary.

Many thanks in advance.

[Ian.M]

https://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious
There are a couple of options.  Brute-forcing it with a Morton table will probably be the fastest, but as the M4 has a barrel shifter, the 'Binary Magic Numbers' method should be fairly efficient.   

[Mr.B]

Wow!
Many thanks Ian.M
That is the second time in the last month you have preserved my sanity.

[helius]

https://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious

The first interleave example contains a bug: it should read

Code: [Select]

for (int i = 0; i < sizeof(x) * CHAR_BIT; i++)
{
  z |= (x & 1U << i) << 2*i | (y & 1U << i) << 2*i + 1;
}

[Ian.M]

I don't think so.
Consider two bytes x,y containing bits x=(h g f e d c b a) and y=(H G F E D C B A)

when i=0, your version  will OR z with the bits ( 0 .... 0 A a) as it should.
when i=1 it will OR z with the bits ( 0 .... 0 B b 0 0 0 0).
when i=2 it will OR z with the bits ( 0 .... 0 C c 0 0 0 0 0 0 0 0).
& etc.

resulting in z=(H h 0 0 G g 0 0 F f 0 0 E e 0 0 D d 0 0 C c 0 0 B b 0 0 A a) which is obviously FUBARed.

Remember, the bit position is retained from picking it out with (x & 1U << i) or (y & 1U << i), so it only needs shifting by i to double that bit position.
If in doubt take a pencil, a sheet of squared paper and your copy of K&R and dry-run it!

[helius]

So it does!

[Ian.M]

I should also note that the maintainer has historically offered a reward for bugs in the bit twiddling hacks page code snippets:

As of May 5, 2005, all the code has been tested thoroughly. Thousands of people have read it. Moreover, Professor Randal Bryant, the Dean of Computer Science at Carnegie Mellon University, has personally tested almost everything with his Uclid code verification system. What he hasn't tested, I have checked against all possible inputs on a 32-bit machine. To the first person to inform me of a legitimate bug in the code, I'll pay a bounty of US$10 (by check or Paypal). If directed to a charity, I'll pay US$20.

so the odds of you finding a bug in the simple algorithms for any of the tasks are very low indeed.

Also, the first presented naive algorithm is almost always what one already has, that one is trying to replace with something better.

[westfw]

You could waste half the space in your "frame buffer", so the "row" bits were already interleaved.  It'd be comparatively easy to spread the bits when drawing (just shift by 2 instead of 1...)
Of your 4 bytes, all 16 row bits are going to be set, but only one column bit, right?
So if you framebuffer has 16 words indexed by column

Code: [Select]

uint32_t fb[16] = { 0x1x2x3x4x...ExFx,  /* the hex digits are the row bits and the x's are empty, then */
 :
}then the refresh code would be a zippy:

Code: [Select]

shiftword = fb[column] /* (spread bits) */ | (1<<(2*column)); /* column bit */
/* shift it out */Classic "trade space for speed" and "make the thing you do a lot (refresh), quicker, while letting the less common thing (drawing) be a bit slower.)
(I may have confused row/column in that description...)