https://github.com/akkartik/mu/blob/main/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 -2 to +2. Viewport height just follows the viewport's aspect
    217 # 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   #  scene-cy - scene-width/width * (height/2 + y)
    243   # At most two numbers being multiplied before a divide, so no risk of overflow.
    244   var result-f/eax: int <- int-to-fixed y
    245   result-f <- multiply-fixed result-f, scene-width-f
    246   var width-f/ecx: int <- copy width
    247   width-f <- shift-left 8/fixed-precision
    248   result-f <- divide-fixed result-f, width-f
    249   result-f <- add scene-cy-f
    250   var second-term-f/edx: int <- copy 0
    251   {
    252     var _second-term-f/eax: int <- copy scene-width-f
    253     _second-term-f <- shift-right 1
    254     var height-f/ebx: int <- copy height
    255     height-f <- shift-left 8/fixed-precision
    256     _second-term-f <- multiply-fixed _second-term-f, height-f
    257     _second-term-f <- divide-fixed _second-term-f, width-f
    258     second-term-f <- copy _second-term-f
    259   }
    260   result-f <- subtract second-term-f
    261   return result-f
    262 }