token.go

     1  // Copyright 2009 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 flate
     6  
     7  import (
     8  	"math"
     9  )
    10  
    11  const (
    12  	// Token is a compound value:
    13  	// bits 0-16  xoffset = offset - MIN_OFFSET_SIZE, or literal - 16 bits
    14  	// bits 16-22 offset code - 5 bits
    15  	// bits 22-30 xlength = length - MIN_MATCH_LENGTH - 8 bits
    16  	// bits 30-32 type, 0 = literal  1=EOF  2=Match   3=Unused - 2 bits
    17  	lengthShift         = 22
    18  	offsetMask          = 1<<lengthShift - 1
    19  	typeMask            = 3 << 30
    20  	matchType           = 1 << 30
    21  	matchOffsetOnlyMask = 0xffff
    22  )
    23  
    24  // The length code for length X (MIN_MATCH_LENGTH <= X <= MAX_MATCH_LENGTH)
    25  // is lengthCodes[length - MIN_MATCH_LENGTH]
    26  var lengthCodes = [256]uint8{
    27  	0, 1, 2, 3, 4, 5, 6, 7, 8, 8,
    28  	9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
    29  	13, 13, 13, 13, 14, 14, 14, 14, 15, 15,
    30  	15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
    31  	17, 17, 17, 17, 17, 17, 17, 17, 18, 18,
    32  	18, 18, 18, 18, 18, 18, 19, 19, 19, 19,
    33  	19, 19, 19, 19, 20, 20, 20, 20, 20, 20,
    34  	20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
    35  	21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
    36  	21, 21, 21, 21, 21, 21, 22, 22, 22, 22,
    37  	22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
    38  	22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
    39  	23, 23, 23, 23, 23, 23, 23, 23, 24, 24,
    40  	24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
    41  	24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
    42  	24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
    43  	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
    44  	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
    45  	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
    46  	25, 25, 26, 26, 26, 26, 26, 26, 26, 26,
    47  	26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
    48  	26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
    49  	26, 26, 26, 26, 27, 27, 27, 27, 27, 27,
    50  	27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
    51  	27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
    52  	27, 27, 27, 27, 27, 28,
    53  }
    54  
    55  // lengthCodes1 is length codes, but starting at 1.
    56  var lengthCodes1 = [256]uint8{
    57  	1, 2, 3, 4, 5, 6, 7, 8, 9, 9,
    58  	10, 10, 11, 11, 12, 12, 13, 13, 13, 13,
    59  	14, 14, 14, 14, 15, 15, 15, 15, 16, 16,
    60  	16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
    61  	18, 18, 18, 18, 18, 18, 18, 18, 19, 19,
    62  	19, 19, 19, 19, 19, 19, 20, 20, 20, 20,
    63  	20, 20, 20, 20, 21, 21, 21, 21, 21, 21,
    64  	21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
    65  	22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
    66  	22, 22, 22, 22, 22, 22, 23, 23, 23, 23,
    67  	23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
    68  	23, 23, 24, 24, 24, 24, 24, 24, 24, 24,
    69  	24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
    70  	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
    71  	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
    72  	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
    73  	26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
    74  	26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
    75  	26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
    76  	26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
    77  	27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
    78  	27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
    79  	27, 27, 27, 27, 28, 28, 28, 28, 28, 28,
    80  	28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
    81  	28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
    82  	28, 28, 28, 28, 28, 29,
    83  }
    84  
    85  var offsetCodes = [256]uint32{
    86  	0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
    87  	8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,
    88  	10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
    89  	11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
    90  	12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
    91  	12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
    92  	13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
    93  	13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
    94  	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
    95  	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
    96  	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
    97  	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
    98  	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
    99  	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
   100  	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
   101  	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
   102  }
   103  
   104  // offsetCodes14 are offsetCodes, but with 14 added.
   105  var offsetCodes14 = [256]uint32{
   106  	14, 15, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
   107  	22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
   108  	24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
   109  	25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
   110  	26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
   111  	26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
   112  	27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
   113  	27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
   114  	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
   115  	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
   116  	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
   117  	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
   118  	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
   119  	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
   120  	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
   121  	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
   122  }
   123  
   124  // A token is a token that will be written to output stream.
   125  // It is either a literal or a match with offset and length.
   126  type token uint32
   127  
   128  // tokens are compound values as described above.
   129  // Histograms are created as tokens are added.
   130  // A full block is allocated.
   131  type tokens struct {
   132  	extraHist [32]uint16  // codes 256->maxnumlit
   133  	offHist   [32]uint16  // offset codes
   134  	litHist   [256]uint16 // codes 0->255
   135  	nFilled   int
   136  	n         uint16 // Must be able to contain maxStoreBlockSize
   137  	tokens    [65536]token
   138  }
   139  
   140  // Reset resets the tokens and histograms.
   141  func (t *tokens) Reset() {
   142  	if t.n == 0 {
   143  		return
   144  	}
   145  	t.n = 0
   146  	t.nFilled = 0
   147  	clear(t.litHist[:])
   148  	clear(t.extraHist[:])
   149  	clear(t.offHist[:])
   150  }
   151  
   152  // indexTokens creates tokens from a slice of unindexed tokens.
   153  func indexTokens(in []token) tokens {
   154  	var t tokens
   155  	t.indexTokens(in)
   156  	return t
   157  }
   158  
   159  // indexTokens clears and sets t from a slice of unindexed tokens.
   160  func (t *tokens) indexTokens(in []token) {
   161  	t.Reset()
   162  	for _, tok := range in {
   163  		if tok < matchType {
   164  			t.AddLiteral(tok.literal())
   165  			continue
   166  		}
   167  		t.AddMatch(uint32(tok.length()), tok.offset()&matchOffsetOnlyMask)
   168  	}
   169  }
   170  
   171  // emitLiterals writes a literal chunk and returns the number of bytes written.
   172  func emitLiterals(dst *tokens, lit []byte) {
   173  	for _, v := range lit {
   174  		dst.tokens[dst.n] = token(v)
   175  		dst.litHist[v]++
   176  		dst.n++
   177  	}
   178  }
   179  
   180  // AddLiteral adds a single literal to the tokens.
   181  func (t *tokens) AddLiteral(lit byte) {
   182  	t.tokens[t.n] = token(lit)
   183  	t.litHist[lit]++
   184  	t.n++
   185  }
   186  
   187  // mFastLog2 returns a fast approximation of log2(val).
   188  // From https://stackoverflow.com/a/28730362.
   189  func mFastLog2(val float32) float32 {
   190  	ux := int32(math.Float32bits(val))
   191  	log2 := (float32)(((ux >> 23) & 255) - 128)
   192  	ux &= -0x7f800001
   193  	ux += 127 << 23
   194  	uval := math.Float32frombits(uint32(ux))
   195  	log2 += ((-0.34484843)*uval+2.02466578)*uval - 0.67487759
   196  	return log2
   197  }
   198  
   199  // EstimatedBits returns an estimated minimum size for the
   200  // optimal compression of t.
   201  // Minimum 1 bit is assigned per symbol.
   202  // Maximum 15 bits are assigned per symbol.
   203  func (t *tokens) EstimatedBits() int {
   204  	shannon := float32(0)
   205  	bits := int(0)
   206  	nMatches := 0
   207  	total := int(t.n) + t.nFilled
   208  	if total > 0 {
   209  		invTotal := 1.0 / float32(total)
   210  		for _, v := range t.litHist[:] {
   211  			if v > 0 {
   212  				n := float32(v)
   213  				shannon += min(15, max(1, -mFastLog2(n*invTotal))) * n
   214  			}
   215  		}
   216  		// Just add 15 for EOB
   217  		shannon += 15
   218  		for i, v := range t.extraHist[1 : literalCount-256] {
   219  			if v > 0 {
   220  				n := float32(v)
   221  				shannon += min(15, max(1, -mFastLog2(n*invTotal))) * n
   222  				bits += int(lengthExtraBits[i&31]) * int(v)
   223  				nMatches += int(v)
   224  			}
   225  		}
   226  	}
   227  	if nMatches > 0 {
   228  		invTotal := 1.0 / float32(nMatches)
   229  		for i, v := range t.offHist[:offsetCodeCount] {
   230  			if v > 0 {
   231  				n := float32(v)
   232  				shannon += min(15, max(1, -mFastLog2(n*invTotal))) * n
   233  				bits += int(offsetExtraBits[i&31]) * int(v)
   234  			}
   235  		}
   236  	}
   237  	return int(shannon) + bits
   238  }
   239  
   240  // AddMatch adds a match to the tokens.
   241  // This function is very sensitive to inlining and right on the border.
   242  func (t *tokens) AddMatch(xlength uint32, xoffset uint32) {
   243  	oCode := offsetCode(xoffset)
   244  	xoffset |= oCode << 16
   245  
   246  	t.extraHist[lengthCodes1[uint8(xlength)]]++
   247  	t.offHist[oCode&31]++
   248  	t.tokens[t.n] = token(matchType | xlength<<lengthShift | xoffset)
   249  	t.n++
   250  }
   251  
   252  // AddMatchLong adds a match to the tokens, potentially longer than max match length.
   253  // Length should NOT have the base subtracted, only offset should.
   254  func (t *tokens) AddMatchLong(xlength int32, xoffset uint32) {
   255  	oc := offsetCode(xoffset)
   256  	xoffset |= oc << 16
   257  	for xlength > 0 {
   258  		xl := xlength
   259  		if xl > 258 {
   260  			// We need to have at least baseMatchLength left over for next loop.
   261  			if xl > 258+baseMatchLength {
   262  				xl = 258
   263  			} else {
   264  				xl = 258 - baseMatchLength
   265  			}
   266  		}
   267  		xlength -= xl
   268  		xl -= baseMatchLength
   269  		t.extraHist[lengthCodes1[uint8(xl)]]++
   270  		t.offHist[oc&31]++
   271  		t.tokens[t.n] = token(matchType | uint32(xl)<<lengthShift | xoffset)
   272  		t.n++
   273  	}
   274  }
   275  
   276  // AddEOB adds an end of block marker to the tokens.
   277  func (t *tokens) AddEOB() {
   278  	t.tokens[t.n] = token(endBlockMarker)
   279  	t.extraHist[0]++
   280  	t.n++
   281  }
   282  
   283  // Slice returns a slice of the tokens that references the tokens in t.
   284  func (t *tokens) Slice() []token {
   285  	return t.tokens[:t.n]
   286  }
   287  
   288  // typ returns the type of a token.
   289  func (t token) typ() uint32 { return uint32(t) & typeMask }
   290  
   291  // literal returns the literal value of t.
   292  func (t token) literal() uint8 { return uint8(t) }
   293  
   294  // offset returns the offset of a match token.
   295  func (t token) offset() uint32 { return uint32(t) & offsetMask }
   296  
   297  // length returns the length of a match token.
   298  func (t token) length() uint8 { return uint8(t >> lengthShift) }
   299  
   300  // lengthCode converts a match length to its code.
   301  func lengthCode(len uint8) uint8 { return lengthCodes[len] }
   302  
   303  // offsetCode returns the offset code corresponding to a specific offset.
   304  func offsetCode(off uint32) uint32 {
   305  	if off < uint32(len(offsetCodes)) {
   306  		return offsetCodes[uint8(off)]
   307  	}
   308  	return offsetCodes14[uint8(off>>7)]
   309  }
   310
View as plain text