1 files changed, 248 insertions, 0 deletions

diff --git a/vendor/github.com/ulikunitz/xz/lzma/rangecodec.go b/vendor/github.com/ulikunitz/xz/lzma/rangecodec.go
new file mode 100644
index 0000000..6361c5e
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/rangecodec.go
@@ -0,0 +1,248 @@
+// Copyright 2014-2017 Ulrich Kunitz. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package lzma
+
+import (
+        "errors"
+        "io"
+)
+
+// rangeEncoder implements range encoding of single bits. The low value can
+// overflow therefore we need uint64. The cache value is used to handle
+// overflows.
+type rangeEncoder struct {
+        lbw      *LimitedByteWriter
+        nrange   uint32
+        low      uint64
+        cacheLen int64
+        cache    byte
+}
+
+// maxInt64 provides the  maximal value of the int64 type
+const maxInt64 = 1<<63 - 1
+
+// newRangeEncoder creates a new range encoder.
+func newRangeEncoder(bw io.ByteWriter) (re *rangeEncoder, err error) {
+        lbw, ok := bw.(*LimitedByteWriter)
+        if !ok {
+                lbw = &LimitedByteWriter{BW: bw, N: maxInt64}
+        }
+        return &rangeEncoder{
+                lbw:      lbw,
+                nrange:   0xffffffff,
+                cacheLen: 1}, nil
+}
+
+// Available returns the number of bytes that still can be written. The
+// method takes the bytes that will be currently written by Close into
+// account.
+func (e *rangeEncoder) Available() int64 {
+        return e.lbw.N - (e.cacheLen + 4)
+}
+
+// writeByte writes a single byte to the underlying writer. An error is
+// returned if the limit is reached. The written byte will be counted if
+// the underlying writer doesn't return an error.
+func (e *rangeEncoder) writeByte(c byte) error {
+        if e.Available() < 1 {
+                return ErrLimit
+        }
+        return e.lbw.WriteByte(c)
+}
+
+// DirectEncodeBit encodes the least-significant bit of b with probability 1/2.
+func (e *rangeEncoder) DirectEncodeBit(b uint32) error {
+        e.nrange >>= 1
+        e.low += uint64(e.nrange) & (0 - (uint64(b) & 1))
+
+        // normalize
+        const top = 1 << 24
+        if e.nrange >= top {
+                return nil
+        }
+        e.nrange <<= 8
+        return e.shiftLow()
+}
+
+// EncodeBit encodes the least significant bit of b. The p value will be
+// updated by the function depending on the bit encoded.
+func (e *rangeEncoder) EncodeBit(b uint32, p *prob) error {
+        bound := p.bound(e.nrange)
+        if b&1 == 0 {
+                e.nrange = bound
+                p.inc()
+        } else {
+                e.low += uint64(bound)
+                e.nrange -= bound
+                p.dec()
+        }
+
+        // normalize
+        const top = 1 << 24
+        if e.nrange >= top {
+                return nil
+        }
+        e.nrange <<= 8
+        return e.shiftLow()
+}
+
+// Close writes a complete copy of the low value.
+func (e *rangeEncoder) Close() error {
+        for i := 0; i < 5; i++ {
+                if err := e.shiftLow(); err != nil {
+                        return err
+                }
+        }
+        return nil
+}
+
+// shiftLow shifts the low value for 8 bit. The shifted byte is written into
+// the byte writer. The cache value is used to handle overflows.
+func (e *rangeEncoder) shiftLow() error {
+        if uint32(e.low) < 0xff000000 || (e.low>>32) != 0 {
+                tmp := e.cache
+                for {
+                        err := e.writeByte(tmp + byte(e.low>>32))
+                        if err != nil {
+                                return err
+                        }
+                        tmp = 0xff
+                        e.cacheLen--
+                        if e.cacheLen <= 0 {
+                                if e.cacheLen < 0 {
+                                        panic("negative cacheLen")
+                                }
+                                break
+                        }
+                }
+                e.cache = byte(uint32(e.low) >> 24)
+        }
+        e.cacheLen++
+        e.low = uint64(uint32(e.low) << 8)
+        return nil
+}
+
+// rangeDecoder decodes single bits of the range encoding stream.
+type rangeDecoder struct {
+        br     io.ByteReader
+        nrange uint32
+        code   uint32
+}
+
+// init initializes the range decoder, by reading from the byte reader.
+func (d *rangeDecoder) init() error {
+        d.nrange = 0xffffffff
+        d.code = 0
+
+        b, err := d.br.ReadByte()
+        if err != nil {
+                return err
+        }
+        if b != 0 {
+                return errors.New("newRangeDecoder: first byte not zero")
+        }
+
+        for i := 0; i < 4; i++ {
+                if err = d.updateCode(); err != nil {
+                        return err
+                }
+        }
+
+        if d.code >= d.nrange {
+                return errors.New("newRangeDecoder: d.code >= d.nrange")
+        }
+
+        return nil
+}
+
+// newRangeDecoder initializes a range decoder. It reads five bytes from the
+// reader and therefore may return an error.
+func newRangeDecoder(br io.ByteReader) (d *rangeDecoder, err error) {
+        d = &rangeDecoder{br: br, nrange: 0xffffffff}
+
+        b, err := d.br.ReadByte()
+        if err != nil {
+                return nil, err
+        }
+        if b != 0 {
+                return nil, errors.New("newRangeDecoder: first byte not zero")
+        }
+
+        for i := 0; i < 4; i++ {
+                if err = d.updateCode(); err != nil {
+                        return nil, err
+                }
+        }
+
+        if d.code >= d.nrange {
+                return nil, errors.New("newRangeDecoder: d.code >= d.nrange")
+        }
+
+        return d, nil
+}
+
+// possiblyAtEnd checks whether the decoder may be at the end of the stream.
+func (d *rangeDecoder) possiblyAtEnd() bool {
+        return d.code == 0
+}
+
+// DirectDecodeBit decodes a bit with probability 1/2. The return value b will
+// contain the bit at the least-significant position. All other bits will be
+// zero.
+func (d *rangeDecoder) DirectDecodeBit() (b uint32, err error) {
+        d.nrange >>= 1
+        d.code -= d.nrange
+        t := 0 - (d.code >> 31)
+        d.code += d.nrange & t
+        b = (t + 1) & 1
+
+        // d.code will stay less then d.nrange
+
+        // normalize
+        // assume d.code < d.nrange
+        const top = 1 << 24
+        if d.nrange >= top {
+                return b, nil
+        }
+        d.nrange <<= 8
+        // d.code < d.nrange will be maintained
+        return b, d.updateCode()
+}
+
+// decodeBit decodes a single bit. The bit will be returned at the
+// least-significant position. All other bits will be zero. The probability
+// value will be updated.
+func (d *rangeDecoder) DecodeBit(p *prob) (b uint32, err error) {
+        bound := p.bound(d.nrange)
+        if d.code < bound {
+                d.nrange = bound
+                p.inc()
+                b = 0
+        } else {
+                d.code -= bound
+                d.nrange -= bound
+                p.dec()
+                b = 1
+        }
+        // normalize
+        // assume d.code < d.nrange
+        const top = 1 << 24
+        if d.nrange >= top {
+                return b, nil
+        }
+        d.nrange <<= 8
+        // d.code < d.nrange will be maintained
+        return b, d.updateCode()
+}
+
+// updateCode reads a new byte into the code.
+func (d *rangeDecoder) updateCode() error {
+        b, err := d.br.ReadByte()
+        if err != nil {
+                return err
+        }
+        d.code = (d.code << 8) | uint32(b)
+        return nil
+}