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