| 1 | package flate
|
|---|
| 2 |
|
|---|
| 3 | import (
|
|---|
| 4 | "io"
|
|---|
| 5 | "math"
|
|---|
| 6 | "sync"
|
|---|
| 7 | )
|
|---|
| 8 |
|
|---|
| 9 | const (
|
|---|
| 10 | maxStatelessBlock = math.MaxInt16
|
|---|
| 11 | // dictionary will be taken from maxStatelessBlock, so limit it.
|
|---|
| 12 | maxStatelessDict = 8 << 10
|
|---|
| 13 |
|
|---|
| 14 | slTableBits = 13
|
|---|
| 15 | slTableSize = 1 << slTableBits
|
|---|
| 16 | slTableShift = 32 - slTableBits
|
|---|
| 17 | )
|
|---|
| 18 |
|
|---|
| 19 | type statelessWriter struct {
|
|---|
| 20 | dst io.Writer
|
|---|
| 21 | closed bool
|
|---|
| 22 | }
|
|---|
| 23 |
|
|---|
| 24 | func (s *statelessWriter) Close() error {
|
|---|
| 25 | if s.closed {
|
|---|
| 26 | return nil
|
|---|
| 27 | }
|
|---|
| 28 | s.closed = true
|
|---|
| 29 | // Emit EOF block
|
|---|
| 30 | return StatelessDeflate(s.dst, nil, true, nil)
|
|---|
| 31 | }
|
|---|
| 32 |
|
|---|
| 33 | func (s *statelessWriter) Write(p []byte) (n int, err error) {
|
|---|
| 34 | err = StatelessDeflate(s.dst, p, false, nil)
|
|---|
| 35 | if err != nil {
|
|---|
| 36 | return 0, err
|
|---|
| 37 | }
|
|---|
| 38 | return len(p), nil
|
|---|
| 39 | }
|
|---|
| 40 |
|
|---|
| 41 | func (s *statelessWriter) Reset(w io.Writer) {
|
|---|
| 42 | s.dst = w
|
|---|
| 43 | s.closed = false
|
|---|
| 44 | }
|
|---|
| 45 |
|
|---|
| 46 | // NewStatelessWriter will do compression but without maintaining any state
|
|---|
| 47 | // between Write calls.
|
|---|
| 48 | // There will be no memory kept between Write calls,
|
|---|
| 49 | // but compression and speed will be suboptimal.
|
|---|
| 50 | // Because of this, the size of actual Write calls will affect output size.
|
|---|
| 51 | func NewStatelessWriter(dst io.Writer) io.WriteCloser {
|
|---|
| 52 | return &statelessWriter{dst: dst}
|
|---|
| 53 | }
|
|---|
| 54 |
|
|---|
| 55 | // bitWriterPool contains bit writers that can be reused.
|
|---|
| 56 | var bitWriterPool = sync.Pool{
|
|---|
| 57 | New: func() interface{} {
|
|---|
| 58 | return newHuffmanBitWriter(nil)
|
|---|
| 59 | },
|
|---|
| 60 | }
|
|---|
| 61 |
|
|---|
| 62 | // StatelessDeflate allows to compress directly to a Writer without retaining state.
|
|---|
| 63 | // When returning everything will be flushed.
|
|---|
| 64 | // Up to 8KB of an optional dictionary can be given which is presumed to presumed to precede the block.
|
|---|
| 65 | // Longer dictionaries will be truncated and will still produce valid output.
|
|---|
| 66 | // Sending nil dictionary is perfectly fine.
|
|---|
| 67 | func StatelessDeflate(out io.Writer, in []byte, eof bool, dict []byte) error {
|
|---|
| 68 | var dst tokens
|
|---|
| 69 | bw := bitWriterPool.Get().(*huffmanBitWriter)
|
|---|
| 70 | bw.reset(out)
|
|---|
| 71 | defer func() {
|
|---|
| 72 | // don't keep a reference to our output
|
|---|
| 73 | bw.reset(nil)
|
|---|
| 74 | bitWriterPool.Put(bw)
|
|---|
| 75 | }()
|
|---|
| 76 | if eof && len(in) == 0 {
|
|---|
| 77 | // Just write an EOF block.
|
|---|
| 78 | // Could be faster...
|
|---|
| 79 | bw.writeStoredHeader(0, true)
|
|---|
| 80 | bw.flush()
|
|---|
| 81 | return bw.err
|
|---|
| 82 | }
|
|---|
| 83 |
|
|---|
| 84 | // Truncate dict
|
|---|
| 85 | if len(dict) > maxStatelessDict {
|
|---|
| 86 | dict = dict[len(dict)-maxStatelessDict:]
|
|---|
| 87 | }
|
|---|
| 88 |
|
|---|
| 89 | for len(in) > 0 {
|
|---|
| 90 | todo := in
|
|---|
| 91 | if len(todo) > maxStatelessBlock-len(dict) {
|
|---|
| 92 | todo = todo[:maxStatelessBlock-len(dict)]
|
|---|
| 93 | }
|
|---|
| 94 | in = in[len(todo):]
|
|---|
| 95 | uncompressed := todo
|
|---|
| 96 | if len(dict) > 0 {
|
|---|
| 97 | // combine dict and source
|
|---|
| 98 | bufLen := len(todo) + len(dict)
|
|---|
| 99 | combined := make([]byte, bufLen)
|
|---|
| 100 | copy(combined, dict)
|
|---|
| 101 | copy(combined[len(dict):], todo)
|
|---|
| 102 | todo = combined
|
|---|
| 103 | }
|
|---|
| 104 | // Compress
|
|---|
| 105 | statelessEnc(&dst, todo, int16(len(dict)))
|
|---|
| 106 | isEof := eof && len(in) == 0
|
|---|
| 107 |
|
|---|
| 108 | if dst.n == 0 {
|
|---|
| 109 | bw.writeStoredHeader(len(uncompressed), isEof)
|
|---|
| 110 | if bw.err != nil {
|
|---|
| 111 | return bw.err
|
|---|
| 112 | }
|
|---|
| 113 | bw.writeBytes(uncompressed)
|
|---|
| 114 | } else if int(dst.n) > len(uncompressed)-len(uncompressed)>>4 {
|
|---|
| 115 | // If we removed less than 1/16th, huffman compress the block.
|
|---|
| 116 | bw.writeBlockHuff(isEof, uncompressed, len(in) == 0)
|
|---|
| 117 | } else {
|
|---|
| 118 | bw.writeBlockDynamic(&dst, isEof, uncompressed, len(in) == 0)
|
|---|
| 119 | }
|
|---|
| 120 | if len(in) > 0 {
|
|---|
| 121 | // Retain a dict if we have more
|
|---|
| 122 | dict = todo[len(todo)-maxStatelessDict:]
|
|---|
| 123 | dst.Reset()
|
|---|
| 124 | }
|
|---|
| 125 | if bw.err != nil {
|
|---|
| 126 | return bw.err
|
|---|
| 127 | }
|
|---|
| 128 | }
|
|---|
| 129 | if !eof {
|
|---|
| 130 | // Align, only a stored block can do that.
|
|---|
| 131 | bw.writeStoredHeader(0, false)
|
|---|
| 132 | }
|
|---|
| 133 | bw.flush()
|
|---|
| 134 | return bw.err
|
|---|
| 135 | }
|
|---|
| 136 |
|
|---|
| 137 | func hashSL(u uint32) uint32 {
|
|---|
| 138 | return (u * 0x1e35a7bd) >> slTableShift
|
|---|
| 139 | }
|
|---|
| 140 |
|
|---|
| 141 | func load3216(b []byte, i int16) uint32 {
|
|---|
| 142 | // Help the compiler eliminate bounds checks on the read so it can be done in a single read.
|
|---|
| 143 | b = b[i:]
|
|---|
| 144 | b = b[:4]
|
|---|
| 145 | return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
|
|---|
| 146 | }
|
|---|
| 147 |
|
|---|
| 148 | func load6416(b []byte, i int16) uint64 {
|
|---|
| 149 | // Help the compiler eliminate bounds checks on the read so it can be done in a single read.
|
|---|
| 150 | b = b[i:]
|
|---|
| 151 | b = b[:8]
|
|---|
| 152 | return uint64(b[0]) | uint64(b[1])<<8 | uint64(b[2])<<16 | uint64(b[3])<<24 |
|
|---|
| 153 | uint64(b[4])<<32 | uint64(b[5])<<40 | uint64(b[6])<<48 | uint64(b[7])<<56
|
|---|
| 154 | }
|
|---|
| 155 |
|
|---|
| 156 | func statelessEnc(dst *tokens, src []byte, startAt int16) {
|
|---|
| 157 | const (
|
|---|
| 158 | inputMargin = 12 - 1
|
|---|
| 159 | minNonLiteralBlockSize = 1 + 1 + inputMargin
|
|---|
| 160 | )
|
|---|
| 161 |
|
|---|
| 162 | type tableEntry struct {
|
|---|
| 163 | offset int16
|
|---|
| 164 | }
|
|---|
| 165 |
|
|---|
| 166 | var table [slTableSize]tableEntry
|
|---|
| 167 |
|
|---|
| 168 | // This check isn't in the Snappy implementation, but there, the caller
|
|---|
| 169 | // instead of the callee handles this case.
|
|---|
| 170 | if len(src)-int(startAt) < minNonLiteralBlockSize {
|
|---|
| 171 | // We do not fill the token table.
|
|---|
| 172 | // This will be picked up by caller.
|
|---|
| 173 | dst.n = 0
|
|---|
| 174 | return
|
|---|
| 175 | }
|
|---|
| 176 | // Index until startAt
|
|---|
| 177 | if startAt > 0 {
|
|---|
| 178 | cv := load3232(src, 0)
|
|---|
| 179 | for i := int16(0); i < startAt; i++ {
|
|---|
| 180 | table[hashSL(cv)] = tableEntry{offset: i}
|
|---|
| 181 | cv = (cv >> 8) | (uint32(src[i+4]) << 24)
|
|---|
| 182 | }
|
|---|
| 183 | }
|
|---|
| 184 |
|
|---|
| 185 | s := startAt + 1
|
|---|
| 186 | nextEmit := startAt
|
|---|
| 187 | // sLimit is when to stop looking for offset/length copies. The inputMargin
|
|---|
| 188 | // lets us use a fast path for emitLiteral in the main loop, while we are
|
|---|
| 189 | // looking for copies.
|
|---|
| 190 | sLimit := int16(len(src) - inputMargin)
|
|---|
| 191 |
|
|---|
| 192 | // nextEmit is where in src the next emitLiteral should start from.
|
|---|
| 193 | cv := load3216(src, s)
|
|---|
| 194 |
|
|---|
| 195 | for {
|
|---|
| 196 | const skipLog = 5
|
|---|
| 197 | const doEvery = 2
|
|---|
| 198 |
|
|---|
| 199 | nextS := s
|
|---|
| 200 | var candidate tableEntry
|
|---|
| 201 | for {
|
|---|
| 202 | nextHash := hashSL(cv)
|
|---|
| 203 | candidate = table[nextHash]
|
|---|
| 204 | nextS = s + doEvery + (s-nextEmit)>>skipLog
|
|---|
| 205 | if nextS > sLimit || nextS <= 0 {
|
|---|
| 206 | goto emitRemainder
|
|---|
| 207 | }
|
|---|
| 208 |
|
|---|
| 209 | now := load6416(src, nextS)
|
|---|
| 210 | table[nextHash] = tableEntry{offset: s}
|
|---|
| 211 | nextHash = hashSL(uint32(now))
|
|---|
| 212 |
|
|---|
| 213 | if cv == load3216(src, candidate.offset) {
|
|---|
| 214 | table[nextHash] = tableEntry{offset: nextS}
|
|---|
| 215 | break
|
|---|
| 216 | }
|
|---|
| 217 |
|
|---|
| 218 | // Do one right away...
|
|---|
| 219 | cv = uint32(now)
|
|---|
| 220 | s = nextS
|
|---|
| 221 | nextS++
|
|---|
| 222 | candidate = table[nextHash]
|
|---|
| 223 | now >>= 8
|
|---|
| 224 | table[nextHash] = tableEntry{offset: s}
|
|---|
| 225 |
|
|---|
| 226 | if cv == load3216(src, candidate.offset) {
|
|---|
| 227 | table[nextHash] = tableEntry{offset: nextS}
|
|---|
| 228 | break
|
|---|
| 229 | }
|
|---|
| 230 | cv = uint32(now)
|
|---|
| 231 | s = nextS
|
|---|
| 232 | }
|
|---|
| 233 |
|
|---|
| 234 | // A 4-byte match has been found. We'll later see if more than 4 bytes
|
|---|
| 235 | // match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
|
|---|
| 236 | // them as literal bytes.
|
|---|
| 237 | for {
|
|---|
| 238 | // Invariant: we have a 4-byte match at s, and no need to emit any
|
|---|
| 239 | // literal bytes prior to s.
|
|---|
| 240 |
|
|---|
| 241 | // Extend the 4-byte match as long as possible.
|
|---|
| 242 | t := candidate.offset
|
|---|
| 243 | l := int16(matchLen(src[s+4:], src[t+4:]) + 4)
|
|---|
| 244 |
|
|---|
| 245 | // Extend backwards
|
|---|
| 246 | for t > 0 && s > nextEmit && src[t-1] == src[s-1] {
|
|---|
| 247 | s--
|
|---|
| 248 | t--
|
|---|
| 249 | l++
|
|---|
| 250 | }
|
|---|
| 251 | if nextEmit < s {
|
|---|
| 252 | emitLiteral(dst, src[nextEmit:s])
|
|---|
| 253 | }
|
|---|
| 254 |
|
|---|
| 255 | // Save the match found
|
|---|
| 256 | dst.AddMatchLong(int32(l), uint32(s-t-baseMatchOffset))
|
|---|
| 257 | s += l
|
|---|
| 258 | nextEmit = s
|
|---|
| 259 | if nextS >= s {
|
|---|
| 260 | s = nextS + 1
|
|---|
| 261 | }
|
|---|
| 262 | if s >= sLimit {
|
|---|
| 263 | goto emitRemainder
|
|---|
| 264 | }
|
|---|
| 265 |
|
|---|
| 266 | // We could immediately start working at s now, but to improve
|
|---|
| 267 | // compression we first update the hash table at s-2 and at s. If
|
|---|
| 268 | // another emitCopy is not our next move, also calculate nextHash
|
|---|
| 269 | // at s+1. At least on GOARCH=amd64, these three hash calculations
|
|---|
| 270 | // are faster as one load64 call (with some shifts) instead of
|
|---|
| 271 | // three load32 calls.
|
|---|
| 272 | x := load6416(src, s-2)
|
|---|
| 273 | o := s - 2
|
|---|
| 274 | prevHash := hashSL(uint32(x))
|
|---|
| 275 | table[prevHash] = tableEntry{offset: o}
|
|---|
| 276 | x >>= 16
|
|---|
| 277 | currHash := hashSL(uint32(x))
|
|---|
| 278 | candidate = table[currHash]
|
|---|
| 279 | table[currHash] = tableEntry{offset: o + 2}
|
|---|
| 280 |
|
|---|
| 281 | if uint32(x) != load3216(src, candidate.offset) {
|
|---|
| 282 | cv = uint32(x >> 8)
|
|---|
| 283 | s++
|
|---|
| 284 | break
|
|---|
| 285 | }
|
|---|
| 286 | }
|
|---|
| 287 | }
|
|---|
| 288 |
|
|---|
| 289 | emitRemainder:
|
|---|
| 290 | if int(nextEmit) < len(src) {
|
|---|
| 291 | // If nothing was added, don't encode literals.
|
|---|
| 292 | if dst.n == 0 {
|
|---|
| 293 | return
|
|---|
| 294 | }
|
|---|
| 295 | emitLiteral(dst, src[nextEmit:])
|
|---|
| 296 | }
|
|---|
| 297 | }
|
|---|
