qsort.c 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195
  1. #include <stdlib.h>
  2. // Do not use register a5; callback function might need it.
  3. register long __tbl asm ("a5");
  4. // This is not a quick sort, it's a shell sort.
  5. // For sorting data that has no significant statistical property, on embedded platforms
  6. // without processor caches, the shell sort is one of the very best size/speed tradeoffs.
  7. __ATTR_LIB_C__ void qsort(void *list, short num_items, short size, compare_t cmp_func);
  8. asm("
  9. | d3 <- p
  10. | d4 <- a+byte_gap
  11. | d5 <- k
  12. | d6 <- i
  13. | d7 <- size
  14. | a2 <- cmp_func
  15. | a3 <- byte_gap
  16. | a4 <- list
  17. | a6 <- num_items * size
  18. .text
  19. .even
  20. .globl qsort
  21. qsort:
  22. movem.l %d3-%d7/%a2-%a4/%a6,-(%sp)
  23. move.l %a0,%a4 ;# list, list
  24. move.w %d1,%d7 ;# size, size
  25. move.l %a1,%a2 ;# cmp_func, cmp_func
  26. move.w #4096,%d5 ;#, k
  27. cmp.w #16,%d0 ;#, num_items
  28. bhi.s .L4 ;#
  29. moveq #1,%d5 ;#, k
  30. .L4:
  31. mulu.w %d7,%d0 ;# size, num_items
  32. move.w %d0,%a6 ;# num_items, num_items.61
  33. bra.s .L5 ;#
  34. .L6:
  35. move.w %d5,%d6 ;# k, i
  36. mulu.w %d7,%d6 ;# size, i
  37. move.l %d6,%d0 ;# i, byte_gap
  38. neg.l %d0
  39. move.l %d0,%a3
  40. bra.s .L7 ;#
  41. .L8:
  42. moveq #0,%d0 ;# i
  43. move.w %d6,%d0 ;# i, i
  44. move.l %a4,%d3 ;# list, p
  45. add.l %d0,%d3 ;# i, p
  46. add.l %a3,%d3 ;# D.1283, p
  47. move.l %d3,%d4 ;# p, ivtmp.60
  48. sub.l %a3,%d4 ;# D.1283, ivtmp.60
  49. bra.s .L9 ;#
  50. .L10:
  51. move.l %d4,-(%sp) ;# ivtmp.60,
  52. move.l %d3,-(%sp) ;# p,
  53. jsr (%a2) ;#
  54. addq.l #8,%sp ;#,
  55. tst.w %d0 ;#
  56. ble.s .L11 ;#
  57. move.l %d4,%a1 ;# ivtmp.60, ivtmp.47
  58. move.w %d7,%d1 ;# size, j
  59. move.l %d3,%a0 ;# p, a
  60. subq.w #1,%d1 ;#
  61. .L14:
  62. move.b (%a0),%d0 ;#* a, temp
  63. move.b (%a1),(%a0)+ ;#* ivtmp.47,
  64. move.b %d0,(%a1)+ ;# temp,
  65. dbf %d1,.L14 ;#, j
  66. add.l %a3,%d3 ;# D.1283, p
  67. add.l %a3,%d4 ;# ivtmp.53, ivtmp.60
  68. .L9:
  69. cmp.l %d3,%a4 ;# p, list
  70. bls.s .L10 ;#
  71. .L11:
  72. add.w %d7,%d6 ;# size, i
  73. .L7:
  74. cmp.w %a6,%d6 ;# num_items.61, i
  75. bcs.s .L8 ;#
  76. lsr.w #1,%d5 ;#, tmp59
  77. move.w %d5,%d0 ;# k, tmp60
  78. lsr.w #3,%d0 ;#, tmp60
  79. sub.w %d0,%d5 ;# tmp60, k
  80. .L5:
  81. tst.w %d5 ;# k
  82. bne.s .L6 ;#
  83. movm.l (%sp)+,%d3-%d7/%a2-%a4/%a6
  84. rts
  85. ");
  86. // The assembly routine above was created using the following C code as a starting point:
  87. /*{
  88. unsigned short byte_gap,i;
  89. short j;
  90. unsigned short k;
  91. char *p,*a,temp;
  92. k = ((unsigned short)num_items <= 16) ? 1 : 4096;
  93. num_items = (unsigned short)num_items * (unsigned short)size;
  94. for (; k > 0; k = (k>>1) - (k>>4)) {
  95. byte_gap=k*(unsigned short)size;
  96. for(i=byte_gap; i<(unsigned short)num_items; i+=size) {
  97. for(p=(char*)list+i-byte_gap; p>=(char*)list; p-= byte_gap) {
  98. a=p;
  99. if(cmp_func(a,a+byte_gap)<=0) break;
  100. for(j=size;j;j--) {
  101. temp=*a; *a=*(a+byte_gap); *(a+byte_gap)=temp; a++;
  102. }
  103. }
  104. }
  105. }
  106. }*/
  107. // Compiling it with -Os under GCC 4.1.2-tigcc-4 yielded:
  108. /*
  109. subq.w #8,%sp
  110. movm.l #0x1f3a,-(%sp)
  111. move.l %a0,%a4 ;# list, list
  112. move.w %d1,%d7 ;# size, size
  113. move.l %a1,40(%sp) ;# cmp_func, cmp_func
  114. muls.w %d1,%d0 ;# size, num_items
  115. move.w %d0,%a3 ;# num_items, num_items.60
  116. move.w #4096,%d2 ;#, k
  117. moveq #16,%d0 ;#,
  118. cmp.w %a3,%d0 ;# num_items.60,
  119. jbcs .L18 ;#
  120. moveq #1,%d2 ;#, k
  121. jbra .L18 ;#
  122. .L5:
  123. move.w %d2,%d6 ;# k, i
  124. muls.w %d7,%d6 ;# size, i
  125. move.w %d6,%a6 ;# i, byte_gap
  126. jbra .L6 ;#
  127. .L7:
  128. moveq #0,%d5 ;# D.1283
  129. move.w %a6,%d5 ;# byte_gap, D.1283
  130. moveq #0,%d0 ;# i
  131. move.w %d6,%d0 ;# i, i
  132. move.l %a4,%d3 ;# list, p
  133. add.l %d0,%d3 ;# i, p
  134. sub.l %d5,%d3 ;# D.1283, p
  135. move.l %d5,%d0 ;# D.1283,
  136. neg.l %d0 ;#
  137. move.l %d0,%a2 ;#, ivtmp.53
  138. move.l %d3,%d4 ;# p, ivtmp.59
  139. add.l %d5,%d4 ;# D.1283, ivtmp.59
  140. jbra .L8 ;#
  141. .L9:
  142. move.l %d4,-(%sp) ;# ivtmp.59,
  143. move.l %d3,-(%sp) ;# p,
  144. move.l %d2,44(%sp) ;#,
  145. move.l 48(%sp),%a0 ;# cmp_func,
  146. jbsr (%a0) ;#
  147. addq.l #8,%sp ;#,
  148. move.l 36(%sp),%d2 ;#,
  149. tst.w %d0 ;#
  150. jble .L10 ;#
  151. move.l %d4,%a1 ;# ivtmp.59, ivtmp.47
  152. move.w %d7,%d1 ;# size, j
  153. move.l %d3,%a0 ;# p, a
  154. jbra .L12 ;#
  155. .L13:
  156. move.b (%a0),%d0 ;#* a, temp
  157. move.b (%a1),(%a0)+ ;#* ivtmp.47,
  158. move.b %d0,(%a1)+ ;# temp,
  159. subq.w #1,%d1 ;#, j
  160. .L12:
  161. tst.w %d1 ;# j
  162. jbne .L13 ;#
  163. sub.l %d5,%d3 ;# D.1283, p
  164. add.l %a2,%d4 ;# ivtmp.53, ivtmp.59
  165. .L8:
  166. cmp.l %d3,%a4 ;# p, list
  167. jbls .L9 ;#
  168. .L10:
  169. add.w %d7,%d6 ;# size, i
  170. .L6:
  171. cmp.w %a3,%d6 ;# num_items.60, i
  172. jbcs .L7 ;#
  173. move.w %d2,%d1 ;# k, tmp58
  174. lsr.w #1,%d1 ;#, tmp58
  175. move.w %d2,%d0 ;# k, tmp59
  176. lsr.w #4,%d0 ;#, tmp59
  177. move.w %d1,%d2 ;# tmp58, k
  178. sub.w %d0,%d2 ;# tmp59, k
  179. .L18:
  180. tst.w %d2 ;# k
  181. jbne .L5 ;#
  182. movm.l (%sp)+,#0x5cf8
  183. addq.w #8,%sp
  184. rts
  185. */
  186. // In six steps, 30 bytes were saved, yielding the ASM routine at the top of this file.