1/*
2 * Copyright (c) 2000-2006 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/* Copyright (c) 1997 Apple Computer, Inc. All Rights Reserved */
29/*
30 * Copyright (c) 1993, 1994 Theo de Raadt
31 * All rights reserved.
32 *
33 * Redistribution and use in source and binary forms, with or without
34 * modification, are permitted provided that the following conditions
35 * are met:
36 * 1. Redistributions of source code must retain the above copyright
37 *    notice unmodified, this list of conditions, and the following
38 *    disclaimer.
39 * 2. Redistributions in binary form must reproduce the above copyright
40 *    notice, this list of conditions and the following disclaimer in the
41 *    documentation and/or other materials provided with the distribution.
42 *
43 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
44 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
45 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
46 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
47 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
48 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
49 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
50 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
51 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
52 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
53 * SUCH DAMAGE.
54 *
55 */
56
57/*
58 * We use the NetBSD based clist system, it is much more efficient than the
59 * old style clist stuff used by free bsd.
60 */
61
62#include <sys/param.h>
63#include <sys/systm.h>
64#include <sys/ioctl.h>
65#include <sys/tty.h>
66#include <sys/malloc.h>
67
68
69/*
70 * At compile time, choose:
71 * There are two ways the TTY_QUOTE bit can be stored. If QBITS is
72 * defined we allocate an array of bits -- 1/8th as much memory but
73 * setbit(), clrbit(), and isset() take more cpu. If QBITS is
74 * undefined, we just use an array of bytes.
75 *
76 * If TTY_QUOTE functionality isn't required by a line discipline,
77 * it can free c_cq and set it to NULL. This speeds things up,
78 * and also does not use any extra memory. This is useful for (say)
79 * a SLIP line discipline that wants a 32K ring buffer for data
80 * but doesn't need quoting.
81 */
82#define QBITS
83
84#ifdef QBITS
85#define QMEM(n)		((((n)-1)/NBBY)+1)
86#else
87#define QMEM(n)		(n)
88#endif
89
90
91/*
92 * Initialize clists.
93 */
94void
95cinit(void)
96{
97}
98
99/*
100 * Initialize a particular clist. Ok, they are really ring buffers,
101 * of the specified length, with/without quoting support.
102 */
103int
104clalloc(struct clist *clp, int size, int quot)
105{
106	MALLOC_ZONE(clp->c_cs, u_char *, size, M_TTYS, M_WAITOK);
107	if (!clp->c_cs)
108		return (-1);
109	bzero(clp->c_cs, size);
110
111	if(quot) {
112		MALLOC_ZONE(clp->c_cq, u_char *, QMEM(size), M_TTYS, M_WAITOK);
113		if (!clp->c_cq) {
114			FREE_ZONE(clp->c_cs, size, M_TTYS);
115			return (-1);
116		}
117		bzero(clp->c_cs, QMEM(size));
118	} else
119		clp->c_cq = (u_char *)0;
120
121	clp->c_cf = clp->c_cl = (u_char *)0;
122	clp->c_ce = clp->c_cs + size;
123	clp->c_cn = size;
124	clp->c_cc = 0;
125	return (0);
126}
127
128void
129clfree(struct clist *clp)
130{
131	if(clp->c_cs)
132		FREE_ZONE(clp->c_cs, clp->c_cn, M_TTYS);
133	if(clp->c_cq)
134		FREE_ZONE(clp->c_cq, QMEM(clp->c_cn), M_TTYS);
135	clp->c_cs = clp->c_cq = (u_char *)0;
136}
137
138
139/*
140 * Get a character from a clist.
141 */
142int
143getc(struct clist *clp)
144{
145	int c = -1;
146
147	if (clp->c_cc == 0)
148		goto out;
149
150	c = *clp->c_cf & 0xff;
151	if (clp->c_cq) {
152#ifdef QBITS
153		if (isset(clp->c_cq, clp->c_cf - clp->c_cs) )
154			c |= TTY_QUOTE;
155#else
156		if (*(clp->c_cf - clp->c_cs + clp->c_cq))
157			c |= TTY_QUOTE;
158#endif
159	}
160	if (++clp->c_cf == clp->c_ce)
161		clp->c_cf = clp->c_cs;
162	if (--clp->c_cc == 0)
163		clp->c_cf = clp->c_cl = (u_char *)0;
164out:
165	return c;
166}
167
168/*
169 * Copy clist to buffer.
170 * Return number of bytes moved.
171 */
172int
173q_to_b(struct clist *clp, u_char *cp, int count)
174{
175	int cc;
176	u_char *p = cp;
177
178	/* optimize this while loop */
179	while (count > 0 && clp->c_cc > 0) {
180		cc = clp->c_cl - clp->c_cf;
181		if (clp->c_cf >= clp->c_cl)
182			cc = clp->c_ce - clp->c_cf;
183		if (cc > count)
184			cc = count;
185		bcopy(clp->c_cf, p, cc);
186		count -= cc;
187		p += cc;
188		clp->c_cc -= cc;
189		clp->c_cf += cc;
190		if (clp->c_cf == clp->c_ce)
191			clp->c_cf = clp->c_cs;
192	}
193	if (clp->c_cc == 0)
194		clp->c_cf = clp->c_cl = (u_char *)0;
195	return p - cp;
196}
197
198/*
199 * Return count of contiguous characters in clist.
200 * Stop counting if flag&character is non-null.
201 */
202int
203ndqb(struct clist *clp, int flag)
204{
205	int count = 0;
206	register int i;
207	register int cc;
208
209	if ((cc = clp->c_cc) == 0)
210		goto out;
211
212	if (flag == 0) {
213		count = clp->c_cl - clp->c_cf;
214		if (count <= 0)
215			count = clp->c_ce - clp->c_cf;
216		goto out;
217	}
218
219	i = clp->c_cf - clp->c_cs;
220	if (flag & TTY_QUOTE) {
221		while (cc-- > 0 && !(clp->c_cs[i++] & (flag & ~TTY_QUOTE) ||
222		    isset(clp->c_cq, i))) {
223			count++;
224			if (i == clp->c_cn)
225				break;
226		}
227	} else {
228		while (cc-- > 0 && !(clp->c_cs[i++] & flag)) {
229			count++;
230			if (i == clp->c_cn)
231				break;
232		}
233	}
234out:
235	return count;
236}
237
238/*
239 * Flush count bytes from clist.
240 */
241void
242ndflush(struct clist *clp, int count)
243{
244	int cc;
245
246	if (count == clp->c_cc) {
247		clp->c_cc = 0;
248		clp->c_cf = clp->c_cl = (u_char *)0;
249		return;
250	}
251	/* optimize this while loop */
252	while (count > 0 && clp->c_cc > 0) {
253		cc = clp->c_cl - clp->c_cf;
254		if (clp->c_cf >= clp->c_cl)
255			cc = clp->c_ce - clp->c_cf;
256		if (cc > count)
257			cc = count;
258		count -= cc;
259		clp->c_cc -= cc;
260		clp->c_cf += cc;
261		if (clp->c_cf == clp->c_ce)
262			clp->c_cf = clp->c_cs;
263	}
264	if (clp->c_cc == 0)
265		clp->c_cf = clp->c_cl = (u_char *)0;
266}
267
268/*
269 * Put a character into the output queue.
270 */
271int
272putc(int c, struct clist *clp)
273{
274	register int i;
275
276	if (clp->c_cc == 0) {
277		if (!clp->c_cs) {
278#if DIAGNOSTIC
279			//printf("putc: required clalloc\n");
280#endif
281			if(clalloc(clp, 1024, 1)) {
282out:
283				return -1;
284			}
285		}
286		clp->c_cf = clp->c_cl = clp->c_cs;
287	}
288
289	if (clp->c_cc == clp->c_cn)
290		goto out;
291
292	*clp->c_cl = c & 0xff;
293	i = clp->c_cl - clp->c_cs;
294	if (clp->c_cq) {
295#ifdef QBITS
296		if (c & TTY_QUOTE)
297			setbit(clp->c_cq, i);
298		else
299			clrbit(clp->c_cq, i);
300#else
301		q = clp->c_cq + i;
302		*q = (c & TTY_QUOTE) ? 1 : 0;
303#endif
304	}
305	clp->c_cc++;
306	clp->c_cl++;
307	if (clp->c_cl == clp->c_ce)
308		clp->c_cl = clp->c_cs;
309	return 0;
310}
311
312#ifdef QBITS
313/*
314 * optimized version of
315 *
316 * for (i = 0; i < len; i++)
317 *	clrbit(cp, off + len);
318 */
319void
320clrbits(u_char *cp, int off, int len)
321{
322	int sby, sbi, eby, ebi;
323	register int i;
324	u_char mask;
325
326	if(len==1) {
327		clrbit(cp, off);
328		return;
329	}
330
331	sby = off / NBBY;
332	sbi = off % NBBY;
333	eby = (off+len) / NBBY;
334	ebi = (off+len) % NBBY;
335	if (sby == eby) {
336		mask = ((1 << (ebi - sbi)) - 1) << sbi;
337		cp[sby] &= ~mask;
338	} else {
339		mask = (1<<sbi) - 1;
340		cp[sby++] &= mask;
341
342		mask = (1<<ebi) - 1;
343		/* handle remainder bits, if any, for a non-0 ebi value */
344		if (mask)
345			cp[eby] &= ~mask;
346
347		for (i = sby; i < eby; i++)
348			cp[i] = 0x00;
349	}
350}
351#endif
352
353/*
354 * Copy buffer to clist.
355 * Return number of bytes not transfered.
356 */
357int
358b_to_q(const u_char *cp, int count, struct clist *clp)
359{
360	int cc;
361	const u_char *p = cp;
362
363	if (count <= 0)
364		return 0;
365
366
367	if (clp->c_cc == 0) {
368		if (!clp->c_cs) {
369#if DIAGNOSTIC
370			printf("b_to_q: required clalloc\n");
371#endif
372			if(clalloc(clp, 1024, 1))
373				goto out;
374		}
375		clp->c_cf = clp->c_cl = clp->c_cs;
376	}
377
378	if (clp->c_cc == clp->c_cn)
379		goto out;
380
381	/* optimize this while loop */
382	while (count > 0 && clp->c_cc < clp->c_cn) {
383		cc = clp->c_ce - clp->c_cl;
384		if (clp->c_cf > clp->c_cl)
385			cc = clp->c_cf - clp->c_cl;
386		if (cc > count)
387			cc = count;
388		bcopy(p, clp->c_cl, cc);
389		if (clp->c_cq) {
390#ifdef QBITS
391			clrbits(clp->c_cq, clp->c_cl - clp->c_cs, cc);
392#else
393			bzero(clp->c_cl - clp->c_cs + clp->c_cq, cc);
394#endif
395		}
396		p += cc;
397		count -= cc;
398		clp->c_cc += cc;
399		clp->c_cl += cc;
400		if (clp->c_cl == clp->c_ce)
401			clp->c_cl = clp->c_cs;
402	}
403out:
404	return count;
405}
406
407static int cc;
408
409/*
410 * Given a non-NULL pointer into the clist return the pointer
411 * to the next character in the list or return NULL if no more chars.
412 *
413 * Callers must not allow getc's to happen between firstc's and getc's
414 * so that the pointer becomes invalid.  Note that interrupts are NOT
415 * masked.
416 */
417u_char *
418nextc(struct clist *clp, u_char *cp, int *c)
419{
420	if (clp->c_cf == cp) {
421		/*
422		 * First time initialization.
423		 */
424		cc = clp->c_cc;
425	}
426	if (cc == 0 || cp == NULL)
427		return NULL;
428	if (--cc == 0)
429		return NULL;
430	if (++cp == clp->c_ce)
431		cp = clp->c_cs;
432	*c = *cp & 0xff;
433	if (clp->c_cq) {
434#ifdef QBITS
435		if (isset(clp->c_cq, cp - clp->c_cs))
436			*c |= TTY_QUOTE;
437#else
438		if (*(clp->c_cf - clp->c_cs + clp->c_cq))
439			*c |= TTY_QUOTE;
440#endif
441	}
442	return cp;
443}
444
445/*
446 * Given a non-NULL pointer into the clist return the pointer
447 * to the first character in the list or return NULL if no more chars.
448 *
449 * Callers must not allow getc's to happen between firstc's and getc's
450 * so that the pointer becomes invalid.  Note that interrupts are NOT
451 * masked.
452 *
453 * *c is set to the NEXT character
454 */
455u_char *
456firstc(struct clist *clp, int *c)
457{
458	u_char *cp;
459
460	cc = clp->c_cc;
461	if (cc == 0)
462		return NULL;
463	cp = clp->c_cf;
464	*c = *cp & 0xff;
465	if(clp->c_cq) {
466#ifdef QBITS
467		if (isset(clp->c_cq, cp - clp->c_cs))
468			*c |= TTY_QUOTE;
469#else
470		if (*(cp - clp->c_cs + clp->c_cq))
471			*c |= TTY_QUOTE;
472#endif
473	}
474	return clp->c_cf;
475}
476
477/*
478 * Remove the last character in the clist and return it.
479 */
480int
481unputc(struct clist *clp)
482{
483	unsigned int c = -1;
484
485	if (clp->c_cc == 0)
486		goto out;
487
488	if (clp->c_cl == clp->c_cs)
489		clp->c_cl = clp->c_ce - 1;
490	else
491		--clp->c_cl;
492	clp->c_cc--;
493
494	c = *clp->c_cl & 0xff;
495	if (clp->c_cq) {
496#ifdef QBITS
497		if (isset(clp->c_cq, clp->c_cl - clp->c_cs))
498			c |= TTY_QUOTE;
499#else
500		if (*(clp->c_cf - clp->c_cs + clp->c_cq))
501			c |= TTY_QUOTE;
502#endif
503	}
504	if (clp->c_cc == 0)
505		clp->c_cf = clp->c_cl = (u_char *)0;
506out:
507	return c;
508}
509
510/*
511 * Put the chars in the from queue on the end of the to queue.
512 */
513void
514catq(struct clist *from, struct clist *to)
515{
516	int c;
517
518	while ((c = getc(from)) != -1)
519		putc(c, to);
520}
521