michael@0: 
michael@0: /*
michael@0:  * Copyright 2011 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkPackBits.h"
michael@0: 
michael@0: #define GATHER_STATSx
michael@0: 
michael@0: static inline void small_memcpy(void* SK_RESTRICT dst,
michael@0:                                 const void* SK_RESTRICT src, int n) {
michael@0:     SkASSERT(n > 0 && n <= 15);
michael@0:     uint8_t* d = (uint8_t*)dst;
michael@0:     const uint8_t* s = (const uint8_t*)src;
michael@0:     switch (n) {
michael@0:         case 15: *d++ = *s++;
michael@0:         case 14: *d++ = *s++;
michael@0:         case 13: *d++ = *s++;
michael@0:         case 12: *d++ = *s++;
michael@0:         case 11: *d++ = *s++;
michael@0:         case 10: *d++ = *s++;
michael@0:         case  9: *d++ = *s++;
michael@0:         case  8: *d++ = *s++;
michael@0:         case  7: *d++ = *s++;
michael@0:         case  6: *d++ = *s++;
michael@0:         case  5: *d++ = *s++;
michael@0:         case  4: *d++ = *s++;
michael@0:         case  3: *d++ = *s++;
michael@0:         case  2: *d++ = *s++;
michael@0:         case  1: *d++ = *s++;
michael@0:         case  0: break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: static inline void small_memset(void* dst, uint8_t value, int n) {
michael@0:     SkASSERT(n > 0 && n <= 15);
michael@0:     uint8_t* d = (uint8_t*)dst;
michael@0:     switch (n) {
michael@0:         case 15: *d++ = value;
michael@0:         case 14: *d++ = value;
michael@0:         case 13: *d++ = value;
michael@0:         case 12: *d++ = value;
michael@0:         case 11: *d++ = value;
michael@0:         case 10: *d++ = value;
michael@0:         case  9: *d++ = value;
michael@0:         case  8: *d++ = value;
michael@0:         case  7: *d++ = value;
michael@0:         case  6: *d++ = value;
michael@0:         case  5: *d++ = value;
michael@0:         case  4: *d++ = value;
michael@0:         case  3: *d++ = value;
michael@0:         case  2: *d++ = value;
michael@0:         case  1: *d++ = value;
michael@0:         case  0: break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // can we do better for small counts with our own inlined memcpy/memset?
michael@0: 
michael@0: #define PB_MEMSET(addr, value, count)       \
michael@0: do {                                        \
michael@0: if ((count) > 15) {                     \
michael@0: memset(addr, value, count);         \
michael@0: } else {                                \
michael@0: small_memset(addr, value, count);   \
michael@0: }                                       \
michael@0: } while (0)
michael@0: 
michael@0: #define PB_MEMCPY(dst, src, count)      \
michael@0: do {                                    \
michael@0:     if ((count) > 15) {                 \
michael@0:         memcpy(dst, src, count);        \
michael@0:     } else {                            \
michael@0:         small_memcpy(dst, src, count);  \
michael@0:     }                                   \
michael@0: } while (0)
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: #ifdef GATHER_STATS
michael@0:     static int gMemSetBuckets[129];
michael@0:     static int gMemCpyBuckets[129];
michael@0:     static int gCounter;
michael@0: 
michael@0: static void register_memset_count(int n) {
michael@0:     SkASSERT((unsigned)n <= 128);
michael@0:     gMemSetBuckets[n] += 1;
michael@0:     gCounter += 1;
michael@0: 
michael@0:     if ((gCounter & 0xFF) == 0) {
michael@0:         SkDebugf("----- packbits memset stats: ");
michael@0:         for (size_t i = 0; i < SK_ARRAY_COUNT(gMemSetBuckets); i++) {
michael@0:             if (gMemSetBuckets[i]) {
michael@0:                 SkDebugf(" %d:%d", i, gMemSetBuckets[i]);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: }
michael@0: static void register_memcpy_count(int n) {
michael@0:     SkASSERT((unsigned)n <= 128);
michael@0:     gMemCpyBuckets[n] += 1;
michael@0:     gCounter += 1;
michael@0: 
michael@0:     if ((gCounter & 0x1FF) == 0) {
michael@0:         SkDebugf("----- packbits memcpy stats: ");
michael@0:         for (size_t i = 0; i < SK_ARRAY_COUNT(gMemCpyBuckets); i++) {
michael@0:             if (gMemCpyBuckets[i]) {
michael@0:                 SkDebugf(" %d:%d", i, gMemCpyBuckets[i]);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: }
michael@0: #else
michael@0: #define register_memset_count(n)
michael@0: #define register_memcpy_count(n)
michael@0: #endif
michael@0: 
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: size_t SkPackBits::ComputeMaxSize16(int count) {
michael@0:     // worst case is the number of 16bit values (times 2) +
michael@0:     // 1 byte per (up to) 128 entries.
michael@0:     return ((count + 127) >> 7) + (count << 1);
michael@0: }
michael@0: 
michael@0: size_t SkPackBits::ComputeMaxSize8(int count) {
michael@0:     // worst case is the number of 8bit values + 1 byte per (up to) 128 entries.
michael@0:     return ((count + 127) >> 7) + count;
michael@0: }
michael@0: 
michael@0: static uint8_t* flush_same16(uint8_t dst[], uint16_t value, int count) {
michael@0:     while (count > 0) {
michael@0:         int n = count;
michael@0:         if (n > 128) {
michael@0:             n = 128;
michael@0:         }
michael@0:         *dst++ = (uint8_t)(n - 1);
michael@0:         *dst++ = (uint8_t)(value >> 8);
michael@0:         *dst++ = (uint8_t)value;
michael@0:         count -= n;
michael@0:     }
michael@0:     return dst;
michael@0: }
michael@0: 
michael@0: static uint8_t* flush_same8(uint8_t dst[], uint8_t value, int count) {
michael@0:     while (count > 0) {
michael@0:         int n = count;
michael@0:         if (n > 128) {
michael@0:             n = 128;
michael@0:         }
michael@0:         *dst++ = (uint8_t)(n - 1);
michael@0:         *dst++ = (uint8_t)value;
michael@0:         count -= n;
michael@0:     }
michael@0:     return dst;
michael@0: }
michael@0: 
michael@0: static uint8_t* flush_diff16(uint8_t* SK_RESTRICT dst,
michael@0:                              const uint16_t* SK_RESTRICT src, int count) {
michael@0:     while (count > 0) {
michael@0:         int n = count;
michael@0:         if (n > 128) {
michael@0:             n = 128;
michael@0:         }
michael@0:         *dst++ = (uint8_t)(n + 127);
michael@0:         PB_MEMCPY(dst, src, n * sizeof(uint16_t));
michael@0:         src += n;
michael@0:         dst += n * sizeof(uint16_t);
michael@0:         count -= n;
michael@0:     }
michael@0:     return dst;
michael@0: }
michael@0: 
michael@0: static uint8_t* flush_diff8(uint8_t* SK_RESTRICT dst,
michael@0:                             const uint8_t* SK_RESTRICT src, int count) {
michael@0:     while (count > 0) {
michael@0:         int n = count;
michael@0:         if (n > 128) {
michael@0:             n = 128;
michael@0:         }
michael@0:         *dst++ = (uint8_t)(n + 127);
michael@0:         PB_MEMCPY(dst, src, n);
michael@0:         src += n;
michael@0:         dst += n;
michael@0:         count -= n;
michael@0:     }
michael@0:     return dst;
michael@0: }
michael@0: 
michael@0: size_t SkPackBits::Pack16(const uint16_t* SK_RESTRICT src, int count,
michael@0:                           uint8_t* SK_RESTRICT dst) {
michael@0:     uint8_t* origDst = dst;
michael@0:     const uint16_t* stop = src + count;
michael@0: 
michael@0:     for (;;) {
michael@0:         count = stop - src;
michael@0:         SkASSERT(count >= 0);
michael@0:         if (count == 0) {
michael@0:             return dst - origDst;
michael@0:         }
michael@0:         if (1 == count) {
michael@0:             *dst++ = 0;
michael@0:             *dst++ = (uint8_t)(*src >> 8);
michael@0:             *dst++ = (uint8_t)*src;
michael@0:             return dst - origDst;
michael@0:         }
michael@0: 
michael@0:         unsigned value = *src;
michael@0:         const uint16_t* s = src + 1;
michael@0: 
michael@0:         if (*s == value) { // accumulate same values...
michael@0:             do {
michael@0:                 s++;
michael@0:                 if (s == stop) {
michael@0:                     break;
michael@0:                 }
michael@0:             } while (*s == value);
michael@0:             dst = flush_same16(dst, value, s - src);
michael@0:         } else {    // accumulate diff values...
michael@0:             do {
michael@0:                 if (++s == stop) {
michael@0:                     goto FLUSH_DIFF;
michael@0:                 }
michael@0:             } while (*s != s[-1]);
michael@0:             s -= 1; // back up so we don't grab one of the "same" values that follow
michael@0:         FLUSH_DIFF:
michael@0:             dst = flush_diff16(dst, src, s - src);
michael@0:         }
michael@0:         src = s;
michael@0:     }
michael@0: }
michael@0: 
michael@0: size_t SkPackBits::Pack8(const uint8_t* SK_RESTRICT src, int count,
michael@0:                          uint8_t* SK_RESTRICT dst) {
michael@0:     uint8_t* origDst = dst;
michael@0:     const uint8_t* stop = src + count;
michael@0: 
michael@0:     for (;;) {
michael@0:         count = stop - src;
michael@0:         SkASSERT(count >= 0);
michael@0:         if (count == 0) {
michael@0:             return dst - origDst;
michael@0:         }
michael@0:         if (1 == count) {
michael@0:             *dst++ = 0;
michael@0:             *dst++ = *src;
michael@0:             return dst - origDst;
michael@0:         }
michael@0: 
michael@0:         unsigned value = *src;
michael@0:         const uint8_t* s = src + 1;
michael@0: 
michael@0:         if (*s == value) { // accumulate same values...
michael@0:             do {
michael@0:                 s++;
michael@0:                 if (s == stop) {
michael@0:                     break;
michael@0:                 }
michael@0:             } while (*s == value);
michael@0:             dst = flush_same8(dst, value, s - src);
michael@0:         } else {    // accumulate diff values...
michael@0:             do {
michael@0:                 if (++s == stop) {
michael@0:                     goto FLUSH_DIFF;
michael@0:                 }
michael@0:                 // only stop if we hit 3 in a row,
michael@0:                 // otherwise we get bigger than compuatemax
michael@0:             } while (*s != s[-1] || s[-1] != s[-2]);
michael@0:             s -= 2; // back up so we don't grab the "same" values that follow
michael@0:         FLUSH_DIFF:
michael@0:             dst = flush_diff8(dst, src, s - src);
michael@0:         }
michael@0:         src = s;
michael@0:     }
michael@0: }
michael@0: 
michael@0: #include "SkUtils.h"
michael@0: 
michael@0: int SkPackBits::Unpack16(const uint8_t* SK_RESTRICT src, size_t srcSize,
michael@0:                          uint16_t* SK_RESTRICT dst) {
michael@0:     uint16_t* origDst = dst;
michael@0:     const uint8_t* stop = src + srcSize;
michael@0: 
michael@0:     while (src < stop) {
michael@0:         unsigned n = *src++;
michael@0:         if (n <= 127) {   // repeat count (n + 1)
michael@0:             n += 1;
michael@0:             sk_memset16(dst, (src[0] << 8) | src[1], n);
michael@0:             src += 2;
michael@0:         } else {    // same count (n - 127)
michael@0:             n -= 127;
michael@0:             PB_MEMCPY(dst, src, n * sizeof(uint16_t));
michael@0:             src += n * sizeof(uint16_t);
michael@0:         }
michael@0:         dst += n;
michael@0:     }
michael@0:     SkASSERT(src == stop);
michael@0:     return dst - origDst;
michael@0: }
michael@0: 
michael@0: int SkPackBits::Unpack8(const uint8_t* SK_RESTRICT src, size_t srcSize,
michael@0:                         uint8_t* SK_RESTRICT dst) {
michael@0:     uint8_t* origDst = dst;
michael@0:     const uint8_t* stop = src + srcSize;
michael@0: 
michael@0:     while (src < stop) {
michael@0:         unsigned n = *src++;
michael@0:         if (n <= 127) {   // repeat count (n + 1)
michael@0:             n += 1;
michael@0:             PB_MEMSET(dst, *src++, n);
michael@0:         } else {    // same count (n - 127)
michael@0:             n -= 127;
michael@0:             PB_MEMCPY(dst, src, n);
michael@0:             src += n;
michael@0:         }
michael@0:         dst += n;
michael@0:     }
michael@0:     SkASSERT(src == stop);
michael@0:     return dst - origDst;
michael@0: }
michael@0: 
michael@0: enum UnpackState {
michael@0:     CLEAN_STATE,
michael@0:     REPEAT_BYTE_STATE,
michael@0:     COPY_SRC_STATE
michael@0: };
michael@0: 
michael@0: void SkPackBits::Unpack8(uint8_t* SK_RESTRICT dst, size_t dstSkip,
michael@0:                          size_t dstWrite, const uint8_t* SK_RESTRICT src) {
michael@0:     if (dstWrite == 0) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     UnpackState state = CLEAN_STATE;
michael@0:     size_t      stateCount = 0;
michael@0: 
michael@0:     // state 1: do the skip-loop
michael@0:     while (dstSkip > 0) {
michael@0:         unsigned n = *src++;
michael@0:         if (n <= 127) {   // repeat count (n + 1)
michael@0:             n += 1;
michael@0:             if (n > dstSkip) {
michael@0:                 state = REPEAT_BYTE_STATE;
michael@0:                 stateCount = n - dstSkip;
michael@0:                 n = dstSkip;
michael@0:                 // we don't increment src here, since its needed in stage 2
michael@0:             } else {
michael@0:                 src++;  // skip the src byte
michael@0:             }
michael@0:         } else {    // same count (n - 127)
michael@0:             n -= 127;
michael@0:             if (n > dstSkip) {
michael@0:                 state = COPY_SRC_STATE;
michael@0:                 stateCount = n - dstSkip;
michael@0:                 n = dstSkip;
michael@0:             }
michael@0:             src += n;
michael@0:         }
michael@0:         dstSkip -= n;
michael@0:     }
michael@0: 
michael@0:     // stage 2: perform any catchup from the skip-stage
michael@0:     if (stateCount > dstWrite) {
michael@0:         stateCount = dstWrite;
michael@0:     }
michael@0:     switch (state) {
michael@0:         case REPEAT_BYTE_STATE:
michael@0:             SkASSERT(stateCount > 0);
michael@0:             register_memset_count(stateCount);
michael@0:             PB_MEMSET(dst, *src++, stateCount);
michael@0:             break;
michael@0:         case COPY_SRC_STATE:
michael@0:             SkASSERT(stateCount > 0);
michael@0:             register_memcpy_count(stateCount);
michael@0:             PB_MEMCPY(dst, src, stateCount);
michael@0:             src += stateCount;
michael@0:             break;
michael@0:         default:
michael@0:             SkASSERT(stateCount == 0);
michael@0:             break;
michael@0:     }
michael@0:     dst += stateCount;
michael@0:     dstWrite -= stateCount;
michael@0: 
michael@0:     // copy at most dstWrite bytes into dst[]
michael@0:     while (dstWrite > 0) {
michael@0:         unsigned n = *src++;
michael@0:         if (n <= 127) {   // repeat count (n + 1)
michael@0:             n += 1;
michael@0:             if (n > dstWrite) {
michael@0:                 n = dstWrite;
michael@0:             }
michael@0:             register_memset_count(n);
michael@0:             PB_MEMSET(dst, *src++, n);
michael@0:         } else {    // same count (n - 127)
michael@0:             n -= 127;
michael@0:             if (n > dstWrite) {
michael@0:                 n = dstWrite;
michael@0:             }
michael@0:             register_memcpy_count(n);
michael@0:             PB_MEMCPY(dst, src, n);
michael@0:             src += n;
michael@0:         }
michael@0:         dst += n;
michael@0:         dstWrite -= n;
michael@0:     }
michael@0:     SkASSERT(0 == dstWrite);
michael@0: }