3.20. โปรโตคอลอนุกรม การกำหนดกรอบข้อมูล และ CRC

UART ในโค้ด ย้ายไบต์ระหว่างสองปลาย แต่เพียงอย่างเดียวนั้นไม่เพียงพอสำหรับการสร้างลิงก์ที่เชื่อถือได้ ปัญหาสามข้อจะปรากฏขึ้นทันทีที่มีอุปกรณ์จริงอยู่อีกด้านของสายไฟ

• ข้อความเริ่มต้นและสิ้นสุดที่ใด? ไบต์มาถึงเป็นสตรีมโดยไม่มีตัวคั่นในตัว หากผู้รับพลาดไบต์แรก (เปิดเครื่องหลังผู้ส่ง หรือมีสัญญาณรบกวนชั่วคราวบนสาย) ทุกไบต์หลังจากนั้นจะเคลื่อนออกทีละหนึ่ง จนกว่าผู้รับจะพบจุดซิงค์ใหม่

• แต่ละข้อความยาวเท่าใด? ข้อมูลจาก sensor ขนาด 32 ไบต์และการตอบสนองสถานะขนาด 4 ไบต์ดูเหมือนกันในระดับไบต์ ผู้รับต้องการวิธีรู้ว่ามีไบต์กี่ไบต์ที่อยู่ในข้อความปัจจุบัน

• ไบต์มาถึงครบถ้วนหรือไม่? สัญญาณรบกวนสามารถพลิกบิตแต่ละบิตได้ หากไม่มีการตรวจสอบ ผู้รับจะดำเนินการกับข้อมูลที่เสียหายโดยไม่รู้ตัว

คำตอบมาตรฐานสำหรับทั้งสามปัญหาคือการห่อข้อมูลไว้ในกรอบแพ็กเก็ต ได้แก่ ลำดับไบต์ที่รู้จักไว้ที่จุดเริ่มต้น ฟิลด์ความยาว ข้อมูลเพย์โหลดเอง และค่าตรวจสอบที่ท้าย

3.20.1. การกำหนดกรอบแพ็กเก็ต

รูปแบบการกำหนดกรอบโดยทั่วไป:

แพ็กเก็ตที่มีกรอบพร้อม CRC แยกสำหรับส่วนหัวและข้อมูล: ส่วนหัว (ไบต์มายากล) คำสั่ง ความยาว CRC ส่วนหัว เพย์โหลด CRC ข้อมูล

แต่ละฟิลด์ทำหน้าที่อย่างหนึ่ง:

• ส่วนหัว (ไบต์มายากล). ลำดับไบต์คงที่ที่ผิดปกติ -- มักเป็นสองไบต์เช่น 0xAA 0x55 -- ที่ผู้รับสแกนหาในสตรีมขาเข้า เมื่อพบลำดับนั้น ผู้รับรู้ว่าแพ็กเก็ตใหม่กำลังเริ่มต้นและสามารถทิ้งข้อมูลขยะที่มาก่อนได้

• คำสั่ง. ไบต์เดียวที่บอกว่าแพ็กเก็ตคืออะไร ค่าคำสั่งต่างกันใช้รูปแบบเพย์โหลดต่างกัน -- คำสั่งหนึ่งอาจหมายถึง "ตั้งมุมเซอร์โว" พร้อมเพย์โหลดสองไบต์ อีกคำสั่งหนึ่งอาจหมายถึง "อ่าน sensor" โดยไม่มีเพย์โหลด และอีกคำสั่งอาจเป็น "บันทึกข้อความ" พร้อมสตริง ผู้รับส่งต่อตามไบต์คำสั่งเพื่อรู้วิธีตีความส่วนที่เหลือของแพ็กเก็ต

• ความยาว. สองไบต์ที่ระบุขนาดของเพย์โหลดในหน่วยไบต์ (little-endian ที่นี่) ช่วยให้เพย์โหลดมีขนาดได้ถึงประมาณ 64 KiB ผู้รับอ่านจำนวนไบต์นี้อย่างแน่นอนเมื่อ CRC ส่วนหัวได้รับการยืนยันแล้ว

