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, int 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, int 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 = 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, 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, 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 = 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, 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, 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 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 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 unsigned 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 unsigned 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
