Reply
 
Thread Tools Display Modes
  #1  
Old 08-06-2019, 12:32 PM
Llama Llogophile is online now
Guest
 
Join Date: Apr 2002
Location: 50% chord point
Posts: 4,021

How to get “under the hood” of an old C64 game?


One of my dirty secrets is that I still love to play Commodore 64 games from my youth. I have a good emulator program, and the experience is just like the original except for the hardware.

One of my favorites is Dino Eggs. I’ve become curious about how it was actually programmed. I’d like to find out how certain variables and timed events in the game are determined and executed.

I haven’t delved into computer programming since... well, since doing BASIC on the C64 when I was a kid. So I have no idea what I’m getting into here. Even if I could somehow expose the code, it would probably mean nothing to me. How can I gain an understanding of how the game was programmed and what’s happening when I play?
  #2  
Old 08-06-2019, 12:57 PM
DPRK is offline
Guest
 
Join Date: May 2016
Posts: 3,490
VICE has a debugger/monitor.

On this page there are some 65xx disassemblers. The CPU is pretty simple, but one issue with the Commodore 64 is that many/most games used all kinds of direct hardware access and clever hacks to squeeze every last bit of performance out if this low-end machine. If the game uses some really crazy stuff it might be difficult to understand if one is not used to the machine, but stuff like simple timing that you describe sounds pretty straightforward.
  #3  
Old 08-06-2019, 01:07 PM
Chronos's Avatar
Chronos is online now
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 84,431
There's a fine line between "ingenious hacks" and "incomprehensible spaghetti". And games of that era tended to walk a tightrope down that line. Most modern programmers would probably scream in pain at the code (at least, at the portions they could understand).
  #4  
Old 08-06-2019, 01:22 PM
DPRK is offline
Guest
 
Join Date: May 2016
Posts: 3,490
btw IDA Pro is a good disassembler if you are not averse to commercial software, and there is also a free version.

The first link above (codebase64.org) also lists some of the "ingenious hacks" Chronos mentions. E.g., you're obviously going to use undocumented opcodes, self-modifying code, etc all over the place to shave off a few execution cycles or bytes of RAM.
  #5  
Old 08-06-2019, 01:26 PM
GargoyleWB's Avatar
GargoyleWB is online now
Guest
 
Join Date: Mar 2001
Location: Somewhere cold 'n squishy
Posts: 5,447
Brings back memories of being a little kid. We had a C64 at home and one day my dad was working on some programming thing and remarked that he really wish he had a disassembler. I biked my 8 year-old self down to a local computer store ready to surprise him with the greatest gift ever for father's day. They had one, it was $250.

I got my dad a coffee mug instead.
__________________
"He was shortish. And oldish. And brownish. And mossy. And he spoke with a voice that was sharpish and bossy."
  #6  
Old 08-06-2019, 06:16 PM
RaftPeople is offline
Guest
 
Join Date: Jan 2003
Location: 7-Eleven
Posts: 6,688
Even for an experienced developer of that type of game on that hardware, reverse engineering the code can be a bit challenging and time consuming. If you don't have experience with assembly and interacting with the hardware it will be even tougher.

For example, on the machine I worked on, the analog to digital converters (joystick input) and the digital to analog converters (sound output) were just bytes in memory (special bytes) you either read or write to. If you were looking at the code without any background, you would be wondering by the program seems to update memory location 178 frequently (sound output, 178 is made up because I forgot which byte, it might have been something like 65384).
  #7  
Old 08-07-2019, 07:57 AM
Kobal2's Avatar
Kobal2 is offline
Guest
 
Join Date: Mar 2008
Location: Paris, France
Posts: 18,396
Quote:
Originally Posted by Chronos View Post
There's a fine line between "ingenious hacks" and "incomprehensible spaghetti". And games of that era tended to walk a tightrope down that line. Most modern programmers would probably scream in pain at the code (at least, at the portions they could understand).
Within the ridiculously tight confines of available memory of that era, there was also a thin line between "ingenious hack" and "deep Magic". Which sadly doesn't really seem to exist in our world any more.
  #8  
Old 08-11-2019, 01:24 AM
tavaritz is offline
Guest
 
