신속 C

Question

의 불일치 패턴을 찾는 방법

사전 조건 :

1. 내가 malloc에 ​​사용할 수 없습니다.
2. 2 바이트 이내에 오류가 발생합니다. 즉 단어 단위로 단어를 검색 할 수 있습니다.
3. 내 CPU는 32 비트 ARM11이며이 시간에는 OS가 없습니다.
4. 처음 두 바이트가 중요합니다. 처음 두 바이트가 0x00이면 나머지 바이트는 모두 0x00이어야합니다.
5. 처음 두 바이트가 0xFF이면 나머지 바이트는 모두 0xFF 여야합니다.
6. 첫 번째 두 바이트가 모두 0x0000 및 0xFFFF가 아닌 경우 오류를보고하므로 나머지는 비교할 필요가 없습니다.

I은 ​​단지 두 개의 상태가 있어야하는 256k byte에서 블록 데이터를 읽어

1. 모든 0xFF를
2. 을 0x00으로

그러나, 일부 데이터는 비 예측 값을 변경할 수있는 모든 . 나는 그들을 찾아야 해. 나는 1 바이트 그것을 하나의 바이트를 검색하지만 너무 느린, 그래서 나는 그것을 할 수 이분법 방법을 사용하기로 결정 수 있습니다 - 다음과 같습니다

1. 분할 후 비교, 동일한 절반으로 데이터를 읽을 수 있습니다.
2. 둘 다 모두 0 또는 F와 같지 않으면 데이터가 양면에서 손상되어 가장 빠른 것을 찾아야하므로 두 번째 부분을 포기하고 첫 번째 부분 만 다시 나누어야 함을 의미합니다. 단지 한쪽에만 문제가 있다면, 좋은 것을 포기하고 문제에 초점을 맞 춥니 다 .e
3. 위의 루프
4. 17 시간 후에 나타나는 것 같습니다.

루프에 코드를 작성하는 방법은 무엇입니까? 크기가 다른 17 개의 참조 정적 데이터가 필요하고 memcmp을 사용합니까? 당신이 적어도 한 번 각 바이트를 검사 할 필요가 임의의 위치에서 결함을 발견하기 위해

unsigned char gReferData1[2] = {0xFF, 0xFF}; 
unsigned char gReferData2[2] = {0x00, 0x00}; 

int main(void) 
{ 
    int i = 0, result1 = 0, result2 =0; 

    read_somewhere(readBuff, sizeof(readBuff)); //read out data 

    //first test first two bytes 
    result1 = memcmp(gReferData1, readBuff, 2); //test if 0xFFFF 
    result2 = memcmp(gReferData2, readBuff, 2); //test if 0x0000 
    if(result1 == 0) 
    { 
     // means all rest data should be 0xFF 
     for(i=2; i<(0x40000/2); i++) 
     { 
      result1 = memcmp(gReferData1, readBuff + offet, 2); //test if 0xFFFF 
      if(result1 != 0) 
      { 
       //means find 
       // do error handle 
      } 
      offset+=2; 
     } 
    } 
    else if(result2 == 0) 
    { 
     // means all rest data should be 0x00 
     for(i=2; i<(0x40000/2); i++) 
     { 
      result2 = memcmp(gReferData2, readBuff + offet, 2); //test if 0x0000 
      if(result2 != 0) 
      { 
       //means find 
       // do error handle 
      } 
      offset+=2; 
     } 
    } 
    else 
    { 
     //just error 
     // do error handle 
    } 

    return 0; 
} 

Answer 1

:

내 현재 코드는 것 같습니다. 이에 대한 알고리즘은 O(n)보다 빠릅니다.

그러나 제안 된 알고리즘은 각 바이트를 두 번 이상 검사해야합니다. "데이터를 동등한 반으로 나눈 다음 비교"하기 위해 모든 바이트를 읽어야합니다. 이것은 memcmp이 내부적으로 수행 할 작업입니다. 두 메모리 세그먼트를 통해 처음부터 끝까지 반복하여 처리 할 때까지 반복합니다. 그것은 마법이 아닙니다. 그것은 단순한 루프로 할 수있는 것보다 더 효율적으로 할 수 없습니다.

힘 속도이 최대 (테스트하고 측정이!) 데이터 배열 바이트 단위를하지만 sizeof(long)의 단계로 이동 한 다음 비교하기 전에 long 해당 세그먼트를 캐스팅하지 될 수있는 최적화 그것. 이것은 많은 32 비트 CPU (모든 것이 아니라, 테스트하고 측정)에서 두 개의 8 비트 값을 비교하는 것보다 두 개의 32 비트 값을 비교하는 데 더 많은 시간이 걸리지 않는다는 사실을 이용합니다.

Answer 2

해당 버퍼의 바이트에 잘못된 상태가 있는지 확인해야하므로 각 바이트를 한 번 이상 확인해야합니다.

대부분의 시스템에서 점프하는 것은 비용이 많이 들고 바이트를 순차적으로 읽는 것이 무엇보다 저렴합니다. 그래서 더 순차적 인 읽기가 가능합니다.

전체 버퍼를 순차적으로 읽고 이전 항목의 항목과 비교하십시오. "항목"은 바이트 또는 16, 32 또는 64 비트 단어입니다. 빠르다 :

DATATYPE previous = *bufptr; 
for (i = 1; i < (length of buffer divided by DATATYPE size); i++) { 
    if (previous != *(bufptr++)) { 
     break; 
    } 
} 
if (i != (length of buffer divided by DATATYPE size)) { 
    // There has been an error. 
} 
// Verify that previous is either 0 or the appropriate number of 0xF's. 

다른 가능성은 첫 번째 바이트가 실제로 어느 × 00 또는 0xFF로인지 확인 (단지 lols 대해) 다음에, 상기 버퍼의 전반부 버퍼 후반 사이 memcmp()을 실행하는 것 . 두 반쪽의 같은 상대 위치에있는 두 비트가 동시에 반전되면 실패합니다. 그게 얼마나 가능성이 있니? 그것은 또한 하드웨어에 달려 있습니다. (버퍼가 완벽하게 직각으로 들어오는 동일한 우주 광선에 의해 꼬이게 된 두 개의 동일한 칩이 있다고 가정합니다 ...?).

아키텍처, 컴파일러 및 최적화에 따라 솔루션이 더 빠를 수 있습니다. 아마 그 정도까지는 아닙니다.