Source file src/github.com/klauspost/compress/flate/inflate_gen.go

Documentation: github.com/klauspost/compress/flate

     1  // Code generated by go generate gen_inflate.go. DO NOT EDIT.
     2  
     3  package flate
     4  
     5  import (
     6  	"bufio"
     7  	"bytes"
     8  	"fmt"
     9  	"math/bits"
    10  	"strings"
    11  )
    12  
    13  // Decode a single Huffman block from f.
    14  // hl and hd are the Huffman states for the lit/length values
    15  // and the distance values, respectively. If hd == nil, using the
    16  // fixed distance encoding associated with fixed Huffman blocks.
    17  func (f *decompressor) huffmanBytesBuffer() {
    18  	const (
    19  		stateInit = iota // Zero value must be stateInit
    20  		stateDict
    21  	)
    22  	fr := f.r.(*bytes.Buffer)
    23  
    24  	// Optimization. Compiler isn't smart enough to keep f.b,f.nb in registers,
    25  	// but is smart enough to keep local variables in registers, so use nb and b,
    26  	// inline call to moreBits and reassign b,nb back to f on return.
    27  	fnb, fb, dict := f.nb, f.b, &f.dict
    28  
    29  	switch f.stepState {
    30  	case stateInit:
    31  		goto readLiteral
    32  	case stateDict:
    33  		goto copyHistory
    34  	}
    35  
    36  readLiteral:
    37  	// Read literal and/or (length, distance) according to RFC section 3.2.3.
    38  	{
    39  		var v int
    40  		{
    41  			// Inlined v, err := f.huffSym(f.hl)
    42  			// Since a huffmanDecoder can be empty or be composed of a degenerate tree
    43  			// with single element, huffSym must error on these two edge cases. In both
    44  			// cases, the chunks slice will be 0 for the invalid sequence, leading it
    45  			// satisfy the n == 0 check below.
    46  			n := uint(f.hl.maxRead)
    47  			for {
    48  				for fnb < n {
    49  					c, err := fr.ReadByte()
    50  					if err != nil {
    51  						f.b, f.nb = fb, fnb
    52  						f.err = noEOF(err)
    53  						return
    54  					}
    55  					f.roffset++
    56  					fb |= uint32(c) << (fnb & regSizeMaskUint32)
    57  					fnb += 8
    58  				}
    59  				chunk := f.hl.chunks[fb&(huffmanNumChunks-1)]
    60  				n = uint(chunk & huffmanCountMask)
    61  				if n > huffmanChunkBits {
    62  					chunk = f.hl.links[chunk>>huffmanValueShift][(fb>>huffmanChunkBits)&f.hl.linkMask]
    63  					n = uint(chunk & huffmanCountMask)
    64  				}
    65  				if n <= fnb {
    66  					if n == 0 {
    67  						f.b, f.nb = fb, fnb
    68  						if debugDecode {
    69  							fmt.Println("huffsym: n==0")
    70  						}
    71  						f.err = CorruptInputError(f.roffset)
    72  						return
    73  					}
    74  					fb = fb >> (n & regSizeMaskUint32)
    75  					fnb = fnb - n
    76  					v = int(chunk >> huffmanValueShift)
    77  					break
    78  				}
    79  			}
    80  		}
    81  
    82  		var length int
    83  		switch {
    84  		case v < 256:
    85  			dict.writeByte(byte(v))
    86  			if dict.availWrite() == 0 {
    87  				f.toRead = dict.readFlush()
    88  				f.step = huffmanBytesBuffer
    89  				f.stepState = stateInit
    90  				f.b, f.nb = fb, fnb
    91  				return
    92  			}
    93  			goto readLiteral
    94  		case v == 256:
    95  			f.b, f.nb = fb, fnb
    96  			f.finishBlock()
    97  			return
    98  		// otherwise, reference to older data
    99  		case v < 265:
   100  			length = v - (257 - 3)
   101  		case v < maxNumLit:
   102  			val := decCodeToLen[(v - 257)]
   103  			length = int(val.length) + 3
   104  			n := uint(val.extra)
   105  			for fnb < n {
   106  				c, err := fr.ReadByte()
   107  				if err != nil {
   108  					f.b, f.nb = fb, fnb
   109  					if debugDecode {
   110  						fmt.Println("morebits n>0:", err)
   111  					}
   112  					f.err = err
   113  					return
   114  				}
   115  				f.roffset++
   116  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   117  				fnb += 8
   118  			}
   119  			length += int(fb & bitMask32[n])
   120  			fb >>= n & regSizeMaskUint32
   121  			fnb -= n
   122  		default:
   123  			if debugDecode {
   124  				fmt.Println(v, ">= maxNumLit")
   125  			}
   126  			f.err = CorruptInputError(f.roffset)
   127  			f.b, f.nb = fb, fnb
   128  			return
   129  		}
   130  
   131  		var dist uint32
   132  		if f.hd == nil {
   133  			for fnb < 5 {
   134  				c, err := fr.ReadByte()
   135  				if err != nil {
   136  					f.b, f.nb = fb, fnb
   137  					if debugDecode {
   138  						fmt.Println("morebits f.nb<5:", err)
   139  					}
   140  					f.err = err
   141  					return
   142  				}
   143  				f.roffset++
   144  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   145  				fnb += 8
   146  			}
   147  			dist = uint32(bits.Reverse8(uint8(fb & 0x1F << 3)))
   148  			fb >>= 5
   149  			fnb -= 5
   150  		} else {
   151  			// Since a huffmanDecoder can be empty or be composed of a degenerate tree
   152  			// with single element, huffSym must error on these two edge cases. In both
   153  			// cases, the chunks slice will be 0 for the invalid sequence, leading it
   154  			// satisfy the n == 0 check below.
   155  			n := uint(f.hd.maxRead)
   156  			// Optimization. Compiler isn't smart enough to keep f.b,f.nb in registers,
   157  			// but is smart enough to keep local variables in registers, so use nb and b,
   158  			// inline call to moreBits and reassign b,nb back to f on return.
   159  			for {
   160  				for fnb < n {
   161  					c, err := fr.ReadByte()
   162  					if err != nil {
   163  						f.b, f.nb = fb, fnb
   164  						f.err = noEOF(err)
   165  						return
   166  					}
   167  					f.roffset++
   168  					fb |= uint32(c) << (fnb & regSizeMaskUint32)
   169  					fnb += 8
   170  				}
   171  				chunk := f.hd.chunks[fb&(huffmanNumChunks-1)]
   172  				n = uint(chunk & huffmanCountMask)
   173  				if n > huffmanChunkBits {
   174  					chunk = f.hd.links[chunk>>huffmanValueShift][(fb>>huffmanChunkBits)&f.hd.linkMask]
   175  					n = uint(chunk & huffmanCountMask)
   176  				}
   177  				if n <= fnb {
   178  					if n == 0 {
   179  						f.b, f.nb = fb, fnb
   180  						if debugDecode {
   181  							fmt.Println("huffsym: n==0")
   182  						}
   183  						f.err = CorruptInputError(f.roffset)
   184  						return
   185  					}
   186  					fb = fb >> (n & regSizeMaskUint32)
   187  					fnb = fnb - n
   188  					dist = uint32(chunk >> huffmanValueShift)
   189  					break
   190  				}
   191  			}
   192  		}
   193  
   194  		switch {
   195  		case dist < 4:
   196  			dist++
   197  		case dist < maxNumDist:
   198  			nb := uint(dist-2) >> 1
   199  			// have 1 bit in bottom of dist, need nb more.
   200  			extra := (dist & 1) << (nb & regSizeMaskUint32)
   201  			for fnb < nb {
   202  				c, err := fr.ReadByte()
   203  				if err != nil {
   204  					f.b, f.nb = fb, fnb
   205  					if debugDecode {
   206  						fmt.Println("morebits f.nb<nb:", err)
   207  					}
   208  					f.err = err
   209  					return
   210  				}
   211  				f.roffset++
   212  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   213  				fnb += 8
   214  			}
   215  			extra |= fb & bitMask32[nb]
   216  			fb >>= nb & regSizeMaskUint32
   217  			fnb -= nb
   218  			dist = 1<<((nb+1)&regSizeMaskUint32) + 1 + extra
   219  			// slower: dist = bitMask32[nb+1] + 2 + extra
   220  		default:
   221  			f.b, f.nb = fb, fnb
   222  			if debugDecode {
   223  				fmt.Println("dist too big:", dist, maxNumDist)
   224  			}
   225  			f.err = CorruptInputError(f.roffset)
   226  			return
   227  		}
   228  
   229  		// No check on length; encoding can be prescient.
   230  		if dist > uint32(dict.histSize()) {
   231  			f.b, f.nb = fb, fnb
   232  			if debugDecode {
   233  				fmt.Println("dist > dict.histSize():", dist, dict.histSize())
   234  			}
   235  			f.err = CorruptInputError(f.roffset)
   236  			return
   237  		}
   238  
   239  		f.copyLen, f.copyDist = length, int(dist)
   240  		goto copyHistory
   241  	}
   242  
   243  copyHistory:
   244  	// Perform a backwards copy according to RFC section 3.2.3.
   245  	{
   246  		cnt := dict.tryWriteCopy(f.copyDist, f.copyLen)
   247  		if cnt == 0 {
   248  			cnt = dict.writeCopy(f.copyDist, f.copyLen)
   249  		}
   250  		f.copyLen -= cnt
   251  
   252  		if dict.availWrite() == 0 || f.copyLen > 0 {
   253  			f.toRead = dict.readFlush()
   254  			f.step = huffmanBytesBuffer // We need to continue this work
   255  			f.stepState = stateDict
   256  			f.b, f.nb = fb, fnb
   257  			return
   258  		}
   259  		goto readLiteral
   260  	}
   261  	// Not reached
   262  }
   263  
   264  // Decode a single Huffman block from f.
   265  // hl and hd are the Huffman states for the lit/length values
   266  // and the distance values, respectively. If hd == nil, using the
   267  // fixed distance encoding associated with fixed Huffman blocks.
   268  func (f *decompressor) huffmanBytesReader() {
   269  	const (
   270  		stateInit = iota // Zero value must be stateInit
   271  		stateDict
   272  	)
   273  	fr := f.r.(*bytes.Reader)
   274  
   275  	// Optimization. Compiler isn't smart enough to keep f.b,f.nb in registers,
   276  	// but is smart enough to keep local variables in registers, so use nb and b,
   277  	// inline call to moreBits and reassign b,nb back to f on return.
   278  	fnb, fb, dict := f.nb, f.b, &f.dict
   279  
   280  	switch f.stepState {
   281  	case stateInit:
   282  		goto readLiteral
   283  	case stateDict:
   284  		goto copyHistory
   285  	}
   286  
   287  readLiteral:
   288  	// Read literal and/or (length, distance) according to RFC section 3.2.3.
   289  	{
   290  		var v int
   291  		{
   292  			// Inlined v, err := f.huffSym(f.hl)
   293  			// Since a huffmanDecoder can be empty or be composed of a degenerate tree
   294  			// with single element, huffSym must error on these two edge cases. In both
   295  			// cases, the chunks slice will be 0 for the invalid sequence, leading it
   296  			// satisfy the n == 0 check below.
   297  			n := uint(f.hl.maxRead)
   298  			for {
   299  				for fnb < n {
   300  					c, err := fr.ReadByte()
   301  					if err != nil {
   302  						f.b, f.nb = fb, fnb
   303  						f.err = noEOF(err)
   304  						return
   305  					}
   306  					f.roffset++
   307  					fb |= uint32(c) << (fnb & regSizeMaskUint32)
   308  					fnb += 8
   309  				}
   310  				chunk := f.hl.chunks[fb&(huffmanNumChunks-1)]
   311  				n = uint(chunk & huffmanCountMask)
   312  				if n > huffmanChunkBits {
   313  					chunk = f.hl.links[chunk>>huffmanValueShift][(fb>>huffmanChunkBits)&f.hl.linkMask]
   314  					n = uint(chunk & huffmanCountMask)
   315  				}
   316  				if n <= fnb {
   317  					if n == 0 {
   318  						f.b, f.nb = fb, fnb
   319  						if debugDecode {
   320  							fmt.Println("huffsym: n==0")
   321  						}
   322  						f.err = CorruptInputError(f.roffset)
   323  						return
   324  					}
   325  					fb = fb >> (n & regSizeMaskUint32)
   326  					fnb = fnb - n
   327  					v = int(chunk >> huffmanValueShift)
   328  					break
   329  				}
   330  			}
   331  		}
   332  
   333  		var length int
   334  		switch {
   335  		case v < 256:
   336  			dict.writeByte(byte(v))
   337  			if dict.availWrite() == 0 {
   338  				f.toRead = dict.readFlush()
   339  				f.step = huffmanBytesReader
   340  				f.stepState = stateInit
   341  				f.b, f.nb = fb, fnb
   342  				return
   343  			}
   344  			goto readLiteral
   345  		case v == 256:
   346  			f.b, f.nb = fb, fnb
   347  			f.finishBlock()
   348  			return
   349  		// otherwise, reference to older data
   350  		case v < 265:
   351  			length = v - (257 - 3)
   352  		case v < maxNumLit:
   353  			val := decCodeToLen[(v - 257)]
   354  			length = int(val.length) + 3
   355  			n := uint(val.extra)
   356  			for fnb < n {
   357  				c, err := fr.ReadByte()
   358  				if err != nil {
   359  					f.b, f.nb = fb, fnb
   360  					if debugDecode {
   361  						fmt.Println("morebits n>0:", err)
   362  					}
   363  					f.err = err
   364  					return
   365  				}
   366  				f.roffset++
   367  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   368  				fnb += 8
   369  			}
   370  			length += int(fb & bitMask32[n])
   371  			fb >>= n & regSizeMaskUint32
   372  			fnb -= n
   373  		default:
   374  			if debugDecode {
   375  				fmt.Println(v, ">= maxNumLit")
   376  			}
   377  			f.err = CorruptInputError(f.roffset)
   378  			f.b, f.nb = fb, fnb
   379  			return
   380  		}
   381  
   382  		var dist uint32
   383  		if f.hd == nil {
   384  			for fnb < 5 {
   385  				c, err := fr.ReadByte()
   386  				if err != nil {
   387  					f.b, f.nb = fb, fnb
   388  					if debugDecode {
   389  						fmt.Println("morebits f.nb<5:", err)
   390  					}
   391  					f.err = err
   392  					return
   393  				}
   394  				f.roffset++
   395  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   396  				fnb += 8
   397  			}
   398  			dist = uint32(bits.Reverse8(uint8(fb & 0x1F << 3)))
   399  			fb >>= 5
   400  			fnb -= 5
   401  		} else {
   402  			// Since a huffmanDecoder can be empty or be composed of a degenerate tree
   403  			// with single element, huffSym must error on these two edge cases. In both
   404  			// cases, the chunks slice will be 0 for the invalid sequence, leading it
   405  			// satisfy the n == 0 check below.
   406  			n := uint(f.hd.maxRead)
   407  			// Optimization. Compiler isn't smart enough to keep f.b,f.nb in registers,
   408  			// but is smart enough to keep local variables in registers, so use nb and b,
   409  			// inline call to moreBits and reassign b,nb back to f on return.
   410  			for {
   411  				for fnb < n {
   412  					c, err := fr.ReadByte()
   413  					if err != nil {
   414  						f.b, f.nb = fb, fnb
   415  						f.err = noEOF(err)
   416  						return
   417  					}
   418  					f.roffset++
   419  					fb |= uint32(c) << (fnb & regSizeMaskUint32)
   420  					fnb += 8
   421  				}
   422  				chunk := f.hd.chunks[fb&(huffmanNumChunks-1)]
   423  				n = uint(chunk & huffmanCountMask)
   424  				if n > huffmanChunkBits {
   425  					chunk = f.hd.links[chunk>>huffmanValueShift][(fb>>huffmanChunkBits)&f.hd.linkMask]
   426  					n = uint(chunk & huffmanCountMask)
   427  				}
   428  				if n <= fnb {
   429  					if n == 0 {
   430  						f.b, f.nb = fb, fnb
   431  						if debugDecode {
   432  							fmt.Println("huffsym: n==0")
   433  						}
   434  						f.err = CorruptInputError(f.roffset)
   435  						return
   436  					}
   437  					fb = fb >> (n & regSizeMaskUint32)
   438  					fnb = fnb - n
   439  					dist = uint32(chunk >> huffmanValueShift)
   440  					break
   441  				}
   442  			}
   443  		}
   444  
   445  		switch {
   446  		case dist < 4:
   447  			dist++
   448  		case dist < maxNumDist:
   449  			nb := uint(dist-2) >> 1
   450  			// have 1 bit in bottom of dist, need nb more.
   451  			extra := (dist & 1) << (nb & regSizeMaskUint32)
   452  			for fnb < nb {
   453  				c, err := fr.ReadByte()
   454  				if err != nil {
   455  					f.b, f.nb = fb, fnb
   456  					if debugDecode {
   457  						fmt.Println("morebits f.nb<nb:", err)
   458  					}
   459  					f.err = err
   460  					return
   461  				}
   462  				f.roffset++
   463  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   464  				fnb += 8
   465  			}
   466  			extra |= fb & bitMask32[nb]
   467  			fb >>= nb & regSizeMaskUint32
   468  			fnb -= nb
   469  			dist = 1<<((nb+1)&regSizeMaskUint32) + 1 + extra
   470  			// slower: dist = bitMask32[nb+1] + 2 + extra
   471  		default:
   472  			f.b, f.nb = fb, fnb
   473  			if debugDecode {
   474  				fmt.Println("dist too big:", dist, maxNumDist)
   475  			}
   476  			f.err = CorruptInputError(f.roffset)
   477  			return
   478  		}
   479  
   480  		// No check on length; encoding can be prescient.
   481  		if dist > uint32(dict.histSize()) {
   482  			f.b, f.nb = fb, fnb
   483  			if debugDecode {
   484  				fmt.Println("dist > dict.histSize():", dist, dict.histSize())
   485  			}
   486  			f.err = CorruptInputError(f.roffset)
   487  			return
   488  		}
   489  
   490  		f.copyLen, f.copyDist = length, int(dist)
   491  		goto copyHistory
   492  	}
   493  
   494  copyHistory:
   495  	// Perform a backwards copy according to RFC section 3.2.3.
   496  	{
   497  		cnt := dict.tryWriteCopy(f.copyDist, f.copyLen)
   498  		if cnt == 0 {
   499  			cnt = dict.writeCopy(f.copyDist, f.copyLen)
   500  		}
   501  		f.copyLen -= cnt
   502  
   503  		if dict.availWrite() == 0 || f.copyLen > 0 {
   504  			f.toRead = dict.readFlush()
   505  			f.step = huffmanBytesReader // We need to continue this work
   506  			f.stepState = stateDict
   507  			f.b, f.nb = fb, fnb
   508  			return
   509  		}
   510  		goto readLiteral
   511  	}
   512  	// Not reached
   513  }
   514  
   515  // Decode a single Huffman block from f.
   516  // hl and hd are the Huffman states for the lit/length values
   517  // and the distance values, respectively. If hd == nil, using the
   518  // fixed distance encoding associated with fixed Huffman blocks.
   519  func (f *decompressor) huffmanBufioReader() {
   520  	const (
   521  		stateInit = iota // Zero value must be stateInit
   522  		stateDict
   523  	)
   524  	fr := f.r.(*bufio.Reader)
   525  
   526  	// Optimization. Compiler isn't smart enough to keep f.b,f.nb in registers,
   527  	// but is smart enough to keep local variables in registers, so use nb and b,
   528  	// inline call to moreBits and reassign b,nb back to f on return.
   529  	fnb, fb, dict := f.nb, f.b, &f.dict
   530  
   531  	switch f.stepState {
   532  	case stateInit:
   533  		goto readLiteral
   534  	case stateDict:
   535  		goto copyHistory
   536  	}
   537  
   538  readLiteral:
   539  	// Read literal and/or (length, distance) according to RFC section 3.2.3.
   540  	{
   541  		var v int
   542  		{
   543  			// Inlined v, err := f.huffSym(f.hl)
   544  			// Since a huffmanDecoder can be empty or be composed of a degenerate tree
   545  			// with single element, huffSym must error on these two edge cases. In both
   546  			// cases, the chunks slice will be 0 for the invalid sequence, leading it
   547  			// satisfy the n == 0 check below.
   548  			n := uint(f.hl.maxRead)
   549  			for {
   550  				for fnb < n {
   551  					c, err := fr.ReadByte()
   552  					if err != nil {
   553  						f.b, f.nb = fb, fnb
   554  						f.err = noEOF(err)
   555  						return
   556  					}
   557  					f.roffset++
   558  					fb |= uint32(c) << (fnb & regSizeMaskUint32)
   559  					fnb += 8
   560  				}
   561  				chunk := f.hl.chunks[fb&(huffmanNumChunks-1)]
   562  				n = uint(chunk & huffmanCountMask)
   563  				if n > huffmanChunkBits {
   564  					chunk = f.hl.links[chunk>>huffmanValueShift][(fb>>huffmanChunkBits)&f.hl.linkMask]
   565  					n = uint(chunk & huffmanCountMask)
   566  				}
   567  				if n <= fnb {
   568  					if n == 0 {
   569  						f.b, f.nb = fb, fnb
   570  						if debugDecode {
   571  							fmt.Println("huffsym: n==0")
   572  						}
   573  						f.err = CorruptInputError(f.roffset)
   574  						return
   575  					}
   576  					fb = fb >> (n & regSizeMaskUint32)
   577  					fnb = fnb - n
   578  					v = int(chunk >> huffmanValueShift)
   579  					break
   580  				}
   581  			}
   582  		}
   583  
   584  		var length int
   585  		switch {
   586  		case v < 256:
   587  			dict.writeByte(byte(v))
   588  			if dict.availWrite() == 0 {
   589  				f.toRead = dict.readFlush()
   590  				f.step = huffmanBufioReader
   591  				f.stepState = stateInit
   592  				f.b, f.nb = fb, fnb
   593  				return
   594  			}
   595  			goto readLiteral
   596  		case v == 256:
   597  			f.b, f.nb = fb, fnb
   598  			f.finishBlock()
   599  			return
   600  		// otherwise, reference to older data
   601  		case v < 265:
   602  			length = v - (257 - 3)
   603  		case v < maxNumLit:
   604  			val := decCodeToLen[(v - 257)]
   605  			length = int(val.length) + 3
   606  			n := uint(val.extra)
   607  			for fnb < n {
   608  				c, err := fr.ReadByte()
   609  				if err != nil {
   610  					f.b, f.nb = fb, fnb
   611  					if debugDecode {
   612  						fmt.Println("morebits n>0:", err)
   613  					}
   614  					f.err = err
   615  					return
   616  				}
   617  				f.roffset++
   618  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   619  				fnb += 8
   620  			}
   621  			length += int(fb & bitMask32[n])
   622  			fb >>= n & regSizeMaskUint32
   623  			fnb -= n
   624  		default:
   625  			if debugDecode {
   626  				fmt.Println(v, ">= maxNumLit")
   627  			}
   628  			f.err = CorruptInputError(f.roffset)
   629  			f.b, f.nb = fb, fnb
   630  			return
   631  		}
   632  
   633  		var dist uint32
   634  		if f.hd == nil {
   635  			for fnb < 5 {
   636  				c, err := fr.ReadByte()
   637  				if err != nil {
   638  					f.b, f.nb = fb, fnb
   639  					if debugDecode {
   640  						fmt.Println("morebits f.nb<5:", err)
   641  					}
   642  					f.err = err
   643  					return
   644  				}
   645  				f.roffset++
   646  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   647  				fnb += 8
   648  			}
   649  			dist = uint32(bits.Reverse8(uint8(fb & 0x1F << 3)))
   650  			fb >>= 5
   651  			fnb -= 5
   652  		} else {
   653  			// Since a huffmanDecoder can be empty or be composed of a degenerate tree
   654  			// with single element, huffSym must error on these two edge cases. In both
   655  			// cases, the chunks slice will be 0 for the invalid sequence, leading it
   656  			// satisfy the n == 0 check below.
   657  			n := uint(f.hd.maxRead)
   658  			// Optimization. Compiler isn't smart enough to keep f.b,f.nb in registers,
   659  			// but is smart enough to keep local variables in registers, so use nb and b,
   660  			// inline call to moreBits and reassign b,nb back to f on return.
   661  			for {
   662  				for fnb < n {
   663  					c, err := fr.ReadByte()
   664  					if err != nil {
   665  						f.b, f.nb = fb, fnb
   666  						f.err = noEOF(err)
   667  						return
   668  					}
   669  					f.roffset++
   670  					fb |= uint32(c) << (fnb & regSizeMaskUint32)
   671  					fnb += 8
   672  				}
   673  				chunk := f.hd.chunks[fb&(huffmanNumChunks-1)]
   674  				n = uint(chunk & huffmanCountMask)
   675  				if n > huffmanChunkBits {
   676  					chunk = f.hd.links[chunk>>huffmanValueShift][(fb>>huffmanChunkBits)&f.hd.linkMask]
   677  					n = uint(chunk & huffmanCountMask)
   678  				}
   679  				if n <= fnb {
   680  					if n == 0 {
   681  						f.b, f.nb = fb, fnb
   682  						if debugDecode {
   683  							fmt.Println("huffsym: n==0")
   684  						}
   685  						f.err = CorruptInputError(f.roffset)
   686  						return
   687  					}
   688  					fb = fb >> (n & regSizeMaskUint32)
   689  					fnb = fnb - n
   690  					dist = uint32(chunk >> huffmanValueShift)
   691  					break
   692  				}
   693  			}
   694  		}
   695  
   696  		switch {
   697  		case dist < 4:
   698  			dist++
   699  		case dist < maxNumDist:
   700  			nb := uint(dist-2) >> 1
   701  			// have 1 bit in bottom of dist, need nb more.
   702  			extra := (dist & 1) << (nb & regSizeMaskUint32)
   703  			for fnb < nb {
   704  				c, err := fr.ReadByte()
   705  				if err != nil {
   706  					f.b, f.nb = fb, fnb
   707  					if debugDecode {
   708  						fmt.Println("morebits f.nb<nb:", err)
   709  					}
   710  					f.err = err
   711  					return
   712  				}
   713  				f.roffset++
   714  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   715  				fnb += 8
   716  			}
   717  			extra |= fb & bitMask32[nb]
   718  			fb >>= nb & regSizeMaskUint32
   719  			fnb -= nb
   720  			dist = 1<<((nb+1)&regSizeMaskUint32) + 1 + extra
   721  			// slower: dist = bitMask32[nb+1] + 2 + extra
   722  		default:
   723  			f.b, f.nb = fb, fnb
   724  			if debugDecode {
   725  				fmt.Println("dist too big:", dist, maxNumDist)
   726  			}
   727  			f.err = CorruptInputError(f.roffset)
   728  			return
   729  		}
   730  
   731  		// No check on length; encoding can be prescient.
   732  		if dist > uint32(dict.histSize()) {
   733  			f.b, f.nb = fb, fnb
   734  			if debugDecode {
   735  				fmt.Println("dist > dict.histSize():", dist, dict.histSize())
   736  			}
   737  			f.err = CorruptInputError(f.roffset)
   738  			return
   739  		}
   740  
   741  		f.copyLen, f.copyDist = length, int(dist)
   742  		goto copyHistory
   743  	}
   744  
   745  copyHistory:
   746  	// Perform a backwards copy according to RFC section 3.2.3.
   747  	{
   748  		cnt := dict.tryWriteCopy(f.copyDist, f.copyLen)
   749  		if cnt == 0 {
   750  			cnt = dict.writeCopy(f.copyDist, f.copyLen)
   751  		}
   752  		f.copyLen -= cnt
   753  
   754  		if dict.availWrite() == 0 || f.copyLen > 0 {
   755  			f.toRead = dict.readFlush()
   756  			f.step = huffmanBufioReader // We need to continue this work
   757  			f.stepState = stateDict
   758  			f.b, f.nb = fb, fnb
   759  			return
   760  		}
   761  		goto readLiteral
   762  	}
   763  	// Not reached
   764  }
   765  
   766  // Decode a single Huffman block from f.
   767  // hl and hd are the Huffman states for the lit/length values
   768  // and the distance values, respectively. If hd == nil, using the
   769  // fixed distance encoding associated with fixed Huffman blocks.
   770  func (f *decompressor) huffmanStringsReader() {
   771  	const (
   772  		stateInit = iota // Zero value must be stateInit
   773  		stateDict
   774  	)
   775  	fr := f.r.(*strings.Reader)
   776  
   777  	// Optimization. Compiler isn't smart enough to keep f.b,f.nb in registers,
   778  	// but is smart enough to keep local variables in registers, so use nb and b,
   779  	// inline call to moreBits and reassign b,nb back to f on return.
   780  	fnb, fb, dict := f.nb, f.b, &f.dict
   781  
   782  	switch f.stepState {
   783  	case stateInit:
   784  		goto readLiteral
   785  	case stateDict:
   786  		goto copyHistory
   787  	}
   788  
   789  readLiteral:
   790  	// Read literal and/or (length, distance) according to RFC section 3.2.3.
   791  	{
   792  		var v int
   793  		{
   794  			// Inlined v, err := f.huffSym(f.hl)
   795  			// Since a huffmanDecoder can be empty or be composed of a degenerate tree
   796  			// with single element, huffSym must error on these two edge cases. In both
   797  			// cases, the chunks slice will be 0 for the invalid sequence, leading it
   798  			// satisfy the n == 0 check below.
   799  			n := uint(f.hl.maxRead)
   800  			for {
   801  				for fnb < n {
   802  					c, err := fr.ReadByte()
   803  					if err != nil {
   804  						f.b, f.nb = fb, fnb
   805  						f.err = noEOF(err)
   806  						return
   807  					}
   808  					f.roffset++
   809  					fb |= uint32(c) << (fnb & regSizeMaskUint32)
   810  					fnb += 8
   811  				}
   812  				chunk := f.hl.chunks[fb&(huffmanNumChunks-1)]
   813  				n = uint(chunk & huffmanCountMask)
   814  				if n > huffmanChunkBits {
   815  					chunk = f.hl.links[chunk>>huffmanValueShift][(fb>>huffmanChunkBits)&f.hl.linkMask]
   816  					n = uint(chunk & huffmanCountMask)
   817  				}
   818  				if n <= fnb {
   819  					if n == 0 {
   820  						f.b, f.nb = fb, fnb
   821  						if debugDecode {
   822  							fmt.Println("huffsym: n==0")
   823  						}
   824  						f.err = CorruptInputError(f.roffset)
   825  						return
   826  					}
   827  					fb = fb >> (n & regSizeMaskUint32)
   828  					fnb = fnb - n
   829  					v = int(chunk >> huffmanValueShift)
   830  					break
   831  				}
   832  			}
   833  		}
   834  
   835  		var length int
   836  		switch {
   837  		case v < 256:
   838  			dict.writeByte(byte(v))
   839  			if dict.availWrite() == 0 {
   840  				f.toRead = dict.readFlush()
   841  				f.step = huffmanStringsReader
   842  				f.stepState = stateInit
   843  				f.b, f.nb = fb, fnb
   844  				return
   845  			}
   846  			goto readLiteral
   847  		case v == 256:
   848  			f.b, f.nb = fb, fnb
   849  			f.finishBlock()
   850  			return
   851  		// otherwise, reference to older data
   852  		case v < 265:
   853  			length = v - (257 - 3)
   854  		case v < maxNumLit:
   855  			val := decCodeToLen[(v - 257)]
   856  			length = int(val.length) + 3
   857  			n := uint(val.extra)
   858  			for fnb < n {
   859  				c, err := fr.ReadByte()
   860  				if err != nil {
   861  					f.b, f.nb = fb, fnb
   862  					if debugDecode {
   863  						fmt.Println("morebits n>0:", err)
   864  					}
   865  					f.err = err
   866  					return
   867  				}
   868  				f.roffset++
   869  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   870  				fnb += 8
   871  			}
   872  			length += int(fb & bitMask32[n])
   873  			fb >>= n & regSizeMaskUint32
   874  			fnb -= n
   875  		default:
   876  			if debugDecode {
   877  				fmt.Println(v, ">= maxNumLit")
   878  			}
   879  			f.err = CorruptInputError(f.roffset)
   880  			f.b, f.nb = fb, fnb
   881  			return
   882  		}
   883  
   884  		var dist uint32
   885  		if f.hd == nil {
   886  			for fnb < 5 {
   887  				c, err := fr.ReadByte()
   888  				if err != nil {
   889  					f.b, f.nb = fb, fnb
   890  					if debugDecode {
   891  						fmt.Println("morebits f.nb<5:", err)
   892  					}
   893  					f.err = err
   894  					return
   895  				}
   896  				f.roffset++
   897  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   898  				fnb += 8
   899  			}
   900  			dist = uint32(bits.Reverse8(uint8(fb & 0x1F << 3)))
   901  			fb >>= 5
   902  			fnb -= 5
   903  		} else {
   904  			// Since a huffmanDecoder can be empty or be composed of a degenerate tree
   905  			// with single element, huffSym must error on these two edge cases. In both
   906  			// cases, the chunks slice will be 0 for the invalid sequence, leading it
   907  			// satisfy the n == 0 check below.
   908  			n := uint(f.hd.maxRead)
   909  			// Optimization. Compiler isn't smart enough to keep f.b,f.nb in registers,
   910  			// but is smart enough to keep local variables in registers, so use nb and b,
   911  			// inline call to moreBits and reassign b,nb back to f on return.
   912  			for {
   913  				for fnb < n {
   914  					c, err := fr.ReadByte()
   915  					if err != nil {
   916  						f.b, f.nb = fb, fnb
   917  						f.err = noEOF(err)
   918  						return
   919  					}
   920  					f.roffset++
   921  					fb |= uint32(c) << (fnb & regSizeMaskUint32)
   922  					fnb += 8
   923  				}
   924  				chunk := f.hd.chunks[fb&(huffmanNumChunks-1)]
   925  				n = uint(chunk & huffmanCountMask)
   926  				if n > huffmanChunkBits {
   927  					chunk = f.hd.links[chunk>>huffmanValueShift][(fb>>huffmanChunkBits)&f.hd.linkMask]
   928  					n = uint(chunk & huffmanCountMask)
   929  				}
   930  				if n <= fnb {
   931  					if n == 0 {
   932  						f.b, f.nb = fb, fnb
   933  						if debugDecode {
   934  							fmt.Println("huffsym: n==0")
   935  						}
   936  						f.err = CorruptInputError(f.roffset)
   937  						return
   938  					}
   939  					fb = fb >> (n & regSizeMaskUint32)
   940  					fnb = fnb - n
   941  					dist = uint32(chunk >> huffmanValueShift)
   942  					break
   943  				}
   944  			}
   945  		}
   946  
   947  		switch {
   948  		case dist < 4:
   949  			dist++
   950  		case dist < maxNumDist:
   951  			nb := uint(dist-2) >> 1
   952  			// have 1 bit in bottom of dist, need nb more.
   953  			extra := (dist & 1) << (nb & regSizeMaskUint32)
   954  			for fnb < nb {
   955  				c, err := fr.ReadByte()
   956  				if err != nil {
   957  					f.b, f.nb = fb, fnb
   958  					if debugDecode {
   959  						fmt.Println("morebits f.nb<nb:", err)
   960  					}
   961  					f.err = err
   962  					return
   963  				}
   964  				f.roffset++
   965  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
   966  				fnb += 8
   967  			}
   968  			extra |= fb & bitMask32[nb]
   969  			fb >>= nb & regSizeMaskUint32
   970  			fnb -= nb
   971  			dist = 1<<((nb+1)&regSizeMaskUint32) + 1 + extra
   972  			// slower: dist = bitMask32[nb+1] + 2 + extra
   973  		default:
   974  			f.b, f.nb = fb, fnb
   975  			if debugDecode {
   976  				fmt.Println("dist too big:", dist, maxNumDist)
   977  			}
   978  			f.err = CorruptInputError(f.roffset)
   979  			return
   980  		}
   981  
   982  		// No check on length; encoding can be prescient.
   983  		if dist > uint32(dict.histSize()) {
   984  			f.b, f.nb = fb, fnb
   985  			if debugDecode {
   986  				fmt.Println("dist > dict.histSize():", dist, dict.histSize())
   987  			}
   988  			f.err = CorruptInputError(f.roffset)
   989  			return
   990  		}
   991  
   992  		f.copyLen, f.copyDist = length, int(dist)
   993  		goto copyHistory
   994  	}
   995  
   996  copyHistory:
   997  	// Perform a backwards copy according to RFC section 3.2.3.
   998  	{
   999  		cnt := dict.tryWriteCopy(f.copyDist, f.copyLen)
  1000  		if cnt == 0 {
  1001  			cnt = dict.writeCopy(f.copyDist, f.copyLen)
  1002  		}
  1003  		f.copyLen -= cnt
  1004  
  1005  		if dict.availWrite() == 0 || f.copyLen > 0 {
  1006  			f.toRead = dict.readFlush()
  1007  			f.step = huffmanStringsReader // We need to continue this work
  1008  			f.stepState = stateDict
  1009  			f.b, f.nb = fb, fnb
  1010  			return
  1011  		}
  1012  		goto readLiteral
  1013  	}
  1014  	// Not reached
  1015  }
  1016  
  1017  // Decode a single Huffman block from f.
  1018  // hl and hd are the Huffman states for the lit/length values
  1019  // and the distance values, respectively. If hd == nil, using the
  1020  // fixed distance encoding associated with fixed Huffman blocks.
  1021  func (f *decompressor) huffmanGenericReader() {
  1022  	const (
  1023  		stateInit = iota // Zero value must be stateInit
  1024  		stateDict
  1025  	)
  1026  	fr := f.r.(Reader)
  1027  
  1028  	// Optimization. Compiler isn't smart enough to keep f.b,f.nb in registers,
  1029  	// but is smart enough to keep local variables in registers, so use nb and b,
  1030  	// inline call to moreBits and reassign b,nb back to f on return.
  1031  	fnb, fb, dict := f.nb, f.b, &f.dict
  1032  
  1033  	switch f.stepState {
  1034  	case stateInit:
  1035  		goto readLiteral
  1036  	case stateDict:
  1037  		goto copyHistory
  1038  	}
  1039  
  1040  readLiteral:
  1041  	// Read literal and/or (length, distance) according to RFC section 3.2.3.
  1042  	{
  1043  		var v int
  1044  		{
  1045  			// Inlined v, err := f.huffSym(f.hl)
  1046  			// Since a huffmanDecoder can be empty or be composed of a degenerate tree
  1047  			// with single element, huffSym must error on these two edge cases. In both
  1048  			// cases, the chunks slice will be 0 for the invalid sequence, leading it
  1049  			// satisfy the n == 0 check below.
  1050  			n := uint(f.hl.maxRead)
  1051  			for {
  1052  				for fnb < n {
  1053  					c, err := fr.ReadByte()
  1054  					if err != nil {
  1055  						f.b, f.nb = fb, fnb
  1056  						f.err = noEOF(err)
  1057  						return
  1058  					}
  1059  					f.roffset++
  1060  					fb |= uint32(c) << (fnb & regSizeMaskUint32)
  1061  					fnb += 8
  1062  				}
  1063  				chunk := f.hl.chunks[fb&(huffmanNumChunks-1)]
  1064  				n = uint(chunk & huffmanCountMask)
  1065  				if n > huffmanChunkBits {
  1066  					chunk = f.hl.links[chunk>>huffmanValueShift][(fb>>huffmanChunkBits)&f.hl.linkMask]
  1067  					n = uint(chunk & huffmanCountMask)
  1068  				}
  1069  				if n <= fnb {
  1070  					if n == 0 {
  1071  						f.b, f.nb = fb, fnb
  1072  						if debugDecode {
  1073  							fmt.Println("huffsym: n==0")
  1074  						}
  1075  						f.err = CorruptInputError(f.roffset)
  1076  						return
  1077  					}
  1078  					fb = fb >> (n & regSizeMaskUint32)
  1079  					fnb = fnb - n
  1080  					v = int(chunk >> huffmanValueShift)
  1081  					break
  1082  				}
  1083  			}
  1084  		}
  1085  
  1086  		var length int
  1087  		switch {
  1088  		case v < 256:
  1089  			dict.writeByte(byte(v))
  1090  			if dict.availWrite() == 0 {
  1091  				f.toRead = dict.readFlush()
  1092  				f.step = huffmanGenericReader
  1093  				f.stepState = stateInit
  1094  				f.b, f.nb = fb, fnb
  1095  				return
  1096  			}
  1097  			goto readLiteral
  1098  		case v == 256:
  1099  			f.b, f.nb = fb, fnb
  1100  			f.finishBlock()
  1101  			return
  1102  		// otherwise, reference to older data
  1103  		case v < 265:
  1104  			length = v - (257 - 3)
  1105  		case v < maxNumLit:
  1106  			val := decCodeToLen[(v - 257)]
  1107  			length = int(val.length) + 3
  1108  			n := uint(val.extra)
  1109  			for fnb < n {
  1110  				c, err := fr.ReadByte()
  1111  				if err != nil {
  1112  					f.b, f.nb = fb, fnb
  1113  					if debugDecode {
  1114  						fmt.Println("morebits n>0:", err)
  1115  					}
  1116  					f.err = err
  1117  					return
  1118  				}
  1119  				f.roffset++
  1120  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
  1121  				fnb += 8
  1122  			}
  1123  			length += int(fb & bitMask32[n])
  1124  			fb >>= n & regSizeMaskUint32
  1125  			fnb -= n
  1126  		default:
  1127  			if debugDecode {
  1128  				fmt.Println(v, ">= maxNumLit")
  1129  			}
  1130  			f.err = CorruptInputError(f.roffset)
  1131  			f.b, f.nb = fb, fnb
  1132  			return
  1133  		}
  1134  
  1135  		var dist uint32
  1136  		if f.hd == nil {
  1137  			for fnb < 5 {
  1138  				c, err := fr.ReadByte()
  1139  				if err != nil {
  1140  					f.b, f.nb = fb, fnb
  1141  					if debugDecode {
  1142  						fmt.Println("morebits f.nb<5:", err)
  1143  					}
  1144  					f.err = err
  1145  					return
  1146  				}
  1147  				f.roffset++
  1148  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
  1149  				fnb += 8
  1150  			}
  1151  			dist = uint32(bits.Reverse8(uint8(fb & 0x1F << 3)))
  1152  			fb >>= 5
  1153  			fnb -= 5
  1154  		} else {
  1155  			// Since a huffmanDecoder can be empty or be composed of a degenerate tree
  1156  			// with single element, huffSym must error on these two edge cases. In both
  1157  			// cases, the chunks slice will be 0 for the invalid sequence, leading it
  1158  			// satisfy the n == 0 check below.
  1159  			n := uint(f.hd.maxRead)
  1160  			// Optimization. Compiler isn't smart enough to keep f.b,f.nb in registers,
  1161  			// but is smart enough to keep local variables in registers, so use nb and b,
  1162  			// inline call to moreBits and reassign b,nb back to f on return.
  1163  			for {
  1164  				for fnb < n {
  1165  					c, err := fr.ReadByte()
  1166  					if err != nil {
  1167  						f.b, f.nb = fb, fnb
  1168  						f.err = noEOF(err)
  1169  						return
  1170  					}
  1171  					f.roffset++
  1172  					fb |= uint32(c) << (fnb & regSizeMaskUint32)
  1173  					fnb += 8
  1174  				}
  1175  				chunk := f.hd.chunks[fb&(huffmanNumChunks-1)]
  1176  				n = uint(chunk & huffmanCountMask)
  1177  				if n > huffmanChunkBits {
  1178  					chunk = f.hd.links[chunk>>huffmanValueShift][(fb>>huffmanChunkBits)&f.hd.linkMask]
  1179  					n = uint(chunk & huffmanCountMask)
  1180  				}
  1181  				if n <= fnb {
  1182  					if n == 0 {
  1183  						f.b, f.nb = fb, fnb
  1184  						if debugDecode {
  1185  							fmt.Println("huffsym: n==0")
  1186  						}
  1187  						f.err = CorruptInputError(f.roffset)
  1188  						return
  1189  					}
  1190  					fb = fb >> (n & regSizeMaskUint32)
  1191  					fnb = fnb - n
  1192  					dist = uint32(chunk >> huffmanValueShift)
  1193  					break
  1194  				}
  1195  			}
  1196  		}
  1197  
  1198  		switch {
  1199  		case dist < 4:
  1200  			dist++
  1201  		case dist < maxNumDist:
  1202  			nb := uint(dist-2) >> 1
  1203  			// have 1 bit in bottom of dist, need nb more.
  1204  			extra := (dist & 1) << (nb & regSizeMaskUint32)
  1205  			for fnb < nb {
  1206  				c, err := fr.ReadByte()
  1207  				if err != nil {
  1208  					f.b, f.nb = fb, fnb
  1209  					if debugDecode {
  1210  						fmt.Println("morebits f.nb<nb:", err)
  1211  					}
  1212  					f.err = err
  1213  					return
  1214  				}
  1215  				f.roffset++
  1216  				fb |= uint32(c) << (fnb & regSizeMaskUint32)
  1217  				fnb += 8
  1218  			}
  1219  			extra |= fb & bitMask32[nb]
  1220  			fb >>= nb & regSizeMaskUint32
  1221  			fnb -= nb
  1222  			dist = 1<<((nb+1)&regSizeMaskUint32) + 1 + extra
  1223  			// slower: dist = bitMask32[nb+1] + 2 + extra
  1224  		default:
  1225  			f.b, f.nb = fb, fnb
  1226  			if debugDecode {
  1227  				fmt.Println("dist too big:", dist, maxNumDist)
  1228  			}
  1229  			f.err = CorruptInputError(f.roffset)
  1230  			return
  1231  		}
  1232  
  1233  		// No check on length; encoding can be prescient.
  1234  		if dist > uint32(dict.histSize()) {
  1235  			f.b, f.nb = fb, fnb
  1236  			if debugDecode {
  1237  				fmt.Println("dist > dict.histSize():", dist, dict.histSize())
  1238  			}
  1239  			f.err = CorruptInputError(f.roffset)
  1240  			return
  1241  		}
  1242  
  1243  		f.copyLen, f.copyDist = length, int(dist)
  1244  		goto copyHistory
  1245  	}
  1246  
  1247  copyHistory:
  1248  	// Perform a backwards copy according to RFC section 3.2.3.
  1249  	{
  1250  		cnt := dict.tryWriteCopy(f.copyDist, f.copyLen)
  1251  		if cnt == 0 {
  1252  			cnt = dict.writeCopy(f.copyDist, f.copyLen)
  1253  		}
  1254  		f.copyLen -= cnt
  1255  
  1256  		if dict.availWrite() == 0 || f.copyLen > 0 {
  1257  			f.toRead = dict.readFlush()
  1258  			f.step = huffmanGenericReader // We need to continue this work
  1259  			f.stepState = stateDict
  1260  			f.b, f.nb = fb, fnb
  1261  			return
  1262  		}
  1263  		goto readLiteral
  1264  	}
  1265  	// Not reached
  1266  }
  1267  
  1268  func (f *decompressor) huffmanBlockDecoder() {
  1269  	switch f.r.(type) {
  1270  	case *bytes.Buffer:
  1271  		f.huffmanBytesBuffer()
  1272  	case *bytes.Reader:
  1273  		f.huffmanBytesReader()
  1274  	case *bufio.Reader:
  1275  		f.huffmanBufioReader()
  1276  	case *strings.Reader:
  1277  		f.huffmanStringsReader()
  1278  	case Reader:
  1279  		f.huffmanGenericReader()
  1280  	default:
  1281  		f.huffmanGenericReader()
  1282  	}
  1283  }
  1284  

View as plain text