decompress_generic.go

Documentation: github.com/klauspost/compress/huff0

     1  //go:build !amd64 || appengine || !gc || noasm
     2  // +build !amd64 appengine !gc noasm
     3  
     4  // This file contains a generic implementation of Decoder.Decompress4X.
     5  package huff0
     6  
     7  import (
     8  	"errors"
     9  	"fmt"
    10  )
    11  
    12  // Decompress4X will decompress a 4X encoded stream.
    13  // The length of the supplied input must match the end of a block exactly.
    14  // The *capacity* of the dst slice must match the destination size of
    15  // the uncompressed data exactly.
    16  func (d *Decoder) Decompress4X(dst, src []byte) ([]byte, error) {
    17  	if len(d.dt.single) == 0 {
    18  		return nil, errors.New("no table loaded")
    19  	}
    20  	if len(src) < 6+(4*1) {
    21  		return nil, errors.New("input too small")
    22  	}
    23  	if use8BitTables && d.actualTableLog <= 8 {
    24  		return d.decompress4X8bit(dst, src)
    25  	}
    26  
    27  	var br [4]bitReaderShifted
    28  	// Decode "jump table"
    29  	start := 6
    30  	for i := 0; i < 3; i++ {
    31  		length := int(src[i*2]) | (int(src[i*2+1]) << 8)
    32  		if start+length >= len(src) {
    33  			return nil, errors.New("truncated input (or invalid offset)")
    34  		}
    35  		err := br[i].init(src[start : start+length])
    36  		if err != nil {
    37  			return nil, err
    38  		}
    39  		start += length
    40  	}
    41  	err := br[3].init(src[start:])
    42  	if err != nil {
    43  		return nil, err
    44  	}
    45  
    46  	// destination, offset to match first output
    47  	dstSize := cap(dst)
    48  	dst = dst[:dstSize]
    49  	out := dst
    50  	dstEvery := (dstSize + 3) / 4
    51  
    52  	const tlSize = 1 << tableLogMax
    53  	const tlMask = tlSize - 1
    54  	single := d.dt.single[:tlSize]
    55  
    56  	// Use temp table to avoid bound checks/append penalty.
    57  	buf := d.buffer()
    58  	var off uint8
    59  	var decoded int
    60  
    61  	// Decode 2 values from each decoder/loop.
    62  	const bufoff = 256
    63  	for {
    64  		if br[0].off < 4 || br[1].off < 4 || br[2].off < 4 || br[3].off < 4 {
    65  			break
    66  		}
    67  
    68  		{
    69  			const stream = 0
    70  			const stream2 = 1
    71  			br[stream].fillFast()
    72  			br[stream2].fillFast()
    73  
    74  			val := br[stream].peekBitsFast(d.actualTableLog)
    75  			val2 := br[stream2].peekBitsFast(d.actualTableLog)
    76  			v := single[val&tlMask]
    77  			v2 := single[val2&tlMask]
    78  			br[stream].advance(uint8(v.entry))
    79  			br[stream2].advance(uint8(v2.entry))
    80  			buf[stream][off] = uint8(v.entry >> 8)
    81  			buf[stream2][off] = uint8(v2.entry >> 8)
    82  
    83  			val = br[stream].peekBitsFast(d.actualTableLog)
    84  			val2 = br[stream2].peekBitsFast(d.actualTableLog)
    85  			v = single[val&tlMask]
    86  			v2 = single[val2&tlMask]
    87  			br[stream].advance(uint8(v.entry))
    88  			br[stream2].advance(uint8(v2.entry))
    89  			buf[stream][off+1] = uint8(v.entry >> 8)
    90  			buf[stream2][off+1] = uint8(v2.entry >> 8)
    91  		}
    92  
    93  		{
    94  			const stream = 2
    95  			const stream2 = 3
    96  			br[stream].fillFast()
    97  			br[stream2].fillFast()
    98  
    99  			val := br[stream].peekBitsFast(d.actualTableLog)
   100  			val2 := br[stream2].peekBitsFast(d.actualTableLog)
   101  			v := single[val&tlMask]
   102  			v2 := single[val2&tlMask]
   103  			br[stream].advance(uint8(v.entry))
   104  			br[stream2].advance(uint8(v2.entry))
   105  			buf[stream][off] = uint8(v.entry >> 8)
   106  			buf[stream2][off] = uint8(v2.entry >> 8)
   107  
   108  			val = br[stream].peekBitsFast(d.actualTableLog)
   109  			val2 = br[stream2].peekBitsFast(d.actualTableLog)
   110  			v = single[val&tlMask]
   111  			v2 = single[val2&tlMask]
   112  			br[stream].advance(uint8(v.entry))
   113  			br[stream2].advance(uint8(v2.entry))
   114  			buf[stream][off+1] = uint8(v.entry >> 8)
   115  			buf[stream2][off+1] = uint8(v2.entry >> 8)
   116  		}
   117  
   118  		off += 2
   119  
   120  		if off == 0 {
   121  			if bufoff > dstEvery {
   122  				d.bufs.Put(buf)
   123  				return nil, errors.New("corruption detected: stream overrun 1")
   124  			}
   125  			// There must at least be 3 buffers left.
   126  			if len(out)-bufoff < dstEvery*3 {
   127  				d.bufs.Put(buf)
   128  				return nil, errors.New("corruption detected: stream overrun 2")
   129  			}
   130  			//copy(out, buf[0][:])
   131  			//copy(out[dstEvery:], buf[1][:])
   132  			//copy(out[dstEvery*2:], buf[2][:])
   133  			//copy(out[dstEvery*3:], buf[3][:])
   134  			*(*[bufoff]byte)(out) = buf[0]
   135  			*(*[bufoff]byte)(out[dstEvery:]) = buf[1]
   136  			*(*[bufoff]byte)(out[dstEvery*2:]) = buf[2]
   137  			*(*[bufoff]byte)(out[dstEvery*3:]) = buf[3]
   138  			out = out[bufoff:]
   139  			decoded += bufoff * 4
   140  		}
   141  	}
   142  	if off > 0 {
   143  		ioff := int(off)
   144  		if len(out) < dstEvery*3+ioff {
   145  			d.bufs.Put(buf)
   146  			return nil, errors.New("corruption detected: stream overrun 3")
   147  		}
   148  		copy(out, buf[0][:off])
   149  		copy(out[dstEvery:], buf[1][:off])
   150  		copy(out[dstEvery*2:], buf[2][:off])
   151  		copy(out[dstEvery*3:], buf[3][:off])
   152  		decoded += int(off) * 4
   153  		out = out[off:]
   154  	}
   155  
   156  	// Decode remaining.
   157  	remainBytes := dstEvery - (decoded / 4)
   158  	for i := range br {
   159  		offset := dstEvery * i
   160  		endsAt := offset + remainBytes
   161  		if endsAt > len(out) {
   162  			endsAt = len(out)
   163  		}
   164  		br := &br[i]
   165  		bitsLeft := br.remaining()
   166  		for bitsLeft > 0 {
   167  			br.fill()
   168  			if offset >= endsAt {
   169  				d.bufs.Put(buf)
   170  				return nil, errors.New("corruption detected: stream overrun 4")
   171  			}
   172  
   173  			// Read value and increment offset.
   174  			val := br.peekBitsFast(d.actualTableLog)
   175  			v := single[val&tlMask].entry
   176  			nBits := uint8(v)
   177  			br.advance(nBits)
   178  			bitsLeft -= uint(nBits)
   179  			out[offset] = uint8(v >> 8)
   180  			offset++
   181  		}
   182  		if offset != endsAt {
   183  			d.bufs.Put(buf)
   184  			return nil, fmt.Errorf("corruption detected: short output block %d, end %d != %d", i, offset, endsAt)
   185  		}
   186  		decoded += offset - dstEvery*i
   187  		err = br.close()
   188  		if err != nil {
   189  			return nil, err
   190  		}
   191  	}
   192  	d.bufs.Put(buf)
   193  	if dstSize != decoded {
   194  		return nil, errors.New("corruption detected: short output block")
   195  	}
   196  	return dst, nil
   197  }
   198  
   199  // Decompress1X will decompress a 1X encoded stream.
   200  // The cap of the output buffer will be the maximum decompressed size.
   201  // The length of the supplied input must match the end of a block exactly.
   202  func (d *Decoder) Decompress1X(dst, src []byte) ([]byte, error) {
   203  	if len(d.dt.single) == 0 {
   204  		return nil, errors.New("no table loaded")
   205  	}
   206  	if use8BitTables && d.actualTableLog <= 8 {
   207  		return d.decompress1X8Bit(dst, src)
   208  	}
   209  	var br bitReaderShifted
   210  	err := br.init(src)
   211  	if err != nil {
   212  		return dst, err
   213  	}
   214  	maxDecodedSize := cap(dst)
   215  	dst = dst[:0]
   216  
   217  	// Avoid bounds check by always having full sized table.
   218  	const tlSize = 1 << tableLogMax
   219  	const tlMask = tlSize - 1
   220  	dt := d.dt.single[:tlSize]
   221  
   222  	// Use temp table to avoid bound checks/append penalty.
   223  	bufs := d.buffer()
   224  	buf := &bufs[0]
   225  	var off uint8
   226  
   227  	for br.off >= 8 {
   228  		br.fillFast()
   229  		v := dt[br.peekBitsFast(d.actualTableLog)&tlMask]
   230  		br.advance(uint8(v.entry))
   231  		buf[off+0] = uint8(v.entry >> 8)
   232  
   233  		v = dt[br.peekBitsFast(d.actualTableLog)&tlMask]
   234  		br.advance(uint8(v.entry))
   235  		buf[off+1] = uint8(v.entry >> 8)
   236  
   237  		// Refill
   238  		br.fillFast()
   239  
   240  		v = dt[br.peekBitsFast(d.actualTableLog)&tlMask]
   241  		br.advance(uint8(v.entry))
   242  		buf[off+2] = uint8(v.entry >> 8)
   243  
   244  		v = dt[br.peekBitsFast(d.actualTableLog)&tlMask]
   245  		br.advance(uint8(v.entry))
   246  		buf[off+3] = uint8(v.entry >> 8)
   247  
   248  		off += 4
   249  		if off == 0 {
   250  			if len(dst)+256 > maxDecodedSize {
   251  				br.close()
   252  				d.bufs.Put(bufs)
   253  				return nil, ErrMaxDecodedSizeExceeded
   254  			}
   255  			dst = append(dst, buf[:]...)
   256  		}
   257  	}
   258  
   259  	if len(dst)+int(off) > maxDecodedSize {
   260  		d.bufs.Put(bufs)
   261  		br.close()
   262  		return nil, ErrMaxDecodedSizeExceeded
   263  	}
   264  	dst = append(dst, buf[:off]...)
   265  
   266  	// br < 8, so uint8 is fine
   267  	bitsLeft := uint8(br.off)*8 + 64 - br.bitsRead
   268  	for bitsLeft > 0 {
   269  		br.fill()
   270  		if false && br.bitsRead >= 32 {
   271  			if br.off >= 4 {
   272  				v := br.in[br.off-4:]
   273  				v = v[:4]
   274  				low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
   275  				br.value = (br.value << 32) | uint64(low)
   276  				br.bitsRead -= 32
   277  				br.off -= 4
   278  			} else {
   279  				for br.off > 0 {
   280  					br.value = (br.value << 8) | uint64(br.in[br.off-1])
   281  					br.bitsRead -= 8
   282  					br.off--
   283  				}
   284  			}
   285  		}
   286  		if len(dst) >= maxDecodedSize {
   287  			d.bufs.Put(bufs)
   288  			br.close()
   289  			return nil, ErrMaxDecodedSizeExceeded
   290  		}
   291  		v := d.dt.single[br.peekBitsFast(d.actualTableLog)&tlMask]
   292  		nBits := uint8(v.entry)
   293  		br.advance(nBits)
   294  		bitsLeft -= nBits
   295  		dst = append(dst, uint8(v.entry>>8))
   296  	}
   297  	d.bufs.Put(bufs)
   298  	return dst, br.close()
   299  }
   300
View as plain text