TweetFollow Us on Twitter

June 95 - KON & BAL'S PUZZLE PAGE

KON & BAL'S PUZZLE PAGE

A Branch Too Far

Chris YERGA

[IMAGE 124-129_Puzzle_Page_http1.GIF]

See if you can solve this programming puzzle, presented in the form of a dialog between Konstantin Othmer and guest puzzler Chris Yerga. The dialog gives clues to help you. Keep guessing until you're done; your score is the number to the left of the clue that gave you the correct answer. Even if you never run into the particular problems being solved here, you'll learn some valuable debugging techniques that will help you solve your own programming conundrums. And please, make KON & BAL's day by submitting a puzzle of your own to AppleLink DEVELOP.

Chris I have a piece of code that runs fine on my Quadra, but when I run it on a plain old 68000 it crashes.

KON A 68000? So you're still trying to get GX to run on that Mac Portable in Cary's office, huh? How does it crash?

Chris With an address error.

KON What's hard about that? Your code is doing a 2- or 4-byte access to an odd address, which is OK on a 68040 but not on a 68000. It's a trivial problem.

Chris That's what I thought, but the address it's accessing appears to be uninitialized data. The code is simply allocating a block and then storing a pointer in the block, but the store never seems to occur, because afterward the block has random data in it. And of course the block itself is long-aligned, because it came from the Memory Manager, so there's no problem there.

KON Maybe on your Quadra, but on a Mac Plus the Memory Manager allocates blocks that are word-aligned.

Chris Thanks for the history lesson, chief, but this isn't a Mac Plus and the Memory Manager on this machine is much different -- much simpler, actually. It just so happens that our Memory Manager always long-aligns blocks.

KON Since when are you writing new Memory Managers? I thought you wrote graphics code.

Chris Yes. But the cornerstone of any decent graphics system is its Memory Manager -- I wouldn't expect a "QuickDraw classic" guy like you to understand.

KON I understand memory management just fine, Jackson. Show me where you're setting up this data.

100 Chris This is the interesting section:

NewDMAQueueEntry
...
+0030 0020C5D6  MOVE.L  D3,D0
+0036 0020C5DC  _NewPtr
+0038 0020C5DE  MOVE.L  A0,-$0008(A6)
+003C 0020C5E2  MOVE.L  -$000C(A6),-(A7)
+0040 0020C5E6  MOVEA.W -$000E(A6),A1
+0044 0020C5EA  MOVE.L  A1,-(A7)
+0046 0020C5EC  JSR     *+$53A4 ; 00211990
+004A 0020C5F0  MOVE.L  D0,-$000C(A6)
+004E 0020C5F4  MOVE.L  A2,(A0,D0.L)

It makes the _NewPtr call, makes some other function call, and then stores the pointer in A2 into our newly allocated buffer.

KON What's the other function call doing?

95 Chris I'm not sure, actually. The C source doesn't indicate that a function call should be happening:

buffer = NewPtr(totalSize);
count = count * size;
*(long *) (buffer + count) = (long) handlerProc;

The only thing I see happening in the source code is a multiply. You don't need a function call for that.

KON Could this be some wacky C++ operator overloading nonsense? C++ is very good at generating extra function calls. I think we'd better bring a SmartFriend in on this one.

Chris Don't bring out the big guns just yet. The code is written completely in plain old C: no C++ and no CFront.

KON It's got to be code you've written, because it's a PC-relative JSR. Since it's not an A5- relative JSR, it's not going through the jump table, so it couldn't have been linked in from a library or something external to your program. It looks like a call to a static function.

Chris Actually, all the JSR instructions in this code are PC-relative. I wrote a tool that transforms all JSRs that go through the jump table to PC-relative JSRs. You may want to sit down for this next part -- it's a little tricky.

KON That's why it ended up in the Puzzle Page. Let's hear it.

90 Chris All the code is being built into a ROM; however, our development system of choice only allows us to build our code as a Mac application. So I created a custom tool that postprocesses the application and turns it into something that will run out of ROM. Basically we use the CODE 0 jump table to link everything together.

KON I see. You know where the code will reside in ROM, so you fake out the jump table to make it look as if all the segments are loaded. Since nothing will ever move or unload, your ROM jump table entries never need to change. Pretty tricky.

Chris But not tricky enough. The scheme you describe will work, but it has two problems. First, our ROM can be mapped into different addresses, so the code must be completely relocatable. A Mac jump table contains JMP instructions with fixed long addresses (for example, JMP $4083143A), which are not relocatable. Second, as a cycle counter like you should know, the jump table is superfluous here, because no code will ever move or unload while it's running. You're doing a JSR to the JMP in the jump table -- the extra JMP is unnecessary and wastes cycles.

KON I didn't know you GX guys counted cycles. How do you get away with removing the extra JMP?

