pouët.net

Hello, I am newschool. I've coded a rotozoomer for DOS that runs at ~9.86 FPS when DOSBox is set to 12010 cycles/ms (i.e. approximately the speed of a 486DX 33MHz). It already:
- computes texture coordinates using increments
- uses inline assembly for the inner loop.

How could the effect be done in a significantly faster way? I reckon at this point it's not about shaving off a few cycles from the inner loop, but about doing some 'magic' that accomplishes the effect in a different way. I know it has been done on even lower specs (like the Amiga 500), but how?

You can see the code here: https://github.com/tazumeki/rotozoom-dos/blob/main/rotozoom.c.

Assuming you've already reordered the texels in the texture to be tiled/cache efficient etc, and I also haven't looked at the actual math, but looking at the code (without executing it), I see:

* mov al, [si] + stosb

mosvb?

* dec x

You probably want to do this in a register, like cx. You will need to free cx from the outer loop (push/pop?)

* add bx, dux + add dx, dvx

Again, seems a bad idea to reach out to memory. Something I did in a rotozoom like this at the time was to make the code segment where this routine exists writable. Then I made the code self-modifying, so before entering the loop the code would write to the locations where the add bx and add dx instructions are and write the dux and dyv as literals arguments.

Unroll your loops.

Just some thoughts:
All the shifting- and masking-instructions disappear when you use a 256x256 texture and have the integer part of your UV in the H,L-parts of a register.
You can add-carry the overflows of the fractional parts directly into the integer parts.
This should end up at about 5 instructions per pixel.
Dont't send single bytes to the VGA, unroll to store aligned dwords.
At this point you should see that the code runs significantly slower at ~90deg texture rotations because the data cache doesn't work efficiently there.
You have a 32bit CPU but only use 16bit instructions.
Smaller plattforms unroll speed-code for a quarter scanline or so and fix the interpolation errors in between. This precalced code can be reused for all scanlines because the deltas are constant. That should result in 3 instructions for 2 pixels.

On this note: you can solve this by creating a 90deg rotated version of your texture and switching between the two depending on your angle. If you zoom far out you may even get some benefits of 2x/4x tiled "mip" versions.

Besides what everyone says, x86 can be tough because of very few registers, as I see in this code the use of memory per pixel for at least three variables and there might be ways to avoid. I have a rotozoomer that runs like 30fps on 386dx where I fit everything in the regs for the inner loop, although I unrolled the whole X to not have to loop over X and free a reg.

Your loop is kinda different, over 64000 but also check for 320 every pixel. If you could rewrite it to double loop over 320 and 200, then if registers are not enough, do the dec [memory] only on outside 200 loop, so inside use cx instead of 320. But there might be a lot things to change so I might be asking much :)

Also if your FP_SHIFT was 8, maybe there was a posibility to avoid the shifts, but after add bx,step and add dx,step you can move use the high bytes b or d directly without shift to construct the tex offset. On my roto I kinda went too far (bad for cache though) with 256x256 texture so that after these, I could easilly construct from high bytes the new 16bit address in a reg and read directly (and so also avoid AND with mask for tiling).

Or unroll the innerloop x2 to get down to 160 and use "dec cl" for inner and "dec ch" for the outer loop, voila :)

Are there advantages to not using 32-bit protected mode on a 486?

Oh, the folks above have already pointed out most of the important things :)

Yeah, if it’s not critical for you, switch to using a 256×256 texture, and you’ll be surprised how much simpler your inner loop becomes (hint: you won’t need any shr or and instructions to calculate the pixel address in the texture).

And yes, of course, there should be no memory variable accesses inside the inner loop, registers only. Yes, there are never enough registers, but in this case it’s a solvable problem.

Something more specific:

Instead of stosb, it’s better to use:
mov es:[di], al
inc di
Oddly enough, this is faster on a 486.

And if you unroll the inner loop, you’ll end up with just:
mov es:[di], ax
add di, 2

To solve the uneven FPS issue (depending on the angle) that was mentioned earlier, I split the rendering into 16×16 tiles. It’s a bit of a hassle, but the resulting FPS becomes much more consistent.

Happy coding :)

P.S. And yes, DOSBox of course doesn’t reproduce all the nuances, such as how the CPU cache behaves. Some things that run faster in DOSBox actually run slower on real hardware, and vice versa.

If you still think there’s some kind of magic involved, take a look at the rotzoomer code for the 8086 (8 MHz): https://github.com/mills32/CUTE_DEMO-MS-DOS/blob/main/src/rotozoom.asm - check out this on [youtube]

but this makes sense specifically for 8086-80286.

