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 an automated test (that does the exact same thing):
 11 #   $ subx run apps/factorial test
 12 # Expected output:
 13 #   .
 14 # Every '.' indicates a passing test. Failing tests get a 'F'.
 15 
 16 == code
 17 # instruction                     effective address                                                   operand     displacement    immediate
 18 # op          subop               mod             rm32          base        index         scale       r32
 19 # 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
 20 
 21 # main:
 22   # if (argc > 1)
 23   8b/copy                         0/mod/indirect  4/rm32/sib    4/base/ESP  4/index/none  .           0/r32/EAX   .               .                 # copy *ESP to EAX
 24   3d/compare                      .               .             .           .             .           .           .               1/imm32           # compare EAX with 1
 25   7e/jump-if-lesser-or-equal  $run_main/disp8
 26   # and if (argv[1] == "test")
 27   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none  .           0/r32/EAX   8/disp8         .                 # copy *(ESP+8) to EAX
 28     # push args
 29   68/push  Test_argv/imm32
 30   50/push-EAX
 31     # call
 32   e8/call  argv_equal/disp32
 33     # discard args
 34   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               8/imm32           # add 8 to ESP
 35     # check result
 36   3d/compare                      .               .             .           .             .           .           .               1/imm32           # compare EAX with 1
 37   75/jump-if-not-equal  $run_main/disp8
 38   # then
 39   e8/call  run_tests/disp32
 40   eb/jump  $main_exit/disp8
 41   # else EAX <- factorial(5)
 42 $run_main:
 43     # push arg
 44   68/push                         .               .             .           .             .           .           .               5/imm32           # push 5
 45     # EAX <- call
 46   e8/call                         .               .             .           .             .           .           factorial/disp32
 47     # discard arg
 48   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
 49 $main_exit:
 50   # exit(EAX)
 51   89/copy                         3/mod/direct    3/rm32/EBX    .           .             .           0/r32/EAX   .               .                 # copy EAX to EBX
 52   b8/copy                         .               .             .           .             .           .           .               1/imm32           # copy 1 to EAX
 53   cd/syscall  0x80/imm8
 54 
 55 # factorial(n)
 56 factorial:
 57   # initialize EAX to 1 (base case)
 58   b8/copy                         .               .             .           .             .           .           .               1/imm32           # copy 1 to EAX
 59   # if (n <= 1) jump exit
 60   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
 61   7e/jump-if-<=                   .               .             .           .             .           .           $factorial:exit/disp8             # jump if <= to $factorial:exit
 62   # EBX: n-1
 63   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none              3/r32/EBX   4/disp8         .                 # copy *(ESP+4) to EBX
 64   81          5/subop/subtract    3/mod/direct    3/rm32/EBX    .           .             .           .           .               1/imm32           # subtract 1 from EBX
 65   # prepare call
 66   55/push                         .               .             .           .             .           .           .               .                 # push EBP
 67   89/copy                         3/mod/direct    5/rm32/EBP    .           .             .           4/r32/ESP   .               .                 # copy ESP to EBP
 68   # EAX: factorial(n-1)
 69   53/push                         .               .             .           .             .           .           .               .                 # push EBX
 70   e8/call                         .               .             .           .             .           .           factorial/disp32
 71   # discard arg
 72   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
 73   # clean up after call
 74   89/copy                         3/mod/direct    4/rm32/ESP    .           .             .           5/r32/EBP   .               .                 # copy EBP to ESP
 75   5d/pop                          .               .             .           .             .           .           .               .                 # pop to EBP
 76   # refresh n
 77   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none              2/r32/EDX   4/disp8         .                 # copy *(ESP+4) to EDX
 78   # return n * factorial(n-1)
 79   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))
 80   # TODO: check for overflow
 81 $factorial:exit:
 82   c3/return
 83 
 84 test_factorial:
 85   # factorial(5)
 86     # push arg
 87   68/push                         .               .             .           .             .           .           .               5/imm32           # push 5
 88     # call
 89   e8/call                         .               .             .           .             .           .           factorial/disp32
 90     # discard arg
 91   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
 92   # if EAX == 120
 93   3d/compare                      .               .             .           .             .           .           .               0x78/imm32/120    # compare EAX with 120
 94   75/jump-if-unequal              .               .             .           .             .           .           $test_factorial:else/disp8
 95     # print('.')
 96       # push args
 97   68/push                         .               .             .           .             .           .           .               Test_passed/imm32
 98       # call
 99   e8/call                         .               .             .           .             .           .           write_stderr/disp32
