Writing SM/REM and FM/MOD

Julian Fondren

unread,

Apr 21, 2015, 4:23:09 PM4/21/15

to

Hello clf,

I have about a week's worth of spare-time learning of ARM assembly under my
belt. You can see some of the fruits of that at

http://minimaltype.com/13.txt
http://minimaltype.com/innerloops.txt

(13 preceded by 1.S, 2.S, 3.S, and so on, starting from hello world.)

Once I got to the level of 13.S, I started converting AvdH's yourforth from x86
to ARM. For the most part, despite my knowing almost nothing at all about x86
assembler, this has been a real pleasure. ARM assembler is really a joy to
work with, or at least I think so now after bashing my head against a few walls
early on. Especially ARM's stack words and conditional instructions are very
clean and flexible. The conversion to ARM assembly was also proceeding at a
pretty quick pace... until I hit the first word requiring division.

Which brings me to the subject of this post.

I can perform division with repeated subtraction (using subtract-with-carry to
divide a 64-bit dividend by a 32-bit divisor), but what do I do about negative
numbers? My education takes me as a far as, for ratios, "if they're both
negative, that cancels out - they are now both positive; if one is negative,
normalize the ratio so that only the numerator is negative; if the ratio is
reduced [i.e., if division is performed], the result has the sign of the
numerator." Which doesn't cover the sign of the remainder, which is apaprently
not the same thing as the modulus, which is apparently controversial.

Can someone clearly describe, or point me to a clear description, as to how one
*implements* floored division vs. symmetric division? Suppose I start out by
discarding signs and just repeatedly subtract numbers until I get a positive
quotient and remainder. What do i then do to satisfy callers expecting foored
or symmetric division? This has proven to be remarkably difficult to search
for. Wikipedia literally just says that things "break down" when negative
numbers are involved. yourforth just uses x86's idiv instruction. An ARM
jonesforth that I've found has a division routine, but out of excessive
unconcern for ANS compatibility it doesn't identify what kind of a routine it
is.

I'm aware that this manner of division is going to be dreadfully slow. For
known divisors I'll have a way to perform the division with multipication,
Otherwise this is fine for now.

And I feel compelled to add.. I'm not writing a Forth. I'm porting a Forth.
Starting with yourforth as it's small and commented well enough to make up for
my not knowing x86. I'm using gas as there's a convenient package of gcc for
Android, and as fasm doesn't seem to actually have arm binaries.

Thanks,
-- Julian

Mark Wills

unread,

Apr 21, 2015, 4:45:13 PM4/21/15

to

Hi Julian

Have a look here: http://turboforth.net/source/Bank0/0-03-Math.html

Scroll down about 4 fifths towards the bottom. There you will find my floored division routine. It's written in TMS9900 assembler and heavily commented. Should suit you just fine. The TMS9900 does not have signed math so I have to set flags to remember the signs, perform an unsigned division then convert according to the signs. The 9900 has a DIV instruction which the ARM doesn't have so you'll need a little subroutine for that. Other than that it should be very easy to convert.

Shout if anything doesn't make sense!

Regards

Mark

Mark Wills

unread,

Apr 21, 2015, 4:54:34 PM4/21/15

to

The ABS (absolute value) instruction possibly needs a little explanation, otherwise the code looks wrong. ABS forces a value positive, but sets <0 flag in the status register according to the sign of the value before the ABS instruction is executed.

Stephen Pelc

unread,

Apr 21, 2015, 5:44:18 PM4/21/15

to

On Tue, 21 Apr 2015 13:23:08 -0700 (PDT), Julian Fondren
<julian....@gmail.com> wrote:

>Can someone clearly describe, or point me to a clear description, as to how one
>*implements* floored division vs. symmetric division? Suppose I start out by
>discarding signs and just repeatedly subtract numbers until I get a positive
>quotient and remainder.

See the "ARM System Developers Guide" by Sloss, Symes and Wright.

You also need to decide which of the many ARM instruction sets you
are talking about. Dealing with Cortex Ax is not the same as dealing
with Cortex-Mx or ARM7/9/11.

Stephen

--
Stephen Pelc, steph...@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

Rod Pemberton

unread,