Join Date: Sep 2011
Location: Helsinki, Finland
Posts: 40
Quote:
Originally Posted by Kobal2 View Post
Within the ridiculously tight confines of available memory of that era, there was also a thin line between "ingenious hack" and "deep Magic". Which sadly doesn't really seem to exist in our world any more.
That's not quite true but the environment where that is still done is robotics ea. selfcontained programmed workunits. They have small memory controllers that you want to squeeze everything out.
  #9  
Old 08-06-2019, 01:12 PM
engineer_comp_geek's Avatar
engineer_comp_geek is online now
Robot Mod in Beta Testing
Moderator
 
Join Date: Mar 2001
Location: Pennsylvania
Posts: 24,507
Quote:
Originally Posted by Llama Llogophile View Post
Even if I could somehow expose the code, it would probably mean nothing to me. How can I gain an understanding of how the game was programmed and what’s happening when I play?
You are probably never going to be able to find the original source code, so the best you can do to see how it was programmed is to disassemble the binary code, like DPRK suggested. Unfortunately, as you note, the end result is likely going to be fairly incomprehensible to you, as the game's original variable names, subroutine names, and source code comments are all long gone.

If you want to really understand how the game was made, you will need to really dig into serious 6502/6510 processors and how they were programmed in assembly, and even then, deciphering the output from a disassembler isn't going to be easy.

You can get the Commodore 64's programmer's reference guide here, which will give you a good idea of what the machine has available inside (warning, pdf):
http://www.classiccmp.org/cini/pdf/C...ce%20Guide.pdf
  #10  
Old 08-06-2019, 06:55 PM
Baron Greenback's Avatar
Baron Greenback is offline
Member
 
Join Date: Jul 2006
Location: Scotland
Posts: 11,785
Quote:
Originally Posted by engineer_comp_geek View Post
You can get the Commodore 64's programmer's reference guide here, which will give you a good idea of what the machine has available inside (warning, pdf):
http://www.classiccmp.org/cini/pdf/C...ce%20Guide.pdf
I had a copy of this when I was a kid. It's an exceptionally good walk-through of the machine - starts with Commodore Basic and how that interacts with the hardware, and then moves on, explaining as it goes. You'll need something like a 64MON cartridge if you've got an actual C64 to play with, or a simulation thereof, if you really want to do the assembly language.

What I'm saying is: don't try to understand decades-old disassembled code that the original developer probably doesn't even have much of of a clue about. Have a go yourself!
  #11  
Old 08-07-2019, 07:12 AM
Thudlow Boink's Avatar
Thudlow Boink is online now
Charter Member
 
Join Date: May 2000
Location: Lincoln, IL
Posts: 27,176
Quote:
Originally Posted by engineer_comp_geek View Post
You can get the Commodore 64's programmer's reference guide here, which will give you a good idea of what the machine has available inside (warning, pdf):
http://www.classiccmp.org/cini/pdf/C...ce%20Guide.pdf
Damn, that brings back memories!
  #12  
Old 08-06-2019, 06:19 PM
Heracles's Avatar
Heracles is offline
Member
 
Join Date: Jul 2009
Location: Southern Québec, Canada
Posts: 1,594
There were such things as unassemblers for the 6502 back then. These would take the raw output from a dumb disassembler and try to substitute the known names for system calls and hardware registers, and assign (random) names to the program's branch points, variables and memory areas. With lots of hours of work, you could eventually end up with a program you could modify and reassemble. Ah! when we have the luxury of time...
  #13  
Old 08-06-2019, 06:52 PM
DPRK is offline
Guest
 
Join Date: May 2016
Posts: 3,490
This blog post by the author (also this one) describes some of the code for Dino Eggs ("My core graphic routine was a central chunk of self-modifying code..."); that's describing the original Apple II version and not the C64 port, but the processors are pretty compatible.

If you just want to see some sample source code, the codebase web site has several small sample games in addition to tutorials on game programming techniques, C64 hardware info, etc. Also http://covertbitops.c64.org/ has a bunch of games along with their source code.
  #14  
Old 08-06-2019, 07:51 PM
Llama Llogophile is online now
Guest
 
