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