nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Мучаем 5576ХС4Т - часть 'h27 - PNG и коды коррекции ошибок CRC32

Часть 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 на ПЛИС и передавать его на компьютер.

Заголовки мы можем заранее записать в память, сжатие изображения лучше всего производить по мере оцифровки, и в память заносить уже сжатый поток (а на первых порах можно обойтись и без него, с использованием несжатых блоков zlib), а вот 4-байтные CRC-коды, которыми должен заканчиваться каждый блок (chunk) PNG, удобнее всего посчитать непосредственно во время отправки этого изображения ("файла") по UART или какому-нибудь ещё интерфейсу.

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

Но сначала небольшое пояснение, зачем это вообще надо...


Давно уже пора заняться оцифровкой видео и обработкой изображений на ПЛИС. Для этого у меня на макетке стоит быстродействующая 8-битная АЦП, способная давать до 100 млн. выборок в секунду, а также селектор синхроимпульсов LM1881. Возможно, в итоге удастся обойтись и без него (у нас же есть АЦП, так оцифруем сигнал "сплошняком" и напишем на верилоге функциональный аналог LM1881!), но для этого надо очень хорошо закопаться в телевидение, и даже в этом случае есть небольшая проблемка с уровнями сигналов. Хотя размах композитного видеосигнала - 1 вольт, и диапазон входных напряжений АЦП - тоже 1 вольт, это вовсе не означает, что сигнал "поместится". Постоянная составляющая на входе имеет право быть какой угодно, её рекомендуется "выкинуть" с помощью разделительного конденсатора. И тут-то и оказывается: если у нас довольно "светлый" кадр, наши синхроимпульсы выйдут за входной диапазон АЦП. Либо надо неким хитрым образом "восстанавливать" постоянную составляющую (так это делается в видеоусилителях старых добрых кинескопных телевизоров), либо просто чуть ослабить сигнал, чтобы при всех возможных вариациях яркости мы не теряли синхроимпульсы, но при 8 битах делать этого ой как не хочется...

Про это всё непременно напишем. Но вот в чём трудность - мы вполне могли проверить работоспособность АЦП, подав двоичный код на 8 светодиодиков. Мигают как положено, когда крутишь переменный резистор - всё хорошо. Можно проверить работу селектора синхроимпульсов, сосчитав количество кадров в секунду и число строк в кадре.

А вот чтобы уже убедиться, что мы правильно оцифровываем картинку, очень хочется эту картинку перетащить на компьютер, и там открыть и тщательно изучить!

У меня сейчас небольшой бзик - не люблю каждый раз писать программу на компьютере для обработки поступивших данных - выходит в итоге, что нужно и её начать отлаживать, находить, где у нас начинаются проблемы - со стороны ПЛИС или со стороны программы обработки, поэтому всё равно придётся вернуться к "сырым данным", открыть hex-редактор и уйти глубоко в отладку.

Почему бы всё-таки не "обернуть" наши данные в какой-нибудь формат уже со стороны ПЛИС, передать, сохранить в файл, поменять ему расширение - и спокойненько открыть? Заодно потренироваться в построении сколько-нибудь сложных "конструкций" в Верилоге и Quartus'е. (Благо, задачи вполне типовые - CRC очень много где надо считать, и именно его использование в связке с передатчиком кажется наиболее предпочтительным.)

Остаётся выбрать формат. Вроде бы напрашивается BMP, но, во-первых, в нём отсутствует сжатие как класс (какие-то вариации есть, но не шибко используются), и в своём классическом виде он хранит картинку "вверх ногами" - первой идёт нижняя строка, затем предпоследняя, и так далее. Согласно документации, если указать высоту изображения со знаком "минус", можно будет записать её "сверху вниз", но я не проверял, все ли понимают такую вариацию.

JPEG - убейте на месте, штука ужасающе хитрая, ну и сжимает с потерями. (да, есть lossless режим, но он ПРИНЦИПИАЛЬНО ДРУГОЙ, и тоже далеко не все его понимают)

Мой выбор - PNG, я с ним в своё время очень долго провозился, когда хотел написать свой собственный обработчик сканов книг (эх, когда-нибудь я его всё-таки доделаю!), поэтому знаю его как облупленного.

