Email: Password: Remember Me | Create Account (Free)

Back to Subject List

Old thread has been locked -- no new posts accepted in this thread
???
01/28/11 00:59
Read: times


 
#180872 - You are forgetting memory variables in state machines
Responding to: ???'s previous message
A software test harness is additional source code that may be used during testing.

In some situations, you may split a large program into smaller modules, and perform module testing on them. Calling functions with different parameters (calling does mean software since your test generator would have a hard time calling anything unless you have a processor with external memory interface...) and verifying the output.

In some situations, physical properties may make inputs too slow in relatino to the number of combinations you need to test. You may have a 20-key keypad. The keyboard scan logic may have a 100ms debounce filter. The keypad may allow a user to enter a large number of command sequences (for example when programming a security alarm panel - adding sequence dial numbers, configuring inputs and outputs, protocol types etc). There may be 200 valid code sequences. But there may be a number of thousand boundary tests to check invalid combinations. Enter a phone number of zero digits. Trying a non-digit at first position. At second position. At third postion, ...

So you may need to test 5000 command sequences - each averaging 20 key presses. 100,000 key presses with a minimum delay of > 100ms between each. A mechanical device pressing the keys would be impressive and non-intrusive. An electrical device could be implemented where you connect to the PCB - but you still have the debounce filter time to care about. A software harness could replace the normal debounce algorithm with an alternative function that takes the next key press from a serial port. Suddenly, you may be able to test the command processing code at 1000 key presses/second (assuming a paltry 9600 baud for the key data).

You can't see how a lowly 8-bit processor can have 2^128 states? That is because you see a state as a pattern of inputs into a sequence of and/or/not logic producing output. But as soon as you add a single 8-bit memory cell into the state machine, you have suddenly created a memory effect. The state machine isn't any longer fully controlled by the input pattern - it is also affected by history. 10 inputs may be 2^10 states. With that single byte, you may have 2^18 states. With a 16-byte history memory in the state machine you may have 2^128 states just for the history memory. 16 bytes is tiny even for a 8051.

Think about a state machine processing protocol data from a serial port. The length byte received first is 8 or 16 bits of state information that the state machine must keep. The 8 or 16-bit command at the start of the packet is 8 or 16 bits of state it needs to keep. So a 16-bit length and a 16-bit command are alone enough to introduce 2^32 states within the decoder. And then we haven't considered the packet checksum (say CRC-32) or the possiblitiy for framing errors or parity errors.

Think about a state machine processing sign data for a sign showing bus arrival times. Lots of parameters and formatting options in the message the sign receives and have to decode. None of the states inside the decoder cares about the input bits you think are the only possible state-machine states. What about bold text? Blinking? Red color? Scrolling? Big font? Right-aligned? Time-delayed?

In short - quite a lot of embedded devices can have state machines with huge states just because the state machine needs to operate with internal memory.

The states gets too large to be possible to test with an external pattern generator even if the pattern generator would be able to generate a billion patterns per second.

So the only option is to switch to internal testing, using a software test harness. You can then force the contents of the state machine bytes before adding the next stimuli. So instead of running through 2^128 states, you can prune all "in-the-middle" parts and just test the corner cases. If you have a loop from 0 to 9999, the most important parts of the loop is 0, 1, 2 and 9998, 9999, (10000). An external pattern generator can't get the loop to take the big jump from 2 to 9998. But a sw test harness can do that, cutting away 99.9% of the work because it isn't interesting.

So software harnesses are critical parts much used in both embedded and PC development.

Next thing is that there are a number of tools that can read C code and analyze it and figure out important corner cases and automatically create test vectors. So when you change some part of the code, you can test it again using the old test vectors to see if you have accidentally introduced a change in the logic. The automatic code scanning can not only see that the loop starts at zero and should end at 9999. It can also notice conditionals inside the loop and figure out input patterns that can match a conditinal break or a conditional continue. So the pattern generator may figure out that it is also important to test the loop at 999, 1000, 1001, 1999, 2000, 2001, 2999, 3000, 3001, ... becaue these numbers also represents corner-cases for the algorithm. And the analysis code can figure out that the function is only safe to call with parameter "n" below the value 715, because for values 716 and larger, the code inside the loop will produce a negative result that may make the loop lock up.

