lz4sconvert.go

Documentation: github.com/klauspost/compress/s2

     1  // Copyright (c) 2022 Klaus Post. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package s2
     6  
     7  import (
     8  	"encoding/binary"
     9  	"fmt"
    10  )
    11  
    12  // LZ4sConverter provides conversion from LZ4s.
    13  // (Intel modified LZ4 Blocks)
    14  // https://cdrdv2-public.intel.com/743912/743912-qat-programmers-guide-v2.0.pdf
    15  // LZ4s is a variant of LZ4 block format. LZ4s should be considered as an intermediate compressed block format.
    16  // The LZ4s format is selected when the application sets the compType to CPA_DC_LZ4S in CpaDcSessionSetupData.
    17  // The LZ4s block returned by the Intel® QAT hardware can be used by an external
    18  // software post-processing to generate other compressed data formats.
    19  // The following table lists the differences between LZ4 and LZ4s block format. LZ4s block format uses
    20  // the same high-level formatting as LZ4 block format with the following encoding changes:
    21  // For Min Match of 4 bytes, Copy length value 1-15 means length 4-18 with 18 bytes adding an extra byte.
    22  // ONLY "Min match of 4 bytes" is supported.
    23  type LZ4sConverter struct {
    24  }
    25  
    26  // ConvertBlock will convert an LZ4s block and append it as an S2
    27  // block without block length to dst.
    28  // The uncompressed size is returned as well.
    29  // dst must have capacity to contain the entire compressed block.
    30  func (l *LZ4sConverter) ConvertBlock(dst, src []byte) ([]byte, int, error) {
    31  	if len(src) == 0 {
    32  		return dst, 0, nil
    33  	}
    34  	const debug = false
    35  	const inline = true
    36  	const lz4MinMatch = 3
    37  
    38  	s, d := 0, len(dst)
    39  	dst = dst[:cap(dst)]
    40  	if !debug && hasAmd64Asm {
    41  		res, sz := cvtLZ4sBlockAsm(dst[d:], src)
    42  		if res < 0 {
    43  			const (
    44  				errCorrupt     = -1
    45  				errDstTooSmall = -2
    46  			)
    47  			switch res {
    48  			case errCorrupt:
    49  				return nil, 0, ErrCorrupt
    50  			case errDstTooSmall:
    51  				return nil, 0, ErrDstTooSmall
    52  			default:
    53  				return nil, 0, fmt.Errorf("unexpected result: %d", res)
    54  			}
    55  		}
    56  		if d+sz > len(dst) {
    57  			return nil, 0, ErrDstTooSmall
    58  		}
    59  		return dst[:d+sz], res, nil
    60  	}
    61  
    62  	dLimit := len(dst) - 10
    63  	var lastOffset uint16
    64  	var uncompressed int
    65  	if debug {
    66  		fmt.Printf("convert block start: len(src): %d, len(dst):%d \n", len(src), len(dst))
    67  	}
    68  
    69  	for {
    70  		if s >= len(src) {
    71  			return dst[:d], 0, ErrCorrupt
    72  		}
    73  		// Read literal info
    74  		token := src[s]
    75  		ll := int(token >> 4)
    76  		ml := int(lz4MinMatch + (token & 0xf))
    77  
    78  		// If upper nibble is 15, literal length is extended
    79  		if token >= 0xf0 {
    80  			for {
    81  				s++
    82  				if s >= len(src) {
    83  					if debug {
    84  						fmt.Printf("error reading ll: s (%d) >= len(src) (%d)\n", s, len(src))
    85  					}
    86  					return dst[:d], 0, ErrCorrupt
    87  				}
    88  				val := src[s]
    89  				ll += int(val)
    90  				if val != 255 {
    91  					break
    92  				}
    93  			}
    94  		}
    95  		// Skip past token
    96  		if s+ll >= len(src) {
    97  			if debug {
    98  				fmt.Printf("error literals: s+ll (%d+%d) >= len(src) (%d)\n", s, ll, len(src))
    99  			}
   100  			return nil, 0, ErrCorrupt
   101  		}
   102  		s++
   103  		if ll > 0 {
   104  			if d+ll > dLimit {
   105  				return nil, 0, ErrDstTooSmall
   106  			}
   107  			if debug {
   108  				fmt.Printf("emit %d literals\n", ll)
   109  			}
   110  			d += emitLiteralGo(dst[d:], src[s:s+ll])
   111  			s += ll
   112  			uncompressed += ll
   113  		}
   114  
   115  		// Check if we are done...
   116  		if ml == lz4MinMatch {
   117  			if s == len(src) {
   118  				break
   119  			}
   120  			// 0 bytes.
   121  			continue
   122  		}
   123  		// 2 byte offset
   124  		if s >= len(src)-2 {
   125  			if debug {
   126  				fmt.Printf("s (%d) >= len(src)-2 (%d)", s, len(src)-2)
   127  			}
   128  			return nil, 0, ErrCorrupt
   129  		}
   130  		offset := binary.LittleEndian.Uint16(src[s:])
   131  		s += 2
   132  		if offset == 0 {
   133  			if debug {
   134  				fmt.Printf("error: offset 0, ml: %d, len(src)-s: %d\n", ml, len(src)-s)
   135  			}
   136  			return nil, 0, ErrCorrupt
   137  		}
   138  		if int(offset) > uncompressed {
   139  			if debug {
   140  				fmt.Printf("error: offset (%d)> uncompressed (%d)\n", offset, uncompressed)
   141  			}
   142  			return nil, 0, ErrCorrupt
   143  		}
   144  
   145  		if ml == lz4MinMatch+15 {
   146  			for {
   147  				if s >= len(src) {
   148  					if debug {
   149  						fmt.Printf("error reading ml: s (%d) >= len(src) (%d)\n", s, len(src))
   150  					}
   151  					return nil, 0, ErrCorrupt
   152  				}
   153  				val := src[s]
   154  				s++
   155  				ml += int(val)
   156  				if val != 255 {
   157  					if s >= len(src) {
   158  						if debug {
   159  							fmt.Printf("error reading ml: s (%d) >= len(src) (%d)\n", s, len(src))
   160  						}
   161  						return nil, 0, ErrCorrupt
   162  					}
   163  					break
   164  				}
   165  			}
   166  		}
   167  		if offset == lastOffset {
   168  			if debug {
   169  				fmt.Printf("emit repeat, length: %d, offset: %d\n", ml, offset)
   170  			}
   171  			if !inline {
   172  				d += emitRepeat16(dst[d:], offset, ml)
   173  			} else {
   174  				length := ml
   175  				dst := dst[d:]
   176  				for len(dst) > 5 {
   177  					// Repeat offset, make length cheaper
   178  					length -= 4
   179  					if length <= 4 {
   180  						dst[0] = uint8(length)<<2 | tagCopy1
   181  						dst[1] = 0
   182  						d += 2
   183  						break
   184  					}
   185  					if length < 8 && offset < 2048 {
   186  						// Encode WITH offset
   187  						dst[1] = uint8(offset)
   188  						dst[0] = uint8(offset>>8)<<5 | uint8(length)<<2 | tagCopy1
   189  						d += 2
   190  						break
   191  					}
   192  					if length < (1<<8)+4 {
   193  						length -= 4
   194  						dst[2] = uint8(length)
   195  						dst[1] = 0
   196  						dst[0] = 5<<2 | tagCopy1
   197  						d += 3
   198  						break
   199  					}
   200  					if length < (1<<16)+(1<<8) {
   201  						length -= 1 << 8
   202  						dst[3] = uint8(length >> 8)
   203  						dst[2] = uint8(length >> 0)
   204  						dst[1] = 0
   205  						dst[0] = 6<<2 | tagCopy1
   206  						d += 4
   207  						break
   208  					}
   209  					const maxRepeat = (1 << 24) - 1
   210  					length -= 1 << 16
   211  					left := 0
   212  					if length > maxRepeat {
   213  						left = length - maxRepeat + 4
   214  						length = maxRepeat - 4
   215  					}
   216  					dst[4] = uint8(length >> 16)
   217  					dst[3] = uint8(length >> 8)
   218  					dst[2] = uint8(length >> 0)
   219  					dst[1] = 0
   220  					dst[0] = 7<<2 | tagCopy1
   221  					if left > 0 {
   222  						d += 5 + emitRepeat16(dst[5:], offset, left)
   223  						break
   224  					}
   225  					d += 5
   226  					break
   227  				}
   228  			}
   229  		} else {
   230  			if debug {
   231  				fmt.Printf("emit copy, length: %d, offset: %d\n", ml, offset)
   232  			}
   233  			if !inline {
   234  				d += emitCopy16(dst[d:], offset, ml)
   235  			} else {
   236  				length := ml
   237  				dst := dst[d:]
   238  				for len(dst) > 5 {
   239  					// Offset no more than 2 bytes.
   240  					if length > 64 {
   241  						off := 3
   242  						if offset < 2048 {
   243  							// emit 8 bytes as tagCopy1, rest as repeats.
   244  							dst[1] = uint8(offset)
   245  							dst[0] = uint8(offset>>8)<<5 | uint8(8-4)<<2 | tagCopy1
   246  							length -= 8
   247  							off = 2
   248  						} else {
   249  							// Emit a length 60 copy, encoded as 3 bytes.
   250  							// Emit remaining as repeat value (minimum 4 bytes).
   251  							dst[2] = uint8(offset >> 8)
   252  							dst[1] = uint8(offset)
   253  							dst[0] = 59<<2 | tagCopy2
   254  							length -= 60
   255  						}
   256  						// Emit remaining as repeats, at least 4 bytes remain.
   257  						d += off + emitRepeat16(dst[off:], offset, length)
   258  						break
   259  					}
   260  					if length >= 12 || offset >= 2048 {
   261  						// Emit the remaining copy, encoded as 3 bytes.
   262  						dst[2] = uint8(offset >> 8)
   263  						dst[1] = uint8(offset)
   264  						dst[0] = uint8(length-1)<<2 | tagCopy2
   265  						d += 3
   266  						break
   267  					}
   268  					// Emit the remaining copy, encoded as 2 bytes.
   269  					dst[1] = uint8(offset)
   270  					dst[0] = uint8(offset>>8)<<5 | uint8(length-4)<<2 | tagCopy1
   271  					d += 2
   272  					break
   273  				}
   274  			}
   275  			lastOffset = offset
   276  		}
   277  		uncompressed += ml
   278  		if d > dLimit {
   279  			return nil, 0, ErrDstTooSmall
   280  		}
   281  	}
   282  
   283  	return dst[:d], uncompressed, nil
   284  }
   285  
   286  // ConvertBlockSnappy will convert an LZ4s block and append it
   287  // as a Snappy block without block length to dst.
   288  // The uncompressed size is returned as well.
   289  // dst must have capacity to contain the entire compressed block.
   290  func (l *LZ4sConverter) ConvertBlockSnappy(dst, src []byte) ([]byte, int, error) {
   291  	if len(src) == 0 {
   292  		return dst, 0, nil
   293  	}
   294  	const debug = false
   295  	const lz4MinMatch = 3
   296  
   297  	s, d := 0, len(dst)
   298  	dst = dst[:cap(dst)]
   299  	// Use assembly when possible
   300  	if !debug && hasAmd64Asm {
   301  		res, sz := cvtLZ4sBlockSnappyAsm(dst[d:], src)
   302  		if res < 0 {
   303  			const (
   304  				errCorrupt     = -1
   305  				errDstTooSmall = -2
   306  			)
   307  			switch res {
   308  			case errCorrupt:
   309  				return nil, 0, ErrCorrupt
   310  			case errDstTooSmall:
   311  				return nil, 0, ErrDstTooSmall
   312  			default:
   313  				return nil, 0, fmt.Errorf("unexpected result: %d", res)
   314  			}
   315  		}
   316  		if d+sz > len(dst) {
   317  			return nil, 0, ErrDstTooSmall
   318  		}
   319  		return dst[:d+sz], res, nil
   320  	}
   321  
   322  	dLimit := len(dst) - 10
   323  	var uncompressed int
   324  	if debug {
   325  		fmt.Printf("convert block start: len(src): %d, len(dst):%d \n", len(src), len(dst))
   326  	}
   327  
   328  	for {
   329  		if s >= len(src) {
   330  			return nil, 0, ErrCorrupt
   331  		}
   332  		// Read literal info
   333  		token := src[s]
   334  		ll := int(token >> 4)
   335  		ml := int(lz4MinMatch + (token & 0xf))
   336  
   337  		// If upper nibble is 15, literal length is extended
   338  		if token >= 0xf0 {
   339  			for {
   340  				s++
   341  				if s >= len(src) {
   342  					if debug {
   343  						fmt.Printf("error reading ll: s (%d) >= len(src) (%d)\n", s, len(src))
   344  					}
   345  					return nil, 0, ErrCorrupt
   346  				}
   347  				val := src[s]
   348  				ll += int(val)
   349  				if val != 255 {
   350  					break
   351  				}
   352  			}
   353  		}
   354  		// Skip past token
   355  		if s+ll >= len(src) {
   356  			if debug {
   357  				fmt.Printf("error literals: s+ll (%d+%d) >= len(src) (%d)\n", s, ll, len(src))
   358  			}
   359  			return nil, 0, ErrCorrupt
   360  		}
   361  		s++
   362  		if ll > 0 {
   363  			if d+ll > dLimit {
   364  				return nil, 0, ErrDstTooSmall
   365  			}
   366  			if debug {
   367  				fmt.Printf("emit %d literals\n", ll)
   368  			}
   369  			d += emitLiteralGo(dst[d:], src[s:s+ll])
   370  			s += ll
   371  			uncompressed += ll
   372  		}
   373  
   374  		// Check if we are done...
   375  		if ml == lz4MinMatch {
   376  			if s == len(src) {
   377  				break
   378  			}
   379  			// 0 bytes.
   380  			continue
   381  		}
   382  		// 2 byte offset
   383  		if s >= len(src)-2 {
   384  			if debug {
   385  				fmt.Printf("s (%d) >= len(src)-2 (%d)", s, len(src)-2)
   386  			}
   387  			return nil, 0, ErrCorrupt
   388  		}
   389  		offset := binary.LittleEndian.Uint16(src[s:])
   390  		s += 2
   391  		if offset == 0 {
   392  			if debug {
   393  				fmt.Printf("error: offset 0, ml: %d, len(src)-s: %d\n", ml, len(src)-s)
   394  			}
   395  			return nil, 0, ErrCorrupt
   396  		}
   397  		if int(offset) > uncompressed {
   398  			if debug {
   399  				fmt.Printf("error: offset (%d)> uncompressed (%d)\n", offset, uncompressed)
   400  			}
   401  			return nil, 0, ErrCorrupt
   402  		}
   403  
   404  		if ml == lz4MinMatch+15 {
   405  			for {
   406  				if s >= len(src) {
   407  					if debug {
   408  						fmt.Printf("error reading ml: s (%d) >= len(src) (%d)\n", s, len(src))
   409  					}
   410  					return nil, 0, ErrCorrupt
   411  				}
   412  				val := src[s]
   413  				s++
   414  				ml += int(val)
   415  				if val != 255 {
   416  					if s >= len(src) {
   417  						if debug {
   418  							fmt.Printf("error reading ml: s (%d) >= len(src) (%d)\n", s, len(src))
   419  						}
   420  						return nil, 0, ErrCorrupt
   421  					}
   422  					break
   423  				}
   424  			}
   425  		}
   426  		if debug {
   427  			fmt.Printf("emit copy, length: %d, offset: %d\n", ml, offset)
   428  		}
   429  		length := ml
   430  		// d += emitCopyNoRepeat(dst[d:], int(offset), ml)
   431  		for length > 0 {
   432  			if d >= dLimit {
   433  				return nil, 0, ErrDstTooSmall
   434  			}
   435  
   436  			// Offset no more than 2 bytes.
   437  			if length > 64 {
   438  				// Emit a length 64 copy, encoded as 3 bytes.
   439  				dst[d+2] = uint8(offset >> 8)
   440  				dst[d+1] = uint8(offset)
   441  				dst[d+0] = 63<<2 | tagCopy2
   442  				length -= 64
   443  				d += 3
   444  				continue
   445  			}
   446  			if length >= 12 || offset >= 2048 || length < 4 {
   447  				// Emit the remaining copy, encoded as 3 bytes.
   448  				dst[d+2] = uint8(offset >> 8)
   449  				dst[d+1] = uint8(offset)
   450  				dst[d+0] = uint8(length-1)<<2 | tagCopy2
   451  				d += 3
   452  				break
   453  			}
   454  			// Emit the remaining copy, encoded as 2 bytes.
   455  			dst[d+1] = uint8(offset)
   456  			dst[d+0] = uint8(offset>>8)<<5 | uint8(length-4)<<2 | tagCopy1
   457  			d += 2
   458  			break
   459  		}
   460  		uncompressed += ml
   461  		if d > dLimit {
   462  			return nil, 0, ErrDstTooSmall
   463  		}
   464  	}
   465  
   466  	return dst[:d], uncompressed, nil
   467  }
   468
View as plain text