1 /* $OpenBSD: ring.c,v 1.6 2014/07/19 23:50:38 guenther Exp $ */ 2 /* $NetBSD: ring.c,v 1.7 1996/02/28 21:04:07 thorpej Exp $ */ 3 4 /* 5 * Copyright (c) 1988, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 */ 32 33 #include "telnet_locl.h" 34 35 /* 36 * This defines a structure for a ring buffer. 37 * 38 * The circular buffer has two parts: 39 *((( 40 * full: [consume, supply) 41 * empty: [supply, consume) 42 *]]] 43 * 44 */ 45 46 /* Internal macros */ 47 48 #if !defined(MIN) 49 #define MIN(a,b) (((a)<(b))? (a):(b)) 50 #endif /* !defined(MIN) */ 51 52 #define ring_subtract(d,a,b) (((a)-(b) >= 0)? \ 53 (a)-(b): (((a)-(b))+(d)->size)) 54 55 #define ring_increment(d,a,c) (((a)+(c) < (d)->top)? \ 56 (a)+(c) : (((a)+(c))-(d)->size)) 57 58 #define ring_decrement(d,a,c) (((a)-(c) >= (d)->bottom)? \ 59 (a)-(c) : (((a)-(c))-(d)->size)) 60 61 62 /* 63 * The following is a clock, used to determine full, empty, etc. 64 * 65 * There is some trickiness here. Since the ring buffers are initialized 66 * to ZERO on allocation, we need to make sure, when interpreting the 67 * clock, that when the times are EQUAL, then the buffer is FULL. 68 */ 69 static u_long ring_clock = 0; 70 71 72 #define ring_empty(d) (((d)->consume == (d)->supply) && \ 73 ((d)->consumetime >= (d)->supplytime)) 74 #define ring_full(d) (((d)->supply == (d)->consume) && \ 75 ((d)->supplytime > (d)->consumetime)) 76 77 78 79 80 81 /* Buffer state transition routines */ 82 83 int 84 ring_init(ring, buffer, count) 85 Ring *ring; 86 unsigned char *buffer; 87 int count; 88 { 89 memset((char *)ring, 0, sizeof *ring); 90 91 ring->size = count; 92 93 ring->supply = ring->consume = ring->bottom = buffer; 94 95 ring->top = ring->bottom+ring->size; 96 97 return 1; 98 } 99 100 /* Mark routines */ 101 102 /* 103 * Mark the most recently supplied byte. 104 */ 105 106 void 107 ring_mark(ring) 108 Ring *ring; 109 { 110 ring->mark = ring_decrement(ring, ring->supply, 1); 111 } 112 113 /* 114 * Is the ring pointing to the mark? 115 */ 116 117 int 118 ring_at_mark(ring) 119 Ring *ring; 120 { 121 if (ring->mark == ring->consume) { 122 return 1; 123 } else { 124 return 0; 125 } 126 } 127 128 /* 129 * Clear any mark set on the ring. 130 */ 131 132 void 133 ring_clear_mark(ring) 134 Ring *ring; 135 { 136 ring->mark = 0; 137 } 138 139 /* 140 * Add characters from current segment to ring buffer. 141 */ 142 void 143 ring_supplied(ring, count) 144 Ring *ring; 145 int count; 146 { 147 ring->supply = ring_increment(ring, ring->supply, count); 148 ring->supplytime = ++ring_clock; 149 } 150 151 /* 152 * We have just consumed "c" bytes. 153 */ 154 void 155 ring_consumed(ring, count) 156 Ring *ring; 157 int count; 158 { 159 if (count == 0) /* don't update anything */ 160 return; 161 162 if (ring->mark && 163 (ring_subtract(ring, ring->mark, ring->consume) < count)) { 164 ring->mark = 0; 165 } 166 ring->consume = ring_increment(ring, ring->consume, count); 167 ring->consumetime = ++ring_clock; 168 /* 169 * Try to encourage "ring_empty_consecutive()" to be large. 170 */ 171 if (ring_empty(ring)) { 172 ring->consume = ring->supply = ring->bottom; 173 } 174 } 175 176 177 178 /* Buffer state query routines */ 179 180 181 /* Number of bytes that may be supplied */ 182 int 183 ring_empty_count(ring) 184 Ring *ring; 185 { 186 if (ring_empty(ring)) { /* if empty */ 187 return ring->size; 188 } else { 189 return ring_subtract(ring, ring->consume, ring->supply); 190 } 191 } 192 193 /* number of CONSECUTIVE bytes that may be supplied */ 194 int 195 ring_empty_consecutive(ring) 196 Ring *ring; 197 { 198 if ((ring->consume < ring->supply) || ring_empty(ring)) { 199 /* 200 * if consume is "below" supply, or empty, then 201 * return distance to the top 202 */ 203 return ring_subtract(ring, ring->top, ring->supply); 204 } else { 205 /* 206 * else, return what we may. 207 */ 208 return ring_subtract(ring, ring->consume, ring->supply); 209 } 210 } 211 212 /* Return the number of bytes that are available for consuming 213 * (but don't give more than enough to get to cross over set mark) 214 */ 215 216 int 217 ring_full_count(ring) 218 Ring *ring; 219 { 220 if ((ring->mark == 0) || (ring->mark == ring->consume)) { 221 if (ring_full(ring)) { 222 return ring->size; /* nothing consumed, but full */ 223 } else { 224 return ring_subtract(ring, ring->supply, ring->consume); 225 } 226 } else { 227 return ring_subtract(ring, ring->mark, ring->consume); 228 } 229 } 230 231 /* 232 * Return the number of CONSECUTIVE bytes available for consuming. 233 * However, don't return more than enough to cross over set mark. 234 */ 235 int 236 ring_full_consecutive(ring) 237 Ring *ring; 238 { 239 if ((ring->mark == 0) || (ring->mark == ring->consume)) { 240 if ((ring->supply < ring->consume) || ring_full(ring)) { 241 return ring_subtract(ring, ring->top, ring->consume); 242 } else { 243 return ring_subtract(ring, ring->supply, ring->consume); 244 } 245 } else { 246 if (ring->mark < ring->consume) { 247 return ring_subtract(ring, ring->top, ring->consume); 248 } else { /* Else, distance to mark */ 249 return ring_subtract(ring, ring->mark, ring->consume); 250 } 251 } 252 } 253 254 /* 255 * Move data into the "supply" portion of of the ring buffer. 256 */ 257 void 258 ring_supply_data(ring, buffer, count) 259 Ring *ring; 260 unsigned char *buffer; 261 int count; 262 { 263 int i; 264 265 while (count) { 266 i = MIN(count, ring_empty_consecutive(ring)); 267 memmove(ring->supply, buffer, i); 268 ring_supplied(ring, i); 269 count -= i; 270 buffer += i; 271 } 272 } 273