Disassembling Jak and Daxter | Hacker News Reader

Disassembling Jak and Daxter

codersnotes.com

180 pointskayamon32 comments

"GOAL never had a source-line debugger, as far as I know, although there's no reason it couldn't given some effort to write one."

Actually, it did. IIRC, the debug state required for converting run-time addresses to source lines was persisted in the compiler (which was a REPL, not a one-shot process like C), rather than exported in the form of symbols. The interface was pretty sketchy, but I'd say it was about as usable as GDB. You could set breakpoints, inspect registers, etc...

A lot of debugging was "live" though - since all the code was hot-loadable, you could just insert a debug print in the middle of a function on the fly. It was a really nice, iterative way to work.

Oh cool, I wondered if ND ever went to the trouble to write one or not. Thanks :)

Since the entire thing was hot-loadable, how was the game linked, did every function call go through a indirection, or did you potentially re-link the entire program if the new function couldn't fit at the address of the old one?

> did every function call go through a indirection

Yes.

I wonder if that would still be an acceptable trade-off with high-performance games on modern memory architectures.

My suspicion is "yes" -- the PS2 wasn't great at memory access, and modern CPU tend to have better caching/branch prediction anyway.

No need to wonder. That is exactly how C++ vtables work.

For virtual functions. Not all calls get an indirection. At least with any respectable compiler..

Right, and how many game developers are recommending to "never use virtual functions because they are slow" in 2017? I remember seeing statements like that in Usenet posts and articles from the 1990s.

https://shaneenishry.com/blog/2014/12/27/misconceptions-of-c... is from 2014. I tend to think it might actually make a difference in this case given it's a vtable indirection for every entity every frame (or for every subsystem * every subsystem tick).

Also, "never use virtual functions" is very different than "don't use virtual functions everywhere" Common wisdom is that virtual function usage in hot loops can become problematic.

Yeah, and in C++ one also avoids vtables when possible.

I have such immense respect for the kind of people that made GOAL. From the powerpoint, it states that it was made by one developer over a year-ish, and solely supported it through the development of Jak and Daxter.

It's the kind of confidence like that, in a very aggressive market, where delays are killer, but knowing that you can make a tool that would help make an even better product.

Apparently the team had difficulty picking it up and using it for a while, and lots of issues that would run the development machines into the ground. Through all that, they still produced a very refined and high quality product on a tight deadline.

Anecdotally, introducing Angular to a group of seasoned developers, more experienced in RPG and JCL than anything web-wise, over the course of a month was enough to lose sleep on. Heavy respect for that developer and the team as a whole.

The first Jak game I played was Jak II. It blew my God-damned mind. Completely smooth world transitions, completely smooth character and facial animations... and AUTO-SAVE. I used to tell my buddies "they could do auto-save because they wrote a custom threading system using coroutines -- in Lisp! -- that interleaved memory card I/O with the main engine in a way that C++ just couldn't do at the time!" They didn't understand, but oh well. Lisp had saved me from putting up with the game grinding gameplay to a halt while it was "Saving. Do not remove the MEMORY CARD (8MB) (for PlayStation® 2) or turn off the power."

Interesting read! If you want to read more about the programming of Jak & Dexter, as well as its predecessor Crash Bandicoot, check out Andy Gavin's awesome blog: http://all-things-andy-gavin.com/2011/03/12/making-crash-ban...

A while ago he gave me the manuals to GOALENV and GOALASM, but not the right to post them. Hopefully it's long enough ago now he'd be willing to make them public!

Alas, I suspect it's up to Sony whether these things get published :(

You should ask him.

I'd love to see those. It's worth an ask I figure.

I don't work at Naughty Dog, and I don't have any secret knowledge of Jak & Daxter, except what I figured out myself from the disc. So a lot of this may well be wrong. Take a pinch of salt with it.

Isn't there an HN regular who did work at Naughty Dog, at least in the Crash Bandicoot days? Was he still around by the J&D days to fact-check?

I know of at least a couple of ex-dogs who lurk around here. The article's pretty much correct, if memory serves.

I started at ND in 2004, around the tail-end of Jak 3. After Andy had left, I picked up the Goal compiler, and hacked it around to generate code for the PSP. After about a week or two, we had the kernel booting, and hot-patching working. We built a whole engine that looked amazing, but unfortunately the project was shelved. Still, it was some of the most fun I've had in my career.

