https://github.com/kazuho/rangecoder
Tip revision: 4376ceaf7c93adc652f712e513640c0ad4539b64 authored by Kazuho Oku on 22 October 2010, 07:34:06 UTC
binary search was accessing [0..N) when [0..N-1) only was necessary, though it was not a bug since the data structure is actually [0..N-1) and the last elements is always the maximum value within the range
binary search was accessing [0..N) when [0..N-1) only was necessary, though it was not a bug since the data structure is actually [0..N-1) and the last elements is always the maximum value within the range
Tip revision: 4376cea
range_coder.hpp
/*
* Copyrgght (c) 2006, Daisuke Okanohara
* Copyright (c) 2008-2010, Cybozu Labs, Inc.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
* * Neither the name of the copyright holders nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef __RANGE_CODER_HPP__
#define __RANGE_CODER_HPP__
#ifdef RANGE_CODER_USE_SSE
#include <xmmintrin.h>
#endif
struct rc_type_t {
enum {
TOP = 1U << 24,
TOPMASK = TOP - 1,
};
typedef unsigned int uint;
typedef unsigned char byte;
};
template <class Iter> class rc_encoder_t : public rc_type_t {
public:
rc_encoder_t(const Iter &i) : iter(i) {
L = 0;
R = 0xFFFFFFFF;
buffer = 0;
carryN = 0;
counter = 0;
start = true;
}
void encode(const uint low, const uint high, const uint total) {
uint r = R / total;
if (high < total) {
R = r * (high-low);
} else {
R -= r * low;
}
uint newL = L + r*low;
if (newL < L) {
//overflow occured (newL >= 2^32)
//buffer FF FF .. FF -> buffer+1 00 00 .. 00
buffer++;
for (;carryN > 0; carryN--) {
*iter++ = buffer;
buffer = 0;
}
}
L = newL;
while (R < TOP) {
const byte newBuffer = (L >> 24);
if (start) {
buffer = newBuffer;
start = false;
} else if (newBuffer == 0xFF) {
carryN++;
} else {
*iter++ = buffer;
for (; carryN != 0; carryN--) {
*iter++ = 0xFF;
}
buffer = newBuffer;
}
L <<= 8;
R <<= 8;
}
counter++;
}
void final() {
*iter++ = buffer;
for (; carryN != 0; carryN--) {
*iter++ = 0xFF;
}
uint t = L + R;
while (1) {
uint t8 = t >> 24, l8 = L >> 24;
*iter++ = l8;
if (t8 != l8) {
break;
}
t <<= 8;
L <<= 8;
}
}
private:
uint R;
uint L;
bool start;
byte buffer;
uint carryN;
Iter iter;
uint counter;
};
template <typename FreqType, unsigned _N, int _BASE> struct rc_decoder_search_traits_t : public rc_type_t {
typedef FreqType freq_type;
enum {
N = _N,
BASE = _BASE
};
};
template <typename FreqType, unsigned _N, int _BASE = 0> struct rc_decoder_search_t : public rc_decoder_search_traits_t<FreqType, _N, _BASE> {
static rc_type_t::uint get_index(const FreqType *freq, FreqType pos) {
rc_type_t::uint left = 0;
rc_type_t::uint right = _N - 1;
while(left < right) {
rc_type_t::uint mid = (left+right)/2;
if (freq[mid+1] <= pos) left = mid+1;
else right = mid;
}
return left;
}
};
#ifdef RANGE_CODER_USE_SSE
template<int _BASE> struct rc_decoder_search_t<short, 256, _BASE> : public rc_decoder_search_traits_t<short, 256, _BASE> {
static rc_type_t::uint get_index(const short *freq, short pos) {
__m128i v = _mm_set1_epi16(pos);
unsigned i, mask = 0;
for (i = 0; i < 256; i += 16) {
__m128i x = *reinterpret_cast<const __m128i*>(freq + i);
__m128i y = *reinterpret_cast<const __m128i*>(freq + i + 8);
__m128i a = _mm_cmplt_epi16(v, x);
__m128i b = _mm_cmplt_epi16(v, y);
mask = (_mm_movemask_epi8(b) << 16) | _mm_movemask_epi8(a);
if (mask) {
return i + (__builtin_ctz(mask) >> 1) - 1;
}
}
return 255;
}
};
#endif
template <class Iterator, class SearchType> class rc_decoder_t : public rc_type_t {
public:
typedef SearchType search_type;
typedef typename search_type::freq_type freq_type;
static const unsigned N = search_type::N;
rc_decoder_t(const Iterator& _i, const Iterator _e) : iter(_i), iter_end(_e) {
R = 0xFFFFFFFF;
D = 0;
for (int i = 0; i < 4; i++) {
D = (D << 8) | next();
}
}
uint decode(const uint total, const freq_type* cumFreq) {
const uint r = R / total;
const int targetPos = std::min(total-1, D / r);
//find target s.t. cumFreq[target] <= targetPos < cumFreq[target+1]
const uint target =
search_type::get_index(cumFreq, targetPos + search_type::BASE);
const uint low = cumFreq[target] - search_type::BASE;
const uint high = cumFreq[target+1] - search_type::BASE;
D -= r * low;
if (high != total) {
R = r * (high-low);
} else {
R -= r * low;
}
while (R < TOP) {
R <<= 8;
D = (D << 8) | next();
}
return target;
}
byte next() {
return iter != iter_end ? (byte)*iter++ : 0xff;
}
private:
uint R;
uint D;
Iterator iter, iter_end;
};
#endif