fse_decoder_generic.go raw

   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