Tag Archives: assembly-language

Preprocessor in Fifty Lines of SPITBOL

As part of the conversion of SPITBOl to generate gnu assembler (gas) instead of NASM format, I learned that the GAS assembler is less powerful than that of NASM. For example, in NASM I could
use ‘define’ to map a register name to ‘eax’ in 32-bit mode, or ‘rax’ in 64-bit mode.

No problemo … SPITBOL to the rescue.

Here is the simple preprocessor I wrote in about twenty minutes:

*	rename registers according to word size

	target = host(0)
	target break('_') . os "_" rem . ws

	prefix = (eq(ws,32) '%e', '%r')

	word = (eq(ws,32) 'dword','qword')
	defines = 'M_WORD ' word ' '
	defines = defines 'D_WORD' ' ' (eq(ws,32) '.long', '.quad') ' '

	define('a(ref)')			:(a.end)
						:(next)
a	ident(os,"osx")				:s(a.err)
	a = '[' ref ']' 			:(return)
a.end

	define('m(ref)')			:(m.end)
m	ident(os,"osx")				:s(m.err)
	m = (eq(ws,32) 'd', 'q') 'word ptr ' ref ']' :(return)
m.end

	rmap = table(20)

	s = 'XLsiXRdiXSspXTsiWAcxWBbxWCdxW0axIAbp'
rinit	s len(2) . min  len(2) . reg = 		:f(rdone)
	rmap[min] = reg				:(rinit)
rdone
	rpat =  'IA' | ('X' any('LRST')) | ('W' any('ABC0')) 

next
	line = input				:f(end)

aloop	line breakx('A') . first 'A(' bal . ref ')' rem . last = first a(ref) last	:s(mloop)
	defs = defines

dloop
	defs break(' ') . key ' ' break(' ') . val ' ' =	:f(mloop)
dloop.1	line key = val				:s(dloop.1)f(dloop)

mloop	line breakx('M') . first 'M(' bal . ref ')' rem . last = first m(ref) last	:s(mloop)

rloop 	line rpat . reg = prefix rmap[reg]	:s(rloop)
	output = line				:(next)
err	output = 'error '
end

SPITBOL Status Report: NASM to GAS conversion complete

The conversion of asm.spt to generate gnu assembler (gas) code instead of nasm format is complete.

For those who know of such matters, I now generate att syntax, as it’s easier to generate from a program than intel syntax.

A few hours ago I finally got a compile with no errors, so I could run the executable.

It’s still dying early on. The good news is that with the use of gas I can now use ‘-g’ for debugging and get useful information from the ‘ddd’ debugger.

Simply put, I have debugging resources at hand that should suffice, so it’s just a matter of slogging along until its done. I don’t think it’ll take that long.

If you want to follow the details, or track my work, checkout branch ‘gas’.

I’ll keep you posted.

Version 15.01 of Spitbol Now Available: Supports 64-bit Unix.

This version adds support for x86-64, so that both 32-bit and 64-bit versions of Spitbol are now available.

Downloads in the traditional form are no longer directly supported, since both “Google Code” and “Github” no longer provide downloads built by the project.

Spitbol is now available only from its home at github.com/hardbol/spitbol.

If you wish to use git to work with the probject, use:

$ git clone http://github.com/hardbol/spitbol

If you just want to use the system, then select “Download ZIP” from the project home page, and extract the files from that.

The binaries for 32-bit and 64-bit versions can be found in ./bin/spitbol.m32 and ./bin/spitbol.m64, respectively.

This 64-bit version is built by default, as 32-bit processors are no longer widely used.

Three tools are needed to build Spitbol:

  1. A C compiler
  2. A C runtime library
  3. An assembler

Previous versions used gcc and glibc for the compiler and runtime support, and the nasm assembler.

This version uses tcc for the compiler, musl for the runtime support, and continues the use of nasm.

The make file makefile now uses tcc and musl to build (only) the 64-bit version. To build the 32-bit version and/or to use gcc, use makefile.gcc.

