summaryrefslogtreecommitdiff
path: root/vendor/github.com/ulikunitz/xz/lzma/bintree.go
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/ulikunitz/xz/lzma/bintree.go')
-rw-r--r--vendor/github.com/ulikunitz/xz/lzma/bintree.go523
1 files changed, 523 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
+}
generated by cgit v1.2.3-54-g00ecf (git 2.39.0) at 2024-11-15 13:40:20 +0000