При том стандарт довольно-таки последовательный, не шибко перемудрёный, и сжимает БЕЗ ПОТЕРЬ. В случае фотографий или сканов, сжатие получается где-то в 2 раза - это не так впечатляет, как JPEG, но всё-таки подспорье. Но главное - ты знаешь, что данные были сохранены "как есть".

Начинается файл PNG с 8-байтного заголовка (signature):
 89  50  4e  47  0d  0a  1a  0a

(если в виде символов, то
\211   P   N   G  \r  \n \032 \n

)
Увидев этот заголовок, мы можем понять, что имеем дело с форматом PNG, а также убедиться, что никто не попытался "сменить ему кодировку" или преобразовать его в UTF-8 (о чём будет свидетельствовать 1-й байт, который не входит в стандартный ASCII), или преобразовать CR-LF в LF (или назад), о чём будут свидетельствовать 5-й, 6-й и 8-й байты. 7-й байт должен остановить вывод текста под "командной строкой", ибо дальше он совсем нечитаемый!

Далее у нас идёт набор блоков (Chunks). Их должно быть хотя бы 3: IHDR (Image HeaDeR), IDAT (Image DATa) и IEND (Image END), обязательно именно в таком порядке. Блоков IDAT может быть сколько угодно, следующих друг за другом, именно в них хранятся пиксели изображения в виде непрерывной строки байтов, ужатых с помощью ZLIB.

В начале каждого блока идёт 4 байта - беззнаковое целое число, указывающее размер этого блока в байтах, без учёта самих этих 4 байт, а также 4 байт имени блока и 4 байт CRC. К примеру, размер блока IEND - ровно 0 байт. Байты в этом числе идут от старшего к младшему. К примеру, длина 13 байт блока IHDR записывается так:
00 00 00 0d


Затем идёт 4 байта - имя блока. Собственно, IHDR, IDAT, IEND, есть и другие.

После этого начинаются полезные данные, хранящиеся в этом блоке и, наконец, 4 байта CRC.

CRC вычисляется для 4 байт имени блока и для полезных данных. Длина блока в вычисление CRC не попадает.

Модуль для вычисления CRC может "не догадываться" о существовании байтов, он имеет дело с последовательностью битов. Так вот, в стандарте PNG прописано подавать биты от младшего к старшему. Для нас это удобно - в UART тоже принято начинать с младших битов и заканчивать старшими, так что мы можем "прицепить" вход CRC прямо к выходу передатчика UART!

32-битный регистр CRC согласно того же стандарта надо инициализировать всеми единицами. Мотивация в том, что тогда мы сможем отличить последовательности нулей разной длины друг от друга, иначе мы можем случайно "пропустить ноль" и не заметить этого. Не уверен, что это шибко помогает, поскольку у нас в самом начале идёт заведомо ненулевая последовательность, например IDAT, но так уж повелось.

Наконец, полином, использующийся в CRC в формате PNG, таков:
x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1


По сути, вычислитель CRC находит остаток от деления гигантского полинома, каковым являются наши данные, на этот полином (многочлен). Т.е наши 32 бита - это коэффициенты при x^31, x^30, ... , 1.

Но взять и записать результат было бы слишком просто - дальше его нужно инвертировать (честно говоря, не вполне понимаю мотивацию. Типа, отыграть назад те единицы, которыми мы это дело инициализировали) и выдать МЛАДШИМ БИТОМ (выражающим коэф. при 1) ВПЕРЁД!

Выглядит это всё страшно, но, как оказалось, есть несколько сайтов, которые генерируют verilog'овский модуль для CRC для заданного полинома и для заданной ширины входных данных. Например, вот:
http://outputlogic.com/?page_id=321

