qsort.c 4.4 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. .L6:
  34. move.w %d5,%d6 ;# k, i
  35. mulu.w %d7,%d6 ;# size, i
  36. move.l %d6,%d0 ;# i, byte_gap
  37. neg.l %d0
  38. move.l %d0,%a3
  39. bra.s .L7 ;#
  40. .L8:
  41. moveq #0,%d0 ;# i
  42. move.w %d6,%d0 ;# i, i
  43. move.l %a4,%d3 ;# list, p
  44. add.l %d0,%d3 ;# i, p
  45. add.l %a3,%d3 ;# D.1283, p
  46. move.l %d3,%d4 ;# p, ivtmp.60
  47. sub.l %a3,%d4 ;# D.1283, ivtmp.60
  48. bra.s .L9 ;#
  49. .L10:
  50. move.l %d4,-(%sp) ;# ivtmp.60,
  51. move.l %d3,-(%sp) ;# p,
  52. jsr (%a2) ;#
  53. addq.l #8,%sp ;#,
  54. tst.w %d0 ;#
  55. ble.s .L11 ;#
  56. move.l %d4,%a1 ;# ivtmp.60, ivtmp.47
  57. move.w %d7,%d1 ;# size, j
  58. move.l %d3,%a0 ;# p, a
  59. subq.w #1,%d1 ;#
  60. .L14:
  61. move.b (%a0),%d0 ;#* a, temp
  62. move.b (%a1),(%a0)+ ;#* ivtmp.47,
  63. move.b %d0,(%a1)+ ;# temp,
  64. dbf %d1,.L14 ;#, j
  65. add.l %a3,%d3 ;# D.1283, p
  66. add.l %a3,%d4 ;# ivtmp.53, ivtmp.60
  67. .L9:
  68. cmp.l %d3,%a4 ;# p, list
  69. bls.s .L10 ;#
  70. .L11:
  71. add.w %d7,%d6 ;# size, i
  72. .L7:
  73. cmp.w %a6,%d6 ;# num_items.61, i
  74. bcs.s .L8 ;#
  75. lsr.w #1,%d5 ;#, tmp59
  76. move.w %d5,%d0 ;# k, tmp60
  77. lsr.w #3,%d0 ;#, tmp60
  78. sub.w %d0,%d5 ;# tmp60, k
  79. bne.s .L6 ;#
  80. movem.l (%sp)+,%d3-%d7/%a2-%a4/%a6
  81. rts
  82. ");
  83. // The assembly routine above was created using the following C code as a starting point:
  84. /*{
  85. unsigned short byte_gap,i;
  86. short j;
  87. unsigned short k;
  88. char *p,*a,temp;
  89. k = ((unsigned short)num_items <= 16) ? 1 : 4096;
  90. num_items = (unsigned short)num_items * (unsigned short)size;
  91. for (; k > 0; k = (k>>1) - (k>>4)) {
  92. byte_gap=k*(unsigned short)size;
  93. for(i=byte_gap; i<(unsigned short)num_items; i+=size) {
  94. for(p=(char*)list+i-byte_gap; p>=(char*)list; p-= byte_gap) {
  95. a=p;
  96. if(cmp_func(a,a+byte_gap)<=0) break;
  97. for(j=size;j;j--) {
  98. temp=*a; *a=*(a+byte_gap); *(a+byte_gap)=temp; a++;
  99. }
  100. }
  101. }
  102. }
  103. }*/
  104. // Compiling it with -Os under GCC 4.1.2-tigcc-4 yielded:
  105. /*
  106. subq.w #8,%sp
  107. movm.l #0x1f3a,-(%sp)
  108. move.l %a0,%a4 ;# list, list
  109. move.w %d1,%d7 ;# size, size
  110. move.l %a1,40(%sp) ;# cmp_func, cmp_func
  111. muls.w %d1,%d0 ;# size, num_items
  112. move.w %d0,%a3 ;# num_items, num_items.60
  113. move.w #4096,%d2 ;#, k
  114. moveq #16,%d0 ;#,
  115. cmp.w %a3,%d0 ;# num_items.60,
  116. jbcs .L18 ;#
  117. moveq #1,%d2 ;#, k
  118. jbra .L18 ;#
  119. .L5:
  120. move.w %d2,%d6 ;# k, i
  121. muls.w %d7,%d6 ;# size, i
  122. move.w %d6,%a6 ;# i, byte_gap
  123. jbra .L6 ;#
  124. .L7:
  125. moveq #0,%d5 ;# D.1283
  126. move.w %a6,%d5 ;# byte_gap, D.1283
  127. moveq #0,%d0 ;# i
  128. move.w %d6,%d0 ;# i, i
  129. move.l %a4,%d3 ;# list, p
  130. add.l %d0,%d3 ;# i, p
  131. sub.l %d5,%d3 ;# D.1283, p
  132. move.l %d5,%d0 ;# D.1283,
  133. neg.l %d0 ;#
  134. move.l %d0,%a2 ;#, ivtmp.53
  135. move.l %d3,%d4 ;# p, ivtmp.59
  136. add.l %d5,%d4 ;# D.1283, ivtmp.59
  137. jbra .L8 ;#
  138. .L9:
  139. move.l %d4,-(%sp) ;# ivtmp.59,
  140. move.l %d3,-(%sp) ;# p,
  141. move.l %d2,44(%sp) ;#,
  142. move.l 48(%sp),%a0 ;# cmp_func,
  143. jbsr (%a0) ;#
  144. addq.l #8,%sp ;#,
  145. move.l 36(%sp),%d2 ;#,
  146. tst.w %d0 ;#
  147. jble .L10 ;#
  148. move.l %d4,%a1 ;# ivtmp.59, ivtmp.47
  149. move.w %d7,%d1 ;# size, j
  150. move.l %d3,%a0 ;# p, a
  151. jbra .L12 ;#
  152. .L13:
  153. move.b (%a0),%d0 ;#* a, temp
  154. move.b (%a1),(%a0)+ ;#* ivtmp.47,
  155. move.b %d0,(%a1)+ ;# temp,
  156. subq.w #1,%d1 ;#, j
  157. .L12:
  158. tst.w %d1 ;# j
  159. jbne .L13 ;#
  160. sub.l %d5,%d3 ;# D.1283, p
  161. add.l %a2,%d4 ;# ivtmp.53, ivtmp.59
  162. .L8:
  163. cmp.l %d3,%a4 ;# p, list
  164. jbls .L9 ;#
  165. .L10:
  166. add.w %d7,%d6 ;# size, i
  167. .L6:
  168. cmp.w %a3,%d6 ;# num_items.60, i
  169. jbcs .L7 ;#
  170. move.w %d2,%d1 ;# k, tmp58
  171. lsr.w #1,%d1 ;#, tmp58
  172. move.w %d2,%d0 ;# k, tmp59
  173. lsr.w #4,%d0 ;#, tmp59
  174. move.w %d1,%d2 ;# tmp58, k
  175. sub.w %d0,%d2 ;# tmp59, k
  176. .L18:
  177. tst.w %d2 ;# k
  178. jbne .L5 ;#
  179. movm.l (%sp)+,#0x5cf8
  180. addq.w #8,%sp
  181. rts
  182. */
  183. // In six steps, 30 bytes were saved, yielding the ASM routine at the top of this file.