如何快速找到匹配模式用C

我不能使用malloc。
錯誤發生在兩個字節內，意味着我可以逐字搜索。
我的CPU是32位ARM11，在此期間沒有操作系統。
前兩個字節是重要的，如果前兩個字節是0x00，這意味着所有其餘的字節應該是0x00。
如果前兩個字節是0xFF，則剩餘的字節應該是0xFF。
如果前兩個字節不是0x0000和0xFFFF，我只是報告一個錯誤，不需要比較其餘的。

我讀256Kbyte的數據塊，這應該只有兩種狀態：

所有0xFF的
全部爲0x00

然而，一些數據可能會更改爲一個不可預測值。我需要找出他們。我可以用一個字節搜索這一個字節，但似乎太慢了，所以我決定用二分法的方式來做到這一點 - 它看起來像：

鴻溝讀出的數據爲相等的一半，然後進行比較。
如果兩者都不等於全0或F，則表示數據在兩端都已損壞，我只需要找到最早的一個，所以我應該放棄第二部分，然後再分開第一部分。如果只有一方有問題，就放棄好的問題，重點放在問題上.e
loop以上的想法
似乎在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; 
}

來源

2016-10-22 How Chen

您提出的解決方案讀取所有數據，所以我不知道它會如何更快。沒有辦法繞過它，如果你想找到一個錯誤的字節，你將不得不閱讀它。 – Fredrik

「我可以一個字節搜索一個字節，但似乎很慢。」你有沒有測量它有多慢？ – 2016-10-22 13:13:26

爲了在隨機位置，你需要至少一次檢查每個字節找到缺陷。對此，沒有比O(n)更快的算法。

但是，您提出的算法需要不止一次檢查每個字節。爲了「將讀出的數據分成相等的一半，然後比較」，你必須讀取每個字節。這是memcmp將在內部執行的操作：從開始到結束循環兩個內存段，直到出現瑕疵。這不是魔術。它不可能比使用簡單的循環更有效。

這威力加快這（測試和測量它！）可能是不經過你的數據陣列逐字節但在sizeof(long)步驟，然後施放該段long你比較之前的優化它。這就利用了許多32位CPU（不是全部，測試和測量它！）的事實，比較兩個32位值不需要比較兩個8位值所需的時間。

來源

2016-10-22 12:49:52 Philipp

我應該使用'strcmp'或'memcmp？'，你的意思是'memcmp'的速度，比如比較256K的日期和我寫'for'循環來比較每個字節是否一樣？ –

@HowChen正如文檔會告訴你的，memcmp在這種情況下是正確的，因爲['strcmp']（http://www.cplusplus.com/reference/cstring/strcmp/）會在第一個'0x00'之後停止比較遭遇。 'memcmp'需要一個緩衝區來進行比較，所以當你想使用它時，你需要創建兩個256k塊，一個全部爲0x00，另一個全部爲0xFF。 – Philipp

啊，我會改成'memcmp' –

您需要檢查沒有字節的那個緩衝區有非法狀態，所以你必須檢查每個字節至少一次。

在大多數系統上，跳轉很昂貴，並且按順序讀取字節比任何東西都便宜。所以我會使用更多順序讀取。

你可能試圖做的一件事是按順序讀取整個緩衝區，並將每個條目與前一個條目的條目進行比較，「entry」是一個字節或一個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.

另一種可能性是緩衝器的第一半和緩衝器的第二半之間運行memcmp()，然後（只是爲了LOLS）驗證該第一字節是確實要麼0×00或0xFF的。如果兩個半部分中的相同相對位置中的兩個位同時翻轉，則失敗。那有多可能？它也取決於硬件（假設緩衝區是兩個相同的芯片，通過相同的宇宙射線以完美的直角進入......）。

根據架構，使用的編譯器和優化，解決方案可能會變得更快;可能不是那麼多。

來源

2016-10-22 13:17:49 LSerni

如何快速找到匹配模式用C

回答

相關問題