Showing posts with label Bonus Material. Show all posts
Showing posts with label Bonus Material. Show all posts

2008/03/04

Bonus: Automated Testing

One of the principles of agile development is that your code should have completely automated unit tests. Your tests should require no interaction on your part, and they should require no interpretation; they should simply run and say pass or fail. If your tests require input, then they are not repeatable. If they require interpretation, then they are not automated.

By building an automated regression suite, you can use the tests as an enabler of change to allow you to test every change that you make to your code-base with little effort. Ideally, you would make running tests as part of your build process. In most agile environments, the automated execution of tests is at least part of the integration process (when you commit your code changes to the repository).

There are many testing tools available for agile developers. The most popular is the xUnit framework. (Java: JUnit, .NET: NUnit, C++: CppUnit). These tools may be too heavyweight to learn just for testing your cs213 assignment, so we're going to see how to write an automated testing framework using some more basic primitives. The C language includes a basic assertion package <assert.h>.

Consider the file:
testable.c:
#include <stdbool.h>
#include <assert.h>

int isBiggerThanFive(const int x) {
    return x > 5;
}

int main() {

    assert(true == isBiggerThanFive(10));
    assert(true == isBiggerThanFive(6));
    assert(false == isBiggerThanFive(5));
    assert(false == isBiggerThanFive(4));
    assert(false == isBiggerThanFive(-10));

    return 0;
}

Compiling and running this file with gcc -Wall testable.c -o testable; ./testable produces no output since all of the tests pass.

[Note: an assertion is a statement that something is believed to be true, so all of your assertions should pass.]

If we add the incorrect assertion that assert(false == isBiggerThanFive(50)); to the bottom of our method, we get the output:

testable: testable.c:15: main: Assertion `0 == isBiggerThanFive(50)' failed.

This is telling us that for the executable testable, in the file testable.c, on line 15, in method main, our assertion that false == isBiggerThanFive(50) failed. In this case, it's because our test is invalid, but it could have just as easily been an error in our implementation.

If we add another incorrect assertion to our test method true == isBiggerThanFive(0) and re-build, we still get the same output. There is no output from the second test, even though it should fail. This is the expected behavior.

In unit testing, it's desired that a test harness fails on the first error for each test. There is no sense in continuing to run a test after a failure since it means that the unit under test (or the test itself) has entered an unknown state, and therefore we can no longer make assertions (our belief was wrong).

Failing an assert in C causes the program to abort execution. This has the unfortunate effect that only one unit test can fail per executable (subsequent tests will not run if there was a failure). The xUnit testing frameworks handle testing multiple units better, but assert is good enough for testing small programs.

If you don't want to use the assert library, you can write your test harnesses to use the printf function, but all that you should be printing is pass or fail [details]; don't print things that require you to read them to verify that they are correct, as this will destroy any chance of test automation.

See also:

2008/02/07

Bonus: Advanced Branching (Switch Statement)

Consider a switch statement:


switch(r0) {
  case 0: ~~~0;
          break;
  case 1: ~~~1;
          break;
  ...
  case 0xf: ~~~f;
            break;
  default:
            ~~~default;
}
~~~done

If / Else Naive Implementation

  0: rr move r1, r0     # r1 = r0
     beq r1, 0x??0      # goto "0" case
     dec r1             # r1 = r0 - 1
     beq r1, 0x??1      # goto "1" case
     ...
     dec r1             # r1 = r0 - f
     beq r1, 0x??f      # goto "f" case
     ~~~default         # execute "default" case
     br 0x???           # exit
??0: ~~~0               # execute "0" case
     br 0x???           # exit
??1: ~~~1               # execute "1" case
     br 0x???           # exit
...
??f: ~~~f               # execute "f" case
???: ~~~done            # outside the switch
Case     # conditions evaluated      # branches taken
  0                 1                      2
  1                 2                      2
 ..
  e                15                      2
  f                16                      1
 <0                17                      1
 >f                17                      1
Sum:              170                     31

Every additional case adds progressively more and more to the number of conditions evaluated. The number of branches taken remains constant for each execution path.

Switch / Jump Table Implementation

   0:  move r1, r0          # r1 = r0
       dec r1               
       bgt r1 0x08          # ensure >=0 (in range)
       br "def"             # if not, goto "default" case
   8:  move r1, r0          # r1 = r0
       ld $0xFFFFFFF1, r2   # r2 = -f
       add r2, r1           # r1 = r0 - f
       bgt r1 "def"         # goto "default" case if > f
       move r1, r0          # r1 = r0 (and r1 is in range)
       ld $0x00001000, r2   # r2 = & jump table
       jmp *(4*r1, r2)      # jump to the right case
"c0":  ~~~0                 # case "0"
       br "done"            # exit
"c1":  ~~~1                 # case "1"
       br "done"            # exit
...
"cf":  ~~~f                 # case "f"
       br "done"            # exit
"def": ~~~~default         # "default" case
"done" ~~~~done            # outside the switch
...
1000:  &"c0"    # jump table, filled with addresses of cases
       &"c1"
       ...
       &"cf"
Case     # conditions evaluated      # branches taken
  0                 3                      3
  1                 3                      3
 ..
  e                 3                      3
  f                 3                      3
 <0                 1                      1
 >f                 2                      1
Sum:               48                     47

More cases do not grow the number of conditions evaluated per path, and the number of branches taken per path remains constant.

Special Note: the number of branches taken in the above example is higher than that of the if/else example due to the branch on the ">0" case. This branch can be eliminated by reversing the test:

   0:  move r1, r0          # r1 = r0
       not r1               # 
       inc r1               # r1 = -r0
       bgt r1 "def"         # goto "default" if <0
   8:  move r1, r0
       ld $0xFFFFFFF1, r2   # r2 = -f
       add r2, r1           # r1 = r0 - f
       bgt r1 "def"         # goto "default" case if > f
       move r1, r0          # r1 = r0 (and r1 is in range)
       ld $0x00001000, r2   # r2 = & jump table
       jmp *(4*r1, r2)      # jump to the right case
...
Case     # conditions evaluated      # branches taken
  0                 3                      2
  1                 3                      2
 ..
  e                 3                      2
  f                 3                      2
 <0                 1                      1
 >f                 2                      1
Sum:               48                     32

For more information, see Implementing Common Control Structures in Assembly Language and/or C to Assembly Translation III.