3.1.8.2.3 Data Compression Example

This example is based on the flowchart in the preceding figure that describes the operation of the bulk compressor.

 Source Data (ANSI characters):
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
  
 HistoryPtr = 0
 HistoryOffset = 0

(1) Copy the source data to the history buffer.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
 ^ (HistoryPtr = 0)
  
 HistoryOffset = 49
  
 Output Buffer:
 <empty>

(2) No match larger than 2 characters found at the current position. Add the ANSI character at HistoryPtr ('f') to the output buffer and advance HistoryPtr.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
  ^ (HistoryPtr = 1)
  
 Output Buffer:
 f

(3) No match larger than 2 characters found at the current position. Add the ANSI character at HistoryPtr ('o') to the output buffer and advance HistoryPtr.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
   ^ (HistoryPtr = 2)
  
 Output Buffer:
 fo

(4) No match larger than 2 characters found at the current position. Add the ANSI character at HistoryPtr ('r') to the output buffer and advance HistoryPtr.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
    ^ (HistoryPtr = 3)
  
 Output Buffer:
 for

(5) No match larger than 2 characters found at the current position. Add the ANSI character at HistoryPtr ('.') to the output buffer and advance HistoryPtr.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
     ^ (HistoryPtr = 4)
  
 Output Buffer:
 for.

For the sake of brevity, we skip the next 19 steps where we just add ANSI characters to the output buffer.

(6) Current value of HistoryPtr is 23. No match larger than 2 characters found at the current position. Add the ANSI character at HistoryPtr (',') to the output buffer and advance HistoryPtr.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
                         ^ (HistoryPtr = 24)
  
 Output Buffer:
 for.whom.the.bell.tolls,

(7) We find a match in the history buffer at position 8 of length 15 characters (".the.bell.tolls"). Encode the copy-tuple and add it to the output buffer and advance HistoryPtr by the size of the match. Recall from section 3.1.8.2 that the copy-offset component of the copy-tuple is an index into HistoryBuffer (counting backwards from the HistoryPtr towards the start of the buffer) where there is a match to the data to be sent.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
                                        ^ (HistoryPtr = 39)
  
 Output Buffer:
 for.whom.the.bell.tolls,<16,15>

(8) No match larger than 2 characters found at the current position. Add the ANSI character at HistoryPtr ('.') to the output buffer and advance HistoryPtr.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
                                         ^ (HistoryPtr = 40)
  
 Output Buffer:
 for.whom.the.bell.tolls,<16,15>.

(9) We find a match in the history buffer at position 0 of length 4 characters ("for."). Encode the copy-tuple and add it to the output buffer and advance HistoryPtr by the size of the match.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
                                             ^ (HistoryPtr = 44)
  
 Output Buffer:
 for.whom.the.bell.tolls,<16,15>.<40,4>

(10) We find a match in the history buffer at position 25 of length 3 characters ("the"). Encode the copy-tuple and add it to the output buffer and advance HistoryPtr by the size of the match.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
                                                ^ (HistoryPtr = 47)
  
 Output Buffer:
 for.whom.the.bell.tolls,<16,15>.<40,4><19,3>

(11) No match larger than 2 characters found at the current position. Add the ANSI character at HistoryPtr ('e') to the output buffer and advance HistoryPtr.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
                                                 ^ (HistoryPtr = 48)
  
 Output Buffer:
 for.whom.the.bell.tolls,<16,15>.<40,4><19,3>e

(12) No match larger than 2 characters found at the current position. Add the ANSI character at HistoryPtr ('!') to the output buffer and advance HistoryPtr.

 History Buffer:
 0         1         2         3         4
 012345678901234567890123456789012345678901234567890
 for.whom.the.bell.tolls,.the.bell.tolls.for.thee!
                                                  ^ (HistoryPtr = 49)
  
 Output Buffer:
 for.whom.the.bell.tolls,<16,15>.<40,4><19,3>e!

(13) HistoryPtr (49) is not less than HistoryOffset (49), so we add the PACKET_COMPRESSED flag to the output packet and send the Output Buffer.