Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.sys.apple2.programmer > #2602 > unrolled thread

Unix V6 : Sample C to 65c02 translation from 'sh'

Back to article view | Back to comp.sys.apple2.programmer

Contents

  Unix V6 : Sample C to 65c02 translation from 'sh' wssimms@gmail.com - 2016-03-28 21:32 -0700
    Re: Unix V6 : Sample C to 65c02 translation from 'sh' Benoit0123 <bgilon@free.fr> - 2016-03-29 12:56 +0000
      Re: Unix V6 : Sample C to 65c02 translation from 'sh' wssimms@gmail.com - 2016-03-29 06:56 -0700

#2602 — Unix V6 : Sample C to 65c02 translation from 'sh'

I've started working on translating the Unix V6 sh to 65c02 assembler.
This shell is called the Thompson shell because it was written by Ken
Thompson. It is less sophisticated than the Bourne Shell that was
included in 7th Edition Unix, but it's actually more complicated than
I thought because the last time I looked at shell source (about 9 months
ago), I was looking at the 1st Edition Unix shell.

The 6th Edition shell is written in C and includes a recursive descent
parser for the (very simple) command language it accepts. Here is one
of the parse functions. There is an array of pointers to char called
args[] that contains the tokens of the input line. The pointers p1 & p2
being passed into syn1, are pointers to the first and last+1 elements
of args[] that are to be parsed by this function (i.e, they delimit a
subrange of the tokenized input line)

The purpose of this function is to find expression delimiters in the
input line and build a list of parse subtrees of the expressions between
the delimiters. The result is a pointer to a tree node consisting of
four words: a type, flags, a pointer to a left subtree, and a pointer to
a right subtree. The chain of right-subtree links represents the list
of delimited expresssions.

The possible delimiters are ';', which results in sequential execution
of the subexpressions, and '&', which results in background execution
of the preceding subexpression. This should be pretty familiar to most
people. Here's the C code from 6th Edition Unix

/*
 * syn1
 *      syn2
 *      syn2 & syntax
 *      syn2 ; syntax
 */

syn1(p1, p2)
char **p1, **p2;
{
        register char **p;
        register *t, *t1;
        int l;

        l = 0;
        for(p=p1; p!=p2; p++)
        switch(**p) {

        case '(':
                l++;
                continue;

        case ')':
                l--;
                if(l < 0)
                        error++;
                continue;

        case '&':
        case ';':
        case '\n':
                if(l == 0) {
                        l = **p;
                        t = tree(4);
                        t[DTYP] = TLST;
                        t[DLEF] = syn2(p1, p);
                        t[DFLG] = 0;
                        if(l == '&') {
                                t1 = t[DLEF];
                                t1[DFLG] =| FAND|FPRS|FINT;
                        }
                        t[DRIT] = syntax(p+1, p2);
                        return(t);
                }
        }
        if(l == 0)
                return(syn2(p1, p2));
        error++;
}

Here's my translation into 65c02 code. It should be possible to compare
this code (and comments) to the above C code and figure out what's going
on, but a few tips might be helpful.

1. The total size of the args[] array is 100 bytes (even in the C version)
   so it is possible to avoid the use of pointers into the args[] array
   and use 8-bit indices instead.

2. The total size of the heap used to allocate parse tree nodes is 200
   bytes (even in the C version) so it is possible to avoid the use of
   pointers in the parse tree and use 8-bit indicies instead

3. The size of the allocated parse tree node is 4 words in the C version
   but only 4 bytes here, because 8-bit indicies are stored instead of
   pointers.

4. I have included a utility function called ddargix that deferences
   the currently indexed member of the args[] array to retrieve the first
   character of the indexed token. (This is equivalent to **p in the C
   code). It uses a zero-page pointer called 'dip'.

5. The code calls routines named pusha, popa, etc. which access a
   secondary stack implemented with a zero-page pointer at $FE. This
   location will be reserved for this use in Apple II Unix and the name
   'sp' is predefined in the system assembler to refer to this location.
   This stack can be used to pass arguments, save values across function
   calls, implement recursive algorithms, etc.

6. I usually handle local variables by using a statically allocated
   .bss location and then saving and restoring the value as necessary
   across function calls. The only non-register local variable in the
   following code is 'parcnt'. It is never saved however because it's
   value is no longer needed by the time the recursive calls are made.

7. register local variables are saved on the sp-stack when they need to
   be preserved across a recursive call, and on the regular 65c02 stack
   when they need to be preserved temporarily, but not across a recursive
   call.

