source: proto/lz4d/extract_e1_m0_kernel.py @ 5546

Last change on this file since 5546 was 5546, checked in by xwa163, 22 months ago

fix a typo in the prototype of extract_e1_m0_kernel

File size: 6.4 KB
Line 
1from sequential_pablo_kernel import SequentialPabloKernel
2import sequential_pablo
3
4#
5#  === The E1 and M0 Bitstreams for LZ4 Decoding ===
6#
7#  Suppose Z is a LZ4-compressed text stream and T is the equivalent uncompressed text.
8#
9#  First define the basic extract and deposit streams E and D.
10#
11#  The bit stream E is a bit stream of length |Z| such that E[i] = 1 iff Z[i] is a
12#  literal character to be copied directly to T.
13#
14#  The bit stream D is a bit stream of length |T| such that D[i] = 1 iff T[i] is a
15#  a character copied directly from Z[j], where Z[j] = 1, and popcnt(T[0..i-1]) = popcnt(Z[0..j-1])
16#
17#  So suppose we have a compressed stream Z with literal characters marked by E
18#
19#  Z    -ab---pqrstu------FGH---JK
20#  E    .11...111111......111...11
21#
22#  The uncompressed stream T and deposit stream D could look like:
23#
24#  T    ab------------pqrstu------------fgh----------jk
25#  D    11............111111............111..........11
26#
27#
28#  But during decoding, it is better to compute the bitstream E1, which
29#  is defined by E1[i] = E[i] | E[i+1].
30#
31#  E1 is the stream marking the byte prior to a literal plus the literal.  The
32#  byte prior to the literal is the token or the last length byte after length
33#  extenders.
34#
35#  Z    -ab---pqrstu------fgh---jk
36#  E1   111..1111111..1..1111..111
37#
38#  Given the E1 stream, the E stream can easily be computed as E = E1 & Advance(E1).
39#
40#  The advantage of the E1 stream is that we mark the position of every literal,
41#  even if it is of length 0.   This allows us to compute the bit stream marking
42#  all the offsets:
43#  Offset_stream = Advance(E1) &~ E1
44#
45#  In our example, we might have had a length 0 literal between the PQRSTU and the FGH
46#  literals
47#
48#  Z    -ab---pqrstu------fgh---jk
49#  E1   111..1111111..1..1111..111
50#
51#  Similarly, instead of directly storing the D stream, I think it is useful
52#  to store the M0 stream which consists of the output positions for all
53#  the nonfinal bytes of match copies.
54#
55#  T    ab------------pqrstu------------fgh----------jk
56#  M0   ..11111111111.......1111.111111....111111111...
57#
58#  The advantage of the M0 stream is that it lets us compute the length
59#  of match copies even if we have two consecutive copies in the output
60#  (because there was a 0-length literal).  The length is always one more
61#  than the length of the run of one bits plus 1.
62#
63#  We can also easily compute the D stream from the M0 stream
64#
65#  D = ~(M0 | Advance(M0))
66#  (Assuming that we are confined to the compressed stream region).
67
68class ExtractE1M0Kernel(SequentialPabloKernel):
69    def __init__(self, input_buffers):
70        SequentialPabloKernel.__init__(self, input_buffers, {
71            'e1_marker' : 0,
72            'm0_marker' : 0
73        })
74
75    def process(self):
76        self.init_buffer_cursor(['extender'])
77        file_content = self._input_buffers['file_content']
78        block_data = self._input_buffers['block_data']
79
80        uncompressed_data = []
81        output_pos = 0
82
83        for (isCompressed, block_start_pos, block_end_pos) in block_data:
84
85            if isCompressed:
86                self.advance_cursor_until_pos('extender', block_start_pos)
87                # token_pos = block_start_pos
88
89                while self.get_cursor_value('extender') < block_end_pos:
90                    token = ord(file_content[self.get_cursor_value('extender')])
91
92                    # print(token_pos)
93                    # print(ord(file_content[token_pos]))
94                    literal_length_base = token >> 4
95                    match_length_base = token & 0x0f
96
97                    extended_literal_value = token & 0xf0 == 0xf0
98
99                    token_pos = self.get_cursor_value('extender')
100
101                    self.modify_input_bitstream('extender', 'extender', extended_literal_value)
102                    self.advance_cursor_until_next_zero('extender', 'extender')
103
104                    literal_length_end_pos = self.get_cursor_value('extender')
105
106                    literal_extension_size = literal_length_end_pos - token_pos
107
108                    final_length_byte = ord(file_content[literal_length_end_pos])
109
110                    literal_length = literal_length_base
111
112                    # Will be a Select Instruction
113                    if literal_extension_size > 0:
114                        literal_length += (literal_extension_size - 1) * 255 + final_length_byte
115
116                    # handle e1 bits
117                    # Assume we have enough output buffer
118                    self.mark_output_bitstream_one('e1_marker', literal_length_end_pos, literal_length_end_pos + 1 + literal_length )
119
120                    output_pos += literal_length
121                    offset_pos = literal_length_end_pos + literal_length + 1
122
123                    # This branch will almost always be taken, there will just one misprediction penalty at the end.
124                    if offset_pos < block_end_pos:
125                        match_length_start_pos = offset_pos + 1
126                        self.advance_cursor_until_pos('extender', match_length_start_pos)
127                        extended_match_value = token & 0xf == 0xf
128
129                        self.modify_input_bitstream('extender', 'extender', extended_match_value)
130
131                        self.advance_cursor_until_next_zero('extender', 'extender')
132                        match_extension_size = self.get_cursor_value('extender') - match_length_start_pos
133
134                        match_length = match_length_base + 4
135
136                        # Will Be a Select Instruction
137                        if match_extension_size > 0:
138                            match_length += (match_extension_size - 1) * 255 + ord(
139                                file_content[offset_pos + 1 + match_extension_size])
140
141                        # Handle M0 Bits
142                        # Assume we have enough output buffer
143                        self.mark_output_bitstream_one('m0_marker', output_pos, output_pos + match_length - 1)
144                        output_pos += match_length
145
146                        self.advance_cursor('extender', 1)
147                    else:
148                        self.advance_cursor_until_pos('extender', offset_pos)
149            else:
150                block_length = block_end_pos - block_start_pos
151                uncompressed_data.append(block_start_pos, block_length, output_pos)
152                output_pos += block_length
153
154        return self._output_buffers['e1_marker'], self._output_buffers['m0_marker'], uncompressed_data, output_pos
Note: See TracBrowser for help on using the repository browser.