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