token.go 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375
  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. package flate
  5. import (
  6. "bytes"
  7. "encoding/binary"
  8. "fmt"
  9. "io"
  10. "math"
  11. )
  12. const (
  13. // 2 bits: type 0 = literal 1=EOF 2=Match 3=Unused
  14. // 8 bits: xlength = length - MIN_MATCH_LENGTH
  15. // 22 bits xoffset = offset - MIN_OFFSET_SIZE, or literal
  16. lengthShift = 22
  17. offsetMask = 1<<lengthShift - 1
  18. typeMask = 3 << 30
  19. literalType = 0 << 30
  20. matchType = 1 << 30
  21. )
  22. // The length code for length X (MIN_MATCH_LENGTH <= X <= MAX_MATCH_LENGTH)
  23. // is lengthCodes[length - MIN_MATCH_LENGTH]
  24. var lengthCodes = [256]uint8{
  25. 0, 1, 2, 3, 4, 5, 6, 7, 8, 8,
  26. 9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
  27. 13, 13, 13, 13, 14, 14, 14, 14, 15, 15,
  28. 15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
  29. 17, 17, 17, 17, 17, 17, 17, 17, 18, 18,
  30. 18, 18, 18, 18, 18, 18, 19, 19, 19, 19,
  31. 19, 19, 19, 19, 20, 20, 20, 20, 20, 20,
  32. 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
  33. 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
  34. 21, 21, 21, 21, 21, 21, 22, 22, 22, 22,
  35. 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
  36. 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
  37. 23, 23, 23, 23, 23, 23, 23, 23, 24, 24,
  38. 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
  39. 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
  40. 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
  41. 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
  42. 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
  43. 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
  44. 25, 25, 26, 26, 26, 26, 26, 26, 26, 26,
  45. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
  46. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
  47. 26, 26, 26, 26, 27, 27, 27, 27, 27, 27,
  48. 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
  49. 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
  50. 27, 27, 27, 27, 27, 28,
  51. }
  52. // lengthCodes1 is length codes, but starting at 1.
  53. var lengthCodes1 = [256]uint8{
  54. 1, 2, 3, 4, 5, 6, 7, 8, 9, 9,
  55. 10, 10, 11, 11, 12, 12, 13, 13, 13, 13,
  56. 14, 14, 14, 14, 15, 15, 15, 15, 16, 16,
  57. 16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
  58. 18, 18, 18, 18, 18, 18, 18, 18, 19, 19,
  59. 19, 19, 19, 19, 19, 19, 20, 20, 20, 20,
  60. 20, 20, 20, 20, 21, 21, 21, 21, 21, 21,
  61. 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
  62. 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
  63. 22, 22, 22, 22, 22, 22, 23, 23, 23, 23,
  64. 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
  65. 23, 23, 24, 24, 24, 24, 24, 24, 24, 24,
  66. 24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
  67. 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
  68. 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
  69. 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
  70. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
  71. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
  72. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
  73. 26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
  74. 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
  75. 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
  76. 27, 27, 27, 27, 28, 28, 28, 28, 28, 28,
  77. 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  78. 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  79. 28, 28, 28, 28, 28, 29,
  80. }
  81. var offsetCodes = [256]uint32{
  82. 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
  83. 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,
  84. 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
  85. 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
  86. 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
  87. 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
  88. 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  89. 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  90. 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  91. 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  92. 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  93. 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  94. 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
  95. 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
  96. 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
  97. 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
  98. }
  99. // offsetCodes14 are offsetCodes, but with 14 added.
  100. var offsetCodes14 = [256]uint32{
  101. 14, 15, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
  102. 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
  103. 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
  104. 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
  105. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
  106. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
  107. 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
  108. 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
  109. 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  110. 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  111. 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  112. 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  113. 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
  114. 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
  115. 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
  116. 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
  117. }
  118. type token uint32
  119. type tokens struct {
  120. nLits int
  121. extraHist [32]uint16 // codes 256->maxnumlit
  122. offHist [32]uint16 // offset codes
  123. litHist [256]uint16 // codes 0->255
  124. n uint16 // Must be able to contain maxStoreBlockSize
  125. tokens [maxStoreBlockSize + 1]token
  126. }
  127. func (t *tokens) Reset() {
  128. if t.n == 0 {
  129. return
  130. }
  131. t.n = 0
  132. t.nLits = 0
  133. for i := range t.litHist[:] {
  134. t.litHist[i] = 0
  135. }
  136. for i := range t.extraHist[:] {
  137. t.extraHist[i] = 0
  138. }
  139. for i := range t.offHist[:] {
  140. t.offHist[i] = 0
  141. }
  142. }
  143. func (t *tokens) Fill() {
  144. if t.n == 0 {
  145. return
  146. }
  147. for i, v := range t.litHist[:] {
  148. if v == 0 {
  149. t.litHist[i] = 1
  150. t.nLits++
  151. }
  152. }
  153. for i, v := range t.extraHist[:literalCount-256] {
  154. if v == 0 {
  155. t.nLits++
  156. t.extraHist[i] = 1
  157. }
  158. }
  159. for i, v := range t.offHist[:offsetCodeCount] {
  160. if v == 0 {
  161. t.offHist[i] = 1
  162. }
  163. }
  164. }
  165. func indexTokens(in []token) tokens {
  166. var t tokens
  167. t.indexTokens(in)
  168. return t
  169. }
  170. func (t *tokens) indexTokens(in []token) {
  171. t.Reset()
  172. for _, tok := range in {
  173. if tok < matchType {
  174. t.AddLiteral(tok.literal())
  175. continue
  176. }
  177. t.AddMatch(uint32(tok.length()), tok.offset())
  178. }
  179. }
  180. // emitLiteral writes a literal chunk and returns the number of bytes written.
  181. func emitLiteral(dst *tokens, lit []byte) {
  182. ol := int(dst.n)
  183. for i, v := range lit {
  184. dst.tokens[(i+ol)&maxStoreBlockSize] = token(v)
  185. dst.litHist[v]++
  186. }
  187. dst.n += uint16(len(lit))
  188. dst.nLits += len(lit)
  189. }
  190. func (t *tokens) AddLiteral(lit byte) {
  191. t.tokens[t.n] = token(lit)
  192. t.litHist[lit]++
  193. t.n++
  194. t.nLits++
  195. }
  196. // from https://stackoverflow.com/a/28730362
  197. func mFastLog2(val float32) float32 {
  198. ux := int32(math.Float32bits(val))
  199. log2 := (float32)(((ux >> 23) & 255) - 128)
  200. ux &= -0x7f800001
  201. ux += 127 << 23
  202. uval := math.Float32frombits(uint32(ux))
  203. log2 += ((-0.34484843)*uval+2.02466578)*uval - 0.67487759
  204. return log2
  205. }
  206. // EstimatedBits will return an minimum size estimated by an *optimal*
  207. // compression of the block.
  208. // The size of the block
  209. func (t *tokens) EstimatedBits() int {
  210. shannon := float32(0)
  211. bits := int(0)
  212. nMatches := 0
  213. if t.nLits > 0 {
  214. invTotal := 1.0 / float32(t.nLits)
  215. for _, v := range t.litHist[:] {
  216. if v > 0 {
  217. n := float32(v)
  218. shannon += -mFastLog2(n*invTotal) * n
  219. }
  220. }
  221. // Just add 15 for EOB
  222. shannon += 15
  223. for i, v := range t.extraHist[1 : literalCount-256] {
  224. if v > 0 {
  225. n := float32(v)
  226. shannon += -mFastLog2(n*invTotal) * n
  227. bits += int(lengthExtraBits[i&31]) * int(v)
  228. nMatches += int(v)
  229. }
  230. }
  231. }
  232. if nMatches > 0 {
  233. invTotal := 1.0 / float32(nMatches)
  234. for i, v := range t.offHist[:offsetCodeCount] {
  235. if v > 0 {
  236. n := float32(v)
  237. shannon += -mFastLog2(n*invTotal) * n
  238. bits += int(offsetExtraBits[i&31]) * int(v)
  239. }
  240. }
  241. }
  242. return int(shannon) + bits
  243. }
  244. // AddMatch adds a match to the tokens.
  245. // This function is very sensitive to inlining and right on the border.
  246. func (t *tokens) AddMatch(xlength uint32, xoffset uint32) {
  247. if debugDeflate {
  248. if xlength >= maxMatchLength+baseMatchLength {
  249. panic(fmt.Errorf("invalid length: %v", xlength))
  250. }
  251. if xoffset >= maxMatchOffset+baseMatchOffset {
  252. panic(fmt.Errorf("invalid offset: %v", xoffset))
  253. }
  254. }
  255. t.nLits++
  256. lengthCode := lengthCodes1[uint8(xlength)] & 31
  257. t.tokens[t.n] = token(matchType | xlength<<lengthShift | xoffset)
  258. t.extraHist[lengthCode]++
  259. t.offHist[offsetCode(xoffset)&31]++
  260. t.n++
  261. }
  262. // AddMatchLong adds a match to the tokens, potentially longer than max match length.
  263. // Length should NOT have the base subtracted, only offset should.
  264. func (t *tokens) AddMatchLong(xlength int32, xoffset uint32) {
  265. if debugDeflate {
  266. if xoffset >= maxMatchOffset+baseMatchOffset {
  267. panic(fmt.Errorf("invalid offset: %v", xoffset))
  268. }
  269. }
  270. oc := offsetCode(xoffset) & 31
  271. for xlength > 0 {
  272. xl := xlength
  273. if xl > 258 {
  274. // We need to have at least baseMatchLength left over for next loop.
  275. xl = 258 - baseMatchLength
  276. }
  277. xlength -= xl
  278. xl -= 3
  279. t.nLits++
  280. lengthCode := lengthCodes1[uint8(xl)] & 31
  281. t.tokens[t.n] = token(matchType | uint32(xl)<<lengthShift | xoffset)
  282. t.extraHist[lengthCode]++
  283. t.offHist[oc]++
  284. t.n++
  285. }
  286. }
  287. func (t *tokens) AddEOB() {
  288. t.tokens[t.n] = token(endBlockMarker)
  289. t.extraHist[0]++
  290. t.n++
  291. }
  292. func (t *tokens) Slice() []token {
  293. return t.tokens[:t.n]
  294. }
  295. // VarInt returns the tokens as varint encoded bytes.
  296. func (t *tokens) VarInt() []byte {
  297. var b = make([]byte, binary.MaxVarintLen32*int(t.n))
  298. var off int
  299. for _, v := range t.tokens[:t.n] {
  300. off += binary.PutUvarint(b[off:], uint64(v))
  301. }
  302. return b[:off]
  303. }
  304. // FromVarInt restores t to the varint encoded tokens provided.
  305. // Any data in t is removed.
  306. func (t *tokens) FromVarInt(b []byte) error {
  307. var buf = bytes.NewReader(b)
  308. var toks []token
  309. for {
  310. r, err := binary.ReadUvarint(buf)
  311. if err == io.EOF {
  312. break
  313. }
  314. if err != nil {
  315. return err
  316. }
  317. toks = append(toks, token(r))
  318. }
  319. t.indexTokens(toks)
  320. return nil
  321. }
  322. // Returns the type of a token
  323. func (t token) typ() uint32 { return uint32(t) & typeMask }
  324. // Returns the literal of a literal token
  325. func (t token) literal() uint8 { return uint8(t) }
  326. // Returns the extra offset of a match token
  327. func (t token) offset() uint32 { return uint32(t) & offsetMask }
  328. func (t token) length() uint8 { return uint8(t >> lengthShift) }
  329. // The code is never more than 8 bits, but is returned as uint32 for convenience.
  330. func lengthCode(len uint8) uint32 { return uint32(lengthCodes[len]) }
  331. // Returns the offset code corresponding to a specific offset
  332. func offsetCode(off uint32) uint32 {
  333. if false {
  334. if off < uint32(len(offsetCodes)) {
  335. return offsetCodes[off&255]
  336. } else if off>>7 < uint32(len(offsetCodes)) {
  337. return offsetCodes[(off>>7)&255] + 14
  338. } else {
  339. return offsetCodes[(off>>14)&255] + 28
  340. }
  341. }
  342. if off < uint32(len(offsetCodes)) {
  343. return offsetCodes[uint8(off)]
  344. }
  345. return offsetCodes14[uint8(off>>7)]
  346. }