In this chapter, we will implement the compressor and decompressor purely in Spin using Test-Driven Development (TDD) methods. Rather than jumping straight into a PASM implementation, starting with a Spin version lets us ease into the problem and also debug more effectively. Once we have a working algorithm in Spin, we will translate it to PASM. In addition, a Spin version can act as a simulator to produce compressed data streams that the PASM decompressor will have to successfully operate on, and vice versa.
5.1 Structure of the Project
5.2 Goals of This Chapter
Start the process by copying 3 bytes from sampsBuf[0] to packBuf. This is done just once to initialize the compressor.
Take the difference of sampsBuf[1] - sampsBuf[0]. If that difference fits in 1 byte, then put that 1 byte in packBuf. If that difference is 2 bytes, put those 2 bytes in packBuf, and if that difference is 3 bytes, put those 3 bytes into packBuf.
Store a 2-bit code in comprCodeBuf that reflects which of three things we did.
Do the previous two steps repeatedly for all the samples (Figure 5-1 shows an example of a real-world “loop”).
The Loop, Agony Point, Darjeeling Hill Railway, 1880. Photo uploaded by Bourne and Shepherd; artist unknown. Public domain.
5.3 First Iteration
Begin by copying the template spin_template.spin and saving it as steim_spin0_Demo.spin. Listing 5-1 is the driver program that sets up the Propeller and then runs the tests to exercise the code. Make the changes shown in the file.
steim_spin0_Demo : First Iteration of Implementing the Compression in Spin
Lines 15–17: Declare the arrays where the packed samples will be stored (packBuf), the samples themselves (sampsBuf), and where the compression codes will be stored (comprCodeBuf). I know that packBuf will be at most four times the length of NSAMPS_MAX and that comprCodeBuf will be 1/16th that length.
Lines 30–31: Initialize the STEIM and TDD objects.
Lines 32–33: Run the test and finish.
Lines 36–38: Perform the compression for a single sample.
Lines 39–42: Verify whether the output is as we expect.
Line 43: Perform the test and print the results.
Add all the lines marked with '<< and add the method TEST_THAT_SAMP0_IS_PROPERLY_PACKED. Lines 4–5 add the STEIM and TDD objects. From now on, any method in the file steim_spin.spin can be called by STEIM.METH_NAME. Similarly, any constant in that file is STEIM#CONSTANT_NAME. Lines 13–17 declare the new variables that will be needed by the compression and the new arrays where the uncompressed samples live before compression ( sampsBuf ) and where the compressed bytes live ( packBuf ).
Finally, in lines 30–31 the two objects are initialized, and in line 32, the first test is run. By convention, tests begin with the word TEST and are descriptive and grammatical. The test method itself is in lines 35–43. Finally, the SUMMARIZE method is called that prints out the number of tests run, the number that succeeded, and the number that failed.
The test is simple: set sample 0 to a known value, call the compression routine, and verify that the compressed data in packBuf is correct. The returned value from COMPRESS is the number of bytes in packBuf or -1 if there is an error; if there is no error, packBuf and comprCodeBuf are modified.
Listing 5-2 shows the code that does the actual work.
steim_spin0.spin : First Iteration of the Compression Code
Lines 1–4: Constants that define the compression codes.
Lines 8–10: The initialization routine. Save a local version of NSAMPS_MAX.
Lines 12–21: The compression method, along with comments detailing what the inputs and outputs are.
Lines 22–26: Check the inputs.
Lines 30–32: Perform the compression for the first sample.
Lines 34–35: Return in the case of N ≡ 1.
Line 36: Otherwise, return an error.
The actual compression is simple. We copy the three low bytes of sampsBuf[0] to packBuf[0]-packBuf[2], we set the compression code to reflect that this is a 3-byte packing, and we return the number 3. The calling code for COMPRESS is as follows:
The method definition is as follows:
MAIN passes in the addresses of the arrays; in particular, it passes the memory location of the first element of each array (@sampsBuf). The method definition saves those addresses as psampsBuf, and so on.
5.4 Passing Arrays to Methods
The compression method in the STEIM object must access the arrays sampsBuf, packBuf, and comprCodeBuf. To do so, it needs the address in hub memory where each of them is stored. The calling method is written thusly:
The symbol @sampsBuf is shorthand for “address of the first byte of the first sample of the sampsBuf array.”
The definition of the called method in the STEIM object is as follows:
Here the variable psampsBuf holds that address. To access that data, we must inform the compiler that the variable is an address (rather than a value). In other words, to access the i-th sample (sampsBuf[i]), we must say long[psampsBuf][i]. Similarly, ppackBuf holds the address of the byte array packBuf, and it must be accessed as byte[ppackBuf][i]. To copy data from sampsBuf to packBuf, we must do something like the following:
Here, 3 bytes are copied from the address psampsBuf (which is the address of the start of that array) to the address ppackBuf (which is the address of the start of the packBuf array).
The bytemove command copies 3 bytes from memory location psampsBuf to memory location ppackBuf (a longmove command would have moved 3 longs).
The expression long[pcomprCodeBuf] := CODE24 says to treat the address pcomprCodeBuf as a long and to write to all 4 bytes following that address.
A function/method definition in Spin looks like this:
The arguments arg1 and arg2, the return value retVal, and the local variable localVar are all optional .
5.5 Testing
Here are the tests that I run. As I was developing the code, I started out with the simpler tests (testing that sample 0 was packed correctly and then sample 1) and moved to successively more complex tests (sample 15, and so on).
I built up the code by writing the test and then writing the code that lets the test succeed. As I built up the code bit by bit, I made sure all the tests were run every time I modified the program and that they all passed.
5.6 Final Code
I won’t go through the compression and decompression routines in detail because the focus of this book is on PASM (and they are quite self-explanatory). However, I reproduce them here because I’ll refer to them when I am developing the PASM code.
5.6.1 Compression in Spin
The full compression code first checks that the inputs are correct. Next, the first sample is compressed, and then the remaining samples are differenced and compressed. The driver file (steim_spin1_Demo.spin) will call the code in Listings 5-3 and 5-4 (which are in file steim_spin1.spin).
steim spin1.spin: Complete Compressor Code Listing
Lines 11–21: Verify inputs and compress sample 0.
Line 27: Form the backward difference δ j = s j − s j−1 .
Line 28: Calculate the absolute value a j = |δ j |.
Lines 29–30: The compression codes are 2 bits each, so the codes for samples s j , j = 0–15 are in comprCodesBuf[0], the codes for samples s j , j=16–31 are in comprCodesBuf[1], and so on. The j-th code is shifted by (j mod 16) × 2 bits.
Lines 31-42: Depending on whether a j fits in 1, 2, or 3 bytes, place the difference in packBuf and place the code in comprCodeBuf .
5.6.2 Decompression in Spin
The decompression is a little more involved, mainly because negative numbers have to be sign-extended properly. The general outline is the same as for compression: handle the first sample and then loop through the remaining samples.
steim_spin.spin: Spin Decompression Method
Lines 26–30: Determine the compression code for this sample by getting the correct long from the comprCodesBuf array and then getting the appropriate 2 bits.
Lines 31–46: Copy the difference bytes (either 1, 2, or 3, depending on the compression code for this sample) from packBuf and sign-extend them to form a proper 32-bit δ j . The operations diff <<= 24 and diff ~>= 24 will first shift the low byte up to the high byte location and then do an arithmetic shift back to the low byte. An arithmetic shift retains the sign of the byte. So, if the low byte was a negative 1-byte number (-127 to -1), then the 32-bit number would still be negative (with 1s in all the high bits).
Lines 51–58: Form the sample s j = s j−1 + δ j and sign-extend.
As we build up the PASM code , we have to reproduce each of these steps, including the loops.
5.7 The Need for Speed
The main reason to implement the code in PASM is to speed it up. Let’s see how much time the compression and decompression take in Spin. Listing 5-5 shows the timing code in the driver file steim_spin1_Demo.spin.
Measuring the Timing of Compression
Running this code prints out the following:
Here, nc is the number of bytes in the compressed buffer packBuf, and the two dt values are the time taken to perform the compression (in clock cycles and milliseconds, respectively).
If your application is OK with taking 20ms to compress 128 samples, then you can stop right here. If not, let’s estimate how much of a speedup we can expect in PASM.
5.7.1 Timing in PASM
Each instruction in PASM takes a fixed number of clock cycles that are documented in the manual. Almost all the instructions take four clock cycles exactly.1
A clock cycle is 12.5ns (when the system clock is running at 80MHz), so typically instructions require 50ns to complete.
The system clock is determined by the constants shown in Listing 5-6 in the main Spin file.
Clock Mode Settings
_XINFREQ is the frequency of the external crystal. The _CLKMODE variable sets the clock to 16 times the crystal frequency (in this case, 80MHz).
5.7.2 PASM Timing Estimate
During the compression, there is some setup, and then all the samples are processed.
Read a sample from the hub (∼20 clock cycles).
Subtract from the previous one (∼5 instructions, ∼20 cycles).
Take the absolute value (∼5 instructions, ∼20 cycles).
Check for the length of the absolute value (∼10 instructions, ∼40 cycles).
Calculate the compression code location (∼5 instructions, ∼20 cycles).
Write up to 3 bytes to the hub (∼60 cycles).
Initialize the variables (∼10 instructions, ∼40 cycles).
Take care of the overhead, in other words, writing the compression code to the hub every 16 samples, or 8 times for 128 samples (∼20 cycles × 8 ∼ 160 cycles).
Bullock cart in front of Victoria Terminus (“The most magnificent railway station in the world,” Bombay, India, 1903. https://upload.wikimedia.org/wikipedia/commons/f/f4/Victoriaterminus1903.JPG .
5.8 Summary
In this chapter, we worked through a full example of using Test-Driven Development to build and verify a Steim compressor and decompressor . The code is pure Spin, with a driver file (with a Demo suffix) and a worker file with functions (also known as methods) that are called from the driver. The tests are in the driver file, and each one exercises one small part of the specification.
I showed how a function/method is defined and called, how to test the inputs for reasonableness, how to copy bytes out of a long, and how to correctly copy them back in during decompression. I discussed how to pass variables and arrays to a Spin function and how to get a return value.
Finally, you learned how measure the time taken to process an array.