diff options
Diffstat (limited to 'vendor/github.com/klauspost/compress/s2/encode_best.go')
-rw-r--r-- | vendor/github.com/klauspost/compress/s2/encode_best.go | 190 |
1 files changed, 166 insertions, 24 deletions
diff --git a/vendor/github.com/klauspost/compress/s2/encode_best.go b/vendor/github.com/klauspost/compress/s2/encode_best.go index 1b7ea394f..1d13e869a 100644 --- a/vendor/github.com/klauspost/compress/s2/encode_best.go +++ b/vendor/github.com/klauspost/compress/s2/encode_best.go @@ -7,6 +7,7 @@ package s2 import ( "fmt" + "math" "math/bits" ) @@ -18,7 +19,7 @@ import ( // // len(dst) >= MaxEncodedLen(len(src)) && // minNonLiteralBlockSize <= len(src) && len(src) <= maxBlockSize -func encodeBlockBest(dst, src []byte) (d int) { +func encodeBlockBest(dst, src []byte, dict *Dict) (d int) { // Initialize the hash tables. const ( // Long hash matches. @@ -30,6 +31,8 @@ func encodeBlockBest(dst, src []byte) (d int) { maxSTableSize = 1 << sTableBits inputMargin = 8 + 2 + + debug = false ) // sLimit is when to stop looking for offset/length copies. The inputMargin @@ -39,6 +42,10 @@ func encodeBlockBest(dst, src []byte) (d int) { if len(src) < minNonLiteralBlockSize { return 0 } + sLimitDict := len(src) - inputMargin + if sLimitDict > MaxDictSrcOffset-inputMargin { + sLimitDict = MaxDictSrcOffset - inputMargin + } var lTable [maxLTableSize]uint64 var sTable [maxSTableSize]uint64 @@ -52,10 +59,15 @@ func encodeBlockBest(dst, src []byte) (d int) { // The encoded form must start with a literal, as there are no previous // bytes to copy, so we start looking for hash matches at s == 1. s := 1 + repeat := 1 + if dict != nil { + dict.initBest() + s = 0 + repeat = len(dict.dict) - dict.repeat + } cv := load64(src, s) // We search for a repeat at -1, but don't output repeats when nextEmit == 0 - repeat := 1 const lowbitMask = 0xffffffff getCur := func(x uint64) int { return int(x & lowbitMask) @@ -67,11 +79,11 @@ func encodeBlockBest(dst, src []byte) (d int) { for { type match struct { - offset int - s int - length int - score int - rep bool + offset int + s int + length int + score int + rep, dict bool } var best match for { @@ -85,6 +97,12 @@ func encodeBlockBest(dst, src []byte) (d int) { if nextS > sLimit { goto emitRemainder } + if dict != nil && s >= MaxDictSrcOffset { + dict = nil + if repeat > s { + repeat = math.MinInt32 + } + } hashL := hash8(cv, lTableBits) hashS := hash4(cv, sTableBits) candidateL := lTable[hashL] @@ -114,7 +132,15 @@ func encodeBlockBest(dst, src []byte) (d int) { } m := match{offset: offset, s: s, length: 4 + offset, rep: rep} s += 4 - for s <= sLimit { + for s < len(src) { + if len(src)-s < 8 { + if src[s] == src[m.length] { + m.length++ + s++ + continue + } + break + } if diff := load64(src, s) ^ load64(src, m.length); diff != 0 { m.length += bits.TrailingZeros64(diff) >> 3 break @@ -130,6 +156,62 @@ func encodeBlockBest(dst, src []byte) (d int) { } return m } + matchDict := func(candidate, s int, first uint32, rep bool) match { + // Calculate offset as if in continuous array with s + offset := -len(dict.dict) + candidate + if best.length != 0 && best.s-best.offset == s-offset && !rep { + // Don't retest if we have the same offset. + return match{offset: offset, s: s} + } + + if load32(dict.dict, candidate) != first { + return match{offset: offset, s: s} + } + m := match{offset: offset, s: s, length: 4 + candidate, rep: rep, dict: true} + s += 4 + if !rep { + for s < sLimitDict && m.length < len(dict.dict) { + if len(src)-s < 8 || len(dict.dict)-m.length < 8 { + if src[s] == dict.dict[m.length] { + m.length++ + s++ + continue + } + break + } + if diff := load64(src, s) ^ load64(dict.dict, m.length); diff != 0 { + m.length += bits.TrailingZeros64(diff) >> 3 + break + } + s += 8 + m.length += 8 + } + } else { + for s < len(src) && m.length < len(dict.dict) { + if len(src)-s < 8 || len(dict.dict)-m.length < 8 { + if src[s] == dict.dict[m.length] { + m.length++ + s++ + continue + } + break + } + if diff := load64(src, s) ^ load64(dict.dict, m.length); diff != 0 { + m.length += bits.TrailingZeros64(diff) >> 3 + break + } + s += 8 + m.length += 8 + } + } + m.length -= candidate + m.score = score(m) + if m.score <= -m.s { + // Eliminate if no savings, we might find a better one. + m.length = 0 + } + return m + } bestOf := func(a, b match) match { if b.length == 0 { @@ -146,35 +228,82 @@ func encodeBlockBest(dst, src []byte) (d int) { return b } - best = bestOf(matchAt(getCur(candidateL), s, uint32(cv), false), matchAt(getPrev(candidateL), s, uint32(cv), false)) - best = bestOf(best, matchAt(getCur(candidateS), s, uint32(cv), false)) - best = bestOf(best, matchAt(getPrev(candidateS), s, uint32(cv), false)) - + if s > 0 { + best = bestOf(matchAt(getCur(candidateL), s, uint32(cv), false), matchAt(getPrev(candidateL), s, uint32(cv), false)) + best = bestOf(best, matchAt(getCur(candidateS), s, uint32(cv), false)) + best = bestOf(best, matchAt(getPrev(candidateS), s, uint32(cv), false)) + } + if dict != nil { + candidateL := dict.bestTableLong[hashL] + candidateS := dict.bestTableShort[hashS] + best = bestOf(best, matchDict(int(candidateL&0xffff), s, uint32(cv), false)) + best = bestOf(best, matchDict(int(candidateL>>16), s, uint32(cv), false)) + best = bestOf(best, matchDict(int(candidateS&0xffff), s, uint32(cv), false)) + best = bestOf(best, matchDict(int(candidateS>>16), s, uint32(cv), false)) + } { - best = bestOf(best, matchAt(s-repeat+1, s+1, uint32(cv>>8), true)) + if (dict == nil || repeat <= s) && repeat > 0 { + best = bestOf(best, matchAt(s-repeat+1, s+1, uint32(cv>>8), true)) + } else if s-repeat < -4 && dict != nil { + candidate := len(dict.dict) - (repeat - s) + best = bestOf(best, matchDict(candidate, s, uint32(cv), true)) + candidate++ + best = bestOf(best, matchDict(candidate, s+1, uint32(cv>>8), true)) + } + if best.length > 0 { + hashS := hash4(cv>>8, sTableBits) // s+1 - nextShort := sTable[hash4(cv>>8, sTableBits)] + nextShort := sTable[hashS] s := s + 1 cv := load64(src, s) - nextLong := lTable[hash8(cv, lTableBits)] + hashL := hash8(cv, lTableBits) + nextLong := lTable[hashL] best = bestOf(best, matchAt(getCur(nextShort), s, uint32(cv), false)) best = bestOf(best, matchAt(getPrev(nextShort), s, uint32(cv), false)) best = bestOf(best, matchAt(getCur(nextLong), s, uint32(cv), false)) best = bestOf(best, matchAt(getPrev(nextLong), s, uint32(cv), false)) - // Repeat at + 2 - best = bestOf(best, matchAt(s-repeat+1, s+1, uint32(cv>>8), true)) + + // Dict at + 1 + if dict != nil { + candidateL := dict.bestTableLong[hashL] + candidateS := dict.bestTableShort[hashS] + + best = bestOf(best, matchDict(int(candidateL&0xffff), s, uint32(cv), false)) + best = bestOf(best, matchDict(int(candidateS&0xffff), s, uint32(cv), false)) + } // s+2 if true { - nextShort = sTable[hash4(cv>>8, sTableBits)] + hashS := hash4(cv>>8, sTableBits) + + nextShort = sTable[hashS] s++ cv = load64(src, s) - nextLong = lTable[hash8(cv, lTableBits)] + hashL := hash8(cv, lTableBits) + nextLong = lTable[hashL] + + if (dict == nil || repeat <= s) && repeat > 0 { + // Repeat at + 2 + best = bestOf(best, matchAt(s-repeat, s, uint32(cv), true)) + } else if repeat-s > 4 && dict != nil { + candidate := len(dict.dict) - (repeat - s) + best = bestOf(best, matchDict(candidate, s, uint32(cv), true)) + } best = bestOf(best, matchAt(getCur(nextShort), s, uint32(cv), false)) best = bestOf(best, matchAt(getPrev(nextShort), s, uint32(cv), false)) best = bestOf(best, matchAt(getCur(nextLong), s, uint32(cv), false)) best = bestOf(best, matchAt(getPrev(nextLong), s, uint32(cv), false)) + + // Dict at +2 + // Very small gain + if dict != nil { + candidateL := dict.bestTableLong[hashL] + candidateS := dict.bestTableShort[hashS] + + best = bestOf(best, matchDict(int(candidateL&0xffff), s, uint32(cv), false)) + best = bestOf(best, matchDict(int(candidateS&0xffff), s, uint32(cv), false)) + } } // Search for a match at best match end, see if that is better. // Allow some bytes at the beginning to mismatch. @@ -227,7 +356,7 @@ func encodeBlockBest(dst, src []byte) (d int) { // Extend backwards, not needed for repeats... s = best.s - if !best.rep { + if !best.rep && !best.dict { for best.offset > 0 && s > nextEmit && src[best.offset-1] == src[s-1] { best.offset-- best.length++ @@ -244,7 +373,6 @@ func encodeBlockBest(dst, src []byte) (d int) { base := s offset := s - best.offset - s += best.length if offset > 65535 && s-base <= 5 && !best.rep { @@ -256,16 +384,28 @@ func encodeBlockBest(dst, src []byte) (d int) { cv = load64(src, s) continue } + if debug && nextEmit != base { + fmt.Println("EMIT", base-nextEmit, "literals. base-after:", base) + } d += emitLiteral(dst[d:], src[nextEmit:base]) if best.rep { - if nextEmit > 0 { + if nextEmit > 0 || best.dict { + if debug { + fmt.Println("REPEAT, length", best.length, "offset:", offset, "s-after:", s, "dict:", best.dict, "best:", best) + } // same as `add := emitCopy(dst[d:], repeat, s-base)` but skips storing offset. d += emitRepeat(dst[d:], offset, best.length) } else { - // First match, cannot be repeat. + // First match without dict cannot be a repeat. + if debug { + fmt.Println("COPY, length", best.length, "offset:", offset, "s-after:", s, "dict:", best.dict, "best:", best) + } d += emitCopy(dst[d:], offset, best.length) } } else { + if debug { + fmt.Println("COPY, length", best.length, "offset:", offset, "s-after:", s, "dict:", best.dict, "best:", best) + } d += emitCopy(dst[d:], offset, best.length) } repeat = offset @@ -296,6 +436,9 @@ emitRemainder: if d+len(src)-nextEmit > dstLimit { return 0 } + if debug && nextEmit != s { + fmt.Println("emitted ", len(src)-nextEmit, "literals") + } d += emitLiteral(dst[d:], src[nextEmit:]) } return d @@ -642,7 +785,6 @@ func emitRepeatSize(offset, length int) int { left := 0 if length > maxRepeat { left = length - maxRepeat + 4 - length = maxRepeat - 4 } if left > 0 { return 5 + emitRepeatSize(offset, left) |