Source file src/github.com/xi2/xz/dec_lzma2.go

Documentation: github.com/xi2/xz

     1  /*
     2   * LZMA2 decoder
     3   *
     4   * Authors: Lasse Collin <lasse.collin@tukaani.org>
     5   *          Igor Pavlov <http://7-zip.org/>
     6   *
     7   * Translation to Go: Michael Cross <https://github.com/xi2>
     8   *
     9   * This file has been put into the public domain.
    10   * You can do whatever you want with this file.
    11   */
    12  
    13  package xz
    14  
    15  /* from linux/lib/xz/xz_lzma2.h ***************************************/
    16  
    17  /* Range coder constants */
    18  const (
    19  	rcShiftBits         = 8
    20  	rcTopBits           = 24
    21  	rcTopValue          = 1 << rcTopBits
    22  	rcBitModelTotalBits = 11
    23  	rcBitModelTotal     = 1 << rcBitModelTotalBits
    24  	rcMoveBits          = 5
    25  )
    26  
    27  /*
    28   * Maximum number of position states. A position state is the lowest pb
    29   * number of bits of the current uncompressed offset. In some places there
    30   * are different sets of probabilities for different position states.
    31   */
    32  const posStatesMax = 1 << 4
    33  
    34  /*
    35   * lzmaState is used to track which LZMA symbols have occurred most recently
    36   * and in which order. This information is used to predict the next symbol.
    37   *
    38   * Symbols:
    39   *  - Literal: One 8-bit byte
    40   *  - Match: Repeat a chunk of data at some distance
    41   *  - Long repeat: Multi-byte match at a recently seen distance
    42   *  - Short repeat: One-byte repeat at a recently seen distance
    43   *
    44   * The symbol names are in from STATE-oldest-older-previous. REP means
    45   * either short or long repeated match, and NONLIT means any non-literal.
    46   */
    47  type lzmaState int
    48  
    49  const (
    50  	stateLitLit lzmaState = iota
    51  	stateMatchLitLit
    52  	stateRepLitLit
    53  	stateShortrepLitLit
    54  	stateMatchLit
    55  	stateRepList
    56  	stateShortrepLit
    57  	stateLitMatch
    58  	stateLitLongrep
    59  	stateLitShortrep
    60  	stateNonlitMatch
    61  	stateNonlitRep
    62  )
    63  
    64  /* Total number of states */
    65  const states = 12
    66  
    67  /* The lowest 7 states indicate that the previous state was a literal. */
    68  const litStates = 7
    69  
    70  /* Indicate that the latest symbol was a literal. */
    71  func lzmaStateLiteral(state *lzmaState) {
    72  	switch {
    73  	case *state <= stateShortrepLitLit:
    74  		*state = stateLitLit
    75  	case *state <= stateLitShortrep:
    76  		*state -= 3
    77  	default:
    78  		*state -= 6
    79  	}
    80  }
    81  
    82  /* Indicate that the latest symbol was a match. */
    83  func lzmaStateMatch(state *lzmaState) {
    84  	if *state < litStates {
    85  		*state = stateLitMatch
    86  	} else {
    87  		*state = stateNonlitMatch
    88  	}
    89  }
    90  
    91  /* Indicate that the latest state was a long repeated match. */
    92  func lzmaStateLongRep(state *lzmaState) {
    93  	if *state < litStates {
    94  		*state = stateLitLongrep
    95  	} else {
    96  		*state = stateNonlitRep
    97  	}
    98  }
    99  
   100  /* Indicate that the latest symbol was a short match. */
   101  func lzmaStateShortRep(state *lzmaState) {
   102  	if *state < litStates {
   103  		*state = stateLitShortrep
   104  	} else {
   105  		*state = stateNonlitRep
   106  	}
   107  }
   108  
   109  /* Test if the previous symbol was a literal. */
   110  func lzmaStateIsLiteral(state lzmaState) bool {
   111  	return state < litStates
   112  }
   113  
   114  /* Each literal coder is divided in three sections:
   115   *   - 0x001-0x0FF: Without match byte
   116   *   - 0x101-0x1FF: With match byte; match bit is 0
   117   *   - 0x201-0x2FF: With match byte; match bit is 1
   118   *
   119   * Match byte is used when the previous LZMA symbol was something else than
   120   * a literal (that is, it was some kind of match).
   121   */
   122  const literalCoderSize = 0x300
   123  
   124  /* Maximum number of literal coders */
   125  const literalCodersMax = 1 << 4
   126  
   127  /* Minimum length of a match is two bytes. */
   128  const matchLenMin = 2
   129  
   130  /* Match length is encoded with 4, 5, or 10 bits.
   131   *
   132   * Length   Bits
   133   *  2-9      4 = Choice=0 + 3 bits
   134   * 10-17     5 = Choice=1 + Choice2=0 + 3 bits
   135   * 18-273   10 = Choice=1 + Choice2=1 + 8 bits
   136   */
   137  const (
   138  	lenLowBits     = 3
   139  	lenLowSymbols  = 1 << lenLowBits
   140  	lenMidBits     = 3
   141  	lenMidSymbols  = 1 << lenMidBits
   142  	lenHighBits    = 8
   143  	lenHighSymbols = 1 << lenHighBits
   144  )
   145  
   146  /*
   147   * Different sets of probabilities are used for match distances that have
   148   * very short match length: Lengths of 2, 3, and 4 bytes have a separate
   149   * set of probabilities for each length. The matches with longer length
   150   * use a shared set of probabilities.
   151   */
   152  const distStates = 4
   153  
   154  /*
   155   * Get the index of the appropriate probability array for decoding
   156   * the distance slot.
   157   */
   158  func lzmaGetDistState(len uint32) uint32 {
   159  	if len < distStates+matchLenMin {
   160  		return len - matchLenMin
   161  	} else {
   162  		return distStates - 1
   163  	}
   164  }
   165  
   166  /*
   167   * The highest two bits of a 32-bit match distance are encoded using six bits.
   168   * This six-bit value is called a distance slot. This way encoding a 32-bit
   169   * value takes 6-36 bits, larger values taking more bits.
   170   */
   171  const (
   172  	distSlotBits = 6
   173  	distSlots    = 1 << distSlotBits
   174  )
   175  
   176  /* Match distances up to 127 are fully encoded using probabilities. Since
   177   * the highest two bits (distance slot) are always encoded using six bits,
   178   * the distances 0-3 don't need any additional bits to encode, since the
   179   * distance slot itself is the same as the actual distance. distModelStart
   180   * indicates the first distance slot where at least one additional bit is
   181   * needed.
   182   */
   183  const distModelStart = 4
   184  
   185  /*
   186   * Match distances greater than 127 are encoded in three pieces:
   187   *   - distance slot: the highest two bits
   188   *   - direct bits: 2-26 bits below the highest two bits
   189   *   - alignment bits: four lowest bits
   190   *
   191   * Direct bits don't use any probabilities.
   192   *
   193   * The distance slot value of 14 is for distances 128-191.
   194   */
   195  const distModelEnd = 14
   196  
   197  /* Distance slots that indicate a distance <= 127. */
   198  const (
   199  	fullDistancesBits = distModelEnd / 2
   200  	fullDistances     = 1 << fullDistancesBits
   201  )
   202  
   203  /*
   204   * For match distances greater than 127, only the highest two bits and the
   205   * lowest four bits (alignment) is encoded using probabilities.
   206   */
   207  const (
   208  	alignBits = 4
   209  	alignSize = 1 << alignBits
   210  )
   211  
   212  /* from linux/lib/xz/xz_dec_lzma2.c ***********************************/
   213  
   214  /*
   215   * Range decoder initialization eats the first five bytes of each LZMA chunk.
   216   */
   217  const rcInitBytes = 5
   218  
   219  /*
   220   * Minimum number of usable input buffer to safely decode one LZMA symbol.
   221   * The worst case is that we decode 22 bits using probabilities and 26
   222   * direct bits. This may decode at maximum of 20 bytes of input. However,
   223   * lzmaMain does an extra normalization before returning, thus we
   224   * need to put 21 here.
   225   */
   226  const lzmaInRequired = 21
   227  
   228  /*
   229   * Dictionary (history buffer)
   230   *
   231   * These are always true:
   232   *    start <= pos <= full <= end
   233   *    pos <= limit <= end
   234   *    end == size
   235   *    size <= sizeMax
   236   *    len(buf) <= size
   237   */
   238  type dictionary struct {
   239  	/* The history buffer */
   240  	buf []byte
   241  	/* Old position in buf (before decoding more data) */
   242  	start uint32
   243  	/* Position in buf */
   244  	pos uint32
   245  	/*
   246  	 * How full dictionary is. This is used to detect corrupt input that
   247  	 * would read beyond the beginning of the uncompressed stream.
   248  	 */
   249  	full uint32
   250  	/* Write limit; we don't write to buf[limit] or later bytes. */
   251  	limit uint32
   252  	/*
   253  	 * End of the dictionary buffer. This is the same as the
   254  	 * dictionary size.
   255  	 */
   256  	end uint32
   257  	/*
   258  	 * Size of the dictionary as specified in Block Header. This is used
   259  	 * together with "full" to detect corrupt input that would make us
   260  	 * read beyond the beginning of the uncompressed stream.
   261  	 */
   262  	size uint32
   263  	/* Maximum allowed dictionary size. */
   264  	sizeMax uint32
   265  }
   266  
   267  /* Range decoder */
   268  type rcDec struct {
   269  	rnge uint32
   270  	code uint32
   271  	/*
   272  	 * Number of initializing bytes remaining to be read
   273  	 * by rcReadInit.
   274  	 */
   275  	initBytesLeft uint32
   276  	/*
   277  	 * Buffer from which we read our input. It can be either
   278  	 * temp.buf or the caller-provided input buffer.
   279  	 */
   280  	in      []byte
   281  	inPos   int
   282  	inLimit int
   283  }
   284  
   285  /* Probabilities for a length decoder. */
   286  type lzmaLenDec struct {
   287  	/* Probability of match length being at least 10 */
   288  	choice uint16
   289  	/* Probability of match length being at least 18 */
   290  	choice2 uint16
   291  	/* Probabilities for match lengths 2-9 */
   292  	low [posStatesMax][lenLowSymbols]uint16
   293  	/* Probabilities for match lengths 10-17 */
   294  	mid [posStatesMax][lenMidSymbols]uint16
   295  	/* Probabilities for match lengths 18-273 */
   296  	high [lenHighSymbols]uint16
   297  }
   298  
   299  type lzmaDec struct {
   300  	/* Distances of latest four matches */
   301  	rep0 uint32
   302  	rep1 uint32
   303  	rep2 uint32
   304  	rep3 uint32
   305  	/* Types of the most recently seen LZMA symbols */
   306  	state lzmaState
   307  	/*
   308  	 * Length of a match. This is updated so that dictRepeat can
   309  	 * be called again to finish repeating the whole match.
   310  	 */
   311  	len uint32
   312  	/*
   313  	 * LZMA properties or related bit masks (number of literal
   314  	 * context bits, a mask derived from the number of literal
   315  	 * position bits, and a mask derived from the number
   316  	 * position bits)
   317  	 */
   318  	lc             uint32
   319  	literalPosMask uint32
   320  	posMask        uint32
   321  	/* If 1, it's a match. Otherwise it's a single 8-bit literal. */
   322  	isMatch [states][posStatesMax]uint16
   323  	/* If 1, it's a repeated match. The distance is one of rep0 .. rep3. */
   324  	isRep [states]uint16
   325  	/*
   326  	 * If 0, distance of a repeated match is rep0.
   327  	 * Otherwise check is_rep1.
   328  	 */
   329  	isRep0 [states]uint16
   330  	/*
   331  	 * If 0, distance of a repeated match is rep1.
   332  	 * Otherwise check is_rep2.
   333  	 */
   334  	isRep1 [states]uint16
   335  	/* If 0, distance of a repeated match is rep2. Otherwise it is rep3. */
   336  	isRep2 [states]uint16
   337  	/*
   338  	 * If 1, the repeated match has length of one byte. Otherwise
   339  	 * the length is decoded from rep_len_decoder.
   340  	 */
   341  	isRep0Long [states][posStatesMax]uint16
   342  	/*
   343  	 * Probability tree for the highest two bits of the match
   344  	 * distance. There is a separate probability tree for match
   345  	 * lengths of 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273].
   346  	 */
   347  	distSlot [distStates][distSlots]uint16
   348  	/*
   349  	 * Probility trees for additional bits for match distance
   350  	 * when the distance is in the range [4, 127].
   351  	 */
   352  	distSpecial [fullDistances - distModelEnd]uint16
   353  	/*
   354  	 * Probability tree for the lowest four bits of a match
   355  	 * distance that is equal to or greater than 128.
   356  	 */
   357  	distAlign [alignSize]uint16
   358  	/* Length of a normal match */
   359  	matchLenDec lzmaLenDec
   360  	/* Length of a repeated match */
   361  	repLenDec lzmaLenDec
   362  	/* Probabilities of literals */
   363  	literal [literalCodersMax][literalCoderSize]uint16
   364  }
   365  
   366  // type of lzma2Dec.sequence
   367  type lzma2Seq int
   368  
   369  const (
   370  	seqControl lzma2Seq = iota
   371  	seqUncompressed1
   372  	seqUncompressed2
   373  	seqCompressed0
   374  	seqCompressed1
   375  	seqProperties
   376  	seqLZMAPrepare
   377  	seqLZMARun
   378  	seqCopy
   379  )
   380  
   381  type lzma2Dec struct {
   382  	/* Position in xzDecLZMA2Run. */
   383  	sequence lzma2Seq
   384  	/* Next position after decoding the compressed size of the chunk. */
   385  	nextSequence lzma2Seq
   386  	/* Uncompressed size of LZMA chunk (2 MiB at maximum) */
   387  	uncompressed int
   388  	/*
   389  	 * Compressed size of LZMA chunk or compressed/uncompressed
   390  	 * size of uncompressed chunk (64 KiB at maximum)
   391  	 */
   392  	compressed int
   393  	/*
   394  	 * True if dictionary reset is needed. This is false before
   395  	 * the first chunk (LZMA or uncompressed).
   396  	 */
   397  	needDictReset bool
   398  	/*
   399  	 * True if new LZMA properties are needed. This is false
   400  	 * before the first LZMA chunk.
   401  	 */
   402  	needProps bool
   403  }
   404  
   405  type xzDecLZMA2 struct {
   406  	/*
   407  	 * The order below is important on x86 to reduce code size and
   408  	 * it shouldn't hurt on other platforms. Everything up to and
   409  	 * including lzma.pos_mask are in the first 128 bytes on x86-32,
   410  	 * which allows using smaller instructions to access those
   411  	 * variables. On x86-64, fewer variables fit into the first 128
   412  	 * bytes, but this is still the best order without sacrificing
   413  	 * the readability by splitting the structures.
   414  	 */
   415  	rc    rcDec
   416  	dict  dictionary
   417  	lzma2 lzma2Dec
   418  	lzma  lzmaDec
   419  	/*
   420  	 * Temporary buffer which holds small number of input bytes between
   421  	 * decoder calls. See lzma2LZMA for details.
   422  	 */
   423  	temp struct {
   424  		buf      []byte // slice buf will be backed by bufArray
   425  		bufArray [3 * lzmaInRequired]byte
   426  	}
   427  }
   428  
   429  /**************
   430   * Dictionary *
   431   **************/
   432  
   433  /*
   434   * Reset the dictionary state. When in single-call mode, set up the beginning
   435   * of the dictionary to point to the actual output buffer.
   436   */
   437  func dictReset(dict *dictionary, b *xzBuf) {
   438  	dict.start = 0
   439  	dict.pos = 0
   440  	dict.limit = 0
   441  	dict.full = 0
   442  }
   443  
   444  /* Set dictionary write limit */
   445  func dictLimit(dict *dictionary, outMax int) {
   446  	if dict.end-dict.pos <= uint32(outMax) {
   447  		dict.limit = dict.end
   448  	} else {
   449  		dict.limit = dict.pos + uint32(outMax)
   450  	}
   451  }
   452  
   453  /* Return true if at least one byte can be written into the dictionary. */
   454  func dictHasSpace(dict *dictionary) bool {
   455  	return dict.pos < dict.limit
   456  }
   457  
   458  /*
   459   * Get a byte from the dictionary at the given distance. The distance is
   460   * assumed to valid, or as a special case, zero when the dictionary is
   461   * still empty. This special case is needed for single-call decoding to
   462   * avoid writing a '\x00' to the end of the destination buffer.
   463   */
   464  func dictGet(dict *dictionary, dist uint32) uint32 {
   465  	var offset uint32 = dict.pos - dist - 1
   466  	if dist >= dict.pos {
   467  		offset += dict.end
   468  	}
   469  	if dict.full > 0 {
   470  		return uint32(dict.buf[offset])
   471  	}
   472  	return 0
   473  }
   474  
   475  /*
   476   * Put one byte into the dictionary. It is assumed that there is space for it.
   477   */
   478  func dictPut(dict *dictionary, byte byte) {
   479  	dict.buf[dict.pos] = byte
   480  	dict.pos++
   481  	if dict.full < dict.pos {
   482  		dict.full = dict.pos
   483  	}
   484  }
   485  
   486  /*
   487   * Repeat given number of bytes from the given distance. If the distance is
   488   * invalid, false is returned. On success, true is returned and *len is
   489   * updated to indicate how many bytes were left to be repeated.
   490   */
   491  func dictRepeat(dict *dictionary, len *uint32, dist uint32) bool {
   492  	var back uint32
   493  	var left uint32
   494  	if dist >= dict.full || dist >= dict.size {
   495  		return false
   496  	}
   497  	left = dict.limit - dict.pos
   498  	if left > *len {
   499  		left = *len
   500  	}
   501  	*len -= left
   502  	back = dict.pos - dist - 1
   503  	if dist >= dict.pos {
   504  		back += dict.end
   505  	}
   506  	for {
   507  		dict.buf[dict.pos] = dict.buf[back]
   508  		dict.pos++
   509  		back++
   510  		if back == dict.end {
   511  			back = 0
   512  		}
   513  		left--
   514  		if !(left > 0) {
   515  			break
   516  		}
   517  	}
   518  	if dict.full < dict.pos {
   519  		dict.full = dict.pos
   520  	}
   521  	return true
   522  }
   523  
   524  /* Copy uncompressed data as is from input to dictionary and output buffers. */
   525  func dictUncompressed(dict *dictionary, b *xzBuf, left *int) {
   526  	var copySize int
   527  	for *left > 0 && b.inPos < len(b.in) && b.outPos < len(b.out) {
   528  		copySize = len(b.in) - b.inPos
   529  		if copySize > len(b.out)-b.outPos {
   530  			copySize = len(b.out) - b.outPos
   531  		}
   532  		if copySize > int(dict.end-dict.pos) {
   533  			copySize = int(dict.end - dict.pos)
   534  		}
   535  		if copySize > *left {
   536  			copySize = *left
   537  		}
   538  		*left -= copySize
   539  		copy(dict.buf[dict.pos:], b.in[b.inPos:b.inPos+copySize])
   540  		dict.pos += uint32(copySize)
   541  		if dict.full < dict.pos {
   542  			dict.full = dict.pos
   543  		}
   544  		if dict.pos == dict.end {
   545  			dict.pos = 0
   546  		}
   547  		copy(b.out[b.outPos:], b.in[b.inPos:b.inPos+copySize])
   548  		dict.start = dict.pos
   549  		b.outPos += copySize
   550  		b.inPos += copySize
   551  	}
   552  }
   553  
   554  /*
   555   * Flush pending data from dictionary to b.out. It is assumed that there is
   556   * enough space in b.out. This is guaranteed because caller uses dictLimit
   557   * before decoding data into the dictionary.
   558   */
   559  func dictFlush(dict *dictionary, b *xzBuf) int {
   560  	var copySize int = int(dict.pos - dict.start)
   561  	if dict.pos == dict.end {
   562  		dict.pos = 0
   563  	}
   564  	copy(b.out[b.outPos:], dict.buf[dict.start:dict.start+uint32(copySize)])
   565  	dict.start = dict.pos
   566  	b.outPos += copySize
   567  	return copySize
   568  }
   569  
   570  /*****************
   571   * Range decoder *
   572   *****************/
   573  
   574  /* Reset the range decoder. */
   575  func rcReset(rc *rcDec) {
   576  	rc.rnge = ^uint32(0)
   577  	rc.code = 0
   578  	rc.initBytesLeft = rcInitBytes
   579  }
   580  
   581  /*
   582   * Read the first five initial bytes into rc->code if they haven't been
   583   * read already. (Yes, the first byte gets completely ignored.)
   584   */
   585  func rcReadInit(rc *rcDec, b *xzBuf) bool {
   586  	for rc.initBytesLeft > 0 {
   587  		if b.inPos == len(b.in) {
   588  			return false
   589  		}
   590  		rc.code = rc.code<<8 + uint32(b.in[b.inPos])
   591  		b.inPos++
   592  		rc.initBytesLeft--
   593  	}
   594  	return true
   595  }
   596  
   597  /* Return true if there may not be enough input for the next decoding loop. */
   598  func rcLimitExceeded(rc *rcDec) bool {
   599  	return rc.inPos > rc.inLimit
   600  }
   601  
   602  /*
   603   * Return true if it is possible (from point of view of range decoder) that
   604   * we have reached the end of the LZMA chunk.
   605   */
   606  func rcIsFinished(rc *rcDec) bool {
   607  	return rc.code == 0
   608  }
   609  
   610  /* Read the next input byte if needed. */
   611  func rcNormalize(rc *rcDec) {
   612  	if rc.rnge < rcTopValue {
   613  		rc.rnge <<= rcShiftBits
   614  		rc.code = rc.code<<rcShiftBits + uint32(rc.in[rc.inPos])
   615  		rc.inPos++
   616  	}
   617  }
   618  
   619  /* Decode one bit. */
   620  func rcBit(rc *rcDec, prob *uint16) bool {
   621  	var bound uint32
   622  	var bit bool
   623  	rcNormalize(rc)
   624  	bound = (rc.rnge >> rcBitModelTotalBits) * uint32(*prob)
   625  	if rc.code < bound {
   626  		rc.rnge = bound
   627  		*prob += (rcBitModelTotal - *prob) >> rcMoveBits
   628  		bit = false
   629  	} else {
   630  		rc.rnge -= bound
   631  		rc.code -= bound
   632  		*prob -= *prob >> rcMoveBits
   633  		bit = true
   634  	}
   635  	return bit
   636  }
   637  
   638  /* Decode a bittree starting from the most significant bit. */
   639  func rcBittree(rc *rcDec, probs []uint16, limit uint32) uint32 {
   640  	var symbol uint32 = 1
   641  	for {
   642  		if rcBit(rc, &probs[symbol-1]) {
   643  			symbol = symbol<<1 + 1
   644  		} else {
   645  			symbol <<= 1
   646  		}
   647  		if !(symbol < limit) {
   648  			break
   649  		}
   650  	}
   651  	return symbol
   652  }
   653  
   654  /* Decode a bittree starting from the least significant bit. */
   655  func rcBittreeReverse(rc *rcDec, probs []uint16, dest *uint32, limit uint32) {
   656  	var symbol uint32 = 1
   657  	var i uint32 = 0
   658  	for {
   659  		if rcBit(rc, &probs[symbol-1]) {
   660  			symbol = symbol<<1 + 1
   661  			*dest += 1 << i
   662  		} else {
   663  			symbol <<= 1
   664  		}
   665  		i++
   666  		if !(i < limit) {
   667  			break
   668  		}
   669  	}
   670  }
   671  
   672  /* Decode direct bits (fixed fifty-fifty probability) */
   673  func rcDirect(rc *rcDec, dest *uint32, limit uint32) {
   674  	var mask uint32
   675  	for {
   676  		rcNormalize(rc)
   677  		rc.rnge >>= 1
   678  		rc.code -= rc.rnge
   679  		mask = 0 - rc.code>>31
   680  		rc.code += rc.rnge & mask
   681  		*dest = *dest<<1 + mask + 1
   682  		limit--
   683  		if !(limit > 0) {
   684  			break
   685  		}
   686  	}
   687  }
   688  
   689  /********
   690   * LZMA *
   691   ********/
   692  
   693  /* Get pointer to literal coder probability array. */
   694  func lzmaLiteralProbs(s *xzDecLZMA2) []uint16 {
   695  	var prevByte uint32 = dictGet(&s.dict, 0)
   696  	var low uint32 = prevByte >> (8 - s.lzma.lc)
   697  	var high uint32 = (s.dict.pos & s.lzma.literalPosMask) << s.lzma.lc
   698  	return s.lzma.literal[low+high][:]
   699  }
   700  
   701  /* Decode a literal (one 8-bit byte) */
   702  func lzmaLiteral(s *xzDecLZMA2) {
   703  	var probs []uint16
   704  	var symbol uint32
   705  	var matchByte uint32
   706  	var matchBit uint32
   707  	var offset uint32
   708  	var i uint32
   709  	probs = lzmaLiteralProbs(s)
   710  	if lzmaStateIsLiteral(s.lzma.state) {
   711  		symbol = rcBittree(&s.rc, probs[1:], 0x100)
   712  	} else {
   713  		symbol = 1
   714  		matchByte = dictGet(&s.dict, s.lzma.rep0) << 1
   715  		offset = 0x100
   716  		for {
   717  			matchBit = matchByte & offset
   718  			matchByte <<= 1
   719  			i = offset + matchBit + symbol
   720  			if rcBit(&s.rc, &probs[i]) {
   721  				symbol = symbol<<1 + 1
   722  				offset &= matchBit
   723  			} else {
   724  				symbol <<= 1
   725  				offset &= ^matchBit
   726  			}
   727  			if !(symbol < 0x100) {
   728  				break
   729  			}
   730  		}
   731  	}
   732  	dictPut(&s.dict, byte(symbol))
   733  	lzmaStateLiteral(&s.lzma.state)
   734  }
   735  
   736  /* Decode the length of the match into s.lzma.len. */
   737  func lzmaLen(s *xzDecLZMA2, l *lzmaLenDec, posState uint32) {
   738  	var probs []uint16
   739  	var limit uint32
   740  	switch {
   741  	case !rcBit(&s.rc, &l.choice):
   742  		probs = l.low[posState][:]
   743  		limit = lenLowSymbols
   744  		s.lzma.len = matchLenMin
   745  	case !rcBit(&s.rc, &l.choice2):
   746  		probs = l.mid[posState][:]
   747  		limit = lenMidSymbols
   748  		s.lzma.len = matchLenMin + lenLowSymbols
   749  	default:
   750  		probs = l.high[:]
   751  		limit = lenHighSymbols
   752  		s.lzma.len = matchLenMin + lenLowSymbols + lenMidSymbols
   753  	}
   754  	s.lzma.len += rcBittree(&s.rc, probs[1:], limit) - limit
   755  }
   756  
   757  /* Decode a match. The distance will be stored in s.lzma.rep0. */
   758  func lzmaMatch(s *xzDecLZMA2, posState uint32) {
   759  	var probs []uint16
   760  	var distSlot uint32
   761  	var limit uint32
   762  	lzmaStateMatch(&s.lzma.state)
   763  	s.lzma.rep3 = s.lzma.rep2
   764  	s.lzma.rep2 = s.lzma.rep1
   765  	s.lzma.rep1 = s.lzma.rep0
   766  	lzmaLen(s, &s.lzma.matchLenDec, posState)
   767  	probs = s.lzma.distSlot[lzmaGetDistState(s.lzma.len)][:]
   768  	distSlot = rcBittree(&s.rc, probs[1:], distSlots) - distSlots
   769  	if distSlot < distModelStart {
   770  		s.lzma.rep0 = distSlot
   771  	} else {
   772  		limit = distSlot>>1 - 1
   773  		s.lzma.rep0 = 2 + distSlot&1
   774  		if distSlot < distModelEnd {
   775  			s.lzma.rep0 <<= limit
   776  			probs = s.lzma.distSpecial[s.lzma.rep0-distSlot:]
   777  			rcBittreeReverse(&s.rc, probs, &s.lzma.rep0, limit)
   778  		} else {
   779  			rcDirect(&s.rc, &s.lzma.rep0, limit-alignBits)
   780  			s.lzma.rep0 <<= alignBits
   781  			rcBittreeReverse(
   782  				&s.rc, s.lzma.distAlign[1:], &s.lzma.rep0, alignBits)
   783  		}
   784  	}
   785  }
   786  
   787  /*
   788   * Decode a repeated match. The distance is one of the four most recently
   789   * seen matches. The distance will be stored in s.lzma.rep0.
   790   */
   791  func lzmaRepMatch(s *xzDecLZMA2, posState uint32) {
   792  	var tmp uint32
   793  	if !rcBit(&s.rc, &s.lzma.isRep0[s.lzma.state]) {
   794  		if !rcBit(&s.rc, &s.lzma.isRep0Long[s.lzma.state][posState]) {
   795  			lzmaStateShortRep(&s.lzma.state)
   796  			s.lzma.len = 1
   797  			return
   798  		}
   799  	} else {
   800  		if !rcBit(&s.rc, &s.lzma.isRep1[s.lzma.state]) {
   801  			tmp = s.lzma.rep1
   802  		} else {
   803  			if !rcBit(&s.rc, &s.lzma.isRep2[s.lzma.state]) {
   804  				tmp = s.lzma.rep2
   805  			} else {
   806  				tmp = s.lzma.rep3
   807  				s.lzma.rep3 = s.lzma.rep2
   808  			}
   809  			s.lzma.rep2 = s.lzma.rep1
   810  		}
   811  		s.lzma.rep1 = s.lzma.rep0
   812  		s.lzma.rep0 = tmp
   813  	}
   814  	lzmaStateLongRep(&s.lzma.state)
   815  	lzmaLen(s, &s.lzma.repLenDec, posState)
   816  }
   817  
   818  /* LZMA decoder core */
   819  func lzmaMain(s *xzDecLZMA2) bool {
   820  	var posState uint32
   821  	/*
   822  	 * If the dictionary was reached during the previous call, try to
   823  	 * finish the possibly pending repeat in the dictionary.
   824  	 */
   825  	if dictHasSpace(&s.dict) && s.lzma.len > 0 {
   826  		dictRepeat(&s.dict, &s.lzma.len, s.lzma.rep0)
   827  	}
   828  	/*
   829  	 * Decode more LZMA symbols. One iteration may consume up to
   830  	 * lzmaInRequired - 1 bytes.
   831  	 */
   832  	for dictHasSpace(&s.dict) && !rcLimitExceeded(&s.rc) {
   833  		posState = s.dict.pos & s.lzma.posMask
   834  		if !rcBit(&s.rc, &s.lzma.isMatch[s.lzma.state][posState]) {
   835  			lzmaLiteral(s)
   836  		} else {
   837  			if rcBit(&s.rc, &s.lzma.isRep[s.lzma.state]) {
   838  				lzmaRepMatch(s, posState)
   839  			} else {
   840  				lzmaMatch(s, posState)
   841  			}
   842  			if !dictRepeat(&s.dict, &s.lzma.len, s.lzma.rep0) {
   843  				return false
   844  			}
   845  		}
   846  	}
   847  	/*
   848  	 * Having the range decoder always normalized when we are outside
   849  	 * this function makes it easier to correctly handle end of the chunk.
   850  	 */
   851  	rcNormalize(&s.rc)
   852  	return true
   853  }
   854  
   855  /*
   856   * Reset the LZMA decoder and range decoder state. Dictionary is not reset
   857   * here, because LZMA state may be reset without resetting the dictionary.
   858   */
   859  func lzmaReset(s *xzDecLZMA2) {
   860  	s.lzma.state = stateLitLit
   861  	s.lzma.rep0 = 0
   862  	s.lzma.rep1 = 0
   863  	s.lzma.rep2 = 0
   864  	s.lzma.rep3 = 0
   865  	/* All probabilities are initialized to the same value, v */
   866  	v := uint16(rcBitModelTotal / 2)
   867  	s.lzma.matchLenDec.choice = v
   868  	s.lzma.matchLenDec.choice2 = v
   869  	s.lzma.repLenDec.choice = v
   870  	s.lzma.repLenDec.choice2 = v
   871  	for _, m := range [][]uint16{
   872  		s.lzma.isRep[:], s.lzma.isRep0[:], s.lzma.isRep1[:],
   873  		s.lzma.isRep2[:], s.lzma.distSpecial[:], s.lzma.distAlign[:],
   874  		s.lzma.matchLenDec.high[:], s.lzma.repLenDec.high[:],
   875  	} {
   876  		for j := range m {
   877  			m[j] = v
   878  		}
   879  	}
   880  	for i := range s.lzma.isMatch {
   881  		for j := range s.lzma.isMatch[i] {
   882  			s.lzma.isMatch[i][j] = v
   883  		}
   884  	}
   885  	for i := range s.lzma.isRep0Long {
   886  		for j := range s.lzma.isRep0Long[i] {
   887  			s.lzma.isRep0Long[i][j] = v
   888  		}
   889  	}
   890  	for i := range s.lzma.distSlot {
   891  		for j := range s.lzma.distSlot[i] {
   892  			s.lzma.distSlot[i][j] = v
   893  		}
   894  	}
   895  	for i := range s.lzma.literal {
   896  		for j := range s.lzma.literal[i] {
   897  			s.lzma.literal[i][j] = v
   898  		}
   899  	}
   900  	for i := range s.lzma.matchLenDec.low {
   901  		for j := range s.lzma.matchLenDec.low[i] {
   902  			s.lzma.matchLenDec.low[i][j] = v
   903  		}
   904  	}
   905  	for i := range s.lzma.matchLenDec.mid {
   906  		for j := range s.lzma.matchLenDec.mid[i] {
   907  			s.lzma.matchLenDec.mid[i][j] = v
   908  		}
   909  	}
   910  	for i := range s.lzma.repLenDec.low {
   911  		for j := range s.lzma.repLenDec.low[i] {
   912  			s.lzma.repLenDec.low[i][j] = v
   913  		}
   914  	}
   915  	for i := range s.lzma.repLenDec.mid {
   916  		for j := range s.lzma.repLenDec.mid[i] {
   917  			s.lzma.repLenDec.mid[i][j] = v
   918  		}
   919  	}
   920  	rcReset(&s.rc)
   921  }
   922  
   923  /*
   924   * Decode and validate LZMA properties (lc/lp/pb) and calculate the bit masks
   925   * from the decoded lp and pb values. On success, the LZMA decoder state is
   926   * reset and true is returned.
   927   */
   928  func lzmaProps(s *xzDecLZMA2, props byte) bool {
   929  	if props > (4*5+4)*9+8 {
   930  		return false
   931  	}
   932  	s.lzma.posMask = 0
   933  	for props >= 9*5 {
   934  		props -= 9 * 5
   935  		s.lzma.posMask++
   936  	}
   937  	s.lzma.posMask = 1<<s.lzma.posMask - 1
   938  	s.lzma.literalPosMask = 0
   939  	for props >= 9 {
   940  		props -= 9
   941  		s.lzma.literalPosMask++
   942  	}
   943  	s.lzma.lc = uint32(props)
   944  	if s.lzma.lc+s.lzma.literalPosMask > 4 {
   945  		return false
   946  	}
   947  	s.lzma.literalPosMask = 1<<s.lzma.literalPosMask - 1
   948  	lzmaReset(s)
   949  	return true
   950  }
   951  
   952  /*********
   953   * LZMA2 *
   954   *********/
   955  
   956  /*
   957   * The LZMA decoder assumes that if the input limit (s.rc.inLimit) hasn't
   958   * been exceeded, it is safe to read up to lzmaInRequired bytes. This
   959   * wrapper function takes care of making the LZMA decoder's assumption safe.
   960   *
   961   * As long as there is plenty of input left to be decoded in the current LZMA
   962   * chunk, we decode directly from the caller-supplied input buffer until
   963   * there's lzmaInRequired bytes left. Those remaining bytes are copied into
   964   * s.temp.buf, which (hopefully) gets filled on the next call to this
   965   * function. We decode a few bytes from the temporary buffer so that we can
   966   * continue decoding from the caller-supplied input buffer again.
   967   */
   968  func lzma2LZMA(s *xzDecLZMA2, b *xzBuf) bool {
   969  	var inAvail int
   970  	var tmp int
   971  	inAvail = len(b.in) - b.inPos
   972  	if len(s.temp.buf) > 0 || s.lzma2.compressed == 0 {
   973  		tmp = 2*lzmaInRequired - len(s.temp.buf)
   974  		if tmp > s.lzma2.compressed-len(s.temp.buf) {
   975  			tmp = s.lzma2.compressed - len(s.temp.buf)
   976  		}
   977  		if tmp > inAvail {
   978  			tmp = inAvail
   979  		}
   980  		copy(s.temp.bufArray[len(s.temp.buf):], b.in[b.inPos:b.inPos+tmp])
   981  		switch {
   982  		case len(s.temp.buf)+tmp == s.lzma2.compressed:
   983  			for i := len(s.temp.buf) + tmp; i < len(s.temp.bufArray); i++ {
   984  				s.temp.bufArray[i] = 0
   985  			}
   986  			s.rc.inLimit = len(s.temp.buf) + tmp
   987  		case len(s.temp.buf)+tmp < lzmaInRequired:
   988  			s.temp.buf = s.temp.bufArray[:len(s.temp.buf)+tmp]
   989  			b.inPos += tmp
   990  			return true
   991  		default:
   992  			s.rc.inLimit = len(s.temp.buf) + tmp - lzmaInRequired
   993  		}
   994  		s.rc.in = s.temp.bufArray[:]
   995  		s.rc.inPos = 0
   996  		if !lzmaMain(s) || s.rc.inPos > len(s.temp.buf)+tmp {
   997  			return false
   998  		}
   999  		s.lzma2.compressed -= s.rc.inPos
  1000  		if s.rc.inPos < len(s.temp.buf) {
  1001  			copy(s.temp.buf, s.temp.buf[s.rc.inPos:])
  1002  			s.temp.buf = s.temp.buf[:len(s.temp.buf)-s.rc.inPos]
  1003  			return true
  1004  		}
  1005  		b.inPos += s.rc.inPos - len(s.temp.buf)
  1006  		s.temp.buf = nil
  1007  	}
  1008  	inAvail = len(b.in) - b.inPos
  1009  	if inAvail >= lzmaInRequired {
  1010  		s.rc.in = b.in
  1011  		s.rc.inPos = b.inPos
  1012  		if inAvail >= s.lzma2.compressed+lzmaInRequired {
  1013  			s.rc.inLimit = b.inPos + s.lzma2.compressed
  1014  		} else {
  1015  			s.rc.inLimit = len(b.in) - lzmaInRequired
  1016  		}
  1017  		if !lzmaMain(s) {
  1018  			return false
  1019  		}
  1020  		inAvail = s.rc.inPos - b.inPos
  1021  		if inAvail > s.lzma2.compressed {
  1022  			return false
  1023  		}
  1024  		s.lzma2.compressed -= inAvail
  1025  		b.inPos = s.rc.inPos
  1026  	}
  1027  	inAvail = len(b.in) - b.inPos
  1028  	if inAvail < lzmaInRequired {
  1029  		if inAvail > s.lzma2.compressed {
  1030  			inAvail = s.lzma2.compressed
  1031  		}
  1032  		s.temp.buf = s.temp.bufArray[:inAvail]
  1033  		copy(s.temp.buf, b.in[b.inPos:])
  1034  		b.inPos += inAvail
  1035  	}
  1036  	return true
  1037  }
  1038  
  1039  /*
  1040   * Take care of the LZMA2 control layer, and forward the job of actual LZMA
  1041   * decoding or copying of uncompressed chunks to other functions.
  1042   */
  1043  func xzDecLZMA2Run(s *xzDecLZMA2, b *xzBuf) xzRet {
  1044  	var tmp int
  1045  	for b.inPos < len(b.in) || s.lzma2.sequence == seqLZMARun {
  1046  		switch s.lzma2.sequence {
  1047  		case seqControl:
  1048  			/*
  1049  			 * LZMA2 control byte
  1050  			 *
  1051  			 * Exact values:
  1052  			 *   0x00   End marker
  1053  			 *   0x01   Dictionary reset followed by
  1054  			 *          an uncompressed chunk
  1055  			 *   0x02   Uncompressed chunk (no dictionary reset)
  1056  			 *
  1057  			 * Highest three bits (s.control & 0xE0):
  1058  			 *   0xE0   Dictionary reset, new properties and state
  1059  			 *          reset, followed by LZMA compressed chunk
  1060  			 *   0xC0   New properties and state reset, followed
  1061  			 *          by LZMA compressed chunk (no dictionary
  1062  			 *          reset)
  1063  			 *   0xA0   State reset using old properties,
  1064  			 *          followed by LZMA compressed chunk (no
  1065  			 *          dictionary reset)
  1066  			 *   0x80   LZMA chunk (no dictionary or state reset)
  1067  			 *
  1068  			 * For LZMA compressed chunks, the lowest five bits
  1069  			 * (s.control & 1F) are the highest bits of the
  1070  			 * uncompressed size (bits 16-20).
  1071  			 *
  1072  			 * A new LZMA2 stream must begin with a dictionary
  1073  			 * reset. The first LZMA chunk must set new
  1074  			 * properties and reset the LZMA state.
  1075  			 *
  1076  			 * Values that don't match anything described above
  1077  			 * are invalid and we return xzDataError.
  1078  			 */
  1079  			tmp = int(b.in[b.inPos])
  1080  			b.inPos++
  1081  			if tmp == 0x00 {
  1082  				return xzStreamEnd
  1083  			}
  1084  			switch {
  1085  			case tmp >= 0xe0 || tmp == 0x01:
  1086  				s.lzma2.needProps = true
  1087  				s.lzma2.needDictReset = false
  1088  				dictReset(&s.dict, b)
  1089  			case s.lzma2.needDictReset:
  1090  				return xzDataError
  1091  			}
  1092  			if tmp >= 0x80 {
  1093  				s.lzma2.uncompressed = (tmp & 0x1f) << 16
  1094  				s.lzma2.sequence = seqUncompressed1
  1095  				switch {
  1096  				case tmp >= 0xc0:
  1097  					/*
  1098  					 * When there are new properties,
  1099  					 * state reset is done at
  1100  					 * seqProperties.
  1101  					 */
  1102  					s.lzma2.needProps = false
  1103  					s.lzma2.nextSequence = seqProperties
  1104  				case s.lzma2.needProps:
  1105  					return xzDataError
  1106  				default:
  1107  					s.lzma2.nextSequence = seqLZMAPrepare
  1108  					if tmp >= 0xa0 {
  1109  						lzmaReset(s)
  1110  					}
  1111  				}
  1112  			} else {
  1113  				if tmp > 0x02 {
  1114  					return xzDataError
  1115  				}
  1116  				s.lzma2.sequence = seqCompressed0
  1117  				s.lzma2.nextSequence = seqCopy
  1118  			}
  1119  		case seqUncompressed1:
  1120  			s.lzma2.uncompressed += int(b.in[b.inPos]) << 8
  1121  			b.inPos++
  1122  			s.lzma2.sequence = seqUncompressed2
  1123  		case seqUncompressed2:
  1124  			s.lzma2.uncompressed += int(b.in[b.inPos]) + 1
  1125  			b.inPos++
  1126  			s.lzma2.sequence = seqCompressed0
  1127  		case seqCompressed0:
  1128  			s.lzma2.compressed += int(b.in[b.inPos]) << 8
  1129  			b.inPos++
  1130  			s.lzma2.sequence = seqCompressed1
  1131  		case seqCompressed1:
  1132  			s.lzma2.compressed += int(b.in[b.inPos]) + 1
  1133  			b.inPos++
  1134  			s.lzma2.sequence = s.lzma2.nextSequence
  1135  		case seqProperties:
  1136  			if !lzmaProps(s, b.in[b.inPos]) {
  1137  				return xzDataError
  1138  			}
  1139  			b.inPos++
  1140  			s.lzma2.sequence = seqLZMAPrepare
  1141  			fallthrough
  1142  		case seqLZMAPrepare:
  1143  			if s.lzma2.compressed < rcInitBytes {
  1144  				return xzDataError
  1145  			}
  1146  			if !rcReadInit(&s.rc, b) {
  1147  				return xzOK
  1148  			}
  1149  			s.lzma2.compressed -= rcInitBytes
  1150  			s.lzma2.sequence = seqLZMARun
  1151  			fallthrough
  1152  		case seqLZMARun:
  1153  			/*
  1154  			 * Set dictionary limit to indicate how much we want
  1155  			 * to be encoded at maximum. Decode new data into the
  1156  			 * dictionary. Flush the new data from dictionary to
  1157  			 * b.out. Check if we finished decoding this chunk.
  1158  			 * In case the dictionary got full but we didn't fill
  1159  			 * the output buffer yet, we may run this loop
  1160  			 * multiple times without changing s.lzma2.sequence.
  1161  			 */
  1162  			outMax := len(b.out) - b.outPos
  1163  			if outMax > s.lzma2.uncompressed {
  1164  				outMax = s.lzma2.uncompressed
  1165  			}
  1166  			dictLimit(&s.dict, outMax)
  1167  			if !lzma2LZMA(s, b) {
  1168  				return xzDataError
  1169  			}
  1170  			s.lzma2.uncompressed -= dictFlush(&s.dict, b)
  1171  			switch {
  1172  			case s.lzma2.uncompressed == 0:
  1173  				if s.lzma2.compressed > 0 || s.lzma.len > 0 ||
  1174  					!rcIsFinished(&s.rc) {
  1175  					return xzDataError
  1176  				}
  1177  				rcReset(&s.rc)
  1178  				s.lzma2.sequence = seqControl
  1179  			case b.outPos == len(b.out) ||
  1180  				b.inPos == len(b.in) &&
  1181  					len(s.temp.buf) < s.lzma2.compressed:
  1182  				return xzOK
  1183  			}
  1184  		case seqCopy:
  1185  			dictUncompressed(&s.dict, b, &s.lzma2.compressed)
  1186  			if s.lzma2.compressed > 0 {
  1187  				return xzOK
  1188  			}
  1189  			s.lzma2.sequence = seqControl
  1190  		}
  1191  	}
  1192  	return xzOK
  1193  }
  1194  
  1195  /*
  1196   * Allocate memory for LZMA2 decoder. xzDecLZMA2Reset must be used
  1197   * before calling xzDecLZMA2Run.
  1198   */
  1199  func xzDecLZMA2Create(dictMax uint32) *xzDecLZMA2 {
  1200  	s := new(xzDecLZMA2)
  1201  	s.dict.sizeMax = dictMax
  1202  	return s
  1203  }
  1204  
  1205  /*
  1206   * Decode the LZMA2 properties (one byte) and reset the decoder. Return
  1207   * xzOK on success, xzMemlimitError if the preallocated dictionary is not
  1208   * big enough, and xzOptionsError if props indicates something that this
  1209   * decoder doesn't support.
  1210   */
  1211  func xzDecLZMA2Reset(s *xzDecLZMA2, props byte) xzRet {
  1212  	if props > 40 {
  1213  		return xzOptionsError // Bigger than 4 GiB
  1214  	}
  1215  	if props == 40 {
  1216  		s.dict.size = ^uint32(0)
  1217  	} else {
  1218  		s.dict.size = uint32(2 + props&1)
  1219  		s.dict.size <<= props>>1 + 11
  1220  	}
  1221  	if s.dict.size > s.dict.sizeMax {
  1222  		return xzMemlimitError
  1223  	}
  1224  	s.dict.end = s.dict.size
  1225  	if len(s.dict.buf) < int(s.dict.size) {
  1226  		s.dict.buf = make([]byte, s.dict.size)
  1227  	}
  1228  	s.lzma.len = 0
  1229  	s.lzma2.sequence = seqControl
  1230  	s.lzma2.compressed = 0
  1231  	s.lzma2.uncompressed = 0
  1232  	s.lzma2.needDictReset = true
  1233  	s.temp.buf = nil
  1234  	return xzOK
  1235  }
  1236  

View as plain text