Как считать данные ошибки crc

1Теория, лежащая в основе расчёта CRC

Для начала давайте немного разберёмся в теории. Итак, что же такое CRC? Если кратко, это одна из разновидностей подсчёта контрольной суммы. Контрольная сумма – это метод проверки целостности принятой информации на стороне приёмника при передаче по каналам связи. Например, одна из простейших проверок – использование бита чётности. Это когда суммируются все биты передаваемого сообщения, и если сумма оказывается чётной, то в конец сообщения добавляется 0, если нечётной – то 1. При приёме также подсчитывается сумма битов сообщения, и сравнивается с принятым битом чётности. Если они отличаются, значит при передаче возникли ошибки, и передаваемая информация была искажена.

Но такой способ определения наличия ошибок – очень неинформативный и срабатывает не всегда, т.к. при искажении нескольких битов сообщения, чётность суммы может не измениться. Поэтому существует множество более «продвинутых» проверок, в том числе CRC.

По сути, CRC – это не сумма, а результат деления некого объёма информации (информационного сообщения) на константу, а точнее – остаток от деления сообщения на константу. Тем не менее, CRC исторически также называют «контрольная сумма». В значение CRC вносит вклад каждый бит сообщения. То есть, если хотя бы один бит исходного сообщения изменится при передаче, контрольная сумма тоже изменится, причём существенно. Это большой плюс такой проверки, так как он позволяет однозначно определить, исказилось исходное сообщение при передаче или нет.

Что такое исходное сообщение – понятно. Это непрерывная последовательность битов произвольной длины.

Что за константа, на которую мы должны делить исходное сообщение? Это некоторое число также любой длины, но обычно используются числа, кратные 1 байту – 8, 16 или 32 бита. Просто так легче считать, ведь компьютеры работают именно с байтами, а не с битами.

Константу-делитель обычно записывают в виде полинома (многочлена) вот таким образом: x⁸ + x² + x¹ + x⁰. Здесь степень числа «x» означает позицию бита-единицы в числе, начиная с нулевой, а старший разряд указывает на степень полинома и отбрасывается при интерпретации числа. То есть записанное ранее число – это не что иное как 100000111 в двоичной системе счисления.

Обычно при записи многочлена старший разряд подразумевается, но не пишется. То есть вышеуказанный многочлен можно было бы записать в двоичной системе как (1)00000111. В скобках я указал подразумеваемый старший разряд числа. Поэтому говорят, что многочлен равен 7 в десятичной системе счисления (111b = 7d).

Вот ещё пример: (x¹⁶ +) x¹⁵ + x² + x⁰ = (1)1000000000000101 = 0x8005 = 32773.

Обычно используются некие стандартные многочлены для разных типов CRC. Вот некоторые из них:

В посвящённой расчёту CRC статье на Википедии есть большая таблица образующих полиномов.

Так как же считать контрольную сумму? Существует базовый метод – деление сообщения на полином «в лоб» – и его модификации в целях уменьшения количества вычислений и, соответственно, ускорения расчёта CRC. Для начала мы рассмотрим именно базовый метод.

В общем виде деление числа на многочлен выполняется по такому алгоритму. Алгоритм вычисления контрольной суммы CRC:

1. Создаётся массив (регистр), заполненный нулями, равный по длине разрядности (степени) полинома.
2. Исходное сообщение дополняется нулями в младших разрядах, в количестве, равном числу разрядов полинома.
3. В младший разряд регистра заносится один старший бит сообщения, а из старшего разряда регистра выдвигается один бит.
4. Если выдвинутый бит равен «1», то производится инверсия битов (операция XOR, исключающее ИЛИ) в тех разрядах регистра, которые соответствуют единицам в полиноме.
5. Если в сообщении ещё есть биты, переходим к шагу 3).
6. Когда все биты сообщения поступили в регистр и были обработаны этим алгоритмом, в регистре остаётся остаток от деления, который и является контрольной суммой CRC.

Назовём этот метод расчёта CRC метод побитового сдвига или простой метод.

Рисунок иллюстрирует деление исходной последовательности битов на число (1)00000111, или многочлен x⁸ + x² + x¹ + x⁰.

Кстати, проверить правильность расчёта CRC очень просто. В пункте (2) описанного алгоритма мы должны вместо дополнения исходного сообщения нулями дополнить его битами рассчитанной контрольной суммы, а остальное оставить как есть. Теперь остаток от деления дополненного сообщения на полином должен равняться нулю – это и есть признак верно рассчитанной контрольной суммы. Отличный от нуля остаток свидетельствует об ошибке.

Осталась ещё пара моментов, о которых стоит сказать. Как вы могли заметить, сообщение можно разделить на любое число. Как его выбрать? Существует ряд стандартных полиномов, которые используются при вычислении CRC. Например, для CRC32 это может быть число 0x04C11DB7, а для CRC16 это может быть 0x8005.

Кроме того, в регистр в начале вычислений можно записать не нули, а какое-то другое число. (И это рекомендуется делать: так повышается надёжность определения начала передачи сообщения, если, например, сообщение имеет в начале нулевые биты).

Также при расчётах непосредственно перед выдачей финальную контрольную сумму CRC можно поделить на какое-то другое число.

И последнее. Байты сообщения при записи в регистр могут помещаться как старшим битом «вперёд», так и наоборот, младшим. И результирующая CRC также может выдаваться, начиная со старшего бита или с младшего.

Изменение порядка битов в байте на обратный назовём «обращение», «реверс» или «отзеркаливание» байта.

Итого имеются 6 параметров, которые влияют на значение контрольной суммы:

• порядок CRC;
• образующий многочлен (его иногда называют «генераторный полином», переводя с английского буквально);
• начальное содержимое регистра;
• значение, с которым производится финальное XOR;
• реверс байтов информационного сообщения;
• реверс байтов CRC перед финальным XOR.

2Расчёт контрольной суммы CRC методом побитового сдвига

На основании всего вышеизложенного, давайте напишем функцию на языке Visual Basic .NET, которая будет рассчитывать контрольную сумму CRC, принимая ряд параметров, которые я описал выше, и возвращая значение CRC в виде 32-разрядного беззнакового числа.

Код расчёта CRC методом побитового сдвига на языке VB.NET

''' <summary>
''' Возвращает контрольную сумму типа CRC, рассчитанную методом побитового сдвига.
''' </summary>
''' <param name="bytes">Входная последовательность байтов (исходное сообщение).</param>
''' <param name="poly">Образующий многочлен разрядности <paramref name="width">width</paramref>.</param>
''' <param name="width">Порядок CRC в битах, 8/16/32.</param>
Public Shared Function GetCrc_Simple(ByVal bytes As Byte(), ByVal poly As UInteger, Optional ByVal width As Integer = 32, Optional ByVal initReg As UInteger = &HFFFFFFFFUI, Optional ByVal finalXor As UInteger = &HFFFFFFFFUI, Optional ByVal reverseBytes As Boolean = True, Optional ByVal reverseCrc As Boolean = True) As UInteger

  Dim widthInBytes As Integer = width  8
  
  'Дополняем сообщение width нулями (расчёт в байтах):
  ReDim Preserve bytes(bytes.Length - 1 + widthInBytes)
  
  'Создаём очередь битов из сообщения:
  Dim msgFifo As New Queue(Of Boolean)(bytes.Count * 8 - 1)
  For Each b As Byte In bytes
    Dim ba As New BitArray({b})
    If reverseBytes Then
      For i As Integer = 0 To 7
          msgFifo.Enqueue(ba(i))
      Next
    Else
      For i As Integer = 7 To 0 Step -1
          msgFifo.Enqueue(ba(i))
      Next
    End If
  Next
  
  'Создаём очередь из битов начального заполнения регистра:
  Dim initBytes As Byte() = BitConverter.GetBytes(initReg)
  Dim initBytesReversed As IEnumerable(Of Byte) = (From b As Byte In initBytes Take widthInBytes).Reverse
  Dim initFifo As New Queue(Of Boolean)(width - 1)
  For Each b As Byte In initBytesReversed
    Dim ba As New BitArray({b})
    If Not reverseBytes Then
       For i As Integer = 0 To 7
           initFifo.Enqueue(ba(i))
       Next
    Else
      For i As Integer = 7 To 0 Step -1
          initFifo.Enqueue(ba(i))
      Next
    End If
  Next
  
  'Сдвиг и XOR:
  Dim register As UInteger = 0 'заполняем width-разрядный регистр нулями.
  Do While msgFifo.Count > 0
    
    Dim poppedBit As Integer = CInt(register >> (width - 1)) And 1 'определить перед сдвигом регистра.
    
    Dim shiftedBit As Byte = Convert.ToByte(msgFifo.Dequeue)
    If initFifo.Count > 0 Then
      Dim b As Byte = Convert.ToByte(initFifo.Dequeue)
      shiftedBit = shiftedBit Xor b
    End If
    
    register = register << 1
    register = register Or shiftedBit
    
    If poppedBit = 1 Then
      register = register Xor poly
    End If
  Loop
  
  'Финальные преобразования:
  Dim crc As UInteger = register 'Регистр содержит остаток от деления - контрольную сумму.
  If reverseCrc Then
    crc = reflect(crc, width)
  End If
  crc = crc Xor finalXor
  crc = crc And (&HFFFFFFFFUI >> (32 - width)) 'маскируем младшие разряды.
  
  Return crc

End Function

