ישנן אפשרויות רבות לחישוב סכום הבדיקה CRC באינטרנט. אך מהי בדיוק בדיקת בדיקה ולמה היא מחושבת בצורה כזו? בואו נבין את זה.
הוראות
שלב 1
ראשית, בואו נקבל מעט תיאוריה. אז מה זה בעצם CRC? בקיצור, זהו אחד הזנים של חישוב סכום הבדיקה. סכום בדיקה הוא שיטה לבדיקת תקינות המידע שהתקבל בצד המקלט בעת העברה בערוצי תקשורת. לדוגמא, אחד הבדיקות הפשוטות ביותר הוא שימוש בסיבית הזוגיות. זה כאשר כל סיביות ההודעה המשודרת מסוכמות, ואם הסכום מתגלה כאחיד, אז 0 מתווסף לסוף ההודעה, אם הוא מוזר, אז 1. בעת קבלת הסכום של ביטים של הודעות נספרים גם הם ומשווים עם סיביות הזוגיות שהתקבלה. אם הם נבדלים, התרחשו שגיאות במהלך השידור והמידע שהועבר עוות.
אבל שיטה זו לאיתור נוכחות של טעויות מאוד אינפורמטיבית ולא תמיד עובדת, כי אם מספר סיביות של ההודעה מעוותות, יתכן ששווי הסכום לא ישתנה. לכן, ישנם הרבה יותר צ'קים "מתקדמים", כולל CRC.
למעשה, CRC אינו סכום, אלא תוצאה של חלוקת כמות מידע מסוימת (הודעת מידע) בקבוע, או ליתר דיוק, את שארית חלוקת המסר בקבוע. עם זאת, CRC מכונה גם מבחינה היסטורית "בדיקת בדיקה". כל ביט בהודעה תורם לערך CRC. כלומר, אם לפחות ביט אחד מההודעה המקורית ישתנה במהלך השידור, גם בדיקת הבדיקה תשתנה, ובאופן משמעותי. זהו יתרון גדול של בדיקה כזו, מכיוון שהיא מאפשרת לך לקבוע באופן חד משמעי אם ההודעה המקורית עוותה במהלך השידור או לא.
שלב 2
לפני שנתחיל בחישוב ה- CRC, יש צורך בתיאוריה קצת יותר.
מה המסר המקורי צריך להיות ברור. זהו רצף רציף של סיביות באורך שרירותי.
מהו הקבוע לפיו עלינו לחלק את המסר המקורי? מספר זה הוא גם בכל אורך, אך בדרך כלל משתמשים בכפולות של בת אחד - 8, 16 ו -32 ביט. פשוט קל יותר לספור, כי מחשבים עובדים עם בתים, ולא עם ביטים.
קבוע המחלק נכתב בדרך כלל כפולינומי (פולינום) כזה: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. כאן, דרגת המספר "x" פירושה המיקום של הסיבית היחידה במספר, החל מאפס, והסיבית המשמעותית ביותר מציינת את מידת הפולינום ונזרקת בעת פירוש המספר. כלומר, המספר שנכתב בעבר הוא לא יותר מ (1) 00000111 בינארי, או 7 בעשרוני. בסוגריים ציינתי את הספרה המשמעותית ביותר של המספר.
הנה דוגמה נוספת: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
בדרך כלל משתמשים בפולינומים סטנדרטיים בכמה סוגים של CRC.
שלב 3
אז איך מחשבים את סכום הבדיקה? ישנה שיטה בסיסית - חלוקת מסר ל"ראש-בראש "פולינומי - ושינויים בו במטרה להפחית את מספר החישובים ובהתאם, לזרז את חישוב ה- CRC. נבחן את השיטה הבסיסית.
באופן כללי, חלוקת המספר על ידי פולינום מתבצעת על פי האלגוריתם הבא:
1) נוצר מערך (רישום), מלא באפסים, שווים באורך לרוחב הפולינום;
2) ההודעה המקורית מתווספת לאפסים בסיביות הפחות משמעותיות, בכמות השווה למספר הסיביות של הפולינום;
3) סיבית אחת משמעותית ביותר של ההודעה מוזנת לסיבית הכי פחות משמעותית של הרישום, וסיבית אחת מועברת מהסיבית המשמעותית ביותר של הרישום;
4) אם הסיבית המורחבת שווה ל- "1", הסיביות הופכות (פעולת XOR, בלעדי OR) באותם סיביות רישום המתאימות לאלה בפולינום;
5) אם עדיין יש ביטים בהודעה, עבור לשלב 3);
6) כשכל סיביות ההודעה נכנסו לרשם ועובדו על ידי אלגוריתם זה, יתרת החלוקה נותרה ברשומה, שהיא סכום הבדיקה CRC.
האיור ממחיש את חלוקת רצף הסיביות המקורי במספר (1) 00000111, או בפולינום x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
שלב 4
נותרו עוד כמה נגיעות. כפי ששמתם לב, ניתן לחלק את המסר בכל מספר. איך לבחור את זה? ישנם מספר פולינומים סטנדרטיים המשמשים לחישוב ה- CRC. לדוגמה, עבור CRC32 זה עשוי להיות 0x04C11DB7, ול CRC16 זה עשוי להיות 0x8005.
בנוסף, במרשם בתחילת החישוב, אתה יכול לכתוב לא אפסים, אלא מספר כלשהו אחר.
כמו כן, במהלך החישובים, מיד לפני הנפקת בדיקת CRC הסופית, ניתן לחלק אותם במספר אחר.
והדבר האחרון. בתים של ההודעה בעת כתיבה לרשם יכולים להיות ממוקמים כקיצור המשמעותי ביותר "קדימה", ולהיפך, הקטן ביותר.
שלב 5
בהתבסס על כל האמור לעיל, בוא נכתוב פונקציית. NET בסיסית המחשבת את בדיקת CRC על ידי לקיחת מספר פרמטרים שתיארתי לעיל והחזרת ערך ה- CRC כמספר לא חתום של 32 סיביות.
פונקציה משותפת ציבורית GetCrc (בתים ByVal בתור Byte (), ByVal פולי כ- Integer, רוחב ByVal אופציונלי כשלם = 32, ByVal initReg אופציונלי כ- Integer = & HFFFFFFFFUI, אופציונלי ByVal finalXor כמו UInteger = & HFFFFFFFFUI, אופציונלי ByVal Reverbean reverseCrc כמו בוליאני = נכון) כלא שלם
עמום רוחבInBytes כשלם = רוחב / 8
'השלם את רוחב ההודעה באפסים (חישוב בתים):
ReDim שמור על בתים (בתים. אורך - 1 + רוחבInBytes)
'צור תור קצת מההודעה:
עמום msgFifo כתור חדש (של בוליאני) (בתים. ספירה * 8 - 1)
עבור כל b בתור בתים בתים
עמעום בתור BitArray חדש ({b})
אם reverseBytes אז
עבור i בתור שלם = 0 עד 7
msgFifo. Enqueue (ba (i))
הַבָּא
אַחֵר
עבור i בתור שלם = 7 עד 0 שלב -1
msgFifo. Enqueue (ba (i))
הַבָּא
סיום אם
הַבָּא
'צור תור מבסיסי המילוי הראשוניים של המרשם:
עמום initBytes As Byte () = BitConverter. GetBytes (initReg)
עמום initBytesReversed כ- IEnumerable (Of Byte) = (From b As Byte In initBytes קח widthInBytes).
Dim initFifo בתור חדש (של בוליאני) (רוחב - 1)
עבור כל b בתור בתים ב- initBytesReversed
עמעום בתור BitArray חדש ({b})
אם לא reverseBytes אז
עבור i בתור שלם = 0 עד 7
initFifo. Enqueue (ba (i))
הַבָּא
אַחֵר
עבור i בתור שלם = 7 עד 0 שלב -1
initFifo. Enqueue (ba (i))
הַבָּא
סיום אם
הַבָּא
'Shift ו- XOR:
עמום רישום כ- UInteger = 0 'מלא את רישום סיביות הרוחב באפסים.
בצע בזמן msgFifo. Count> 0
עמום poppedBit כשלם = CInt (רישום >> (רוחב - 1)) ו- 1 'מגדירים לפני רישום משמרת.
עמום shiftedBit כמו Byte = Convert. ToByte (msgFifo. Dequeue)
אם initFifo. Count> 0 ואז
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
סיום אם
הרשמה = הרשמה << 1
register = register או shiftedBit
אם poppedBit = 1 ואז
רישום = רשום Xor poly
סיום אם
לוּלָאָה
'המרות אחרונות:
Dim crc As UInteger = register 'המרשם מכיל את שארית החלוקה == בדיקת סכום.
אם הפוךCrc ואז
crc = משקף (crc, רוחב)
סיום אם
crc = crc Xor finalXor
crc = crc ו- (& HFFFFFFFFUI >> (32 - רוחב)) 'מסווים את החלקים הפחות משמעותיים.
החזר crc
פונקציית סיום
