#ifdef __cplusplus
extern "C" {
#endif
/*
 *		AIX/370
 *		5713-AFL
 *	LICENSED MATERIALS - PROPERTY OF IBM
 *	(c) Copyright 1989 IBM Corporation
 *	(c) Copyright 1989 Locus Computing Corporation
 *	All Rights Reserved
 */
#ifndef H_SCCSID
#include <sccs.h>
#endif /* ! H_SCCSID */
H_SCCSID(@(#)NLregexp.h	1.3    AIX )       /* Modified: 7/16/92 16:29:32 */


#ifdef _MBCS

#include <mbcs.h>
#include <NLchar.h>
#include <ctype.h>
#include <stdlib.h>
#include <limits.h>
#include <varargs.h>

/*
 * This macro converts an mbchar to an array of bytes.
 * it returns the address of the next position in p
 * Note that there are no embedded nulls in an mbchar_t
 * __len is incremented when a non-0 character was stored in
 *  each of the upper bytes of p
 */

static int	__len, __t;

#define mbtombs(p,c) (__len=0,__t = (c),			\
			((__t) & 0xff000000) || ((__t) <<=8),	\
			((__t) & 0xff000000) || ((__t) <<=8), 	\
			((__t) & 0xff000000) || ((__t) <<=8),	\
			(p[3]=(__t) & 0x000000ff) && __len++,	\
			(p[2]=((__t) & 0x0000ff00)>>8) && __len++,	\
			(p[1]=((__t) & 0x00ff0000)>>16) && __len++,	\
			(p[0]=((__t) & 0xff000000)>>24) && __len++,	\
			p+__len)


#ifdef __CAN_PASTE	/* does compiler paste with ## ? */
#define __PASTE(a,b) a##b
#else
#define __PASTE(a,b) a/**/b
#endif

/*
	Used locally by NLregexp.h, makes conversion of one byte characters
	fast. -cl
*/
#define __mbstomb(mbch, mbs, len) \
	( (_mb_in_tbl->th_chlen_tbl[*((unsigned char *)mbs)] == 1) ? \
	  (*mbch = (mbchar_t)*mbs, 1) : \
	  mbstomb(mbch, mbs, len))

/*
** __PEEKC(mbs) sets the value mbs_peekc and mbs_len, and returns
** the mbchar_t at mbs
** evaluating mbs must not produce a side effect
** callers must examine mbs_peekc for ERR before using mbs_len (it may be -1)
*/

#define __PEEKC(mbs) ((-1==(__PASTE(mbs,_len)=__mbstomb(&__PASTE(mbs,_peekc),mbs,MB_LEN_MAX)))\
			?	__PASTE(mbs,_peekc)=ERR\
			:	__PASTE(mbs,_peekc))

/*
** __GETC returns the next character at mbs, increments mbs.
** evaluating mbs must not have a side effect
*/
#define __GETC(mbs)	(__PEEKC(mbs),mbs+=__PASTE(mbs,_len),__PASTE(mbs,_peekc))

/*
** __UNGETC retracts the mbs pointer by the width of 
** the last character gotten by __GETC
*/
#define __UNGETC(mbs)	(mbs -= __PASTE(mbs,_len), __PASTE(mbs,_len)=0)

/*
** PUTC stuffs an mbchar_t into the char * mbs and bumps mbs
*/
#define __PUTC(str,mb)	mbtombs(str,mb)

/*
** must declare an _len and an _peekc for each cursor using __GETC,
** __PEEKC,__UNGETC
*/
#define __CURSOR(p) mbchar_t __PASTE(p,_peekc); short __PASTE(p,_len); char * p 

__CURSOR(ep);		/* expression pointer */
__CURSOR(lp);		/* line pointer */
__CURSOR(saveep);	/* save expression pointer (for backreferencing) */

/*
** provide a local __ERROR handler that ends up invoking the user provided
** error handler, in case bozo (like sed) wants to do a return in ERROR
*/
#include <setjmp.h>
jmp_buf __NLregexpErrbuf;
#define __ERROR(errcode)	_longjmp(__NLregexpErrbuf,errcode)

/*
** The following __classtab table derives its masks from the following ctype.h
** excerpt.  __classtab must be kept up to date with respect to ctype.h
** 
** #define	iswalpha(c)	(_CTYPE[__wcindx(c)+1]&(_U|_L))
** #define	iswupper(c)	(_CTYPE[__wcindx(c)+1]&_U)
** #define	iswlower(c)	(_CTYPE[__wcindx(c)+1]&_L)
** #define	iswdigit(c)	(_CTYPE[__wcindx(c)+1]&_N)
** #define	iswxdigit(c)	(_CTYPE[__wcindx(c)+1]&_X)
** #define	iswalnum(c)	(_CTYPE[__wcindx(c)+1]&(_U|_L|_N))
** #define	iswspace(c)	(_CTYPE[__wcindx(c)+1]&_S)
** #define	iswpunct(c)	(_CTYPE[__wcindx(c)+1]&_P)
** #define	iswprint(c)	(_CTYPE[__wcindx(c)+1]&(_P|_U|_L|_N|_B))
** #define	iswgraph(c)	(_CTYPE[__wcindx(c)+1]&(_P|_U|_L|_N))
** #define	iswcntrl(c)	(_CTYPE[__wcindx(c)+1]&_C)
*/
struct 				/* this table is consulted */
{				/* when we see [:...:] in a range */
	char * name;		/* the name of the character class */
	short  length;		/* length of the name */
	short  ctype;		/* the internal representation */
} __classtab[]={
	{"alpha:]",7,	_U|_L},
	{"upper:]",7,	_U},
	{"lower:]",7,	_L},
	{"digit:]",7,	_N},
	{"xdigit:]",8,	_X},
	{"alnum:]",7,	_U|_L|_N},
	{"space:]",7,	_S},
	{"punct:]",7,	_P},
	{"print:]",7,	_P|_U|_L|_N|_B},
	{"graph:]",7,	_P|_U|_L|_N},
	{"cntrl:]",7,	_C},
	{NULL,NULL,NULL}
	};

#ifndef ERR
#define ERR (-1)
#endif
#ifndef	WORDSUPPORT1
#define	WORDSUPPORT1 
#endif	
#ifndef	WORDSUPPORT2
#define	WORDSUPPORT2 
#endif	
#ifndef	ADV_CASE
#define	ADV_CASE 
#endif	

/* #define RANGEMAX (NLCHARMAX/8+1) */

#define	CBRA	2
#define	CCHR	4
#define	CDOT	8
#define	CCL	12
#define	CDOL	20
#define	CCEOF	22
#define	CKET	24
#define	CBACK	36
#define NCCL	48
#define CEQV	80
#define	CCOL	84
#define	CCOLF	88
#define	CHCL	92
#define	MINUS	96

#define	STAR	01
#define RNGE	03

#define	NBRA	9

/*
#define PLACE(c)	ep[c >> 3] |= bittab[c & 07]
#define ISTHERE(c, lp, c2)	(c2 = _NCdec2(lp[0],lp[1],c),\
				c = NCcoluniq(c),\
				(ep[c >> 3] & bittab[c & 07]) != 0)
*/
#define PLACE(c) (__PUTC(ep,c))
#define ISTHERE(c,lp,c2) (cclass(ep,lp,c2))

char	*braslist[NBRA];
char	*braelist[NBRA];
char	*loc1, *loc2, *locs;
/* 
char	bittab[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
*/

int     sed, nbra;
int	ebra;
int	nodelim;
int	circf;
int	low;
int	size;

/*
** Error codes lifted from the man page
**
**
   11       Range endpoint too large.
   16       Bad number.
   25       "\"digit out of range.
   36       Illegal or missing delimiter.
   41       No remembered search string.
   42       "\( \)" imbalance.
   43       Too many "\(".
   44       More than two numbers given in \{ \}.
   45       "}" expected after "\".
   46       First number exceeds second in \{ \}.
   49       "[ ]" imbalance.
   50       Regular expression overflow.
*/

#define BIG_RANGE	11       /* Range endpoint too large. */
#define BAD_NUM		16       /* Bad number. */
#define BAD_BACK	25       /* "\"digit out of range. */
#define BAD_DELIM	36       /* Illegal or missing delimiter. */
#define NO_SAVED	41       /* No remembered search string. */
#define BAD_LEFTP	42       /* "\( \)" imbalance. */
#define BAD_RIGHTP	43       /* Too many "\(". */
#define EX_COMMA	44       /* More than two numbers given in \{ \}. */
#define NO_CLOSE	45       /* "}" expected after "\". */
#define MAX_MIN		46       /* First number exceeds second in \{ \}. */
#define BAD_BRAK	49       /* "[ ]" imbalance. */
#define TOO_BIG		50       /* Regular expression overflow. */
#define STACK_EMPTY	51	/* backtrack stack empty */
#define STACK_FULL	52	/* backtrack stack full */
#define	BAD_CHAR	60	/* wierd multibyte char */


#ifndef STACK_MAX
#define STACK_MAX 512		/* intimately related to line length */
#endif

char *	_Stack [STACK_MAX];
int	_Stack_pointer;		/* pushes predecrement sp */
static	int CLOCALE;		/* see if the process is in the ascii locale */


#define ___pop() ((_Stack_pointer < STACK_MAX) ? _Stack[_Stack_pointer++] : (__ERROR(STACK_EMPTY),(char *)0))

char * __pop()
{
	return ___pop();
}

char *
__push(lineptr)
char * lineptr;
{
	if (--_Stack_pointer < 0)
		__ERROR(STACK_FULL);
	return (_Stack[_Stack_pointer] = lineptr);
}

char *
compile(instring, ep, endbuf, seof)
register char *ep;
char *instring, *endbuf;
{
	register mbchar_t c;
	register eof = seof;
	char *lastep = instring;
	char *cclcnt;
	char bracket[NBRA], *bracketp;
	int  i, cflg, closed;
	char class[16];		/* compare buffer for use in __classtab */
	int  classlen;		/* length of word in class[] */
	INIT			/* Dependent declarations and initializations */

	if (_CLOCALE)
		CLOCALE = 1;
	else
		CLOCALE = 0;

	if (i = _setjmp(__NLregexpErrbuf))
	{
		ERROR(i);
	}
	lastep = 0;
	if ((c = GETC()) == eof || c == '\n') {
		if (c == '\n') {
			UNGETC(c);
			nodelim = 1;
		}
		if (*ep == 0 && !sed)
			__ERROR(NO_SAVED);
		RETURN(ep);
	}
	bracketp = bracket;
	circf = closed = nbra = ebra = 0;
	if (c == '^')
		circf++;
	else
		UNGETC(c);
	WORDSUPPORT1
	while (1) {
		if (ep >= endbuf)
			__ERROR(TOO_BIG);
		c = GETC();
		if (c != '*' && ((c != '\\') || (PEEKC() != '{')))
			lastep = ep;
		if (c == eof) {
			WORDSUPPORT2
			*ep++ = CCEOF;
			RETURN(ep);
		}
		switch(c) {

		case ERR:
		    ERROR(BAD_CHAR);
		    /*NOTREACHED*/
		    break;

		case '.':
			*ep++ = CDOT;
			continue;

		case '\n':
			if (!sed) {
				UNGETC(c);
				*ep++ = CCEOF;
				nodelim = 1;
				RETURN(ep);
			}
			else __ERROR(BAD_DELIM);
		case '*':
			if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
				goto defchar;
			*lastep |= STAR;
			continue;

		case '$':
			if (PEEKC() != eof && PEEKC() != '\n')
				goto defchar;
			*ep++ = CDOL;
			continue;

		case '[':
			*ep++ = CCL;
			cclcnt = ep++;
			saveep = ep;
			if ((c = GETC()) == '^') {
				c = GETC();
				ep[-2] = NCCL;
			}
			do {
				if ((c == '\0') || (c == ERR))
				    __ERROR(BAD_BRAK);
				else if (c=='[') /* ugh! XPG3 crud */
				    switch(c = GETC()){
				    case ERR:
					    __ERROR(BAD_BRAK);
					    /*NOTREACHED*/

				    case ':':/* ctype-ish character class */
					for (classlen=0;classlen < sizeof(class);)
					{
						if (']' == (c = class[classlen++] = GETC()))
							break;
						if (!c)
							__ERROR(BAD_BRAK);
						if (seof == c)
							__ERROR(BAD_BRAK);
					}
					class[classlen] = '\0';
					for (i=0; __classtab[i].name; i++)
					    if (!strncmp(class,__classtab[i].name,__classtab[i].length)) {
						    *ep++ = CHCL;
						    *ep++ = __classtab[i].ctype>>8;
						    *ep++ = __classtab[i].ctype&0xff;
						    break;
						    }
					    if (!__classtab[i].name)
						__ERROR(BAD_BRAK);
					continue;

				    case '=':/* equivalence class */
					    c = GETC();
					    if ((ERR == c) || ('\0' == c))
						    __ERROR(BAD_BRAK);
					    *ep++ = CEQV;
					    if (CLOCALE)
						*ep++ = c;
					    else
					        ep = __PUTC(ep, c);
					    /* eat the rest of the expression */
					    if (GETC() != '=')
						    __ERROR(BAD_BRAK);
					    if (GETC() != ']')
						    __ERROR(BAD_BRAK);
					    continue;

				    case '.':/* extended collation character */
					    *ep++ = CCOL;
					    while ('.' != (c=GETC())) {
						    if ((ERR==c) || ('\0'==c))
							__ERROR(BAD_BRAK);
					    	    if (CLOCALE)
							*ep++ = c;
					    	    else
					        	ep = __PUTC(ep, c);
					    }
					    if (']' != GETC())
						    __ERROR(BAD_BRAK);
					    *ep++ = CCOLF;	/* follower */
					    continue;

				    default:
					/* The [ was just a normal character  */
					/* We really need 2 characters of     */
					/* lookahead here, since we need to   */
					/* see the [ and the following char   */
					/* before we know if this is an XPRG3 */
					/* special jobber.  We get by with    */
					/* one character of pushback and the  */
					/* fact that the only character we    */
					/* could have seen before the pushed  */
					/* back one is a left bracket.        */

					    UNGETC(c);
					    c='[';
					    /*FALLTHROUGH*/
				    }
				if ((c == '-') && (ep > cclcnt+1) && 
				    (PEEKC()!=']'))
				{
					register char * p;
					for (p = ep; p >= saveep; p--)
						p[1] = p[0];
					*saveep = MINUS;
					ep++;	/* we added one byte */
					continue;
				}
				saveep = ep;	/* need this to retract ep */
				*ep++ = CCHR;
				if (CLOCALE)
					*ep++ = c;
				else
					ep = __PUTC(ep, c);
			} while ((c = GETC()) != ']');
			if ((ep - cclcnt) > 255)
				__ERROR(TOO_BIG);
			else
				*cclcnt = ep - cclcnt;
			continue;

		case '\\':
			switch(c = GETC()) {

			case '(':
				if (nbra >= NBRA)
					__ERROR(BAD_RIGHTP);
				*bracketp++ = nbra;
				*ep++ = CBRA;
				*ep++ = nbra++;
				continue;

			case ')':
				if (bracketp <= bracket || ++ebra != nbra)
					__ERROR(BAD_LEFTP);
				*ep++ = CKET;
				*ep++ = *--bracketp;
				closed++;
				continue;

			case '{':
				if (lastep == (char *) 0)
					goto defchar;
				*lastep |= RNGE;
				cflg = 0;
			nlim:
				c = GETC();
				i = 0;
				do {
					if('0' <= c && c <= '9')
						i = 10 * i + c - '0';
					else
						__ERROR(BAD_NUM);
				} while (((c = GETC()) != '\\') && (c != ','));
				if (i > 255)
					__ERROR(BIG_RANGE);
				*ep++ = i;
				if (c == ',') {
					if (cflg++)
						__ERROR(EX_COMMA);
					if ((c = GETC()) == '\\')
						*ep++ = 255;
					else {
						UNGETC(c);
						goto nlim;
						/* get 2'nd number */
					}
				}
				if (GETC() != '}')
					__ERROR(NO_CLOSE);
				if (!cflg)	/* one number */
					*ep++ = i;
				else if ((ep[-1] & 0377) < (ep[-2] & 0377))
					__ERROR(MAX_MIN);
				continue;

			case '\n':
				__ERROR(BAD_DELIM);

			case 'n':
				c = '\n';
				goto defchar;

			default:
				if (c >= '1' && c <= '9') {
					if ((c -= '1') >= closed)
						__ERROR(BAD_BACK);
					*ep++ = CBACK;
					if (CLOCALE)
						*ep++ = c;
					else 
						ep = __PUTC(ep,c);
					continue;
				}
			}
	/* Drop through to default to use \ to turn off special chars */

		defchar:
		default:
			lastep = ep;
			*ep++ = CCHR;
			if (CLOCALE)
				*ep++ = c;
			else
				ep = __PUTC(ep, c);
		}
	}
}

int __advanceerrno;
advance(lp, ep)
register char *lp, *ep;
{
	int err;
	__advanceerrno = 0;
	if (err = _setjmp(__NLregexpErrbuf))
	{
		char errbuf[128];
		__advanceerrno = err;
		return(0);
	}
	_Stack_pointer = STACK_MAX;
	return(__advance(lp,ep));
}

int __steperrno;
step(p1, p2)
register char *p1, *p2;
{
	register int c;
	mbchar_t p1_peekc, p2_peekc;
	short p1_len, p2_len;
	int err;

	__steperrno = 0;
	if (err = _setjmp(__NLregexpErrbuf))
	{
		char errbuf[128];
		__steperrno = err;
		return(0);
	}
	_Stack_pointer = STACK_MAX;
	if (circf) {
		loc1 = p1;
		return(__advance(p1, p2));
	}

	/* fast check for first character */
	if (CLOCALE)
	{
		if (*p2 == CCHR)
		{
			c = *(p2+1);
			do {
			    if (c == *p1) {
		    	    	if (__advance(p1, p2)) {
			        	loc1 = p1;
			        	return(1);
			    	}	
			    }
			} while (*p1++);
			return(0);
		}
		/* regular algorithm */
		do {
			if (__advance(p1, p2)) {
				loc1 = p1;
				return(1);
			}
		} while (*p1++);
		return(0);
	} else {
		if (__PEEKC(p2) == CCHR) 
		{
			char *savep2 = p2;
			(void)__GETC(p2);
			c = __PEEKC(p2);
			p2 = savep2;
			do {
			    if (c == __PEEKC(p1)) 
			    {
		    	    	if (__advance(p1, p2)) {
			    		loc1 = p1;
			    		return(1);
		    	    	}
			    }
			} while(__GETC(p1));
			return(0);
		}
		/* regular algorithm */
		do {
			if (__advance(p1, p2)) {
				loc1 = p1;
				return(1);
			}
		} while (__GETC(p1));
		return(0);
	}
}

__advance(lp, ep)
register char *lp, *ep;
{
	register char *curlp;
	register int c;
	char *bbeg;
	int  ct, c2;

	while(1) {
		switch(*ep++) {

		case CCHR:
			if (CLOCALE) {
			    if (*ep++ == *lp++)
				continue;
			} else {
			    c = __GETC(ep);
			    if (c == __GETC(lp))
				continue;
			}
			return(0);
	
		case CDOT:
			if (CLOCALE) {
			    if (*lp++ == 0)
				return(0);
			} else {
			    if (!__GETC(lp))
				return(0);
			}
			continue;
	
		case CDOL:
			if (*lp == 0)
				continue;
			return(0);

		case CCEOF:
			loc2 = lp;
			return(1);

		case NCCL:
		case CCL:
			if (!ISTHERE(c, lp, &c2))
				return(0);
			lp += c2;
			ep += *ep;
			continue;

		case CBRA:
			braslist[*ep++] = lp;
			continue;
	
		case CKET:
			braelist[*ep++] = lp;
			continue;
	
		case CCHR | RNGE:
			if (CLOCALE)
			{
			    c = *ep++;
			    getrnge(ep);
			    while (low--) {
				if (c != *lp++)
					return(0);
			    }
			    curlp = lp;
			    while (size-- && c == *lp)
			    {
			        __push(lp);
			        ++lp;
			    }
			} else {
			    c = __GETC(ep);
			    getrnge(ep);
			    while (low--) {
				if(__GETC(lp) != c)
					return(0);
			    }
			    curlp = lp;
			    while (size-- && c == __PEEKC(lp))
			    {
			        __push(lp);
			        __GETC(lp);
			    }
			}
			ep += 2;
			goto star;
	
		case CDOT | RNGE:
			getrnge(ep);
			if (CLOCALE) {
			    while (low--) {
				if (*lp++ == 0)
				    return(0);
			    }
			    curlp = lp;
			    while (size-- && *lp)
			    {
				__push(lp);
				++lp;
			    }
			} else {
			    while (low--) {
				if (!__GETC(lp))
				    return(0);
			    }
			    curlp = lp;
			    while (size-- && __PEEKC(lp))
			    {
				__push(lp);
				__GETC(lp);
			    }
			}
			ep += 2;
			goto star;
	
		case NCCL | RNGE:
		case CCL | RNGE:
			getrnge(ep + *ep);
			while (low--) {
				if (!ISTHERE(c, lp, &c2))
					return(0);
				lp += c2;
			}
			curlp = lp;
			while (size-- && ISTHERE(c, lp, &c2))
			{
				__push(lp);
				lp += c2;
			} 
			ep += *ep+2;
			goto star;
	
		case CBACK:
			bbeg = braslist[*ep];
			ct = braelist[*ep++] - bbeg;
	
			if (ecmp(bbeg, lp, ct)) {
				lp += ct;
				continue;
			}
			return(0);
	
		case CBACK | STAR:
			bbeg = braslist[*ep];
			ct = braelist[*ep++] - bbeg;
			curlp = lp;
			while (ecmp(bbeg, lp, ct))
				lp += ct;
	
			while (lp >= curlp) {
				if (__advance(lp, ep))
					return(1);
				lp -= ct;
			}
			return(0);
	
	
		case CDOT | STAR:
			curlp = lp;
			if (CLOCALE) {
			    while (*lp) {
				__push(lp);
				++lp;
			    }
			} else {
			    while (__PEEKC(lp)) {
				__push(lp);
				(void) __GETC(lp);
			    }
			}
			goto star;
	
		case CCHR | STAR:
			curlp = lp;
			if (CLOCALE) {
			    c = *ep++;
			    while (c == *lp)
			    {
				__push(lp);
				++lp;
			    }
			} else {
			    c = __GETC(ep);
			    while (c == __PEEKC(lp))
			    {
				__push(lp);
				(void) __GETC(lp);
			    }
			}
			goto star;
	
		case NCCL | STAR:
		case CCL | STAR:
			curlp = lp;
			while (ISTHERE(c, lp, &c2))
			{
				__push(lp);
				lp += c2;
			}
			ep += *ep;
			goto star;
	
		star:
			while ((lp != locs) || (*ep && *ep!=CCEOF)) {
				if (__advance(lp, ep))
					return(1);
				if (lp <= curlp)
					return(0);
				lp = __pop();
			}
			return(0);
		ADV_CASE

		}
	}
}

getrnge(str)
register char *str;
{
	low = *str++ & 0377;
	size = (*str == 255) ? 20000: (*str & 0377) - low;
}

ecmp(a, b, count)
register char	*a, *b;
register	count;
{
	while (count--)
		if (*a++ != *b++)
			return(0);
	return(1);
}

/* NOTE: this code is a hacked/lifted from libPW/regex.c */
/*
** here are the things we can see between square brackets:
**   CIRCFL  - only as the first character, and negates the result of a match
**
**   CCHR (a character)
**   CCOL (a whole bunch of characters) CCOLF
**   CEQV (a character)
**   CHCL (msb of the ctype mask) (lsb of the ctype mask)
**   MINUS  (any of the above) (any of the above)
**
** an equivalence class ([=x=]) at either end of a range matches any of
** the characters in that class.  For example "[[=A=]-C]" matches any of
** the A's in the current collating sequence with any combination of 
** diacriticals, or anything in the collating sequence between those A's
** and the character C.  This probably doesn't mean much for Kanji, 
** cest la vie.
**
** The original code automatically matched a range with all the characters
** between the *equivalence classes* containing the characters at the ends
** of the range.  This is forbidden by XPG3.  Therefore, we only match 
** equiv. classes if the user asks for them.
** 
*/

static int
cclass(set, stream, stream_wid)
char *set;		/* pointer to the [...] set */
char *stream;		/* the stream of test characters */
int *stream_wid;	/* returns the width of the test character */
{
	register int stream_col;/* collation weight of the character */
	register char *end;	/* last character of range */
	int f;			/* return value of "match" */
	wchar_t tmp_wc;		/* misc wide char */
	int range_start=0; 	/* start of range for eqvmap's & ranges */
	int range_end=0; 	/* end of range for eqvmap's & ranges */
	int len;		/* misc length */
	int colval;		/* misc. collation weight */
	wchar_t *ignored;	/* (ignored) pointer to 1-to-n text */
	short mask;		/* CHCL mask built from the compiled expr */
	wchar_t stream_wc;	/* wide char of the character */
	char *stream_beg;	/* beginning of the stream */

	if (*stream == 0)
		return(0);
	stream_beg = stream;	/* so we can count the width */

	if (CLOCALE)
		stream_wc  = stream_col = *stream++;
	else {
		if ((len = _mbtowc(&stream_wc, stream, MB_CUR_MAX)) < 0)
	    		__ERROR(BAD_CHAR);
		if ((stream_col = wc_collate(stream_wc)) < 0)
		{
	    	    if ((stream_col = _mbxcol(stream_col,(unsigned char **)&stream,&ignored)) < 0)
		        __ERROR(BAD_CHAR);  /* 1-to-n map, no can do (yet) */
		} else
			stream += len;
	}

	f = (set[-1] & ~(STAR | RNGE)) == CCL;
	end = set + *set++ - 1; 	/* *set points to byte after range */
	*stream_wid = stream - stream_beg;

	while (set < end) {	/* match stream_col with anything in set */
	    switch (*set++) {
	    case MINUS: {	/* brackets for vi % */

		/* get range start */
		switch (*set++) {

		case CEQV:
		    if (CLOCALE)
		        range_start = *set++;
		    else {
		        if ((len = _mbtowc(&tmp_wc,set,MB_CUR_MAX)) < 0)
			    __ERROR(BAD_CHAR);
		        set += len;
		        range_start = wc_coluniq(tmp_wc);
		        while (wc_eqvmap(range_start) == 0)
			    range_start--;
		    }
		    break;

		case CCOL:
		    if (CLOCALE)
		        range_start = *set++;
		    else {
		        if ((len = _mbtowc(&tmp_wc,set,MB_CUR_MAX)) < 0)
			    __ERROR(BAD_CHAR);
		        if ((colval = wc_collate(tmp_wc)) < 0)
		        {
			    if ((range_start = _mbxcol(colval, (unsigned char **)&set, &ignored)) < 0)
			        __ERROR(BAD_CHAR);  /* 1-to-n map, no can do (yet) */
			    if (*set++ != CCOLF)
			        __ERROR(BAD_CHAR);  /* improper collation sym */
		        }
		        else {
			    /* the collation object was a single character */
			    range_start = colval;
			    set += len;
		        }
		    }
		    continue;

		case CCHR:
		    if (CLOCALE)
			range_start = *set++;
		    else {
		        if ((len = _mbtowc(&tmp_wc, set, MB_CUR_MAX)) < 0)
			    __ERROR(BAD_CHAR);
		        if ((colval = wc_collate(tmp_wc)) < 0)
		        {
			    if ((range_start = _mbxcol(colval, (unsigned char **)&set, &ignored)) < 0)
			        __ERROR(BAD_CHAR);  /* 1-to-n map, no can do (yet) */
		        }
		        else {
			/* the collation object was a single character */
			    set += len;
			    range_start = colval;
			}
		    }
		    break;

		default:
		    __ERROR(BAD_CHAR);	/* no ctypes in ranges */
		    /*NOTREACHED*/
		    break;
		}

		/* get range end */
		switch (*set++) {

		case CEQV:
		    if (CLOCALE)
			range_end = *set++;
		    else {
		        if ((len = _mbtowc(&tmp_wc, set, MB_CUR_MAX)) < 0)
			    __ERROR(BAD_CHAR);
		        set += len;
		        range_end = wc_coluniq(tmp_wc);
		        while (wc_eqvmap(range_end+1) == 0)
			    range_end++;
		    }
		    break;

		case CCOL:
		    if (CLOCALE)
		        range_end = *set++;
		    else {
		        if ((len = _mbtowc(&tmp_wc, set, MB_CUR_MAX)) < 0)
			    __ERROR(BAD_CHAR);
		        if ((colval = wc_collate(tmp_wc)) < 0)
		        {
			    if ((range_end = _mbxcol(colval, (unsigned char **)&set, &ignored)) < 0)
			        __ERROR(BAD_CHAR);  /* 1-to-n map, no can do (yet) */
			    if (*set++ != CCOLF)
			        __ERROR(BAD_CHAR);  /* improper collation sym */
		        }
		        else
		        {
			    /* the collation object was a single character */
			    range_end = colval;
			    set += len;
		        }
		    }
		    continue;

		case CCHR:
		    if (CLOCALE)
		        range_end = *set++;
		    else {
		        if ((len = _mbtowc(&tmp_wc, set, MB_CUR_MAX)) == -1)
			    __ERROR(BAD_CHAR);
		        if ((colval = wc_collate(tmp_wc)) < 0)
		        {
			    if ((range_end = _mbxcol(colval, (unsigned char **)&set, &ignored)) < 0)
			        __ERROR(BAD_CHAR);	/* 1-to-n map, no can do (yet) */
		        }
		        else {
			    /* the collation object was a single character */
			    set += len;
			    range_end = colval;
		        }
		    }
		    break;

		default:
		    __ERROR(BAD_CHAR);	/* no ctypes in ranges */
		    /*NOTREACHED*/
		    break;
		}

		if (range_end - range_start < 0)
			return 0;	/* [b-a] & [^b-a] both match nothing */
		if (range_start <= stream_col && stream_col <= range_end)
			return f;
		break;
		}

	case CEQV:
	    if (CLOCALE)
	        range_start = range_end = *set++;
	    else {
	        if ((len = _mbtowc(&tmp_wc,set,MB_CUR_MAX)) < 0)
		    __ERROR(BAD_CHAR);
	        set += len;
	        range_start = range_end = wc_coluniq(tmp_wc);
	    }
	    while (wc_eqvmap(range_end+1) == 0)
		range_end++;
	    while (wc_eqvmap(range_start) == 0)
		range_start--;
	    if (range_start <= stream_col && stream_col <= range_end)
		    return f;
	    break;

	case CCOL:
	    if (CLOCALE)
	        range_end = *set++;
	    else {
	        if ((len = _mbtowc(&tmp_wc, set, MB_CUR_MAX)) < 0)
		    __ERROR(BAD_CHAR);
	        if ((colval = wc_collate(tmp_wc)) < 0)
	        {
		    if ((range_end = _mbxcol(colval, (unsigned char **)&set, &ignored)) < 0)
		        __ERROR(BAD_CHAR);  /* 1-to-n map, no can do (yet)*/
		    if (*set++ != CCOLF)
		        __ERROR(BAD_CHAR);  /* improper collation sym */
	    	}
	        else {
		    /* the collation object was a single character */
		    range_end = colval;
		    set += len;
		}
	    }
	    if (range_end == stream_col)
		return f;
	    break;

	case CHCL:
	    mask = (*set++ << 8);	/* cc@/i370 screws up the eval order */
	    mask |= *set++;
	    if (mask & _CTYPE[__wcindx(stream_wc)+1])
		return f;
	    break;
	
	case CCHR:
	    if (CLOCALE) {
	        range_end = *set;
	        if (stream_col == range_end)
		    return f;
		++set;
	    } else {
	        if ((len = _mbtowc(&tmp_wc, set, MB_CUR_MAX)) == -1)
		    __ERROR(BAD_CHAR);
	        range_end = wc_collate(tmp_wc);
	        if (stream_col == range_end)
		    return f;
		set += len;
	    }
	    break;

	default:
	    __ERROR(BAD_CHAR);	/* bogus character in range */
	    /*NOTREACHED*/
	    break;
	}
    }
    return (!f);
}

#else  /* _MBCS not defined ==> 1.2 header */

/* Bit tables for ranges have increased from 16 bytes to 96 bytes! */
/* Callers beware: the value (endbuf-ep) better be enlarged...     */
#include <NLchar.h>

#ifndef	WORDSUPPORT1
#define	WORDSUPPORT1 
#endif	
#ifndef	WORDSUPPORT2
#define	WORDSUPPORT2 
#endif	
#ifndef	ADV_CASE
#define	ADV_CASE 
#endif	

#define RANGEMAX (NLCHARMAX/8+1)

#define	CBRA	2
#define	CCHR	4
#define	CDOT	8
#define	CCL	12
#define	CDOL	20
#define	CCEOF	22
#define	CKET	24
#define	CBACK	36

#define	STAR	01
#define RNGE	03

#define	NBRA	9

#define PLACE(c)	ep[c >> 3] |= bittab[c & 07]
#define ISTHERE(c, lp, c2)	(c2 = _NCdec2(lp[0],lp[1],c),\
				c = NCcoluniq(c),\
				(ep[c >> 3] & bittab[c & 07]) != 0)

