← Back to branch summary

~ubuntu-branches/ubuntu/karmic/gears/karmic

« back to all changes in this revision

Viewing changes to third_party/skia/src/core/SkUtils.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Stefan Lesicnik
  • Date: 2009-04-30 19:15:25 UTC
  • Revision ID: james.westby@ubuntu.com-20090430191525-0790sb5wzg8ou0xb
Tags: upstream-0.5.21.0~svn3334+dfsg
Import upstream version 0.5.21.0~svn3334+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
third_party/skia/src/core/SkUtils.cpp
 
1
/* libs/graphics/sgl/SkUtils.cpp
 
2
**
 
3
** Copyright 2006, The Android Open Source Project
 
4
**
 
5
** Licensed under the Apache License, Version 2.0 (the "License"); 
 
6
** you may not use this file except in compliance with the License. 
 
7
** You may obtain a copy of the License at 
 
8
**
 
9
**     http://www.apache.org/licenses/LICENSE-2.0 
 
10
**
 
11
** Unless required by applicable law or agreed to in writing, software 
 
12
** distributed under the License is distributed on an "AS IS" BASIS, 
 
13
** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
 
14
** See the License for the specific language governing permissions and 
 
15
** limitations under the License.
 
16
*/
 
17
 
 
18
#include "SkUtils.h"
 
19
 
 
20
#if 0
 
21
#define assign_16_longs(dst, value)             \
 
22
    do {                                        \
 
23
        (dst)[0] = value;   (dst)[1] = value;   \
 
24
        (dst)[2] = value;   (dst)[3] = value;   \
 
25
        (dst)[4] = value;   (dst)[5] = value;   \
 
26
        (dst)[6] = value;   (dst)[7] = value;   \
 
27
        (dst)[8] = value;   (dst)[9] = value;   \
 
28
        (dst)[10] = value;  (dst)[11] = value;  \
 
29
        (dst)[12] = value;  (dst)[13] = value;  \
 
30
        (dst)[14] = value;  (dst)[15] = value;  \
 
31
    } while (0)
 
32
#else
 
33
#define assign_16_longs(dst, value)             \
 
34
    do {                                        \
 
35
        *(dst)++ = value;   *(dst)++ = value;   \
 
36
        *(dst)++ = value;   *(dst)++ = value;   \
 
37
        *(dst)++ = value;   *(dst)++ = value;   \
 
38
        *(dst)++ = value;   *(dst)++ = value;   \
 
39
        *(dst)++ = value;   *(dst)++ = value;   \
 
40
        *(dst)++ = value;   *(dst)++ = value;   \
 
41
        *(dst)++ = value;   *(dst)++ = value;   \
 
42
        *(dst)++ = value;   *(dst)++ = value;   \
 
43
    } while (0)
 
44
#endif
 
45
 
 
46
///////////////////////////////////////////////////////////////////////////
 
47
 
 
48
void sk_memset16_portable(uint16_t dst[], uint16_t value, int count)
 
49
{
 
50
    SkASSERT(dst != NULL && count >= 0);
 
51
 
 
52
    if (count <= 0)
 
53
        return;
 
54
 
 
55
    // not sure if this helps to short-circuit on small values of count
 
56
    if (count < 8)
 
57
    {
 
58
        do {
 
59
            *dst++ = (uint16_t)value;
 
60
        } while (--count != 0);
 
61
        return;
 
62
    }
 
63
 
 
64
    // ensure we're on a long boundary
 
65
    if ((size_t)dst & 2)
 
66
    {
 
67
        *dst++ = (uint16_t)value;
 
68
        count -= 1;
 
69
    }
 
70
 
 
71
    uint32_t value32 = ((uint32_t)value << 16) | value;
 
72
 
 
73
    // handle the bulk with our unrolled macro
 
74
    {
 
75
        int sixteenlongs = count >> 5;
 
76
        if (sixteenlongs)
 
77
        {
 
78
            uint32_t* dst32 = (uint32_t*)dst;
 
79
            do {
 
80
                assign_16_longs(dst32, value32);
 
81
            } while (--sixteenlongs != 0);
 
82
            dst = (uint16_t*)dst32;
 
83
            count &= 31;
 
84
        }
 
85
    }
 
86
 
 
87
    // handle (most) of the rest
 
88
    {
 
89
        int longs = count >> 1;
 
90
        if (longs)
 
91
        {
 
92
            do {
 
93
                *(uint32_t*)dst = value32;
 
94
                dst += 2;
 
95
            } while (--longs != 0);
 
96
        }
 
97
    }
 
98
 
 
99
    // cleanup a possible trailing short
 
100
    if (count & 1)
 
101
        *dst = (uint16_t)value;
 
102
}
 
