Chameleon

Chameleon Commit Details

Date:2011-08-06 18:57:15 (8 years 17 days ago)
Author:Evan Lojewski
Commit:1293
Parents: 1292
Message:Remove unneeded files. Update makefiles.
Changes:
D/branches/xZenu/src/arch/i386/libsa/zalloc.c
D/branches/xZenu/src/arch/i386/libsa/strtol.c
D/branches/xZenu/src/arch/i386/libsa/qsort.c
M/branches/xZenu/src/arch/i386/libsa/Makefile
M/branches/xZenu/src/arch/i386/libsa/string.c
M/branches/xZenu/src/modules/klibc/Makefile

File differences

branches/xZenu/src/modules/klibc/Makefile
1515
1616
1717
18
18
1919
2020
2121
2222
2323
24
24
2525
2626
2727
__umoddi3 __umodsi3 \
strntoumax strntoimax atoi atol atoll \
strcasecmp strncasecmp strlcat strndup strnlen \
strsep strtoimax strtok_r strtok strtol strtoll \
strsep strtoimax strtok_r strtok strtoll \
strtotimespec strtotimeval \
strtoul strtoull strtoumax strxspn strpbrk \
bsearch calloc \
jrand48 lrand48 mrand48 srand48 nrand48 seed48 \
memccpy memcpy memset bzero memchr memmem memmove memrchr memswap memcmp \
strcmp strncmp strcpy strncpy strlcpy strstr strncat strcat strdup strncasecmp strchr strlen \
strcmp strncmp strcpy strncpy strlcpy strstr strncat strcat strdup strncasecmp strchr strlen strtoul strtol \
qsort sha1hash onexit atexit exit \
snprintf vsnprintf sscanf vsscanf\
fwrite fprintf vfprintf printf
branches/xZenu/src/arch/i386/libsa/zalloc.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
/*
* Copyright (c) 1999-2003 Apple Computer, Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* Portions Copyright (c) 1999-2003 Apple Computer, Inc. All Rights
* Reserved. This file contains Original Code and/or Modifications of
* Original Code as defined in and that are subject to the Apple Public
* Source License Version 2.0 (the "License"). You may not use this file
* except in compliance with the License. Please obtain a copy of the
* License at http://www.apple.com/publicsource and read it before using
* this file.
*
* The Original Code and all software distributed under the License are
* distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT. Please see the
* License for the specific language governing rights and limitations
* under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/
/*
* Copyright 1993 NeXT Computer, Inc.
* All rights reserved.
*
* Sam's simple memory allocator.
*
*/
#include "libsa.h"
//#include "saio_internal.h" - Azi: needed for ZDEBUG (printf)
#include "memory.h"
#define ZDEBUG 0 //Azi: booter doesn't load with this enabled; instant reboot at "boot1: ..."
#if ZDEBUG
int zout;
#endif
typedef struct {
char * start;
size_t size;
} zmem;
static zmem * zalloced;
static zmem * zavailable;
static short availableNodes, allocedNodes, totalNodes;
static char * zalloc_base;
static char * zalloc_end;
static void (*zerror)(char *, size_t, const char *, int);
static void zallocate(char * start,int size);
static void zinsert(zmem * zp, int ndx);
static void zdelete(zmem * zp, int ndx);
static void zcoalesce(void);
#if ZDEBUG
size_t zalloced_size;
#endif
#define ZALLOC_NODES16384
static void malloc_error(char *addr, size_t size, const char *file, int line)
{
#ifdef i386
asm volatile ("hlt");
#endif
}
// define the block of memory that the allocator will use
void malloc_init(char * start, int size, int nodes, void (*malloc_err_fn)(char *, size_t, const char *, int))
{
zalloc_base = start ? start : (char *)ZALLOC_ADDR;
totalNodes = nodes ? nodes : ZALLOC_NODES;
zalloced = (zmem *) zalloc_base;
zavailable = (zmem *) zalloc_base + sizeof(zmem) * totalNodes;
zavailable[0].start = (char *)zavailable + sizeof(zmem) * totalNodes;
if (size == 0) size = ZALLOC_LEN;
zavailable[0].size = size - (zavailable[0].start - zalloc_base);
zalloc_end = zalloc_base + size;
availableNodes = 1;
allocedNodes = 0;
zerror = malloc_err_fn ? malloc_err_fn : malloc_error;
}
#define BEST_FIT 1
#undef malloc
void *malloc(size_t size)
{
return safe_malloc(size, __FILE__, __LINE__);
}
void * safe_malloc(size_t size, const char *file, int line)
{
int i;
#if BEST_FIT
int bestFit;
size_t smallestSize;
#endif
char * ret = 0;
if ( !zalloc_base )
{
// this used to follow the bss but some bios' corrupted it...
malloc_init((char *)ZALLOC_ADDR, ZALLOC_LEN, ZALLOC_NODES, malloc_error);
}
size = ((size + 0xf) & ~0xf);
if (size == 0) {
if (zerror) (*zerror)((char *)0xdeadbeef, 0, file, line);
}
#if BEST_FIT
smallestSize = 0;
bestFit = -1;
#endif
for (i = 0; i < availableNodes; i++)
{
// find node with equal size, or if not found,
// then smallest node that fits.
if ( zavailable[i].size == size )
{
zallocate(ret = zavailable[i].start, size);
zdelete(zavailable, i); availableNodes--;
goto done;
}
#if BEST_FIT
else
{
if ((zavailable[i].size > size) &&
((smallestSize == 0) ||
(zavailable[i].size < smallestSize)))
{
bestFit = i;
smallestSize = zavailable[i].size;
}
}
#else
else if ( zavailable[i].size > size )
{
zallocate(ret = zavailable[i].start, size);
zavailable[i].start += size;
zavailable[i].size -= size;
goto done;
}
#endif
}
#if BEST_FIT
if (bestFit != -1)
{
zallocate(ret = zavailable[bestFit].start, size);
zavailable[bestFit].start += size;
zavailable[bestFit].size -= size;
}
#endif
done:
if ((ret == 0) || (ret + size >= zalloc_end))
{
if (zerror) (*zerror)(ret, size, file, line);
}
if (ret != 0)
{
bzero(ret, size);
}
#if ZDEBUG
zalloced_size += size;
#endif
return (void *) ret;
}
void free(void * pointer)
{
unsigned long rp;
int i, found = 0;
size_t tsize = 0;
char * start = pointer;
#if i386
// Get return address of our caller,
// in case we have to report an error below.
asm volatile ("movl %%esp, %%eax\n\t"
"subl $4, %%eax\n\t"
"movl 0(%%eax), %%eax" : "=a" (rp) );
#else
rp = 0;
#endif
if ( !start ) return;
for (i = 0; i < allocedNodes; i++)
{
if ( zalloced[i].start == start )
{
tsize = zalloced[i].size;
#if ZDEBUG
zout -= tsize;
printf(" zz out %d\n",zout);
#endif
zdelete(zalloced, i); allocedNodes--;
found = 1;
#if ZDEBUG
memset(pointer, 0x5A, tsize);
#endif
break;
}
}
if ( !found ) {
if (zerror) (*zerror)(pointer, rp, "free", 0);
else return;
}
#if ZDEBUG
zalloced_size -= tsize;
#endif
for (i = 0; i < availableNodes; i++)
{
if ((start + tsize) == zavailable[i].start) // merge it in
{
zavailable[i].start = start;
zavailable[i].size += tsize;
zcoalesce();
return;
}
if ((i > 0) &&
(zavailable[i-1].start + zavailable[i-1].size == start))
{
zavailable[i-1].size += tsize;
zcoalesce();
return;
}
if ((start + tsize) < zavailable[i].start)
{
if (++availableNodes > totalNodes) {
if (zerror) (*zerror)((char *)0xf000f000, 0, "free", 0);
}
zinsert(zavailable, i);
zavailable[i].start = start;
zavailable[i].size = tsize;
return;
}
}
if (++availableNodes > totalNodes) {
if (zerror) (*zerror)((char *)0xf000f000, 1, "free", 0);
}
zavailable[i].start = start;
zavailable[i].size = tsize;
zcoalesce();
return;
}
static void
zallocate(char * start,int size)
{
#if ZDEBUG
zout += size;
printf(" alloc %d, total 0x%x\n",size,zout);
#endif
zalloced[allocedNodes].start = start;
zalloced[allocedNodes].size = size;
if (++allocedNodes > totalNodes) {
if (zerror) (*zerror)((char *)0xf000f000, 2, "zallocate", 0);
};
}
static void
zinsert(zmem * zp, int ndx)
{
int i;
zmem *z1, *z2;
i = totalNodes-2;
z1 = zp + i;
z2 = z1 + 1;
for (; i >= ndx; i--, z1--, z2--)
{
*z2 = *z1;
}
}
static void
zdelete(zmem * zp, int ndx)
{
int i;
zmem *z1, *z2;
z1 = zp + ndx;
z2 = z1 + 1;
for (i = ndx; i < totalNodes-1; i++, z1++, z2++)
{
*z1 = *z2;
}
}
static void
zcoalesce(void)
{
int i;
for (i = 0; i < availableNodes-1; i++)
{
if ( zavailable[i].start + zavailable[i].size ==
zavailable[i+1].start )
{
zavailable[i].size += zavailable[i+1].size;
zdelete(zavailable, i+1); availableNodes--;
return;
}
}
}
/* This is the simplest way possible. Should fix this. */
void * realloc(void * start, size_t newsize)
{
void * newstart = safe_malloc(newsize, __FILE__, __LINE__);
bcopy(start, newstart, newsize);
free(start);
return newstart;
}
branches/xZenu/src/arch/i386/libsa/strtol.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
/*
* Copyright (c) 1999-2003 Apple Computer, Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* Portions Copyright (c) 1999-2003 Apple Computer, Inc. All Rights
* Reserved. This file contains Original Code and/or Modifications of
* Original Code as defined in and that are subject to the Apple Public
* Source License Version 2.0 (the "License"). You may not use this file
* except in compliance with the License. Please obtain a copy of the
* License at http://www.apple.com/publicsource and read it before using
* this file.
*
* The Original Code and all software distributed under the License are
* distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT. Please see the
* License for the specific language governing rights and limitations
* under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/
/*-
* Copyright (c) 1990, 1993
*The Regents of the University of California. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
*This product includes software developed by the University of
*California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
/* Copyright (c) 1995 NeXT Computer, Inc. All rights reserved.
*
* HISTORY
* Modified by Curtis Galloway at NeXT June 1993,
* for use in the standalone library.
*
* 30-Nov-1995 Dean Reece at NeXT
* Created based on BSD4.4's strtol.c & strtoul.c.
* Removed dependency on _ctype_ by static versions of isupper()...
* Added support for "0b101..." binary constants.
* Commented out references to errno.
*/
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid[] = "@(#)strtol.c5.4 (Berkeley) 2/23/91";
#endif /* LIBC_SCCS and not lint */
#include "libsa.h"
#include <limits.h>
/*
* Convert a string to a long integer.
*
* Ignores `locale' stuff. Assumes that the upper and lower case
* alphabets and digits are each contiguous.
*/
long
strtol(nptr, endptr, base)
const char *nptr;
char **endptr;
register int base;
{
register const char *s = nptr;
register unsigned long acc;
register int c;
register unsigned long cutoff;
register int neg = 0, any, cutlim;
/*
* Skip white space and pick up leading +/- sign if any.
* If base is 0, allow 0x for hex and 0 for octal, else
* assume decimal; if base is already 16, allow 0x.
*/
do {
c = *s++;
} while (isspace(c));
if (c == '-') {
neg = 1;
c = *s++;
} else if (c == '+')
c = *s++;
if ((base == 0 || base == 16) &&
c == '0' && (*s == 'x' || *s == 'X')) {
c = s[1];
s += 2;
base = 16;
} else if ((base == 0 || base == 2) &&
c == '0' && (*s == 'b' || *s == 'B')) {
c = s[1];
s += 2;
base = 2;
}
if (base == 0)
base = c == '0' ? 8 : 10;
/*
* Compute the cutoff value between legal numbers and illegal
* numbers. That is the largest legal value, divided by the
* base. An input number that is greater than this value, if
* followed by a legal input character, is too big. One that
* is equal to this value may be valid or not; the limit
* between valid and invalid numbers is then based on the last
* digit. For instance, if the range for longs is
* [-2147483648..2147483647] and the input base is 10,
* cutoff will be set to 214748364 and cutlim to either
* 7 (neg==0) or 8 (neg==1), meaning that if we have accumulated
* a value > 214748364, or equal but the next digit is > 7 (or 8),
* the number is too big, and we will return a range error.
*
* Set any if any `digits' consumed; make it negative to indicate
* overflow.
*/
cutoff = neg ? -(unsigned long)LONG_MIN : LONG_MAX;
cutlim = cutoff % (unsigned long)base;
cutoff /= (unsigned long)base;
for (acc = 0, any = 0;; c = *s++) {
if (isdigit(c))
c -= '0';
else if (isalpha(c))
c -= isupper(c) ? 'A' - 10 : 'a' - 10;
else
break;
if (c >= base)
break;
if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim)
any = -1;
else {
any = 1;
acc *= base;
acc += c;
}
}
if (any < 0) {
acc = neg ? LONG_MIN : LONG_MAX;
//errno = ERANGE;
} else if (neg)
acc = -acc;
if (endptr != 0)
*endptr = (char *)(any ? s - 1 : nptr);
return (acc);
}
/*
* Convert a string to an unsigned long integer.
*
* Ignores `locale' stuff. Assumes that the upper and lower case
* alphabets and digits are each contiguous.
*/
unsigned long
strtoul(nptr, endptr, base)
const char *nptr;
char **endptr;
register int base;
{
register const char *s = nptr;
register unsigned long acc;
register int c;
register unsigned long cutoff;
register int neg = 0, any, cutlim;
/*
* See strtol for comments as to the logic used.
*/
do {
c = *s++;
} while (isspace(c));
if (c == '-') {
neg = 1;
c = *s++;
} else if (c == '+')
c = *s++;
if ((base == 0 || base == 16) &&
c == '0' && (*s == 'x' || *s == 'X')) {
c = s[1];
s += 2;
base = 16;
} else if ((base == 0 || base == 2) &&
c == '0' && (*s == 'b' || *s == 'B')) {
c = s[1];
s += 2;
base = 2;
}
if (base == 0)
base = c == '0' ? 8 : 10;
cutoff = (unsigned long)ULONG_MAX / (unsigned long)base;
cutlim = (unsigned long)ULONG_MAX % (unsigned long)base;
for (acc = 0, any = 0;; c = *s++) {
if (isdigit(c))
c -= '0';
else if (isalpha(c))
c -= isupper(c) ? 'A' - 10 : 'a' - 10;
else
break;
if (c >= base)
break;
if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim)
any = -1;
else {
any = 1;
acc *= base;
acc += c;
}
}
if (any < 0) {
acc = ULONG_MAX;
//errno = ERANGE;
} else if (neg)
acc = -acc;
if (endptr != 0)
*endptr = (char *)(any ? s - 1 : nptr);
return (acc);
}
/*
* Convert a string to an unsigned quad integer.
*
* Ignores `locale' stuff. Assumes that the upper and lower case
* alphabets and digits are each contiguous.
*/
unsigned long long
strtouq(nptr, endptr, base)
const char *nptr;
char **endptr;
register int base;
{
register const char *s = nptr;
register unsigned long long acc;
register int c;
register unsigned long long qbase, cutoff;
register int neg, any, cutlim;
/*
* See strtoq for comments as to the logic used.
*/
s = nptr;
do {
c = *s++;
} while (isspace(c));
if (c == '-') {
neg = 1;
c = *s++;
} else {
neg = 0;
if (c == '+')
c = *s++;
}
if ((base == 0 || base == 16) &&
c == '0' && (*s == 'x' || *s == 'X')) {
c = s[1];
s += 2;
base = 16;
}
if (base == 0)
base = c == '0' ? 8 : 10;
qbase = (unsigned)base;
cutoff = (unsigned long long)UQUAD_MAX / qbase;
cutlim = (unsigned long long)UQUAD_MAX % qbase;
for (acc = 0, any = 0;; c = *s++) {
if (isdigit(c))
c -= '0';
else if (isalpha(c))
c -= isupper(c) ? 'A' - 10 : 'a' - 10;
else
break;
if (c >= base)
break;
if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim)
any = -1;
else {
any = 1;
acc *= qbase;
acc += c;
}
}
if (any < 0) {
acc = UQUAD_MAX;
//errno = ERANGE;
} else if (neg)
acc = -acc;
if (endptr != 0)
*endptr = (char *)(any ? s - 1 : nptr);
return (acc);
}
branches/xZenu/src/arch/i386/libsa/qsort.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
/*
* Copyright (c) 1999-2003 Apple Computer, Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* Portions Copyright (c) 1999-2003 Apple Computer, Inc. All Rights
* Reserved. This file contains Original Code and/or Modifications of
* Original Code as defined in and that are subject to the Apple Public
* Source License Version 2.0 (the "License"). You may not use this file
* except in compliance with the License. Please obtain a copy of the
* License at http://www.apple.com/publicsource and read it before using
* this file.
*
* The Original Code and all software distributed under the License are
* distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT. Please see the
* License for the specific language governing rights and limitations
* under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/
/*
* Copyright (c) 1992, 1993
*The Regents of the University of California. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
*This product includes software developed by the University of
*California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include <sys/types.h>
#include <stdlib.h>
#include <sys/param.h>
static inline char*med3 __P((char *, char *, char *, int (*)()));
static inline void swapfunc __P((char *, char *, int, int));
/*
* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
*/
#define swapcode(TYPE, parmi, parmj, n) { \
long i = (n) / sizeof (TYPE); \
register TYPE *pi = (TYPE *) (parmi); \
register TYPE *pj = (TYPE *) (parmj); \
do { \
register TYPEt = *pi;\
*pi++ = *pj;\
*pj++ = t;\
} while (--i > 0);\
}
#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
static inline void
swapfunc(a, b, n, swaptype)
char *a, *b;
int n, swaptype;
{
if(swaptype <= 1)
swapcode(long, a, b, n)
else
swapcode(char, a, b, n)
}
#define swap(a, b)\
if (swaptype == 0) {\
long t = *(long *)(a);\
*(long *)(a) = *(long *)(b);\
*(long *)(b) = t;\
} else\
swapfunc(a, b, es, swaptype)
#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
static inline char *
med3(a, b, c, cmp)
char *a, *b, *c;
int (*cmp)();
{
return cmp(a, b) < 0 ?
(cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
:(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
}
void
qsort(a, n, es, cmp)
void *a;
size_t n, es;
int (*cmp)();
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
int d, r, swaptype, swap_cnt;
loop:SWAPINIT(a, es);
swap_cnt = 0;
if (n < 7) {
for (pm = a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
pl -= es)
swap(pl, pl - es);
return;
}
pm = a + (n / 2) * es;
if (n > 7) {
pl = a;
pn = a + (n - 1) * es;
if (n > 40) {
d = (n / 8) * es;
pl = med3(pl, pl + d, pl + 2 * d, cmp);
pm = med3(pm - d, pm, pm + d, cmp);
pn = med3(pn - 2 * d, pn - d, pn, cmp);
}
pm = med3(pl, pm, pn, cmp);
}
swap(a, pm);
pa = pb = a + es;
pc = pd = a + (n - 1) * es;
for (;;) {
while (pb <= pc && (r = cmp(pb, a)) <= 0) {
if (r == 0) {
swap_cnt = 1;
swap(pa, pb);
pa += es;
}
pb += es;
}
while (pb <= pc && (r = cmp(pc, a)) >= 0) {
if (r == 0) {
swap_cnt = 1;
swap(pc, pd);
pd -= es;
}
pc -= es;
}
if (pb > pc)
break;
swap(pb, pc);
swap_cnt = 1;
pb += es;
pc -= es;
}
if (swap_cnt == 0) { /* Switch to insertion sort */
for (pm = a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
pl -= es)
swap(pl, pl - es);
return;
}
pn = a + n * es;
r = MIN(pa - (char *)a, pb - pa);
vecswap(a, pb - r, r);
r = MIN(pd - pc, (pn - pd) - (int)es);
vecswap(pb, pn - r, r);
if ((r = pb - pa) > (int)es)
qsort(a, r / es, es, cmp);
if ((r = pd - pc) > (int)es) {
/* Iterate rather than recurse to save stack space */
a = pn - r;
n = r / es;
goto loop;
}
/*qsort(pn - r, r / es, es, cmp);*/
}
branches/xZenu/src/arch/i386/libsa/string.c
3939
4040
4141
42
43
44
45
46
4742
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
: "memory", "%edx" );
}
/* #if DONT_USE_GCC_BUILT_IN_STRLEN */
#define tolower(c) ((int)((c) & ~0x20))
#define toupper(c) ((int)((c) | 0x20))
/*#endif*/
int
ptol(const char *str)
{
register int c = *str;
if (c <= '7' && c >= '0')
c -= '0';
else if (c <= 'h' && c >= 'a')
c -= 'a';
else c = 0;
return c;
}
char* strbreak(const char *str, char **next, long *len)
{
char *start = (char*)str, *end;
bool quoted = false;
if ( !start || !len )
return 0;
*len = 0;
while ( isspace(*start) )
start++;
if (*start == '"')
{
start++;
end = strchr(start, '"');
if(end)
quoted = true;
else
end = strchr(start, '\0');
}
else
{
for ( end = start; *end && !isspace(*end); end++ )
{}
}
*len = end - start;
if(next)
*next = quoted ? end+1 : end;
return start;
}
/* COPYRIGHT NOTICE: checksum8 from AppleSMBIOS */
uint8_t checksum8( void * start, unsigned int length )
{
uint8_t csum = 0;
uint8_t * cp = (uint8_t *) start;
unsigned int i;
for ( i = 0; i < length; i++)
csum += *cp++;
return csum;
}
branches/xZenu/src/arch/i386/libsa/Makefile
2222
2323
2424
25
26
25
26
2727
2828
2929
INC = -I. -I$(SYMROOT) -I$(LIBSAIODIR) -I${SRCROOT}/include
OBJECTS = prf printf \
string strtol error \
setjmp qsort efi_tables
string error \
setjmp efi_tables
LIBS = libsa.a
LIBS := $(addprefix $(SYMROOT)/, $(LIBS))

Archive Download the corresponding diff file

Revision: 1293