Turing Welchman Bombe in BASIC

[Simon]

I thought people here might be interested in this. I finally got a (simplified) version of the Turing Welchman Bombe running on my Orwell computer. I did a massive, rambling write up (with an equally rambling YouTube film) here: http://www.asciimation.co.nz/bb/

The BASIC code was just to see if my algorithm is correct. As far as I can tell it is but I don't guarantee it! It is hard coded to run the same menu they use at Bletchley Park on their real Bombe and my code does generate the same stops.

Unfortunately on Orwell it is incredibly slow! I figure it will take Orwell 4.8 months to do one Bombe run (which takes the real one 20 minutes). Currently I have had it running for 72 hours and 38 minutes and I am up to GMZ (it starts at AZZ and the letters go backwards, left most first).

My aim now is to make a desktop physical model of the actual Bombe with just the three indicator drums. I have ported to the code to C and it does a whole run in about 10 seconds on my laptop. The idea is to run it on a Rasp Pi 2 and make the model run the same speed as the real Bombe.

I've prototyped the hardware to do this, basically three steppers controlled by an Arduino. Next step it to get the code running in the Pi and get the Pi talking to the hardware.

Feel free to take the BASIC code and do what you like with it. Orwell runs modified MS BASIC so it will run on any machine running something similar without much modification needed. You can run it on an Apple 2 by changing (or deleting!) one line! I actually want to try ti on a real Apple 2 just out of interest and a friend has one lined up for me to do that. In the mean time you can use the online Javascript version here: http://www.calormen.com/jsbasic/

This code isn't optimized or pretty. I have no idea if my method is the best way. It's just the way I figured out to make it work. I am just pleased it does! Be interesting to see if it will run on other people's machines.

Simon

[BigEd]

I'll have a look at this! Edit: OK, that's brilliant, and with a most excellent writeup too!

The Bombe is a great example of appropriate use of technology: it's a steering-logic machine, more or less, and an extreme parallel processor. Mechanically it connects up a network, and then electrically it determines if the network is connected or not. That second step works because electrical connections are bidirectional, and that means that an efficient FPGA implementation is by no means straightforward - let alone a software implementation!

[Simon]

Thanks! I actually got that wrong in my version at first, the fact that current goes both ways! I was thinking purely software and iterating in a loop and thinking where do I need to send to current next. In some cases I wasn't sending the current in both directions. The interesting thing is that mostly works and it would still give you the same stops. But I also got other false stops because I hadn't sent the current everywhere. Once I realised that it was a simple software change to fix it.

What the Bombe does mechanically/electrically in a fraction of a second takes a computer many, many iterations to achieve the same result. Maybe it's possible to come up with a much more efficient way to do it?

Simon

[Simon]

Oops, I noticed some small bugs in the debug printing in the BASIC listing. I have fixed those now.

Simon

[barrym95838]

I can't say that I understand it well, but it looks pretty neat!

I wonder if it would be on the edge of possible to translate your very well-commented and highly-structured BASIC algorithm to hand-optimized assembly (with the whole bag of speed tricks thrown in) and get it down to the 20 minute ballpark on a 1 MHz 6502. Perhaps a version that's a bit less verbose at run-time, or at least one that avoids scrolling the text screen ... I dunno. I'm not brave enough to attempt it right now, but I might stumble across a burst of bravery someday soon.

Mike B.

[BigEd]

Direct link to the post about the BASIC code, including the code itself:
http://www.asciimation.co.nz/bb/2015/06 ... basic-code

My first thought was to try to use a faster basic, and then of course to run on a faster machine. And then to start optimising! This is probably where most of the execution time is spent:

Code: Select all

4000 REM ---------- Diagonal board subroutine ----------
4010 IF DB(ASC(L1$) - 65, ASC(L2$) - 65) = 0 THEN GOSUB 4100
4020 IF L1$ = L2$ THEN GOTO 4050
4030 T$ = L1$ : L1$ = L2$: L2$ = T$
4040 IF DB(ASC(L1$) - 65, ASC(L2$) - 65) = 0 THEN GOSUB 4100
4050 RETURN

4100 REM ---------- Set value subroutine ---------- 
4120 FOR I2 = 0 TO ML 
4130 IF L1$ = ML$(I2) THEN GOTO 4200
4140 NEXT I2
4150 DB(ASC(L1$) - 65, ASC(L2$) - 65) = 2
4160 RETURN
4200 DB(ASC(L1$) - 65, ASC(L2$) - 65) = -1
4205 UT = UT + 1
4210 RETURN

Of course Simon is right to wonder if there's a superior algorithm - a more efficient algorithm will usually beat mere code improvement.

In BBC Basic it's easy to use indexed byte accesses instead of arrays, and that can help. We can remove the repeated ASC() calls and in-line the subroutines too. But that FOR loop might be the bottleneck. Are there any BASICs with profiling support?

[Simon]

