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 }