Libav 0.7.1
libavcodec/lagarith.c
Go to the documentation of this file.
00001 /*
00002  * Lagarith lossless decoder
00003  * Copyright (c) 2009 Nathan Caldwell <saintdev (at) gmail.com>
00004  *
00005  * This file is part of Libav.
00006  *
00007  * Libav is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU Lesser General Public
00009  * License as published by the Free Software Foundation; either
00010  * version 2.1 of the License, or (at your option) any later version.
00011  *
00012  * Libav is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015  * Lesser General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU Lesser General Public
00018  * License along with Libav; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
00020  */
00021 
00028 #include "avcodec.h"
00029 #include "get_bits.h"
00030 #include "mathops.h"
00031 #include "dsputil.h"
00032 #include "lagarithrac.h"
00033 
00034 enum LagarithFrameType {
00035     FRAME_RAW           = 1,    
00036     FRAME_U_RGB24       = 2,    
00037     FRAME_ARITH_YUY2    = 3,    
00038     FRAME_ARITH_RGB24   = 4,    
00039     FRAME_SOLID_GRAY    = 5,    
00040     FRAME_SOLID_COLOR   = 6,    
00041     FRAME_OLD_ARITH_RGB = 7,    
00042     FRAME_ARITH_RGBA    = 8,    
00043     FRAME_SOLID_RGBA    = 9,    
00044     FRAME_ARITH_YV12    = 10,   
00045     FRAME_REDUCED_RES   = 11,   
00046 };
00047 
00048 typedef struct LagarithContext {
00049     AVCodecContext *avctx;
00050     AVFrame picture;
00051     DSPContext dsp;
00052     int zeros;                  
00053     int zeros_rem;              
00054 } LagarithContext;
00055 
00064 static uint64_t softfloat_reciprocal(uint32_t denom)
00065 {
00066     int shift = av_log2(denom - 1) + 1;
00067     uint64_t ret = (1ULL << 52) / denom;
00068     uint64_t err = (1ULL << 52) - ret * denom;
00069     ret <<= shift;
00070     err <<= shift;
00071     err +=  denom / 2;
00072     return ret + err / denom;
00073 }
00074 
00083 static uint32_t softfloat_mul(uint32_t x, uint64_t mantissa)
00084 {
00085     uint64_t l = x * (mantissa & 0xffffffff);
00086     uint64_t h = x * (mantissa >> 32);
00087     h += l >> 32;
00088     l &= 0xffffffff;
00089     l += 1 << av_log2(h >> 21);
00090     h += l >> 32;
00091     return h >> 20;
00092 }
00093 
00094 static uint8_t lag_calc_zero_run(int8_t x)
00095 {
00096     return (x << 1) ^ (x >> 7);
00097 }
00098 
00099 static int lag_decode_prob(GetBitContext *gb, uint32_t *value)
00100 {
00101     static const uint8_t series[] = { 1, 2, 3, 5, 8, 13, 21 };
00102     int i;
00103     int bit     = 0;
00104     int bits    = 0;
00105     int prevbit = 0;
00106     unsigned val;
00107 
00108     for (i = 0; i < 7; i++) {
00109         if (prevbit && bit)
00110             break;
00111         prevbit = bit;
00112         bit = get_bits1(gb);
00113         if (bit && !prevbit)
00114             bits += series[i];
00115     }
00116     bits--;
00117     if (bits < 0 || bits > 31) {
00118         *value = 0;
00119         return -1;
00120     } else if (bits == 0) {
00121         *value = 0;
00122         return 0;
00123     }
00124 
00125     val  = get_bits_long(gb, bits);
00126     val |= 1 << bits;
00127 
00128     *value = val - 1;
00129 
00130     return 0;
00131 }
00132 
00133 static int lag_read_prob_header(lag_rac *rac, GetBitContext *gb)
00134 {
00135     int i, j, scale_factor;
00136     unsigned prob, cumulative_target;
00137     unsigned cumul_prob = 0;
00138     unsigned scaled_cumul_prob = 0;
00139 
00140     rac->prob[0] = 0;
00141     rac->prob[257] = UINT_MAX;
00142     /* Read probabilities from bitstream */
00143     for (i = 1; i < 257; i++) {
00144         if (lag_decode_prob(gb, &rac->prob[i]) < 0) {
00145             av_log(rac->avctx, AV_LOG_ERROR, "Invalid probability encountered.\n");
00146             return -1;
00147         }
00148         if ((uint64_t)cumul_prob + rac->prob[i] > UINT_MAX) {
00149             av_log(rac->avctx, AV_LOG_ERROR, "Integer overflow encountered in cumulative probability calculation.\n");
00150             return -1;
00151         }
00152         cumul_prob += rac->prob[i];
00153         if (!rac->prob[i]) {
00154             if (lag_decode_prob(gb, &prob)) {
00155                 av_log(rac->avctx, AV_LOG_ERROR, "Invalid probability run encountered.\n");
00156                 return -1;
00157             }
00158             if (prob > 257 - i)
00159                 prob = 257 - i;
00160             for (j = 0; j < prob; j++)
00161                 rac->prob[++i] = 0;
00162         }
00163     }
00164 
00165     if (!cumul_prob) {
00166         av_log(rac->avctx, AV_LOG_ERROR, "All probabilities are 0!\n");
00167         return -1;
00168     }
00169 
00170     /* Scale probabilities so cumulative probability is an even power of 2. */
00171     scale_factor = av_log2(cumul_prob);
00172 
00173     if (cumul_prob & (cumul_prob - 1)) {
00174         uint64_t mul = softfloat_reciprocal(cumul_prob);
00175         for (i = 1; i < 257; i++) {
00176             rac->prob[i] = softfloat_mul(rac->prob[i], mul);
00177             scaled_cumul_prob += rac->prob[i];
00178         }
00179 
00180         scale_factor++;
00181         cumulative_target = 1 << scale_factor;
00182 
00183         if (scaled_cumul_prob > cumulative_target) {
00184             av_log(rac->avctx, AV_LOG_ERROR,
00185                    "Scaled probabilities are larger than target!\n");
00186             return -1;
00187         }
00188 
00189         scaled_cumul_prob = cumulative_target - scaled_cumul_prob;
00190 
00191         for (i = 1; scaled_cumul_prob; i = (i & 0x7f) + 1) {
00192             if (rac->prob[i]) {
00193                 rac->prob[i]++;
00194                 scaled_cumul_prob--;
00195             }
00196             /* Comment from reference source:
00197              * if (b & 0x80 == 0) {     // order of operations is 'wrong'; it has been left this way
00198              *                          // since the compression change is negligable and fixing it
00199              *                          // breaks backwards compatibilty
00200              *      b =- (signed int)b;
00201              *      b &= 0xFF;
00202              * } else {
00203              *      b++;
00204              *      b &= 0x7f;
00205              * }
00206              */
00207         }
00208     }
00209 
00210     rac->scale = scale_factor;
00211 
00212     /* Fill probability array with cumulative probability for each symbol. */
00213     for (i = 1; i < 257; i++)
00214         rac->prob[i] += rac->prob[i - 1];
00215 
00216     return 0;
00217 }
00218 
00219 static void add_lag_median_prediction(uint8_t *dst, uint8_t *src1,
00220                                       uint8_t *diff, int w, int *left,
00221                                       int *left_top)
00222 {
00223     /* This is almost identical to add_hfyu_median_prediction in dsputil.h.
00224      * However the &0xFF on the gradient predictor yealds incorrect output
00225      * for lagarith.
00226      */
00227     int i;
00228     uint8_t l, lt;
00229 
00230     l  = *left;
00231     lt = *left_top;
00232 
00233     for (i = 0; i < w; i++) {
00234         l = mid_pred(l, src1[i], l + src1[i] - lt) + diff[i];
00235         lt = src1[i];
00236         dst[i] = l;
00237     }
00238 
00239     *left     = l;
00240     *left_top = lt;
00241 }
00242 
00243 static void lag_pred_line(LagarithContext *l, uint8_t *buf,
00244                           int width, int stride, int line)
00245 {
00246     int L, TL;
00247 
00248     if (!line) {
00249         /* Left prediction only for first line */
00250         L = l->dsp.add_hfyu_left_prediction(buf + 1, buf + 1,
00251                                             width - 1, buf[0]);
00252         return;
00253     } else if (line == 1) {
00254         /* Second line, left predict first pixel, the rest of the line is median predicted */
00255         /* FIXME: In the case of RGB this pixel is top predicted */
00256         TL = buf[-stride];
00257     } else {
00258         /* Top left is 2 rows back, last pixel */
00259         TL = buf[width - (2 * stride) - 1];
00260     }
00261     /* Left pixel is actually prev_row[width] */
00262     L = buf[width - stride - 1];
00263 
00264     add_lag_median_prediction(buf, buf - stride, buf,
00265                               width, &L, &TL);
00266 }
00267 
00268 static int lag_decode_line(LagarithContext *l, lag_rac *rac,
00269                            uint8_t *dst, int width, int stride,
00270                            int esc_count)
00271 {
00272     int i = 0;
00273     int ret = 0;
00274 
00275     if (!esc_count)
00276         esc_count = -1;
00277 
00278     /* Output any zeros remaining from the previous run */
00279 handle_zeros:
00280     if (l->zeros_rem) {
00281         int count = FFMIN(l->zeros_rem, width - i);
00282         memset(dst + i, 0, count);
00283         i += count;
00284         l->zeros_rem -= count;
00285     }
00286 
00287     while (i < width) {
00288         dst[i] = lag_get_rac(rac);
00289         ret++;
00290 
00291         if (dst[i])
00292             l->zeros = 0;
00293         else
00294             l->zeros++;
00295 
00296         i++;
00297         if (l->zeros == esc_count) {
00298             int index = lag_get_rac(rac);
00299             ret++;
00300 
00301             l->zeros = 0;
00302 
00303             l->zeros_rem = lag_calc_zero_run(index);
00304             goto handle_zeros;
00305         }
00306     }
00307     return ret;
00308 }
00309 
00310 static int lag_decode_zero_run_line(LagarithContext *l, uint8_t *dst,
00311                                     const uint8_t *src, int width,
00312                                     int esc_count)
00313 {
00314     int i = 0;
00315     int count;
00316     uint8_t zero_run = 0;
00317     const uint8_t *start = src;
00318     uint8_t mask1 = -(esc_count < 2);
00319     uint8_t mask2 = -(esc_count < 3);
00320     uint8_t *end = dst + (width - 2);
00321 
00322 output_zeros:
00323     if (l->zeros_rem) {
00324         count = FFMIN(l->zeros_rem, width - i);
00325         if (end - dst < count) {
00326             av_log(l->avctx, AV_LOG_ERROR, "Too many zeros remaining.\n");
00327             return AVERROR_INVALIDDATA;
00328         }
00329 
00330         memset(dst, 0, count);
00331         l->zeros_rem -= count;
00332         dst += count;
00333     }
00334 
00335     while (dst < end) {
00336         i = 0;
00337         while (!zero_run && dst + i < end) {
00338             i++;
00339             zero_run =
00340                 !(src[i] | (src[i + 1] & mask1) | (src[i + 2] & mask2));
00341         }
00342         if (zero_run) {
00343             zero_run = 0;
00344             i += esc_count;
00345             memcpy(dst, src, i);
00346             dst += i;
00347             l->zeros_rem = lag_calc_zero_run(src[i]);
00348 
00349             src += i + 1;
00350             goto output_zeros;
00351         } else {
00352             memcpy(dst, src, i);
00353             src += i;
00354         }
00355     }
00356     return start - src;
00357 }
00358 
00359 
00360 
00361 static int lag_decode_arith_plane(LagarithContext *l, uint8_t *dst,
00362                                   int width, int height, int stride,
00363                                   const uint8_t *src, int src_size)
00364 {
00365     int i = 0;
00366     int read = 0;
00367     uint32_t length;
00368     uint32_t offset = 1;
00369     int esc_count = src[0];
00370     GetBitContext gb;
00371     lag_rac rac;
00372 
00373     rac.avctx = l->avctx;
00374     l->zeros = 0;
00375 
00376     if (esc_count < 4) {
00377         length = width * height;
00378         if (esc_count && AV_RL32(src + 1) < length) {
00379             length = AV_RL32(src + 1);
00380             offset += 4;
00381         }
00382 
00383         init_get_bits(&gb, src + offset, src_size * 8);
00384 
00385         if (lag_read_prob_header(&rac, &gb) < 0)
00386             return -1;
00387 
00388         lag_rac_init(&rac, &gb, length - stride);
00389 
00390         for (i = 0; i < height; i++)
00391             read += lag_decode_line(l, &rac, dst + (i * stride), width,
00392                                     stride, esc_count);
00393 
00394         if (read > length)
00395             av_log(l->avctx, AV_LOG_WARNING,
00396                    "Output more bytes than length (%d of %d)\n", read,
00397                    length);
00398     } else if (esc_count < 8) {
00399         esc_count -= 4;
00400         if (esc_count > 0) {
00401             /* Zero run coding only, no range coding. */
00402             for (i = 0; i < height; i++)
00403                 src += lag_decode_zero_run_line(l, dst + (i * stride), src,
00404                                                 width, esc_count);
00405         } else {
00406             /* Plane is stored uncompressed */
00407             for (i = 0; i < height; i++) {
00408                 memcpy(dst + (i * stride), src, width);
00409                 src += width;
00410             }
00411         }
00412     } else if (esc_count == 0xff) {
00413         /* Plane is a solid run of given value */
00414         for (i = 0; i < height; i++)
00415             memset(dst + i * stride, src[1], width);
00416         /* Do not apply prediction.
00417            Note: memset to 0 above, setting first value to src[1]
00418            and applying prediction gives the same result. */
00419         return 0;
00420     } else {
00421         av_log(l->avctx, AV_LOG_ERROR,
00422                "Invalid zero run escape code! (%#x)\n", esc_count);
00423         return -1;
00424     }
00425 
00426     for (i = 0; i < height; i++) {
00427         lag_pred_line(l, dst, width, stride, i);
00428         dst += stride;
00429     }
00430 
00431     return 0;
00432 }
00433 
00442 static int lag_decode_frame(AVCodecContext *avctx,
00443                             void *data, int *data_size, AVPacket *avpkt)
00444 {
00445     const uint8_t *buf = avpkt->data;
00446     int buf_size = avpkt->size;
00447     LagarithContext *l = avctx->priv_data;
00448     AVFrame *const p = &l->picture;
00449     uint8_t frametype = 0;
00450     uint32_t offset_gu = 0, offset_bv = 0, offset_ry = 9;
00451 
00452     AVFrame *picture = data;
00453 
00454     if (p->data[0])
00455         avctx->release_buffer(avctx, p);
00456 
00457     p->reference = 0;
00458     p->key_frame = 1;
00459 
00460     frametype = buf[0];
00461 
00462     offset_gu = AV_RL32(buf + 1);
00463     offset_bv = AV_RL32(buf + 5);
00464 
00465     switch (frametype) {
00466     case FRAME_ARITH_YV12:
00467         avctx->pix_fmt = PIX_FMT_YUV420P;
00468 
00469         if (avctx->get_buffer(avctx, p) < 0) {
00470             av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
00471             return -1;
00472         }
00473 
00474         lag_decode_arith_plane(l, p->data[0], avctx->width, avctx->height,
00475                                p->linesize[0], buf + offset_ry,
00476                                buf_size);
00477         lag_decode_arith_plane(l, p->data[2], avctx->width / 2,
00478                                avctx->height / 2, p->linesize[2],
00479                                buf + offset_gu, buf_size);
00480         lag_decode_arith_plane(l, p->data[1], avctx->width / 2,
00481                                avctx->height / 2, p->linesize[1],
00482                                buf + offset_bv, buf_size);
00483         break;
00484     default:
00485         av_log(avctx, AV_LOG_ERROR,
00486                "Unsupported Lagarith frame type: %#x\n", frametype);
00487         return -1;
00488     }
00489 
00490     *picture = *p;
00491     *data_size = sizeof(AVFrame);
00492 
00493     return buf_size;
00494 }
00495 
00496 static av_cold int lag_decode_init(AVCodecContext *avctx)
00497 {
00498     LagarithContext *l = avctx->priv_data;
00499     l->avctx = avctx;
00500 
00501     dsputil_init(&l->dsp, avctx);
00502 
00503     return 0;
00504 }
00505 
00506 static av_cold int lag_decode_end(AVCodecContext *avctx)
00507 {
00508     LagarithContext *l = avctx->priv_data;
00509 
00510     if (l->picture.data[0])
00511         avctx->release_buffer(avctx, &l->picture);
00512 
00513     return 0;
00514 }
00515 
00516 AVCodec ff_lagarith_decoder = {
00517     "lagarith",
00518     AVMEDIA_TYPE_VIDEO,
00519     CODEC_ID_LAGARITH,
00520     sizeof(LagarithContext),
00521     lag_decode_init,
00522     NULL,
00523     lag_decode_end,
00524     lag_decode_frame,
00525     CODEC_CAP_DR1,
00526     .long_name = NULL_IF_CONFIG_SMALL("Lagarith lossless"),
00527 };