Проблемы в алгоритме вычисления CRC

Тема в разделе "WASM.ZEN", создана пользователем kkrutoy, 8 июл 2009.

  1. kkrutoy

    kkrutoy New Member

    Публикаций:
    0
    Регистрация:
    6 апр 2007
    Сообщения:
    44
    Адрес:
    Владивосток
    Делаю алгоритм, который будет на основании штрих-кода EAN-13, выдавать 6-значное число xxxxxx.
    Штрих-код, например, такой - 2200000001400.
    Взял за пример код простого CRC из книжки "Элементарное руководство по CRC алгоритмам"

    В середине видно много нулей, что означает, что операция XOR выполняться не будет, и результат первых чисел будет просто потерян.
    Нормального описания обхода таких ситуаций на русском языке я не нашел. В английских источниках вроде говориться, что при встрече с нулями, следует XOR их с каким-нибудь заранее выбранным числом, чтоб результат не терялся (не уверен в точности перевода). Правильный ли это подход?

    Еще вопрос - каким образом изменение одного бита влияет на всю CRC?
    Например, в штрихкоде, я изменил последний "0", на "1". В моей программе CRC тоже изменилась на 1.
    Я скачал утилиту, в которой при изменении последнего "0" на "1" изменилась вся сумма до неузнаваемости.

    Код привести не могу, т.к. он написан на скриптовом языке и абсолютно делу не поможет.
     
  2. MSoft

    MSoft New Member

    Публикаций:
    0
    Регистрация:
    16 дек 2006
    Сообщения:
    2.854
    Ну если бит включен, то значение суммы ксорится с 0EDB88320h. Если нет - ничего не делается. И так по 8 раз для каждого байта.
    покажи код, скорее всего ты где-то что-то напутал. Ну или пример у тебя был ошибочный.
     
  3. kkrutoy

    kkrutoy New Member

    Публикаций:
    0
    Регистрация:
    6 апр 2007
    Сообщения:
    44
    Адрес:
    Владивосток
    Я не точно выразился. Каким образом изменение последнего бита (тот что справа самый крайний) влияет на всю сумму? Ведь это последнее действие и больше ничего ксориться не будет...

    Код у меня для 1С:Предприятие, а здесь кроме ассемблера ничего не уважают.

    Код (Text):
    1. Пока МассивСообщения.Количество() >= РазмерРегистра Цикл
    2.         Бит = МассивСообщения.Получить(0);               
    3.         Если Бит = 1 Тогда                             
    4.             МассивДляОбмена = ХэшМассив;
    5.         Иначе
    6.             МассивДляОбмена = МассивДляНулей;         
    7.         КонецЕсли;    
    8.         Для К = 1 По РазмерРегистра Цикл               
    9.             Результат[К - 1] = XOR(Результат[К - 1], МассивДляОбмена[К - 1]);
    10.         КонецЦикла;          
    11.         МассивСообщения.Удалить(0);
    12.         Если МассивСообщения.Количество() >= РазмерРегистра Тогда
    13.             Результат.Удалить(0);
    14.             Результат.Добавить(МассивСообщения[РазмерРегистра - 1]);     
    15.         КонецЕсли;
    16.     КонецЦикла;
    МассивСообщения - Массив битов исходного кода. Просто там данные, предназначенные для вычисления CRC
    РазмерРегистра = 24.
    ХэшМассив - Массив[24] битовый массив. Элементы этого массива ксорятся с элементами массива сообщения, если старший бит установлен.
    МассивДляНулей - Массив[24]. В этом массиве "магическое" число. Ксорится, когда старший бит не установлен
    Результат - Массив[24]. Так называемый "регистр". В нем содержатся текущие биты, предназначенне для ксоринья.
     
  4. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    Ну кккрутые язык и алгоритм :))
    http://ru.wikipedia.org/wiki/Циклический_избыточный_код
    http://embedded.ifmo.ru/embedded_old/ETC/REFERAT/crc/crc.htm
    http://embedded.ifmo.ru/embedded_old/ETC/REFERAT/crc32/crc32.htm
     
  5. CyberManiac

    CyberManiac New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2003
    Сообщения:
    2.473
    Адрес:
    Russia
  6. kkrutoy

    kkrutoy New Member

    Публикаций:
    0
    Регистрация:
    6 апр 2007
    Сообщения:
    44
    Адрес:
    Владивосток
    Спасибо Y_Mur, разобрался, прочитав википедию раз 20.
    У меня бит, индицирующий необходимость XOR брался из сообщения, а нужно было его брать из результатов. Все работает!