qsort.c 4.4 KB

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