Apr 21, 2015, 6:32:15 PM4/21/15

to

On Tue, 21 Apr 2015 16:23:08 -0400, Julian Fondren
<julian....@gmail.com> wrote:

> Can someone clearly describe, or point me to a clear description,
> as to how one *implements* floored division vs. symmetric division?

"Google is your friend."

These links were all on the first page of results.
The first three go into some detail. The last is a quick summary.

"Symmetric division considered harmful" (for Forth-83)
http://www.nimblemachines.com/symmetric-division-considered-harmful/

"Excerpts from Forth Programmer's Handbook #2"
http://www.computer-solutions.co.uk/chipdev/fph-2.htm

"Signed Integer Division" (kForth)
http://ccreweb.org/software/kforth/kforth5.html

"Division" (ANSForth)
http://www.forth.org/ansforth/node5.html

Sigh, I need to read those too ...

Rod Pemberton

--
Cars kill more people than guns in the U.S.
Yet, no one is trying to take away your car.

Julian Fondren

unread,

Apr 21, 2015, 7:28:18 PM4/21/15

to

On Tuesday, April 21, 2015 at 3:45:13 PM UTC-5, Mark Wills wrote:
> Hi Julian
>
> Have a look here: http://turboforth.net/source/Bank0/0-03-Math.html

Cool, that's remarkably easy to read.

On Tuesday, April 21, 2015 at 4:44:18 PM UTC-5, Stephen Pelc wrote:
> See the "ARM System Developers Guide" by Sloss, Symes and Wright.

Thanks, this looks be generally useful, and especially useful when I want
better division, but of signed division it just says "discard the signs and
then use these rules to put them back". Why those rules? It's oblivious to
the symmetric/floored controversy.

On Tuesday, April 21, 2015 at 5:32:15 PM UTC-5, Rod Pemberton wrote:
> "Google is your friend."

Bah.

> "Signed Integer Division" (kForth)
> http://ccreweb.org/software/kforth/kforth5.html

...

> Sigh, I need to read those too ...

Thanks, this one was useful, both for its remarks and for the link.
Which is broken, but which can be found at:

http://research.microsoft.com/pubs/151917/divmodnote.pdf

It contains some C code that uses symmetric division operators to produce a
floored result.

I guess what I'll do now is: A) write some kind of division routine. B)
determine whether what I've done is symmetric or floored, then C) name it
appropriately, and write another routine that fudges the results. It'd be nice
if I could set out with the intention of doing it one way or the other;
hopefully when I'm done I'll be able provide others with the exact answer that
I was looking for.

Cheers,
-- Julian

Albert van der Horst

unread,

Apr 21, 2015, 8:19:33 PM4/21/15

to

In article <8a492bc8-9c9e-465b...@googlegroups.com>,

Frans van de Markt (Dutch Forth) hit the same snag with porting ciforth to
ARM. My advise was to look at examples from FIG listings and the DEC alpha
ciforth (DEC alpha has no hardware division either)
With that he solved it, but it was one of the hardest parts of the
port. (another one is the -c option, to generate executables.)
You could also get that ciforth from me, but that would take the fun out of
it.
I hope we can in the future compare things and copy each other best
tricks.

>
>I'm aware that this manner of division is going to be dreadfully slow. For
>known divisors I'll have a way to perform the division with multipication,
>Otherwise this is fine for now.
>
>And I feel compelled to add.. I'm not writing a Forth. I'm porting a Forth.
>Starting with yourforth as it's small and commented well enough to make up for
>my not knowing x86. I'm using gas as there's a convenient package of gcc for
>Android, and as fasm doesn't seem to actually have arm binaries.

Nobody ever writes a Forth. The latest ciforth (soon) is in fact FIGforth
version 5.2. yourforth is the bastard child of ciforth and jonesforth.

>
>
>Thanks,
>-- Julian
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

David N. Williams

unread,

Apr 21, 2015, 11:05:41 PM4/21/15

to

Here's one more implementation, for ppc, which includes signed,
symmetric division. The commentary tries to be clear about the
algorithms -- don't know how well it succeeds.

http://www.umich.edu/~williams/archive/forth/kforth/index.html

-- David