• CRC ส่วนหัว. ค่าตรวจสอบหนึ่งไบต์ครอบคลุมฟิลด์ HEADER, CMD และ LEN ผู้รับตรวจสอบก่อนอ่านเพย์โหลดใดๆ ดังนั้น LEN ที่เสียหายจะถูกตรวจพบหลังจากไบต์เพียงไม่กี่ไบต์ (ดูส่วน CRC ด้านล่างว่าทำไมเรื่องนี้จึงสำคัญ)

• เพย์โหลด. ข้อมูลแอปพลิเคชันเฉพาะคำสั่ง มีความยาวพอดี LEN ไบต์ รูปแบบถูกกำหนดโดยไบต์คำสั่ง ได้แก่ ระเบียนที่แพ็กด้วย struct สำหรับฟิลด์ความกว้างคงที่ สตริง หน่วยความจำดิบ -- อะไรก็ตามที่ทั้งสองฝ่ายตกลงกันสำหรับคำสั่งนั้น

• CRC ข้อมูล. CRC สี่ไบต์ครอบคลุมไบต์เพย์โหลด ผู้รับคำนวณใหม่จากไบต์ที่เพิ่งอ่านและทิ้งแพ็กเก็ตหากไม่ตรงกัน

3.20.2. CRC

"ค่าตรวจสอบ" ที่ง่ายที่สุดคือผลรวมของไบต์ทั้งหมด modulo 256 หรือ 65536 มันตรวจจับการพลิกบิตเดียวส่วนใหญ่ แต่พลาดข้อผิดพลาดหลายบิตจำนวนมากและไม่สนใจลำดับไบต์

การตรวจสอบความซ้ำซ้อนแบบวัฏจักร (CRC) คือการอัปเกรดมาตรฐาน โดยมันถือว่าอินพุตเป็นตัวเลขฐานสองยาวหนึ่งตัวและหาร (ด้วยวิธีพิเศษ) ด้วย พหุนาม คงที่ เศษที่เหลือจากการหารคือ CRC พหุนามต่างกันตรวจจับข้อผิดพลาดต่างประเภท พหุนาม 8-, 16- และ 32-บิตทั่วไปแต่ละตัวตรวจจับชุดข้อผิดพลาดทุกชุดที่สั้นกว่าความกว้างของมัน รวมถึงเศษส่วนขนาดใหญ่ของชุดที่ยาวกว่า

3.20.2.1. เหตุใดจึงต้องมี CRC สอง

แผนภาพแพ็กเก็ตด้านบนมี CRC แยก สอง ตัว -- ตัวหนึ่งครอบคลุมส่วนหัว (HEADER, CMD, LEN) และอีกตัวครอบคลุมเพย์โหลด นี่คือสิ่งที่การกำหนดกรอบที่แข็งแกร่งต้องการจริงๆ เนื่องจากวิธีที่ CRC เดียวที่ท้ายล้มเหลวเมื่อฟิลด์ LEN ถูกทำให้เสียหายระหว่างการส่ง:

• ผู้รับดำเนินการกับ LEN ที่เสียหายและอ่านไบต์จำนวนนั้นจากสาย -- อาจมากกว่าที่ผู้ส่งตั้งใจไว้มาก

• CRC ที่ท้ายบอกผู้รับในที่สุดว่ามีบางอย่างผิดพลาด และเฉพาะหลังจากที่ไบต์เหล่านั้นถูกใช้หมดแล้ว

• ในขณะที่ตัวแยกวิเคราะห์ติดค้างรอจำนวนไบต์ที่ผิด แพ็กเก็ตจริงที่มาหลังจากแพ็กเก็ตที่เสียหายจะถูกกลืนเป็นเพย์โหลด และผู้รับสูญเสียหลายแพ็กเก็ตแทนที่จะเป็นเพียงหนึ่งแพ็กเก็ต

การแยก CRC แก้ปัญหานี้:

• CRC ส่วนหัว ครอบคลุม HEADER, CMD และ LEN ผู้รับตรวจสอบก่อนอ่านเพย์โหลดใดๆ ดังนั้น LEN ที่เสียหายจะถูกตรวจพบหลังจากไบต์เพียงไม่กี่ไบต์ และตัวแยกวิเคราะห์จะซิงค์ใหม่ทันที โดยนำเพียงแพ็กเก็ตเสียหนึ่งแพ็กเก็ตออกไป