100       # discard arg
101   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
102     # return
103   c3/return
104   # else:
105 $test_factorial:else:
106     # print('F')
107       # push args
108   68/push                         .               .             .           .             .           .           .               Test_failed/imm32
109       # call
110   e8/call                         .               .             .           .             .           .           write_stderr/disp32
111       # discard arg
112   81          0/subop/add         3/mod/direct    4/rm32/ESP    .           .             .           .           .               4/imm32           # add 4 to ESP
113   # end
114   c3/return
115 
116 ## helpers
117 
118 # compare two null-terminated ascii strings
119 # reason for the name: the only place we should have null-terminated ascii strings is from commandline args
120 argv_equal:  # (s1, s2) : null-terminated ascii strings -> EAX : boolean
121   # initialize s1 (ECX) and s2 (EDX)
122   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none  .           1/r32/ECX   8/disp8         .                 # copy *(ESP+8) to ECX
123   8b/copy                         1/mod/*+disp8   4/rm32/sib    4/base/ESP  4/index/none  .           2/r32/EDX   4/disp8         .                 # copy *(ESP+4) to EDX
124   # while (true)
125 $argv_loop:
126     # c1/EAX, c2/EBX = *s1, *s2
127   b8/copy  0/imm32  # clear EAX
128   8a/copy                         0/mod/indirect  1/rm32/ECX    .           .             .           0/r32/EAX   .               .                 # copy byte at *ECX to lower byte of EAX
129   bb/copy  0/imm32  # clear EBX
130   8a/copy                         0/mod/indirect  2/rm32/EDX    .           .             .           3/r32/EBX   .               .                 # copy byte at *EDX to lower byte of EBX
131     # if (c1 == 0) break
132   3d/compare                      .               .             .           .             .           .           .               0/imm32           # compare EAX with 0
133   74/jump-if-equal  $argv_break/disp8
134     # if (c1 != c2) return false
135   39/compare                      3/mod/direct    0/rm32/EAX    .           .             .           3/r32/EBX   .               .                 # compare EAX with EBX
136   75/jump-if-not-equal  $argv_fail/disp8
137     # ++s1, ++s2
138   41/inc-ECX
139   42/inc-EDX
140   # end while
141   eb/jump  $argv_loop/disp8
142 $argv_break:
143   # if (c2 == 0) return true
144   81          7/subop/compare     3/mod/direct    3/rm32/EBX    .           .             .           .           .               0/imm32           # compare EBX with 0
145   75/jump-if-not-equal  $argv_fail/disp8
146   b8/copy                         .               .             .           .             .           .           .               1/imm32           # copy 1 to EAX
147   c3/return
148   # return false
149 $argv_fail:
150   b8/copy                         .               .             .           .             .           .           .               0/imm32           # copy 0 to EAX
151   c3/return
152 
153 write_stderr:  # s : (address array byte) -> <void>
154   # save registers
155   50/push                         .               .             .           .             .           .           .               .                 # push EAX
156   51/push                         .               .             .           .             .           .           .               .                 # push ECX
157   52/push                         .               .             .           .             .           .           .               .                 # push EDX
158   53/push                         .               .             .           .             .           .           .               .                 # push EBX
159   # write(2/stderr, (data) s+4, (size) *s)
160     # fd = 2 (stderr)
161   bb/copy                         .               .             .           .             .           .           .               2/imm32           # copy 2 to EBX
162     # x = s+4
163   8b/copy                         1/mod/*+disp8   4/rm32/SIB    4/base/ESP  4/index/none  .           1/r32/ECX   0x14/disp8      .                 # copy *(ESP+20) to ECX
164   81          0/subop/add         3/mod/direct    1/rm32/ECX    .           .             .           .           .               4/imm32           # add 4 to ECX
165     # size = *s
166   8b/copy                         1/mod/*+disp8   4/rm32/SIB    4/base/ESP  4/index/none  .           2/r32/EDX   0x14/disp8      .                 # copy *(ESP+20) to EDX
167   8b/copy                         0/mod/indirect  2/rm32/EDX    .           .             .           2/r32/EDX   .               .                 # copy *EDX to EDX
168     # call write()
169   b8/copy                         .               .             .           .             .           .           .               4/imm32/write     # copy 1 to EAX
170   cd/syscall  0x80/imm8
171   # restore registers
172   5b/pop                          .               .             .           .             .           .           .               .                 # pop EBX
173   5a/pop                          .               .             .           .             .           .           .               .                 # pop EDX
174   59/pop                          .               .             .           .             .           .           .               .                 # pop ECX
175   58/pop                          .               .             .           .             .           .           .               .                 # pop EAX
176   # end
177   c3/return
178 
179 == data
180 Test_argv:  # null-terminated
181   # data
182   74/t 65/e 73/s 74/t 00/null
183 
184 Test_passed:
185   # size
186   01 00 00 00
187   # data
188   2e/dot
189 
190 Test_failed:
191   # size
192   01 00 00 00
193   # data
194   46/F
195 
196 # vim:ft=subx:nowrap:so=0