char	*braslist[NBRA];
char	*braelist[NBRA];
char	*loc1, *loc2, *locs;
char	bittab[] = { 1, 2, 4, 8, 16, 32, 64, 128 };

int     sed, nbra;
int	ebra;
int	nodelim;
int	circf;
int	low;
int	size;

char *
compile(instring, ep, endbuf, seof)
register char *ep;
char *instring, *endbuf;
{
	INIT	/* Dependent declarations and initializations */
	register c;
	register eof = seof;
	char *lastep = instring;
	int cclcnt;
	char bracket[NBRA], *bracketp;
	int closed;
	char neg;
	int lc;
	int i, cflg;

	lastep = 0;
	if((c = GETC()) == eof || c == '\n') {
		if(c == '\n') {
			UNGETC(c);
			nodelim = 1;
		}
		if(*ep == 0 && !sed)
			ERROR(41);
		RETURN(ep);
	}
	bracketp = bracket;
	circf = closed = nbra = ebra = 0;
	if(c == '^')
		circf++;
	else
		UNGETC(c);
	WORDSUPPORT1
	while(1) {
		if(ep >= endbuf)
			ERROR(50);
		c = GETC();
		if(c != '*' && ((c != '\\') || (PEEKC() != '{')))
			lastep = ep;
		if(c == eof) {
			WORDSUPPORT2
			*ep++ = CCEOF;
			RETURN(ep);
		}
		switch(c) {

		case '.':
			*ep++ = CDOT;
			continue;

		case '\n':
			if(!sed) {
				UNGETC(c);
				*ep++ = CCEOF;
				nodelim = 1;
				RETURN(ep);
			}
			else ERROR(36);
		case '*':
			if(lastep == 0 || *lastep == CBRA || *lastep == CKET)
				goto defchar;
			*lastep |= STAR;
			continue;

		case '$':
			if(PEEKC() != eof && PEEKC() != '\n')
				goto defchar;
			*ep++ = CDOL;
			continue;

		case '[':
			if(&ep[RANGEMAX+1] >= endbuf)
				ERROR(50);

			*ep++ = CCL;
			lc = 0;
			for(i = 0; i < RANGEMAX; i++)
				ep[i] = 0;

			neg = 0;
			if((c = GETC()) == '^') {
				neg = 1;
				c = GETC();
			}

			do {
				if(c == '\0' || c == '\n')
					ERROR(49);
				if(c == '-' && lc != 0) {
					if((c = GETC()) == ']') {
						PLACE(NCcoluniq('-'));
						break;
					}
					i=GETC();
					if (_NCdec2(c,i,c)==1)
						UNGETC(i);
					c = NCcoluniq(c);
					while(NCeqvmap(lc)==0) lc--;
					while(NCeqvmap(c+1)==0) c++;
					while(lc < c) {
						PLACE(lc);
						lc++;
					}
				}
				else {
					i=GETC();
					if (_NCdec2(c,i,c)==1)
						UNGETC(i);
					c = NCcoluniq(c);
				}
				lc = c;
				PLACE(c);
			} while((c = GETC()) != ']');
			if(neg) {
				for(cclcnt = 0; cclcnt < RANGEMAX; cclcnt++)
					ep[cclcnt] ^= -1;
				ep[0] &= 0374;
			}

			ep += RANGEMAX;

			continue;

		case '\\':
			switch(c = GETC()) {

			case '(':
				if(nbra >= NBRA)
					ERROR(43);
				*bracketp++ = nbra;
				*ep++ = CBRA;
				*ep++ = nbra++;
				continue;

			case ')':
				if(bracketp <= bracket || ++ebra != nbra)
					ERROR(42);
				*ep++ = CKET;
				*ep++ = *--bracketp;
				closed++;
				continue;

			case '{':
				if(lastep == (char *) 0)
					goto defchar;
				*lastep |= RNGE;
				cflg = 0;
			nlim:
				c = GETC();
				i = 0;
				do {
					if('0' <= c && c <= '9')
						i = 10 * i + c - '0';
					else
						ERROR(16);
				} while(((c = GETC()) != '\\') && (c != ','));
				if(i > 255)
					ERROR(11);
				*ep++ = i;
				if(c == ',') {
					if(cflg++)
						ERROR(44);
					if((c = GETC()) == '\\')
						*ep++ = 255;
					else {
						UNGETC(c);
						goto nlim;
						/* get 2'nd number */
					}
				}
				if(GETC() != '}')
					ERROR(45);
				if(!cflg)	/* one number */
					*ep++ = i;
				else if((ep[-1] & 0377) < (ep[-2] & 0377))
					ERROR(46);
				continue;

			case '\n':
				ERROR(36);

			case 'n':
				c = '\n';
				goto defchar;

			default:
				if(c >= '1' && c <= '9') {
					if((c -= '1') >= closed)
						ERROR(25);
					*ep++ = CBACK;
					*ep++ = c;
					continue;
				}
			}
	/* Drop through to default to use \ to turn off special chars */

		defchar:
		default:
			lastep = ep;
			*ep++ = CCHR;
			*ep++ = c;
			if (NCisshift(c)) {
				 c = GETC();
				 if(c == eof || ep >= endbuf)
					 ERROR(50);
				 *ep++ = c;
			}
		}
	}
}

