1 ## compute the factorial of 5, and return the result in the exit code
  2 #
  3 # To run:
  4 #   $ subx translate apps/factorial.subx apps/factorial
  5 #   $ subx run apps/factorial
  6 # Expected result:
  7 #   $ echo $?
  8 #   120
  9 #
 10 # You can also run the automated test suite:
 11 #   $ subx run apps/factorial test
 12 # Expected output:
 13 #   ........
 14 # Every '.' indicates a passing test. Failing tests get a 'F'.
 15 # When running tests the exit status doesn't mean anything. Yet.
 16 
 17 == code
 18 # instruction                     effective address                                                   operand     displacement    immediate
 19 # op          subop               mod             rm32          base        index         scale       r32
 20 # 1-3 bytes   3 bits              2 bits          3 bits        3 bits      3 bits        2 bits      2 bits      0/1/2/4 bytes   0/1/2/4 bytes
 21 
 22 # main:
 23   # if (argc > 1)
 24   8b/copy                         0/mod/indirect  4/rm32/sib    4/base/ESP  4/index/none  .           0/r32/EAX   .               .                 # copy *ESP to EAX
 25   3d/compare                      .               .             .           .             .           .           .               1/imm32           # compare EAX with 1
 26   7e/jump-if-lesser-or-equal  $run_main/disp8
 27   # and if (argv[1] == "test")
 28   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none  .           0/r32/EAX   8/disp8         .                 # copy *(ESP+8) to EAX
 29     # push args
 30   50/push-EAX
 31   68/push  "test"/imm32
 32     # call
 33   e8/call  argv_equal/disp32
 34     # discard args
 35   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add 8 to ESP
 36     # check result
 37   3d/compare                      .               .             .           .             .           .           .               1/imm32           # compare EAX with 1
 38   75/jump-if-not-equal  $run_main/disp8
 39   # then
 40   e8/call  run_tests/disp32
 41   eb/jump  $main_exit/disp8
 42   # else EAX <- factorial(5)
 43 $run_main:
 44     # push arg
 45   68/push  5/imm32
 46     # EAX <- call
 47   e8/call  factorial/disp32
 48     # discard arg
 49   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
 50 $main_exit:
 51   # exit(EAX)
 52   89/copy                         3/mod/direct    3/rm32/EBX    .           .             .           0/r32/EAX   .               .                 # copy EAX to EBX
 53   b8/copy                         .               .             .           .             .           .           .               1/imm32           # copy 1 to EAX
 54   cd/syscall  0x80/imm8
 55 
 56 # factorial(n)
 57 factorial:
 58   # initialize EAX to 1 (base case)
 59   b8/copy                         .               .             .           .             .           .           .               1/imm32           # copy 1 to EAX
 60   # if (n <= 1) jump exit
 61   81          7/subop/compare     1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none  .           .           4/disp8         1/imm32           # compare *(ESP+4) with 1
 62   7e/jump-if-<=  $factorial:exit/disp8
 63   # EBX: n-1
 64   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none              3/r32/EBX   4/disp8         .                 # copy *(ESP+4) to EBX
 65   81          5/subop/subtract    3/mod/direct    3/rm32/EBX    .           .             .           .           .               1/imm32           # subtract 1 from EBX
 66   # prepare call
 67   55/push-EBP
 68   89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
 69   # EAX: factorial(n-1)
 70   53/push-EBX
 71   e8/call                         .               .             .           .             .           .           factorial/disp32
 72   # discard arg
 73   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
 74   # clean up after call
 75   89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
 76   5d/pop                          .               .             .           .             .           .           .               .                 # pop to EBP
 77   # refresh n
 78   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none              2/r32/EDX   4/disp8         .                 # copy *(ESP+4) to EDX
 79   # return n * factorial(n-1)
 80   f7          4/subop/multiply    1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none                          4/disp8         .                 # multiply *(ESP+4) (n) into EAX (factorial(n-1))
 81   # TODO: check for overflow
 82 $factorial:exit:
 83   c3/return
 84 
 85 test_factorial:
 86   # factorial(5)
 87     # push arg
 88   68/push  5/imm32
 89     # call
 90   e8/call  factorial/disp32
 91     # discard arg
 92   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
 93   # check_ints_equal(EAX, 120, failure message)
 94     # push args
 95   50/push-EAX
 96   68/push  0x78/imm32/expected-120
 97   68/push  "F - test_factorial"/imm32
 98     # call
 99   e8/call  check_ints_equal/disp32