David N. Williams

unread,

Apr 21, 2015, 11:07:58 PM4/21/15

to

Oops, here's the actual link:

http://www.umich.edu/~williams/archive/forth/kforth/div.s

-- David

Hans Bezemer

unread,

Apr 22, 2015, 5:49:16 AM4/22/15

to

Mark Wills wrote:

I dunno if that's what's needed here, but this is 4tH's implementation:

: fm/mod ( d1 n1 -- n2 n3 )
dup >r dup 0< if negate >r dnegate r> then
over 0< if tuck + swap then um/mod
r> 0< if swap negate swap then
;

: sm/rem ( d1 n1 -- n2 n3 )
over >r dup >r abs -rot
dabs rot um/mod
r> r@ xor 0< if negate then
r> 0< if swap negate swap then
;

Hans Bezemer

unread,

Apr 22, 2015, 9:57:56 AM4/22/15

to

Julian Fondren <julian....@gmail.com> writes:
>I can perform division with repeated subtraction (using subtract-with-carry to
>divide a 64-bit dividend by a 32-bit divisor), but what do I do about negative
>numbers?

: bla { d1 d2 -- }
d1 s>d d2 fm/mod d1 . d2 . ." fm/mod quot=" . ." mod=" . 5 spaces
d1 s>d d2 sm/rem d1 . d2 . ." fm/rem quot=" . ." rem=" . ;
7 3 bla
-7 3 bla
7 -3 bla
-7 -3 bla

outputs:

7 3 fm/mod quot=2 mod=1 7 3 fm/rem quot=2 rem=1 ok
-7 3 fm/mod quot=-3 mod=2 -7 3 fm/rem quot=-2 rem=-1 ok
7 -3 fm/mod quot=-3 mod=-2 7 -3 fm/rem quot=-2 rem=1 ok
-7 -3 fm/mod quot=2 mod=-1 -7 -3 fm/rem quot=2 rem=-1 ok

> My education takes me as a far as, for ratios, "if they're both
>negative, that cancels out - they are now both positive; if one is negative,
>normalize the ratio so that only the numerator is negative; if the ratio is
>reduced [i.e., if division is performed], the result has the sign of the
>numerator." Which doesn't cover the sign of the remainder, which is apaprently
>not the same thing as the modulus, which is apparently controversial.

You can just look it up in the standard:

http://www.forth200x.org/documents/html/usage.html#usage:div

>Can someone clearly describe, or point me to a clear description, as to how one
>*implements* floored division vs. symmetric division?

Both in C and in Forth from the Gforth sources:

From kernel/prim.fs in Gforth:

: fm/mod ( d1 n1 -- n2 n3 )

dup >r dup 0< IF negate >r dnegate r> THEN
over 0< IF tuck + swap THEN
um/mod
r> 0< IF swap negate swap THEN ;

: sm/rem ( d1 n1 -- n2 n3 )
over >r dup >r abs -rot
dabs rot um/mod

r> r@ xor 0< IF negate THEN
r> 0< IF swap negate swap THEN ;

Or if you prefer it in C, from engine/support.c:

DCell smdiv (DCell num, Cell denom)
/* symmetric divide procedure, mixed prec */
{
DCell res;
UDCell ures;
UCell l, q, r;
Cell h;
Cell denomsign=denom;

vm_d2twoCell(num,l,h);
if (h < 0)
num = dnegate (num);
if (denomsign < 0)
denom = -denom;
ures = umdiv(D2UD(num), denom);
vm_ud2twoCell(ures,q,r);
if ((h^denomsign)<0) {
q = -q;
if (((Cell)q) > 0) /* note: == 0 is possible */
throw(BALL_RESULTRANGE);
} else {
if (((Cell)q) < 0)
throw(BALL_RESULTRANGE);
}
if (h<0)
r = -r;
vm_twoCell2d(q,r,res);
return res;
}