Just swizzle the texture! Googling for pasroto.zip should give you an era-appropriate 1996 explanation of how to do that.

Since these two approaches where just mentioned:
If you fill your screen in 16x16 tiles or sample your texture from 16x16 blocks gives very similar results.
I remember back in the days I found the latter one a bit surprising as a 16x16 source block simply consists of 16 (seamingly) independent cachelines.
But as the 486 uses a 4-way associative cache, it makes a big difference from where you fetch your data. In the 90deg-case all the cachelines from an unswizzled texture are 256 bytes apart and all fall into the same cache bin, basically reducing your cache size to 4x16 bytes for this block. But 16x16 bytes from a linear location all fit into the cache at once.

Thanks for your nice replies and the optimization advice. Turns out the 'magic' I was looking for was precalculation. When I look at mills32's rotozoom.asm, I see he's using tables with 180 frames worth of precalculated pointer increments. I don't understand the math yet TBH, but I guess this answers my question as to how the effect is realized on much slower machines (like an 8 MHz 8086 in this case).

Still, I think you can achieve 70 FPS on a 486 at 33 MHz even without a precalculated table. From a coding practice perspective, that’s actually more interesting.

Post your improved versions of the rotozoomer here and we’ll discuss them :)

I’d be curious too - what tricks are used on the Amiga or the C64? I suspect there’s some stuff that’s way cooler than the PC rotozoomer implementations.

Agreed with @bitl, there are so many things to learn from all comments about optimizing the existing code and get an idea of how to improve things even for other effects.

On the other hand, I was thinking about the implementations like the one in 8088 posted. It reminds me something I presume they do in older platforms and never tried myself. I remember some CPC rotozoomers where the texel precision is so broken when zoom in, that quite possibly they do similar things. Although in this 8088 maybe there is different data to alleviate this. My thought might differ, it's that your rotozoomer animation is brief in your demo, so someone could make crude unrolled code for a single line as the step is the same. The unroll code will read and inc either U or V or wait if it's in same texel. Hardcoded without any fixed point additions or anything, just like people hardcode wolfenstein column stretches for different scale levels. But only for the few frames of your effect, as hardcoding every possibly zoom/rotate level would be too much. Still, maybe too much precalcs for something that can relatively easily run fast enough on 386/486. Would try with one single scale/rotate value on older to see the difference in performance though.

So… I actually went all-in on this ;)

Is it really possible to make a rotozoomer that runs stably at 70 FPS on a 486-33 MHz? Since I told the topic starter that it is possible.

I made 3 variants:

1. Standart rendering (lines by lines), plus an additional texture rotated by 90 degree (to fight CPU cache misses)

2. Rendering in 16x16 tiles

3. Same tiles 16x16, but with precomputed offsets for 16 pixels of a line (applied to the whole frame, low precision, but renders much faster)

Considering the topic-starter measured performance in DOSBox, I want to point out that DOSBox does not emulate CPU cache behavior at all. There it makes no difference whether memory is read sequentially or randomly.

Because of that, the result on a real machine can differ a lot from what you expect. For example, I usually set cycles=15000 in DOSBox to roughly match my PC 486DX2-66 MHz, not super precise, but within +-10 FPS for other effects. Rotozoomer (and not only the ones I coded) run much faster on real hardware than in DOSBox (at the same 15000 cycles). In fact, about twice as fast, but only if you successfully apply tricks to avoid cache misses.

if anyone’s interested, here’s what I got:
(On my 486, with fixed Scale 1:1)

TWO_TXTR.EXE (two textures) — 114 FPS

TAIL_HIG.EXE (16x16 tiles) — 108 FPS

TAIL_LOW.EXE (tiles + low precision) — 167 FPS

With a varying scale in the range 0.7 - 1.7, performance drops by about 6 - 8 FPS.

In DOSBox, for routines types 1 and 2 these numbers are only reached at about 37000 cycles, but at the same TAIL_LOW.EXE shoots up to 300 FPS. So measuring rotozoomer performance in DOSBox is… not a great idea :)

If anyone’s curious, you can test it or look at the sources:

http://chiptown.ru/stuff/rotozoom.zip

Sorry for the Turbo Pascal, but of course the main routine is written in assembly.

And if someone shows me faster routines, I’d appreciate it :)

Top tip: pasroto.zip

This has already been mentioned here.

But still, the Pascal/Cubik Team routine is about the same speed as my two versions (the third one is even faster, but with some loss of accuracy).

And yet it’s optimized for a top-end 486 and Pentium. What about a 386? Or a 286? :)

Oh I apologise for not reading each and every answer in detail.

I just mentioned it because the principle discussed in there is pretty paramount in graphics and performance programming alike.