grab from latest android

git-svn-id: http://skia.googlecode.com/svn/trunk@27 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 574 insertions, 0 deletions

diff --git a/src/core/SkUtils.cpp b/src/core/SkUtils.cpp
new file mode 100644
index 0000000000..4f5ba6eaf8
--- /dev/null
+++ b/src/core/SkUtils.cpp
@@ -0,0 +1,574 @@
+/* libs/graphics/sgl/SkUtils.cpp
+**
+** Copyright 2006, The Android Open Source Project
+**
+** Licensed under the Apache License, Version 2.0 (the "License"); 
+** you may not use this file except in compliance with the License. 
+** You may obtain a copy of the License at 
+**
+**     http://www.apache.org/licenses/LICENSE-2.0 
+**
+** Unless required by applicable law or agreed to in writing, software 
+** distributed under the License is distributed on an "AS IS" BASIS, 
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
+** See the License for the specific language governing permissions and 
+** limitations under the License.
+*/
+
+#include "SkUtils.h"
+
+#if 0
+#define assign_16_longs(dst, value)             \
+    do {                                        \
+        (dst)[0] = value;   (dst)[1] = value;   \
+        (dst)[2] = value;   (dst)[3] = value;   \
+        (dst)[4] = value;   (dst)[5] = value;   \
+        (dst)[6] = value;   (dst)[7] = value;   \
+        (dst)[8] = value;   (dst)[9] = value;   \
+        (dst)[10] = value;  (dst)[11] = value;  \
+        (dst)[12] = value;  (dst)[13] = value;  \
+        (dst)[14] = value;  (dst)[15] = value;  \
+    } while (0)
+#else
+#define assign_16_longs(dst, value)             \
+    do {                                        \
+        *(dst)++ = value;   *(dst)++ = value;   \
+        *(dst)++ = value;   *(dst)++ = value;   \
+        *(dst)++ = value;   *(dst)++ = value;   \
+        *(dst)++ = value;   *(dst)++ = value;   \
+        *(dst)++ = value;   *(dst)++ = value;   \
+        *(dst)++ = value;   *(dst)++ = value;   \
+        *(dst)++ = value;   *(dst)++ = value;   \
+        *(dst)++ = value;   *(dst)++ = value;   \
+    } while (0)
+#endif
+
+///////////////////////////////////////////////////////////////////////////
+
+void sk_memset16_portable(uint16_t dst[], uint16_t value, int count)
+{
+    SkASSERT(dst != NULL && count >= 0);
+
+    if (count <= 0)
+        return;
+
+    // not sure if this helps to short-circuit on small values of count
+    if (count < 8)
+    {
+        do {
+            *dst++ = (uint16_t)value;
+        } while (--count != 0);
+        return;
+    }
+
+    // ensure we're on a long boundary
+    if ((size_t)dst & 2)
+    {
+        *dst++ = (uint16_t)value;
+        count -= 1;
+    }
+
+    uint32_t value32 = ((uint32_t)value << 16) | value;
+
+    // handle the bulk with our unrolled macro
+    {
+        int sixteenlongs = count >> 5;
+        if (sixteenlongs)
+        {
+            uint32_t* dst32 = (uint32_t*)dst;
+            do {
+                assign_16_longs(dst32, value32);
+            } while (--sixteenlongs != 0);
+            dst = (uint16_t*)dst32;
+            count &= 31;
+        }
+    }
+
+    // handle (most) of the rest
+    {
+        int longs = count >> 1;
+        if (longs)
+        {
+            do {
+                *(uint32_t*)dst = value32;
+                dst += 2;
+            } while (--longs != 0);
+        }
+    }
+
+    // cleanup a possible trailing short
+    if (count & 1)
+        *dst = (uint16_t)value;
+}
+
+void sk_memset32_portable(uint32_t dst[], uint32_t value, int count)
+{
+    SkASSERT(dst != NULL && count >= 0);
+
+    {
+        int sixteenlongs = count >> 4;
+        if (sixteenlongs)
+        {
+            do {
+                assign_16_longs(dst, value);
+            } while (--sixteenlongs != 0);
+            count &= 15;
+        }
+    }
+
+    if (count)
+    {
+        do {
+            *dst++ = value;
+        } while (--count != 0);
+    }
+}
+
+//////////////////////////////////////////////////////////////////////////////
+
+/*  0xxxxxxx    1 total
+    10xxxxxx    // never a leading byte
+    110xxxxx    2 total
+    1110xxxx    3 total
+    11110xxx    4 total
+
+    11 10 01 01 xx xx xx xx 0...
+    0xE5XX0000
+    0xE5 << 24
+*/
+
+#ifdef SK_DEBUG
+    static void assert_utf8_leadingbyte(unsigned c)
+    {
+        SkASSERT(c <= 0xF7);    // otherwise leading byte is too big (more than 4 bytes)
+        SkASSERT((c & 0xC0) != 0x80);   // can't begin with a middle char
+    }
+
+    int SkUTF8_LeadByteToCount(unsigned c)
+    {
+        assert_utf8_leadingbyte(c);
+        return (((0xE5 << 24) >> (c >> 4 << 1)) & 3) + 1;
+    }
+#else
+    #define assert_utf8_leadingbyte(c)
+#endif
+
+int SkUTF8_CountUnichars(const char utf8[])
+{
+    SkASSERT(utf8);
+
+    int count = 0;
+
+    for (;;)
+    {
+        int c = *(const uint8_t*)utf8;
+        if (c == 0)
+            break;
+
+        utf8 += SkUTF8_LeadByteToCount(c);
+        count += 1;
+    }
+    return count;
+}
+
+int SkUTF8_CountUnichars(const char utf8[], size_t byteLength)
+{
+    SkASSERT(NULL != utf8 || 0 == byteLength);
+
+    int         count = 0;
+    const char* stop = utf8 + byteLength;
+
+    while (utf8 < stop)
+    {
+        utf8 += SkUTF8_LeadByteToCount(*(const uint8_t*)utf8);
+        count += 1;
+    }
+    return count;
+}
+
+SkUnichar SkUTF8_ToUnichar(const char utf8[])
+{
+    SkASSERT(NULL != utf8);
+
+    const uint8_t*  p = (const uint8_t*)utf8;
+    int             c = *p;
+    int             hic = c << 24;
+
+    assert_utf8_leadingbyte(c);
+
+    if (hic < 0)
+    {
+        uint32_t mask = (uint32_t)~0x3F;
+        hic <<= 1;
+        do {
+            c = (c << 6) | (*++p & 0x3F);
+            mask <<= 5;
+        } while ((hic <<= 1) < 0);
+        c &= ~mask;
+    }
+    return c;
+}
+
+SkUnichar SkUTF8_NextUnichar(const char** ptr)
+{
+    SkASSERT(NULL != ptr && NULL != *ptr);
+
+    const uint8_t*  p = (const uint8_t*)*ptr;
+    int             c = *p;
+    int             hic = c << 24;
+    
+    assert_utf8_leadingbyte(c);
+
+    if (hic < 0)
+    {
+        uint32_t mask = (uint32_t)~0x3F;
+        hic <<= 1;
+        do {
+            c = (c << 6) | (*++p & 0x3F);
+            mask <<= 5;
+        } while ((hic <<= 1) < 0);
+        c &= ~mask;
+    }
+    *ptr = (char*)p + 1;
+    return c;
+}
+
+SkUnichar SkUTF8_PrevUnichar(const char** ptr)
+{
+    SkASSERT(NULL != ptr && NULL != *ptr);
+
+    const char* p = *ptr;
+    
+    if (*--p & 0x80)
+        while (*--p & 0x40)
+            ;
+
+    *ptr = (char*)p;
+    return SkUTF8_NextUnichar(&p);
+}
+
+size_t SkUTF8_FromUnichar(SkUnichar uni, char utf8[])
+{
+    if ((uint32_t)uni > 0x10FFFF)
+    {
+        SkASSERT(!"bad unichar");
+        return 0;
+    }
+
+    if (uni <= 127)
+    {
+        if (utf8)
+            *utf8 = (char)uni;
+        return 1;
+    }
+
+    char    tmp[4];
+    char*   p = tmp;
+    size_t  count = 1;
+
+    SkDEBUGCODE(SkUnichar orig = uni;)
+
+    while (uni > 0x3F)
+    {
+        *p++ = (char)(0x80 | (uni & 0x3F));
+        uni >>= 6;
+        count += 1;
+    }
+
+    if (utf8)
+    {
+        p = tmp;
+        utf8 += count;
+        while (p < tmp + count - 1)
+            *--utf8 = *p++;
+        *--utf8 = (char)(~(0xFF >> count) | uni);
+    }
+
+    SkASSERT(utf8 == NULL || orig == SkUTF8_ToUnichar(utf8));
+    return count;
+}
+
+////////////////////////////////////////////////////////////////////////////////////
+
+int SkUTF16_CountUnichars(const uint16_t src[])
+{
+    SkASSERT(src);
+
+    int count = 0;
+    unsigned c;
+    while ((c = *src++) != 0)
+    {
+        SkASSERT(!SkUTF16_IsLowSurrogate(c));
+        if (SkUTF16_IsHighSurrogate(c))
+        {
+            c = *src++;
+            SkASSERT(SkUTF16_IsLowSurrogate(c));
+        }
+        count += 1;
+    }
+    return count;
+}
+
+int SkUTF16_CountUnichars(const uint16_t src[], int numberOf16BitValues)
+{
+    SkASSERT(src);
+
+    const uint16_t* stop = src + numberOf16BitValues;
+    int count = 0;
+    while (src < stop)
+    {
+        unsigned c = *src++;
+        SkASSERT(!SkUTF16_IsLowSurrogate(c));
+        if (SkUTF16_IsHighSurrogate(c))
+        {
+            SkASSERT(src < stop);
+            c = *src++;
+            SkASSERT(SkUTF16_IsLowSurrogate(c));
+        }
+        count += 1;
+    }
+    return count;
+}
+
+SkUnichar SkUTF16_NextUnichar(const uint16_t** srcPtr)
+{
+    SkASSERT(srcPtr && *srcPtr);
+    
+    const uint16_t* src = *srcPtr;
+    SkUnichar       c = *src++;
+    
+    SkASSERT(!SkUTF16_IsLowSurrogate(c));
+    if (SkUTF16_IsHighSurrogate(c))
+    {
+        unsigned c2 = *src++;
+        SkASSERT(SkUTF16_IsLowSurrogate(c2));
+        
+        // c = ((c & 0x3FF) << 10) + (c2 & 0x3FF) + 0x10000
+        // c = (((c & 0x3FF) + 64) << 10) + (c2 & 0x3FF)
+        c = (c << 10) + c2 + (0x10000 - (0xD800 << 10) - 0xDC00);
+    }
+    *srcPtr = src;
+    return c;
+}
+
+SkUnichar SkUTF16_PrevUnichar(const uint16_t** srcPtr)
+{
+    SkASSERT(srcPtr && *srcPtr);
+    
+    const uint16_t* src = *srcPtr;
+    SkUnichar       c = *--src;
+    
+    SkASSERT(!SkUTF16_IsHighSurrogate(c));
+    if (SkUTF16_IsLowSurrogate(c))
+    {
+        unsigned c2 = *--src;
+        SkASSERT(SkUTF16_IsHighSurrogate(c2));
+        c = (c2 << 10) + c + (0x10000 - (0xD800 << 10) - 0xDC00);
+    }
+    *srcPtr = src;
+    return c;
+}
+
+size_t SkUTF16_FromUnichar(SkUnichar uni, uint16_t dst[])
+{
+    SkASSERT((unsigned)uni <= 0x10FFFF);
+
+    int extra = (uni > 0xFFFF);
+
+    if (dst)
+    {
+        if (extra)
+        {
+            // dst[0] = SkToU16(0xD800 | ((uni - 0x10000) >> 10));
+            // dst[0] = SkToU16(0xD800 | ((uni >> 10) - 64));
+            dst[0] = SkToU16((0xD800 - 64) + (uni >> 10));
+            dst[1] = SkToU16(0xDC00 | (uni & 0x3FF));
+            
+            SkASSERT(SkUTF16_IsHighSurrogate(dst[0]));
+            SkASSERT(SkUTF16_IsLowSurrogate(dst[1]));
+        }
+        else
+        {
+            dst[0] = SkToU16(uni);
+            SkASSERT(!SkUTF16_IsHighSurrogate(dst[0]));
+            SkASSERT(!SkUTF16_IsLowSurrogate(dst[0]));
+        }
+    }
+    return 1 + extra;
+}
+
+size_t SkUTF16_ToUTF8(const uint16_t utf16[], int numberOf16BitValues, char utf8[])
+{
+    SkASSERT(numberOf16BitValues >= 0);
+    if (numberOf16BitValues <= 0)
+        return 0;
+
+    SkASSERT(utf16 != NULL);
+    
+    const uint16_t* stop = utf16 + numberOf16BitValues;
+    size_t          size = 0;
+    
+    if (utf8 == NULL)    // just count
+    {
+        while (utf16 < stop)
+            size += SkUTF8_FromUnichar(SkUTF16_NextUnichar(&utf16), NULL);
+    }
+    else
+    {
+        char* start = utf8;
+        while (utf16 < stop)
+            utf8 += SkUTF8_FromUnichar(SkUTF16_NextUnichar(&utf16), utf8);
+        size = utf8 - start;
+    }
+    return size;
+}
+
+////////////////////////////////////////////////////////////////////////////////////
+
+#include <stdlib.h>
+
+static int round_to_K(size_t bytes)
+{
+    return (bytes + 512) >> 10;
+}
+
+SkAutoMemoryUsageProbe::SkAutoMemoryUsageProbe(const char label[])
+    : fLabel(label)
+{
+#if 0
+    struct mallinfo mi = mallinfo();
+
+    fBytesAllocated = mi.uordblks;
+#endif
+}
+
+SkAutoMemoryUsageProbe::~SkAutoMemoryUsageProbe()
+{
+#if 0
+    struct mallinfo mi = mallinfo();
+
+    printf("SkAutoMemoryUsageProbe ");
+    if (fLabel)
+        printf("<%s> ", fLabel);
+    printf("delta %dK, current total allocated %dK\n",
+            round_to_K(mi.uordblks - fBytesAllocated),
+            round_to_K(mi.uordblks));
+#endif
+}
+
+////////////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_DEBUG
+
+#include "SkRandom.h"
+#include "SkTSearch.h"
+#include "SkTSort.h"
+
+#define kSEARCH_COUNT   91
+
+#ifdef SK_SUPPORT_UNITTEST
+static void test_search()
+{
+    int         i, array[kSEARCH_COUNT];
+    SkRandom    rand;
+
+    for (i = 0; i < kSEARCH_COUNT; i++)
+        array[i] = rand.nextS();
+
+    SkTHeapSort<int>(array, kSEARCH_COUNT);
+    // make sure we got sorted properly
+    for (i = 1; i < kSEARCH_COUNT; i++)
+        SkASSERT(array[i-1] <= array[i]);
+
+    // make sure we can find all of our values
+    for (i = 0; i < kSEARCH_COUNT; i++)
+    {
+        int index = SkTSearch<int>(array, kSEARCH_COUNT, array[i], sizeof(int));
+        SkASSERT(index == i);
+    }
+
+    // make sure that random values are either found, or the correct
+    // insertion index is returned
+    for (i = 0; i < 10000; i++)
+    {
+        int value = rand.nextS();
+        int index = SkTSearch<int>(array, kSEARCH_COUNT, value, sizeof(int));
+
+        if (index >= 0)
+            SkASSERT(index < kSEARCH_COUNT && array[index] == value);
+        else
+        {
+            index = ~index;
+            SkASSERT(index <= kSEARCH_COUNT);
+            if (index < kSEARCH_COUNT)
+            {
+                SkASSERT(value < array[index]);
+                if (index > 0)
+                    SkASSERT(value > array[index - 1]);
+            }
+            else    // we should append the new value
+            {
+                SkASSERT(value > array[kSEARCH_COUNT - 1]);
+            }
+        }
+    }
+}
+
+static void test_utf16()
+{
+    static const SkUnichar gUni[] = {
+        0x10000, 0x18080, 0x20202, 0xFFFFF, 0x101234
+    };
+    
+    uint16_t buf[2];
+    
+    for (unsigned i = 0; i < SK_ARRAY_COUNT(gUni); i++)
+    {
+        size_t count = SkUTF16_FromUnichar(gUni[i], buf);
+        SkASSERT(count == 2);
+        size_t count2 = SkUTF16_CountUnichars(buf, 2);
+        SkASSERT(count2 == 1);
+        const uint16_t* ptr = buf;
+        SkUnichar c = SkUTF16_NextUnichar(&ptr);
+        SkASSERT(c == gUni[i]);
+        SkASSERT(ptr - buf == 2);
+    }
+}
+
+#endif
+
+void SkUtils::UnitTest()
+{
+#ifdef SK_SUPPORT_UNITTEST
+    static const struct {
+        const char* fUtf8;
+        SkUnichar   fUni;
+    } gTest[] = {
+        { "a",                  'a' },
+        { "\xC3\x83",           (3 << 6) | 3    },
+        { "\xE3\x83\x83",       (3 << 12) | (3 << 6) | 3    },
+        { "\xF3\x83\x83\x83",   (3 << 18) | (3 << 12) | (3 << 6) | 3    }
+    };
+
+    for (unsigned i = 0; i < SK_ARRAY_COUNT(gTest); i++)
+    {
+        const char* p = gTest[i].fUtf8;
+        int         n = SkUTF8_CountUnichars(p);
+        SkUnichar   u0 = SkUTF8_ToUnichar(gTest[i].fUtf8);
+        SkUnichar   u1 = SkUTF8_NextUnichar(&p);
+
+        SkASSERT(n == 1);
+        SkASSERT(u0 == u1);
+        SkASSERT(u0 == gTest[i].fUni);
+        SkASSERT(p - gTest[i].fUtf8 == (int)strlen(gTest[i].fUtf8));
+    }
+    
+    test_utf16();
+
+    test_search();
+#endif
+}
+
+#endif
+
+