• CRC ข้อมูล ครอบคลุมเพย์โหลด เมื่อ CRC ส่วนหัวผ่านแล้ว ผู้รับรู้ว่าสามารถเชื่อถือ LEN ได้ อ่านไบต์เพย์โหลดตามจำนวนนั้นอย่างแน่นอน และยืนยันกับ CRC ข้อมูล

ขนาดทั่วไป -- และสิ่งที่หน้านี้ใช้ -- คือหนึ่งไบต์สำหรับ CRC ส่วนหัว (CRC-8 เพียงพอสำหรับส่วนหัวห้าไบต์) และสี่ไบต์สำหรับ CRC ข้อมูล (CRC-32 ครอบคลุมเพย์โหลดหลายกิโลไบต์ด้วยอัตราการชนกันที่ต่ำมาก)

3.20.2.2. ฟังก์ชันช่วยเหลือ

MicroPython มาพร้อมกับ binascii.crc32() สำหรับ CRC สี่ไบต์โดยตรง สำหรับ CRC ส่วนหัวหนึ่งไบต์ ฟังก์ชันช่วยเหลือขนาดเล็กที่ใช้พหุนามที่อุปกรณ์ 1-wire ของ Maxim ใช้ (0x8C ในรูปแบบสะท้อน) สั้นพอที่จะเขียนในบรรทัดเดียว:

def crc8(data: bytes) -> int:
    crc = 0
    for byte in data:
        crc ^= byte
        for _ in range(8):
            crc = (crc >> 1) ^ 0x8C if crc & 1 else crc >> 1
    return crc & 0xFF

ตัวเข้ารหัสที่สมบูรณ์รวม CRC ทั้งสองไว้ในฟังก์ชันเดียว:

import binascii
import struct

def encode_packet(cmd: int, payload: bytes) -> bytes:
    header = b"\xAA\x55" + bytes([cmd]) + struct.pack("<H", len(payload))
    hcrc   = crc8(header)
    dcrc   = binascii.crc32(payload)
    return header + bytes([hcrc]) + payload + struct.pack("<I", dcrc)

ฟังก์ชันผกผันกู้คืนคำสั่งและเพย์โหลดจากแพ็กเก็ตสมบูรณ์ หรือคืนค่า None หากการตรวจสอบ CRC ใดล้มเหลว:

def decode_packet(packet: bytes):
    # Layout: HEADER(2) + CMD(1) + LEN(2) + HCRC(1) + PAYLOAD(LEN) + DCRC(4)
    if len(packet) < 10 or packet[0:2] != b"\xAA\x55":
        return None

    header = packet[0:5]
    if crc8(header) != packet[5]:
        return None                       # header CRC mismatch

    cmd    = packet[2]
    length = struct.unpack("<H", packet[3:5])[0]
    if len(packet) != 6 + length + 4:
        return None                       # truncated or oversized

    payload       = packet[6:6 + length]
    received_dcrc = struct.unpack("<I", packet[6 + length:])[0]
    if binascii.crc32(payload) != received_dcrc:
        return None                       # data CRC mismatch

    return cmd, bytes(payload)

ในทางปฏิบัติ ผู้รับไม่ได้รับแพ็กเก็ตทั้งหมดในครั้งเดียว -- ไบต์มาถึงทีละตัวผ่าน UART และผู้ส่งที่หยุดกลางแพ็กเก็ต (หรือสายที่มีสัญญาณรบกวนที่ทำให้หายไปหนึ่งไบต์) ไม่สามารถเพียงแค่ read() เข้าบัฟเฟอร์ขนาดที่ถูกต้องได้ ส่วนถัดไปรันลอจิกการถอดรหัสเดียวกันทีละไบต์ในรูปแบบ state machine

3.20.3. ผู้รับแบบ State Machine

