1// Copyright 2014-2022 Ulrich Kunitz. All rights reserved.
  2// Use of this source code is governed by a BSD-style
  3// license that can be found in the LICENSE file.
  4
  5package lzma
  6
  7import (
  8	"errors"
  9)
 10
 11// buffer provides a circular buffer of bytes. If the front index equals
 12// the rear index the buffer is empty. As a consequence front cannot be
 13// equal rear for a full buffer. So a full buffer has a length that is
 14// one byte less the the length of the data slice.
 15type buffer struct {
 16	data  []byte
 17	front int
 18	rear  int
 19}
 20
 21// newBuffer creates a buffer with the given size.
 22func newBuffer(size int) *buffer {
 23	return &buffer{data: make([]byte, size+1)}
 24}
 25
 26// Cap returns the capacity of the buffer.
 27func (b *buffer) Cap() int {
 28	return len(b.data) - 1
 29}
 30
 31// Resets the buffer. The front and rear index are set to zero.
 32func (b *buffer) Reset() {
 33	b.front = 0
 34	b.rear = 0
 35}
 36
 37// Buffered returns the number of bytes buffered.
 38func (b *buffer) Buffered() int {
 39	delta := b.front - b.rear
 40	if delta < 0 {
 41		delta += len(b.data)
 42	}
 43	return delta
 44}
 45
 46// Available returns the number of bytes available for writing.
 47func (b *buffer) Available() int {
 48	delta := b.rear - 1 - b.front
 49	if delta < 0 {
 50		delta += len(b.data)
 51	}
 52	return delta
 53}
 54
 55// addIndex adds a non-negative integer to the index i and returns the
 56// resulting index. The function takes care of wrapping the index as
 57// well as potential overflow situations.
 58func (b *buffer) addIndex(i int, n int) int {
 59	// subtraction of len(b.data) prevents overflow
 60	i += n - len(b.data)
 61	if i < 0 {
 62		i += len(b.data)
 63	}
 64	return i
 65}
 66
 67// Read reads bytes from the buffer into p and returns the number of
 68// bytes read. The function never returns an error but might return less
 69// data than requested.
 70func (b *buffer) Read(p []byte) (n int, err error) {
 71	n, err = b.Peek(p)
 72	b.rear = b.addIndex(b.rear, n)
 73	return n, err
 74}
 75
 76// Peek reads bytes from the buffer into p without changing the buffer.
 77// Peek will never return an error but might return less data than
 78// requested.
 79func (b *buffer) Peek(p []byte) (n int, err error) {
 80	m := b.Buffered()
 81	n = len(p)
 82	if m < n {
 83		n = m
 84		p = p[:n]
 85	}
 86	k := copy(p, b.data[b.rear:])
 87	if k < n {
 88		copy(p[k:], b.data)
 89	}
 90	return n, nil
 91}
 92
 93// Discard skips the n next bytes to read from the buffer, returning the
 94// bytes discarded.
 95//
 96// If Discards skips fewer than n bytes, it returns an error.
 97func (b *buffer) Discard(n int) (discarded int, err error) {
 98	if n < 0 {
 99		return 0, errors.New("buffer.Discard: negative argument")
100	}
101	m := b.Buffered()
102	if m < n {
103		n = m
104		err = errors.New(
105			"buffer.Discard: discarded less bytes then requested")
106	}
107	b.rear = b.addIndex(b.rear, n)
108	return n, err
109}
110
111// ErrNoSpace indicates that there is insufficient space for the Write
112// operation.
113var ErrNoSpace = errors.New("insufficient space")
114
115// Write puts data into the  buffer. If less bytes are written than
116// requested ErrNoSpace is returned.
117func (b *buffer) Write(p []byte) (n int, err error) {
118	m := b.Available()
119	n = len(p)
120	if m < n {
121		n = m
122		p = p[:m]
123		err = ErrNoSpace
124	}
125	k := copy(b.data[b.front:], p)
126	if k < n {
127		copy(b.data, p[k:])
128	}
129	b.front = b.addIndex(b.front, n)
130	return n, err
131}
132
133// WriteByte writes a single byte into the buffer. The error ErrNoSpace
134// is returned if no single byte is available in the buffer for writing.
135func (b *buffer) WriteByte(c byte) error {
136	if b.Available() < 1 {
137		return ErrNoSpace
138	}
139	b.data[b.front] = c
140	b.front = b.addIndex(b.front, 1)
141	return nil
142}
143
144// prefixLen returns the length of the common prefix of a and b.
145func prefixLen(a, b []byte) int {
146	if len(a) > len(b) {
147		a, b = b, a
148	}
149	for i, c := range a {
150		if b[i] != c {
151			return i
152		}
153	}
154	return len(a)
155}
156
157// matchLen returns the length of the common prefix for the given
158// distance from the rear and the byte slice p.
159func (b *buffer) matchLen(distance int, p []byte) int {
160	var n int
161	i := b.rear - distance
162	if i < 0 {
163		if n = prefixLen(p, b.data[len(b.data)+i:]); n < -i {
164			return n
165		}
166		p = p[n:]
167		i = 0
168	}
169	n += prefixLen(p, b.data[i:])
170	return n
171}