This version rescinds the support for Unicode added in version 13.05. (This caused enough problems that it was deemed best to abandon this experiment.)

Known problems:

  • The SAVE function doesn’t work. (This loss of function occurred whilst adding 64-bit support).
    Note that SAVE mode was mainly of interest back in the day when Spitbol was proprietary,
    so that one could distribute a program written in Spitbol without having to disclose the source.

Introduction to the Macro SPITBOL MINIMAL Reference Manual

The source code for MACRO SPITBOL contains extensive documentation. I have extracted the specification of the MINIMAL (Machine Independent Macro Assembly Language) and the specification of the OSINT (Operatint System INterface) and converted the plain text to HTML, resulting in what is now the “MINIMAL Reference Manual.

As part of this effort I wrote an introduction in order to give a sense of the flavor of the code. Here is that introduction:

Introduction

The implementation of MACRO SPITBOL is written in three languages: MINIMAL, C, and assembler.

The SPITBOL compiler and runtime is written in MINIMAL, a machine-independent portable assembly language.

The runtime is augmented by procedures written in C that collectively comprise OSINT (Operating System INTerface). These procedures provides such functions as input and output, system initialization and termination, management of UNIX pipes, the loading of external functions, the writing and reading of save files and load modules, and so forth.

The implementation also includes assembly code. This size of this code varies according to the target machine. About 1500 lines are needed for the x86 architecture running UNIX.

This code provides such functions as macros that define the translation of MINIMAL instructions that take more than a few machine-level instructions, support for calling C procedures from MINIMAL, for calling MINIMAL procedures from C, for creating save files and load modules, and for resuming execution from save files or load modules.

To give some idea of the flavor of the code, consider the following simple SPITBOL program that copies standard input to standard output.

loop output = input :s(loop)
end

By default, the variable input is input-associated to standard input, so each attempt to get its value results in reading in a line from standard input and returning the line as a string. The read fails if there are no more lines, and succeeds otherwise.

Similarly, the variable output is output-associated with standard output, so each assignment to output causes the assigned value to be written to the standard output file.

The osint procedure for writing a line is SYSOU. It is called from within SPITBOL as part of assignment, as shown in the follwing excerpt from the MINIMAL source:

*      here for output association

asg10  bze  kvoup,asg07      ignore output assoc if output off
asg1b  mov  xl,xr            copy trblk pointer
       mov  xr,trnxt(xr)     point to next trblk
       beq  (xr),=b_trt,asg1b loop back if another trblk
       mov  xr,xl            else point back to last trblk
.if    .cnbf
       mov  -(xs),trval(xr)  stack value to output
.else
       mov  xr,trval(xr)     get value to output
       beq  (xr),=b_bct,asg11 branch if buffer
       mov  -(xs),xr         stack value to output
.fi
       jsr  gtstg            convert to string
       ppm  asg12            get datatype name if unconvertible

*      merge with string or buffer to output in xr

asg11  mov  wa,trfpt(xl)     fcblk ptr
       bze  wa,asg13         jump if standard output file

*      here for output to file

asg1a  jsr  sysou            call system output routine
       err  206,output caused file overflow
       err  207,output caused non-recoverable error
       exi                   else all done, return to caller

From the OSINT C code (the C procedure name starts with ‘z’ since there is intermediate code (shown below) to call from MINIMAL to C at runtime):

zysou()
{
    REGISTER struct fcblk *fcb = WA(struct fcblk *);
    REGISTER union block *blk = XR(union block *);
    int result;

    if (blk->scb.typ == type_scl) {
	/* called with string, get length from SCBLK */
	SET_WA(blk->scb.len);
    } else {
	/* called with buffer, get length from BCBLK, and treat BSBLK
	 * like an SCBLK
	 */
	SET_WA(blk->bcb.len);
	SET_XR(blk->bcb.bcbuf);
    }

    if (fcb == (struct fcblk *) 0 || fcb == (struct fcblk *) 1) {
	if (!fcb)
	    result = zyspi();
	else
	    result = zyspr();
	if (result == EXI_0) 
	    return EXI_0;
	else 
	    return EXI_2;
    }

    /* ensure iob is open, fail if unsuccessful */
    if (!(MK_MP(fcb->iob, struct ioblk *)->flg1 & IO_OPN)) {
	 return EXI_1;
    }

    /* write the data, fail if unsuccessful */
    if (oswrite
	(fcb->mode, fcb->rsz, WA(word), MK_MP(fcb->iob, struct ioblk *),
	 XR(struct scblk *)) != 0)
	 return EXI_2;

    /* normal return */
    return EXI_0;
}

