level4.go 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212
  1. package flate
  2. import "fmt"
  3. type fastEncL4 struct {
  4. fastGen
  5. table [tableSize]tableEntry
  6. bTable [tableSize]tableEntry
  7. }
  8. func (e *fastEncL4) Encode(dst *tokens, src []byte) {
  9. const (
  10. inputMargin = 12 - 1
  11. minNonLiteralBlockSize = 1 + 1 + inputMargin
  12. )
  13. if debugDeflate && e.cur < 0 {
  14. panic(fmt.Sprint("e.cur < 0: ", e.cur))
  15. }
  16. // Protect against e.cur wraparound.
  17. for e.cur >= bufferReset {
  18. if len(e.hist) == 0 {
  19. for i := range e.table[:] {
  20. e.table[i] = tableEntry{}
  21. }
  22. for i := range e.bTable[:] {
  23. e.bTable[i] = tableEntry{}
  24. }
  25. e.cur = maxMatchOffset
  26. break
  27. }
  28. // Shift down everything in the table that isn't already too far away.
  29. minOff := e.cur + int32(len(e.hist)) - maxMatchOffset
  30. for i := range e.table[:] {
  31. v := e.table[i].offset
  32. if v <= minOff {
  33. v = 0
  34. } else {
  35. v = v - e.cur + maxMatchOffset
  36. }
  37. e.table[i].offset = v
  38. }
  39. for i := range e.bTable[:] {
  40. v := e.bTable[i].offset
  41. if v <= minOff {
  42. v = 0
  43. } else {
  44. v = v - e.cur + maxMatchOffset
  45. }
  46. e.bTable[i].offset = v
  47. }
  48. e.cur = maxMatchOffset
  49. }
  50. s := e.addBlock(src)
  51. // This check isn't in the Snappy implementation, but there, the caller
  52. // instead of the callee handles this case.
  53. if len(src) < minNonLiteralBlockSize {
  54. // We do not fill the token table.
  55. // This will be picked up by caller.
  56. dst.n = uint16(len(src))
  57. return
  58. }
  59. // Override src
  60. src = e.hist
  61. nextEmit := s
  62. // sLimit is when to stop looking for offset/length copies. The inputMargin
  63. // lets us use a fast path for emitLiteral in the main loop, while we are
  64. // looking for copies.
  65. sLimit := int32(len(src) - inputMargin)
  66. // nextEmit is where in src the next emitLiteral should start from.
  67. cv := load6432(src, s)
  68. for {
  69. const skipLog = 6
  70. const doEvery = 1
  71. nextS := s
  72. var t int32
  73. for {
  74. nextHashS := hash4x64(cv, tableBits)
  75. nextHashL := hash7(cv, tableBits)
  76. s = nextS
  77. nextS = s + doEvery + (s-nextEmit)>>skipLog
  78. if nextS > sLimit {
  79. goto emitRemainder
  80. }
  81. // Fetch a short+long candidate
  82. sCandidate := e.table[nextHashS]
  83. lCandidate := e.bTable[nextHashL]
  84. next := load6432(src, nextS)
  85. entry := tableEntry{offset: s + e.cur}
  86. e.table[nextHashS] = entry
  87. e.bTable[nextHashL] = entry
  88. t = lCandidate.offset - e.cur
  89. if s-t < maxMatchOffset && uint32(cv) == load3232(src, lCandidate.offset-e.cur) {
  90. // We got a long match. Use that.
  91. break
  92. }
  93. t = sCandidate.offset - e.cur
  94. if s-t < maxMatchOffset && uint32(cv) == load3232(src, sCandidate.offset-e.cur) {
  95. // Found a 4 match...
  96. lCandidate = e.bTable[hash7(next, tableBits)]
  97. // If the next long is a candidate, check if we should use that instead...
  98. lOff := nextS - (lCandidate.offset - e.cur)
  99. if lOff < maxMatchOffset && load3232(src, lCandidate.offset-e.cur) == uint32(next) {
  100. l1, l2 := matchLen(src[s+4:], src[t+4:]), matchLen(src[nextS+4:], src[nextS-lOff+4:])
  101. if l2 > l1 {
  102. s = nextS
  103. t = lCandidate.offset - e.cur
  104. }
  105. }
  106. break
  107. }
  108. cv = next
  109. }
  110. // A 4-byte match has been found. We'll later see if more than 4 bytes
  111. // match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
  112. // them as literal bytes.
  113. // Extend the 4-byte match as long as possible.
  114. l := e.matchlenLong(s+4, t+4, src) + 4
  115. // Extend backwards
  116. for t > 0 && s > nextEmit && src[t-1] == src[s-1] {
  117. s--
  118. t--
  119. l++
  120. }
  121. if nextEmit < s {
  122. emitLiteral(dst, src[nextEmit:s])
  123. }
  124. if debugDeflate {
  125. if t >= s {
  126. panic("s-t")
  127. }
  128. if (s - t) > maxMatchOffset {
  129. panic(fmt.Sprintln("mmo", t))
  130. }
  131. if l < baseMatchLength {
  132. panic("bml")
  133. }
  134. }
  135. dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
  136. s += l
  137. nextEmit = s
  138. if nextS >= s {
  139. s = nextS + 1
  140. }
  141. if s >= sLimit {
  142. // Index first pair after match end.
  143. if int(s+8) < len(src) {
  144. cv := load6432(src, s)
  145. e.table[hash4x64(cv, tableBits)] = tableEntry{offset: s + e.cur}
  146. e.bTable[hash7(cv, tableBits)] = tableEntry{offset: s + e.cur}
  147. }
  148. goto emitRemainder
  149. }
  150. // Store every 3rd hash in-between
  151. if true {
  152. i := nextS
  153. if i < s-1 {
  154. cv := load6432(src, i)
  155. t := tableEntry{offset: i + e.cur}
  156. t2 := tableEntry{offset: t.offset + 1}
  157. e.bTable[hash7(cv, tableBits)] = t
  158. e.bTable[hash7(cv>>8, tableBits)] = t2
  159. e.table[hash4u(uint32(cv>>8), tableBits)] = t2
  160. i += 3
  161. for ; i < s-1; i += 3 {
  162. cv := load6432(src, i)
  163. t := tableEntry{offset: i + e.cur}
  164. t2 := tableEntry{offset: t.offset + 1}
  165. e.bTable[hash7(cv, tableBits)] = t
  166. e.bTable[hash7(cv>>8, tableBits)] = t2
  167. e.table[hash4u(uint32(cv>>8), tableBits)] = t2
  168. }
  169. }
  170. }
  171. // We could immediately start working at s now, but to improve
  172. // compression we first update the hash table at s-1 and at s.
  173. x := load6432(src, s-1)
  174. o := e.cur + s - 1
  175. prevHashS := hash4x64(x, tableBits)
  176. prevHashL := hash7(x, tableBits)
  177. e.table[prevHashS] = tableEntry{offset: o}
  178. e.bTable[prevHashL] = tableEntry{offset: o}
  179. cv = x >> 8
  180. }
  181. emitRemainder:
  182. if int(nextEmit) < len(src) {
  183. // If nothing was added, don't encode literals.
  184. if dst.n == 0 {
  185. return
  186. }
  187. emitLiteral(dst, src[nextEmit:])
  188. }
  189. }