src/compiler/dmd/adi.d

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