SkUtils.cpp revision e3be725d2b67982a8751f6f7311b6bb2e50c8028
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 48void 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 104void 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 156int 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 174int 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 189SkUnichar 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 212SkUnichar 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 236SkUnichar 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 250size_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 293int 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 312int 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 333SkUnichar 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 354SkUnichar 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 372size_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 400size_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 430static int round_to_K(size_t bytes) 431{ 432 return (bytes + 512) >> 10; 433} 434 435SkAutoMemoryUsageProbe::SkAutoMemoryUsageProbe(const char label[]) 436 : fLabel(label) 437{ 438#if 0 439 struct mallinfo mi = mallinfo(); 440 441 fBytesAllocated = mi.uordblks; 442#endif 443} 444 445SkAutoMemoryUsageProbe::~SkAutoMemoryUsageProbe() 446{ 447#if 0 448 struct mallinfo mi = mallinfo(); 449 450 printf("SkAutoMemoryUsageProbe "); 451 if (fLabel) 452 printf("<%s> ", fLabel); 453 printf("delta %dK, current total allocated %dK\n", 454 round_to_K(mi.uordblks - fBytesAllocated), 455 round_to_K(mi.uordblks)); 456#endif 457} 458 459//////////////////////////////////////////////////////////////////////////////////// 460 461#ifdef SK_DEBUG 462 463#include "SkRandom.h" 464#include "SkTSearch.h" 465#include "SkTSort.h" 466 467#define kSEARCH_COUNT 91 468 469#ifdef SK_SUPPORT_UNITTEST 470static void test_search() 471{ 472 int i, array[kSEARCH_COUNT]; 473 SkRandom rand; 474 475 for (i = 0; i < kSEARCH_COUNT; i++) 476 array[i] = rand.nextS(); 477 478 SkTHeapSort<int>(array, kSEARCH_COUNT); 479 // make sure we got sorted properly 480 for (i = 1; i < kSEARCH_COUNT; i++) 481 SkASSERT(array[i-1] <= array[i]); 482 483 // make sure we can find all of our values 484 for (i = 0; i < kSEARCH_COUNT; i++) 485 { 486 int index = SkTSearch<int>(array, kSEARCH_COUNT, array[i], sizeof(int)); 487 SkASSERT(index == i); 488 } 489 490 // make sure that random values are either found, or the correct 491 // insertion index is returned 492 for (i = 0; i < 10000; i++) 493 { 494 int value = rand.nextS(); 495 int index = SkTSearch<int>(array, kSEARCH_COUNT, value, sizeof(int)); 496 497 if (index >= 0) 498 SkASSERT(index < kSEARCH_COUNT && array[index] == value); 499 else 500 { 501 index = ~index; 502 SkASSERT(index <= kSEARCH_COUNT); 503 if (index < kSEARCH_COUNT) 504 { 505 SkASSERT(value < array[index]); 506 if (index > 0) 507 SkASSERT(value > array[index - 1]); 508 } 509 else // we should append the new value 510 { 511 SkASSERT(value > array[kSEARCH_COUNT - 1]); 512 } 513 } 514 } 515} 516 517static void test_utf16() 518{ 519 static const SkUnichar gUni[] = { 520 0x10000, 0x18080, 0x20202, 0xFFFFF, 0x101234 521 }; 522 523 uint16_t buf[2]; 524 525 for (unsigned i = 0; i < SK_ARRAY_COUNT(gUni); i++) 526 { 527 size_t count = SkUTF16_FromUnichar(gUni[i], buf); 528 SkASSERT(count == 2); 529 size_t count2 = SkUTF16_CountUnichars(buf, 2); 530 SkASSERT(count2 == 1); 531 const uint16_t* ptr = buf; 532 SkUnichar c = SkUTF16_NextUnichar(&ptr); 533 SkASSERT(c == gUni[i]); 534 SkASSERT(ptr - buf == 2); 535 } 536} 537 538#endif 539 540void SkUtils::UnitTest() 541{ 542#ifdef SK_SUPPORT_UNITTEST 543 static const struct { 544 const char* fUtf8; 545 SkUnichar fUni; 546 } gTest[] = { 547 { "a", 'a' }, 548 { "\x7f", 0x7f }, 549 { "\xC2\x80", 0x80 }, 550 { "\xC3\x83", (3 << 6) | 3 }, 551 { "\xDF\xBF", 0x7ff }, 552 { "\xE0\xA0\x80", 0x800 }, 553 { "\xE0\xB0\xB8", 0xC38 }, 554 { "\xE3\x83\x83", (3 << 12) | (3 << 6) | 3 }, 555 { "\xEF\xBF\xBF", 0xFFFF }, 556 { "\xF0\x90\x80\x80", 0x10000 }, 557 { "\xF3\x83\x83\x83", (3 << 18) | (3 << 12) | (3 << 6) | 3 } 558 }; 559 560 for (unsigned i = 0; i < SK_ARRAY_COUNT(gTest); i++) 561 { 562 const char* p = gTest[i].fUtf8; 563 int n = SkUTF8_CountUnichars(p); 564 SkUnichar u0 = SkUTF8_ToUnichar(gTest[i].fUtf8); 565 SkUnichar u1 = SkUTF8_NextUnichar(&p); 566 567 SkASSERT(n == 1); 568 SkASSERT(u0 == u1); 569 SkASSERT(u0 == gTest[i].fUni); 570 SkASSERT(p - gTest[i].fUtf8 == (int)strlen(gTest[i].fUtf8)); 571 } 572 573 test_utf16(); 574 575 test_search(); 576#endif 577} 578 579#endif 580 581 582