;/* a-wada/qsortlib/ccg/qsortsn.asm Mar. 29, 2008 */ ;/* Copyright (c) 2008 Akira Wada */ ;/* qsortsn.asm modified from qsortsn.c, */ ;/* compiled on Win2000 by bcc32 5.5 with " -5 -O2 -S " into */ ;/* http://www.mars.dti.ne.jp/a-wada/qsortlib/ccg/qsortsno.asm */ ;/* and then optimized in Asm manually by A. Wada */ ; .586p model flat _TEXT segment dword public use32 'CODE' align 4 _qsort proc near ;/* a-wada/qsortlib/ccg/qsortsn.c Mar. 23, 2008 */ ;/* Copyright (c) 2008 Akira Wada */ ; ;/* qsortsn.c was updated to be reentlant for system resident kernel routine,*/ ;/* and also random.c was modified from random.c in FreeBSD. */ ; ;/* qsortsn.c was modified from qsortskb.c using "New Partitioning Methoed" */ ;/* to reduce swaps without large increasing of comparisons, suggested from */ ;/* http://src.opensolaris.org/source/raw/onnv/onnv-gate/usr/src/common/util */ ;/* /qsort.c 06-Jan-2006, */ ;/* ie. when scan encounters pivot itself, skip over it wihtout comparison, */ ;/* instead of stopping and swapping, and later move pivot to final position */ ; ;/* Quick sort compatible with "qsort (); in " */ ;/* efficiency by reducing the times of key comparisons and */ ;/* word_mode_swapping for word_aligned object */ ;/* prevention from the degeneration caused by peculiar input */ ;/* This qsort is not stable, but could avoid the bad behavior by many */ ;/* equal sort-keys. For stability, add a unique-key to compare-function.*/ ; ;/* If the object to be sorted is an array of pointers to structs with */ ;/* an unsigned integer key, set the 4'th argument to NULL and the 3'rd */ ;/* to byte-position of the key in the struct, to call RADIX-SORT. */ ;/* For example : kps = 16; qsort (pv, n, kps, NULL); */ ;#include ;long srandom (long); ;long random (long); ;void radixspi (void *, size_t, size_t); ; ;#define MDT 16 /* threshold for median of the 5 or the more, MDT >= 8 */ ;#define MDA 2 /* adjusting threshold slightly, MDT + MDA >= 4 */ ;#define MDM 2 /* multiplier for threshold, MDM >= 2 */ ; ;#define COMP(i, j) (*cf)(i, j) ;#define SZI sizeof (int) ;#define WD(i) *((int *) (i + w)) ;#define CH(i) *(i + w) ;#define SWAP(i, j) do { \ ; w = es; if (al <= 0) do w -= SZI, \ ; t = WD(i), WD(i) = WD(j), WD(j) = t; while (w > 0); \ ; else do --w, \ ; t = CH(i), CH(i) = CH(j), CH(j) = t; \ ; while (w > 0);} while (0) ;#define ROTATE(i, j, k) do { \ ; w = es; if (al <= 0) do w -= SZI, \ ; t = WD(i), WD(i) = WD(j), WD(j) = WD(k), WD(k) = t; \ ; while (w > 0); \ ; else do --w, \ ; t = CH(i), CH(i) = CH(j), CH(j) = CH(k), CH(k) = t; \ ; while (w > 0);} while (0) ;#define STACK s[STKSZ], *p = s + STKSZ ;#define STKSZ sizeof (size_t) * 16 ;#define PUSH(x, y) p -= 2, *(p + 1) = x, *p = y ;#define EMPTY (p >= s + STKSZ) ;#define POP(y, x) y = *p, x = *(p + 1), p += 2 ; ;#define DGT 128 /* threshold of p-size for checking degeneration */ ;#define DGV 16 /* degeneration assumed if the smaller < DGL */ ;#define DGM 0 /* threshold for selecting no median */ ;#define DGS 1 /* threshold for samples distributed uniformly */ ;#define DGU 2 /* threshold for sampling at random */ ;#define DGL ((unsigned) psz / DGV) * es ;#define RDMSMPL(m, i, j) if (m != (n = i + es * ((rnm = random (rnm)) % \ ; ((unsigned) (j - (i)) / es + 1)))) SWAP (m, n) ; ;typedef int (*comp_t) (const void *, const void *); ;typedef char * ptrtyp; ; ;+ *** allocation of variables *** ;+ [ebp+32] cf ;+ [ebp+28] es ;+ [ebp+24] N, r ;+ [ebp+20] A, l ;+ [ebp+16..0] (return address to caller, etc) ;+ [ebp-04] m ;+ [ebp-08] k ;+ [ebp-12] n ;+ [ebp-16] psz ;+ [ebp-20] thr ;+ [ebp-24] cst ;+ [ebp-28] al ;+ [ebp-32] itv, rnm ;+ [ebp-36] dgn ;+ [ebp-40] s[STKSZ - 1] *** using SYS-STACK as if LOCAL-STACK *** ;+ ;+ esp p ;+ edx t, n, ... ;+ ecx nsp, dgn, ... ;+ eax c, w, ... ;+ edi es, m, k, ... ;+ esi j, ... ;+ ebx i, ... ;+ ; void qsort (void *A, size_t N, size_t es, comp_t cf) { ; ptrtyp l, r, m, i, j, k, n, STACK; ; int psz, thr, cst, c, al, t, w, nsp, itv, rnm, dgn = 0; ; ; if (cf == (comp_t) 0) radixspi (A, N, es); /* call RADIX SORT */ sna01: ; ** off-set machine-code ** cmp dword ptr [esp+16],0 ; cf :: 0 0000 83 7C 24 10 00 je _radixspi ;<- == 0005 0F 84 00000000e ; else ; if (N > 1 && es > 0) { /* do QUICK SORT */ push ebp ; 000B 55 push ebx ; 000C 53 push esi ; 000D 56 push edi ; 000E 57 mov ebp,esp ; 000F 8B EC add esp,-36 ; resv 36 = p <- s + STKSZ 0011 83 C4 DC mov esi,dword ptr [ebp+24] ; v <- N 0014 8B 75 18 dec esi ; --v :: 0 0017 4E jle short sna02 ;<- <= 0018 7E 07 mov edi,dword ptr [ebp+28] ; es 001A 8B 7D 1C test edi,edi ; es :: 0 001D 85 FF ja short sna03 ;<- > 001F 77 07 sna02: mov esp,ebp ; 0021 8B E5 pop edi ; 0023 5F pop esi ; 0024 5E pop ebx ; 0025 5B pop ebp ; 0026 5D ret ;<- (exit) 0027 C3 sna03: mov dword ptr [ebp-36],0 ; dgn <- 0 0028 C7 45 DC 00000000 ; al =((int) A | es) & (SZI - 1); mov ebx,dword ptr [ebp+20] ; i <- A 002F 8B 5D 14 mov ecx,ebx ; w <- A 0032 8B CB or ecx,edi ; w |= es 0034 0B CF and ecx,3 ; w &= SZI - 1 0036 83 E1 03 mov dword ptr [ebp-28],ecx ; al <- w 0039 89 4D E4 ; l = i = (char *) A, r = j = i + (N - 1) * es; imul esi,edi ; v *= es 003C 0F AF F7 add esi,ebx ; j <- i + v 003F 03 F3 mov dword ptr [ebp+24],esi ; r <- j 0041 89 75 18 jmp short sna12 ;<- 0044 EB 75 ; if (i - l < r - (j += es)) { /* select for next iteration */ sna04: add esi,edi ; j += es 0046 03 F7 mov edx,ebx ; w <- i 0048 8B D3 mov eax,dword ptr [ebp+20] ; l 004A 8B 45 14 sub edx,eax ; w -= l 004D 2B D0 add edx,esi ; w += j 004F 03 D6 mov ecx,dword ptr [ebp+24] ; r 0051 8B 4D 18 cmp edx,ecx ; w :: r 0054 3B D1 mov edx,dword ptr [ebp-16] ; v <- psz 0056 8B 55 F0 jae short sna05 ;<- >= 0059 73 16 ; if (psz >= DGT && l + DGL > j) dgn++; cmp edx,127 ; psz :: DGT - 1 005B 83 FA 7F jle short sna08 ;<- <= 005E 7E 34 shr edx,4 ; v /= DGV 0060 C1 EA 04 imul edx,edi ; v *= es 0063 0F AF D7 add edx,eax ; v + l 0066 03 D0 cmp esi,edx ; j :: v 0068 3B F2 jae short sna08 ;<- >= 006A 73 28 inc dword ptr [ebp-36] ; dgn++ 006C FF 45 DC jmp short sna08 ;<- 006F EB 23 ; else { ; if (psz >= DGT && i + DGL > r) dgn++; sna05: cmp edx,127 ; psz :: DGT - 1 0071 83 FA 7F jle short sna06 ;<- <= 0074 7E 0F shr edx,4 ; v /= DGV 0076 C1 EA 04 imul edx,edi ; v *= es 0079 0F AF D7 add edx,ebx ; v += i 007C 03 D3 cmp edx,ecx ; v :: r 007E 3B D1 jbe short sna06 ;<- <= 0080 76 03 inc dword ptr [ebp-36] ; dgn++ 0082 FF 45 DC ; if (j >= r) r = i; else PUSH (l, i), l = j;} sna06: cmp esi,ecx ; j :: r 0085 3B F1 jae short sna09 ;<- >= 0087 73 11 push eax ; *(--p) <- l 0089 50 push ebx ; *(--p) <- i 008A 53 sna07: mov dword ptr [ebp+20],esi ; l <- j 008B 89 75 14 mov ebx,esi ; i <- l 008E 8B DE mov esi,ecx ; j <- r 0090 8B F1 jmp short sna10 ;<- 0092 EB 0D ; if (l >= i) l = j; else PUSH (j, r), r = i;} sna08: cmp ebx,eax ; i :: l 0094 3B D8 jbe short sna07 ;<- <= 0096 76 F3 push esi ; *(--p) <- j 0098 56 push ecx ; *(--p) <- r 0099 51 sna09: mov dword ptr [ebp+24],ebx ; r <- i 009A 89 5D 18 mov esi,ebx ; j <- r 009D 8B F3 mov ebx,eax ; i <- l 009F 8B D8 ; if ((i = l) < (j = r)) continue;} sna10: cmp ebx,esi ; i :: j 00A1 3B DE jb short sna12 ;<- < 00A3 72 16 ; /* pop up next from stack */ ; if (!EMPTY) POP (j, i), r = j, l = i; else break;}}} sna11: lea eax,dword ptr [ebp-36] ; s + STKSZ 00A5 8D 45 DC cmp esp,eax ; p :: s + STKSZ 00A8 3B E0 jae sna02 ;<- >= 00AA 0F 83 FFFFFF71 pop esi ; j <- *(p++) 00B0 5E pop ebx ; i <- *(p++) 00B1 5B mov dword ptr [ebp+24],esi ; r <- j 00B2 89 75 18 mov dword ptr [ebp+20],ebx ; l <- i 00B5 89 5D 14 mov edi,dword ptr [ebp+28] ; es 00B8 8B 7D 1C ; for ( ; ; ) { /* initialize for current partition */ ; m = i + ((unsigned) (psz = (j - i) / es) / 2) * es, sna12: mov eax,esi ; w <- j 00BB 8B C6 sub eax,ebx ; w -= i 00BD 2B C3 xor edx,edx ; 0 00BF 33 D2 div edi ; w /= es 00C1 F7 F7 mov dword ptr [ebp-16],eax ; psz <- w 00C3 89 45 F0 shr eax,1 ; w /= 2 00C6 D1 E8 imul edi ; w *= es 00C8 F7 EF lea edi,dword ptr [ebx+eax] ; m <- i + w 00CA 8D 3C 03 mov dword ptr [ebp-04],edi ; m 00CD 89 7D FC ; thr = MDT, psz -= (MDA), cst = 1; mov dword ptr [ebp-20],16 ; thr <- MDT 00D0 C7 45 EC 00000010 sub dword ptr [ebp-16],2 ; psz -= MDA 00D7 83 6D F0 02 mov dword ptr [ebp-24],1 ; cst <- 1 00DB C7 45 E8 00000001 ; if (psz <= MDT || dgn <= DGM || dgn > DGS) { /* if not No-Median */ mov ecx,dword ptr [ebp-36] ; dgn 00E2 8B 4D DC test ecx,ecx ; dgn :: DGM 00E5 85 C9 jle sna27 ;<- <= 00E7 0F 8E 000000B7 cmp dword ptr [ebp-16],16 ; psz :: MDT 00ED 83 7D F0 10 jle sna27 ;<- <= 00F1 0F 8E 000000AD jmp sna60 ;<- 00F7 E9 00000294 ; n = i, k = j; do sna13: mov edi,esi ; k <- j 00FC 8B FE push esi ; j 00FE 56 mov esi,ebx ; n <- i 00FF 8B F3 ; if (COMP (k, n) < 0) n = k; while ((k += es) <= r); sna14: push esi ; n 0101 56 push edi ; k 0102 57 call dword ptr [ebp+32] ;<= (*cf)(k,n) -> c 0103 FF 55 20 add esp,8 ; 0106 83 C4 08 test eax,eax ; c :: 0 0109 85 C0 jge short sna15 ;<- >= 010B 7D 02 mov esi,edi ; n <- k 010D 8B F7 sna15: add edi,dword ptr [ebp+28] ; k += es 010F 03 7D 1C cmp edi,dword ptr [ebp+24] ; k :: r 0112 3B 7D 18 jbe short sna14 ;<- <= 0115 76 EA ; if (n == i) SWAP (m, i); else ROTATE (m, n, i); mov ecx,ebx ; k <- i 0117 8B CB jmp short sna19 ;<- 0119 EB 1D ; n = j, k = i; do sna16: push esi ; n <- j 011B 56 mov edi,ebx ; k <- i 011C 8B FB ; if (COMP (k, n) > 0) n = k; while ((k -= es) >= l); sna17: push esi ; n 011E 56 push edi ; k 011F 57 call dword ptr [ebp+32] ;<= (*cf)(k,n) -> c 0120 FF 55 20 add esp,8 ; 0123 83 C4 08 test eax,eax ; c :: 0 0126 85 C0 jle short sna18 ;<- <= 0128 7E 02 mov esi,edi ; n <- k 012A 8B F7 sna18: sub edi,dword ptr [ebp+28] ; k -= es 012C 2B 7D 1C cmp edi,dword ptr [ebp+20] ; k :: l 012F 3B 7D 14 jae short sna17 ;<- >= 0132 73 EA ; if (n == j) SWAP (m, j); else ROTATE (m, n, j);} pop ecx ; k <- j 0134 59 sub esp,4 ; 0135 83 EC 04 sna19: mov edi,dword ptr [ebp-04] ; m 0138 8B 7D FC mov eax,dword ptr [ebp+28] ; w <- es 013B 8B 45 1C cmp esi,ecx ; n :: k 013E 3B F1 jne short sna21 ;<- != 0140 75 1D cmp dword ptr [ebp-28],0 ; al :: 0 0142 83 7D E4 00 jg sna78 ;<- > 0146 0F 8F 00000393 sna20: sub eax,4 ; w -= SZI :: 0 014C 83 E8 04 mov edx,dword ptr [edi+eax] ; t <- *(m + w) 014F 8B 14 07 mov ecx,dword ptr [esi+eax] ; v <- *(n + w) 0152 8B 0C 06 mov dword ptr [edi+eax],ecx ; *(m + w) <- v 0155 89 0C 07 mov dword ptr [esi+eax],edx ; *(n + w) <- t 0158 89 14 06 jg short sna20 ;<- > 015B 7F EF jmp short sna24 ;<- 015D EB 23 sna21: push ebx ; i 015F 53 cmp dword ptr [ebp-28],0 ; al :: 0 0160 83 7D E4 00 jg sna79 ;<- > 0164 0F 8F 00000389 sna22: sub eax,4 ; w -= SZI :: 0 016A 83 E8 04 mov edx,dword ptr [edi+eax] ; t <- *(m + w) 016D 8B 14 07 mov ebx,dword ptr [esi+eax] ; v <- *(n + w) 0170 8B 1C 06 mov dword ptr [edi+eax],ebx ; *(m + w) <- v 0173 89 1C 07 mov ebx,dword ptr [ecx+eax] ; v <- *(k + w) 0176 8B 1C 01 mov dword ptr [esi+eax],ebx ; *(n + w) <- v 0179 89 1C 06 mov dword ptr [ecx+eax],edx ; *(k + w) <- t 017C 89 14 01 jg short sna22 ;<- > 017F 7F E9 sna23: pop ebx ; i 0181 5B sna24: pop esi ; j 0182 5E ; cst = 0;}} ; cst = 0;} sna25: mov dword ptr [ebp-24],0 ; cst <- 0 0183 C7 45 E8 00000000 ; i += es, j -= es; sna26: mov eax,dword ptr [ebp+28] ; es 018A 8B 45 1C add ebx,eax ; i += es 018D 03 D8 sub esi,eax ; j -= es 018F 2B F0 cmp esi,ebx ; j :: i 0191 3B F3 jbe sna11 ;<- <= 0193 0F 86 FFFFFF0C ; if (psz > thr) thr *= MDM; else break;}} mov ecx,dword ptr [ebp-20] ; thr 0199 8B 4D EC cmp dword ptr [ebp-16],ecx ; psz :: thr 019C 39 4D F0 jle short sna31 ;<- <= 019F 7E 5D add dword ptr [ebp-20],ecx ; thr *= MDM 01A1 01 4D EC ; for ( ; ; ) { /* bring median of samples to middle */ ; if (COMP (m, j) <= 0) { sna27: push esi ; j 01A4 56 push edi ; m 01A5 57 call dword ptr [ebp+32] ;<= (*cf)(m,j) -> c 01A6 FF 55 20 add esp,8 ; 01A9 83 C4 08 test eax,eax ; c :: 0 01AC 85 C0 jg short sna28 ;<- > 01AE 7F 1A ; if (i < m && COMP (i, m) > 0) { cmp ebx,edi ; i :: m 01B0 3B DF jae sna11 ;<- >= 01B2 0F 83 FFFFFEED push edi ; m 01B8 57 push ebx ; i 01B9 53 call dword ptr [ebp+32] ;<= (*cf)(i,m) -> c 01BA FF 55 20 add esp,8 ; 01BD 83 C4 08 test eax,eax ; c :: 0 01C0 85 C0 jg sna13 ;<- > 01C2 0F 8F FFFFFF34 jmp short sna26 ;<- 01C8 EB C0 ; else { ; if (i >= m || COMP (i, m) > 0) SWAP (i, j); else { sna28: cmp ebx,edi ; i :: m 01CA 3B DF jae short sna29 ;<- >= 01CC 73 10 push edi ; m 01CE 57 push ebx ; i 01CF 53 call dword ptr [ebp+32] ;<= (*cf)(i,m) -> c 01D0 FF 55 20 add esp,8 ; 01D3 83 C4 08 test eax,eax ; c :: 0 01D6 85 C0 jle sna16 ;<- <= 01D8 0F 8E FFFFFF3D sna29: mov eax,dword ptr [ebp+28] ; w <- es 01DE 8B 45 1C cmp dword ptr [ebp-28],0 ; al :: 0 01E1 83 7D E4 00 jg sna80 ;<- > 01E5 0F 8F 00000322 sna30: sub eax,4 ; w -= SZI :: 0 01EB 83 E8 04 mov edx,dword ptr [ebx+eax] ; t <- *(i + w) 01EE 8B 14 03 mov ecx,dword ptr [esi+eax] ; v <- *(j + w) 01F1 8B 0C 06 mov dword ptr [ebx+eax],ecx ; *(i + w) <- v 01F4 89 0C 03 mov dword ptr [esi+eax],edx ; *(j + w) <- t 01F7 89 14 06 jg short sna30 ;<- > 01FA 7F EF jmp short sna25 ;<- 01FC EB 85 ; if (cst != 0 && psz > MDT) { /* check sorted already */ sna31: cmp dword ptr [ebp-24],0 ; cst :: 0 01FE 83 7D E8 00 je short sna33 ;<- == 0202 74 2E cmp dword ptr [ebp-16],16 ; psz :: MDT 0204 83 7D F0 10 jle short sna33 ;<- <= 0208 7E 28 ; k = l, n = k + es; mov ecx,dword ptr [ebp+20] ; k <- l 020A 8B 4D 14 mov edi,ecx ; n <- k 020D 8B F9 ; while (k < r && COMP (k, n) <= 0) k = n, n += es; sna32: cmp ecx,dword ptr [ebp+24] ; k :: r 020F 3B 4D 18 jae sna11 ;<- >= 0212 0F 83 FFFFFE8D add edi,dword ptr [ebp+28] ; n += es 0218 03 7D 1C push edi ; n 021B 57 push ecx ; k 021C 51 call dword ptr [ebp+32] ;<= (*cf)(k,n) -> c 021D FF 55 20 add esp,8 ; 0220 83 C4 08 test eax,eax ; c :: 0 0223 85 C0 mov ecx,edi ; k <- n 0225 8B CF jle short sna32 ;<= <= 0227 7E E6 mov edi,dword ptr [ebp-04] ; m 0229 8B 7D FC ; if (k >= r) i = j; else if (k >= m) i = m;} cmp ecx,edi ; k :: m 022C 3B CF jbe short sna33 ;<- <= 022E 76 02 mov ebx,edi ; i <- m 0230 8B DF ; if (i < j) { /* do partitioning by middle as pivot */ ; for (k = l; ; ) { /* gathering equal keys to left end */ sna33: mov ecx,dword ptr [ebp+20] ; l 0232 8B 4D 14 mov dword ptr [ebp-08],ecx ; k <- l 0235 89 4D F8 mov eax,dword ptr [ebp+28] ; w <- es 0238 8B 45 1C jmp short sna40 ;<- 023B EB 49 ; j -= es;} sna34: sub esi,eax ; j -= es 023D 2B F0 ; while (i < j) { sna35: cmp esi,ebx ; j :: i 023F 3B F3 jbe sna48 ;<- <= 0241 0F 86 000000CD ; if (m != j) { /* scan skipping over pivot */ cmp esi,edi ; j :: m 0247 3B F7 je short sna34 ;<- == 0249 74 F2 ; if ((c = COMP (m, j)) >= 0) break;} push esi ; j 024B 56 push edi ; m 024C 57 call dword ptr [ebp+32] ;<= (*cf)(m,j) -> c 024D FF 55 20 add esp,8 ; 0250 83 C4 08 test eax,eax ; c :: 0 0253 85 C0 mov eax,dword ptr [ebp+28] ; w <- es 0255 8B 45 1C jl short sna34 ;<- < 0258 7C E3 je short sna44 ;<- == 025A 74 75 ; if (i >= j) break; ; if (c != 0) SWAP (i, j); else { sna36: cmp dword ptr [ebp-28],0 ; al :: 0 025C 83 7D E4 00 jg sna81 ;<- > 0260 0F 8F 000002BB sna37: sub eax,4 ; w -= SZI :: 0 0266 83 E8 04 mov edx,dword ptr [ebx+eax] ; t <- *(i + w) 0269 8B 14 03 mov ecx,dword ptr [esi+eax] ; v <- *(j + w) 026C 8B 0C 06 mov dword ptr [ebx+eax],ecx ; *(i + w) <- v 026F 89 0C 03 mov dword ptr [esi+eax],edx ; *(j + w) <- t 0272 89 14 06 jg short sna37 ;<- > 0275 7F EF ; j -= es, i += es;} sna38: mov eax,dword ptr [ebp+28] ; w <- es 0277 8B 45 1C sub esi,eax ; j -= es 027A 2B F0 ; i += es;} sna39: add ebx,eax ; i += es 027C 03 D8 ; while (i <= j) { cmp esi,ebx ; j :: i 027E 3B F3 jb sna50 ;<- < 0280 0F 82 0000009C ; if (i != m) { /* scan skipping over pivot */ sna40: cmp ebx,edi ; i :: m 0286 3B DF je short sna39 ;<- == 0288 74 F2 ; if ((c = COMP (i, m)) > 0) break; push edi ; m 028A 57 push ebx ; i 028B 53 call dword ptr [ebp+32] ;<= (*cf)(i,m) -> c 028C FF 55 20 add esp,8 ; 028F 83 C4 08 test eax,eax ; c :: 0 0292 85 C0 mov eax,dword ptr [ebp+28] ; w <- es 0294 8B 45 1C jl short sna39 ;<- < 0297 7C E3 jg short sna35 ;<- > 0299 7F A4 ; if (c == 0) { ; if (k == m) m = i; else if (k != i) SWAP (k, i); ; k += es;}} mov ecx,dword ptr [ebp-08] ; n <- k 029B 8B 4D F8 add dword ptr [ebp-08],eax ; k += es 029E 01 45 F8 cmp ecx,edi ; n :: m 02A1 3B CF jne short sna41 ;<- != 02A3 75 04 mov edi,ebx ; m <- i 02A5 8B FB jmp short sna39 ;<- 02A7 EB D3 sna41: cmp ebx,ecx ; i :: n 02A9 3B D9 je short sna39 ;<- == 02AB 74 CF push edi ; m 02AD 57 mov edi,ecx ; n 02AE 8B F9 cmp dword ptr [ebp-28],0 ; al :: 0 02B0 83 7D E4 00 jg sna82 ;<- > 02B4 0F 8F 0000027B sna42: sub eax,4 ; w -= SZI :: 0 02BA 83 E8 04 mov edx,dword ptr [edi+eax] ; t <- *(n + w) 02BD 8B 14 07 mov ecx,dword ptr [ebx+eax] ; v <- *(i + w) 02C0 8B 0C 03 mov dword ptr [edi+eax],ecx ; *(n + w) <- v 02C3 89 0C 07 mov dword ptr [ebx+eax],edx ; *(i + w) <- t 02C6 89 14 03 jg short sna42 ;<- > 02C9 7F EF sna43: pop edi ; m 02CB 5F mov eax,dword ptr [ebp+28] ; w <- es 02CC 8B 45 1C jmp short sna39 ;<- 02CF EB AB ; n = k, k += es; if (n == m) n = m = i; sna44: mov ecx,dword ptr [ebp-08] ; n <- k 02D1 8B 4D F8 add dword ptr [ebp-08],eax ; k += es 02D4 01 45 F8 cmp ecx,edi ; n :: m 02D7 3B CF jne short sna45 ;<- != 02D9 75 07 mov edi,ebx ; m <- i 02DB 8B FB jmp sna36 ;<- 02DD E9 FFFFFF7A ; if (n != i) ROTATE (n, j, i); else SWAP (i, j);} sna45: cmp ebx,ecx ; i :: n 02E2 3B D9 je sna36 ;<- == 02E4 0F 84 FFFFFF72 push edi ; m 02EA 57 mov edi,ecx ; n 02EB 8B F9 cmp dword ptr [ebp-28],0 ; al :: 0 02ED 83 7D E4 00 jg sna83 ;<- > 02F1 0F 8F 00000252 sna46: sub eax,4 ; w -= SZI :: 0 02F7 83 E8 04 mov edx,dword ptr [edi+eax] ; t <- *(n + w) 02FA 8B 14 07 mov ecx,dword ptr [esi+eax] ; v <- *(j + w) 02FD 8B 0C 06 mov dword ptr [edi+eax],ecx ; *(n + w) <- v 0300 89 0C 07 mov ecx,dword ptr [ebx+eax] ; v <- *(i + w) 0303 8B 0C 03 mov dword ptr [esi+eax],ecx ; *(j + w) <- v 0306 89 0C 06 mov dword ptr [ebx+eax],edx ; *(i + w) <- t 0309 89 14 03 jg short sna46 ;<- > 030C 7F E9 sna47: pop edi ; m 030E 5F jmp sna38 ;<- 030F E9 FFFFFF63 ; if (i == j) { /* find final position of pivot */ sna48: jne short sna50 ;<- != 0314 75 0C ; if (m < i) i -= es;} cmp ebx,edi ; i :: m 0316 3B DF jbe short sna49 ;<- <= 0318 76 04 sub ebx,eax ; i -= es 031A 2B D8 cmp ebx,edi ; i :: m 031C 3B DF sna49: je short sna54 ;<- == 031E 74 2D jmp short sna52 ;<- 0320 EB 10 ; else { ; if (m < j) i = j; else if (i >= m) i = m;} sna50: cmp esi,edi ; j :: m 0322 3B F7 jbe short sna51 ;<- <= 0324 73 04 mov ebx,esi ; i <- j 0326 8B DE jmp short sna52 ;<- 0328 EB 08 sna51: cmp ebx,edi ; i :: m 032A 3B DF jb short sna52 ;<- < 032C 72 04 mov ebx,edi ; i <- m 032E 8B DF jmp short sna54 ;<- 0330 EB 1B ; if ((j = i) != m) SWAP (j, m); sna52: cmp dword ptr [ebp-28],0 ; al :: 0 0332 83 7D E4 00 jg sna84 ;<- > 0336 0F 8F 00000227 sna53: sub eax,4 ; w -= SZI :: 0 033C 83 E8 04 mov edx,dword ptr [ebx+eax] ; t <- *(i + w) 033F 8B 14 03 mov ecx,dword ptr [edi+eax] ; v <- *(m + w) 0342 8B 0C 07 mov dword ptr [ebx+eax],ecx ; *(i + w) <- v 0345 89 0C 03 mov dword ptr [edi+eax],edx ; *(m + w) <- t 0348 89 14 07 jg short sna53 ;<- > 034B 7F EF sna54: mov esi,ebx ; j <- i 034D 8B F3 ; i -= es, n = l; /* move equal keys to where to be */ mov edi,dword ptr [ebp+28] ; es 034F 8B 7D 1C sub ebx,edi ; i -= es 0352 2B DF push esi ; j 0354 56 mov esi,dword ptr [ebp+20] ; n <- l 0355 8B 75 14 jmp short sna58 ;<- 0358 EB 21 ; SWAP (n, i); n += es, i -= es;} sna55: mov eax,edi ; w <- es 035A 8B C7 cmp dword ptr [ebp-28],0 ; al :: 0 035C 83 7D E4 00 jg sna85 ;<- > 0360 0F 8F 00000211 sna56: sub eax,4 ; w -= SZI :: 0 0366 83 E8 04 mov edx,dword ptr [esi+eax] ; t <- *(n + w) 0369 8B 14 06 mov ecx,dword ptr [ebx+eax] ; v <- *(i + w) 036C 8B 0C 03 mov dword ptr [esi+eax],ecx ; *(n + w) <- v 036F 89 0C 06 mov dword ptr [ebx+eax],edx ; *(i + w) <- t 0372 89 14 03 jg short sna56 ;<- > 0375 7F EF sna57: add esi,edi ; n += es 0377 03 F7 sub ebx,edi ; i -= es 0379 2B DF ; while (n < k && k <= i) { sna58: mov ecx,dword ptr [ebp-08] ; k 037B 8B 4D F8 cmp esi,ecx ; n :: k 037E 3B F1 jae short sna59 ;<- >= 0380 73 08 cmp ebx,ecx ; i :: k 0382 3B D9 jae short sna55 ;<- >= 0384 73 D4 ; if (k > i) i = n - es; mov ebx,esi ; i <- n 0386 8B DE sub ebx,edi ; i -= es 0388 2B DF sna59: pop esi ; j 038A 5E jmp sna04 ;<- 038B E9 FFFFFCB6 ; /* to prevent from degeneration */ ; if (psz > MDT && dgn > DGS) { /* if degeneration assumed */ sna60: cmp ecx,1 ; dgn :: DGS 0390 83 F9 01 jle sna31 ;<- <= 0393 0F 8E FFFFFE65 ; if (dgn <= DGU) { /* samples distributed uniform */ cmp ecx,2 ; dgn :: DGU 0399 83 F9 02 jg sna69 ;<- > 039C 0F 8F 00000093 ; nsp = 3; while (psz > thr) thr *= MDM, nsp += 2; mov ecx,3 ; nsp <- 3 03A2 B9 00000003 mov edx,dword ptr [ebp-20] ; thr 03A7 8B 55 EC jmp short sna62 ;<- 03AA EB 05 sna61: add edx,edx ; thr *= MDM 03AC 03 D2 add ecx,2 ; nsp += 2 03AE 83 C1 02 sna62: cmp dword ptr [ebp-16],edx ; psz :: thr 03B1 39 55 F0 jg short sna61 ;<- > 03B4 7F F6 ; itv = ((unsigned) psz / (nsp - 1)) * es; k = i, n = j; dec ecx ; nsp-- 03B6 49 mov eax,dword ptr [ebp-16] ; w <- psz 03B7 8B 45 F0 xor edx,edx ; 0 03BA 33 D2 div ecx ; w /= nsp 03BC F7 F1 imul dword ptr [ebp+28] ; w *= es 03BE F7 6D 1C mov dword ptr [ebp-32],eax ; itv <- w 03C1 89 45 E0 mov dword ptr [ebp-08],ebx ; k <- i 03C4 89 5D F8 mov dword ptr [ebp-12],esi ; n <- j 03C7 89 75 F4 ; for (thr = MDT; psz > thr; thr *= MDM) { mov eax,16 ; thr <- MDT 03CA B8 00000010 jmp short sna68 ;<- 03CF EB 5A ; i += es, k += itv; SWAP (i, k); sna63: mov dword ptr [ebp-20],eax ; thr 03D1 89 45 EC mov eax,dword ptr [ebp+28] ; w <- es 03D4 8B 45 1C mov edx,dword ptr [ebp-32] ; itv 03D7 8B 55 E0 add dword ptr [ebp-08],edx ; k += itv 03DA 01 55 F8 add ebx,eax ; i += es 03DD 03 D8 mov edi,dword ptr [ebp-08] ; k 03DF 8B 7D F8 cmp dword ptr [ebp-28],0 ; al :: 0 03E2 83 7D E4 00 jg sna86 ;<- > 03E6 0F 8F 0000019F sna64: sub eax,4 ; w -= SZI :: 0 03EC 83 E8 04 mov edx,dword ptr [ebx+eax] ; t <- *(i + w) 03EF 8B 14 03 mov ecx,dword ptr [edi+eax] ; v <- *(k + w) 03F2 8B 0C 07 mov dword ptr [ebx+eax],ecx ; *(i + w) <- v 03F5 89 0C 03 mov dword ptr [edi+eax],edx ; *(k + w) <- t 03F8 89 14 07 jg short sna64 ;<- > 03FB 7F EF ; j -= es, n -= itv; SWAP (n, j);}} sna65: mov eax,dword ptr [ebp+28] ; w <- es 03FD 8B 45 1C mov edx,dword ptr [ebp-32] ; itv 0400 8B 55 E0 sub dword ptr [ebp-12],edx ; n -= itv 0403 29 55 F4 sub esi,eax ; j -= es 0406 2B F0 mov edi,dword ptr [ebp-12] ; n 0408 8B 7D F4 cmp dword ptr [ebp-28],0 ; al :: 0 040B 83 7D E4 00 jg sna87 ;<- > 040F 0F 8F 0000018A sna66: sub eax,4 ; w -= SZI :: 0 0415 83 E8 04 mov edx,dword ptr [edi+eax] ; t <- *(n + w) 0418 8B 14 07 mov ecx,dword ptr [esi+eax] ; v <- *(j + w) 041B 8B 0C 06 mov dword ptr [edi+eax],ecx ; *(n + w) <- v 041E 89 0C 07 mov dword ptr [esi+eax],edx ; *(j + w) <- t 0421 89 14 06 jg short sna66 ;<- > 0424 7F EF sna67: mov eax,dword ptr [ebp-20] ; thr 0426 8B 45 EC add eax,eax ; thr *= MDM 0429 03 C0 sna68: cmp dword ptr [ebp-16],eax ; psz :: thr 042B 39 45 F0 jg short sna63 ;<- > 042E 7F A1 mov edi,dword ptr [ebp-04] ; m 0430 8B 7D FC jmp short sna73 ;<- 0433 EB 51 ; else { /* samples at random */ ; if (dgn == DGU + 1) dgn++, srandom (time (0)); sna69: cmp ecx,3 ; dgn :: DGU + 1 0435 83 F9 03 jne short sna70 ;<- != 0438 75 15 inc dword ptr [ebp-36] ; dgn++ 043A FF 45 DC push 0 ; 0 043D 6A 00 call _time ;<= time(0) -> v 043F E8 00000000e pop ecx ; 0444 59 push eax ; v 0445 50 call _srandom ;<= srandom(v) -> w 0446 E8 00000000e pop ecx ; 044B 59 mov dword ptr [ebp-32],eax ; rnm <- w 044C 89 45 E0 ; for ((unsigned) thr /= MDM; psz > thr; thr *= MDM) { sna70: mov eax,dword ptr [ebp-20] ; thr 044F 8B 45 EC sar eax,1 ; thr /= MDM 0452 D1 F8 mov edi,dword ptr [ebp+28] ; es 0454 8B 7D 1C jmp short sna72 ;<- <= 0457 EB 20 ; RDMSMPL (i, i, j); i += es; sna71: mov dword ptr [ebp-20],eax ; thr 0459 89 45 EC mov eax,ebx ; k <- i 045C 8B C3 call sna74 ;<= sna74(i) 045E E8 00000035 mov edi,dword ptr [ebp+28] ; es 0463 8B 7D 1C add ebx,edi ; i += es 0466 03 DF ; RDMSMPL (j, i, j); j -= es;} mov eax,esi ; k <- j 0468 8B C6 call sna74 ;<= sna74(j) 046A E8 00000029 mov edi,dword ptr [ebp+28] ; es 046F 8B 7D 1C sub esi,edi ; j -= es 0472 2B F7 mov eax,dword ptr [ebp-20] ; thr 0474 8B 45 EC add eax,eax ; thr *= MDM 0477 03 C0 sna72: cmp dword ptr [ebp-16],eax ; psz :: thr 0479 39 45 F0 jg short sna71 ;<- > 047C 7F DB ; RDMSMPL (m, i, j);} mov eax,dword ptr [ebp-04] ; k <- m 047E 8B 45 FC call sna74 ;<= sna74(m) 0481 E8 00000012 ; i = l, j = r, thr = MDT;} sna73: mov ebx,dword ptr [ebp+20] ; i <- l 0486 8B 5D 14 mov esi,dword ptr [ebp+24] ; j <- r 0489 8B 75 18 mov dword ptr [ebp-20],16 ; thr <- MDT 048C C7 45 EC 00000010 jmp sna27 ;<- 0493 E9 FFFFFD0C sna74: push eax ; k 0498 50 mov eax,esi ; v <- j 0499 8B C6 sub eax,ebx ; v -= i 049B 2B C3 xor edx,edx ; 0 049D 33 D2 div edi ; v /= es 049F F7 F7 inc eax ; v++ 04A1 40 push eax ; v 04A2 50 mov edx,dword ptr [ebp-32] ; rnm 04A3 8B 55 E0 push edx ; rnm 04A6 52 call _random ;<= random(rnm) -> w 04A7 E8 00000000e pop edx ; 04AC 5A mov dword ptr [ebp-32],eax ; rnm <- w 04AD 89 45 E0 pop ecx ; v 04B0 59 xor edx,edx ; n <- 0 04B1 33 D2 div ecx ; n <- w % v 04B3 F7 F1 imul edx,edi ; n *= es 04B5 0F AF D7 add edx,ebx ; n += i 04B8 03 D3 mov eax,edi ; w <- es 04BA 8B C7 pop edi ; k 04BC 5F cmp edx,edi ; n :: k 04BD 3B D7 je short sna77 ;<- == 04BF 74 1D push ebx ; i 04C1 53 cmp dword ptr [ebp-28],0 ; al :: 0 04C2 83 7D E4 00 jg sna88 ;<- > 04C6 0F 8F 000000E7 sna75: sub eax,4 ; w -= SZI :: 0 04CC 83 E8 04 mov ebx,dword ptr [edi+eax] ; t <- *(k + w) 04CF 8B 1C 07 mov ecx,dword ptr [edx+eax] ; v <- *(n + w) 04D2 8B 0C 02 mov dword ptr [edi+eax],ecx ; *(k + w) <- v 04D5 89 0C 07 mov dword ptr [edx+eax],ebx ; *(n + w) <- t 04D8 89 1C 02 jg short sna75 ;<- > 04DB 7F EF sna76: pop ebx ; i 04DD 5B sna77: ret ;<- (go back) 04DE C3 ; sna78: dec eax ; --w :: 0 04DF 48 mov dl,byte ptr [edi+eax] ; u <- *(m + w) 04E0 8A 14 07 mov cl,byte ptr [esi+eax] ; z <- *(n + w) 04E3 8A 0C 06 mov byte ptr [edi+eax],cl ; *(m + w) <- z 04E6 88 0C 07 mov byte ptr [esi+eax],dl ; *(n + w) <- u 04E9 88 14 06 jg short sna78 ;<- > 04EC 7F F1 jmp sna24 ;<- 04EE E9 FFFFFC8F sna79: dec eax ; --w :: 0 04F3 48 mov dl,byte ptr [edi+eax] ; u <- *(m + w) 04F4 8A 14 07 mov bl,byte ptr [esi+eax] ; z <- *(n + w) 04F7 8A 1C 06 mov byte ptr [edi+eax],bl ; *(m + w) <- z 04FA 88 1C 07 mov bl,byte ptr [ecx+eax] ; z <- *(k + w) 04FD 8A 1C 01 mov byte ptr [esi+eax],bl ; *(n + w) <- z 0500 88 1C 06 mov byte ptr [ecx+eax],dl ; *(k + w) <- u 0503 88 14 01 jg short sna79 ;<- > 0506 7F EB jmp sna23 ;<- 0508 E9 FFFFFC74 sna80: dec eax ; --w :: 0 050D 48 mov dl,byte ptr [ebx+eax] ; u <- *(i + w) 050E 8A 14 03 mov cl,byte ptr [esi+eax] ; z <- *(j + w) 0511 8A 0C 06 mov byte ptr [ebx+eax],cl ; *(i + w) <- z 0514 88 0C 03 mov byte ptr [esi+eax],dl ; *(j + w) <- u 0517 88 14 06 jg short sna80 ;<- > 051A 7F F1 jmp sna25 ;<- 051C E9 FFFFFC62 sna81: dec eax ; --w :: 0 0521 48 mov dl,byte ptr [ebx+eax] ; u <- *(i + w) 0522 8A 14 03 mov cl,byte ptr [esi+eax] ; z <- *(j + w) 0525 8A 0C 06 mov byte ptr [ebx+eax],cl ; *(i + w) <- z 0528 88 0C 03 mov byte ptr [esi+eax],dl ; *(j + w) <- u 052B 88 14 06 jg short sna81 ;<- > 052E 7F F1 jmp sna38 ;<- 0530 E9 FFFFFD42 sna82: dec eax ; --w :: 0 0535 48 mov dl,byte ptr [edi+eax] ; u <- *(k + w) 0536 8A 14 07 mov cl,byte ptr [ebx+eax] ; z <- *(i + w) 0539 8A 0C 03 mov byte ptr [edi+eax],cl ; *(k + w) <- z 053C 88 0C 07 mov byte ptr [ebx+eax],dl ; *(i + w) <- u 053F 88 14 03 jg short sna82 ;<- > 0542 7F F1 jmp sna43 ;<- 0544 E9 FFFFFD82 sna83: dec eax ; --w :: 0 0549 48 mov dl,byte ptr [edi+eax] ; u <- *(n + w) 054A 8A 14 07 mov cl,byte ptr [esi+eax] ; z <- *(j + w) 054D 8A 0C 06 mov byte ptr [edi+eax],cl ; *(n + w) <- z 0550 88 0C 07 mov cl,byte ptr [ebx+eax] ; z <- *(i + w) 0553 8A 0C 03 mov byte ptr [esi+eax],cl ; *(j + w) <- z 0556 88 0C 06 mov byte ptr [ebx+eax],dl ; *(i + w) <- u 0559 88 14 03 jg short sna83 ;<- > 055C 7F EB jmp sna47 ;<- 055E E9 FFFFFDAB sna84: dec eax ; --w :: 0 0563 48 mov dl,byte ptr [esi+eax] ; u <- *(J + w) 0564 8A 14 06 mov cl,byte ptr [edi+eax] ; z <- *(m + w) 0567 8A 0C 07 mov byte ptr [esi+eax],cl ; *(J + w) <- z 056A 88 0C 06 mov byte ptr [edi+eax],dl ; *(m + w) <- u 056D 88 14 07 jg short sna84 ;<- > 0570 7F F1 jmp sna54 ;<- 0572 E9 FFFFFDD6 sna85: dec eax ; --w :: 0 0577 48 mov dl,byte ptr [esi+eax] ; u <- *(n + w) 0578 8A 14 06 mov cl,byte ptr [ebx+eax] ; z <- *(i + w) 057B 8A 0C 03 mov byte ptr [esi+eax],cl ; *(n + w) <- z 057E 88 0C 06 mov byte ptr [ebx+eax],dl ; *(i + w) <- u 0581 88 14 03 jg short sna85 ;<- > 0584 7F F1 jmp sna57 ;<- 0586 E9 FFFFFDEC sna86: dec eax ; --w :: 0 058B 48 mov dl,byte ptr [ebx+eax] ; u <- *(i + w) 058C 8A 14 03 mov cl,byte ptr [edi+eax] ; z <- *(k + w) 058F 8A 0C 07 mov byte ptr [ebx+eax],cl ; *(i + w) <- z 0592 88 0C 03 mov byte ptr [edi+eax],dl ; *(k + w) <- u 0595 88 14 07 jg short sna86 ;<- > 0598 7F F1 jmp sna65 ;<- 059A E9 FFFFFE5E sna87: dec eax ; --w :: 0 059F 48 mov dl,byte ptr [edi+eax] ; u <- *(n + w) 05A0 8A 14 07 mov cl,byte ptr [esi+eax] ; z <- *(j + w) 05A3 8A 0C 06 mov byte ptr [edi+eax],cl ; *(n + w) <- z 05A6 88 0C 07 mov byte ptr [esi+eax],dl ; *(j + w) <- u 05A9 88 14 06 jg short sna87 ;<- > 05AC 7F F1 jmp sna67 ;<- 05AE E9 FFFFFE73 sna88: dec eax ; --w :: 0 05B3 48 mov bl,byte ptr [edi+eax] ; u <- *(k + w) 05B4 8A 1C 07 mov cl,byte ptr [edx+eax] ; z <- *(n + w) 05B7 8A 0C 02 mov byte ptr [edi+eax],cl ; *(k + w) <- z 05BA 88 0C 07 mov byte ptr [edx+eax],bl ; *(n + w) <- u 05BD 88 1C 02 jg short sna88 ;<- > 05C0 7F F1 jmp sna76 ;<- 05C2 E9 FFFFFF16 _qsort endp _TEXT ends public _qsort extrn _radixspi:near extrn _time:near extrn _srandom:near extrn _random:near end ;/* a-wada/qsortlib/ccg/qsortsn.asm end */