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