In this chapter we will write a PASM decompressor. We will go in the opposite direction from the compression code (flowchart in Figure 10-1): converting the packBuf array to the sampsBuf array (using the comprCodeBuf array to help in the reconstruction). In Figure 10-2, we have a great picture demonstrating that what goes up must come down... and that work can be fun!
10.1 Getting the Sign Right
Remember, packBuf contains sample 0 (the low 3 bytes) and differences between the j-th and j-1 sample. The length of the difference is stored (as 2 bits at the appropriate location) in the long array comprCodeBuf.
To regenerate the samples, we need to first get the difference value and make it a proper long. Let’s say the difference between two samples was equal to -200, which would be represented as a 2s-complement long:
11111111 | 11111111 | 11111111 | 0011 1000 |
Because the absolute value of the number is greater than 127, this will be stored in 2 bytes in
packBuf
, as shown here:
To reconstruct the original number, we have to sign-extend the high bit of the second byte. If that bit is 1 (as it is here), then we must put 1s in all the bits of the upper 2 bytes as well.
10.2 Overall Flowchart
Figure 10-1 shows the flowchart
. We trigger the decompression by setting N < 0 (myns) to signal the PASM cog that we want decompression rather than compression (recall, for compression, we set N > 0).
Figure 10-1
Flowchart for decompression of samples
The cog will read a compression code long and, based on the codes, read the correct number of bytes from packBuf. It will then reconstruct a sample. Every 16th sample, it will read a new compression code from hub memory. Finally, after processing all the samples, it will set N = 0.
Once the PASM cog completes the decompression
, it will set myns to zero and set myncompr to the number of bytes read from packBuf during the decompression. (This can be used as a check on the decompression; it should be equal to ncompr from the compression stage.)
10.3 Spin Code
Listing 10-1 shows the Spin code
for decompression.
1 PUB DECOMPRESS(psampsBuf, ns, ppackBuf, ncompr, pcomprcodeBuf)
2 " Inputs : psampsBuf - address of long array of samples (max len mymax)
3 " ns - number of samples to decompress
4 " ppackBuf - address of byte array of packed data
5 " pcomprCodeBuf - address of long array of compression codes
6 " Output : ncompr - number of bytes unpacked from packBuf
7 " Modified : sampsBuf
8 myns := 0
9 myncompr := 0
10
11 sampsBufAddr := psampsBuf
12 packBufAddr := ppackBuf
13 comprCodeBufAddr := pcomprCodeBuf
14
15 ' this will start the decompression
16 ' set to negative ns to trigger decompression
17 myns := -ns
18
19 ' when myns is zero, the decompression is complete
20 repeat until myns == 0
21 return myncompr
Listing 10-1
Decompression Method in Spin That Triggers the PASM Decompression Cog
10.4 PASM: Main Decompression Loop
We will use the same cog as in the previous chapter but will trigger a decompression if myns < 0 (in the previous chapter, myns > 0 was a signal to start a compression). See Listing 10-2.
1 mov _ccodebitidx, #0
2 mov _ccodelongidx, #0
3
4 ' ADD THESE LINES >>>
5 ' check for compression or decompression ?
6 abs r0, _cns wc ' C set if nsamps < 0
7 if_c jmp #:decompress
8 ' ADD THESE LINES <<<
9
10 call #GET_SAMPLE
11 mov _cprev, _csamp ' save sample for diff
12 call #HANDLE_SAMP0
Listing 10-2
Decompression Code in PASM; Initialization
Here we add two lines in the initialization section: abs r0, cns wc will take the absolute value of _cns and set C if _cns is negative. If so, jump to :decompress.
Listing 10-3 shows the decompression code.
Figure 10-2
Riding the cog railway down. Mt. Washington Railway. By Benjamin West Kilburn (1827–1909). Reproduced from an original stereographic card published by Kilburn Brothers, Littleton, New Hampshire, Public Domain,
https://commons.wikimedia.org/w/index.php?curid=20253073
.
1 : decompress ' _cns negative
2
3 rdlong _ccomprcode, _ccomprcodebufptr
4 mov _cncompr, #0
5 mov _cj, #0
6
7 call #MK_SAMP0
8 call #PUT_SAMPLE
9
10 add _cj, #1 'sample number j
11 add _cns, #1 wz
12 if_z jmp #:donedecomp
13
14 ' and the rest of the samps
15 : loopdecompns
16 call #MK_SAMPJ
17 call #PUT_SAMPLE
18 add _cj, #1
19 add _cns, #1
20
21 ' every 16th sample, read a new comprcode long
22 test _cj, #15 wz
23 if_nz jmp #:testns
24 add _ccomprcodebufptr, #4
25 rdlong _ccomprcode, _ccomprcodebufptr
26
27 : testns
28 tjnz _cns, #:loopdecompns
29
30 : donedecomp
31 wrlong _cncompr, _cncomprPtr
32 ' signal decompression complete
33 wrlong _cns, _cnsPtr
34 jmp #:mainLoop
Listing 10-3
Decompression Code in PASM; Details
You should recognize most of the code, explained here:
- Lines 3–5: Get the first compression code long and initialize the variables ncompr and j.
- Lines 7–8: Make sample 0 from packBuf and write it to sampsBuf in the hub (subroutines are explained in the next section).
- Lines 10–12: Here we add 1 to _cns because it starts out at -ns. When it is zero, we are done.
- Lines 15–28: Loop over the remaining samples.
- Lines 22–25: During this loop, every 16th sample, read a new compression code long from hub memory.
- Lines 28–34: Once we have processed all the samples, set myncompr to the number of bytes read from packBuf and set myns to zero to signal the completion of decompression.
10.5 Subroutines for Unpacking
1 PUT_SAMPLE
2 ' put a sample from _csamp to HUB sampsBuf
3 wrlong _csamp, _csampsbufPtr
4 add _csampsbufPtr, #4
5 PUT_SAMPLE_ret ret
Listing 10-4
Decompression Code in PASM; Subroutine to Save a Sample to the Hub After Reconstruction
PUT SAMPLE should be obvious: write the reconstructed sample back to hub memory and increment the pointer. See Listing 10-5.
1 MK_SAMP0 ' decompress samp 0
2 ' read from HUB packbuf to _csamp for samp0 (3 bytes)
3 mov r0, #0
4 mov _csamp, #0
5 :read3
6 rdbyte r1, _cpackbufPtr
7 shl r1, r0
8 or _csamp, r1
9 add _cpackbufPtr, #1
10 add r0, #8
11 cmp r0, #24 wz
12 if_nz jmp #:read3
13
14 rol _csamp, #8 ' sign extend
15 sar _csamp, #8
16
17 ' update ncompr and code
18 add _cncompr, #3
19 shr _ccomprcode, #2 ' remove samp0 code ...
20 MK_SAMP0_ret ret
Listing 10-5
Decompression Code in PASM; Subroutine to Reconstruct the First Sample
MK_SAMP0 reads 3 bytes from packBuf and places them in the correct spots in _csamp.
- Lines 3–4: r0 is the number of bits to shift each byte of packBuf. r1 is the current byte read from packBuf and shifted by 0, then 8, then 16 bits (bytes 0, 1, and 2, respectively).
- Lines 5–12: Loop three times to :read3 (r0 = 0, 8, and 16). When r0==24, break out of the loop. The sign bit for the sample isn’t correctly set yet (the upper byte, which is byte 3, containing bits 31–24 are all zero. However, if the sample was originally negative, those bits should all be 1. Luckily, that information (about whether the sample was originally negative or positive) is in the most significant bit of byte 2 (bit 23). If the sample was originally negative before compression, bits 23 would have been 1; if the sample was positive, bit 23 would be 0. The instruction rol _csamp, #8 shifts bits 23–0 up to bits 31–8, and sar _csamp, #8 then shifts the bits back to the right but preserves the sign of the long. In other words, we shift bit 23 to bit 31 (rol) and then shift bit 31 back to 23, but if it is a 1, then bits 31–23 are set to 1. If that MSB is a zero, then those bits are set to 0.
- Lines 18–19: Update ncompr and comprCode.
Finally, Listing 10-6 shows the reconstruction of the j-th sample by properly making the difference and adding it to the previous sample.
1 MK_SAMPJ
2 mov r0, #0 ' number of bytes
3 mov _cdiff, #0
4 mov r1, _ccomprcode
5 and r1, #3 ' get compr code for this samp. (2 low bits)
6 shr _ccomprcode, #2 ' and prep for next loop ...
7
8 ' byte 0 - right most
9 rdbyte r2, _cpackbufPtr
10 add _cpackbufPtr, #1
11 mov _cdiff, r2
12 add r0, #1
13 cmp r1, _ccode08 wz ' check r1 (code)
14
15 if_z jmp #:shiftde
16
17 ' byte 1
18 rdbyte r2, _cpackbufPtr
19 add _cpackbufPtr, #1
20 rol r2, #8
21 or _cdiff, r2
22 add r0, #1
23
24 cmp r1, _ccode16 wz
25 if_z jmp #:shiftde
26
27 ' byte 2
28 rdbyte r2, _cpackbufPtr
29 add _cpackbufPtr, #1
30 rol r2, #16
31 or _cdiff, r2
32 add r0, #1
33
34 : shiftde
35 ' set the sign of the diff correctly by sign extending ...
36 ' 1 byte diff ...
37 cmp r0, #1 wz
38 if_nz jmp #:sh2
39 rol _cdiff, #24 ' sign extend
40 sar _cdiff, #24
41 jmp #:donede
42
43 ' 2 byte diff ...
44 :sh2
45 cmp r0, #2 wz
46 if_nz jmp #:sh3
47 rol _cdiff, #16 ' sign extend
48 sar _cdiff, #16
49 jmp #:donede
50
51 ' 3 byte diff ...
52 :sh3
53 rol _cdiff, #8 ' sign extend
54 sar _cdiff, #8
55
56 : donede
57 ' add sample to prev
58 add _csamp, _cdiff
59 ' now mask off the high byte and sign extend the 3 lower
60 rol _csamp, #8
61 sar _csamp, #8
62 add _cncompr, r0 ' update ncompr
63 MK_SAMPJ_ret ret
Listing 10-6
Decompression Code in PASM; Subroutine to Reconstruct a Sample
MK SAMPJ tests the value of the compression code for the j-th sample and reads 1, 2, or 3 bytes from packBuf accordingly. It writes those bytes to _cdiff (with the dance of shifting left and right to get the sign right) and then adds _cdiff to _csamp to get the current sample (again, with the shift left/right dance).
- Lines 2–6: Initialize variables. r0 is number of bytes to read, r1 is the compression code, and r2 will be the byte read from packBuf.
- Lines 9–15: Read a byte, place it in _cdiff, and check the code to see whether we are done.
- Lines 13–25: If code was CODE08, then we’re done. If not, then get another byte, shift it left by 8, and or it with _cdiff.
- Lines 28–32: Again, these lines will properly set byte 2 if necessary (if the compression code is CODE16).
- Lines 34–54: If only 1 byte was read (r0==1), then shift _cdiff by 24 bits up and then back down. If 2 bytes were read, then shift by 16; if 3 were read, then shift by 8; and so on.
- Lines 58–62: Add _cdiff to _csamp (the previous sample), shift it up by 8, and then shift it back down and return.
10.6 Testing Decompression of Two Samples
The testing is straightforward: compress the samples and then decompress them. In between the compression and decompression, I set sampsBuf to zero, so I know that the values in sampsBuf after decompression were in fact generated by the decompression code. Compare these values for sampsBuf with the original numbers.
1 PUB MAIN
2 ...
3 TEST_THAT_SAMP0_IS_PROPERLY_UNPACKED
4 TEST_THAT_SAMP1_IS_PROPERLY_UNPACKED
5 ...
6 PRI TEST_THAT_SAMP0_IS_PROPERLY_UNPACKED | t0, nc, nc1, ns, d
7 nsamps := 1
8 d := $FF_FF_AB_CD
9 sampsBuf[0] := d
10 nc := COMPR.COMPRESS (@sampsBuf, nsamps, @packBuf, @comprCodeBuf)
11 sampsBuf[0] := 0
12
13 nc1 := COMPR.DECOMPRESS (@sampsBuf, nsamps, @packBuf, nc, @comprCodeBuf)
14
15 t0 := (nc == nc1) & (sampsBuf[0] == d)
16 TDD.ASSERT_TRUTHY (t0, string (" Test that sample 0 is properly unpacked from packBuf "))
17
18 PRI TEST_THAT_SAMP1_IS_PROPERLY_UNPACKED | t0, nc, nc1, ns, s0, s1
19 nsamps := 2
20 s0 := $FF_FA_09_19
21 s1 := $FF_FA_4F_2E
22 sampsBuf[0] := s0
23 sampsBuf[1] := s1
24 nc := COMPR.COMPRESS (@sampsBuf, nsamps, @packBuf, @comprCodeBuf)
25 sampsBuf[0] := 0
26 sampsBuf[1] := 0
27
28 nc1 := COMPR.DECOMPRESS (@sampsBuf, nsamps, @packBuf, nc, @comprCodeBuf)
29 t0 := (nc == nc1) & (sampsBuf[1] == s1)
30 TDD.ASSERT_TRUTHY (t0, string(" Test that sample 1 is properly unpacked from packBuf "))
The test should pass, as shown here:
Test that sample 0 is properly unpacked from packBuf
...ok
Test that sample 1 is properly unpacked from packBuf
...ok
10.7 Testing Decompression of 128 Samples
OK, that worked. Let’s try it with 128 samples. We will generate 128 pseudorandom numbers. Listing 10-7 shows the Spin instructions.
1 j := 0
2 sampsBuf[j] := cnt ' seed it with counter
3 ?sampsBuf[j] ' pseudorandom number
4 sampsBuf[j] &= $FF_FF_FF ' low 3 bytes only
5
6 sampsBuf[j] <<= 8 ' sign extend
7 sampsBuf[j] ~>= 8
8 sav[j] := sampsBuf[j]
Listing 10-7
Testing the Decompression Code; 128 Samples Initialized
These instructions will seed the sample with the current value of the counter and then use that seed to look up a pseudorandom number. The number has to be limited to 3 bytes, so we mask off those 3 bytes and then sign-extend the upper bit.
The compression, decompression, and testing are done as shown in Listing 10-8.
1 nc := COMPR.COMPRESS (@sampsBuf, nsamps, @packBuf, @comprCodeBuf)
2
3 repeat j from 0 to nsamps -1
4 sampsBuf[j] := 0
5
6 nc1 := COMPR.DECOMPRESS (@sampsBuf, nsamps, @packBuf, nc, @comprCodeBuf)
7
8 t0 := (nc == nc1)
9 repeat j from 0 to nsamps -1
10 t1 := (sampsBuf[j] == sav[j])
11 t0 &= t1
Listing 10-8
Testing the Decompression Code; Stub Showing Test Results
The samples are compressed, the sampsBuf array is cleared, and the samples are decompressed. We then check that the number of compressed and decompressed bytes is equal (nc==nc1) and that the samples are equal to their saved values.
1 PUB MAIN
2 ...
3 TEST_THAT_128_SAMPS_PROPERLY_COMPRESS_AND_DECOMPRESS
4 ...
5 PRI TEST_THAT_128_SAMPS_PROPERLY_COMPRESS_AND_DECOMPRESS | t0, t1, j, nc, nc1, sav [128]
6 nsamps := 128
7
8 j := 0
9 sampsBuf[j] := cnt ' seed it with counter
10 ?sampsBuf[j] ' pseudorandom number
11 sampsBuf[j] &= $FF_FF_FF ' low 3 bytes only
12
13 sampsBuf[j] <<= 8 ' sign extend
14 sampsBuf[j] ~>= 8
15 sav[j] := sampsBuf[j]
16
17 repeat j from 1 to nsamps -1
18 sampsBuf[j] := sampsBuf[j -1]
19 ?sampsBuf[j] ' pseudorandom numbers
20 sampsBuf[j] &= $FF_FF_FF ' low 3 bytes only
21 sampsBuf[j] <<= 8 ' sign extend
22 sampsBuf[j] ~>= 8
23 sav[j] := sampsBuf[j]
24
25 nc := COMPR.COMPRESS (@sampsBuf, nsamps, @packBuf, @comprCodeBuf)
26
27 repeat j from 0 to nsamps -1
28 sampsBuf[j] := 0
29
30 nc1 := COMPR.DECOMPRESS (@sampsBuf, nsamps, @packBuf, nc, @comprCodeBuf)
31
32 t0 := (nc == nc1)
33 repeat j from 0 to nsamps -1
34 t1 := (sampsBuf[j] == sav[j])
35 t0 &= t1
36
37 TDD.ASSERT_TRUTHY (t0, string(" Test that compression and decompression of 128 random numbers is successful "))
Next run the test, as shown here:
Test that compression and decompression of 128 random numbers is successful
***FAIL
Oh no! What went wrong? Let’s do some debugging in the next chapter. As you can see in Figure 10-3, there are real-world consequences to engineering or user mistakes!
Figure 10-3
Derailment at Eastwood Junction, 1948.
https://upload.wikimedia.org/wikipedia/commons/4/4a/Derailment_at_Eastwood%2C_1948_%285247093755%29.jpg
.
