1 /* Copyright (C) 2011 by Valentin Ochs
2 *
3 * Permission is hereby granted, free of charge, to any person obtaining a copy
4 * of this software and associated documentation files (the "Software"), to
5 * deal in the Software without restriction, including without limitation the
6 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
7 * sell copies of the Software, and to permit persons to whom the Software is
8 * furnished to do so, subject to the following conditions:
9 *
10 * The above copyright notice and this permission notice shall be included in
11 * all copies or substantial portions of the Software.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
18 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
19 * IN THE SOFTWARE.
20 */
21
22 /* Minor changes by Rich Felker for integration in musl, 2011-04-27. */
23
24 #include <stdint.h>
25 #include <stdlib.h>
26 #include <string.h>
27
28 #define ntz(x) __builtin_ctzl(x)
29
30 typedef int (*cmpfun)(const void*, const void*);
31
pntz(size_t p[2])32 static inline int pntz(size_t p[2]) {
33 int r = ntz(p[0] - 1);
34 if (r != 0 || (r = 8 * sizeof(size_t) + ntz(p[1])) != 8 * sizeof(size_t)) {
35 return r;
36 }
37 return 0;
38 }
39
cycle(size_t width,unsigned char * ar[],int n)40 static void cycle(size_t width, unsigned char* ar[], int n) {
41 unsigned char tmp[256];
42 size_t l;
43 int i;
44
45 if (n < 2) {
46 return;
47 }
48
49 ar[n] = tmp;
50 while (width) {
51 l = sizeof(tmp) < width ? sizeof(tmp) : width;
52 memcpy(ar[n], ar[0], l);
53 for (i = 0; i < n; i++) {
54 memcpy(ar[i], ar[i + 1], l);
55 ar[i] += l;
56 }
57 width -= l;
58 }
59 }
60
61 /* shl() and shr() need n > 0 */
shl(size_t p[2],int n)62 static inline void shl(size_t p[2], int n) {
63 if (n >= 8 * sizeof(size_t)) {
64 n -= 8 * sizeof(size_t);
65 p[1] = p[0];
66 p[0] = 0;
67 }
68 p[1] <<= n;
69 p[1] |= p[0] >> (sizeof(size_t) * 8 - n);
70 p[0] <<= n;
71 }
72
shr(size_t p[2],int n)73 static inline void shr(size_t p[2], int n) {
74 if (n >= 8 * sizeof(size_t)) {
75 n -= 8 * sizeof(size_t);
76 p[0] = p[1];
77 p[1] = 0;
78 }
79 p[0] >>= n;
80 p[0] |= p[1] << (sizeof(size_t) * 8 - n);
81 p[1] >>= n;
82 }
83
sift(unsigned char * head,size_t width,cmpfun cmp,int pshift,size_t lp[])84 static void sift(unsigned char* head, size_t width, cmpfun cmp, int pshift, size_t lp[]) {
85 unsigned char *rt, *lf;
86 unsigned char* ar[14 * sizeof(size_t) + 1];
87 int i = 1;
88
89 ar[0] = head;
90 while (pshift > 1) {
91 rt = head - width;
92 lf = head - width - lp[pshift - 2];
93
94 if ((*cmp)(ar[0], lf) >= 0 && (*cmp)(ar[0], rt) >= 0) {
95 break;
96 }
97 if ((*cmp)(lf, rt) >= 0) {
98 ar[i++] = lf;
99 head = lf;
100 pshift -= 1;
101 } else {
102 ar[i++] = rt;
103 head = rt;
104 pshift -= 2;
105 }
106 }
107 cycle(width, ar, i);
108 }
109
trinkle(unsigned char * head,size_t width,cmpfun cmp,size_t pp[2],int pshift,int trusty,size_t lp[])110 static void trinkle(unsigned char* head, size_t width, cmpfun cmp, size_t pp[2], int pshift, int trusty, size_t lp[]) {
111 unsigned char *stepson,
112 *rt, *lf;
113 size_t p[2];
114 unsigned char* ar[14 * sizeof(size_t) + 1];
115 int i = 1;
116 int trail;
117
118 p[0] = pp[0];
119 p[1] = pp[1];
120
121 ar[0] = head;
122 while (p[0] != 1 || p[1] != 0) {
123 stepson = head - lp[pshift];
124 if ((*cmp)(stepson, ar[0]) <= 0) {
125 break;
126 }
127 if (!trusty && pshift > 1) {
128 rt = head - width;
129 lf = head - width - lp[pshift - 2];
130 if ((*cmp)(rt, stepson) >= 0 || (*cmp)(lf, stepson) >= 0) {
131 break;
132 }
133 }
134
135 ar[i++] = stepson;
136 head = stepson;
137 trail = pntz(p);
138 shr(p, trail);
139 pshift += trail;
140 trusty = 0;
141 }
142 if (!trusty) {
143 cycle(width, ar, i);
144 sift(head, width, cmp, pshift, lp);
145 }
146 }
147
qsort(void * base,size_t nel,size_t width,cmpfun cmp)148 void qsort(void* base, size_t nel, size_t width, cmpfun cmp) {
149 size_t lp[12 * sizeof(size_t)];
150 size_t i, size = width * nel;
151 unsigned char *head, *high;
152 size_t p[2] = {1, 0};
153 int pshift = 1;
154 int trail;
155
156 if (!size)
157 return;
158
159 head = base;
160 high = head + size - width;
161
162 /* Precompute Leonardo numbers, scaled by element width */
163 for (lp[0] = lp[1] = width, i = 2; (lp[i] = lp[i - 2] + lp[i - 1] + width) < size; i++)
164 ;
165
166 while (head < high) {
167 if ((p[0] & 3) == 3) {
168 sift(head, width, cmp, pshift, lp);
169 shr(p, 2);
170 pshift += 2;
171 } else {
172 if (lp[pshift - 1] >= high - head) {
173 trinkle(head, width, cmp, p, pshift, 0, lp);
174 } else {
175 sift(head, width, cmp, pshift, lp);
176 }
177
178 if (pshift == 1) {
179 shl(p, 1);
180 pshift = 0;
181 } else {
182 shl(p, pshift - 1);
183 pshift = 1;
184 }
185 }
186
187 p[0] |= 1;
188 head += width;
189 }
190
191 trinkle(head, width, cmp, p, pshift, 0, lp);
192
193 while (pshift != 1 || p[0] != 1 || p[1] != 0) {
194 if (pshift <= 1) {
195 trail = pntz(p);
196 shr(p, trail);
197 pshift += trail;
198 } else {
199 shl(p, 2);
200 pshift -= 2;
201 p[0] ^= 7;
202 shr(p, 1);
203 trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp);
204 shl(p, 1);
205 p[0] |= 1;
206 trinkle(head - width, width, cmp, p, pshift, 1, lp);
207 }
208 head -= width;
209 }
210 }
211