Changeset 5529


Ignore:
Timestamp:
Jun 23, 2017, 2:54:01 PM (20 months ago)
Author:
cameron
Message:

Document and simplify the creation of E1 and M0 masks

File:
1 edited

Legend:

Unmodified
Added
Removed
  • proto/lz4d/lz4d_e_d.py

    r5520 r5529  
    5656Kernels
    5757'''
    58 # Extract the start and end marker bits streams of compressed and uncompressed block.
    59 # @param file_content
    60 # @return compressed_start_marker
    61 #         compressed_end_marker
    62 #         uncompressed_start_marker
    63 #         uncompressed_end_marker
    64 
    65 def extract_block_marker(file_content):
     58
     59def extract_blocks(file_content):
    6660    offset = 0
    67     compressed_start_marker = 0
    68     uncompressed_start_marker = 0
    69     endmark_bit_pos = 0
    70     compressed_end_marker = 0
    71     uncompressed_end_marker = 0
     61    block_data = []
     62    uncompressed_mask = 0
    7263
    7364    offset += 4  #Magicc Number
     
    10394        if realBlockSize == 0: #End Mark
    10495            break
    105         elif isCompressed:
    106             compressed_start_marker = compressed_start_marker | (1 << offset)
    107         else:
    108             uncompressed_start_marker = uncompressed_start_marker | (1 << offset)
     96
     97        block_start = offset
    10998
    11099        offset = offset + realBlockSize
    111100
    112         endmark_bit_pos != singleton(offset)
    113         if isCompressed:
    114             compressed_end_marker |= singleton(offset)
    115         else:
    116             uncompressed_end_marker |= singleton(offset)
     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)
    117106
    118107        if has_block_checksum:
     
    120109
    121110    # Ignore Content Check Sum
    122     return compressed_start_marker, compressed_end_marker, uncompressed_start_marker, uncompressed_end_marker
    123 
    124 
    125 
    126 def extract_e1_marker(file_content, basis_bits, compressed_start_marker, compressed_end_marker, extender):
     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):
    127180    # CC_0x0X = (~basis_bits.bit_0) & (~basis_bits.bit_1) & (~basis_bits.bit_2) & (~basis_bits.bit_3)
    128181
     
    130183    CC_0xXF = basis_bits.bit_4 & basis_bits.bit_5 & basis_bits.bit_6 & basis_bits.bit_7
    131184
    132     token_markers = 0
    133     offset_marker = 0
    134     literal_marker = 0
    135 
    136     e1_marker = 0
    137 
    138     while compressed_start_marker:
    139         token_marker = singletonStream(compressed_start_marker)  # May be handle in parallel if Position() support
    140         compressed_start_marker = compressed_start_marker - token_marker
    141 
    142         while token_marker:
    143             token_markers |= token_marker
    144             token_pos = position(token_marker)
    145 
    146             # print(token_pos)
    147             # print(ord(file_content[token_pos]))
    148 
    149             extended_literal = token_marker & CC_0xFX
    150             extended_match = token_marker & CC_0xXF
    151 
    152             literal_length_end = pablo.ScanThru(token_marker, extended_literal | extender)
    153 
    154             literal_length_end_pos = position(literal_length_end)
    155 
    156             literal_extension_size = literal_length_end_pos - token_pos
    157 
    158             length_base = ord(file_content[literal_length_end_pos])
    159 
    160             # Will be a Select Instruction
    161             if literal_extension_size == 0:
    162                 literal_length = length_base >> 4
    163             else:
    164                 literal_length = (literal_extension_size - 1) * 255 + 15 + length_base
    165 
    166             literal_marker_bit = literal_length_end
    167 
    168             literal_marker_bit = pablo.Advance(literal_marker_bit)
    169             literal_marker_end_bit = pablo.AdvancebyPos(literal_marker_bit, literal_length)
    170             # If literal_marker_bit and literal_marker_end_bit are the same, there will be no literal part in this sequence
    171             real_literal_marker_bit = literal_marker_bit & (~literal_marker_end_bit)  # handle no literal part
    172 
    173             literal_marker |= real_literal_marker_bit  # literal start bit
    174             literal_marker |= pablo.AdvancebyPos(real_literal_marker_bit, literal_length)  # literal end bit
    175 
    176             # handle e1 bits
    177             new_e1_bits = literal_marker_end_bit - literal_length_end
    178             e1_marker |= new_e1_bits
    179 
    180             offset_pos = literal_length_end_pos + literal_length + 1
    181             offset_marker |= (singleton(offset_pos) & ~compressed_end_marker)
    182 
    183             c = offset_pos - token_pos + 1
    184             match_length_start = pablo.AdvancebyPos(token_marker, c)  # second bit of offset
    185             match_length_start = match_length_start & ~(pablo.Advance(compressed_end_marker))  # clear bit before scanThru if reached block end
    186 
    187             match_length_extend_start = pablo.AdvancebyPos(extended_match, offset_pos - token_pos + 1)
    188             match_length_end = pablo.ScanThru(match_length_start, match_length_extend_start | extender)
    189 
    190             match_length_end = match_length_end & ~compressed_end_marker
    191             # print(compressed_end_marker)
    192             token_marker = pablo.Advance(match_length_end)
    193     return token_markers, offset_marker, literal_marker, e1_marker
    194 
    195 
    196 
    197 # TODO may need to use some other way
    198 def extract_m0_and_d(file_content, literal_marker, token_marker, offset_marker, uncompressed_marker, extender_bits):
    199     m0_marker = 0
    200     d_uncompressed_marker = 0
    201 
    202     cur_output_pos = 0
    203 
    204     while literal_marker or token_marker or offset_marker or uncompressed_marker:
    205         literal_one_pos = count_forward_zero(literal_marker)
    206         token_one_pos = count_forward_zero(token_marker)
    207         offset_one_pos = count_forward_zero(offset_marker)
    208         uncompressed_one_pos = count_forward_zero(uncompressed_marker)
    209         min_pos = min_position(literal_one_pos, token_one_pos, offset_one_pos, uncompressed_one_pos)
    210 
    211         if min_pos == literal_one_pos:
    212             literal_marker = bit_clear(literal_marker, literal_one_pos)
    213             secondLiteralOnePos = count_forward_zero(literal_marker)
    214             literal_marker = bit_clear(literal_marker, secondLiteralOnePos)
    215             cur_output_pos = cur_output_pos + secondLiteralOnePos - literal_one_pos
    216 
    217         elif min_pos == uncompressed_one_pos:
    218             uncompressed_marker = bit_clear(uncompressed_marker, uncompressed_one_pos)
    219             uncompressed_end_pos = count_forward_zero(uncompressed_marker)
    220             uncompressed_marker = bit_clear(uncompressed_marker, uncompressed_end_pos)
    221             new_output_pos = cur_output_pos + uncompressed_end_pos - uncompressed_one_pos
    222             d_uncompressed_marker |= (singleton(cur_output_pos) - singleton(new_output_pos))
    223             cur_output_pos = new_output_pos
    224 
    225         elif min_pos == token_one_pos:
    226             token_marker = bit_clear(token_marker, token_one_pos)
    227             tempTokenByte = ord(file_content[token_one_pos])
    228         elif min_pos == offset_one_pos:
    229             offset_marker = bit_clear(offset_marker, offset_one_pos)
    230 
    231             match_length_base = tempTokenByte & 0xf
    232 
    233             extended_length = extend_match_length(offset_one_pos + 2, extender_bits)
    234 
    235             # Will Be a Select Instruction
    236             if match_length_base < 0xf:
    237                 match_length = match_length_base
    238             else:
    239                 match_length = match_length_base + extended_length * 255 + ord(file_content[offset_one_pos + 2 + extended_length])
    240 
    241             match_length += 4
    242 
    243             m0_cur_end = cur_output_pos + match_length - 1
    244             m0_mask = singleton(m0_cur_end) - singleton(cur_output_pos)
    245             m0_marker |= m0_mask
    246 
    247             cur_output_pos += match_length
    248 
    249     # return cur_output_pos only in prototype in order to produce enough output string buffer
    250     #        it will be represent by the marker length of m0 or d_uncompressed markers
    251     return (m0_marker, d_uncompressed_marker, cur_output_pos)
    252 
    253 
    254 def deposit_compressed(file_content, compressed_start_marker, compressed_end_marker, e1_marker, m0_marker, e_uncompressed_marker, outputStrBuffer):
     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)
    255274
    256275    d_marker = (~(m0_marker | pablo.Advance(m0_marker))) & (~e_uncompressed_marker)
     
    314333        pass
    315334
    316 def deposit_uncompressed(file_content, e_uncompressed_marker, e_uncompressed_end_marker, d_uncompressed_marker, outputStrBuffer):
    317     output_pos = 0
    318     while e_uncompressed_marker:
    319         uncompressed_start_bit = singletonStream(e_uncompressed_marker)
    320         uncompressed_start_pos = position(uncompressed_start_bit)
    321         e_uncompressed_marker = e_uncompressed_marker - uncompressed_start_bit
    322 
    323         uncompressed_end_bit = singletonStream(e_uncompressed_end_marker)
    324         uncompressed_end_pos = position(uncompressed_end_bit)
    325         e_uncompressed_end_marker = e_uncompressed_end_marker - uncompressed_end_bit
    326 
    327         output_pos_marker = pablo.ScanTo(singleton(output_pos), d_uncompressed_marker)
    328         output_pos = position(output_pos_marker)
    329 
    330         copy_length = uncompressed_end_pos - uncompressed_start_pos
    331 
     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
    332338        outputStrBuffer[output_pos: output_pos + copy_length] = list(
    333339            file_content[uncompressed_start_pos: uncompressed_end_pos]
     
    356362
    357363        # Extract start and end marker of compressed and uncompressed blocks
    358         compressed_start_marker, compressed_end_marker, uncompressed_start_marker, uncompressed_end_marker = extract_block_marker(file_content)
    359         e_uncompressed_marker = uncompressed_end_marker - uncompressed_start_marker
     364        block_data, uncompressed_mask = extract_blocks(file_content)
     365        #print block_data
    360366
    361367        # Imitate ParabixCharacterClassKernelBuilder to produce extenders stream
    362368        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
    363369
    364         # Extract e1 marker (also extract token, offset and literal marker for extracting m0)
    365         token_marker, offset_marker, literal_marker, e1_marker = extract_e1_marker(file_content, basis_bits, compressed_start_marker, compressed_end_marker, extender_bits)
    366 
    367         # Extract m0 marker for compressed block, deposit (d) marker for uncompressed block
    368         uncompressed_marker = uncompressed_start_marker | uncompressed_end_marker
    369         m0_marker, d_uncompressed_marker, output_length = extract_m0_and_d(file_content, literal_marker, token_marker, offset_marker, uncompressed_marker, extender_bits)
     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)
    370372
    371373        # Use Array of char to imitate output string buffer of fixed length
     
    373375
    374376        # Deposit compressed and uncompressed blocks
    375         deposit_compressed(file_content, compressed_start_marker, compressed_end_marker, e1_marker, m0_marker, e_uncompressed_marker, outputStrBuffer)
    376         deposit_uncompressed(file_content, uncompressed_start_marker, uncompressed_end_marker, d_uncompressed_marker, outputStrBuffer)
     377       
     378        deposit_compressed(file_content, block_data, E1_marker, M0_marker, outputStrBuffer)
     379        deposit_uncompressed(file_content, uncompressed_data, outputStrBuffer)
    377380
    378381
     
    382385            f.write(outputStr)
    383386
    384 
    385 
    386 
Note: See TracChangeset for help on using the changeset viewer.