int
do_subst(TARG,arg,sp)
STR *TARG;
ARG *arg;
int sp;
{
    register SPAT *spat;
    SPAT *rspat;
    register STR *dstr;
    register char *s = str_get(TARG);
    char *strend = s + TARG->str_cur;
    register char *m;
    char *c;
    register char *d;
    int clen;
    int iters = 0;
    int maxiters = (strend - s) + 10;
    register int i;
    bool once;
    char *orig;
    int safebase;

    rspat = spat = arg[2].arg_ptr.arg_spat;
    if (!spat || !s)
	fatal("panic: do_subst");
    else if (spat->spat_runtime) {
	nointrp = "|)";
	(void)eval(spat->spat_runtime,G_SCALAR,sp);
	m = str_get(dstr = stack->ary_array[sp+1]);
	nointrp = "";
	if (spat->spat_regexp) {
	    regfree(spat->spat_regexp);
	    spat->spat_regexp = Null(REGEXP*);	/* required if regcomp pukes */
	}
	spat->spat_regexp = regcomp(m,m+dstr->str_cur,
	    spat->spat_flags & SPAT_FOLD);
	if (spat->spat_flags & SPAT_KEEP) {
	    if (!(spat->spat_flags & SPAT_FOLD))
		scanconst(spat, m, dstr->str_cur);
	    arg_free(spat->spat_runtime);	/* it won't change, so */
	    spat->spat_runtime = Nullarg;	/* no point compiling again */
	    hoistmust(spat);
            if (curcmd->c_expr && (curcmd->c_flags & CF_OPTIMIZE) == CFT_EVAL) {
                curcmd->c_flags &= ~CF_OPTIMIZE;
                opt_arg(curcmd, 1, curcmd->c_type == C_EXPR);
            }
	}
    }
#ifdef DEBUGGING
    if (debug & 8) {
	deb("2.SPAT /%s/\n",spat->spat_regexp->precomp);
    }
#endif
    safebase = ((!spat->spat_regexp || !spat->spat_regexp->nparens) &&
      !sawampersand);
    if (!spat->spat_regexp->prelen && lastspat)
	spat = lastspat;
    orig = m = s;
    if (hint) {
	if (hint < s || hint > strend)
	    fatal("panic: hint in do_match");
	s = hint;
	hint = Nullch;
	if (spat->spat_regexp->regback >= 0) {
	    s -= spat->spat_regexp->regback;
	    if (s < m)
		s = m;
	}
	else
	    s = m;
    }
    else if (spat->spat_short) {
	if (spat->spat_flags & SPAT_SCANFIRST) {
	    if (TARG->str_pok & SP_STUDIED) {
		if (screamfirst[spat->spat_short->str_rare] < 0)
		    goto nope;
		else if (!(s = screaminstr(TARG,spat->spat_short)))
		    goto nope;
	    }
#ifndef lint
	    else if (!(s = fbminstr((unsigned char*)s, (unsigned char*)strend,
	      spat->spat_short)))
		goto nope;
#endif
	    if (s && spat->spat_regexp->regback >= 0) {
		++spat->spat_short->str_u.str_useful;
		s -= spat->spat_regexp->regback;
		if (s < m)
		    s = m;
	    }
	    else
		s = m;
	}
	else if (!multiline && (*spat->spat_short->str_ptr != *s ||
	  bcmp(spat->spat_short->str_ptr, s, spat->spat_slen) ))
	    goto nope;
	if (--spat->spat_short->str_u.str_useful < 0) {
	    str_free(spat->spat_short);
	    spat->spat_short = Nullstr;	/* opt is being useless */
	}
    }
    once = !(rspat->spat_flags & SPAT_GLOBAL);
    if (rspat->spat_flags & SPAT_CONST) {	/* known replacement string? */
	if ((rspat->spat_repl[1].arg_type & A_MASK) == A_SINGLE)
	    dstr = rspat->spat_repl[1].arg_ptr.arg_str;
	else {					/* constant over loop, anyway */
	    (void)eval(rspat->spat_repl,G_SCALAR,sp);
	    dstr = stack->ary_array[sp+1];
	}
	c = str_get(dstr);
	clen = dstr->str_cur;
	if (clen <= spat->spat_regexp->minlen) {
					/* can do inplace substitution */
	    if (regexec(spat->spat_regexp, s, strend, orig, 0,
	      TARG->str_pok & SP_STUDIED ? TARG : Nullstr, safebase)) {
		if (spat->spat_regexp->subbase) /* oops, no we can't */
		    goto long_way;
		d = s;
		lastspat = spat;
		TARG->str_pok = SP_VALID;	/* disable possible screamer */
		if (once) {
		    m = spat->spat_regexp->startp[0];
		    d = spat->spat_regexp->endp[0];
		    s = orig;
		    if (m - s > strend - d) {	/* faster to shorten from end */
			if (clen) {
			    Copy(c, m, clen, char);
			    m += clen;
			}
			i = strend - d;
			if (i > 0) {
			    Move(d, m, i, char);
			    m += i;
			}
			*m = '\0';
			TARG->str_cur = m - s;
			STABSET(TARG);
			str_numset(ARGTARG, 1.0);
			stack->ary_array[++sp] = ARGTARG;
			return sp;
		    }
		    /*SUPPRESS 560*/
		    else if (i = m - s) {	/* faster from front */
			d -= clen;
			m = d;
			str_chop(TARG,d-i);
			s += i;
			while (i--)
			    *--d = *--s;
			if (clen)
			    Copy(c, m, clen, char);
			STABSET(TARG);
			str_numset(ARGTARG, 1.0);
			stack->ary_array[++sp] = ARGTARG;
			return sp;
		    }
		    else if (clen) {
			d -= clen;
			str_chop(TARG,d);
			Copy(c,d,clen,char);
			STABSET(TARG);
			str_numset(ARGTARG, 1.0);
			stack->ary_array[++sp] = ARGTARG;
			return sp;
		    }
		    else {
			str_chop(TARG,d);
			STABSET(TARG);
			str_numset(ARGTARG, 1.0);
			stack->ary_array[++sp] = ARGTARG;
			return sp;
		    }
		    /* NOTREACHED */
		}
		do {
		    if (iters++ > maxiters)
			fatal("Substitution loop");
		    m = spat->spat_regexp->startp[0];
		    /*SUPPRESS 560*/
		    if (i = m - s) {
			if (s != d)
			    Move(s,d,i,char);
			d += i;
		    }
		    if (clen) {
			Copy(c,d,clen,char);
			d += clen;
		    }
		    s = spat->spat_regexp->endp[0];
		} while (regexec(spat->spat_regexp, s, strend, orig, s == m,
		    Nullstr, TRUE));	/* (don't match same null twice) */
		if (s != d) {
		    i = strend - s;
		    TARG->str_cur = d - TARG->str_ptr + i;
		    Move(s,d,i+1,char);		/* include the Null */
		}
		STABSET(TARG);
		str_numset(ARGTARG, (double)iters);
		stack->ary_array[++sp] = ARGTARG;
		return sp;
	    }
	    str_numset(ARGTARG, 0.0);
	    stack->ary_array[++sp] = ARGTARG;
	    return sp;
	}
    }
    else
	c = Nullch;
    if (regexec(spat->spat_regexp, s, strend, orig, 0,
      TARG->str_pok & SP_STUDIED ? TARG : Nullstr, safebase)) {
    long_way:
	dstr = Str_new(25,str_len(TARG));
	str_nset(dstr,m,s-m);
	if (spat->spat_regexp->subbase)
	    curspat = spat;
	lastspat = spat;
	do {
	    if (iters++ > maxiters)
		fatal("Substitution loop");
	    if (spat->spat_regexp->subbase
	      && spat->spat_regexp->subbase != orig) {
		m = s;
		s = orig;
		orig = spat->spat_regexp->subbase;
		s = orig + (m - s);
		strend = s + (strend - m);
	    }
	    m = spat->spat_regexp->startp[0];
	    str_ncat(dstr,s,m-s);
	    s = spat->spat_regexp->endp[0];
	    if (c) {
		if (clen)
		    str_ncat(dstr,c,clen);
	    }
	    else {
		char *mysubbase = spat->spat_regexp->subbase;

		spat->spat_regexp->subbase = Nullch;	/* so recursion works */
		(void)eval(rspat->spat_repl,G_SCALAR,sp);
		str_scat(dstr,stack->ary_array[sp+1]);
		if (spat->spat_regexp->subbase)
		    Safefree(spat->spat_regexp->subbase);
		spat->spat_regexp->subbase = mysubbase;
	    }
	    if (once)
		break;
	} while (regexec(spat->spat_regexp, s, strend, orig, s == m, Nullstr,
	    safebase));
	str_ncat(dstr,s,strend - s);
	str_replace(TARG,dstr);
	STABSET(TARG);
	str_numset(ARGTARG, (double)iters);
	stack->ary_array[++sp] = ARGTARG;
	return sp;
    }
    str_numset(ARGTARG, 0.0);
    stack->ary_array[++sp] = ARGTARG;
    return sp;

nope:
    ++spat->spat_short->str_u.str_useful;
    str_numset(ARGTARG, 0.0);
    stack->ary_array[++sp] = ARGTARG;
    return sp;
}
#ifdef BUGGY_MSC
 #pragma intrinsic(memcmp)
#endif /* BUGGY_MSC */