100     # discard args
101   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               0xc/imm32         # add 12 to ESP
102   # end
103   c3/return
104 
105 ## helpers
106 
107 # print msg to stderr if a != b, otherwise print "."
108 check_ints_equal:  # (a : int, b : int, msg : (address array byte)) -> boolean
109   # load args into EAX, EBX and ECX
110   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none  .           0/r32/EAX   0xc/disp8       .                 # copy *(ESP+12) to EAX
111   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none  .           3/r32/EBX   0x8/disp8       .                 # copy *(ESP+8) to EBX
112   # if EAX == b/EBX
113   39/compare                      3/mod/direct    0/rm32/EAX    .           .             .           3/r32/EBX   .               .                 # compare EAX and EBX
114   75/jump-if-unequal  $check_ints_equal:else/disp8
115     # print('.')
116       # push args
117   68/push  "."/imm32
118       # call
119   e8/call  write_stderr/disp32
120       # discard arg
121   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
122     # return
123   c3/return
124   # else:
125 $check_ints_equal:else:
126   # copy msg into ECX
127   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none  .           1/r32/ECX   4/disp8         .                 # copy *(ESP+4) to ECX
128     # print(ECX)
129       # push args
130   51/push-ECX
131       # call
132   e8/call  write_stderr/disp32
133       # discard arg
134   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
135     # print newline
136       # push args
137   68/push  Newline/imm32
138       # call
139   e8/call  write_stderr/disp32
140       # discard arg
141   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
142   # end
143   c3/return
144 
145 # compare a null-terminated ascii string with a more idiomatic length-prefixed byte array
146 # reason for the name: the only place we should have null-terminated ascii strings is from commandline args
147 argv_equal:  # s : null-terminated ascii string, benchmark : length-prefixed ascii string -> EAX : boolean
148   # pseudocode:
149   #   initialize n = b.length
150   #   initialize s1 = s
151   #   initialize s2 = b.data
152   #   i = 0
153   #   for (i = 0; i < n; ++n)
154   #     c1 = *s1
155   #     c2 = *s2
156   #     if c1 == 0
157   #       return false
158   #     if c1 != c2
159   #       return false
160   #   return *s1 == 0
161 +-- 45 lines: # --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
206 +--134 lines: # tests for argv_equal -----------------------------------------------------------------------------------------------------------------------------------------------------------------------
340 
341 write_stderr:  # s : (address array byte) -> <void>
342   # save registers
343   50/push-EAX
344   51/push-ECX
345   52/push-EDX
346   53/push-EBX
347   # write(2/stderr, (data) s+4, (size) *s)
348     # fd = 2 (stderr)
349   bb/copy                         .               .             .           .             .           .           .               2/imm32           # copy 2 to EBX
350     # x = s+4
351   8b/copy                         1/mod/*+disp8   4/rm32/SIB    4/base/ESP  4/index/none  .           1/r32/ECX   0x14/disp8      .                 # copy *(ESP+20) to ECX
352   81          0/subop/add         3/mod/direct    1/rm32/ECX    .           .             .           .           .               4/imm32           # add 4 to ECX
353     # size = *s
354   8b/copy                         1/mod/*+disp8   4/rm32/SIB    4/base/ESP  4/index/none  .           2/r32/EDX   0x14/disp8      .                 # copy *(ESP+20) to EDX
355   8b/copy                         0/mod/indirect  2/rm32/EDX    .           .             .           2/r32/EDX   .               .                 # copy *EDX to EDX
356     # call write()
357   b8/copy                         .               .             .           .             .           .           .               4/imm32/write     # copy 1 to EAX
358   cd/syscall  0x80/imm8
359   # restore registers
360   5b/pop-EBX
361   5a/pop-EDX
362   59/pop-ECX
363   58/pop-EAX
364   # end
365   c3/return
366 
367 == data
368 Newline:
369   # size
370   01 00 00 00
371   # data
372   0a/newline
373 
374 # for argv_equal tests
375 Null_argv:
376   00/null
377 Abc_argv:
378   41/A 62/b 63/c 00/null
379 
380 # vim:ft=subx:nowrap:so=0