Mercurial > projects > ldc

comparison tango/lib/compiler/llvmdc/adi.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children 8f43f5c43c95
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
1 //_ adi.d
2
3 /**
4 * Part of the D programming language runtime library.
5 * Dynamic array property support routines
6 */
7
8 /*
9 * Copyright (C) 2000-2006 by Digital Mars, www.digitalmars.com
10 * Written by Walter Bright
11 *
12 * This software is provided 'as-is', without any express or implied
13 * warranty. In no event will the authors be held liable for any damages
14 * arising from the use of this software.
15 *
16 * Permission is granted to anyone to use this software for any purpose,
17 * including commercial applications, and to alter it and redistribute it
18 * freely, in both source and binary form, subject to the following
19 * restrictions:
20 *
21 * o The origin of this software must not be misrepresented; you must not
22 * claim that you wrote the original software. If you use this software
23 * in a product, an acknowledgment in the product documentation would be
24 * appreciated but is not required.
25 * o Altered source versions must be plainly marked as such, and must not
26 * be misrepresented as being the original software.
27 * o This notice may not be removed or altered from any source
28 * distribution.
29 */
30
31 /*
32 * Modified by Sean Kelly <sean@f4.ca> for use with Tango.
33 */
34
35
36 //debug=adi; // uncomment to turn on debugging printf's
37
38 private
39 {
40 import tango.stdc.string;
41 import tango.stdc.stdlib;
42 import util.utf;
43
44 enum BlkAttr : uint
45 {
46 FINALIZE = 0b0000_0001,
47 NO_SCAN = 0b0000_0010,
48 NO_MOVE = 0b0000_0100,
49 ALL_BITS = 0b1111_1111
50 }
51
52 extern (C) void* gc_malloc( size_t sz, uint ba = 0 );
53 extern (C) void* gc_calloc( size_t sz, uint ba = 0 );
54 extern (C) void gc_free( void* p );
55 }
56
57
58 struct Array
59 {
60 size_t length;
61 void* ptr;
62 }
63
64 /**********************************************
65 * Reverse array of chars.
66 * Handled separately because embedded multibyte encodings should not be
67 * reversed.
68 */
69
70 extern (C) long _adReverseChar(char[] a)
71 {
72 if (a.length > 1)
73 {
74 char[6] tmp;
75 char[6] tmplo;
76 char* lo = a.ptr;
77 char* hi = &a[length - 1];
78
79 while (lo < hi)
80 { auto clo = *lo;
81 auto chi = *hi;
82
83 debug(adi) printf("lo = %d, hi = %d\n", lo, hi);
84 if (clo <= 0x7F && chi <= 0x7F)
85 {
86 debug(adi) printf("\tascii\n");
87 *lo = chi;
88 *hi = clo;
89 lo++;
90 hi--;
91 continue;
92 }
93
94 uint stridelo = UTF8stride[clo];
95
96 uint stridehi = 1;
97 while ((chi & 0xC0) == 0x80)
98 {
99 chi = *--hi;
100 stridehi++;
101 assert(hi >= lo);
102 }
103 if (lo == hi)
104 break;
105
106 debug(adi) printf("\tstridelo = %d, stridehi = %d\n", stridelo, stridehi);
107 if (stridelo == stridehi)
108 {
109
110 memcpy(tmp.ptr, lo, stridelo);
111 memcpy(lo, hi, stridelo);
112 memcpy(hi, tmp.ptr, stridelo);
113 lo += stridelo;
114 hi--;
115 continue;
116 }
117
118 /* Shift the whole array. This is woefully inefficient
119 */
120 memcpy(tmp.ptr, hi, stridehi);
121 memcpy(tmplo.ptr, lo, stridelo);
122 memmove(lo + stridehi, lo + stridelo , cast(size_t)(hi - lo) - stridelo);
123 memcpy(lo, tmp.ptr, stridehi);
124 memcpy(hi + stridehi - stridelo, tmplo.ptr, stridelo);
125
126 lo += stridehi;
127 hi = hi - 1 + (stridehi - stridelo);
128 }
129 }
130 return *cast(long*)(&a);
131 }
132
133 unittest
134 {
135 auto a = "abcd"c;
136
137 auto r = a.dup.reverse;
138 //writefln(r);
139 assert(r == "dcba");
140
141 a = "a\u1235\u1234c";
142 //writefln(a);
143 r = a.dup.reverse;
144 //writefln(r);
145 assert(r == "c\u1234\u1235a");
146
147 a = "ab\u1234c";
148 //writefln(a);
149 r = a.dup.reverse;
150 //writefln(r);
151 assert(r == "c\u1234ba");
152
153 a = "\u3026\u2021\u3061\n";
154 r = a.dup.reverse;
155 assert(r == "\n\u3061\u2021\u3026");
156 }
157
158
159 /**********************************************
160 * Reverse array of wchars.
161 * Handled separately because embedded multiword encodings should not be
162 * reversed.
163 */
164
165 extern (C) long _adReverseWchar(wchar[] a)
166 {
167 if (a.length > 1)
168 {
169 wchar[2] tmp;
170 wchar* lo = a.ptr;
171 wchar* hi = &a[length - 1];
172
173 while (lo < hi)
174 { auto clo = *lo;
175 auto chi = *hi;
176
177 if ((clo < 0xD800 || clo > 0xDFFF) &&
178 (chi < 0xD800 || chi > 0xDFFF))
179 {
180 *lo = chi;
181 *hi = clo;
182 lo++;
183 hi--;
184 continue;
185 }
186
187 int stridelo = 1 + (clo >= 0xD800 && clo <= 0xDBFF);
188
189 int stridehi = 1;
190 if (chi >= 0xDC00 && chi <= 0xDFFF)
191 {
192 chi = *--hi;
193 stridehi++;
194 assert(hi >= lo);
195 }
196 if (lo == hi)
197 break;
198
199 if (stridelo == stridehi)
200 { int stmp;
201
202 assert(stridelo == 2);
203 assert(stmp.sizeof == 2 * (*lo).sizeof);
204 stmp = *cast(int*)lo;
205 *cast(int*)lo = *cast(int*)hi;
206 *cast(int*)hi = stmp;
207 lo += stridelo;
208 hi--;
209 continue;
210 }
211
212 /* Shift the whole array. This is woefully inefficient
213 */
214 memcpy(tmp.ptr, hi, stridehi * wchar.sizeof);
215 memcpy(hi + stridehi - stridelo, lo, stridelo * wchar.sizeof);
216 memmove(lo + stridehi, lo + stridelo , (hi - (lo + stridelo)) * wchar.sizeof);
217 memcpy(lo, tmp.ptr, stridehi * wchar.sizeof);
218
219 lo += stridehi;
220 hi = hi - 1 + (stridehi - stridelo);
221 }
222 }
223 return *cast(long*)(&a);
224 }
225
226 unittest
227 {
228 wstring a = "abcd";
229 wstring r;
230
231 r = a.dup.reverse;
232 assert(r == "dcba");
233
234 a = "a\U00012356\U00012346c";
235 r = a.dup.reverse;
236 assert(r == "c\U00012346\U00012356a");
237
238 a = "ab\U00012345c";
239 r = a.dup.reverse;
240 assert(r == "c\U00012345ba");
241 }
242
243
244 /**********************************************
245 * Support for array.reverse property.
246 */
247
248 extern (C) long _adReverse(Array a, size_t szelem)
249 out (result)
250 {
251 assert(result is *cast(long*)(&a));
252 }
253 body
254 {
255 if (a.length >= 2)
256 {
257 byte* tmp;
258 byte[16] buffer;
259
260 void* lo = a.ptr;
261 void* hi = a.ptr + (a.length - 1) * szelem;
262
263 tmp = buffer.ptr;
264 if (szelem > 16)
265 {
266 //version (Win32)
267 tmp = cast(byte*) alloca(szelem);
268 //else
269 //tmp = gc_malloc(szelem);
270 }
271
272 for (; lo < hi; lo += szelem, hi -= szelem)
273 {
274 memcpy(tmp, lo, szelem);
275 memcpy(lo, hi, szelem);
276 memcpy(hi, tmp, szelem);
277 }
278
279 version (Win32)
280 {
281 }
282 else
283 {
284 //if (szelem > 16)
285 // BUG: bad code is generate for delete pointer, tries
286 // to call delclass.
287 //gc_free(tmp);
288 }
289 }
290 return *cast(long*)(&a);
291 }
292
293 unittest
294 {
295 debug(adi) printf("array.reverse.unittest\n");
296
297 int[] a = new int[5];
298 int[] b;
299 size_t i;
300
301 for (i = 0; i < 5; i++)
302 a[i] = i;
303 b = a.reverse;
304 assert(b is a);
305 for (i = 0; i < 5; i++)
306 assert(a[i] == 4 - i);
307
308 struct X20
309 { // More than 16 bytes in size
310 int a;
311 int b, c, d, e;
312 }
313
314 X20[] c = new X20[5];
315 X20[] d;
316
317 for (i = 0; i < 5; i++)
318 { c[i].a = i;
319 c[i].e = 10;
320 }
321 d = c.reverse;
322 assert(d is c);
323 for (i = 0; i < 5; i++)
324 {
325 assert(c[i].a == 4 - i);
326 assert(c[i].e == 10);
327 }
328 }
329
330 /**********************************************
331 * Sort array of chars.
332 */
333
334 extern (C) long _adSortChar(char[] a)
335 {
336 if (a.length > 1)
337 {
338 dchar[] da = toUTF32(a);
339 da.sort;
340 size_t i = 0;
341 foreach (dchar d; da)
342 { char[4] buf;
343 auto t = toUTF8(buf, d);
344 a[i .. i + t.length] = t[];
345 i += t.length;
346 }
347 delete da;
348 }
349 return *cast(long*)(&a);
350 }
351
352 /**********************************************
353 * Sort array of wchars.
354 */
355
356 extern (C) long _adSortWchar(wchar[] a)
357 {
358 if (a.length > 1)
359 {
360 dchar[] da = toUTF32(a);
361 da.sort;
362 size_t i = 0;
363 foreach (dchar d; da)
364 { wchar[2] buf;
365 auto t = toUTF16(buf, d);
366 a[i .. i + t.length] = t[];
367 i += t.length;
368 }
369 delete da;
370 }
371 return *cast(long*)(&a);
372 }
373
374 /***************************************
375 * Support for array equality test.
376 */
377
378 extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
379 {
380 debug(adi) printf("_adEq(a1.length = %d, a2.length = %d)\n", a1.length, a2.length);
381 if (a1.length != a2.length)
382 return 0; // not equal
383 auto sz = ti.tsize();
384 auto p1 = a1.ptr;
385 auto p2 = a2.ptr;
386
387 /+
388 for (int i = 0; i < a1.length; i++)
389 {
390 printf("%4x %4x\n", (cast(short*)p1)[i], (cast(short*)p2)[i]);
391 }
392 +/
393
394 if (sz == 1)
395 // We should really have a ti.isPOD() check for this
396 return (memcmp(p1, p2, a1.length) == 0);
397
398 for (size_t i = 0; i < a1.length; i++)
399 {
400 if (!ti.equals(p1 + i * sz, p2 + i * sz))
401 return 0; // not equal
402 }
403 return 1; // equal
404 }
405
406 unittest
407 {
408 debug(adi) printf("array.Eq unittest\n");
409
410 auto a = "hello"c;
411
412 assert(a != "hel");
413 assert(a != "helloo");
414 assert(a != "betty");
415 assert(a == "hello");
416 assert(a != "hxxxx");
417 }
418
419 /***************************************
420 * Support for array compare test.
421 */
422
423 extern (C) int _adCmp(Array a1, Array a2, TypeInfo ti)
424 {
425 debug(adi) printf("adCmp()\n");
426 auto len = a1.length;
427 if (a2.length < len)
428 len = a2.length;
429 auto sz = ti.tsize();
430 void *p1 = a1.ptr;
431 void *p2 = a2.ptr;
432
433 if (sz == 1)
434 { // We should really have a ti.isPOD() check for this
435 auto c = memcmp(p1, p2, len);
436 if (c)
437 return c;
438 }
439 else
440 {
441 for (size_t i = 0; i < len; i++)
442 {
443 auto c = ti.compare(p1 + i * sz, p2 + i * sz);
444 if (c)
445 return c;
446 }
447 }
448 if (a1.length == a2.length)
449 return 0;
450 return (a1.length > a2.length) ? 1 : -1;
451 }
452
453 unittest
454 {
455 debug(adi) printf("array.Cmp unittest\n");
456
457 auto a = "hello"c;
458
459 assert(a > "hel");
460 assert(a >= "hel");
461 assert(a < "helloo");
462 assert(a <= "helloo");
463 assert(a > "betty");
464 assert(a >= "betty");
465 assert(a == "hello");
466 assert(a <= "hello");
467 assert(a >= "hello");
468 }
469
470 /***************************************
471 * Support for array compare test.
472 */
473
474 extern (C) int _adCmpChar(Array a1, Array a2)
475 {
476 version (X86)
477 {
478 asm
479 { naked ;
480
481 push EDI ;
482 push ESI ;
483
484 mov ESI,a1+4[4+ESP] ;
485 mov EDI,a2+4[4+ESP] ;
486
487 mov ECX,a1[4+ESP] ;
488 mov EDX,a2[4+ESP] ;
489
490 cmp ECX,EDX ;
491 jb GotLength ;
492
493 mov ECX,EDX ;
494
495 GotLength:
496 cmp ECX,4 ;
497 jb DoBytes ;
498
499 // Do alignment if neither is dword aligned
500 test ESI,3 ;
501 jz Aligned ;
502
503 test EDI,3 ;
504 jz Aligned ;
505 DoAlign:
506 mov AL,[ESI] ; //align ESI to dword bounds
507 mov DL,[EDI] ;
508
509 cmp AL,DL ;
510 jnz Unequal ;
511
512 inc ESI ;
513 inc EDI ;
514
515 test ESI,3 ;
516
517 lea ECX,[ECX-1] ;
518 jnz DoAlign ;
519 Aligned:
520 mov EAX,ECX ;
521
522 // do multiple of 4 bytes at a time
523
524 shr ECX,2 ;
525 jz TryOdd ;
526
527 repe ;
528 cmpsd ;
529
530 jnz UnequalQuad ;
531
532 TryOdd:
533 mov ECX,EAX ;
534 DoBytes:
535 // if still equal and not end of string, do up to 3 bytes slightly
536 // slower.
537
538 and ECX,3 ;
539 jz Equal ;
540
541 repe ;
542 cmpsb ;
543
544 jnz Unequal ;
545 Equal:
546 mov EAX,a1[4+ESP] ;
547 mov EDX,a2[4+ESP] ;
548
549 sub EAX,EDX ;
550 pop ESI ;
551
552 pop EDI ;
553 ret ;
554
555 UnequalQuad:
556 mov EDX,[EDI-4] ;
557 mov EAX,[ESI-4] ;
558
559 cmp AL,DL ;
560 jnz Unequal ;
561
562 cmp AH,DH ;
563 jnz Unequal ;
564
565 shr EAX,16 ;
566
567 shr EDX,16 ;
568
569 cmp AL,DL ;
570 jnz Unequal ;
571
572 cmp AH,DH ;
573 Unequal:
574 sbb EAX,EAX ;
575 pop ESI ;
576
577 or EAX,1 ;
578 pop EDI ;
579
580 ret ;
581 }
582 }
583 else
584 {
585 int len;
586 int c;
587
588 debug(adi) printf("adCmpChar()\n");
589 len = cast(int)a1.length;
590 if (a2.length < len)
591 len = cast(int)a2.length;
592 c = memcmp(cast(char *)a1.ptr, cast(char *)a2.ptr, len);
593 if (!c)
594 c = cast(int)a1.length - cast(int)a2.length;
595 return c;
596 }
597 }
598
599 unittest
600 {
601 debug(adi) printf("array.CmpChar unittest\n");
602
603 auto a = "hello"c;
604
605 assert(a > "hel");
606 assert(a >= "hel");
607 assert(a < "helloo");
608 assert(a <= "helloo");
609 assert(a > "betty");
610 assert(a >= "betty");
611 assert(a == "hello");
612 assert(a <= "hello");
613 assert(a >= "hello");
614 }