85 Chris Our tool scans all the object code for all instructions that reference the jump table. They are JSR xx(A5) (function call), PEA xx(A5) (pass a function pointer on the stack), and LEA xx(A5),Ax (get a function pointer in a local variable). When it finds one of these instructions, it looks up the function in the jump table and changes the instruction to a PC-relative version that simply references the address of the target function directly. Everything is PC-relative, so it relocates correctly, and there are no extra instructions.

KON But the PC-relative addressing mode has only a 16-bit offset, so you can only reference functions within 32K of the PC. Is your ROM that small?

80 Chris Are you kidding? The pictures for the About box are bigger than that. When we need to reference a function that's beyond 32K, we create a "jump island" that's still PC- relative but allows us a greater reach.

0020122A:   JSR     $00201FA8       ;go to jump island
0020122E:   MOVE.W  D0,(A3)
...
00201FA8:   LEA     *+0,A0          ;get pc
00201FAC:   ADDA.L  #$00014B02,A0   ;add long offset
00201FB2:   JMP (A0)                ;jump to destination

KON That looks suspicious to me. You're messing with A0 in your jump island.

75 Chris But that should be OK because the whole thing is written in C, which never passes a parameter in A0 and never expects A0 to be preserved.

KON I can't find a specific problem, but I'm still a little suspicious of all this OS code you're writing. You said that this code runs fine on your Quadra. Does the Quadra version undergo the jump table transformation process?

Chris No. The Quadra version is run just like a Mac application out of RAM.

KON Tell me all the differences between the two environments.

70 Chris The 68000 version of the software is different in two ways. First, it's generated with the exact same compiler, but without 68020 code generation enabled. Then, I run it through my BuildROM tool, which transforms all the jump table references to PC- relative references. The 68000 target hardware is a diskless system; the only way to get code into it is through ROM cartridges, so we can't try to run a version of the software that hasn't undergone the BuildROM step.

KON So the bug may have nothing to do with the differences between the 68040 and 68000 processors -- it may be the BuildROM process. Let's sum up what we know: First we saw a piece of code that allocates a block of memory and stores a value into that block, but the store never seems to happen. Near that code is an unexplained JSR which we believe is a function call. Finally, we know that a critical difference in the environment is that you alter the code path of function calls. It's really starting to smell like your BuildROM tool.

Chris The evidence is all circumstantial, counselor. The only questionable part of the BuildROM process we've seen is my usage of A0 in the jump islands, but I can't see a case where a C function call takes a parameter in A0 or assumes A0 is preserved.

KON We should trace through the NewDMAQueueEntry routine and see what that mysterious function call is doing.

65 Chris I put in a breakpoint. But when I run the program again, I drop into the debugger with a debug message complaining that some kind of parameter is out of range.

KON You mean the bug isn't reproducible?

Chris After many tries, this is the first time it's failed this way.

KON Hmm. What parameter is out of range?

Chris The debug message doesn't say, exactly. The value it's complaining about is in D2. The value is $00004E56.

KON That's a funny-looking number. It looks like an opcode to me. dh 4E56 tells me it's a LINK A6,#xx instruction. Where did the value in D2 come from?

60 Chris From a MOVE.W (A0),D2 instruction. The code seems to think A0 points to some data.

KON But it looks as if it points to code instead. Where is A0?

Chris It points to the start of a routine called VBLHandler.

KON VBLHandler sure sounds like an interrupt service routine to me, which would explain the various failure modes. Is the routine written in C? C routines don't bother to preserve A0, so your interrupt routine is trashing a register!

55 Chris There's some inline assembly code to save all the registers. Take a look:

 void VBLHandler(void)
{
asm {
    MOVEM.L     A0-A6/D0-D7, -(SP)
};

FlushQueue();
HandleVBLTasks();

asm {
    MOVEM.L     (SP)+, A0-A6/D0-D7
};
}

KON It seems quite suspicious to me that A0 points to the beginning of this routine. Sounds like your jump islands are at work. Look at the interrupt vector for your VBL handler.

50 Chris On this particular machine the VBL is handled as a level-6 interrupt. The level-6 vector is at $0078. It points to a jump island entry like the one above.

KON And the first thing it does is trash A0 before your inline assembly gets a chance to save it! Maybe you should stick to drawing bitmaps and leave the OS work to someone else.

45 Chris The problem is that the code that installed the interrupt handler is more than 32K away from the handler itself. So when it did an LEA xx(A5),Ax to get the address of the interrupt handler, the ROM builder tool needed to stick a jump island in there. Nasty. But I still need a way to do PC-relative jump islands.

KON Use the stack, son. Try this:

PEA     * ;push the pc
ADD.L   #xxxxxx,(sp) ;add a long offset
RTS     ;jump to the destination

