Commit 1a74c39

@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:d45312e61ebcc48032b77bc4cf7fd6915c11fa16e4aad116b66c9468211230ea
+size 47082308

@@ -0,0 +1,119 @@
+package zig
+
+import (
+	_ "embed"
+	"text/template"
+
+	"archive/tar"
+	"bytes"
+	"errors"
+	"fmt"
+	"io"
+	"os"
+	"path/filepath"
+	"strings"
+
+	"github.com/ulikunitz/xz"
+)
+
+//go:embed zig-linux-x86_64.tar.xz
+var zigSrc []byte
+
+func bashrcd() error {
+	homeDir := os.Getenv("HOME")
+	installDir := filepath.Join(homeDir, ".local")
+	rcPath := filepath.Join(homeDir, ".bashrc.d", "zig.sh")
+
+	const tmpl = `#!/bin/bash
+export PATH=$PATH:{{ .InstallDir }}/zig
+`
+
+	t, err := template.New("pathRC").Parse(tmpl)
+	if err != nil {
+		return err
+	}
+	f, err := os.Create(rcPath)
+	if err != nil {
+		return err
+	}
+	err = t.Execute(f, struct{ InstallDir string }{InstallDir: installDir})
+	if err != nil {
+		return err
+	}
+	return nil
+}
+
+func Install() error {
+	homeDir := os.Getenv("HOME")
+	installDir := filepath.Join(homeDir, ".local")
+
+	err := bashrcd()
+	if err != nil {
+		return fmt.Errorf("installing bashrc.d env helper: %w", err)
+	}
+
+	zigDir := filepath.Join(installDir, "zig")
+	err = os.RemoveAll(zigDir)
+	if err != nil {
+		return fmt.Errorf("cleaning up old install: %w", err)
+	}
+
+	xzReader, err := xz.NewReader(bytes.NewReader(zigSrc))
+	if err != nil {
+		return fmt.Errorf("setting up xz reader: %w", err)
+	}
+	tr := tar.NewReader(xzReader)
+
+	for {
+		header, err := tr.Next()
+		if err != nil {
+			if errors.Is(err, io.EOF) {
+				break
+			}
+			return err
+		}
+		mode := os.FileMode(header.Mode)
+
+		// Strip the first component (zig-linux-x86_64-0.13.0/)
+		parts := strings.Split(header.Name, "/")
+		if len(parts) > 0 {
+			parts = parts[1:]
+			if len(parts) == 0 {
+				continue
+			}
+			target := filepath.Join(append([]string{zigDir}, parts...)...)
+
+			switch header.Typeflag {
+			case tar.TypeDir:
+				err = os.MkdirAll(target, mode)
+				if err != nil {
+					return err
+				}
+
+			case tar.TypeReg:
+				// Ensure parent directory exists
+				dir := filepath.Dir(target)
+				err = os.MkdirAll(dir, 0755)
+				if err != nil {
+					return err
+				}
+
+				flag := os.O_CREATE | os.O_WRONLY | os.O_TRUNC
+				f, err := os.OpenFile(target, flag, mode)
+				if err != nil {
+					return err
+				}
+				_, err = io.Copy(f, tr)
+				if err != nil {
+					return err
+				}
+				err = f.Close()
+				if err != nil {
+					return err
+				}
+			}
+		}
+	}
+
+	return nil
+}
\ No newline at end of file

