Omegamatrix's Blog

Dang, I was looking for a good divide by 33 routine.

 

Educational as always Omega. Thanks for posting this!

You can also do division as a "shift and subtract", which will reduce the number of loops to the number of shifts. However, the 6502 doesn't have the instruction set which will make this method efficient.

Hmm, I'll have to look into that reciprocal multiplication tonight. I'm got a 185 byte table in Frantic that's used for divide by 5 for dealing with the PF pixels that make up walls (each brick of the wall is 5 scan lines tall). The table's used in the calculations that check if a sprite or missile has collided with a wall. Due to flicker, all collisions are done in software. Also the Frenzy variation needs to know which segment was hit so it can remove the brick if it was part of a destructible wall.

The division routines are for 6502 assembly and highly optimized to take as little time and bytes as possible. I don't know if you could port it to C code or ARM assembly so easily. The divide by five looks like this:

;Divide by 5
;18 bytes, 30 cycles
  sta  temp
  lsr
  adc  #13
  adc  temp
  ror
  lsr
  lsr
  adc  temp
  ror
  adc  temp
  ror
  lsr
  lsr

The carry is never set or cleared, but its contents are depended on.

http://www.hackersdelight.org/divcMore.pdf might have something of use

I ended up working late so haven't tried it yet. After reading the reciprocal multiplication page I believe the code would be something along these lines:

div5 = (orig * %001100110011) >> 12

if the values are slightly off, because 1/5 is an infinite repeating fraction when represented in binary, then extended the fixed point value such as

div5 = (orig * %0011001100110011) >> 16

In the Correcting the Errors section they mention that using these values would be accurate for all 16 bit dividends:

div5 = (orig * %001100110011001101) >> 18

Since I'm only dividing an 8 bit value, I believe the 12 or 16 should meet my needs.

 

What I plan to do is add a division test to the "menu" which tests the values 0-255. I'll use the score to display the test results - if a dividend doesn't divide correctly I'll show it in the score. If 0-255 all succeed then I'll show FFFFFF.

I dropped this in during lunch:

 

#define DIV_BY_5                0xCCCD
#define DIV_BY_5_SHIFT          18

/*
const unsigned char div_5[] = {
    0,  0,  0,  0,  0,
    1,  1,  1,  1,  1,
    2,  2,  2,  2,  2,
...
    36, 36, 36, 36, 36
};
 */

int PlayfieldSpriteCheck(int x, int y)
{
...
//        y5 = div_5[y];
        y5 = (y * DIV_BY_5) >> DIV_BY_5_SHIFT;
...
}

void MoveShots(int count)
{
...
//                        y = div_5[gMissileY[i] + y];
                        y = ((gMissileY[i] + y) * DIV_BY_5) >> DIV_BY_5_SHIFT;
...
}

It appears to work as the correct wall segments get shot out in the Frenzy variation and the humanoid still correctly collides with the walls. Before the change the ARM code was 11272 bytes, after it's 11100 for a 172 byte savings!

 

I still plan to do the div check before committing this change. I'll do that when I next work on Frantic, possibly tonight but most likely over the weekend.

#define DIV_BY_5                0xCCCD
#define DIV_BY_5_SHIFT          18

        y5 = (y * DIV_BY_5) >> DIV_BY_5_SHIFT;

 

I took a quick peek tonight, and I believe you can get by with this (good for values 0 to 259).

#define DIV_BY_5                0x33
#define DIV_BY_5_SHIFT          8

        y5 = ((y + 1) * DIV_BY_5) >> DIV_BY_5_SHIFT;

.

.

I did this by looking at the values in excel, and I saw that they were off by 1 when the transition to the next integer result occurred. Initially increasing the dividend by 1 fixes this.

 

I am curious how the compiler is computing the multiplication. I believe the arm chip in the harmony has no hardware multiplier. This is what I came up with in pseudo code:

    inc       ; +1
    sta temp
    asl       ; x2
    adc temp  ; x3
    sta temp
    asl       ; x6
    asl       ; x12
    asl       ; x24
    asl       ; x48
    adc temp  ; x51
    lsr >> 8

Thinking about is some more, it could be further improved since you are shifting left four times, and then right eight. So you might do something like this instead:

    inc       ; +1
    sta temp
    asl       ; x2
    adc temp  ; x3
    sta temp
    lsr >> 4
    adc temp
    lsr >> 4


or:

   temp = ((Y + 1)*3)
   result = ((temp / 16) + temp) / 16

I tested the 0xCCCD value I'd dropped in from the page and it worked as expected. When I tried the 0x33_ values it didn't work. I didn't wish to spend any more time on it, so I decided to leave it with the 0xCCCD value.

 

Based on this section of the listing, at 3320, I'd say the ARM has hardware multiply:

2341:main.c        ****     if (y < 36*5)
2342:main.c        ****         y5 = (y * DIV_BY_5) >> DIV_BY_5_SHIFT;
2343:main.c        ****     else
2344:main.c        ****         y5 = 36;
 3313              		.loc 1 2344 0
 3314 0004 2424     		mov	r4, #36	@ y5,
2341:main.c        ****     if (y < 36*5)
 3315              		.loc 1 2341 0
 3316 0006 B329     		cmp	r1, #179	@ y,
 3317 0008 02DC     		bgt	.L268	@,
2342:main.c        ****         y5 = (y * DIV_BY_5) >> DIV_BY_5_SHIFT;
 3318              		.loc 1 2342 0
 3319 000a 3D4C     		ldr	r4, .L282	@ tmp197,
 3320 000c 4C43     		mul	r4, r1	@ tmp196, y
 3321 000e A414     		asr	r4, r4, #18	@ y5, tmp196,
 3322              	.LVL220:
 3323              	.L268:

Per wiki:

The ARM supports add, subtract, and multiply instructions. The integer divide instructions are only implemented by ARM cores based on the following ARM architectures...(not what's in the Harmony)

Today I have found better routines for dividing 6,10,12,20,24,26, and 28. I removed the old file, and replaced it Rev 1 which contains the new routines.

Upgraded the file to Rev 2. It has a new divide by 22 routine which is 3 cycles faster then before, and uses the same amount of bytes.