Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. /*
  2.  * Range coder
  3.  * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>
  4.  *
  5.  * This file is part of FFmpeg.
  6.  *
  7.  * FFmpeg is free software; you can redistribute it and/or
  8.  * modify it under the terms of the GNU Lesser General Public
  9.  * License as published by the Free Software Foundation; either
  10.  * version 2.1 of the License, or (at your option) any later version.
  11.  *
  12.  * FFmpeg is distributed in the hope that it will be useful,
  13.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15.  * Lesser General Public License for more details.
  16.  *
  17.  * You should have received a copy of the GNU Lesser General Public
  18.  * License along with FFmpeg; if not, write to the Free Software
  19.  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  20.  */
  21.  
  22. /**
  23.  * @file
  24.  * Range coder.
  25.  * based upon
  26.  *    "Range encoding: an algorithm for removing redundancy from a digitised
  27.  *                     message.
  28.  *     G. N. N. Martin                  Presented in March 1979 to the Video &
  29.  *                                      Data Recording Conference,
  30.  *     IBM UK Scientific Center         held in Southampton July 24-27 1979."
  31.  *
  32.  */
  33.  
  34. #include <string.h>
  35.  
  36. #include "libavutil/attributes.h"
  37. #include "libavutil/avassert.h"
  38. #include "avcodec.h"
  39. #include "rangecoder.h"
  40. #include "bytestream.h"
  41.  
  42. av_cold void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size)
  43. {
  44.     c->bytestream_start  =
  45.     c->bytestream        = buf;
  46.     c->bytestream_end    = buf + buf_size;
  47.     c->low               = 0;
  48.     c->range             = 0xFF00;
  49.     c->outstanding_count = 0;
  50.     c->outstanding_byte  = -1;
  51. }
  52.  
  53. av_cold void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf,
  54.                                    int buf_size)
  55. {
  56.     /* cast to avoid compiler warning */
  57.     ff_init_range_encoder(c, (uint8_t *)buf, buf_size);
  58.  
  59.     c->low = bytestream_get_be16((const uint8_t **)&c->bytestream);
  60. }
  61.  
  62. void ff_build_rac_states(RangeCoder *c, int factor, int max_p)
  63. {
  64.     const int64_t one = 1LL << 32;
  65.     int64_t p;
  66.     int last_p8, p8, i;
  67.  
  68.     memset(c->zero_state, 0, sizeof(c->zero_state));
  69.     memset(c->one_state, 0, sizeof(c->one_state));
  70.  
  71.     last_p8 = 0;
  72.     p       = one / 2;
  73.     for (i = 0; i < 128; i++) {
  74.         p8 = (256 * p + one / 2) >> 32; // FIXME: try without the one
  75.         if (p8 <= last_p8)
  76.             p8 = last_p8 + 1;
  77.         if (last_p8 && last_p8 < 256 && p8 <= max_p)
  78.             c->one_state[last_p8] = p8;
  79.  
  80.         p      += ((one - p) * factor + one / 2) >> 32;
  81.         last_p8 = p8;
  82.     }
  83.  
  84.     for (i = 256 - max_p; i <= max_p; i++) {
  85.         if (c->one_state[i])
  86.             continue;
  87.  
  88.         p  = (i * one + 128) >> 8;
  89.         p += ((one - p) * factor + one / 2) >> 32;
  90.         p8 = (256 * p + one / 2) >> 32; // FIXME: try without the one
  91.         if (p8 <= i)
  92.             p8 = i + 1;
  93.         if (p8 > max_p)
  94.             p8 = max_p;
  95.         c->one_state[i] = p8;
  96.     }
  97.  
  98.     for (i = 1; i < 255; i++)
  99.         c->zero_state[i] = 256 - c->one_state[256 - i];
  100. }
  101.  
  102. /* Return the number of bytes written. */
  103. int ff_rac_terminate(RangeCoder *c)
  104. {
  105.     c->range = 0xFF;
  106.     c->low  += 0xFF;
  107.     renorm_encoder(c);
  108.     c->range = 0xFF;
  109.     renorm_encoder(c);
  110.  
  111.     av_assert1(c->low   == 0);
  112.     av_assert1(c->range >= 0x100);
  113.  
  114.     return c->bytestream - c->bytestream_start;
  115. }
  116.  
  117. #ifdef TEST
  118. #define SIZE 10240
  119.  
  120. #include "libavutil/lfg.h"
  121. #include "libavutil/log.h"
  122.  
  123. int main(void)
  124. {
  125.     RangeCoder c;
  126.     uint8_t b[9 * SIZE];
  127.     uint8_t r[9 * SIZE];
  128.     int i;
  129.     uint8_t state[10];
  130.     AVLFG prng;
  131.  
  132.     av_lfg_init(&prng, 1);
  133.  
  134.     ff_init_range_encoder(&c, b, SIZE);
  135.     ff_build_rac_states(&c, 0.05 * (1LL << 32), 128 + 64 + 32 + 16);
  136.  
  137.     memset(state, 128, sizeof(state));
  138.  
  139.     for (i = 0; i < SIZE; i++)
  140.         r[i] = av_lfg_get(&prng) % 7;
  141.  
  142.     for (i = 0; i < SIZE; i++)
  143.         put_rac(&c, state, r[i] & 1);
  144.  
  145.     ff_rac_terminate(&c);
  146.  
  147.     ff_init_range_decoder(&c, b, SIZE);
  148.  
  149.     memset(state, 128, sizeof(state));
  150.  
  151.     for (i = 0; i < SIZE; i++)
  152.         if ((r[i] & 1) != get_rac(&c, state)) {
  153.             av_log(NULL, AV_LOG_ERROR, "rac failure at %d\n", i);
  154.             return 1;
  155.         }
  156.  
  157.     return 0;
  158. }
  159. #endif /* TEST */
  160.