8. global variables used are 'error', which flags the occurrence of a
   parse error and 'trebuf', which is the 200-byte heap for parse trees

9. recursive calls are made to the routines 'syntax', which is the top
   level parse routine, and 'syn2', which parses pipelines of the form
   E1 | E2 | ... | En

10. The assembler syntax is that of the Unix system assembler. local
    labels are specified as a digit 0-9 followed by a colon, and referred
    to by the digit followed by a 'b', meaning the preceding such label
    or an 'f', meaning the next such label, going out from the point of
    reference.

Lastly, this code has not been assembled or tested. So there just might
be errors. I've made several passes over it, but I rarely get everything
right before first assembly/test :-D.

//
// syn1
//	syn2
//	syn2 & syntax
//	syn2 ; syntax
//
// syn1 -- first level parsing
//    Take care of expressions separated by ; and & separators
//    When entering:
//       X: contains the index of the first token in the to-be-parsed
//          range of the args array (p1 in the C code)
//       Y: contains the index of the first token after the to-be-parsed
//          range of the args array (p2 in the C code)
//    In syn1:
//       X: is used advance through the args array (p in the C code)
//    Returns:
//       the parse tree (as an index into trebuf) of the passed-in
//       range of the args array
//
syn1:
	stx	8f+1		// store p1 for later use
	sty	9f+1		// store p2 for later use
	stz	parcnt		// clear the nesting depth
9:
	cpx	#0		// p1 == p2?	
	bcc	1f
	lda	parcnt		// if so, check nesting depth
	beq	8f
	inc	error		// if not zero, then error
	rts			// (returns garbage in A)
8:
	ldx	#0		// otherwise no '&' or ';' found
	ldy	9b+1		// reload p1 and p2 and parse again
	jmp	syn2		// with syn2

	// here p1 < p2 and we are considering each element of args
1:	
	jsr	ddargix		// get the first character of the token
	cmp	#'('
	bne	1f
	inc	parcnt		// if '(', increment nesting depth
	bra	2f		// advance to next arg
1:
	cmp	#')'
	bne	1f
	dec	parcnt		// if ')', decrement nesting depth
	bpl	2f
	inc	error		// error if nesting depth goes negative
2:
	inx
	inx			// advance to next arg
	bra	9b
1:
	cmp	#'&'
	beq	2f
	cmp	#';'
	beq	2f
	cmp	#'\n'
	bne	2b		// if not '&' ';' '\n' advance to next arg
2:
	lda	parcnt		// if nesting depth is nonzero
	bne	2b		// advance to next arg
	txa
	jsr	pusha		// save p across the recursive call
	jsr	ddargix		// get the token again ('&' ';' or '\n')
	jsr	pusha		// save it across the recursive call
	phx			// temporarily remember p
	lda	#4
	jsr	tree		// allocate 4 bytes
	jsr	pusha		// save the index across the recursive call
	tax			// get the tree index in X for indexing
	lda	#TLST
	sta	trebuf+DTYP,x	// the type of this tree node is TLST
	ldx	8b+1		// retrieve p1
	ply			// retrieve p
	jsr	syn2		// syn2(p1,p)
	jsr	popx		// retrieve the tree index
	sta	trebuf+DLEF,x	// store the index of the left subtree
	stz	trebuf+DFLG,x	// clear flags for this node
	jsr	popa		// retrieve the token
	cmp	#'&'		// was it '&' (nowait)?
	bne	2f
	phx			// if so, temporarily save tree index
	lda	trebuf+DLEF,x	// get index of left subtree
	tax
	lda	trebuf+DFLG,x	// set flags for left subtree
	ora	#FAND|FPRS|FINT	// nowait, print pid, background
	sta	trebuf+DFLG,x
	plx			// retrieve tree index
2:
	jsr	popa		// retrieve p
	jsr	pushx		// save tree index across recursive call
	ldy	9b+1		// retrieve p2
	inx
	jsr	syntax		// syntax(p+1,p2)
	jsr	popx		// retrieve tree index
	sta	t+DRIT,x	// store the index of the right subtree
	txa
	rts			// return the index of the parse tree
	
ddargix:
	lda	args,x
	sta	ddp
	lda	args+1,x
	sta	ddp+1
	lda	(ddp)
	rts

[toc] | [next] | [standalone]

#2603

