template< u8 kernel_size, u8 half_size = kernel_size / 2 >
class MEDIAN
{
union QUAD
{
u8 bytes[ 4 ];
u32 value;
};
template< i8 unit >
struct COUNTER
{
static rigid u32 size()
{
return 1 << ( 16 - unit );
}
using type =
if_( kernel_size < size() )
then_( u8 )
else_( u32 );
using read_type =
if_( u32( kernel_size * 4 ) < size() )
then_( QUAD )
else_( type );
static rigid u32 bytes()
{
return sizeof( type ) * size();
}
static INLINE oo next( const xx* src )
{
return ( COUNTER< unit - 4 >::read_type* )
( ( COUNTER< unit >::type* )src + size() );
}
};
template< i8 unit >
static rigid u32 offset()
{
return COUNTER< unit + 4 >::bytes() + offset< unit + 4 >();
}
template<>
static rigid u32 offset< 12 >()
{
return 0;
}
static rigid u32 bytes()
{
return offset< -4 >();
}
///-------------------------+---------------------------------------------------------------
template< i8 unit >
struct LEVEL
{
template< class T >
static INLINE oo settle( const T* hist, const u32 base, const u32 counter )
{
return LEVEL< unit >::sum( COUNTER< unit + 4 >::next( hist ), base, counter );
}
template< class T >
static INLINE oo sum( const T* hist, u32 base = 0, u32 counter = 0 )
{
T* s = (T*)hist + ( base >> unit ) - 1;
while( counter + *++s <= half_size )
counter += *s;
base = u32( s - hist ) << unit;
return LEVEL< unit - 4 >::settle( hist, base, counter );
}
template< class T >
static INLINE oo assort(
const T* hist, const u32 base, const u32 counter, const u8 val )
{
if( counter + val > half_size )
return LEVEL< unit - 4 >::settle( hist, base, counter );
return LEVEL< unit - 4 >::settle( hist, base + ( 1 << unit ), counter + val );
}
static INLINE oo sum( const QUAD* hist, u32 base = 0, u32 counter = 0 )
{
QUAD* q = (QUAD*)( (u8*)hist + ( base >> unit ) ) - 1;
while( 1 )
{
if( !( ++q )->value )
continue;
const u32 sum01 = ( q->bytes[ 0 ] + q->bytes[ 1 ] );
const u32 sum23 = ( q->bytes[ 2 ] + q->bytes[ 3 ] );
const u32 last = counter;
counter += sum01 + sum23;
if( counter > half_size )
{
base = ( (u8*)q - (u8*)hist ) << unit;
if( last + sum01 > half_size )
return assort( hist, base, last, q->bytes[ 0 ] );
return assort( hist, base + ( 2 << unit ), last + sum01, q->bytes[ 2 ] );
}
}
}
};
template<> struct LEVEL< -4 >
{
template< class T >
static INLINE oo settle( const T* hist, const u32 base, const u32 counter )
{
return base;
}
};
///-------------------------+---------------------------------------------------------------
template< i8 unit >
static INLINE oo get_counters( const xx* hist )
{
return ( COUNTER< unit >::type* )hist + offset< unit >();
}
template< class T >
static INLINE xx count_up( const u8* hist, const T v )
{
get_counters< 0 >( hist )[ v ]++;
get_counters< 4 >( hist )[ v >> 4 ]++;
get_counters< 8 >( hist )[ v >> 8 ]++;
get_counters< 12 >( hist )[ v >> 12 ]++;
}
template< class T >
static INLINE xx count_down( const u8* hist, const T v )
{
get_counters< 0 >( hist )[ v ]--;
get_counters< 4 >( hist )[ v >> 4 ]--;
get_counters< 8 >( hist )[ v >> 8 ]--;
get_counters< 12 >( hist )[ v >> 12 ]--;
}
public:
template< class T >
static oo run( T* dst, const T* src, const uu size )
{
rigid u32 back_step = kernel_size - 1;
u8 histo[ MEDIAN< kernel_size >::bytes() ];
memset( histo, 0, MEDIAN< kernel_size >::bytes() );
std::memcpy( dst, src, half_size * sizeof *src );
for( u32 i = 0; i < kernel_size - 1; ++i )
count_up( histo, src[ i ] );
T* d = dst - half_size;
T old_median = ~src[ back_step ];
i32 changed = 0;
for( u32 i = back_step; i < size; ++i )
{
changed += quick_compare( old_median, src[ i ] );
count_up( histo, src[ i ] );
const u32 o = i - back_step;
if( changed )
{
changed = 0;
old_median = LEVEL< 12 >::sum( ( COUNTER< 12 >::type* )histo );
}
count_down( histo, src[ o ] );
changed += quick_compare( src[ o ], old_median );
d[ i ] = old_median;
}
std::memcpy( size - half_size + dst, size - half_size + src, half_size * sizeof *src );
return dst;
}
};
음 Level Of Detail 로 중앙값을 고속으로 찾아가는 카운터 소트 응용기법인데
가령, 미디언 필터의 커널이라고 해봐야 보통 작은걸 쓰니까 끽해야 수백개 정돈데, 다뤄야 할 값의 dynamic range 그러니까 샘플의 표현범위가 16비트라면
카운터 소트할 버킷의 크기가 65536개란 소리니 몇백개를 세어봐야 대부분의 배열이 희소행렬 처럼 되어버리지.
그래서 빈집이 많고 카우트의 량은 작으니 8비트 카운터 버킷에다 갯수를 셀수 있게 하고, 4바이트 단위로 탐색,
빈집을 4배속으로 뛰어넘는구조지.
그러기 위해서 카운트를 셀때는 1바이트 단위에, 읽을때는 4바이트 단위로 할 수 있도록 타입을 나눴지.
QUAD 라는게 4배속을 가능케 하는 자료구조고
COUNTER 라는 녀석 안에 type 과 read_type 으로 나뉘어져 있는게
type 은 카운트용 타입, read_type 은 읽기시 배속을 할 수 있는 타입이 되는거지.
이건 냅다 긁어서 저장해야겠군
내부 코드들은 상당히 재사용되고 있고 가장 복잡한 함수인 sum( QUAD ... ) 함수도 30줄을 넘지 않아.
이거 모조리 다 expanding 되면 수백줄 가까이 될텐데 그게 가독성이 높은 코드는 결코 아니지. 가독성이란 단순 읽기량도 상관이 있다구.
sh 가 맨날 "조은글이네요길어서읽지않았습니다" 하는것도 같은 맥락이고.
비슷해보이는 중복 코드가 있다는건, 수정 필요가 생겼을때 반복 수정점이 복수개가 된다는 말과 같고, 그럼 또 실수할 확률이 높아짐.
이코드도 assort ( 좀 어색한 네이밍이지만 ) 함수를 나누지 않았으면 들여쓰기가 4단이 되었을꺼임.
근데 저걸 나누고 오히려 속도가 5% 상승했음.
오 콜비용같은건 알아서 계산돼서 최적화시커줌??
인라인 함수잖아.
대문자 INLINE 키워드가 사실은 __forceinline 라고 강제로 무조건 인라인 시킨건데, 저걸 한거랑 안한거랑 속도비교하고 한게 더 나은 경우였기 땜에 반영한거지.
눈에만 분리되어 있지 내장되는 코드야. 의미적으로만 분리시켜 놓은거지.
아하
인라인이 너무 커지면 코드 캐시를 다 써버려서 캐시 효율이 나빠져 오히려 속도가 떨어지는데,
어느선에서 자를지는 성능평가해보고 정하는게 좋아.
루프 안이 너무 커지면 차라리 4~6클럭 쓰고 함수 점프 하는게 인라인 보다 빠를 수 있거든.
즉, 인라인으로 싸든 일반 함수로 싸든 대부분 성능 이슈에서 큰 덩어리 코드는 죄악이야.
codesafer//갯수->개수 (개수 (個數)[명사] : 한 개씩 낱으로 셀 수 있는 물건의 수효.) [리듬 맞춤법 봇♬]