1 /*	$OpenBSD: ring.c,v 1.5 2003/06/03 02:56:18 millert 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
ring_init(ring,buffer,count)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 #if    defined(ENCRYPTION)
98     ring->clearto = 0;
99 #endif
100 
101     return 1;
102 }
103 
104 /* Mark routines */
105 
106 /*
107  * Mark the most recently supplied byte.
108  */
109 
110     void
ring_mark(ring)111 ring_mark(ring)
112     Ring *ring;
113 {
114     ring->mark = ring_decrement(ring, ring->supply, 1);
115 }
116 
117 /*
118  * Is the ring pointing to the mark?
119  */
120 
121     int
ring_at_mark(ring)122 ring_at_mark(ring)
123     Ring *ring;
124 {
125     if (ring->mark == ring->consume) {
126 	return 1;
127     } else {
128 	return 0;
129     }
130 }
131 
132 /*
133  * Clear any mark set on the ring.
134  */
135 
136     void
ring_clear_mark(ring)137 ring_clear_mark(ring)
138     Ring *ring;
139 {
140     ring->mark = 0;
141 }
142 
143 /*
144  * Add characters from current segment to ring buffer.
145  */
146     void
ring_supplied(ring,count)147 ring_supplied(ring, count)
148     Ring *ring;
149     int count;
150 {
151     ring->supply = ring_increment(ring, ring->supply, count);
152     ring->supplytime = ++ring_clock;
153 }
154 
155 /*
156  * We have just consumed "c" bytes.
157  */
158     void
ring_consumed(ring,count)159 ring_consumed(ring, count)
160     Ring *ring;
161     int count;
162 {
163     if (count == 0)	/* don't update anything */
164 	return;
165 
166     if (ring->mark &&
167 		(ring_subtract(ring, ring->mark, ring->consume) < count)) {
168 	ring->mark = 0;
169     }
170 #if    defined(ENCRYPTION)
171     if (ring->consume < ring->clearto &&
172                ring->clearto <= ring->consume + count)
173 	ring->clearto = 0;
174     else if (ring->consume + count > ring->top &&
175                ring->bottom <= ring->clearto &&
176                ring->bottom + ((ring->consume + count) - ring->top))
177 	ring->clearto = 0;
178 #endif
179     ring->consume = ring_increment(ring, ring->consume, count);
180     ring->consumetime = ++ring_clock;
181     /*
182      * Try to encourage "ring_empty_consecutive()" to be large.
183      */
184     if (ring_empty(ring)) {
185 	ring->consume = ring->supply = ring->bottom;
186     }
187 }
188 
189 
190 
191 /* Buffer state query routines */
192 
193 
194 /* Number of bytes that may be supplied */
195     int
ring_empty_count(ring)196 ring_empty_count(ring)
197     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
ring_empty_consecutive(ring)208 ring_empty_consecutive(ring)
209     Ring *ring;
210 {
211     if ((ring->consume < ring->supply) || ring_empty(ring)) {
212 			    /*
213 			     * if consume is "below" supply, or empty, then
214 			     * return distance to the top
215 			     */
216 	return ring_subtract(ring, ring->top, ring->supply);
217     } else {
218 				    /*
219 				     * else, return what we may.
220 				     */
221 	return ring_subtract(ring, ring->consume, ring->supply);
222     }
223 }
224 
225 /* Return the number of bytes that are available for consuming
226  * (but don't give more than enough to get to cross over set mark)
227  */
228 
229     int
ring_full_count(ring)230 ring_full_count(ring)
231     Ring *ring;
232 {
233     if ((ring->mark == 0) || (ring->mark == ring->consume)) {
234 	if (ring_full(ring)) {
235 	    return ring->size;	/* nothing consumed, but full */
236 	} else {
237 	    return ring_subtract(ring, ring->supply, ring->consume);
238 	}
239     } else {
240 	return ring_subtract(ring, ring->mark, ring->consume);
241     }
242 }
243 
244 /*
245  * Return the number of CONSECUTIVE bytes available for consuming.
246  * However, don't return more than enough to cross over set mark.
247  */
248     int
ring_full_consecutive(ring)249 ring_full_consecutive(ring)
250     Ring *ring;
251 {
252     if ((ring->mark == 0) || (ring->mark == ring->consume)) {
253 	if ((ring->supply < ring->consume) || ring_full(ring)) {
254 	    return ring_subtract(ring, ring->top, ring->consume);
255 	} else {
256 	    return ring_subtract(ring, ring->supply, ring->consume);
257 	}
258     } else {
259 	if (ring->mark < ring->consume) {
260 	    return ring_subtract(ring, ring->top, ring->consume);
261 	} else {	/* Else, distance to mark */
262 	    return ring_subtract(ring, ring->mark, ring->consume);
263 	}
264     }
265 }
266 
267 /*
268  * Move data into the "supply" portion of of the ring buffer.
269  */
270     void
ring_supply_data(ring,buffer,count)271 ring_supply_data(ring, buffer, count)
272     Ring *ring;
273     unsigned char *buffer;
274     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
ring_consume_data(ring,buffer,count)293 ring_consume_data(ring, buffer, count)
294     Ring *ring;
295     unsigned char *buffer;
296     int count;
297 {
298     int i;
299 
300     while (count) {
301 	i = MIN(count, ring_full_consecutive(ring));
302 	memmove(buffer, ring->consume, i);
303 	ring_consumed(ring, i);
304 	count -= i;
305 	buffer += i;
306     }
307 }
308 #endif
309 
310 #if    defined(ENCRYPTION)
311 void
ring_encrypt(Ring * ring,void (* encryptor)())312 ring_encrypt(Ring *ring, void (*encryptor)())
313 {
314     unsigned char *s, *c;
315 
316     if (ring_empty(ring) || ring->clearto == ring->supply)
317 	return;
318 
319     if (!(c = ring->clearto))
320 	c = ring->consume;
321 
322     s = ring->supply;
323 
324     if (s <= c) {
325 	(*encryptor)(c, ring->top - c);
326 	(*encryptor)(ring->bottom, s - ring->bottom);
327     } else
328 	(*encryptor)(c, s - c);
329 
330     ring->clearto = ring->supply;
331 }
332 
333 void
ring_clearto(Ring * ring)334 ring_clearto(Ring *ring)
335 {
336     if (!ring_empty(ring))
337 	ring->clearto = ring->supply;
338     else
339 	ring->clearto = 0;
340 }
341 #endif
342 
343