Optimising has never been my strong point! I am sure there are loads of improvements that can be made. I am a coding workman, not a craftsman Actually part of my job is writing test code for things and often that's an advantage!

There are a few small things I did in this though. The main one was making the arrays of the rotors double ended. I initially had one array for each rotor. Going through in the 'forward' direction was no problem. Just use the index and get the value. But going back meant scanning the array to find the matching entry then returning the matching index. Horribly slow! Hence the arrays I have now. When I go in the 'backwards' direction I just add on as fixed offset to the index and use that as before.

I actually wrote a little BASIC program to generate the reverse bit of the array to avoid any typos in them which would be tricky to trace down!

Any printing to the screen is incredibly slow. Especially on Orwell. It takes forever to draw the diagonal board for example.

My ASM wouldn't be strong enough to port it to that very easily. I could probably do it given a lot of time. I find my brain gets easily tangled by offsets and array indexing and so on. Should be simple but it always trips me up. Dealing with circular arrays with various offsets that have to be applied in the right directions always takes me a while to get right.

It's a great project. Am really enjoying working on it. It's not exactly mass appeal though. You have to be pretty interested in it all (or just bonkers) to put in all the effort to understand the thing and even then I am not sure it's really useful for anything. But I think it's good someone takes the time to appreciate what they did back then.

Simon

[Dr Jefyll]

Simon wrote:

It's not exactly mass appeal though. You have to be pretty interested in it all (or just bonkers) to put in all the effort to understand the thing

That may be true in regard to the technical details, but if you take several steps back and look at the context what you see is a story more genuine and dramatic than any you're likely to see on a movie screen.

Simon wrote:

But I think it's good someone takes the time to appreciate what they did back then.

I found it deeply thought-provoking. In fact I got a little carried away, reading on Wikipedia about WWII and submarine warfare and the desperate importance of countermeasures to Enigma. And while the team at Bletchley Park fought using their brains, their success hinged in part on the efforts of others who faced dire personal peril:

en.wikipedia.org/wiki/Tommy_Brown_(GM) wrote:

Lieutenant Francis Anthony Blair Fasson and Able Seaman Colin Grazier dived into the sea and swam to the [captured German] submarine, with Brown following them over.[4] The German crew had opened the boat's seacocks, and water was pouring into the vessel.[4] The two Navy men made their way into the captain's cabin where Fasson found a set of keys. They unlocked drawers[5] and found two code books: the Short Weather Cipher and Short Signal Book.[3] Brown carried these documents up the iron ladder of the U-boat's conning tower to Petard's whaler, climbing with one hand while holding the documents in the other. After his third trip down and up the ladder, he called for his shipmates to get out of the boat, but the submarine sank before they could escape.

And the drama involving Turing didn't stop when the war ended. https://en.wikipedia.org/wiki/Alan_Turi ... and_pardon

I'm very glad to hear about your project, Simon. Have you ever daydreamed about traveling back in time and introducing your Orwell computer to the Bletchley Park lot? Congratulations, and thanks for telling us about it.

-- Jeff

[Michael]

Hi Simon,

Another fantastic effort and a wonderful example of forensic computer archaeology. Bravo Sir!

Having spent several weeks doing research and several days coding last August to come up with Enigma algorithms for a little PIC microcontroller, I can't imagine the effort required to understand and simulate the Bombe. My Enigma algorithms used two constant arrays for each rotor, that is, one array for data moving each way through the rotor (see code excerpt below).

I look forward to following your progress, Sir...

Cheerful regards, Mike

Code: Select all