103
 
 
104
void sk_memset32_portable(uint32_t dst[], uint32_t value, int count)
 
105
{
 
106
    SkASSERT(dst != NULL && count >= 0);
 
107
 
 
108
    {
 
109
        int sixteenlongs = count >> 4;
 
110
        if (sixteenlongs)
 
111
        {
 
112
            do {
 
113
                assign_16_longs(dst, value);
 
114
            } while (--sixteenlongs != 0);
 
115
            count &= 15;
 
116
        }
 
117
    }
 
118
 
 
119
    if (count)
 
120
    {
 
121
        do {
 
122
            *dst++ = value;
 
123
        } while (--count != 0);
 
124
    }
 
125
}
 
126
 
 
127
//////////////////////////////////////////////////////////////////////////////
 
128
 
 
129
/*  0xxxxxxx    1 total
 
130
    10xxxxxx    // never a leading byte
 
131
    110xxxxx    2 total
 
132
    1110xxxx    3 total
 
133
    11110xxx    4 total
 
134
 
 
135
    11 10 01 01 xx xx xx xx 0...
 
136
    0xE5XX0000
 
137
    0xE5 << 24
 
138
*/
 
139
 
 
140
#ifdef SK_DEBUG
 
141
    static void assert_utf8_leadingbyte(unsigned c)
 
142
    {
 
143
        SkASSERT(c <= 0xF7);    // otherwise leading byte is too big (more than 4 bytes)
 
144
        SkASSERT((c & 0xC0) != 0x80);   // can't begin with a middle char
 
145
    }
 
146
 
 
147
    int SkUTF8_LeadByteToCount(unsigned c)
 
148
    {
 
149
        assert_utf8_leadingbyte(c);
 
150
        return (((0xE5 << 24) >> (c >> 4 << 1)) & 3) + 1;
 
151
    }
 
152
#else
 
153
    #define assert_utf8_leadingbyte(c)
 
154
#endif
 
155
 
 
156
int SkUTF8_CountUnichars(const char utf8[])
 
157
{
 
158
    SkASSERT(utf8);
 
159
 
 
160
    int count = 0;
 
161
 
 
162
    for (;;)
 
163
    {
 
164
        int c = *(const uint8_t*)utf8;
 
165
        if (c == 0)
 
166
            break;
 
167
 
 
168
        utf8 += SkUTF8_LeadByteToCount(c);
 
169
        count += 1;
 
170
    }
 
171
    return count;
 
172
}
 
173
 
 
174
int SkUTF8_CountUnichars(const char utf8[], size_t byteLength)
 
175
{
 
176
    SkASSERT(NULL != utf8 || 0 == byteLength);
 
177
 
 
178
    int         count = 0;
 
179
    const char* stop = utf8 + byteLength;
 
180
 
 
181
    while (utf8 < stop)
 
182
    {
 
183
        utf8 += SkUTF8_LeadByteToCount(*(const uint8_t*)utf8);
 
184
        count += 1;
 
185
    }
 
186
    return count;
 
187
}
 
188
 
 
189
SkUnichar SkUTF8_ToUnichar(const char utf8[])
 
