MDV Software Reclamation

[bwinkel67]

So I wrote a few pieces of software back in the early 90's. Some personal and some professional. The professional was really for the Apple Mac market but I didn't have a Mac at the time so I wrote it specifically on the QL using Digital C's compiler and then later ported it to the Mac (it was actually a crazy plan that I had and it worked perfectly). Specifically a simple BASIC interpreter tied to a command shell where Mac users could script things like disk backups, etc. It was well received by reviewers but little interest by Mac users and never sold well. I'm still trying to recover the QL sources and have most of them (only like 4 files I think) but the years of sitting on an MDV have not been kind. I do have it copied to a hard disk on a Mac (well, a Mac emulator) but need to see if it compiles on the QL via Digital C. If so I will post it here eventually, including source, in case anyone wants to see how to write an interpreter (note that the QL version is very inefficient but does work). I now use that same BASIC interpreter to teach students in a programming languages class how to write one though it is no longer BASIC and instead a simpler made-up language that students write with me during the semester.

In the meantime my first reclamation is Crypt, a small encryption/decryption program based on the idea of a stream cipher using a psuedo random number generator. Looks like I used BSD's version back in 92 and I'm not doing a good job adding modulus arithmetic. I hash the password to get a key and I'm not sure I like that either. For the past 10 years I've taught security and my students create a similar stream cipher in JavaScript using a much better pseudo random number generator and I do a better job with modulus. Also the hash function in that version adds up the ascii values and multiplies by their position to avoid MAP and PAM password conflicts but is till rather simple hash (its' for teaching). Not sure if my Crypt hash function is any better.

Here it is. Comes as an executable, Small C source (pretty generic and simple) and a text file with instructions. Use it either as a learning tool or for productivity. Stream ciphers are simple to write, with this one 31 bit (i.e. its cycle should be 2 billion) so good enough to protect things from prying eyes. If you want a bigger cycle a) you need integers longer than 32 bits and b) a pseudo random number generator that goes beyond the 31 bits. Some common psuedo random number generators are in the form of: i = (i*p1 + p2) % N where N is the size of the cycle. The one I use in my class room is: i = ( 1 * 16807 + 1 ) % 2^31-1. The magic prime number is 16807 as it relates to 2^31-1 (i.e. 2147483647). So put that one in Crypt_c as I think it's better than the BSD one. There are better random number generators that are a bit more involved to implement if you really want to secure things but the stream cipher still uses the sequence the same way.

Crypt.zip

(4.36 KiB) Downloaded 99 times

References for each:

The one I used in 92 (no idea how I found it without the web):

https://rosettacode.org/wiki/Linear_con ... _generator

This one was actually developed by a former professor of mine in the late 80's and now I use in my classroom:

http://www.math.utah.edu/~pa/Random/Random.html

[tcat]

Hi,

Interesting algo for file encryption. In Rand(), I miss the idea of having a pointer to int, and returning a first element of an int array?

I have done some reading on randoms, in Green Oberon Book [M. Reiser / N. Wirth 1992]

Code: Select all

   PROCEDURE Uniform* (): REAL;
	(* Returns a uniformly distributed floating point value between 0.0 and 1.0 *)
		CONST a = 48271;   (* suggested: 48271 is prime, iso 16807 = 7^5 *)
			m = 2147483647;  (* = 2^31 - 1 *)
			q = m DIV a;  r = m MOD a;
	BEGIN
		seed := a * (seed MOD q) - r * (seed DIV q);
		IF seed <= 0 THEN seed := seed + m END;
		RETURN seed * (1.0 / m)
	END Uniform;