Why was it shelved?

Afaik they rewrote their engine for better threaded workflows for the ps3

We had to shift focus to the PS3 project, which needed everyone's full attention.

This is basically the reason I visit HN at least once every day. What a fantastic article. Like the author, I've always had a fascination with ND games and especially the Jak & Daxter series (a fascination which only augmented when I learned how much of them was coded in a Scheme and I understood what that meant). Unlike the author, I've never had the perseverance or chops to disassemble the game like this. Props, and thank you!

I worked at Naughty Dog, shipped Crash Team Racing and worked for 6 months on Jak & Daxter.

These are my understandings. If someone there as different recollections I'm happy to be corrected.

The LOD system in Jak & Daxter was based on / inspired by the LOD system in Crash Team Racing written by Danny Chan. The easiest way to explain that system is to imagine a cube with 8 vertices. Subdivide it so it's got 9 quads per face using 48 vertices. Let the artists move the vertices wherever they want. The close up LOD is the full 48 vertices, the far LOD is the 8 vertices. At some distance between the 2 the 48 are interpolated until they match the 8 so there's no popping. You can see this happen in CTR pretty easily if you play the Coco Park track. If you can manage to keep the purple pillars on the left in view you'll see them morph. Unfortunately this video doesn't keep them in view but it shows the pillars I'm referring to

https://www.youtube.com/watch?v=StURmtwJfLk#t=6m30s

Hiding the morph or rather building things that don't appear to morph was a skill the artists learned as they progressed. Jak & Daxter you don't see it much. The first Ratchet & Clank which uses the same tech from Naughty Dog you see it quite often as their artists were new to the technique.

As for GOAL it was my first experience writing a large amount of LISP. Before that I only wrote a few emacs macros. Things I took away from it

* Having your own compiler can be a huge benefit

Whether or not LISP itself is awesome many of the benefits were because we had our own compiler anything we wanted could be added. Live reloading of functions is not impossible in other languages if you have your own compiler.

Another simple example you could specify the byte offsets of fields of structs. As a game programmer that seemed awesome compared to C where you just had to go through contortions and add padding and pray.

* Having a full language for macros is amazing

I'm still surprised so few other languages have this. LISP lets you use the entire language at compile time. Query a database, read a file, emit code. In C/C++ most people use python to generate code in my experience. C++ has the template system but it's arguably not designed to do the things people make it do. In fact I'm surprised there aren't more transpilers from some reasonable language to C++ template meta programming. Even if that was popular though C++ templates can't read files or query databases at compile time.

As one tiny example I designed a particle system. There was an init structure listing all the parameters for particles. To be efficient it needed the list of be in the same order as the fields in memory. The macros I wrote would take an unsorted list and sort at compile time, filling out any missing parameters with defaults so the code that emits a particle would walk straight forward, no conditionals, cache friendly.

In any case I'm still waiting for a mainstream language to offer this

* Having a REPL into the game is cool

You could almost think of working on Jak & Daxter like opening up an webpage in your browser's devtools. A REPL at the bottom you can start inspecting things, changing variables, even more you could replace functions. The whole thing ran inside emacs. You could open a file, put your cursor in some function and press some hotkey to compile just that function live and patch it into the running game. This was better than say Unity in that Unity serializes the entire game, compiles everything, then deserializes back where as GOAL would just compile that one function.

* No 3rd party libraries

I'm not sure this was important back then but nowadays with so much open source and commercial libraries to help make a game it was a problem that the GOAL environment was not really conducive to using any 3rd party code since that would have been in C/C++

* No Visual Studio quality debugger

I've been on lots of projects without a good debugger and it's always been frustrating. Writing your own language from scratch probably means no good source level debugger. From the REPL you could set breakpoints and step through code but it was like using gdb. Sure I get by but not nearly as fast as a real debugger with watches, various panes showing live memory, live variables, conditional breakpoints, etc...

Maybe now a days you could easily make a web based backend or abuse the browser devtools with source maps and remote debugging protocol or something to get a good debugger with low effort?

* Slow Dev system