190
{
 
191
    SkASSERT(NULL != utf8);
 
192
 
 
193
    const uint8_t*  p = (const uint8_t*)utf8;
 
194
    int             c = *p;
 
195
    int             hic = c << 24;
 
196
 
 
197
    assert_utf8_leadingbyte(c);
 
198
 
 
199
    if (hic < 0)
 
200
    {
 
201
        uint32_t mask = (uint32_t)~0x3F;
 
202
        hic <<= 1;
 
203
        do {
 
204
            c = (c << 6) | (*++p & 0x3F);
 
205
            mask <<= 5;
 
206
        } while ((hic <<= 1) < 0);
 
207
        c &= ~mask;
 
208
    }
 
209
    return c;
 
210
}
 
211
 
 
212
SkUnichar SkUTF8_NextUnichar(const char** ptr)
 
213
{
 
214
    SkASSERT(NULL != ptr && NULL != *ptr);
 
215
 
 
216
    const uint8_t*  p = (const uint8_t*)*ptr;
 
217
    int             c = *p;
 
218
    int             hic = c << 24;
 
219
    
 
220
    assert_utf8_leadingbyte(c);
 
221
 
 
222
    if (hic < 0)
 
223
    {
 
224
        uint32_t mask = (uint32_t)~0x3F;
 
225
        hic <<= 1;
 
226
        do {
 
227
            c = (c << 6) | (*++p & 0x3F);
 
228
            mask <<= 5;
 
229
        } while ((hic <<= 1) < 0);
 
230
        c &= ~mask;
 
231
    }
 
232
    *ptr = (char*)p + 1;
 
233
    return c;
 
234
}
 
235
 
 
236
SkUnichar SkUTF8_PrevUnichar(const char** ptr)
 
237
{
 
238
    SkASSERT(NULL != ptr && NULL != *ptr);
 
239
 
 
240
    const char* p = *ptr;
 
241
    
 
242
    if (*--p & 0x80)
 
243
        while (*--p & 0x40)
 
244
            ;
 
245
 
 
246
    *ptr = (char*)p;
 
247
    return SkUTF8_NextUnichar(&p);
 
248
}
 
249
 
 
250
size_t SkUTF8_FromUnichar(SkUnichar uni, char utf8[])
 
251
{
 
252
    if ((uint32_t)uni > 0x10FFFF)
 
253
    {
 
254
        SkASSERT(!"bad unichar");
 
255
        return 0;
 
256
    }
 
257
 
 
258
    if (uni <= 127)
 
259
    {
 
260
        if (utf8)
 
261
            *utf8 = (char)uni;
 
262
        return 1;
 
263
    }
 
264
 
 
265
    char    tmp[4];
 
266
    char*   p = tmp;
 
267
    size_t  count = 1;
 
268
 
 
269
    SkDEBUGCODE(SkUnichar orig = uni;)
 
270
 
 
271
    while (uni > 0x7F >> count)
 
272
    {
 
273
        *p++ = (char)(0x80 | (uni & 0x3F));
 
274
        uni >>= 6;
 
275
        count += 1;
 
276
    }
 
277
 
 
278
    if (utf8)
 
279
    {
 
280
        p = tmp;
 
281
        utf8 += count;
 
282
        while (p < tmp + count - 1)
 
283
            *--utf8 = *p++;
 
284
        *--utf8 = (char)(~(0xFF >> count) | uni);
 
285
    }
 
286
 
 
287
    SkASSERT(utf8 == NULL || orig == SkUTF8_ToUnichar(utf8));
 
288
    return count;
 
289
}
 
290
 
 
291
////////////////////////////////////////////////////////////////////////////////////
 
292
 
 
293
int SkUTF16_CountUnichars(const uint16_t src[])
 
294
{
 
295
    SkASSERT(src);
 
296
 
 
297
    int count = 0;
 
298
    unsigned c;
 
299
    while ((c = *src++) != 0)
 
300
    {
 
301
        SkASSERT(!SkUTF16_IsLowSurrogate(c));
 
302
        if (SkUTF16_IsHighSurrogate(c))
 
303
        {
 
304
            c = *src++;
 
305
            SkASSERT(SkUTF16_IsLowSurrogate(c));
 
306
        }
 
307
        count += 1;
 
308
    }
 
309
    return count;
 
310
}
 