Here is the assembly code that is used to call a C procedure from MINIMAL. The code is for 32-bit X86
and is written using NASM (Netwide Assembler) syntax.

	%macro	mtoc	1
	extern	%1
	; save minimal registers to make their values available to called procedure
	mov     dword [reg_wa],ecx     
        mov     dword [reg_wb],ebx
        mov     dword [reg_wc],edx	; (also reg_ia)
        mov     dword [reg_xr],edi
        mov     dword [reg_xl],esi
        mov     dword [reg_cp],ebp	; Needed in image saved by sysxi
        call    %1			; call c interface function
;       restore minimal registers since called procedure  may have changed them
        mov     ecx, dword [reg_wa]	; restore registers
        mov     ebx, dword [reg_wb]
        mov     edx, dword [reg_wc]	; (also reg_ia)
        mov     edi, dword [reg_xr]
        mov     esi, dword [reg_xl]
        mov     ebp, dword [reg_cp]
;	restore direction flag in (the unlikely) case that it was changed
        cld
;	note that the called procedure must return exi action in eax
	ret
	%endmacro

  ...

	global	sysou			; output record
sysou:
	mtoc	zysou

Aggressive Assembly Language Programming in SPITBOL

The Preface to “Macro SPITBOL: The High-Performance SNOBOL4 Language,” by Mark B. Emmer and Edward K. Quillen, includes the following:

Robert Dewar created Macro SPITBOL in the mid 1970’s, and showed the world that a high-performance version of SNOBOL4 was possible. His Macro SPITBOL compiler forms the kernel of this implementation. As an example of “aggressive” assembly-language-programming, it remains a programs tour de force.

I was reminded of this when I came upon a comment by Mark in the source for Macro SPITBOL:

note: as an experiment, we tried aligning all ent and prc’s on a dword boundary, in an attempt to minimize instruction stall time on the first opcode of a procedure. the resultant exe file waslarger by 592 bytes, and actually ran 0.1% slower. we will continue to use odd alignment of block entry routines so that the .cepp conditional may be used.

592 bytes? 0.1% difference in performance?

Can you think of another programmer who pays this level of attention to performance?

Here is another:


* move chars from xl (esi) to xr (edi), count in wa (ecx)
*
* the following sequence "old method" is shorter than the "new method"
* shown below, but is much slower because of the conditional jumps that
* cause the instruction cache to be flushed for 3 out of 4 count values.
*
* old method:
* shr ecx,1
* jnc tmp1
* movsb ; move odd byte
* tmp1 shr ecx,1
* jnc tmp2
* movsw ; move odd word
* tmp2 rep movsd ; move string as double words
*
* genop('shr','ecx','1')
* genop('jnc','short ' (t1 = genlab()))
* genop('movsb')
* genopl(t1 label.delim,'shr','ecx','1')
* genop('jnc','short ' (t1 = genlab()))
* genop('movsw')
* genopl(t1 label.delim,'rep','movsd') :(opdone)
*
* new method:
* shrd eax,ecx,1 ; preserve ecx[0] in eax[31]
* shr ecx,2 ; preserve ecx[1] in cy, divide by 4
* rep movsd ; move dwords, leaves ecx=0
* adc ecx,ecx ; copy cy to ecx[0]
* rep movsw ; copy 1 or 0 words, leaves ecx=0
* shld ecx,eax,1 ; copy eax[31] to ecx[0]
* rep movsb ; copy 1 or 0 bytes

elel

