Search |
 |
|
 |
| Author |
Message |
|
|
 Posted: Feb 18, 2012 - 08:50 AM |
|
Joined: Jun 08, 2011
Posts: 90
|
|
I need to detect the positions of bits set in a 40 byte bit array. The number of '1's can vary wildly and I'm thinking it's better if I first calculate the number of bits set and then allocate the array as follows:
Code:
unsigned int PositionOfOnes[countBitsSet];
This array will be passed to a function which returns the positions of '1's it detects in an bit array.
Is this legal in AVR-GCC? It compiled just fine (though my circuit is at work so I can't change it) but is it a recommend practice?
Should I switch over to malloc and declare a dynamic array? |
|
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 09:00 AM |
|
Joined: Mar 27, 2002
Posts: 18531
Location: Lund, Sweden
|
|
|
Quote:
Code:
unsigned int Ones[countBitsSet];
Is this legal in AVR-GCC?
That would depend on how countBitSet was defined.
Still, if the worst case is that all bits are set then you need an array of 40*8=320 elements to record all their positions. Assuming you actually have 640 bytes free for such an array, what would be more effective in the cases where you just need half of that? The coded has to work under worst-case conditions, anyway...
If you tell us more on why you need to do this, then we might have ideas to alternate solutions that are more efficient. |
|
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 09:11 AM |
|
Joined: Jun 08, 2011
Posts: 90
|
|
countBitsSet is just an unsigned int.
The bit array is basically a test vector that the uC receives via SPI. It compares this test vector with a stored test vector on an SD Card. The comparison is basically a XOR operation on every byte of the array.
This tells us where the anomalies lie but I also need the positions of the '1's in the array. To do this, I use the following function:
Code:
int returnSetBitPositionsInByte(char byteToCheck, unsigned char faultsAt[])
{
int shift=0,r;
unsigned char v = byteToCheck;
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
20, 8, 19, 18
};
int i=0;
while(1)
{
r = Mod37BitPosition[(-v & v) % 37];
faultsAt[i]=shift+r;
v = v >> (r+1);
shift = shift + r + 1;
if(v == 0x00) break;
i++;
}
return countBitsSet(byteToCheck);
}
This function counts the number consecutive zeroes in a byte from the right. Using that feature, I find the positions of '1's present in a byte by shifting it right. The Mod37BitPosition technique was something I found here: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup.
Note, the above function only calculates the number of '1's in a byte not in an bit array. There is an additional function which wraps around this and calls this function repeatedly to find the positions of '1's in the entire bit array. I, of course, have to offset the numbers because this function returns the positions relative to the byte it's processing whereas I need the position of '1's relative to the bit array. |
|
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 09:36 AM |
|
Joined: Mar 27, 2002
Posts: 18531
Location: Lund, Sweden
|
|
|
Quote:
countBitsSet is just an unsigned int.
If it is not known at compile time then your declaration (in the OP) is not valid C AFAIK. If you need to allocate something dynamically at run-time, then use malloc().
Quote:
but I also need the positions of the '1's in the array
Again, explaining how this is ultimately to be used might help us give some good advice.
Also, in the latest code it seems that countBitsSet is a function that you call. Earlier it was a variable. You are very confusing now.. |
|
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 09:50 AM |
|
Joined: Jun 08, 2011
Posts: 90
|
|
I'm sorry, the code in the first post was just pseudo code. countBitSet is indeed a function which just returns the number of bits set. So, to allocate an array, I'm doing the following:
Code:
int count = countBitsSet(myBitArray)
unsigned int PositionOfOnes[count];
From what I've read it seems the above code is legal in C99 but not C89. I think AVR Studio does use C99, but I'm not sure. Considering it's valid in C99, should I just go ahead and use it? Example: http://stackoverflow.com/questions/7372 ... is-allowed
This circuit is actually a wiring harness continuity checker. I drive a test vector onto the harness and recieve the data back from the other end. Between the uC and the harness is a CPLD, configured as a Parallel In Serial Out shift register, which talks to the uC via SPI.
Each bit position in the bit array corresponds to a pin of the CPLD onto which the harness is connected. Now, after the XOR operation we find the anomalies as only the bits which aren't supposed to be set or clear will be 1. So, suppose, I find a '1' at position 2. This implies that the wire at 2 is faulty. The uC then reads a file from an SD Card which provides information on the wire that's present at that particular position in the bit array. The information can be like the location of the wire (physically, on the harness), colour, gauge etc
The uC will then display this information on a graphic LCD so that the operator can find the fault.
I hope this clears up any confusion. |
|
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 10:00 AM |
|
Joined: Mar 27, 2002
Posts: 18531
Location: Lund, Sweden
|
|
|
Quote:
From what I've read it seems the above code is legal in C99 but not C89.
Well-well. I was convinced this was not allowed. You live and you learn.
The remaining warning then is that you should watch out so that you do not return (a pointer) to the array exiting the function where the variable was defined. At that point is is actually not "alive" any more, the memory it occupied is free for other uses and you might end up handling pure garbage later.
Example (sketchy, not tested):
Code:
int * foo(int theSize)
{
int theArray[theSize];
// Do something with theArray here...
return theArray; // DON'T DO THIS!
)
|
|
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 10:09 AM |
|
Joined: Jun 08, 2011
Posts: 90
|
|
Thank you. I will keep that in mind!
I'm actually just passing my PositionOfOnes array from main onto the function wrapper function I described earlier, so I think I should be OK as I'm not returning anything. Sort of like:
Code:
int count = countBitsSet(myBitArray);
unsigned int PositionOfOnes[count];
findPositionOfFaults(PositionOfOnes, count);
My only question is: are these sort of arrays (I believe called Variable Length Array) legal in AVR-GCC?
Doing a search didn't really return anything specific to AVR-GCC so I thought I'll ask here. It works well on GCC-4.2 (but oddly enough, there's a bug when using it with LLVM.)
EDIT: Some more digging reveals that even in GCC4.2 support for Variable Length Arrays is broken. Only GCC4.6 supports this.
Would you folks suggest I go with malloc then or just declare a 300 element array and be done with it? One way of reducing the memory issue footprint of the static array would be to declare it as an unsigned char instead of an unsigned int and simply assign the value '1' to the position where a set bit was found. So, for example, I find bit 32 to be set in the bit array. In my PositionOfOnes, I do
Code:
PositionOfOnes[32] = 1
;
What do you folks think of this approach? |
Last edited by NilRecurring on Feb 18, 2012 - 10:43 AM; edited 1 time in total
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 10:41 AM |
|
Joined: Mar 27, 2002
Posts: 18531
Location: Lund, Sweden
|
|
|
Quote:
Curiously, why is it that malloc is discouraged in embedded programming?
When general advice are given regarding embedded programming a lot of assumptions are made. I guess that two assumptions when malloc in embedded is discussed are
i) The system is severely memory challenged, and
ii) The programmer does not know/understand the implications of what he is doing.
I suppose the advice against malloc in embedded is based hevaily on people coming from e.g. PC programming where you can malloc away heavily, not free'ing or free'ing so that you get a heavily fragmented heap, w/o getting into serious trouble for a long time. In embedded, such coding spells disaster sooner rather than later.
As far as I can see there is no absolute argument for never using malloc in embedded systems. It always depends. The first question you should ask yourself is: What are the alternatives?
I.e. if you only need an array while a function is executing you might be better off with an automatic variable (read that as "local variable).
Or, if the array is only needed in one instance and used throughout large parts of the program and/or for most of the execution time, then you might be better of with a global variable.
HTH! |
|
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 12:03 PM |
|
Joined: Nov 09, 2011
Posts: 396
|
|
|
Quote:
Each bit position in the bit array corresponds to a pin of the CPLD onto which the harness is connected. Now, after the XOR operation we find the anomalies as only the bits which aren't supposed to be set or clear will be 1. So, suppose, I find a '1' at position 2. This implies that the wire at 2 is faulty. The uC then reads a file from an SD Card which provides information on the wire that's present at that particular position in the bit array. The information can be like the location of the wire (physically, on the harness), colour, gauge etc
The uC will then display this information on a graphic LCD so that the operator can find the fault.
Can you avoid creating the array of faulty wire positions entirely? Let's say you have the bitarray of faulty wires in
Code:
uint8_t fault_array[40];
You can iterate thru fault_array without needing to explicitly creating a list of bit positions that are set. So the code will look something like:
Code:
for (int wire = 0; wire < 320; wire++) {
int index = wire >> 3;
uint8_t mask = 1 << (wire & 0x7);
if (fault_array[index] & mask) {
report_fault(wire);
}
}
- S |
|
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 02:05 PM |
|
Joined: Jun 08, 2011
Posts: 90
|
|
|
mnehpets wrote:
ithout needing to explicitly creating a list of bit positions that are set. So the code will look something like:
Code:
for (int wire = 0; wire < 320; wire++) {
int index = wire >> 3;
uint8_t mask = 1 << (wire & 0x7);
if (fault_array[index] & mask) {
report_fault(wire);
}
}
- S
This is an interesting approach. We don't need to display all the errors in a test vector at once on the display, so why not just display the first one encountered, wait till it's fixed and then go on further.
There is one small issue though. For open or short circuits this will work perfectly. But there's another type of error that we call "Wrong Slot". This happens when a wire is inserted into a wrong slot i.e. suppose, a wire was supposed to go into connector A's pin 1 but it ends up going to connector B's pin 5. This IS detectable in my circuit because it effectively shows up as a short and an open (which, too, can open but is very rare in practice). So, for example, suppose the following is a known good vector 1111111 11111011 and the following is the received vector 11011111 11111111. In this, it's clear that the wire was inserted into the wrong position - the display can show that a wire that was supposed to be in position 2 is possibly in position 13.. If a wire is short circuited and also inserted into the wrong slot, the program can report ALL positions where the fault lies.
But to identify where the missing wire is going, I will have to scan the entire list of 'positions' - exactly like I was doing before. However, as this is a special case, I could program it such that I only allocate the 320 element array when a wrong slot is detected and not otherwise.
Do you think this is a good approach? |
|
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 07:44 PM |
|
Joined: Oct 29, 2006
Posts: 2640
|
|
|
NilRecurring wrote:
But to identify where the missing wire is going, I will have to scan the entire list of 'positions' - exactly like I was doing before. However, as this is a special case, I could program it such that I only allocate the 320 element array when a wrong slot is detected and not otherwise.
Do you think this is a good approach?
No. It's too much code, therefore too much maintenance.
Code:
#define BYTES_NUM 40
uint8_t bytes[BYTES_NUM];
uint16_t bit_positions[BYTES_NUM*8];
Unless bit_positions takes too much memory, one might as well allocate it as simply as possible.
Dynamic allocation should not be your default.
In borderline cases, dynamic allocation can make it worse.
Most dynamic allocation techniques use some memory for housekeeping.
That memory could doom your code.
Were I feeling especially anal, the 8 above would have been CHAR_BIT.
The names already there would seem to provide that information. |
_________________
Michael Hennebry
Iluvatar is the better part of Valar.
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 08:10 PM |
|
Joined: Nov 28, 2004
Posts: 3552
Location: San Diego, Ca
|
|
|
|
|
|
|
|
Posted: Feb 18, 2012 - 08:14 PM |
|
Joined: Jun 08, 2011
Posts: 90
|
|
|
skeeve wrote:
NilRecurring wrote:
But to identify where the missing wire is going, I will have to scan the entire list of 'positions' - exactly like I was doing before. However, as this is a special case, I could program it such that I only allocate the 320 element array when a wrong slot is detected and not otherwise.
Do you think this is a good approach?
No. It's too much code, therefore too much maintenance.
Code:
#define BYTES_NUM 40
uint8_t bytes[BYTES_NUM];
uint16_t bit_positions[BYTES_NUM*8];
Unless bit_positions takes too much memory, one might as well allocate it as simply as possible.
Dynamic allocation should not be your default.
In borderline cases, dynamic allocation can make it worse.
Most dynamic allocation techniques use some memory for housekeeping.
That memory could doom your code.
Were I feeling especially anal, the 8 above would have been CHAR_BIT.
The names already there would seem to provide that information.
They do take up lots of memory. There's absolutely no telling how many wires will go and so the program must be able to detect them all. Which means the worst care is an array of 320 elements (320 bits in 40 bytes). If each element is an uint16_t, that's effectively 640 bytes. At the moment, my SRAM is 77% full (on an AT Mega 128. Upgrading to 1281 ASAP). I have FatFs, graphic LCD code, SPI and this. I will also have a footprint for additional 64K SRAM on the next spin of the boards. So if we require it, we'll just slap the chip down.
Considering that, I suppose the best way is to just declare the 320 element array and be done with it.
--
If I were to do the following:
Code:
if(numShorts>0 && and numOpens>0)
{
uint16_t bit_positions[MAX_TEST_POINTS];
// do stuff
}
Will the program ONLY declare this array if there were both opens and shorts or would it always be on the stack? If the former, then would it still be too much maintenance if I chose mnehpets' approach when either shorts or opens existed but not both? |
|
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 11:05 PM |
|
Joined: Oct 29, 2006
Posts: 2640
|
|
|
NilRecurring wrote:
They do take up lots of memory. There's absolutely no telling how many wires will go and so the program must be able to detect them all. Which means the worst care is an array of 320 elements (320 bits in 40 bytes). If each element is an uint16_t, that's effectively 640 bytes. At the moment, my SRAM is 77% full (on an AT Mega 128. Upgrading to 1281 ASAP). I have FatFs, graphic LCD code, SPI and this. I will also have a footprint for additional 64K SRAM on the next spin of the boards. So if we require it, we'll just slap the chip down.
Considering that, I suppose the best way is to just declare the 320 element array and be done with it.
--
If I were to do the following:
Code:
if(numShorts>0 && and numOpens>0)
{
uint16_t bit_positions[MAX_TEST_POINTS];
// do stuff
}
Will the program ONLY declare this array if there were both opens and shorts or would it always be on the stack? If the former, then would it still be too much maintenance if I chose mnehpets' approach when either shorts or opens existed but not both?
The array would exist only during the body of the if.
Consider:
Code:
if(0==numShorts) {
uint16_t bit_positions[MAX_TEST_POINTS/2];
// process opens
} else if(0==numOpens) {
uint16_t bit_positions[MAX_TEST_POINTS/2];
// process shorts
} else {
uint16_t bit_positions[MAX_TEST_POINTS];
// process opens and shorts
}
Do process opens and process shorts require less memory than process opens and shorts?
If not, the worst case memory usage is not made worse by making all bit_positions's the same size.
If they are all the same size, they can have the same declaration.
If, somehow, you get the declaration wrong,
the fix will be in only one line.
Not only that, the declaration can occur before the computation of numShorts and numOpens.
In some circumstances that might be convenient.
If you compute numOpens and numShorts before declaring bit_positions,
you can still have a fairly simple single declaration:
Code:
uint16_t bit_positions[numShorts+numOpens];
Because of housekeeping data, if numShorts+numOpens==MAX_TEST_POINTS,
then this declaration will require a bit more memory than a simple
Code:
uint16_t bit_positions[MAX_TEST_POINTS];
When it comes time to debug, do you want to think about three declarations or just one? |
_________________
Michael Hennebry
Iluvatar is the better part of Valar.
|
| |
|
|
|
|
|
|
Posted: Feb 18, 2012 - 11:55 PM |
|
Joined: Jun 15, 2008
Posts: 1755
Location: North Carolina USA
|
|
| It will be on the stack for the scope of the declaration. Note on AVRs malloc comes off the stack anyway, starting from the end of .bss, with extra overhead for the block pointers (which are malloc'd themselves in fairly large chunks). In either case the advantage of a variable length array is to leave as much stack as possible, so the strange errors will only occur in the really complicated cases. |
|
|
| |
|
|
|
|
|
|
Posted: Feb 19, 2012 - 12:43 AM |
|
Joined: Nov 09, 2011
Posts: 396
|
|
|
Quote:
But to identify where the missing wire is going, I will have to scan the entire list of 'positions' - exactly like I was doing before.
Well, you're basically trading off memory for cpu cycles. You said that SRAM was tight, so it might be worth assessing whether burning extra cpu cycles is acceptable. Are there situations where it's unacceptable to do a full scan of 320 bits?
I would guess it would take less than 1 usec to check a single bit of the bitarray, so you're looking at less than 300ish usecs to scan thru the entire array (hmmm... this could probably be optimised for the sparse case by careful loop unrolling or table lookups). In the case where you are diagnosing the test signal to a single wire, I would guess you need to scan each of the test bitarray, result bitarray and fault bitarray once. So we get a total overhead of about 1 msecs. Note that you only have to do these scans where you have detected a fault. I would guess you would quickly check to see if all of the fault bitarray entries are 0 before doing a bit-by-bit scan. Something like this:
Code:
uint8_t fault_summary;
fault_summary = fault_vector[0]
| fault_vector[1]
| fault_vector[2]
| fault_vector[3]
[...]
| fault_vector[38]
| fault_vector[39];
if (fault_summary == 0) {
// test passes
return true;
}
// now do the slower diagnostics
- S |
|
|
| |
|
|
|
|
|
|
Posted: Feb 19, 2012 - 02:27 AM |
|
Joined: Oct 29, 2006
Posts: 2640
|
|
One way to solve your memory problems would be to get rid of Mod37BitPosition and use brute force.
In this case, brute force would be faster.
Even cutting it to uint8_t might do the trick.
That would take it down from 74 to 37 bytes.
Also, for 8-bit bytes, 11 is a big enough modulus.
From 74 to 11 would save 63 bytes,
more than enough to solve your memory problem.
The modulus technique isn't very useful on platforms that don't do a hardware modulus. |
_________________
Michael Hennebry
Iluvatar is the better part of Valar.
|
| |
|
|
|
|
|
|
Posted: Feb 19, 2012 - 06:53 AM |
|
Joined: Jun 08, 2011
Posts: 90
|
|
I wasn't aware that there was no improvement with Mod37BitPosition. I'll get rid of that and opt for more simpler code. But here's how my array business is looking:
Code:
int bit_positions[MAX_TEST_POINTS];
if(short_circuit_count>0 && open_circuit_count>0)
{
//Likihood that a wire was inserted into the wrong pin.
unsigned char wrong_slots[NUM_BYTES];
for(int i=0;i<NUM_BYTES;i++)
{
wrong_slots[i] = shorts[i] | opens[i];
}
int bit_set = open_circuit_count + short_circuit_count;
get_fault_positions(wrong_slots, kArraySlots, bit_set, bit_positions);
// find relevent information on SD Card.
// display data on LCD
// go back to start of program and wait till user presses "Check".
}
else if(short_circuit_count>0)
{
get_fault_positions(shorts, kArraySlots, short_circuit_count, bit_positions);
// find relevent information on SD Card.
// display data on LCD
// go back to start of program and wait till user presses "Check".
}
else
{
get_fault_positions(opens, kArraySlots, open_circuit_count, bit_positions);
// find relevent information on SD Card.
// display data on LCD
// go back to start of program and wait till user presses "Check".
}
MAX_TEST_POINTS would be 320 and NUM_BYTES would be 40. The reason for declaring bit_positions as an int is that any unused elements, I equate to -1. This has the advantage of that when I'm actually scanning through this array I will only have to loop till I encounter a -1. The alternative approach, one that utilized a char array, would be that I would equate 1 at the position where a '1' was declared - however I would have to scan through the entire array. I think I will try both approaches and see if the latter is fast enough, I'll go with that. |
|
|
| |
|
|
|
|
|
|
Posted: Feb 19, 2012 - 05:11 PM |
|
Joined: Oct 29, 2006
Posts: 2640
|
|
|
NilRecurring wrote:
MAX_TEST_POINTS would be 320 and NUM_BYTES would be 40. The reason for declaring bit_positions as an int is that any unused elements, I equate to -1. This has the advantage of that when I'm actually scanning through this array I will only have to loop till I encounter a -1. The alternative approach, one that utilized a char array, would be that I would equate 1 at the position where a '1' was declared - however I would have to scan through the entire array. I think I will try both approaches and see if the latter is fast enough, I'll go with that.
I'd replace MAX_TEST_POINTS with NUM_BYTES*8 or even NUM_BYTES*CHAR_BIT.
Instead of two application-defined constants that must satisfy a constraint,
one has one application-defined constant and an expression whose correctness is obvious.
Similarly, if both approaches to fault representation work,
the one to use is the one that is most obviously correct. |
_________________
Michael Hennebry
Iluvatar is the better part of Valar.
|
| |
|
|
|
|
|
|
Posted: Feb 19, 2012 - 08:49 PM |
|
Joined: Jun 08, 2011
Posts: 90
|
|
Thank you, Michael. Your posts have been invaluable.
I had another question regarding arrays - what if it was necessary to determine the size of the array at runtime? The 320 elements needed is for the worst case and when the system is actually running with 320 test points. The hardware of the circuit is such that the design is extendable via "daughter-cards". The main board, which has the uC, has 72 test points.
The number of daughter cards connected is controlled by a DIP switch and each daughter card will have 72 test points. In this case, it would be necessary to determine the size of the array at runtime, wouldn't it?
NOTE: The worst case is still 320. We will never have more than 320 test points connected. Should the size of the array STILL be a fixed 320 elements?
This extendable design is something we are considering and I thought I'd ask here what it would mean when it comes to arrays and memory. |
|
|
| |
|
|
|
|
|
|
|
|
FAQ
Search
Register
Log in to check your private messages
Log in
Maximize
RSS
