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