ผู้รับไม่สามารถเพียงแค่เรียก uart.read(N) สำหรับ N คงที่ -- มันไม่รู้ว่าแพ็กเก็ตถัดไปจะมีกี่ไบต์ และข้อมูลขยะใดๆ บนสายจะทำให้การจัดเรียงเสีย วิธีแก้คือ state machine ขนาดเล็กที่รับไบต์ทีละตัวและตอบสนองตามตำแหน่งที่อยู่ในแพ็กเก็ต ลูปหลักสำรวจ any() เพื่อดูว่ามีไบต์กี่ไบต์ที่บัฟเฟอร์อยู่ ดูดออกในการเรียก read() ครั้งเดียว และส่งแต่ละไบต์ผ่าน state machine:

import time
import binascii
import struct
from machine import UART

HEADER = b"\xAA\x55"
HEADER_LEN = len(HEADER)

# States, in the order the receiver walks through them per packet.
HUNT_FOR_HEADER = 0
READ_COMMAND    = 1
READ_LENGTH     = 2
READ_HEADER_CRC = 3
READ_PAYLOAD    = 4
READ_DATA_CRC   = 5

uart = UART(3, baudrate=115200)

# Receiver state plus partial-field buffers.
state        = HUNT_FOR_HEADER
matched      = 0              # bytes of HEADER matched so far
cmd          = 0              # CMD captured in READ_COMMAND
length_bytes = bytearray()    # raw LEN bytes (kept for the header CRC)
length       = 0              # unpacked LEN
payload      = bytearray()    # payload bytes accumulated in READ_PAYLOAD
crc_bytes    = bytearray()    # DCRC bytes accumulated in READ_DATA_CRC

def handle_packet(cmd: int, payload: bytes) -> None:
    print("cmd", cmd, "payload", payload)

while True:
    # Drain whatever bytes have arrived since the last poll. Idle
    # briefly when the line is quiet so the loop is not a busy spin.
    n = uart.any()
    if not n:
        time.sleep_ms(1)
        continue

    for b in uart.read(n):
        if state == HUNT_FOR_HEADER:
            # Walk the magic bytes. On a mismatch, back off by one
            # so a stray HEADER[0] in the noise still counts as a
            # possible start.
            if b == HEADER[matched]:
                matched += 1
                if matched == HEADER_LEN:
                    state = READ_COMMAND
                    matched = 0
            else:
                matched = 1 if b == HEADER[0] else 0

        elif state == READ_COMMAND:
            cmd = b
            length_bytes = bytearray()
            state = READ_LENGTH

        elif state == READ_LENGTH:
            # LEN is two bytes little-endian.
            length_bytes.append(b)
            if len(length_bytes) == 2:
                length = struct.unpack("<H", length_bytes)[0]
                state = READ_HEADER_CRC

        elif state == READ_HEADER_CRC:
            # Verify the CRC over HEADER + CMD + LEN before
            # committing to read LEN payload bytes. A mismatch
            # aborts here, after just five header bytes -- the
            # next valid header re-syncs quickly.
            expected = crc8(HEADER + bytes([cmd]) + length_bytes)
            if b == expected:
                payload = bytearray()
                state = READ_PAYLOAD
            else:
                state = HUNT_FOR_HEADER

        elif state == READ_PAYLOAD:
            payload.append(b)
            if len(payload) == length:
                crc_bytes = bytearray()
                state = READ_DATA_CRC

        elif state == READ_DATA_CRC:
            # Verify the CRC over the payload and either deliver
            # the packet or drop it. Either way, go back to
            # looking for the next header.
            crc_bytes.append(b)
            if len(crc_bytes) == 4:
                expected = binascii.crc32(payload)
                received = struct.unpack("<I", crc_bytes)[0]
                if expected == received:
                    handle_packet(cmd, bytes(payload))
                state = HUNT_FOR_HEADER

แต่ละไบต์ทำให้ state machine เดินหน้าหนึ่งขั้น หรือกลับไปที่ HUNT_FOR_HEADER หลังจากแพ็กเก็ตสมบูรณ์ CRC ส่วนหัวเสีย หรือ CRC ข้อมูลเสีย ข้อมูลขยะบนสายที่ไม่ตรงกับส่วนหัวจะถูกทิ้งอย่างเงียบๆ ส่วนหัวที่ถูกต้องถัดไปจะซิงค์ผู้รับใหม่ คุณสมบัติความปลอดภัยหลักมาจาก CRC ส่วนหัว: หากฟิลด์ LEN เสียหาย ตัวแยกวิเคราะห์จะตรวจพบหลังการตรวจสอบ CRC ส่วนหัว (ไบต์เพียงไม่กี่ไบต์) ไม่ใช่หลังจากยืนยันที่จะอ่านจำนวนไบต์เพย์โหลดที่ผิดพลาดอย่างมาก

