1// Copyright 2014-2017 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}
172