This might have been a problem that was fixed but when I left you'd start up the game and wait several minutes as in like 10 or maybe even 20 before you could play. The entire AST for the code would be put into GOAL and then the game would be running. If the game crashed you'd get a message in the REPL. Andy Gavin, the guy that created GOAL would look at the message, see the issue, type some magic incantation, and the game would come back instantly. For me though who didn't have a mental image of how the entire system worked most of the time I just had to reboot and wait the 10-20 minutes.

How that was eventually solved I have no idea. Maybe all the programmers internalized the system and could do the same magic that Andy could do. Or maybe Andy found a way to make the system start up faster.

I'd be curious to know the answer.

Of course this was offset by being able to live edit functions for fast iteration.

* LISP can be fast

There's nothing inherently slow about LISP. Maybe most impls are not fast but GOAL was. Jak & Daxter has some of the largest worlds, with the most polygons on the screen and it runs at 60fps on PS2 where as most other games on PS2 run at 30fps or less and far less polygons. That includes whatever garbage collection it used (I honestly don't remember what it did there). In other words, whatever assumptions I had about higher level languages and/or garbage collection being bad for game dev were mostly proven wrong.

> There's nothing inherently slow about LISP.

> In other words, whatever assumptions I had about higher level languages and/or garbage collection being bad for game dev were mostly proven wrong.

I'm afraid I have to disagree on that point. GOAL is not LISP -- it just looks a bit like it, and draws a lot of ideas from it. However, LISP is ultimately dynamically typed, while GOAL is statically typed. This means the compiler can generate fast code ahead of time, LISP can't.

GOAL also does not use runtime garbage collection in the same way a LISP system does.

Yeah, the runtime for GOAL was much closer to C/C++ than LISP. The pre-processor was pretty much a full Scheme implementation, and had all kinds of dynamic cons cell allocations and garbage collection, but not the generated code itself.

(In fact, C and GOAL code almost used the same ABI. IIRC, GOAL always had the GP(?) register pointing at the symbol table for fast access, but gcc MIPS code expected it to be something else. If you wanted to be able to call back and forth, you had to write tiny shim functions).

> However, LISP is ultimately dynamically typed, while GOAL is statically typed. This means the compiler can generate fast code ahead of time, LISP can't.

LISP (of 1958) can't, but Lisp can. Optimizing compilers for Lisp were invented decades ago.

Surprise: Common Lisp has types and type declarations since day one (1984). The type system is not what you would expect from, say, Haskell. But it allows the developer to define and specify types.

Additionally one can set optimization policies (debug, space, safety, ...), declare functions to be compiled inline or request to have data stack allocated. And so on...

Compilers which take advantage of type declarations and type inference to create optimized code exist also since that time.

See the Common Lisp Hyperspec chapter on types:

http://www.lispworks.com/documentation/HyperSpec/Body/04_.ht...

> GOAL also does not use runtime garbage collection in the same way a LISP system does.

There are several Lisp systems which do similar things (manual memory management) like GOAL. Mostly they were/are used to develop certain types of applications - like GOAL.

