Home | History | Annotate | Download | only in core
      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 }
    412