Free the mouse Replay MagicDivision
Home | Changes | Index | Search | Go
On many processors, including the MIPS used in the Replay, division is slower than multipication -- but division is the same as multipication by an inverse. Of course, finding an inverse is a special case of division, so at first glance this doesn't seem to help. If the division is by a constant, though, the inverse can be found at compile time (or looked up in a table, I suspect). http://the.wall.riscom.net/books/proc/ppc/cwg/cwg_ix.html discusses how to do this, from a compiler's-writer point of view (for the PowerPC?, not the MIPS, but the principle's the same).

But what does a disassembler do?

Given the code:

  11ef1c:       3c031a41        lui     v1,0x1a41   
                                                                                
  11ef20:       8fa202cc        lw      v0,716(sp)                                                                    
  11ef24:       00021102        srl     v0,v0,0x4         
  11ef28:       3463a41b        ori     v1,v1,0xa41b                            
  11ef2c:       00430019        multu   v0,v1        
  11ef30:       00004810        mfhi    t1  
  11ef34:       00099082        srl     s2,t1,0x2       
how does a disassembler figure out what's really going on?

For people who aren't familiar with MIPS assembly but want to follow along, that's basically equivalent to:

union {longlong together; struct {u32 hi; u32 lo} apart} hilo;
v1 = 0x1a41a41b;
v0 = arg1;
v0 >>= 4;
hilo.together = v0 * v1;
s2 = hilo.apart.hi >> 2;
So, we take a number, divide it by 16, multiply by a magic number, take the high word, divide that by 4, and call it done. That's clear, except for what multiplying by the magic number and taking the high word does.

After reading the page above and solving for the divisor, we get:

(2^32 + x - 1) / x = 0x1a41a41b
2^32 + x - 1 = x * 0x1a41a41b
2^32 - 1 = x * 0x1a41a41a
x = (2^32 - 1)/0x1a41a41a
x = 9.75  (well, close enough)
so the magic sequence is division by 9.75. The shifts before and after additionally divide by 64. 9.75 * 64 = 624, so the whole sequence is division by 624. Not coincidentally, that's the size of a ReplayChannel structure.

-- ToddLarason - 20 Mar 2002

Topic MagicDivision . { Edit | Attach | Ref-By | Printable | Diffs | r1.1 | More }
Revision r1.1 - 20 Mar 2002 - 09:23 GMT - ToddLarason

Copyright © 2001 by the contributing authors. All material on this collaboration tool is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.