Chris All this and you can draw bitmaps too! I'll fix the ROM builder tool to do this. But somehow I doubt that a VBL interrupt was hitting us at the same spot in my NewDMAQueueEntry routine every time. There must be another problem there.

KON We still have the breakpoint there; before we recompile and fix the bug, let's run it again and see if we can get the original failure mode to happen again.

40 Chris This time we hit the breakpoint. We trace over the NewPtr and see that it returns a valid pointer in A0. We step into the JSR at $20C5EC and it takes us to one of my jump islands.

KON Which alters A0, and then jumps to the function being called. What is the function doing?

35 Chris It's a very short routine; it just takes some parameters off the stack and does a few multiplies. It returns the result in D0 just like any normal C function would.

KON But is it using the trashed A0 for anything?

Chris No. In fact, it's not using any address registers at all. It only uses data registers for the multiplies. I repeat: no C function would ever take a parameter in A0.

KON So we return to the NewDMAQueueEntry routine, with a return value in D0. We save D0 in a local variable on the stack frame, and then hit the instruction at $20C5F4, which stores a value in the buffer pointed to by A0.

30 Chris But A0 still has the result of the jump island calculation in it. The code didn't set up A0 to point to anything!

KON Look at the listing of NewDMAQueueEntry again. The code gets the result of the NewPtr call in A0, makes the function call, and then assumes that A0 still has the valid pointer in it. But meanwhile, some wannabe OS programmer has gotten in there and hosed A0 on us!

20 Chris That function call seems to be doing the multiply. It must be some runtime math library that the compiler uses.

KON I'll bet one of your variables is a long word. With 68020 code generation turned on, the compiler was able to generate a long multiply instruction, but the 68000 doesn't have a long multiply instruction, so it calls the math library.

10 Chris I see. Since the math library was written by the same people who wrote the compiler, their code generator knows that A0 won't get trashed, so it doesn't bother to save and restore it around the call to the long multiply routine. Pretty sneaky.

KON But nice. You want the person writing your code generator to be the ultimate cycle counter. Since the Mac Segment Loader implementation doesn't trash A0, it's a worthwhile optimization for them to make.

Chris Except in this case, the code that performs a multiply is more than 32K away from where the math library resides in the ROM, so it hits a jump island and loses the value of A0.

KON Even a lowly register like A0 is sacred sometimes.

Chris So it appears.

KON Nasty.

Chris Yeah.

SCORING

  • 80-100 Please fax your resumé to Catapult Entertainment, Inc., (408)366-2471.
  • 60-75 We also have junior positions available.
  • 40-55 Don't worry; just let CopyBits do the tricky stuff.
  • 10-35 I see you've done your share of long multiplies. *

Chris YERGA During his four years working on QuickDraw GX, Chris learned a lot about graphics systems and large projects. He's currently employed by Catapult Entertainment, where he learned that a Sega is kinda like a Macintosh, a SNES is kinda like an Apple II GS, and carbon dioxide can be explosive. *

Thanks to Josh Horwich,

KON (Konstantin Othmer), and BAL (Bruce Leak) for reviewing this column. *

 
AAPL
$98.63
Apple Inc.
-0.39
MSFT
$43.92
Microsoft Corpora
-0.05
GOOG
$585.19
Google Inc.
-5.41

MacTech Search:
Community Search:

Software Updates via MacUpdate

OS X Yosemite Wallpaper 1.0 - Desktop im...
OS X Yosemite Wallpaper is the gorgeous new background image for Apple's upcoming OS X 10.10 Yosemite. This wallpaper is available for all screen resolutions with a source file that measures 5,418... Read more
Acorn 4.4 - Bitmap image editor. (Demo)
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Bartender 1.2.20 - Organize your menu ba...
Bartender lets you organize your menu bar apps. Features: Lets you tidy your menu bar apps how you want. See your menu bar apps when you want. Hide the apps you need to run, but do not need to... Read more
TotalFinder 1.6.2 - Adds tabs, hotkeys,...
TotalFinder is a universally acclaimed navigational companion for your Mac. Enhance your Mac's Finder with features so smart and convenient, you won't believe you ever lived without them. Tab-based... Read more
Vienna 3.0.0 RC 2 :be5265e: - RSS and At...
Vienna is a freeware and Open-Source RSS/Atom newsreader with article storage and management via a SQLite database, written in Objective-C and Cocoa, for the OS X operating system. It provides... Read more
VLC Media Player 2.1.5 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Default Folder X 4.6.7 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click... Read more
TinkerTool 5.3 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Audio Hijack Pro 2.11.0 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Intermission 1.1.1 - Pause and rewind li...
Intermission allows you to pause and rewind live audio from any application on your Mac. Intermission will buffer up to 3 hours of audio, allowing users to skip through any assortment of audio... Read more

Latest Forum Discussions

