API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 18th, 2019
131
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.33 KB | None | 0 0
raw download clone embed print report
  1. .text
  2.  
  3. # short count_odd_nodes(TreeNode* head) {
  4. # // Base case
  5. # if (head == NULL) {
  6. # return 0;
  7. # }
  8. # // Recurse once for each child
  9. # short count_left = count_odd_nodes(head->left);
  10. # short count_right = count_odd_nodes(head->right);
  11. # short count = count_left + count_right;
  12. # // Determine if this current node is odd
  13. # if (head->value%2 != 0) {
  14. # count += 1;
  15. # }
  16. # return count;
  17. # }
  18.  
  19. .globl count_odd_nodes
  20. count_odd_nodes:
  21. li $v0, 0
  22. beq $a0, $zero, count_odd_nodes_end # branch if (head == NULL)
  23.  
  24. sub $sp, $sp, 16
  25. sw $ra, 0($sp)
  26. sw $v0, 4($sp)
  27. sw $a0, 8 ($sp)
  28.  
  29. lw $a0, 0($a0); # load head->left into $a0
  30. jal count_odd_nodes # count_odd_nodes(head->left)
  31.  
  32. move $t0, $v0 # x = count_odd_nodes(head->left)
  33. sw $t0, 12($sp)
  34.  
  35. lw $t1, 8($sp) # load head->right into $a0
  36. lw $a0, 4($t1)
  37. jal count_odd_nodes # count_odd_nodes(head->right)
  38.  
  39. move $t1, $v0 # y = count_odd_nodes(head->right)
  40.  
  41. lw $t0, 12($sp)
  42. lw $a0, 8($sp)
  43. lw $v0, 4($sp)
  44. lw $ra, 0($sp)
  45. add $sp, $sp, 16
  46.  
  47. add $v0, $t1, $t0 # count = count_left + count_right
  48.  
  49. lh $t3, 8($a0) # load head->value
  50. div $t4, $t3, 2 # divide by 2
  51. mfhi $t4 # load remainder into $t4
  52. beq $t4, $zero, count_odd_nodes_end # branch if !(head->value%2 != 0))
  53. add $v0, $v0, 1 # count += 1
  54.  
  55. count_odd_nodes_end:
  56. jr $ra
  57.  
  58.  
  59.  
  60. .text
  61.  
  62. # bool rule1(unsigned short* board) {
  63. # bool changed = false;
  64. # for (int y = 0 ; y < GRIDSIZE ; y++) {
  65. # for (int x = 0 ; x < GRIDSIZE ; x++) {
  66. # unsigned value = board[y*GRIDSIZE + x];
  67. # if (has_single_bit_set(value)) {
  68. # for (int k = 0 ; k < GRIDSIZE ; k++) {
  69. # // eliminate from row
  70. # if (k != x) {
  71. # if (board[y*GRIDSIZE + k] & value) {
  72. # board[y*GRIDSIZE + k] &= ~value;
  73. # changed = true;
  74. # }
  75. # }
  76. # // eliminate from column
  77. # if (k != y) {
  78. # if (board[k*GRIDSIZE + x] & value) {
  79. # board[k*GRIDSIZE + x] &= ~value;
  80. # changed = true;
  81. # }
  82. # }
  83. # }
  84. # }
  85. # }
  86. # }
  87. # return changed;
  88. # }
  89. #a0: board
  90.  
  91. .globl rule1
  92. rule1:
  93. li $v0, 0 # bool changed = false
  94. li $t1, 0 # int y = 0
  95. li $t0, GRIDSIZE # GRIDSIZE = 4
  96. y_for_loop:
  97. bge $t1, $t0, y_end # branch if !(y < GRIDSIZE)
  98. li $t2, 0 # int x = 0
  99. x_for_loop:
  100. bge $t2, $t0, x_end # branch if !(x < GRIDSIZE)
  101. mul $t3, $t1, $t0 # y * GRIDSIZE
  102. add $t3, $t3, $t2 # y * GRIDSIZE + x
  103. sll $t3, $t3, 1 # 2 bit append
  104. add $t3, $a0, $t3 # load &board[y * GRIDSIZE + x]
  105. lh $t3, 0($t3) # value = board[y * GRIDSIZE + x]
  106.  
  107. sub $sp, $sp, 28
  108. sw $ra, 0($sp)
  109. sw $v0, 4($sp)
  110. sw $a0, 8($sp)
  111. sw $t0, 12($sp)
  112. sw $t1, 16($sp)
  113. sw $t2, 20($sp)
  114. sw $t3, 24($sp)
  115.  
  116. move $a0, $t3 # move value into argument 0
  117. jal has_single_bit_set
  118.  
  119. move $t4, $v0 # output = has_single_bit_set(value)
  120.  
  121. lw $t3, 24($sp)
  122. lw $t2, 20($sp)
  123. lw $t1, 16($sp)
  124. lw $t0, 12($sp)
  125. lw $a0, 8($sp)
  126. lw $v0, 4($sp)
  127. lw $ra, 0($sp)
  128. add $sp, $sp, 28
  129.  
  130. beq $t4, $zero, x_next # branch if !(has_single_bit_set(value))
  131. li $t5, 0 # k = 0
  132. k_for_loop:
  133. bge $t5, $t0, k_end # branch if !(k < GRIDSIZE)
  134. beq $t5, $t2, ky_if # branch if !(k != x)
  135. mul $t6, $t1, $t0 # y * GRIDSIZE
  136. add $t6, $t6, $t5 # y * GRIDSIZE + k
  137. sll $t6, $t6, 1 # 2 bit append
  138. add $t6, $a0, $t6 # load &board[y * GRIDSIZE + k]
  139. lh $t9, 0($t6) # get board[y * GRIDSIZE + k]
  140. and $t7, $t9, $t3 # board[y * GRIDSIZE + k] & value
  141. beq $t7, $zero, ky_if # branch if !(board[y * GRIDSIZE + k] & value)
  142. not $t8, $t3 # $t8 = ~value
  143. and $t9, $t9, $t8 # board[y * GRIDSIZE + k] & ~value
  144. sh $t9, 0($t6) # board[y * GRIDSIZE + k] = board[y * GRIDSIZE + k] & ~value
  145. li $v0, 1 # changed = true
  146.  
  147. ky_if:
  148. beq $t5, $t1, k_next # branch if !(k != y)
  149. mul $t6, $t5, $t0 # k * GRIDSIZE
  150. add $t6, $t6, $t2 # k * GRIDSIZE + x
  151. sll $t6, $t6, 1 # 2 bit append
  152. add $t6, $a0, $t6 # load &board[k * GRIDSIZE + x]
  153. lh $t9, 0($t6) # get board[k * GRIDSIZE + x]
  154. and $t7, $t9, $t3 # board[k * GRIDSIZE + x] & value
  155. beq $t7, $zero, k_next # branch if !(board[k * GRIDSIZE + x] & value)
  156. not $t8, $t3 # $t8 = ~value
  157. and $t9, $t9, $t8 # board[k * GRIDSIZE + x] & ~value
  158. sh $t9, 0($t6) # board[k * GRIDSIZE + x] = board[k * GRIDSIZE + x] & ~value
  159. li $v0, 1 # changed = true
  160.  
  161. k_next:
  162. add $t5, $t5, 1 # k++
  163. j k_for_loop
  164. k_end:
  165. j x_next
  166.  
  167. x_next:
  168. add $t2, $t2, 1 # x++
  169. j x_for_loop
  170. x_end:
  171. j y_next
  172.  
  173. y_next:
  174. add $t1, $t1, 1 # y++
  175. j y_for_loop
  176. y_end:
  177. jr $ra
  178.  
  179.  
  180.  
  181. # bool solve(unsigned short *current_board, unsigned row, unsigned col, Puzzle* puzzle) {
  182. # if (row >= GRIDSIZE || col >= GRIDSIZE) {
  183. # bool done = board_done(current_board, puzzle);
  184. # if (done) {
  185. # copy_board(current_board, puzzle->board);
  186. # }
  187.  
  188. # return done;
  189. # }
  190. # current_board = increment_heap(current_board);
  191.  
  192. # bool changed;
  193. # do {
  194. # changed = rule1(current_board);
  195. # changed |= rule2(current_board);
  196. # } while (changed);
  197.  
  198. # short possibles = current_board[row*GRIDSIZE + col];
  199. # for(char number = 0; number < GRIDSIZE; ++number) {
  200. # // Remember & is a bitwise operator
  201. # if ((1 << number) & possibles) {
  202. # current_board[row*GRIDSIZE + col] = 1 << number;
  203. # unsigned next_row = ((col == GRIDSIZE-1) ? row + 1 : row);
  204. # if (solve(current_board, next_row, (col + 1) % GRIDSIZE, puzzle)) {
  205. # return true;
  206. # }
  207. # current_board[row*GRIDSIZE + col] = possibles;
  208. # }
  209. # }
  210. # return false;
  211. # }
  212.  
  213. .globl solve
  214. solve:
  215. li $t0, GRIDSIZE # GRIDSIZE = 4
  216. sge $t1, $a1, $t0 # row >= GRIDSIZE
  217. sge $t2, $a2, $t0 # col >= GRIDSIZE
  218. or $t1, $t1, $t2 # row >= GRIDSIZE || col >= GRIDSIZE
  219. beq $t1, $zero, set_current_board # branch if !(row >= GRIDSIZE || col >= GRIDSIZE)
  220.  
  221. sub $sp, $sp, 24
  222. sw $ra, 0($sp)
  223. sw $a0, 4($sp)
  224. sw $a1, 8($sp)
  225. sw $a2, 12($sp)
  226. sw $a3, 16($sp)
  227. sw $t0, 20($sp)
  228.  
  229. move $a1, $a3 # set the second argument to puzzle
  230. jal board_done
  231.  
  232. lw $ra, 0($sp)
  233. lw $a0, 4($sp)
  234. lw $a1, 8($sp)
  235. lw $a2, 12($sp)
  236. lw $a3, 16($sp)
  237. lw $t0, 20($sp)
  238. add $sp, $sp, 24
  239.  
  240. beq $v0, $zero, solve_end # branch if !(done)
  241.  
  242. sub $sp, $sp, 28
  243. sw $ra, 0($sp)
  244. sw $a0, 4($sp)
  245. sw $a1, 8($sp)
  246. sw $a2, 12($sp)
  247. sw $a3, 16($sp)
  248. sw $t0, 20($sp)
  249. sw $v0, 24($sp)
  250.  
  251. la $a1, 0($a3) # set the second argument to puzzle->board
  252. jal copy_board
  253.  
  254. lw $ra, 0($sp)
  255. lw $a0, 4($sp)
  256. lw $a1, 8($sp)
  257. lw $a2, 12($sp)
  258. lw $a3, 16($sp)
  259. lw $t0, 20($sp)
  260. lw $v0, 24($sp)
  261. add $sp, $sp, 28
  262.  
  263. j solve_end
  264.  
  265. set_current_board:
  266.  
  267. sub $sp, $sp, 24
  268. sw $ra, 0($sp)
  269. sw $a0, 4($sp)
  270. sw $a1, 8($sp)
  271. sw $a2, 12($sp)
  272. sw $a3, 16($sp)
  273. sw $t0, 20($sp)
  274.  
  275. jal increment_heap
  276.  
  277. lw $ra, 0($sp)
  278. lw $a0, 4($sp)
  279. lw $a1, 8($sp)
  280. lw $a2, 12($sp)
  281. lw $a3, 16($sp)
  282. lw $t0, 20($sp)
  283. add $sp, $sp, 24
  284.  
  285. move $a0, $v0 # current_board = increment_heap(current_board)
  286. do_while:
  287. sub $sp, $sp, 28
  288. sw $ra, 0($sp)
  289. sw $a0, 4($sp)
  290. sw $a1, 8($sp)
  291. sw $a2, 12($sp)
  292. sw $a3, 16($sp)
  293. sw $t0, 20($sp)
  294.  
  295. jal rule1
  296. move $t1, $v0 # changed = rule1(current_board)
  297. sw $t1, 24($sp)
  298. jal rule2
  299. move $t2, $v0 # $t2 = rule2(current_board)
  300. lw $t1, 24($sp)
  301.  
  302. or $t1, $t1, $t2 # changed = changed | rule2(current_board)
  303.  
  304. lw $ra, 0($sp)
  305. lw $a0, 4($sp)
  306. lw $a1, 8($sp)
  307. lw $a2, 12($sp)
  308. lw $a3, 16($sp)
  309. lw $t0, 20($sp)
  310. add $sp, $sp, 28
  311.  
  312. beq $t1, $zero, set_possibles # branch if !(changed)
  313. j do_while
  314.  
  315.  
  316.  
  317. set_possibles:
  318. mul $t1, $t0, $a1 # row * GRIDSIZE
  319. add $t1, $t1, $a2 # row * GRIDSIZE + col
  320. sll $t1, $t1, 1 # 2 bit append
  321. add $t1, $a0, $t1 # load &current_board[row * GRIDSIZE + col]
  322. lh $t2, 0($t1) # short possibles = current_board[row * GRIDSIZE + col]
  323. li $t3, 0 # char number = 0
  324.  
  325. solve_for_loop:
  326. bgt $t3, $t0, solve_for_loop_end # branch if !(number < GRIDSIZE)
  327. li $t8, 1 # $t8 = 1
  328. sll $t4, $t8, $t3 # 1 << number
  329. and $t4, $t4, $t2 # 1 << number & possibles
  330. beq $t4, $zero, solve_for_loop_next # branch if !(1 << number & possibles)
  331.  
  332. sll $t4, $t8, $t3 # 1 << number
  333. sh $t4, 0($t1) # current_board[row * GRIDSIZE + col] = 1 << number
  334.  
  335. sub $t6, $t0, 1 # GRIDSIZE - 1
  336. bne $a2, $t6, set_row # branch if !(col == GRIDSIZE - 1)
  337. add $t5, $a1, 1 # next_row = row + 1
  338. j if_solve
  339. set_row:
  340. move $t5, $a1 # next_row = row
  341.  
  342. if_solve:
  343. sub $sp, $sp, 52
  344. sw $ra, 0($sp)
  345. sw $a0, 4($sp)
  346. sw $a1, 8($sp)
  347. sw $a2, 12($sp)
  348. sw $a3, 16($sp)
  349. sw $t0, 20($sp)
  350. sw $t1, 24($sp)
  351. sw $t2, 28($sp)
  352. sw $t3, 32($sp)
  353. sw $t4, 36($sp)
  354. sw $t5, 40($sp)
  355. sw $t6, 44($sp)
  356. sw $v0, 48($sp)
  357.  
  358. move $a1, $t5 # move next_row into argument 1
  359. add $t1, $a2, 1 # col + 1
  360. div $t1, $t1, $t0 # col + 1 / GRIDSIZE
  361. mfhi $t2 # col + 1 % GRIDSIZE
  362. move $a2, $t2 # move col + 1 & GRIDSIZE into argument 2
  363.  
  364. jal solve
  365.  
  366. move $t7, $v0 # x = solve(current_board, next_row, (col + 1) % GRIDSIZE, puzzle)
  367.  
  368. lw $ra, 0($sp)
  369. lw $a0, 4($sp)
  370. lw $a1, 8($sp)
  371. lw $a2, 12($sp)
  372. lw $a3, 16($sp)
  373. lw $t0, 20($sp)
  374. lw $t1, 24($sp)
  375. lw $t2, 28($sp)
  376. lw $t3, 32($sp)
  377. lw $t4, 36($sp)
  378. lw $t5, 40($sp)
  379. lw $t6, 44($sp)
  380. lw $v0, 48($sp)
  381. add $sp, $sp, 52
  382.  
  383.  
  384. beq $t7, $zero, final_set # branch if !(solve(current_board, next_row, (col + 1) % GRIDSIZE, puzzle))
  385. li $v0, 1 # return true
  386. j solve_end
  387.  
  388. final_set:
  389. sh $t2, 0($t1) # current_board[row * GRIDSIZE + col] = possibles
  390. solve_for_loop_next:
  391. add $t3, $t3, 1 # ++number
  392. j solve_for_loop
  393.  
  394. solve_for_loop_end:
  395. li $v0, 0 # return false
  396. j solve_end;
  397. solve_end:
  398. jr $ra
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!