source: proto/lz4d/lz4d_e_d.py @ 5529

Last change on this file since 5529 was 5529, checked in by cameron, 20 months ago

Document and simplify the creation of E1 and M0 masks

File size: 13.4 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, block_end_pos) in block_data:
191
192        if isCompressed:
193            token_pos = block_start
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 * 255 + ord(file_content[offset_pos + 2 + 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            uncompressed_data.append(block_start, block_length, output_pos)
258            output_pos += block_end_pos - block_start_pos
259
260    return E1_marker, M0_marker, uncompressed_data, output_pos
261
262
263def deposit_compressed(file_content, block_data, e1_marker, m0_marker, outputStrBuffer):
264   
265    compressed_start_marker = 0
266    compressed_end_marker = 0
267    e_uncompressed_marker = 0
268   
269    for (isCompressed, block_start, block_end_pos) in block_data:
270        if isCompressed:
271            compressed_start_marker |= 1 << block_start
272            compressed_end_marker |= 1 << block_end_pos
273        else: e_uncompressed_marker |= (1 << block_end) - (1 << block_start)
274
275    d_marker = (~(m0_marker | pablo.Advance(m0_marker))) & (~e_uncompressed_marker)
276
277    output_pos = 0
278
279    # Outer loop will iterate throught all of the compressed block
280    while (compressed_start_marker):
281        output_pos_marker = pablo.ScanTo(singleton(output_pos), d_marker)
282        output_pos = position(output_pos_marker)
283
284        compressed_start_bit = singletonStream(compressed_start_marker)
285        token_mark = compressed_start_bit
286        compressed_start_marker = compressed_start_marker - compressed_start_bit
287
288        compressed_end_bit = singletonStream(compressed_end_marker)
289        compressed_end_marker = compressed_end_marker - compressed_end_bit
290        compressed_end_bit_pos = position(compressed_end_bit)
291
292        # token_pos = 1 << compressed_start_pos
293        # token_mark = singleton(token_pos)
294        last_match_len_marker = pablo.ScanTo(token_mark, e1_marker)  # first e1 bit
295        last_match_len_marker_pos = position(last_match_len_marker)
296        literal_end_mark = pablo.ScanThru(last_match_len_marker, e1_marker)
297        literal_end_pos = position(literal_end_mark)
298        literal_length = literal_end_pos - last_match_len_marker_pos - 1
299
300        # Output
301        outputStrBuffer[output_pos: output_pos + literal_length] = list(file_content[last_match_len_marker_pos + 1: last_match_len_marker_pos + 1 + literal_length])
302
303        output_pos += literal_length
304        while literal_end_pos < compressed_end_bit_pos:
305            offset_pos = literal_end_pos
306
307            match_offset = ord(file_content[offset_pos]) + (ord(file_content[offset_pos+ 1]) << 8)
308            match_copy_pos = output_pos - match_offset
309
310            output_mark = singleton(output_pos)
311            match_end_mark = pablo.ScanThru(output_mark, m0_marker)
312
313            match_length = position(match_end_mark) - output_pos + 1
314
315            # Match Copy
316            for i in range(match_length):
317                outputStrBuffer[output_pos + i] = outputStrBuffer[match_copy_pos + i]
318
319            output_pos += match_length
320
321            #  /* next token */
322            last_match_len_marker = pablo.ScanTo(literal_end_mark, e1_marker)
323            last_match_len_marker_pos = position(last_match_len_marker)
324            literal_end_mark = pablo.ScanThru(last_match_len_marker, e1_marker)
325            literal_end_pos = position(literal_end_mark)
326            literal_length = literal_end_pos - position(last_match_len_marker) - 1
327
328            # Literal Copy
329            outputStrBuffer[output_pos: output_pos + literal_length] = list(
330                file_content[last_match_len_marker_pos + 1: last_match_len_marker_pos + 1 + literal_length])
331
332            output_pos += literal_length
333        pass
334
335def deposit_uncompressed(file_content, uncompressed_block_data, outputStrBuffer):
336    for (uncompressed_start_pos, block_length, output_pos) in uncompressed_block_data:
337        uncompressed_end_pos = uncompressed_start_pos + block_length
338        outputStrBuffer[output_pos: output_pos + copy_length] = list(
339            file_content[uncompressed_start_pos: uncompressed_end_pos]
340        )
341        output_pos += copy_length
342
343'''
344Main
345'''
346
347if __name__ == '__main__':
348    if len(sys.argv) < 3:
349        print("""
350Usage:
351python lz4d_e_d.py [input_file_path] [output_file_path]
352        """)
353    else:
354        # Prepare Input
355        inputFile = sys.argv[1]
356        outputFile = sys.argv[2]
357        with open(inputFile, "rb") as f:
358            file_content = f.read()
359        basis_bits = Basis_bits()
360        pablo.EOF_mask = pablo.transpose_streams(file_content, basis_bits)
361
362
363        # Extract start and end marker of compressed and uncompressed blocks
364        block_data, uncompressed_mask = extract_blocks(file_content)
365        #print block_data
366
367        # Imitate ParabixCharacterClassKernelBuilder to produce extenders stream
368        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
369
370        # Extract E1  and M0 marker streams as wells as data for uncompressed blocks and total length
371        E1_marker, M0_marker, uncompressed_data, output_length = extract_E1_M0(file_content, basis_bits, block_data, extender_bits)
372
373        # Use Array of char to imitate output string buffer of fixed length
374        outputStrBuffer = ["" for i in range(output_length)]
375
376        # Deposit compressed and uncompressed blocks
377       
378        deposit_compressed(file_content, block_data, E1_marker, M0_marker, outputStrBuffer)
379        deposit_uncompressed(file_content, uncompressed_data, outputStrBuffer)
380
381
382        outputStr = ''.join(outputStrBuffer)
383
384        with open(outputFile, 'w') as f:
385            f.write(outputStr)
386
Note: See TracBrowser for help on using the repository browser.