Mercurial > projects > ldc

comparison lphobos/internal/adi.d @ 94:61615fa85940 trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca"). Added support for array .sort and .reverse properties. Fixed some bugs with pointer arithmetic. Disabled some DMD AST optimizations that was messing things up, destroying valuable information. Added a KDevelop project file, this is what I use for coding LLVMDC now :) Other minor stuff.
author lindquist
date Mon, 12 Nov 2007 06:32:46 +0100
parents
children c4e161556a21
comparison
equal deleted inserted replaced
93:08508eebbb3e 94:61615fa85940
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 //debug=adi; // uncomment to turn on debugging printf's
32
33 //import std.stdio;
34 import std.c.stdio;
35 import std.c.stdlib;
36 import std.c.string;
37 //import std.string;
38 import std.outofmemory;
39 import std.utf;
40
41 struct Array
42 {
43 size_t length;
44 void* ptr;
45 }
46
47 /**********************************************
48 * Reverse array of chars.
49 * Handled separately because embedded multibyte encodings should not be
50 * reversed.
51 */
52
53 extern (C) long _adReverseChar(char[] a)
54 {
55 if (a.length > 1)
56 {
57 char[6] tmp;
58 char[6] tmplo;
59 char* lo = a.ptr;
60 char* hi = &a[length - 1];
61
62 while (lo < hi)
63 { auto clo = *lo;
64 auto chi = *hi;
65
66 //printf("lo = %d, hi = %d\n", lo, hi);
67 if (clo <= 0x7F && chi <= 0x7F)
68 {
69 //printf("\tascii\n");
70 *lo = chi;
71 *hi = clo;
72 lo++;
73 hi--;
74 continue;
75 }
76
77 uint stridelo = std.utf.UTF8stride[clo];
78
79 uint stridehi = 1;
80 while ((chi & 0xC0) == 0x80)
81 {
82 chi = *--hi;
83 stridehi++;
84 assert(hi >= lo);
85 }
86 if (lo == hi)
87 break;
88
89 //printf("\tstridelo = %d, stridehi = %d\n", stridelo, stridehi);
90 if (stridelo == stridehi)
91 {
92
93 memcpy(tmp.ptr, lo, stridelo);
94 memcpy(lo, hi, stridelo);
95 memcpy(hi, tmp.ptr, stridelo);
96 lo += stridelo;
97 hi--;
98 continue;
99 }
100
101 /* Shift the whole array. This is woefully inefficient
102 */
103 memcpy(tmp.ptr, hi, stridehi);
104 memcpy(tmplo.ptr, lo, stridelo);
105 memmove(lo + stridehi, lo + stridelo , (hi - lo) - stridelo);
106 memcpy(lo, tmp.ptr, stridehi);
107 memcpy(hi + stridehi - stridelo, tmplo.ptr, stridelo);
108
109 lo += stridehi;
110 hi = hi - 1 + (stridehi - stridelo);
111 }
112 }
113 return *cast(long*)(&a);
114 }
115
116 unittest
117 {
118 string a = "abcd";
119 string r;
120
121 r = a.dup.reverse;
122 //writefln(r);
123 assert(r == "dcba");
124
125 a = "a\u1235\u1234c";
126 //writefln(a);
127 r = a.dup.reverse;
128 //writefln(r);
129 assert(r == "c\u1234\u1235a");
130
131 a = "ab\u1234c";
132 //writefln(a);
133 r = a.dup.reverse;
134 //writefln(r);
135 assert(r == "c\u1234ba");
136
137 a = "\u3026\u2021\u3061\n";
138 r = a.dup.reverse;
139 assert(r == "\n\u3061\u2021\u3026");
140 }
141
142
143 /**********************************************
144 * Reverse array of wchars.
145 * Handled separately because embedded multiword encodings should not be
146 * reversed.
147 */
148
149 extern (C) long _adReverseWchar(wchar[] a)
150 {
151 if (a.length > 1)
152 {
153 wchar[2] tmp;
154 wchar* lo = a.ptr;
155 wchar* hi = &a[length - 1];
156
157 while (lo < hi)
158 { auto clo = *lo;
159 auto chi = *hi;
160
161 if ((clo < 0xD800 || clo > 0xDFFF) &&
162 (chi < 0xD800 || chi > 0xDFFF))
163 {
164 *lo = chi;
165 *hi = clo;
166 lo++;
167 hi--;
168 continue;
169 }
170
171 int stridelo = 1 + (clo >= 0xD800 && clo <= 0xDBFF);
172
173 int stridehi = 1;
174 if (chi >= 0xDC00 && chi <= 0xDFFF)
175 {
176 chi = *--hi;
177 stridehi++;
178 assert(hi >= lo);
179 }
180 if (lo == hi)
181 break;
182
183 if (stridelo == stridehi)
184 { int stmp;
185
186 assert(stridelo == 2);
187 assert(stmp.sizeof == 2 * (*lo).sizeof);
188 stmp = *cast(int*)lo;
189 *cast(int*)lo = *cast(int*)hi;
190 *cast(int*)hi = stmp;
191 lo += stridelo;
192 hi--;
193 continue;
194 }
195
196 /* Shift the whole array. This is woefully inefficient
197 */
198 memcpy(tmp.ptr, hi, stridehi * wchar.sizeof);
199 memcpy(hi + stridehi - stridelo, lo, stridelo * wchar.sizeof);
200 memmove(lo + stridehi, lo + stridelo , (hi - (lo + stridelo)) * wchar.sizeof);
201 memcpy(lo, tmp.ptr, stridehi * wchar.sizeof);
202
203 lo += stridehi;
204 hi = hi - 1 + (stridehi - stridelo);
205 }
206 }
207 return *cast(long*)(&a);
208 }
209
210 unittest
211 {
212 wstring a = "abcd";
213 wstring r;
214
215 r = a.dup.reverse;
216 assert(r == "dcba");
217
218 a = "a\U00012356\U00012346c";
219 r = a.dup.reverse;
220 assert(r == "c\U00012346\U00012356a");
221
222 a = "ab\U00012345c";
223 r = a.dup.reverse;
224 assert(r == "c\U00012345ba");
225 }
226
227
228 /**********************************************
229 * Support for array.reverse property.
230 */
231
232 extern (C) long _adReverse(Array a, size_t szelem)
233 out (result)
234 {
235 assert(result is *cast(long*)(&a));
236 }
237 body
238 {
239 if (a.length >= 2)
240 {
241 byte* tmp;
242 byte[16] buffer;
243
244 void* lo = a.ptr;
245 void* hi = a.ptr + (a.length - 1) * szelem;
246
247 tmp = buffer.ptr;
248 if (szelem > 16)
249 {
250 //version (Win32)
251 tmp = cast(byte*) alloca(szelem);
252 //else
253 //tmp = new byte[szelem];
254 }
255
256 for (; lo < hi; lo += szelem, hi -= szelem)
257 {
258 memcpy(tmp, lo, szelem);
259 memcpy(lo, hi, szelem);
260 memcpy(hi, tmp, szelem);
261 }
262
263 version (Win32)
264 {
265 }
266 else
267 {
268 //if (szelem > 16)
269 // BUG: bad code is generate for delete pointer, tries
270 // to call delclass.
271 //delete tmp;
272 }
273 }
274 return *cast(long*)(&a);
275 }
276
277 unittest
278 {
279 debug(adi) printf("array.reverse.unittest\n");
280
281 int[] a = new int[5];
282 int[] b;
283 size_t i;
284
285 for (i = 0; i < 5; i++)
286 a[i] = i;
287 b = a.reverse;
288 assert(b is a);
289 for (i = 0; i < 5; i++)
290 assert(a[i] == 4 - i);
291
292 struct X20
293 { // More than 16 bytes in size
294 int a;
295 int b, c, d, e;
296 }
297
298 X20[] c = new X20[5];
299 X20[] d;
300
301 for (i = 0; i < 5; i++)
302 { c[i].a = i;
303 c[i].e = 10;
304 }
305 d = c.reverse;
306 assert(d is c);
307 for (i = 0; i < 5; i++)
308 {
309 assert(c[i].a == 4 - i);
310 assert(c[i].e == 10);
311 }
312 }
313
314 /**********************************************
315 * Support for array.reverse property for bit[].
316 */
317
318 version (none)
319 {
320 extern (C) bit[] _adReverseBit(bit[] a)
321 out (result)
322 {
323 assert(result is a);
324 }
325 body
326 {
327 if (a.length >= 2)
328 {
329 bit t;
330 int lo, hi;
331
332 lo = 0;
333 hi = a.length - 1;
334 for (; lo < hi; lo++, hi--)
335 {
336 t = a[lo];
337 a[lo] = a[hi];
338 a[hi] = t;
339 }
340 }
341 return a;
342 }
343
344 unittest
345 {
346 debug(adi) printf("array.reverse_Bit[].unittest\n");
347
348 bit[] b;
349 b = new bit[5];
350 static bit[5] data = [1,0,1,1,0];
351 int i;
352
353 b[] = data[];
354 b.reverse;
355 for (i = 0; i < 5; i++)
356 {
357 assert(b[i] == data[4 - i]);
358 }
359 }
360 }
361
362 /**********************************************
363 * Sort array of chars.
364 */
365
366 extern (C) long _adSortChar(char[] a)
367 {
368 if (a.length > 1)
369 {
370 dstring da = toUTF32(a);
371 da.sort;
372 size_t i = 0;
373 foreach (dchar d; da)
374 { char[4] buf;
375 string t = toUTF8(buf, d);
376 a[i .. i + t.length] = t[];
377 i += t.length;
378 }
379 delete da;
380 }
381 return *cast(long*)(&a);
382 }
383
384 /**********************************************
385 * Sort array of wchars.
386 */
387
388 extern (C) long _adSortWchar(wchar[] a)
389 {
390 if (a.length > 1)
391 {
392 dstring da = toUTF32(a);
393 da.sort;
394 size_t i = 0;
395 foreach (dchar d; da)
396 { wchar[2] buf;
397 wstring t = toUTF16(buf, d);
398 a[i .. i + t.length] = t[];
399 i += t.length;
400 }
401 delete da;
402 }
403 return *cast(long*)(&a);
404 }
405
406 /**********************************************
407 * Support for array.sort property for bit[].
408 */
409
410 version (none)
411 {
412 extern (C) bit[] _adSortBit(bit[] a)
413 out (result)
414 {
415 assert(result is a);
416 }
417 body
418 {
419 if (a.length >= 2)
420 {
421 size_t lo, hi;
422
423 lo = 0;
424 hi = a.length - 1;
425 while (1)
426 {
427 while (1)
428 {
429 if (lo >= hi)
430 goto Ldone;
431 if (a[lo] == true)
432 break;
433 lo++;
434 }
435
436 while (1)
437 {
438 if (lo >= hi)
439 goto Ldone;
440 if (a[hi] == false)
441 break;
442 hi--;
443 }
444
445 a[lo] = false;
446 a[hi] = true;
447
448 lo++;
449 hi--;
450 }
451 Ldone:
452 ;
453 }
454 return a;
455 }
456
457 unittest
458 {
459 debug(adi) printf("array.sort_Bit[].unittest\n");
460 }
461 }
462
463 /***************************************
464 * Support for array equality test.
465 */
466
467 extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
468 {
469 //printf("_adEq(a1.length = %d, a2.length = %d)\n", a1.length, a2.length);
470 if (a1.length != a2.length)
471 return 0; // not equal
472 auto sz = ti.tsize();
473 auto p1 = a1.ptr;
474 auto p2 = a2.ptr;
475
476 /+
477 for (int i = 0; i < a1.length; i++)
478 {
479 printf("%4x %4x\n", (cast(short*)p1)[i], (cast(short*)p2)[i]);
480 }
481 +/
482
483 if (sz == 1)
484 // We should really have a ti.isPOD() check for this
485 return (memcmp(p1, p2, a1.length) == 0);
486
487 for (size_t i = 0; i < a1.length; i++)
488 {
489 if (!ti.equals(p1 + i * sz, p2 + i * sz))
490 return 0; // not equal
491 }
492 return 1; // equal
493 }
494
495 unittest
496 {
497 debug(adi) printf("array.Eq unittest\n");
498
499 string a = "hello";
500
501 assert(a != "hel");
502 assert(a != "helloo");
503 assert(a != "betty");
504 assert(a == "hello");
505 assert(a != "hxxxx");
506 }
507
508 /***************************************
509 * Support for array equality test for bit arrays.
510 */
511
512 version (none)
513 {
514 extern (C) int _adEqBit(Array a1, Array a2)
515 { size_t i;
516
517 if (a1.length != a2.length)
518 return 0; // not equal
519 auto p1 = cast(byte*)a1.ptr;
520 auto p2 = cast(byte*)a2.ptr;
521 auto n = a1.length / 8;
522 for (i = 0; i < n; i++)
523 {
524 if (p1[i] != p2[i])
525 return 0; // not equal
526 }
527
528 ubyte mask;
529
530 n = a1.length & 7;
531 mask = cast(ubyte)((1 << n) - 1);
532 //printf("i = %d, n = %d, mask = %x, %x, %x\n", i, n, mask, p1[i], p2[i]);
533 return (mask == 0) || (p1[i] & mask) == (p2[i] & mask);
534 }
535
536 unittest
537 {
538 debug(adi) printf("array.EqBit unittest\n");
539
540 static bit[] a = [1,0,1,0,1];
541 static bit[] b = [1,0,1];
542 static bit[] c = [1,0,1,0,1,0,1];
543 static bit[] d = [1,0,1,1,1];
544 static bit[] e = [1,0,1,0,1];
545
546 assert(a != b);
547 assert(a != c);
548 assert(a != d);
549 assert(a == e);
550 }
551 }
552
553 /***************************************
554 * Support for array compare test.
555 */
556
557 extern (C) int _adCmp(Array a1, Array a2, TypeInfo ti)
558 {
559 //printf("adCmp()\n");
560 auto len = a1.length;
561 if (a2.length < len)
562 len = a2.length;
563 auto sz = ti.tsize();
564 void *p1 = a1.ptr;
565 void *p2 = a2.ptr;
566
567 if (sz == 1)
568 { // We should really have a ti.isPOD() check for this
569 auto c = memcmp(p1, p2, len);
570 if (c)
571 return c;
572 }
573 else
574 {
575 for (size_t i = 0; i < len; i++)
576 {
577 auto c = ti.compare(p1 + i * sz, p2 + i * sz);
578 if (c)
579 return c;
580 }
581 }
582 if (a1.length == a2.length)
583 return 0;
584 return (a1.length > a2.length) ? 1 : -1;
585 }
586
587 unittest
588 {
589 debug(adi) printf("array.Cmp unittest\n");
590
591 string a = "hello";
592
593 assert(a > "hel");
594 assert(a >= "hel");
595 assert(a < "helloo");
596 assert(a <= "helloo");
597 assert(a > "betty");
598 assert(a >= "betty");
599 assert(a == "hello");
600 assert(a <= "hello");
601 assert(a >= "hello");
602 }
603
604 /***************************************
605 * Support for array compare test.
606 */
607
608 extern (C) int _adCmpChar(Array a1, Array a2)
609 {
610 version (D_InlineAsm_X86)
611 {
612 asm
613 { naked ;
614
615 push EDI ;
616 push ESI ;
617
618 mov ESI,a1+4[4+ESP] ;
619 mov EDI,a2+4[4+ESP] ;
620
621 mov ECX,a1[4+ESP] ;
622 mov EDX,a2[4+ESP] ;
623
624 cmp ECX,EDX ;
625 jb GotLength ;
626
627 mov ECX,EDX ;
628
629 GotLength:
630 cmp ECX,4 ;
631 jb DoBytes ;
632
633 // Do alignment if neither is dword aligned
634 test ESI,3 ;
635 jz Aligned ;
636
637 test EDI,3 ;
638 jz Aligned ;
639 DoAlign:
640 mov AL,[ESI] ; //align ESI to dword bounds
641 mov DL,[EDI] ;
642
643 cmp AL,DL ;
644 jnz Unequal ;
645
646 inc ESI ;
647 inc EDI ;
648
649 test ESI,3 ;
650
651 lea ECX,[ECX-1] ;
652 jnz DoAlign ;
653 Aligned:
654 mov EAX,ECX ;
655
656 // do multiple of 4 bytes at a time
657
658 shr ECX,2 ;
659 jz TryOdd ;
660
661 repe ;
662 cmpsd ;
663
664 jnz UnequalQuad ;
665
666 TryOdd:
667 mov ECX,EAX ;
668 DoBytes:
669 // if still equal and not end of string, do up to 3 bytes slightly
670 // slower.
671
672 and ECX,3 ;
673 jz Equal ;
674
675 repe ;
676 cmpsb ;
677
678 jnz Unequal ;
679 Equal:
680 mov EAX,a1[4+ESP] ;
681 mov EDX,a2[4+ESP] ;
682
683 sub EAX,EDX ;
684 pop ESI ;
685
686 pop EDI ;
687 ret ;
688
689 UnequalQuad:
690 mov EDX,[EDI-4] ;
691 mov EAX,[ESI-4] ;
692
693 cmp AL,DL ;
694 jnz Unequal ;
695
696 cmp AH,DH ;
697 jnz Unequal ;
698
699 shr EAX,16 ;
700
701 shr EDX,16 ;
702
703 cmp AL,DL ;
704 jnz Unequal ;
705
706 cmp AH,DH ;
707 Unequal:
708 sbb EAX,EAX ;
709 pop ESI ;
710
711 or EAX,1 ;
712 pop EDI ;
713
714 ret ;
715 }
716 }
717 else
718 {
719 int len;
720 int c;
721
722 //printf("adCmpChar()\n");
723 len = a1.length;
724 if (a2.length < len)
725 len = a2.length;
726 c = memcmp(cast(char *)a1.ptr, cast(char *)a2.ptr, len);
727 if (!c)
728 c = cast(int)a1.length - cast(int)a2.length;
729 return c;
730 }
731 }
732
733 unittest
734 {
735 debug(adi) printf("array.CmpChar unittest\n");
736
737 string a = "hello";
738
739 assert(a > "hel");
740 assert(a >= "hel");
741 assert(a < "helloo");
742 assert(a <= "helloo");
743 assert(a > "betty");
744 assert(a >= "betty");
745 assert(a == "hello");
746 assert(a <= "hello");
747 assert(a >= "hello");
748 }
749
750 /***************************************
751 * Support for array compare test.
752 */
753
754 version (none)
755 {
756 extern (C) int _adCmpBit(Array a1, Array a2)
757 {
758 int len;
759 uint i;
760
761 len = a1.length;
762 if (a2.length < len)
763 len = a2.length;
764 ubyte *p1 = cast(ubyte*)a1.ptr;
765 ubyte *p2 = cast(ubyte*)a2.ptr;
766 uint n = len / 8;
767 for (i = 0; i < n; i++)
768 {
769 if (p1[i] != p2[i])
770 break; // not equal
771 }
772 for (uint j = i * 8; j < len; j++)
773 { ubyte mask = cast(ubyte)(1 << j);
774 int c;
775
776 c = cast(int)(p1[i] & mask) - cast(int)(p2[i] & mask);
777 if (c)
778 return c;
779 }
780 return cast(int)a1.length - cast(int)a2.length;
781 }
782
783 unittest
784 {
785 debug(adi) printf("array.CmpBit unittest\n");
786
787 static bit[] a = [1,0,1,0,1];
788 static bit[] b = [1,0,1];
789 static bit[] c = [1,0,1,0,1,0,1];
790 static bit[] d = [1,0,1,1,1];
791 static bit[] e = [1,0,1,0,1];
792
793 assert(a > b);
794 assert(a >= b);
795 assert(a < c);
796 assert(a <= c);
797 assert(a < d);
798 assert(a <= d);
799 assert(a == e);
800 assert(a <= e);
801 assert(a >= e);
802 }
803 }