apps/mandelbrot-fixed.mu

   1 # Mandelbrot set using fixed-point numbers.
   2 #
   3 # Install:
   4 #   $ git clone https://github.com/akkartik/mu
   5 #   $ cd mu
   6 # Build on Linux:
   7 #   $ ./translate apps/mandelbrot-fixed.mu
   8 # Build on other platforms (slow):
   9 #   $ ./translate_emulated apps/mandelbrot-fixed.mu
  10 # Run:
  11 #   $ qemu-system-i386 code.img
  12
  13 fn main screen: (addr screen), keyboard: (addr keyboard), data-disk: (addr disk) {
  14   # Initially the viewport is centered at 0, 0 in the scene.
  15   var scene-cx-f: int
  16   var scene-cy-f: int
  17   # Initially the viewport shows a section of the scene 4 units wide.
  18   var scene-width-f: int
  19   copy-to scene-width-f, 0x400/4
  20   {
  21     mandelbrot screen scene-cx-f, scene-cy-f, scene-width-f
  22     # move at an angle slowly towards the edge
  23     var adj-f/eax: int <- multiply-fixed scene-width-f, 0x12/0.07
  24     subtract-from scene-cx-f, adj-f
  25     add-to scene-cy-f, adj-f
  26     # slowly shrink the scene width to zoom in
  27     var tmp-f/eax: int <- multiply-fixed scene-width-f, 0x80/0.5
  28     copy-to scene-width-f, tmp-f
  29     loop
  30   }
  31 }
  32
  33 # Since they still look like int types, we'll append a '-f' suffix to variable
  34 # names to designate fixed-point numbers.
  35
  36 fn int-to-fixed in: int -> _/eax: int {
  37   var result-f/eax: int <- copy in
  38   result-f <- shift-left 8/fixed-precision
  39   {
  40     break-if-not-overflow
  41     abort "int-to-fixed: overflow"
  42   }
  43   return result-f
  44 }
  45
  46 fn fixed-to-int in-f: int -> _/eax: int {
  47   var result/eax: int <- copy in-f
  48   result <- shift-right-signed 8/fixed-precision
  49   return result
  50 }
  51
  52 # The process of throwing bits away always adjusts a number towards -infinity.
  53 fn test-fixed-conversion {
  54   # 0
  55   var f/eax: int <- int-to-fixed 0
  56   var result/eax: int <- fixed-to-int f
  57   check-ints-equal result, 0, "F - test-fixed-conversion - 0"
  58   # 1
  59   var f/eax: int <- int-to-fixed 1
  60   var result/eax: int <- fixed-to-int f
  61   check-ints-equal result, 1, "F - test-fixed-conversion - 1"
  62   # -1
  63   var f/eax: int <- int-to-fixed -1
  64   var result/eax: int <- fixed-to-int f
  65   check-ints-equal result, -1, "F - test-fixed-conversion - -1"
  66   # 0.5 = 1/2
  67   var f/eax: int <- int-to-fixed 1
  68   f <- shift-right-signed 1
  69   var result/eax: int <- fixed-to-int f
  70   check-ints-equal result, 0, "F - test-fixed-conversion - 0.5"
  71   # -0.5 = -1/2
  72   var f/eax: int <- int-to-fixed -1
  73   f <- shift-right-signed 1
  74   var result/eax: int <- fixed-to-int f
  75   check-ints-equal result, -1, "F - test-fixed-conversion - -0.5"
  76   # 1.5 = 3/2
  77   var f/eax: int <- int-to-fixed 3
  78   f <- shift-right-signed 1
  79   var result/eax: int <- fixed-to-int f
  80   check-ints-equal result, 1, "F - test-fixed-conversion - 1.5"
  81   # -1.5 = -3/2
  82   var f/eax: int <- int-to-fixed -3
  83   f <- shift-right-signed 1
  84   var result/eax: int <- fixed-to-int f
  85   check-ints-equal result, -2, "F - test-fixed-conversion - -1.5"
  86   # 1.25 = 5/4
  87   var f/eax: int <- int-to-fixed 5
  88   f <- shift-right-signed 2
  89   var result/eax: int <- fixed-to-int f
  90   check-ints-equal result, 1, "F - test-fixed-conversion - 1.25"
  91   # -1.25 = -5/4
  92   var f/eax: int <- int-to-fixed -5
  93   f <- shift-right-signed 2
  94   var result/eax: int <- fixed-to-int f
  95   check-ints-equal result, -2, "F - test-fixed-conversion - -1.25"
  96 }
  97
  98 # special routines for multiplying and dividing fixed-point numbers
  99
 100 fn multiply-fixed a-f: int, b-f: int -> _/eax: int {
 101   var result/eax: int <- copy a-f
 102   result <- multiply b-f
 103   {
 104     break-if-not-overflow
 105     abort "multiply-fixed: overflow"
 106   }
 107   result <- shift-right-signed 8/fixed-precision
 108   return result
 109 }
 110
 111 fn divide-fixed a-f: int, b-f: int -> _/eax: int {
 112   var result-f/eax: int <- copy a-f
 113   result-f <- shift-left 8/fixed-precision
 114   {
 115     break-if-not-overflow
 116     abort "divide-fixed: overflow"
 117   }
 118   var dummy-remainder/edx: int <- copy 0
 119   result-f, dummy-remainder <- integer-divide result-f, b-f
 120   return result-f
 121 }
 122
 123 # multiplying or dividing by an integer can use existing instructions.
 124
 125 # adding and subtracting two fixed-point numbers can use existing instructions.
 126
 127 fn mandelbrot screen: (addr screen), scene-cx-f: int, scene-cy-f: int, scene-width-f: int {
 128   var a/eax: int <- copy 0
 129   var b/ecx: int <- copy 0
 130   a, b <- screen-size screen
 131   var width/esi: int <- copy a
 132   width <- shift-left 3/log2-font-width
 133   var height/edi: int <- copy b
 134   height <- shift-left 4/log2-font-height
 135   var y/ecx: int <- copy 0
 136   {
 137     compare y, height
 138     break-if->=
 139     var imaginary-f/ebx: int <- viewport-to-imaginary-f y, width, height, scene-cy-f, scene-width-f
 140     var x/eax: int <- copy 0
 141     {
 142       compare x, width
 143       break-if->=
 144       var real-f/edx: int <- viewport-to-real-f x, width, scene-cx-f, scene-width-f
 145       var iterations/esi: int <- mandelbrot-iterations-for-point real-f, imaginary-f, 0x400/max
 146       iterations <- shift-right 3
 147       var color/edx: int <- copy 0
 148       {
 149         var dummy/eax: int <- copy 0
 150         dummy, color <- integer-divide iterations, 0x18/24/size-of-cycle-0
 151         color <- add 0x20/cycle-0
 152       }
 153       pixel screen, x, y, color
 154       x <- increment
 155       loop
 156     }
 157     y <- increment
 158     loop
 159   }
 160 }
 161
 162 fn mandelbrot-iterations-for-point real-f: int, imaginary-f: int, max: int -> _/esi: int {
 163   var x-f/esi: int <- copy 0
 164   var y-f/edi: int <- copy 0
 165   var iterations/ecx: int <- copy 0
 166   {
 167     var done?/eax: boolean <- mandelbrot-done? x-f, y-f
 168     compare done?, 0/false
 169     break-if-!=
 170     compare iterations, max
 171     break-if->=
 172     var x2-f/edx: int <- mandelbrot-x x-f, y-f, real-f
 173     var y2-f/ebx: int <- mandelbrot-y x-f, y-f, imaginary-f
 174     x-f <- copy x2-f
 175     y-f <- copy y2-f
 176     iterations <- increment
 177     loop
 178   }
 179   return iterations
 180 }
 181
 182 fn mandelbrot-done? x-f: int, y-f: int -> _/eax: boolean {
 183   # x*x + y*y > 4
 184   var tmp-f/eax: int <- multiply-fixed x-f, x-f
 185   var result-f/ecx: int <- copy tmp-f
 186   tmp-f <- multiply-fixed y-f, y-f
 187   result-f <- add tmp-f
 188   compare result-f, 0x400/4
 189   {
 190     break-if->
 191     return 0/false
 192   }
 193   return 1/true
 194 }
 195
 196 fn mandelbrot-x x-f: int, y-f: int, real-f: int -> _/edx: int {
 197   # x*x - y*y + real
 198   var tmp-f/eax: int <- multiply-fixed x-f, x-f
 199   var result-f/ecx: int <- copy tmp-f
 200   tmp-f <- multiply-fixed y-f, y-f
 201   result-f <- subtract tmp-f
 202   result-f <- add real-f
 203   return result-f
 204 }
 205
 206 fn mandelbrot-y x-f: int, y-f: int, imaginary-f: int -> _/ebx: int {
 207   # 2*x*y + imaginary
 208   var result-f/eax: int <- copy x-f
 209   result-f <- shift-left 1/log2
 210   result-f <- multiply-fixed result-f, y-f
 211   result-f <- add imaginary-f
 212   return result-f
 213 }
 214
 215 # Scale (x, y) pixel coordinates to a complex plane where the viewport width
 216 # ranges from (scene-cx - scene-width/2) to (scene-cx + scene-width/2).
 217 # Viewport height just follows the viewport's aspect ratio.
 218
 219 fn viewport-to-real-f x: int, width: int, scene-cx-f: int, scene-width-f: int -> _/edx: int {
 220   # 0 in the viewport       goes to scene-cx - scene-width/2
 221   # width in the viewport   goes to scene-cx + scene-width/2
 222   # Therefore:
 223   # x in the viewport       goes to (scene-cx - scene-width/2) + x*scene-width/width
 224   # At most two numbers being multiplied before a divide, so no risk of overflow.
 225   var result-f/eax: int <- int-to-fixed x
 226   result-f <- multiply-fixed result-f, scene-width-f
 227   var width-f/ecx: int <- copy width
 228   width-f <- shift-left 8/fixed-precision
 229   result-f <- divide-fixed result-f, width-f
 230   result-f <- add scene-cx-f
 231   var half-scene-width-f/ecx: int <- copy scene-width-f
 232   half-scene-width-f <- shift-right 1
 233   result-f <- subtract half-scene-width-f
 234   return result-f
 235 }
 236
 237 fn viewport-to-imaginary-f y: int, width: int, height: int, scene-cy-f: int, scene-width-f: int -> _/ebx: int {
 238   # 0 in the viewport       goes to scene-cy - scene-width/2*height/width
 239   # height in the viewport  goes to scene-cy + scene-width/2*height/width
 240   # Therefore:
 241   # y in the viewport       goes to (scene-cy - scene-width/2*height/width) + y*scene-width/width
 242   # At most two numbers being multiplied before a divide, so no risk of overflow.
 243   var result-f/eax: int <- int-to-fixed y
 244   result-f <- multiply-fixed result-f, scene-width-f
 245   var width-f/ecx: int <- copy width
 246   width-f <- shift-left 8/fixed-precision
 247   result-f <- divide-fixed result-f, width-f
 248   result-f <- add scene-cy-f
 249   var second-term-f/edx: int <- copy 0
 250   {
 251     var _second-term-f/eax: int <- copy scene-width-f
 252     _second-term-f <- shift-right 1
 253     var height-f/ebx: int <- copy height
 254     height-f <- shift-left 8/fixed-precision
 255     _second-term-f <- multiply-fixed _second-term-f, height-f
 256     _second-term-f <- divide-fixed _second-term-f, width-f
 257     second-term-f <- copy _second-term-f
 258   }
 259   result-f <- subtract second-term-f
 260   return result-f
 261 }