wssimms wrote:
> I've started working on translating the Unix V6 sh to 65c02 assembler.
> This shell is called the Thompson shell because it was written by Ken
> Thompson. It is less sophisticated than the Bourne Shell that was
> included in 7th Edition Unix, but it's actually more complicated than
> I thought because the last time I looked at shell source (about 9 months
> ago), I was looking at the 1st Edition Unix shell.
> 
> The 6th Edition shell is written in C and includes a recursive descent
> parser for the (very simple) command language it accepts. Here is one
> of the parse functions. There is an array of pointers to char called
> args[] that contains the tokens of the input line. The pointers p1 & p2
> being passed into syn1, are pointers to the first and last+1 elements
> of args[] that are to be parsed by this function (i.e, they delimit a
> subrange of the tokenized input line)
> 
> The purpose of this function is to find expression delimiters in the
> input line and build a list of parse subtrees of the expressions between
> the delimiters. The result is a pointer to a tree node consisting of
> four words: a type, flags, a pointer to a left subtree, and a pointer to
> a right subtree. The chain of right-subtree links represents the list
> of delimited expresssions.
> 
> The possible delimiters are ';', which results in sequential execution
> of the subexpressions, and '&', which results in background execution
> of the preceding subexpression. This should be pretty familiar to most
> people. Here's the C code from 6th Edition Unix
> (snip)
a) Should the code extract below
2:	inx
	inx                        // advance to next arg
	bra        9b
1:	cmp        #'&'
	beq        2f
	cmp        #';'
	beq        2f
	cmp        #'\n'
	bne        2b                // if not '&' ';' '\n' advance to next arg
2:	lda        parcnt                // if nesting depth is nonzero
	bne        2b                // advance to next arg
read
2:	inx
	inx                        // advance to next arg
	bra        9b
1:	cmp        #'&'
	beq        1f
	cmp        #';'
	beq        1f
	cmp        #'\n'
	bne        2b                // if not '&' ';' '\n' advance to next arg
1:
	lda        parcnt                // if nesting depth is nonzero
	bne        2b                // advance to next arg
instead? otherwise there might be an infinite loop within the current
process?

b) Your code seems to use self modifying tricks (bytes at addresse 9:+1 and
8:+1), beware  if an interrupt occured after those addressed are updated but
before they are accessed again within the code. But I might be wrong if your
code is considered private and stored into a dedicated (i.e. not shared)
segment to the current process.


-- 
Growing old is mandatory..
growing up is optional..
But the other way round is as true.

[toc] | [prev] | [next] | [standalone]

#2604

On Tuesday, March 29, 2016 at 10:00:10 PM UTC+9, Benoit0123 wrote:
> a) Should the code extract below
> 2:	inx
> 	inx                        // advance to next arg
> 	bra        9b
> 1:	cmp        #'&'
> 	beq        2f
> 	cmp        #';'
> 	beq        2f
> 	cmp        #'\n'
> 	bne        2b                // if not '&' ';' '\n' advance to next arg
> 2:	lda        parcnt                // if nesting depth is nonzero
> 	bne        2b                // advance to next arg
> read
> 2:	inx
> 	inx                        // advance to next arg
> 	bra        9b
> 1:	cmp        #'&'
> 	beq        1f
> 	cmp        #';'
> 	beq        1f
> 	cmp        #'\n'
> 	bne        2b                // if not '&' ';' '\n' advance to next arg
> 1:
> 	lda        parcnt                // if nesting depth is nonzero
> 	bne        2b                // advance to next arg
> instead? otherwise there might be an infinite loop within the current
> process?

Yes you are correct. Good catch.

> b) Your code seems to use self modifying tricks (bytes at addresse 9:+1 and
> 8:+1), beware  if an interrupt occured after those addressed are updated but
> before they are accessed again within the code. But I might be wrong if your
> code is considered private and stored into a dedicated (i.e. not shared)
> segment to the current process.

You are correct that that would be a problem if the text segment  were shared.
At the moment I have not made a final decision about sharing the text segment.

The argument for it is that it saves memory and PDP-11 6th Edition Unix does it.

The arguments against it are that the memory saving is unlikely to be an issue on
Apple II Unix because there are unlikely to be many (if any) multiuser systems,
other than temporary "look what we can do woohoo!" setups, and since there
is no segmentation hardware there is no way to enforce the purity of the text
segment in any case.

Currently I'm leaning towards not having shared text segments. If that were to
change sometime in the future, the self-modifying code could either be
eliminated or, as in PDP-11 Unix, simply moved into the data segment.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.sys.apple2.programmer

csiph-web