tomas@443: //_ adi.d
tomas@443: 
tomas@443: /**
tomas@443:  * Part of the D programming language runtime library.
tomas@443:  * Dynamic array property support routines
tomas@443:  */
tomas@443: 
tomas@443: /*
tomas@443:  *  Copyright (C) 2000-2006 by Digital Mars, www.digitalmars.com
tomas@443:  *  Written by Walter Bright
tomas@443:  *
tomas@443:  *  This software is provided 'as-is', without any express or implied
tomas@443:  *  warranty. In no event will the authors be held liable for any damages
tomas@443:  *  arising from the use of this software.
tomas@443:  *
tomas@443:  *  Permission is granted to anyone to use this software for any purpose,
tomas@443:  *  including commercial applications, and to alter it and redistribute it
tomas@443:  *  freely, in both source and binary form, subject to the following
tomas@443:  *  restrictions:
tomas@443:  *
tomas@443:  *  o  The origin of this software must not be misrepresented; you must not
tomas@443:  *     claim that you wrote the original software. If you use this software
tomas@443:  *     in a product, an acknowledgment in the product documentation would be
tomas@443:  *     appreciated but is not required.
tomas@443:  *  o  Altered source versions must be plainly marked as such, and must not
tomas@443:  *     be misrepresented as being the original software.
tomas@443:  *  o  This notice may not be removed or altered from any source
tomas@443:  *     distribution.
tomas@443:  */
tomas@443: 
tomas@443: /*
tomas@443:  *  Modified by Sean Kelly <sean@f4.ca> for use with Tango.
tomas@443:  */
tomas@443: 
tomas@443: 
tomas@443: //debug=adi;            // uncomment to turn on debugging printf's
tomas@443: 
tomas@443: private
tomas@443: {
tomas@443:     import tango.stdc.string;
tomas@443:     import tango.stdc.stdlib;
tomas@443:     import util.utf;
tomas@443: 
tomas@443:     enum BlkAttr : uint
tomas@443:     {
tomas@443:         FINALIZE = 0b0000_0001,
tomas@443:         NO_SCAN  = 0b0000_0010,
tomas@443:         NO_MOVE  = 0b0000_0100,
tomas@443:         ALL_BITS = 0b1111_1111
tomas@443:     }
tomas@443: 
tomas@443:     extern (C) void* gc_malloc( size_t sz, uint ba = 0 );
tomas@443:     extern (C) void* gc_calloc( size_t sz, uint ba = 0 );
tomas@443:     extern (C) void  gc_free( void* p );
tomas@443: }
tomas@443: 
tomas@443: 
tomas@443: /**********************************************
tomas@443:  * Reverse array of chars.
tomas@443:  * Handled separately because embedded multibyte encodings should not be
tomas@443:  * reversed.
tomas@443:  */
tomas@443: 
tomas@486: extern (C) char[] _adReverseChar(char[] a)
tomas@443: {
kamm@855:     bool hadErrors = false;
tomas@443:     if (a.length > 1)
tomas@443:     {
tomas@443:         char[6] tmp;
tomas@443:         char[6] tmplo;
tomas@443:         char* lo = a.ptr;
tomas@443:         char* hi = &a[length - 1];
tomas@443: 
tomas@443:         while (lo < hi)
tomas@443:         {   auto clo = *lo;
tomas@443:             auto chi = *hi;
tomas@443: 
tomas@443: 	    debug(adi) printf("lo = %d, hi = %d\n", lo, hi);
tomas@443:             if (clo <= 0x7F && chi <= 0x7F)
tomas@443:             {
tomas@443: 		debug(adi) printf("\tascii\n");
tomas@443:                 *lo = chi;
tomas@443:                 *hi = clo;
tomas@443:                 lo++;
tomas@443:                 hi--;
tomas@443:                 continue;
tomas@443:             }
tomas@443: 
tomas@443:             uint stridelo = UTF8stride[clo];
kamm@855:             if (stridelo > 6) { // invalid UTF-8 0xFF 
kamm@855:                 stridelo = 1; 
kamm@855:                 hadErrors=true;
kamm@855:             }
tomas@443: 
tomas@443:             uint stridehi = 1;
kamm@855:             while ((chi & 0xC0) == 0x80 && hi >= lo)
tomas@443:             {
tomas@443:                 chi = *--hi;
tomas@443:                 stridehi++;
tomas@443:             }
kamm@855:             if (lo >= hi) {
kamm@855:                 if (lo > hi) {
kamm@855:                     hadErrors = true;
kamm@855:                 }
tomas@443:                 break;
kamm@855:             }
kamm@855:             if (stridehi > 6) {
kamm@855:                 hadErrors = true;
kamm@855:                 stridehi = 6;
kamm@855:             }
tomas@443: 
tomas@443: 	    debug(adi) printf("\tstridelo = %d, stridehi = %d\n", stridelo, stridehi);
tomas@443:             if (stridelo == stridehi)
tomas@443:             {
tomas@443:                 memcpy(tmp.ptr, lo, stridelo);
tomas@443:                 memcpy(lo, hi, stridelo);
tomas@443:                 memcpy(hi, tmp.ptr, stridelo);
tomas@443:                 lo += stridelo;
tomas@443:                 hi--;
tomas@443:                 continue;
tomas@443:             }
tomas@443: 
tomas@443:             /* Shift the whole array. This is woefully inefficient
tomas@443:              */
tomas@443:             memcpy(tmp.ptr, hi, stridehi);
tomas@443:             memcpy(tmplo.ptr, lo, stridelo);
tomas@443:             memmove(lo + stridehi, lo + stridelo , cast(size_t)(hi - lo) - stridelo);
tomas@443:             memcpy(lo, tmp.ptr, stridehi);
tomas@443:             memcpy(hi + stridehi - stridelo, tmplo.ptr, stridelo);
tomas@443: 
tomas@443:             lo += stridehi;
tomas@443:             hi = hi - 1 + (stridehi - stridelo);
tomas@443:         }
tomas@443:     }
kamm@855:     if (hadErrors)
kamm@855:         throw new Exception("invalid UTF-8 sequence",__FILE__,__LINE__);
tomas@486:     return a;
tomas@443: }
tomas@443: 
tomas@443: unittest
tomas@443: {
tomas@486:     char[] a = "abcd"c;
tomas@443: 
tomas@486:     char[] r = a.dup.reverse;
tomas@443:     //writefln(r);
tomas@443:     assert(r == "dcba");
tomas@443: 
tomas@443:     a = "a\u1235\u1234c";
tomas@443:     //writefln(a);
tomas@443:     r = a.dup.reverse;
tomas@443:     //writefln(r);
tomas@443:     assert(r == "c\u1234\u1235a");
tomas@443: 
tomas@443:     a = "ab\u1234c";
tomas@443:     //writefln(a);
tomas@443:     r = a.dup.reverse;
tomas@443:     //writefln(r);
tomas@443:     assert(r == "c\u1234ba");
tomas@443: 
tomas@443:     a = "\u3026\u2021\u3061\n";
tomas@443:     r = a.dup.reverse;
tomas@443:     assert(r == "\n\u3061\u2021\u3026");
tomas@443: }
tomas@443: 
tomas@443: 
tomas@443: /**********************************************
tomas@443:  * Reverse array of wchars.
tomas@443:  * Handled separately because embedded multiword encodings should not be
tomas@443:  * reversed.
tomas@443:  */
tomas@443: 
tomas@486: extern (C) wchar[] _adReverseWchar(wchar[] a)
tomas@443: {
kamm@855:     bool hadErrors = false;
tomas@443:     if (a.length > 1)
tomas@443:     {
tomas@443:         wchar[2] tmp;
tomas@443:         wchar* lo = a.ptr;
tomas@443:         wchar* hi = &a[length - 1];
tomas@443: 
tomas@443:         while (lo < hi)
tomas@443:         {   auto clo = *lo;
tomas@443:             auto chi = *hi;
tomas@443: 
tomas@443:             if ((clo < 0xD800 || clo > 0xDFFF) &&
tomas@443:                 (chi < 0xD800 || chi > 0xDFFF))
tomas@443:             {
tomas@443:                 *lo = chi;
tomas@443:                 *hi = clo;
tomas@443:                 lo++;
tomas@443:                 hi--;
tomas@443:                 continue;
tomas@443:             }
tomas@443: 
tomas@443:             int stridelo = 1 + (clo >= 0xD800 && clo <= 0xDBFF);
tomas@443: 
tomas@443:             int stridehi = 1;
tomas@443:             if (chi >= 0xDC00 && chi <= 0xDFFF)
tomas@443:             {
tomas@443:                 chi = *--hi;
tomas@443:                 stridehi++;
tomas@443:             }
kamm@855:             if (lo >= hi) {
kamm@855:                 if (lo > hi) {
kamm@855:                     hadErrors = true;
kamm@855:                 }
tomas@443:                 break;
kamm@855:             }
tomas@443: 
tomas@443:             if (stridelo == stridehi)
tomas@443:             {   int stmp;
tomas@443: 
tomas@443:                 assert(stridelo == 2);
tomas@443:                 assert(stmp.sizeof == 2 * (*lo).sizeof);
tomas@443:                 stmp = *cast(int*)lo;
tomas@443:                 *cast(int*)lo = *cast(int*)hi;
tomas@443:                 *cast(int*)hi = stmp;
tomas@443:                 lo += stridelo;
tomas@443:                 hi--;
tomas@443:                 continue;
tomas@443:             }
tomas@443: 
tomas@443:             /* Shift the whole array. This is woefully inefficient
tomas@443:              */
tomas@443:             memcpy(tmp.ptr, hi, stridehi * wchar.sizeof);
tomas@443:             memcpy(hi + stridehi - stridelo, lo, stridelo * wchar.sizeof);
tomas@443:             memmove(lo + stridehi, lo + stridelo , (hi - (lo + stridelo)) * wchar.sizeof);
tomas@443:             memcpy(lo, tmp.ptr, stridehi * wchar.sizeof);
tomas@443: 
tomas@443:             lo += stridehi;
tomas@443:             hi = hi - 1 + (stridehi - stridelo);
tomas@443:         }
tomas@443:     }
kamm@855:     if (hadErrors)
kamm@855:         throw new Exception("invalid UTF-8 sequence",__FILE__,__LINE__);
tomas@486:     return a;
tomas@443: }
tomas@443: 
tomas@443: unittest
tomas@443: {
tomas@486:     wchar[] a = "abcd";
tomas@486:     wchar[] r;
tomas@443: 
tomas@443:     r = a.dup.reverse;
tomas@443:     assert(r == "dcba");
tomas@443: 
tomas@443:     a = "a\U00012356\U00012346c";
tomas@443:     r = a.dup.reverse;
tomas@443:     assert(r == "c\U00012346\U00012356a");
tomas@443: 
tomas@443:     a = "ab\U00012345c";
tomas@443:     r = a.dup.reverse;
tomas@443:     assert(r == "c\U00012345ba");
tomas@443: }
tomas@443: 
tomas@443: 
tomas@443: /**********************************************
tomas@443:  * Support for array.reverse property.
tomas@717:  * The actual type is painted on the return value by the frontend
tomas@717:  * Given and returned length are number of elements
tomas@443:  */
tomas@443: 
tomas@715: extern (C) void[] _adReverse(void[] a, size_t szelem)
tomas@443:     out (result)
tomas@443:     {
tomas@443:         assert(result.ptr is a.ptr);
tomas@443:     }
tomas@443:     body
tomas@443:     {
tomas@443:         if (a.length >= 2)
tomas@443:         {
tomas@443:             byte*    tmp;
tomas@443:             byte[16] buffer;
tomas@443: 
tomas@443:             void* lo = a.ptr;
tomas@443:             void* hi = a.ptr + (a.length - 1) * szelem;
tomas@443: 
tomas@443:             tmp = buffer.ptr;
tomas@443:             if (szelem > 16)
tomas@443:             {
tomas@443:                 //version (Win32)
tomas@443:                     //tmp = cast(byte*) alloca(szelem);
tomas@443:                 //else
tomas@443:                     tmp = cast(byte*) gc_malloc(szelem);
tomas@443:             }
tomas@443: 
tomas@443:             for (; lo < hi; lo += szelem, hi -= szelem)
tomas@443:             {
tomas@443:                 memcpy(tmp, lo,  szelem);
tomas@443:                 memcpy(lo,  hi,  szelem);
tomas@443:                 memcpy(hi,  tmp, szelem);
tomas@443:             }
tomas@443: 
tomas@443:             version (Win32)
tomas@443:             {
tomas@443:             }
tomas@443:             else
tomas@443:             {
tomas@443:                 //if (szelem > 16)
tomas@443:                     // BUG: bad code is generate for delete pointer, tries
tomas@443:                     // to call delclass.
tomas@443:                     //gc_free(tmp);
tomas@443:             }
tomas@443:         }
tomas@715:         return a.ptr[0 .. a.length];
tomas@443:     }
tomas@443: 
tomas@443: unittest
tomas@443: {
tomas@443:     debug(adi) printf("array.reverse.unittest\n");
tomas@443: 
tomas@443:     int[] a = new int[5];
tomas@443:     int[] b;
tomas@443:     size_t i;
tomas@443: 
tomas@443:     for (i = 0; i < 5; i++)
tomas@443:         a[i] = i;
tomas@443:     b = a.reverse;
tomas@443:     assert(b is a);
tomas@443:     for (i = 0; i < 5; i++)
tomas@443:         assert(a[i] == 4 - i);
tomas@443: 
tomas@443:     struct X20
tomas@443:     {   // More than 16 bytes in size
tomas@443:         int a;
tomas@443:         int b, c, d, e;
tomas@443:     }
tomas@443: 
tomas@443:     X20[] c = new X20[5];
tomas@443:     X20[] d;
tomas@443: 
tomas@443:     for (i = 0; i < 5; i++)
tomas@443:     {   c[i].a = i;
tomas@443:         c[i].e = 10;
tomas@443:     }
tomas@443:     d = c.reverse;
tomas@443:     assert(d is c);
tomas@443:     for (i = 0; i < 5; i++)
tomas@443:     {
tomas@443:         assert(c[i].a == 4 - i);
tomas@443:         assert(c[i].e == 10);
tomas@443:     }
tomas@443: }
tomas@443: 
tomas@443: /**********************************************
tomas@443:  * Sort array of chars.
tomas@443:  */
tomas@443: 
tomas@486: extern (C) char[] _adSortChar(char[] a)
tomas@443: {
tomas@443:     if (a.length > 1)
tomas@443:     {
tomas@443: 	dchar[] da = toUTF32(a);
tomas@443:         da.sort;
tomas@443:         size_t i = 0;
tomas@443:         foreach (dchar d; da)
tomas@443:         {   char[4] buf;
tomas@443:             auto t = toUTF8(buf, d);
tomas@443:             a[i .. i + t.length] = t[];
tomas@443:             i += t.length;
tomas@443:         }
tomas@443:         delete da;
tomas@443:     }
tomas@486:     return a;
tomas@443: }
tomas@443: 
tomas@443: /**********************************************
tomas@443:  * Sort array of wchars.
tomas@443:  */
tomas@443: 
tomas@486: extern (C) wchar[] _adSortWchar(wchar[] a)
tomas@443: {
tomas@443:     if (a.length > 1)
tomas@443:     {
tomas@443: 	dchar[] da = toUTF32(a);
tomas@443:         da.sort;
tomas@443:         size_t i = 0;
tomas@443:         foreach (dchar d; da)
tomas@443:         {   wchar[2] buf;
tomas@443: 	    auto t = toUTF16(buf, d);
tomas@443:             a[i .. i + t.length] = t[];
tomas@443:             i += t.length;
tomas@443:         }
tomas@443:         delete da;
tomas@443:     }
tomas@486:     return a;
tomas@443: }
tomas@443: 
tomas@443: /***************************************
tomas@443:  * Support for array equality test.
tomas@717:  * The actual type is painted on the return value by the frontend
tomas@717:  * Given lengths are number of elements
tomas@443:  */
tomas@443: 
tomas@715: extern (C) int _adEq(void[] a1, void[] a2, TypeInfo ti)
tomas@443: {
tomas@443:     debug(adi) printf("_adEq(a1.length = %d, a2.length = %d)\n", a1.length, a2.length);
tomas@443: 
tomas@443:     if (a1.length != a2.length)
tomas@443:         return 0;               // not equal
tomas@443:     else if (a1.ptr == a2.ptr)
tomas@443:         return 1;               // equal
tomas@443: 
tomas@443:     // let typeinfo decide
tomas@443:     return ti.equals(&a1, &a2);
tomas@443: }
tomas@443: 
tomas@443: unittest
tomas@443: {
tomas@443:     debug(adi) printf("array.Eq unittest\n");
tomas@443: 
tomas@486:     char[] a = "hello"c;
tomas@443: 
tomas@443:     assert(a != "hel");
tomas@443:     assert(a != "helloo");
tomas@443:     assert(a != "betty");
tomas@443:     assert(a == "hello");
tomas@443:     assert(a != "hxxxx");
tomas@443: }
tomas@443: 
tomas@443: /***************************************
tomas@443:  * Support for array compare test.
tomas@717:  * The actual type is painted on the return value by the frontend
tomas@717:  * Given lengths are number of elements
tomas@443:  */
tomas@443: 
tomas@715: extern (C) int _adCmp(void[] a1, void[] a2, TypeInfo ti)
tomas@443: {
tomas@443:     debug(adi) printf("adCmp()\n");
tomas@443: 
tomas@443:     if (a1.ptr == a2.ptr &&
tomas@443:         a1.length == a2.length)
tomas@443:         return 0;
tomas@443: 
tomas@443:     auto len = a1.length;
tomas@443:     if (a2.length < len)
tomas@443:         len = a2.length;
tomas@443: 
tomas@443:     // let typeinfo decide
tomas@443:     return ti.compare(&a1, &a2);
tomas@443: }
tomas@443: 
tomas@443: unittest
tomas@443: {
tomas@443:     debug(adi) printf("array.Cmp unittest\n");
tomas@443: 
tomas@486:     char[] a = "hello"c;
tomas@443: 
tomas@443:     assert(a >  "hel");
tomas@443:     assert(a >= "hel");
tomas@443:     assert(a <  "helloo");
tomas@443:     assert(a <= "helloo");
tomas@443:     assert(a >  "betty");
tomas@443:     assert(a >= "betty");
tomas@443:     assert(a == "hello");
tomas@443:     assert(a <= "hello");
tomas@443:     assert(a >= "hello");
tomas@443: }
tomas@443: 
tomas@443: /***************************************
tomas@443:  * Support for array compare test.
tomas@717:  * The actual type is painted on the return value by the frontend
tomas@717:  * Given lengths are number of elements
tomas@443:  */
tomas@443: 
tomas@715: extern (C) int _adCmpChar(void[] a1, void[] a2)
tomas@443: {
tomas@443:   version(D_InlineAsm_X86)
tomas@443:   {
tomas@443:   //version = Asm86;
tomas@443:   }
tomas@443:   version (Asm86)
tomas@443:   {
tomas@443:     asm
tomas@443:     {   naked                   ;
tomas@443: 
tomas@443:         push    EDI             ;
tomas@443:         push    ESI             ;
tomas@443: 
tomas@443:         mov    ESI,a1+4[4+ESP]  ;
tomas@443:         mov    EDI,a2+4[4+ESP]  ;
tomas@443: 
tomas@443:         mov    ECX,a1[4+ESP]    ;
tomas@443:         mov    EDX,a2[4+ESP]    ;
tomas@443: 
tomas@443:         cmp     ECX,EDX         ;
tomas@443:         jb      GotLength       ;
tomas@443: 
tomas@443:         mov     ECX,EDX         ;
tomas@443: 
tomas@443: GotLength:
tomas@443:         cmp    ECX,4            ;
tomas@443:         jb    DoBytes           ;
tomas@443: 
tomas@443:         // Do alignment if neither is dword aligned
tomas@443:         test    ESI,3           ;
tomas@443:         jz    Aligned           ;
tomas@443: 
tomas@443:         test    EDI,3           ;
tomas@443:         jz    Aligned           ;
tomas@443: DoAlign:
tomas@443:         mov    AL,[ESI]         ; //align ESI to dword bounds
tomas@443:         mov    DL,[EDI]         ;
tomas@443: 
tomas@443:         cmp    AL,DL            ;
tomas@443:         jnz    Unequal          ;
tomas@443: 
tomas@443:         inc    ESI              ;
tomas@443:         inc    EDI              ;
tomas@443: 
tomas@443:         test    ESI,3           ;
tomas@443: 
tomas@443:         lea    ECX,[ECX-1]      ;
tomas@443:         jnz    DoAlign          ;
tomas@443: Aligned:
tomas@443:         mov    EAX,ECX          ;
tomas@443: 
tomas@443:         // do multiple of 4 bytes at a time
tomas@443: 
tomas@443:         shr    ECX,2            ;
tomas@443:         jz    TryOdd            ;
tomas@443: 
tomas@443:         repe                    ;
tomas@443:         cmpsd                   ;
tomas@443: 
tomas@443:         jnz    UnequalQuad      ;
tomas@443: 
tomas@443: TryOdd:
tomas@443:         mov    ECX,EAX          ;
tomas@443: DoBytes:
tomas@443:         // if still equal and not end of string, do up to 3 bytes slightly
tomas@443:         // slower.
tomas@443: 
tomas@443:         and    ECX,3            ;
tomas@443:         jz    Equal             ;
tomas@443: 
tomas@443:         repe                    ;
tomas@443:         cmpsb                   ;
tomas@443: 
tomas@443:         jnz    Unequal          ;
tomas@443: Equal:
tomas@443:         mov    EAX,a1[4+ESP]    ;
tomas@443:         mov    EDX,a2[4+ESP]    ;
tomas@443: 
tomas@443:         sub    EAX,EDX          ;
tomas@443:         pop    ESI              ;
tomas@443: 
tomas@443:         pop    EDI              ;
tomas@443:         ret                     ;
tomas@443: 
tomas@443: UnequalQuad:
tomas@443:         mov    EDX,[EDI-4]      ;
tomas@443:         mov    EAX,[ESI-4]      ;
tomas@443: 
tomas@443:         cmp    AL,DL            ;
tomas@443:         jnz    Unequal          ;
tomas@443: 
tomas@443:         cmp    AH,DH            ;
tomas@443:         jnz    Unequal          ;
tomas@443: 
tomas@443:         shr    EAX,16           ;
tomas@443: 
tomas@443:         shr    EDX,16           ;
tomas@443: 
tomas@443:         cmp    AL,DL            ;
tomas@443:         jnz    Unequal          ;
tomas@443: 
tomas@443:         cmp    AH,DH            ;
tomas@443: Unequal:
tomas@443:         sbb    EAX,EAX          ;
tomas@443:         pop    ESI              ;
tomas@443: 
tomas@443:         or     EAX,1            ;
tomas@443:         pop    EDI              ;
tomas@443: 
tomas@443:         ret                     ;
tomas@443:     }
tomas@443:   }
tomas@443:   else
tomas@443:   {
tomas@443:     int len;
tomas@443:     int c;
tomas@443: 
tomas@443:     debug(adi) printf("adCmpChar()\n");
tomas@443:     len = cast(int)a1.length;
tomas@443:     if (a2.length < len)
tomas@443:         len = cast(int)a2.length;
tomas@443:     c = memcmp(cast(char *)a1.ptr, cast(char *)a2.ptr, len);
tomas@443:     if (!c)
tomas@443:         c = cast(int)a1.length - cast(int)a2.length;
tomas@443:     return c;
tomas@443:   }
tomas@443: }
tomas@443: 
tomas@443: unittest
tomas@443: {
tomas@443:     debug(adi) printf("array.CmpChar unittest\n");
tomas@443: 
tomas@486:     char[] a = "hello"c;
tomas@443: 
tomas@443:     assert(a >  "hel");
tomas@443:     assert(a >= "hel");
tomas@443:     assert(a <  "helloo");
tomas@443:     assert(a <= "helloo");
tomas@443:     assert(a >  "betty");
tomas@443:     assert(a >= "betty");
tomas@443:     assert(a == "hello");
tomas@443:     assert(a <= "hello");
tomas@443:     assert(a >= "hello");
tomas@443: }