Electronic – Reading to PIC32MX’s memory in C and XORing big sets of data

cmatrixpic

I have a project in which I have 102 8-bit PISO shift-registers in daisy chain configuration and they are outputting to a common SDI line connected to a PIC32MX controller.

There is a total of 816 bits I need to read and store in the memory so I can manipulate the data being read. Also, I'll have to read them 34 times because the application requires that I XOR those 816 bits for each of these read operations.

I have two questions:

  • How would you store the data? I'm worried because I'll have quite a bit of data to handle and I'm trying to optimize processing to the very minimum. Note that I need to be able to extract the (row, col) indexes so I can compute other values accordingly.
  • After XORing the data, I'll need to traverse the structure and find occurrences of '0's. What do you suggest in terms of search algorithm?

I was thinking of creating a matrix with [34,816] dimension and sequentially XOR the rows to a single, 816 column array and then search for '0's in the array, but I'm not sure how to do it, any thoughts?

Best Answer

To process the bits as efficiently as possible, you're going to want to keep them packed into 32-bit words whereever it makes sense. 816 bits is 25.5 words, which really isn't bad at all.

To search for ones efficiently, break the task into two steps: Check entire words for non-zero in the outer loop, then search for individual bits in the words that aren't all-zero in the inner loop.

One trick that can be used to isolate individual bits in a word that has multiple bits set is to AND the word with its negation (2's complement). The result has just a single bit set — the rightmost 'one' in the original word. You can then use this result to clear that bit and look for the next 'one'.

In C:

temp = word & -word;
word &= ~temp;

For example, suppose your 32-bit word contains 0x40010080:

01000000000000010000000010000000  original word
10111111111111101111111110000000  ... negated
00000000000000000000000010000000  ... and then ANDed together

11111111111111111111111101111111  complement of previous word
01000000000000010000000000000000  ... ANDed with original word for next iteration

EDIT:

The efficiency of this algorithm comes from the fact that you only iterate once for each 'one' (three of them in this example), rather than once for each of the 32 bits in the word. This is a huge advantage if you're doing something like simply counting the 'one's. The downside is that it doesn't give you the bit index directly, but there are ways to accelerate that as well. For example, to get the bit index of a single bit set in a word, you could use a binary encoding algorithm:

index = 0;
if (word & 0xAAAAAAAA) index += 1;
if (word & 0xCCCCCCCC) index += 2;
if (word & 0xF0F0F0F0) index += 4;
if (word & 0xFF00FF00) index += 8;
if (word & 0xFFFF0000) index += 16;

The overall advantage of the two algorithms above, as compared to a brute-force iteration through the bits, depends on how many bits you expect to find in each word. If they're rare (less than about 4 per word), then these algorithms should be faster. If they're more common than that, just go with the iterative loop:

for (index = 0, mask = 0x00000001; index < 32; ++index, mask <<= 1) {
  if (word & mask) {
    /* do your processng here */
  }
}
Related Topic