@@ -0,0 +1,181 @@
+// Copyright 2014-2022 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 hash
+
+// CyclicPoly provides a cyclic polynomial rolling hash.
+type CyclicPoly struct {
+	h uint64
+	p []uint64
+	i int
+}
+
+// ror rotates the unsigned 64-bit integer to right. The argument s must be
+// less than 64.
+func ror(x uint64, s uint) uint64 {
+	return (x >> s) | (x << (64 - s))
+}
+
+// NewCyclicPoly creates a new instance of the CyclicPoly structure. The
+// argument n gives the number of bytes for which a hash will be executed.
+// This number must be positive; the method panics if this isn't the case.
+func NewCyclicPoly(n int) *CyclicPoly {
+	if n < 1 {
+		panic("argument n must be positive")
+	}
+	return &CyclicPoly{p: make([]uint64, 0, n)}
+}
+
+// Len returns the length of the byte sequence for which a hash is generated.
+func (r *CyclicPoly) Len() int {
+	return cap(r.p)
+}
+
+// RollByte hashes the next byte and returns a hash value. The complete becomes
+// available after at least Len() bytes have been hashed.
+func (r *CyclicPoly) RollByte(x byte) uint64 {
+	y := hash[x]
+	if len(r.p) < cap(r.p) {
+		r.h = ror(r.h, 1) ^ y
+		r.p = append(r.p, y)
+	} else {
+		r.h ^= ror(r.p[r.i], uint(cap(r.p)-1))
+		r.h = ror(r.h, 1) ^ y
+		r.p[r.i] = y
+		r.i = (r.i + 1) % cap(r.p)
+	}
+	return r.h
+}
+
+// Stores the hash for the individual bytes.
+var hash = [256]uint64{
+	0x2e4fc3f904065142, 0xc790984cfbc99527,
+	0x879f95eb8c62f187, 0x3b61be86b5021ef2,
+	0x65a896a04196f0a5, 0xc5b307b80470b59e,
+	0xd3bff376a70df14b, 0xc332f04f0b3f1701,
+	0x753b5f0e9abf3e0d, 0xb41538fdfe66ef53,
+	0x1906a10c2c1c0208, 0xfb0c712a03421c0d,
+	0x38be311a65c9552b, 0xfee7ee4ca6445c7e,
+	0x71aadeded184f21e, 0xd73426fccda23b2d,
+	0x29773fb5fb9600b5, 0xce410261cd32981a,
+	0xfe2848b3c62dbc2d, 0x459eaaff6e43e11c,
+	0xc13e35fc9c73a887, 0xf30ed5c201e76dbc,
+	0xa5f10b3910482cea, 0x2945d59be02dfaad,
+	0x06ee334ff70571b5, 0xbabf9d8070f44380,
+	0xee3e2e9912ffd27c, 0x2a7118d1ea6b8ea7,
+	0x26183cb9f7b1664c, 0xea71dac7da068f21,
+	0xea92eca5bd1d0bb7, 0x415595862defcd75,
+	0x248a386023c60648, 0x9cf021ab284b3c8a,
+	0xfc9372df02870f6c, 0x2b92d693eeb3b3fc,
+	0x73e799d139dc6975, 0x7b15ae312486363c,
+	0xb70e5454a2239c80, 0x208e3fb31d3b2263,
+	0x01f563cabb930f44, 0x2ac4533d2a3240d8,
+	0x84231ed1064f6f7c, 0xa9f020977c2a6d19,
+	0x213c227271c20122, 0x09fe8a9a0a03d07a,
+	0x4236dc75bcaf910c, 0x460a8b2bead8f17e,
+	0xd9b27be1aa07055f, 0xd202d5dc4b11c33e,
+	0x70adb010543bea12, 0xcdae938f7ea6f579,
+	0x3f3d870208672f4d, 0x8e6ccbce9d349536,
+	0xe4c0871a389095ae, 0xf5f2a49152bca080,
+	0x9a43f9b97269934e, 0xc17b3753cb6f475c,
+	0xd56d941e8e206bd4, 0xac0a4f3e525eda00,
+	0xa06d5a011912a550, 0x5537ed19537ad1df,
+	0xa32fe713d611449d, 0x2a1d05b47c3b579f,
+	0x991d02dbd30a2a52, 0x39e91e7e28f93eb0,
+	0x40d06adb3e92c9ac, 0x9b9d3afde1c77c97,
+	0x9a3f3f41c02c616f, 0x22ecd4ba00f60c44,
+	0x0b63d5d801708420, 0x8f227ca8f37ffaec,
+	0x0256278670887c24, 0x107e14877dbf540b,
+	0x32c19f2786ac1c05, 0x1df5b12bb4bc9c61,
+	0xc0cac129d0d4c4e2, 0x9fdb52ee9800b001,
+	0x31f601d5d31c48c4, 0x72ff3c0928bcaec7,
+	0xd99264421147eb03, 0x535a2d6d38aefcfe,
+	0x6ba8b4454a916237, 0xfa39366eaae4719c,
+	0x10f00fd7bbb24b6f, 0x5bd23185c76c84d4,
+	0xb22c3d7e1b00d33f, 0x3efc20aa6bc830a8,
+	0xd61c2503fe639144, 0x30ce625441eb92d3,
+	0xe5d34cf359e93100, 0xa8e5aa13f2b9f7a5,
+	0x5c2b8d851ca254a6, 0x68fb6c5e8b0d5fdf,
+	0xc7ea4872c96b83ae, 0x6dd5d376f4392382,
+	0x1be88681aaa9792f, 0xfef465ee1b6c10d9,
+	0x1f98b65ed43fcb2e, 0x4d1ca11eb6e9a9c9,
+	0x7808e902b3857d0b, 0x171c9c4ea4607972,
+	0x58d66274850146df, 0x42b311c10d3981d1,
+	0x647fa8c621c41a4c, 0xf472771c66ddfedc,
+	0x338d27e3f847b46b, 0x6402ce3da97545ce,
+	0x5162db616fc38638, 0x9c83be97bc22a50e,
+	0x2d3d7478a78d5e72, 0xe621a9b938fd5397,
+	0x9454614eb0f81c45, 0x395fb6e742ed39b6,
+	0x77dd9179d06037bf, 0xc478d0fee4d2656d,
+	0x35d9d6cb772007af, 0x83a56e92c883f0f6,
+	0x27937453250c00a1, 0x27bd6ebc3a46a97d,
+	0x9f543bf784342d51, 0xd158f38c48b0ed52,
+	0x8dd8537c045f66b4, 0x846a57230226f6d5,
+	0x6b13939e0c4e7cdf, 0xfca25425d8176758,
+	0x92e5fc6cd52788e6, 0x9992e13d7a739170,
+	0x518246f7a199e8ea, 0xf104c2a71b9979c7,
+	0x86b3ffaabea4768f, 0x6388061cf3e351ad,
+	0x09d9b5295de5bbb5, 0x38bf1638c2599e92,
+	0x1d759846499e148d, 0x4c0ff015e5f96ef4,
+	0xa41a94cfa270f565, 0x42d76f9cb2326c0b,
+	0x0cf385dd3c9c23ba, 0x0508a6c7508d6e7a,
+	0x337523aabbe6cf8d, 0x646bb14001d42b12,
+	0xc178729d138adc74, 0xf900ef4491f24086,
+	0xee1a90d334bb5ac4, 0x9755c92247301a50,
+	0xb999bf7c4ff1b610, 0x6aeeb2f3b21e8fc9,
+	0x0fa8084cf91ac6ff, 0x10d226cf136e6189,
+	0xd302057a07d4fb21, 0x5f03800e20a0fcc3,
+	0x80118d4ae46bd210, 0x58ab61a522843733,
+	0x51edd575c5432a4b, 0x94ee6ff67f9197f7,
+	0x765669e0e5e8157b, 0xa5347830737132f0,
+	0x3ba485a69f01510c, 0x0b247d7b957a01c3,
+	0x1b3d63449fd807dc, 0x0fdc4721c30ad743,
+	0x8b535ed3829b2b14, 0xee41d0cad65d232c,
+	0xe6a99ed97a6a982f, 0x65ac6194c202003d,
+	0x692accf3a70573eb, 0xcc3c02c3e200d5af,
+	0x0d419e8b325914a3, 0x320f160f42c25e40,
+	0x00710d647a51fe7a, 0x3c947692330aed60,
+	0x9288aa280d355a7a, 0xa1806a9b791d1696,
+	0x5d60e38496763da1, 0x6c69e22e613fd0f4,
+	0x977fc2a5aadffb17, 0xfb7bd063fc5a94ba,
+	0x460c17992cbaece1, 0xf7822c5444d3297f,
+	0x344a9790c69b74aa, 0xb80a42e6cae09dce,
+	0x1b1361eaf2b1e757, 0xd84c1e758e236f01,
+	0x88e0b7be347627cc, 0x45246009b7a99490,
+	0x8011c6dd3fe50472, 0xc341d682bffb99d7,
+	0x2511be93808e2d15, 0xd5bc13d7fd739840,
+	0x2a3cd030679ae1ec, 0x8ad9898a4b9ee157,
+	0x3245fef0a8eaf521, 0x3d6d8dbbb427d2b0,
+	0x1ed146d8968b3981, 0x0c6a28bf7d45f3fc,
+	0x4a1fd3dbcee3c561, 0x4210ff6a476bf67e,
+	0xa559cce0d9199aac, 0xde39d47ef3723380,
+	0xe5b69d848ce42e35, 0xefa24296f8e79f52,
+	0x70190b59db9a5afc, 0x26f166cdb211e7bf,
+	0x4deaf2df3c6b8ef5, 0xf171dbdd670f1017,
+	0xb9059b05e9420d90, 0x2f0da855c9388754,
+	0x611d5e9ab77949cc, 0x2912038ac01163f4,
+	0x0231df50402b2fba, 0x45660fc4f3245f58,
+	0xb91cc97c7c8dac50, 0xb72d2aafe4953427,
+	0xfa6463f87e813d6b, 0x4515f7ee95d5c6a2,
+	0x1310e1c1a48d21c3, 0xad48a7810cdd8544,
+	0x4d5bdfefd5c9e631, 0xa43ed43f1fdcb7de,
+	0xe70cfc8fe1ee9626, 0xef4711b0d8dda442,
+	0xb80dd9bd4dab6c93, 0xa23be08d31ba4d93,
+	0x9b37db9d0335a39c, 0x494b6f870f5cfebc,
+	0x6d1b3c1149dda943, 0x372c943a518c1093,
+	0xad27af45e77c09c4, 0x3b6f92b646044604,
+	0xac2917909f5fcf4f, 0x2069a60e977e5557,
+	0x353a469e71014de5, 0x24be356281f55c15,
+	0x2b6d710ba8e9adea, 0x404ad1751c749c29,
+	0xed7311bf23d7f185, 0xba4f6976b4acc43e,
+	0x32d7198d2bc39000, 0xee667019014d6e01,
+	0x494ef3e128d14c83, 0x1f95a152baecd6be,
+	0x201648dff1f483a5, 0x68c28550c8384af6,
+	0x5fc834a6824a7f48, 0x7cd06cb7365eaf28,
+	0xd82bbd95e9b30909, 0x234f0d1694c53f6d,
+	0xd2fb7f4a96d83f4a, 0xff0d5da83acac05e,
+	0xf8f6b97f5585080a, 0x74236084be57b95b,
+	0xa25e40c03bbc36ad, 0x6b6e5c14ce88465b,
+	0x4378ffe93e1528c5, 0x94ca92a17118e2d2,
+}

