#keywords filter,positive,negative,반복,스트림,stream,필터,가속,MPEG,TS,Transport,Section,mask,마스크,변경,감지,비트연산
#title Positive 및 Negative Filter (MPEG TS Section Filter)
[wiki:Home 대문] / [wiki:CategoryProgramming 프로그래밍] / [wiki:Positive_and_Negative_filter Positive 및 Negative Filter (MPEG TS Section Filter)]
----
== [wiki:Positive_and_Negative_filter Positive 및 Negative Filter (MPEG TS Section Filter)] ==
 * 작성자
  조재혁([mailto:minzkn@minzkn.com])

 * 고친과정
  2008년 2월 5일 : 처음씀

[[TableOfContents]]
=== 구현 ===
 Filter는 어떤 입력으로부터의 Data에서 원하는 부분을 선별하기 위한 용도의 함수를 말합니다.[[br]]
 높은 트래픽 입력을 선별하는데 있어서 CPU가 처리하기 보다는 H/W 적인 FPGA등의 논리적인 회로 구현으로 이 연속적인 스트림 트래픽에서 내가 원하는 데이터인가 아닌가를 빠르게 선별하는데 유용할 수 있을겁니다.   

 Filter중에서 MPEG TS 의 SectionFilter 를 구현하는데 있어서 [wiki:Positive_and_Negative_filter Positive 및 Negative Filter (MPEG TS Section Filter)] 알고리즘으로 적절한 H/W 적인 Filter와 유사한 동작을 구현할수 있게 됩니다.

 여기서 Positive mask 는 주어진 data 와 mask 값을 AND연산후 comp 와 비교하는 일반적인 mask 동작으로 특정 비트패턴을 일치조건으로 취하는 동작입니다.[[br]]
 반면에 Negative mask 는 주어진 data 와 mask 값을 AND연산후 주어진 비트패턴이 주어진 comp 값과 다른 경우 일치조건으로 취하는 동작입니다.

 Positive mask 는 특정 비트열을 통과시키는 용도로 구현되며[[br]]
 Negative mask 는 현재조건이 변경되는 시점을 통과시키는 용도로 구현되는것이죠.

 즉, 다음과 같이 스트림 입력에 대한 비트연산으로 통과(ACCEPT)/거부(DROP) 을 결정하는 스트림 이력에 대한 스위치 논리입니다.
 * Positive mask 의사 구현 (어떠한 입력과 일치하는 것을 ACCEPT 처리)
  {{{#!plain
func bool positive_mask_filter(in_stream, mask, mode, comp, n)
{
    positive_mask[0..n] = mask[0..n] & mode[0..n];
    if ( (in_stream[0..n] & positive_mask[0..n]) == (comp[0..n] & positive_mask[0..n]) )
        return ACCEPT;
    return DROP;
}
}}}
 * Negative mask 의사 구현 (어떠한 반복되는 동일한 입력 중에서 변화가 발생될 때만 ACCEPT 처리)
  {{{#!plain
func bool negative_mask_filter(in_stream, mask, mode, comp, n)
{
    negative_mask[0..n] = mask[0..n] & (~mode[0..n]);
    if ( ((in_stream[0..n] ^ comp[0..n]) & negative_mask[0..n]) != 0[0..n] )
        return ACCEPT;
    return DROP;
}
}}}

 아래의 예제가 충분할지는 모르겠지만 대략 다음과 같이 구현된다고 보시면 됩니다. 당연히 H/W 설계적인 관점에서도 가능한 구조로 되어 있습니다.

 거의 기능상 구현으로 봤을때는 Positive mask 만 있으면 충분합니다.[[br]]
 하지만 불필요한 반복적인 data를 무시하지 않기 때문에 CPU가 과도하게 피곤해지겠죠.[[br]]
 Negative mask 는 이러한 부하의 줄이는 목적으로 사용합니다.
 
 {{{#!enscript c
/*
  Copyright (C) JAEHYUK CHO
  All rights reserved.
  Author: JAEHYUK CHO <mailto:minzkn@minzkn.com>
*/

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <unistd.h>

static __inline int __mzmatch_filter(const unsigned char *s_data, const unsigned char *s_mask, const unsigned char *s_mode, const unsigned char *s_comp, size_t s_size);
int mzmatch_filter(const void *s_data, const void *s_mask, const void *s_mode, const void *s_comp, size_t s_size);

static __inline int __mzmatch_filter(const unsigned char *s_data, const unsigned char *s_mask, const unsigned char *s_mode, const unsigned char *s_comp, size_t s_size)
{
    size_t s_offset = (size_t)0;
    unsigned char s_positive_mask, s_negative_mask;
    while(s_offset < s_size) {
        s_positive_mask = s_mask[s_offset] & s_mode[s_offset];
        s_negative_mask = s_mask[s_offset] & (~s_mode[s_offset]);
        if(((s_positive_mask & s_data[s_offset]) != (s_positive_mask & s_comp[s_offset])) ||
           ((s_negative_mask != ((unsigned char)0)) && ((s_negative_mask & (s_data[s_offset] ^ s_comp[s_offset])) == ((unsigned char)0)))) {
            return(0);
        }
        s_offset++;
    }
    return(1);
}

int mzmatch_filter(const void *s_data, const void *s_mask, const void *s_mode, const void *s_comp, size_t s_size)
{
    return(__mzmatch_filter((const unsigned char *)s_data, (const unsigned char *)s_mask, (const unsigned char *)s_mode, (const unsigned char *)s_comp, s_size));
}

void test(unsigned char s_mask, unsigned char s_mode, unsigned char s_comp)
{
    int s_match_condition;
    unsigned int s_data_min = 0x00u, s_data_max = 0xffu;
    (void)fprintf(stdout, "TEST => data=%02X~%02X mask=%02X mode=%02X comp=%02X",
        (unsigned int)s_data_min,
        (unsigned int)s_data_max,
        (unsigned int)s_mask,
        (unsigned int)s_mode,
        (unsigned int)s_comp
    );
    do {
        if((s_data_min % 0x10u) == 0x00u)(void)fputs("\n", stdout);
        s_match_condition = mzmatch_filter(&s_data_min, &s_mask, &s_mode, &s_comp, (size_t)1);
#if defined(__linux__) /* can use ansi code(escape sequence code) */
        (void)fprintf(stdout,
            " %s%02X\x1b[0m",
            (s_match_condition == 0) ? "\x1b[1;31m" : "\x1b[1;33m",
            (unsigned int)s_data_min);
#else
        if(s_match_condition != 0) {
            (void)fprintf(stdout,
                " %02X",
                (unsigned int)s_data_min);
        }
#endif
    }while((s_data_min++) < s_data_max);
    (void)fputs("\n", stdout);
}

int main(void)
{
    test(0xffu, 0xffu, 0x80u);
    test(0xffu, 0x00u, 0x80u);
    test(0xffu, 0xf9u, 0xceu);
    test(0xffu, 0xf0u, 0x24u);
    test(0x3fu, ~((unsigned char)0x3fu), 0x04u);
    /* TS filter */
    test(0xffu, 0xffu, 0x00u); /* PAT */
    test(0xffu, 0xffu, 0x01u); /* CAT */
    test(0xffu, 0xffu, 0x02u); /* PMT */
    test(0xffu, 0xffu, 0x3eu); /* DSM CC */
    test(0xfcu, 0xffu, 0x80u); /* ECM 0x80, 0x81, 0x82 */
    return(EXIT_SUCCESS);
}
}}}