1

I'm developing a program for a uC that reads in a 40 byte bit array via SPI. This 40 byte array is a test vector that's compared against a 'known good' test vector, which is stored on an SD Card.

To find the anomalies/faults/errors, I XOR every byte of the received test vector with the stored data. This results in a bit array that has '1's where the faults lie. I can find the position of these '1's easily by using the following algorithm.

The trouble is storing the position of these '1's. Currently, I'm using Variable Length Arrays but the support for these is broken in GCC4.2 and so I'm not sure how reliable they would be in AVR-GCC.

My next thought was to use malloc, but that's usually discouraged in embedded systems. Should I just declare a unsigned char array of length 320 and store a '1' when I find a bit set? Example: I find bits 4, 8, 10, 42 and 250 set in my bit array. I then set the corresponding elements to '1' to indicate that there were '1's detected at these positions. This would take up 320 bytes of my SRAM. Alternatively, I could declare the array as an int and store the actual position starting from the top of the array.

Why I need the position of bits set? The SD Card contains another file which has information that corresponds to the position in the bit array. So, if a fault is discovered at position 24, the program can go and read the file and display information about everything it knows that's connected to position 24.

NOTE: Some may wonder whether I need to read in the entire test vector at once. That is indeed the case.

Improve this question

2 Answers 2

Reset to default
3

If you know the upper bound on your storage and it's not onerous, it's usually better to simply create a fixed size array.

As you stated, variable length array support is spotty in some implementations and totally unavailable in others. And malloc comes with added overhead, and includes the possibility that it may fail.

I'd go for the non-variable-length fixed-size (static is, I think, a misleading term to use here) array.

Now, as to whether you use a character array where each value specifies whether or not the equivalent bit is bad, or an integer array where each element is a sequential list of the bad bits is a different matter.

For a start, I'd try to minimise data in the second case use by using a 16-bit value - whether that's a short or an int in your implementation I don't know.

But, since you have 320 bits, an 8-bit char won't work for bit position, so a 16-bit value is needed.

Hence, for that second case, you'll need to use 640 bytes rather than 320, for the worst case where every bit in the sample is bad. You can get away with not needing a bad-bit count by storing -1 values in the unused slots of this array.

So the choices really are (for bad-bit positions of 42 and 314, for example):

BytePos  BadBitFlag    or:     BytePos  BadBitPosition
0..41    0                     0/1      42
42       1                     2/3      314
43..313  0                     4/5      -1
314      1                     :
315..319 0                     638/9    -1

It really depends on the limits of storage.

You have to calculate the data regardless of which method you choose, since you're opting for char-based "bits" in the first solution, meaning that the XOR result will need to be expanded from a bit array in 40 bytes to a byte array in 320 bytes.

If you're going to process the list of bad bits a lot, and you can spare the extra storage, I'd opt for the second solution.

If you're either only going to process the list a few times, or memory is really tight, go for the first solution.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Would that be the char array to store '1' where the bits were set or an int array to store the actual positions?
@saad, if you can spare the space, it'll be easier to store each "bit" in a char variable. If not, you'll have to store the bits and use masking and bit shifting to get at them.
perhaps I'm misunderstanding something - but I won't need to mask or bit shift. If I have a int array and the first '1' I encounter in my bit array is at 20, I store 20 at the 0th element in my int array. It would be array of positions of the bits set. It would take more memory overall (twice as much) but reduce the processing time because a loop would only loop for n times where n is the total number of bits that were set in the bit array. The current system has 8K SRAM of which 40% is already being consumed. We will add additional SRAM - upto 64K - on the next spin of boards.
@saad, sorry, I think I misunderstood the second part of your question. I've updated the answer to (hopefully) fix that :-)
2

If space is at such a premium, why convert the entire array to indices at once? I would hold on to the 40-byte xor array and loop through it (using your bitshift algorithm) when you need to look up an offset.

Improve this answer

2 Comments

Because the test vector can hold related faults at any position. A fault at position 5 maybe related to a fault at position 25. Your approach would work but if doing it this way it has the potential to provide more complete information to the operator.
Well, if you need to process the information you'll presumably have to organize it somehow. Organize it by looping over the bits directly. My point is, an array of 40x32 bits contains exactly the same information as an array of 1280 integer zeroes or ones.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.