source: proto/lz4d/lz4d_e_d.py @ 5530

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

fix some bugs and typos in lz4d_e_d prototype

File size: 12.9 KB
Line 
1
2import sys
3from Basis_Bits import Basis_bits
4import pablo
5
6'''
7Bitwise Operation
8'''
9def bit_test(bit, index):
10    return bit >> index & 1
11def bit_clear(bit, index):
12    mask = ~0 - (1 << index);
13    return bit & mask
14
15
16'''
17Methods that should be implemented in Pablo
18'''
19def position(bits) :
20    return len(bin(bits)) - 3
21    # can not use log2 since log2 will cause some inprecise results when the data is large
22    # return int(math.log(bits, 2))
23def singletonStream(bits):
24    return bits - ((bits - 1) & bits)
25def singleton(pos):
26    return 1 << pos
27
28# Advance by variable
29
30
31'''
32Methods that has already been supported
33'''
34def count_forward_zero(bits):
35    if bits == 0 :
36        return -1
37    return position(singletonStream(bits))
38
39def extend_match_length(fromIndex, extender_bits):
40    return count_forward_zero(~(extender_bits >> fromIndex))
41
42'''
43Helper Functions for extract_m0_and_d
44'''
45def min_position(a,b,c,d):
46    for i in [a,b,c,d]:
47        if i > 0:
48            temp = i
49            break
50    for i in [a,b,c,d]:
51        if i > 0 and i < temp:
52            temp = i
53    return temp
54
55'''
56Kernels
57'''
58
59def extract_blocks(file_content):
60    offset = 0
61    block_data = []
62    uncompressed_mask = 0
63
64    offset += 4  #Magicc Number
65
66    flag = ord(file_content[offset])
67
68    has_content_checksum = bit_test(flag, 2)
69    has_content_size = bit_test(flag, 3)
70    has_block_checksum = bit_test(flag, 4)
71
72    frame_descriptor_size = 3
73    if has_content_size:
74        frame_descriptor_size = 11
75    offset += frame_descriptor_size
76
77    # Process Data Block
78    while True:
79        blockSize = 0
80        for i in range(4):
81            blockSize += (ord(file_content[offset + i]) << (i * 8))
82            pass
83
84        if blockSize == 0:
85            # End Mark
86            break
87
88        highestIndex = 4 * 8 - 1
89        isCompressed = not bit_test(blockSize, highestIndex)
90        realBlockSize = bit_clear(blockSize, highestIndex)
91
92        offset = offset + 4
93
94        if realBlockSize == 0: #End Mark
95            break
96
97        block_start = offset
98
99        offset = offset + realBlockSize
100
101        block_end = offset
102
103        block_data.append((isCompressed, block_start, block_end))
104       
105        if not isCompressed: uncompressed_mask |= (1 << block_end) - (1 << block_start)
106
107        if has_block_checksum:
108            offset = offset + 4
109
110    # Ignore Content Check Sum
111    return block_data, uncompressed_mask
112
113#
114#  === The E1 and M0 Bitstreams for LZ4 Decoding ===
115#
116#  Suppose Z is a LZ4-compressed text stream and T is the equivalent uncompressed text.
117#
118#  First define the basic extract and deposit streams E and D.
119#
120#  The bit stream E is a bit stream of length |Z| such that E[i] = 1 iff Z[i] is a
121#  literal character to be copied directly to T.
122#
123#  The bit stream D is a bit stream of length |T| such that D[i] = 1 iff T[i] is a
124#  a character copied directly from Z[j], where Z[j] = 1, and popcnt(T[0..i-1]) = popcnt(Z[0..j-1])
125#
126#  So suppose we have a compressed stream Z with literal characters marked by E
127#
128#  Z    -ab---pqrstu------FGH---JK
129#  E    .11...111111......111...11
130#
131#  The uncompressed stream T and deposit stream D could look like:
132#
133#  T    ab------------pqrstu------------fgh----------jk
134#  D    11............111111............111..........11
135#
136#
137#  But during decoding, it is better to compute the bitstream E1, which
138#  is defined by E1[i] = E[i] | E[i+1].
139#
140#  E1 is the stream marking the byte prior to a literal plus the literal.  The
141#  byte prior to the literal is the token or the last length byte after length
142#  extenders.
143#
144#  Z    -ab---pqrstu------fgh---jk
145#  E1   111..1111111..1..1111..111
146#
147#  Given the E1 stream, the E stream can easily be computed as E = E1 & Advance(E1).
148#
149#  The advantage of the E1 stream is that we mark the position of every literal,
150#  even if it is of length 0.   This allows us to compute the bit stream marking
151#  all the offsets:
152#  Offset_stream = Advance(E1) &~ E1
153#
154#  In our example, we might have had a length 0 literal between the PQRSTU and the FGH
155#  literals
156#
157#  Z    -ab---pqrstu------fgh---jk
158#  E1   111..1111111..1..1111..111
159#
160#  Similarly, instead of directly storing the D stream, I think it is useful
161#  to store the M0 stream which consists of the output positions for all
162#  the nonfinal bytes of match copies. 
163#
164#  T    ab------------pqrstu------------fgh----------jk
165#  M0   ..11111111111.......1111.111111....111111111...
166#
167#  The advantage of the M0 stream is that it lets us compute the length
168#  of match copies even if we have two consecutive copies in the output
169#  (because there was a 0-length literal).  The length is always one more
170#  than the length of the run of one bits plus 1.
171#
172#  We can also easily compute the D stream from the M0 stream
173#
174#  D = ~(M0 | Advance(M0))
175#  (Assuming that we are confined to the compressed stream region).
176
177
178
179def extract_E1_M0(file_content, basis_bits, block_data, extender):
180    # CC_0x0X = (~basis_bits.bit_0) & (~basis_bits.bit_1) & (~basis_bits.bit_2) & (~basis_bits.bit_3)
181
182    CC_0xFX = basis_bits.bit_0 & basis_bits.bit_1 & basis_bits.bit_2 & basis_bits.bit_3
183    CC_0xXF = basis_bits.bit_4 & basis_bits.bit_5 & basis_bits.bit_6 & basis_bits.bit_7
184
185    E1_marker = 0
186    M0_marker = 0
187    uncompressed_data = []
188    output_pos = 0
189
190    for (isCompressed, block_start_pos, block_end_pos) in block_data:
191
192        if isCompressed:
193            token_pos = block_start_pos
194
195            while token_pos < block_end_pos:
196                token_marker = 1 << token_pos
197
198                token = ord(file_content[token_pos])
199                #print(token_pos)
200                # print(ord(file_content[token_pos]))
201                literal_length_base = token >> 4
202                match_length_base = token & 0x0f
203
204                extended_literal = token_marker & CC_0xFX
205                extended_match = token_marker & CC_0xXF
206
207                literal_length_end = pablo.ScanThru(token_marker, extended_literal | extender)
208
209                literal_length_end_pos = position(literal_length_end)
210
211                literal_extension_size = literal_length_end_pos - token_pos
212               
213                final_length_byte = ord(file_content[literal_length_end_pos])
214
215                literal_length = literal_length_base
216               
217                # Will be a Select Instruction
218                if literal_extension_size > 0:
219                    literal_length += (literal_extension_size - 1) * 255 + final_length_byte
220
221                literal_marker_bit = pablo.Advance(literal_length_end)
222                literal_marker_end_bit = pablo.AdvancebyPos(literal_marker_bit, literal_length)
223
224                # handle e1 bits
225                new_e1_bits = literal_marker_end_bit - literal_length_end
226                E1_marker |= new_e1_bits
227               
228                output_pos += literal_length
229
230                offset_pos = literal_length_end_pos + literal_length + 1
231
232                # This branch will almost always be taken, there will just one misprediction penalty at the end.
233                if offset_pos < block_end_pos: 
234                    c = offset_pos - token_pos + 1
235
236                    match_length_start = pablo.AdvancebyPos(token_marker, c)  # second bit of offset
237                    match_length_extend_start = pablo.AdvancebyPos(extended_match, c)
238                    match_length_end = pablo.ScanThru(match_length_start, match_length_extend_start | extender)
239                    match_extension_size = position(match_length_end) - position(match_length_start)
240
241                    match_length = match_length_base + 4
242
243                    # Will Be a Select Instruction
244                    if match_extension_size > 0:
245                        match_length += (match_extension_size - 1) * 255 + ord(file_content[offset_pos + 1 + match_extension_size])
246
247                    new_M0_bits = ((1 << (match_length - 1)) - 1) << output_pos
248                    output_pos += match_length
249                   
250                    M0_marker |= new_M0_bits
251                   
252                    #token_marker = pablo.Advance(match_length_end)
253                    token_pos = offset_pos + match_extension_size + 2
254                else:
255                    token_pos = offset_pos
256        else:
257            block_length = block_end_pos - block_start_pos
258            uncompressed_data.append(block_start_pos, block_length, output_pos)
259            output_pos += block_length
260
261    return E1_marker, M0_marker, uncompressed_data, output_pos
262
263
264def deposit_compressed(file_content, block_data, e1_marker, m0_marker, outputStrBuffer):
265   
266    d_marker = ~(m0_marker | pablo.Advance(m0_marker))
267    output_pos = 0
268
269    # Outer loop will iterate throught all of the compressed block
270    # while (compressed_start_marker):
271    for (isCompressed, block_start_pos, block_end_pos) in block_data:
272        if not isCompressed:
273            # There will be much fewer uncompressed block than compressed block
274            output_pos = output_pos + block_end_pos - block_start_pos
275            continue
276
277        output_pos_marker = pablo.ScanTo(singleton(output_pos), d_marker)
278        output_pos = position(output_pos_marker)
279
280        compressed_start_bit = singleton(block_start_pos)
281        token_mark = compressed_start_bit
282
283        last_match_len_marker = pablo.ScanTo(token_mark, e1_marker)  # first e1 bit
284        last_match_len_marker_pos = position(last_match_len_marker)
285        literal_end_mark = pablo.ScanThru(last_match_len_marker, e1_marker)
286        literal_end_pos = position(literal_end_mark)
287        literal_length = literal_end_pos - last_match_len_marker_pos - 1
288
289        # Output
290        outputStrBuffer[output_pos: output_pos + literal_length] = list(file_content[last_match_len_marker_pos + 1: last_match_len_marker_pos + 1 + literal_length])
291
292        output_pos += literal_length
293        while literal_end_pos < block_end_pos:
294            offset_pos = literal_end_pos
295
296            match_offset = ord(file_content[offset_pos]) + (ord(file_content[offset_pos+ 1]) << 8)
297            match_copy_pos = output_pos - match_offset
298
299            output_mark = singleton(output_pos)
300            match_end_mark = pablo.ScanThru(output_mark, m0_marker)
301
302            match_length = position(match_end_mark) - output_pos + 1
303
304            # Match Copy
305            for i in range(match_length):
306                outputStrBuffer[output_pos + i] = outputStrBuffer[match_copy_pos + i]
307
308            output_pos += match_length
309
310            #  /* next token */
311            last_match_len_marker = pablo.ScanTo(literal_end_mark, e1_marker)
312            last_match_len_marker_pos = position(last_match_len_marker)
313            literal_end_mark = pablo.ScanThru(last_match_len_marker, e1_marker)
314            literal_end_pos = position(literal_end_mark)
315            literal_length = literal_end_pos - position(last_match_len_marker) - 1
316
317            # Literal Copy
318            outputStrBuffer[output_pos: output_pos + literal_length] = list(
319                file_content[last_match_len_marker_pos + 1: last_match_len_marker_pos + 1 + literal_length])
320
321            output_pos += literal_length
322
323def deposit_uncompressed(file_content, uncompressed_block_data, outputStrBuffer):
324    for (uncompressed_start_pos, block_length, output_pos) in uncompressed_block_data:
325        uncompressed_end_pos = uncompressed_start_pos + block_length
326        outputStrBuffer[output_pos: output_pos + block_length] = list(
327            file_content[uncompressed_start_pos: uncompressed_end_pos]
328        )
329
330'''
331Main
332'''
333
334if __name__ == '__main__':
335    if len(sys.argv) < 3:
336        print("""
337Usage:
338python lz4d_e_d.py [input_file_path] [output_file_path]
339        """)
340    else:
341        # Prepare Input
342        inputFile = sys.argv[1]
343        outputFile = sys.argv[2]
344        with open(inputFile, "rb") as f:
345            file_content = f.read()
346        basis_bits = Basis_bits()
347        pablo.EOF_mask = pablo.transpose_streams(file_content, basis_bits)
348
349
350        # Extract start and end marker of compressed and uncompressed blocks
351        block_data, uncompressed_mask = extract_blocks(file_content)
352        #print block_data
353
354        # Imitate ParabixCharacterClassKernelBuilder to produce extenders stream
355        extender_bits = basis_bits.bit_0 & basis_bits.bit_1 & basis_bits.bit_2 & basis_bits.bit_3 & basis_bits.bit_4 & basis_bits.bit_5 & basis_bits.bit_6 & basis_bits.bit_7
356
357        # Extract E1  and M0 marker streams as wells as data for uncompressed blocks and total length
358        E1_marker, M0_marker, uncompressed_data, output_length = extract_E1_M0(file_content, basis_bits, block_data, extender_bits)
359
360        # Use Array of char to imitate output string buffer of fixed length
361        outputStrBuffer = ["" for i in range(output_length)]
362
363        # Deposit compressed and uncompressed blocks
364        deposit_compressed(file_content, block_data, E1_marker, M0_marker, outputStrBuffer)
365        deposit_uncompressed(file_content, uncompressed_data, outputStrBuffer)
366
367        outputStr = ''.join(outputStrBuffer)
368        # print(outputStr)
369        with open(outputFile, 'w') as f:
370            f.write(outputStr)
371
Note: See TracBrowser for help on using the repository browser.