src/third_party/skia/src/core/SkPackBits.cpp

   1
   2 /*
   3  * Copyright 2011 Google Inc.
   4  *
   5  * Use of this source code is governed by a BSD-style license that can be
   6  * found in the LICENSE file.
   7  */
   8 #include "SkPackBits.h"
   9
  10 #define GATHER_STATSx
  11
  12 static inline void small_memcpy(void* SK_RESTRICT dst,
  13                                 const void* SK_RESTRICT src, size_t n) {
  14     SkASSERT(n > 0 && n <= 15);
  15     uint8_t* d = (uint8_t*)dst;
  16     const uint8_t* s = (const uint8_t*)src;
  17     switch (n) {
  18         case 15: *d++ = *s++;
  19         case 14: *d++ = *s++;
  20         case 13: *d++ = *s++;
  21         case 12: *d++ = *s++;
  22         case 11: *d++ = *s++;
  23         case 10: *d++ = *s++;
  24         case  9: *d++ = *s++;
  25         case  8: *d++ = *s++;
  26         case  7: *d++ = *s++;
  27         case  6: *d++ = *s++;
  28         case  5: *d++ = *s++;
  29         case  4: *d++ = *s++;
  30         case  3: *d++ = *s++;
  31         case  2: *d++ = *s++;
  32         case  1: *d++ = *s++;
  33         case  0: break;
  34     }
  35 }
  36
  37 static inline void small_memset(void* dst, uint8_t value, size_t n) {
  38     SkASSERT(n > 0 && n <= 15);
  39     uint8_t* d = (uint8_t*)dst;
  40     switch (n) {
  41         case 15: *d++ = value;
  42         case 14: *d++ = value;
  43         case 13: *d++ = value;
  44         case 12: *d++ = value;
  45         case 11: *d++ = value;
  46         case 10: *d++ = value;
  47         case  9: *d++ = value;
  48         case  8: *d++ = value;
  49         case  7: *d++ = value;
  50         case  6: *d++ = value;
  51         case  5: *d++ = value;
  52         case  4: *d++ = value;
  53         case  3: *d++ = value;
  54         case  2: *d++ = value;
  55         case  1: *d++ = value;
  56         case  0: break;
  57     }
  58 }
  59
  60 // can we do better for small counts with our own inlined memcpy/memset?
  61
  62 #define PB_MEMSET(addr, value, count)       \
  63 do {                                        \
  64 if ((count) > 15) {                     \
  65 memset(addr, value, count);         \
  66 } else {                                \
  67 small_memset(addr, value, count);   \
  68 }                                       \
  69 } while (0)
  70
  71 #define PB_MEMCPY(dst, src, count)      \
  72 do {                                    \
  73     if ((count) > 15) {                 \
  74         memcpy(dst, src, count);        \
  75     } else {                            \
  76         small_memcpy(dst, src, count);  \
  77     }                                   \
  78 } while (0)
  79
  80 ///////////////////////////////////////////////////////////////////////////////
  81
  82 #ifdef GATHER_STATS
  83     static int gMemSetBuckets[129];
  84     static int gMemCpyBuckets[129];
  85     static int gCounter;
  86
  87 static void register_memset_count(int n) {
  88     SkASSERT((unsigned)n <= 128);
  89     gMemSetBuckets[n] += 1;
  90     gCounter += 1;
  91
  92     if ((gCounter & 0xFF) == 0) {
  93         SkDebugf("----- packbits memset stats: ");
  94         for (size_t i = 0; i < SK_ARRAY_COUNT(gMemSetBuckets); i++) {
  95             if (gMemSetBuckets[i]) {
  96                 SkDebugf(" %d:%d", i, gMemSetBuckets[i]);
  97             }
  98         }
  99     }
 100 }
 101 static void register_memcpy_count(int n) {
 102     SkASSERT((unsigned)n <= 128);
 103     gMemCpyBuckets[n] += 1;
 104     gCounter += 1;
 105
 106     if ((gCounter & 0x1FF) == 0) {
 107         SkDebugf("----- packbits memcpy stats: ");
 108         for (size_t i = 0; i < SK_ARRAY_COUNT(gMemCpyBuckets); i++) {
 109             if (gMemCpyBuckets[i]) {
 110                 SkDebugf(" %d:%d", i, gMemCpyBuckets[i]);
 111             }
 112         }
 113     }
 114 }
 115 #else
 116 #define register_memset_count(n)
 117 #define register_memcpy_count(n)
 118 #endif
 119
 120
 121 ///////////////////////////////////////////////////////////////////////////////
 122
 123 size_t SkPackBits::ComputeMaxSize16(int count) {
 124     // worst case is the number of 16bit values (times 2) +
 125     // 1 byte per (up to) 128 entries.
 126     return ((count + 127) >> 7) + (count << 1);
 127 }
 128
 129 size_t SkPackBits::ComputeMaxSize8(int count) {
 130     // worst case is the number of 8bit values + 1 byte per (up to) 128 entries.
 131     return ((count + 127) >> 7) + count;
 132 }
 133
 134 static uint8_t* flush_same16(uint8_t dst[], uint16_t value, int count) {
 135     while (count > 0) {
 136         int n = count;
 137         if (n > 128) {
 138             n = 128;
 139         }
 140         *dst++ = (uint8_t)(n - 1);
 141         *dst++ = (uint8_t)(value >> 8);
 142         *dst++ = (uint8_t)value;
 143         count -= n;
 144     }
 145     return dst;
 146 }
 147
 148 static uint8_t* flush_same8(uint8_t dst[], uint8_t value, int count) {
 149     while (count > 0) {
 150         int n = count;
 151         if (n > 128) {
 152             n = 128;
 153         }
 154         *dst++ = (uint8_t)(n - 1);
 155         *dst++ = (uint8_t)value;
 156         count -= n;
 157     }
 158     return dst;
 159 }
 160
 161 static uint8_t* flush_diff16(uint8_t* SK_RESTRICT dst,
 162                              const uint16_t* SK_RESTRICT src, int count) {
 163     while (count > 0) {
 164         int n = count;
 165         if (n > 128) {
 166             n = 128;
 167         }
 168         *dst++ = (uint8_t)(n + 127);
 169         PB_MEMCPY(dst, src, n * sizeof(uint16_t));
 170         src += n;
 171         dst += n * sizeof(uint16_t);
 172         count -= n;
 173     }
 174     return dst;
 175 }
 176
 177 static uint8_t* flush_diff8(uint8_t* SK_RESTRICT dst,
 178                             const uint8_t* SK_RESTRICT src, int count) {
 179     while (count > 0) {
 180         int n = count;
 181         if (n > 128) {
 182             n = 128;
 183         }
 184         *dst++ = (uint8_t)(n + 127);
 185         PB_MEMCPY(dst, src, n);
 186         src += n;
 187         dst += n;
 188         count -= n;
 189     }
 190     return dst;
 191 }
 192
 193 size_t SkPackBits::Pack16(const uint16_t* SK_RESTRICT src, int count,
 194                           uint8_t* SK_RESTRICT dst) {
 195     uint8_t* origDst = dst;
 196     const uint16_t* stop = src + count;
 197
 198     for (;;) {
 199         count = SkToInt(stop - src);
 200         SkASSERT(count >= 0);
 201         if (count == 0) {
 202             return dst - origDst;
 203         }
 204         if (1 == count) {
 205             *dst++ = 0;
 206             *dst++ = (uint8_t)(*src >> 8);
 207             *dst++ = (uint8_t)*src;
 208             return dst - origDst;
 209         }
 210
 211         unsigned value = *src;
 212         const uint16_t* s = src + 1;
 213
 214         if (*s == value) { // accumulate same values...
 215             do {
 216                 s++;
 217                 if (s == stop) {
 218                     break;
 219                 }
 220             } while (*s == value);
 221             dst = flush_same16(dst, value, SkToInt(s - src));
 222         } else {    // accumulate diff values...
 223             do {
 224                 if (++s == stop) {
 225                     goto FLUSH_DIFF;
 226                 }
 227             } while (*s != s[-1]);
 228             s -= 1; // back up so we don't grab one of the "same" values that follow
 229         FLUSH_DIFF:
 230             dst = flush_diff16(dst, src, SkToInt(s - src));
 231         }
 232         src = s;
 233     }
 234 }
 235
 236 size_t SkPackBits::Pack8(const uint8_t* SK_RESTRICT src, int count,
 237                          uint8_t* SK_RESTRICT dst) {
 238     uint8_t* origDst = dst;
 239     const uint8_t* stop = src + count;
 240
 241     for (;;) {
 242         count = SkToInt(stop - src);
 243         SkASSERT(count >= 0);
 244         if (count == 0) {
 245             return dst - origDst;
 246         }
 247         if (1 == count) {
 248             *dst++ = 0;
 249             *dst++ = *src;
 250             return dst - origDst;
 251         }
 252
 253         unsigned value = *src;
 254         const uint8_t* s = src + 1;
 255
 256         if (*s == value) { // accumulate same values...
 257             do {
 258                 s++;
 259                 if (s == stop) {
 260                     break;
 261                 }
 262             } while (*s == value);
 263             dst = flush_same8(dst, value, SkToInt(s - src));
 264         } else {    // accumulate diff values...
 265             do {
 266                 if (++s == stop) {
 267                     goto FLUSH_DIFF;
 268                 }
 269                 // only stop if we hit 3 in a row,
 270                 // otherwise we get bigger than compuatemax
 271             } while (*s != s[-1] || s[-1] != s[-2]);
 272             s -= 2; // back up so we don't grab the "same" values that follow
 273         FLUSH_DIFF:
 274             dst = flush_diff8(dst, src, SkToInt(s - src));
 275         }
 276         src = s;
 277     }
 278 }
 279
 280 #include "SkUtils.h"
 281
 282 int SkPackBits::Unpack16(const uint8_t* SK_RESTRICT src, size_t srcSize,
 283                          uint16_t* SK_RESTRICT dst) {
 284     uint16_t* origDst = dst;
 285     const uint8_t* stop = src + srcSize;
 286
 287     while (src < stop) {
 288         unsigned n = *src++;
 289         if (n <= 127) {   // repeat count (n + 1)
 290             n += 1;
 291             sk_memset16(dst, (src[0] << 8) | src[1], n);
 292             src += 2;
 293         } else {    // same count (n - 127)
 294             n -= 127;
 295             PB_MEMCPY(dst, src, n * sizeof(uint16_t));
 296             src += n * sizeof(uint16_t);
 297         }
 298         dst += n;
 299     }
 300     SkASSERT(src == stop);
 301     return SkToInt(dst - origDst);
 302 }
 303
 304 int SkPackBits::Unpack8(const uint8_t* SK_RESTRICT src, size_t srcSize,
 305                         uint8_t* SK_RESTRICT dst) {
 306     uint8_t* origDst = dst;
 307     const uint8_t* stop = src + srcSize;
 308
 309     while (src < stop) {
 310         unsigned n = *src++;
 311         if (n <= 127) {   // repeat count (n + 1)
 312             n += 1;
 313             PB_MEMSET(dst, *src++, n);
 314         } else {    // same count (n - 127)
 315             n -= 127;
 316             PB_MEMCPY(dst, src, n);
 317             src += n;
 318         }
 319         dst += n;
 320     }
 321     SkASSERT(src == stop);
 322     return SkToInt(dst - origDst);
 323 }
 324
 325 enum UnpackState {
 326     CLEAN_STATE,
 327     REPEAT_BYTE_STATE,
 328     COPY_SRC_STATE
 329 };
 330
 331 void SkPackBits::Unpack8(uint8_t* SK_RESTRICT dst, size_t dstSkip,
 332                          size_t dstWrite, const uint8_t* SK_RESTRICT src) {
 333     if (dstWrite == 0) {
 334         return;
 335     }
 336
 337     UnpackState state = CLEAN_STATE;
 338     size_t      stateCount = 0;
 339
 340     // state 1: do the skip-loop
 341     while (dstSkip > 0) {
 342         size_t n = *src++;
 343         if (n <= 127) {   // repeat count (n + 1)
 344             n += 1;
 345             if (n > dstSkip) {
 346                 state = REPEAT_BYTE_STATE;
 347                 stateCount = n - dstSkip;
 348                 n = dstSkip;
 349                 // we don't increment src here, since its needed in stage 2
 350             } else {
 351                 src++;  // skip the src byte
 352             }
 353         } else {    // same count (n - 127)
 354             n -= 127;
 355             if (n > dstSkip) {
 356                 state = COPY_SRC_STATE;
 357                 stateCount = n - dstSkip;
 358                 n = dstSkip;
 359             }
 360             src += n;
 361         }
 362         dstSkip -= n;
 363     }
 364
 365     // stage 2: perform any catchup from the skip-stage
 366     if (stateCount > dstWrite) {
 367         stateCount = dstWrite;
 368     }
 369     switch (state) {
 370         case REPEAT_BYTE_STATE:
 371             SkASSERT(stateCount > 0);
 372             register_memset_count(stateCount);
 373             PB_MEMSET(dst, *src++, stateCount);
 374             break;
 375         case COPY_SRC_STATE:
 376             SkASSERT(stateCount > 0);
 377             register_memcpy_count(stateCount);
 378             PB_MEMCPY(dst, src, stateCount);
 379             src += stateCount;
 380             break;
 381         default:
 382             SkASSERT(stateCount == 0);
 383             break;
 384     }
 385     dst += stateCount;
 386     dstWrite -= stateCount;
 387
 388     // copy at most dstWrite bytes into dst[]
 389     while (dstWrite > 0) {
 390         size_t n = *src++;
 391         if (n <= 127) {   // repeat count (n + 1)
 392             n += 1;
 393             if (n > dstWrite) {
 394                 n = dstWrite;
 395             }
 396             register_memset_count(n);
 397             PB_MEMSET(dst, *src++, n);
 398         } else {    // same count (n - 127)
 399             n -= 127;
 400             if (n > dstWrite) {
 401                 n = dstWrite;
 402             }
 403             register_memcpy_count(n);
 404             PB_MEMCPY(dst, src, n);
 405             src += n;
 406         }
 407         dst += n;
 408         dstWrite -= n;
 409     }
 410     SkASSERT(0 == dstWrite);
 411 }