Some knowledge — indeed more than I have — of programming for Intel’s x86 architecture is needed to fully appreciate the above, but the attention to detail is obvious.

Dewar’s MACRO SPITBOL was preceded by SPITBOL/360, written in IBM360 Assembly Language in the late 1960’s by Dewar and Ken Belcher. [1]

It must be the most efficient 360 assembly language program ever written. Robert once remarked that it was the only program known to him where the authors kept a copy of the instruction timing/cycle details for each model of the 360 in front of them as they wrote the code, and they frequently consulted these details to decide on best code sequence.

SPITBOL/360 demonstrated an astounding level of performance. SPITBOL/360 routinely compiled hundreds of thousands of lines of source code per second.

I once heard, perhaps from Robert himself, of one of the great tricks in SPITBOL/360.

SNOBOL has an integer variable &STLIMIT. A counter is initially set to this value. Whenever a new statement is executed, the counter is decremented, and if the value reaches zero then an exception is raised. This is used to avoid runaway loops and other code that would result in execution going on forever.

The obvious method is to use an integer counter, decrement it when a new statement is executed, and raise the exception when the value zero is reached.

Dewar and Belcher’s device was to maintain the counter as a floating-point (real) variable. It was set by computing a “magic” value and initializing the counter to that value. When a new statement was executed, the value 1.0 was added to the floating point counter. The magic was in that a floating-point exception, due to overflow of the value, would be raised at the appropriate time.

Andy Koenig — a fellow contributor to Macro SPITBOL — made mention of this device in his column Some Programs Are Poorly Designed On Purpose. The post includes several other examples from SPITBOL of what Andy calls “nefarious purposes” in the use of floating point arithmetic.

Another device, one of much greater generality, was the use of indirect threaded code (ITC), described in Dewar’s paper Indirect Threaded Code.

Most interpreters use a “switch on opcode” statement when a new statement is to be execute. However, this involves testing the value, and doing a switch instruction to the appropriate code, which tends to slow things down. Indeed this is one of the main costs of writing an interpreter instead of generating actual code for the target machine. After all, the hardware is designed to extract opcodes and take the appropriate execution as fast as it is possible.

When using ITC, the transition from one abstract instruction to the next is made not by a switch, but by doing an “indirect branch” to the address contained in the the code block for the next statement.

By the way, this is the reason you cannot write code in C to execute the Minimal assembly language level code in which SPITBOL is written. C has no such contruct (what is needed is something like goto *p).

By the way, Dewar is equally aggressive when it comes to documenting his code. See for example the source code for SPITBOL in file spitbol.min available at Github Hardbol SPITBOL. I consider it a tour de force in program documentation.

For example, while working together on the port of Macro SPITBOL to the IBM PC in the early 80’s, I remember particularly an instance where Dewar saved a file, and then immediately went back to edit the source when he noticed there was an extraneous space..

Notes:

1. SPITBOL/360 is available in open source form under the GPL license. See SPITBOL 360.

Dewar and Belcher applied their aggressive programing techniques in the early 80’s by writing a COBOL compiler in COBOL! The wikipedia entry for Robert Dewar includes:

In the 1970s Dewar was a principal author of the Realia COBOL compiler, widely used in commercial environments to this day (marketed by Computer Associates).

Written in COBOL, a remarkable feat in itself, I learned later from colleagues at IBM that Realia COBOL generated code that was better than that produced by IBM’s product COBOL compiler

  • Pages

  • March 2021
    M T W T F S S
    1234567
    891011121314
    15161718192021
    22232425262728
    293031  
  • RSS The Wayward Word Press

  • Recent Comments

    daveshields on SPITBOL for OSX is now av…
    Russ Urquhart on SPITBOL for OSX is now av…
    Sahana’s Respo… on A brief history of Sahana by S…
    Sahana’s Respo… on A brief history of Sahana by S…
    James Murray on On being the maintainer, sole…
  • Archives

  • Blog Stats

  • Top Posts

  • Top Rated

  • Recent Posts

  • Archives

  • Top Rated