Умови участі та терміни проведення.
Важливе зауваження. не обов'язково робити обидві програми. Якщо ви зробили тільки одну, або навіть половину програми - надсилайте вийшло нам, ми розберемося.
Очний тур і нагородження переможців.
Переможці та лауреати будуть нагороджені цінними призами та красивими грамотами.
Завдання 1. HDLC-фреймер.
Для передачі даних по синхронним каналам зв'язку часто використовується HDLC-подібна структура пересилаються пакетів, званих кадрами. Потік кадрів є бітовим потоком, оскільки передані дані інтерпретуються на рівні окремих бітів.
Домовимося про наступні термінах: дані - це інформація, призначена для передачі між двома точками і розділена на логічні блоки, розмір яких кратний восьми бітам; кадр - сукупність блоку даних і його контрольної суми; пакет - кадр, над яким проведена операція стаффинга.
HDLC-потік влаштований таким чином:- Дані передаються блоками, кратними восьми бітам, тобто розмір в байтах блоку даних є цілим числом.
- Молодший (самий правий в двійковій запису) біт окремого байта йде в потоці першим, старший (самий лівий) - останнім.
- Пакети відокремлюються одна від одної восьмибитового послідовністю 0111 1110 (0x7E). Ця ж послідовність передається в разі відсутності корисних даних для передачі.
- Оскільки в самому потоці даних може зустрітися послідовність 0111 1110, то в процесі формування пакету проводиться операція, яка називається Стаффінг (stuffing): після передачі п'яти одиничних біт поспіль в потік додається нульовий біт. Таким чином, через процедури стаффинга розмір переданого пакета може ставати некратними восьми бітам.
- На приймачі виробляється зворотна операція - дестаффінг (destuffing): нульовий біт, що йде після п'яти одиничних, ігнорується. Завдяки цим двом операціям всередині переданого пакета не може зустрітися байт 0x7E.
- Для контролю цілісності даних, тобто виявлення неправильно переданих пакетів, до даних додається контрольна сума CRC16-CCITT, породжувана полиномом, правда, з деякою модифікацією, яку ми розглянемо нижче.
На передавачі спочатку проводиться розрахунок контрольної суми потоку даних, потім вона дописується до потоку даних. В результаті цього з блоку даних утворюється кадр. Над кадром відбувається операція стаффинга: кадр перетворюється в пакет. У лінії пакети відокремлюються одна від одної одним або більше байтами 0x7E.
Приймач ділить потік бітів з лінії на пакети, виробляє операцію дестаффінга, отримуючи кадри. Потім розділяє кадр на блок даних і передану контрольну суму, розраховує контрольну суму блоку даних і здійснює порівняння двох контрольних сум.
Потік даних розглядається як поліном: якщо якийсь біт дорівнює нулю, то коефіцієнт перед відповідним ступенем в поліномі - 0, якщо біт дорівнює одиниці, то коефіцієнт - одиниця. Наприклад, потік з 17 бітів +10001000000100001 еквівалентний породжує полиному. Підрахунок контрольної суми (CRC, Cyclical Redundancy Code) заснований на знаходженні залишку від ділення полінома даних на породжує поліном. Залишок - це поліном, який, будучи розглянуто як бітова послідовність, і є контрольною сумою. Розподіл полиномов відбувається по модулю два, тобто звичайна операція віднімання замінюється двійковим відніманням (або складанням - це все одно) без переносу або позику.
Контрольна сума даних виходить так:- Передані дані записуються по порядку їх передачі в лінію: найперший біт зліва, найостанніший - справа. До цієї послідовності ми додаємо праворуч 16 нулів, що еквівалентно множенню відповідного полінома на, і ділимо отриманий поліном на який породжує. Отримуємо перший залишок від ділення.
- Записуємо 16 одиниць і дописуємо справа стільки нулів, скільки біт займають передані дані. Ділимо вийшло на породжує поліном, отримуючи другий залишок.
- Складаємо по модулю 2 обидва залишку і число 0xFFFF. Результат і є контрольною сумою пакета, він займає 16 біт і дописується в кінець переданого пакета.
Нехай ми хочемо передати блок даних, що складається з байта 0x30 (це ASCII-код символу 0). У бітовому вигляді пакет виглядає як 0000 1100. Порахуємо контрольну суму: допишемо 16 нулів - 0000 1100 0000 0000 0000 0000 і поділимо на породжує поліном:
Залишок від ділення дорівнює 1100 0001 1000 1100. Тепер візьмемо 16 одиниць і 8 нулів (довжина даних) - 1111 1111 1111 1111 0000 0000. Другий залишок дорівнює 1110 0001 1111 0000. Результат складання по модулю два залишків і числа 0xFFFF дорівнює 1101 1111 1000 0011 . Це і є контрольна сума, яка дорівнює 0xC1FB, якщо повернутися до звичного порядку бітів.
З урахуванням контрольної суми кадр виходить наступним: 0x30, 0xFB, 0xC1. Або в двійковому вигляді (найперший передається біт зліва) 0000 1100 11011111 1000 0011. Жирним виділено послідовність з п'яти одиничних бітів, до якої після проведення стаффинга додасться нульовий біт. Отже, пакет виглядає так: 0000 1100 1101 1111 0100 0001 1. Повністю оформлений потік бітів матиме такий вигляд: 0111 1110 0000 1100 1101 1111 0100 0001 1011 1111 0. Це приклад ще раз демонструє, що розмір переданих даних не кратний одному байту.
Потрібно написати три програми: фреймер, дефреймер і емулятор фізичної лінії. Фреймер перетворює потік даних, що подається йому з деякого файлу, в HDLC-потік, що зберігається в іншому файлі. Довжина блоків даних, на які ділиться вихідний потік, задається з командного рядка двома параметрами: максимальним і мінімальним розміром блоку. При цьому розмір конкретного блоку повинен бути випадковою величиною, що знаходиться в заданому діапазоні. Пакети повинні розділятися будь-якою кількістю байтів-роздільників.
Дефреймер приймає потік бітів, що складається з HDLC-пакетів, і перетворює його в пакети даних. Потік бітів читається з одного файлу; дані записуються в інший файл. Бітовий потік не обов'язково починається з послідовності 0111 1110 - її ще необхідно знайти (синхронізувати з потоком); в потоці може перебувати будь-яку кількість пакетів; ніяких припущень про довжину кожного пакета не робиться. Необхідно виділити з потоку кожен пакет, підрахувати його контрольну суму, порівняти її з переданої разом з самим пакетом. Якщо сума правильна і розмір пакета кратний одному байту, то вміст пакета додається до вихідного файлу. якщо ж сума неправильна або розмір пакета не кратний байту, то друкуємо повідомлення про помилку і вміст неправильного пакета. Потім переходимо до обробки наступного пакета.
Емулятор фізичної лінії читає з одного файлу HDLC-потік, з певною ймовірністю інвертує довільні біти потоку (симулює перешкоди в лініях передачі), і записує отриманий потік у вихідний файл. Емулятор псує біти, обрані випадковим чином; відсоток інвертованих бітів є дійсним числом, що знаходяться на відрізку [0; 100], і задається параметром командного рядка емулятора.
Зауваження: в реальних лініях відсоток інвертованих бітів, при якому ще можлива синхронізація, - це величина порядку одного відсотка. Тому не слід очікувати, що при більш високому відсотку помилок в лінії ви зможете синхронізуватися з потоком і відновити дані. Однак, це не означає що емулятора завжди будуть передаватися числа менше одиниці.
Завдання 2. Генератор японських кросвордів.
Існує безліч різних типів кросвордів: звичайні, фінські, японські і т.д. На відміну від звичайних кросвордів, де потрібно відгадувати слова, в японському кросворді зашифровано зображення. Вам пропонується реалізувати програму, яка будує за відомим зображенню японський кросворд.
Сам кросворд вдає із себе прямокутну область, що складається з квадратів (клітинок), які можуть бути зафарбовані різними кольорами. Зверху кожного стовпчика і зліва від кожного рядка розташовані по порядку кілька чисел. Можливо, що ці числа пофарбовані в різні кольори, тоді кросворд називається кольоровим. Якщо колір чисел один, то кросворд чорно-білий. Самі числа є довжинами горизонтальних (для чисел зліва від рядка) і вертикальних (для чисел зверху від стовпця) блоків з квадратів, зафарбовані в відповідний колір. Серед всіх кольорів, присутніх в кросворді, один називається кольором фону; вертикальні або горизонтальні блоки даного кольору не враховуються при складанні кросворду. Суть кросворду полягає в тому, щоб вгадати де знаходяться блоки кольору фону і який у них розмір.
Для чорно-білого кросворду між блоків чорного кольору завжди присутній блок кольору фону. Для кольорових кросвордів такого обмеження немає. Проте, між блоками одного кольору завжди повинен знаходитися блок іншого кольору (можливо кольору фону). Блоки різного кольору можуть примикати один до одного впритул.
Числа, що знаходяться в рядках і стовпцях, не повинні суперечити один одному, тобто картинка повинні відновлюватися з цих чисел деяким чином.
Потрібно написати програму, якої на вхід подається картинка в форматі BMP. Картинка може бути чорно-білою або 16-кольоровий. Ваша програма повинна будувати по даній картинці вирішуване японський кросворд, якщо його можливо побудувати несуперечливим чином. Якщо картинка двоколірна, то колір фону білий, а числа фарбуються в чорний колір. Якщо ж картинка має 16 кольорів, то в програмі повинна бути передбачена можливість вибору кольору фону.
У разі неможливості побудови несуперечливого решаемого кросворду програма повинна інформувати про це користувача. Якщо кросворд будується, то він повинен бути визуализирован.
Ще раз звертаємо вашу увагу: кросворд має вирішуватися.