Changeset 1357


Ignore:
Timestamp:
07/21/09 14:13:26 (3 years ago)
Author:
debrouxl
Message:

tigcclib: save 20 bytes on the shell sort implementation used in qsort(), while making it faster for all array sizes.
While at it: in the "Sort Integers" example, use integer comparison instead of floating-point comparison...

Location:
trunk/tigcc
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/tigcc/archive/qsort.c

    r1307 r1357  
    44register long __tbl asm ("a5"); 
    55 
    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 
     11asm(" 
     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 
     24qsort: 
     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        } 
    21113    } 
    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  
    1313CALLBACK short int_comp(const void *a, const void *b) 
    1414{ 
    15   return fcmp (*(const short*)a, *(const short*)b); 
     15  return (*(const short*)a) - (*(const short*)b); 
    1616} 
    1717 
Note: See TracChangeset for help on using the changeset viewer.