311
 
 
312
int SkUTF16_CountUnichars(const uint16_t src[], int numberOf16BitValues)
 
313
{
 
314
    SkASSERT(src);
 
315
 
 
316
    const uint16_t* stop = src + numberOf16BitValues;
 
317
    int count = 0;
 
318
    while (src < stop)
 
319
    {
 
320
        unsigned c = *src++;
 
321
        SkASSERT(!SkUTF16_IsLowSurrogate(c));
 
322
        if (SkUTF16_IsHighSurrogate(c))
 
323
        {
 
324
            SkASSERT(src < stop);
 
325
            c = *src++;
 
326
            SkASSERT(SkUTF16_IsLowSurrogate(c));
 
327
        }
 
328
        count += 1;
 
329
    }
 
330
    return count;
 
331
}
 
332
 
 
333
SkUnichar SkUTF16_NextUnichar(const uint16_t** srcPtr)
 
334
{
 
335
    SkASSERT(srcPtr && *srcPtr);
 
336
    
 
337
    const uint16_t* src = *srcPtr;
 
338
    SkUnichar       c = *src++;
 
339
    
 
340
    SkASSERT(!SkUTF16_IsLowSurrogate(c));
 
341
    if (SkUTF16_IsHighSurrogate(c))
 
342
    {
 
343
        unsigned c2 = *src++;
 
344
        SkASSERT(SkUTF16_IsLowSurrogate(c2));
 
345
        
 
346
        // c = ((c & 0x3FF) << 10) + (c2 & 0x3FF) + 0x10000
 
347
        // c = (((c & 0x3FF) + 64) << 10) + (c2 & 0x3FF)
 
348
        c = (c << 10) + c2 + (0x10000 - (0xD800 << 10) - 0xDC00);
 
349
    }
 
350
    *srcPtr = src;
 
351
    return c;
 
352
}
 
353
 
 
354
SkUnichar SkUTF16_PrevUnichar(const uint16_t** srcPtr)
 
355
{
 
356
    SkASSERT(srcPtr && *srcPtr);
 
357
    
 
358
    const uint16_t* src = *srcPtr;
 
359
    SkUnichar       c = *--src;
 
360
    
 
361
    SkASSERT(!SkUTF16_IsHighSurrogate(c));
 
362
    if (SkUTF16_IsLowSurrogate(c))
 
363
    {
 
364
        unsigned c2 = *--src;
 
365
        SkASSERT(SkUTF16_IsHighSurrogate(c2));
 
366
        c = (c2 << 10) + c + (0x10000 - (0xD800 << 10) - 0xDC00);
 
367
    }
 
368
    *srcPtr = src;
 
369
    return c;
 
370
}
 
371
 
 
372
size_t SkUTF16_FromUnichar(SkUnichar uni, uint16_t dst[])
 
373
{
 
374
    SkASSERT((unsigned)uni <= 0x10FFFF);
 
375
 
 
376
    int extra = (uni > 0xFFFF);
 
377
 
 
378
    if (dst)
 
379
    {
 
380
        if (extra)
 
381
        {
 
382
            // dst[0] = SkToU16(0xD800 | ((uni - 0x10000) >> 10));
 
383
            // dst[0] = SkToU16(0xD800 | ((uni >> 10) - 64));
 
384
            dst[0] = SkToU16((0xD800 - 64) + (uni >> 10));
 
385
            dst[1] = SkToU16(0xDC00 | (uni & 0x3FF));
 
386
            
 
387
            SkASSERT(SkUTF16_IsHighSurrogate(dst[0]));
 
388
            SkASSERT(SkUTF16_IsLowSurrogate(dst[1]));
 
389
        }
 
390
        else
 
391
        {
 
392
            dst[0] = SkToU16(uni);
 
393
            SkASSERT(!SkUTF16_IsHighSurrogate(dst[0]));
 
394
            SkASSERT(!SkUTF16_IsLowSurrogate(dst[0]));
 
395
        }
 
396
    }
 
397
    return 1 + extra;
 
398
}
 