See All

Note Review
Note Review By Jennifer Allen on July 29th, 2014 Our Rating: :: TOO SIMPLEiPhone App - Designed for the iPhone, compatible with the iPad Note is a note taking app that’s a little too short on features to be worth its asking price... | Read more »
Chainsaw Warrior Goes on Sale & Ther...
Chainsaw Warrior Goes on Sale & There’s a Chance to Win a Copy of the Original Board Game Posted by Jennifer Allen on July 29th, 2014 [ permalink | Read more »
It Came From Canada: Tiny Tower Vegas
If you go to a casino, you might make a lot of money. If you run a casino, you’re guaranteed to make a lot of money. The choice seems pretty obvious. So while waiting for your shady real estate deals to move forward, get prepared with Tiny Tower... | Read more »
Z Hunter Review
Z Hunter Review By Lee Hamlet on July 29th, 2014 Our Rating: :: RIGHT ON TARGETUniversal App - Designed for iPhone and iPad While it might not necessarily break new ground, Z Hunter has enough tricks up its sleeve to ensure that... | Read more »
Huge Update Comes To Duet, Adding 48 New...
Huge Update Comes To Duet, Adding 48 New Stages Posted by Jennifer Allen on July 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Sharknado: The Video Game Available Now....
Sharknado: The Video Game Available Now. Seriously. Posted by Rob Rich on July 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Frog Orbs 2 Review
Frog Orbs 2 Review By Nadia Oxford on July 29th, 2014 Our Rating: :: THIS MAGIC IS A TAD MONOTONOUS Universal App - Designed for iPhone and iPad Frog Orbs 2 is repetitive, but younger players should enjoy it nonetheless.   | Read more »
Puzzix Review
Puzzix Review By Jennifer Allen on July 29th, 2014 Our Rating: :: NICE IDEAUniversal App - Designed for iPhone and iPad A little like Tetris, Puzzix is all about piecing together blocks and watching them vanish. It could do with... | Read more »
Cannonball eMail is Now Live – Works Wit...
Cannonball eMail is Now Live – Works With Gmail, Yahoo, Outlook, Hotmail, and AOL Posted by Jessica Fisher on July 29th, 2014 [ permalink ] | Read more »
To The End Review
To The End Review By Lee Hamlet on July 29th, 2014 Our Rating: :: A VICIOUS CYCLEUniversal App - Designed for iPhone and iPad To The End will test players’ patience, timing, and dedication as they try to navigate all 13 levels in... | Read more »

Price Scanner via MacPrices.net

Updated MacBook Pro Price Trackers
We’ve updated our MacBook Pro Price Trackers with the latest information on prices, bundles, and availability on the new 2014 models from Apple’s authorized internet/catalog resellers as well as... Read more
Apple updates MacBook Pros with slightly fast...
Apple updated 13″ and 15″ Retina MacBook Pros today with slightly faster Haswell processors. 13″ models now ship with 8GB of RAM standard, while 15″ MacBook Pros ship with 16GB across the board. Most... Read more
Apple drops price on 13″ 2.5GHz MacBook Pro b...
The Apple Store has dropped their price for the 13″ 2.5GHz MacBook Pro by $100 to $1099 including free shipping. Read more
Apple drops prices on refurbished 2013 MacBoo...
The Apple Store has dropped prices on Apple Certified Refurbished 13″ and 15″ 2013 MacBook Pros, with model now available starting at $929. Apple’s one-year warranty is standard, and shipping is free... Read more
iOS 8 and OS X 10.10 To Support DuckDuckGo As...
Writing for Quartz, Dan Frommer reports that Apple’s forthcoming iOS 8 and OS X 10.10 operating systems version updates will allow users to select DuckDuckGo as their default search engine. He notes... Read more
U.K. Hospital Using iPods and iPads To Record...
British news journal GazetteLive’s. Ian McNeal notes that the old “an apple a day keeps the doctor away” proverb is being turned on its head at http://southtees.nhs.uk/hospitals/james-cook/ James... Read more
13-inch 2.5GHz MacBook Pro on sale for $1099,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $1099.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $100 off MSRP. Price is... Read more
Roundup of Apple refurbished MacBook Pros, th...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available for up to $400 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. Their prices... Read more
Record Mac Shipments In Q2/14 Confound Analys...
A Seeking Alpha Trefis commentary notes that Apple’s fiscal Q3 2014 results released July 22, beat market predictions on earnings, although revenues were slightly lower than anticipated. Apple’s Mac’... Read more
Intel To Launch Core M Silicon For Use In Not...
Digitimes’ Monica Chen and Joseph Tsai, report that Intel will launch 14nm-based Core M series processors specifically for use in fanless notebook/tablet 2-in-1 models in Q4 2014, with many models to... Read more

Jobs Board

Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.