Join Date: Apr 2002
Location: 50% chord point
Posts: 4,021
I was out of my depth by around response #3. I don't know from compilers and disassemblers. It's clear this sort of project is well beyond my ability.

Any other way to find out what I'm looking for besides finding the guy who wrote it?
  #15  
Old 08-07-2019, 09:29 AM
bump is offline
Guest
 
Join Date: Jun 2000
Location: Dallas, TX
Posts: 18,086
Quote:
Originally Posted by Llama Llogophile View Post
I was out of my depth by around response #3. I don't know from compilers and disassemblers. It's clear this sort of project is well beyond my ability.

Any other way to find out what I'm looking for besides finding the guy who wrote it?
Basically what most people think of as programming is higher level programming- it deals primarily with concepts and data elements.

However, in the compilation or interpretation process, that gets translated into machine level code, i.e. assembly code. This is about one level above bits and bytes.

So for example, if you were to have a few lines of code like this:

a = b + c // assign a the value of b + c, where b and c are already assigned values.


That translates into a whole raft of assembly

First, you'd have to move the values of B and C into registers out of memory.

Then you'd have to add the two registers together.

Then you'd have to store the result back in memory.


All this is extremely dependent on the actual architecture of the system in question. The flip side is that since it's so low level, you can really optimize it to be fast or small or whatever.

And you can often do stuff that compilers and interpreters don't let you do- like change the code of your program on the fly by rewriting the bits and bytes to change the actual instructions.

A decompiler would basically take the machine language code and try and basically turn it into something a bit more readable and abstract than assembly code. But it's necessarily inexact, because there's not always a 1:1 correspondence between chunks of assembly code and higher level language components.
  #16  
Old 08-07-2019, 11:46 PM
pulykamell is offline
Charter Member
 
Join Date: May 2000
Location: SW Side, Chicago
Posts: 47,682
Quote:
Originally Posted by bump View Post
a = b + c // assign a the value of b + c, where b and c are already assigned values.


That translates into a whole raft of assembly

First, you'd have to move the values of B and C into registers out of memory.

Then you'd have to add the two registers together.

Then you'd have to store the result back in memory.
For something as simple as 8-bit addition with an 8-bit result on a 6502, to give an example for the OP, the code would be something like this. You only need to use the accumulator; the X- and Y-registers aren't needed.

Code:
CLC        // Clear the carry flag
LDA b_var  // Load the accumulator with the contents of memory address b_var
ADC c_var  // Add with carry (to the accumulator) the contents of memory address c_var
STA a_var  // Store the accumulator to memory address a_var
RTS        // Return from subroutine
With a_var, b_var, and c_var being the addresses where the variables a, b, and c are stored.

So, when disassembled, you might see something like:

Code:
CLC
LDA $C102
ADC $C101
STA $C100
RTS
You won't have variable names upon disassembly. All you will see is that the program clears the carry bit, loads the accumulator with the contents of memory $C102, adds to the accumulator contents of memory $C101, and stores the result in memory location $C100. Those memory location need not be those--they can be stored anywhere in available memory, and they don't have to be contiguous. I just pretended we were storing A at $C100, B at $C101, and C at $C102.

So that's part of the tricky part; with the disassembly you see what's going on, but you don't have variable names, you don't have labels, you don't have comments, etc., so you won't necessarily know what memory locations $C100, $C101, and $C102 are being used for. You'll just understand that this routine is adding what's in the latter two memory locations and storing the result in the first location. So by looking at the rest of the disassembly, you'll have to infer what these memory locations are being used for. Is it keeping track of what "room" you are in in the game? Is it the number of enemies on a screen? Is it x- or y- coordinates for a sprite? Etc.

(Note that will only allow you to add two 8-bit numbers and return an 8-bit result. So if you are adding 255 + 1, you will have 0 stored into the memory location where the a_var is. If you want to allow for a 16-bit result, then you have to add a couple of more lines and have a a_variable_low_byte and a_variable_high_byte to store the high and low bytes of the result, and you can figure out whether to assign a 0 or 1 to the high byte by storing the status of the carry flag there. This is not meant to be an exhaustive example, but rather a simple example of what something like A = B + C might look like in 6502 assembly when disassembled, so the OP can get an idea of what they would be getting themselves into were they to undertake the project in the OP.)
  #17  