''' <summary>
''' Обращает заданное число младших битов переданного числа.
''' </summary>
''' <param name="inpValue">Число, которое требуется «отзеркалить».</param>
''' <param name="bitsToReflect">Сколько младших битов обратить, 0..32.</param>
''' <returns></returns>
''' <remarks>Например: reflect(&H3E23, 3) == &H3E26.</remarks>
Private Shared Function reflect(ByVal inpValue As UInteger, Optional ByVal bitsToReflect As Integer = 32) As UInteger
    Dim t As UInteger = inpValue
    Dim reflected As UInteger = inpValue
    For i As Integer = 0 To bitsToReflect - 1
        Dim bm As UInteger = bitMask(bitsToReflect - 1 - i)
        If (t And 1) = 1 Then
            reflected = reflected Or bm
        Else
            reflected = reflected And Not bm
        End If
        t >>= 1
    Next
    Return reflected
End Function

''' <summary>
''' Возвращает наибольший разряд числа.
''' </summary>
''' <param name="number">Число, разрядность которого следует определить.</param>
''' <returns></returns>
Private Shared Function bitMask(ByVal number As Integer) As UInteger
    Dim res As UInteger = (1UI << number)
    Return res
End Function

Как вы могли заметить, в данной реализации расчёта CRC используется LINQ, так что соответствующая ссылка должна быть добавлена в проект.

Предлагаемая программа плохо масштабируема. То есть она работает хорошо при вычислении контрольной суммы CRC для коротких сообщений, длиной до нескольких десятков килобайтов. Я писал её с целью только продемонстрировать работу простого алгоритма, и не занимался оптимизацией. При расчёте CRC для длинного сообщения, размером десятки или сотни мегабайтов, программа будет сильно загружать процессор и память, т.к. всё сообщение целиком загружается в очередь. Этому способствует метод преобразования числа в битовую последовательность, используя Queue(Of Boolean). Для работы с такими большими сообщениями желательно реализовать промежуточный буфер, который будет передавать сообщение в программу небольшими порциями.

Зато у этой программы есть одно преимущество: она может быть использована для расчёта CRC любого порядка, не обязательно 8, 16 или 32. Это может быть CRC5 или CRC49. Только для чисел больше 32-х разрядов нужно изменить соответствующим образом входные параметры – допустим, poly передавать не как UInteger, а как ULong, или передавать его в виде битового массива (тогда теоретически порядок CRC вообще будет неограничен).

3Расчёт контрольной суммы CRC табличным методом

Для сокращения числа вычислений из предыдущего метода – метода побитового сдвига – придуманы некоторые оптимизации.

В частности, сдвигают не по одному биту за раз, а сразу по несколько. Наибольшую популярность снискали варианты, в которых сообщение сдвигается на число битов, кратное числу битов в байте: 8, 16 или 32, т.к. с байтами легче работать (не нужны дополнительные преобразования). При этом идея алгоритма осталась та же: сдвиг и исключающее ИЛИ с содержимым регистра.

Кроме того, оказывается, что часть расчётов можно провести заранее и записать в массив – таблицу, из которой по мере необходимости будет браться нужное число. Такой метод расчёта назвали табличный метод расчёта CRC.

Я не буду здесь вдаваться в теорию, она довольно сложна и много раз описана в других статьях. В частности, очень хорошее и подробное описание бинарной арифметики, лежащей в основе расчёта CRC, и описание табличного метода, даётся в статье Ross N. Williams: «A Painless Guide to CRC Error Detection Algorithms». Рекомендую к прочтению обязательно! Оригинальный текст – в приложении к статье, а русский перевод легко найти в интернете.

Ну что же, пришло время для самой программы. Она будет несколько длиннее предыдущей. По сути, это реализация алгоритма из указанной статьи в стиле объектно-ориентированного программирования. Опять же будем писать программу на моём любимом языке программирования VB.NET. Я назвал этот класс RocksoftCrcModel, по названию компании, в которой работал автор указанной статьи.

Код расчёта CRC табличным методом на языке VB.NET

    ''' <summary>
    ''' Реализует алгоритм расчёта CRC методом Rocksoft^tm Model CRC.
    ''' </summary>
    Public Class RocksoftCrcModel

#Region "PROPS AND FIELDS"

        ''' <summary>
        ''' Таблица предвычисленных значений для расчёта контрольной суммы.
        ''' </summary>
        Public ReadOnly CrcLookupTable(255) As UInteger

        ''' <summary>
        ''' Порядок CRC, в битах (строго 8, 16 или 32).
        ''' Изменение этого свойства ведёт к пересчёту таблицы.
        ''' </summary>
        Public Property CrcWidth As Integer
            Get
                Return _CrcWidth
            End Get
            Set(value As Integer)
                If _CrcWidth <> value Then
                    _CrcWidth = value
                    _TopBit = getBitMask(_CrcWidth - 1)
                    _WidMask = (((1UI << (_CrcWidth - 1)) - 1UI) << 1) Or 1UI
                    generateLookupTable()
                End If
            End Set
        End Property
        Private _CrcWidth As Integer = 32

        ''' <summary>
        ''' Образующий многочлен.
        ''' Изменение этого свойства ведёт к пересчёту таблицы.
        ''' </summary>
        Public Property Polynom As UInteger
            Get
                Return _Polynom
            End Get
            Set(value As UInteger)
                If _Polynom <> value Then
                    _Polynom = value
                    generateLookupTable()
                End If
            End Set
        End Property
        Private _Polynom As UInteger = &H4C11DB7

        ''' <summary>
        ''' Обращать ли байты сообщения?
        ''' Изменение этого свойства ведёт к пересчёту таблицы.
        ''' </summary>
        Public Property ReflectIn As Boolean
            Get
                Return _ReflectIn
            End Get
            Set(value As Boolean)
                If _ReflectIn <> value Then
                    _ReflectIn = value
                    generateLookupTable()
                End If
            End Set
        End Property
        Private _ReflectIn As Boolean = True

        ''' <summary>
        ''' Начальное содержимое регистра.
        ''' </summary>
        Public Property InitRegister As UInteger
            Get
                Return _InitRegister
            End Get
            Set(value As UInteger)
                If _InitRegister <> value Then
                    _InitRegister = value
                End If
            End Set
        End Property
        Private _InitRegister As UInteger = &HFFFFFFFFUI

        ''' <summary>
        ''' Обращать выходное значение CRC?
        ''' </summary>
        Public Property ReflectOut As Boolean
            Get
                Return _ReflectOut
            End Get
            Set(value As Boolean)
                If _ReflectOut <> value Then
                    _ReflectOut = value
                End If
            End Set
        End Property
        Private _ReflectOut As Boolean = True

        ''' <summary>
        ''' Значение, с которым XOR-ится выходное значение CRC.
        ''' </summary>
        Public Property XorOut As UInteger
            Get
                Return _XorOut
            End Get
            Set(value As UInteger)
                If _XorOut <> value Then
                    _XorOut = value
                End If
            End Set
        End Property
        Private _XorOut As UInteger = &HFFFFFFFFUI

#End Region '/PROPS AND FIELDS

#Region "READ-ONLY PROPS"

        ''' <summary>
        ''' Возвращает старший разряд полинома.
        ''' </summary>
        ReadOnly Property TopBit As UInteger
            Get
                Return _TopBit
            End Get
        End Property
        Private _TopBit As UInteger = getBitMask(CrcWidth - 1)

        ''' <summary>
        ''' Возвращает длинное слово со значением (2^width)-1.
        ''' </summary>
        Private ReadOnly Property WidMask As UInteger
            Get
                Return _WidMask
            End Get
        End Property
        Private _WidMask As UInteger = (((1UI << (CrcWidth - 1)) - 1UI) << 1) Or 1UI

#End Region '/READ-ONLY PROPS

#Region "CTOR"

        ''' <summary>
        ''' Конструктор, инициализированный параметрами по умолчанию для алгоритма CRC32.
        ''' </summary>
        Public Sub New()
            generateLookupTable()
        End Sub

        ''' <summary>
        ''' Инициализирует новый экземпляр параметрической модели CRC с настраиваемыми параметрами.
        ''' </summary>
        ''' <param name="width">Разрядность контрольной суммы в битах.</param>
        ''' <param name="poly">Полином.</param>
        ''' <param name="initReg">начальное содержимое регистра.</param>
        ''' <param name="isReflectIn">Обращать ли входящие байты сообщения?</param>
        ''' <param name="isReflectOut">Обратить ли CRC перед финальным XOR.</param>
        ''' <param name="xorOut">Конечное значение XOR.</param>
        Public Sub New(ByVal width As Integer, ByVal poly As UInteger, Optional ByVal initReg As UInteger = &HFFFFFFFFUI, Optional ByVal isReflectIn As Boolean = True, Optional ByVal isReflectOut As Boolean = True, Optional ByVal xorOut As UInteger = &HFFFFFFFFUI)
            Me.CrcWidth = width
            Me.Polynom = poly
            Me.InitRegister = initReg
            Me.ReflectIn = isReflectIn
            Me.ReflectOut = isReflectOut
            Me.XorOut = xorOut
            generateLookupTable()
        End Sub

#End Region '/CTOR

#Region "ВЫЧИСЛЕНИЕ CRC"

        ''' <summary>
        ''' Вычисляет значение контрольной суммы переданного сообщения.
        ''' </summary>
        ''' <param name="message">Исходное сообщение, для которого нужно посчитать контрольную сумму.</param>
       Public Function ComputeCrc(ByRef message As Byte()) As UInteger
            Dim registerContent As UInteger = InitRegister 'Содержимое регистра в процессе пересчёта CRC.
            For Each b As Byte In message
                registerContent = getNextRegisterContent(registerContent, b)
            Next
            Dim finalCrc As UInteger = getFinalCrc(registerContent)
            Return finalCrc
        End Function

        ''' <summary>
        ''' Вычисляет значение контрольной суммы переданного сообщения и возвращает его в виде массива байтов.
        ''' </summary>
        ''' <param name="message">Исходное сообщение, для которого нужно посчитать контрольную сумму.</param>
        Public Function ComputeCrcAsBytes(ByRef message As Byte()) As Byte()
            Dim crc As UInteger = ComputeCrc(message)
            Dim crcBytes As Byte() = BitConverter.GetBytes(crc)
            Dim crcBytesOrdered(crcBytes.Length - 1) As Byte
            For i As Integer = 0 To crcBytes.Length - 1
                crcBytesOrdered(i) = crcBytes(crcBytes.Length - 1 - i)
            Next
            Return crcBytesOrdered
        End Function

        ''' <summary>
        ''' Обрабатывает один байт сообщения (0..255).
        ''' </summary>
        ''' <param name="prevRegContent">Содержимое регистра на предыдущем шаге.</param>
        ''' <param name="value">Значение очередного байта из сообщения.</param>
        Private Function getNextRegisterContent(ByVal prevRegContent As UInteger, ByVal value As Byte) As UInteger
            Dim uValue As UInteger = value
            If ReflectIn Then
                uValue = reflect(uValue, 8)
            End If
            Dim reg As UInteger = prevRegContent
            reg = reg Xor (uValue << (CrcWidth - 8))
            For i As Integer = 0 To 7
                If (reg And TopBit) = TopBit Then
                    reg = (reg << 1) Xor Polynom
                Else
                    reg <<= 1
                End If
                reg = reg And WidMask()
            Next
            Return reg
        End Function

        ''' <summary>
        ''' Возвращает значение CRC для обработанного сообщения.
        ''' </summary>
        ''' <param name="regContent">Значение регистра до финального обращения и XORа.</param>
        Private Function getFinalCrc(ByVal regContent As UInteger) As UInteger
            If ReflectOut Then
                Dim res As UInteger = XorOut Xor reflect(regContent, CrcWidth)
                Return res
            Else
                Dim res As UInteger = XorOut Xor regContent
                Return res
            End If
        End Function