399
 
 
400
size_t SkUTF16_ToUTF8(const uint16_t utf16[], int numberOf16BitValues, char utf8[])
 
401
{
 
402
    SkASSERT(numberOf16BitValues >= 0);
 
403
    if (numberOf16BitValues <= 0)
 
404
        return 0;
 
405
 
 
406
    SkASSERT(utf16 != NULL);
 
407
    
 
408
    const uint16_t* stop = utf16 + numberOf16BitValues;
 
409
    size_t          size = 0;
 
410
    
 
411
    if (utf8 == NULL)    // just count
 
412
    {
 
413
        while (utf16 < stop)
 
414
            size += SkUTF8_FromUnichar(SkUTF16_NextUnichar(&utf16), NULL);
 
415
    }
 
416
    else
 
417
    {
 
418
        char* start = utf8;
 
419
        while (utf16 < stop)
 
420
            utf8 += SkUTF8_FromUnichar(SkUTF16_NextUnichar(&utf16), utf8);
 
421
        size = utf8 - start;
 
422
    }
 
423
    return size;
 
424
}
 
425
 
 
426
////////////////////////////////////////////////////////////////////////////////////
 
427
 
 
428
#include <stdlib.h>
 
429
 
 
430
#if 0
 
431
static int round_to_K(size_t bytes)
 
432
{
 
433
    return (bytes + 512) >> 10;
 
434
}
 
435
#endif
 
436
 
 
437
SkAutoMemoryUsageProbe::SkAutoMemoryUsageProbe(const char label[])
 
438
    : fLabel(label)
 
439
{
 
440
#if 0
 
441
    struct mallinfo mi = mallinfo();
 
442
 
 
443
    fBytesAllocated = mi.uordblks;
 
444
#endif
 
445
}
 
446
 
 
447
SkAutoMemoryUsageProbe::~SkAutoMemoryUsageProbe()
 
448
{
 
449
#if 0
 
450
    struct mallinfo mi = mallinfo();
 
451
 
 
452
    printf("SkAutoMemoryUsageProbe ");
 
453
    if (fLabel)
 
454
        printf("<%s> ", fLabel);
 
455
    printf("delta %dK, current total allocated %dK\n",
 
456
            round_to_K(mi.uordblks - fBytesAllocated),
 
457
            round_to_K(mi.uordblks));
 
458
#endif
 
459
}
 
460
 
 
461
////////////////////////////////////////////////////////////////////////////////////
 
462
 
 
463
#ifdef SK_DEBUG
 
464
 
 
465
#include "SkRandom.h"
 
466
#include "SkTSearch.h"
 
467
#include "SkTSort.h"
 
468
 
 
469
#define kSEARCH_COUNT   91
 
470
 
 
471
#ifdef SK_SUPPORT_UNITTEST
 
472
static void test_search()
 