step(p1, p2)
register char *p1, *p2;
{
	register c;

	if(circf) {
		loc1 = p1;
		return(advance(p1, p2));
	}
	/* fast check for first character */
	if(*p2 == CCHR) {
		c = p2[1];
		do {
			if (*p1==c)
			if(advance(p1, p2)) {
				loc1 = p1;
				return(1);
			}
			if (NCisshift(*p1)) p1++;
		} while(*p1++);
		return(0);
	}
		/* regular algorithm */
	do {
		if(advance(p1, p2)) {
			loc1 = p1;
			return(1);
		}
		if (NCisshift(*p1)) p1++;
	} while(*p1++);
	return(0);
}


advance(lp, ep)
register char *lp, *ep;
{
	register char *curlp;
	register int c;
	int c2;
	char *bbeg;
	int ct;

	while(1) {
		switch(*ep++) {

		case CCHR:
			c = *ep++;
			if(c == *lp++)
				if (!NCisshift(c) || *ep++ == *lp++) continue;
			return(0);
	
		case CDOT:
			if (*lp==0)
				return(0);
			else if( NCisshift(*lp++) )
				lp++;
			continue;
	
		case CDOL:
			if(*lp == 0)
				continue;
			return(0);
	
		case CCEOF:
			loc2 = lp;
			return(1);
	
		case CCL:
			if (!ISTHERE(c, lp, c2)) return (0);
			lp += c2;
			ep += RANGEMAX;
			continue;

		case CBRA:
			braslist[*ep++] = lp;
			continue;
	
		case CKET:
			braelist[*ep++] = lp;
			continue;
	
		case CCHR | RNGE:
			c = *ep++;
			if (NCisshift(c)) {
				c2 = *ep++;
				getrnge(ep);
				while(low--) {
					if(*lp++ != c || *lp++ != c2)
						return(0);
				}
				curlp = lp;
				while (size-- && *lp == c && lp[1] == c2) lp += 2;
			} else {
				getrnge(ep);
				while(low--) {
					if(*lp++ != c)
						return(0);
				}
				curlp = lp;
				while (size-- && *lp == c) lp++;
			}
			ep += 2;
			goto star;
	
		case CDOT | RNGE:
			getrnge(ep);
			while(low--) {
				if (NCisshift(*lp)) lp++;
				if(*lp++ == '\0')
					return(0);
			}
			curlp = lp;
			while(size-- && *lp != '\0') {
				lp += (NCisshift(*lp) ? 2 : 1);
			}
			ep += 2;
			goto star;
	
		case CCL | RNGE:
			getrnge(ep + RANGEMAX);
			while(low--) {
				if (!ISTHERE(c, lp, c2)) return (0);
				lp += c2;
			}
			curlp = lp;
			while(size-- && ISTHERE(c, lp, c2)) lp += c2;
			ep += RANGEMAX+2;
			goto star;
	
		case CBACK:
			bbeg = braslist[*ep];
			ct = braelist[*ep++] - bbeg;
	
			if(ecmp(bbeg, lp, ct)) {
				lp += ct;
				continue;
			}
			return(0);
	
		case CBACK | STAR:
			bbeg = braslist[*ep];
			ct = braelist[*ep++] - bbeg;
			curlp = lp;
			while(ecmp(bbeg, lp, ct))
				lp += ct;
	
			while(lp >= curlp) {
				if(advance(lp, ep))	return(1);
				lp -= ct;
			}
			return(0);
	
	
		case CDOT | STAR:
			curlp = lp;
			while(*lp) lp++;
			goto star;
	
		case CCHR | STAR:
			curlp = lp;
			c = *ep++;
			if (NCisshift(c)){
				c2 =  *ep++; 
				while(*lp == c && lp[1] == c2) lp += 2;
			}else {
				while (*lp == c) lp++;
			}
			goto star;
	
		case CCL | STAR:
			curlp = lp;
			while (ISTHERE(c, lp, c2)) lp += c2;
			ep += RANGEMAX;
			goto star;
	
		star:
			while (lp != locs) {
				if (advance(lp, ep)) return (1);
				if (lp <= curlp) return (0);
				lp--;
				if (lp > curlp && NCisshift(lp[-1])) lp--;
			}
			return (0);
		ADV_CASE

		}
	}
}

getrnge(str)
register char *str;
{
	low = *str++ & 0377;
	size = (*str == 255)? 20000: (*str &0377) - low;
}

ecmp(a, b, count)
register char	*a, *b;
register	count;
{
	while(count--)
		if(*a++ != *b++)
			return(0);
	return(1);
}

#endif  /* _MBCS */
#ifdef __cplusplus
}
#endif