3.20.4. นอกเหนือจากพื้นฐาน

การกำหนดกรอบข้างต้นเป็น ขั้นต่ำ ที่ลิงก์อนุกรมต้องการเพื่อกู้คืนจากสัญญาณรบกวนบนสาย: ไบต์มายากลส่วนหัว ความยาว คำสั่ง และ CRC สอง มันตรวจจับการเสียหายและซิงค์ใหม่หลังจากไบต์ที่ผิดพลาด แต่ยอมแพ้กับแพ็กเก็ตที่เสียหายแทนที่จะส่งผ่านได้ และทำให้ผู้ส่งไม่รู้ว่าผู้รับได้ยินอะไรจริงๆ

โปรโตคอลอนุกรมในโลกจริงเพิ่มลักษณะต่างๆ บนพื้นฐานนั้น ไม่ใช่ทุกลิงก์สำหรับอุปกรณ์ฝังตัวที่ต้องการทั้งหมด -- เลือกสิ่งที่แอปพลิเคชันต้องการจริงๆ:

• หมายเลขลำดับ. ตัวนับขนาดเล็กที่เพิ่มขึ้นทุกครั้งที่ส่ง ผู้รับตรวจจับช่องว่าง (แพ็กเก็ตหาย) รายการซ้ำ (ผู้ส่งส่งซ้ำแต่ผู้รับยอมรับสำเนาแรกไปแล้ว) และ -- ในกรณีที่ช่องสัญญาณสามารถเรียงลำดับใหม่ได้ -- การมาถึงที่ไม่เป็นลำดับ

• การยืนยัน. แพ็กเก็ต ACK เฉพาะ (หรือบิตพ่วงในการตอบกลับ) ที่ผู้รับส่งกลับมาเพื่อยืนยันแต่ละแพ็กเก็ต หากไม่มี ACK ผู้ส่งไม่มีทางรู้ว่าข้อมูลของมันมาถึงแล้ว

• การปฏิเสธแบบเชิงลบ. NACK ที่ส่งเมื่อผู้รับเห็นความล้มเหลวของ CRC หรือช่องว่างในลำดับ ผู้ส่งส่งซ้ำทันทีแทนที่จะรอให้หมดเวลา ACK

• การส่งซ้ำ. ผู้ส่งเก็บแต่ละแพ็กเก็ตที่ยังไม่ได้รับการยืนยันไว้ในคิวขนาดเล็กและส่งใหม่หลังจากหมดเวลา (หรือเมื่อได้รับ NACK) การจำกัดจำนวนครั้งลองซ้ำและการหน่วงระหว่างการลองซ้ำบางส่วนหยุดลิงก์ที่เสียอย่างถาวรไม่ให้วนลูปตลอดไป

• หน้าต่างเลื่อน. การอนุญาตให้มีแพ็กเก็ตหลายตัวในระหว่างบินก่อนที่จะต้องการ ACK ช่วยรักษาปริมาณงานที่ผ่านได้บนลิงก์ที่ round-trip ยาวนานเมื่อเทียบกับเวลาส่งต่อแพ็กเก็ต ต้นทุนคือสถานะฝั่งผู้ส่งเพิ่มเติม -- หนึ่งสล็อตต่อแพ็กเก็ตที่กำลังบิน

• การควบคุมการไหล. สัญญาณจากผู้รับบอกให้ผู้ส่งช้าลงหรือหยุดชั่วคราวเมื่อบัฟเฟอร์กำลังเต็ม การใช้งานแตกต่างกัน -- ไบต์ XON / XOFF ที่ชัดเจน การให้เครดิตที่ผู้รับอนุญาต N แพ็กเก็ตเพิ่มเติมต่อครั้ง หรือสาย RTS / CTS บนฮาร์ดแวร์ตัวสายเอง หากไม่มีการควบคุมการไหล ผู้ส่งที่เร็วในที่สุดจะล้นผู้รับที่ช้าและแพ็กเก็ตจะหล่น

