Обновить

Если вы знакомы с ISA-L, Jerasure, Leopard-RS, klauspost/reed-solomon, то полагаю пояснений к картинке выше не нужно, вот ссылка -- забирайте.

Ну а теперь некоторые пояснения: выше перечислены известные библиотеки, реализующие коды Рида-Соломона под CPU для задачи стирания, т.е. у вас есть k блоков, вы к ним добавляете еще n-k блоков и получаете право потерять любые n-k блоков изn, РС код позволит восстановить потерянное. РС код состоит из нескольких рутин с многочленами, реализация за \mathcal{O}(n^2) -- уровень сложного практического задания на курсе по вычислительной алгебре. В теории еще с 80-х годов было подозрение, что эти рутины можно полностью сделать на основе FFT, получить вычислительную сложность хотя бы \mathcal{O}(n\log^2k) и быстрый алгоритм на его основе. На практике с этим было много проблем, первая и по большому счету единственная практическая реализация со сложностью \mathcal{O}(n\log k) появилась в 2016 году в Leopard-RS на основе работы Лина-Чуна-Хана и соответствующего FFT-подобного преобразования (LCH transform). В этом году вышел обновленный алгоритм от авторов исходного подхода с улучшенным декодером, реализация доступна тут. Моя роль тут инженерная: я скрестил Leopard с XDRS, добавил GFNI, отполировал интерфейс и получил

  • Совместимый с Leopard РС код с произвольными параметрами (Leopard только поддерживает только 2k\geq n, у XDRS параметры должны быть степенями двойки)

  • Выделенные интерфейсы для LCH преобразования и затьюненные вычислительные ядра под AVX2 и GFNI

  • Ускорение по сравнению и с Leopard, и с XDRS

  • Единый воспроизводимый бенчмарк

Спасибо за внимание

Теги:
+3
Комментарии0

Записки из подполья незаконного архивирования фильмов

«Люди, видоизменяющие или уничтожающие художественные работы и наше культурное наследие ради прибылей или демонстрации власти — это варвары, и если законы США продолжат оправдывать такое поведение, то мы точно войдём в историю, как варварское общество.»

— Джордж Лукас, 1988 год

«Для меня её [оригинальной трилогии «Звёздных войн»] больше не существует. Я задумывал этот фильм именно так, и мне жаль, что вы увидели половину целого фильма и полюбили его.»

— Джордж Лукас, 2004 год

Ванкувер, 2011 год: мы с моей соседкой Виллой Росс сидим в одной из характерно стерильных монтажных студий Университета Саймона Фрейзера и уже не знаем, что делать: мы провели все выходные, ваяя из трёх разных копий вестерна Серджо Леоне 1966 года «Хороший, плохой, злой» одну версию — причём все три копии были незаконными рипами. В начале 2000-х этот фильм пал жертвой «реставрации», выполненной компанией MGM: вырезанные Серджо Леоне сцены были возвращены, увеличив время англоязычной версии с 161 до 179 минут; Клинт Иствуд и Илай Уоллак дублировали недостающие диалоги, а место умершего к тому времени Ли Ван Клифа занял похожий на него голосом дублёр. Монофоническая дорожка была переработана в многоканальный звук с неприятно современными звуками выстрелов. Почти десяток лет эта «дополненная» лента оставалась единственной продаваемой версией фильма; подобное очень часто происходит в эпоху ревизионистских студийных реставраций.

Наша цель была простой: спасти фильм от этой вивисекции. Мы планировали соединить звук уже не издававшегося DVD 1998 года (приблизительно похожий на звук международного релиза 1967 года) с видео из недавно привезённого Blu-ray итальянской версии. После того, как мы успешно преодолели многочисленные подводные камни, связанные с риппингом домашних видеозаписей конца 2000-х, наши надежды рухнули из-за катастрофического открытия: итальянская версия оказалась ещё сильнее отличающейся от международной, чем расширенная версия: печально известная сцена пытки была полностью перестроена, а у некоторых кадров отсутствовали начало и конец. Мы почти на десяток лет отказались от этой затеи.

Записки из подполья незаконного архивирования фильмов

Публикации