Мучаем 5576ХС4Т - часть 'h2A - ZLIB и коды коррекции ошибок Adler32
Часть 0 - покупаем, паяем, ставим драйвера и софт
Часть 1 - что это вообще за зверь?
Часть 2 - наша первая схема!
Часть 3 - кнопочки и лампочки
Часть 4 - делитель частоты
Часть 5 - подавление дребезга кнопки
Часть 6 - заканчиваем кнопочки и лампочки
Часть 7 - счетчики и жаба
Часть 8 - передатчик UART
Часть 9 - Hello, wolf!
Часть 'hA - приёмник UART
Часть 'hB - UART и жаба
Часть 'hC - полудуплексный UART.
Часть 'hD - МКО (МКИО, Mil-Std 1553) для бедных, введение.
Часть 'hE - приёмопередатчик МКО "из подручных материалов" (в процессе)
Часть 'hF - модуль передатчика МКО
Часть 'h10 - передатчик сообщений МКО
Часть 'h20 - работа с АЦП ADC124s051
Часть 'h21 - преобразование двоичного кода в двоично-десятичный (BCD)
Часть 'h22 - Bin2Bcd с последовательной выдачей данных
Часть 'h23 - перемножитель беззнаковых чисел с округлением
Часть 'h24 - перемножитель беззнаковых чисел, реализация
Часть 'h25 - передаём показания АЦП на компьютер
Часть 'h26 - работа над ошибками (быстрый UART)
Часть 'h27 - PNG и коды коррекции ошибок CRC32
Часть 'h28 - передатчик изображения PNG
Часть 'h29 - принимаем с ПЛИС изображение PNG
Часть 'h2A - ZLIB и коды коррекции ошибок Adler32
Часть 'h2B - ускоряем Adler32
Часть 'h2C - формирователь потока Zlib
Часть 'h2D - передаём сгенерированное PNG-изображение
Часть 'h2E - делим отрезок на равные части
Часть 'h2F - знаковые умножители, тысячи их!
Часть 'h30 - вычислитель множества Мандельброта
Часть 'h31 - ускоренные сумматоры
Часть 'h32 - ускоренные счётчики (делаем часы)
Часть 'h33 - ускоряем ВСЁ
Часть 'h34 - ускоренные перемножители
Часть 'h35 - умножители совсем просто
Часть 'h36 - уравновешенный четверичный умножитель
Продолжаем углубляться в формат PNG. Мы рассмотрели общую структуру и даже научились "на ходу" добавлять в выходной поток CRC32.
Но внутри IDAT (причём возможно, в нескольких подряд идущих IDAT) размещается сжатый поток ZLIB - если мы хотим генерировать png-изображение "сами" - то должны научиться из "исходных данных" формировать корректный поток ZLIB. Проще всего составить его из несжатых блоков, но даже в этом случае нам нужно посчитать ещё одну контрольную сумму - Adler32...
Для теста я "нарисовал" в фотошопе картинку:
Размер 48х1, 8 бит градации серого, простое чередование чёрных и белых пикселей. Сохранил в PNG, причём выбрал "без сжатия" - фотошоп почему-то умеет либо совсем без сжатия, либо с максимальным сжатием - третьего (а также четвёртого и пятого) не дано!
Именно содержимое данного файла PNG мы и будем сейчас изучать.
На рисунке в начале поста, в hex-коде мы видим 4 байта, образующие слово IDAT (Image DATa), и сразу за ним начинается поток. Вот его заголовок:
78 01
Да, всего 2 байта. Первые 4 бита означают ширину окна для алгоритма Deflate. 7 - максимальное допустимое значение и соответствует 32 килобайтам (6 - это 16 КБ, 5 - 8 КБ, и т.д, степени двойки). По идее, декодер может в этом месте сообразить, насколько длинный буфер ему нужен - и выделить ровно столько памяти, сколько требуется. Для 16-битных приложений (где памяти всего 64 КБ) и всевозможного Embedded это может быть весьма критично (так, в нашей ПЛИС памяти всего 96 килобит!), но как-то так повелось, что почти всегда здесь стоит семёрка, даже если поток несжатый и никакого окна не требует! На дальнейший поток значение, приведённое здесь, не оказывает никакого влияния.
Следующие 4 бита - тип компрессии, используемой в ZLIB. На данный момент (с 1996 года ничего не поменялось) доступен только один вариант - Deflate, и ему соответствует восьмёрка.
Поэтому если видим в hex-коде байт 78 - это указание, что здесь может начинаться zlib :)
Следующий байт разбит на 3 части. Старшие 2 бита (7-й и 6-й, если нумеровать с нуля) указывают степень сжатия:
00 - наименьшее сжатие (самый быстрый алгоритм),
01 - малое сжатие (быстрый алгоритм)
10 - сжатие по умолчанию
11 - наибольшее сжатие (самое медленное)
Никакого влияния на последующий поток эти биты не оказывают. Мотивация их появления - чтобы мы могли очень быстро заглянуть в файлы, найти, используют ли они наибольшее сжатие, а если нет - пережать по-новой ради уменьшения размера. Если же мы натыкаемся на 11, то оставляем такой файл в покое, пережимать его гиблое дело!
Далее, бит 5 указывает, используем ли мы "словарь" (preset dictionary) - в стандарте предусмотрена возможность начинать не с "пустого окна", а сразу заполнить его некоторым текстом, возможно - списком часто встречающихся слов, чтобы сжатие с самого начала получалось эффективным. Не шибко поможет при сжатии больших файлов (особенно если речь идёт об изображениях PNG), но очень здорово при обмене короткими сообщениями.
И наконец, биты 4..0 являются маленькой "контрольной суммой" для заголовка - их подбирают такими, чтобы двухбайтный заголовок, представленный как целое беззнаковое число, делился нацело на 31.
Мы видим байт 01 - это означает наименьшее сжатие (вообще без сжатия!) и отсутствие словаря. Проверяем "контрольную сумму":
0x7801 = 30721 = 991 * 31
Отлично: похоже, это действительно заголовок ZLIB, а не какой-то рандомный кусок кода :)
После этого начинается поток Deflate - про него нам в описании ZLIB ничего не говорят, нужно лезть в соответствующий документ.
Для нас важно, что каждый следующий блок может начинаться "в любом месте" (не обязательно в начале байта), причём биты мы отсчитываем от младшего к старшего, после чего принимаемся за следующий байт.
Вот заголовок несжатого блока:
00 31 00 CE FF
Начинаем с младшего бита первого байта - это признак последнего блока. Если стоит единица - значит сразу после текущего блока поток заканчивается. У нас стоит ноль - значит блок не последний.
Затем прочитываем ещё 2 бита - это тип блока. 00 означает несжатый блок.
Только в случае несжатого блока мы заполняем остатки байта нулями!
После этого идёт 2 байта - размер данного несжатого блока (конкретно полезных данных, т.е не считая заголовка), причём во всём Deflate принято начинать передачу чисел с младших разрядов (тогда как в ZLIB - со старших!). Т.е 31 00 означает число 0x0031 = 49 - именно столько полезных байт содержится в блоке.
Затем этот же размер представлен ещё раз, но в "инвертированном виде" - все нули заменяются на единицы и наоборот. Вот и выходит CE FF.
Далее мы отсчитываем 49 байт - это и есть наши данные:
00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00
Первый байт - фильтр, используемый в данной строке. Ноль означает отсутствие фильтра (фильтр None) - пиксели передаются "как есть".
Далее мы видим ещё два несжатых блока:
00 00 00 FF FF 01 00 00 FF FF
Первый - это блок нулевого размера, второй - ПОСЛЕДНИЙ БЛОК нулевого размера.
Такие нулевые блоки очень любят вставлять время от времени, чтобы передать наконец целое число байтов и "начать сначала". Нечто такое генерится в разных режимах flush.
Но вообще, стандарт вовсе не обязывает к применению таких блоков - если сейчас влезть в hex и сократить поток до
78 01
01 31 00 CE FF
00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00
,
то ничего не поменяется (если ещё подкорректировать длину блока IDAT и контрольную сумму к нему).
На ПОСЛЕДНЕМ БЛОКЕ заканчивается поток Deflate, но ещё не заканчивается ZLIB. Чтобы закончить его, остаётся записать 32-битный код Adler32:
55 F7 17 E9
Два последних байта, 17 E9 (назовём их s1) - образуют число, сумму всех байт НЕСЖАТЫХ ДАННЫХ, плюс единичка, и взять ПО МОДУЛЮ 65521.
В нашем случае имеем ровно 24 байта FF и 25 байт 00, так что их сумма (и ещё +1) получается
255 * 24 + 1 = 6121 = 0x17E9
Совпадает!
А вот первые два байта (их называют s2) - это сумма последних 2 байт, s1, получаемых на каждом этапе выполнения Adler32.
Т.е мы получили 1-й байт данных, 00, и s1 как был единицей, так ей и остался. Тогда и s2 станет единицей.
Получили 2-й байт, FF, и s1 стал 0x0100. Тогда s2 стал 0x0101.
И здесь мы тоже используем вычисления ПО МОДУЛЮ 65521 - это самое большое простое число, которое можно уместить в 16 бит!
Мотивация применения Adler32 вместо CRC32 - в простоте его вычисления, когда речь идёт о компьютере, процессор которого не очень-то любит оперировать отдельными битами, а вот перемалывать на уровне байтов (а лучше - по 2..4..8 байта за раз) - самое то!
Как ни странно, при реализации на ПЛИС всё наоборот - вычислитель CRC32 занимает чуть больше 32 ЛЭ, если в него поступает по 1 биту за раз (т.е на обработку 1 байта уходит 8 тактов), либо 55 ЛЭ, если за каждый такт надо обрабатывать сразу по байту.
[Вот его код, если интересно]
Вот его код, если интересно. Самому его писать не надо - заходим на OutputLogic.com и генерим его там для заданного многочлена.
//-----------------------------------------------------------------------------
// Copyright (C) 2009 OutputLogic.com
// This source file may be used and distributed without restriction
// provided that this copyright statement is not removed from the file
// and that any derivative work contains the original copyright notice
// and the associated disclaimer.
//
// THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS
// OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
// WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//-----------------------------------------------------------------------------
// CRC module for data[7:0] , crc[31:0]=1+x^1+x^2+x^4+x^5+x^7+x^8+x^10+x^11+x^12+x^16+x^22+x^23+x^26+x^32;
//-----------------------------------------------------------------------------
module CRC32_8bit_by_output_logic(
input [7:0] data_in,
input crc_en,
output [31:0] crc_out,
input rst,
input clk);
reg [31:0] lfsr_q,lfsr_c;
assign crc_out = lfsr_q;
always @(*) begin
lfsr_c[0] = lfsr_q[24] ^ lfsr_q[30] ^ data_in[0] ^ data_in[6];
lfsr_c[1] = lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[0] ^ data_in[1] ^ data_in[6] ^ data_in[7];
lfsr_c[2] = lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[0] ^ data_in[1] ^ data_in[2] ^ data_in[6] ^ data_in[7];
lfsr_c[3] = lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[31] ^ data_in[1] ^ data_in[2] ^ data_in[3] ^ data_in[7];
lfsr_c[4] = lfsr_q[24] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[28] ^ lfsr_q[30] ^ data_in[0] ^ data_in[2] ^ data_in[3] ^ data_in[4] ^ data_in[6];
lfsr_c[5] = lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[27] ^ lfsr_q[28] ^ lfsr_q[29] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[0] ^ data_in[1] ^ data_in[3] ^ data_in[4] ^ data_in[5] ^ data_in[6] ^ data_in[7];
lfsr_c[6] = lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[28] ^ lfsr_q[29] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[1] ^ data_in[2] ^ data_in[4] ^ data_in[5] ^ data_in[6] ^ data_in[7];
lfsr_c[7] = lfsr_q[24] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[29] ^ lfsr_q[31] ^ data_in[0] ^ data_in[2] ^ data_in[3] ^ data_in[5] ^ data_in[7];
lfsr_c[8] = lfsr_q[0] ^ lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[27] ^ lfsr_q[28] ^ data_in[0] ^ data_in[1] ^ data_in[3] ^ data_in[4];
lfsr_c[9] = lfsr_q[1] ^ lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[28] ^ lfsr_q[29] ^ data_in[1] ^ data_in[2] ^ data_in[4] ^ data_in[5];
lfsr_c[10] = lfsr_q[2] ^ lfsr_q[24] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[29] ^ data_in[0] ^ data_in[2] ^ data_in[3] ^ data_in[5];
lfsr_c[11] = lfsr_q[3] ^ lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[27] ^ lfsr_q[28] ^ data_in[0] ^ data_in[1] ^ data_in[3] ^ data_in[4];
lfsr_c[12] = lfsr_q[4] ^ lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[28] ^ lfsr_q[29] ^ lfsr_q[30] ^ data_in[0] ^ data_in[1] ^ data_in[2] ^ data_in[4] ^ data_in[5] ^ data_in[6];
lfsr_c[13] = lfsr_q[5] ^ lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[29] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[1] ^ data_in[2] ^ data_in[3] ^ data_in[5] ^ data_in[6] ^ data_in[7];
lfsr_c[14] = lfsr_q[6] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[28] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[2] ^ data_in[3] ^ data_in[4] ^ data_in[6] ^ data_in[7];
lfsr_c[15] = lfsr_q[7] ^ lfsr_q[27] ^ lfsr_q[28] ^ lfsr_q[29] ^ lfsr_q[31] ^ data_in[3] ^ data_in[4] ^ data_in[5] ^ data_in[7];
lfsr_c[16] = lfsr_q[8] ^ lfsr_q[24] ^ lfsr_q[28] ^ lfsr_q[29] ^ data_in[0] ^ data_in[4] ^ data_in[5];
lfsr_c[17] = lfsr_q[9] ^ lfsr_q[25] ^ lfsr_q[29] ^ lfsr_q[30] ^ data_in[1] ^ data_in[5] ^ data_in[6];
lfsr_c[18] = lfsr_q[10] ^ lfsr_q[26] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[2] ^ data_in[6] ^ data_in[7];
lfsr_c[19] = lfsr_q[11] ^ lfsr_q[27] ^ lfsr_q[31] ^ data_in[3] ^ data_in[7];
lfsr_c[20] = lfsr_q[12] ^ lfsr_q[28] ^ data_in[4];
lfsr_c[21] = lfsr_q[13] ^ lfsr_q[29] ^ data_in[5];
lfsr_c[22] = lfsr_q[14] ^ lfsr_q[24] ^ data_in[0];
lfsr_c[23] = lfsr_q[15] ^ lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[30] ^ data_in[0] ^ data_in[1] ^ data_in[6];
lfsr_c[24] = lfsr_q[16] ^ lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[31] ^ data_in[1] ^ data_in[2] ^ data_in[7];
lfsr_c[25] = lfsr_q[17] ^ lfsr_q[26] ^ lfsr_q[27] ^ data_in[2] ^ data_in[3];
lfsr_c[26] = lfsr_q[18] ^ lfsr_q[24] ^ lfsr_q[27] ^ lfsr_q[28] ^ lfsr_q[30] ^ data_in[0] ^ data_in[3] ^ data_in[4] ^ data_in[6];
lfsr_c[27] = lfsr_q[19] ^ lfsr_q[25] ^ lfsr_q[28] ^ lfsr_q[29] ^ lfsr_q[31] ^ data_in[1] ^ data_in[4] ^ data_in[5] ^ data_in[7];
lfsr_c[28] = lfsr_q[20] ^ lfsr_q[26] ^ lfsr_q[29] ^ lfsr_q[30] ^ data_in[2] ^ data_in[5] ^ data_in[6];
lfsr_c[29] = lfsr_q[21] ^ lfsr_q[27] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[3] ^ data_in[6] ^ data_in[7];
lfsr_c[30] = lfsr_q[22] ^ lfsr_q[28] ^ lfsr_q[31] ^ data_in[4] ^ data_in[7];
lfsr_c[31] = lfsr_q[23] ^ lfsr_q[29] ^ data_in[5];
end // always
always @(posedge clk, posedge rst) begin
if(rst) begin
lfsr_q <= {32{1'b1}};
end
else begin
lfsr_q <= crc_en ? lfsr_c : lfsr_q;
end
end // always
endmodule // crc
А вот посчитать Adler32 на ПЛИС - самую чуточку сложнее. Каждый раз, принимая новый байт данных, мы должны произвести два сложения по модулю 65521. По сути, каждое такое сложение "распадается" на обычное сложение с образованием бита переноса, на проверку результата и на корректирующее сложение - мы должны прибавить 15, если результат "обычного сложения" превысил 65520.
Причём, мы должны обновлять s2 только после того, как обновили s1.
Как оказалось, в данной ПЛИС 16-битный сумматор - штука на удивление медленная. При тактовой частоте 80 МГц, мы не можем поставить два таких сумматора "подряд" (сначала прибавление нового байта, затем прибавление 15 либо нуля) - задержка распространения к старшим разрядам превысит один такт, и такая схема будет работать нестабильно!
Да и в целом, это "слишком жирно", поэтому в итоге я пришёл вот к такому варианту:
module Adler32 (input clk, input [7:0] A, input ce, input aclr, input shift, output [7:0] Q);
//control logic
//at ce, we latch A into input reg
reg ce_z1 = 1'b0; //1 clk delay, controls s1 <= s1 + A
reg ce_z2 = 1'b0; //2 clk delay, controls correction of s1
reg ce_z3 = 1'b0; //3 clk delay, controls s2 <= s2 + s1
reg ce_z4 = 1'b0; //4 clk delay, controls correction of s2
//input reg (otherwise we have serious problems!)
reg [7:0] rA = 1'b0;
//first adder
reg [15:0] s1 = 1'b0;
reg r_cout1 = 1'b0; //we store this also, for 1 clk
wire [15:0] AorCorr; //input of first adder
Adler32MUX Mux1 ( .B ({8'b0, rA}),
.UseB (ce_z1),
.correction (r_cout1),
.Q (AorCorr));
wire [15:0] sum1; //output of first adder
wire cout1; //carry-out of first adder
lpm_add_sub AdderS1 (
.dataa (AorCorr),
.datab (s1),
.cout (cout1),
.result (sum1) );
defparam
AdderS1.lpm_direction = "ADD",
AdderS1.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=NO",
AdderS1.lpm_representation = "UNSIGNED",
AdderS1.lpm_type = "LPM_ADD_SUB",
AdderS1.lpm_width = 16;
//second adder
reg [15:0] s2 = 1'b0;
reg r_cout2 = 1'b0;
wire [15:0] s1orCorr; //input of second adder
Adler32MUX Mux2 ( .B (s1),
.UseB (ce_z3),
.correction (r_cout2),
.Q (s1orCorr));
wire [15:0] sum2; //output of second adder
wire cout2; //carry-out of second adder
lpm_add_sub AdderS2 (
.dataa (s1orCorr),
.datab (s2),
.cout (cout2),
.result (sum2));
defparam
AdderS2.lpm_direction = "ADD",
AdderS2.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=NO",
AdderS2.lpm_representation = "UNSIGNED",
AdderS2.lpm_type = "LPM_ADD_SUB",
AdderS2.lpm_width = 16;
always @(posedge clk, posedge aclr) begin
if (aclr) begin
s1 <= 16'b1; //by definition of Adler32
s2 <= 16'b0;
end
else begin
ce_z1 <= ce;
ce_z2 <= ce_z1;
ce_z3 <= ce_z2;
ce_z4 <= ce_z3;
rA <= A;
r_cout1 <= cout1 | (sum1 >= 65521);
r_cout2 <= cout2 | (sum2 >= 65521);
if (ce_z1 | ce_z2 | shift) begin
s1 <= shift? s1 << 8 : sum1;
end
if (ce_z3 | ce_z4 | shift) begin
s2 <= shift? {s2[7:0], s1[15:8]} : sum2;
end
end
end
assign Q = s2[15:8];
endmodule
module Adler32MUX (input [15:0] B, input UseB, input correction, output [15:0] Q);
assign Q = UseB? B : correction? 15'd15 : 15'd0;
endmodule
Возможно, было не обязательно "в явном виде" подключать сумматоры - хватило бы символа "+", но не факт. К сожалению, весьма ходовой вариант, когда при сложении двух 16-битных чисел мы получаем 17-битное (т.е бит переноса в дополнение к 16 битам) - компилятор в упор не понимает! Он начинает ставить 17-битный сумматор с неподключёнными "старшими битами".
Но меня больше всего "выбесило", когда строки
wire [16:0] RawSum = A + B;
assign C = (RawSum < 65521)? RawSum[15:0] : RawSum[15:0] - 16'd65521;
(это была другая реализация, я надеялся за один такт провести как сложение, так и коррекцию)
были преобразованы в 17-битный сумматор, 16-битный сумматор и долбаный МУЛЬТИПЛЕКСОР!!! Т.е он опять "не увидел в упор", что можно вторым операндом сумматора ставить либо 0, либо 15, а решил поставить сумматор с константой на входе, а потом переключать выход - либо он присоединяется к входу, либо к выходу. Получилось мало того что громоздко, но ещё и медленно - очередной Critical Warning по таймингам. Правда, избавившись от мультиплексора (выписав процедуру в явном виде), сделать это за один такт все равно не удалось...
Мы же здесь делаем чуть по-другому.
Когда мы подаём очередной байт, он первым делом "защёлкивается" во входном регистре rA. Возможно, в дальнейшем, в порыве жадности, я этот регистр выкину, а пока он был принципиально нужен для правильной работы хотя бы на симуляторе - иначе задержка распространения входного сигнала через входные буферы, интерконнекторы, через мультиплексор и сумматор до входа в регистр s1 оказались больше, чем 1 период тактовой частоты - и у меня вообще ничего не работало.
На следующем такте (теперь уже ce=0, зато ce_z1=1 - это стартовый импульс, задержанный на такт) мы складываем содержимое rA (наш байт) с регистром s1. Выход сразу же "защёлкивается" назад, и тут же мы проверяем - получился ли результат больше, чем 65520? То есть, нужна ли коррекция? Чтобы дать корректный ответ, мы обязаны воспользоваться выходом переноса, иначе очень вероятно, что результат "перевернётся" через 65535 и станет снова маленьким :)
На этом такте мы ни в коем случае не должны "защёлкивать" новый байт - между двумя байтами должна быть пауза хотя бы в 1 такт!
Ответ на вопрос "нужна ли коррекция" мы сохраняем в регистр r_cout1.
На следующем такте мы уже можем отправлять на вход новый байт. А вот дальше по "конвейеру" у нас ce_z1 = 0, и ce_z2 = 1. Теперь на второй вход сумматора поступает либо 0, либо 15 - в зависимости от значения r_cout1. Выход сумматора снова загружается в регистр s1 - на этом формирование корректного значения s1 завершено.
Спустя ещё один такт мы берём значение s1 и ровно таким же способом прибавляем его к s2. На это уходит ещё 2 такта.
Таким образом, задержка от входа до выхода составляет 5 тактов, но мы можем заносить данные каждый 2-й такт, что для большинства применений вполне терпимо. По сути, мы можем "перемалывать" данные на скорости 40 МБайт/с = 320 МБит/с. Неплохая скорость :)
В конце работы мы, как обычно, устраиваем сдвиг влево в 4 этапа, что позволяет сохранить 4 байта результата в последовательные адреса в памяти.
Данная штуковина синтезируется в 113 ЛЭ - несколько побольше, чем понадобилось для CRC32, но в целом жить можно. Правда, чтобы дстичь такого результата, мы решили немножко поступиться своими принципами и поставить асинхронный сброс. Это освобождает один из 4 входов ГФ, благодаря чему одним махом мы выигрываем 32 ЛЭ. Но обращаться с этим сбросом надо осторожно - желательно сделать некоторую паузу между сбросом и началом выдачи данных, чтобы точно не случилось ситуации метастабильности, когда мы одновременно (или очень близко во времени) "тянем в разные стороны" и заставляем несчастные триггеры застрять ровно посерединке!
Осталось совсем немного - модуль для "оборачивания" несжатого потока в Deflate и ZLIB - и мы сможем генерить PNG совсем "на лету" из данных оцифровки.
PS. ЖЖ как-то хитро тупит - кнопка "просмотр" стала работать ровно также, как "опубликовать" - недописанный пост тут же размещается "для всех".
Часть 1 - что это вообще за зверь?
Часть 2 - наша первая схема!
Часть 3 - кнопочки и лампочки
Часть 4 - делитель частоты
Часть 5 - подавление дребезга кнопки
Часть 6 - заканчиваем кнопочки и лампочки
Часть 7 - счетчики и жаба
Часть 8 - передатчик UART
Часть 9 - Hello, wolf!
Часть 'hA - приёмник UART
Часть 'hB - UART и жаба
Часть 'hC - полудуплексный UART.
Часть 'hD - МКО (МКИО, Mil-Std 1553) для бедных, введение.
Часть 'hE - приёмопередатчик МКО "из подручных материалов" (в процессе)
Часть 'hF - модуль передатчика МКО
Часть 'h10 - передатчик сообщений МКО
Часть 'h20 - работа с АЦП ADC124s051
Часть 'h21 - преобразование двоичного кода в двоично-десятичный (BCD)
Часть 'h22 - Bin2Bcd с последовательной выдачей данных
Часть 'h23 - перемножитель беззнаковых чисел с округлением
Часть 'h24 - перемножитель беззнаковых чисел, реализация
Часть 'h25 - передаём показания АЦП на компьютер
Часть 'h26 - работа над ошибками (быстрый UART)
Часть 'h27 - PNG и коды коррекции ошибок CRC32
Часть 'h28 - передатчик изображения PNG
Часть 'h29 - принимаем с ПЛИС изображение PNG
Часть 'h2A - ZLIB и коды коррекции ошибок Adler32
Часть 'h2B - ускоряем Adler32
Часть 'h2C - формирователь потока Zlib
Часть 'h2D - передаём сгенерированное PNG-изображение
Часть 'h2E - делим отрезок на равные части
Часть 'h2F - знаковые умножители, тысячи их!
Часть 'h30 - вычислитель множества Мандельброта
Часть 'h31 - ускоренные сумматоры
Часть 'h32 - ускоренные счётчики (делаем часы)
Часть 'h33 - ускоряем ВСЁ
Часть 'h34 - ускоренные перемножители
Часть 'h35 - умножители совсем просто
Часть 'h36 - уравновешенный четверичный умножитель
Продолжаем углубляться в формат PNG. Мы рассмотрели общую структуру и даже научились "на ходу" добавлять в выходной поток CRC32.
Но внутри IDAT (причём возможно, в нескольких подряд идущих IDAT) размещается сжатый поток ZLIB - если мы хотим генерировать png-изображение "сами" - то должны научиться из "исходных данных" формировать корректный поток ZLIB. Проще всего составить его из несжатых блоков, но даже в этом случае нам нужно посчитать ещё одну контрольную сумму - Adler32...
Для теста я "нарисовал" в фотошопе картинку:
Размер 48х1, 8 бит градации серого, простое чередование чёрных и белых пикселей. Сохранил в PNG, причём выбрал "без сжатия" - фотошоп почему-то умеет либо совсем без сжатия, либо с максимальным сжатием - третьего (а также четвёртого и пятого) не дано!
Именно содержимое данного файла PNG мы и будем сейчас изучать.
На рисунке в начале поста, в hex-коде мы видим 4 байта, образующие слово IDAT (Image DATa), и сразу за ним начинается поток. Вот его заголовок:
78 01
Да, всего 2 байта. Первые 4 бита означают ширину окна для алгоритма Deflate. 7 - максимальное допустимое значение и соответствует 32 килобайтам (6 - это 16 КБ, 5 - 8 КБ, и т.д, степени двойки). По идее, декодер может в этом месте сообразить, насколько длинный буфер ему нужен - и выделить ровно столько памяти, сколько требуется. Для 16-битных приложений (где памяти всего 64 КБ) и всевозможного Embedded это может быть весьма критично (так, в нашей ПЛИС памяти всего 96 килобит!), но как-то так повелось, что почти всегда здесь стоит семёрка, даже если поток несжатый и никакого окна не требует! На дальнейший поток значение, приведённое здесь, не оказывает никакого влияния.
Следующие 4 бита - тип компрессии, используемой в ZLIB. На данный момент (с 1996 года ничего не поменялось) доступен только один вариант - Deflate, и ему соответствует восьмёрка.
Поэтому если видим в hex-коде байт 78 - это указание, что здесь может начинаться zlib :)
Следующий байт разбит на 3 части. Старшие 2 бита (7-й и 6-й, если нумеровать с нуля) указывают степень сжатия:
00 - наименьшее сжатие (самый быстрый алгоритм),
01 - малое сжатие (быстрый алгоритм)
10 - сжатие по умолчанию
11 - наибольшее сжатие (самое медленное)
Никакого влияния на последующий поток эти биты не оказывают. Мотивация их появления - чтобы мы могли очень быстро заглянуть в файлы, найти, используют ли они наибольшее сжатие, а если нет - пережать по-новой ради уменьшения размера. Если же мы натыкаемся на 11, то оставляем такой файл в покое, пережимать его гиблое дело!
Далее, бит 5 указывает, используем ли мы "словарь" (preset dictionary) - в стандарте предусмотрена возможность начинать не с "пустого окна", а сразу заполнить его некоторым текстом, возможно - списком часто встречающихся слов, чтобы сжатие с самого начала получалось эффективным. Не шибко поможет при сжатии больших файлов (особенно если речь идёт об изображениях PNG), но очень здорово при обмене короткими сообщениями.
И наконец, биты 4..0 являются маленькой "контрольной суммой" для заголовка - их подбирают такими, чтобы двухбайтный заголовок, представленный как целое беззнаковое число, делился нацело на 31.
Мы видим байт 01 - это означает наименьшее сжатие (вообще без сжатия!) и отсутствие словаря. Проверяем "контрольную сумму":
0x7801 = 30721 = 991 * 31
Отлично: похоже, это действительно заголовок ZLIB, а не какой-то рандомный кусок кода :)
После этого начинается поток Deflate - про него нам в описании ZLIB ничего не говорят, нужно лезть в соответствующий документ.
Для нас важно, что каждый следующий блок может начинаться "в любом месте" (не обязательно в начале байта), причём биты мы отсчитываем от младшего к старшего, после чего принимаемся за следующий байт.
Вот заголовок несжатого блока:
00 31 00 CE FF
Начинаем с младшего бита первого байта - это признак последнего блока. Если стоит единица - значит сразу после текущего блока поток заканчивается. У нас стоит ноль - значит блок не последний.
Затем прочитываем ещё 2 бита - это тип блока. 00 означает несжатый блок.
Только в случае несжатого блока мы заполняем остатки байта нулями!
После этого идёт 2 байта - размер данного несжатого блока (конкретно полезных данных, т.е не считая заголовка), причём во всём Deflate принято начинать передачу чисел с младших разрядов (тогда как в ZLIB - со старших!). Т.е 31 00 означает число 0x0031 = 49 - именно столько полезных байт содержится в блоке.
Затем этот же размер представлен ещё раз, но в "инвертированном виде" - все нули заменяются на единицы и наоборот. Вот и выходит CE FF.
Далее мы отсчитываем 49 байт - это и есть наши данные:
00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00
Первый байт - фильтр, используемый в данной строке. Ноль означает отсутствие фильтра (фильтр None) - пиксели передаются "как есть".
Далее мы видим ещё два несжатых блока:
00 00 00 FF FF 01 00 00 FF FF
Первый - это блок нулевого размера, второй - ПОСЛЕДНИЙ БЛОК нулевого размера.
Такие нулевые блоки очень любят вставлять время от времени, чтобы передать наконец целое число байтов и "начать сначала". Нечто такое генерится в разных режимах flush.
Но вообще, стандарт вовсе не обязывает к применению таких блоков - если сейчас влезть в hex и сократить поток до
78 01
01 31 00 CE FF
00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00 FF 00
,
то ничего не поменяется (если ещё подкорректировать длину блока IDAT и контрольную сумму к нему).
На ПОСЛЕДНЕМ БЛОКЕ заканчивается поток Deflate, но ещё не заканчивается ZLIB. Чтобы закончить его, остаётся записать 32-битный код Adler32:
55 F7 17 E9
Два последних байта, 17 E9 (назовём их s1) - образуют число, сумму всех байт НЕСЖАТЫХ ДАННЫХ, плюс единичка, и взять ПО МОДУЛЮ 65521.
В нашем случае имеем ровно 24 байта FF и 25 байт 00, так что их сумма (и ещё +1) получается
255 * 24 + 1 = 6121 = 0x17E9
Совпадает!
А вот первые два байта (их называют s2) - это сумма последних 2 байт, s1, получаемых на каждом этапе выполнения Adler32.
Т.е мы получили 1-й байт данных, 00, и s1 как был единицей, так ей и остался. Тогда и s2 станет единицей.
Получили 2-й байт, FF, и s1 стал 0x0100. Тогда s2 стал 0x0101.
И здесь мы тоже используем вычисления ПО МОДУЛЮ 65521 - это самое большое простое число, которое можно уместить в 16 бит!
Мотивация применения Adler32 вместо CRC32 - в простоте его вычисления, когда речь идёт о компьютере, процессор которого не очень-то любит оперировать отдельными битами, а вот перемалывать на уровне байтов (а лучше - по 2..4..8 байта за раз) - самое то!
Как ни странно, при реализации на ПЛИС всё наоборот - вычислитель CRC32 занимает чуть больше 32 ЛЭ, если в него поступает по 1 биту за раз (т.е на обработку 1 байта уходит 8 тактов), либо 55 ЛЭ, если за каждый такт надо обрабатывать сразу по байту.
[Вот его код, если интересно]
Вот его код, если интересно. Самому его писать не надо - заходим на OutputLogic.com и генерим его там для заданного многочлена.
//-----------------------------------------------------------------------------
// Copyright (C) 2009 OutputLogic.com
// This source file may be used and distributed without restriction
// provided that this copyright statement is not removed from the file
// and that any derivative work contains the original copyright notice
// and the associated disclaimer.
//
// THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS
// OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
// WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//-----------------------------------------------------------------------------
// CRC module for data[7:0] , crc[31:0]=1+x^1+x^2+x^4+x^5+x^7+x^8+x^10+x^11+x^12+x^16+x^22+x^23+x^26+x^32;
//-----------------------------------------------------------------------------
module CRC32_8bit_by_output_logic(
input [7:0] data_in,
input crc_en,
output [31:0] crc_out,
input rst,
input clk);
reg [31:0] lfsr_q,lfsr_c;
assign crc_out = lfsr_q;
always @(*) begin
lfsr_c[0] = lfsr_q[24] ^ lfsr_q[30] ^ data_in[0] ^ data_in[6];
lfsr_c[1] = lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[0] ^ data_in[1] ^ data_in[6] ^ data_in[7];
lfsr_c[2] = lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[0] ^ data_in[1] ^ data_in[2] ^ data_in[6] ^ data_in[7];
lfsr_c[3] = lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[31] ^ data_in[1] ^ data_in[2] ^ data_in[3] ^ data_in[7];
lfsr_c[4] = lfsr_q[24] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[28] ^ lfsr_q[30] ^ data_in[0] ^ data_in[2] ^ data_in[3] ^ data_in[4] ^ data_in[6];
lfsr_c[5] = lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[27] ^ lfsr_q[28] ^ lfsr_q[29] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[0] ^ data_in[1] ^ data_in[3] ^ data_in[4] ^ data_in[5] ^ data_in[6] ^ data_in[7];
lfsr_c[6] = lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[28] ^ lfsr_q[29] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[1] ^ data_in[2] ^ data_in[4] ^ data_in[5] ^ data_in[6] ^ data_in[7];
lfsr_c[7] = lfsr_q[24] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[29] ^ lfsr_q[31] ^ data_in[0] ^ data_in[2] ^ data_in[3] ^ data_in[5] ^ data_in[7];
lfsr_c[8] = lfsr_q[0] ^ lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[27] ^ lfsr_q[28] ^ data_in[0] ^ data_in[1] ^ data_in[3] ^ data_in[4];
lfsr_c[9] = lfsr_q[1] ^ lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[28] ^ lfsr_q[29] ^ data_in[1] ^ data_in[2] ^ data_in[4] ^ data_in[5];
lfsr_c[10] = lfsr_q[2] ^ lfsr_q[24] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[29] ^ data_in[0] ^ data_in[2] ^ data_in[3] ^ data_in[5];
lfsr_c[11] = lfsr_q[3] ^ lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[27] ^ lfsr_q[28] ^ data_in[0] ^ data_in[1] ^ data_in[3] ^ data_in[4];
lfsr_c[12] = lfsr_q[4] ^ lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[28] ^ lfsr_q[29] ^ lfsr_q[30] ^ data_in[0] ^ data_in[1] ^ data_in[2] ^ data_in[4] ^ data_in[5] ^ data_in[6];
lfsr_c[13] = lfsr_q[5] ^ lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[29] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[1] ^ data_in[2] ^ data_in[3] ^ data_in[5] ^ data_in[6] ^ data_in[7];
lfsr_c[14] = lfsr_q[6] ^ lfsr_q[26] ^ lfsr_q[27] ^ lfsr_q[28] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[2] ^ data_in[3] ^ data_in[4] ^ data_in[6] ^ data_in[7];
lfsr_c[15] = lfsr_q[7] ^ lfsr_q[27] ^ lfsr_q[28] ^ lfsr_q[29] ^ lfsr_q[31] ^ data_in[3] ^ data_in[4] ^ data_in[5] ^ data_in[7];
lfsr_c[16] = lfsr_q[8] ^ lfsr_q[24] ^ lfsr_q[28] ^ lfsr_q[29] ^ data_in[0] ^ data_in[4] ^ data_in[5];
lfsr_c[17] = lfsr_q[9] ^ lfsr_q[25] ^ lfsr_q[29] ^ lfsr_q[30] ^ data_in[1] ^ data_in[5] ^ data_in[6];
lfsr_c[18] = lfsr_q[10] ^ lfsr_q[26] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[2] ^ data_in[6] ^ data_in[7];
lfsr_c[19] = lfsr_q[11] ^ lfsr_q[27] ^ lfsr_q[31] ^ data_in[3] ^ data_in[7];
lfsr_c[20] = lfsr_q[12] ^ lfsr_q[28] ^ data_in[4];
lfsr_c[21] = lfsr_q[13] ^ lfsr_q[29] ^ data_in[5];
lfsr_c[22] = lfsr_q[14] ^ lfsr_q[24] ^ data_in[0];
lfsr_c[23] = lfsr_q[15] ^ lfsr_q[24] ^ lfsr_q[25] ^ lfsr_q[30] ^ data_in[0] ^ data_in[1] ^ data_in[6];
lfsr_c[24] = lfsr_q[16] ^ lfsr_q[25] ^ lfsr_q[26] ^ lfsr_q[31] ^ data_in[1] ^ data_in[2] ^ data_in[7];
lfsr_c[25] = lfsr_q[17] ^ lfsr_q[26] ^ lfsr_q[27] ^ data_in[2] ^ data_in[3];
lfsr_c[26] = lfsr_q[18] ^ lfsr_q[24] ^ lfsr_q[27] ^ lfsr_q[28] ^ lfsr_q[30] ^ data_in[0] ^ data_in[3] ^ data_in[4] ^ data_in[6];
lfsr_c[27] = lfsr_q[19] ^ lfsr_q[25] ^ lfsr_q[28] ^ lfsr_q[29] ^ lfsr_q[31] ^ data_in[1] ^ data_in[4] ^ data_in[5] ^ data_in[7];
lfsr_c[28] = lfsr_q[20] ^ lfsr_q[26] ^ lfsr_q[29] ^ lfsr_q[30] ^ data_in[2] ^ data_in[5] ^ data_in[6];
lfsr_c[29] = lfsr_q[21] ^ lfsr_q[27] ^ lfsr_q[30] ^ lfsr_q[31] ^ data_in[3] ^ data_in[6] ^ data_in[7];
lfsr_c[30] = lfsr_q[22] ^ lfsr_q[28] ^ lfsr_q[31] ^ data_in[4] ^ data_in[7];
lfsr_c[31] = lfsr_q[23] ^ lfsr_q[29] ^ data_in[5];
end // always
always @(posedge clk, posedge rst) begin
if(rst) begin
lfsr_q <= {32{1'b1}};
end
else begin
lfsr_q <= crc_en ? lfsr_c : lfsr_q;
end
end // always
endmodule // crc
А вот посчитать Adler32 на ПЛИС - самую чуточку сложнее. Каждый раз, принимая новый байт данных, мы должны произвести два сложения по модулю 65521. По сути, каждое такое сложение "распадается" на обычное сложение с образованием бита переноса, на проверку результата и на корректирующее сложение - мы должны прибавить 15, если результат "обычного сложения" превысил 65520.
Причём, мы должны обновлять s2 только после того, как обновили s1.
Как оказалось, в данной ПЛИС 16-битный сумматор - штука на удивление медленная. При тактовой частоте 80 МГц, мы не можем поставить два таких сумматора "подряд" (сначала прибавление нового байта, затем прибавление 15 либо нуля) - задержка распространения к старшим разрядам превысит один такт, и такая схема будет работать нестабильно!
Да и в целом, это "слишком жирно", поэтому в итоге я пришёл вот к такому варианту:
module Adler32 (input clk, input [7:0] A, input ce, input aclr, input shift, output [7:0] Q);
//control logic
//at ce, we latch A into input reg
reg ce_z1 = 1'b0; //1 clk delay, controls s1 <= s1 + A
reg ce_z2 = 1'b0; //2 clk delay, controls correction of s1
reg ce_z3 = 1'b0; //3 clk delay, controls s2 <= s2 + s1
reg ce_z4 = 1'b0; //4 clk delay, controls correction of s2
//input reg (otherwise we have serious problems!)
reg [7:0] rA = 1'b0;
//first adder
reg [15:0] s1 = 1'b0;
reg r_cout1 = 1'b0; //we store this also, for 1 clk
wire [15:0] AorCorr; //input of first adder
Adler32MUX Mux1 ( .B ({8'b0, rA}),
.UseB (ce_z1),
.correction (r_cout1),
.Q (AorCorr));
wire [15:0] sum1; //output of first adder
wire cout1; //carry-out of first adder
lpm_add_sub AdderS1 (
.dataa (AorCorr),
.datab (s1),
.cout (cout1),
.result (sum1) );
defparam
AdderS1.lpm_direction = "ADD",
AdderS1.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=NO",
AdderS1.lpm_representation = "UNSIGNED",
AdderS1.lpm_type = "LPM_ADD_SUB",
AdderS1.lpm_width = 16;
//second adder
reg [15:0] s2 = 1'b0;
reg r_cout2 = 1'b0;
wire [15:0] s1orCorr; //input of second adder
Adler32MUX Mux2 ( .B (s1),
.UseB (ce_z3),
.correction (r_cout2),
.Q (s1orCorr));
wire [15:0] sum2; //output of second adder
wire cout2; //carry-out of second adder
lpm_add_sub AdderS2 (
.dataa (s1orCorr),
.datab (s2),
.cout (cout2),
.result (sum2));
defparam
AdderS2.lpm_direction = "ADD",
AdderS2.lpm_hint = "ONE_INPUT_IS_CONSTANT=NO,CIN_USED=NO",
AdderS2.lpm_representation = "UNSIGNED",
AdderS2.lpm_type = "LPM_ADD_SUB",
AdderS2.lpm_width = 16;
always @(posedge clk, posedge aclr) begin
if (aclr) begin
s1 <= 16'b1; //by definition of Adler32
s2 <= 16'b0;
end
else begin
ce_z1 <= ce;
ce_z2 <= ce_z1;
ce_z3 <= ce_z2;
ce_z4 <= ce_z3;
rA <= A;
r_cout1 <= cout1 | (sum1 >= 65521);
r_cout2 <= cout2 | (sum2 >= 65521);
if (ce_z1 | ce_z2 | shift) begin
s1 <= shift? s1 << 8 : sum1;
end
if (ce_z3 | ce_z4 | shift) begin
s2 <= shift? {s2[7:0], s1[15:8]} : sum2;
end
end
end
assign Q = s2[15:8];
endmodule
module Adler32MUX (input [15:0] B, input UseB, input correction, output [15:0] Q);
assign Q = UseB? B : correction? 15'd15 : 15'd0;
endmodule
Возможно, было не обязательно "в явном виде" подключать сумматоры - хватило бы символа "+", но не факт. К сожалению, весьма ходовой вариант, когда при сложении двух 16-битных чисел мы получаем 17-битное (т.е бит переноса в дополнение к 16 битам) - компилятор в упор не понимает! Он начинает ставить 17-битный сумматор с неподключёнными "старшими битами".
Но меня больше всего "выбесило", когда строки
wire [16:0] RawSum = A + B;
assign C = (RawSum < 65521)? RawSum[15:0] : RawSum[15:0] - 16'd65521;
(это была другая реализация, я надеялся за один такт провести как сложение, так и коррекцию)
были преобразованы в 17-битный сумматор, 16-битный сумматор и долбаный МУЛЬТИПЛЕКСОР!!! Т.е он опять "не увидел в упор", что можно вторым операндом сумматора ставить либо 0, либо 15, а решил поставить сумматор с константой на входе, а потом переключать выход - либо он присоединяется к входу, либо к выходу. Получилось мало того что громоздко, но ещё и медленно - очередной Critical Warning по таймингам. Правда, избавившись от мультиплексора (выписав процедуру в явном виде), сделать это за один такт все равно не удалось...
Мы же здесь делаем чуть по-другому.
Когда мы подаём очередной байт, он первым делом "защёлкивается" во входном регистре rA. Возможно, в дальнейшем, в порыве жадности, я этот регистр выкину, а пока он был принципиально нужен для правильной работы хотя бы на симуляторе - иначе задержка распространения входного сигнала через входные буферы, интерконнекторы, через мультиплексор и сумматор до входа в регистр s1 оказались больше, чем 1 период тактовой частоты - и у меня вообще ничего не работало.
На следующем такте (теперь уже ce=0, зато ce_z1=1 - это стартовый импульс, задержанный на такт) мы складываем содержимое rA (наш байт) с регистром s1. Выход сразу же "защёлкивается" назад, и тут же мы проверяем - получился ли результат больше, чем 65520? То есть, нужна ли коррекция? Чтобы дать корректный ответ, мы обязаны воспользоваться выходом переноса, иначе очень вероятно, что результат "перевернётся" через 65535 и станет снова маленьким :)
На этом такте мы ни в коем случае не должны "защёлкивать" новый байт - между двумя байтами должна быть пауза хотя бы в 1 такт!
Ответ на вопрос "нужна ли коррекция" мы сохраняем в регистр r_cout1.
На следующем такте мы уже можем отправлять на вход новый байт. А вот дальше по "конвейеру" у нас ce_z1 = 0, и ce_z2 = 1. Теперь на второй вход сумматора поступает либо 0, либо 15 - в зависимости от значения r_cout1. Выход сумматора снова загружается в регистр s1 - на этом формирование корректного значения s1 завершено.
Спустя ещё один такт мы берём значение s1 и ровно таким же способом прибавляем его к s2. На это уходит ещё 2 такта.
Таким образом, задержка от входа до выхода составляет 5 тактов, но мы можем заносить данные каждый 2-й такт, что для большинства применений вполне терпимо. По сути, мы можем "перемалывать" данные на скорости 40 МБайт/с = 320 МБит/с. Неплохая скорость :)
В конце работы мы, как обычно, устраиваем сдвиг влево в 4 этапа, что позволяет сохранить 4 байта результата в последовательные адреса в памяти.
Данная штуковина синтезируется в 113 ЛЭ - несколько побольше, чем понадобилось для CRC32, но в целом жить можно. Правда, чтобы дстичь такого результата, мы решили немножко поступиться своими принципами и поставить асинхронный сброс. Это освобождает один из 4 входов ГФ, благодаря чему одним махом мы выигрываем 32 ЛЭ. Но обращаться с этим сбросом надо осторожно - желательно сделать некоторую паузу между сбросом и началом выдачи данных, чтобы точно не случилось ситуации метастабильности, когда мы одновременно (или очень близко во времени) "тянем в разные стороны" и заставляем несчастные триггеры застрять ровно посерединке!
Осталось совсем немного - модуль для "оборачивания" несжатого потока в Deflate и ZLIB - и мы сможем генерить PNG совсем "на лету" из данных оцифровки.
PS. ЖЖ как-то хитро тупит - кнопка "просмотр" стала работать ровно также, как "опубликовать" - недописанный пост тут же размещается "для всех".