;******************************************************************
;
;  the first 26 byte table for each rotor is for entering the
;  rotor from the right side (the input side) and the second
;  26 byte table is for entering the rotor from the left (the
;  reflector) side.
;
;       index   00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
;       index    A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
;               -----------------------------------------------------------------------------
;
;  1930 Enigma I
;
ROT1    db       4,10,12, 5,11, 6, 3,16,21,25,13,19,14,22,24, 7,23,20,18,15, 0, 8, 1,17, 2, 9
;                E  K  M  F  L  G  D  Q  V  Z  N  T  O  W  Y  H  X  U  S  P  A  I  B  R  C  J
RET1    db      20,22,24, 6, 0, 3, 5,15,21,25, 1, 4, 2,10,12,19, 7,23,18,11,17, 8,13,16,14, 9
;                U  W  Y  G  A  D  F  P  V  Z  B  E  C  K  M  T  H  X  S  L  R  I  N  Q  O  J
;
;  1930 Enigma I
;
ROT2    db       0, 9, 3,10,18, 8,17,20,23, 1,11, 7,22,19,12, 2,16, 6,25,13,15,24, 5,21,14, 4
;                A  J  D  K  S  I  R  U  X  B  L  H  W  T  M  C  Q  G  Z  N  P  Y  F  V  O  E
RET2    db       0, 9,15, 2,25,22,17,11, 5, 1, 3,10,14,19,24,20,16, 6, 4,13, 7,23,12, 8,21,18
;                A  J  P  C  Z  W  R  L  F  B  D  K  O  T  Y  U  Q  G  E  N  H  X  M  I  V  S
;
;  1930 Enigma I
;
ROT3    db       1, 3, 5, 7, 9,11, 2,15,17,19,23,21,25,13,24, 4, 8,22, 6, 0,10,12,20,18,16,14
;                B  D  F  H  J  L  C  P  R  T  X  V  Z  N  Y  E  I  W  G  A  K  M  U  S  Q  0
RET3    db      19, 0, 6, 1,15, 2,18, 3,16, 4,20, 5,21,13,25, 7,24, 8,23, 9,22,11,17,10,14,12
;                T  A  G  B  P  C  S  D  Q  E  U  F  V  N  Z  H  Y  I  X  J  W  L  R  K  O  M
;
;  DEC 1938, M3 Army
;
ROT4    db       4,18,14,21,15,25, 9, 0,24,16,20, 8,17, 7,23,11,13, 5,19, 6,10, 3, 2,12,22, 1
;                E  S  O  V  P  Z  J  A  Y  Q  U  I  R  H  X  L  N  F  T  G  K  D  C  M  W  B
RET4    db       7,25,22,21, 0,17,19,13,11, 6,20,15,23,16, 2, 4, 9,12, 1,18,10, 3,24,14, 8, 5
;                H  Z  W  V  A  R  T  N  L  G  U  P  X  Q  C  E  J  M  B  S  K  D  Y  O  I  F
;
;  DEC 1938, M3 Army
;
ROT5    db      21,25, 1,17, 6, 8,19,24,20,15,18, 3,13, 7,11,23, 0,22,12, 9,16,14, 5, 4, 2,10
;                V  Z  B  R  G  I  T  Y  U  P  S  D  N  H  L  X  A  W  M  J  Q  O  F  E  C  K
RET5    db      16, 2,24,11,23,22, 4,13, 5,19,25,14,18,12,21, 9,20, 3,10, 6, 8, 0,17,15, 7, 1
;                Q  C  Y  L  X  W  E  N  F  T  Z  O  S  M  V  J  U  D  K  G  I  A  R  P  H  B
;
;       index   00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
;       index    A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
;               -----------------------------------------------------------------------------
;
;  1939 M3 & M4 Naval (FEB 1942)
;
ROT6    db       9,15, 6,21,14,20,12, 5,24,16, 1, 4,13, 7,25,17, 3,10, 0,18,23,11, 8, 2,19,22

[Simon]

Whatever you do don't watch the film U-571. It's meant to be a historical drama but they went more for drama than history!

http://www.theguardian.com/film/2009/fe ... el-history

Simon

[BigDumbDinosaur]

Simon wrote:

Whatever you do don't watch the film U-571. It's meant to be a historical drama but they went more for drama than history!

In fact, any resemblance to reality in that film was 100 percent accidental. No wonder Tony Blair gave it two thumbs-down. I wouldn't go so far as to call U-571 the worst war movie ever, but it's a pretty sad specimen.

[BigEd]

Similarly, Simon links to a detailed takedown of the recent Imitation Game. Although that film does seem to have reached a number of people who (still) had no idea of Turing as a great figure of the century, so that's worthwhile. The campaign to get him on the back of the £10 note failed - Jane Austen won instead. (We have at least had some scientific people: Stephenson, Nightingale, Faraday, Smith, Wren, Boulton, Watt, Darwin, Newton. No Babbage or Brunel as yet.)

[Simon]

BigEd wrote:

Similarly, Simon links to a detailed takedown of the recent Imitation Game. Although that film does seem to have reached a number of people who (still) had no idea of Turing as a great figure of the century, so that's worthwhile. The campaign to get him on the back of the £10 note failed - Jane Austen won instead. (We have at least had some scientific people: Stephenson, Nightingale, Faraday, Smith, Wren, Boulton, Watt, Darwin, Newton. No Babbage or Brunel as yet.)

I hated that film the first time I saw it. That was before I knew all the details and even then I knew it was all wrong. It was that that made me so determined to learn more. I've probably gone a little too far down that path now I know people always say with these kind of 'historical' films do encourage a few people to go find out the real details but I wonder if they sometimes do more harm by creating false histories in more people's minds. For every one person who looks up the actual history there are now 10 more who think it happened like in the film.

I don't find the film as annoying now. I just treat it as entertainment. And I spot new mistakes every time I watch it.

It did help raise awareness of Bletchley Park which is definitely a good thing.

I didn't know about the banknote thing.

Simon

[Simon]

Sorry to dig up an old thread but this might be of interest to people here.

I finally finished my own desktop sized Turing-Welchman Bombe. It doesn't have a 6502 in it of course (Raspberry Pi 2 and an Arduino!) but it is using the same algorithm I wrote in BASIC on my Orwell 6502 computer.

http://www.asciimation.co.nz/bb/2015/10 ... -completed

Simon

[BigEd]

Great work!