seqenc.go

Documentation: github.com/klauspost/compress/zstd

     1  // Copyright 2019+ Klaus Post. All rights reserved.
     2  // License information can be found in the LICENSE file.
     3  // Based on work by Yann Collet, released under BSD License.
     4  
     5  package zstd
     6  
     7  import "math/bits"
     8  
     9  type seqCoders struct {
    10  	llEnc, ofEnc, mlEnc    *fseEncoder
    11  	llPrev, ofPrev, mlPrev *fseEncoder
    12  }
    13  
    14  // swap coders with another (block).
    15  func (s *seqCoders) swap(other *seqCoders) {
    16  	*s, *other = *other, *s
    17  }
    18  
    19  // setPrev will update the previous encoders to the actually used ones
    20  // and make sure a fresh one is in the main slot.
    21  func (s *seqCoders) setPrev(ll, ml, of *fseEncoder) {
    22  	compareSwap := func(used *fseEncoder, current, prev **fseEncoder) {
    23  		// We used the new one, more current to history and reuse the previous history
    24  		if *current == used {
    25  			*prev, *current = *current, *prev
    26  			c := *current
    27  			p := *prev
    28  			c.reUsed = false
    29  			p.reUsed = true
    30  			return
    31  		}
    32  		if used == *prev {
    33  			return
    34  		}
    35  		// Ensure we cannot reuse by accident
    36  		prevEnc := *prev
    37  		prevEnc.symbolLen = 0
    38  	}
    39  	compareSwap(ll, &s.llEnc, &s.llPrev)
    40  	compareSwap(ml, &s.mlEnc, &s.mlPrev)
    41  	compareSwap(of, &s.ofEnc, &s.ofPrev)
    42  }
    43  
    44  func highBit(val uint32) (n uint32) {
    45  	return uint32(bits.Len32(val) - 1)
    46  }
    47  
    48  var llCodeTable = [64]byte{0, 1, 2, 3, 4, 5, 6, 7,
    49  	8, 9, 10, 11, 12, 13, 14, 15,
    50  	16, 16, 17, 17, 18, 18, 19, 19,
    51  	20, 20, 20, 20, 21, 21, 21, 21,
    52  	22, 22, 22, 22, 22, 22, 22, 22,
    53  	23, 23, 23, 23, 23, 23, 23, 23,
    54  	24, 24, 24, 24, 24, 24, 24, 24,
    55  	24, 24, 24, 24, 24, 24, 24, 24}
    56  
    57  // Up to 6 bits
    58  const maxLLCode = 35
    59  
    60  // llBitsTable translates from ll code to number of bits.
    61  var llBitsTable = [maxLLCode + 1]byte{
    62  	0, 0, 0, 0, 0, 0, 0, 0,
    63  	0, 0, 0, 0, 0, 0, 0, 0,
    64  	1, 1, 1, 1, 2, 2, 3, 3,
    65  	4, 6, 7, 8, 9, 10, 11, 12,
    66  	13, 14, 15, 16}
    67  
    68  // llCode returns the code that represents the literal length requested.
    69  func llCode(litLength uint32) uint8 {
    70  	const llDeltaCode = 19
    71  	if litLength <= 63 {
    72  		// Compiler insists on bounds check (Go 1.12)
    73  		return llCodeTable[litLength&63]
    74  	}
    75  	return uint8(highBit(litLength)) + llDeltaCode
    76  }
    77  
    78  var mlCodeTable = [128]byte{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
    79  	16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
    80  	32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
    81  	38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
    82  	40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
    83  	41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
    84  	42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
    85  	42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42}
    86  
    87  // Up to 6 bits
    88  const maxMLCode = 52
    89  
    90  // mlBitsTable translates from ml code to number of bits.
    91  var mlBitsTable = [maxMLCode + 1]byte{
    92  	0, 0, 0, 0, 0, 0, 0, 0,
    93  	0, 0, 0, 0, 0, 0, 0, 0,
    94  	0, 0, 0, 0, 0, 0, 0, 0,
    95  	0, 0, 0, 0, 0, 0, 0, 0,
    96  	1, 1, 1, 1, 2, 2, 3, 3,
    97  	4, 4, 5, 7, 8, 9, 10, 11,
    98  	12, 13, 14, 15, 16}
    99  
   100  // note : mlBase = matchLength - MINMATCH;
   101  // because it's the format it's stored in seqStore->sequences
   102  func mlCode(mlBase uint32) uint8 {
   103  	const mlDeltaCode = 36
   104  	if mlBase <= 127 {
   105  		// Compiler insists on bounds check (Go 1.12)
   106  		return mlCodeTable[mlBase&127]
   107  	}
   108  	return uint8(highBit(mlBase)) + mlDeltaCode
   109  }
   110  
   111  func ofCode(offset uint32) uint8 {
   112  	// A valid offset will always be > 0.
   113  	return uint8(bits.Len32(offset) - 1)
   114  }
   115
View as plain text