window.go

     1  // Copyright 2023 The Go Authors. 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  
     5  package zstd
     6  
     7  // window stores up to size bytes of data.
     8  // It is implemented as a circular buffer:
     9  // sequential save calls append to the data slice until
    10  // its length reaches configured size and after that,
    11  // save calls overwrite previously saved data at off
    12  // and update off such that it always points at
    13  // the byte stored before others.
    14  type window struct {
    15  	size int
    16  	data []byte
    17  	off  int
    18  }
    19  
    20  // reset clears stored data and configures window size.
    21  func (w *window) reset(size int) {
    22  	b := w.data[:0]
    23  	if cap(b) < size {
    24  		b = make([]byte, 0, size)
    25  	}
    26  	w.data = b
    27  	w.off = 0
    28  	w.size = size
    29  }
    30  
    31  // len returns the number of stored bytes.
    32  func (w *window) len() uint32 {
    33  	return uint32(len(w.data))
    34  }
    35  
    36  // save stores up to size last bytes from the buf.
    37  func (w *window) save(buf []byte) {
    38  	if w.size == 0 {
    39  		return
    40  	}
    41  	if len(buf) == 0 {
    42  		return
    43  	}
    44  
    45  	if len(buf) >= w.size {
    46  		from := len(buf) - w.size
    47  		w.data = append(w.data[:0], buf[from:]...)
    48  		w.off = 0
    49  		return
    50  	}
    51  
    52  	// Update off to point to the oldest remaining byte.
    53  	free := w.size - len(w.data)
    54  	if free == 0 {
    55  		n := copy(w.data[w.off:], buf)
    56  		if n == len(buf) {
    57  			w.off += n
    58  		} else {
    59  			w.off = copy(w.data, buf[n:])
    60  		}
    61  	} else {
    62  		if free >= len(buf) {
    63  			w.data = append(w.data, buf...)
    64  		} else {
    65  			w.data = append(w.data, buf[:free]...)
    66  			w.off = copy(w.data, buf[free:])
    67  		}
    68  	}
    69  }
    70  
    71  // appendTo appends stored bytes between from and to indices to the buf.
    72  // Index from must be less or equal to index to and to must be less or equal to w.len().
    73  func (w *window) appendTo(buf []byte, from, to uint32) []byte {
    74  	dataLen := uint32(len(w.data))
    75  	from += uint32(w.off)
    76  	to += uint32(w.off)
    77  
    78  	wrap := false
    79  	if from > dataLen {
    80  		from -= dataLen
    81  		wrap = !wrap
    82  	}
    83  	if to > dataLen {
    84  		to -= dataLen
    85  		wrap = !wrap
    86  	}
    87  
    88  	if wrap {
    89  		buf = append(buf, w.data[from:]...)
    90  		return append(buf, w.data[:to]...)
    91  	} else {
    92  		return append(buf, w.data[from:to]...)
    93  	}
    94  }
    95
View as plain text