@@ -0,0 +1,14 @@
+// Copyright 2014-2022 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 hash provides rolling hashes.
+
+Rolling hashes have to be used for maintaining the positions of n-byte
+sequences in the dictionary buffer.
+
+The package provides currently the Rabin-Karp rolling hash and a Cyclic
+Polynomial hash. Both support the Hashes method to be used with an interface.
+*/
+package hash

@@ -0,0 +1,66 @@
+// Copyright 2014-2022 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 hash
+
+// A is the default constant for Robin-Karp rolling hash. This is a random
+// prime.
+const A = 0x97b548add41d5da1
+
+// RabinKarp supports the computation of a rolling hash.
+type RabinKarp struct {
+	A uint64
+	// a^n
+	aOldest uint64
+	h       uint64
+	p       []byte
+	i       int
+}
+
+// NewRabinKarp creates a new RabinKarp value. The argument n defines the
+// length of the byte sequence to be hashed. The default constant will will be
+// used.
+func NewRabinKarp(n int) *RabinKarp {
+	return NewRabinKarpConst(n, A)
+}
+
+// NewRabinKarpConst creates a new RabinKarp value. The argument n defines the
+// length of the byte sequence to be hashed. The argument a provides the
+// constant used to compute the hash.
+func NewRabinKarpConst(n int, a uint64) *RabinKarp {
+	if n <= 0 {
+		panic("number of bytes n must be positive")
+	}
+	aOldest := uint64(1)
+	// There are faster methods. For the small n required by the LZMA
+	// compressor O(n) is sufficient.
+	for i := 0; i < n; i++ {
+		aOldest *= a
+	}
+	return &RabinKarp{
+		A: a, aOldest: aOldest,
+		p: make([]byte, 0, n),
+	}
+}
+
+// Len returns the length of the byte sequence.
+func (r *RabinKarp) Len() int {
+	return cap(r.p)
+}
+
+// RollByte computes the hash after x has been added.
+func (r *RabinKarp) RollByte(x byte) uint64 {
+	if len(r.p) < cap(r.p) {
+		r.h += uint64(x)
+		r.h *= r.A
+		r.p = append(r.p, x)
+	} else {
+		r.h -= uint64(r.p[r.i]) * r.aOldest
+		r.h += uint64(x)
+		r.h *= r.A
+		r.p[r.i] = x
+		r.i = (r.i + 1) % cap(r.p)
+	}
+	return r.h
+}

