summaryrefslogtreecommitdiff
path: root/vendor/github.com/ulikunitz/xz/lzma
diff options
context:
space:
mode:
authorDaniel J Walsh <dwalsh@redhat.com>2018-07-08 07:55:30 -0400
committerAtomic Bot <atomic-devel@projectatomic.io>2018-07-19 18:43:32 +0000
commit98703eb204923f06555605c648fc165a55214520 (patch)
treea407bae8b3489d4f9b0f0d0f228658bbfe95a38e /vendor/github.com/ulikunitz/xz/lzma
parentc020db8cd21cb221cfbe36b264e0ec02999596ed (diff)
downloadpodman-98703eb204923f06555605c648fc165a55214520.tar.gz
podman-98703eb204923f06555605c648fc165a55214520.tar.bz2
podman-98703eb204923f06555605c648fc165a55214520.zip
Vendor in latest code for storage,image, buildah
vendor in containers/storage vendor in containers/image vendor in projectatomic/buildah Signed-off-by: Daniel J Walsh <dwalsh@redhat.com> Closes: #1114 Approved by: mheon
Diffstat (limited to 'vendor/github.com/ulikunitz/xz/lzma')
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/bintree.go523
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/bitops.go45
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/breader.go39
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/buffer.go171
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/bytewriter.go37
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/decoder.go277
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/decoderdict.go135
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/directcodec.go49
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/distcodec.go156
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/encoder.go268
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/encoderdict.go149
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/hashtable.go309
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/header.go167
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/header2.go398
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/lengthcodec.go129
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/literalcodec.go132
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/matchalgorithm.go52
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/operation.go80
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/prob.go53
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/properties.go69
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/rangecodec.go248
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/reader.go100
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/reader2.go232
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/state.go151
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/treecodecs.go133
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/writer.go209
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/writer2.go305
27 files changed, 4616 insertions, 0 deletions
diff --git a/vendor/github.com/ulikunitz/xz/lzma/bintree.go b/vendor/github.com/ulikunitz/xz/lzma/bintree.go
new file mode 100644
index 000000000..a781bd195
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/bintree.go
@@ -0,0 +1,523 @@
+// 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 (
+ "bufio"
+ "errors"
+ "fmt"
+ "io"
+ "unicode"
+)
+
+// node represents a node in the binary tree.
+type node struct {
+ // x is the search value
+ x uint32
+ // p parent node
+ p uint32
+ // l left child
+ l uint32
+ // r right child
+ r uint32
+}
+
+// wordLen is the number of bytes represented by the v field of a node.
+const wordLen = 4
+
+// binTree supports the identification of the next operation based on a
+// binary tree.
+//
+// Nodes will be identified by their index into the ring buffer.
+type binTree struct {
+ dict *encoderDict
+ // ring buffer of nodes
+ node []node
+ // absolute offset of the entry for the next node. Position 4
+ // byte larger.
+ hoff int64
+ // front position in the node ring buffer
+ front uint32
+ // index of the root node
+ root uint32
+ // current x value
+ x uint32
+ // preallocated array
+ data []byte
+}
+
+// null represents the nonexistent index. We can't use zero because it
+// would always exist or we would need to decrease the index for each
+// reference.
+const null uint32 = 1<<32 - 1
+
+// newBinTree initializes the binTree structure. The capacity defines
+// the size of the buffer and defines the maximum distance for which
+// matches will be found.
+func newBinTree(capacity int) (t *binTree, err error) {
+ if capacity < 1 {
+ return nil, errors.New(
+ "newBinTree: capacity must be larger than zero")
+ }
+ if int64(capacity) >= int64(null) {
+ return nil, errors.New(
+ "newBinTree: capacity must less 2^{32}-1")
+ }
+ t = &binTree{
+ node: make([]node, capacity),
+ hoff: -int64(wordLen),
+ root: null,
+ data: make([]byte, maxMatchLen),
+ }
+ return t, nil
+}
+
+func (t *binTree) SetDict(d *encoderDict) { t.dict = d }
+
+// WriteByte writes a single byte into the binary tree.
+func (t *binTree) WriteByte(c byte) error {
+ t.x = (t.x << 8) | uint32(c)
+ t.hoff++
+ if t.hoff < 0 {
+ return nil
+ }
+ v := t.front
+ if int64(v) < t.hoff {
+ // We are overwriting old nodes stored in the tree.
+ t.remove(v)
+ }
+ t.node[v].x = t.x
+ t.add(v)
+ t.front++
+ if int64(t.front) >= int64(len(t.node)) {
+ t.front = 0
+ }
+ return nil
+}
+
+// Writes writes a sequence of bytes into the binTree structure.
+func (t *binTree) Write(p []byte) (n int, err error) {
+ for _, c := range p {
+ t.WriteByte(c)
+ }
+ return len(p), nil
+}
+
+// add puts the node v into the tree. The node must not be part of the
+// tree before.
+func (t *binTree) add(v uint32) {
+ vn := &t.node[v]
+ // Set left and right to null indices.
+ vn.l, vn.r = null, null
+ // If the binary tree is empty make v the root.
+ if t.root == null {
+ t.root = v
+ vn.p = null
+ return
+ }
+ x := vn.x
+ p := t.root
+ // Search for the right leave link and add the new node.
+ for {
+ pn := &t.node[p]
+ if x <= pn.x {
+ if pn.l == null {
+ pn.l = v
+ vn.p = p
+ return
+ }
+ p = pn.l
+ } else {
+ if pn.r == null {
+ pn.r = v
+ vn.p = p
+ return
+ }
+ p = pn.r
+ }
+ }
+}
+
+// parent returns the parent node index of v and the pointer to v value
+// in the parent.
+func (t *binTree) parent(v uint32) (p uint32, ptr *uint32) {
+ if t.root == v {
+ return null, &t.root
+ }
+ p = t.node[v].p
+ if t.node[p].l == v {
+ ptr = &t.node[p].l
+ } else {
+ ptr = &t.node[p].r
+ }
+ return
+}
+
+// Remove node v.
+func (t *binTree) remove(v uint32) {
+ vn := &t.node[v]
+ p, ptr := t.parent(v)
+ l, r := vn.l, vn.r
+ if l == null {
+ // Move the right child up.
+ *ptr = r
+ if r != null {
+ t.node[r].p = p
+ }
+ return
+ }
+ if r == null {
+ // Move the left child up.
+ *ptr = l
+ t.node[l].p = p
+ return
+ }
+
+ // Search the in-order predecessor u.
+ un := &t.node[l]
+ ur := un.r
+ if ur == null {
+ // In order predecessor is l. Move it up.
+ un.r = r
+ t.node[r].p = l
+ un.p = p
+ *ptr = l
+ return
+ }
+ var u uint32
+ for {
+ // Look for the max value in the tree where l is root.
+ u = ur
+ ur = t.node[u].r
+ if ur == null {
+ break
+ }
+ }
+ // replace u with ul
+ un = &t.node[u]
+ ul := un.l
+ up := un.p
+ t.node[up].r = ul
+ if ul != null {
+ t.node[ul].p = up
+ }
+
+ // replace v by u
+ un.l, un.r = l, r
+ t.node[l].p = u
+ t.node[r].p = u
+ *ptr = u
+ un.p = p
+}
+
+// search looks for the node that have the value x or for the nodes that
+// brace it. The node highest in the tree with the value x will be
+// returned. All other nodes with the same value live in left subtree of
+// the returned node.
+func (t *binTree) search(v uint32, x uint32) (a, b uint32) {
+ a, b = null, null
+ if v == null {
+ return
+ }
+ for {
+ vn := &t.node[v]
+ if x <= vn.x {
+ if x == vn.x {
+ return v, v
+ }
+ b = v
+ if vn.l == null {
+ return
+ }
+ v = vn.l
+ } else {
+ a = v
+ if vn.r == null {
+ return
+ }
+ v = vn.r
+ }
+ }
+}
+
+// max returns the node with maximum value in the subtree with v as
+// root.
+func (t *binTree) max(v uint32) uint32 {
+ if v == null {
+ return null
+ }
+ for {
+ r := t.node[v].r
+ if r == null {
+ return v
+ }
+ v = r
+ }
+}
+
+// min returns the node with the minimum value in the subtree with v as
+// root.
+func (t *binTree) min(v uint32) uint32 {
+ if v == null {
+ return null
+ }
+ for {
+ l := t.node[v].l
+ if l == null {
+ return v
+ }
+ v = l
+ }
+}
+
+// pred returns the in-order predecessor of node v.
+func (t *binTree) pred(v uint32) uint32 {
+ if v == null {
+ return null
+ }
+ u := t.max(t.node[v].l)
+ if u != null {
+ return u
+ }
+ for {
+ p := t.node[v].p
+ if p == null {
+ return null
+ }
+ if t.node[p].r == v {
+ return p
+ }
+ v = p
+ }
+}
+
+// succ returns the in-order successor of node v.
+func (t *binTree) succ(v uint32) uint32 {
+ if v == null {
+ return null
+ }
+ u := t.min(t.node[v].r)
+ if u != null {
+ return u
+ }
+ for {
+ p := t.node[v].p
+ if p == null {
+ return null
+ }
+ if t.node[p].l == v {
+ return p
+ }
+ v = p
+ }
+}
+
+// xval converts the first four bytes of a into an 32-bit unsigned
+// integer in big-endian order.
+func xval(a []byte) uint32 {
+ var x uint32
+ switch len(a) {
+ default:
+ x |= uint32(a[3])
+ fallthrough
+ case 3:
+ x |= uint32(a[2]) << 8
+ fallthrough
+ case 2:
+ x |= uint32(a[1]) << 16
+ fallthrough
+ case 1:
+ x |= uint32(a[0]) << 24
+ case 0:
+ }
+ return x
+}
+
+// dumpX converts value x into a four-letter string.
+func dumpX(x uint32) string {
+ a := make([]byte, 4)
+ for i := 0; i < 4; i++ {
+ c := byte(x >> uint((3-i)*8))
+ if unicode.IsGraphic(rune(c)) {
+ a[i] = c
+ } else {
+ a[i] = '.'
+ }
+ }
+ return string(a)
+}
+
+// dumpNode writes a representation of the node v into the io.Writer.
+func (t *binTree) dumpNode(w io.Writer, v uint32, indent int) {
+ if v == null {
+ return
+ }
+
+ vn := &t.node[v]
+
+ t.dumpNode(w, vn.r, indent+2)
+
+ for i := 0; i < indent; i++ {
+ fmt.Fprint(w, " ")
+ }
+ if vn.p == null {
+ fmt.Fprintf(w, "node %d %q parent null\n", v, dumpX(vn.x))
+ } else {
+ fmt.Fprintf(w, "node %d %q parent %d\n", v, dumpX(vn.x), vn.p)
+ }
+
+ t.dumpNode(w, vn.l, indent+2)
+}
+
+// dump prints a representation of the binary tree into the writer.
+func (t *binTree) dump(w io.Writer) error {
+ bw := bufio.NewWriter(w)
+ t.dumpNode(bw, t.root, 0)
+ return bw.Flush()
+}
+
+func (t *binTree) distance(v uint32) int {
+ dist := int(t.front) - int(v)
+ if dist <= 0 {
+ dist += len(t.node)
+ }
+ return dist
+}
+
+type matchParams struct {
+ rep [4]uint32
+ // length when match will be accepted
+ nAccept int
+ // nodes to check
+ check int
+ // finish if length get shorter
+ stopShorter bool
+}
+
+func (t *binTree) match(m match, distIter func() (int, bool), p matchParams,
+) (r match, checked int, accepted bool) {
+ buf := &t.dict.buf
+ for {
+ if checked >= p.check {
+ return m, checked, true
+ }
+ dist, ok := distIter()
+ if !ok {
+ return m, checked, false
+ }
+ checked++
+ if m.n > 0 {
+ i := buf.rear - dist + m.n - 1
+ if i < 0 {
+ i += len(buf.data)
+ } else if i >= len(buf.data) {
+ i -= len(buf.data)
+ }
+ if buf.data[i] != t.data[m.n-1] {
+ if p.stopShorter {
+ return m, checked, false
+ }
+ continue
+ }
+ }
+ n := buf.matchLen(dist, t.data)
+ switch n {
+ case 0:
+ if p.stopShorter {
+ return m, checked, false
+ }
+ continue
+ case 1:
+ if uint32(dist-minDistance) != p.rep[0] {
+ continue
+ }
+ }
+ if n < m.n || (n == m.n && int64(dist) >= m.distance) {
+ continue
+ }
+ m = match{int64(dist), n}
+ if n >= p.nAccept {
+ return m, checked, true
+ }
+ }
+}
+
+func (t *binTree) NextOp(rep [4]uint32) operation {
+ // retrieve maxMatchLen data
+ n, _ := t.dict.buf.Peek(t.data[:maxMatchLen])
+ if n == 0 {
+ panic("no data in buffer")
+ }
+ t.data = t.data[:n]
+
+ var (
+ m match
+ x, u, v uint32
+ iterPred, iterSucc func() (int, bool)
+ )
+ p := matchParams{
+ rep: rep,
+ nAccept: maxMatchLen,
+ check: 32,
+ }
+ i := 4
+ iterSmall := func() (dist int, ok bool) {
+ i--
+ if i <= 0 {
+ return 0, false
+ }
+ return i, true
+ }
+ m, checked, accepted := t.match(m, iterSmall, p)
+ if accepted {
+ goto end
+ }
+ p.check -= checked
+ x = xval(t.data)
+ u, v = t.search(t.root, x)
+ if u == v && len(t.data) == 4 {
+ iter := func() (dist int, ok bool) {
+ if u == null {
+ return 0, false
+ }
+ dist = t.distance(u)
+ u, v = t.search(t.node[u].l, x)
+ if u != v {
+ u = null
+ }
+ return dist, true
+ }
+ m, _, _ = t.match(m, iter, p)
+ goto end
+ }
+ p.stopShorter = true
+ iterSucc = func() (dist int, ok bool) {
+ if v == null {
+ return 0, false
+ }
+ dist = t.distance(v)
+ v = t.succ(v)
+ return dist, true
+ }
+ m, checked, accepted = t.match(m, iterSucc, p)
+ if accepted {
+ goto end
+ }
+ p.check -= checked
+ iterPred = func() (dist int, ok bool) {
+ if u == null {
+ return 0, false
+ }
+ dist = t.distance(u)
+ u = t.pred(u)
+ return dist, true
+ }
+ m, _, _ = t.match(m, iterPred, p)
+end:
+ if m.n == 0 {
+ return lit{t.data[0]}
+ }
+ return m
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/bitops.go b/vendor/github.com/ulikunitz/xz/lzma/bitops.go
new file mode 100644
index 000000000..e9bab0199
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/bitops.go
@@ -0,0 +1,45 @@
+// 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
+
+/* Naming conventions follows the CodeReviewComments in the Go Wiki. */
+
+// ntz32Const is used by the functions NTZ and NLZ.
+const ntz32Const = 0x04d7651f
+
+// ntz32Table is a helper table for de Bruijn algorithm by Danny Dubé.
+// See Henry S. Warren, Jr. "Hacker's Delight" section 5-1 figure 5-26.
+var ntz32Table = [32]int8{
+ 0, 1, 2, 24, 3, 19, 6, 25,
+ 22, 4, 20, 10, 16, 7, 12, 26,
+ 31, 23, 18, 5, 21, 9, 15, 11,
+ 30, 17, 8, 14, 29, 13, 28, 27,
+}
+
+// ntz32 computes the number of trailing zeros for an unsigned 32-bit integer.
+func ntz32(x uint32) int {
+ if x == 0 {
+ return 32
+ }
+ x = (x & -x) * ntz32Const
+ return int(ntz32Table[x>>27])
+}
+
+// nlz32 computes the number of leading zeros for an unsigned 32-bit integer.
+func nlz32(x uint32) int {
+ // Smear left most bit to the right
+ x |= x >> 1
+ x |= x >> 2
+ x |= x >> 4
+ x |= x >> 8
+ x |= x >> 16
+ // Use ntz mechanism to calculate nlz.
+ x++
+ if x == 0 {
+ return 0
+ }
+ x *= ntz32Const
+ return 32 - int(ntz32Table[x>>27])
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/breader.go b/vendor/github.com/ulikunitz/xz/lzma/breader.go
new file mode 100644
index 000000000..5350d814f
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/breader.go
@@ -0,0 +1,39 @@
+// 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"
+)
+
+// breader provides the ReadByte function for a Reader. It doesn't read
+// more data from the reader than absolutely necessary.
+type breader struct {
+ io.Reader
+ // helper slice to save allocations
+ p []byte
+}
+
+// ByteReader converts an io.Reader into an io.ByteReader.
+func ByteReader(r io.Reader) io.ByteReader {
+ br, ok := r.(io.ByteReader)
+ if !ok {
+ return &breader{r, make([]byte, 1)}
+ }
+ return br
+}
+
+// ReadByte read byte function.
+func (r *breader) ReadByte() (c byte, err error) {
+ n, err := r.Reader.Read(r.p)
+ if n < 1 {
+ if err == nil {
+ err = errors.New("breader.ReadByte: no data")
+ }
+ return 0, err
+ }
+ return r.p[0], nil
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/buffer.go b/vendor/github.com/ulikunitz/xz/lzma/buffer.go
new file mode 100644
index 000000000..50e0b6d57
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/buffer.go
@@ -0,0 +1,171 @@
+// 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"
+)
+
+// buffer provides a circular buffer of bytes. If the front index equals
+// the rear index the buffer is empty. As a consequence front cannot be
+// equal rear for a full buffer. So a full buffer has a length that is
+// one byte less the the length of the data slice.
+type buffer struct {
+ data []byte
+ front int
+ rear int
+}
+
+// newBuffer creates a buffer with the given size.
+func newBuffer(size int) *buffer {
+ return &buffer{data: make([]byte, size+1)}
+}
+
+// Cap returns the capacity of the buffer.
+func (b *buffer) Cap() int {
+ return len(b.data) - 1
+}
+
+// Resets the buffer. The front and rear index are set to zero.
+func (b *buffer) Reset() {
+ b.front = 0
+ b.rear = 0
+}
+
+// Buffered returns the number of bytes buffered.
+func (b *buffer) Buffered() int {
+ delta := b.front - b.rear
+ if delta < 0 {
+ delta += len(b.data)
+ }
+ return delta
+}
+
+// Available returns the number of bytes available for writing.
+func (b *buffer) Available() int {
+ delta := b.rear - 1 - b.front
+ if delta < 0 {
+ delta += len(b.data)
+ }
+ return delta
+}
+
+// addIndex adds a non-negative integer to the index i and returns the
+// resulting index. The function takes care of wrapping the index as
+// well as potential overflow situations.
+func (b *buffer) addIndex(i int, n int) int {
+ // subtraction of len(b.data) prevents overflow
+ i += n - len(b.data)
+ if i < 0 {
+ i += len(b.data)
+ }
+ return i
+}
+
+// Read reads bytes from the buffer into p and returns the number of
+// bytes read. The function never returns an error but might return less
+// data than requested.
+func (b *buffer) Read(p []byte) (n int, err error) {
+ n, err = b.Peek(p)
+ b.rear = b.addIndex(b.rear, n)
+ return n, err
+}
+
+// Peek reads bytes from the buffer into p without changing the buffer.
+// Peek will never return an error but might return less data than
+// requested.
+func (b *buffer) Peek(p []byte) (n int, err error) {
+ m := b.Buffered()
+ n = len(p)
+ if m < n {
+ n = m
+ p = p[:n]
+ }
+ k := copy(p, b.data[b.rear:])
+ if k < n {
+ copy(p[k:], b.data)
+ }
+ return n, nil
+}
+
+// Discard skips the n next bytes to read from the buffer, returning the
+// bytes discarded.
+//
+// If Discards skips fewer than n bytes, it returns an error.
+func (b *buffer) Discard(n int) (discarded int, err error) {
+ if n < 0 {
+ return 0, errors.New("buffer.Discard: negative argument")
+ }
+ m := b.Buffered()
+ if m < n {
+ n = m
+ err = errors.New(
+ "buffer.Discard: discarded less bytes then requested")
+ }
+ b.rear = b.addIndex(b.rear, n)
+ return n, err
+}
+
+// ErrNoSpace indicates that there is insufficient space for the Write
+// operation.
+var ErrNoSpace = errors.New("insufficient space")
+
+// Write puts data into the buffer. If less bytes are written than
+// requested ErrNoSpace is returned.
+func (b *buffer) Write(p []byte) (n int, err error) {
+ m := b.Available()
+ n = len(p)
+ if m < n {
+ n = m
+ p = p[:m]
+ err = ErrNoSpace
+ }
+ k := copy(b.data[b.front:], p)
+ if k < n {
+ copy(b.data, p[k:])
+ }
+ b.front = b.addIndex(b.front, n)
+ return n, err
+}
+
+// WriteByte writes a single byte into the buffer. The error ErrNoSpace
+// is returned if no single byte is available in the buffer for writing.
+func (b *buffer) WriteByte(c byte) error {
+ if b.Available() < 1 {
+ return ErrNoSpace
+ }
+ b.data[b.front] = c
+ b.front = b.addIndex(b.front, 1)
+ return nil
+}
+
+// prefixLen returns the length of the common prefix of a and b.
+func prefixLen(a, b []byte) int {
+ if len(a) > len(b) {
+ a, b = b, a
+ }
+ for i, c := range a {
+ if b[i] != c {
+ return i
+ }
+ }
+ return len(a)
+}
+
+// matchLen returns the length of the common prefix for the given
+// distance from the rear and the byte slice p.
+func (b *buffer) matchLen(distance int, p []byte) int {
+ var n int
+ i := b.rear - distance
+ if i < 0 {
+ if n = prefixLen(p, b.data[len(b.data)+i:]); n < -i {
+ return n
+ }
+ p = p[n:]
+ i = 0
+ }
+ n += prefixLen(p, b.data[i:])
+ return n
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/bytewriter.go b/vendor/github.com/ulikunitz/xz/lzma/bytewriter.go
new file mode 100644
index 000000000..a3696ba08
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/bytewriter.go
@@ -0,0 +1,37 @@
+// 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"
+)
+
+// ErrLimit indicates that the limit of the LimitedByteWriter has been
+// reached.
+var ErrLimit = errors.New("limit reached")
+
+// LimitedByteWriter provides a byte writer that can be written until a
+// limit is reached. The field N provides the number of remaining
+// bytes.
+type LimitedByteWriter struct {
+ BW io.ByteWriter
+ N int64
+}
+
+// WriteByte writes a single byte to the limited byte writer. It returns
+// ErrLimit if the limit has been reached. If the byte is successfully
+// written the field N of the LimitedByteWriter will be decremented by
+// one.
+func (l *LimitedByteWriter) WriteByte(c byte) error {
+ if l.N <= 0 {
+ return ErrLimit
+ }
+ if err := l.BW.WriteByte(c); err != nil {
+ return err
+ }
+ l.N--
+ return nil
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/decoder.go b/vendor/github.com/ulikunitz/xz/lzma/decoder.go
new file mode 100644
index 000000000..16e14db39
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/decoder.go
@@ -0,0 +1,277 @@
+// 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"
+ "fmt"
+ "io"
+)
+
+// decoder decodes a raw LZMA stream without any header.
+type decoder struct {
+ // dictionary; the rear pointer of the buffer will be used for
+ // reading the data.
+ Dict *decoderDict
+ // decoder state
+ State *state
+ // range decoder
+ rd *rangeDecoder
+ // start stores the head value of the dictionary for the LZMA
+ // stream
+ start int64
+ // size of uncompressed data
+ size int64
+ // end-of-stream encountered
+ eos bool
+ // EOS marker found
+ eosMarker bool
+}
+
+// newDecoder creates a new decoder instance. The parameter size provides
+// the expected byte size of the decompressed data. If the size is
+// unknown use a negative value. In that case the decoder will look for
+// a terminating end-of-stream marker.
+func newDecoder(br io.ByteReader, state *state, dict *decoderDict, size int64) (d *decoder, err error) {
+ rd, err := newRangeDecoder(br)
+ if err != nil {
+ return nil, err
+ }
+ d = &decoder{
+ State: state,
+ Dict: dict,
+ rd: rd,
+ size: size,
+ start: dict.pos(),
+ }
+ return d, nil
+}
+
+// Reopen restarts the decoder with a new byte reader and a new size. Reopen
+// resets the Decompressed counter to zero.
+func (d *decoder) Reopen(br io.ByteReader, size int64) error {
+ var err error
+ if d.rd, err = newRangeDecoder(br); err != nil {
+ return err
+ }
+ d.start = d.Dict.pos()
+ d.size = size
+ d.eos = false
+ return nil
+}
+
+// decodeLiteral decodes a single literal from the LZMA stream.
+func (d *decoder) decodeLiteral() (op operation, err error) {
+ litState := d.State.litState(d.Dict.byteAt(1), d.Dict.head)
+ match := d.Dict.byteAt(int(d.State.rep[0]) + 1)
+ s, err := d.State.litCodec.Decode(d.rd, d.State.state, match, litState)
+ if err != nil {
+ return nil, err
+ }
+ return lit{s}, nil
+}
+
+// errEOS indicates that an EOS marker has been found.
+var errEOS = errors.New("EOS marker found")
+
+// readOp decodes the next operation from the compressed stream. It
+// returns the operation. If an explicit end of stream marker is
+// identified the eos error is returned.
+func (d *decoder) readOp() (op operation, err error) {
+ // Value of the end of stream (EOS) marker
+ const eosDist = 1<<32 - 1
+
+ state, state2, posState := d.State.states(d.Dict.head)
+
+ b, err := d.State.isMatch[state2].Decode(d.rd)
+ if err != nil {
+ return nil, err
+ }
+ if b == 0 {
+ // literal
+ op, err := d.decodeLiteral()
+ if err != nil {
+ return nil, err
+ }
+ d.State.updateStateLiteral()
+ return op, nil
+ }
+ b, err = d.State.isRep[state].Decode(d.rd)
+ if err != nil {
+ return nil, err
+ }
+ if b == 0 {
+ // simple match
+ d.State.rep[3], d.State.rep[2], d.State.rep[1] =
+ d.State.rep[2], d.State.rep[1], d.State.rep[0]
+
+ d.State.updateStateMatch()
+ // The length decoder returns the length offset.
+ n, err := d.State.lenCodec.Decode(d.rd, posState)
+ if err != nil {
+ return nil, err
+ }
+ // The dist decoder returns the distance offset. The actual
+ // distance is 1 higher.
+ d.State.rep[0], err = d.State.distCodec.Decode(d.rd, n)
+ if err != nil {
+ return nil, err
+ }
+ if d.State.rep[0] == eosDist {
+ d.eosMarker = true
+ return nil, errEOS
+ }
+ op = match{n: int(n) + minMatchLen,
+ distance: int64(d.State.rep[0]) + minDistance}
+ return op, nil
+ }
+ b, err = d.State.isRepG0[state].Decode(d.rd)
+ if err != nil {
+ return nil, err
+ }
+ dist := d.State.rep[0]
+ if b == 0 {
+ // rep match 0
+ b, err = d.State.isRepG0Long[state2].Decode(d.rd)
+ if err != nil {
+ return nil, err
+ }
+ if b == 0 {
+ d.State.updateStateShortRep()
+ op = match{n: 1, distance: int64(dist) + minDistance}
+ return op, nil
+ }
+ } else {
+ b, err = d.State.isRepG1[state].Decode(d.rd)
+ if err != nil {
+ return nil, err
+ }
+ if b == 0 {
+ dist = d.State.rep[1]
+ } else {
+ b, err = d.State.isRepG2[state].Decode(d.rd)
+ if err != nil {
+ return nil, err
+ }
+ if b == 0 {
+ dist = d.State.rep[2]
+ } else {
+ dist = d.State.rep[3]
+ d.State.rep[3] = d.State.rep[2]
+ }
+ d.State.rep[2] = d.State.rep[1]
+ }
+ d.State.rep[1] = d.State.rep[0]
+ d.State.rep[0] = dist
+ }
+ n, err := d.State.repLenCodec.Decode(d.rd, posState)
+ if err != nil {
+ return nil, err
+ }
+ d.State.updateStateRep()
+ op = match{n: int(n) + minMatchLen, distance: int64(dist) + minDistance}
+ return op, nil
+}
+
+// apply takes the operation and transforms the decoder dictionary accordingly.
+func (d *decoder) apply(op operation) error {
+ var err error
+ switch x := op.(type) {
+ case match:
+ err = d.Dict.writeMatch(x.distance, x.n)
+ case lit:
+ err = d.Dict.WriteByte(x.b)
+ default:
+ panic("op is neither a match nor a literal")
+ }
+ return err
+}
+
+// decompress fills the dictionary unless no space for new data is
+// available. If the end of the LZMA stream has been reached io.EOF will
+// be returned.
+func (d *decoder) decompress() error {
+ if d.eos {
+ return io.EOF
+ }
+ for d.Dict.Available() >= maxMatchLen {
+ op, err := d.readOp()
+ switch err {
+ case nil:
+ break
+ case errEOS:
+ d.eos = true
+ if !d.rd.possiblyAtEnd() {
+ return errDataAfterEOS
+ }
+ if d.size >= 0 && d.size != d.Decompressed() {
+ return errSize
+ }
+ return io.EOF
+ case io.EOF:
+ d.eos = true
+ return io.ErrUnexpectedEOF
+ default:
+ return err
+ }
+ if err = d.apply(op); err != nil {
+ return err
+ }
+ if d.size >= 0 && d.Decompressed() >= d.size {
+ d.eos = true
+ if d.Decompressed() > d.size {
+ return errSize
+ }
+ if !d.rd.possiblyAtEnd() {
+ switch _, err = d.readOp(); err {
+ case nil:
+ return errSize
+ case io.EOF:
+ return io.ErrUnexpectedEOF
+ case errEOS:
+ break
+ default:
+ return err
+ }
+ }
+ return io.EOF
+ }
+ }
+ return nil
+}
+
+// Errors that may be returned while decoding data.
+var (
+ errDataAfterEOS = errors.New("lzma: data after end of stream marker")
+ errSize = errors.New("lzma: wrong uncompressed data size")
+)
+
+// Read reads data from the buffer. If no more data is available io.EOF is
+// returned.
+func (d *decoder) Read(p []byte) (n int, err error) {
+ var k int
+ for {
+ // Read of decoder dict never returns an error.
+ k, err = d.Dict.Read(p[n:])
+ if err != nil {
+ panic(fmt.Errorf("dictionary read error %s", err))
+ }
+ if k == 0 && d.eos {
+ return n, io.EOF
+ }
+ n += k
+ if n >= len(p) {
+ return n, nil
+ }
+ if err = d.decompress(); err != nil && err != io.EOF {
+ return n, err
+ }
+ }
+}
+
+// Decompressed returns the number of bytes decompressed by the decoder.
+func (d *decoder) Decompressed() int64 {
+ return d.Dict.pos() - d.start
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/decoderdict.go b/vendor/github.com/ulikunitz/xz/lzma/decoderdict.go
new file mode 100644
index 000000000..564a12b83
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/decoderdict.go
@@ -0,0 +1,135 @@
+// 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"
+ "fmt"
+)
+
+// decoderDict provides the dictionary for the decoder. The whole
+// dictionary is used as reader buffer.
+type decoderDict struct {
+ buf buffer
+ head int64
+}
+
+// newDecoderDict creates a new decoder dictionary. The whole dictionary
+// will be used as reader buffer.
+func newDecoderDict(dictCap int) (d *decoderDict, err error) {
+ // lower limit supports easy test cases
+ if !(1 <= dictCap && int64(dictCap) <= MaxDictCap) {
+ return nil, errors.New("lzma: dictCap out of range")
+ }
+ d = &decoderDict{buf: *newBuffer(dictCap)}
+ return d, nil
+}
+
+// Reset clears the dictionary. The read buffer is not changed, so the
+// buffered data can still be read.
+func (d *decoderDict) Reset() {
+ d.head = 0
+}
+
+// WriteByte writes a single byte into the dictionary. It is used to
+// write literals into the dictionary.
+func (d *decoderDict) WriteByte(c byte) error {
+ if err := d.buf.WriteByte(c); err != nil {
+ return err
+ }
+ d.head++
+ return nil
+}
+
+// pos returns the position of the dictionary head.
+func (d *decoderDict) pos() int64 { return d.head }
+
+// dictLen returns the actual length of the dictionary.
+func (d *decoderDict) dictLen() int {
+ capacity := d.buf.Cap()
+ if d.head >= int64(capacity) {
+ return capacity
+ }
+ return int(d.head)
+}
+
+// byteAt returns a byte stored in the dictionary. If the distance is
+// non-positive or exceeds the current length of the dictionary the zero
+// byte is returned.
+func (d *decoderDict) byteAt(dist int) byte {
+ if !(0 < dist && dist <= d.dictLen()) {
+ return 0
+ }
+ i := d.buf.front - dist
+ if i < 0 {
+ i += len(d.buf.data)
+ }
+ return d.buf.data[i]
+}
+
+// writeMatch writes the match at the top of the dictionary. The given
+// distance must point in the current dictionary and the length must not
+// exceed the maximum length 273 supported in LZMA.
+//
+// The error value ErrNoSpace indicates that no space is available in
+// the dictionary for writing. You need to read from the dictionary
+// first.
+func (d *decoderDict) writeMatch(dist int64, length int) error {
+ if !(0 < dist && dist <= int64(d.dictLen())) {
+ return errors.New("writeMatch: distance out of range")
+ }
+ if !(0 < length && length <= maxMatchLen) {
+ return errors.New("writeMatch: length out of range")
+ }
+ if length > d.buf.Available() {
+ return ErrNoSpace
+ }
+ d.head += int64(length)
+
+ i := d.buf.front - int(dist)
+ if i < 0 {
+ i += len(d.buf.data)
+ }
+ for length > 0 {
+ var p []byte
+ if i >= d.buf.front {
+ p = d.buf.data[i:]
+ i = 0
+ } else {
+ p = d.buf.data[i:d.buf.front]
+ i = d.buf.front
+ }
+ if len(p) > length {
+ p = p[:length]
+ }
+ if _, err := d.buf.Write(p); err != nil {
+ panic(fmt.Errorf("d.buf.Write returned error %s", err))
+ }
+ length -= len(p)
+ }
+ return nil
+}
+
+// Write writes the given bytes into the dictionary and advances the
+// head.
+func (d *decoderDict) Write(p []byte) (n int, err error) {
+ n, err = d.buf.Write(p)
+ d.head += int64(n)
+ return n, err
+}
+
+// Available returns the number of available bytes for writing into the
+// decoder dictionary.
+func (d *decoderDict) Available() int { return d.buf.Available() }
+
+// Read reads data from the buffer contained in the decoder dictionary.
+func (d *decoderDict) Read(p []byte) (n int, err error) { return d.buf.Read(p) }
+
+// Buffered returns the number of bytes currently buffered in the
+// decoder dictionary.
+func (d *decoderDict) buffered() int { return d.buf.Buffered() }
+
+// Peek gets data from the buffer without advancing the rear index.
+func (d *decoderDict) peek(p []byte) (n int, err error) { return d.buf.Peek(p) }
diff --git a/vendor/github.com/ulikunitz/xz/lzma/directcodec.go b/vendor/github.com/ulikunitz/xz/lzma/directcodec.go
new file mode 100644
index 000000000..e08eb989f
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/directcodec.go
@@ -0,0 +1,49 @@
+// 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 "fmt"
+
+// directCodec allows the encoding and decoding of values with a fixed number
+// of bits. The number of bits must be in the range [1,32].
+type directCodec byte
+
+// makeDirectCodec creates a directCodec. The function panics if the number of
+// bits is not in the range [1,32].
+func makeDirectCodec(bits int) directCodec {
+ if !(1 <= bits && bits <= 32) {
+ panic(fmt.Errorf("bits=%d out of range", bits))
+ }
+ return directCodec(bits)
+}
+
+// Bits returns the number of bits supported by this codec.
+func (dc directCodec) Bits() int {
+ return int(dc)
+}
+
+// Encode uses the range encoder to encode a value with the fixed number of
+// bits. The most-significant bit is encoded first.
+func (dc directCodec) Encode(e *rangeEncoder, v uint32) error {
+ for i := int(dc) - 1; i >= 0; i-- {
+ if err := e.DirectEncodeBit(v >> uint(i)); err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
+// Decode uses the range decoder to decode a value with the given number of
+// given bits. The most-significant bit is decoded first.
+func (dc directCodec) Decode(d *rangeDecoder) (v uint32, err error) {
+ for i := int(dc) - 1; i >= 0; i-- {
+ x, err := d.DirectDecodeBit()
+ if err != nil {
+ return 0, err
+ }
+ v = (v << 1) | x
+ }
+ return v, nil
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/distcodec.go b/vendor/github.com/ulikunitz/xz/lzma/distcodec.go
new file mode 100644
index 000000000..b053a2dce
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/distcodec.go
@@ -0,0 +1,156 @@
+// 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
+
+// Constants used by the distance codec.
+const (
+ // minimum supported distance
+ minDistance = 1
+ // maximum supported distance, value is used for the eos marker.
+ maxDistance = 1 << 32
+ // number of the supported len states
+ lenStates = 4
+ // start for the position models
+ startPosModel = 4
+ // first index with align bits support
+ endPosModel = 14
+ // bits for the position slots
+ posSlotBits = 6
+ // number of align bits
+ alignBits = 4
+ // maximum position slot
+ maxPosSlot = 63
+)
+
+// distCodec provides encoding and decoding of distance values.
+type distCodec struct {
+ posSlotCodecs [lenStates]treeCodec
+ posModel [endPosModel - startPosModel]treeReverseCodec
+ alignCodec treeReverseCodec
+}
+
+// deepcopy initializes dc as deep copy of the source.
+func (dc *distCodec) deepcopy(src *distCodec) {
+ if dc == src {
+ return
+ }
+ for i := range dc.posSlotCodecs {
+ dc.posSlotCodecs[i].deepcopy(&src.posSlotCodecs[i])
+ }
+ for i := range dc.posModel {
+ dc.posModel[i].deepcopy(&src.posModel[i])
+ }
+ dc.alignCodec.deepcopy(&src.alignCodec)
+}
+
+// distBits returns the number of bits required to encode dist.
+func distBits(dist uint32) int {
+ if dist < startPosModel {
+ return 6
+ }
+ // slot s > 3, dist d
+ // s = 2(bits(d)-1) + bit(d, bits(d)-2)
+ // s>>1 = bits(d)-1
+ // bits(d) = 32-nlz32(d)
+ // s>>1=31-nlz32(d)
+ // n = 5 + (s>>1) = 36 - nlz32(d)
+ return 36 - nlz32(dist)
+}
+
+// newDistCodec creates a new distance codec.
+func (dc *distCodec) init() {
+ for i := range dc.posSlotCodecs {
+ dc.posSlotCodecs[i] = makeTreeCodec(posSlotBits)
+ }
+ for i := range dc.posModel {
+ posSlot := startPosModel + i
+ bits := (posSlot >> 1) - 1
+ dc.posModel[i] = makeTreeReverseCodec(bits)
+ }
+ dc.alignCodec = makeTreeReverseCodec(alignBits)
+}
+
+// lenState converts the value l to a supported lenState value.
+func lenState(l uint32) uint32 {
+ if l >= lenStates {
+ l = lenStates - 1
+ }
+ return l
+}
+
+// Encode encodes the distance using the parameter l. Dist can have values from
+// the full range of uint32 values. To get the distance offset the actual match
+// distance has to be decreased by 1. A distance offset of 0xffffffff (eos)
+// indicates the end of the stream.
+func (dc *distCodec) Encode(e *rangeEncoder, dist uint32, l uint32) (err error) {
+ // Compute the posSlot using nlz32
+ var posSlot uint32
+ var bits uint32
+ if dist < startPosModel {
+ posSlot = dist
+ } else {
+ bits = uint32(30 - nlz32(dist))
+ posSlot = startPosModel - 2 + (bits << 1)
+ posSlot += (dist >> uint(bits)) & 1
+ }
+
+ if err = dc.posSlotCodecs[lenState(l)].Encode(e, posSlot); err != nil {
+ return
+ }
+
+ switch {
+ case posSlot < startPosModel:
+ return nil
+ case posSlot < endPosModel:
+ tc := &dc.posModel[posSlot-startPosModel]
+ return tc.Encode(dist, e)
+ }
+ dic := directCodec(bits - alignBits)
+ if err = dic.Encode(e, dist>>alignBits); err != nil {
+ return
+ }
+ return dc.alignCodec.Encode(dist, e)
+}
+
+// Decode decodes the distance offset using the parameter l. The dist value
+// 0xffffffff (eos) indicates the end of the stream. Add one to the distance
+// offset to get the actual match distance.
+func (dc *distCodec) Decode(d *rangeDecoder, l uint32) (dist uint32, err error) {
+ posSlot, err := dc.posSlotCodecs[lenState(l)].Decode(d)
+ if err != nil {
+ return
+ }
+
+ // posSlot equals distance
+ if posSlot < startPosModel {
+ return posSlot, nil
+ }
+
+ // posSlot uses the individual models
+ bits := (posSlot >> 1) - 1
+ dist = (2 | (posSlot & 1)) << bits
+ var u uint32
+ if posSlot < endPosModel {
+ tc := &dc.posModel[posSlot-startPosModel]
+ if u, err = tc.Decode(d); err != nil {
+ return 0, err
+ }
+ dist += u
+ return dist, nil
+ }
+
+ // posSlots use direct encoding and a single model for the four align
+ // bits.
+ dic := directCodec(bits - alignBits)
+ if u, err = dic.Decode(d); err != nil {
+ return 0, err
+ }
+ dist += u << alignBits
+ if u, err = dc.alignCodec.Decode(d); err != nil {
+ return 0, err
+ }
+ dist += u
+ return dist, nil
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/encoder.go b/vendor/github.com/ulikunitz/xz/lzma/encoder.go
new file mode 100644
index 000000000..18ce00992
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/encoder.go
@@ -0,0 +1,268 @@
+// 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 (
+ "fmt"
+ "io"
+)
+
+// opLenMargin provides the upper limit of the number of bytes required
+// to encode a single operation.
+const opLenMargin = 10
+
+// compressFlags control the compression process.
+type compressFlags uint32
+
+// Values for compressFlags.
+const (
+ // all data should be compressed, even if compression is not
+ // optimal.
+ all compressFlags = 1 << iota
+)
+
+// encoderFlags provide the flags for an encoder.
+type encoderFlags uint32
+
+// Flags for the encoder.
+const (
+ // eosMarker requests an EOS marker to be written.
+ eosMarker encoderFlags = 1 << iota
+)
+
+// Encoder compresses data buffered in the encoder dictionary and writes
+// it into a byte writer.
+type encoder struct {
+ dict *encoderDict
+ state *state
+ re *rangeEncoder
+ start int64
+ // generate eos marker
+ marker bool
+ limit bool
+ margin int
+}
+
+// newEncoder creates a new encoder. If the byte writer must be
+// limited use LimitedByteWriter provided by this package. The flags
+// argument supports the eosMarker flag, controlling whether a
+// terminating end-of-stream marker must be written.
+func newEncoder(bw io.ByteWriter, state *state, dict *encoderDict,
+ flags encoderFlags) (e *encoder, err error) {
+
+ re, err := newRangeEncoder(bw)
+ if err != nil {
+ return nil, err
+ }
+ e = &encoder{
+ dict: dict,
+ state: state,
+ re: re,
+ marker: flags&eosMarker != 0,
+ start: dict.Pos(),
+ margin: opLenMargin,
+ }
+ if e.marker {
+ e.margin += 5
+ }
+ return e, nil
+}
+
+// Write writes the bytes from p into the dictionary. If not enough
+// space is available the data in the dictionary buffer will be
+// compressed to make additional space available. If the limit of the
+// underlying writer has been reached ErrLimit will be returned.
+func (e *encoder) Write(p []byte) (n int, err error) {
+ for {
+ k, err := e.dict.Write(p[n:])
+ n += k
+ if err == ErrNoSpace {
+ if err = e.compress(0); err != nil {
+ return n, err
+ }
+ continue
+ }
+ return n, err
+ }
+}
+
+// Reopen reopens the encoder with a new byte writer.
+func (e *encoder) Reopen(bw io.ByteWriter) error {
+ var err error
+ if e.re, err = newRangeEncoder(bw); err != nil {
+ return err
+ }
+ e.start = e.dict.Pos()
+ e.limit = false
+ return nil
+}
+
+// writeLiteral writes a literal into the LZMA stream
+func (e *encoder) writeLiteral(l lit) error {
+ var err error
+ state, state2, _ := e.state.states(e.dict.Pos())
+ if err = e.state.isMatch[state2].Encode(e.re, 0); err != nil {
+ return err
+ }
+ litState := e.state.litState(e.dict.ByteAt(1), e.dict.Pos())
+ match := e.dict.ByteAt(int(e.state.rep[0]) + 1)
+ err = e.state.litCodec.Encode(e.re, l.b, state, match, litState)
+ if err != nil {
+ return err
+ }
+ e.state.updateStateLiteral()
+ return nil
+}
+
+// iverson implements the Iverson operator as proposed by Donald Knuth in his
+// book Concrete Mathematics.
+func iverson(ok bool) uint32 {
+ if ok {
+ return 1
+ }
+ return 0
+}
+
+// writeMatch writes a repetition operation into the operation stream
+func (e *encoder) writeMatch(m match) error {
+ var err error
+ if !(minDistance <= m.distance && m.distance <= maxDistance) {
+ panic(fmt.Errorf("match distance %d out of range", m.distance))
+ }
+ dist := uint32(m.distance - minDistance)
+ if !(minMatchLen <= m.n && m.n <= maxMatchLen) &&
+ !(dist == e.state.rep[0] && m.n == 1) {
+ panic(fmt.Errorf(
+ "match length %d out of range; dist %d rep[0] %d",
+ m.n, dist, e.state.rep[0]))
+ }
+ state, state2, posState := e.state.states(e.dict.Pos())
+ if err = e.state.isMatch[state2].Encode(e.re, 1); err != nil {
+ return err
+ }
+ g := 0
+ for ; g < 4; g++ {
+ if e.state.rep[g] == dist {
+ break
+ }
+ }
+ b := iverson(g < 4)
+ if err = e.state.isRep[state].Encode(e.re, b); err != nil {
+ return err
+ }
+ n := uint32(m.n - minMatchLen)
+ if b == 0 {
+ // simple match
+ e.state.rep[3], e.state.rep[2], e.state.rep[1], e.state.rep[0] =
+ e.state.rep[2], e.state.rep[1], e.state.rep[0], dist
+ e.state.updateStateMatch()
+ if err = e.state.lenCodec.Encode(e.re, n, posState); err != nil {
+ return err
+ }
+ return e.state.distCodec.Encode(e.re, dist, n)
+ }
+ b = iverson(g != 0)
+ if err = e.state.isRepG0[state].Encode(e.re, b); err != nil {
+ return err
+ }
+ if b == 0 {
+ // g == 0
+ b = iverson(m.n != 1)
+ if err = e.state.isRepG0Long[state2].Encode(e.re, b); err != nil {
+ return err
+ }
+ if b == 0 {
+ e.state.updateStateShortRep()
+ return nil
+ }
+ } else {
+ // g in {1,2,3}
+ b = iverson(g != 1)
+ if err = e.state.isRepG1[state].Encode(e.re, b); err != nil {
+ return err
+ }
+ if b == 1 {
+ // g in {2,3}
+ b = iverson(g != 2)
+ err = e.state.isRepG2[state].Encode(e.re, b)
+ if err != nil {
+ return err
+ }
+ if b == 1 {
+ e.state.rep[3] = e.state.rep[2]
+ }
+ e.state.rep[2] = e.state.rep[1]
+ }
+ e.state.rep[1] = e.state.rep[0]
+ e.state.rep[0] = dist
+ }
+ e.state.updateStateRep()
+ return e.state.repLenCodec.Encode(e.re, n, posState)
+}
+
+// writeOp writes a single operation to the range encoder. The function
+// checks whether there is enough space available to close the LZMA
+// stream.
+func (e *encoder) writeOp(op operation) error {
+ if e.re.Available() < int64(e.margin) {
+ return ErrLimit
+ }
+ switch x := op.(type) {
+ case lit:
+ return e.writeLiteral(x)
+ case match:
+ return e.writeMatch(x)
+ default:
+ panic("unexpected operation")
+ }
+}
+
+// compress compressed data from the dictionary buffer. If the flag all
+// is set, all data in the dictionary buffer will be compressed. The
+// function returns ErrLimit if the underlying writer has reached its
+// limit.
+func (e *encoder) compress(flags compressFlags) error {
+ n := 0
+ if flags&all == 0 {
+ n = maxMatchLen - 1
+ }
+ d := e.dict
+ m := d.m
+ for d.Buffered() > n {
+ op := m.NextOp(e.state.rep)
+ if err := e.writeOp(op); err != nil {
+ return err
+ }
+ d.Discard(op.Len())
+ }
+ return nil
+}
+
+// eosMatch is a pseudo operation that indicates the end of the stream.
+var eosMatch = match{distance: maxDistance, n: minMatchLen}
+
+// Close terminates the LZMA stream. If requested the end-of-stream
+// marker will be written. If the byte writer limit has been or will be
+// reached during compression of the remaining data in the buffer the
+// LZMA stream will be closed and data will remain in the buffer.
+func (e *encoder) Close() error {
+ err := e.compress(all)
+ if err != nil && err != ErrLimit {
+ return err
+ }
+ if e.marker {
+ if err := e.writeMatch(eosMatch); err != nil {
+ return err
+ }
+ }
+ err = e.re.Close()
+ return err
+}
+
+// Compressed returns the number bytes of the input data that been
+// compressed.
+func (e *encoder) Compressed() int64 {
+ return e.dict.Pos() - e.start
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/encoderdict.go b/vendor/github.com/ulikunitz/xz/lzma/encoderdict.go
new file mode 100644
index 000000000..9d0fbc703
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/encoderdict.go
@@ -0,0 +1,149 @@
+// 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"
+ "fmt"
+ "io"
+)
+
+// matcher is an interface that supports the identification of the next
+// operation.
+type matcher interface {
+ io.Writer
+ SetDict(d *encoderDict)
+ NextOp(rep [4]uint32) operation
+}
+
+// encoderDict provides the dictionary of the encoder. It includes an
+// addtional buffer atop of the actual dictionary.
+type encoderDict struct {
+ buf buffer
+ m matcher
+ head int64
+ capacity int
+ // preallocated array
+ data [maxMatchLen]byte
+}
+
+// newEncoderDict creates the encoder dictionary. The argument bufSize
+// defines the size of the additional buffer.
+func newEncoderDict(dictCap, bufSize int, m matcher) (d *encoderDict, err error) {
+ if !(1 <= dictCap && int64(dictCap) <= MaxDictCap) {
+ return nil, errors.New(
+ "lzma: dictionary capacity out of range")
+ }
+ if bufSize < 1 {
+ return nil, errors.New(
+ "lzma: buffer size must be larger than zero")
+ }
+ d = &encoderDict{
+ buf: *newBuffer(dictCap + bufSize),
+ capacity: dictCap,
+ m: m,
+ }
+ m.SetDict(d)
+ return d, nil
+}
+
+// Discard discards n bytes. Note that n must not be larger than
+// MaxMatchLen.
+func (d *encoderDict) Discard(n int) {
+ p := d.data[:n]
+ k, _ := d.buf.Read(p)
+ if k < n {
+ panic(fmt.Errorf("lzma: can't discard %d bytes", n))
+ }
+ d.head += int64(n)
+ d.m.Write(p)
+}
+
+// Len returns the data available in the encoder dictionary.
+func (d *encoderDict) Len() int {
+ n := d.buf.Available()
+ if int64(n) > d.head {
+ return int(d.head)
+ }
+ return n
+}
+
+// DictLen returns the actual length of data in the dictionary.
+func (d *encoderDict) DictLen() int {
+ if d.head < int64(d.capacity) {
+ return int(d.head)
+ }
+ return d.capacity
+}
+
+// Available returns the number of bytes that can be written by a
+// following Write call.
+func (d *encoderDict) Available() int {
+ return d.buf.Available() - d.DictLen()
+}
+
+// Write writes data into the dictionary buffer. Note that the position
+// of the dictionary head will not be moved. If there is not enough
+// space in the buffer ErrNoSpace will be returned.
+func (d *encoderDict) Write(p []byte) (n int, err error) {
+ m := d.Available()
+ if len(p) > m {
+ p = p[:m]
+ err = ErrNoSpace
+ }
+ var e error
+ if n, e = d.buf.Write(p); e != nil {
+ err = e
+ }
+ return n, err
+}
+
+// Pos returns the position of the head.
+func (d *encoderDict) Pos() int64 { return d.head }
+
+// ByteAt returns the byte at the given distance.
+func (d *encoderDict) ByteAt(distance int) byte {
+ if !(0 < distance && distance <= d.Len()) {
+ return 0
+ }
+ i := d.buf.rear - distance
+ if i < 0 {
+ i += len(d.buf.data)
+ }
+ return d.buf.data[i]
+}
+
+// CopyN copies the last n bytes from the dictionary into the provided
+// writer. This is used for copying uncompressed data into an
+// uncompressed segment.
+func (d *encoderDict) CopyN(w io.Writer, n int) (written int, err error) {
+ if n <= 0 {
+ return 0, nil
+ }
+ m := d.Len()
+ if n > m {
+ n = m
+ err = ErrNoSpace
+ }
+ i := d.buf.rear - n
+ var e error
+ if i < 0 {
+ i += len(d.buf.data)
+ if written, e = w.Write(d.buf.data[i:]); e != nil {
+ return written, e
+ }
+ i = 0
+ }
+ var k int
+ k, e = w.Write(d.buf.data[i:d.buf.rear])
+ written += k
+ if e != nil {
+ err = e
+ }
+ return written, err
+}
+
+// Buffered returns the number of bytes in the buffer.
+func (d *encoderDict) Buffered() int { return d.buf.Buffered() }
diff --git a/vendor/github.com/ulikunitz/xz/lzma/hashtable.go b/vendor/github.com/ulikunitz/xz/lzma/hashtable.go
new file mode 100644
index 000000000..d786a9745
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/hashtable.go
@@ -0,0 +1,309 @@
+// 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"
+ "fmt"
+
+ "github.com/ulikunitz/xz/internal/hash"
+)
+
+/* For compression we need to find byte sequences that match the byte
+ * sequence at the dictionary head. A hash table is a simple method to
+ * provide this capability.
+ */
+
+// maxMatches limits the number of matches requested from the Matches
+// function. This controls the speed of the overall encoding.
+const maxMatches = 16
+
+// shortDists defines the number of short distances supported by the
+// implementation.
+const shortDists = 8
+
+// The minimum is somehow arbitrary but the maximum is limited by the
+// memory requirements of the hash table.
+const (
+ minTableExponent = 9
+ maxTableExponent = 20
+)
+
+// newRoller contains the function used to create an instance of the
+// hash.Roller.
+var newRoller = func(n int) hash.Roller { return hash.NewCyclicPoly(n) }
+
+// hashTable stores the hash table including the rolling hash method.
+//
+// We implement chained hashing into a circular buffer. Each entry in
+// the circular buffer stores the delta distance to the next position with a
+// word that has the same hash value.
+type hashTable struct {
+ dict *encoderDict
+ // actual hash table
+ t []int64
+ // circular list data with the offset to the next word
+ data []uint32
+ front int
+ // mask for computing the index for the hash table
+ mask uint64
+ // hash offset; initial value is -int64(wordLen)
+ hoff int64
+ // length of the hashed word
+ wordLen int
+ // hash roller for computing the hash values for the Write
+ // method
+ wr hash.Roller
+ // hash roller for computing arbitrary hashes
+ hr hash.Roller
+ // preallocated slices
+ p [maxMatches]int64
+ distances [maxMatches + shortDists]int
+}
+
+// hashTableExponent derives the hash table exponent from the dictionary
+// capacity.
+func hashTableExponent(n uint32) int {
+ e := 30 - nlz32(n)
+ switch {
+ case e < minTableExponent:
+ e = minTableExponent
+ case e > maxTableExponent:
+ e = maxTableExponent
+ }
+ return e
+}
+
+// newHashTable creates a new hash table for words of length wordLen
+func newHashTable(capacity int, wordLen int) (t *hashTable, err error) {
+ if !(0 < capacity) {
+ return nil, errors.New(
+ "newHashTable: capacity must not be negative")
+ }
+ exp := hashTableExponent(uint32(capacity))
+ if !(1 <= wordLen && wordLen <= 4) {
+ return nil, errors.New("newHashTable: " +
+ "argument wordLen out of range")
+ }
+ n := 1 << uint(exp)
+ if n <= 0 {
+ panic("newHashTable: exponent is too large")
+ }
+ t = &hashTable{
+ t: make([]int64, n),
+ data: make([]uint32, capacity),
+ mask: (uint64(1) << uint(exp)) - 1,
+ hoff: -int64(wordLen),
+ wordLen: wordLen,
+ wr: newRoller(wordLen),
+ hr: newRoller(wordLen),
+ }
+ return t, nil
+}
+
+func (t *hashTable) SetDict(d *encoderDict) { t.dict = d }
+
+// buffered returns the number of bytes that are currently hashed.
+func (t *hashTable) buffered() int {
+ n := t.hoff + 1
+ switch {
+ case n <= 0:
+ return 0
+ case n >= int64(len(t.data)):
+ return len(t.data)
+ }
+ return int(n)
+}
+
+// addIndex adds n to an index ensuring that is stays inside the
+// circular buffer for the hash chain.
+func (t *hashTable) addIndex(i, n int) int {
+ i += n - len(t.data)
+ if i < 0 {
+ i += len(t.data)
+ }
+ return i
+}
+
+// putDelta puts the delta instance at the current front of the circular
+// chain buffer.
+func (t *hashTable) putDelta(delta uint32) {
+ t.data[t.front] = delta
+ t.front = t.addIndex(t.front, 1)
+}
+
+// putEntry puts a new entry into the hash table. If there is already a
+// value stored it is moved into the circular chain buffer.
+func (t *hashTable) putEntry(h uint64, pos int64) {
+ if pos < 0 {
+ return
+ }
+ i := h & t.mask
+ old := t.t[i] - 1
+ t.t[i] = pos + 1
+ var delta int64
+ if old >= 0 {
+ delta = pos - old
+ if delta > 1<<32-1 || delta > int64(t.buffered()) {
+ delta = 0
+ }
+ }
+ t.putDelta(uint32(delta))
+}
+
+// WriteByte converts a single byte into a hash and puts them into the hash
+// table.
+func (t *hashTable) WriteByte(b byte) error {
+ h := t.wr.RollByte(b)
+ t.hoff++
+ t.putEntry(h, t.hoff)
+ return nil
+}
+
+// Write converts the bytes provided into hash tables and stores the
+// abbreviated offsets into the hash table. The method will never return an
+// error.
+func (t *hashTable) Write(p []byte) (n int, err error) {
+ for _, b := range p {
+ // WriteByte doesn't generate an error.
+ t.WriteByte(b)
+ }
+ return len(p), nil
+}
+
+// getMatches the matches for a specific hash. The functions returns the
+// number of positions found.
+//
+// TODO: Make a getDistances because that we are actually interested in.
+func (t *hashTable) getMatches(h uint64, positions []int64) (n int) {
+ if t.hoff < 0 || len(positions) == 0 {
+ return 0
+ }
+ buffered := t.buffered()
+ tailPos := t.hoff + 1 - int64(buffered)
+ rear := t.front - buffered
+ if rear >= 0 {
+ rear -= len(t.data)
+ }
+ // get the slot for the hash
+ pos := t.t[h&t.mask] - 1
+ delta := pos - tailPos
+ for {
+ if delta < 0 {
+ return n
+ }
+ positions[n] = tailPos + delta
+ n++
+ if n >= len(positions) {
+ return n
+ }
+ i := rear + int(delta)
+ if i < 0 {
+ i += len(t.data)
+ }
+ u := t.data[i]
+ if u == 0 {
+ return n
+ }
+ delta -= int64(u)
+ }
+}
+
+// hash computes the rolling hash for the word stored in p. For correct
+// results its length must be equal to t.wordLen.
+func (t *hashTable) hash(p []byte) uint64 {
+ var h uint64
+ for _, b := range p {
+ h = t.hr.RollByte(b)
+ }
+ return h
+}
+
+// Matches fills the positions slice with potential matches. The
+// functions returns the number of positions filled into positions. The
+// byte slice p must have word length of the hash table.
+func (t *hashTable) Matches(p []byte, positions []int64) int {
+ if len(p) != t.wordLen {
+ panic(fmt.Errorf(
+ "byte slice must have length %d", t.wordLen))
+ }
+ h := t.hash(p)
+ return t.getMatches(h, positions)
+}
+
+// NextOp identifies the next operation using the hash table.
+//
+// TODO: Use all repetitions to find matches.
+func (t *hashTable) NextOp(rep [4]uint32) operation {
+ // get positions
+ data := t.dict.data[:maxMatchLen]
+ n, _ := t.dict.buf.Peek(data)
+ data = data[:n]
+ var p []int64
+ if n < t.wordLen {
+ p = t.p[:0]
+ } else {
+ p = t.p[:maxMatches]
+ n = t.Matches(data[:t.wordLen], p)
+ p = p[:n]
+ }
+
+ // convert positions in potential distances
+ head := t.dict.head
+ dists := append(t.distances[:0], 1, 2, 3, 4, 5, 6, 7, 8)
+ for _, pos := range p {
+ dis := int(head - pos)
+ if dis > shortDists {
+ dists = append(dists, dis)
+ }
+ }
+
+ // check distances
+ var m match
+ dictLen := t.dict.DictLen()
+ for _, dist := range dists {
+ if dist > dictLen {
+ continue
+ }
+
+ // Here comes a trick. We are only interested in matches
+ // that are longer than the matches we have been found
+ // before. So before we test the whole byte sequence at
+ // the given distance, we test the first byte that would
+ // make the match longer. If it doesn't match the byte
+ // to match, we don't to care any longer.
+ i := t.dict.buf.rear - dist + m.n
+ if i < 0 {
+ i += len(t.dict.buf.data)
+ }
+ if t.dict.buf.data[i] != data[m.n] {
+ // We can't get a longer match. Jump to the next
+ // distance.
+ continue
+ }
+
+ n := t.dict.buf.matchLen(dist, data)
+ switch n {
+ case 0:
+ continue
+ case 1:
+ if uint32(dist-minDistance) != rep[0] {
+ continue
+ }
+ }
+ if n > m.n {
+ m = match{int64(dist), n}
+ if n == len(data) {
+ // No better match will be found.
+ break
+ }
+ }
+ }
+
+ if m.n == 0 {
+ return lit{data[0]}
+ }
+ return m
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/header.go b/vendor/github.com/ulikunitz/xz/lzma/header.go
new file mode 100644
index 000000000..bc708969f
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/header.go
@@ -0,0 +1,167 @@
+// 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"
+ "fmt"
+)
+
+// uint32LE reads an uint32 integer from a byte slice
+func uint32LE(b []byte) uint32 {
+ x := uint32(b[3]) << 24
+ x |= uint32(b[2]) << 16
+ x |= uint32(b[1]) << 8
+ x |= uint32(b[0])
+ return x
+}
+
+// uint64LE converts the uint64 value stored as little endian to an uint64
+// value.
+func uint64LE(b []byte) uint64 {
+ x := uint64(b[7]) << 56
+ x |= uint64(b[6]) << 48
+ x |= uint64(b[5]) << 40
+ x |= uint64(b[4]) << 32
+ x |= uint64(b[3]) << 24
+ x |= uint64(b[2]) << 16
+ x |= uint64(b[1]) << 8
+ x |= uint64(b[0])
+ return x
+}
+
+// putUint32LE puts an uint32 integer into a byte slice that must have at least
+// a length of 4 bytes.
+func putUint32LE(b []byte, x uint32) {
+ b[0] = byte(x)
+ b[1] = byte(x >> 8)
+ b[2] = byte(x >> 16)
+ b[3] = byte(x >> 24)
+}
+
+// putUint64LE puts the uint64 value into the byte slice as little endian
+// value. The byte slice b must have at least place for 8 bytes.
+func putUint64LE(b []byte, x uint64) {
+ b[0] = byte(x)
+ b[1] = byte(x >> 8)
+ b[2] = byte(x >> 16)
+ b[3] = byte(x >> 24)
+ b[4] = byte(x >> 32)
+ b[5] = byte(x >> 40)
+ b[6] = byte(x >> 48)
+ b[7] = byte(x >> 56)
+}
+
+// noHeaderSize defines the value of the length field in the LZMA header.
+const noHeaderSize uint64 = 1<<64 - 1
+
+// HeaderLen provides the length of the LZMA file header.
+const HeaderLen = 13
+
+// header represents the header of an LZMA file.
+type header struct {
+ properties Properties
+ dictCap int
+ // uncompressed size; negative value if no size is given
+ size int64
+}
+
+// marshalBinary marshals the header.
+func (h *header) marshalBinary() (data []byte, err error) {
+ if err = h.properties.verify(); err != nil {
+ return nil, err
+ }
+ if !(0 <= h.dictCap && int64(h.dictCap) <= MaxDictCap) {
+ return nil, fmt.Errorf("lzma: DictCap %d out of range",
+ h.dictCap)
+ }
+
+ data = make([]byte, 13)
+
+ // property byte
+ data[0] = h.properties.Code()
+
+ // dictionary capacity
+ putUint32LE(data[1:5], uint32(h.dictCap))
+
+ // uncompressed size
+ var s uint64
+ if h.size > 0 {
+ s = uint64(h.size)
+ } else {
+ s = noHeaderSize
+ }
+ putUint64LE(data[5:], s)
+
+ return data, nil
+}
+
+// unmarshalBinary unmarshals the header.
+func (h *header) unmarshalBinary(data []byte) error {
+ if len(data) != HeaderLen {
+ return errors.New("lzma.unmarshalBinary: data has wrong length")
+ }
+
+ // properties
+ var err error
+ if h.properties, err = PropertiesForCode(data[0]); err != nil {
+ return err
+ }
+
+ // dictionary capacity
+ h.dictCap = int(uint32LE(data[1:]))
+ if h.dictCap < 0 {
+ return errors.New(
+ "LZMA header: dictionary capacity exceeds maximum " +
+ "integer")
+ }
+
+ // uncompressed size
+ s := uint64LE(data[5:])
+ if s == noHeaderSize {
+ h.size = -1
+ } else {
+ h.size = int64(s)
+ if h.size < 0 {
+ return errors.New(
+ "LZMA header: uncompressed size " +
+ "out of int64 range")
+ }
+ }
+
+ return nil
+}
+
+// validDictCap checks whether the dictionary capacity is correct. This
+// is used to weed out wrong file headers.
+func validDictCap(dictcap int) bool {
+ if int64(dictcap) == MaxDictCap {
+ return true
+ }
+ for n := uint(10); n < 32; n++ {
+ if dictcap == 1<<n {
+ return true
+ }
+ if dictcap == 1<<n+1<<(n-1) {
+ return true
+ }
+ }
+ return false
+}
+
+// ValidHeader checks for a valid LZMA file header. It allows only
+// dictionary sizes of 2^n or 2^n+2^(n-1) with n >= 10 or 2^32-1. If
+// there is an explicit size it must not exceed 256 GiB. The length of
+// the data argument must be HeaderLen.
+func ValidHeader(data []byte) bool {
+ var h header
+ if err := h.unmarshalBinary(data); err != nil {
+ return false
+ }
+ if !validDictCap(h.dictCap) {
+ return false
+ }
+ return h.size < 0 || h.size <= 1<<38
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/header2.go b/vendor/github.com/ulikunitz/xz/lzma/header2.go
new file mode 100644
index 000000000..ac6a71a5a
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/header2.go
@@ -0,0 +1,398 @@
+// 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"
+ "fmt"
+ "io"
+)
+
+const (
+ // maximum size of compressed data in a chunk
+ maxCompressed = 1 << 16
+ // maximum size of uncompressed data in a chunk
+ maxUncompressed = 1 << 21
+)
+
+// chunkType represents the type of an LZMA2 chunk. Note that this
+// value is an internal representation and no actual encoding of a LZMA2
+// chunk header.
+type chunkType byte
+
+// Possible values for the chunk type.
+const (
+ // end of stream
+ cEOS chunkType = iota
+ // uncompressed; reset dictionary
+ cUD
+ // uncompressed; no reset of dictionary
+ cU
+ // LZMA compressed; no reset
+ cL
+ // LZMA compressed; reset state
+ cLR
+ // LZMA compressed; reset state; new property value
+ cLRN
+ // LZMA compressed; reset state; new property value; reset dictionary
+ cLRND
+)
+
+// chunkTypeStrings provide a string representation for the chunk types.
+var chunkTypeStrings = [...]string{
+ cEOS: "EOS",
+ cU: "U",
+ cUD: "UD",
+ cL: "L",
+ cLR: "LR",
+ cLRN: "LRN",
+ cLRND: "LRND",
+}
+
+// String returns a string representation of the chunk type.
+func (c chunkType) String() string {
+ if !(cEOS <= c && c <= cLRND) {
+ return "unknown"
+ }
+ return chunkTypeStrings[c]
+}
+
+// Actual encodings for the chunk types in the value. Note that the high
+// uncompressed size bits are stored in the header byte additionally.
+const (
+ hEOS = 0
+ hUD = 1
+ hU = 2
+ hL = 1 << 7
+ hLR = 1<<7 | 1<<5
+ hLRN = 1<<7 | 1<<6
+ hLRND = 1<<7 | 1<<6 | 1<<5
+)
+
+// errHeaderByte indicates an unsupported value for the chunk header
+// byte. These bytes starts the variable-length chunk header.
+var errHeaderByte = errors.New("lzma: unsupported chunk header byte")
+
+// headerChunkType converts the header byte into a chunk type. It
+// ignores the uncompressed size bits in the chunk header byte.
+func headerChunkType(h byte) (c chunkType, err error) {
+ if h&hL == 0 {
+ // no compression
+ switch h {
+ case hEOS:
+ c = cEOS
+ case hUD:
+ c = cUD
+ case hU:
+ c = cU
+ default:
+ return 0, errHeaderByte
+ }
+ return
+ }
+ switch h & hLRND {
+ case hL:
+ c = cL
+ case hLR:
+ c = cLR
+ case hLRN:
+ c = cLRN
+ case hLRND:
+ c = cLRND
+ default:
+ return 0, errHeaderByte
+ }
+ return
+}
+
+// uncompressedHeaderLen provides the length of an uncompressed header
+const uncompressedHeaderLen = 3
+
+// headerLen returns the length of the LZMA2 header for a given chunk
+// type.
+func headerLen(c chunkType) int {
+ switch c {
+ case cEOS:
+ return 1
+ case cU, cUD:
+ return uncompressedHeaderLen
+ case cL, cLR:
+ return 5
+ case cLRN, cLRND:
+ return 6
+ }
+ panic(fmt.Errorf("unsupported chunk type %d", c))
+}
+
+// chunkHeader represents the contents of a chunk header.
+type chunkHeader struct {
+ ctype chunkType
+ uncompressed uint32
+ compressed uint16
+ props Properties
+}
+
+// String returns a string representation of the chunk header.
+func (h *chunkHeader) String() string {
+ return fmt.Sprintf("%s %d %d %s", h.ctype, h.uncompressed,
+ h.compressed, &h.props)
+}
+
+// UnmarshalBinary reads the content of the chunk header from the data
+// slice. The slice must have the correct length.
+func (h *chunkHeader) UnmarshalBinary(data []byte) error {
+ if len(data) == 0 {
+ return errors.New("no data")
+ }
+ c, err := headerChunkType(data[0])
+ if err != nil {
+ return err
+ }
+
+ n := headerLen(c)
+ if len(data) < n {
+ return errors.New("incomplete data")
+ }
+ if len(data) > n {
+ return errors.New("invalid data length")
+ }
+
+ *h = chunkHeader{ctype: c}
+ if c == cEOS {
+ return nil
+ }
+
+ h.uncompressed = uint32(uint16BE(data[1:3]))
+ if c <= cU {
+ return nil
+ }
+ h.uncompressed |= uint32(data[0]&^hLRND) << 16
+
+ h.compressed = uint16BE(data[3:5])
+ if c <= cLR {
+ return nil
+ }
+
+ h.props, err = PropertiesForCode(data[5])
+ return err
+}
+
+// MarshalBinary encodes the chunk header value. The function checks
+// whether the content of the chunk header is correct.
+func (h *chunkHeader) MarshalBinary() (data []byte, err error) {
+ if h.ctype > cLRND {
+ return nil, errors.New("invalid chunk type")
+ }
+ if err = h.props.verify(); err != nil {
+ return nil, err
+ }
+
+ data = make([]byte, headerLen(h.ctype))
+
+ switch h.ctype {
+ case cEOS:
+ return data, nil
+ case cUD:
+ data[0] = hUD
+ case cU:
+ data[0] = hU
+ case cL:
+ data[0] = hL
+ case cLR:
+ data[0] = hLR
+ case cLRN:
+ data[0] = hLRN
+ case cLRND:
+ data[0] = hLRND
+ }
+
+ putUint16BE(data[1:3], uint16(h.uncompressed))
+ if h.ctype <= cU {
+ return data, nil
+ }
+ data[0] |= byte(h.uncompressed>>16) &^ hLRND
+
+ putUint16BE(data[3:5], h.compressed)
+ if h.ctype <= cLR {
+ return data, nil
+ }
+
+ data[5] = h.props.Code()
+ return data, nil
+}
+
+// readChunkHeader reads the chunk header from the IO reader.
+func readChunkHeader(r io.Reader) (h *chunkHeader, err error) {
+ p := make([]byte, 1, 6)
+ if _, err = io.ReadFull(r, p); err != nil {
+ return
+ }
+ c, err := headerChunkType(p[0])
+ if err != nil {
+ return
+ }
+ p = p[:headerLen(c)]
+ if _, err = io.ReadFull(r, p[1:]); err != nil {
+ return
+ }
+ h = new(chunkHeader)
+ if err = h.UnmarshalBinary(p); err != nil {
+ return nil, err
+ }
+ return h, nil
+}
+
+// uint16BE converts a big-endian uint16 representation to an uint16
+// value.
+func uint16BE(p []byte) uint16 {
+ return uint16(p[0])<<8 | uint16(p[1])
+}
+
+// putUint16BE puts the big-endian uint16 presentation into the given
+// slice.
+func putUint16BE(p []byte, x uint16) {
+ p[0] = byte(x >> 8)
+ p[1] = byte(x)
+}
+
+// chunkState is used to manage the state of the chunks
+type chunkState byte
+
+// start and stop define the initial and terminating state of the chunk
+// state
+const (
+ start chunkState = 'S'
+ stop = 'T'
+)
+
+// errors for the chunk state handling
+var (
+ errChunkType = errors.New("lzma: unexpected chunk type")
+ errState = errors.New("lzma: wrong chunk state")
+)
+
+// next transitions state based on chunk type input
+func (c *chunkState) next(ctype chunkType) error {
+ switch *c {
+ // start state
+ case 'S':
+ switch ctype {
+ case cEOS:
+ *c = 'T'
+ case cUD:
+ *c = 'R'
+ case cLRND:
+ *c = 'L'
+ default:
+ return errChunkType
+ }
+ // normal LZMA mode
+ case 'L':
+ switch ctype {
+ case cEOS:
+ *c = 'T'
+ case cUD:
+ *c = 'R'
+ case cU:
+ *c = 'U'
+ case cL, cLR, cLRN, cLRND:
+ break
+ default:
+ return errChunkType
+ }
+ // reset required
+ case 'R':
+ switch ctype {
+ case cEOS:
+ *c = 'T'
+ case cUD, cU:
+ break
+ case cLRN, cLRND:
+ *c = 'L'
+ default:
+ return errChunkType
+ }
+ // uncompressed
+ case 'U':
+ switch ctype {
+ case cEOS:
+ *c = 'T'
+ case cUD:
+ *c = 'R'
+ case cU:
+ break
+ case cL, cLR, cLRN, cLRND:
+ *c = 'L'
+ default:
+ return errChunkType
+ }
+ // terminal state
+ case 'T':
+ return errChunkType
+ default:
+ return errState
+ }
+ return nil
+}
+
+// defaultChunkType returns the default chunk type for each chunk state.
+func (c chunkState) defaultChunkType() chunkType {
+ switch c {
+ case 'S':
+ return cLRND
+ case 'L', 'U':
+ return cL
+ case 'R':
+ return cLRN
+ default:
+ // no error
+ return cEOS
+ }
+}
+
+// maxDictCap defines the maximum dictionary capacity supported by the
+// LZMA2 dictionary capacity encoding.
+const maxDictCap = 1<<32 - 1
+
+// maxDictCapCode defines the maximum dictionary capacity code.
+const maxDictCapCode = 40
+
+// The function decodes the dictionary capacity byte, but doesn't change
+// for the correct range of the given byte.
+func decodeDictCap(c byte) int64 {
+ return (2 | int64(c)&1) << (11 + (c>>1)&0x1f)
+}
+
+// DecodeDictCap decodes the encoded dictionary capacity. The function
+// returns an error if the code is out of range.
+func DecodeDictCap(c byte) (n int64, err error) {
+ if c >= maxDictCapCode {
+ if c == maxDictCapCode {
+ return maxDictCap, nil
+ }
+ return 0, errors.New("lzma: invalid dictionary size code")
+ }
+ return decodeDictCap(c), nil
+}
+
+// EncodeDictCap encodes a dictionary capacity. The function returns the
+// code for the capacity that is greater or equal n. If n exceeds the
+// maximum support dictionary capacity, the maximum value is returned.
+func EncodeDictCap(n int64) byte {
+ a, b := byte(0), byte(40)
+ for a < b {
+ c := a + (b-a)>>1
+ m := decodeDictCap(c)
+ if n <= m {
+ if n == m {
+ return c
+ }
+ b = c
+ } else {
+ a = c + 1
+ }
+ }
+ return a
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/lengthcodec.go b/vendor/github.com/ulikunitz/xz/lzma/lengthcodec.go
new file mode 100644
index 000000000..e51773092
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/lengthcodec.go
@@ -0,0 +1,129 @@
+// 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"
+
+// maxPosBits defines the number of bits of the position value that are used to
+// to compute the posState value. The value is used to select the tree codec
+// for length encoding and decoding.
+const maxPosBits = 4
+
+// minMatchLen and maxMatchLen give the minimum and maximum values for
+// encoding and decoding length values. minMatchLen is also used as base
+// for the encoded length values.
+const (
+ minMatchLen = 2
+ maxMatchLen = minMatchLen + 16 + 256 - 1
+)
+
+// lengthCodec support the encoding of the length value.
+type lengthCodec struct {
+ choice [2]prob
+ low [1 << maxPosBits]treeCodec
+ mid [1 << maxPosBits]treeCodec
+ high treeCodec
+}
+
+// deepcopy initializes the lc value as deep copy of the source value.
+func (lc *lengthCodec) deepcopy(src *lengthCodec) {
+ if lc == src {
+ return
+ }
+ lc.choice = src.choice
+ for i := range lc.low {
+ lc.low[i].deepcopy(&src.low[i])
+ }
+ for i := range lc.mid {
+ lc.mid[i].deepcopy(&src.mid[i])
+ }
+ lc.high.deepcopy(&src.high)
+}
+
+// init initializes a new length codec.
+func (lc *lengthCodec) init() {
+ for i := range lc.choice {
+ lc.choice[i] = probInit
+ }
+ for i := range lc.low {
+ lc.low[i] = makeTreeCodec(3)
+ }
+ for i := range lc.mid {
+ lc.mid[i] = makeTreeCodec(3)
+ }
+ lc.high = makeTreeCodec(8)
+}
+
+// lBits gives the number of bits used for the encoding of the l value
+// provided to the range encoder.
+func lBits(l uint32) int {
+ switch {
+ case l < 8:
+ return 4
+ case l < 16:
+ return 5
+ default:
+ return 10
+ }
+}
+
+// Encode encodes the length offset. The length offset l can be compute by
+// subtracting minMatchLen (2) from the actual length.
+//
+// l = length - minMatchLen
+//
+func (lc *lengthCodec) Encode(e *rangeEncoder, l uint32, posState uint32,
+) (err error) {
+ if l > maxMatchLen-minMatchLen {
+ return errors.New("lengthCodec.Encode: l out of range")
+ }
+ if l < 8 {
+ if err = lc.choice[0].Encode(e, 0); err != nil {
+ return
+ }
+ return lc.low[posState].Encode(e, l)
+ }
+ if err = lc.choice[0].Encode(e, 1); err != nil {
+ return
+ }
+ if l < 16 {
+ if err = lc.choice[1].Encode(e, 0); err != nil {
+ return
+ }
+ return lc.mid[posState].Encode(e, l-8)
+ }
+ if err = lc.choice[1].Encode(e, 1); err != nil {
+ return
+ }
+ if err = lc.high.Encode(e, l-16); err != nil {
+ return
+ }
+ return nil
+}
+
+// Decode reads the length offset. Add minMatchLen to compute the actual length
+// to the length offset l.
+func (lc *lengthCodec) Decode(d *rangeDecoder, posState uint32,
+) (l uint32, err error) {
+ var b uint32
+ if b, err = lc.choice[0].Decode(d); err != nil {
+ return
+ }
+ if b == 0 {
+ l, err = lc.low[posState].Decode(d)
+ return
+ }
+ if b, err = lc.choice[1].Decode(d); err != nil {
+ return
+ }
+ if b == 0 {
+ l, err = lc.mid[posState].Decode(d)
+ l += 8
+ return
+ }
+ l, err = lc.high.Decode(d)
+ l += 16
+ return
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/literalcodec.go b/vendor/github.com/ulikunitz/xz/lzma/literalcodec.go
new file mode 100644
index 000000000..c949d6ebd
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/literalcodec.go
@@ -0,0 +1,132 @@
+// 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
+
+// literalCodec supports the encoding of literal. It provides 768 probability
+// values per literal state. The upper 512 probabilities are used with the
+// context of a match bit.
+type literalCodec struct {
+ probs []prob
+}
+
+// deepcopy initializes literal codec c as a deep copy of the source.
+func (c *literalCodec) deepcopy(src *literalCodec) {
+ if c == src {
+ return
+ }
+ c.probs = make([]prob, len(src.probs))
+ copy(c.probs, src.probs)
+}
+
+// init initializes the literal codec.
+func (c *literalCodec) init(lc, lp int) {
+ switch {
+ case !(minLC <= lc && lc <= maxLC):
+ panic("lc out of range")
+ case !(minLP <= lp && lp <= maxLP):
+ panic("lp out of range")
+ }
+ c.probs = make([]prob, 0x300<<uint(lc+lp))
+ for i := range c.probs {
+ c.probs[i] = probInit
+ }
+}
+
+// Encode encodes the byte s using a range encoder as well as the current LZMA
+// encoder state, a match byte and the literal state.
+func (c *literalCodec) Encode(e *rangeEncoder, s byte,
+ state uint32, match byte, litState uint32,
+) (err error) {
+ k := litState * 0x300
+ probs := c.probs[k : k+0x300]
+ symbol := uint32(1)
+ r := uint32(s)
+ if state >= 7 {
+ m := uint32(match)
+ for {
+ matchBit := (m >> 7) & 1
+ m <<= 1
+ bit := (r >> 7) & 1
+ r <<= 1
+ i := ((1 + matchBit) << 8) | symbol
+ if err = probs[i].Encode(e, bit); err != nil {
+ return
+ }
+ symbol = (symbol << 1) | bit
+ if matchBit != bit {
+ break
+ }
+ if symbol >= 0x100 {
+ break
+ }
+ }
+ }
+ for symbol < 0x100 {
+ bit := (r >> 7) & 1
+ r <<= 1
+ if err = probs[symbol].Encode(e, bit); err != nil {
+ return
+ }
+ symbol = (symbol << 1) | bit
+ }
+ return nil
+}
+
+// Decode decodes a literal byte using the range decoder as well as the LZMA
+// state, a match byte, and the literal state.
+func (c *literalCodec) Decode(d *rangeDecoder,
+ state uint32, match byte, litState uint32,
+) (s byte, err error) {
+ k := litState * 0x300
+ probs := c.probs[k : k+0x300]
+ symbol := uint32(1)
+ if state >= 7 {
+ m := uint32(match)
+ for {
+ matchBit := (m >> 7) & 1
+ m <<= 1
+ i := ((1 + matchBit) << 8) | symbol
+ bit, err := d.DecodeBit(&probs[i])
+ if err != nil {
+ return 0, err
+ }
+ symbol = (symbol << 1) | bit
+ if matchBit != bit {
+ break
+ }
+ if symbol >= 0x100 {
+ break
+ }
+ }
+ }
+ for symbol < 0x100 {
+ bit, err := d.DecodeBit(&probs[symbol])
+ if err != nil {
+ return 0, err
+ }
+ symbol = (symbol << 1) | bit
+ }
+ s = byte(symbol - 0x100)
+ return s, nil
+}
+
+// minLC and maxLC define the range for LC values.
+const (
+ minLC = 0
+ maxLC = 8
+)
+
+// minLC and maxLC define the range for LP values.
+const (
+ minLP = 0
+ maxLP = 4
+)
+
+// minState and maxState define a range for the state values stored in
+// the State values.
+const (
+ minState = 0
+ maxState = 11
+)
diff --git a/vendor/github.com/ulikunitz/xz/lzma/matchalgorithm.go b/vendor/github.com/ulikunitz/xz/lzma/matchalgorithm.go
new file mode 100644
index 000000000..4a244eb1a
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/matchalgorithm.go
@@ -0,0 +1,52 @@
+// 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"
+
+// MatchAlgorithm identifies an algorithm to find matches in the
+// dictionary.
+type MatchAlgorithm byte
+
+// Supported matcher algorithms.
+const (
+ HashTable4 MatchAlgorithm = iota
+ BinaryTree
+)
+
+// maStrings are used by the String method.
+var maStrings = map[MatchAlgorithm]string{
+ HashTable4: "HashTable4",
+ BinaryTree: "BinaryTree",
+}
+
+// String returns a string representation of the Matcher.
+func (a MatchAlgorithm) String() string {
+ if s, ok := maStrings[a]; ok {
+ return s
+ }
+ return "unknown"
+}
+
+var errUnsupportedMatchAlgorithm = errors.New(
+ "lzma: unsupported match algorithm value")
+
+// verify checks whether the matcher value is supported.
+func (a MatchAlgorithm) verify() error {
+ if _, ok := maStrings[a]; !ok {
+ return errUnsupportedMatchAlgorithm
+ }
+ return nil
+}
+
+func (a MatchAlgorithm) new(dictCap int) (m matcher, err error) {
+ switch a {
+ case HashTable4:
+ return newHashTable(dictCap, 4)
+ case BinaryTree:
+ return newBinTree(dictCap)
+ }
+ return nil, errUnsupportedMatchAlgorithm
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/operation.go b/vendor/github.com/ulikunitz/xz/lzma/operation.go
new file mode 100644
index 000000000..733bb99da
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/operation.go
@@ -0,0 +1,80 @@
+// 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"
+ "fmt"
+ "unicode"
+)
+
+// operation represents an operation on the dictionary during encoding or
+// decoding.
+type operation interface {
+ Len() int
+}
+
+// rep represents a repetition at the given distance and the given length
+type match struct {
+ // supports all possible distance values, including the eos marker
+ distance int64
+ // length
+ n int
+}
+
+// verify checks whether the match is valid. If that is not the case an
+// error is returned.
+func (m match) verify() error {
+ if !(minDistance <= m.distance && m.distance <= maxDistance) {
+ return errors.New("distance out of range")
+ }
+ if !(1 <= m.n && m.n <= maxMatchLen) {
+ return errors.New("length out of range")
+ }
+ return nil
+}
+
+// l return the l-value for the match, which is the difference of length
+// n and 2.
+func (m match) l() uint32 {
+ return uint32(m.n - minMatchLen)
+}
+
+// dist returns the dist value for the match, which is one less of the
+// distance stored in the match.
+func (m match) dist() uint32 {
+ return uint32(m.distance - minDistance)
+}
+
+// Len returns the number of bytes matched.
+func (m match) Len() int {
+ return m.n
+}
+
+// String returns a string representation for the repetition.
+func (m match) String() string {
+ return fmt.Sprintf("M{%d,%d}", m.distance, m.n)
+}
+
+// lit represents a single byte literal.
+type lit struct {
+ b byte
+}
+
+// Len returns 1 for the single byte literal.
+func (l lit) Len() int {
+ return 1
+}
+
+// String returns a string representation for the literal.
+func (l lit) String() string {
+ var c byte
+ if unicode.IsPrint(rune(l.b)) {
+ c = l.b
+ } else {
+ c = '.'
+ }
+ return fmt.Sprintf("L{%c/%02x}", c, l.b)
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/prob.go b/vendor/github.com/ulikunitz/xz/lzma/prob.go
new file mode 100644
index 000000000..24d50ec68
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/prob.go
@@ -0,0 +1,53 @@
+// 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
+
+// movebits defines the number of bits used for the updates of probability
+// values.
+const movebits = 5
+
+// probbits defines the number of bits of a probability value.
+const probbits = 11
+
+// probInit defines 0.5 as initial value for prob values.
+const probInit prob = 1 << (probbits - 1)
+
+// Type prob represents probabilities. The type can also be used to encode and
+// decode single bits.
+type prob uint16
+
+// Dec decreases the probability. The decrease is proportional to the
+// probability value.
+func (p *prob) dec() {
+ *p -= *p >> movebits
+}
+
+// Inc increases the probability. The Increase is proportional to the
+// difference of 1 and the probability value.
+func (p *prob) inc() {
+ *p += ((1 << probbits) - *p) >> movebits
+}
+
+// Computes the new bound for a given range using the probability value.
+func (p prob) bound(r uint32) uint32 {
+ return (r >> probbits) * uint32(p)
+}
+
+// Bits returns 1. One is the number of bits that can be encoded or decoded
+// with a single prob value.
+func (p prob) Bits() int {
+ return 1
+}
+
+// Encode encodes the least-significant bit of v. Note that the p value will be
+// changed.
+func (p *prob) Encode(e *rangeEncoder, v uint32) error {
+ return e.EncodeBit(v, p)
+}
+
+// Decode decodes a single bit. Note that the p value will change.
+func (p *prob) Decode(d *rangeDecoder) (v uint32, err error) {
+ return d.DecodeBit(p)
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/properties.go b/vendor/github.com/ulikunitz/xz/lzma/properties.go
new file mode 100644
index 000000000..23418e25d
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/properties.go
@@ -0,0 +1,69 @@
+// 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"
+ "fmt"
+)
+
+// maximum and minimum values for the LZMA properties.
+const (
+ minPB = 0
+ maxPB = 4
+)
+
+// maxPropertyCode is the possible maximum of a properties code byte.
+const maxPropertyCode = (maxPB+1)*(maxLP+1)*(maxLC+1) - 1
+
+// Properties contains the parameters LC, LP and PB. The parameter LC
+// defines the number of literal context bits; parameter LP the number
+// of literal position bits and PB the number of position bits.
+type Properties struct {
+ LC int
+ LP int
+ PB int
+}
+
+// String returns the properties in a string representation.
+func (p *Properties) String() string {
+ return fmt.Sprintf("LC %d LP %d PB %d", p.LC, p.LP, p.PB)
+}
+
+// PropertiesForCode converts a properties code byte into a Properties value.
+func PropertiesForCode(code byte) (p Properties, err error) {
+ if code > maxPropertyCode {
+ return p, errors.New("lzma: invalid properties code")
+ }
+ p.LC = int(code % 9)
+ code /= 9
+ p.LP = int(code % 5)
+ code /= 5
+ p.PB = int(code % 5)
+ return p, err
+}
+
+// verify checks the properties for correctness.
+func (p *Properties) verify() error {
+ if p == nil {
+ return errors.New("lzma: properties are nil")
+ }
+ if !(minLC <= p.LC && p.LC <= maxLC) {
+ return errors.New("lzma: lc out of range")
+ }
+ if !(minLP <= p.LP && p.LP <= maxLP) {
+ return errors.New("lzma: lp out of range")
+ }
+ if !(minPB <= p.PB && p.PB <= maxPB) {
+ return errors.New("lzma: pb out of range")
+ }
+ return nil
+}
+
+// Code converts the properties to a byte. The function assumes that
+// the properties components are all in range.
+func (p Properties) Code() byte {
+ return byte((p.PB*5+p.LP)*9 + p.LC)
+}
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 000000000..6361c5e7c
--- /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
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/reader.go b/vendor/github.com/ulikunitz/xz/lzma/reader.go
new file mode 100644
index 000000000..2ef3dcaaa
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/reader.go
@@ -0,0 +1,100 @@
+// 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 supports the decoding and encoding of LZMA streams.
+// Reader and Writer support the classic LZMA format. Reader2 and
+// Writer2 support the decoding and encoding of LZMA2 streams.
+//
+// The package is written completely in Go and doesn't rely on any external
+// library.
+package lzma
+
+import (
+ "errors"
+ "io"
+)
+
+// ReaderConfig stores the parameters for the reader of the classic LZMA
+// format.
+type ReaderConfig struct {
+ DictCap int
+}
+
+// fill converts the zero values of the configuration to the default values.
+func (c *ReaderConfig) fill() {
+ if c.DictCap == 0 {
+ c.DictCap = 8 * 1024 * 1024
+ }
+}
+
+// Verify checks the reader configuration for errors. Zero values will
+// be replaced by default values.
+func (c *ReaderConfig) Verify() error {
+ c.fill()
+ if !(MinDictCap <= c.DictCap && int64(c.DictCap) <= MaxDictCap) {
+ return errors.New("lzma: dictionary capacity is out of range")
+ }
+ return nil
+}
+
+// Reader provides a reader for LZMA files or streams.
+type Reader struct {
+ lzma io.Reader
+ h header
+ d *decoder
+}
+
+// NewReader creates a new reader for an LZMA stream using the classic
+// format. NewReader reads and checks the header of the LZMA stream.
+func NewReader(lzma io.Reader) (r *Reader, err error) {
+ return ReaderConfig{}.NewReader(lzma)
+}
+
+// NewReader creates a new reader for an LZMA stream in the classic
+// format. The function reads and verifies the the header of the LZMA
+// stream.
+func (c ReaderConfig) NewReader(lzma io.Reader) (r *Reader, err error) {
+ if err = c.Verify(); err != nil {
+ return nil, err
+ }
+ data := make([]byte, HeaderLen)
+ if _, err := io.ReadFull(lzma, data); err != nil {
+ if err == io.EOF {
+ return nil, errors.New("lzma: unexpected EOF")
+ }
+ return nil, err
+ }
+ r = &Reader{lzma: lzma}
+ if err = r.h.unmarshalBinary(data); err != nil {
+ return nil, err
+ }
+ if r.h.dictCap < MinDictCap {
+ return nil, errors.New("lzma: dictionary capacity too small")
+ }
+ dictCap := r.h.dictCap
+ if c.DictCap > dictCap {
+ dictCap = c.DictCap
+ }
+
+ state := newState(r.h.properties)
+ dict, err := newDecoderDict(dictCap)
+ if err != nil {
+ return nil, err
+ }
+ r.d, err = newDecoder(ByteReader(lzma), state, dict, r.h.size)
+ if err != nil {
+ return nil, err
+ }
+ return r, nil
+}
+
+// EOSMarker indicates that an EOS marker has been encountered.
+func (r *Reader) EOSMarker() bool {
+ return r.d.eosMarker
+}
+
+// Read returns uncompressed data.
+func (r *Reader) Read(p []byte) (n int, err error) {
+ return r.d.Read(p)
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/reader2.go b/vendor/github.com/ulikunitz/xz/lzma/reader2.go
new file mode 100644
index 000000000..a55cfaa4e
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/reader2.go
@@ -0,0 +1,232 @@
+// 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"
+
+ "github.com/ulikunitz/xz/internal/xlog"
+)
+
+// Reader2Config stores the parameters for the LZMA2 reader.
+// format.
+type Reader2Config struct {
+ DictCap int
+}
+
+// fill converts the zero values of the configuration to the default values.
+func (c *Reader2Config) fill() {
+ if c.DictCap == 0 {
+ c.DictCap = 8 * 1024 * 1024
+ }
+}
+
+// Verify checks the reader configuration for errors. Zero configuration values
+// will be replaced by default values.
+func (c *Reader2Config) Verify() error {
+ c.fill()
+ if !(MinDictCap <= c.DictCap && int64(c.DictCap) <= MaxDictCap) {
+ return errors.New("lzma: dictionary capacity is out of range")
+ }
+ return nil
+}
+
+// Reader2 supports the reading of LZMA2 chunk sequences. Note that the
+// first chunk should have a dictionary reset and the first compressed
+// chunk a properties reset. The chunk sequence may not be terminated by
+// an end-of-stream chunk.
+type Reader2 struct {
+ r io.Reader
+ err error
+
+ dict *decoderDict
+ ur *uncompressedReader
+ decoder *decoder
+ chunkReader io.Reader
+
+ cstate chunkState
+ ctype chunkType
+}
+
+// NewReader2 creates a reader for an LZMA2 chunk sequence.
+func NewReader2(lzma2 io.Reader) (r *Reader2, err error) {
+ return Reader2Config{}.NewReader2(lzma2)
+}
+
+// NewReader2 creates an LZMA2 reader using the given configuration.
+func (c Reader2Config) NewReader2(lzma2 io.Reader) (r *Reader2, err error) {
+ if err = c.Verify(); err != nil {
+ return nil, err
+ }
+ r = &Reader2{r: lzma2, cstate: start}
+ r.dict, err = newDecoderDict(c.DictCap)
+ if err != nil {
+ return nil, err
+ }
+ if err = r.startChunk(); err != nil {
+ r.err = err
+ }
+ return r, nil
+}
+
+// uncompressed tests whether the chunk type specifies an uncompressed
+// chunk.
+func uncompressed(ctype chunkType) bool {
+ return ctype == cU || ctype == cUD
+}
+
+// startChunk parses a new chunk.
+func (r *Reader2) startChunk() error {
+ r.chunkReader = nil
+ header, err := readChunkHeader(r.r)
+ if err != nil {
+ if err == io.EOF {
+ err = io.ErrUnexpectedEOF
+ }
+ return err
+ }
+ xlog.Debugf("chunk header %v", header)
+ if err = r.cstate.next(header.ctype); err != nil {
+ return err
+ }
+ if r.cstate == stop {
+ return io.EOF
+ }
+ if header.ctype == cUD || header.ctype == cLRND {
+ r.dict.Reset()
+ }
+ size := int64(header.uncompressed) + 1
+ if uncompressed(header.ctype) {
+ if r.ur != nil {
+ r.ur.Reopen(r.r, size)
+ } else {
+ r.ur = newUncompressedReader(r.r, r.dict, size)
+ }
+ r.chunkReader = r.ur
+ return nil
+ }
+ br := ByteReader(io.LimitReader(r.r, int64(header.compressed)+1))
+ if r.decoder == nil {
+ state := newState(header.props)
+ r.decoder, err = newDecoder(br, state, r.dict, size)
+ if err != nil {
+ return err
+ }
+ r.chunkReader = r.decoder
+ return nil
+ }
+ switch header.ctype {
+ case cLR:
+ r.decoder.State.Reset()
+ case cLRN, cLRND:
+ r.decoder.State = newState(header.props)
+ }
+ err = r.decoder.Reopen(br, size)
+ if err != nil {
+ return err
+ }
+ r.chunkReader = r.decoder
+ return nil
+}
+
+// Read reads data from the LZMA2 chunk sequence.
+func (r *Reader2) Read(p []byte) (n int, err error) {
+ if r.err != nil {
+ return 0, r.err
+ }
+ for n < len(p) {
+ var k int
+ k, err = r.chunkReader.Read(p[n:])
+ n += k
+ if err != nil {
+ if err == io.EOF {
+ err = r.startChunk()
+ if err == nil {
+ continue
+ }
+ }
+ r.err = err
+ return n, err
+ }
+ if k == 0 {
+ r.err = errors.New("lzma: Reader2 doesn't get data")
+ return n, r.err
+ }
+ }
+ return n, nil
+}
+
+// EOS returns whether the LZMA2 stream has been terminated by an
+// end-of-stream chunk.
+func (r *Reader2) EOS() bool {
+ return r.cstate == stop
+}
+
+// uncompressedReader is used to read uncompressed chunks.
+type uncompressedReader struct {
+ lr io.LimitedReader
+ Dict *decoderDict
+ eof bool
+ err error
+}
+
+// newUncompressedReader initializes a new uncompressedReader.
+func newUncompressedReader(r io.Reader, dict *decoderDict, size int64) *uncompressedReader {
+ ur := &uncompressedReader{
+ lr: io.LimitedReader{R: r, N: size},
+ Dict: dict,
+ }
+ return ur
+}
+
+// Reopen reinitializes an uncompressed reader.
+func (ur *uncompressedReader) Reopen(r io.Reader, size int64) {
+ ur.err = nil
+ ur.eof = false
+ ur.lr = io.LimitedReader{R: r, N: size}
+}
+
+// fill reads uncompressed data into the dictionary.
+func (ur *uncompressedReader) fill() error {
+ if !ur.eof {
+ n, err := io.CopyN(ur.Dict, &ur.lr, int64(ur.Dict.Available()))
+ if err != io.EOF {
+ return err
+ }
+ ur.eof = true
+ if n > 0 {
+ return nil
+ }
+ }
+ if ur.lr.N != 0 {
+ return io.ErrUnexpectedEOF
+ }
+ return io.EOF
+}
+
+// Read reads uncompressed data from the limited reader.
+func (ur *uncompressedReader) Read(p []byte) (n int, err error) {
+ if ur.err != nil {
+ return 0, ur.err
+ }
+ for {
+ var k int
+ k, err = ur.Dict.Read(p[n:])
+ n += k
+ if n >= len(p) {
+ return n, nil
+ }
+ if err != nil {
+ break
+ }
+ err = ur.fill()
+ if err != nil {
+ break
+ }
+ }
+ ur.err = err
+ return n, err
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/state.go b/vendor/github.com/ulikunitz/xz/lzma/state.go
new file mode 100644
index 000000000..502351052
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/state.go
@@ -0,0 +1,151 @@
+// 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
+
+// states defines the overall state count
+const states = 12
+
+// State maintains the full state of the operation encoding or decoding
+// process.
+type state struct {
+ rep [4]uint32
+ isMatch [states << maxPosBits]prob
+ isRepG0Long [states << maxPosBits]prob
+ isRep [states]prob
+ isRepG0 [states]prob
+ isRepG1 [states]prob
+ isRepG2 [states]prob
+ litCodec literalCodec
+ lenCodec lengthCodec
+ repLenCodec lengthCodec
+ distCodec distCodec
+ state uint32
+ posBitMask uint32
+ Properties Properties
+}
+
+// initProbSlice initializes a slice of probabilities.
+func initProbSlice(p []prob) {
+ for i := range p {
+ p[i] = probInit
+ }
+}
+
+// Reset sets all state information to the original values.
+func (s *state) Reset() {
+ p := s.Properties
+ *s = state{
+ Properties: p,
+ // dict: s.dict,
+ posBitMask: (uint32(1) << uint(p.PB)) - 1,
+ }
+ initProbSlice(s.isMatch[:])
+ initProbSlice(s.isRep[:])
+ initProbSlice(s.isRepG0[:])
+ initProbSlice(s.isRepG1[:])
+ initProbSlice(s.isRepG2[:])
+ initProbSlice(s.isRepG0Long[:])
+ s.litCodec.init(p.LC, p.LP)
+ s.lenCodec.init()
+ s.repLenCodec.init()
+ s.distCodec.init()
+}
+
+// initState initializes the state.
+func initState(s *state, p Properties) {
+ *s = state{Properties: p}
+ s.Reset()
+}
+
+// newState creates a new state from the give Properties.
+func newState(p Properties) *state {
+ s := &state{Properties: p}
+ s.Reset()
+ return s
+}
+
+// deepcopy initializes s as a deep copy of the source.
+func (s *state) deepcopy(src *state) {
+ if s == src {
+ return
+ }
+ s.rep = src.rep
+ s.isMatch = src.isMatch
+ s.isRepG0Long = src.isRepG0Long
+ s.isRep = src.isRep
+ s.isRepG0 = src.isRepG0
+ s.isRepG1 = src.isRepG1
+ s.isRepG2 = src.isRepG2
+ s.litCodec.deepcopy(&src.litCodec)
+ s.lenCodec.deepcopy(&src.lenCodec)
+ s.repLenCodec.deepcopy(&src.repLenCodec)
+ s.distCodec.deepcopy(&src.distCodec)
+ s.state = src.state
+ s.posBitMask = src.posBitMask
+ s.Properties = src.Properties
+}
+
+// cloneState creates a new clone of the give state.
+func cloneState(src *state) *state {
+ s := new(state)
+ s.deepcopy(src)
+ return s
+}
+
+// updateStateLiteral updates the state for a literal.
+func (s *state) updateStateLiteral() {
+ switch {
+ case s.state < 4:
+ s.state = 0
+ return
+ case s.state < 10:
+ s.state -= 3
+ return
+ }
+ s.state -= 6
+}
+
+// updateStateMatch updates the state for a match.
+func (s *state) updateStateMatch() {
+ if s.state < 7 {
+ s.state = 7
+ } else {
+ s.state = 10
+ }
+}
+
+// updateStateRep updates the state for a repetition.
+func (s *state) updateStateRep() {
+ if s.state < 7 {
+ s.state = 8
+ } else {
+ s.state = 11
+ }
+}
+
+// updateStateShortRep updates the state for a short repetition.
+func (s *state) updateStateShortRep() {
+ if s.state < 7 {
+ s.state = 9
+ } else {
+ s.state = 11
+ }
+}
+
+// states computes the states of the operation codec.
+func (s *state) states(dictHead int64) (state1, state2, posState uint32) {
+ state1 = s.state
+ posState = uint32(dictHead) & s.posBitMask
+ state2 = (s.state << maxPosBits) | posState
+ return
+}
+
+// litState computes the literal state.
+func (s *state) litState(prev byte, dictHead int64) uint32 {
+ lp, lc := uint(s.Properties.LP), uint(s.Properties.LC)
+ litState := ((uint32(dictHead) & ((1 << lp) - 1)) << lc) |
+ (uint32(prev) >> (8 - lc))
+ return litState
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/treecodecs.go b/vendor/github.com/ulikunitz/xz/lzma/treecodecs.go
new file mode 100644
index 000000000..504b3d78e
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/treecodecs.go
@@ -0,0 +1,133 @@
+// 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
+
+// treeCodec encodes or decodes values with a fixed bit size. It is using a
+// tree of probability value. The root of the tree is the most-significant bit.
+type treeCodec struct {
+ probTree
+}
+
+// makeTreeCodec makes a tree codec. The bits value must be inside the range
+// [1,32].
+func makeTreeCodec(bits int) treeCodec {
+ return treeCodec{makeProbTree(bits)}
+}
+
+// deepcopy initializes tc as a deep copy of the source.
+func (tc *treeCodec) deepcopy(src *treeCodec) {
+ tc.probTree.deepcopy(&src.probTree)
+}
+
+// Encode uses the range encoder to encode a fixed-bit-size value.
+func (tc *treeCodec) Encode(e *rangeEncoder, v uint32) (err error) {
+ m := uint32(1)
+ for i := int(tc.bits) - 1; i >= 0; i-- {
+ b := (v >> uint(i)) & 1
+ if err := e.EncodeBit(b, &tc.probs[m]); err != nil {
+ return err
+ }
+ m = (m << 1) | b
+ }
+ return nil
+}
+
+// Decodes uses the range decoder to decode a fixed-bit-size value. Errors may
+// be caused by the range decoder.
+func (tc *treeCodec) Decode(d *rangeDecoder) (v uint32, err error) {
+ m := uint32(1)
+ for j := 0; j < int(tc.bits); j++ {
+ b, err := d.DecodeBit(&tc.probs[m])
+ if err != nil {
+ return 0, err
+ }
+ m = (m << 1) | b
+ }
+ return m - (1 << uint(tc.bits)), nil
+}
+
+// treeReverseCodec is another tree codec, where the least-significant bit is
+// the start of the probability tree.
+type treeReverseCodec struct {
+ probTree
+}
+
+// deepcopy initializes the treeReverseCodec as a deep copy of the
+// source.
+func (tc *treeReverseCodec) deepcopy(src *treeReverseCodec) {
+ tc.probTree.deepcopy(&src.probTree)
+}
+
+// makeTreeReverseCodec creates treeReverseCodec value. The bits argument must
+// be in the range [1,32].
+func makeTreeReverseCodec(bits int) treeReverseCodec {
+ return treeReverseCodec{makeProbTree(bits)}
+}
+
+// Encode uses range encoder to encode a fixed-bit-size value. The range
+// encoder may cause errors.
+func (tc *treeReverseCodec) Encode(v uint32, e *rangeEncoder) (err error) {
+ m := uint32(1)
+ for i := uint(0); i < uint(tc.bits); i++ {
+ b := (v >> i) & 1
+ if err := e.EncodeBit(b, &tc.probs[m]); err != nil {
+ return err
+ }
+ m = (m << 1) | b
+ }
+ return nil
+}
+
+// Decodes uses the range decoder to decode a fixed-bit-size value. Errors
+// returned by the range decoder will be returned.
+func (tc *treeReverseCodec) Decode(d *rangeDecoder) (v uint32, err error) {
+ m := uint32(1)
+ for j := uint(0); j < uint(tc.bits); j++ {
+ b, err := d.DecodeBit(&tc.probs[m])
+ if err != nil {
+ return 0, err
+ }
+ m = (m << 1) | b
+ v |= b << j
+ }
+ return v, nil
+}
+
+// probTree stores enough probability values to be used by the treeEncode and
+// treeDecode methods of the range coder types.
+type probTree struct {
+ probs []prob
+ bits byte
+}
+
+// deepcopy initializes the probTree value as a deep copy of the source.
+func (t *probTree) deepcopy(src *probTree) {
+ if t == src {
+ return
+ }
+ t.probs = make([]prob, len(src.probs))
+ copy(t.probs, src.probs)
+ t.bits = src.bits
+}
+
+// makeProbTree initializes a probTree structure.
+func makeProbTree(bits int) probTree {
+ if !(1 <= bits && bits <= 32) {
+ panic("bits outside of range [1,32]")
+ }
+ t := probTree{
+ bits: byte(bits),
+ probs: make([]prob, 1<<uint(bits)),
+ }
+ for i := range t.probs {
+ t.probs[i] = probInit
+ }
+ return t
+}
+
+// Bits provides the number of bits for the values to de- or encode.
+func (t *probTree) Bits() int {
+ return int(t.bits)
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/writer.go b/vendor/github.com/ulikunitz/xz/lzma/writer.go
new file mode 100644
index 000000000..efe34fb6b
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/writer.go
@@ -0,0 +1,209 @@
+// 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 (
+ "bufio"
+ "errors"
+ "io"
+)
+
+// MinDictCap and MaxDictCap provide the range of supported dictionary
+// capacities.
+const (
+ MinDictCap = 1 << 12
+ MaxDictCap = 1<<32 - 1
+)
+
+// WriterConfig defines the configuration parameter for a writer.
+type WriterConfig struct {
+ // Properties for the encoding. If the it is nil the value
+ // {LC: 3, LP: 0, PB: 2} will be chosen.
+ Properties *Properties
+ // The capacity of the dictionary. If DictCap is zero, the value
+ // 8 MiB will be chosen.
+ DictCap int
+ // Size of the lookahead buffer; value 0 indicates default size
+ // 4096
+ BufSize int
+ // Match algorithm
+ Matcher MatchAlgorithm
+ // SizeInHeader indicates that the header will contain an
+ // explicit size.
+ SizeInHeader bool
+ // Size of the data to be encoded. A positive value will imply
+ // than an explicit size will be set in the header.
+ Size int64
+ // EOSMarker requests whether the EOSMarker needs to be written.
+ // If no explicit size is been given the EOSMarker will be
+ // set automatically.
+ EOSMarker bool
+}
+
+// fill converts zero-value fields to their explicit default values.
+func (c *WriterConfig) fill() {
+ if c.Properties == nil {
+ c.Properties = &Properties{LC: 3, LP: 0, PB: 2}
+ }
+ if c.DictCap == 0 {
+ c.DictCap = 8 * 1024 * 1024
+ }
+ if c.BufSize == 0 {
+ c.BufSize = 4096
+ }
+ if c.Size > 0 {
+ c.SizeInHeader = true
+ }
+ if !c.SizeInHeader {
+ c.EOSMarker = true
+ }
+}
+
+// Verify checks WriterConfig for errors. Verify will replace zero
+// values with default values.
+func (c *WriterConfig) Verify() error {
+ c.fill()
+ var err error
+ if c == nil {
+ return errors.New("lzma: WriterConfig is nil")
+ }
+ if c.Properties == nil {
+ return errors.New("lzma: WriterConfig has no Properties set")
+ }
+ if err = c.Properties.verify(); err != nil {
+ return err
+ }
+ if !(MinDictCap <= c.DictCap && int64(c.DictCap) <= MaxDictCap) {
+ return errors.New("lzma: dictionary capacity is out of range")
+ }
+ if !(maxMatchLen <= c.BufSize) {
+ return errors.New("lzma: lookahead buffer size too small")
+ }
+ if c.SizeInHeader {
+ if c.Size < 0 {
+ return errors.New("lzma: negative size not supported")
+ }
+ } else if !c.EOSMarker {
+ return errors.New("lzma: EOS marker is required")
+ }
+ if err = c.Matcher.verify(); err != nil {
+ return err
+ }
+
+ return nil
+}
+
+// header returns the header structure for this configuration.
+func (c *WriterConfig) header() header {
+ h := header{
+ properties: *c.Properties,
+ dictCap: c.DictCap,
+ size: -1,
+ }
+ if c.SizeInHeader {
+ h.size = c.Size
+ }
+ return h
+}
+
+// Writer writes an LZMA stream in the classic format.
+type Writer struct {
+ h header
+ bw io.ByteWriter
+ buf *bufio.Writer
+ e *encoder
+}
+
+// NewWriter creates a new LZMA writer for the classic format. The
+// method will write the header to the underlying stream.
+func (c WriterConfig) NewWriter(lzma io.Writer) (w *Writer, err error) {
+ if err = c.Verify(); err != nil {
+ return nil, err
+ }
+ w = &Writer{h: c.header()}
+
+ var ok bool
+ w.bw, ok = lzma.(io.ByteWriter)
+ if !ok {
+ w.buf = bufio.NewWriter(lzma)
+ w.bw = w.buf
+ }
+ state := newState(w.h.properties)
+ m, err := c.Matcher.new(w.h.dictCap)
+ if err != nil {
+ return nil, err
+ }
+ dict, err := newEncoderDict(w.h.dictCap, c.BufSize, m)
+ if err != nil {
+ return nil, err
+ }
+ var flags encoderFlags
+ if c.EOSMarker {
+ flags = eosMarker
+ }
+ if w.e, err = newEncoder(w.bw, state, dict, flags); err != nil {
+ return nil, err
+ }
+
+ if err = w.writeHeader(); err != nil {
+ return nil, err
+ }
+ return w, nil
+}
+
+// NewWriter creates a new LZMA writer using the classic format. The
+// function writes the header to the underlying stream.
+func NewWriter(lzma io.Writer) (w *Writer, err error) {
+ return WriterConfig{}.NewWriter(lzma)
+}
+
+// writeHeader writes the LZMA header into the stream.
+func (w *Writer) writeHeader() error {
+ data, err := w.h.marshalBinary()
+ if err != nil {
+ return err
+ }
+ _, err = w.bw.(io.Writer).Write(data)
+ return err
+}
+
+// Write puts data into the Writer.
+func (w *Writer) Write(p []byte) (n int, err error) {
+ if w.h.size >= 0 {
+ m := w.h.size
+ m -= w.e.Compressed() + int64(w.e.dict.Buffered())
+ if m < 0 {
+ m = 0
+ }
+ if m < int64(len(p)) {
+ p = p[:m]
+ err = ErrNoSpace
+ }
+ }
+ var werr error
+ if n, werr = w.e.Write(p); werr != nil {
+ err = werr
+ }
+ return n, err
+}
+
+// Close closes the writer stream. It ensures that all data from the
+// buffer will be compressed and the LZMA stream will be finished.
+func (w *Writer) Close() error {
+ if w.h.size >= 0 {
+ n := w.e.Compressed() + int64(w.e.dict.Buffered())
+ if n != w.h.size {
+ return errSize
+ }
+ }
+ err := w.e.Close()
+ if w.buf != nil {
+ ferr := w.buf.Flush()
+ if err == nil {
+ err = ferr
+ }
+ }
+ return err
+}
diff --git a/vendor/github.com/ulikunitz/xz/lzma/writer2.go b/vendor/github.com/ulikunitz/xz/lzma/writer2.go
new file mode 100644
index 000000000..7c1afe157
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/writer2.go
@@ -0,0 +1,305 @@
+// 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 (
+ "bytes"
+ "errors"
+ "io"
+)
+
+// Writer2Config is used to create a Writer2 using parameters.
+type Writer2Config struct {
+ // The properties for the encoding. If the it is nil the value
+ // {LC: 3, LP: 0, PB: 2} will be chosen.
+ Properties *Properties
+ // The capacity of the dictionary. If DictCap is zero, the value
+ // 8 MiB will be chosen.
+ DictCap int
+ // Size of the lookahead buffer; value 0 indicates default size
+ // 4096
+ BufSize int
+ // Match algorithm
+ Matcher MatchAlgorithm
+}
+
+// fill replaces zero values with default values.
+func (c *Writer2Config) fill() {
+ if c.Properties == nil {
+ c.Properties = &Properties{LC: 3, LP: 0, PB: 2}
+ }
+ if c.DictCap == 0 {
+ c.DictCap = 8 * 1024 * 1024
+ }
+ if c.BufSize == 0 {
+ c.BufSize = 4096
+ }
+}
+
+// Verify checks the Writer2Config for correctness. Zero values will be
+// replaced by default values.
+func (c *Writer2Config) Verify() error {
+ c.fill()
+ var err error
+ if c == nil {
+ return errors.New("lzma: WriterConfig is nil")
+ }
+ if c.Properties == nil {
+ return errors.New("lzma: WriterConfig has no Properties set")
+ }
+ if err = c.Properties.verify(); err != nil {
+ return err
+ }
+ if !(MinDictCap <= c.DictCap && int64(c.DictCap) <= MaxDictCap) {
+ return errors.New("lzma: dictionary capacity is out of range")
+ }
+ if !(maxMatchLen <= c.BufSize) {
+ return errors.New("lzma: lookahead buffer size too small")
+ }
+ if c.Properties.LC+c.Properties.LP > 4 {
+ return errors.New("lzma: sum of lc and lp exceeds 4")
+ }
+ if err = c.Matcher.verify(); err != nil {
+ return err
+ }
+ return nil
+}
+
+// Writer2 supports the creation of an LZMA2 stream. But note that
+// written data is buffered, so call Flush or Close to write data to the
+// underlying writer. The Close method writes the end-of-stream marker
+// to the stream. So you may be able to concatenate the output of two
+// writers as long the output of the first writer has only been flushed
+// but not closed.
+//
+// Any change to the fields Properties, DictCap must be done before the
+// first call to Write, Flush or Close.
+type Writer2 struct {
+ w io.Writer
+
+ start *state
+ encoder *encoder
+
+ cstate chunkState
+ ctype chunkType
+
+ buf bytes.Buffer
+ lbw LimitedByteWriter
+}
+
+// NewWriter2 creates an LZMA2 chunk sequence writer with the default
+// parameters and options.
+func NewWriter2(lzma2 io.Writer) (w *Writer2, err error) {
+ return Writer2Config{}.NewWriter2(lzma2)
+}
+
+// NewWriter2 creates a new LZMA2 writer using the given configuration.
+func (c Writer2Config) NewWriter2(lzma2 io.Writer) (w *Writer2, err error) {
+ if err = c.Verify(); err != nil {
+ return nil, err
+ }
+ w = &Writer2{
+ w: lzma2,
+ start: newState(*c.Properties),
+ cstate: start,
+ ctype: start.defaultChunkType(),
+ }
+ w.buf.Grow(maxCompressed)
+ w.lbw = LimitedByteWriter{BW: &w.buf, N: maxCompressed}
+ m, err := c.Matcher.new(c.DictCap)
+ if err != nil {
+ return nil, err
+ }
+ d, err := newEncoderDict(c.DictCap, c.BufSize, m)
+ if err != nil {
+ return nil, err
+ }
+ w.encoder, err = newEncoder(&w.lbw, cloneState(w.start), d, 0)
+ if err != nil {
+ return nil, err
+ }
+ return w, nil
+}
+
+// written returns the number of bytes written to the current chunk
+func (w *Writer2) written() int {
+ if w.encoder == nil {
+ return 0
+ }
+ return int(w.encoder.Compressed()) + w.encoder.dict.Buffered()
+}
+
+// errClosed indicates that the writer is closed.
+var errClosed = errors.New("lzma: writer closed")
+
+// Writes data to LZMA2 stream. Note that written data will be buffered.
+// Use Flush or Close to ensure that data is written to the underlying
+// writer.
+func (w *Writer2) Write(p []byte) (n int, err error) {
+ if w.cstate == stop {
+ return 0, errClosed
+ }
+ for n < len(p) {
+ m := maxUncompressed - w.written()
+ if m <= 0 {
+ panic("lzma: maxUncompressed reached")
+ }
+ var q []byte
+ if n+m < len(p) {
+ q = p[n : n+m]
+ } else {
+ q = p[n:]
+ }
+ k, err := w.encoder.Write(q)
+ n += k
+ if err != nil && err != ErrLimit {
+ return n, err
+ }
+ if err == ErrLimit || k == m {
+ if err = w.flushChunk(); err != nil {
+ return n, err
+ }
+ }
+ }
+ return n, nil
+}
+
+// writeUncompressedChunk writes an uncompressed chunk to the LZMA2
+// stream.
+func (w *Writer2) writeUncompressedChunk() error {
+ u := w.encoder.Compressed()
+ if u <= 0 {
+ return errors.New("lzma: can't write empty uncompressed chunk")
+ }
+ if u > maxUncompressed {
+ panic("overrun of uncompressed data limit")
+ }
+ switch w.ctype {
+ case cLRND:
+ w.ctype = cUD
+ default:
+ w.ctype = cU
+ }
+ w.encoder.state = w.start
+
+ header := chunkHeader{
+ ctype: w.ctype,
+ uncompressed: uint32(u - 1),
+ }
+ hdata, err := header.MarshalBinary()
+ if err != nil {
+ return err
+ }
+ if _, err = w.w.Write(hdata); err != nil {
+ return err
+ }
+ _, err = w.encoder.dict.CopyN(w.w, int(u))
+ return err
+}
+
+// writeCompressedChunk writes a compressed chunk to the underlying
+// writer.
+func (w *Writer2) writeCompressedChunk() error {
+ if w.ctype == cU || w.ctype == cUD {
+ panic("chunk type uncompressed")
+ }
+
+ u := w.encoder.Compressed()
+ if u <= 0 {
+ return errors.New("writeCompressedChunk: empty chunk")
+ }
+ if u > maxUncompressed {
+ panic("overrun of uncompressed data limit")
+ }
+ c := w.buf.Len()
+ if c <= 0 {
+ panic("no compressed data")
+ }
+ if c > maxCompressed {
+ panic("overrun of compressed data limit")
+ }
+ header := chunkHeader{
+ ctype: w.ctype,
+ uncompressed: uint32(u - 1),
+ compressed: uint16(c - 1),
+ props: w.encoder.state.Properties,
+ }
+ hdata, err := header.MarshalBinary()
+ if err != nil {
+ return err
+ }
+ if _, err = w.w.Write(hdata); err != nil {
+ return err
+ }
+ _, err = io.Copy(w.w, &w.buf)
+ return err
+}
+
+// writes a single chunk to the underlying writer.
+func (w *Writer2) writeChunk() error {
+ u := int(uncompressedHeaderLen + w.encoder.Compressed())
+ c := headerLen(w.ctype) + w.buf.Len()
+ if u < c {
+ return w.writeUncompressedChunk()
+ }
+ return w.writeCompressedChunk()
+}
+
+// flushChunk terminates the current chunk. The encoder will be reset
+// to support the next chunk.
+func (w *Writer2) flushChunk() error {
+ if w.written() == 0 {
+ return nil
+ }
+ var err error
+ if err = w.encoder.Close(); err != nil {
+ return err
+ }
+ if err = w.writeChunk(); err != nil {
+ return err
+ }
+ w.buf.Reset()
+ w.lbw.N = maxCompressed
+ if err = w.encoder.Reopen(&w.lbw); err != nil {
+ return err
+ }
+ if err = w.cstate.next(w.ctype); err != nil {
+ return err
+ }
+ w.ctype = w.cstate.defaultChunkType()
+ w.start = cloneState(w.encoder.state)
+ return nil
+}
+
+// Flush writes all buffered data out to the underlying stream. This
+// could result in multiple chunks to be created.
+func (w *Writer2) Flush() error {
+ if w.cstate == stop {
+ return errClosed
+ }
+ for w.written() > 0 {
+ if err := w.flushChunk(); err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
+// Close terminates the LZMA2 stream with an EOS chunk.
+func (w *Writer2) Close() error {
+ if w.cstate == stop {
+ return errClosed
+ }
+ if err := w.Flush(); err != nil {
+ return nil
+ }
+ // write zero byte EOS chunk
+ _, err := w.w.Write([]byte{0})
+ if err != nil {
+ return err
+ }
+ w.cstate = stop
+ return nil
+}