#End Region '/ВЫЧИСЛЕНИЕ CRC

#Region "РАСЧЁТ ТАБЛИЦЫ"

        ''' <summary>
        ''' Вычисляет таблицу предвычисленных значений для расчёта контрольной суммы.
        ''' </summary>
        Private Sub generateLookupTable()
            For i As Integer = 0 To 255
                CrcLookupTable(i) = generateTableItem(i)
            Next
        End Sub

        ''' <summary>
        ''' Рассчитывает один байт таблицы значений для расчёта контрольной суммы
        ''' по алгоритму Rocksoft^tm Model CRC Algorithm.
        ''' </summary>
        ''' <param name="index">Индекс записи в таблице, 0..255.</param>
        Private Function generateTableItem(ByVal index As Integer) As UInteger

            Dim inbyte As UInteger = CUInt(index)

            If ReflectIn Then
                inbyte = reflect(inbyte, 8)
            End If

            Dim reg As UInteger = inbyte << (CrcWidth - 8)

            For i As Integer = 0 To 7
                If (reg And TopBit) = TopBit Then
                    reg = (reg << 1) Xor Polynom
                Else
                    reg <<= 1
                End If
            Next

            If ReflectIn Then
                reg = reflect(reg, CrcWidth)
            End If

            Dim res As UInteger = reg And WidMask
            Return res

        End Function

#End Region '/РАСЧЁТ ТАБЛИЦЫ

#Region "ВСПОМОГАТЕЛЬНЫЕ"

        ''' <summary>
        ''' Возвращает наибольший разряд числа.
        ''' </summary>
        ''' <param name="number">Число, разрядность которого следует определить, степень двойки.</param>
        Private Function getBitMask(ByVal number As Integer) As UInteger
            Dim res As UInteger = 1UI << number
            Return res
        End Function

        ''' <summary>
        ''' Обращает заданное число младших битов переданного числа.
        ''' </summary>
        ''' <param name="value">Число, которое требуется обратить («отзеркалить»).</param>
        ''' <param name="bitsToReflect">Сколько младших битов числа обратить, 0..32.</param>
        ''' <remarks>Например: reflect(0x3E23, 3) == 0x3E26.</remarks>
        Private Function reflect(ByVal value As UInteger, Optional ByVal bitsToReflect As Integer = 32) As UInteger
            Dim t As UInteger = value
            Dim reflected As UInteger = value
            For i As Integer = 0 To bitsToReflect - 1
                Dim bm As UInteger = getBitMask(bitsToReflect - 1 - i)
                If (t And 1) = 1 Then
                    reflected = reflected Or bm
                Else
                    reflected = reflected And Not bm
                End If
                t >>= 1
            Next
            Return reflected
        End Function

#End Region '/ВСПОМОГАТЕЛЬНЫЕ

    End Class 

Этот код полностью готов к использованию, можно брать и применять. Пользоваться данной программой так:

• создать экземпляр класса RocksoftCrcModel(), передав в конструктор параметры модели CRC;
• для расчёта контрольной суммы, вызвать метод данного объекта ComputeCrc() или ComputeCrcAsBytes(), передав в качестве параметра информационное сообщение, для которого необходимо посчитать контрольную сумму;
• если меняются параметры модели CRC, таблица автоматически пересчитывается, и новый экземпляр класса можно не создавать.

Приведу пример использования данного класса для алгоритма CRC16. В качестве сообщения message будем использовать массив байтов, который представляет собой строку «123456789» в коде ASCII, которая используется во многих онлайн-калькуляторах CRC:

Dim crcModel As New RocksoftCrcModel(16, &H8005, 0, True, True, 0)
Dim message as Byte() = {&H31, &H32, &H33, &H34, &H35, &H36, &H37, &H38, &H39}
Dim crc As UInteger = crcModel.ComputeCrc(message)

Данная реализация расчёта CRC была проверена мною путём сличения со многими онлайн-калькуляторами CRC (назовём это «слабой» проверкой, именно такое определение дано в вышеуказанной статье, когда проверка осуществляется на основании сравнения рассчитанной контрольной суммы с эталонной, при одинаковых исходных параметрах и сообщении).

Для любителей C# перепишем данный класс таким образом:

Код расчёта CRC табличным методом на языке C# (разворачивается)

using System;

namespace CRC
{
  /// <summary>Реализует алгоритм расчёта CRC методом Rocksoft^tm Model CRC.</summary>
  public class RocksoftCrcModel
  {
    /// <summary>Таблица предвычисленных значений для расчёта контрольной суммы.</summary>
    public readonly uint[] CrcLookupTable;
    private int _CrcWidth;
    private uint _Polynom;
    private bool _ReflectIn;
    private uint _InitRegister;
    private bool _ReflectOut;
    private uint _XorOut;
    private uint _TopBit;
    private uint _WidMask;

    /// <summary>
    /// Порядок CRC, в битах (8/16/32).
    /// Изменение этого свойства ведёт к пересчёту таблицы.
    /// </summary>
    public int CrcWidth
    {
      get
      {
        return this._CrcWidth;
      }
      set
      {
        if (this._CrcWidth == value)
          return;
        this._CrcWidth = value;
        this._TopBit = this.getBitMask(checked (this._CrcWidth - 1));
        this._WidMask = (uint) ((int) checked (unchecked ((uint) (1 << checked (this._CrcWidth - 1))) - 1U) << 1 | 1);
        this.generateLookupTable();
      }
    }

    /// <summary>
    /// Образующий многочлен.
    /// Изменение этого свойства ведёт к пересчёту таблицы.
    /// </summary>
    public uint Polynom
    {
      get
      {
        return this._Polynom;
      }
      set
      {
        if ((int) this._Polynom == (int) value)
          return;
        this._Polynom = value;
        this.generateLookupTable();
      }
    }

    /// <summary>
    /// Обращать байты сообщения?
    /// Изменение этого свойства ведёт к пересчёту таблицы.
    /// </summary>
    public bool ReflectIn
    {
      get
      {
        return this._ReflectIn;
      }
      set
      {
        if (this._ReflectIn == value)
          return;
        this._ReflectIn = value;
        this.generateLookupTable();
      }
    }

    /// <summary>Начальное содержимое регистра.</summary>
    public uint InitRegister
    {
      get
      {
        return this._InitRegister;
      }
      set
      {
        if ((int) this._InitRegister == (int) value)
          return;
        this._InitRegister = value;
      }
    }

    /// <summary>Обращать выходное значение CRC?</summary>
    public bool ReflectOut
    {
      get
      {
        return this._ReflectOut;
      }
      set
      {
        if (this._ReflectOut == value)
          return;
        this._ReflectOut = value;
      }
    }

    /// <summary>Значение, с которым XOR-ится выходное значение CRC.</summary>
    public uint XorOut
    {
      get
      {
        return this._XorOut;
      }
      set
      {
        if ((int) this._XorOut == (int) value)
          return;
        this._XorOut = value;
      }
    }

    /// <summary>Возвращает старший разряд полинома.</summary>
    public uint TopBit
    {
      get
      {
        return this._TopBit;
      }
    }

    /// <summary>Возвращает длинное слово со значением (2^width)-1.</summary>
    /// <returns></returns>
    /// <remarks></remarks>
    private uint WidMask
    {
      get
      {
        return this._WidMask;
      }
    }

    /// <summary>
    /// Конструктор, инициализированный параметрами по умолчанию для алгоритма CRC32.
    /// </summary>
    public RocksoftCrcModel()
    {
      base..ctor();
      this.CrcLookupTable = new uint[256];
      this._CrcWidth = 32;
      this._Polynom = 79764919U;
      this._ReflectIn = true;
      this._InitRegister = uint.MaxValue;
      this._ReflectOut = true;
      this._XorOut = uint.MaxValue;
      this._TopBit = this.getBitMask(checked (this.CrcWidth - 1));
      this._WidMask = (uint) ((int) checked (unchecked ((uint) (1 << checked (this.CrcWidth - 1))) - 1U) << 1 | 1);
      this.generateLookupTable();
    }