Let's see how sbcl, ( http://sbcl.org ) handles types at compile time: it clearly identifies and describes where it has not enough information for best optimization.

    (declaim (optimize (speed 3) (debug 0)))

    ; a TYPE declaration

    (deftype somebyte ()
      `(integer 0 255))

    ; an untyped function

    (defun add1 (a b)
      (+ a b))

    ; declararing the types of function ADD2
    ; but one argument remains of general type. 
    ; arguments are of type SOMEBYTE and T.
    ; T is the most general type.
    ; Return value has type SOMEBYTE.

    (declaim (ftype (function (somebyte t) somebyte)
                    add2))

    (defun add2 (a b)
      (+ a b))


    ; declararing the types of function ADD3

    (declaim (ftype (function (somebyte somebyte) somebyte)
                    add3))

    (defun add3 (a b)
      (+ a b))

You can now see what the LISP (sic!) compiler says, when it can't optimize the code:

    * (compile-file "/tmp/test.lisp")

    ; compiling file "/private/tmp/test.lisp" (written 13 JAN 2017 09:15:03 AM):
    ; compiling (DECLAIM (OPTIMIZE # ...))
    ; compiling (DEFTYPE SOMEBYTE ...)
    ; compiling (DEFUN ADD1 ...)
    ; file: /private/tmp/test.lisp
    ; in: DEFUN ADD1
    ;     (+ A B)
    ;
    ; note: forced to do GENERIC-+ (cost 10)
    ;       unable to do inline float arithmetic (cost 2) because:
    ;       The first argument is a T, not a DOUBLE-FLOAT.
    ;       The second argument is a T, not a DOUBLE-FLOAT.
    ;       The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES DOUBLE-FLOAT
    ;                                                                &REST T).
    ;       unable to do inline float arithmetic (cost 2) because:
    ;       The first argument is a T, not a SINGLE-FLOAT.
    ;       The second argument is a T, not a SINGLE-FLOAT.
    ;       The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES SINGLE-FLOAT
    ;                                                                &REST T).
    ;       etc.

    ; compiling (DECLAIM (FTYPE # ...))
    ; compiling (DEFUN ADD2 ...)
    ; file: /private/tmp/test.lisp
    ; in: DEFUN ADD2
    ;     (+ A B)
    ;
    ; note: forced to do GENERIC-+ (cost 10)
    ;       unable to do inline fixnum arithmetic (cost 2) because:
    ;       The second argument is a T, not a FIXNUM.
    ;       The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES FIXNUM &REST T).
    ;       unable to do inline (signed-byte 64) arithmetic (cost 5) because:
    ;       The second argument is a T, not a (SIGNED-BYTE 64).
    ;       The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES (SIGNED-BYTE 64)
    ;                                                                &REST T).
    ;       etc.

    ; compiling (DECLAIM (FTYPE # ...))
    ; compiling (DEFUN ADD3 ...);
    ; compilation unit finished
    ;   printed 2 notes


    ; /tmp/test.fasl written
    ; compilation finished in 0:00:00.030
    #P"/private/tmp/test.fasl"
    NIL
    NIL

It might also be interesting for readers to see what the resulting code is from these three functions.

I recompiled your code with SAFETY 0 and here is the result. This example also shows off how you can look at the disassembly of any function directly from the REPL.

First, ADD1. Since the compiler doesn't know anything about the types (the arguments could be floating points numbers, rationals, bignums or any other type) so it will simply call the GENERIC-+ function which does all of this. Needless to say, it's much slower than a native addition.

    CL-USER> (disassemble #'add1)
    ; disassembly for ADD1
    ; Size: 14 bytes. Origin: #x2291202A
    ; 2A:       488BD1           MOV RDX, RCX                     ; no-arg-parsing entry point
    ; 2D:       E86EE26EFD       CALL #x200002A0                  ; GENERIC-+
    ; 32:       488BE5           MOV RSP, RBP
    ; 35:       F8               CLC
    ; 36:       5D               POP RBP
    ; 37:       C3               RET

The function ADD2 still has unknown types, so there is not much the compiler can do but to call GENERIC-+ in this case.

    CL-USER> (disassemble #'add2)
    ; disassembly for ADD2
    ; Size: 14 bytes. Origin: #x22911FBA
    ; BA:       488BD1           MOV RDX, RCX                     ; no-arg-parsing entry point
    ; BD:       E8DEE26EFD       CALL #x200002A0                  ; GENERIC-+
    ; C2:       488BE5           MOV RSP, RBP
    ; C5:       F8               CLC
    ; C6:       5D               POP RBP
    ; C7:       C3               RET

Since the compiler knows that both arguments are bytes, it can simply call the ADD instruction. With the exception of some extra bookkeeping needed when returning from the function, this is just as efficient as what a C++ compiler would generate. You can also declare a function as INLINE to allow the compiler to inline the call.

    CL-USER> (disassemble #'add3)
    ; disassembly for ADD3
    ; Size: 12 bytes. Origin: #x22911F4A
    ; 4A:       4801F9           ADD RCX, RDI                     ; no-arg-parsing entry point
    ; 4D:       488BD1           MOV RDX, RCX
    ; 50:       488BE5           MOV RSP, RBP
    ; 53:       F8               CLC
    ; 54:       5D               POP RBP
    ; 55:       C3               RET

If the author is reading, I found the disassembler source[1] interesting - MSVC hangs when you compile it for Release!

[1] https://github.com/rmitton/goaldis

Yeah I noticed that :)

I believe it might be the giant if-then chain I use for disassembling opcodes.

Reply on news.ycombinator.com