Old 08-08-2019, 09:59 AM
bump is offline
Guest
 
Join Date: Jun 2000
Location: Dallas, TX
Posts: 18,086
Quote:
Originally Posted by pulykamell View Post
This is not meant to be an exhaustive example, but rather a simple example of what something like A = B + C might look like in 6502 assembly when disassembled, so the OP can get an idea of what they would be getting themselves into were they to undertake the project in the OP.)
Definitely. I was deliberately leaving my assembly example vague; my experience was in college with IBM 360 assembly language, not x86 or anything like that.

But yours is better- you take a simple thing: A= B + C and show what that translates into in assembly.

(BTW; assembly and architecture were the two computer science courses that really hammered home how computers actually work. Prior to that, there was a big element of "below this level, magic happens" for me. But taking those two, I learned how they actually work down low.)
  #18  
Old 08-09-2019, 12:42 AM
sweepkick is offline
Guest
 
Join Date: Nov 2002
Location: Minneapolis, MN
Posts: 485
I remember playing Dino Eggs on my Apple II back in the day. Great game.

The author put up a page of the original assembly code up on his Dino Eggs: Rebirth Facebook page here:

https://www.facebook.com/DinoEggsReb...type=3&theater
  #19  
Old 08-09-2019, 03:44 PM
Hoopy Frood is online now
Guest
 
Join Date: Jan 2001
Location: Chicago, IL
Posts: 4,627
Quote:
Originally Posted by bump View Post
(BTW; assembly and architecture were the two computer science courses that really hammered home how computers actually work. Prior to that, there was a big element of "below this level, magic happens" for me. But taking those two, I learned how they actually work down low.)
Yep. Though, these days not much use to anyone who's not working in hardware, and even then only probably a small percentage.

Even back when I took architecture back in 1997 (the class centered around the MIPS pipeline), the professor said on the first day of class that only about 3% of the students taking the class would ever need to apply what they were about to learn, since at the time the pipeline processing field was saturated as far as job availability went. And this was Computer Engineering, not Computer Science, so I imagine even fewer CS majors would have ever used it.

Our assembler course which I took back in 1996 was based on the Intel 8086. Our professor was cheap and gave us for our development environment Borland Turbo Assembler 1.0 (the version without the debugger). It was free for him, and awful for us. Running a DOS assembler with no sandbox on Windows 95 leads to all sorts of fun. If you're lucky, you just get weird ASCII text on your screen somewhere. If you're unlucky, you BSODed as you accessed something you weren't supposed to. Most of the time you were unlucky. The application we were building was to have multiple (ASCII character-based) Windows that performed various tasks such as a calculator. (The calculator is the only one I can remember.) I remember at one point I don't know what I did, but I drew a blue border around my Desktop wallpaper that didn't go away until the next time my system rebooted. (Which no doubt happened shortly thereafter based on the inherent instability in the whole process of making this application.)

The border itself drew itself by starting at the top center of the screen, and then mirrored itself as it traced the perimeter downward and finished at bottom center of the screen. I was struck with the odd thought that my computer was telling me I was a "square" with its invisible fingers.
  #20  
Old 08-06-2019, 09:06 PM
Baron Greenback's Avatar
Baron Greenback is offline
Member
 
Join Date: Jul 2006
Location: Scotland
Posts: 11,785
Quote:
Originally Posted by Llama Llogophile View Post
I haven’t delved into computer programming since... well, since doing BASIC on the C64 when I was a kid.
Did you ever define a sprite, or muck about with the sound chip? Because if you did then you had a grasp of how the machine architecture works. Those POKES and DATA arrays - they were way closer to the hardware in a way that doesn't just happen these days.
  #21  
Old 08-06-2019, 09:17 PM
DPRK is offline
Guest
 
Join Date: May 2016
Posts: 3,490
If you don't actually care about the source code and it's just a gameplay question, you may as well just ask him [Schroeder].

Hmm, I notice Dino Eggs: Rebirth is out...
  #22  
Old 08-06-2019, 09:53 PM
Llama Llogophile is online now
Guest
 