    /// <summary>
    /// Инициализирует новый экземпляр параметрической модели CRC с настраиваемыми параметрами.
    /// </summary>
    /// <param name="width">Разрядность контрольной суммы в битах.</param>
    /// <param name="poly">Полином.</param>
    /// <param name="initReg">начальное содержимое регистра.</param>
    /// <param name="isReflectIn">Обращать ли входящие байты сообщения?</param>
    /// <param name="isReflectOut">Обратить ли CRC перед финальным XOR.</param>
    /// <param name="xorOut">Конечное значение XOR.</param>
    public RocksoftCrcModel(int width, uint poly, uint initReg = 4294967295, bool isReflectIn = true, bool isReflectOut = true, uint xorOut = 4294967295)
    {
      base..ctor();
      this.CrcLookupTable = new uint[256];
      this._CrcWidth = 32;
      this._Polynom = 79764919U;
      this._ReflectIn = true;
      this._InitRegister = uint.MaxValue;
      this._ReflectOut = true;
      this._XorOut = uint.MaxValue;
      this._TopBit = this.getBitMask(checked (this.CrcWidth - 1));
      this._WidMask = (uint) ((int) checked (unchecked ((uint) (1 << checked (this.CrcWidth - 1))) - 1U) << 1 | 1);
      this.CrcWidth = width;
      this.Polynom = poly;
      this.InitRegister = initReg;
      this.ReflectIn = isReflectIn;
      this.ReflectOut = isReflectOut;
      this.XorOut = xorOut;
      this.generateLookupTable();
    }

    /// <summary>Вычисляет значение контрольной суммы переданного сообщения.</summary>
    /// <param name="message">Исходное сообщение, для которого нужно посчитать контрольную сумму.</param>
    /// <returns></returns>
    public uint ComputeCrc(ref byte[] message)
    {
      uint num1 = this.InitRegister;
      byte[] numArray = message;
      int index = 0;
      while (index < numArray.Length)
      {
        byte num2 = numArray[index];
        num1 = this.getNextRegisterContent(num1, num2);
        checked { ++index; }
      }
      return this.getFinalCrc(num1);
    }

    /// <summary>
    /// Вычисляет значение контрольной суммы переданного сообщения и возвращает его в виде массива байтов.
    /// </summary>
    /// <param name="message">Исходное сообщение, для которого нужно посчитать контрольную сумму.</param>
    /// <returns></returns>
    public byte[] ComputeCrcAsBytes(byte[] message)
    {
      byte[] bytes = BitConverter.GetBytes(this.ComputeCrc(ref message));
      byte[] numArray = new byte[checked (bytes.Length - 1 + 1)];
      int num1 = 0;
      int num2 = checked (bytes.Length - 1);
      int index = num1;
      while (index <= num2)
      {
        numArray[index] = bytes[checked (bytes.Length - 1 - index)];
        checked { ++index; }
      }
      return numArray;
    }

    /// <summary>Обрабатывает один байт сообщения (0..255).</summary>
    /// <param name="prevRegContent">Содержимое регистра на предыдущем шаге.</param>
    /// <param name="value">Значение очередного байта из сообщения.</param>
    private uint getNextRegisterContent(uint prevRegContent, byte value)
    {
      uint num1 = (uint) value;
      if (this.ReflectIn)
        num1 = this.reflect(num1, 8);
      uint num2 = prevRegContent ^ num1 << checked (this.CrcWidth - 8);
      int num3 = 0;
      do
      {
        num2 = (((int) num2 & (int) this.TopBit) != (int) this.TopBit ? num2 << 1 : num2 << 1 ^ this.Polynom) & this.WidMask;
        checked { ++num3; }
      }
      while (num3 <= 7);
      return num2;
    }

    /// <summary>Возвращает значение CRC для обработанного сообщения.</summary>
    /// <param name="regContent">Значение регистра до финального обращения и XORа.</param>
    /// <returns></returns>
    private uint getFinalCrc(uint regContent)
    {
      if (this.ReflectOut)
        return this.XorOut ^ this.reflect(regContent, this.CrcWidth);
      return this.XorOut ^ regContent;
    }

    /// <summary>Вычисляет таблицу предвычисленных значений для расчёта контрольной суммы.</summary>
    private void generateLookupTable()
    {
      int index = 0;
      do
      {
        this.CrcLookupTable[index] = this.generateTableItem(index);
        checked { ++index; }
      }
      while (index <= (int) byte.MaxValue);
    }

    /// <summary>
    /// Рассчитывает один байт таблицы значений для расчёта контрольной суммы
    /// по алгоритму Rocksoft^tm Model CRC Algorithm.
    /// </summary>
    /// <param name="index">Индекс записи в таблице, 0..255.</param>
    private uint generateTableItem(int index)
    {
      uint num1 = checked ((uint) index);
      if (this.ReflectIn)
        num1 = this.reflect(num1, 8);
      uint num2 = num1 << checked (this.CrcWidth - 8);
      int num3 = 0;
      do
      {
        if (((int) num2 & (int) this.TopBit) == (int) this.TopBit)
          num2 = num2 << 1 ^ this.Polynom;
        else
          num2 <<= 1;
        checked { ++num3; }
      }
      while (num3 <= 7);
      if (this.ReflectIn)
        num2 = this.reflect(num2, this.CrcWidth);
      return num2 & this.WidMask;
    }

    /// <summary>Возвращает наибольший разряд числа.</summary>
    /// <param name="number">Число, разрядность которого следует определить, степень двойки.</param>
    /// <returns></returns>
    private uint getBitMask(int number)
    {
      return (uint) (1 << number);
    }

    /// <summary>Обращает заданное число младших битов переданного числа.</summary>
    /// <param name="value">Число, которое требуется обратить ("отзеркалить").</param>
    /// <param name="bitsToReflect">Сколько младших битов числа обратить, 0..32.</param>
    /// <returns></returns>
    /// <remarks>Например: reflect(0x3E23, 3) == 0x3E26.</remarks>
    private uint reflect(uint value, int bitsToReflect = 32)
    {
      uint num1 = value;
      uint num2 = value;
      int num3 = 0;
      int num4 = checked (bitsToReflect - 1);
      int num5 = num3;
      while (num5 <= num4)
      {
        uint bitMask = this.getBitMask(checked (bitsToReflect - 1 - num5));
        if (((long) num1 & 1L) == 1L)
          num2 |= bitMask;
        else
          num2 &= ~bitMask;
        num1 >>= 1;
        checked { ++num5; }
      }
      return num2;
    }
  }
}

Данная программа на C# не тестировалась мной, в отличие от предыдущей, написанной на VB.NET. Этот код получен через декомпиляцию предыдущего. Если в нём обнаружатся какие-то ошибки, то пишите в комментариях или мне на почту, исправлю.

Прикладываю к статье полностью рабочий и готовый к использованию файл RocksoftCrcModel.vb с реализацией расчёта контрольной суммы CRC, который мы тут рассмотрели, а также RocksoftCrcModel.cs на C#.

Полную и самую последнюю версию кода можно скачать с репозитория на GitHub.

4«Взлом» контрольной суммы CRC32 и CRC16

Кратко затронем вопрос «взлома» CRC32. И прежде всего давайте определимся с понятием «взлом» применительно к данному вопросу.

Если задача определения контрольной суммы некоторого массива данных – прямая задача, то «взлом» – это обратная задача, а именно: подгонка контрольной суммы под определённый массив данных.

Допустим, вы имеете файл и рассчитали его контрольную сумму. Вам нужно изменить в нём произвольное число байтов, сохранив при этом контрольную сумму. Сделать это совсем не сложно.

Для начала нужно посчитать обычным образом контрольную сумму CRC32, CRC16 или любую другую, какая вам нужна, для этого изменённого файла. Пусть это будет C1. Теперь нужно добавить такое же число нулевых байтов в конец файла, которое содержится в контрольной сумме (для CRC32 – 4 байта, для CRC16 – 2 байта, и т.д.). Можно простым перебором подобрать такое число C2, которое мы и запишем в эти нулевые байты. Ведь понятно, что полный диапазон всех допустимых значений CRC32 укладывается в 2³² ~ 4,295 млрд. То есть за 4 с небольшим миллиарда итераций расчёта контрольной суммы с начальным содержимым регистра, равным С1, мы брутфорсом («в лоб», методом грубой силы) подберём нужное значение. При современных вычислительных мощностях это не составит проблемы. А уж «взломать» с помощью перебора CRC16 вообще дело нескольких секунд.

Можно ли разместить нулевые байты в середине или начале файла? Можно. К операции XOR применим сочетательный закон: a XOR (b XOR c) = (a XOR b) XOR c, поэтому можно с успехом разбить файл на 3 части: до вставки, после вставки, и сама вставка. Посчитать CRC для первых двух частей (C1 и C2 на иллюстрации), объединить их операцией XOR, заполнить этим числом начальное содержимое регистра, а затем «сбрутфорсить» CRC оставшейся третьей части X.

+-----------------+-----+---------+
|        c1       |  x  |   c2    |
+-----------------+-----+---------+

Есть более интеллектуальный и изящный способ подогнать CRC под нужное значение. Суть его в том, что вместо последовательного перебора всех подряд значений мы «прокручиваем назад» несколько раз (по числу байтов или битов контрольной суммы) наш табличный алгоритм или алгоритм побитового сдвига до тех пор, пока CRC не будет желаемой. На эту тему есть подробные и качественные материалы в сети.

Таким образом, напрашивается вывод: контрольная сумма типа CRC хорошо подходит для проверки целостности данных при случайных искажениях информации в канале передачи данных, но совершенно не подходит для защиты от намеренного взлома.