473
{
 
474
    int         i, array[kSEARCH_COUNT];
 
475
    SkRandom    rand;
 
476
 
 
477
    for (i = 0; i < kSEARCH_COUNT; i++)
 
478
        array[i] = rand.nextS();
 
479
 
 
480
    SkTHeapSort<int>(array, kSEARCH_COUNT);
 
481
    // make sure we got sorted properly
 
482
    for (i = 1; i < kSEARCH_COUNT; i++)
 
483
        SkASSERT(array[i-1] <= array[i]);
 
484
 
 
485
    // make sure we can find all of our values
 
486
    for (i = 0; i < kSEARCH_COUNT; i++)
 
487
    {
 
488
        int index = SkTSearch<int>(array, kSEARCH_COUNT, array[i], sizeof(int));
 
489
        SkASSERT(index == i);
 
490
    }
 
491
 
 
492
    // make sure that random values are either found, or the correct
 
493
    // insertion index is returned
 
494
    for (i = 0; i < 10000; i++)
 
495
    {
 
496
        int value = rand.nextS();
 
497
        int index = SkTSearch<int>(array, kSEARCH_COUNT, value, sizeof(int));
 
498
 
 
499
        if (index >= 0)
 
500
            SkASSERT(index < kSEARCH_COUNT && array[index] == value);
 
501
        else
 
502
        {
 
503
            index = ~index;
 
504
            SkASSERT(index <= kSEARCH_COUNT);
 
505
            if (index < kSEARCH_COUNT)
 
506
            {
 
507
                SkASSERT(value < array[index]);
 
508
                if (index > 0)
 
509
                    SkASSERT(value > array[index - 1]);
 
510
            }
 
511
            else    // we should append the new value
 
512
            {
 
513
                SkASSERT(value > array[kSEARCH_COUNT - 1]);
 
514
            }
 
515
        }
 
516
    }
 
517
}
 
518
 
 
519
static void test_utf16()
 
520
{
 
521
    static const SkUnichar gUni[] = {
 
522
        0x10000, 0x18080, 0x20202, 0xFFFFF, 0x101234
 
523
    };
 
524
    
 
525
    uint16_t buf[2];
 
526
    
 
527
    for (unsigned i = 0; i < SK_ARRAY_COUNT(gUni); i++)
 
528
    {
 
529
        size_t count = SkUTF16_FromUnichar(gUni[i], buf);
 
530
        SkASSERT(count == 2);
 
531
        size_t count2 = SkUTF16_CountUnichars(buf, 2);
 
532
        SkASSERT(count2 == 1);
 
533
        const uint16_t* ptr = buf;
 
534
        SkUnichar c = SkUTF16_NextUnichar(&ptr);
 
535
        SkASSERT(c == gUni[i]);
 
536
        SkASSERT(ptr - buf == 2);
 
537
    }
 
538
}
 
539
 
 
540
#endif
 
541
 
 
542
void SkUtils::UnitTest()
 
543
{
 
544
#ifdef SK_SUPPORT_UNITTEST
 
545
    static const struct {
 
546
        const char* fUtf8;
 
547
        SkUnichar   fUni;
 
548
    } gTest[] = {
 
549
        { "a",                  'a' },
 
550
        { "\x7f",               0x7f },
 
551
        { "\xC2\x80",           0x80 },
 
552
        { "\xC3\x83",           (3 << 6) | 3    },
 
553
        { "\xDF\xBF",           0x7ff },
 
554
        { "\xE0\xA0\x80",       0x800 },
 
555
        { "\xE0\xB0\xB8",       0xC38 },
 
556
        { "\xE3\x83\x83",       (3 << 12) | (3 << 6) | 3    },
 
557
        { "\xEF\xBF\xBF",       0xFFFF },
 
558
        { "\xF0\x90\x80\x80",   0x10000 },
 
559
        { "\xF3\x83\x83\x83",   (3 << 18) | (3 << 12) | (3 << 6) | 3    }
 
560
    };
 
561
 
 
562
    for (unsigned i = 0; i < SK_ARRAY_COUNT(gTest); i++)
 
563
    {
 
564
        const char* p = gTest[i].fUtf8;
 
565
        int         n = SkUTF8_CountUnichars(p);
 
566
        SkUnichar   u0 = SkUTF8_ToUnichar(gTest[i].fUtf8);
 
567
        SkUnichar   u1 = SkUTF8_NextUnichar(&p);
 
568
 
 
569
        SkASSERT(n == 1);
 
570
        SkASSERT(u0 == u1);
 
571
        SkASSERT(u0 == gTest[i].fUni);
 
572
        SkASSERT(p - gTest[i].fUtf8 == (int)strlen(gTest[i].fUtf8));
 
573
    }
 
574
    
 
575
    test_utf16();
 
576
 
 
577
    test_search();
 
578
#endif
 
579
}
 
580
 
 
581
#endif
 
582
 
 
583