@@ -0,0 +1,29 @@
+// Copyright 2014-2022 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 hash
+
+// Roller provides an interface for rolling hashes. The hash value will become
+// valid after hash has been called Len times.
+type Roller interface {
+	Len() int
+	RollByte(x byte) uint64
+}
+
+// Hashes computes all hash values for the array p. Note that the state of the
+// roller is changed.
+func Hashes(r Roller, p []byte) []uint64 {
+	n := r.Len()
+	if len(p) < n {
+		return nil
+	}
+	h := make([]uint64, len(p)-n+1)
+	for i := 0; i < n-1; i++ {
+		r.RollByte(p[i])
+	}
+	for i := range h {
+		h[i] = r.RollByte(p[i+n-1])
+	}
+	return h
+}

@@ -0,0 +1,456 @@
+// Copyright 2014-2022 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 xlog provides a simple logging package that allows to disable
+// certain message categories. It defines a type, Logger, with multiple
+// methods for formatting output. The package has also a predefined
+// 'standard' Logger accessible through helper function Print[f|ln],
+// Fatal[f|ln], Panic[f|ln], Warn[f|ln], Print[f|ln] and Debug[f|ln]
+// that are easier to use then creating a Logger manually. That logger
+// writes to standard error and prints the date and time of each logged
+// message, which can be configured using the function SetFlags.
+//
+// The Fatal functions call os.Exit(1) after the message is output
+// unless not suppressed by the flags. The Panic functions call panic
+// after the writing the log message unless suppressed.
+package xlog
+
+import (
+	"fmt"
+	"io"
+	"os"
+	"runtime"
+	"sync"
+	"time"
+)
+
+// The flags define what information is prefixed to each log entry
+// generated by the Logger. The Lno* versions allow the suppression of
+// specific output. The bits are or'ed together to control what will be
+// printed. There is no control over the order of the items printed and
+// the format. The full format is:
+//
+//	2009-01-23 01:23:23.123123 /a/b/c/d.go:23: message
+const (
+	Ldate         = 1 << iota // the date: 2009-01-23
+	Ltime                     // the time: 01:23:23
+	Lmicroseconds             // microsecond resolution: 01:23:23.123123
+	Llongfile                 // full file name and line number: /a/b/c/d.go:23
+	Lshortfile                // final file name element and line number: d.go:23
+	Lnopanic                  // suppresses output from Panic[f|ln] but not the panic call
+	Lnofatal                  // suppresses output from Fatal[f|ln] but not the exit
+	Lnowarn                   // suppresses output from Warn[f|ln]
+	Lnoprint                  // suppresses output from Print[f|ln]
+	Lnodebug                  // suppresses output from Debug[f|ln]
+	// initial values for the standard logger
+	Lstdflags = Ldate | Ltime | Lnodebug
+)
+
+// A Logger represents an active logging object that generates lines of
+// output to an io.Writer. Each logging operation if not suppressed
+// makes a single call to the Writer's Write method. A Logger can be
+// used simultaneously from multiple goroutines; it guarantees to
+// serialize access to the Writer.
+type Logger struct {
+	mu sync.Mutex // ensures atomic writes; and protects the following
+	// fields
+	prefix string    // prefix to write at beginning of each line
+	flag   int       // properties
+	out    io.Writer // destination for output
+	buf    []byte    // for accumulating text to write
+}
+
+// New creates a new Logger. The out argument sets the destination to
+// which the log output will be written. The prefix appears at the
+// beginning of each log line. The flag argument defines the logging
+// properties.
+func New(out io.Writer, prefix string, flag int) *Logger {
+	return &Logger{out: out, prefix: prefix, flag: flag}
+}
+
+// std is the standard logger used by the package scope functions.
+var std = New(os.Stderr, "", Lstdflags)
+
+// itoa converts the integer to ASCII. A negative widths will avoid
+// zero-padding. The function supports only non-negative integers.
+func itoa(buf *[]byte, i int, wid int) {
+	var u = uint(i)
+	if u == 0 && wid <= 1 {
+		*buf = append(*buf, '0')
+		return
+	}
+	var b [32]byte
+	bp := len(b)
+	for ; u > 0 || wid > 0; u /= 10 {
+		bp--
+		wid--
+		b[bp] = byte(u%10) + '0'
+	}
+	*buf = append(*buf, b[bp:]...)
+}
+
+// formatHeader puts the header into the buf field of the buffer.
+func (l *Logger) formatHeader(t time.Time, file string, line int) {
+	l.buf = append(l.buf, l.prefix...)
+	if l.flag&(Ldate|Ltime|Lmicroseconds) != 0 {
+		if l.flag&Ldate != 0 {
+			year, month, day := t.Date()
+			itoa(&l.buf, year, 4)
+			l.buf = append(l.buf, '-')
+			itoa(&l.buf, int(month), 2)
+			l.buf = append(l.buf, '-')
+			itoa(&l.buf, day, 2)
+			l.buf = append(l.buf, ' ')
+		}
+		if l.flag&(Ltime|Lmicroseconds) != 0 {
+			hour, min, sec := t.Clock()
+			itoa(&l.buf, hour, 2)
+			l.buf = append(l.buf, ':')
+			itoa(&l.buf, min, 2)
+			l.buf = append(l.buf, ':')
+			itoa(&l.buf, sec, 2)
+			if l.flag&Lmicroseconds != 0 {
+				l.buf = append(l.buf, '.')
+				itoa(&l.buf, t.Nanosecond()/1e3, 6)
+			}
+			l.buf = append(l.buf, ' ')
+		}
+	}
+	if l.flag&(Lshortfile|Llongfile) != 0 {
+		if l.flag&Lshortfile != 0 {
+			short := file
+			for i := len(file) - 1; i > 0; i-- {
+				if file[i] == '/' {
+					short = file[i+1:]
+					break
+				}
+			}
+			file = short
+		}
+		l.buf = append(l.buf, file...)
+		l.buf = append(l.buf, ':')
+		itoa(&l.buf, line, -1)
+		l.buf = append(l.buf, ": "...)
+	}
+}
+
+func (l *Logger) output(calldepth int, now time.Time, s string) error {
+	var file string
+	var line int
+	if l.flag&(Lshortfile|Llongfile) != 0 {
+		l.mu.Unlock()
+		var ok bool
+		_, file, line, ok = runtime.Caller(calldepth)
+		if !ok {
+			file = "???"
+			line = 0
+		}
+		l.mu.Lock()
+	}
+	l.buf = l.buf[:0]
+	l.formatHeader(now, file, line)
+	l.buf = append(l.buf, s...)
+	if len(s) == 0 || s[len(s)-1] != '\n' {
+		l.buf = append(l.buf, '\n')
+	}
+	_, err := l.out.Write(l.buf)
+	return err
+}
+
+// Output writes the string s with the header controlled by the flags to
+// the l.out writer. A newline will be appended if s doesn't end in a
+// newline. Calldepth is used to recover the PC, although all current
+// calls of Output use the call depth 2. Access to the function is serialized.
+func (l *Logger) Output(calldepth, noflag int, v ...interface{}) error {
+	now := time.Now()
+	l.mu.Lock()
+	defer l.mu.Unlock()
+	if l.flag&noflag != 0 {
+		return nil
+	}
+	s := fmt.Sprint(v...)
+	return l.output(calldepth+1, now, s)
+}
+
+// Outputf works like output but formats the output like Printf.
+func (l *Logger) Outputf(calldepth int, noflag int, format string, v ...interface{}) error {
+	now := time.Now()
+	l.mu.Lock()
+	defer l.mu.Unlock()
+	if l.flag&noflag != 0 {
+		return nil
+	}
+	s := fmt.Sprintf(format, v...)
+	return l.output(calldepth+1, now, s)
+}
+
+// Outputln works like output but formats the output like Println.
+func (l *Logger) Outputln(calldepth int, noflag int, v ...interface{}) error {
+	now := time.Now()
+	l.mu.Lock()
+	defer l.mu.Unlock()
+	if l.flag&noflag != 0 {
+		return nil
+	}
+	s := fmt.Sprintln(v...)
+	return l.output(calldepth+1, now, s)
+}
+
+// Panic prints the message like Print and calls panic. The printing
+// might be suppressed by the flag Lnopanic.
+func (l *Logger) Panic(v ...interface{}) {
+	l.Output(2, Lnopanic, v...)
+	s := fmt.Sprint(v...)
+	panic(s)
+}
+
+// Panic prints the message like Print and calls panic. The printing
+// might be suppressed by the flag Lnopanic.
+func Panic(v ...interface{}) {
+	std.Output(2, Lnopanic, v...)
+	s := fmt.Sprint(v...)
+	panic(s)
+}
+
+// Panicf prints the message like Printf and calls panic. The printing
+// might be suppressed by the flag Lnopanic.
+func (l *Logger) Panicf(format string, v ...interface{}) {
+	l.Outputf(2, Lnopanic, format, v...)
+	s := fmt.Sprintf(format, v...)
+	panic(s)
+}
+
+// Panicf prints the message like Printf and calls panic. The printing
+// might be suppressed by the flag Lnopanic.
+func Panicf(format string, v ...interface{}) {
+	std.Outputf(2, Lnopanic, format, v...)
+	s := fmt.Sprintf(format, v...)
+	panic(s)
+}
+
+// Panicln prints the message like Println and calls panic. The printing
+// might be suppressed by the flag Lnopanic.
+func (l *Logger) Panicln(v ...interface{}) {
+	l.Outputln(2, Lnopanic, v...)
+	s := fmt.Sprintln(v...)
+	panic(s)
+}
+
+// Panicln prints the message like Println and calls panic. The printing
+// might be suppressed by the flag Lnopanic.
+func Panicln(v ...interface{}) {
+	std.Outputln(2, Lnopanic, v...)
+	s := fmt.Sprintln(v...)
+	panic(s)
+}
+
+// Fatal prints the message like Print and calls os.Exit(1). The
+// printing might be suppressed by the flag Lnofatal.
+func (l *Logger) Fatal(v ...interface{}) {
+	l.Output(2, Lnofatal, v...)
+	os.Exit(1)
+}
+
+// Fatal prints the message like Print and calls os.Exit(1). The
+// printing might be suppressed by the flag Lnofatal.
+func Fatal(v ...interface{}) {
+	std.Output(2, Lnofatal, v...)
+	os.Exit(1)
+}
+
+// Fatalf prints the message like Printf and calls os.Exit(1). The
+// printing might be suppressed by the flag Lnofatal.
+func (l *Logger) Fatalf(format string, v ...interface{}) {
+	l.Outputf(2, Lnofatal, format, v...)
+	os.Exit(1)
+}
+
+// Fatalf prints the message like Printf and calls os.Exit(1). The
+// printing might be suppressed by the flag Lnofatal.
+func Fatalf(format string, v ...interface{}) {
+	std.Outputf(2, Lnofatal, format, v...)
+	os.Exit(1)
+}
+
+// Fatalln prints the message like Println and calls os.Exit(1). The
+// printing might be suppressed by the flag Lnofatal.
+func (l *Logger) Fatalln(format string, v ...interface{}) {
+	l.Outputln(2, Lnofatal, v...)
+	os.Exit(1)
+}
+
+// Fatalln prints the message like Println and calls os.Exit(1). The
+// printing might be suppressed by the flag Lnofatal.
+func Fatalln(format string, v ...interface{}) {
+	std.Outputln(2, Lnofatal, v...)
+	os.Exit(1)
+}
+
+// Warn prints the message like Print. The printing might be suppressed
+// by the flag Lnowarn.
+func (l *Logger) Warn(v ...interface{}) {
+	l.Output(2, Lnowarn, v...)
+}
+
+// Warn prints the message like Print. The printing might be suppressed
+// by the flag Lnowarn.
+func Warn(v ...interface{}) {
+	std.Output(2, Lnowarn, v...)
+}
+
+// Warnf prints the message like Printf. The printing might be suppressed
+// by the flag Lnowarn.
+func (l *Logger) Warnf(format string, v ...interface{}) {
+	l.Outputf(2, Lnowarn, format, v...)
+}
+
+// Warnf prints the message like Printf. The printing might be suppressed
+// by the flag Lnowarn.
+func Warnf(format string, v ...interface{}) {
+	std.Outputf(2, Lnowarn, format, v...)
+}
+
+// Warnln prints the message like Println. The printing might be suppressed
+// by the flag Lnowarn.
+func (l *Logger) Warnln(v ...interface{}) {
+	l.Outputln(2, Lnowarn, v...)
+}
+
+// Warnln prints the message like Println. The printing might be suppressed
+// by the flag Lnowarn.
+func Warnln(v ...interface{}) {
+	std.Outputln(2, Lnowarn, v...)
+}
+
+// Print prints the message like fmt.Print. The printing might be suppressed
+// by the flag Lnoprint.
+func (l *Logger) Print(v ...interface{}) {
+	l.Output(2, Lnoprint, v...)
+}
+
+// Print prints the message like fmt.Print. The printing might be suppressed
+// by the flag Lnoprint.
+func Print(v ...interface{}) {
+	std.Output(2, Lnoprint, v...)
+}
+
+// Printf prints the message like fmt.Printf. The printing might be suppressed
+// by the flag Lnoprint.
+func (l *Logger) Printf(format string, v ...interface{}) {
+	l.Outputf(2, Lnoprint, format, v...)
+}
+
+// Printf prints the message like fmt.Printf. The printing might be suppressed
+// by the flag Lnoprint.
+func Printf(format string, v ...interface{}) {
+	std.Outputf(2, Lnoprint, format, v...)
+}
+
+// Println prints the message like fmt.Println. The printing might be
+// suppressed by the flag Lnoprint.
+func (l *Logger) Println(v ...interface{}) {
+	l.Outputln(2, Lnoprint, v...)
+}
+
+// Println prints the message like fmt.Println. The printing might be
+// suppressed by the flag Lnoprint.
+func Println(v ...interface{}) {
+	std.Outputln(2, Lnoprint, v...)
+}
+
+// Debug prints the message like Print. The printing might be suppressed
+// by the flag Lnodebug.
+func (l *Logger) Debug(v ...interface{}) {
+	l.Output(2, Lnodebug, v...)
+}
+
+// Debug prints the message like Print. The printing might be suppressed
+// by the flag Lnodebug.
+func Debug(v ...interface{}) {
+	std.Output(2, Lnodebug, v...)
+}
+
+// Debugf prints the message like Printf. The printing might be suppressed
+// by the flag Lnodebug.
+func (l *Logger) Debugf(format string, v ...interface{}) {
+	l.Outputf(2, Lnodebug, format, v...)
+}
+
+// Debugf prints the message like Printf. The printing might be suppressed
+// by the flag Lnodebug.
+func Debugf(format string, v ...interface{}) {
+	std.Outputf(2, Lnodebug, format, v...)
+}
+
+// Debugln prints the message like Println. The printing might be suppressed
+// by the flag Lnodebug.
+func (l *Logger) Debugln(v ...interface{}) {
+	l.Outputln(2, Lnodebug, v...)
+}
+
+// Debugln prints the message like Println. The printing might be suppressed
+// by the flag Lnodebug.
+func Debugln(v ...interface{}) {
+	std.Outputln(2, Lnodebug, v...)
+}
+
+// Flags returns the current flags used by the logger.
+func (l *Logger) Flags() int {
+	l.mu.Lock()
+	defer l.mu.Unlock()
+	return l.flag
+}
+
+// Flags returns the current flags used by the standard logger.
+func Flags() int {
+	return std.Flags()
+}
+
+// SetFlags sets the flags of the logger.
+func (l *Logger) SetFlags(flag int) {
+	l.mu.Lock()
+	defer l.mu.Unlock()
+	l.flag = flag
+}
+
+// SetFlags sets the flags for the standard logger.
+func SetFlags(flag int) {
+	std.SetFlags(flag)
+}
+
+// Prefix returns the prefix used by the logger.
+func (l *Logger) Prefix() string {
+	l.mu.Lock()
+	defer l.mu.Unlock()
+	return l.prefix
+}
+
+// Prefix returns the prefix used by the standard logger of the package.
+func Prefix() string {
+	return std.Prefix()
+}
+
+// SetPrefix sets the prefix for the logger.
+func (l *Logger) SetPrefix(prefix string) {
+	l.mu.Lock()
+	defer l.mu.Unlock()
+	l.prefix = prefix
+}
+
+// SetPrefix sets the prefix of the standard logger of the package.
+func SetPrefix(prefix string) {
+	std.SetPrefix(prefix)
+}
+
+// SetOutput sets the output of the logger.
+func (l *Logger) SetOutput(w io.Writer) {
+	l.mu.Lock()
+	defer l.mu.Unlock()
+	l.out = w
+}
+
+// SetOutput sets the output for the standard logger of the package.
+func SetOutput(w io.Writer) {
+	std.SetOutput(w)
+}

@@ -0,0 +1,522 @@
+// Copyright 2014-2022 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"
+	"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
+}

@@ -0,0 +1,47 @@
+// Copyright 2014-2022 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])
+}

@@ -0,0 +1,39 @@
+// Copyright 2014-2022 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
+}

@@ -0,0 +1,171 @@
+// Copyright 2014-2022 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
+}

@@ -0,0 +1,37 @@
+// Copyright 2014-2022 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
+}

@@ -0,0 +1,277 @@
+// Copyright 2014-2022 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
+}