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