fse_decoder_generic.go

Documentation: github.com/klauspost/compress/zstd

     1  //go:build !amd64 || appengine || !gc || noasm
     2  // +build !amd64 appengine !gc noasm
     3  
     4  package zstd
     5  
     6  import (
     7  	"errors"
     8  	"fmt"
     9  )
    10  
    11  // buildDtable will build the decoding table.
    12  func (s *fseDecoder) buildDtable() error {
    13  	tableSize := uint32(1 << s.actualTableLog)
    14  	highThreshold := tableSize - 1
    15  	symbolNext := s.stateTable[:256]
    16  
    17  	// Init, lay down lowprob symbols
    18  	{
    19  		for i, v := range s.norm[:s.symbolLen] {
    20  			if v == -1 {
    21  				s.dt[highThreshold].setAddBits(uint8(i))
    22  				highThreshold--
    23  				v = 1
    24  			}
    25  			symbolNext[i] = uint16(v)
    26  		}
    27  	}
    28  
    29  	// Spread symbols
    30  	{
    31  		tableMask := tableSize - 1
    32  		step := tableStep(tableSize)
    33  		position := uint32(0)
    34  		for ss, v := range s.norm[:s.symbolLen] {
    35  			for i := 0; i < int(v); i++ {
    36  				s.dt[position].setAddBits(uint8(ss))
    37  				for {
    38  					// lowprob area
    39  					position = (position + step) & tableMask
    40  					if position <= highThreshold {
    41  						break
    42  					}
    43  				}
    44  			}
    45  		}
    46  		if position != 0 {
    47  			// position must reach all cells once, otherwise normalizedCounter is incorrect
    48  			return errors.New("corrupted input (position != 0)")
    49  		}
    50  	}
    51  
    52  	// Build Decoding table
    53  	{
    54  		tableSize := uint16(1 << s.actualTableLog)
    55  		for u, v := range s.dt[:tableSize] {
    56  			symbol := v.addBits()
    57  			nextState := symbolNext[symbol]
    58  			symbolNext[symbol] = nextState + 1
    59  			nBits := s.actualTableLog - byte(highBits(uint32(nextState)))
    60  			s.dt[u&maxTableMask].setNBits(nBits)
    61  			newState := (nextState << nBits) - tableSize
    62  			if newState > tableSize {
    63  				return fmt.Errorf("newState (%d) outside table size (%d)", newState, tableSize)
    64  			}
    65  			if newState == uint16(u) && nBits == 0 {
    66  				// Seems weird that this is possible with nbits > 0.
    67  				return fmt.Errorf("newState (%d) == oldState (%d) and no bits", newState, u)
    68  			}
    69  			s.dt[u&maxTableMask].setNewState(newState)
    70  		}
    71  	}
    72  	return nil
    73  }
    74
View as plain text