Join Date: Apr 2002
Location: 50% chord point
Posts: 4,021
Quote:
Originally Posted by DPRK View Post
If you don't actually care about the source code and it's just a gameplay question, you may as well just ask him [Schroeder].

Hmm, I notice Dino Eggs: Rebirth is out...
I actually have corresponded with him a bit a few years back. But I don't think he did the C64 port, so I'd imagine that's the guy I need.
  #23  
Old 08-06-2019, 10:09 PM
Trancephalic is offline
Guest
 
Join Date: Jun 2013
Posts: 902
Have fun.
  #24  
Old 08-06-2019, 11:03 PM
pulykamell is offline
Charter Member
 
Join Date: May 2000
Location: SW Side, Chicago
Posts: 47,682
Quote:
Originally Posted by Trancephalic View Post
Basically, yeah.

It's been many, many years since I've done 6502 assembly and the C64, but what you would need to do is, well, learn 6502 assembly, as well as become intimately familiar with the memory map of the C64 and an understanding of the computer at a very low level. It's not impossible -- that's just what we did in the 80s if we wanted to get beyond slow-ass BASIC and get some arcade-style performance out of the machine. I think it's possible to figure out what's going on without the actual source code, but just the assembly instructions, as you're working with a fairly small memory map and code space here. But if you have no experience at all with 6502 assembly and no idea how the C64s memory addresses are laid out, then, yeah, it's gonna be quite a lot of studying to get up to the level where you can start figuring routines out.
  #25  
Old 08-07-2019, 02:26 AM
blindboyard is offline
Guest
 
Join Date: Jan 2010
Location: Newark
Posts: 2,199
Maybe slightly OT, but a reminder that archive.org has a C64 emulator on their site.
  #26  
Old 08-07-2019, 09:33 AM
Balthisar is offline
Charter Member
 
Join Date: Nov 2000
Location: Southeast Michigan, USA
Posts: 11,187
I'm generally not a nostalgic guy, but this thread is making me nostalgic!

I remember writing neat little hacks in assembler and BASIC for the 64 and 128. I had two or three "Magic Tricks" published in RUN magazine. I wrote a BBS for the 128 that used a bit of relocatable assembler code for things like PETSCII to ASCII conversion, and an iTunes-like SID player. Those were the days.

Aside from games, there was the "demo scene," and those guys really, really knew how to push the hardware. I think these guys still exist, and if they do, I would bet that they have reference materials (even if not catalogued and organizes) to lots and lots of undocumented (by CBM) hardware features. The OP might find himself going down a rabbit hole, but it might be a good start.
  #27  
Old 08-07-2019, 09:37 AM
Chronos's Avatar
Chronos is online now
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 84,431
I don't know if any Deep Magic still exists, but it existed as recently as Quake III Arena.

Though even that is still relatively low-level magic compared to self-modifying code.
  #28  
Old 08-07-2019, 10:02 AM
Kobal2's Avatar
Kobal2 is offline
Guest
 
Join Date: Mar 2008
Location: Paris, France
Posts: 18,396
Quote:
Originally Posted by Chronos View Post
I don't know if any Deep Magic still exists, but it existed as recently as Quake III Arena.
I... wait, how does this... hold on, I think I've got nope I don't got it, how the hell...my brain hurts now, please stop doing that.

Last edited by Kobal2; 08-07-2019 at 10:03 AM.
  #29  
Old 08-09-2019, 07:32 AM
Gorbag is offline
Guest
 
Join Date: Aug 2004
Location: Upstate NY
Posts: 12
Quote:
Originally Posted by Chronos View Post
I don't know if any Deep Magic still exists, but it existed as recently as Quake III Arena.

Though even that is still relatively low-level magic compared to self-modifying code.
I once knew someone who did Mel's trick on old drum-based calculators. Monroe's IIRC. Even reading Knuth there are a number of instances of what, today, would be considered 'bad programming practice.' So remember kids, what you do today will be judged by the politics of tomorrow. You can't win, you can't break even, you can't get out of the game.

As for self-modifying code, in my earlier days device drivers often were self-modifying ij order to be fast enough to keep up and minimize overhead during interrupt cycles. Debugging typically required a logic analyzer to know what was actually going on on the bus. I really hated this at the time, but now I'm pretty nostalgic.