DCell fmdiv (DCell num, Cell denom)
/* floored divide procedure, mixed prec */
{
/* I have this technique from Andrew Haley */
DCell res;
UDCell ures;
Cell denomsign=denom;
Cell numsign;
UCell q,r;

if (denom < 0) {
denom = -denom;
num = dnegate(num);
}
numsign = DHI(num);
if (numsign < 0)
DHI_IS(num,DHI(num)+denom);
ures = umdiv(D2UD(num),denom);
vm_ud2twoCell(ures,q,r);
if ((numsign^((Cell)q)) < 0)
throw(BALL_RESULTRANGE);
if (denomsign<0)
r = -r;
vm_twoCell2d(q,r,res);
return res;

Hans Bezemer

unread,

Apr 22, 2015, 10:50:47 AM4/22/15

to

Anton Ertl wrote:

http://www.complang.tuwien.ac.at/cvsweb/cgi-bin/cvsweb/gforth/Attic/primitives?rev=1.53;content-type=text%2Fplain

As far as double cell stack operations go:

: 2swap rot >r rot r> ;

Is probably more efficient than:

: 2swap >r -rot r> -rot ;

Since most systems define -ROT as "ROT ROT" (gforth doesn't - it's a
primitive).

Hence,

: 2nip rot drop rot drop ;

Is probably more efficient than:

: 2nip 2swap 2drop ;

And finally, if your PICK or 2SWAP isn't too good, this /may/ be a slightly
better alternative:

: 2TUCK OVER >R ROT >R ROT OVER R> R> ROT ;

Hans Bezemer

Here are some alternate definitions which may be useful
depending on which low-leve words ("primitives") are
available to you.

: 2SWAP 2TUCK 2DROP ;
: 2SWAP 2OVER 2>R 2>R 2DROP 2R> 2R> ;
: 2SWAP ROT >R ROT R> ;
: 2SWAP >R -ROT R> -ROT ;
: 2SWAP >R SWAP R> SWAP >R >R SWAP R> SWAP R> ;

: 2NIP 2SWAP 2DROP ;
: 2NIP 2>R 2DROP 2R> ;
: 2NIP ROT DROP ROT DROP ;
: 2NIP >R -ROT DROP DROP R> ;
: 2NIP >R >R DROP DROP R> R> ;
: 2NIP >R SWAP DROP SWAP DROP R> ;

: 2TUCK 2SWAP 2OVER ;
: 2TUCK 2DUP 2>R 2SWAP 2R> ;
: 2TUCK DUP >R OVER >R ROT >R ROT R> R> R> ;
: 2TUCK OVER >R >R -ROT R@ -ROT R> R> SWAP ;

: 2OVER 2SWAP 2TUCK ;
: 2OVER 2>R 2DUP 2R> 2SWAP ;
: 2OVER >R >R OVER OVER R> R> ROT >R ROT R> ;
: 2OVER >R >R OVER OVER R> -ROT R> -ROT ;

: 2ROT 2>R 2SWAP 2R> 2SWAP ;

I was hoping to obtain a definition for 2TUCK or 2OVER without
ROT or -ROT for my own use, but the solver was taking way, way
too long ... So, the best I could do was two ROTs, for now.

Rod Pemberton

Michael Barry

unread,

Apr 28, 2015, 1:08:17 AM4/28/15

to

On Friday, April 24, 2015 at 6:46:24 PM UTC-7, Rod Pemberton wrote:
> ...

> I was hoping to obtain a definition for 2TUCK or 2OVER without
> ROT or -ROT for my own use, but the solver was taking way, way
> too long ... So, the best I could do was two ROTs, for now.
>
>
> Rod Pemberton

I don't really have to avoid ROT and -ROT in the DTC Forth for
my insane little cpu hobby project, because both of them are
very fast primitives (allegedly):

; 294 ;------------------------------------ ROT
000000a1:0000009b; 295 NOT_IMM 'ROT'
000000a2:03524f54; 295
; 296 _rot: ; ( x1 x2 x3 -- x2 x3 x1 )
000000a3:e1020000; 297 exa ,x
000000a4:e1020001; 298 exa 1,x
000000a5:5e040000; 299 jmp (,y+) ; NEXT

; 792 ;----------------------------------- -ROT
000001b0:000001a9; 793 NOT_IMM '-ROT'
000001b1:042d524f; 793
000001b2:54000000; 793
; 794 _dashrot: ; ( x1 x2 x3 -- x3 x1 x2 )
000001b3:e1020001; 795 exa 1,x
000001b4:e1020000; 796 exa ,x
000001b5:5e040000; 797 jmp (,y+) ; NEXT

It's a shame to have all of those zeros in the machine code
words (still hand-assembled by yours truly), but if I ever
get to writing something bigger than about 2KW, they might
eventually be put to good use.

Mike

Rod Pemberton

unread,

Apr 28, 2015, 3:24:17 AM4/28/15

to

On Tue, 28 Apr 2015 01:08:16 -0400, Michael Barry <barry...@yahoo.com>
wrote:

> On Friday, April 24, 2015 at 6:46:24 PM UTC-7, Rod Pemberton wrote:

>> I was hoping to obtain a definition for 2TUCK or 2OVER without
>> ROT or -ROT for my own use, but the solver was taking way, way
>> too long ... So, the best I could do was two ROTs, for now.
>>
>

> I don't really have to avoid ROT and -ROT in the DTC Forth for
> my insane little cpu hobby project, because both of them are
> very fast primitives (allegedly):
>

I have ROT as a primitive in my ITC Forth too, as C code which
optimizes very well to assembly. However, it's still one of
the larger stack primitives. Of course, the call overhead when
interpreting the threaded code probably limits non-ROT definations
to 3 or 4 words, i.e., longer definitions would underperform ROT
based definitions.

foxaudio...@gmail.com

unread,

Apr 28, 2015, 9:44:08 AM4/28/15

to

Mark,

Those are nice looking code pages. What did you use to write the HTML?

BF

Mark Wills

unread,

Apr 28, 2015, 10:27:13 AM4/28/15

to

Hi. It's a hand-written vb.net program that I wrote about 5 or 6 years
ago!

Julian Fondren

unread,

May 11, 2015, 7:38:41 PM5/11/15

to

On Tuesday, April 21, 2015 at 7:19:33 PM UTC-5, Albert van der Horst wrote:
> You could also get that ciforth from me, but that would take the fun out of
> it.

I've spent too much time on this, so I'm done. I just wanted
to easily run and test some CGI on my android laptop. The CGI
stuff was fun. This has become a chore. If you do have an ARM
version of C Forth, I might be able to offer something to that.

I did find:

* C can be easily employed for SM/REM (and compiles to a call to
some ARM library, so the assembler is still not really useful.)

* although at the cost of -omagic linking becoming impossible,
so you have to separate your executable and your writable data.

* which is fairly easily done, if you use macro to lay down .data
headers and then auto-switch to .text for primitive code words
(or stay in .data for colon words.)

* a touch of Forth really helps with debugging.

I took things farther with the direct rewrite of ci86.lina.s,
before the time ran out, but http://minimaltype.com/forth.tgz
pretty much has what I've come up with. SM/REM in C. An ITC
threading model. Macros that lay down headers conveniently.

Meanwhile, https://www.mininodes.com/ <- ARM web hosting.

-- Julian

Albert van der Horst

unread,

May 11, 2015, 8:24:57 PM5/11/15

to

In article <63d4206c-bfe1-40e4...@googlegroups.com>,

If it is any help, I found the following definition of
SM/REM in terms of Um/MOD. It is probably a transcription of
some figForth code.

: +- 0< IF NEGATE THEN ;
: SM/REM
OVER \ low high quot high
>R
>R \ low high R: wuot ot high
DABS \
R@
ABS
UM/MOD
R>
R@
XOR
+-
SWAP
R>
+-
SWAP
;

Anton Ertl

unread,

May 12, 2015, 10:02:41 AM5/12/15

to

Julian Fondren <ayr...@gmail.com> writes:
>* C can be easily employed for SM/REM (and compiles to a call to
>some ARM library, so the assembler is still not really useful.)

We have found that trying to do mixed-precision division (SM/REM
UM/MOD FM/MOD) in straight-forward C results in slow code, if you have
the integer types to do that at all; that's because C does a
double-by-double division. We have fixed this with assembler escapes
and, for machines that don't have mixed-precision division as an
instruction, a big, messy pile of code.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html

EuroForth 2015: http://www.mpeforth.com/euroforth2015/euroforth2015.htm