Здравствуйте! Задумался над одной проблемой.. Хотел сделать чтобы моя программа давала контрольную сумму 0. Конечно, все зависит от способа ее подсчета. Если считать сумму всех байтов с учетом переполнения (счетчик 32битный), то сумма будет расчитываться примерно так: Код (Text): mov esi, offset Buffer mov ecx, BufSize mov CRC, 0 @@: lodsb add byte ptr CRC, al adc dword ptr CRC+1, 0 loop @B ... CRC dd ? db ? В этом случае приходит в голову только добавить ~10Мб байтов, заполненных 0FFh, чтобы сбросить счетчик Если CRC считается простой суммой байтов без учета переноса, Код (Text): @@: lodsb add byte ptr CRC, al loop @B то все просто - добавляем к программе 1 байт, дополняющий CRC до нуля. Если считается сумма двойных слов Код (Text): @@: lodsd add dword ptr CRC, eax loop @B - то добавляем соответенно двойное слово, равное -(CRC). Тут мне стало интересно, можно ли сделать так, чтобы CRC высчитанный двумя последними способами, был равен нулю? То есть, чтобы у куска кода, сумма всех байтов (без учета переполнения) была равна 0 и сумма всех двойных слов (начиная с 1 байта, размер кода кратен 4), тоже была равна нулю. Пример - поле, заполненное нулями Допустим, у нас есть кусок памяти заданного размера. У него известна сумма всех байтов (байтовая величина, без учета переполнения) - X, а также сумма всех двойных слов - Y(4 байтовая). Можно ли добавить к этой памяти какие-то значения, чтобы после подсчета вместе с ними стало X=0 и Y=0? Или это невозможно?
'x80\x00\x00\x00\x80\x00\x00\x00', 'xC0\x40\x00\x00\x40\xC0\x00\x00', etc Сложение не рулит, юзайте деление http://www.wasm.ru/docs/5/crc.zip
Нафига тебе все эти арифметические суммы и переполнения? Программер должен отдавать предпочтение XOR. Перексорь все байты-слова - вот тебе и контрольная сумма! Если есть предубеждения против обычного ксора, типа просто и ненадежно, тогда применяй xor и циклический поворот, скажем, на 17 бит. sum = ЦП(Sum,17) xor Data
Не катит) сумма по двойным словам - 1'00'00'00 Я не ставлю себе задачу искать методы вычисления контрольной суммы.. Просто заинтересовался вопросом можно так сделать или нет. Думаю, для того чтобы условие выполнилось, нужно чтобы сумма байтов двойного слова (которое мы будем добавлять) была равна сумме по байтам, взятой со знаком минус. То есть допустим, Y - сумма двойных слов (-Y) будет записываться как AABBCCDD, где A,B,C,D - hex цифры надо чтобы AA+BB+CC+DD = -X где X - сумма по байтам Есть идеи?
droopy То есть, если я правильно понял, в первом случае мы производим сложение байтов mod 2^8, во втором сложение двойных слов mod 2^32. Обозначим 0-X=:a mod 2^8 и 0-Y=:b mod 2^32. Дополнять кусок памяти будем некоторым количеством двойных слов. Получаем два уравнения: k + m + n + p = a mod 2^8 k*2^24 + m*2^16 + n*2^8 + p = b mod 2^32 где k,m,n,p соответственно суммы четвертого(высшего), третьего, второго и первого(низшего) байтов добавленных двойных слов. Эти два уравнения можно переформулировать в линейную систему с байтовыми переменными по модулю 2^8. Размер k,m,n,p и значит количество переменных системы зависит от количества слов. В случае одного DWORD'a система получается переопределенной (4 переменных, 5 уравнений) ) => решение существует, если b_{1} + b_{2} + b_{3} + b_{4} = a mod 2^8. Если разрешено добавлять более одного DWORD'a, то система будет недоопределенной и решение существует для всех a и b.
Чувак, я же говорю, контрольная сумма - это не обязательно складывать! Лучше даже, надежней не складывать, а делить на простое число или полином - так будет меньше коллизий. Но вернемся к нашим баранам... Те че нужно, чтобы checksum рассчитанная по байтам равнялась checksum рассчитанной по dword и равнялась нулю? Через XOR решается элементарно!!! Перексориваем все dword и приписываем ЧЕТЫРЕ байта к результату. Все, задача решена. =))) Теперь можно проксоривать как dword, так и отдельные байты, в результате будет нулль.
Вдогонку: интереснее будет наверное вопрос про размер дополнительных данных. То есть для заданных X и Y найти (= привести алгоритм) _минимальное_ количество DWORD'ов, которыми можно дополнить обе суммы до нуля. persicum Перечитай тему еще раз и внимательно. Человек задал совершенно определенный вопрос по совершенно определенной задаче. Вряд ли стоит впихивать сюда объяснения, как работает XOR.
Сегодня с droopy разобрали, не оптимальный алгоритм, но 100%. 1. dword подгоняем 32 битную сумму к 0. 2. Добавляем N комплементарных пар dword. Сумма пары равна 0, но при этом существуют пары у которых по-байтная сумма равна 0,-1,-2,-3. Итог: максимальный случай 4 + 85*8 = 684 байта.
Похоже оптимальная длина в DWORD'aх будет где-то в районе (b_{1} + b_{2} + b_{3} + b_{4} - a mod 2^8)/3, но не уверен, проверю вечером..
Респект AlB80 Прокомментирую его решение: Имеются заданные суммы - X (байтовая) и Y (4-байтовая) Сначала мы добавляем 1 двойное слово, равное -Y. Этим мы сбрасываем сумму по двойным словам в ноль. Далее, есть такие замечательные пары двойных слов: 1)FF'FF'00'00 - 00'01'00'00 - сумма по байтам -1 2)FF'FF'FF'00 - 00'00'01'00 - сумма по байтам -2 3)FF'FF'FF'FF - 00'00'00'01 - сумма по байтам -3 Заметьте, что у них всех сумма равно нулю. Мы берем сумму кода по байтам, делим ее на три. Добавляем такое количество пар №3. Если остаток от деления получился 1 или 2, то добавляем соответственно пару №1 или №2. Этим мы приводим сумму по байтам к нулю. В лучшем случае добавляем 4 байта, в худшем - 4+(255/3)*8 = 684 байта
Размер дополнительных данных действительно зависит от a и b: количество DWORD'ов = ceil((b_{1} + b_{2} + b_{3} + b_{4} - a)/3) + 1 где b_{1} + b_{2} + b_{3} + b_{4} - отдельные байты в b и операции производятся по модулю 256. Таким образом в худшем случае случае (например b=0 и a=1) требуются 86*4 = 344 байта. Это верхняя граница - оптимальная длина может быть на 1 меньше (как в случае b=0 и a=0), но рассматривать этот граничный случай я, честно говоря, поленился Вот код, который строит искомую байтовую последовательность. Для наглядности никак не оптимировал. Код (Text): // input data - a, b int a = 1; int b[] = new int[]{0,0,0,0}; int diff = mod(b[0] + b[1] + b[2] + b[3] - a, 256); int alpha2 = diff / 3; int beta1 = mod(b[1] - alpha2, 256); int over = alpha2>b[1]?1:0; diff = mod(diff - alpha2 - over, 256); int beta2 = diff / 2; int gamma1 = mod(b[2] - over - beta2, 256); over = over + beta2>b[2]?1:0; int gamma2 = mod(diff - beta2 - over, 256); int delta1 = mod(b[3] - gamma2 - over, 256); int alpha = alpha2*256 + b[0]; int beta = beta2*256 + beta1; int gamma = gamma2*256 + gamma1; int[] arr = new int[4*(alpha2+2)]; int i = 0; for(;;) { if(alpha>=255) { arr[i+3]=255; alpha-=255; } else { arr[i+3]=alpha; alpha = 0; } if(beta>=255) { arr[i+2]=255; beta-=255; } else { arr[i+2]=beta; beta = 0; } if(gamma>=255) { arr[i+1]+=255; gamma-=255; } else { arr[i+1]=gamma; gamma = 0; } i+=4; if(alpha + beta + gamma == 0) { break; } } arr[0] = delta1; System.out.println("Array length: "+i + "(bytes), "+i/4+" (DWORDs)"); System.out.println("Array content: "); for(int j=0;j<i;j++) { System.out.print(Integer.toHexString(arr[j])+" "); } Вроде не наврал нигде..