Computation of a cyclic redundancy check is derived from the mathematics of polynomial division, modulo two. In practice, it resembles long division of the binary message string, with a fixed number of zeroes appended, by the «generator polynomial» string except that exclusive or operations replace subtractions. Division of this type is efficiently realised in hardware by a modified shift register,^[1] and in software by a series of equivalent algorithms, starting with simple code close to the mathematics and becoming faster (and arguably more obfuscated^[2]) through byte-wise parallelism and space–time tradeoffs.

Various CRC standards extend the polynomial division algorithm by specifying an initial shift register value, a final Exclusive-Or step and, most critically, a bit ordering (endianness). As a result, the code seen in practice deviates confusingly from «pure» division,^[2] and the register may shift left or right.

Example[edit]

As an example of implementing polynomial division in hardware, suppose that we are trying to compute an 8-bit CRC of an 8-bit message made of the ASCII character «W», which is binary 01010111₂, decimal 87₁₀, or hexadecimal 57₁₆. For illustration, we will use the CRC-8-ATM (HEC) polynomial . Writing the first bit transmitted (the coefficient of the highest power of ) on the left, this corresponds to the 9-bit string «100000111».

The byte value 57₁₆ can be transmitted in two different orders, depending on the bit ordering convention used. Each one generates a different message polynomial . Msbit-first, this is = 01010111, while lsbit-first, it is = 11101010. These can then be multiplied by to produce two 16-bit message polynomials .

Computing the remainder then consists of subtracting multiples of the generator polynomial . This is just like decimal long division, but even simpler because the only possible multiples at each step are 0 and 1, and the subtractions borrow «from infinity» instead of reducing the upper digits. Because we do not care about the quotient, there is no need to record it.

Observe that after each subtraction, the bits are divided into three groups: at the beginning, a group which is all zero; at the end, a group which is unchanged from the original; and a blue shaded group in the middle which is «interesting». The «interesting» group is 8 bits long, matching the degree of the polynomial. Every step, the appropriate multiple of the polynomial is subtracted to make the zero group one bit longer, and the unchanged group becomes one bit shorter, until only the final remainder is left.

In the msbit-first example, the remainder polynomial is . Converting to a hexadecimal number using the convention that the highest power of x is the msbit; this is A2₁₆. In the lsbit-first, the remainder is . Converting to hexadecimal using the convention that the highest power of x is the lsbit, this is 19₁₆.

Implementation[edit]

Writing out the full message at each step, as done in the example above, is very tedious. Efficient implementations
use an -bit shift register to hold only the interesting bits. Multiplying the polynomial by is equivalent to shifting the register by one place, as the coefficients do not change in value but only move up to the next term of the polynomial.

Here is a first draft of some pseudocode for computing an n-bit CRC. It uses a contrived composite data type for polynomials, where x is not an integer variable, but a constructor generating a Polynomial object that can be added, multiplied and exponentiated. To xor two polynomials is to add them, modulo two; that is, to exclusive OR the coefficients of each matching term from both polynomials.

function crc(bit array bitString[1..len], int len) {
    remainderPolynomial := polynomialForm(bitString[1..n])   // First n bits of the message
    // A popular variant complements remainderPolynomial here; see § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x0   // Define bitString[k]=0 for k>len
        if coefficient of xn of remainderPolynomial = 1 {
            remainderPolynomial := remainderPolynomial xor generatorPolynomial
        }
    }
    // A popular variant complements remainderPolynomial here; see § Post-invert below
    return remainderPolynomial
}

Code fragment 1: Simple polynomial division

Note that this example code avoids the need to specify a bit-ordering convention by not using bytes; the input bitString is already in the form of a bit array, and the remainderPolynomial is manipulated in terms of polynomial operations; the multiplication by could be a left or right shift, and the addition of bitString[i+n] is done to the coefficient, which could be the right or left end of the register.

This code has two disadvantages. First, it actually requires an n+1-bit register to hold the remainderPolynomial so that the coefficient can be tested. More significantly, it requires the bitString to be padded with n zero bits.

The first problem can be solved by testing the coefficient of the remainderPolynomial before it is multiplied by .

The second problem could be solved by doing the last n iterations differently, but there is a more subtle optimization which is used universally, in both hardware and software implementations.

Because the XOR operation used to subtract the generator polynomial from the message is commutative and associative, it does not matter in what order the various inputs are combined into the remainderPolynomial. And specifically, a given bit of the bitString does not need to be added to the remainderPolynomial until the very last instant when it is tested to determine whether to xor with the generatorPolynomial.

This eliminates the need to preload the remainderPolynomial with the first n bits of the message, as well:

function crc(bit array bitString[1..len], int len) {
    remainderPolynomial := 0
    // A popular variant complements remainderPolynomial here; see § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial xor (bitstring[i] * xn−1)
        if (coefficient of xn−1 of remainderPolynomial) = 1 {
            remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
        } else {
            remainderPolynomial := (remainderPolynomial * x)
        }
    }
    // A popular variant complements remainderPolynomial here; see § Post-invert below
    return remainderPolynomial
}

Code fragment 2: Polynomial division with deferred message XORing

This is the standard bit-at-a-time hardware CRC implementation, and is well worthy of study; once you understand why this computes exactly the same result as the first version, the remaining optimizations are quite straightforward. If remainderPolynomial is only n bits long, then the coefficients of it and of generatorPolynomial are simply discarded. This is the reason that you will usually see CRC polynomials written in binary with the leading coefficient omitted.

In software, it is convenient to note that while one may delay the xor of each bit until the very last moment, it is also possible to do it earlier. It is usually convenient to perform the xor a byte at a time, even in a bit-at-a-time implementation like this:

function crc(byte array string[1..len], int len) {
    remainderPolynomial := 0
    // A popular variant complements remainderPolynomial here; see § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial xor polynomialForm(string[i]) * xn−8
        for j from 1 to 8 {    // Assuming 8 bits per byte
            if coefficient of xn−1 of remainderPolynomial = 1 {
                remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
            } else {
                remainderPolynomial := (remainderPolynomial * x)
            }
        }
    }
    // A popular variant complements remainderPolynomial here; see § Post-invert below
    return remainderPolynomial
}

Code fragment 3: Polynomial division with bytewise message XORing

This is usually the most compact software implementation, used in microcontrollers when space is at a premium over speed.

Bit ordering (endianness)[edit]

When implemented in bit serial hardware, the generator polynomial uniquely describes the bit assignment; the first bit transmitted is always the coefficient of the highest power of , and the last bits transmitted are the CRC remainder , starting with the coefficient of and ending with the coefficient of , a.k.a. the coefficient of 1.

However, when bits are processed a byte at a time, such as when using parallel transmission, byte framing as in 8B/10B encoding or RS-232-style asynchronous serial communication, or when implementing a CRC in software, it is necessary to specify the bit ordering (endianness) of the data; which bit in each byte is considered «first» and will be the coefficient of the higher power of .

If the data is destined for serial communication, it is best to use the bit ordering the data will ultimately be sent in. This is because a CRC’s ability to detect burst errors is based on proximity in the message polynomial ; if adjacent polynomial terms are not transmitted sequentially, a physical error burst of one length may be seen as a longer burst due to the rearrangement of bits.

For example, both IEEE 802 (ethernet) and RS-232 (serial port) standards specify least-significant bit first (little-endian) transmission, so a software CRC implementation to protect data sent across such a link should map the least significant bits in each byte to coefficients of the highest powers of . On the other hand, floppy disks and most hard drives write the most significant bit of each byte first.

The lsbit-first CRC is slightly simpler to implement in software, so is somewhat more commonly seen, but many programmers find the msbit-first bit ordering easier to follow. Thus, for example, the XMODEM-CRC extension, an early use of CRCs in software, uses an msbit-first CRC.

So far, the pseudocode has avoided specifying the ordering of bits within bytes by describing shifts in the pseudocode as multiplications by and writing explicit conversions from binary to polynomial form. In practice, the CRC is held in a standard binary register using a particular bit-ordering convention. In msbit-first form, the most significant binary bits will be sent first and so contain the higher-order polynomial coefficients, while in lsbit-first form, the least-significant binary bits contain the higher-order coefficients. The above pseudocode can be written in both forms. For concreteness, this uses the 16-bit CRC-16-CCITT polynomial :

// Most significant bit first (big-endian)
// x^16+x^12+x^5+1 = (1) 0001 0000 0010 0001 = 0x1021
function crc(byte array string[1..len], int len) {
    rem := 0
    // A popular variant complements rem here
    for i from 1 to len {
        rem  := rem xor (string[i] leftShift (n-8))   // n = 16 in this example
        for j from 1 to 8 {   // Assuming 8 bits per byte
            if rem and 0x8000 {   // if leftmost (most significant) bit is set
                rem  := (rem leftShift 1) xor 0x1021
            } else {
                rem  := rem leftShift 1
            }
            rem  := rem and 0xffff      // Trim remainder to 16 bits
        }
    }
    // A popular variant complements rem here
    return rem
}

Code fragment 4: Shift register based division, MSB first

// Least significant bit first (little-endian)
// x^16+x^12+x^5+1 = 1000 0100 0000 1000 (1) = 0x8408
function crc(byte array string[1..len], int len) {
    rem  := 0
    // A popular variant complements rem here
    for i from 1 to len {
        rem  := rem xor string[i]
        for j from 1 to 8 {   // Assuming 8 bits per byte
            if rem and 0x0001 {   // if rightmost (most significant) bit is set
                rem  := (rem rightShift 1) xor 0x8408
            } else {
                rem  := rem rightShift 1
            }
        }
    }
    // A popular variant complements rem here
    return rem
}

Code fragment 5: Shift register based division, LSB first

Note that the lsbit-first form avoids the need to shift string[i] before the xor. In either case, be sure to transmit the bytes of the CRC in the order that matches your chosen bit-ordering convention.

Multi-bit computation[edit]

