Problem With Random Macro

[MICHAEL GARDI]

I've been teaching myself PDP-1 assembler and to that end have coded an implementation of Bresenham's integer based line drawing algorithm. It seems to be working OK but to really test it out I wrote a program to generate random end points and draw lines between them in a continuous loop. To generate the random coordinates I "borrowed" the random macro from Retrochallenge 2016 Computer Space Simulator code. (Note the identical code is in Spacewar 3.1 which is where they got it ;-) That is where I started having problems. Random with a starting "seed" of zero would immediately converge on 0 and only produce zeros. With a non-zero seed it would produce a small set of numbers (say 3-20) before settling into a repeating loop of those numbers. According to this article:  "Anatomy of a Random Number Generator" this code should produce 261,654 distinctive values before repeating. So I wrote a small test program.

STARS

/ Create a random number.
define random
lac ran
rar 1s
xor (355670
add (355670
dac ran
term

100/
go, random / Generate a new random number.
cli    / Clear IO.
scr 9s / Move low 9 bits into high 9 bits of IO.
sal 9s / Move remaining 9 bits into AC high part.
dpy-i / Plot the point. Don't wait.
jmp go

ran, 716243
start go

The stars are being plotted exactly as the Computer Space code did by treating he 18 bit random number being produced as two 9-bit numbers for the x and y coordinates. I assembled and ran this through the Web interface and this is the result:

Good distribution but there are only 18 static "stars" which tells me they are being repeatedly refreshed. There should be many, many stars with old stars fading out as new stars are plotted.

The only theory I have is that the add instruction is not handling the carry overflow correctly. From the linked article:

That is, there’s also a pecularity to the addition, which introduces a bit of extra variety: Using one’s complement, a) we have to adjust for minus zero (777777 → 000000) and b) we have to adjust for any overflow in the sign position by an extra increment (as may be observed in iteration #6).

emulation of one’s complement addition (18 bits)

function adc(value) {
    ac = ac + value;
    // check overflow of sign bits (to bit 18)
    if (ac & 0o1000000) ac = (ac + 1) & 0o777777;
    // correct negative zero
    if (ac == 0o777777) ac = 0;
}

thus

     101000111110011011  //  507633
  +  011101101110111000  //  355670
  = 1000110101101010011  // 1065523

but

  adc(
     101000111110011011, //  507633
     011101101110111000  //  355670
  )
  => 000110101101010100  //  065524

OK. I've probably said too much.

Thoughts?

Mike

[Alen Shapiro]

Hi Mike,

I've been trying to document issues with the available C -> PDP1 cross compiler and have run across an issue that may be related to how the simulator handles "shift" instructions across a 16-bit boundary. I've not been able to isolate the issue away from the compiler yet as there's a more fundamental issue with initializing integers larger than 12-bits. Just in case this is relevant the code I'm playing with shifts 3-bits (07) up from the low bits, up to the high bits and then back down again. Here's the C Code:

#define THREE_BITS 07

bits = THREE_BITS;
pdp1_puti(bits, OCTAL_BASE);
pdp1_putc(NL);

for(i=0 ; i < 5 ; i++) {
bits = bits << 3;
pdp1_puti(bits, OCTAL_BASE);
pdp1_putc(NL);
}
pdp1_putc(NL);
for(i=0 ; i < 6 ; i++) {
pdp1_puti(bits, OCTAL_BASE);
bits = bits >> 3;
pdp1_putc(NL);
}

pdp1_puti(bits, OCTAL_BASE);
pdp1_putc(NL);

which gives this output:

0
07
070
0700
07000
070000
0100000

0100000
030000
03000
0300
030
03
0

Looks like shifting up into the 16th, 17th, and 18th bits loses 2 out of the three bits but shifting back down again gains back one of the bits.

Might this be related to your random function misbehaving?

Regards,

--Alen

[MICHAEL GARDI]

I’m not sure  I see a connection to my issue Alen. If I had to guess your issue could be related to arithmetic vs logical shifts. What op codes are being generated under the covers? 

Mike

--
You received this message because you are subscribed to the Google Groups "[PiDP-1]" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pidp-1+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/pidp-1/166d0b36-8931-496f-94c3-0f0868829f57n%40googlegroups.com.

[Bill E]

Interesting. I assembled the same code using macro1 as installed by the distribution. Works fine, I see points uniformly distributed over the entire screen.

Here is my source and rim, try the rim.

Bill

[MICHAEL GARDI]

Thanks for doing that Bill. Your rim works the same as mine when loaded through the Web interface. Yes there is and even distribution of stars but there should be hundreds of starts plotted not just 18. random should generate 261,654 unique x/y positions and not just repeat 18 positions.  

Mike

[Alen Shapiro]

It's doing "SAL 3" for the left shift loop and "SAR 3" for the right shift loop. Both seem to not properly handle the high-2 bits (b17 and b18) which could easily affect the distribution and count in pseudo-random functions.

L52: L53:
law -2 law -2
add 0130 add 0130
dac 0100 dac 0100
law -2 law 8
add 0130 dac 0101
dac 0101 lac.i 0100
lac.i 0101 dac 0100

sal 3 jsp pdp1_puti
dac.i 0100 law -2
law -2 add 0130
add 0130 dac 0100
dac 0100 law -2
law 8 add 0130
dac 0101 dac 0101
lac.i 0100 lac.i 0101

dac 0100 sar 3
jsp pdp1_puti dac.i 0100
law 63 law 63
dac 0100 dac 0100
jsp pdp1_putc jsp pdp1_putc
law -1 law -1
add 0130 add 0130
dac 0100 dac 0100
law -1 law -1
add 0130 add 0130
dac 0101 dac 0101
law 1 law 1
add.i 0101 add.i 0101
dac.i 0100 dac.i 0100

[Bill E]

I do get hundreds, many hundreds of stars on the display. Here's the lst for the assembly. I'd compare it to yours, check that the opcodes match.

Also, shift works as documented. It DOES NOT shift the high bit in the ac. Check the description in the original PDP-1 Handbook.

Bill

[MICHAEL GARDI]

I should mention that I resolved this issue but don't know why. I switched to the native Pi environment and re-assembled my programs with macro1_1 and ran them through the GUI interface and they worked. I had been exclusively working through the Web interface and via VNC. In the process I rebooted the pi a couple of times. The weird part is that when I switched back to Web/VNC the programs worked there too! Go figure. Sorry for the wasted bandwidth. Big thanks to Bill for his help.

Mike