Now we have namby-pamby processors that separate data and instruction (unlike real VonNeumann machines) for "security," so we have to fake it by putting an interpreter in the instruction memory and the program in data memory. Or do incremental compilation with a higher level language (like Lisp) that deals with this nonsense for you. (In Lisp, data is executable by calling 'eval' on it, programs and data are not distinguished as they are both 'lists,' and depending on your implementation, you can redefine even core parts of the language on the fly and have it take effect while the program is running).
  #30  
Old 08-09-2019, 04:17 PM
Voyager's Avatar
Voyager is offline
Charter Member
 
Join Date: Aug 2002
Location: Deep Space
Posts: 46,165
Quote:
Originally Posted by Gorbag View Post
I once knew someone who did Mel's trick on old drum-based calculators. Monroe's IIRC. Even reading Knuth there are a number of instances of what, today, would be considered 'bad programming practice.' So remember kids, what you do today will be judged by the politics of tomorrow. You can't win, you can't break even, you can't get out of the game.
I did Mel's trick in high school on an LGP-21, the later, transistorized, and slower version of the LGP-30 that Mel used. (PDF of the user manual here

With 4K of memory, you almost had to modify your code. I wrote a tic-tac-toe program, and the best way to figure out what the opponent would do in the space available was to change a bunch of add instructions to subtracts. I had an initialization sequence to make sure they were all adds when you started the program. This was in 1969, so don't expect me to remember all the details.
No assembler for that thing. I wrote one myself. No ASCII. No interrupts. It was a great way to learn how to program.
  #31  
Old 08-07-2019, 10:31 AM
Chronos's Avatar
Chronos is online now
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 84,431
Brief summary: A floating-point number is stored in something similar to scientific notation, something times two-to-the-something. The exponent is stored in the first (most significant) few bits. So re-casting a floating point number is (approximately) like taking a logarithm.

Bit-shifting that integer logarithm means dividing it by two, and dividing a log by 2 is equivalent to the square root of the original number. Subtracting the logarithm from something else, meanwhile, is equivalent to taking the inverse of the original number. And then we re-cast it as a float, so our sequence is (approximately) equivalent to 1/sqrt(x).

Now, that approximation isn't quite good enough yet to use it, so we use it to get a better approximation, using Newton's method (a tried and true technique for numerical calculation). The programmer originally wrote in two steps of Newton, but it turns out that one is good enough, so he edited out the second step.

As for that magic number 0x5F3759DF , that depends on the precise details of floating-point representation (how many bits are used for each part). Naively, the magic number "should" be sqrt(2^127). The magic number actually used is close to that, but not exactly equal. It turns out that, while sqrt(2^127) would be better for the first approximation, the actual number used is slightly better than it after one Newton step.
  #32  
Old 08-07-2019, 10:52 AM
Kobal2's Avatar
Kobal2 is offline
Guest
 
Join Date: Mar 2008
Location: Paris, France
Posts: 18,396
I SAID STOP MAKING MY MEAT HURT !
Please. Let's just collectively agree on the "it's Magic" explanation.

Last edited by Kobal2; 08-07-2019 at 10:54 AM.
  #33  
Old 08-07-2019, 11:23 AM
Chronos's Avatar
Chronos is online now
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 84,431
You think with... meat?
  #34  
Old 08-07-2019, 11:30 AM
Kobal2's Avatar
Kobal2 is offline
Guest
 
Join Date: Mar 2008
Location: Paris, France
Posts: 18,396
Speak with it, too.
  #35  
Old 08-07-2019, 11:44 AM
DPRK is offline
Guest
 
Join Date: May 2016
Posts: 3,490
Ain't no floating point on a 6502 processor, though. What you did have, if the user was rich enough to spring for a Commodore floppy drive, was a perfectly good second processor...
  #36  
Old 08-10-2019, 12:42 PM
Chronos's Avatar
Chronos is online now
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 84,431
Of course, once any one programmer figured out a clever and efficient multiplication routine, all other programmers could then use it without needing to fully understand it, either through calling it from a library or copying and pasting it. Though you might need to understand the performance of the routine: One can imagine a routine that's much faster but of limited precision, or one that's only good for a certain range of values, or the like.
  #37  
