bit_writer_utils.c (10986B)
1 // Copyright 2011 Google Inc. All Rights Reserved. 2 // 3 // Use of this source code is governed by a BSD-style license 4 // that can be found in the COPYING file in the root of the source 5 // tree. An additional intellectual property rights grant can be found 6 // in the file PATENTS. All contributing project authors may 7 // be found in the AUTHORS file in the root of the source tree. 8 // ----------------------------------------------------------------------------- 9 // 10 // Bit writing and boolean coder 11 // 12 // Author: Skal (pascal.massimino@gmail.com) 13 // Vikas Arora (vikaas.arora@gmail.com) 14 15 #include <assert.h> 16 #include <stdlib.h> 17 #include <string.h> // for memcpy() 18 19 #include "src/utils/bit_writer_utils.h" 20 #include "src/webp/types.h" 21 #include "src/utils/endian_inl_utils.h" 22 #include "src/utils/utils.h" 23 24 //------------------------------------------------------------------------------ 25 // VP8BitWriter 26 27 static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) { 28 uint8_t* new_buf; 29 size_t new_size; 30 const uint64_t needed_size_64b = (uint64_t)bw->pos + extra_size; 31 const size_t needed_size = (size_t)needed_size_64b; 32 if (needed_size_64b != needed_size) { 33 bw->error = 1; 34 return 0; 35 } 36 if (needed_size <= bw->max_pos) return 1; 37 // If the following line wraps over 32bit, the test just after will catch it. 38 new_size = 2 * bw->max_pos; 39 if (new_size < needed_size) new_size = needed_size; 40 if (new_size < 1024) new_size = 1024; 41 new_buf = (uint8_t*)WebPSafeMalloc(1ULL, new_size); 42 if (new_buf == NULL) { 43 bw->error = 1; 44 return 0; 45 } 46 if (bw->pos > 0) { 47 assert(bw->buf != NULL); 48 memcpy(new_buf, bw->buf, bw->pos); 49 } 50 WebPSafeFree(bw->buf); 51 bw->buf = new_buf; 52 bw->max_pos = new_size; 53 return 1; 54 } 55 56 static void Flush(VP8BitWriter* const bw) { 57 const int s = 8 + bw->nb_bits; 58 const int32_t bits = bw->value >> s; 59 assert(bw->nb_bits >= 0); 60 bw->value -= bits << s; 61 bw->nb_bits -= 8; 62 if ((bits & 0xff) != 0xff) { 63 size_t pos = bw->pos; 64 if (!BitWriterResize(bw, bw->run + 1)) { 65 return; 66 } 67 if (bits & 0x100) { // overflow -> propagate carry over pending 0xff's 68 if (pos > 0) bw->buf[pos - 1]++; 69 } 70 if (bw->run > 0) { 71 const int value = (bits & 0x100) ? 0x00 : 0xff; 72 for (; bw->run > 0; --bw->run) bw->buf[pos++] = value; 73 } 74 bw->buf[pos++] = bits & 0xff; 75 bw->pos = pos; 76 } else { 77 bw->run++; // delay writing of bytes 0xff, pending eventual carry. 78 } 79 } 80 81 //------------------------------------------------------------------------------ 82 // renormalization 83 84 static const uint8_t kNorm[128] = { // renorm_sizes[i] = 8 - log2(i) 85 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 86 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 87 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 88 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 89 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 90 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 91 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 92 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 93 0 94 }; 95 96 // range = ((range + 1) << kVP8Log2Range[range]) - 1 97 static const uint8_t kNewRange[128] = { 98 127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239, 99 127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239, 100 247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179, 101 183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239, 102 243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 103 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 104 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209, 105 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239, 106 241, 243, 245, 247, 249, 251, 253, 127 107 }; 108 109 int VP8PutBit(VP8BitWriter* const bw, int bit, int prob) { 110 const int split = (bw->range * prob) >> 8; 111 if (bit) { 112 bw->value += split + 1; 113 bw->range -= split + 1; 114 } else { 115 bw->range = split; 116 } 117 if (bw->range < 127) { // emit 'shift' bits out and renormalize 118 const int shift = kNorm[bw->range]; 119 bw->range = kNewRange[bw->range]; 120 bw->value <<= shift; 121 bw->nb_bits += shift; 122 if (bw->nb_bits > 0) Flush(bw); 123 } 124 return bit; 125 } 126 127 int VP8PutBitUniform(VP8BitWriter* const bw, int bit) { 128 const int split = bw->range >> 1; 129 if (bit) { 130 bw->value += split + 1; 131 bw->range -= split + 1; 132 } else { 133 bw->range = split; 134 } 135 if (bw->range < 127) { 136 bw->range = kNewRange[bw->range]; 137 bw->value <<= 1; 138 bw->nb_bits += 1; 139 if (bw->nb_bits > 0) Flush(bw); 140 } 141 return bit; 142 } 143 144 void VP8PutBits(VP8BitWriter* const bw, uint32_t value, int nb_bits) { 145 uint32_t mask; 146 assert(nb_bits > 0 && nb_bits < 32); 147 for (mask = 1u << (nb_bits - 1); mask; mask >>= 1) { 148 VP8PutBitUniform(bw, value & mask); 149 } 150 } 151 152 void VP8PutSignedBits(VP8BitWriter* const bw, int value, int nb_bits) { 153 if (!VP8PutBitUniform(bw, value != 0)) return; 154 if (value < 0) { 155 VP8PutBits(bw, ((-value) << 1) | 1, nb_bits + 1); 156 } else { 157 VP8PutBits(bw, value << 1, nb_bits + 1); 158 } 159 } 160 161 //------------------------------------------------------------------------------ 162 163 int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) { 164 bw->range = 255 - 1; 165 bw->value = 0; 166 bw->run = 0; 167 bw->nb_bits = -8; 168 bw->pos = 0; 169 bw->max_pos = 0; 170 bw->error = 0; 171 bw->buf = NULL; 172 return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1; 173 } 174 175 uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) { 176 VP8PutBits(bw, 0, 9 - bw->nb_bits); 177 bw->nb_bits = 0; // pad with zeroes 178 Flush(bw); 179 return bw->buf; 180 } 181 182 int VP8BitWriterAppend(VP8BitWriter* const bw, 183 const uint8_t* data, size_t size) { 184 assert(data != NULL); 185 if (bw->nb_bits != -8) return 0; // Flush() must have been called 186 if (!BitWriterResize(bw, size)) return 0; 187 memcpy(bw->buf + bw->pos, data, size); 188 bw->pos += size; 189 return 1; 190 } 191 192 void VP8BitWriterWipeOut(VP8BitWriter* const bw) { 193 if (bw != NULL) { 194 WebPSafeFree(bw->buf); 195 memset(bw, 0, sizeof(*bw)); 196 } 197 } 198 199 //------------------------------------------------------------------------------ 200 // VP8LBitWriter 201 202 // This is the minimum amount of size the memory buffer is guaranteed to grow 203 // when extra space is needed. 204 #define MIN_EXTRA_SIZE (32768ULL) 205 206 // Returns 1 on success. 207 static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) { 208 uint8_t* allocated_buf; 209 size_t allocated_size; 210 const size_t max_bytes = bw->end - bw->buf; 211 const size_t current_size = bw->cur - bw->buf; 212 const uint64_t size_required_64b = (uint64_t)current_size + extra_size; 213 const size_t size_required = (size_t)size_required_64b; 214 if (size_required != size_required_64b) { 215 bw->error = 1; 216 return 0; 217 } 218 if (max_bytes > 0 && size_required <= max_bytes) return 1; 219 allocated_size = (3 * max_bytes) >> 1; 220 if (allocated_size < size_required) allocated_size = size_required; 221 // make allocated size multiple of 1k 222 allocated_size = (((allocated_size >> 10) + 1) << 10); 223 allocated_buf = (uint8_t*)WebPSafeMalloc(1ULL, allocated_size); 224 if (allocated_buf == NULL) { 225 bw->error = 1; 226 return 0; 227 } 228 if (current_size > 0) { 229 memcpy(allocated_buf, bw->buf, current_size); 230 } 231 WebPSafeFree(bw->buf); 232 bw->buf = allocated_buf; 233 bw->cur = bw->buf + current_size; 234 bw->end = bw->buf + allocated_size; 235 return 1; 236 } 237 238 int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) { 239 memset(bw, 0, sizeof(*bw)); 240 return VP8LBitWriterResize(bw, expected_size); 241 } 242 243 int VP8LBitWriterClone(const VP8LBitWriter* const src, 244 VP8LBitWriter* const dst) { 245 const size_t current_size = src->cur - src->buf; 246 assert(src->cur >= src->buf && src->cur <= src->end); 247 if (!VP8LBitWriterResize(dst, current_size)) return 0; 248 memcpy(dst->buf, src->buf, current_size); 249 dst->bits = src->bits; 250 dst->used = src->used; 251 dst->error = src->error; 252 dst->cur = dst->buf + current_size; 253 return 1; 254 } 255 256 void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) { 257 if (bw != NULL) { 258 WebPSafeFree(bw->buf); 259 memset(bw, 0, sizeof(*bw)); 260 } 261 } 262 263 void VP8LBitWriterReset(const VP8LBitWriter* const bw_init, 264 VP8LBitWriter* const bw) { 265 bw->bits = bw_init->bits; 266 bw->used = bw_init->used; 267 bw->cur = bw->buf + (bw_init->cur - bw_init->buf); 268 assert(bw->cur <= bw->end); 269 bw->error = bw_init->error; 270 } 271 272 void VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst) { 273 const VP8LBitWriter tmp = *src; 274 *src = *dst; 275 *dst = tmp; 276 } 277 278 void VP8LPutBitsFlushBits(VP8LBitWriter* const bw) { 279 // If needed, make some room by flushing some bits out. 280 if (bw->cur + VP8L_WRITER_BYTES > bw->end) { 281 const uint64_t extra_size = (bw->end - bw->buf) + MIN_EXTRA_SIZE; 282 if (!CheckSizeOverflow(extra_size) || 283 !VP8LBitWriterResize(bw, (size_t)extra_size)) { 284 bw->cur = bw->buf; 285 bw->error = 1; 286 return; 287 } 288 } 289 *(vp8l_wtype_t*)bw->cur = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)bw->bits); 290 bw->cur += VP8L_WRITER_BYTES; 291 bw->bits >>= VP8L_WRITER_BITS; 292 bw->used -= VP8L_WRITER_BITS; 293 } 294 295 void VP8LPutBitsInternal(VP8LBitWriter* const bw, uint32_t bits, int n_bits) { 296 assert(n_bits <= 32); 297 // That's the max we can handle: 298 assert(sizeof(vp8l_wtype_t) == 2); 299 if (n_bits > 0) { 300 vp8l_atype_t lbits = bw->bits; 301 int used = bw->used; 302 // Special case of overflow handling for 32bit accumulator (2-steps flush). 303 #if VP8L_WRITER_BITS == 16 304 if (used + n_bits >= VP8L_WRITER_MAX_BITS) { 305 // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below. 306 const int shift = VP8L_WRITER_MAX_BITS - used; 307 lbits |= (vp8l_atype_t)bits << used; 308 used = VP8L_WRITER_MAX_BITS; 309 n_bits -= shift; 310 bits >>= shift; 311 assert(n_bits <= VP8L_WRITER_MAX_BITS); 312 } 313 #endif 314 // If needed, make some room by flushing some bits out. 315 while (used >= VP8L_WRITER_BITS) { 316 if (bw->cur + VP8L_WRITER_BYTES > bw->end) { 317 const uint64_t extra_size = (bw->end - bw->buf) + MIN_EXTRA_SIZE; 318 if (!CheckSizeOverflow(extra_size) || 319 !VP8LBitWriterResize(bw, (size_t)extra_size)) { 320 bw->cur = bw->buf; 321 bw->error = 1; 322 return; 323 } 324 } 325 *(vp8l_wtype_t*)bw->cur = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)lbits); 326 bw->cur += VP8L_WRITER_BYTES; 327 lbits >>= VP8L_WRITER_BITS; 328 used -= VP8L_WRITER_BITS; 329 } 330 bw->bits = lbits | ((vp8l_atype_t)bits << used); 331 bw->used = used + n_bits; 332 } 333 } 334 335 uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) { 336 // flush leftover bits 337 if (VP8LBitWriterResize(bw, (bw->used + 7) >> 3)) { 338 while (bw->used > 0) { 339 *bw->cur++ = (uint8_t)bw->bits; 340 bw->bits >>= 8; 341 bw->used -= 8; 342 } 343 bw->used = 0; 344 } 345 return bw->buf; 346 } 347 348 //------------------------------------------------------------------------------