fse.go

     1  // Copyright 2023 The Go Authors. 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 zstd
     6  
     7  import (
     8  	"math/bits"
     9  )
    10  
    11  // fseEntry is one entry in an FSE table.
    12  type fseEntry struct {
    13  	sym  uint8  // value that this entry records
    14  	bits uint8  // number of bits to read to determine next state
    15  	base uint16 // add those bits to this state to get the next state
    16  }
    17  
    18  // readFSE reads an FSE table from data starting at off.
    19  // maxSym is the maximum symbol value.
    20  // maxBits is the maximum number of bits permitted for symbols in the table.
    21  // The FSE is written into table, which must be at least 1<<maxBits in size.
    22  // This returns the number of bits in the FSE table and the new offset.
    23  // RFC 4.1.1.
    24  func (r *Reader) readFSE(data block, off, maxSym, maxBits int, table []fseEntry) (tableBits, roff int, err error) {
    25  	br := r.makeBitReader(data, off)
    26  	if err := br.moreBits(); err != nil {
    27  		return 0, 0, err
    28  	}
    29  
    30  	accuracyLog := int(br.val(4)) + 5
    31  	if accuracyLog > maxBits {
    32  		return 0, 0, br.makeError("FSE accuracy log too large")
    33  	}
    34  
    35  	// The number of remaining probabilities, plus 1.
    36  	// This determines the number of bits to be read for the next value.
    37  	remaining := (1 << accuracyLog) + 1
    38  
    39  	// The current difference between small and large values,
    40  	// which depends on the number of remaining values.
    41  	// Small values use 1 less bit.
    42  	threshold := 1 << accuracyLog
    43  
    44  	// The number of bits needed to compute threshold.
    45  	bitsNeeded := accuracyLog + 1
    46  
    47  	// The next character value.
    48  	sym := 0
    49  
    50  	// Whether the last count was 0.
    51  	prev0 := false
    52  
    53  	var norm [256]int16
    54  
    55  	for remaining > 1 && sym <= maxSym {
    56  		if err := br.moreBits(); err != nil {
    57  			return 0, 0, err
    58  		}
    59  
    60  		if prev0 {
    61  			// Previous count was 0, so there is a 2-bit
    62  			// repeat flag. If the 2-bit flag is 0b11,
    63  			// it adds 3 and then there is another repeat flag.
    64  			zsym := sym
    65  			for (br.bits & 0xfff) == 0xfff {
    66  				zsym += 3 * 6
    67  				br.bits >>= 12
    68  				br.cnt -= 12
    69  				if err := br.moreBits(); err != nil {
    70  					return 0, 0, err
    71  				}
    72  			}
    73  			for (br.bits & 3) == 3 {
    74  				zsym += 3
    75  				br.bits >>= 2
    76  				br.cnt -= 2
    77  				if err := br.moreBits(); err != nil {
    78  					return 0, 0, err
    79  				}
    80  			}
    81  
    82  			// We have at least 14 bits here,
    83  			// no need to call moreBits
    84  
    85  			zsym += int(br.val(2))
    86  
    87  			if zsym > maxSym {
    88  				return 0, 0, br.makeError("FSE symbol index overflow")
    89  			}
    90  
    91  			for ; sym < zsym; sym++ {
    92  				norm[uint8(sym)] = 0
    93  			}
    94  
    95  			prev0 = false
    96  			continue
    97  		}
    98  
    99  		max := (2*threshold - 1) - remaining
   100  		var count int
   101  		if int(br.bits&uint32(threshold-1)) < max {
   102  			// A small value.
   103  			count = int(br.bits & uint32((threshold - 1)))
   104  			br.bits >>= bitsNeeded - 1
   105  			br.cnt -= uint32(bitsNeeded - 1)
   106  		} else {
   107  			// A large value.
   108  			count = int(br.bits & uint32((2*threshold - 1)))
   109  			if count >= threshold {
   110  				count -= max
   111  			}
   112  			br.bits >>= bitsNeeded
   113  			br.cnt -= uint32(bitsNeeded)
   114  		}
   115  
   116  		count--
   117  		if count >= 0 {
   118  			remaining -= count
   119  		} else {
   120  			remaining--
   121  		}
   122  		if sym >= 256 {
   123  			return 0, 0, br.makeError("FSE sym overflow")
   124  		}
   125  		norm[uint8(sym)] = int16(count)
   126  		sym++
   127  
   128  		prev0 = count == 0
   129  
   130  		for remaining < threshold {
   131  			bitsNeeded--
   132  			threshold >>= 1
   133  		}
   134  	}
   135  
   136  	if remaining != 1 {
   137  		return 0, 0, br.makeError("too many symbols in FSE table")
   138  	}
   139  
   140  	for ; sym <= maxSym; sym++ {
   141  		norm[uint8(sym)] = 0
   142  	}
   143  
   144  	br.backup()
   145  
   146  	if err := r.buildFSE(off, norm[:maxSym+1], table, accuracyLog); err != nil {
   147  		return 0, 0, err
   148  	}
   149  
   150  	return accuracyLog, int(br.off), nil
   151  }
   152  
   153  // buildFSE builds an FSE decoding table from a list of probabilities.
   154  // The probabilities are in norm. next is scratch space. The number of bits
   155  // in the table is tableBits.
   156  func (r *Reader) buildFSE(off int, norm []int16, table []fseEntry, tableBits int) error {
   157  	tableSize := 1 << tableBits
   158  	highThreshold := tableSize - 1
   159  
   160  	var next [256]uint16
   161  
   162  	for i, n := range norm {
   163  		if n >= 0 {
   164  			next[uint8(i)] = uint16(n)
   165  		} else {
   166  			table[highThreshold].sym = uint8(i)
   167  			highThreshold--
   168  			next[uint8(i)] = 1
   169  		}
   170  	}
   171  
   172  	pos := 0
   173  	step := (tableSize >> 1) + (tableSize >> 3) + 3
   174  	mask := tableSize - 1
   175  	for i, n := range norm {
   176  		for j := 0; j < int(n); j++ {
   177  			table[pos].sym = uint8(i)
   178  			pos = (pos + step) & mask
   179  			for pos > highThreshold {
   180  				pos = (pos + step) & mask
   181  			}
   182  		}
   183  	}
   184  	if pos != 0 {
   185  		return r.makeError(off, "FSE count error")
   186  	}
   187  
   188  	for i := 0; i < tableSize; i++ {
   189  		sym := table[i].sym
   190  		nextState := next[sym]
   191  		next[sym]++
   192  
   193  		if nextState == 0 {
   194  			return r.makeError(off, "FSE state error")
   195  		}
   196  
   197  		highBit := 15 - bits.LeadingZeros16(nextState)
   198  
   199  		bits := tableBits - highBit
   200  		table[i].bits = uint8(bits)
   201  		table[i].base = (nextState << bits) - uint16(tableSize)
   202  	}
   203  
   204  	return nil
   205  }
   206  
   207  // fseBaselineEntry is an entry in an FSE baseline table.
   208  // We use these for literal/match/length values.
   209  // Those require mapping the symbol to a baseline value,
   210  // and then reading zero or more bits and adding the value to the baseline.
   211  // Rather than looking these up in separate tables,
   212  // we convert the FSE table to an FSE baseline table.
   213  type fseBaselineEntry struct {
   214  	baseline uint32 // baseline for value that this entry represents
   215  	basebits uint8  // number of bits to read to add to baseline
   216  	bits     uint8  // number of bits to read to determine next state
   217  	base     uint16 // add the bits to this base to get the next state
   218  }
   219  
   220  // Given a literal length code, we need to read a number of bits and
   221  // add that to a baseline. For states 0 to 15 the baseline is the
   222  // state and the number of bits is zero. RFC 3.1.1.3.2.1.1.
   223  
   224  const literalLengthOffset = 16
   225  
   226  var literalLengthBase = []uint32{
   227  	16 | (1 << 24),
   228  	18 | (1 << 24),
   229  	20 | (1 << 24),
   230  	22 | (1 << 24),
   231  	24 | (2 << 24),
   232  	28 | (2 << 24),
   233  	32 | (3 << 24),
   234  	40 | (3 << 24),
   235  	48 | (4 << 24),
   236  	64 | (6 << 24),
   237  	128 | (7 << 24),
   238  	256 | (8 << 24),
   239  	512 | (9 << 24),
   240  	1024 | (10 << 24),
   241  	2048 | (11 << 24),
   242  	4096 | (12 << 24),
   243  	8192 | (13 << 24),
   244  	16384 | (14 << 24),
   245  	32768 | (15 << 24),
   246  	65536 | (16 << 24),
   247  }
   248  
   249  // makeLiteralBaselineFSE converts the literal length fseTable to baselineTable.
   250  func (r *Reader) makeLiteralBaselineFSE(off int, fseTable []fseEntry, baselineTable []fseBaselineEntry) error {
   251  	for i, e := range fseTable {
   252  		be := fseBaselineEntry{
   253  			bits: e.bits,
   254  			base: e.base,
   255  		}
   256  		if e.sym < literalLengthOffset {
   257  			be.baseline = uint32(e.sym)
   258  			be.basebits = 0
   259  		} else {
   260  			if e.sym > 35 {
   261  				return r.makeError(off, "FSE baseline symbol overflow")
   262  			}
   263  			idx := e.sym - literalLengthOffset
   264  			basebits := literalLengthBase[idx]
   265  			be.baseline = basebits & 0xffffff
   266  			be.basebits = uint8(basebits >> 24)
   267  		}
   268  		baselineTable[i] = be
   269  	}
   270  	return nil
   271  }
   272  
   273  // makeOffsetBaselineFSE converts the offset length fseTable to baselineTable.
   274  func (r *Reader) makeOffsetBaselineFSE(off int, fseTable []fseEntry, baselineTable []fseBaselineEntry) error {
   275  	for i, e := range fseTable {
   276  		be := fseBaselineEntry{
   277  			bits: e.bits,
   278  			base: e.base,
   279  		}
   280  		if e.sym > 31 {
   281  			return r.makeError(off, "FSE offset symbol overflow")
   282  		}
   283  
   284  		// The simple way to write this is
   285  		//     be.baseline = 1 << e.sym
   286  		//     be.basebits = e.sym
   287  		// That would give us an offset value that corresponds to
   288  		// the one described in the RFC. However, for offsets > 3
   289  		// we have to subtract 3. And for offset values 1, 2, 3
   290  		// we use a repeated offset.
   291  		//
   292  		// The baseline is always a power of 2, and is never 0,
   293  		// so for those low values we will see one entry that is
   294  		// baseline 1, basebits 0, and one entry that is baseline 2,
   295  		// basebits 1. All other entries will have baseline >= 4
   296  		// basebits >= 2.
   297  		//
   298  		// So we can check for RFC offset <= 3 by checking for
   299  		// basebits <= 1. That means that we can subtract 3 here
   300  		// and not worry about doing it in the hot loop.
   301  
   302  		be.baseline = 1 << e.sym
   303  		if e.sym >= 2 {
   304  			be.baseline -= 3
   305  		}
   306  		be.basebits = e.sym
   307  		baselineTable[i] = be
   308  	}
   309  	return nil
   310  }
   311  
   312  // Given a match length code, we need to read a number of bits and add
   313  // that to a baseline. For states 0 to 31 the baseline is state+3 and
   314  // the number of bits is zero. RFC 3.1.1.3.2.1.1.
   315  
   316  const matchLengthOffset = 32
   317  
   318  var matchLengthBase = []uint32{
   319  	35 | (1 << 24),
   320  	37 | (1 << 24),
   321  	39 | (1 << 24),
   322  	41 | (1 << 24),
   323  	43 | (2 << 24),
   324  	47 | (2 << 24),
   325  	51 | (3 << 24),
   326  	59 | (3 << 24),
   327  	67 | (4 << 24),
   328  	83 | (4 << 24),
   329  	99 | (5 << 24),
   330  	131 | (7 << 24),
   331  	259 | (8 << 24),
   332  	515 | (9 << 24),
   333  	1027 | (10 << 24),
   334  	2051 | (11 << 24),
   335  	4099 | (12 << 24),
   336  	8195 | (13 << 24),
   337  	16387 | (14 << 24),
   338  	32771 | (15 << 24),
   339  	65539 | (16 << 24),
   340  }
   341  
   342  // makeMatchBaselineFSE converts the match length fseTable to baselineTable.
   343  func (r *Reader) makeMatchBaselineFSE(off int, fseTable []fseEntry, baselineTable []fseBaselineEntry) error {
   344  	for i, e := range fseTable {
   345  		be := fseBaselineEntry{
   346  			bits: e.bits,
   347  			base: e.base,
   348  		}
   349  		if e.sym < matchLengthOffset {
   350  			be.baseline = uint32(e.sym) + 3
   351  			be.basebits = 0
   352  		} else {
   353  			if e.sym > 52 {
   354  				return r.makeError(off, "FSE baseline symbol overflow")
   355  			}
   356  			idx := e.sym - matchLengthOffset
   357  			basebits := matchLengthBase[idx]
   358  			be.baseline = basebits & 0xffffff
   359  			be.basebits = uint8(basebits >> 24)
   360  		}
   361  		baselineTable[i] = be
   362  	}
   363  	return nil
   364  }
   365  
   366  // predefinedLiteralTable is the predefined table to use for literal lengths.
   367  // Generated from table in RFC 3.1.1.3.2.2.1.
   368  // Checked by TestPredefinedTables.
   369  var predefinedLiteralTable = [...]fseBaselineEntry{
   370  	{0, 0, 4, 0}, {0, 0, 4, 16}, {1, 0, 5, 32},
   371  	{3, 0, 5, 0}, {4, 0, 5, 0}, {6, 0, 5, 0},
   372  	{7, 0, 5, 0}, {9, 0, 5, 0}, {10, 0, 5, 0},
   373  	{12, 0, 5, 0}, {14, 0, 6, 0}, {16, 1, 5, 0},
   374  	{20, 1, 5, 0}, {22, 1, 5, 0}, {28, 2, 5, 0},
   375  	{32, 3, 5, 0}, {48, 4, 5, 0}, {64, 6, 5, 32},
   376  	{128, 7, 5, 0}, {256, 8, 6, 0}, {1024, 10, 6, 0},
   377  	{4096, 12, 6, 0}, {0, 0, 4, 32}, {1, 0, 4, 0},
   378  	{2, 0, 5, 0}, {4, 0, 5, 32}, {5, 0, 5, 0},
   379  	{7, 0, 5, 32}, {8, 0, 5, 0}, {10, 0, 5, 32},
   380  	{11, 0, 5, 0}, {13, 0, 6, 0}, {16, 1, 5, 32},
   381  	{18, 1, 5, 0}, {22, 1, 5, 32}, {24, 2, 5, 0},
   382  	{32, 3, 5, 32}, {40, 3, 5, 0}, {64, 6, 4, 0},
   383  	{64, 6, 4, 16}, {128, 7, 5, 32}, {512, 9, 6, 0},
   384  	{2048, 11, 6, 0}, {0, 0, 4, 48}, {1, 0, 4, 16},
   385  	{2, 0, 5, 32}, {3, 0, 5, 32}, {5, 0, 5, 32},
   386  	{6, 0, 5, 32}, {8, 0, 5, 32}, {9, 0, 5, 32},
   387  	{11, 0, 5, 32}, {12, 0, 5, 32}, {15, 0, 6, 0},
   388  	{18, 1, 5, 32}, {20, 1, 5, 32}, {24, 2, 5, 32},
   389  	{28, 2, 5, 32}, {40, 3, 5, 32}, {48, 4, 5, 32},
   390  	{65536, 16, 6, 0}, {32768, 15, 6, 0}, {16384, 14, 6, 0},
   391  	{8192, 13, 6, 0},
   392  }
   393  
   394  // predefinedOffsetTable is the predefined table to use for offsets.
   395  // Generated from table in RFC 3.1.1.3.2.2.3.
   396  // Checked by TestPredefinedTables.
   397  var predefinedOffsetTable = [...]fseBaselineEntry{
   398  	{1, 0, 5, 0}, {61, 6, 4, 0}, {509, 9, 5, 0},
   399  	{32765, 15, 5, 0}, {2097149, 21, 5, 0}, {5, 3, 5, 0},
   400  	{125, 7, 4, 0}, {4093, 12, 5, 0}, {262141, 18, 5, 0},
   401  	{8388605, 23, 5, 0}, {29, 5, 5, 0}, {253, 8, 4, 0},
   402  	{16381, 14, 5, 0}, {1048573, 20, 5, 0}, {1, 2, 5, 0},
   403  	{125, 7, 4, 16}, {2045, 11, 5, 0}, {131069, 17, 5, 0},
   404  	{4194301, 22, 5, 0}, {13, 4, 5, 0}, {253, 8, 4, 16},
   405  	{8189, 13, 5, 0}, {524285, 19, 5, 0}, {2, 1, 5, 0},
   406  	{61, 6, 4, 16}, {1021, 10, 5, 0}, {65533, 16, 5, 0},
   407  	{268435453, 28, 5, 0}, {134217725, 27, 5, 0}, {67108861, 26, 5, 0},
   408  	{33554429, 25, 5, 0}, {16777213, 24, 5, 0},
   409  }
   410  
   411  // predefinedMatchTable is the predefined table to use for match lengths.
   412  // Generated from table in RFC 3.1.1.3.2.2.2.
   413  // Checked by TestPredefinedTables.
   414  var predefinedMatchTable = [...]fseBaselineEntry{
   415  	{3, 0, 6, 0}, {4, 0, 4, 0}, {5, 0, 5, 32},
   416  	{6, 0, 5, 0}, {8, 0, 5, 0}, {9, 0, 5, 0},
   417  	{11, 0, 5, 0}, {13, 0, 6, 0}, {16, 0, 6, 0},
   418  	{19, 0, 6, 0}, {22, 0, 6, 0}, {25, 0, 6, 0},
   419  	{28, 0, 6, 0}, {31, 0, 6, 0}, {34, 0, 6, 0},
   420  	{37, 1, 6, 0}, {41, 1, 6, 0}, {47, 2, 6, 0},
   421  	{59, 3, 6, 0}, {83, 4, 6, 0}, {131, 7, 6, 0},
   422  	{515, 9, 6, 0}, {4, 0, 4, 16}, {5, 0, 4, 0},
   423  	{6, 0, 5, 32}, {7, 0, 5, 0}, {9, 0, 5, 32},
   424  	{10, 0, 5, 0}, {12, 0, 6, 0}, {15, 0, 6, 0},
   425  	{18, 0, 6, 0}, {21, 0, 6, 0}, {24, 0, 6, 0},
   426  	{27, 0, 6, 0}, {30, 0, 6, 0}, {33, 0, 6, 0},
   427  	{35, 1, 6, 0}, {39, 1, 6, 0}, {43, 2, 6, 0},
   428  	{51, 3, 6, 0}, {67, 4, 6, 0}, {99, 5, 6, 0},
   429  	{259, 8, 6, 0}, {4, 0, 4, 32}, {4, 0, 4, 48},
   430  	{5, 0, 4, 16}, {7, 0, 5, 32}, {8, 0, 5, 32},
   431  	{10, 0, 5, 32}, {11, 0, 5, 32}, {14, 0, 6, 0},
   432  	{17, 0, 6, 0}, {20, 0, 6, 0}, {23, 0, 6, 0},
   433  	{26, 0, 6, 0}, {29, 0, 6, 0}, {32, 0, 6, 0},
   434  	{65539, 16, 6, 0}, {32771, 15, 6, 0}, {16387, 14, 6, 0},
   435  	{8195, 13, 6, 0}, {4099, 12, 6, 0}, {2051, 11, 6, 0},
   436  	{1027, 10, 6, 0},
   437  }
   438
View as plain text