1/* 2 * ELS (Entropy Logarithmic-Scale) decoder 3 * 4 * Copyright (c) 2013 Maxim Poliakovski 5 * 6 * This file is part of FFmpeg. 7 * 8 * FFmpeg is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU Lesser General Public 10 * License as published by the Free Software Foundation; either 11 * version 2.1 of the License, or (at your option) any later version. 12 * 13 * FFmpeg is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with FFmpeg; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 21 */ 22 23/** 24 * @file 25 * Entropy Logarithmic-Scale binary arithmetic decoder 26 */ 27 28#include <stddef.h> 29#include <stdint.h> 30#include <string.h> 31 32#include "libavutil/error.h" 33#include "libavutil/intreadwrite.h" 34#include "libavutil/macros.h" 35#include "libavutil/mem.h" 36 37#include "elsdec.h" 38 39/* ELS coder constants and structures. */ 40#define ELS_JOTS_PER_BYTE 36 41#define ELS_MAX (1 << 24) 42#define RUNG_SPACE (64 * sizeof(ElsRungNode)) 43 44/* ELS coder tables. */ 45static const struct Ladder { 46 int8_t AMps; 47 int8_t ALps; 48 uint8_t next0; 49 uint8_t next1; 50} Ladder[174] = { 51 { -6, -5, 2, 1 }, 52 { -2, -12, 3, 6 }, 53 { -2, -12, 4, 6 }, 54 { -1, -16, 7, 5 }, 55 { -1, -16, 8, 10 }, 56 { -5, -6, 11, 9 }, 57 { -6, -5, 10, 5 }, 58 { -1, -18, 13, 11 }, 59 { -1, -18, 12, 14 }, 60 { -6, -5, 15, 18 }, 61 { -5, -6, 14, 9 }, 62 { -3, -8, 17, 15 }, 63 { -1, -20, 20, 16 }, 64 { -1, -20, 23, 17 }, 65 { -3, -8, 16, 18 }, 66 { -5, -6, 19, 26 }, 67 { -3, -9, 22, 24 }, 68 { -3, -9, 21, 19 }, 69 { -5, -6, 24, 26 }, 70 { -4, -7, 27, 25 }, 71 { -1, -22, 34, 28 }, 72 { -2, -11, 29, 27 }, 73 { -2, -11, 28, 30 }, 74 { -1, -22, 39, 29 }, 75 { -4, -7, 30, 32 }, 76 { -6, -5, 33, 31 }, 77 { -6, -5, 32, 25 }, 78 { -3, -8, 35, 33 }, 79 { -2, -12, 36, 38 }, 80 { -2, -12, 37, 35 }, 81 { -3, -8, 38, 40 }, 82 { -6, -5, 41, 48 }, 83 { -6, -5, 40, 31 }, 84 { -5, -6, 43, 41 }, 85 { -1, -24, 94, 42 }, 86 { -3, -8, 45, 43 }, 87 { -2, -12, 42, 44 }, 88 { -2, -12, 47, 45 }, 89 { -3, -8, 44, 46 }, 90 { -1, -24, 125, 47 }, 91 { -5, -6, 46, 48 }, 92 { -6, -5, 49, 49 }, 93 { -2, -13, 152, 164 }, 94 { -4, -7, 51, 49 }, 95 { -3, -9, 164, 168 }, 96 { -3, -9, 55, 51 }, 97 { -4, -7, 168, 170 }, 98 { -2, -13, 67, 55 }, 99 { -6, -5, 170, 49 }, 100 { -6, -5, 51, 170 }, 101 { -1, -72, 50, 74 }, 102 { -4, -7, 53, 49 }, 103 { -1, -61, 50, 74 }, 104 { -3, -8, 55, 49 }, 105 { -1, -51, 52, 76 }, 106 { -3, -9, 57, 51 }, 107 { -1, -46, 54, 76 }, 108 { -2, -10, 59, 53 }, 109 { -1, -43, 56, 78 }, 110 { -2, -11, 61, 53 }, 111 { -1, -41, 58, 80 }, 112 { -2, -12, 63, 55 }, 113 { -1, -39, 60, 82 }, 114 { -2, -12, 65, 55 }, 115 { -1, -37, 62, 84 }, 116 { -2, -13, 67, 57 }, 117 { -1, -36, 64, 86 }, 118 { -1, -14, 69, 59 }, 119 { -1, -35, 66, 88 }, 120 { -1, -14, 71, 59 }, 121 { -1, -34, 68, 90 }, 122 { -1, -15, 73, 61 }, 123 { -1, -33, 70, 92 }, 124 { -1, -15, 75, 61 }, 125 { -1, -32, 72, 94 }, 126 { -1, -15, 77, 63 }, 127 { -1, -31, 74, 96 }, 128 { -1, -16, 79, 65 }, 129 { -1, -31, 76, 98 }, 130 { -1, -16, 81, 67 }, 131 { -1, -30, 78, 100 }, 132 { -1, -17, 83, 67 }, 133 { -1, -29, 80, 102 }, 134 { -1, -17, 85, 69 }, 135 { -1, -29, 82, 104 }, 136 { -1, -18, 87, 71 }, 137 { -1, -28, 84, 104 }, 138 { -1, -18, 89, 73 }, 139 { -1, -28, 86, 108 }, 140 { -1, -18, 91, 73 }, 141 { -1, -27, 88, 108 }, 142 { -1, -19, 93, 75 }, 143 { -1, -27, 90, 112 }, 144 { -1, -19, 95, 77 }, 145 { -1, -26, 92, 112 }, 146 { -1, -20, 97, 79 }, 147 { -1, -26, 94, 114 }, 148 { -1, -20, 99, 81 }, 149 { -1, -25, 96, 116 }, 150 { -1, -20, 101, 83 }, 151 { -1, -25, 98, 118 }, 152 { -1, -21, 103, 83 }, 153 { -1, -24, 100, 120 }, 154 { -1, -21, 105, 85 }, 155 { -1, -24, 102, 122 }, 156 { -1, -22, 107, 87 }, 157 { -1, -23, 104, 124 }, 158 { -1, -22, 109, 89 }, 159 { -1, -23, 106, 126 }, 160 { -1, -22, 111, 91 }, 161 { -1, -22, 108, 128 }, 162 { -1, -23, 113, 93 }, 163 { -1, -22, 110, 130 }, 164 { -1, -23, 115, 95 }, 165 { -1, -22, 112, 132 }, 166 { -1, -24, 117, 97 }, 167 { -1, -21, 114, 134 }, 168 { -1, -24, 119, 99 }, 169 { -1, -21, 116, 136 }, 170 { -1, -25, 121, 101 }, 171 { -1, -20, 118, 136 }, 172 { -1, -25, 123, 103 }, 173 { -1, -20, 120, 138 }, 174 { -1, -26, 125, 105 }, 175 { -1, -20, 122, 140 }, 176 { -1, -26, 127, 107 }, 177 { -1, -19, 124, 142 }, 178 { -1, -27, 129, 107 }, 179 { -1, -19, 126, 144 }, 180 { -1, -27, 131, 111 }, 181 { -1, -18, 128, 146 }, 182 { -1, -28, 133, 111 }, 183 { -1, -18, 130, 146 }, 184 { -1, -28, 135, 115 }, 185 { -1, -18, 132, 148 }, 186 { -1, -29, 137, 115 }, 187 { -1, -17, 134, 150 }, 188 { -1, -29, 139, 117 }, 189 { -1, -17, 136, 152 }, 190 { -1, -30, 141, 119 }, 191 { -1, -16, 138, 152 }, 192 { -1, -31, 143, 121 }, 193 { -1, -16, 140, 154 }, 194 { -1, -31, 145, 123 }, 195 { -1, -15, 142, 156 }, 196 { -1, -32, 147, 125 }, 197 { -1, -15, 144, 158 }, 198 { -1, -33, 149, 127 }, 199 { -1, -15, 146, 158 }, 200 { -1, -34, 151, 129 }, 201 { -1, -14, 148, 160 }, 202 { -1, -35, 153, 131 }, 203 { -1, -14, 150, 160 }, 204 { -1, -36, 155, 133 }, 205 { -2, -13, 152, 162 }, 206 { -1, -37, 157, 135 }, 207 { -2, -12, 154, 164 }, 208 { -1, -39, 159, 137 }, 209 { -2, -12, 156, 164 }, 210 { -1, -41, 161, 139 }, 211 { -2, -11, 158, 166 }, 212 { -1, -43, 163, 141 }, 213 { -2, -10, 160, 166 }, 214 { -1, -46, 165, 143 }, 215 { -3, -9, 162, 168 }, 216 { -1, -51, 167, 143 }, 217 { -3, -8, 164, 170 }, 218 { -1, -61, 169, 145 }, 219 { -4, -7, 166, 170 }, 220 { -1, -72, 169, 145 }, 221 { -6, -5, 168, 49 }, 222 { 0, -108, 171, 171 }, 223 { 0, -108, 172, 172 }, 224 { -6, -5, 173, 173 }, 225}; 226 227static const uint32_t els_exp_tab[ELS_JOTS_PER_BYTE * 4 + 1] = { 228 0, 0, 0, 0, 0, 0, 0, 0, 229 0, 0, 0, 0, 0, 0, 0, 0, 230 0, 0, 0, 0, 0, 0, 0, 0, 231 0, 0, 0, 0, 0, 0, 0, 0, 232 0, 0, 0, 0, 1, 1, 1, 1, 233 1, 2, 2, 2, 3, 4, 4, 5, 234 6, 7, 8, 10, 11, 13, 16, 18, 235 21, 25, 29, 34, 40, 47, 54, 64, 236 74, 87, 101, 118, 138, 161, 188, 219, 237 256, 298, 348, 406, 474, 552, 645, 752, 238 877, 1024, 1194, 1393, 1625, 1896, 2211, 2580, 239 3010, 3511, 4096, 4778, 5573, 6501, 7584, 8847, 240 10321, 12040, 14045, 16384, 19112, 22295, 26007, 30339, 241 35391, 41285, 48160, 56180, 65536, 76288, 89088, 103936, 242 121344, 141312, 165120, 192512, 224512, 262144, 305664, 356608, 243 416000, 485376, 566016, 660480, 770560, 898816, 1048576, 1223168, 244 1426688, 1664256, 1941504, 2264832, 2642176, 3082240, 3595520, 4194304, 245 4892672, 5707520, 6657792, 7766784, 9060096, 10568960, 12328960, 14382080, 246 16777216, 247}; 248 249void ff_els_decoder_init(ElsDecCtx *ctx, const uint8_t *in, size_t data_size) 250{ 251 int nbytes; 252 253 /* consume up to 3 bytes from the input data */ 254 if (data_size >= 3) { 255 ctx->x = AV_RB24(in); 256 nbytes = 3; 257 } else if (data_size == 2) { 258 ctx->x = AV_RB16(in); 259 nbytes = 2; 260 } else { 261 ctx->x = *in; 262 nbytes = 1; 263 } 264 265 ctx->in_buf = in + nbytes; 266 ctx->data_size = data_size - nbytes; 267 ctx->err = 0; 268 ctx->j = ELS_JOTS_PER_BYTE; 269 ctx->t = ELS_MAX; 270 ctx->diff = FFMIN(ELS_MAX - ctx->x, 271 ELS_MAX - els_exp_tab[ELS_JOTS_PER_BYTE * 4 - 1]); 272} 273 274void ff_els_decoder_uninit(ElsUnsignedRung *rung) 275{ 276 av_freep(&rung->rem_rung_list); 277} 278 279static int els_import_byte(ElsDecCtx *ctx) 280{ 281 if (!ctx->data_size) { 282 ctx->err = AVERROR_EOF; 283 return AVERROR_EOF; 284 } 285 ctx->x = (ctx->x << 8) | *ctx->in_buf++; 286 ctx->data_size--; 287 ctx->j += ELS_JOTS_PER_BYTE; 288 ctx->t <<= 8; 289 290 return 0; 291} 292 293int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung) 294{ 295 int z, bit, ret; 296 const uint32_t *pAllowable = &els_exp_tab[ELS_JOTS_PER_BYTE * 3]; 297 298 if (ctx->err) 299 return 0; 300 301 z = pAllowable[ctx->j + Ladder[*rung].ALps]; 302 ctx->t -= z; 303 ctx->diff -= z; 304 if (ctx->diff > 0) 305 return *rung & 1; /* shortcut for x < t > pAllowable[j - 1] */ 306 307 if (ctx->t > ctx->x) { /* decode most probable symbol (MPS) */ 308 ctx->j += Ladder[*rung].AMps; 309 while (ctx->t > pAllowable[ctx->j]) 310 ctx->j++; 311 312 if (ctx->j <= 0) { /* MPS: import one byte from bytestream. */ 313 ret = els_import_byte(ctx); 314 if (ret < 0) 315 return ret; 316 } 317 318 z = ctx->t; 319 bit = *rung & 1; 320 *rung = Ladder[*rung].next0; 321 } else { /* decode less probable symbol (LPS) */ 322 ctx->x -= ctx->t; 323 ctx->t = z; 324 325 ctx->j += Ladder[*rung].ALps; 326 if (ctx->j <= 0) { 327 /* LPS: import one byte from bytestream. */ 328 z <<= 8; 329 ret = els_import_byte(ctx); 330 if (ret < 0) 331 return ret; 332 if (ctx->j <= 0) { 333 /* LPS: import second byte from bytestream. */ 334 z <<= 8; 335 ret = els_import_byte(ctx); 336 if (ret < 0) 337 return ret; 338 while (pAllowable[ctx->j - 1] >= z) 339 ctx->j--; 340 } 341 } 342 343 bit = !(*rung & 1); 344 *rung = Ladder[*rung].next1; 345 } 346 347 ctx->diff = FFMIN(z - ctx->x, z - pAllowable[ctx->j - 1]); 348 349 return bit; 350} 351 352unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur) 353{ 354 int i, n, r, bit; 355 ElsRungNode *rung_node; 356 357 if (ctx->err) 358 return 0; 359 360 /* decode unary prefix */ 361 for (n = 0; n < ELS_EXPGOLOMB_LEN + 1; n++) 362 if (ff_els_decode_bit(ctx, &ur->prefix_rung[n])) 363 break; 364 365 /* handle the error/overflow case */ 366 if (ctx->err || n >= ELS_EXPGOLOMB_LEN) { 367 ctx->err = AVERROR_INVALIDDATA; 368 return 0; 369 } 370 371 /* handle the zero case */ 372 if (!n) 373 return 0; 374 375 /* initialize probability tree */ 376 if (!ur->rem_rung_list) { 377 ur->rem_rung_list = av_realloc(NULL, RUNG_SPACE); 378 if (!ur->rem_rung_list) { 379 ctx->err = AVERROR(ENOMEM); 380 return 0; 381 } 382 memset(ur->rem_rung_list, 0, RUNG_SPACE); 383 ur->rung_list_size = RUNG_SPACE; 384 ur->avail_index = ELS_EXPGOLOMB_LEN; 385 } 386 387 /* decode the remainder */ 388 for (i = 0, r = 0, bit = 0; i < n; i++) { 389 if (!i) 390 rung_node = &ur->rem_rung_list[n]; 391 else { 392 if (!rung_node->next_index) { 393 if (ur->rung_list_size <= (ur->avail_index + 2) * sizeof(ElsRungNode)) { 394 // remember rung_node position 395 ptrdiff_t pos = rung_node - ur->rem_rung_list; 396 ctx->err = av_reallocp(&ur->rem_rung_list, 397 ur->rung_list_size + 398 RUNG_SPACE); 399 if (ctx->err < 0) { 400 return 0; 401 } 402 memset((uint8_t *) ur->rem_rung_list + ur->rung_list_size, 0, 403 RUNG_SPACE); 404 ur->rung_list_size += RUNG_SPACE; 405 // restore rung_node position in the new list 406 rung_node = &ur->rem_rung_list[pos]; 407 } 408 rung_node->next_index = ur->avail_index; 409 ur->avail_index += 2; 410 } 411 rung_node = &ur->rem_rung_list[rung_node->next_index + bit]; 412 } 413 414 bit = ff_els_decode_bit(ctx, &rung_node->rung); 415 if (ctx->err) 416 return bit; 417 418 r = (r << 1) + bit; 419 } 420 421 return (1 << n) - 1 + r; /* make value from exp golomb code */ 422} 423