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
 232     auto r = a.dup.reverse;
 233     assert(r == "dcba");
 234
 235     a = "a\U00012356\U00012346c";
 236     r = a.dup.reverse;
 237     assert(r == "c\U00012346\U00012356a");
 238
 239     a = "ab\U00012345c";
 240     r = a.dup.reverse;
 241     assert(r == "c\U00012345ba");
 242 }
 243
 244
 245 /**********************************************
 246  * Support for array.reverse property.
 247  */
 248
 249 extern (C) long _adReverse(Array a, size_t szelem)
 250     out (result)
 251     {
 252         assert(result is *cast(long*)(&a));
 253     }
 254     body
 255     {
 256         if (a.length >= 2)
 257         {
 258             byte*    tmp;
 259             byte[16] buffer;
 260
 261             void* lo = a.ptr;
 262             void* hi = a.ptr + (a.length - 1) * szelem;
 263
 264             tmp = buffer.ptr;
 265             if (szelem > 16)
 266             {
 267                 //version (Windows)
 268                     tmp = cast(byte*) alloca(szelem);
 269                 //else
 270                     //tmp = gc_malloc(szelem);
 271             }
 272
 273             for (; lo < hi; lo += szelem, hi -= szelem)
 274             {
 275                 memcpy(tmp, lo,  szelem);
 276                 memcpy(lo,  hi,  szelem);
 277                 memcpy(hi,  tmp, szelem);
 278             }
 279
 280             version (Windows)
 281             {
 282             }
 283             else
 284             {
 285                 //if (szelem > 16)
 286                     // BUG: bad code is generate for delete pointer, tries
 287                     // to call delclass.
 288                     //gc_free(tmp);
 289             }
 290         }
 291         return *cast(long*)(&a);
 292     }
 293
 294 unittest
 295 {
 296     debug(adi) printf("array.reverse.unittest\n");
 297
 298     int[] a = new int[5];
 299     int[] b;
 300     size_t i;
 301
 302     for (i = 0; i < 5; i++)
 303         a[i] = i;
 304     b = a.reverse;
 305     assert(b is a);
 306     for (i = 0; i < 5; i++)
 307         assert(a[i] == 4 - i);
 308
 309     struct X20
 310     {   // More than 16 bytes in size
 311         int a;
 312         int b, c, d, e;
 313     }
 314
 315     X20[] c = new X20[5];
 316     X20[] d;
 317
 318     for (i = 0; i < 5; i++)
 319     {   c[i].a = i;
 320         c[i].e = 10;
 321     }
 322     d = c.reverse;
 323     assert(d is c);
 324     for (i = 0; i < 5; i++)
 325     {
 326         assert(c[i].a == 4 - i);
 327         assert(c[i].e == 10);
 328     }
 329 }
 330
 331 /**********************************************
 332  * Sort array of chars.
 333  */
 334
 335 extern (C) long _adSortChar(char[] a)
 336 {
 337     if (a.length > 1)
 338     {
 339         dstring da = toUTF32(a);
 340         da.sort;
 341         size_t i = 0;
 342         foreach (dchar d; da)
 343         {   char[4] buf;
 344             auto t = toUTF8(buf, d);
 345             a[i .. i + t.length] = t[];
 346             i += t.length;
 347         }
 348         delete da;
 349     }
 350     return *cast(long*)(&a);
 351 }
 352
 353 /**********************************************
 354  * Sort array of wchars.
 355  */
 356
 357 extern (C) long _adSortWchar(wchar[] a)
 358 {
 359     if (a.length > 1)
 360     {
 361         dstring da = toUTF32(a);
 362         da.sort;
 363         size_t i = 0;
 364         foreach (dchar d; da)
 365         {   wchar[2] buf;
 366             auto t = toUTF16(buf, d);
 367             a[i .. i + t.length] = t[];
 368             i += t.length;
 369         }
 370         delete da;
 371     }
 372     return *cast(long*)(&a);
 373 }
 374
 375 /***************************************
 376  * Support for array equality test.
 377  * Returns:
 378  *      1       equal
 379  *      0       not equal
 380  */
 381
 382 extern (C) int _adEq(Array a1, Array a2, TypeInfo ti)
 383 {
 384     debug(adi) printf("_adEq(a1.length = %d, a2.length = %d)\n", a1.length, a2.length);
 385     if (a1.length != a2.length)
 386         return 0; // not equal
 387     auto sz = ti.tsize();
 388     auto p1 = a1.ptr;
 389     auto p2 = a2.ptr;
 390
 391     if (sz == 1)
 392         // We should really have a ti.isPOD() check for this
 393         return (memcmp(p1, p2, a1.length) == 0);
 394
 395     for (size_t i = 0; i < a1.length; i++)
 396     {
 397         if (!ti.equals(p1 + i * sz, p2 + i * sz))
 398             return 0; // not equal
 399     }
 400     return 1; // equal
 401 }
 402
 403 extern (C) int _adEq2(Array a1, Array a2, TypeInfo ti)
 404 {
 405     debug(adi) printf("_adEq2(a1.length = %d, a2.length = %d)\n", a1.length, a2.length);
 406     if (a1.length != a2.length)
 407         return 0;               // not equal
 408     if (!ti.equals(&a1, &a2))
 409         return 0;
 410     return 1;
 411 }
 412 unittest
 413 {
 414     debug(adi) printf("array.Eq unittest\n");
 415
 416     auto a = "hello"c;
 417
 418     assert(a != "hel");
 419     assert(a != "helloo");
 420     assert(a != "betty");
 421     assert(a == "hello");
 422     assert(a != "hxxxx");
 423 }
 424
 425 /***************************************
 426  * Support for array compare test.
 427  */
 428
 429 extern (C) int _adCmp(Array a1, Array a2, TypeInfo ti)
 430 {
 431     debug(adi) printf("adCmp()\n");
 432     auto len = a1.length;
 433     if (a2.length < len)
 434         len = a2.length;
 435     auto sz = ti.tsize();
 436     void *p1 = a1.ptr;
 437     void *p2 = a2.ptr;
 438
 439     if (sz == 1)
 440     {   // We should really have a ti.isPOD() check for this
 441         auto c = memcmp(p1, p2, len);
 442         if (c)
 443             return c;
 444     }
 445     else
 446     {
 447         for (size_t i = 0; i < len; i++)
 448         {
 449             auto c = ti.compare(p1 + i * sz, p2 + i * sz);
 450             if (c)
 451                 return c;
 452         }
 453     }
 454     if (a1.length == a2.length)
 455         return 0;
 456     return (a1.length > a2.length) ? 1 : -1;
 457 }
 458
 459 extern (C) int _adCmp2(Array a1, Array a2, TypeInfo ti)
 460 {
 461     debug(adi) printf("_adCmp2(a1.length = %d, a2.length = %d)\n", a1.length, a2.length);
 462     return ti.compare(&a1, &a2);
 463 }
 464 unittest
 465 {
 466     debug(adi) printf("array.Cmp unittest\n");
 467
 468     auto a = "hello"c;
 469
 470     assert(a >  "hel");
 471     assert(a >= "hel");
 472     assert(a <  "helloo");
 473     assert(a <= "helloo");
 474     assert(a >  "betty");
 475     assert(a >= "betty");
 476     assert(a == "hello");
 477     assert(a <= "hello");
 478     assert(a >= "hello");
 479 }
 480
 481 /***************************************
 482  * Support for array compare test.
 483  */
 484
 485 extern (C) int _adCmpChar(Array a1, Array a2)
 486 {
 487   version (X86)
 488   {
 489     asm
 490     {   naked                   ;
 491
 492         push    EDI             ;
 493         push    ESI             ;
 494
 495         mov    ESI,a1+4[4+ESP]  ;
 496         mov    EDI,a2+4[4+ESP]  ;
 497
 498         mov    ECX,a1[4+ESP]    ;
 499         mov    EDX,a2[4+ESP]    ;
 500
 501         cmp     ECX,EDX         ;
 502         jb      GotLength       ;
 503
 504         mov     ECX,EDX         ;
 505
 506 GotLength:
 507         cmp    ECX,4            ;
 508         jb    DoBytes           ;
 509
 510         // Do alignment if neither is dword aligned
 511         test    ESI,3           ;
 512         jz    Aligned           ;
 513
 514         test    EDI,3           ;
 515         jz    Aligned           ;
 516 DoAlign:
 517         mov    AL,[ESI]         ; //align ESI to dword bounds
 518         mov    DL,[EDI]         ;
 519
 520         cmp    AL,DL            ;
 521         jnz    Unequal          ;
 522
 523         inc    ESI              ;
 524         inc    EDI              ;
 525
 526         test    ESI,3           ;
 527
 528         lea    ECX,[ECX-1]      ;
 529         jnz    DoAlign          ;
 530 Aligned:
 531         mov    EAX,ECX          ;
 532
 533         // do multiple of 4 bytes at a time
 534
 535         shr    ECX,2            ;
 536         jz    TryOdd            ;
 537
 538         repe                    ;
 539         cmpsd                   ;
 540
 541         jnz    UnequalQuad      ;
 542
 543 TryOdd:
 544         mov    ECX,EAX          ;
 545 DoBytes:
 546         // if still equal and not end of string, do up to 3 bytes slightly
 547         // slower.
 548
 549         and    ECX,3            ;
 550         jz    Equal             ;
 551
 552         repe                    ;
 553         cmpsb                   ;
 554
 555         jnz    Unequal          ;
 556 Equal:
 557         mov    EAX,a1[4+ESP]    ;
 558         mov    EDX,a2[4+ESP]    ;
 559
 560         sub    EAX,EDX          ;
 561         pop    ESI              ;
 562
 563         pop    EDI              ;
 564         ret                     ;
 565
 566 UnequalQuad:
 567         mov    EDX,[EDI-4]      ;
 568         mov    EAX,[ESI-4]      ;
 569
 570         cmp    AL,DL            ;
 571         jnz    Unequal          ;
 572
 573         cmp    AH,DH            ;
 574         jnz    Unequal          ;
 575
 576         shr    EAX,16           ;
 577
 578         shr    EDX,16           ;
 579
 580         cmp    AL,DL            ;
 581         jnz    Unequal          ;
 582
 583         cmp    AH,DH            ;
 584 Unequal:
 585         sbb    EAX,EAX          ;
 586         pop    ESI              ;
 587
 588         or     EAX,1            ;
 589         pop    EDI              ;
 590
 591         ret                     ;
 592     }
 593   }
 594   else
 595   {
 596     int len;
 597     int c;
 598
 599     debug(adi) printf("adCmpChar()\n");
 600     len = a1.length;
 601     if (a2.length < len)
 602         len = a2.length;
 603     c = memcmp(cast(char *)a1.ptr, cast(char *)a2.ptr, len);
 604     if (!c)
 605         c = cast(int)a1.length - cast(int)a2.length;
 606     return c;
 607   }
 608 }
 609
 610 unittest
 611 {
 612     debug(adi) printf("array.CmpChar unittest\n");
 613
 614     auto a = "hello"c;
 615
 616     assert(a >  "hel");
 617     assert(a >= "hel");
 618     assert(a <  "helloo");
 619     assert(a <= "helloo");
 620     assert(a >  "betty");
 621     assert(a >= "betty");
 622     assert(a == "hello");
 623     assert(a <= "hello");
 624     assert(a >= "hello");
 625 }