As a seed, the system second or millisecond ticks can be used, where `q' - quotient, `r' - remainder, `m' - modulus, `a' - multiplier.
There was also an argument to use 48271 instead of 16807 prime.
Tomas

[bwinkel67]

I saw that with regard to the pointer to int. I can't remember why on earth I had to do that but Digital C was a weird beast if I recall. So the rand function needs to return a long integer and it seems that's how Digital C handled it. It's an implementation of Small C and I do have James Hendrix's book on it with source code and all. The only difference from it and Digital's is that they added floating point libraries.

With regard to seed, yes, when you don't care to recreate the random sequence then you can come up with nicer, more random ways to seed it. But the point of encryption/decryption is to be able to repeat the sequence so you have to seed it with a specific value as that is your encryption key. And since humans don't like to remember numbers and instead phrases (or passwords) we can use a simple hash (checksum) to convert a phrase to a number. Again, this is a very simple cipher with lots of weaknesses starting with the hash and the linear congruent generator, the latter of which isn't the best foundation for random sequences when you get into more sophisticated encryption methods like AES. But fundamentally, encryption is about shifting things in some random sequence. True cipher streams, for efficiency, xor their sequence rather than add them, but this little Crypt program doesn't care about efficiency :-/

[bwinkel67]

Here is the Sinclair QL prototype for the Macintosh command shell and BASIC interpreter. I'm including the executable as well as the C source code that implements the BASIC interpreter (written in Digital C SE back in 1992, which is pretty vanilla C).

On the QL it was code named CL. There is a README.txt file that gives you a little bit of background of what it is and does. Note this prototype isn't optimized and does pretty inefficient parsing but I ran a little test program (test_bas) between the QL and it (running in QLAY2) and the QL runs about 25% faster, so not bad for an unoptimized BASIC interpreter. As I mentioned earlier, it saw good reviews from MacWorld and MacUser but never sold much. I did later on hack the Mac kernel to add QL-like job control and that did sell very well (#3 best seller in the Japanese market in the mid 90's). I just liked the QL in the day, even better than Unix :-/

cl.zip

(36.21 KiB) Downloaded 100 times

Many of the operating system shell commands are not implemented, some just say "COMMAND: blah blah" showing that it's been parsed properly. Others aren't even being parsed so you get the "NO COMMAND" error. But there are some that do work like "date" and "prompt" and "alias" with the latter allowing you to create new commands combining shell and BASIC syntax. Note that the BASIC doesn't quite align with SuperBASIC (i.e. I use GOTO vs GO TO for one example, though QL will actually read in GOTO and correct it but not vice versa). On the Macintosh version I also implemented piping which allowed the shell commands to work with BASIC (I did implement a few in the prototype so you can do "date > today$" and "version > cur$" as examples). So you could do stuff like "copy myFile.txt > a$" which would copy the contents of a file into an internal variable. Or you could do "dir > $dirList" to get an internal string of the directory listing. Here is an example encryption program that was released in the scripts folder with the product to demonstrate how shell and BASIC interacted (this won't work on the CL prototype though all of the BASIC is implemented):

Code: Select all

10 rem *** Encrypt ***
20 flags : print "Welcome to the Encryption/Decryption program."
30 repeat loop
40    print "Enter E)ncode, D)ecode or Q)uit? "; : input ans$
50    if (ans$ = "Q") or (ans$ = "q") then exit loop
60    print "Enter password? "; : input pwd$
70    print "Enter text file name? "; : input file$
80    let seed=1: for i=1 to len(pwd$): let seed = seed*code(pwd$(i))
90    let i = rand(seed) : copy file$ > text$
100    if (ans$ = "E") or (ans$ = "e") then
110       print "Starting encoding run..." : let suf$ = ".ecr"
120       for i=1 to len(text$)
130          let ch=code(text$(i))+(int(rand()*255)+1): let text$(i)=chr$(ch-255*(ch>255))
140       next i
150    else
160       print "Starting decoding run..." : let suf$ = ".dcr"
170       for i=1 to len(text$)
180          let ch=code(text$(i))-(int(rand()*255)+1): let text$(i)=chr$(ch+255*(ch<1))
190       next i
200    end if
210    copy -o file$&suf$ < text$ : rem save new file
220    copy -kro file$ file$&suf$ : rem copy resource fork to new file
230 end repeat loop

Note that I couldn't get Digital 'C' to compile my original source under QLAY2. I think it has to do with directory defaults (I will try again with my QL to see if vDrive gets it to work). I ended up taking my 4 source files an concatenated them all together into on large cl_c file (modifying the header file since it had a condition where it externed for aux_c and expr_c). I included the original source in a zip file within the zip file but there are absolutely no differences (sans the aforementioned cmd_h file change). Compiling with the single source is straight forward:

exec_w mdv1_cc;"mdv2_cl_c"
exec_w mdv1_cg;"mdv2_cl mdv2_cl -nc"

This assumes you have Digital C in MDV1 and the source in MDV2. If you actually do this on MDV's you will run out of space since CC stores the resulting _obj file on MDV1. A trick that worked is to only store cl_c on MDV2 and move CC to MDV2 as well. You then run CC from there and the space left by the missing CC on MDV1 will be enough to host cl_obj. Then just move cl_obj over to MDV2 (removing cl_c first) and run CG (this one can stay on mdv1) and you should be good to go. If you are using FLP you should have no problems. Still trying to weed through the use of WIN on QLAY2 so stay tuned. Of course I used to compile with 4 files so if anyone figures this out on QLAY2 with Digital C SE please share.

It's a pretty straightforward recursive descent parser and should be pretty easy to follow. So if you ever wanted to see how a high level language is written in another high level language without using tools like lex and yacc, this is it. If you use tools, the resultant code is usually pretty unreadable albeit more efficient. I teach this stuff now and my students usually write a recursive descent parser like this (a bit simpler) in Java in about two to three weeks and then implement another one as a final project in lex/yacc (flex/bison are the free GNU ones).

BTW, this interpreter got me thinking of writing a ZX81 simulator on the QL. I say simulator and not emulator because instead of emulating the Z80 chip and then having it run the original ROM, I'm thinking of just implementing the ZX81 BASIC (which this is already pretty close too) and adding the simple graphics capability. Should make for a fast ZX81 even running on a BBQL. No machine code stuff would work and most POKE and PEEK commands would fail but in the day I wrote some cool BASIC programs like Battleship (still have the printout) that only relied on BASIC. Any thoughts on some of the hurdles I might encounter? Might make for a fun project.

[pjw]

Cute It runs on QPC2, including the test_bas. Do you intend to do any more work on it for the QL?

[bwinkel67]

Cute It runs on QPC2, including the test_bas. Do you intend to do any more work on it for the QL?

In terms of adding the command functionality? No, I hadn't planned on it. I implemented all that back in 92 on the Mac. Not even sure if Digital C gives you access to some of the directory tasks like getting a listing of a drive or deleting a file. Copying would be easy enough but the QL doesn't support renaming so that would be a hack. Plus, there is no directory structure in the basic OS though I suppose one could create one.

I'm sure it will be easy to port to a different C supported by the QL and anyone can add to it or finish those commands. Perhaps I should put it on GitHub so multiple people could branch off of it to work. Then anyone can use it as a starting point and create a shell. Might work pretty well in some of the larger systems supported by the Q60 or Q68. Might also frustrate folks when they see it's not exactly SuperBASIC.

I personally plan to modify it to create a version to conform to the ZX81 BASIC and see if I can add graphics to simulate that machine...that would be cool. I was frustrated that the only ZX81 emulator is too resource intensive and uses the pointer environment that you can't run it on a BBQL...with 128K running a 1K machine that shouldn't have been too hard. I have been writing my own CPU emulators for a class so maybe I'll do that someday though I'll have to get back into learning the ins and outs of a Z80.

[stevepoole]

Hi,
Here is a little program which generates random numbers. First ENTER 'start' before running ...
I have tested this statistically, and the results are good !
Steve Poole.

____________

100 REMark QLrand4_bas (+test) v24oct17
110 ::
120 REMark ENTER 'start' to Randomise..
130 IF q$='': STOP
140 ::
150 REPeat demo
160 CLS: PRINT 'seed'!q
170 INPUT '(-/+)32764 Nb ?'!i$: i=i$
180 PRINT 'RaND_01'; TO 11; RaND_01
190 PRINT 'RaND_int';TO 11; RaND_int(i)
200 PRINT 'RaND_to'; TO 11; RaND_to(-i,i)
210 PAUSE 250
220 END REPeat demo
230 :
240 ::::::::::::::::::::::::::
250 DEFine FuNction r(d)
260 LOCal k: REMark random generator:
270 REMark IF d<0 OR d>65537: STOP
280 c=8421: g=65537
290 k=d*c+1: k=k-(INT(k/g)*g)
300 RETurn INT(k)
310 END DEFine
320 ::::
330 DEFine FuNction RaND_01
340 q=r(q): RETurn q/65537
350 END DEFine
360 :
370 DEFine FuNction RaND_int(mo)
380 REMark -65534 / +65536
390 IF mo=0: RETurn 0
400 IF mo<0: mo=mo-2
410 q=r(q): RETurn MOD_(q,mo+1)
420 END DEFine
430 :
440 DEFine FuNction RaND_to(a,b)
450 REMark integer -/+ 32766
460 q=r(q): IF a=b: RETurn a
470 sa=(a>0)-(a<0): sb=(b>0)-(b<0)
480 IF sa+sb=2: RETurn a+MOD_(q,(b-a)+1)
490 IF sa=0 THEN
500 IF sb=0: RETurn 0
510 IF sb=1: RETurn MOD_(q,(b-a)+1)+a
520 END IF
530 IF sa=-1 THEN
540 IF sb=-1: RETurn MOD_(q, b-a+1)+a
550 IF sb=0: RETurn -MOD_(q,-a+1)
560 IF sb=1: RETurn MOD_(q,b-a+1)+a
570 END IF
580 PRINT 'out of range...': STOP
590 END DEFine
600 :
610 DEFine FuNction MOD_(ms,md)
620 REMark calculate even huge MODulus:
630 RETurn ms-(INT(ms/md)*md)
640 END DEFine
650 :
660 ::::::::::::::::::::::::::
670 DEFine FuNction get_r$
680 LOCal q$,d$,i: REMark 0 to 65536
690 IF ql=0
695 REMark PC randomiser
700 q$='0': FOR i=1 TO 5: q$=q$&R$
710 IF q$>'032766': q$=q$/2
720 RETurn q$
730 END IF
735 REMark QL randomiser
740 d$=DATE$:d$=d$(19 TO 20):Ract=Ract+d$
750 BEEP 1,16: RETurn r(Ract)
760 END DEFine
770 :
780 DEFine FuNction R$
790 LOCal rs,kt: REMark PC randomiser:
800 BEEP 1,bc: bc=bc+1: IF bc>24: bc=1
810 REPeat rs
820 FOR kt=1 TO 10
830 IF BEEPING=0: EXIT rs
840 END FOR kt
850 END REPeat rs
860 RETurn '0123456789'(kt)
870 END DEFine
880 :
890 ::::
900 :
910 DEFine PROCedure start
920 CLS: INPUT'QL 1 or Pc 0 ?'!q$
930 IF q$='0' OR q$='1': ELSE GO TO 920
940 ql=0: IF q$=='1': ql=1
950 q=get_r$
960 END DEFine
970 :
980 ::::::::::::::::::::::::::

[bwinkel67]

Hi,
Here is a little program which generates random numbers. First ENTER 'start' before running ...
I have tested this statistically, and the results are good !
Steve Poole.

Below is a simplified form of your Linear Congruent Generator. You are basically doing this as far as I can tell:

seed = (seed * 8421 + 1) MOD 2^16 + 1

You might want to try 65535 which is 2^16 - 1

Code: Select all

10 PRINT "Enter seed? ";
20 INPUT seed
30 FOR i = 1 TO 10: PRINT myRand
40 GO TO 10
50 DEFine FuNction myRand
60   seed = (seed * 8421 + 1)
70   seed = seed - INT(seed / 65537) * 65537
80   RETurn seed
90 END DEFine 

I tried using MOD but it gives a quick overflow error...i.e. I tried having it be:

Code: Select all

60 seed = (seed * 8421 + 1) MOD 65537

To get values between 0 and 1 you just divide myRand by 65537. To test whether it is sufficiently random you can try and plot say every 10th seed on an x/y axis to see if it appears to give you an even distribution of plot points...that's one of the first tests.

The other is to make sure if you run it 65,537 times you never repeat a number more than ones. For that you'd have to set up an array of 65537 values and just fill in each one as you see it with each successive call to rand() and if any array entry is already filled when you hit it then you know you have a smaller cycle and the random number generator is no good.

With regards to randomness, it's such a small cycle of only 16 bits...sometimes it's better to have a bigger cycle to give you more values. Also, 8421 isn't prime, though that doesn't necessarily mean it's a bad multiplier. Did you find it or just choose it (no pun intended) randomly? I couldn't find it associated with a set LGR in Google.

P.S. I completely missed the fact that you had said it is statistically sound so apologies for discussing how to test it above, perhaps you tried some of these already. I will leave it in for others to see how one goes about testing a random number generator.

[bwinkel67]

Cute It runs on QPC2, including the test_bas. Do you intend to do any more work on it for the QL?

BTW, with Steve's random number generator, I tried my formula in CL and realized that I only implemented integer arithmetic in the CL BASIC prototype. So 1 / 2 gives you 0 and not 0.5 and you can't even play with that formula. I did just now try it on the final Macintosh product (run under Basilisk II) and it worked identically to the QL. So I did eventually implement floating point. I think since Digital C is a Small C implementation it doesn't naturally support floating point and you had to use floating point libraries/functions in its place if I recall correctly (Small C was an integer-only version of C). I'll have to compare code bases to see what I added on the Macintosh side. I imagine if CL gets ported to C68 it would be much easier to add floating point.

Also, thinking of putting the source on GitHub, I realize the name CL is kind of boring. Perhaps CLue for "Command Line user environment" or do I need to stick a Q in there somewhere like QLue or Q-CLue? Or perhaps the command shell part isn't as interesting as the BASIC interpreter since the command shell part was never fully implemented, so maybe something with BASIC in it to differentiate with SuperBASIC...that one is tricky since QBASIC is already taken. ClueBASIC sounds weird. I think I know now why I stooped writing software and became a teacher...just finding a good name is a chore :-/

[NormanDunbar]

Mac Shell for QL?
Maybe not!

Cheers,
Norm.