Sarwate algorithm (single lookup table)[edit]

Another common optimization uses a lookup table indexed by highest order coefficients of rem to process more than one bit of dividend per iteration.^[3] Most commonly, a 256-entry lookup table is used, replacing the body of the outer loop (over i) with:

// Msbit-first
rem = (rem leftShift 8) xor big_endian_table[string[i] xor ((leftmost 8 bits of rem) rightShift (n-8))]
// Lsbit-first
rem = (rem rightShift 8) xor little_endian_table[string[i] xor (rightmost 8 bits of rem)]

Code fragment 6: Cores of table based division

One of the most commonly encountered CRC algorithms is known as CRC-32, used by (among others) Ethernet, FDDI, ZIP and other archive formats, and PNG image format. Its polynomial can be written msbit-first as 0x04C11DB7, or lsbit-first as 0xEDB88320. The W3C webpage on PNG includes an appendix with a short and simple table-driven implementation in C of CRC-32.^[4] You will note that the code corresponds to the lsbit-first byte-at-a-time pseudocode presented here, and the table is generated using the bit-at-a-time code.

Using a 256-entry table is usually most convenient, but other sizes can be used. In small microcontrollers, using a 16-entry table to process four bits at a time gives a useful speed improvement while keeping the table small. On computers with ample storage, a 65536-entry table can be used to process 16 bits at a time.

Generating the tables[edit]

The software to generate the tables is so small and fast that it is usually faster to compute them on program startup than to load precomputed tables from storage. One popular technique is to use the bit-at-a-time code 256 times to generate the CRCs of the 256 possible 8-bit bytes. However, this can be optimized significantly by taking advantage of the property that table[i xor j] == table[i] xor table[j]. Only the table entries corresponding to powers of two need to be computed directly.

In the following example code, crc holds the value of table[i]:

big_endian_table[0] := 0
crc := 0x8000 // Assuming a 16-bit polynomial
i := 1
do {
    if crc and 0x8000 {
        crc := (crc leftShift 1) xor 0x1021 // The CRC polynomial
    } else {
        crc := crc leftShift 1
    }
    // crc is the value of big_endian_table[i]; let j iterate over the already-initialized entries
    for j from 0 to i−1 {
        big_endian_table[i + j] := crc xor big_endian_table[j];
    }
    i := i leftshift 1
} while i < 256

Code fragment 7: Byte-at-a-time CRC table generation, MSB first

little_endian_table[0] := 0
crc := 1;
i := 128
do {
    if crc and 1 {
        crc := (crc rightShift 1) xor 0x8408 // The CRC polynomial
    } else {
        crc := crc rightShift 1
    }
    // crc is the value of little_endian_table[i]; let j iterate over the already-initialized entries
    for j from 0 to 255 by 2 × i {
        little_endian_table[i + j] := crc xor little_endian_table[j];
    }
    i := i rightshift 1
} while i > 0

Code fragment 8: Byte-at-a-time CRC table generation, LSB first

In these code samples, the table index i + j is equivalent to i xor j; you may use whichever form is more convenient.

CRC-32 algorithm[edit]

This is a practical algorithm for the CRC-32 variant of CRC.^[5] The CRCTable is a memoization of a calculation that would have to be repeated for each byte of the message (Computation of cyclic redundancy checks § Multi-bit computation).

Function CRC32
   Input:
      data:  Bytes     // Array of bytes
   Output:
      crc32: UInt32    // 32-bit unsigned CRC-32 value

// Initialize CRC-32 to starting value
crc32 ← 0xFFFFFFFF

for each byte in data do
   nLookupIndex ← (crc32 xor byte) and 0xFF
   crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex]  // CRCTable is an array of 256 32-bit constants

// Finalize the CRC-32 value by inverting all the bits
crc32 ← crc32 xor 0xFFFFFFFF
return crc32

In C, the algorithm looks as such:

#include <inttypes.h> // uint32_t, uint8_t

uint32_t CRC32(const uint8_t data[], size_t data_length) {
	uint32_t crc32 = 0xFFFFFFFFu;
	
	for (size_t i = 0; i < data_length; i++) {
		const uint32_t lookupIndex = (crc32 ^ data[i]) & 0xff;
		crc32 = (crc32 >> 8) ^ CRCTable[lookupIndex];  // CRCTable is an array of 256 32-bit constants
	}
	
	// Finalize the CRC-32 value by inverting all the bits
	crc32 ^= 0xFFFFFFFFu;
	return crc32;
}

Byte-Slicing using multiple tables[edit]

This section needs expansion. You can help by adding to it. (August 2017)

There exists a slice-by-N (typically slice-by-8 for CRC32; N ≤ 64) algorithm that usually doubles or triples the performance compared to the Sarwate algorithm. Instead of reading 8 bits at a time, the algorithm reads 8N bits at a time. Doing so maximizes performance on superscalar processors.^[6][7][8][9]

It is unclear who actually invented the algorithm.^[10]

Parallel computation without table[edit]

Parallel update for a byte or a word at a time can also be done explicitly, without a table.^[11] This is normally used in high-speed hardware implementations. For each bit an equation is solved after 8 bits have been shifted in. The following tables list the equations for some commonly used polynomials, using following symbols:

r0  ←
r1  ←
r2  ←
r3  ←
r4  ←
r5  ←
r6  ←
r7  ←

0
e0 + e4 + e7
e1 + e5
e2 + e6
e3 + e7      + e0 + e4 + e7
e4           + e1 + e5
e5           + e2 + e6
e6           + e3 + e7

e0           + e4 + e1 + e0        + e5 + e2 + e1
e1           + e5 + e2 + e1        + e6 + e3 + e2 + e0
e2           + e6 + e3 + e2 + e0   + e7 + e4 + e3 + e1
e3 + e0      + e7 + e4 + e3 + e1
e4 + e1 + e0
e5 + e2 + e1
e6 + e3 + e2 + e0
e7 + e4 + e3 + e1

 uint8_t c, d, e, f, r;
 …
 e = c ^ d;
 f = e ^ (e >> 4) ^ (e >> 7);
 r =     (f << 1) ^ (f << 4);

 uint8_t c, d, e, f, r;
 …
 e = c ^ d;
 f = e ^ (e << 3) ^ (e << 4) ^ (e << 6);
 r = f ^ (f >> 4) ^ (f >> 5);

r0  ←
r1  ←
r2  ←
r3  ←
r4  ←
r5  ←
r6  ←
r7  ←
r8  ←
r9  ←
r10 ←
r11 ←
r12 ←
r13 ←
r14 ←
r15 ←

s4 + s0
s5 + s1
s6 + s2
s7 + s3
     s4
     s5  + s4 + s0
     s6  + s5 + s1
     s7  + s6 + s2
c0       + s7 + s3
c1            + s4
c2            + s5
c3            + s6
c4            + s7  + s4 + s0
c5                  + s5 + s1
c6                  + s6 + s2
c7                  + s7 + s3

c8             + e4 + e0
c9             + e5 + e1
c10            + e6 + e2
c11      + e0  + e7 + e3
c12      + e1
c13      + e2
c14      + e3
c15      + e4 + e0
     e0  + e5 + e1
     e1  + e6 + e2
     e2  + e7 + e3
     e3
     e4 + e0
     e5 + e1
     e6 + e2
     e7 + e3

          sp
          s0 + sp
          s1 + s0
          s2 + s1
          s3 + s2
          s4 + s3
          s5 + s4
          s6 + s5
c0      + s7 + s6
c1           + s7
c2
c3
c4
c5
c6
c7 + sp

c8            + ep
c9 
c10
c11
c12
c13
c14 + e0
c15 + e1 + e0
      e2 + e1
      e3 + e2
      e4 + e3
      e5 + e4
      e6 + e5
      e7 + e6
      ep + e7
           ep

 uint8_t  d, s, t;
 uint16_t c, r;
 …
 s = d ^ (c >> 8);
 t = s ^ (s >> 4);
 r = (c << 8) ^
      t       ^
     (t << 5) ^
     (t << 12);

 uint8_t  d, e, f;
 uint16_t c, r;
 …
 e = c ^ d;
 f = e ^ (e << 4);
 r = (c >> 8) ^
     (f << 8) ^
     (f << 3) ^
     (f >> 4);

 uint8_t  d, s, p;
 uint16_t c, r, t;
 …
 s = d ^ (c >> 8);
 p = s ^ (s >> 4);
 p = p ^ (p >> 2);
 p = p ^ (p >> 1);
 p = p & 1;
 t = p | (s << 1);
 r = (c << 8)  ^
     (t << 15) ^
      t        ^
     (t << 1);

 uint8_t  d, e, p;
 uint16_t c, r, f;
 …
 e = c ^ d;
 p = e ^ (e >> 4);
 p = p ^ (p >> 2);
 p = p ^ (p >> 1);
 p = p & 1;
 f = e | (p << 8);
 r = (c >> 8) ^
     (f << 6) ^
     (f << 7) ^
     (f >> 8);

Two-step computation[edit]

As the CRC-32 polynomial has a large number of terms, when computing the remainder a byte at a time each bit depends on several bits of the previous iteration. In byte-parallel hardware implementations this calls for either multiple-input or cascaded XOR gates which increases propagation delay.

To maximise computation speed, an intermediate remainder can be calculated by passing the message through a 123-bit shift register. The polynomial is a carefully selected multiple of the standard polynomial such that the terms (feedback taps) are widely spaced, and no bit of the remainder is XORed more than once per byte iteration. Thus only two-input XOR gates, the fastest possible, are needed. Finally the intermediate remainder is divided by the standard polynomial in a second shift register to yield the CRC-32 remainder.^[12]

Block-wise computation[edit]

Block-wise computation of the remainder can be performed in hardware for any CRC polynomial by factorizing the State Space transformation matrix needed to compute the remainder into two simpler Toeplitz matrices.^[13]

