29 Jul
2005
29 Jul
'05
9 a.m.
On Fri, 29 Jul 2005 "Jerome H. Fine" <jhfinexgs2 at compsys.to> wrote:
I've already posted code for how to do arbitrary size additions in
FORTRAN-77 on the PDP-11. Substraction is very straight forward the same
deal. Multiplication and division follows the same line as well. Nothing
difficult at all, really.
Yes, the MUL instruction sign adjust the 32-bit result, based on the two
16-bit input values. However, who cares?
You can get FORTRAN-77 to do unsigned 16 bit multiplication by just
grabbing the 16 bit value, and move it (unsigned) into a 32-bit variable,
do the multiplication, and you'll get an unsigned result back, in
combination with the carry into the next word (when split into two 16-bit
values again).
Do it just like you do on paper. Deal with 16 bits at a time, stuffed into
32-bit variables. Sign will be preserved, overflow dealt with, and
everything works out just fine.
Johnny
Johnny Billquist || "I'm on a bus
|| on a psychedelic trip
email: bqt at update.uu.se || Reading murder books
pdp is alive! || tryin' to stay hip" - B. Idol
Sean
'Captain Napalm' Conner wrote:
It was thus said that the Great Jerome H. Fine
once stated:
Jerome Fine replies:
While the logic will probably be in FORTRAN 77 under RT-11
on an emulated PDP-11, I might actually check that it all works
on a real PDP-11. However, since FORTRAN 77 is rather nasty
using more than 32 bit integers, I will probably code the routines
in MACRO-11 for 64/128 bit add and compare after I first write
the program for 32 bit integers which can calculate up to 2 billion. By the way, are there any standard algorithms for
the
4 basic operations (add, subtract, multiply and divide)
for 128 bit numbers which are composed of 8 * 16 bit
words? As per your suggestion, I would probably use:
CHARACTER * 16 ARRAY ( nnn )
What language? In assembly addition and subtraction are pretty trivial if
you have a carry bit you can use (not all RISC based CPUs have a carry bit).
Just make sure you keep track of endian issues (given an array A[n] is A[0]
the Most Significant or Least Significant word?).
[Snip]
As for endian issues, I can define the most
significant word to be
at either end, but I tend to think that I will place the most significant
at the high end of the word since this allows FORTRAN 77 to use
octal to output the value correctly with 64 bit floating point values.
??? Not sure what you actually say here. Floating point values hardly have
anything to do with this. Pick whatever byte order you want, and stick
with it. Output is something you'll have to figure out anyway, and you
deal with any byte order you decided on then. Either way is not that
difficult. However, I'd recommend using little-endian, since that is the
"natural" order of the PDP-11, and F77 on the machine. That means you can
let it deal with 16-bit quantities natively without having to to byte
swapping.
A B
C D
W X Y Z
---------------------
AZ BZ CZ DZ
AY BY CY DY
AX BX CX DX
AW BW CW DW
(and don't forget the carries!) One trick you might want to try is to take
advantage of the fact that these are binary values so multiplication becomes
shifts and adds but with larger values like these, doing the multibyte
rotates may not be as effective as using the actual MUL instructions.
For the PDP-11, I tend to understand that MUL is only for signed
16 bit numbers, so I don't think MUL can be useful with unsigned
values which are required for a 64 bit multiple as per the above
example.
CAN SOMEONE PLEASE CORRECT ME IF I AM WRONG??? That said, in MACRO-11, it should not be too difficult
to do multiple shift
and add operations. However, maybe someone already had some code
handy?
Someone probably have, yes. But it is still *very* easy.
No more than a days work. If you pay me, I'll throw the code together for
you.
Division is
nasty, but again, works like long division.
[Snip]
I have some C code that does some of this---one is a C implementation of a
techique Woz used in calculating e to 100,000 digits (as described in Byte
magazine of either Dec 1980 or Dec 1981) and another one that does division
in C, if you are interested.
I am interested!!!!!!! 
29 Jul
29 Jul
9:47 a.m.
> For the PDP-11, I tend to understand that MUL is
only for signed 16
> bit numbers, so I don't think MUL can be useful with unsigned values
> which are required for a 64 bit multiple as per the above example.
> CAN SOMEONE PLEASE CORRECT ME IF I AM
WRONG???
You're right and you're wrong. :-)
If you're doing a 16*16->16 multiply, it doesn't matter whether it's
signed or not, except for detecting overflow.
If you're doing a 16*16->32 multiply, the difference between signed and
unsigned is the high half of the result. To figure details, consider,
for example, A*B where A is in the "problematic" range (32768..65535).
You want A*B; the instruction will give you (A-65536)*B = A*B - 65536*B.
Come to think of it, I think the code I posted earlier using EMUL to do
extended-precision multiplication is wrong for this reason; as I read
the VARM, EMUL does a signed multiply-and-add....
/~\ The ASCII der Mouse
\ / Ribbon Campaign
X Against HTML mouse at rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
30 Jul
30 Jul
6:53 p.m.
Johnny Billquist wrote:
Jerome Fine replies:
Please define little-endian and big endian.
Also, I should have explained what I meant! Specifically,
it should be possible to use floating point variables
as arguments to subroutines and let FORTRAN 77 take
care of allocating the actual storage by doing so:
1000 FORMAT ( O25, O25 )
REAL * 8 Value1, Value2
CALL I64ADD ( Value1, Value2 )
TYPE 1000, Value1, Value2
I64ADD::
Mov R0,-(SP)
Mov R1,-(SP)
Mov 2(R5),R0
Mov 4(R5),R1
Add (R0)+,(R1)+
Adc (R1)
Add (R0)+,(R1)+
Adc (R1)+
Add (R0)+,(R1)+
Adc (R1)+
Add (R0)+,(R1)+
Mov (SP)+,R1
Mov (SP)+,R0
Return
.End
This could be the code to add two 64 bit unsigned integers
with the names of Value1 and Value2 which each occupy
64 bits. Of course, I could also use:
INTEGER * 2 I2Val1 ( 4 ), I2Val2 ( 4 )
EQUIVALENCE ( Value1, I2Val1 ), ( Value2, I2Val2 )
but "REAL * 8" also allows the output in octal as a
single 64 bit value which is quite convenient and allows
me to use a single index when I need a vector of values.
If I am correct, the above code assumes that the low order
words/bytes are the least significant and the high order
words/bytes are the most significant. Is this little-endian
or big-endian?
NOTE that if the most significant bit is in the most
significant word and byte (as per the above MACRO-11
subroutine), then the most significant of everything
is in the highest address of everything. HOWEVER, from
looking at the order of bytes, words and bits in the
PDP-11 manual (Chapter 10 of Microcomputer Processor
Handbook), when the most significant bit is in the
word with the lowest address, the most significant
bit (actually the sign bit and the exponent of real
floating point numbers) is in byte 1 rather than byte 0.
This is not a problem per say within FORTRAN 77 as it
clearly knows about these endian issues, but I found it
a bit confusing at first until I realized that the
bytes seemed to be interchanged within each word when
the most significant bit is defined to be in word 0.
On the other hand, if the most significant bit is in
the byte and word with the highest address, then in
FORTRAN 77 under RT-11, outputting Value1 in octal
with this order of significance shows a 64 bit octal
value with the most significant bit on the left and
the least significant on the right.
Can you please comment on the endian question?
Also, am I correct about octal output of Value1?
Thank you for your comments and any answers!
Sincerely yours,
Jerome Fine
--
If you attempted to send a reply and the original e-mail
address has been discontinued due a high volume of junk
e-mail, then the semi-permanent e-mail address can be
obtained by replacing the four characters preceding the
'at' with the four digits of the current year.
Jerome H. Fine
wrote:
As for endian issues, I can define the most
significant word to be
at either end, but I tend to think that I will place the most significant
at the high end of the word since this allows FORTRAN 77 to use
octal to output the value correctly with 64 bit floating point values.
??? Not sure what you actually say here. Floating point values hardly have
anything to do with this. Pick whatever byte order you want, and stick
with it. Output is something you'll have to figure out anyway, and you
deal with any byte order you decided on then. Either way is not that
difficult. However, I'd recommend using little-endian, since that is the
"natural" order of the PDP-11, and F77 on the machine. That means you can
let it deal with 16-bit quantities natively without having to to byte
swapping.
7:28 p.m.
Please define little-endian and big endian.
Little-endian and big-endian apply whenever you have a multi-digit
value broken up into smaller ordered multi-digit units. (Usually this
is for base-2 digits, but it doesn't have to be.) Most often, the
smaller units are 8-bit bytes, with the order being memory addressing,
but this doesn't have to be so. (An example that violates all of those
assumptions is sending multi-bit bytes over a bit-serial line, where
the "smaller..units" are individual bits, ordered by chronology on the
wire.)
As a concrete example, consider the 32-bit value 305,419,896 (decimal),
stored in 4 bytes on a computer with 8-bit bytes. 305,419,896 is hex
12345678; the four bytes will have values 12, 34, 56, and 78 (hex).
The question is, which comes first?
In little-endian, the byte with value 78, the least significant one,
comes first, followed by 56, 34, and 12. In big-endian order, it's the
other way around: 12, 34, 56, 78. As applied to values in memory,
"comes first" generally means "stored at lower-addressed memory".
Little-endian is how the x86 family of CPUs works. The VAX also uses
little-endian, as do some MIPS systems, and probably others that don't
come to my mind immediately. Big-endian is used by the SPARC, the
680x0 family, some MIPS systems, and, again, doubtless others.
The PDP-11 is an odd case. The hardware is little-endian, but the
hardware is 16-bit. Some languages store 32-bit integers in what we
might call "schizophrenic endian": that 12345678 value is stored in
four consecutive bytes as 34 12 78 56: it is broken into two 16-bit
words with the more-significant one stored first, but those 16-bit
words are then stored little-endian in the bytes making them up. Some
aspects of the VAX - notably its floating-point layout - are comparably
twisted; it's quite impressive to look at the data layouts section of
the VAX Architecture Reference Manual and notice how some things are
shown in 8-bit columns, some 16, some 32, so that it all looks natural
even when it's totally bizarre.
Specifically, it should be possible to use floating
point variables
as arguments to subroutines and let FORTRAN 77 take care of
allocating the actual storage by doing so:
1000 FORMAT ( O25, O25 )
REAL * 8 Value1, Value2
CALL I64ADD ( Value1, Value2 )
TYPE 1000, Value1, Value2
Whether this will do what you want depends on what the implementation
does when asked to print a floating-point value in octal. You appear
to be assuming it simply prints the bits making up the floating-point
number, rather than (as would be more logically consistent) doing a
conversion to octal floating point. (I would actually expect to get a
compile-time error from using an O format with a REAL*8 value.)
I64ADD::
Mov R0,-(SP)
Mov R1,-(SP)
Mov 2(R5),R0
Mov 4(R5),R1
Add (R0)+,(R1)+
Adc (R1)
Add (R0)+,(R1)+
Adc (R1)+
Add (R0)+,(R1)+
Adc (R1)+
Add (R0)+,(R1)+
Mov (SP)+,R1
Mov (SP)+,R0
Return
I see two problems here. First, you have to eliminate the
postincrement on the second and third ADC instructions. Second, this
loses carries resulting from the ADCs. For example, if r1 points to
0x00000000ffffffff and r0 points to 0x0000000000000001, the result
will, I think be zero, not the 0x0000000100000000 it should be. (Also,
the return instruction is normally spelled "ret", not "return".)
If I am correct, the above code assumes that the low
order
words/bytes are the least significant and the high order words/bytes
are the most significant.
Right - or at least, it does after you've fixed the bugs.
Is this little-endian or big-endian?
Little-endian.
/~\ The ASCII der Mouse
\ / Ribbon Campaign
X Against HTML mouse at rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
6865
days inactive
6867
days old
3 comments
3 participants
participants (3)
-
bqt＠Update.UU.SE -
jhfinexgs2＠compsys.to -
mouse＠Rodents.Montreal.QC.CA