So using C, you can both get help producing automatic software test harnesses. And you can get help finding corner cases in the code that needs to be tested to find +/- 1 errors or overflows or other little surprises that in real life may affect one customer in one million once every two years making the error just about totally impossible to test with traditional external tests.

Another thing is that you may have code that uses a variable in the main loop and updates the variable in an interrupt. A software test harness can allow you to change that variable at specific positions in the code, to verify the behaviour of the code. With an external pattern generator, it's almost impossible to trig an interrupt exactly between two specific assembler instructions in the main loop. Traditional external testing is one of the reasons why we do see strange behaviour from products when they live in the field do turn over one byte of a 16-bit counter but not the other when the other part of the code comes and picks up the value. so 0xffff should have become 0x0000 but the code did see 0xff00 because it had picked up the high byte before the increment and then got the low byte after the increment.

Regression testing really does help a lot. But regression testing works best when the source code is written to help with the testing. After all, even quite small projects with tiny processors can be much too complex to test if seen as a single black box.

List of 58 messages in thread
TopicAuthorDate
"standard syntax" of '51 assemblers            01/01/70 00:00      
   Use C            01/01/70 00:00      
      Use C - prudently            01/01/70 00:00      
         I hate C            01/01/70 00:00      
            Fight!            01/01/70 00:00      
            Time in the Trade            01/01/70 00:00      
               I'd submit that there are "gotcha's"            01/01/70 00:00      
                  The tools are better for HLL            01/01/70 00:00      
                  Gotchas!            01/01/70 00:00      
               Yes. Fight.            01/01/70 00:00      
                  why fight?            01/01/70 00:00      
                     that are still language-agnostic issues            01/01/70 00:00      
                        to Jan and others            01/01/70 00:00      
                           personal experience            01/01/70 00:00      
                  HLL productivity            01/01/70 00:00      
                     show me the proof            01/01/70 00:00      
                        Productivity article            01/01/70 00:00      
                           Tautologies!            01/01/70 00:00      
                              What's up with that???            01/01/70 00:00      
                           interesting but irrelevant            01/01/70 00:00      
                              Why is that irrelevant?            01/01/70 00:00      
                                 I think part of the confusion stems from this ...            01/01/70 00:00      
                                    which packages have you seen????            01/01/70 00:00      
                                       not those in recent history            01/01/70 00:00      
                                          I don't think that's true?            01/01/70 00:00      
                                             Common that consultants have commercial compilers            01/01/70 00:00      
                                                Who benefits?            01/01/70 00:00      
                                             Why would they buy that product at all?            01/01/70 00:00      
                                                So You are Niche            01/01/70 00:00      
                                          look at the link in my post above            01/01/70 00:00      
                                             Technology front            01/01/70 00:00      
                                                Richard doesn't exactly follow the technology front....            01/01/70 00:00      
                                                   and doesn't let that stop him ....            01/01/70 00:00      
                                                      Just because the paint is dry doesn't mean it won't work            01/01/70 00:00      
                                                   Perhaps not ...            01/01/70 00:00      
                                                Technology front? In '51 asm?            01/01/70 00:00      
                              again ... I have to agree            01/01/70 00:00      
                                 as usual, Richard            01/01/70 00:00      
                                    all you have to do is to read the whole message            01/01/70 00:00      
                        Do you test your code?            01/01/70 00:00      
                           sure I do            01/01/70 00:00      
                              What you can do ...            01/01/70 00:00      
                                 sw test harness            01/01/70 00:00      
                                    I don't know about yours, but mine can do that ...            01/01/70 00:00      
                                       Why didn't you read?            01/01/70 00:00      
                                          Well, I have to admit ...            01/01/70 00:00      
                                             You are forgetting memory variables in state machines            01/01/70 00:00      
                                                I think you're going over the top.            01/01/70 00:00      
                                                   Stop and think before you write            01/01/70 00:00      
                                                      Footnote about code coverage            01/01/70 00:00      
                                                         I agree with the principle, but not with the range            01/01/70 00:00      
                                                            Lucky you            01/01/70 00:00      
                                                               where you sit determines what you see            01/01/70 00:00      
                                                                  when seeing too little - get a chair to stand on            01/01/70 00:00      
                                                                     I'm not on board with all of that            01/01/70 00:00      
                                                                        I know, lifebuoy needed            01/01/70 00:00      
                  I have to agree            01/01/70 00:00      
            As I've often said ...            01/01/70 00:00      

Back to Subject List