Old 08-10-2019, 01:55 PM
engineer_comp_geek's Avatar
engineer_comp_geek is online now
Robot Mod in Beta Testing
Moderator
 
Join Date: Mar 2001
Location: Pennsylvania
Posts: 24,507
Quote:
Originally Posted by Chronos View Post
Of course, once any one programmer figured out a clever and efficient multiplication routine, all other programmers could then use it without needing to fully understand it, either through calling it from a library or copying and pasting it. Though you might need to understand the performance of the routine: One can imagine a routine that's much faster but of limited precision, or one that's only good for a certain range of values, or the like.
Back in the day, if you needed a general purpose multiply or divide, most people used some variant of Booth's algorithm, which is basically just breaking down multiplication or division into a series of add/subtract and shift instructions. It's a bit CPU intensive since an 8 bit x 8 bit multiply or divide requires 8 passes through the add/subtract and shift loop, but a lot of early CPUs that had multiply and divide instructions did basically the same thing internally.

While Booth's algorithm requires a lot of looping, it has the advantages of being both compact and easy to understand.
  #38  
Old 08-10-2019, 02:14 PM
DPRK is offline
Guest
 
Join Date: May 2016
Posts: 3,490
The software routines linked to above, which trade space for time by using a pre-computed table of squares, seem to run slightly faster. I guess it depends what your constraints are. Similar issues arise with the Z80.
  #39  
Old 08-12-2019, 10:38 AM
Kevbo is offline
Guest
 
Join Date: May 2005
Posts: 5,902
Quote:
Originally Posted by engineer_comp_geek View Post
While Booth's algorithm requires a lot of looping, it has the advantages of being both compact and easy to understand.
In case anyone gets the bright idea of unrolling those loops:

Since the early processors were not pipelined, nor cached, unrolling those loops doesn't help much. (saves a little time, but memory was sparse back then, so was seldom done.)
__________________
-Never tell a politician they are a two-bit whore, unless you want to be beaten silly with their bag of quarters.
  #40  
Old 08-11-2019, 02:15 AM
tavaritz is offline
Guest
 
Join Date: Sep 2011
Location: Helsinki, Finland
Posts: 40
I had C64 way back when and there was a dedicated magazine published in England (I'm a finn) that I subscribed. It had program listings that one could key in and execute and get somthing nifty. Most were simple games and one was an adventure game. I was baffled why would anyone publish an adventure game to key in when in keying in you read all the text in the game and know exactly what you need to do. Btw. these were all in C64 Basic.

So I wrote an adveture game that only had this big array and and an interpretter. All the code and data of the game was in that huge array of numbers and the interpretter was very stripped down Forth-interpretter that executed that array. They published it and in the next number I got lists of asks to publish how to write the games for my interpretter and I complied and others start to publish their games using the same interpretter. Fun times.
  #41  
Old 08-12-2019, 12:23 PM
Chronos's Avatar
Chronos is online now
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 84,431
Isn't Booth's algorithm basically just the binary equivalent of the method grade schoolers are taught for multiplying with pencil and paper?
  #42  
Old 08-12-2019, 12:44 PM
ftg's Avatar
ftg is online now
Guest
 
Join Date: Feb 2001
Location: Not the PNW :-(
Posts: 19,853
Quote:
Originally Posted by Chronos View Post
Isn't Booth's algorithm basically just the binary equivalent of the method grade schoolers are taught for multiplying with pencil and paper?
It's a bit more complicated. It looks at two bits at a time and does one of four things during a step. But then it shifts only 1 bit for the next step.

It relies on properties of 2's complement numbers.

Me, I prefer the Wallace tree multiplier. Much faster. You just need a lot of gates, but still sub quadratic.
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 03:37 PM.

Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, vBulletin Solutions, Inc.

Send questions for Cecil Adams to: cecil@straightdope.com

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope!
(Your direct line to thousands of the smartest, hippest people on the planet, plus a few total dipsticks.)

Copyright © 2018 STM Reader, LLC.

 
Copyright © 2017