• เวอร์ชันโปรโตคอล. ฟิลด์เวอร์ชันที่ต้นแพ็กเก็ตช่วยให้รูปแบบพัฒนาได้ แต่ละฝ่ายสามารถเจรจาเวอร์ชันสูงสุดที่ทั้งสองรองรับตอนเริ่มต้น หรือปฏิเสธแพ็กเก็ตจาก peer ที่ไม่เข้ากัน

• การแบ่งส่วนและการประกอบใหม่. LEN สองไบต์จำกัดแพ็กเก็ตที่ 64 KiB ข้อความที่ใหญ่กว่านั้นจะถูกแบ่งเป็นแพ็กเก็ตหลายตัวและประกอบใหม่ที่ปลายอีกด้าน ข้อมูลเมตาการแบ่งส่วน (ดัชนีส่วน จำนวนรวม หรือแฟล็ก "มีส่วนเพิ่มเติม") อยู่ในเพย์โหลด

• สัญญาณบอกอยู่. แพ็กเก็ตขนาดเล็กที่ส่งเป็นระยะบอกว่า "ฉันยังอยู่นี่" อีกฝ่ายสังเกตเห็นเมื่อสัญญาณหยุดและเชื่อมต่อใหม่ (หรือล้มเหลวอย่างชัดเจน) แทนที่จะค้างอยู่เงียบๆ

• ช่อง. ช่องหรือ ID สตรีมในส่วนหัว ทำให้ลิงก์ฟิสิคัลเดียวรองรับสตรีมลอจิคัลหลายสตรีม -- ช่องควบคุม ช่องข้อมูลการตรวจวัด ช่องบันทึก -- โดยแยกกันด้วยฟิลด์นั้นเท่านั้น

• การยืนยันตัวตน. แท็กสั้นที่คำนวณจากเพย์โหลดและค่าลับที่เฉพาะผู้ส่งและผู้รับที่ถูกต้องรู้เท่านั้น ผู้รับคำนวณแท็กอีกครั้งจากไบต์ที่ได้รับและปฏิเสธแพ็กเก็ตหากทั้งสองไม่ตรงกัน นี้ตรวจจับทั้งการดัดแปลง (ผู้โจมตีแก้ไขไบต์) และ -- หากหมายเลขลำดับหรือเวลาเป็นส่วนหนึ่งของสิ่งที่แท็กครอบคลุม -- การเล่นซ้ำ ที่ผู้โจมตีบันทึกแพ็กเก็ตจริงจากสายและส่งซ้ำในภายหลังเพื่อให้ผู้รับดำเนินการสองครั้ง

• การเข้ารหัส. การปนเปื้อนไบต์เพย์โหลดด้วยกุญแจลับร่วมกัน ทำให้ผู้ใดที่อ่านสายโดยไม่มีกุญแจนั้นเห็นแค่สัญญาณรบกวน มักรวมกับแท็กยืนยันตัวตนด้านบน -- หากไม่มีแท็ก ผู้โจมตีสามารถป้อนข้อมูลขยะที่บังเอิญผ่าน CRC และผู้รับเสียรอบในการพยายามถอดรหัสความไร้สาระ

โปรโตคอล "ที่ดี" โดยทั่วไปสำหรับอุปกรณ์อุตสาหกรรมจบลงด้วยการกำหนดกรอบ CRC คู่ หมายเลขลำดับ ACK / NACK พร้อมการส่งซ้ำ และสัญญาณบอกอยู่ ตัวอย่างในโลกจริงที่น่าสนใจ: MAVLink (ข้อมูลการตรวจวัดโดรน พร้อมหมายเลขลำดับ system / component ID และลายเซ็นแพ็กเก็ตเสริม) Modbus (PLC อุตสาหกรรม พร้อมรหัสฟังก์ชันและ CRC) และ NMEA 0183 (โปรโตคอล ASCII ที่ receiver GPS สำหรับผู้บริโภคทุกตัวใช้ -- ข้อความบนบรรทัดพร้อมค่าตรวจสอบหลังตัวคั่นดาว)