fse_predefined.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 (
     8  	"fmt"
     9  	"math"
    10  	"sync"
    11  )
    12  
    13  var (
    14  	// fsePredef are the predefined fse tables as defined here:
    15  	// https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#default-distributions
    16  	// These values are already transformed.
    17  	fsePredef [3]fseDecoder
    18  
    19  	// fsePredefEnc are the predefined encoder based on fse tables as defined here:
    20  	// https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#default-distributions
    21  	// These values are already transformed.
    22  	fsePredefEnc [3]fseEncoder
    23  
    24  	// symbolTableX contain the transformations needed for each type as defined in
    25  	// https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#the-codes-for-literals-lengths-match-lengths-and-offsets
    26  	symbolTableX [3][]baseOffset
    27  
    28  	// maxTableSymbol is the biggest supported symbol for each table type
    29  	// https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#the-codes-for-literals-lengths-match-lengths-and-offsets
    30  	maxTableSymbol = [3]uint8{tableLiteralLengths: maxLiteralLengthSymbol, tableOffsets: maxOffsetLengthSymbol, tableMatchLengths: maxMatchLengthSymbol}
    31  
    32  	// bitTables is the bits table for each table.
    33  	bitTables = [3][]byte{tableLiteralLengths: llBitsTable[:], tableOffsets: nil, tableMatchLengths: mlBitsTable[:]}
    34  )
    35  
    36  type tableIndex uint8
    37  
    38  const (
    39  	// indexes for fsePredef and symbolTableX
    40  	tableLiteralLengths tableIndex = 0
    41  	tableOffsets        tableIndex = 1
    42  	tableMatchLengths   tableIndex = 2
    43  
    44  	maxLiteralLengthSymbol = 35
    45  	maxOffsetLengthSymbol  = 30
    46  	maxMatchLengthSymbol   = 52
    47  )
    48  
    49  // baseOffset is used for calculating transformations.
    50  type baseOffset struct {
    51  	baseLine uint32
    52  	addBits  uint8
    53  }
    54  
    55  // fillBase will precalculate base offsets with the given bit distributions.
    56  func fillBase(dst []baseOffset, base uint32, bits ...uint8) {
    57  	if len(bits) != len(dst) {
    58  		panic(fmt.Sprintf("len(dst) (%d) != len(bits) (%d)", len(dst), len(bits)))
    59  	}
    60  	for i, bit := range bits {
    61  		if base > math.MaxInt32 {
    62  			panic("invalid decoding table, base overflows int32")
    63  		}
    64  
    65  		dst[i] = baseOffset{
    66  			baseLine: base,
    67  			addBits:  bit,
    68  		}
    69  		base += 1 << bit
    70  	}
    71  }
    72  
    73  var predef sync.Once
    74  
    75  func initPredefined() {
    76  	predef.Do(func() {
    77  		// Literals length codes
    78  		tmp := make([]baseOffset, 36)
    79  		for i := range tmp[:16] {
    80  			tmp[i] = baseOffset{
    81  				baseLine: uint32(i),
    82  				addBits:  0,
    83  			}
    84  		}
    85  		fillBase(tmp[16:], 16, 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
    86  		symbolTableX[tableLiteralLengths] = tmp
    87  
    88  		// Match length codes
    89  		tmp = make([]baseOffset, 53)
    90  		for i := range tmp[:32] {
    91  			tmp[i] = baseOffset{
    92  				// The transformation adds the 3 length.
    93  				baseLine: uint32(i) + 3,
    94  				addBits:  0,
    95  			}
    96  		}
    97  		fillBase(tmp[32:], 35, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
    98  		symbolTableX[tableMatchLengths] = tmp
    99  
   100  		// Offset codes
   101  		tmp = make([]baseOffset, maxOffsetBits+1)
   102  		tmp[1] = baseOffset{
   103  			baseLine: 1,
   104  			addBits:  1,
   105  		}
   106  		fillBase(tmp[2:], 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
   107  		symbolTableX[tableOffsets] = tmp
   108  
   109  		// Fill predefined tables and transform them.
   110  		// https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#default-distributions
   111  		for i := range fsePredef[:] {
   112  			f := &fsePredef[i]
   113  			switch tableIndex(i) {
   114  			case tableLiteralLengths:
   115  				// https://github.com/facebook/zstd/blob/ededcfca57366461021c922720878c81a5854a0a/lib/decompress/zstd_decompress_block.c#L243
   116  				f.actualTableLog = 6
   117  				copy(f.norm[:], []int16{4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
   118  					2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
   119  					-1, -1, -1, -1})
   120  				f.symbolLen = 36
   121  			case tableOffsets:
   122  				// https://github.com/facebook/zstd/blob/ededcfca57366461021c922720878c81a5854a0a/lib/decompress/zstd_decompress_block.c#L281
   123  				f.actualTableLog = 5
   124  				copy(f.norm[:], []int16{
   125  					1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
   126  					1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1})
   127  				f.symbolLen = 29
   128  			case tableMatchLengths:
   129  				//https://github.com/facebook/zstd/blob/ededcfca57366461021c922720878c81a5854a0a/lib/decompress/zstd_decompress_block.c#L304
   130  				f.actualTableLog = 6
   131  				copy(f.norm[:], []int16{
   132  					1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
   133  					1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
   134  					1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1,
   135  					-1, -1, -1, -1, -1})
   136  				f.symbolLen = 53
   137  			}
   138  			if err := f.buildDtable(); err != nil {
   139  				panic(fmt.Errorf("building table %v: %v", tableIndex(i), err))
   140  			}
   141  			if err := f.transform(symbolTableX[i]); err != nil {
   142  				panic(fmt.Errorf("building table %v: %v", tableIndex(i), err))
   143  			}
   144  			f.preDefined = true
   145  
   146  			// Create encoder as well
   147  			enc := &fsePredefEnc[i]
   148  			copy(enc.norm[:], f.norm[:])
   149  			enc.symbolLen = f.symbolLen
   150  			enc.actualTableLog = f.actualTableLog
   151  			if err := enc.buildCTable(); err != nil {
   152  				panic(fmt.Errorf("building encoding table %v: %v", tableIndex(i), err))
   153  			}
   154  			enc.setBits(bitTables[i])
   155  			enc.preDefined = true
   156  		}
   157  	})
   158  }
   159
View as plain text