WAH is to define the fills and tails so that they can be stored in words ??“ the smallest
operational unit of modern computer hardware.
The WAH compression is illustrated in Figure 5. Assuming that a machine word is
32 bits long, the example shows how a sequence of 5456 bits (see Figure 5(a)) is
broken into two runs and encoded as three words. Conceptually, the bit sequence
is first broken into groups of 31 bits each (see Figure 5(b)). Next, the neighboring
groups with identical bits are merged (Figure 5(c)). Finally, these three groups
are encoded as 32-bit machine words (Figure 5(d)). The first run contains a fill of
length 0 and a tail. There is no fill word but only a literal word representing the 31
tail bits for this run. Since a literal word has 32 bits, we use the first bit to indicate
it is a literal word, and the rest to store the 31 tail bits. The second run contains a
fill of length 174 (and thus represents 174 groups of 31 bits each) plus a tail. This
run requires a fill word and a tail word. As illustrated, the first bit of a fill word
indicates that it is a fill word, the second bit stores the bit value of the fill, which is
0 in this example. The remaining 30 bits store the binary version of the fill length,
which is 10101110 (174) in this example.
Figure 5. An example of WAH encoding of a sequence of 5456 bits on a 32-bit
machine
.
Pages:
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331