One-pass checking[edit]

When appending a CRC to a message, it is possible to detach the transmitted CRC, recompute it, and verify the recomputed value against the transmitted one. However, a simpler technique is commonly
used in hardware.

When the CRC is transmitted with the correct byte order (matching the chosen bit-ordering convention), a receiver can compute an overall CRC, over the message and the CRC, and if they are correct, the result will be zero.^[14]
This possibility is the reason that most network protocols that include a CRC do so before the ending delimiter; it is not necessary to know whether the end of the packet is imminent to check the CRC.
In fact, a few protocols use the CRC *as* the ending delimiter — CRC-based framing.

CRC variants[edit]

In practice, most standards specify presetting the register to all-ones and inverting the CRC before transmission. This has no effect on the ability of a CRC to detect changed bits, but gives it the ability to notice bits that are added to the message.

Preset to −1[edit]

The basic mathematics of a CRC accepts (considers as correctly transmitted) messages which, when interpreted as a polynomial, are a multiple of the CRC polynomial. If some leading 0 bits are prepended to such a message, they will not change its interpretation as a polynomial. This is equivalent to the fact that 0001 and 1 are the same number.

But if the message being transmitted does care about leading 0 bits, the inability of the basic CRC algorithm to detect such a change is undesirable. If it is possible that a transmission error could add such bits, a simple solution is to start with the rem shift register set to some non-zero value; for convenience, the all-ones value is typically used. This is mathematically equivalent to complementing (binary NOT) the first n bits of the message, where n is the number of bits in the CRC register.

This does not affect CRC generation and checking in any way, as long as both generator and checker use the same initial value. Any non-zero initial value will do, and a few standards specify unusual values,^[15] but the all-ones value (−1 in twos complement binary) is by far the most common. Note that a one-pass CRC generate/check will still produce a result of zero when the message is correct, regardless of the preset value.

Post-invert[edit]

The same sort of error can occur at the end of a message, albeit with a more limited set of messages. Appending 0 bits to a message is equivalent to multiplying its polynomial by x, and if it was previously a multiple of the CRC polynomial, the result of that multiplication will be, as well. This is equivalent to the fact that, since 726 is a multiple of 11, so is 7260.

A similar solution can be applied at the end of the message, inverting the CRC register before it is appended to the message. Again, any non-zero change will do; inverting all the bits (XORing with an all-ones pattern) is simply the most common.

This has an effect on one-pass CRC checking: instead of producing a result of zero when the message is correct, it produces a fixed non-zero result. (To be precise, the result is the CRC (without non-zero preset, but with post-invert) of the inversion pattern.) Once this constant has been obtained (most easily by performing a one-pass CRC generate/check on an arbitrary message), it can be used directly to verify the correctness of any other message checked using the same CRC algorithm.

See also[edit]

General category

• Error correcting code
• List of hash functions
• Parity is equivalent to a 1-bit CRC with polynomial x+1.

Non-CRC checksums

• Adler-32
• Fletcher’s checksum

References[edit]

External links[edit]

• JohnPaul Adamovsky. «64 Bit Cyclic Redundant Code – XOR Long Division To Bytewise Table Lookup».

• Andrew Kadarch, Bob Jenkins. «Efficient (~1 CPU cycle per byte) CRC implementation». GitHub.

Во время передачи информации от одного устройства к другому могут возникать различные ошибки (помехи в радио-эфире, электромагнитные наводки в проводах), приводящие к повреждению данных. Достаточно повредить один бит, и число может сильно измениться! Например передавали число 123, которое выглядит как 0b01111011, и неправильно передали один бит. Приёмник получил число 0b01011011, что уже является числом 91! Если речь идёт о дистанционном управлении каким-то устройством, то даже один “битый” бит в посылке может привести к серьёзной аварии. Как приёмнику понять, что принятые данные повреждены?

Контрольная сумма

Самый простой вариант – контрольная сумма. Перед отправкой данных передатчик суммирует все байты и отправляет их например последними в посылке. Благодаря такой штуке как переполнение переменной, даже в один байт можно бесконечно суммировать данные и получить в итоге конкретное число, олицетворяющее все передаваемые данные. Например, передаём набор байтов 201, 125, 47, 94, 10, 185. Их суммой будет число 662, если брать ячейку int, или 150, если это byte. Осталось отправить контрольную сумму последним байтом (или двумя, если передаём int число)! Приёмник получает посылку, в свою очередь суммирует все байты кроме последнего (или двух последних, если контрольная сумма 16-битная), а затем сравнивает это значение с полученной контрольной суммой. Если отличается хоть на 1 – данные повреждены. Причём повреждёнными при передаче могут быть как сами данные, так и контрольная сумма: в любом случае они не совпадут, а это означает, что передача произошла с ошибкой. Давайте рассмотрим пример “передачи и приёма” структуры, где будет использоваться конструкция, позволяющая разбивать любые данные на байтовый поток. Три таких конструкции мы рассмотрели в уроке про указатели и ссылки. Структуру используем для удобства упаковки и использования данных. Универсальная для любого типа данных функция расчёта хеш-суммы может выглядеть так:

byte getHash(byte* data, int length) {
  byte hash = 0;
  int i = 0;
  while (length--) {
    hash += *(data + i);
    i++;
  }
  return hash;
}

И возвращать байт суммы. Создадим и заполним структуру данными и прогоним через эту функцию. В последний байт структуры запишем контрольную сумму:

// структура данных посылки
struct MyData {
  byte channel;
  int val_i;
  float val_f;
  byte hash;  // байт контрольной суммы
};

void setup() {
  Serial.begin(9600);
  // создаём и заполняем дату
  MyData data;
  data.channel = 16;
  data.val_i = 12345;
  data.val_f = 3.1415;
  data.hash = 0;

  // расчёт суммы
  byte thisHash = getHash((byte*)&data, sizeof(data));

  // пакуем в посылку
  data.hash = thisHash;

  // выведем для отладки
  Serial.println(thisHash); // выдаст 102
}

Теперь можно передать структуру приёмнику! Пример “синтетический”, так как кому и каким способом передавать данные мы не рассматриваем. Хотя, можно отправить по Serial, например с одной Ардуины на другую, как в уроке по парсингу Serial:

Serial.write((byte*)&data, sizeof(data));

Далее на приёмнике примем данные:

// структура данных посылки
struct MyData {
  byte channel;
  int val_i;
  float val_f;
  byte hash;  // байт контрольной суммы
};
MyData rxData;

void setup() {
  Serial.begin(9600);
}

void loop() {
  if (Serial.readBytes((byte*)&rxData, sizeof(rxData))) {
    // приняли данные
  }
}

Теперь нужно убедиться в том, что данные верны. Для этого прогоним их через ту же суммирующую функцию, но без учёта последнего байта, так как он сам является суммой:

byte thisHash = getHash((byte*)&rxData, sizeof(rxData) - 1);

Если значение совпадёт с переданным rxData.hash – данные верны! Дополним предыдущий код:

void loop() { 
  if (Serial.readBytes((byte*)&rxData, sizeof(rxData))) {        // читаем дату
    byte thisHash = getHash((byte*)&rxData, sizeof(rxData) - 1); // считаем сумму
    if (thisHash == rxData.hash) {
      // данные верны
    } else {
      // данные повреждены
    }
  }
}

И по условию можем выполнять какие-то действия, например применить полученные данные к устройству или проигнорировать их. Достоинства контрольной суммы:

• Быстрое и простое вычисление на любой платформе
• Возможность сделать 8 и 16 бит без особых вмешательств в код (это ваше домашнее задание)

Недостатки контрольной суммы:

• Низкая надёжность по сравнению с другими алгоритмами

Низкая надёжность заключается в том, что контрольная сумма не учитывает порядок байтов в посылке, то есть не является уникальным “отпечатком” всех данных. Например, данные повредились так, что из вот такого пакета

data.channel = 16;
data.val_i = 12345;
data.val_f = 3.1415;

Превратились в такой:

data.channel = 15;
data.val_i = 12346;
data.val_f = 3.1415;

Но контрольная сумма всё равно будет 102! Также контрольная сумма фактически игнорирует нули, то есть любой набор данных со всеми нулями и условно одной единичкой будет обрабатываться одинаково (например 0, 0, 0, 1, 0, 0 и 0, 1, 0, 0, 0, 0), что также снижает надёжность. Поэтому рассмотрим более хитрый алгоритм, который называется CRC.

CRC

CRC (cyclic redundancy code) – циклический избыточный код. Алгоритм тоже выдаёт некое “число” при прохождении через него потока байтов, но учитывает все предыдущие данные при расчёте. Как работает данный алгоритм мы рассматривать не будем, об этом можно почитать на Википедии или здесь. Рассмотрим реализацию CRC 8 бит по стандарту Dallas, он используется в датчиках этой фирмы (например DS18b20 и домофонные ключи iButton). Данная реализация должна работать на всех платформах, так как это чисто C++ без привязки к архитектуре (компилятор сам разберётся):

byte crc8(byte *buffer, byte size) {
  byte crc = 0;
  for (byte i = 0; i < size; i++) {
    byte data = buffer[i];
    for (int j = 8; j > 0; j--) {
      crc = ((crc ^ data) & 1) ? (crc >> 1) ^ 0x8C : (crc >> 1);
      data >>= 1;
    }
  }
  return crc;
}

Данная функция применяется точно так же, как предыдущая getHash(), просто “скармливаем” ей данные в байтовом представлении и всё! Но есть пара моментов:

• При расчёте CRC перед отправкой нужно исключить байт самого CRC (последний), даже если он нулевой. То есть в примерах выше: byte thisHash = crc8((byte*)&data, sizeof(data) - 1);
• При расчёте CRC на стороне приёмника можно прогнать все данные полностью, вместе с байтом CRC. В этом случае функция вернёт 0, если данные верны! Это очень удобно использовать.