Поскольку мы уже "сериализуем" входные данные, отправляя их через UART по одному биту за раз, мы выбираем Data width = 1 (именно это даёт нам самый компактный код. Не самый быстрый, но при UART'е спешить нам вообще некуда!).

Polynomial width выбираем 32 (это имеется в виду количество коэффициентов полинома остатка. Тот полином, что мы привели выше, имеет ширину 33, но самый старший коэффициент всегда единичный, и о нём принятно забывать!).

Жмём apply и переходим к шагу 2. Ставим галочки напротив нужных нам степеней и не волнуемся, что тут нет x^32 - он по умолчанию присутствует, иначе остаток от деления получится совсем "жиденьким". Наконец, жмём generate verilog - и получаем такую штуку:

//-----------------------------------------------------------------------------
// 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[0: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 crc(
  input [0: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[31] ^ data_in[0];
    lfsr_c[1] = lfsr_q[0] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[2] = lfsr_q[1] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[3] = lfsr_q[2];
    lfsr_c[4] = lfsr_q[3] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[5] = lfsr_q[4] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[6] = lfsr_q[5];
    lfsr_c[7] = lfsr_q[6] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[8] = lfsr_q[7] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[9] = lfsr_q[8];
    lfsr_c[10] = lfsr_q[9] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[11] = lfsr_q[10] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[12] = lfsr_q[11] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[13] = lfsr_q[12];
    lfsr_c[14] = lfsr_q[13];
    lfsr_c[15] = lfsr_q[14];
    lfsr_c[16] = lfsr_q[15] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[17] = lfsr_q[16];
    lfsr_c[18] = lfsr_q[17];
    lfsr_c[19] = lfsr_q[18];
    lfsr_c[20] = lfsr_q[19];
    lfsr_c[21] = lfsr_q[20];
    lfsr_c[22] = lfsr_q[21] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[23] = lfsr_q[22] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[24] = lfsr_q[23];
    lfsr_c[25] = lfsr_q[24];
    lfsr_c[26] = lfsr_q[25] ^ lfsr_q[31] ^ data_in[0];
    lfsr_c[27] = lfsr_q[26];
    lfsr_c[28] = lfsr_q[27];
    lfsr_c[29] = lfsr_q[28];
    lfsr_c[30] = lfsr_q[29];
    lfsr_c[31] = lfsr_q[30];

  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


Если приглядеться, это почти что регистр циклического сдвига, но с дополнительными "обратными связями". Синтезируется очень здорово всего в 32 ЛЭ - меньше попросту невозможно! Также мы замечаем, что наш регистр инициализируется всеми единицами - ровно это нам и надо.

Но вот сброс здесь использован асинхронный - мне как-то спокойнее жить с синхронными, из-за панического страха метастабильности.

И снова у нас "параллельный" выход шириной 32 бита - куда же мы их денем???

Нет, у нас вход UART-передатчика имеет ширину 8 бит, именно по 8 бит за раз мы и хотим получать. Разумеется, можно было бы поставить сдвиговый регистр или мультиплексор "снаружи", но ведь CRC - это УЖЕ регистр циклического сдвига! Надо только напомнить ему об этом:

//-----------------------------------------------------------------------------
// 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[0: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_by_output_logic(
  input data_in,
  input crc_en,
  input just_shift,
  output [7:0] CRC_byte,
  input rst,
  input clk);

	wire d = (~just_shift) & (data_in ^ CRC[31]);
	
	reg [31:0] CRC;
	
	assign CRC_byte = CRC[7:0];
	
  always @(posedge clk) begin
    if (rst) begin
      CRC <= {32{1'b1}};
    end
    else if (crc_en | just_shift) begin
		CRC[0] <= CRC[31] ^ (data_in & (~just_shift));
		CRC[1] <= CRC[0] ^ d;
		CRC[2] <= CRC[1] ^ d;
		CRC[3] <= CRC[2];
		CRC[4] <= CRC[3] ^ d;
		CRC[5] <= CRC[4] ^ d;
		CRC[6] <= CRC[5];
		CRC[7] <= CRC[6] ^ d;
		CRC[8] <= CRC[7] ^ d;
		CRC[9] <= CRC[8];
		CRC[10] <= CRC[9] ^ d;
		CRC[11] <= CRC[10] ^ d;
		CRC[12] <= CRC[11] ^ d;
		CRC[13] <= CRC[12];
		CRC[14] <= CRC[13];
		CRC[15] <= CRC[14];
		CRC[16] <= CRC[15] ^ d;
		CRC[17] <= CRC[16];
		CRC[18] <= CRC[17];
		CRC[19] <= CRC[18];
		CRC[20] <= CRC[19];
		CRC[21] <= CRC[20];
		CRC[22] <= CRC[21] ^ d;
		CRC[23] <= CRC[22] ^ d;
		CRC[24] <= CRC[23];
		CRC[25] <= CRC[24];
		CRC[26] <= CRC[25] ^ d;
		CRC[27] <= CRC[26];
		CRC[28] <= CRC[27];
		CRC[29] <= CRC[28];
		CRC[30] <= CRC[29];
		CRC[31] <= CRC[30];
    end
  end // always
endmodule // crc


Здесь у нас синхронный сброс, а ещё появился вход just_shift - когда он задействован, модуль перестаёт вычислять CRC, вместо этого он "катает данные на карусели" - сдвигает их циклически влево на 1 шаг за каждый такт clk (вход crc_en в этом режиме игнорируется). При этом задействованные ресурсы практически не поменялись - теперь модуль занимает 35 ЛЭ.

Увы, стандарт PNG подложил нам небольшую свинку - правило выдавать данные "младшим битом вперёд" означает - нам следовало бы сдвигать данные вправо, а наш регистр умеет работать только влево. Добавить в него функцию сдвига вправо будет означать удвоение ЛЭ, тогда уж проще поставить внешний сдвиговый регистр.

Но можно не беспокоится - циклический сдвиг влево на 24 позиции - это то же самое, что сдвиг вправо на 8 позиций. В прямом смысле "через задницу", но работает.

На этом свинья не заканчивается - этот младший байт нам нужно "зеркально отразить", и с этим в verilog'e, как ни странно, есть проблемы. Мне казалось, что я могу написать что-то типа
assign CRC_byte = CRC[0:7]; 


оказалось - не могу, ругается на обратное направление. Так что переправлять надо либо ручками, либо чуточку это "автоматизировать" с помощью цикла for (он работает только внутри always-блока) либо, для комбинаторной логики - с помощью generate / genvar / endgenerate.

Для 8 бит мне было проще (и нагляднее) сделать инверсию "ручками":
//module for transmitting PNG images over UART or another serial protocol.
//To be sensible to series of zeros, it was decided to first initialize CRC with all ones,
//then invert final value once again.
//that's what we do here. Seems like most 'comfortable' place for this operation.
//not to 'overload' CRC module.

module Data_or_CRC_MUX (input [7:0] Data, input [7:0] CRC, input ChooseCRC, output [7:0] Q);

wire [7:0] CRCrev;

	assign CRCrev[0] = CRC[7];
	assign CRCrev[1] = CRC[6];
	assign CRCrev[2] = CRC[5];
	assign CRCrev[3] = CRC[4];
	assign CRCrev[4] = CRC[3];
	assign CRCrev[5] = CRC[2];
	assign CRCrev[6] = CRC[1];
	assign CRCrev[7] = CRC[0];


assign Q = ChooseCRC? ~CRCrev : Data;

endmodule


Как видно, всё через одно место - нужно и отрицание сделать, и поменять порядок следования битов. Эти операции мы запихнули в мультиплексор, который позволяет передавать через UART как байты из памяти, так и только что "на лету" сгенерированный CRC. Этот модуль совсем маленький: всего 8 ЛЭ.


Очень сумбурный пост получился - после нескольких дней мучений у меня наконец-то стали сходиться эти значения, не мог не поделиться радостью.

В следующий раз соберём передатчик PNG-изображений.
Tags: ПЛИС, работа, странные девайсы
Subscribe

  • Так ли страшно 0,99969 вместо 1?

    В размышлениях о DMA, о возможных последствиях "смешивания" старых и новых значений при выдаче целевой информации, опять выполз вопрос: насколько…

  • Как продлить агонию велотрансмиссии на 1500+ км

    Последний раз о велосипедных делах отчитывался в середине мая, когда прошёл год "велопробегом по коронавирусу". Уже тогда я "жаловался", что…

  • DMA для QuatCore

    Вот фрагмент схемы нашего "процессорного ядра" QuatCore: Справа сверху "притаилась" оперативная память. На той ПЛИС, что у меня есть сейчас…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments