rangecoder.c 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153
  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 rangecoder.c
  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. #include <string.h>
  34. #include "avcodec.h"
  35. #include "common.h"
  36. #include "rangecoder.h"
  37. void ff_init_range_encoder(RangeCoder *c, uint8_t *buf, int buf_size){
  38. c->bytestream_start=
  39. c->bytestream= buf;
  40. c->bytestream_end= buf + buf_size;
  41. c->low= 0;
  42. c->range= 0xFF00;
  43. c->outstanding_count= 0;
  44. c->outstanding_byte= -1;
  45. }
  46. void ff_init_range_decoder(RangeCoder *c, const uint8_t *buf, int buf_size){
  47. /* cast to avoid compiler warning */
  48. ff_init_range_encoder(c, (uint8_t *) buf, buf_size);
  49. c->low =(*c->bytestream++)<<8;
  50. c->low+= *c->bytestream++;
  51. }
  52. void ff_build_rac_states(RangeCoder *c, int factor, int max_p){
  53. const int64_t one= 1LL<<32;
  54. int64_t p;
  55. int last_p8, p8, i;
  56. memset(c->zero_state, 0, sizeof(c->zero_state));
  57. memset(c-> one_state, 0, sizeof(c-> one_state));
  58. last_p8= 0;
  59. p= one/2;
  60. for(i=0; i<128; i++){
  61. p8= (256*p + one/2) >> 32; //FIXME try without the one
  62. if(p8 <= last_p8) p8= last_p8+1;
  63. if(last_p8 && last_p8<256 && p8<=max_p)
  64. c->one_state[last_p8]= p8;
  65. p+= ((one-p)*factor + one/2) >> 32;
  66. last_p8= p8;
  67. }
  68. for(i=256-max_p; i<=max_p; i++){
  69. if(c->one_state[i])
  70. continue;
  71. p= (i*one + 128) >> 8;
  72. p+= ((one-p)*factor + one/2) >> 32;
  73. p8= (256*p + one/2) >> 32; //FIXME try without the one
  74. if(p8 <= i) p8= i+1;
  75. if(p8 > max_p) p8= max_p;
  76. c->one_state[ i]= p8;
  77. }
  78. for(i=1; i<255; i++)
  79. c->zero_state[i]= 256-c->one_state[256-i];
  80. }
  81. /**
  82. *
  83. * @return the number of bytes written
  84. */
  85. int ff_rac_terminate(RangeCoder *c){
  86. c->range=0xFF;
  87. c->low +=0xFF;
  88. renorm_encoder(c);
  89. c->range=0xFF;
  90. renorm_encoder(c);
  91. assert(c->low == 0);
  92. assert(c->range >= 0x100);
  93. return c->bytestream - c->bytestream_start;
  94. }
  95. #if 0 //selftest
  96. #define SIZE 10240
  97. int main(){
  98. RangeCoder c;
  99. uint8_t b[9*SIZE];
  100. uint8_t r[9*SIZE];
  101. int i;
  102. uint8_t state[10]= {0};
  103. ff_init_range_encoder(&c, b, SIZE);
  104. ff_build_rac_states(&c, 0.05*(1LL<<32), 128+64+32+16);
  105. memset(state, 128, sizeof(state));
  106. for(i=0; i<SIZE; i++){
  107. r[i]= random()%7;
  108. }
  109. for(i=0; i<SIZE; i++){
  110. START_TIMER
  111. put_rac(&c, state, r[i]&1);
  112. STOP_TIMER("put_rac")
  113. }
  114. ff_put_rac_terminate(&c);
  115. ff_init_range_decoder(&c, b, SIZE);
  116. memset(state, 128, sizeof(state));
  117. for(i=0; i<SIZE; i++){
  118. START_TIMER
  119. if( (r[i]&1) != get_rac(&c, state) )
  120. av_log(NULL, AV_LOG_DEBUG, "rac failure at %d\n", i);
  121. STOP_TIMER("get_rac")
  122. }
  123. return 0;
  124. }
  125. #endif