Финальный пример. Передатчик:

// структура данных посылки
struct MyData {
  byte channel;
  int val_i;
  float val_f;
  byte crc;  // байт crc
};

void setup() {
  Serial.begin(9600);
  // создаём и заполняем дату
  MyData data;
  data.channel = 16;
  data.val_i = 12345;
  data.val_f = 3.1415;

  // расчёт CRC (без последнего байта)
  byte crc = crc8((byte*)&data, sizeof(data) - 1);

  // пакуем в посылку
  data.crc = crc;
}

void loop() {
  // отправляем
  Serial.write((byte*)&data, sizeof(data));
  delay(1000);
}

byte crc8(byte *buffer, byte size) {
  byte crc = 0;
  for (byte i = 0; i < size; i++) {
    byte data = buffer[i];
    for (int j = 8; j > 0; j--) {
      crc = ((crc ^ data) & 1) ? (crc >> 1) ^ 0x8C : (crc >> 1);
      data >>= 1;
    }
  }
  return crc;
}

Приёмник:

// структура данных посылки
struct MyData {
  byte channel;
  int val_i;
  float val_f;
  byte crc;  // байт crc
};
MyData rxData;

void setup() {
  Serial.begin(9600);
}

void loop() { 
  if (Serial.readBytes((byte*)&rxData, sizeof(rxData))) { // читаем дату 
    byte crc = crc8((byte*)&rxData, sizeof(rxData)); // считаем crc посылки полностью
    if (crc == 0) {
      // данные верны
    } else {
      // данные повреждены
    }
  }
}

byte crc8(byte *buffer, byte size) {
  byte crc = 0;
  for (byte i = 0; i < size; i++) {
    byte data = buffer[i];
    for (int j = 8; j > 0; j--) {
      crc = ((crc ^ data) & 1) ? (crc >> 1) ^ 0x8C : (crc >> 1);
      data >>= 1;
    }
  }
  return crc;
}

Также коллега поделился реализацией данного алгоритма на ассемблере для AVR, она работает чуть быстрее и весит чуть легче, что может быть критично например для ATtiny:

byte crc8_asm(byte *buffer, byte size) {
  byte crc = 0;
  for (byte i = 0; i < size; i++) {
    byte data = buffer[i];
    // резкий алгоритм для AVR
    uint8_t counter;
    uint8_t buffer;
    asm volatile (
      "EOR %[crc_out], %[data_in] nt"
      "LDI %[counter], 8          nt"
      "LDI %[buffer], 0x8C        nt"
      "_loop_start_%=:            nt"
      "LSR %[crc_out]             nt"
      "BRCC _loop_end_%=          nt"
      "EOR %[crc_out], %[buffer]  nt"
      "_loop_end_%=:              nt"
      "DEC %[counter]             nt"
      "BRNE _loop_start_%="
      : [crc_out]"=r" (crc), [counter]"=d" (counter), [buffer]"=d" (buffer)
      : [crc_in]"0" (crc), [data_in]"r" (data)
    );
  }
  return crc;
}

Функция используется точно так же, как предыдущая.

Полезные страницы

• Набор GyverKIT – большой стартовый набор Arduino моей разработки, продаётся в России
• Каталог ссылок на дешёвые Ардуины, датчики, модули и прочие железки с AliExpress у проверенных продавцов
• Подборка библиотек для Arduino, самых интересных и полезных, официальных и не очень
• Полная документация по языку Ардуино, все встроенные функции и макросы, все доступные типы данных
• Сборник полезных алгоритмов для написания скетчей: структура кода, таймеры, фильтры, парсинг данных
• Видео уроки по программированию Arduino с канала “Заметки Ардуинщика” – одни из самых подробных в рунете
• Поддержать автора за работу над уроками
• Обратная связь – сообщить об ошибке в уроке или предложить дополнение по тексту ([email protected])

Некоторые пользователи при загрузке (или установке) файлов с каких-либо источников могут столкнуться с ошибкой CRC, проявляющей себя сообщением «Ошибка в данных (CRC)». Данная проблема обычно возникает в ситуации, когда система фиксирует несовпадение контрольных данных загружаемого файла, вследствие чего возникает сообщение об ошибке в данных CRC. В этой статье я расскажу, что это за ошибка, при каких условиях она возникает, а также поясню как её исправить.

Что такое CRC

Прежде чем начать описывать, что делать в ситуации, когда появляется ошибка CRC, следует пояснить, что такое «CRC».

Как известно, CRC (Cycle Redundancy Check – в переводе «циклическая избыточная проверка») являет собой алгоритм создания и проверки «контрольной суммы файла». Последняя используется в слежении за целостностью передаваемых данных с целью профилактики их повреждения или потери.

Данный алгоритм на основе циклического кода вычисляет контрольную сумму файла и добавляет её к телу самого файла. При загрузке (копировании) данного файла система, обладая алгоритмом вычисления контрольной суммы, проверяет правильность полученных данных, и при возникновении нестыковок выдаёт сообщение об ошибке CRC (data error — cycle redundancy check ).

Алгоритм CRC был изобретён в далёком 1961 году, пережил несколько качественных улучшений, и ныне является универсальным средством для проверки целостности получаемых данных.

Особенности возникновения ошибки

Что же до причин возникновения данной дисфункции, то конкретные причины ошибки CRC могут быть следующими:

• Потеря или повреждение какого-либо из пакетов сетевых данных при их передаче;
• Потеря или повреждение данных на жёстком диске (к примеру, из-за плохих секторов);
• Физическое повреждение оптического диска с информацией (CD, DVD и др.);
• Нарушение целостности системного реестра;
• Случайный сбой при инсталляции программы;
• Неверная конфигурация файлов и так далее.

Для отображения кода CRC существует такая программа как HashTab, которая, после своей установки, в свойствах самого файла (кликаем правой клавишей мыши на файле, затем выбираем «Свойства) отображает значения контрольных сумм данного файла.

Ошибка в данных CRC — проблемы с жёстким диском

Итак, как исправить ошибку CRC? Поскольку она регулярно случается из-за проблем к доступу жёсткого диска, то рекомендую выполнить следующее:

Действие 1. Восстановите потерянные данные на жёстком диске. Если данная проблема возникла при попытке получения доступа к какому-либо файлу на жёстком диске, тогда стоит использовать различные программы для восстановления потерянных данных. В частности, можно попробовать в деле такие программные продукты как Power Data Recovery или BadCopy Pro, предназначенные именно для рассматриваемых мной задач.

К примеру, чтобы воспользоваться Power Data Recovery, необходимо скачать и установить приложение, в меню выбрать «Damaged Partition Recovery», и осуществить полное сканирование (Full Scan). Если потерянные данные удастся восстановить, тогда, первым делом, нужно будет скопировать их на надёжный и безопасный носитель.

Действие 2. Альтернативным вариантом восстановления доступа к данным на винчестере является использование системной утилиты проверки диска.

1. Зайдите в Проводник, кликните правой клавишей мыши на проблемном диске (например, С:), в появившемся меню выберите «Свойства».
2. Перейдите на вкладку «Сервис», кликните на «Выполнить проверку», поставьте галочки напротив двух опций проверки диска, нажмите на «Ок», а затем перезагрузите компьютер.
3. После перезагрузки система автоматически задействует проверку целостности данных на жёстком диске, и попытается восстановить повреждённые сектора (может занять какое-то время).

Действие 3. Также можно запустить командную строку от имени администратора (нажать на кнопку «Пуск», в строке поиска написать cmd (не нажимая на ввод), кликнуть на появившийся вверху однотипный результат правой клавишей мыши, и выбрать «Запуск от имени администратора). В командной строке необходимо написать:

chkdsk c: /r /f — (вместо «с:» впишите имя другого проблемного диска при необходимости) затем нажать на ввод, и дождаться окончания проверки.

Как исправить ошибку CRC — альтернативные варианты

Кроме проблем с жёстким диском, ошибка CRC может возникать и по другим причинам. Потому чтобы пофиксить ошибку CRC сделайте следующее:

• Скачайте торрент-файл из другого источника. Если вы скачали какой-либо файл с торрентов и получили ошибку CRC, тогда запустите торрент-клиент, удалите закачку с ошибкой, а потом и сами некорректно загруженные файлы на жёстком диске. Попробуйте поискать альтернативную закачку той же программы на торрент-трекере, возможно проблемная закачка была создана не совсем корректно, или файлы в ней были повреждены. В некоторых ситуациях не будет лишним и переустановить торрент-клиент, причина ошибки CRC может быть и в нём;
• Если вы получили данную ошибку при попытке считывания данных с СД (ДВД) диска, тогда, для начала, необходимо аккуратно протереть поверхность диска мягкой тканью с целью удаления пыли или грязи на его поверхности, а затем попробовать считать его содержимое с помощью уже упомянутой программы BadCopyPro;

• Если данная ошибка возникла при установке какой-либо игры, будет проще загрузить её образ ещё раз (или сами файлы программы) из другого источника с помощью проверенных программ уровня Download Master, возможно, это поможет избавиться от ошибки CRC.

Заключение

Если у вас возникла ошибка в данных CRC, то, прежде всего, определитесь с условиями, при которых возникла данная ошибка. Наиболее часто она возникает при попытке закачки и установки образов дисков (или самых программ) из сети. Эффективным средством в этом случае будет использование альтернативных ресурсов для закачки данных файлов, что, в большинстве случаев, помогает эффективно решить указанную проблему. Если же вы имеете дело с дисфункцией в работе жёсткого диска, тогда необходимо использовать программы уровня Power Data Recovery или BadCopyPro, способных помочь в восстановлении доступа к нужным вам файлам.