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